## Submission #997138

# Submission time Handle Problem Language Result Execution time Memory
997138 2024-06-11T17:58:39 Z anonymous321 Feast (NOI19_feast) C++17
0 / 100
174 ms 11648 KB
```// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
int n, k;
cin >> n >> k;
vector<ll> a (n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}

ll ans = 0;
ll lo = -1e9;
ll hi = 1e9;
while (lo < hi) {
ll mid = lo + (hi - lo)/2;
vector<ll> dp (n+1, 0);
vector<ll> p (n+1, 0);
ll best = 0;
int id = 0;
vector<int> cnt (n+1, 0);
for (int i = 0; i < n; i++) {
p[i+1] = p[i] + a[i];
dp[i+1] = max(dp[i+1], dp[i]);
cnt[i+1] = cnt[i];
if (dp[i+1] < best + p[i+1] - lo) {
dp[i+1] = best + p[i+1] - lo;
cnt[i+1] = cnt[id] + 1;
}
if (best < dp[i+1] - p[i+1]) {
best = dp[i+1] - p[i+1];
id = i+1;
}
}

if (cnt[n] <= k) {
hi = mid;
ans = dp[n];
} else {
lo = mid+1;
}
}
cout << ans + k*lo << "\n";
return 0;
}```

#### Subtask #1 0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 11292 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 9652 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #3 0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 11648 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #4 0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #5 0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #6 0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #7 0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 11292 KB Output isn't correct
2 Halted 0 ms 0 KB -