# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
503429 |
2022-01-07T23:34:06 Z |
maximumSHOT |
Feast (NOI19_feast) |
C++17 |
|
392 ms |
16456 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
ll res;
void print() {
cout << res << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct input {
int n, k;
vector<int> a;
vector<ll> pref;
input() = default;
void read() {
cin >> n >> k;
a.resize(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
}
void print() {
cout << n << " " << k << "\n";
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << "\n";
}
void gen() {
static mt19937 rnd(42);
const int MAXN = 10;
const int MAXX = 10;
n = rnd() % MAXN + 1;
k = rnd() % n + 1;
a.resize(n + 1);
for (int i = 1; i <= n; i++)
a[i] = rnd() % (2 * MAXX + 1) - MAXX;
}
void gen_max_test() {
}
pair<ll, int> check(ll lambda) {
vector<pair<ll, int>> dp(n + 1, make_pair(-inf64, -inf)), pr = dp;
pr[0] = {0, 0};
pair<ll, int> mx = {pr[0].first - pref[0], pr[0].second};
for (int i = 1; i <= n; i++) {
{
pair<ll, int> tmp = {
mx.first + (pref[i]) - lambda,
mx.second + 1
};
dp[i] = max(dp[i], tmp);
}
pr[i] = max(pr[i - 1], dp[i]);
mx = max(mx, make_pair(pr[i].first - pref[i], pr[i].second));
}
pair<ll, int> res = {-inf64, -inf};
for (int i = 1; i <= n; i++)
res = max(res, dp[i]);
return res;
}
output fast() {
pref.assign(n + 1, 0);
for (int i = 1; i <= n; i++)
pref[i] = pref[i - 1] + a[i];
ll bl = 0, br = inf64 / 3, bm;
while (br - bl > 1) {
bm = bl + (br - bl) / 2;
auto tmp = check(bm);
if (tmp.second >= k) bl = bm;
else br = bm;
}
ll res = 0;
auto tmp = check(bl);
res = max(res, tmp.first + 1ll * bl * k);
return output{res};
}
output slow() {
#ifndef DEBUG
throw;
#endif
vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, -inf64));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= k; c++) {
dp[i][c] = max(dp[i - 1][c], c ? dp[i][c - 1] : -inf64);
ll sm = 0;
for (int j = i; j >= 1; j--) {
sm += a[j];
dp[i][c] = max(dp[i][c], (c ? dp[j - 1][c - 1] : -inf64) + sm);
}
}
}
return output{dp[n][k]};
}
};
void test_case() {
input in;
in.read();
output res = in.fast();
res.print();
}
void work() {
int t = 1;
while (t--)
test_case();
}
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
Compilation message
feast.cpp: In function 'void max_test()':
feast.cpp:27:8: warning: 'in.input::n' is used uninitialized in this function [-Wuninitialized]
27 | struct input {
| ^~~~~
feast.cpp:27:8: warning: 'in' is used uninitialized in this function [-Wuninitialized]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
15508 KB |
Output is correct |
2 |
Correct |
278 ms |
16036 KB |
Output is correct |
3 |
Correct |
292 ms |
16260 KB |
Output is correct |
4 |
Correct |
277 ms |
16072 KB |
Output is correct |
5 |
Correct |
294 ms |
16112 KB |
Output is correct |
6 |
Correct |
269 ms |
15764 KB |
Output is correct |
7 |
Correct |
271 ms |
15800 KB |
Output is correct |
8 |
Correct |
307 ms |
16084 KB |
Output is correct |
9 |
Correct |
288 ms |
15828 KB |
Output is correct |
10 |
Correct |
282 ms |
15992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
14164 KB |
Output is correct |
2 |
Correct |
307 ms |
14480 KB |
Output is correct |
3 |
Correct |
289 ms |
14120 KB |
Output is correct |
4 |
Correct |
297 ms |
14376 KB |
Output is correct |
5 |
Correct |
300 ms |
15760 KB |
Output is correct |
6 |
Correct |
292 ms |
14108 KB |
Output is correct |
7 |
Correct |
286 ms |
14460 KB |
Output is correct |
8 |
Correct |
317 ms |
16440 KB |
Output is correct |
9 |
Correct |
293 ms |
15712 KB |
Output is correct |
10 |
Correct |
296 ms |
14504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
310 ms |
15728 KB |
Output is correct |
2 |
Correct |
327 ms |
16100 KB |
Output is correct |
3 |
Correct |
342 ms |
16132 KB |
Output is correct |
4 |
Correct |
334 ms |
16136 KB |
Output is correct |
5 |
Correct |
313 ms |
16140 KB |
Output is correct |
6 |
Correct |
330 ms |
16308 KB |
Output is correct |
7 |
Correct |
320 ms |
16260 KB |
Output is correct |
8 |
Correct |
310 ms |
16152 KB |
Output is correct |
9 |
Correct |
320 ms |
16380 KB |
Output is correct |
10 |
Correct |
337 ms |
16288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
324 KB |
Output is correct |
23 |
Correct |
2 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
2 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
15508 KB |
Output is correct |
2 |
Correct |
278 ms |
16036 KB |
Output is correct |
3 |
Correct |
292 ms |
16260 KB |
Output is correct |
4 |
Correct |
277 ms |
16072 KB |
Output is correct |
5 |
Correct |
294 ms |
16112 KB |
Output is correct |
6 |
Correct |
269 ms |
15764 KB |
Output is correct |
7 |
Correct |
271 ms |
15800 KB |
Output is correct |
8 |
Correct |
307 ms |
16084 KB |
Output is correct |
9 |
Correct |
288 ms |
15828 KB |
Output is correct |
10 |
Correct |
282 ms |
15992 KB |
Output is correct |
11 |
Correct |
292 ms |
14164 KB |
Output is correct |
12 |
Correct |
307 ms |
14480 KB |
Output is correct |
13 |
Correct |
289 ms |
14120 KB |
Output is correct |
14 |
Correct |
297 ms |
14376 KB |
Output is correct |
15 |
Correct |
300 ms |
15760 KB |
Output is correct |
16 |
Correct |
292 ms |
14108 KB |
Output is correct |
17 |
Correct |
286 ms |
14460 KB |
Output is correct |
18 |
Correct |
317 ms |
16440 KB |
Output is correct |
19 |
Correct |
293 ms |
15712 KB |
Output is correct |
20 |
Correct |
296 ms |
14504 KB |
Output is correct |
21 |
Correct |
310 ms |
15728 KB |
Output is correct |
22 |
Correct |
327 ms |
16100 KB |
Output is correct |
23 |
Correct |
342 ms |
16132 KB |
Output is correct |
24 |
Correct |
334 ms |
16136 KB |
Output is correct |
25 |
Correct |
313 ms |
16140 KB |
Output is correct |
26 |
Correct |
330 ms |
16308 KB |
Output is correct |
27 |
Correct |
320 ms |
16260 KB |
Output is correct |
28 |
Correct |
310 ms |
16152 KB |
Output is correct |
29 |
Correct |
320 ms |
16380 KB |
Output is correct |
30 |
Correct |
337 ms |
16288 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
0 ms |
312 KB |
Output is correct |
33 |
Correct |
0 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
208 KB |
Output is correct |
35 |
Correct |
0 ms |
204 KB |
Output is correct |
36 |
Correct |
1 ms |
292 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
0 ms |
308 KB |
Output is correct |
39 |
Correct |
0 ms |
312 KB |
Output is correct |
40 |
Correct |
1 ms |
308 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
0 ms |
332 KB |
Output is correct |
43 |
Correct |
0 ms |
204 KB |
Output is correct |
44 |
Correct |
1 ms |
204 KB |
Output is correct |
45 |
Correct |
1 ms |
312 KB |
Output is correct |
46 |
Correct |
1 ms |
204 KB |
Output is correct |
47 |
Correct |
1 ms |
332 KB |
Output is correct |
48 |
Correct |
0 ms |
332 KB |
Output is correct |
49 |
Correct |
0 ms |
204 KB |
Output is correct |
50 |
Correct |
1 ms |
332 KB |
Output is correct |
51 |
Correct |
2 ms |
332 KB |
Output is correct |
52 |
Correct |
2 ms |
324 KB |
Output is correct |
53 |
Correct |
2 ms |
332 KB |
Output is correct |
54 |
Correct |
1 ms |
332 KB |
Output is correct |
55 |
Correct |
1 ms |
332 KB |
Output is correct |
56 |
Correct |
1 ms |
332 KB |
Output is correct |
57 |
Correct |
2 ms |
332 KB |
Output is correct |
58 |
Correct |
1 ms |
332 KB |
Output is correct |
59 |
Correct |
1 ms |
332 KB |
Output is correct |
60 |
Correct |
1 ms |
332 KB |
Output is correct |
61 |
Correct |
376 ms |
15960 KB |
Output is correct |
62 |
Correct |
391 ms |
16456 KB |
Output is correct |
63 |
Correct |
334 ms |
16108 KB |
Output is correct |
64 |
Correct |
381 ms |
16268 KB |
Output is correct |
65 |
Correct |
378 ms |
16436 KB |
Output is correct |
66 |
Correct |
392 ms |
16204 KB |
Output is correct |
67 |
Correct |
373 ms |
16432 KB |
Output is correct |
68 |
Correct |
306 ms |
16284 KB |
Output is correct |
69 |
Correct |
298 ms |
15956 KB |
Output is correct |
70 |
Correct |
315 ms |
16012 KB |
Output is correct |