| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1103146 | DuongKiet | Feast (NOI19_feast) | C++17 | 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.
#include <bits/stdc++.h>
#define N 300005
#define inf (long long) 1e17
#define ll long long
#define int long long
#define ii pair <int,long long>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const unsigned ll Mod = 1000000007LL;
int n, k, a[N];
void init(){
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
}
bool ifsub1(){
for (int i = 1; i <= n; i++)
if (a[i] < 0) return 0;
return 1;
}
void sub1(){
int ans = 0;
for (int i = 1; i <= n; i++)
ans += a[i];
cout << ans << '\n';
}
int pos;
bool ifsub2(){
int cnt = 0;
for (int i = 1; i <= n; i++)
if (a[i] < 0) {pos = a[i]; cnt++;}
return (cnt < 2);
}
void sub2(){
int sum = 0, suml = 0, am = 0;
bool kt = 0;
for (int i = 1; i <= n; i++){
if (a[i] < 0) {
kt = 1;
am = a[i];
}
if (!kt) suml += a[i];
sum += a[i];
}
if (k > 1)
cout << sum - am << '\n';
else cout << max(suml, max(sum, sum - suml - am));
}
void sub3(){
int ans = 0, res = 0;
for (int i = 1; i <= n; i++) {
res = max(0ll, res + a[i]);
ans = max(ans, res);
}
cout << ans << '\n';
}
//int pa[N], sz[N];
//int findpa(int u){
//
// if (u == pa[u]) return u;
// return pa[u] = findpa(pa[u]);
//}
//void Union(int a, int b){
//
// a = findpa(a);
// b = findpa(b);
// if (a == b) return;
// if (sz[a] < sz[b]) swap(a,b);
// pa[b] = a;
// sz[a] += sz[b];
// sum[a] += sum[b];
//}
//vector <ii> d;
//void Add(int u){
// d.pb({u, sum[u]});
//}
//void sub6(){
// for (int i = 1; i <= n; i++){
// pa[i] = i;
// sz[i] = 1;
// sum[i] = a[i];
// }
// int parduong, param;
// bool task = 0;
// if (a[1] >= 0) {parduong = 1; task = 1;}
// else param = 1;
// for (int i = 1; i <= n; i++){
// if (a[i] >= 0) {
// if (task)
// Union(parduong, i);
// else parduong = i;
// task = 1;
// }
// else {
// if (!task) Union(param, i);
// else param = i;
// task = 0;
// }
// }
// int curpa = findpa(1);
// Add(curpa);
// for (int i = 1; i <= n; i++){
// int u = findpa(i);
// if (u != curpa){
// curpa = u;
// Add(u);
// }
// }
// for (int i = 2; i < d.size(); i++){
// if (d[i].se > 0 && d[i-2].se > 0){
// g.pb({d[i].fi, d[i - 2].fi, d[i].se + d[i].se });
// }
// }
//}
pair<int, int> dp[N + 1][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(){
int l = 0, r = 1e14;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
int res = l;
check(res);
cout << res * k + max(dp[n][0].fi, dp[n][1]).fi));
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#define nametask "PRESUFF"
if(fopen(nametask".inp", "r")) {
freopen(nametask".inp", "r", stdin);
freopen(nametask".out", "w", stdout);
}
init();
// if (ifsub1()) return sub1(), 0;
// if (ifsub2()) return sub2(), 0;
// if (k == 1) return sub3(), 0;
// if (k <= n && n <= 2000) return sub6(), 0;
solve();
return 0;
}
/// Duong Anh Kiet from Kien Giang ///
/*
6 1
-1 -2 -1 2 -1 2
*/