Submission #1122253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122253		Aviansh	Feast (NOI19_feast)	C++17	0 / 100	1066 ms	51348 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>e){
        return 0LL;
    }
    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]});
        //cout <<"adding to joins: "<< prefsum(pref,las+1,(*it)[0]-1) << " " << las << " " << (*it)[0] << "\n";
        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]});
        //cout << "adding to rangsums: " << prefsum(pref,a[0],a[1]) << " " << a[0]<< " " <<a[1] << "\n";
    }
    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(joins.size()){
        array<long long,3>curr = joins.top();
        assert(curr[0]<=0);
        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;
        assert(curr[2]==up[0]);
        assert(curr[1]==down[1]);
        rangs.erase(up);
        rangs.erase(down);
        //cout << "finding: " << prefsum(pref,down[0],down[1]) << " " << down[0] << " " << down[1] << "\n";
        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);
          //  cout << "erased: " << prefsum(pref,down[0],down[1]) << " " << down[0] << " " << down[1] << "\n";
            sum-=prefsum(pref,down[0],down[1]);
        }
        //cout << "finding: " << prefsum(pref,up[0],up[1]) << " " << up[0] << " " << up[1] << "\n";
        c = rangsums.find({prefsum(pref,up[0],up[1]),up[0],up[1]});
        if(c!=rangsums.end()){
            rangsums.erase(c);
          //  cout << "erased: " << prefsum(pref,up[0],up[1]) << " " << up[0] << " " << up[1] << "\n";
            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]});
        //cout << "adding: " << prefsum(pref,down[0],up[1]) << " " << down[0] << " " << up[1] << "\n";
        sum+=prefsum(pref,down[0],up[1]);
        while(rangsums.size()>k){
            array<long long,3>curr = *rangsums.begin();
            sum-=curr[0];
            //cout << "erased: " << curr[0] << " " << curr[1] << " " << curr[2] << "\n";
            rangsums.erase(rangsums.begin());
        }
        vector<long long>sums;
        for(array<int,2>a:rangs){
            sums.push_back(prefsum(pref,a[0],a[1]));
        }
        sort(sums.rbegin(),sums.rend());
        sum=0;
        for(int i = 0;i<min(k,(int)sums.size());i++){
            sum+=sums[i];
        }
        ans=max(ans,sum);
    }
    assert(rangs.size()==1);
    cout << ans;
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:54: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]
   54 |     while(rangsums.size()>k){
      |           ~~~~~~~~~~~~~~~^~
feast.cpp:67: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]
   67 |         set<array<int,2>>::iterator it = rangs.lower_bound({curr[2],-1});
      |                                                                        ^
feast.cpp:93: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]
   93 |         while(rangsums.size()>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