Submission #69716

#TimeUsernameProblemLanguageResultExecution timeMemory
69716khohkoHomecoming (BOI18_homecoming)C++17
31 / 100
266 ms146380 KiB
#include<bits/stdc++.h> #include "homecoming.h" using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define ARRS ((ll)(4e6+100)) #define MAX ((ll)(1e12+100)) ll a[ARRS]; ll b[ARRS]; ll s[ARRS]; ll dp[ARRS][2]; ll sum(ll l,ll r){ return s[r]-s[l-1]; } long long solve(int n, int K, int *B, int *A){ ll pas=0,p=0; for(int i=1; i<=n; i++){ a[i]=A[i-1]; a[i+n]=A[i-1]; b[i]=B[i-1]; b[i+n]=B[i-1]; p-=a[i]; p+=b[i]; } for(int i=1; i<=2*n; i++)s[i]=s[i-1]+a[i]; pas=max(pas,p); vector<ll> ps; for(int i=0; i<n; i++) if(A[i]>=B[i])ps.pb(i); pair<ll,ll> mn={MAX,MAX}; ll es=0; for(int i=1; i<=2*n; i++){ //ll sm=0; //for(int j=i; j<=2*n; j++){ // sm-=a[j]-b[j]; es-=a[i]-b[i]; if(es>=0)es=0; mn=min(mn,{es,i-1}); // } } ll s=mn.sc; s++; s%=n; dp[0][0]=0; dp[0][1]=-MAX; for(int i=1; i<=n; i++){ dp[i][0]=dp[i-1][0]; dp[i][1]=-MAX; if(i>=K){ dp[i][1]=max(dp[i][1],dp[i-K][0]+b[i-K+1+s]-sum(i-K+1+s,i+s)); dp[i][1]=max(dp[i][1],dp[i-1][1]+b[i-K+1+s]-a[i+s]); } dp[i][0]=max(dp[i][0],dp[i][1]); //cout<<dp[i][0]<<" "<<dp[i][1]<<endl; } pas=max(pas,dp[n][0]); //cout<<endl; return pas; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...