Submission #121329

#	Time	Username	Problem	Language	Result	Execution time	Memory
121329		onjo0127	Coin Collecting (JOI19_ho_t4)	C++11	100 / 100	68 ms	1784 KiB

joi2019_ho_t4

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

const long long INF = 1LL * 1e18;
int A[100009], B[100009];

inline int d(int a, int b, int c, int d) {
	return max(a - c, c - a) + max(b - d, d - b);
}

int main() {
	long long s = 0;
	int N; scanf("%d",&N);
	for(int i=0; i<2*N; i++) {
		int X, Y; scanf("%d%d",&X,&Y);
		if(Y <= 1) {
			if(Y == 1 && 1 <= X && X <= N) ++A[X];
			else if(X <= 1) ++A[1], s += d(1, 1, X, Y);
			else if(N <= X) ++A[N], s += d(N, 1, X, Y);
			else ++A[X], s += d(X, 1, X, Y);
		}
		else {
			if(Y == 2 && 1 <= X && X <= N) ++B[X];
			else if(X <= 1) ++B[1], s += d(1, 2, X, Y);
			else if(N <= X) ++B[N], s += d(N, 2, X, Y);
			else ++B[X], s += d(X, 2, X, Y);
		}
	}
	for(int i=1; i<=N; i++) --A[i], --B[i];
	for(int i=1; i<=N; i++) {
		if(A[i] >= 0 && B[i] >= 0) s += A[i] + B[i];
		else if(A[i] <= 0 && B[i] <= 0) s += - A[i] - B[i];
		else {
			int tmp = min(max(A[i], -A[i]), max(B[i], -B[i]));
			s += tmp;
			if(A[i] < 0) A[i] += tmp, B[i] -= tmp, s += - A[i] + B[i];
			else A[i] -= tmp, B[i] += tmp, s += A[i] - B[i];
		}
		A[i+1] += A[i];
		B[i+1] += B[i];
	}
	printf("%lld", s);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:15: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: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 63 / 63