Submission #1679665


Source Code Expand

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using static System.Console;
using static System.Math;
using static CS_Contest.Utils;
using System.Numerics;
using System.Linq.Expressions;

//using static CS_Contest.Library;

namespace CS_Contest {
	using Li = List<int>;
	using LLi = List<List<int>>;
	using Ll = List<long>;

	internal class Program {
		private static void Main(string[] args) {
			var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
			SetOut(sw);
			new Calc().Solve();
			Out.Flush();
		}
		

		public class Calc {

			public void Solve() {
				int N, H;
				ReadMulti(out N, out H);
				var read = ReadInts();
				int A = read[0], B = read[1], C = read[2], D = read[3], E = read[4];


				int target = H - N * E;
				if(target>0)
				{
					0.WL();
					return;
				}

				var Q = new Queue<G>();
				Q.Enqueue(new G(A,H+B));
				Q.Enqueue(new G(C, H + D));
				if(H-E>0)Q.Enqueue(new G(0, H - E));
				for(int i=0;i<N-1;i++)
				{
					var tmp = new Queue<G>();
					foreach (var item in Q)
					{
						if (item.V - E > 0) tmp.Enqueue(new G(item.Cost, item.V - E));
						tmp.Enqueue(new G(item.Cost + A, item.V + B));
						tmp.Enqueue(new G(item.Cost + C, item.V + D));
					}
					Q = tmp;
				}
				Q.Min(x => x.Cost).WL();

				return;
			}
			struct G
			{
				public int Cost { get; set; }
				public int V { get; set; }
				public G(int c,int v) { Cost = c;V = v; }
			}
		}
	}

	public static class Utils {
		public static int ModValue = (int)(1000000007);
		public static long INF = long.MaxValue;

		public static long Mod(long x) => x % ModValue;

		public static long ModPow(long x, long n) {
			long tmp = 1; while (n != 0) { if (n % 2 == 1) { tmp = Mod(tmp * x); } x = Mod(x * x); n /= 2; }
			return tmp;
		}

		public static long DivMod(long x, long y) => Mod(x * ModPow(y, (long)(1e9 + 5)));

		public static void WL(this object obj) => WriteLine(obj);

		public static void WL(this string obj) => WriteLine(obj);

		public static void WL<T>(this IEnumerable<T> list) => list.ToList().ForEach(x => x.WL());

		public static int ReadInt() => int.Parse(ReadLine());

		public static List<int> ReadInts(char s = ' ') => ReadLine().Split(s).Where(x => x != "").Select(int.Parse).ToList();

		public static long ReadLong() => long.Parse(ReadLine());

		public static List<long> ReadLongs(char s = ' ') => ReadLine().Split(s).Select(long.Parse).ToList();

		public static void ReadMulti(out int x, out int y) {
			var i = ReadInts(' ');
			x = i[0]; y = i[1];
		}

		public static void ReadMulti(out long x, out long y) {
			var i = ReadLongs(' ');
			x = i[0]; y = i[1];
		}

		public static void ReadMulti(out int x, out int y, out int z) {
			var i = ReadInts(' ');
			x = i[0]; y = i[1]; z = i[2];
		}

		public static void ReadMulti(out int x, out int y, out int z, out int v) {
			var i = ReadInts(' ');
			x = i[0]; y = i[1]; z = i[2]; v = i[3];
		}

		public static string StringJoin<T>(this IEnumerable<T> l, string separator = "") => string.Join(separator, l);

		public static long GCD(long m, long n) {
			long tmp;
			if (m < n) { tmp = n; n = m; m = tmp; }
			while (m % n != 0) {
				tmp = n;
				n = m % n;
				m = tmp;
			}
			return n;
		}

		public static long LCM(long m, long n) => m * (n / GCD(m, n));

		public static void REP(int n, Action<int> act) {
			for (var i = 0; i < n; i++) {
				act(i);
			}
		}

		public static void RREP(int n, Action<int> act) {
			for (var i = n - 1; i >= 0; i--) {
				act(i);
			}
		}



