oj.uz

Submission #684527

# Submission time Handle Problem Language Result Execution time Memory
684527 2023-01-21T13:21:35 Z JooDdae Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;
int n, L, x[222], s[222], t[222];
ll dp[222][222][222][2];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> L;
    for(int i=1;i<=n;i++) cin >> x[i]; x[n+1] = L;
    for(int i=1;i<=n;i++) cin >> t[i];

    for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) dp[i][j][k][0] = dp[i][j][k][1] = INF;

    int ans = 0;
    dp[0][0][0][0] = 0; // L R 개수
    for(int l=1;l<=n;l++) {
        for(int i=-l;i<=0;i++) { // l = i, r = i+l
            int L = (n+1+i) % (n+1), R = i+l;

            for(int k=n;k>=0;k--) {
                auto &u = dp[L][R][k];

                if(L) {
                    auto &X = dp[(L+1)%(n+1)][R][k];
                    u[0] = min(u[0], X[0] + (x[L+1]-x[L]));
                    u[0] = min(u[0], X[1] + (x[n+1]-x[L]) + x[R]);
                }

                if(R) {
                    auto &X = dp[L][R-1][k];
                    u[1] = min(u[1], X[0] + (x[n+1]-x[L]) + x[R]);
                    u[1] = min(u[1], X[1] + (x[R]-x[R-1]));
                }

                if(u[0] <= t[L]) {
                    dp[L][R][k+1][0] = min(dp[L][R][k+1][0], u[0]);
                    ans = max(ans, k+1);
                }
                if(u[1] <= t[R]) {
                    dp[L][R][k+1][1] = min(dp[L][R][k+1][1], u[1]);
                    ans = max(ans, k+1);
                }
            }
        }
    }

    cout << ans;
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:12:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   12 |     for(int i=1;i<=n;i++) cin >> x[i]; x[n+1] = L;
      |     ^~~
ho_t3.cpp:12:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   12 |     for(int i=1;i<=n;i++) cin >> x[i]; x[n+1] = L;
      |                                        ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 75.0

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