# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1103236 | khoaha123 | Feast (NOI19_feast) | C++14 | 297 ms | 137544 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define endl '\n'
#define ii pair<int,int>
#define task "BANQUET"
#define all(x) x.begin(),x.end()
#define MASK(x) (1 << (x))
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int LOG = 20;
const int mod = 998244353;
const long long INF = 1e18;
int n,a[N],s[N];
int k;
void subtask1(void){
int sum = 0;
for (int i = 1; i <= n; ++i) sum += a[i];
cout << sum;
}
void subtask2(void){
int pos = -1;
for (int i = 1; i <= n; ++i){
if (a[i] < 0){
pos = i;break;
}
}
if (pos == -1){
subtask1();return;
}
int sum = 0;
for (int i = 1; i <= n; ++i) sum += a[i];
if (k == 1){
int sum1 = 0,sum2 = 0;
for (int i = 1; i < pos; ++i) sum1 += a[i];
for (int i = pos+1; i <= n; ++i) sum2 += a[i];
cout << max(sum1,max(sum2,sum));
}
else {
cout << max(sum,sum - a[pos]);
}
}
void subtask3(void){
int best = 0;
int sum = 0;
for (int i = 1; i <= n; ++i){
sum = max(a[i],sum + a[i]);
best = max(best,sum);
}
cout << best;
}
long long Rand(long long l, long long r) {
long long res = 0;
for (int i= 1; i <= 4; ++i) res = (res << 15) ^ (rand() & ((1 << 15) - 1));
return l + res % (r-l+1);
}
int f[2005][2005],g[2005][2005];
void subtask6(void){
int ans = 0;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= k; ++j){
f[i][j] = f[i-1][j] + a[i];
if (j >= 1) f[i][j] = max(f[i][j],g[i-1][j-1] + a[i]);
g[i][j] = max(g[i-1][j],f[i][j]);
ans = max(ans,g[i][j]);
}
}
cout << ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
freopen(task".OUT","w",stdout);
}
srand(time(NULL));
cin >> n >> k;
int sub1 = 0,am = 0;
for (int i = 1; i <= n; ++i){
cin >> a[i];
//a[i] = Rand(-1000000000,1000000000);
if (a[i] >= 0) sub1++;
else am++;
s[i] = s[i-1] + a[i];
}
if (sub1 == n){
subtask1();
return 0;
}
if (k == 1){
subtask3();
return 0;
}
if (am == 1){
subtask2();
return 0;
}
subtask6();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |