Submission #1028163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028163		snpmrnhlol	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	121 ms	8292 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
struct xy{
    ll x,y;
}v[N*2];
ll f[N][2];
ll f2[2];
int main(){
    ll n;
    ll ans = 0;
    cin>>n;
    for(ll i = 0;i < 2*n;i++){
        cin>>v[i].x>>v[i].y;
        v[i].x--;v[i].y--;
        if(0 > v[i].x || v[i].x > n - 1){
            ans+=min(abs(v[i].x - 0),abs(v[i].x - (n - 1)));
        }
        ans+=min(abs(v[i].y - 0),abs(v[i].y - 1));
        v[i].x = max(v[i].x,0ll);
        v[i].y = max(v[i].y,0ll);
        v[i].x = min(v[i].x,n - 1);
        v[i].y = min(v[i].y,1ll);
        f[v[i].x][v[i].y]++;
    }
    for(int i = 0;i < n;i++){
        f2[0]+=f[i][0];
        f2[1]+=f[i][1];
        f2[0]--;
        f2[1]--;
        if(f2[0] > 0 && f2[1] < 0){
            int x = min(f2[0],-f2[1]);
            f2[0]-=x;
            f2[1]+=x;
            ans+=x;
        }
        if(f2[0] < 0 && f2[1] > 0){
            int x = min(-f2[0],f2[1]);
            f2[0]+=x;
            f2[1]-=x;
            ans+=x;
        }
        if(i != n - 1){
            ans+=abs(f2[1]);
            ans+=abs(f2[0]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}

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