# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244943 | maximath_1 | Collecting Stamps 3 (JOI20_ho_t3) | C++11 | 89 ms | 65280 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9 + 69;
int x[205], t[205], n, l, dp[205][205][205][2];
int main(){
scanf("%d%d", &n, &l);
for(int i = 1; i <= n; i ++) scanf("%d", &x[i]);
for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);
x[n + 1] = l;
for(int i = 0; i <= n; i ++) for(int j = 0; j <= n; j ++) for(int k = 0; k <= n; k ++) for(int a = 0; a < 2; a ++)
dp[i][j][k][a] = inf + 5;
dp[0][0][0][0] = 0;
for(int i = 0; i < n; i ++) for(int j = 0; i + j < n; j ++) for(int k = 0; k <= i + j; k ++){
int tim;
if(dp[i][j][k][0] < inf){
tim = dp[i][j][k][0] + x[i + 1] - x[i];
dp[i + 1][j][k + (t[i + 1] >= tim)][0] = min(dp[i + 1][j][k + (t[i + 1] >= tim)][0], tim);
tim = dp[i][j][k][0] + x[i] + l - x[n - j];
dp[i][j + 1][k + (t[n - j] >= tim)][1] = min(dp[i][j + 1][k + (t[n - j] >= tim)][1], tim);
}
if(dp[i][j][k][1] < inf){
tim = dp[i][j][k][1] + x[n - j + 1] - x[n -j];
dp[i][j + 1][k + (t[n - j] >= tim)][1] = min(dp[i][j + 1][k + (t[n - j] >= tim)][1], tim);
tim = dp[i][j][k][1] + l - x[n - j + 1] + x[i + 1];
dp[i + 1][j][k + (t[i + 1] >= tim)][0] = min(dp[i + 1][j][k + (t[i + 1] >= tim)][0], tim);
}
}
int ans = 0;
for(int i = 0; i <= n; i ++) for(int j = 0; i + j <= n; j ++) for(int k = 0; k <= i + j; k ++){
if(min(dp[i][j][k][0], dp[i][j][k][1]) < inf)
ans = max(ans, k);
}
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |