oj.uz

Submission #837879

# Submission time Handle Problem Language Result Execution time Memory
837879 2023-08-25T19:28:16 Z Ahmed57 Feast (NOI19_feast) C++17
30 / 100
 747 ms 15772 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 = 1e16 , 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 461 ms 15400 KB Output is correct
2 Correct 480 ms 15580 KB Output is correct
3 Correct 548 ms 15708 KB Output is correct
4 Correct 459 ms 15612 KB Output is correct
5 Correct 491 ms 15576 KB Output is correct
6 Correct 439 ms 15460 KB Output is correct
7 Correct 458 ms 15484 KB Output is correct
8 Correct 474 ms 15652 KB Output is correct
9 Correct 469 ms 15452 KB Output is correct
10 Correct 472 ms 15564 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 15464 KB Output is correct
2 Correct 460 ms 15772 KB Output is correct
3 Correct 425 ms 15536 KB Output is correct
4 Correct 425 ms 15532 KB Output is correct
5 Correct 468 ms 15464 KB Output is correct
6 Correct 421 ms 15456 KB Output is correct
7 Correct 460 ms 15696 KB Output is correct
8 Correct 473 ms 15604 KB Output is correct
9 Correct 499 ms 15712 KB Output is correct
10 Correct 434 ms 15632 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 15524 KB Output is correct
2 Correct 747 ms 15424 KB Output is correct
3 Correct 706 ms 15740 KB Output is correct
4 Correct 701 ms 15632 KB Output is correct
5 Correct 717 ms 15584 KB Output is correct
6 Correct 710 ms 15600 KB Output is correct
7 Correct 735 ms 15556 KB Output is correct
8 Correct 724 ms 15624 KB Output is correct
9 Correct 710 ms 15720 KB Output is correct
10 Correct 740 ms 15572 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 461 ms 15400 KB Output is correct
2 Correct 480 ms 15580 KB Output is correct
3 Correct 548 ms 15708 KB Output is correct
4 Correct 459 ms 15612 KB Output is correct
5 Correct 491 ms 15576 KB Output is correct
6 Correct 439 ms 15460 KB Output is correct
7 Correct 458 ms 15484 KB Output is correct
8 Correct 474 ms 15652 KB Output is correct
9 Correct 469 ms 15452 KB Output is correct
10 Correct 472 ms 15564 KB Output is correct
11 Correct 443 ms 15464 KB Output is correct
12 Correct 460 ms 15772 KB Output is correct
13 Correct 425 ms 15536 KB Output is correct
14 Correct 425 ms 15532 KB Output is correct
15 Correct 468 ms 15464 KB Output is correct
16 Correct 421 ms 15456 KB Output is correct
17 Correct 460 ms 15696 KB Output is correct
18 Correct 473 ms 15604 KB Output is correct
19 Correct 499 ms 15712 KB Output is correct
20 Correct 434 ms 15632 KB Output is correct
21 Correct 695 ms 15524 KB Output is correct
22 Correct 747 ms 15424 KB Output is correct
23 Correct 706 ms 15740 KB Output is correct
24 Correct 701 ms 15632 KB Output is correct
25 Correct 717 ms 15584 KB Output is correct
26 Correct 710 ms 15600 KB Output is correct
27 Correct 735 ms 15556 KB Output is correct
28 Correct 724 ms 15624 KB Output is correct
29 Correct 710 ms 15720 KB Output is correct
30 Correct 740 ms 15572 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 -