Submission #214503

---

Source Code Expand

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

Judge Result