Submission #99697

#	Time	Username	Problem	Language	Result	Execution time	Memory
99697		cki86201	Coin Collecting (JOI19_ho_t4)	C++11	0 / 100	3 ms	896 KiB

joi2019_ho_t4

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N;
pii p[200010];
ll ans;
int X[100010][2];

void upd(ll &a, ll b) { if(a > b) a = b; }
ll dis(pii a, pii b) { return (ll)abs(a.Fi - b.Fi) + abs(a.Se - b.Se); }

ll dp[1010][1010];

ll calc(int l, int r) {
	vector <pii> pts;
	for(int i=l;i<=r;i++) rep(v, 2) rep(j, X[i][v]) pts.pb(pii(i - l + 1, v + 1));
	int N = r - l + 1;
	for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) dp[i][j] = 1e18;
	dp[0][0] = 0;
	for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) {
		pii pv = pts[i + j];
		if(i < N) {
			upd(dp[i+1][j], dis(pv, pii(i+1, 1)) + dp[i][j]);
		}
		if(j < N) {
			upd(dp[i][j+1], dis(pv, pii(j+1, 2)) + dp[i][j]);
		}
	}
	return dp[N][N];
}

int main() {
	scanf("%d", &N);
	if(N > 1000) return 0;
	for(int i=1;i<=2*N;i++) {
		int x, y; scanf("%d%d", &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;
		p[i] = pii(x, y);
		X[x][y-1]++;
	}
	int V[100010] = {}, cc[2] = {};
	int prv = 0;
	for(int i=1;i<=N;i++) {
		V[i] = V[i-1] - 2 + X[i][0] + X[i][1];
		cc[0] += X[i][0] - 1;
		cc[1] += X[i][1] - 1;
		if(V[i] == 0) {
			ans += calc(prv + 1, i);
			cc[0] = cc[1] = 0;
			prv = i;
		}
		else if(V[i-1] != 0 && (ll)V[i] * V[i-1] < 0) {
			if(V[i] > 0) {
				while(V[i] > 0) {
					if(X[i][1] == 0 || (cc[0] >= cc[1] && X[i][0] > 0)) --cc[0], ++X[i+1][0], --X[i][0], ++ans, --V[i];
					else --cc[1], ++X[i+1][1], --X[i][1], ++ans, --V[i];
				}
				ans += calc(prv + 1, i);
				cc[0] = cc[1] = 0;
				prv = i;
			}
			else {
				int t = 0;
				if(cc[0] < cc[1]) t = 1;
				int lst = -1;
				for(int f=i;f>prv;f--) if(X[f][t]) {
					lst = f; break;
				}
				X[lst][t]--; X[i][t]++;
				ans += i - lst;
				ans += calc(prv + 1, i - 1);
				prv = i - 1;
				V[i-1] = 0; --i;
			}
		}
	}
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
joi2019_ho_t4.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

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