| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 837885 |
2023-08-25T19:33:27 Z |
Ahmed57 |
Feast (NOI19_feast) |
C++17 |
|
796 ms |
18764 KB |
#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long arr[300001];
pair<long long,long long> check(long long x){
priority_queue<pair<long long,long long>> q;
q.push({0,0});
pair<long long,long long> ans = {0,0};
for(int i = 0;i<n;i++){
long long val = arr[i]+q.top().first-x;
long long sec = (q.top().second)+1;
pair<long long,long long> fawzya = {val,sec};
ans = max(ans,fawzya);
fawzya = ans;
q.push({(-arr[i])+fawzya.first,fawzya.second});
ans = max(ans,make_pair(fawzya.first,fawzya.second));
}
return ans;
}
int main(){
cin>>n>>k;
long long ans = 0;
for(int i = 0;i<n;i++){
cin>>arr[i];
if(arr[i]>0)ans+=arr[i];
if(i)arr[i]+=arr[i-1];
}
long long l = 0 , r = 1e16;
while(l<=r){
long long mid = (l+r)/2;
pair<long long ,long long> an = check(mid);
if(an.second>=k){
ans =an.first+k*mid;
l = mid+1;
}else {
r = mid-1;
}
}
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
488 ms |
15396 KB |
Output is correct |
| 2 |
Correct |
503 ms |
15552 KB |
Output is correct |
| 3 |
Correct |
509 ms |
15616 KB |
Output is correct |
| 4 |
Correct |
501 ms |
15580 KB |
Output is correct |
| 5 |
Correct |
471 ms |
15536 KB |
Output is correct |
| 6 |
Correct |
515 ms |
15452 KB |
Output is correct |
| 7 |
Correct |
470 ms |
15436 KB |
Output is correct |
| 8 |
Correct |
470 ms |
15564 KB |
Output is correct |
| 9 |
Correct |
496 ms |
15488 KB |
Output is correct |
| 10 |
Correct |
502 ms |
15508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
15500 KB |
Output is correct |
| 2 |
Correct |
454 ms |
15632 KB |
Output is correct |
| 3 |
Correct |
452 ms |
15484 KB |
Output is correct |
| 4 |
Correct |
436 ms |
15552 KB |
Output is correct |
| 5 |
Correct |
462 ms |
15460 KB |
Output is correct |
| 6 |
Correct |
438 ms |
15464 KB |
Output is correct |
| 7 |
Correct |
452 ms |
15656 KB |
Output is correct |
| 8 |
Correct |
491 ms |
15728 KB |
Output is correct |
| 9 |
Correct |
471 ms |
15420 KB |
Output is correct |
| 10 |
Correct |
472 ms |
15592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
712 ms |
15544 KB |
Output is correct |
| 2 |
Correct |
712 ms |
15456 KB |
Output is correct |
| 3 |
Correct |
704 ms |
15512 KB |
Output is correct |
| 4 |
Correct |
695 ms |
15416 KB |
Output is correct |
| 5 |
Correct |
710 ms |
15656 KB |
Output is correct |
| 6 |
Correct |
710 ms |
15600 KB |
Output is correct |
| 7 |
Correct |
742 ms |
15648 KB |
Output is correct |
| 8 |
Correct |
719 ms |
15496 KB |
Output is correct |
| 9 |
Correct |
720 ms |
15592 KB |
Output is correct |
| 10 |
Correct |
726 ms |
15628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
324 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
308 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
324 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
3 ms |
340 KB |
Output is correct |
| 22 |
Correct |
3 ms |
340 KB |
Output is correct |
| 23 |
Correct |
3 ms |
340 KB |
Output is correct |
| 24 |
Correct |
3 ms |
340 KB |
Output is correct |
| 25 |
Correct |
3 ms |
316 KB |
Output is correct |
| 26 |
Correct |
3 ms |
340 KB |
Output is correct |
| 27 |
Correct |
3 ms |
340 KB |
Output is correct |
| 28 |
Correct |
3 ms |
324 KB |
Output is correct |
| 29 |
Correct |
3 ms |
340 KB |
Output is correct |
| 30 |
Correct |
3 ms |
324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
488 ms |
15396 KB |
Output is correct |
| 2 |
Correct |
503 ms |
15552 KB |
Output is correct |
| 3 |
Correct |
509 ms |
15616 KB |
Output is correct |
| 4 |
Correct |
501 ms |
15580 KB |
Output is correct |
| 5 |
Correct |
471 ms |
15536 KB |
Output is correct |
| 6 |
Correct |
515 ms |
15452 KB |
Output is correct |
| 7 |
Correct |
470 ms |
15436 KB |
Output is correct |
| 8 |
Correct |
470 ms |
15564 KB |
Output is correct |
| 9 |
Correct |
496 ms |
15488 KB |
Output is correct |
| 10 |
Correct |
502 ms |
15508 KB |
Output is correct |
| 11 |
Correct |
448 ms |
15500 KB |
Output is correct |
| 12 |
Correct |
454 ms |
15632 KB |
Output is correct |
| 13 |
Correct |
452 ms |
15484 KB |
Output is correct |
| 14 |
Correct |
436 ms |
15552 KB |
Output is correct |
| 15 |
Correct |
462 ms |
15460 KB |
Output is correct |
| 16 |
Correct |
438 ms |
15464 KB |
Output is correct |
| 17 |
Correct |
452 ms |
15656 KB |
Output is correct |
| 18 |
Correct |
491 ms |
15728 KB |
Output is correct |
| 19 |
Correct |
471 ms |
15420 KB |
Output is correct |
| 20 |
Correct |
472 ms |
15592 KB |
Output is correct |
| 21 |
Correct |
712 ms |
15544 KB |
Output is correct |
| 22 |
Correct |
712 ms |
15456 KB |
Output is correct |
| 23 |
Correct |
704 ms |
15512 KB |
Output is correct |
| 24 |
Correct |
695 ms |
15416 KB |
Output is correct |
| 25 |
Correct |
710 ms |
15656 KB |
Output is correct |
| 26 |
Correct |
710 ms |
15600 KB |
Output is correct |
| 27 |
Correct |
742 ms |
15648 KB |
Output is correct |
| 28 |
Correct |
719 ms |
15496 KB |
Output is correct |
| 29 |
Correct |
720 ms |
15592 KB |
Output is correct |
| 30 |
Correct |
726 ms |
15628 KB |
Output is correct |
| 31 |
Correct |
1 ms |
212 KB |
Output is correct |
| 32 |
Correct |
0 ms |
212 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
| 34 |
Correct |
1 ms |
212 KB |
Output is correct |
| 35 |
Correct |
1 ms |
212 KB |
Output is correct |
| 36 |
Correct |
1 ms |
212 KB |
Output is correct |
| 37 |
Correct |
1 ms |
212 KB |
Output is correct |
| 38 |
Correct |
1 ms |
308 KB |
Output is correct |
| 39 |
Correct |
1 ms |
212 KB |
Output is correct |
| 40 |
Correct |
1 ms |
212 KB |
Output is correct |
| 41 |
Correct |
1 ms |
308 KB |
Output is correct |
| 42 |
Correct |
1 ms |
212 KB |
Output is correct |
| 43 |
Correct |
1 ms |
212 KB |
Output is correct |
| 44 |
Correct |
1 ms |
212 KB |
Output is correct |
| 45 |
Correct |
1 ms |
212 KB |
Output is correct |
| 46 |
Correct |
1 ms |
212 KB |
Output is correct |
| 47 |
Correct |
1 ms |
212 KB |
Output is correct |
| 48 |
Correct |
1 ms |
324 KB |
Output is correct |
| 49 |
Correct |
1 ms |
212 KB |
Output is correct |
| 50 |
Correct |
1 ms |
212 KB |
Output is correct |
| 51 |
Correct |
3 ms |
340 KB |
Output is correct |
| 52 |
Correct |
3 ms |
340 KB |
Output is correct |
| 53 |
Correct |
3 ms |
340 KB |
Output is correct |
| 54 |
Correct |
3 ms |
340 KB |
Output is correct |
| 55 |
Correct |
3 ms |
316 KB |
Output is correct |
| 56 |
Correct |
3 ms |
340 KB |
Output is correct |
| 57 |
Correct |
3 ms |
340 KB |
Output is correct |
| 58 |
Correct |
3 ms |
324 KB |
Output is correct |
| 59 |
Correct |
3 ms |
340 KB |
Output is correct |
| 60 |
Correct |
3 ms |
324 KB |
Output is correct |
| 61 |
Correct |
793 ms |
18412 KB |
Output is correct |
| 62 |
Correct |
796 ms |
18764 KB |
Output is correct |
| 63 |
Correct |
767 ms |
18472 KB |
Output is correct |
| 64 |
Correct |
793 ms |
18564 KB |
Output is correct |
| 65 |
Correct |
762 ms |
18596 KB |
Output is correct |
| 66 |
Correct |
763 ms |
18612 KB |
Output is correct |
| 67 |
Correct |
789 ms |
18472 KB |
Output is correct |
| 68 |
Correct |
713 ms |
18732 KB |
Output is correct |
| 69 |
Correct |
704 ms |
18444 KB |
Output is correct |
| 70 |
Correct |
709 ms |
18376 KB |
Output is correct |
