Submission #580833

#	Time	Username	Problem	Language	Result	Execution time	Memory
580833		JovanB	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	63 ms	8120 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 200000;

ll a[N+5][2], b[N+5][2];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    ll res = 0;
    for(int i=1; i<=2*n; i++){
        int x, y;
        cin >> x >> y;
        if(x < 1){
            res += 1 - x;
            x = 1;
        }
        if(x > n){
            res += x - n;
            x = n;
        }
        if(y < 1){
            res += 1 - y;
            y = 1;
        }
        if(y > 2){
            res += y - 2;
            y = 2;
        }
        a[x][2 - y]++;
    }
    for(int i=1; i<=n; i++) b[i][0] = 1;
    for(int i=1; i<=n; i++) b[i][1] = 1;
    ll c0 = 0, c1 = 0;
    for(int i=1; i<=n; i++){
        ll k = min(a[i][0], b[i][0]);
        a[i][0] -= k, b[i][0] -= k;
        k = min(a[i][1], b[i][1]);
        a[i][1] -= k, b[i][1] -= k;
        k = max(0LL, min(c0, a[i][0]));
        res += i*k;
        c0 -= k, a[i][0] -= k;
        k = max(0LL, min(c1, a[i][1]));
        res += i*k;
        c1 -= k, a[i][1] -= k;
        k = max(0LL, min(c1, a[i][0]));
        res += (i + 1)*k;
        c1 -= k, a[i][0] -= k;
        k = max(0LL, min(c0, a[i][1]));
        res += (i + 1)*k;
        c0 -= k, a[i][1] -= k;
        if(c0 < 0 && b[i][0]){
            b[i][0] = 0;
            res += i;
            c0++;
        }
        if(c1 < 0 && b[i][1]){
            b[i][1] = 0;
            res += i;
            c1++;
        }
        if(a[i][0] && b[i][1]){
            a[i][0]--, b[i][1] = 0;
            res++;
        }
        if(a[i][1] && b[i][0]){
            a[i][1]--, b[i][0] = 0;
            res++;
        }
        if(c1 < 0 && b[i][0]){
            b[i][0] = 0;
            res += i + 1;
            c1++;
        }
        if(c0 < 0 && b[i][1]){
            b[i][1] = 0;
            res += i + 1;
            c0++;
        }
        res -= i*a[i][0];
        c0 -= a[i][0];
        res -= i*a[i][1];
        c1 -= a[i][1];
        if(b[i][0]){
            res -= i;
            c0++;
        }
        if(b[i][1]){
            res -= i;
            c1++;
        }
    }
    if(c0 || c1) cout << "-1\n";
    else cout << res << "\n";
    return 0;
}

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