		public static int ManhattanDistance(int x1, int y1, int x2, int y2) => Abs(x2 - x1) + Abs(y2 - y1);

		public struct IndexT<T> {
			public T Value { get; set; }
			public int Index { get; set; }

			public IndexT(T v, int i) {
				Value = v; Index = i;
			}
			public override string ToString() {
				return Value + " " + Index;
			}
		}

		public static IEnumerable<IndexT<T>> ToIndexEnumerable<T>(this IEnumerable<T> list) => list.Select((x, i) => new IndexT<T>(x, i));

		public static Queue<T> ToQueue<T>(this IEnumerable<T> iEnumerable) {
			var rt = new Queue<T>();
			foreach (var item in iEnumerable) {
				rt.Enqueue(item);
			}
			return rt;
		}

		public static IndexT<T> IndexOf<T>(this IEnumerable<T> ie, Func<IndexT<T>, IndexT<T>, IndexT<T>> func) =>
			ie.ToIndexEnumerable().Aggregate(func);

		public static Tuple<TKey, TSource> ToTuple<TKey, TSource>(this KeyValuePair<TKey, TSource> kvp) => new Tuple<TKey, TSource>(kvp.Key, kvp.Value);

		public static IEnumerable<Tuple<TKey, TSource>> ToTupleList<TKey, TSource>(this Dictionary<TKey, TSource> d) => d.Select(_ => _.ToTuple());

		public static IEnumerable<T> When<T>(this IEnumerable<T> iEnumerable, Func<T, bool> condition, Func<T,T> filterFunc) {
			var rt = iEnumerable.ToArray();
			var index = 0;
			foreach (var item in iEnumerable) {
				rt[index] = condition(item) ? filterFunc(item) : item;
				index++;
			}
			return rt;
		}

		public static T[] Range<T>(int range,Func<int,T> func) {
			var rt = new T[range];
			for (var i = 0; i < range; i++) rt[i] = func(i);
			return rt;
		}
		public static void Swap<T>(ref T x,ref T y) {
			var tmp = x;
			x = y;
			y = tmp;
		}

		public static int Count<T>(this IEnumerable<T> l, T target) => l.Count(x => x.Equals(target));
	}
}

Submission Info

