Submission #238525

#TimeUsernameProblemLanguageResultExecution timeMemory
238525PbezzFeast (NOI19_feast)C++14
30 / 100
1090 ms8824 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 siga(ll pos, ll left){ //retornar o best que posso fazer //usei até pos-1 if(pos==n+1)return 0; if(left==0)return 0; ll i,ret=0,k,gains; k=siga(pos+1,left); ret=max(ret,k); for(i=pos+1;i<=n;i++){//usar até i gains=dp[i]-dp[pos-1]; k = siga(i+1,left-1)+gains; ret=max(ret,k); k = siga(i+1,left); ret=max(ret,k); } return ret; } int main(){ 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 ans=siga(1,k); } 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...