oj.uz

Submission #362292

# Submission time Handle Problem Language Result Execution time Memory
362292 2021-02-02T14:20:29 Z Aryan_Raina Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int INF = 1e15;
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+(tl<=stamps[R-1].tim)], tr);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -