Submission #202329

#TimeUsernameProblemLanguageResultExecution timeMemory
202329giorgikobCollecting Stamps 3 (JOI20_ho_t3)C++17
15 / 100
89 ms103544 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 1e6 + 69; int n,k,l,r,ans; ll dro,x,L; ll A[N],T[N]; ll dp[202][202][202][2]; int main(){ cin>>n>>L; for(int i=1;i<=n;i++){ cin>>A[i]; } A[n+1] = L; for(int i=1;i<=n;i++){ cin>>T[i]; } for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ for(int t=0;t<=1;t++) dp[i][j][k][t] = 1e18; } } } dp[0][0][0][1] = dp[0][0][0][0] = 0; for(int i=0;i<=n;i++){ for(int j=0;j<=n-i;j++){ for(int k=0;k<=i+j;k++){ x = dp[i][j][k][0]; if(x<1e18){ ans = max(k,ans); } dro = x + A[i+1] - A[i]; dp[i+1][j][k+(dro<=T[i+1])][0] = min(dp[i+1][j][k+(dro<=T[i+1])][0],dro); dro = x + A[n+1-j] - A[n-j] + A[i]; dp[i][j+1][k+(dro<=T[n-j])][1] = min(dp[i][j+1][k+(dro<=T[n-j])][1],dro); x = dp[i][j][k][1]; if(x<1e18){ ans = max(k,ans); } dro = x + A[i+1] + A[n+1] - A[n+1-j]; dp[i+1][j][k+(dro<=T[i+1])][0] = min(dp[i+1][j][k+(dro<=T[i+1])][0],dro); dro = x + A[n+1-j] - A[n-j]; dp[i][j+1][k+(dro<=T[n-j])][1] = min(dp[i][j+1][k+(dro<=T[n-j])][1],dro); } } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...