# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
638336 |
2022-09-05T12:44:09 Z |
shmad |
Feast (NOI19_feast) |
C++17 |
|
160 ms |
15308 KB |
#pragma GCC optimize("O3", "unroll-loops") // "Ofast"
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
#include <bits/stdc++.h>
#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using vvt = vt< vt<int> >;
const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;
int n, k;
ll l[N], r[N];
ll a[N], b[N];
void solve () {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int m = 0;
for (int i = 1; i <= n; i++) {
if (i == 1) {
b[++m] = a[i];
continue;
}
if ((a[i] > 0 && b[m] > 0) || (a[i] < 0 && b[m] < 0)) b[m] += a[i];
else b[++m] = a[i];
}
if (b[m] < 0) b[m--] = 0;
multiset<pii> s;
int cnt = 0;
for (int i = 1; i <= m; i++) {
s.insert({abs(b[i]), i});
l[i] = i - 1;
r[i] = i + 1;
cnt += (b[i] > 0);
}
while (cnt > k) {
pii v = *s.begin();
s.erase(s.begin());
ll i = v.ss;
if (b[i] > 0) cnt--;
if (l[i] != 0) {
if (b[l[i]] > 0) cnt--;
s.erase({abs(b[l[i]]), l[i]});
b[i] += b[l[i]];
if (l[l[i]] != 0) r[l[l[i]]] = i;
}
if (r[i] != m + 1) {
if (b[r[i]] > 0) cnt--;
s.erase({abs(b[r[i]]), r[i]});
b[i] += b[r[i]];
if (r[r[i]] != m + 1) l[r[r[i]]] = i;
}
b[l[i]] = b[r[i]] = 0;
l[i] = l[l[i]];
r[i] = r[r[i]];
if (b[i] > 0) {
s.insert({abs(b[i]), i});
cnt++;
continue;
}
if (l[i] == 0) l[r[i]] = b[i] = 0;
else if (r[i] == m + 1) r[l[i]] = m + 1, b[i] = 0;
}
ll ans = 0;
for (auto [val, i]: s) if (b[i] > 0) ans += b[i];
cout << ans;
cout << '\n';
}
bool testcases = 0;
signed main() {
#ifdef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
cin.tie(0) -> sync_with_stdio(0);
int test = 1;
if (testcases) cin >> test;
for (int cs = 1; cs <= test; cs++) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2516 KB |
Output is correct |
2 |
Correct |
27 ms |
2644 KB |
Output is correct |
3 |
Correct |
27 ms |
2708 KB |
Output is correct |
4 |
Correct |
26 ms |
2544 KB |
Output is correct |
5 |
Correct |
28 ms |
2628 KB |
Output is correct |
6 |
Correct |
26 ms |
2524 KB |
Output is correct |
7 |
Correct |
30 ms |
2504 KB |
Output is correct |
8 |
Correct |
30 ms |
2556 KB |
Output is correct |
9 |
Correct |
27 ms |
2564 KB |
Output is correct |
10 |
Correct |
26 ms |
2516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
2660 KB |
Output is correct |
2 |
Correct |
17 ms |
2676 KB |
Output is correct |
3 |
Correct |
18 ms |
2644 KB |
Output is correct |
4 |
Correct |
17 ms |
2704 KB |
Output is correct |
5 |
Correct |
27 ms |
2512 KB |
Output is correct |
6 |
Correct |
17 ms |
2664 KB |
Output is correct |
7 |
Correct |
18 ms |
2692 KB |
Output is correct |
8 |
Correct |
27 ms |
2596 KB |
Output is correct |
9 |
Correct |
26 ms |
2532 KB |
Output is correct |
10 |
Correct |
17 ms |
2620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
15308 KB |
Output is correct |
2 |
Incorrect |
152 ms |
15172 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2516 KB |
Output is correct |
2 |
Correct |
27 ms |
2644 KB |
Output is correct |
3 |
Correct |
27 ms |
2708 KB |
Output is correct |
4 |
Correct |
26 ms |
2544 KB |
Output is correct |
5 |
Correct |
28 ms |
2628 KB |
Output is correct |
6 |
Correct |
26 ms |
2524 KB |
Output is correct |
7 |
Correct |
30 ms |
2504 KB |
Output is correct |
8 |
Correct |
30 ms |
2556 KB |
Output is correct |
9 |
Correct |
27 ms |
2564 KB |
Output is correct |
10 |
Correct |
26 ms |
2516 KB |
Output is correct |
11 |
Correct |
17 ms |
2660 KB |
Output is correct |
12 |
Correct |
17 ms |
2676 KB |
Output is correct |
13 |
Correct |
18 ms |
2644 KB |
Output is correct |
14 |
Correct |
17 ms |
2704 KB |
Output is correct |
15 |
Correct |
27 ms |
2512 KB |
Output is correct |
16 |
Correct |
17 ms |
2664 KB |
Output is correct |
17 |
Correct |
18 ms |
2692 KB |
Output is correct |
18 |
Correct |
27 ms |
2596 KB |
Output is correct |
19 |
Correct |
26 ms |
2532 KB |
Output is correct |
20 |
Correct |
17 ms |
2620 KB |
Output is correct |
21 |
Correct |
160 ms |
15308 KB |
Output is correct |
22 |
Incorrect |
152 ms |
15172 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |