Submission #869078

#	Time	Username	Problem	Language	Result	Execution time	Memory
869078		Darren0724	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	348 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]++;
        }
    }
    /*for(int i=1;i<=n;i++){
        cout<<dp1[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<dp2[i]<<' ';
    }
    cout<<endl;
    cout<<ans<<endl;*/
    for(int i=1;i<=n;i++){
        //cout<<dp1[i]<<' '<<dp2[i]<<endl;
        if(dp1[i]+dp2[i]>=2){
            if(dp1[i]==0){
                dp1[i]=1;
                dp2[i]--;
                ans++;
            }
            if(dp2[i]==0){
                dp2[i]=1;
                dp1[i]--;
                ans++;
            }
            dp1[i+1]+=dp1[i]-1;
            dp2[i+1]+=dp2[i]-1;
            ans+=dp1[i]+dp2[i]-2;
            dp1[i]=1;
            dp2[i]=1;
        }
        else{
            if(dp1[i]==0){
                for(int j=i+1;j<=n;j++){
                    if(dp1[j]>1){
                        dp1[j]--;
                        ans+=j-i;
                        break;
                    }
                    if(dp2[j]>1){
                        dp2[j]--;
                        ans+=j-i+1;
                        break;
                    }
                }
                dp1[i]=1;
            }
            if(dp2[i]==0){
                for(int j=i+1;j<=n;j++){
                    if(dp2[j]>1){
                        dp2[j]--;
                        ans+=j-i;
                        break;
                    }
                    if(dp1[j]>1){
                        dp1[j]--;
                        ans+=j-i+1;
                        break;
                    }
                }
                dp2[i]=1;
            }
            dp1[i+1]+=dp1[i]-1;
            dp2[i+1]+=dp2[i]-1;
            ans+=dp1[i]+dp2[i]-2;
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
    return 0;
}

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