Submission #362294

#	Time	Username	Problem	Language	Result	Execution time	Memory
362294		Aryan_Raina	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	147 ms	132972 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define pos first
#define tim second
#define int long long int

const int INF = 1e18;
int32_t main() {
	int n, l;
	cin>>n>>l;
	vector<pair<int,int>> stamps(n+2);
	stamps[0] = {0,INF};
	for (int i = 1; i<=n; i++) cin>>stamps[i].pos;
	for (int i = 1; i<=n; i++) cin>>stamps[i].tim;
	stamps[n+1] = {l, INF};
	int ldp[n+5][n+5][n+5], rdp[n+5][n+5][n+5];
	// whenever we move if we are moving optimally we will cover a range L, R (taking some stamps)
	// ldp[L][R][i] - min time when covered L to R and we are at left end and taken i stamps
	// rdp[L][R][i] - same but we are at right end
	for (int i = 0; i <= n+1; i++) for (int j = 0; j <= n+1; j++) for (int k = 0; k <= n; k++) ldp[i][j][k] = rdp[i][j][k] = INF;
	ldp[0][n+1][0] = rdp[0][n+1][0] = 0; 

	for (int L = 0; L <= n; L++) {
		for (int R = n+1; R >= L+2; R--) {
			for (int k = 0; k <= n; k++) {
				// go L to L+1, go from R to L+1
				int tl = min(ldp[L][R][k]+stamps[L+1].pos-stamps[L].pos, rdp[L][R][k]+(l-stamps[R].pos)+stamps[L+1].pos);
				// go L to R-1, go from R to R-1
				int tr = min(ldp[L][R][k]+(l-stamps[R-1].pos)+stamps[L].pos, rdp[L][R][k]+stamps[R].pos-stamps[R-1].pos);
				// will we be able to take R-1 or L+1 stamp? check and update
				ldp[L+1][R][k+(tl<=stamps[L+1].tim)] = min(ldp[L+1][R][k+(tl<=stamps[L+1].tim)], tl);
				rdp[L][R-1][k+(tr<=stamps[R-1].tim)] = min(rdp[L][R-1][k+(tr<=stamps[R-1].tim)], tr);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= n+1; i++) {
		for (int j = 0; j <= n+1; j++) {
			for (int k = 0; k <= n; k++) {
				if (ldp[i][j][k] != INF || rdp[i][j][k] != INF) ans = max(ans, k);
			}
		}
	}
	cout<<ans;
}

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