oj.uz

Submission #974940

# Submission time Handle Problem Language Result Execution time Memory
974940 2024-05-04T07:33:11 Z berr Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 8540 KB 
#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N=205, INF=1e18;
int dp[N][N][2][N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, L; cin >> n >> L;

    for(int i=0; i<=n; i++){
        for(int l=0; l<=n; l++){
            for(int j=0; j<2; j++){
                for(int x=0; x<=n; x++){
                    dp[i][l][j][x] = INF;
                }
            }
        }
    }    

    vector<int> x(n), t(n);
    for(auto &i: x) cin >> i;
    for(auto &i: t) cin >> i;


    dp[0][0][0][(t[0]>=min(x[0], L-x[0]))]=dp[0][0][1][(t[0]>=min(x[0], L-x[0]))]=min(x[0], L-x[0]);
    dp[n-1][n-1][0][(t[n-1]>=(min(x[n-1], L-x[n-1])))]=dp[n-1][n-1][1][(t[n-1]>=(min(x[n-1], L-x[n-1])))]=min(x[n-1], L-x[n-1]);

    auto val=[&](int a, int b){
        int dis;
        if(a==b) return INF;
        if(b<a) dis=x[b]+L-x[a];
        else dis=x[b]-x[a];

        if(a<b) dis=min(dis, x[a]+L-x[b]);
        else dis=min(dis, x[a]-x[b]);

        return dis;
    };
    auto m=[&](int a){
        if(a<0) a+=n; if(a>=n) a-=n;
        return a;
    };
    int ans=0;


    for(int i=0; i<n-1; i++){
        for(int l=0; l<n; l++){
            for(int j=0; j<2; j++){
                for(int x=0; x<n; x++){
                    int r=m(l+i);
                    int v=dp[l][r][j][x];
                    if(v==INF) continue;

                    ans=max(ans, x);

                    int dis=val((j==0?l:r), m(l-1));   
                    int nex=x+((v+dis)<=t[m(l-1)]);
                    ans=max(ans, nex);
                    dp[m(l-1)][r][0][nex]=min(dp[m(l-1)][r][0][nex], v+dis); 

                    dis=val((j==0?l:r), m(r+1));
                    nex=x+((v+dis)<=t[m(r+1)]);
                    ans=max(ans, nex);
                    dp[l][m(r+1)][1][nex]=min(dp[l][m(r+1)][1][nex], v+dis); 
                    

                        
                }
            }
        }
    }

    cout<<ans;
}

Compilation message

ho_t3.cpp: In lambda function:
ho_t3.cpp:43:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |         if(a<0) a+=n; if(a>=n) a-=n;
      |         ^~
ho_t3.cpp:43:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |         if(a<0) a+=n; if(a>=n) a-=n;
      |                       ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6604 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6604 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6604 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 6604 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Incorrect 1 ms 2512 KB Output isn't correct
12 Halted 0 ms 0 KB -