제출 #1122257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122257		Aviansh	Feast (NOI19_feast)	C++17	12 / 100	548 ms	46228 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++;
    }
    set<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});
        assert(it!=rangs.end());
        assert(it!=rangs.end());
        array<int,2>up = *it;
        assert(it!=rangs.begin());
        it--;
        assert(it!=rangs.end());
        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";
        set<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]});
        if(prefsum(pref,down[0],up[1])>0){
            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());
        }
        ans=max(ans,sum);
    }
    assert(rangs.size()==1);
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int main()':
feast.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::set<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:99:30: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         while(rangsums.size()>k){
      |               ~~~~~~~~~~~~~~~^~

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