# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
588017 |
2022-07-02T16:10:50 Z |
sofapuden |
Feast (NOI19_feast) |
C++14 |
|
154 ms |
26736 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mn = -(1ll<<60);
void solve(){
int n, k; cin >> n >> k;
vector<ll> v(n);
for(auto &x : v)cin >> x;
ll l = 0, r = (1ll<<42), bes = 0;
vector<vector<pair<ll,ll>>> dp(n,vector<pair<ll,ll>>(2));
while(l<=r){
ll m = (l+r)>>1;
dp[0][0] = {0,0};
dp[0][1] = {-m+v[0],1};
for(int i = 1; i < n; ++i){
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
dp[i][1] = max(dp[i-1][1],{dp[i-1][0].first-m,dp[i-1][0].second+1});
dp[i][1].first+=v[i];
}
pair<ll,ll> b = max(dp[n-1][0], dp[n-1][1]);
if(b.second >= k){
bes = b.first + m*k;
l = m+1;
}
else{
r = m-1;
}
}
cout << bes << '\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
123 ms |
23068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
23236 KB |
Output is correct |
2 |
Correct |
120 ms |
24756 KB |
Output is correct |
3 |
Correct |
117 ms |
24196 KB |
Output is correct |
4 |
Incorrect |
115 ms |
24520 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
23532 KB |
Output is correct |
2 |
Correct |
144 ms |
26188 KB |
Output is correct |
3 |
Correct |
152 ms |
26468 KB |
Output is correct |
4 |
Correct |
137 ms |
26280 KB |
Output is correct |
5 |
Correct |
143 ms |
26420 KB |
Output is correct |
6 |
Correct |
136 ms |
26556 KB |
Output is correct |
7 |
Correct |
137 ms |
26732 KB |
Output is correct |
8 |
Correct |
133 ms |
26432 KB |
Output is correct |
9 |
Correct |
154 ms |
26704 KB |
Output is correct |
10 |
Correct |
141 ms |
26736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
123 ms |
23068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |