Submission #384636

#	Time	Username	Problem	Language	Result	Execution time	Memory
384636		dapig	Collecting Stamps 3 (JOI20_ho_t3)	Java	15 / 100	2129 ms	498216 KiB

ho_t3

import java.io.*;
import java.util.*;

// how this will work
// recursion: dp[l][r][#stamps][l/r endpoint? (0/1)] = min time
// dp[l][r][#stamps][l] = dp[l+1-->r][r][#stamps/#stamps-1][l/r]+dist(l/r point, this l)
// dp[l][r][#stamps][r] = dp[l][l-->r-1][#stamps/#stamps-1][l/r]+dist(l/r point, this r)
// base case: dp[0 (mid)][r] and dp[l][0 (mid)]

class ho_t3 {
	
	int ans = 0;

	public static void main(String[] args) throws IOException {

		ho_t3 obj = new ho_t3();

		obj.doStuff();

	}
	
	void process(int l, int r, int end) {
		if (vis[l][r][end]) return;
		vis[l][r][end] = true;
		if (l==r) {
			dp[l][l][0][end] = Math.abs(len-grid[l]);
			if (Math.abs(len-grid[l]) <= time[l])
				dp[l][l][1][end] = Math.abs(len-grid[l]);
		} else if (end == 0) {
			for (int i = l+1; i <= r; i++) {
				process(i, r, 0); process(i, r, 1);
				long distl = grid[i]-grid[l];
				long distr = grid[r]-grid[l];
				for (int j = 0; j < dp[0][0].length; j++) {
					if (dp[i][r][j][0]+distl <= time[l]) {
						if (j != dp[0][0].length-1)
							dp[l][r][j+1][0] = Math.min(dp[l][r][j+1][0],
									dp[i][r][j][0]+distl);
					} else
							dp[l][r][j][0] = Math.min(dp[l][r][j][0],
									dp[i][r][j][0]+distl);
					if (dp[i][r][j][1]+distr <= time[l]) {
						if (j != dp[0][0].length-1)
							dp[l][r][j+1][0] = Math.min(dp[l][r][j+1][0],
									dp[i][r][j][1]+distr);
					} else
							dp[l][r][j][0] = Math.min(dp[l][r][j][0],
									dp[i][r][j][1]+distr);
				}
				for (int j = dp[l][r].length-2; j >= 0; j--) {
					dp[l][r][j][0] = Math.min(dp[l][r][j][0],
							dp[l][r][j+1][0]);
				}
			}
		} else {
			for (int i = r-1; i >= l; i--) {
				process(l, i, 0); process(l, i, 1);
				long distl = grid[r]-grid[l];
				long distr = grid[r]-grid[i];
				for (int j = 0; j < dp[0][0].length; j++) {
					if (dp[l][i][j][0]+distl <= time[r]) {
						if (j != dp[0][0].length-1)
							dp[l][r][j+1][1] = Math.min(dp[l][r][j+1][1],
									dp[l][i][j][0]+distl);
					} else
							dp[l][r][j][1] = Math.min(dp[l][r][j][1],
									dp[l][i][j][0]+distl);
					if (dp[l][i][j][1]+distr <= time[r]) {
						if (j != dp[0][0].length-1)
							dp[l][r][j+1][1] = Math.min(dp[l][r][j+1][1],
									dp[l][i][j][1]+distr);
					} else
							dp[l][r][j][1] = Math.min(dp[l][r][j][1],
									dp[l][i][j][1]+distr);
				}
				for (int j = dp[l][r].length-2; j >= 0; j--) {
					dp[l][r][j][1] = Math.min(dp[l][r][j][1],
							dp[l][r][j+1][1]);
				}
			}
		}
		for (int i = 0; i < dp[0][0].length; i++) {
			if (dp[l][r][i][end] != (((long) Integer.MAX_VALUE)*3)) {
				ans = Math.max(ans, i);
			}
		}
	}

	int nums; long len;
	long[] grid, time;
	long[][][][] dp; // l r #stamps endpoint
	boolean[][][] vis;
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		nums = Integer.parseInt(st.nextToken());
		len = Integer.parseInt(st.nextToken());
		grid = new long[nums*2];
		time = new long[nums*2];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < nums; i++) {
			int val = Integer.parseInt(st.nextToken());
			grid[i] = val; grid[nums+i] = val+len;
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < nums; i++) {
			int val = Integer.parseInt(st.nextToken());
			time[i] = val; time[nums+i] = val;
		}
		br.close();

		dp = new long[grid.length][grid.length][nums+1][2];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				for (int k = 0; k < dp[0][0].length; k++) {
					for (int l = 0; l < dp[0][0][0].length; l++) {
						dp[i][j][k][l] = ((long) Integer.MAX_VALUE)*3;
					}
				}
			}
		}
		vis = new boolean[grid.length][grid.length][2];
		
		/*
		int sum = 0;
		for (int i = nums; i < grid.length; i++) {
			if (time[i] >= grid[i]-len) sum++;
			dp[nums][i][0] = new long[] {0, 0};
			for (int j = 1; j <= sum; j++) {
				dp[nums][i][j][1] = grid[i]-len;
				dp[nums][i][j][0] = (grid[i]-len)*2;
			}
			vis[nums][i] = new boolean[] {true, true};
		}
		sum = 0;
		for (int i = nums-1; i >= 0; i--) {
			if (time[i] >= len-grid[i]) sum++;
			dp[nums][i][0] = new long[] {0, 0};
			for (int j = 1; j <= sum; j++) {
				dp[i][nums-1][j][0] = len-grid[i];
				dp[i][nums-1][j][1] = (len-grid[i])*2;
			}
			vis[i][nums-1] = new boolean[] {true, true};
		}
		*/

		for (int i = 0; i <= nums; i++) {
			process(i, i+nums-1, 0);
			process(i, i+nums-1, 1);
		}
		System.out.println(ans);

	}

}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75