Submission #332963

#TimeUsernameProblemLanguageResultExecution timeMemory
332963limabeansCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
363 ms135412 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl using ll = long long; const ll inf = 1e18; const int maxn = 205; ll n,l; ll x[maxn], t[maxn]; ll dp[maxn][maxn][2][maxn]; // left end, right end, which end?, taken // 0, 1,2,...,n // n+1 ll f(int l, int r, int p, int taken) { if (l<0 || l>n+1) return inf; if (r<0 || r>n+1) return inf; if (p<0) return inf; ll &res = dp[l][r][p][taken]; if (~res) return res; res = inf; // don't take if (p==0 && l>0) { res = min(res, f(l-1,r,0,taken)+(x[l]-x[l-1])); res = min(res, f(l-1,r,1,taken)+(x[n+1]-x[r])+x[l]); } if (p==1 && r<n+1) { res = min(res, f(l,r+1,1,taken)+(x[r+1]-x[r])); res = min(res, f(l,r+1,0,taken)+x[l]+(x[n+1]-x[r])); } // take if (taken>0) { ll tmp = -1; if (p==0 && l>0) { tmp = f(l-1,r,0,taken-1)+(x[l]-x[l-1]); if (tmp<=t[l]) { res = min(res, tmp); } tmp = f(l-1,r,1,taken-1)+(x[n+1]-x[r])+x[l]; if (tmp<=t[l]) { res = min(res, tmp); } } if (p==1 && r<n+1) { tmp = f(l,r+1,1,taken-1)+(x[r+1]-x[r]); if (tmp<=t[r]) { res = min(res, tmp); } tmp = f(l,r+1,0,taken-1)+(x[n+1]-x[r])+x[l]; if (tmp<=t[r]) { res = min(res, tmp); } } } return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>l; for (int i=1; i<=n; i++) { cin>>x[i]; } x[0] = 0; x[n+1] = l; for (int i=1; i<=n; i++) { cin>>t[i]; } int ans = 0; memset(dp,-1,sizeof(dp)); dp[0][n+1][0][0] = 0; dp[0][n+1][1][0] = 0; for (int x=0; x<n+1; x++) { for (int taken=1; taken<=n; taken++) { if (f(x,x+1,0,taken)<inf) ans = max(ans, taken); if (f(x,x+1,1,taken)<inf) ans = max(ans, taken); } } cout<<ans<<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...