Submission #869636

#	Time	Username	Problem	Language	Result	Execution time	Memory
869636		Darren0724	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	38 ms	11308 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
const int mod=998244353;


int32_t main(){
    LCBorz;
    int n;cin>>n;
    int m=n*2;
    vector<int> a(m),b(m);
    int ans=0;
    vector<int> dp1(m+1),dp2(m+1);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        int place=0;
        if(a[i]>n){
            place=n;
            ans+=a[i]-n;
        }
        else if(a[i]<1){
            place=1;
            ans+=1-a[i];
        }
        else{
            place=a[i];
        }
        if(b[i]<=1){
            ans+=1-b[i];
            dp1[place]++;
        }
        else{
            ans+=b[i]-2;
            dp2[place]++;
        }
    }
    //cout<<ans<<endl;
    int d1=0,d2=0;
    for(int i=1;i<=n;i++){
        d1+=dp1[i]-1;
        d2+=dp2[i]-1;
        if(d1<0&&d2>0){
            int p=min(-d1,d2);
            d1+=p;
            d2-=p;
            ans+=p;
        }
        if(d1>0&&d2<0){
            int p=min(d1,-d2);
            d1-=p;
            d2+=p;
            ans+=p;
        }
        ans+=abs(d1)+abs(d2);
    }
    cout<<ans<<endl;

    
    return 0;
}

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