Submission #1082471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082471		muhammad	Feast (NOI19_feast)	C++17	0 / 100	1100 ms	13872 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) {
            if (all[i]== 0) {
                negativez.push_back(1);
            }else {
                negativez.push_back(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--) {
            int g , s;
            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;
                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++ ) {
                    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;
                    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++ ) {
                        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 {
        sort (negativez.begin(),negativez.end());
        for (int i = 0 ; i < p ; i++ ) {
            answer += pp[i].first ;
        }
        int negative = (int) negativez.size() ;
        if (negativez[negative-1] == 1 ) {
            cout << answer << endl;
        }else {
            int kkk = k - p ; 
            for (int i = negative-1 ; i >= 0 && kkk > 0 ; i-- , kkk-- ) {
                answer += negativez[i] ;
            }
            cout << answer << endl;
        }
    }/*
    //cout << endl; cout << endl;
    for (int i = 0 ; i < p ; i++) {
        cout << pp[i].first << " " << pp[i].second.first << " " << pp[i].second.second<< endl;
        if (i < p-1) {
            cout << nn[i].first << " * " << nn[i].second.first << " * " << nn[i].second.second<< endl;
        }
    }*/
    


    return 0 ;
 }

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

#define ll long long

int main() {
	int n, k;
	cin >> n >> k;

	int a[n];
	for (int &i : a) { cin >> i; }

	auto solve_lambda = [&](ll lmb) {
		pair<ll, ll> dp[n][2];

		dp[0][0] = {0, 0};
		dp[0][1] = {a[0] - lmb, 1};

		for (int i = 1; i < n; i++) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);

			dp[i][1] =
			    max(make_pair(dp[i - 1][0].first + a[i] - lmb,
			                  dp[i - 1][0].second + 1),
			        make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
		}

		return max(dp[n - 1][0], dp[n - 1][1]);
	};

	ll lo = 0;
	ll hi = 1e18;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		solve_lambda(mid).second >= k ? lo = mid : hi = mid - 1;
	}

	cout << solve_lambda(lo).first + lo * k << endl;
}*/

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:81:19: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |             if (g + s >= 0 ) {
      |                 ~~^~~
feast.cpp:84:47: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |                 pp[sg].first += pp[sg1].first + g ;

• 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