Submission #101992

#	Time	Username	Problem	Language	Result	Execution time	Memory
101992		brcode	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	302 ms	5028 KiB

joi2019_ho_t4

#include <iostream>

using namespace std;
int r[2];
long long ans;
int c[100100][2];
int main(){
    int n;
    cin>>n;
    
    for(int i=0;i<n*2;i++){
        int x,y;
        cin>>x>>y;
        if(x<1){
            ans+=(1-x);
            x= 1;
            
        }
        if(x>n){
            ans+=(x-n);
            x=n;
        }
        if(y<1){
            ans+=1-y;
            y=1;
        }
        if(y>2){
            ans+=y-2;
            y=2;
        }
        //shift all coins into the rectangle itself
        c[x][y-1]++;
    }
    for(int i=1;i<=n;i++){
        r[0]+=c[i][0]-1;
        r[1]+=c[i][1]-1;
        //go from l to r for the 2 columns, keeping track of the number of empty positions/ amount coins have had to move. 
        for(int k=0;k<2;k++){
            if(r[k]>0 && r[!k]<0){
                //if coins can be shifted to empty positions in a different row, shift them
                int x = min(r[k],-1*r[!k]);
                ans+=x;
                r[k]-=x;
                r[!k]+=x;
            }
        }
        ans+=abs(r[0])+abs(r[1]);
        //amount coins have moved or will have to move
    }
    cout<<ans<<endl;
}

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