Submission Time
Task C - 節制
User xztaityozx
Language C# (Mono 4.6.2.0)
Score 10
Code Size 5512 Byte
Status WA
Exec Time 2126 ms
Memory 1051772 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 0 / 30 0 / 60 0 / 1
Status
AC × 25
AC × 10
TLE × 15
AC × 37
TLE × 49
AC × 37
WA × 6
TLE × 60
Set Name Test Cases
Subtask1 sample_1.txt, sample_2.txt, sample_3.txt, 01_010.txt, 01_011.txt, 01_020.txt, 01_021.txt, 01_100.txt, 01_101.txt, 01_110.txt, 01_111.txt, 01_200.txt, 01_201.txt, 01_220.txt, 01_221.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt, 01_random08.txt, 01_random09.txt, 01_random10.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, 02_010.txt, 02_011.txt, 02_020.txt, 02_021.txt, 02_100.txt, 02_101.txt, 02_110.txt, 02_111.txt, 02_200.txt, 02_201.txt, 02_220.txt, 02_221.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_random09.txt, 02_random10.txt
Subtask3 sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 01_010.txt, 01_011.txt, 01_020.txt, 01_021.txt, 01_100.txt, 01_101.txt, 01_110.txt, 01_111.txt, 01_200.txt, 01_201.txt, 01_220.txt, 01_221.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt, 01_random08.txt, 01_random09.txt, 01_random10.txt, 02_010.txt, 02_011.txt, 02_020.txt, 02_021.txt, 02_100.txt, 02_101.txt, 02_110.txt, 02_111.txt, 02_200.txt, 02_201.txt, 02_220.txt, 02_221.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_random09.txt, 02_random10.txt, 03_010.txt, 03_011.txt, 03_012.txt, 03_020.txt, 03_021.txt, 03_022.txt, 03_100.txt, 03_101.txt, 03_102.txt, 03_110.txt, 03_111.txt, 03_112.txt, 03_200.txt, 03_201.txt, 03_202.txt, 03_220.txt, 03_221.txt, 03_222.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt, 03_random16.txt, 03_random17.txt, 03_random18.txt, 03_random19.txt, 03_random20.txt
Subtask4 01_010.txt, 01_011.txt, 01_020.txt, 01_021.txt, 01_100.txt, 01_101.txt, 01_110.txt, 01_111.txt, 01_200.txt, 01_201.txt, 01_220.txt, 01_221.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt, 01_random08.txt, 01_random09.txt, 01_random10.txt, 02_010.txt, 02_011.txt, 02_020.txt, 02_021.txt, 02_100.txt, 02_101.txt, 02_110.txt, 02_111.txt, 02_200.txt, 02_201.txt, 02_220.txt, 02_221.txt, 02_random01.txt, 02_random02.txt, 02_random03.txt, 02_random04.txt, 02_random05.txt, 02_random06.txt, 02_random07.txt, 02_random08.txt, 02_random09.txt, 02_random10.txt, 03_010.txt, 03_011.txt, 03_012.txt, 03_020.txt, 03_021.txt, 03_022.txt, 03_100.txt, 03_101.txt, 03_102.txt, 03_110.txt, 03_111.txt, 03_112.txt, 03_200.txt, 03_201.txt, 03_202.txt, 03_220.txt, 03_221.txt, 03_222.txt, 03_random01.txt, 03_random02.txt, 03_random03.txt, 03_random04.txt, 03_random05.txt, 03_random06.txt, 03_random07.txt, 03_random08.txt, 03_random09.txt, 03_random10.txt, 03_random11.txt, 03_random12.txt, 03_random13.txt, 03_random14.txt, 03_random15.txt, 03_random16.txt, 03_random17.txt, 03_random18.txt, 03_random19.txt, 03_random20.txt, 04_010.txt, 04_011.txt, 04_020.txt, 04_021.txt, 04_100.txt, 04_101.txt, 04_110.txt, 04_111.txt, 04_200.txt, 04_201.txt, 04_220.txt, 04_221.txt, 04_random01.txt, 04_random02.txt, 04_random03.txt, 04_random04.txt, 04_random05.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
Case Name Status Exec Time Memory
01_010.txt AC 32 ms 11604 KB
01_011.txt AC 29 ms 11516 KB
01_020.txt AC 30 ms 9516 KB
01_021.txt AC 28 ms 11476 KB
01_100.txt AC 29 ms 11476 KB
01_101.txt AC 29 ms 9496 KB
01_110.txt AC 29 ms 11476 KB
01_111.txt AC 30 ms 13612 KB
01_200.txt AC 28 ms 9504 KB
01_201.txt AC 29 ms 11564 KB
01_220.txt AC 29 ms 9696 KB
01_221.txt AC 29 ms 11552 KB
01_random01.txt AC 26 ms 11476 KB
01_random02.txt AC 30 ms 9952 KB
01_random03.txt AC 27 ms 11476 KB
01_random04.txt AC 31 ms 13792 KB
01_random05.txt AC 29 ms 11476 KB
01_random06.txt AC 30 ms 11544 KB
01_random07.txt AC 25 ms 9428 KB
01_random08.txt AC 30 ms 11744 KB
01_random09.txt AC 31 ms 9568 KB
01_random10.txt AC 30 ms 11476 KB
02_010.txt TLE 2125 ms 892424 KB
02_011.txt TLE 2122 ms 933408 KB
02_020.txt AC 57 ms 23008 KB
02_021.txt TLE 2111 ms 881472 KB
02_100.txt TLE 2113 ms 905256 KB
02_101.txt AC 782 ms 193560 KB
02_110.txt AC 29 ms 11476 KB
02_111.txt TLE 2119 ms 964856 KB
02_200.txt TLE 2111 ms 875504 KB
02_201.txt TLE 2111 ms 766972 KB
02_220.txt AC 30 ms 9696 KB
02_221.txt TLE 2112 ms 887792 KB
02_random01.txt AC 307 ms 74288 KB
02_random02.txt TLE 2111 ms 830492 KB
02_random03.txt TLE 2110 ms 697372 KB
02_random04.txt TLE 2110 ms 668680 KB
02_random05.txt TLE 2111 ms 867312 KB
02_random06.txt AC 29 ms 11476 KB
02_random07.txt TLE 2112 ms 921760 KB
02_random08.txt AC 47 ms 18144 KB
02_random09.txt TLE 2111 ms 746496 KB
02_random10.txt TLE 2115 ms 787440 KB
03_010.txt TLE 2111 ms 865404 KB
03_011.txt TLE 2111 ms 742424 KB
03_012.txt TLE 2110 ms 777260 KB
03_020.txt TLE 2111 ms 779292 KB
03_021.txt TLE 2111 ms 805880 KB
03_022.txt TLE 2111 ms 762928 KB
03_100.txt TLE 2110 ms 758824 KB
03_101.txt TLE 2115 ms 871472 KB
03_102.txt TLE 2111 ms 873528 KB
03_110.txt TLE 2110 ms 742324 KB
03_111.txt TLE 2126 ms 1051772 KB
03_112.txt TLE 2111 ms 738408 KB
03_200.txt TLE 2110 ms 742340 KB
03_201.txt TLE 2111 ms 742404 KB
03_202.txt TLE 2110 ms 765036 KB
03_220.txt TLE 2123 ms 1049628 KB
03_221.txt TLE 2114 ms 740412 KB
03_222.txt TLE 2110 ms 742384 KB
03_random01.txt TLE 2111 ms 769064 KB
03_random02.txt AC 27 ms 9428 KB
03_random03.txt TLE 2111 ms 736308 KB
03_random04.txt TLE 2115 ms 998896 KB
03_random05.txt AC 27 ms 11476 KB
03_random06.txt TLE 2114 ms 742332 KB
03_random07.txt TLE 2111 ms 742424 KB
03_random08.txt TLE 2111 ms 742448 KB
03_random09.txt TLE 2111 ms 838704 KB
03_random10.txt AC 27 ms 11476 KB
03_random11.txt TLE 2111 ms 740336 KB
03_random12.txt TLE 2114 ms 744496 KB
03_random13.txt TLE 2111 ms 775268 KB
03_random14.txt TLE 2111 ms 742392 KB
03_random15.txt AC 29 ms 11476 KB
03_random16.txt TLE 2111 ms 881732 KB
03_random17.txt TLE 2111 ms 777228 KB
03_random18.txt TLE 2110 ms 723972 KB
03_random19.txt TLE 2110 ms 723992 KB
03_random20.txt AC 28 ms 9428 KB
04_010.txt WA 27 ms 9428 KB
04_011.txt TLE 2111 ms 731232 KB
04_020.txt TLE 2111 ms 822352 KB
04_021.txt WA 29 ms 9300 KB
04_100.txt TLE 2111 ms 742196 KB
04_101.txt TLE 2111 ms 740392 KB
04_110.txt TLE 2110 ms 730172 KB
04_111.txt TLE 2111 ms 724000 KB
04_200.txt TLE 2111 ms 732184 KB
04_201.txt TLE 2111 ms 739080 KB
04_220.txt TLE 2110 ms 744472 KB
04_221.txt TLE 2110 ms 846896 KB
04_random01.txt WA 29 ms 13524 KB
04_random02.txt WA 29 ms 11476 KB
04_random03.txt WA 27 ms 11476 KB
04_random04.txt WA 30 ms 9428 KB
04_random05.txt TLE 2119 ms 740408 KB
sample_1.txt AC 32 ms 11476 KB
sample_2.txt AC 32 ms 11584 KB
sample_3.txt AC 33 ms 9696 KB
sample_4.txt TLE 2111 ms 706556 KB