Submission #914695

#	Time	Username	Problem	Language	Result	Execution time	Memory
914695		WongYiKai	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	39 ms	7256 KiB

joi2019_ho_t4

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

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	ll total=0;
	ll dp[3][n+1];
	memset(dp,0,sizeof(dp));
	for (int i=0;i<n*2;i++){
		ll x,y;
		cin >> x >> y;
		if (y<=1) {
			total += 1-y;
			y = 1;
		}
		else {
			total += y-2;
			y = 2;
		}
		if (x < 1){
			total += 1-x;
			x=1;
		}
		else if (x>n){
			total += x-n;
			x=n;
		}
		dp[y][x]++;
	}
	ll top=0,down=0;
	for (int i=1;i<=n;i++){
		top += dp[1][i]-1;
		down += dp[2][i]-1;
		if (top<0 && down>0){
			ll val = min(-top,down);
			total += val;
			top+=val;
			down-=val;
		}
		if (down<0 && top>0){
			ll val = min(top,-down);
			total += val;
			top -= val;
			down += val;
		}
		total += abs(top);
		total += abs(down);
	}
	cout << total;
}

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