oj.uz

Submission #923998

# Submission time Handle Problem Language Result Execution time Memory
923998 2024-02-08T08:18:58 Z yeediot Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 6 ms 31068 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]=4e18;
            }
        }
    }
    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);
            //cout<<dp[i][i][1][0]<<'\n';
        }
    }
    int ans=0;
    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)4e18);
                dp[l][r][k][1]=min(dp[l][r][k][1],(int)4e18);
                if(r-l+1<=n and (dp[l][r][k][0]<4e18 or dp[l][r][k][1]<4e18)){
                    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20828 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 Incorrect 1 ms 4444 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20828 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 Incorrect 1 ms 4444 KB Output isn't correct
12 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 14772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20828 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 Incorrect 1 ms 4444 KB Output isn't correct
12 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 14772 KB Output is correct
3 Correct 6 ms 24924 KB Output is correct
4 Correct 2 ms 16732 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 2 ms 20828 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 Incorrect 1 ms 4444 KB Output isn't correct
12 Halted 0 ms 0 KB -