Submission #214503


Source Code Expand

Copy
import java.io.BufferedInputStream;
import java.io.IOException;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
	//public static final int C = 1000000007;
	//static int map[][];
	//static int N;
	//static int M;
	//static int tic[][];
	//static int dp[][];
	static int a[][];
	static ArrayList<HashMap<Integer, Long>> al;
	

	public static void main(String[] args) {
		//StringBuilder sb = new StringBuilder();
		BufferedInputStream bs = new BufferedInputStream(System.in);
		Scanner sc = new Scanner(bs);

		int n = sc.nextInt();
		
		int h = sc.nextInt();

		
		a = new int[3][2];
		a[0][0] = sc.nextInt();
		a[0][1] = sc.nextInt();
		a[1][0] = sc.nextInt();
		a[1][1] = sc.nextInt();
		a[2][0] = 0;
		a[2][1] = -sc.nextInt();
		al = new ArrayList<HashMap<Integer,Long>>();
		for (int i=0; i < n; i++) {
			al.add(new HashMap<Integer, Long>());
		}
		/*dp = new int[n+1][-a[2][1]+1];
		 for (int i=0; i < n+1; i++) {
			 for (int t=0; t < -a[2][1]+1; t++) {
				 dp[i][t] = -1;
			 }
		 }*/
		//HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
		
		
		//int map[][] = new int[n][n];
		
		long ans = set(n, h);
		
		
		
		System.out.println(ans);
		
	}
	static long set(int n, long h) {
		if (n == 0) return 0;
		if (h >= -a[2][1] +1) return set(n-1, h + a[2][1]);
		if (al.get(n-1).containsKey((int)h)) return al.get(n-1).get((int)h);
		
		long m[] = new long[3];
		for (int i=0; i < 3; i++) {
			if (h + a[i][1] <= 0) {
				m[i] = Long.MAX_VALUE;
				continue;
			}
			m[i] = a[i][0] + set(n-1, h + a[i][1]);
		}
		long rtn =  Math.min(m[0], Math.min(m[1], m[2]));
		al.get(n-1).put((int)h, rtn);
		return rtn;
	}
	
}

Submission Info

