Submission #1148055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148055		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	44 ms	5916 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class CoinCollector {
private:
    int N;
    vector<vector<ll>> coins;
    ll result;

    ll processInitialPosition(ll x, ll y) {
        ll moves = 0;
        
        if (x < 1) {
            moves += 1 - x;
            x = 1;
        }
        else if (x > N) {
            moves += x - N;
            x = N;
        }
        
        if (y < 1) {
            moves += 1 - y;
            y = 1;
        }
        else if (y > 2) {
            moves += y - 2;
            y = 2;
        }
        
        coins[x][y-1]++;
        
        return moves;
    }

    ll moveCoins() {
        ll moves = 0;
        int up = 0, down = 0;
        
        for (int i = 1; i <= N; i++) {
            up += coins[i][0];
            down += coins[i][1];
            
            if (up > i && down < i) {
                ll transfer = min(up - i, i - down);
                moves += transfer;
                up -= transfer;
                down += transfer;
            }
            else if (up < i && down > i) {
                ll transfer = min(down - i, i - up);
                moves += transfer;
                up += transfer;
                down -= transfer;
            }
            
            moves += abs(up - i);
            moves += abs(down - i);
        }
        
        return moves;
    }

public:
    ll solve() {
        cin >> N;
        coins.resize(N + 1, vector<ll>(2, 0));
        result = 0;
        
        for (int i = 0; i < 2 * N; i++) {
            ll x, y;
            cin >> x >> y;
            result += processInitialPosition(x, y);
        }
        
        result += moveCoins();
        
        return result;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    CoinCollector solver;
    cout << solver.solve() << endl;
    
    return 0;
}

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