Submission #1123478

#TimeUsernameProblemLanguageResultExecution timeMemory
1123478LucaIlieCoin Collecting (JOI19_ho_t4)C++20
100 / 100
128 ms1216 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
int mat[2][MAX_N];

int main() {
    int n;
    long long ans = 0;

    cin >> n;
    for ( int i = 0; i < 2 * n; i++ ) {
        int x, y;
        cin >> x >> y;
        if ( x < 1 ) {
            ans += 1 - x;
            x = 1;
        } else if ( x > n ) {
            ans += x - n;
            x = n;
        }
        if ( y < 1 ) {
            ans += 1 - y;
            y = 1;
        } else if ( y > 2 ) {
            ans += y - 2;
            y = 2;
        }
        mat[y - 1][x - 1]++;
    }

    for ( int c = 0; c < n; c++ ) {
        int a = mat[0][c], b = mat[1][c];
        a--;
        b--;

        //printf( "%d %d %d\n", a, b, ans );

        if ( a < 0 ) {
            int r = max( 0, min( b, -a ) );
            b -= r;
            a += r;
            ans += r;
        }
        if ( b < 0 ) {
            int r = max( 0, min( a, -b ) );
            a -= r;
            b += r;
            ans += r;
        }
        mat[0][c + 1] += a;
        ans += abs( a );
        mat[1][c + 1] += b;
        ans += abs( b );
        //printf( "%d %d %d\n\n", a, b, ans );
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...