Submission #1122190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122190		Aviansh	Feast (NOI19_feast)	C++17	30 / 100	548 ms	46168 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(k==1){
        long long ans = 0;
        long long curr = 0;
        for(int i = 0;i<n;i++){
            curr+=arr[i];
            curr=max(curr,0LL);
            ans=max(ans,curr);
        }
        cout << ans;
        return 0;
    }
    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<array<long long,3>>rangsums;
    for(array<int,2> a : rangs){
        rangsums.insert({prefsum(pref,a[0],a[1]),a[0],a[1]});
    }
    while(rangsums.size()>k){
        rangsums.erase(rangsums.begin());
    }
    long long ans = 0;
    long long sum = 0;
    for(array<long long,3>a : rangsums){
        sum+=a[0];
    }
    ans=max(ans,sum);
    while(rangs.size()>k||(joins.size()&&joins.top()[0]==0)){
        assert(joins.size());
        array<long long,3>curr = joins.top();
        joins.pop();
        set<array<int,2>>::iterator it = rangs.lower_bound({curr[2],-1});
        array<int,2>up = *it;
        it--;
        array<int,2>down = *it;
        rangs.erase(up);
        rangs.erase(down);
        multiset<array<long long,3>>::iterator c = rangsums.find({prefsum(pref,down[0],down[1]),down[0],down[1]});
        if(c!=rangsums.end()){
            rangsums.erase(c);
            sum-=prefsum(pref,down[0],down[1]);
        }
        c = rangsums.find({prefsum(pref,up[0],up[1]),up[0],up[1]});
        if(c!=rangsums.end()){
            rangsums.erase(c);
            sum-=prefsum(pref,up[0],up[1]);
        }
        rangs.insert({down[0],up[1]});
        rangsums.insert({prefsum(pref,down[0],up[1]),down[0],up[1]});
        sum+=prefsum(pref,down[0],up[1]);
        while(rangsums.size()>k){
            array<long long,3>curr = *rangsums.begin();
            sum-=curr[0];
            rangsums.erase(rangsums.begin());
        }
        ans=max(ans,sum);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:60:26: warning: comparison of integer expressions of different signedness: 'std::multiset<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     while(rangsums.size()>k){
      |           ~~~~~~~~~~~~~~~^~
feast.cpp:69: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]
   69 |     while(rangs.size()>k||(joins.size()&&joins.top()[0]==0)){
      |           ~~~~~~~~~~~~^~
feast.cpp:73:72: warning: narrowing conversion of 'curr.std::array<long long int, 3>::operator[](2)' from 'std::array<long long int, 3>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   73 |         set<array<int,2>>::iterator it = rangs.lower_bound({curr[2],-1});
      |                                                                        ^
feast.cpp:92:30: warning: comparison of integer expressions of different signedness: 'std::multiset<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |         while(rangsums.size()>k){
      |               ~~~~~~~~~~~~~~~^~

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