Submission #680915

#TimeUsernameProblemLanguageResultExecution timeMemory
680915uyluluCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
249 ms66892 KiB
#include <bits/stdc++.h> using namespace std; #define double long double // #define int long long #define endl "\n" const int N = 200 + 3,oo = 1e9 + 5; int dp[N + 1][N + 1][N + 1][2]; int x[N + 1],t[N + 1]; int n,len; int f(int l,int r,int cnt,int side) { if(l == n + 1 && r == 0) { if(cnt != 0) { return oo; } return 0; } // cout<<cnt<<endl; if(dp[l][r][cnt][side] != -1) return dp[l][r][cnt][side]; int res = oo; // cout<<l<<" "<<r<<" "<<cnt<<endl; if(side == 1) { if(r > 0) { res = min(res,f(l,r - 1,cnt,1) + (x[r] - x[r - 1])); res = min(res,f(l,r - 1,cnt,0) + (len - x[l]) + x[r]); } if(r > 0 && cnt > 0) { int tl = f(l,r - 1,cnt - 1,1); if(t[r] >= tl + (x[r] - x[r - 1])) { res = min(res,tl + x[r] - x[r - 1]); } tl = f(l,r - 1,cnt - 1,0); if(t[r] >= tl + (len - x[l]) + x[r]) { res = min(res,tl + (len - x[l]) + x[r]); } } return dp[l][r][cnt][side] = res; } else { if(l <= n) { res = min(res,f(l + 1,r,cnt,0) + abs(x[l] - x[l + 1])); res = min(res,f(l + 1,r,cnt,1) + (len - x[l]) + x[r]); } if(l <= n && cnt > 0) { int tl = f(l + 1,r,cnt - 1,0); if(t[l] >= tl + abs(x[l] - x[l + 1])) { res = min(res,tl + abs(x[l] - x[l + 1])); } tl = f(l + 1,r,cnt - 1,1); if(t[l] >= tl + (len - x[l]) + x[r]) { res = min(res,tl + (len - x[l]) + x[r]); } } return dp[l][r][cnt][side] = res; } return dp[l][r][cnt][side] = oo; } signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); memset(dp,-1,sizeof(dp)); cin>>n>>len; for(int i = 1;i <= n;i++) { cin>>x[i]; } for(int i = 1;i <= n;i++) { cin>>t[i]; } int res = 0; if(x[n] == len) { res++; n--; } x[0] = 0; x[n + 1] = len; int sum = 0; // cout<<f(0,4,7,1)<<endl; for(int i = 0;i <= n;i++) { for(int j = i + 1;j <= n + 1;j++) { for(int k = 0;k <= n;k++) { int asd = min(f(j,i,k,0),f(j,i,k,1)); if(asd < oo) { sum = max(sum,k); // cout<<j<<" "<<i<<" "<<k<<endl; } } } } cout<<res + sum<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...