oj.uz

Submission #837872

# Submission time Handle Problem Language Result Execution time Memory
837872 2023-08-25T19:20:11 Z Ahmed57 Feast (NOI19_feast) C++17
30 / 100
 611 ms 18652 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;
    for(int i = 0;i<n;i++){
        cin>>arr[i];
        if(i)arr[i]+=arr[i-1];
    }
    long long l = 0 , r = 1e12 , ans = 0;
    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;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 15524 KB Output is correct
2 Correct 413 ms 18420 KB Output is correct
3 Correct 404 ms 18532 KB Output is correct
4 Correct 386 ms 18492 KB Output is correct
5 Correct 377 ms 18600 KB Output is correct
6 Correct 379 ms 18244 KB Output is correct
7 Correct 373 ms 18340 KB Output is correct
8 Correct 363 ms 18420 KB Output is correct
9 Correct 350 ms 18340 KB Output is correct
10 Correct 370 ms 18352 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 15504 KB Output is correct
2 Correct 344 ms 16752 KB Output is correct
3 Correct 329 ms 16588 KB Output is correct
4 Correct 360 ms 16756 KB Output is correct
5 Correct 379 ms 18320 KB Output is correct
6 Correct 340 ms 16652 KB Output is correct
7 Correct 342 ms 16808 KB Output is correct
8 Correct 369 ms 18652 KB Output is correct
9 Correct 339 ms 18224 KB Output is correct
10 Correct 342 ms 16772 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 15508 KB Output is correct
2 Correct 545 ms 18472 KB Output is correct
3 Correct 561 ms 18520 KB Output is correct
4 Correct 544 ms 18404 KB Output is correct
5 Correct 604 ms 18648 KB Output is correct
6 Correct 611 ms 18644 KB Output is correct
7 Correct 562 ms 18600 KB Output is correct
8 Correct 561 ms 18516 KB Output is correct
9 Correct 570 ms 18628 KB Output is correct
10 Correct 577 ms 18616 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 15524 KB Output is correct
2 Correct 413 ms 18420 KB Output is correct
3 Correct 404 ms 18532 KB Output is correct
4 Correct 386 ms 18492 KB Output is correct
5 Correct 377 ms 18600 KB Output is correct
6 Correct 379 ms 18244 KB Output is correct
7 Correct 373 ms 18340 KB Output is correct
8 Correct 363 ms 18420 KB Output is correct
9 Correct 350 ms 18340 KB Output is correct
10 Correct 370 ms 18352 KB Output is correct
11 Correct 333 ms 15504 KB Output is correct
12 Correct 344 ms 16752 KB Output is correct
13 Correct 329 ms 16588 KB Output is correct
14 Correct 360 ms 16756 KB Output is correct
15 Correct 379 ms 18320 KB Output is correct
16 Correct 340 ms 16652 KB Output is correct
17 Correct 342 ms 16808 KB Output is correct
18 Correct 369 ms 18652 KB Output is correct
19 Correct 339 ms 18224 KB Output is correct
20 Correct 342 ms 16772 KB Output is correct
21 Correct 544 ms 15508 KB Output is correct
22 Correct 545 ms 18472 KB Output is correct
23 Correct 561 ms 18520 KB Output is correct
24 Correct 544 ms 18404 KB Output is correct
25 Correct 604 ms 18648 KB Output is correct
26 Correct 611 ms 18644 KB Output is correct
27 Correct 562 ms 18600 KB Output is correct
28 Correct 561 ms 18516 KB Output is correct
29 Correct 570 ms 18628 KB Output is correct
30 Correct 577 ms 18616 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 1 ms 212 KB Output isn't correct
33 Halted 0 ms 0 KB -