Submission #384644

#	Time	Username	Problem	Language	Result	Execution time	Memory
384644		dapig	Collecting Stamps 3 (JOI20_ho_t3)	C++98	15 / 100	2106 ms	405228 KiB

ho_t3

#include <cstdio>
#include <iostream> 
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <utility>

using namespace std;

int ans = 0;
bool vis[400][400][2];
long long dp[400][400][201][2];
long long grid[400];
long long stamptime[400];

	int nums; long long len;
    int dplen, dp0len, dp00len;
	
void findans(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] = abs(len-grid[l]);
			if (abs(len-grid[l]) <= stamptime[l])
				dp[l][l][1][end] = abs(len-grid[l]);
		} else if (end == 0) {
			for (int i = l+1; i <= r; i++) {
				findans(i, r, 0); findans(i, r, 1);
				long distl = grid[i]-grid[l];
				long distr = grid[r]-grid[l];
				for (int j = 0; j < dp00len; j++) {
					if (dp[i][r][j][0]+distl <= stamptime[l]) {
						if (j != dp00len-1)
							dp[l][r][j+1][0] = min(dp[l][r][j+1][0],
									dp[i][r][j][0]+distl);
					} else
							dp[l][r][j][0] = min(dp[l][r][j][0],
									dp[i][r][j][0]+distl);
					if (dp[i][r][j][1]+distr <= stamptime[l]) {
						if (j != dp00len-1)
							dp[l][r][j+1][0] = min(dp[l][r][j+1][0],
									dp[i][r][j][1]+distr);
					} else
							dp[l][r][j][0] = min(dp[l][r][j][0],
									dp[i][r][j][1]+distr);
				}
				for (int j = dp00len-2; j >= 0; j--) {
					dp[l][r][j][0] = min(dp[l][r][j][0],
							dp[l][r][j+1][0]);
				}
			}
		} else {
			for (int i = r-1; i >= l; i--) {
				findans(l, i, 0); findans(l, i, 1);
				long distl = grid[r]-grid[l];
				long distr = grid[r]-grid[i];
				for (int j = 0; j < dp00len; j++) {
					if (dp[l][i][j][0]+distl <= stamptime[r]) {
						if (j != dp00len-1)
							dp[l][r][j+1][1] = min(dp[l][r][j+1][1],
									dp[l][i][j][0]+distl);
					} else
							dp[l][r][j][1] = min(dp[l][r][j][1],
									dp[l][i][j][0]+distl);
					if (dp[l][i][j][1]+distr <= stamptime[r]) {
						if (j != dp00len-1)
							dp[l][r][j+1][1] = min(dp[l][r][j+1][1],
									dp[l][i][j][1]+distr);
					} else
							dp[l][r][j][1] = min(dp[l][r][j][1],
									dp[l][i][j][1]+distr);
				}
				for (int j = dp00len-2; j >= 0; j--) {
					dp[l][r][j][1] = min(dp[l][r][j][1],
							dp[l][r][j+1][1]);
				}
			}
		}
		for (int i = 0; i < dp00len; i++) {
			if (dp[l][r][i][end] != (((long long) 2*1e9)*3)) {
				ans = max(ans, i);
			}
		}
	}

	int main() {

		cin >> nums >> len;
        dplen = nums*2; dp0len = nums*2; dp00len = nums+1;
		for (int i = 0; i < nums; i++) {
			int val; cin >> val;
			grid[i] = val; grid[nums+i] = val+len;
		}
		for (int i = 0; i < nums; i++) {
			int val; cin >> val;
			stamptime[i] = val; stamptime[nums+i] = val;
		}

		for (int i = 0; i < dplen; i++) {
			for (int j = 0; j < dp0len; j++) {
				for (int k = 0; k < dp00len; k++) {
					for (int l = 0; l < 2; l++) {
						dp[i][j][k][l] = ((long long) 2*1e9)*3;
					}
				}
			}
		}
		
		/*
		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++) {
			findans(i, i+nums-1, 0);
			findans(i, i+nums-1, 1);
		}
		cout << (ans) << "\n";

	}

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