Submission #238535

#TimeUsernameProblemLanguageResultExecution timeMemory
238535PbezzFeast (NOI19_feast)C++14
51 / 100
1089 ms16768 KiB
#include <bits/stdc++.h> using namespace std; #define loop(i,n) for (ll i = 0; i < n; i++) #define ll long long #define INF 1e9+5 #define MAXN 300007 #define pb push_back #define mp make_pair typedef pair<ll,ll> pii; ll n,k; vector<ll>dp(MAXN);//de 1 a n ll arr[2005][2005][2]; ll siga(ll pos, ll left,bool maybe){ //retornar o best que posso fazer //usei até pos-1 if(pos==n+1)return 0; if(left==0)return 0; ll x; if(maybe)x=1; else x=0; if(arr[pos][left][x]!=-1){ return arr[pos][left][x]; } ll i,ret=0,k,gains; for(i=pos;i<=n;i++){//usar até i gains=dp[i]-dp[pos-1]; k = siga(i+1,left-1,true)+gains; ret=max(ret,k); if(maybe){ k = siga(i+1,left,false); ret=max(ret,k); } } arr[pos][left][x]=ret; return ret; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll i,ans,count=0,mini,x; cin>>n>>k; vector<ll>a(n+1); for(i=1;i<=n;i++){ cin>>a[i]; if(a[i]<0){count++; mini=i;} dp[i]=dp[i-1]+a[i]; } if(count==0){ ans=dp[n]; }else if(count==1){ if(k>=2)ans=dp[n]-a[mini]; else{ x=dp[n]-dp[mini]; ans=max(dp[n], max(dp[mini-1], x)); } }else if(k==1){//clássico maximum sum subarray ans=0; vector<ll>bruh(n+1); for(i=1;i<=n;i++){ bruh[i]=max(bruh[i-1],(ll int)0)+a[i]; ans=max(ans,bruh[i]); } }else{//bruteforce básico ll j; for(i=0;i<=n+1;i++){ for(j=0;j<=k+1;j++){ arr[i][j][0]=(ll)-1; arr[i][j][1]=(ll)-1; } } ans=siga(1,k,true); } printf("%lld\n",ans); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...