Submission #1148072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148072		tito_daynor	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	27 ms	1608 KiB

joi2019_ho_t4

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

const int MAXN = 1e5 + 5;
int dp[MAXN][3];
ll ans = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    for(int i = 1; i <= 2 * n; i++) {
        ll x, y;
        cin >> x >> y;
        
        if(x < 1) {
            ans += 1 - x;
            x = 1;
        }
        if(x > n) {
            ans += x - n;
            x = n;
        }
        if(y < 1) {
            ans += 1 - y;
            y = 1;
        }
        if(y > 2) {
            ans += y - 2;
            y = 2;
        }
        
        dp[x][y]++;
    }
    
    ll carry1 = 0, carry2 = 0;
    for(int i = 1; i <= n; i++) {
        dp[i][1]--;
        dp[i][2]--;
        
        dp[i][1] += carry1;
        dp[i][2] += carry2;
        
        if(dp[i][1] > 0 && dp[i][2] < 0) {
            int move = min(dp[i][1], -dp[i][2]);
            ans += move;
            dp[i][1] -= move;
            dp[i][2] += move;
        }
        if(dp[i][2] > 0 && dp[i][1] < 0) {
            int move = min(dp[i][2], -dp[i][1]);
            ans += move;
            dp[i][2] -= move;
            dp[i][1] += move;
        }
        
        ans += abs(dp[i][1]) + abs(dp[i][2]);
        carry1 = dp[i][1];
        carry2 = dp[i][2];
    }
    
    cout << ans << "\n";
    return 0;
}

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