| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 240617 |
2020-06-20T09:25:31 Z |
mhy908 |
Feast (NOI19_feast) |
C++14 |
|
186 ms |
12092 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
const LL llinf=10000000000000;
int n, k;
LL arr[300010], dp[300010][2], cnt[300010][2];
int solve(LL x){
for(int i=1; i<=n; i++){
if(pll(dp[i-1][0], -cnt[i-1][0])>pll(dp[i-1][1]-x, -cnt[i-1][1]))dp[i][0]=dp[i-1][0]+arr[i], cnt[i][0]=cnt[i-1][0];
else dp[i][0]=dp[i-1][1]+arr[i]-x, cnt[i][0]=cnt[i-1][1]+1;
if(pll(dp[i-1][0], -cnt[i-1][0])>pll(dp[i-1][1], -cnt[i-1][1]))dp[i][1]=dp[i-1][0], cnt[i][1]=cnt[i-1][0];
else dp[i][1]=dp[i-1][1], cnt[i][1]=cnt[i-1][1];
}
if(pll(dp[n][0], -cnt[n][0])>pll(dp[n][1], -cnt[n][1]))return cnt[n][0];
return cnt[n][1];
}
int main(){
dp[0][0]=-llinf, dp[0][1]=0;
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
arr[i]*=2;
}
LL l=0, r=llinf;
while(l<r){
LL mid=(l+r)/2;
if(solve(mid*2+1)>k)l=mid+1;
else r=mid;
}
solve(l*2);
printf("%lld", max(dp[n][0], dp[n][1])/2+l*k);
}
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
feast.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &arr[i]);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
11772 KB |
Output is correct |
| 2 |
Correct |
118 ms |
11896 KB |
Output is correct |
| 3 |
Correct |
111 ms |
12024 KB |
Output is correct |
| 4 |
Correct |
114 ms |
11896 KB |
Output is correct |
| 5 |
Correct |
110 ms |
11900 KB |
Output is correct |
| 6 |
Correct |
111 ms |
11756 KB |
Output is correct |
| 7 |
Correct |
109 ms |
11768 KB |
Output is correct |
| 8 |
Correct |
109 ms |
11896 KB |
Output is correct |
| 9 |
Correct |
108 ms |
11768 KB |
Output is correct |
| 10 |
Correct |
111 ms |
11980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
11776 KB |
Output is correct |
| 2 |
Correct |
91 ms |
12024 KB |
Output is correct |
| 3 |
Correct |
97 ms |
11768 KB |
Output is correct |
| 4 |
Correct |
101 ms |
11896 KB |
Output is correct |
| 5 |
Correct |
115 ms |
11768 KB |
Output is correct |
| 6 |
Correct |
88 ms |
11768 KB |
Output is correct |
| 7 |
Correct |
90 ms |
12024 KB |
Output is correct |
| 8 |
Correct |
110 ms |
12072 KB |
Output is correct |
| 9 |
Correct |
104 ms |
11640 KB |
Output is correct |
| 10 |
Correct |
91 ms |
12024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
11884 KB |
Output is correct |
| 2 |
Correct |
128 ms |
11984 KB |
Output is correct |
| 3 |
Correct |
135 ms |
11984 KB |
Output is correct |
| 4 |
Correct |
126 ms |
11768 KB |
Output is correct |
| 5 |
Correct |
130 ms |
12024 KB |
Output is correct |
| 6 |
Correct |
131 ms |
11896 KB |
Output is correct |
| 7 |
Correct |
133 ms |
12024 KB |
Output is correct |
| 8 |
Correct |
133 ms |
12024 KB |
Output is correct |
| 9 |
Correct |
133 ms |
12028 KB |
Output is correct |
| 10 |
Correct |
131 ms |
12024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
4 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
6 ms |
384 KB |
Output is correct |
| 23 |
Correct |
6 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
384 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Correct |
5 ms |
384 KB |
Output is correct |
| 28 |
Correct |
6 ms |
384 KB |
Output is correct |
| 29 |
Correct |
6 ms |
384 KB |
Output is correct |
| 30 |
Correct |
6 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
11772 KB |
Output is correct |
| 2 |
Correct |
118 ms |
11896 KB |
Output is correct |
| 3 |
Correct |
111 ms |
12024 KB |
Output is correct |
| 4 |
Correct |
114 ms |
11896 KB |
Output is correct |
| 5 |
Correct |
110 ms |
11900 KB |
Output is correct |
| 6 |
Correct |
111 ms |
11756 KB |
Output is correct |
| 7 |
Correct |
109 ms |
11768 KB |
Output is correct |
| 8 |
Correct |
109 ms |
11896 KB |
Output is correct |
| 9 |
Correct |
108 ms |
11768 KB |
Output is correct |
| 10 |
Correct |
111 ms |
11980 KB |
Output is correct |
| 11 |
Correct |
89 ms |
11776 KB |
Output is correct |
| 12 |
Correct |
91 ms |
12024 KB |
Output is correct |
| 13 |
Correct |
97 ms |
11768 KB |
Output is correct |
| 14 |
Correct |
101 ms |
11896 KB |
Output is correct |
| 15 |
Correct |
115 ms |
11768 KB |
Output is correct |
| 16 |
Correct |
88 ms |
11768 KB |
Output is correct |
| 17 |
Correct |
90 ms |
12024 KB |
Output is correct |
| 18 |
Correct |
110 ms |
12072 KB |
Output is correct |
| 19 |
Correct |
104 ms |
11640 KB |
Output is correct |
| 20 |
Correct |
91 ms |
12024 KB |
Output is correct |
| 21 |
Correct |
127 ms |
11884 KB |
Output is correct |
| 22 |
Correct |
128 ms |
11984 KB |
Output is correct |
| 23 |
Correct |
135 ms |
11984 KB |
Output is correct |
| 24 |
Correct |
126 ms |
11768 KB |
Output is correct |
| 25 |
Correct |
130 ms |
12024 KB |
Output is correct |
| 26 |
Correct |
131 ms |
11896 KB |
Output is correct |
| 27 |
Correct |
133 ms |
12024 KB |
Output is correct |
| 28 |
Correct |
133 ms |
12024 KB |
Output is correct |
| 29 |
Correct |
133 ms |
12028 KB |
Output is correct |
| 30 |
Correct |
131 ms |
12024 KB |
Output is correct |
| 31 |
Correct |
5 ms |
384 KB |
Output is correct |
| 32 |
Correct |
4 ms |
384 KB |
Output is correct |
| 33 |
Correct |
4 ms |
384 KB |
Output is correct |
| 34 |
Correct |
4 ms |
384 KB |
Output is correct |
| 35 |
Correct |
5 ms |
384 KB |
Output is correct |
| 36 |
Correct |
5 ms |
384 KB |
Output is correct |
| 37 |
Correct |
5 ms |
384 KB |
Output is correct |
| 38 |
Correct |
5 ms |
384 KB |
Output is correct |
| 39 |
Correct |
4 ms |
384 KB |
Output is correct |
| 40 |
Correct |
5 ms |
384 KB |
Output is correct |
| 41 |
Correct |
5 ms |
384 KB |
Output is correct |
| 42 |
Correct |
5 ms |
384 KB |
Output is correct |
| 43 |
Correct |
4 ms |
384 KB |
Output is correct |
| 44 |
Correct |
5 ms |
384 KB |
Output is correct |
| 45 |
Correct |
4 ms |
384 KB |
Output is correct |
| 46 |
Correct |
5 ms |
384 KB |
Output is correct |
| 47 |
Correct |
5 ms |
384 KB |
Output is correct |
| 48 |
Correct |
5 ms |
384 KB |
Output is correct |
| 49 |
Correct |
5 ms |
384 KB |
Output is correct |
| 50 |
Correct |
5 ms |
384 KB |
Output is correct |
| 51 |
Correct |
5 ms |
384 KB |
Output is correct |
| 52 |
Correct |
6 ms |
384 KB |
Output is correct |
| 53 |
Correct |
6 ms |
384 KB |
Output is correct |
| 54 |
Correct |
5 ms |
384 KB |
Output is correct |
| 55 |
Correct |
5 ms |
384 KB |
Output is correct |
| 56 |
Correct |
5 ms |
384 KB |
Output is correct |
| 57 |
Correct |
5 ms |
384 KB |
Output is correct |
| 58 |
Correct |
6 ms |
384 KB |
Output is correct |
| 59 |
Correct |
6 ms |
384 KB |
Output is correct |
| 60 |
Correct |
6 ms |
384 KB |
Output is correct |
| 61 |
Correct |
169 ms |
11712 KB |
Output is correct |
| 62 |
Correct |
165 ms |
12024 KB |
Output is correct |
| 63 |
Correct |
146 ms |
11768 KB |
Output is correct |
| 64 |
Correct |
174 ms |
12024 KB |
Output is correct |
| 65 |
Correct |
172 ms |
11896 KB |
Output is correct |
| 66 |
Correct |
186 ms |
12092 KB |
Output is correct |
| 67 |
Correct |
172 ms |
11768 KB |
Output is correct |
| 68 |
Correct |
130 ms |
12024 KB |
Output is correct |
| 69 |
Correct |
126 ms |
11768 KB |
Output is correct |
| 70 |
Correct |
126 ms |
11768 KB |
Output is correct |
