Submission #1006584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006584		_callmelucian	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	35 ms	5716 KiB

joi2019_ho_t4

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 1e5 + 5;
int cnt[3][mn];

ll dist (ll x1, ll y1, ll x2, ll y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; ll ans = 0; cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
        int x, y; cin >> x >> y;
        int r = (y >= 2 ? 2 : 1), c = (x <= 1 ? 1 : (x >= n ? n : x));
        cnt[r][c]++, ans += dist(y, x, r, c);
    }
    for (int i = 1; i <= n; i++) cnt[1][i]--, cnt[2][i]--;

    for (int i = 1; i <= n; i++) {
        if (cnt[1][i] > 0 && cnt[2][i] < 0) {
            // pass from row 1 to 2
            int pass = min(cnt[1][i], -cnt[2][i]);
            cnt[1][i] -= pass, cnt[2][i] += pass, ans += pass;
        }
        if (cnt[1][i] < 0 && cnt[2][i] > 0) {
            // pass from row 2 to 1
            int pass = min(-cnt[1][i], cnt[2][i]);
            cnt[1][i] += pass, cnt[2][i] -= pass, ans += pass;
        }
        if (i < n) {
            // pass from column i to i + 1 (also pass "debt")
            cnt[1][i + 1] += cnt[1][i], cnt[2][i + 1] += cnt[2][i];
            ans += abs(cnt[1][i]) + abs(cnt[2][i]);
        }
    }

    cout << ans;

    return 0;
}

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