| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1113195 | kzhi | Feast (NOI19_feast) | C++14 | 0 ms | 0 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.
/*
Author : kmv a.k.a kzhi
K41 IT CHV
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a ; i <= b; ++ i)
#define FOD(i,a,b) for (int i = a; i >= b; -- i)
#define BIT(mask,i) ((mask >> i) & 1)
#define MASK(i) (1ll << (i))
#define OFFBIT(mask,i) (mask &~(1ll<<(i)))
#define ONBIT(mask,i) (mask | (1ll << (i)))
#define lg2(x) (63 - __builtin_clzll(x))
#define c_bit __builtin_popcountll
#define vi vector < int >
#define all(a) a.begin(), a.end()
#define pb push_back
#define ii pair<int,int>
#define pll pair < ll, ll >
#define fi first
#define se second
#define openfile(TASK) if (fopen(TASK".inp","r"))\
{freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define endl '\n'
#define Faster ios_base::sync_with_stdio(false); \
cin.tie(0); cout.tie(0);
#define mid(l,r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1) | 1)
#define ci const int
template <class X, class Y> bool maximize(X &a, const Y &b){if(a < b) return a = b, true;return false;}
template <class X, class Y> bool minimize(X &a, const Y &b){if(a > b) return a = b, true;return false;}
const int N = 3e5 + 5;
const ll oo = 1e17 + 7;
const int LOG = lg2(N);
int n, k;
int a[N];
ll t[N];
ll sum(int l, int r){
if (l > r)
return 0;
return t[r] - t[l - 1];
}
bool ok1 = 1;
int cnt2 = 0, pos2 = -1;
namespace SUB1{
ll pt[N];
void SOLVE(){
pt[0] = oo;
ll res = - oo;
FOR (i, 1, n){
pt[i] = min(t[i], pt[i - 1]);
maximize(res, t[i] - pt[i - 1]);
maximize(res, t[i]);
}
maximize(res, 0ll);
cout << res;
}
}
namespace SUB6{
static const int maxN = 2e3 + 5;
ll dp[maxN][maxN][2];
ll sol(int i, int cnt, bool ok){
if (i == n + 1 || cnt == k + 1)
return 0;
if (dp[i][cnt][ok] != - oo)
return dp[i][cnt][ok];
ll cur = - oo;
if (!ok){
maximize(cur, sol(i + 1, cnt, 1) + a[i]);
maximize(cur, sol(i + 1, cnt, 0));
}
else{
maximize(cur, sol(i + 1, cnt, 1) + a[i]);
maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0ll));
}
return dp[i][cnt][ok] = cur;
}
void SOLVE(){
FOR (i, 0, maxN - 1)
FOR (j, 0, maxN - 1)
FOR (ok, 0, 1)
dp[i][j][ok] = - oo;
cout << sol(1, 1, 0);
}
}
namespace FULL {
pll dp[N][2];
bool check(int res) {
dp[0][0] = {0, 0}, dp[0][1] = {-inf, 0};
for (int i = 1; i <= n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] =
max(make_pair(dp[i - 1][1].fi + a[i], dp[i - 1][1].se),
make_pair(dp[i - 1][0].fi + a[i] - res, dp[i - 1][0].se + 1));
}
return max(dp[n][0], dp[n][1]).se >= k;
};
void SOLVE(){
ll l = 0, r = oo;
while (l + 1 < r){
ll mid = mid(l, r);
if(check(mid))
l = mid;
else
r = mid;
}
check(l);
cout << l * k + max(dp[n][0].fi, dp[n][1].fi);
}
}
void SOLVE(){
cin >> n >> k;
FOR (i, 1, n){
cin >> a[i];
t[i] = t[i - 1] + a[i];
if (a[i] < 0){
ok1 = 0;
cnt2 ++;
pos2 = i;
}
}
if (ok1){
cout << t[n];
return;
}
if (cnt2 == 1){
if (k >= 2)
cout << t[n] - a[pos2];
else
cout << max({t[n], sum(1, pos2 - 1), sum(pos2 + 1, n)});
return;
}
if (k == 1){
SUB1 :: SOLVE();
return;
}
if (n <= 2000 && k <= 2000){
SUB6 :: SOLVE();
return;
}
FULL :: SOLVE();
}
signed main(){
Faster
openfile("feast")
int q = 1;
// cin >> q;
while (q --){
SOLVE();
}
return 0;
}