Submission #300930

#	Time	Username	Problem	Language	Result	Execution time	Memory
300930		pit4h	Coin Collecting (JOI19_ho_t4)	C++14	100 / 100	85 ms	9080 KiB

joi2019_ho_t4

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<vector<int>> cnt(n+1, vector<int>(3));
	ll ans = 0;
	for(int i=0; i<2*n; ++i) {
		ll x, y; cin>>x>>y;
		ll nx = max(1LL, min((ll)n, x));
		ll ny = max(1LL, min(2LL, y));
		cnt[nx][ny]++;
		ans += abs(x - nx) + abs(y - ny);
	}
	vector<int> filled(3);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=2; ++j) {
			int fill = min(i - filled[j], cnt[i][j]); 
			ans += (ll)(i-filled[j]-1) * fill - (ll)fill * (fill-1) / 2;
			filled[j] += fill;
			cnt[i][j] -= fill;
		}
		for(int j=1; j<=2; ++j) {
			int fill = min(i - filled[j%2+1], cnt[i][j]);
			ans += (ll)(i-filled[j%2+1]-1) * fill - (ll)fill * (fill-1) / 2 + (ll)fill;
			filled[j%2+1] += fill;
			cnt[i][j] -= fill;
		}
		if(i+1 <= n) {
			for(int j=1; j<=2; ++j) {
				ans += cnt[i][j];
				cnt[i+1][j] += cnt[i][j];
			}
		}
	}
	cout<<ans;
}

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