oj.uz

Submission #924000

# Submission time Handle Problem Language Result Execution time Memory
924000 2024-02-08T08:28:31 Z yeediot Collecting Stamps 3 (JOI20_ho_t3) C++14
5 / 100
 267 ms 424832 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=405;
int dp[mxn][mxn][mxn/2][2];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,l;
    cin>>n>>l;
    vector<pii>temp;
    vector<int>pos(2*n+1);
    vector<int>time(2*n+1);
    temp.pb({0,0});
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        temp.pb({x,0});
    }
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        temp[i+1].S=t;
    }
    sort(all(temp));
    for(int i=1;i<=n;i++){
        time[i]=time[i+n]=temp[i].S;
        pos[i]=temp[i].F;
        pos[i+n]=temp[i].F+l;
    }
    for(int i=0;i<=2*n;i++){
        for(int j=0;j<=2*n;j++){
            for(int k=0;k<=2*n;k++){
                dp[i][j][k][0]=dp[i][j][k][1]=1e15;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=2*n;i++){
        if(abs(pos[i]-l)<=time[i]){
            dp[i][i][1][0]=dp[i][i][1][1]=abs(pos[i]-l);
            ans=1;
        }
    }
    for(int k=2;k<=n;k++){
        for(int l=2*n;l>=1;l--){
            for(int r=l+k-1;r<=2*n;r++){
                if(l==r)continue;
                dp[l][r][k][0]=min(dp[l+1][r][k][0]+abs(pos[l]-pos[l+1]),
                                   dp[l+1][r][k][1]+abs(pos[l]-pos[r]));
                if(dp[l+1][r][k-1][0]+abs(pos[l]-pos[l+1])<=time[l])dp[l][r][k][0]=min(dp[l][r][k][0],dp[l+1][r][k-1][0]+abs(pos[l]-pos[l+1]));
                if(dp[l+1][r][k-1][1]+abs(pos[l]-pos[  r])<=time[l])dp[l][r][k][0]=min(dp[l][r][k][0],dp[l+1][r][k-1][1]+abs(pos[l]-pos[r]));
                dp[l][r][k][1]=min(dp[l][r-1][k][0]+abs(pos[r  ]-pos[l]),
                                   dp[l][r-1][k][1]+abs(pos[r-1]-pos[r]));
                if(dp[l][r-1][k-1][0]+abs(pos[l]-pos[  r])<=time[r])dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r-1][k-1][0]+abs(pos[l]-pos[r]));
                if(dp[l][r-1][k-1][1]+abs(pos[r-1]-pos[r])<=time[r])dp[l][r][k][1]=min(dp[l][r][k][1],dp[l][r-1][k-1][1]+abs(pos[r-1]-pos[r]));
                dp[l][r][k][0]=min(dp[l][r][k][0],(int)1e15);
                dp[l][r][k][1]=min(dp[l][r][k][1],(int)1e15);
                if(r-l+1<=n and (dp[l][r][k][0]<1e15 or dp[l][r][k][1]<1e15)){
                    ans=max(ans,k);
                }
                //cout<<l<<' '<<r<<' '<<k<<' '<<dp[l][r][k][0]<<' '<<dp[l][r][k][1]<<'\n';
            }
        }
    }
    cout<<ans<<'\n';
}
/*
dp[l][r][k][0/1] min time to collect k stamps between lth~rth stamp 0->ends at l 1->ends at r
dp[l][r][k][0]=if(dp[l+1][r][k-1][0]+x[l]-x[l-1]<=t[l])dp[l-1][r][k-1][0]+x[l]-x[l-1]
               if(dp[l+1][r][k-1][1]+x[l]-x[r]<=t[l])
               dp[l-1][r][k][0]+x[l]-x[l-1]
               dp[l-1][r][k][1]+x[l]-x[r]
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20824 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 4 ms 31180 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20824 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 4 ms 31180 KB Output is correct
18 Correct 6 ms 37468 KB Output is correct
19 Incorrect 3 ms 26972 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20824 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 4 ms 31180 KB Output is correct
18 Correct 267 ms 424832 KB Output is correct
19 Correct 111 ms 287824 KB Output is correct
20 Correct 57 ms 196660 KB Output is correct
21 Correct 103 ms 275652 KB Output is correct
22 Correct 142 ms 334228 KB Output is correct
23 Correct 45 ms 181084 KB Output is correct
24 Incorrect 35 ms 163408 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 16732 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20824 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 2 ms 18780 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 4 ms 31068 KB Output is correct
17 Correct 4 ms 31180 KB Output is correct
18 Correct 6 ms 37468 KB Output is correct
19 Incorrect 3 ms 26972 KB Output isn't correct
20 Halted 0 ms 0 KB -