Submission #778799

#	Time	Username	Problem	Language	Result	Execution time	Memory
778799		anton	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	130 ms	6056 KiB

joi2019_ho_t4

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


signed main(){
    int n;
    cin>>n;
    vector<pair<int, int>> v(2*n);

    for(int i = 0; i<2*n; i++){
        cin>>v[i].first>>v[i].second;
        v[i].first--;v[i].second--;
    }

    vector<vector<int>> v2(2, vector<int> (n, -1));

    int res= 0;

    for(int i = 0; i<2*n; i++){
        auto cur = v[i];

        if(cur.first<0){
            res += -cur.first;
            cur.first = 0;
        }
        else if(cur.first>=n){
            res += cur.first -(n-1);
            cur.first = n-1;
        }

        if(cur.second<0){
            res+=-cur.second;
            cur.second = 0;
        }
        else if(cur.second>1){
            res += cur.second -1;
            cur.second = 1;
        }

        v2[cur.second][cur.first] ++;
    }

    //cout<<res<<endl;

    vector<int> balance(2, 0);

    for(int i = 0; i<n; i++){
        for(int side= 0; side<2; side++){
            balance[side] += v2[side][i];
        }

        if(balance[0]*balance[1]<0){
            
            int transfer = min(abs(balance[0]), abs(balance[1]));
            if(balance[0]>0){
                balance[0]-= transfer;
                balance[1] += transfer;
            }
            else{
                balance[0]+= transfer;
                balance[1] -= transfer;
            }
            res+=transfer;
        }

        for(int side = 0; side<2; side++){
            res+=abs(balance[side]);
        }
    }

    cout<<res<<endl;

    
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63