Submission #1082636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082636		muhammad	Feast (NOI19_feast)	C++17	0 / 100	73 ms	13616 KiB

feast

#include <bits/stdc++.h>
using namespace std ;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) ;
 // freopen("tallbarn.in", "r", stdin);
 // freopen("tallbarn.out", "w", stdout);


    int p=0 , n , k ;
    cin >> n >> k ;
    int answer = 0 ;
    int all [n] ;
    vector <pair<int,pair<int,int>>> pp ;
    vector <pair<int,pair<int,int>>> nn ;
    vector<int> negativez ;
    int neg = 0 ;
    for (int i  = 0 ; i < n ; i++ ) {
        cin >> all[i] ;
        if (all[i] > 0 ) {
            p++ ;
            pp.push_back( {all[i], {-1,-1} }  ) ;
            if (p>=2) {
                pp[p-2].second.second = p-2 ;
                pp[p-1].second.first = p-2 ;
                nn.push_back({neg, {p-2,p-1} } ) ;
                neg = 0 ;
            }
        }else if (p >=1 && all[i] <= 0  ) {
                neg+= all[i] ;
        }
    }
    sort (pp.begin(),pp.end()) ;
    for (int i = 0 ; i < p ; i++ ) {
        if (pp[i].second.first!=-1) {
            int sf = pp[i].second.first ;
            nn[sf].second.second = i ;
        }
        if (pp[i].second.second!=-1) {
            int sf = pp[i].second.second ;
            nn[sf].second.first = i ;
        }
    }
    if (p >= k) {
        sort (nn.rbegin(),nn.rend()) ;
        for (int i = 0 ; i < p-1;i++) {
            int sf = nn[i].second.first;
            pp[sf].second.second = i ;
            sf = nn[i].second.second ;
            pp[sf].second.first = i ;
        }
        int kk = p;
        int hg=0,hs=0 ;
        for (int i = kk ; i > k ; i/=2) {
            int g = 0 , s =0;
            for (int ii = hg ; ii < p-1;ii++ ) {
                if (nn[ii].first <= 0 ) {
                    g = nn[ii].first ;
                    hg = ii ;
                    break;
                }
            }
            for (int ii = hs ; ii < p ; ii++) {
                if (pp[ii].first > 0 ) {
                    s = pp[ii].first ;
                    hs= ii ;
                    break;
                }
            }
            if (g + s >= 0 ) {
                int sg = nn[hg].second.second;
                int sg1= nn[hg].second.first;
                if (sg>sg1) {
                        pp[sg].first += pp[sg1].first + g ;
                        nn[hg].first = 1 ;
                        pp[sg].second.first = pp[sg1].second.first;
                        if (pp[sg1].second.first !=-1) {
                            nn[pp[sg1].second.first ].second.second= sg;
                        }
                        pp[sg1].first = -1 ;
                        for (int ii = sg ; ii < p-1 && ii < p-k ; ii++ ) {
                            if (pp[ii].first > pp[ii+1].first) {
                                swap (pp[ii],pp[ii+1]);
                                if ( pp[ii+1].second.first !=-1) {
                                    nn[pp[ii+1].second.first].second.second = ii+1;
                                }
                                if ( pp[ii+1].second.second!=-1) {
                                    nn[pp[ii+1].second.second].second.first = ii+1;
                                }
                                if (pp[ii].first != -1  ){
                                    if ( pp[ii].second.first!=-1) {
                                        nn[pp[ii].second.first].second.second = ii ;
                                    }
                                    if (pp[ii].second.second!=-1) {
                                        nn[pp[ii].second.second].second.first = ii ;
                                    }
                                }
                            }else {
                                break;
                            }
                        }
                }else {
                        swap (sg,sg1);
                        pp[sg].first += pp[sg1].first + g ;
                        nn[hg].first = 1 ;
                        pp[sg].second.second = pp[sg1].second.second;
                        if (pp[sg1].second.second !=-1) {
                            nn[pp[sg1].second.second ].second.first= sg;
                        }
                        pp[sg1].first = -1 ;
                        for (int ii = sg ; ii < p-1 && ii < p-k ; ii++ ) {
                            if (pp[ii].first > pp[ii+1].first) {
                                swap (pp[ii],pp[ii+1]);
                                if ( pp[ii+1].second.first !=-1) {
                                    nn[pp[ii+1].second.first].second.second = ii+1;
                                }
                                if ( pp[ii+1].second.second!=-1) {
                                    nn[pp[ii+1].second.second].second.first = ii+1;
                                }
                                if (pp[ii].first != -1  ){
                                    if ( pp[ii].second.first!=-1) {
                                        nn[pp[ii].second.first].second.second = ii ;
                                    }
                                    if (pp[ii].second.second!=-1) {
                                        nn[pp[ii].second.second].second.first = ii ;
                                    }
                                }
                            }else {
                                break;
                            }
                        }
                }
            }else {
                if (pp[hs].second.first == -1 || pp[hs].second.second == -1 ) {
                    pp[hs].first = -1;
                    if (pp[hs].second.first == -1 ) {
                        nn[pp[hs].second.second].first = 1 ;
                        pp[nn[pp[hs].second.second].second.second].second.first = -1 ;
                    }else {
                        nn[pp[hs].second.first].first = 1 ;
                        pp[nn[pp[hs].second.first].second.first].second.second = -1;
                    }
                }else {
                    int sg = pp[hs].second.second;
                    int sg1= pp[hs].second.first;
                    if (sg < sg1) {
                            nn[sg].first += nn[sg1].first + s ;
                            pp[hs].first = -1 ;
                            nn[sg].second.first = nn[sg1].second.first;
                            pp[nn[sg1].second.first ].second.second= sg;
                            nn[sg1].first = 1 ;
                            for (int ii = sg ; ii < p-2 && ii < p-k ; ii++ ) {

                                if (nn[ii].first < nn[ii+1].first) {
                                    swap (nn[ii],nn[ii+1]);
                                    pp[nn[ii+1].second.first].second.second = ii+1;
                                    pp[nn[ii+1].second.second].second.first = ii+1;
                                if (nn[ii].first !=1) {
                                        pp[nn[ii].second.first].second.second = ii ;
                                        pp[nn[ii].second.second].second.first = ii ;
                                }
                                }else {
                                    break;
                                }
                            }
                    }else {
                        swap (sg,sg1) ;
                            nn[sg].first += nn[sg1].first + s ;
                            pp[hs].first = -1 ;
                            nn[sg].second.second = nn[sg1].second.second;
                            pp[nn[sg1].second.second ].second.first= sg;
                            nn[sg1].first = 1 ;
                            for (int ii = sg ; ii < p-2 && ii < p-k ; ii++ ) {

                                if (nn[ii].first < nn[ii+1].first) {
                                    swap (nn[ii],nn[ii+1]);
                                    pp[nn[ii+1].second.first].second.second = ii+1;
                                    pp[nn[ii+1].second.second].second.first = ii+1;
                                if (nn[ii].first !=1) {
                                        pp[nn[ii].second.first].second.second = ii ;
                                        pp[nn[ii].second.second].second.first = ii ;
                                }
                                }else {
                                    break;
                                }
                            }
                    }  
                }
            }
        }
        for (int i = 0 ; i < p ; i++ ) {
            if ( pp[i].first!= -1 ) {
                answer += pp[i].first  ;
            }
        }
        cout << answer << endl;
    }else {
        for (int i = 0 ; i < p ; i++ ) {
            answer += pp[i].first ;
        }
            cout << answer << endl;
    }



    return 0 ;
 }
 

• 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