Submission Time
Task C - 節制
User kiki33
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1784 Byte
Status TLE
Exec Time 2837 ms
Memory 589092 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 10 / 10 30 / 30 60 / 60 0 / 1
Status
AC × 25
AC × 25
AC × 86
AC × 83
TLE × 16
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
Case Name Status Exec Time Memory
01_010.txt AC 491 ms 22960 KB
01_011.txt AC 478 ms 22960 KB
01_020.txt AC 476 ms 22960 KB
01_021.txt AC 525 ms 23088 KB
01_100.txt AC 576 ms 22832 KB
01_101.txt AC 480 ms 23076 KB
01_110.txt AC 474 ms 22952 KB
01_111.txt AC 474 ms 22956 KB
01_200.txt AC 481 ms 23076 KB
01_201.txt AC 477 ms 23084 KB
01_220.txt AC 475 ms 23080 KB
01_221.txt AC 478 ms 23088 KB
01_random01.txt AC 482 ms 22828 KB
01_random02.txt AC 491 ms 22960 KB
01_random03.txt AC 489 ms 22960 KB
01_random04.txt AC 475 ms 22952 KB
01_random05.txt AC 478 ms 23056 KB
01_random06.txt AC 474 ms 22952 KB
01_random07.txt AC 481 ms 22828 KB
01_random08.txt AC 471 ms 22960 KB
01_random09.txt AC 487 ms 23080 KB
01_random10.txt AC 471 ms 23088 KB
02_010.txt AC 493 ms 22956 KB
02_011.txt AC 489 ms 23088 KB
02_020.txt AC 481 ms 23080 KB
02_021.txt AC 495 ms 23088 KB
02_100.txt AC 489 ms 23088 KB
02_101.txt AC 476 ms 23056 KB
02_110.txt AC 480 ms 23084 KB
02_111.txt AC 473 ms 22956 KB
02_200.txt AC 476 ms 23084 KB
02_201.txt AC 485 ms 23084 KB
02_220.txt AC 494 ms 23048 KB
02_221.txt AC 482 ms 22952 KB
02_random01.txt AC 479 ms 22960 KB
02_random02.txt AC 481 ms 22948 KB
02_random03.txt AC 471 ms 22960 KB
02_random04.txt AC 478 ms 22960 KB
02_random05.txt AC 475 ms 23036 KB
02_random06.txt AC 485 ms 23084 KB
02_random07.txt AC 479 ms 23080 KB
02_random08.txt AC 464 ms 22936 KB
02_random09.txt AC 473 ms 22952 KB
02_random10.txt AC 476 ms 23084 KB
03_010.txt AC 824 ms 49324 KB
03_011.txt AC 492 ms 23208 KB
03_012.txt AC 649 ms 39012 KB
03_020.txt AC 553 ms 28240 KB
03_021.txt AC 843 ms 52288 KB
03_022.txt AC 546 ms 25520 KB
03_100.txt AC 658 ms 42788 KB
03_101.txt AC 530 ms 25132 KB
03_102.txt AC 732 ms 45756 KB
03_110.txt AC 614 ms 34620 KB
03_111.txt AC 670 ms 37916 KB
03_112.txt AC 717 ms 42104 KB
03_200.txt AC 596 ms 31616 KB
03_201.txt AC 715 ms 45992 KB
03_202.txt AC 647 ms 37920 KB
03_220.txt AC 670 ms 37848 KB
03_221.txt AC 688 ms 42704 KB
03_222.txt AC 662 ms 37948 KB
03_random01.txt AC 622 ms 33340 KB
03_random02.txt AC 490 ms 22876 KB
03_random03.txt AC 592 ms 29012 KB
03_random04.txt AC 752 ms 45960 KB
03_random05.txt AC 477 ms 22832 KB
03_random06.txt AC 618 ms 31108 KB
03_random07.txt AC 495 ms 23900 KB
03_random08.txt AC 864 ms 52616 KB
03_random09.txt AC 746 ms 45556 KB
03_random10.txt AC 475 ms 22956 KB
03_random11.txt AC 628 ms 37832 KB
03_random12.txt AC 1161 ms 73880 KB
03_random13.txt AC 655 ms 38136 KB
03_random14.txt AC 673 ms 42516 KB
03_random15.txt AC 474 ms 22820 KB
03_random16.txt AC 853 ms 52528 KB
03_random17.txt AC 967 ms 52392 KB
03_random18.txt AC 516 ms 23232 KB
03_random19.txt AC 592 ms 29868 KB
03_random20.txt AC 492 ms 22824 KB
04_010.txt TLE 2491 ms 504712 KB
04_011.txt TLE 2453 ms 496720 KB
04_020.txt TLE 2420 ms 480988 KB
04_021.txt TLE 2573 ms 479332 KB
04_100.txt TLE 2573 ms 510708 KB
04_101.txt TLE 2737 ms 436012 KB
04_110.txt TLE 2094 ms 346000 KB
04_111.txt TLE 2077 ms 359800 KB
04_200.txt TLE 2055 ms 169668 KB
04_201.txt AC 590 ms 32304 KB
04_220.txt TLE 2058 ms 223740 KB
04_221.txt TLE 2688 ms 449312 KB
04_random01.txt TLE 2072 ms 139040 KB
04_random02.txt TLE 2101 ms 191068 KB
04_random03.txt TLE 2491 ms 307572 KB
04_random04.txt TLE 2837 ms 589092 KB
04_random05.txt TLE 2090 ms 224364 KB
sample_1.txt AC 479 ms 23088 KB
sample_2.txt AC 496 ms 22948 KB
sample_3.txt AC 497 ms 22960 KB
sample_4.txt AC 755 ms 41904 KB