# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
345558 |
2021-01-07T14:53:10 Z |
Nursik |
Feast (NOI19_feast) |
C++14 |
|
1000 ms |
49004 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define ld long double
using namespace std;
void data() {
#ifdef NURS
freopen("main.in", "r", stdin);
freopen("main.out", "w", stdout);
#endif
}
void win()
{
ios_base::sync_with_stdio(0),
cin.tie(0),cout.tie(0);
}
int block = 400;
const ld eps = 1e-6;
const int N = 1e6 + 500;
const int mod = 1e9 + 7;
const ll hh = 100010683;
const ll hh2 = 150005819;
int n, k, g, pos;
int a[N];
ll s, ans;
ll dp[5000][5000], pref[5000];
int main()
{
data();
win();
cin >> n >> k;
bool was = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
was = was | (a[i] < 0), s += a[i];
if (a[i] < 0)
g++, pos = i;
pref[i] += pref[i - 1] + a[i];
}
//first subtask
if (was == 0)
{
cout << s << '\n';
return 0;
}
//second subtask
if (g == 1 && k >= 2)
{
cout << s - a[pos] << '\n';
return 0;
}
else if (g == 1 && k == 1)
{
ans = max(ans, s);
s = 0;
for (int i = 1; i < pos; i++)
s += a[i];
ans = max(ans, s), s = 0;
for (int i = pos + 1; i <= n; i++)
s += a[i];
ans = max(ans, s);
cout << ans << '\n';
return 0;
}
//3, 4, 5 subtasks
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
dp[i][j] = -1e9;
}
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
for (int len = 0; len <= i; len++)
{
if (dp[i - len][j - 1] != -1e9)
{
dp[i][j] = max(dp[i - len][j - 1] + pref[i] - pref[i - len], dp[i][j]);
}
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if (i == n && j == k)
ans = max(ans, dp[i][j]);
}
dp[i][0] = max(dp[i][0], dp[i - 1][0]);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
3820 KB |
Output is correct |
2 |
Correct |
37 ms |
3820 KB |
Output is correct |
3 |
Correct |
36 ms |
3820 KB |
Output is correct |
4 |
Correct |
35 ms |
3820 KB |
Output is correct |
5 |
Correct |
36 ms |
3820 KB |
Output is correct |
6 |
Correct |
36 ms |
3820 KB |
Output is correct |
7 |
Correct |
34 ms |
3820 KB |
Output is correct |
8 |
Correct |
37 ms |
3820 KB |
Output is correct |
9 |
Correct |
34 ms |
3820 KB |
Output is correct |
10 |
Correct |
35 ms |
3820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
3820 KB |
Output is correct |
2 |
Correct |
24 ms |
3820 KB |
Output is correct |
3 |
Correct |
24 ms |
3820 KB |
Output is correct |
4 |
Correct |
24 ms |
3968 KB |
Output is correct |
5 |
Correct |
42 ms |
3820 KB |
Output is correct |
6 |
Correct |
25 ms |
3820 KB |
Output is correct |
7 |
Correct |
30 ms |
3820 KB |
Output is correct |
8 |
Correct |
35 ms |
3820 KB |
Output is correct |
9 |
Correct |
35 ms |
3692 KB |
Output is correct |
10 |
Correct |
24 ms |
3820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
136 ms |
49004 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
620 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
620 KB |
Output is correct |
6 |
Correct |
1 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
620 KB |
Output is correct |
8 |
Correct |
1 ms |
620 KB |
Output is correct |
9 |
Correct |
1 ms |
620 KB |
Output is correct |
10 |
Correct |
1 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
620 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
620 KB |
Output is correct |
6 |
Correct |
1 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
620 KB |
Output is correct |
8 |
Correct |
1 ms |
620 KB |
Output is correct |
9 |
Correct |
1 ms |
620 KB |
Output is correct |
10 |
Correct |
1 ms |
620 KB |
Output is correct |
11 |
Correct |
6 ms |
1644 KB |
Output is correct |
12 |
Correct |
7 ms |
1516 KB |
Output is correct |
13 |
Correct |
3 ms |
1516 KB |
Output is correct |
14 |
Correct |
6 ms |
1516 KB |
Output is correct |
15 |
Correct |
4 ms |
1516 KB |
Output is correct |
16 |
Correct |
4 ms |
1516 KB |
Output is correct |
17 |
Correct |
9 ms |
1644 KB |
Output is correct |
18 |
Correct |
2 ms |
1516 KB |
Output is correct |
19 |
Correct |
2 ms |
1516 KB |
Output is correct |
20 |
Correct |
2 ms |
1516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
620 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
3 |
Correct |
1 ms |
620 KB |
Output is correct |
4 |
Correct |
1 ms |
620 KB |
Output is correct |
5 |
Correct |
1 ms |
620 KB |
Output is correct |
6 |
Correct |
1 ms |
620 KB |
Output is correct |
7 |
Correct |
1 ms |
620 KB |
Output is correct |
8 |
Correct |
1 ms |
620 KB |
Output is correct |
9 |
Correct |
1 ms |
620 KB |
Output is correct |
10 |
Correct |
1 ms |
620 KB |
Output is correct |
11 |
Correct |
6 ms |
1644 KB |
Output is correct |
12 |
Correct |
7 ms |
1516 KB |
Output is correct |
13 |
Correct |
3 ms |
1516 KB |
Output is correct |
14 |
Correct |
6 ms |
1516 KB |
Output is correct |
15 |
Correct |
4 ms |
1516 KB |
Output is correct |
16 |
Correct |
4 ms |
1516 KB |
Output is correct |
17 |
Correct |
9 ms |
1644 KB |
Output is correct |
18 |
Correct |
2 ms |
1516 KB |
Output is correct |
19 |
Correct |
2 ms |
1516 KB |
Output is correct |
20 |
Correct |
2 ms |
1516 KB |
Output is correct |
21 |
Execution timed out |
1092 ms |
11372 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
3820 KB |
Output is correct |
2 |
Correct |
37 ms |
3820 KB |
Output is correct |
3 |
Correct |
36 ms |
3820 KB |
Output is correct |
4 |
Correct |
35 ms |
3820 KB |
Output is correct |
5 |
Correct |
36 ms |
3820 KB |
Output is correct |
6 |
Correct |
36 ms |
3820 KB |
Output is correct |
7 |
Correct |
34 ms |
3820 KB |
Output is correct |
8 |
Correct |
37 ms |
3820 KB |
Output is correct |
9 |
Correct |
34 ms |
3820 KB |
Output is correct |
10 |
Correct |
35 ms |
3820 KB |
Output is correct |
11 |
Correct |
24 ms |
3820 KB |
Output is correct |
12 |
Correct |
24 ms |
3820 KB |
Output is correct |
13 |
Correct |
24 ms |
3820 KB |
Output is correct |
14 |
Correct |
24 ms |
3968 KB |
Output is correct |
15 |
Correct |
42 ms |
3820 KB |
Output is correct |
16 |
Correct |
25 ms |
3820 KB |
Output is correct |
17 |
Correct |
30 ms |
3820 KB |
Output is correct |
18 |
Correct |
35 ms |
3820 KB |
Output is correct |
19 |
Correct |
35 ms |
3692 KB |
Output is correct |
20 |
Correct |
24 ms |
3820 KB |
Output is correct |
21 |
Runtime error |
136 ms |
49004 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |