Submission #923999

#TimeUsernameProblemLanguageResultExecution timeMemory
923999yeediotCollecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
5 ms31068 KiB
#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; } } } 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)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] */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...