Submission #646184

#TimeUsernameProblemLanguageResultExecution timeMemory
646184kith14Feast (NOI19_feast)C++17
51 / 100
1058 ms55252 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define pairll pair<ll,ll> #define lpairll pair<ll,pairll> #define repp(i,a,b) for (ll i = a; i <= b; i++) #define repz(i,a,b) for (ll i = a; i < b; i++) #define repm(i,a,b) for (ll i = a; i >= b; i--) #define fr first #define sc second #define x first #define y second #define mp make_pair #define pb push_back const ll N = 3e5+5, MOD = 1e9+7; ll tc = 1, n, m, ar[N], br[N], tot; string s, s1, s2, ye = "YA", no = "TIDAK"; void input(){ cin >> n >> m; repp(i,1,n){ cin >> ar[i]; tot += (ar[i] < 0); } } void t1(){ ll sum1 = 0, sum2 = 0, red = 0; repp(i,1,n){ if (ar[i] < 0) red = ar[i]; else{ if (red == 0) sum1 += ar[i]; else sum2 += ar[i]; } } if (m >= 2) cout << sum1+sum2 << endl; else cout << max(sum1,max(sum2,sum1+sum2+red)) << endl; exit(0); } void knd(){ ll ans = 0, cur = 0; repp(i,1,n){ cur += ar[i]; cur = max(cur,0LL); ans = max(ans,cur); } cout << ans << endl; exit(0); } void solve(){ if (tot <= 1) t1(); else if (m== 1) knd(); ll dp[n+5][m+5], prec[n+5][n+5]; repp(i,1,n){ ll cur = 0, maxi = 0; repp(j,i,n){ cur += ar[j]; maxi = max(maxi,cur); cur = max(0LL,cur); prec[i][j] = maxi; } } memset(dp,0,sizeof(dp)); repm(idx,n,1){ repp(rem,1,m){ dp[idx][rem] = dp[idx+1][rem]; repp(i,idx,n){ dp[idx][rem] = max(dp[idx][rem],prec[idx][i]+dp[i+1][rem-1]); } } } cout << dp[1][m] << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); //cin >> tc; while(tc--){ input(); solve(); } }
#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...