# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
638330 |
2022-09-05T12:11:55 Z |
shmad |
Feast (NOI19_feast) |
C++17 |
|
189 ms |
12140 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<int, int>;
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, 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);
}
r[m] = 0;
while (!s.empty() && cnt > k) {
pii v = *s.begin();
s.erase(s.begin());
int val = v.ff, i = v.ss;
if (b[i] > 0) cnt--;
if (l[i] != 0) {
s.erase({abs(b[l[i]]), l[i]});
if (b[l[i]] > 0) cnt--;
b[i] += b[l[i]];
l[i] = l[l[i]];
if (l[i] != 0) r[l[i]] = i;
}
if (r[i] != 0) {
s.erase({abs(b[r[i]]), r[i]});
if (b[r[i]] > 0) cnt--;
b[i] += b[r[i]];
r[i] = r[r[i]];
if (r[i] != 0) l[r[i]] = i;
}
if (b[i] > 0) {
s.insert({abs(b[i]), i});
cnt++;
continue;
}
if (l[i] == 0) l[r[i]] = 0;
else if (r[i] == 0) r[l[i]] = 0;
else s.insert({abs(b[i]), i});
}
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();
}
}
Compilation message
feast.cpp: In function 'void solve()':
feast.cpp:53:7: warning: unused variable 'val' [-Wunused-variable]
53 | int val = v.ff, i = v.ss;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
2852 KB |
Output is correct |
2 |
Correct |
32 ms |
5412 KB |
Output is correct |
3 |
Correct |
35 ms |
5576 KB |
Output is correct |
4 |
Correct |
35 ms |
5440 KB |
Output is correct |
5 |
Correct |
32 ms |
5452 KB |
Output is correct |
6 |
Correct |
36 ms |
5320 KB |
Output is correct |
7 |
Correct |
33 ms |
5324 KB |
Output is correct |
8 |
Correct |
29 ms |
5508 KB |
Output is correct |
9 |
Correct |
28 ms |
5352 KB |
Output is correct |
10 |
Correct |
36 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2924 KB |
Output is correct |
2 |
Correct |
24 ms |
3812 KB |
Output is correct |
3 |
Correct |
20 ms |
3736 KB |
Output is correct |
4 |
Correct |
19 ms |
3788 KB |
Output is correct |
5 |
Correct |
27 ms |
5324 KB |
Output is correct |
6 |
Correct |
18 ms |
3748 KB |
Output is correct |
7 |
Correct |
19 ms |
3800 KB |
Output is correct |
8 |
Correct |
29 ms |
5492 KB |
Output is correct |
9 |
Correct |
35 ms |
5388 KB |
Output is correct |
10 |
Correct |
18 ms |
3732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
189 ms |
12140 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
2852 KB |
Output is correct |
2 |
Correct |
32 ms |
5412 KB |
Output is correct |
3 |
Correct |
35 ms |
5576 KB |
Output is correct |
4 |
Correct |
35 ms |
5440 KB |
Output is correct |
5 |
Correct |
32 ms |
5452 KB |
Output is correct |
6 |
Correct |
36 ms |
5320 KB |
Output is correct |
7 |
Correct |
33 ms |
5324 KB |
Output is correct |
8 |
Correct |
29 ms |
5508 KB |
Output is correct |
9 |
Correct |
28 ms |
5352 KB |
Output is correct |
10 |
Correct |
36 ms |
5368 KB |
Output is correct |
11 |
Correct |
23 ms |
2924 KB |
Output is correct |
12 |
Correct |
24 ms |
3812 KB |
Output is correct |
13 |
Correct |
20 ms |
3736 KB |
Output is correct |
14 |
Correct |
19 ms |
3788 KB |
Output is correct |
15 |
Correct |
27 ms |
5324 KB |
Output is correct |
16 |
Correct |
18 ms |
3748 KB |
Output is correct |
17 |
Correct |
19 ms |
3800 KB |
Output is correct |
18 |
Correct |
29 ms |
5492 KB |
Output is correct |
19 |
Correct |
35 ms |
5388 KB |
Output is correct |
20 |
Correct |
18 ms |
3732 KB |
Output is correct |
21 |
Incorrect |
189 ms |
12140 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |