Submission #1122179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122179		Aviansh	Feast (NOI19_feast)	C++17	0 / 100	1048 ms	41384 KiB

feast

#include <bits/stdc++.h>

using namespace std;

long long prefsum(long long pref[],int s, int e){
    long long ans = pref[e];
    if(s){
        s--;
        ans-=pref[s];
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    vector<long long> arr(n);
    set<array<int,2>>rangs;
    long long pref[n];
    for(int i = 0;i<n;i++){
        cin >> arr[i];
        if(arr[i]>0){
            rangs.insert({i,i});
        }
    }
    if(rangs.size()==0){
        cout << 0;
        return 0;
    }
    pref[0]=arr[0];
    for(int i = 1;i<n;i++){
        pref[i]=pref[i-1]+arr[i];
    }
    priority_queue<array<long long,3>>joins;
    set<array<int,2>>::iterator it = rangs.begin();
    int las = (*it)[1];
    it++;
    while(it!=rangs.end()){
        joins.push({prefsum(pref,las+1,(*it)[0]-1),las,(*it)[0]});
        las=(*it)[1];
        it++;
    }
    multiset<long long>rangsums;
    for(array<int,2> a : rangs){
        rangsums.insert(prefsum(pref,a[0],a[1]));
    }
    long long ans = 0;
    multiset<long long>::iterator s = rangsums.end();
    s--;
    int cn = 0;
    long long sum = 0;
    while(cn<rangsums.size()&&cn<k){
        sum+=(*s);
        cn++;
        s--;
    }
    ans=max(ans,sum);
    while(rangs.size()>k){
        array<long long,3>curr = joins.top();
        joins.pop();
        set<array<int,2>>::iterator it = rangs.upper_bound({curr[1],2000000000});
        array<int,2>up = *it;
        it--;
        array<int,2>down = *it;
        rangs.erase(up);
        rangs.erase(down);
        rangsums.erase(rangsums.find(prefsum(pref,down[0],down[1])));
        rangsums.erase(rangsums.find(prefsum(pref,up[0],up[1])));
        rangs.insert({down[0],up[1]});
        rangsums.insert(prefsum(pref,down[0],up[1]));
        multiset<long long>::iterator s = rangsums.end();
        s--;
        int cn = 0;
        long long sum = 0;
        while(cn<rangsums.size()&&cn<k){
            sum+=(*s);
            cn++;
            s--;
        }
        ans=max(ans,sum);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while(cn<rangsums.size()&&cn<k){
      |           ~~^~~~~~~~~~~~~~~~
feast.cpp:60:23: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     while(rangs.size()>k){
      |           ~~~~~~~~~~~~^~
feast.cpp:63:80: warning: narrowing conversion of 'curr.std::array<long long int, 3>::operator[](1)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   63 |         set<array<int,2>>::iterator it = rangs.upper_bound({curr[1],2000000000});
      |                                                                                ^
feast.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(cn<rangsums.size()&&cn<k){
      |               ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29