Submission #104329

#	Time	Username	Problem	Language	Result	Execution time	Memory
104329		ihdignite	Coin Collecting (JOI19_ho_t4)	C++14	8 / 100	166 ms	157052 KiB

joi2019_ho_t4

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

#define ll long long

const int mxN=1e5;
int n;
ll a1, dp[2*mxN+1][100];
array<int, 3> a[2*mxN];

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

	cin >> n;
	for(int i=0; i<2*n; ++i) {
		cin >> a[i][0] >> a[i][2];
		a[i][1]=rand();
		if(a[i][0]<1) {
			a1+=1-a[i][0];
			a[i][0]=1;
		} else if(a[i][0]>n) {
			a1+=a[i][0]-n;
			a[i][0]=n;
		}
		if(a[i][2]<1) {
			a1+=1-a[i][2];
			a[i][2]=1;
		} else if(a[i][2]>2) {
			a1+=a[i][2]-2;
			a[i][2]=2;
		}
	}
	sort(a, a+2*n);
	memset(dp, 0x3f, sizeof(dp));
	dp[0][48]=a1;
	for(int i=0; i<2*n; ++i) {
		for(int j=max(i/2-46, 0); j<=min(i/2+46, n); ++j) {
			if(j<n)
				dp[i+1][j-(i+1)/2+49]=min(dp[i][j-i/2+48]+abs(j+1-a[i][0])+(a[i][2]!=1), dp[i+1][j-(i+1)/2+49]);
			dp[i+1][j-(i+1)/2+48]=min(dp[i][j-i/2+48]+abs(i-j+1-a[i][0])+(a[i][2]!=2), dp[i+1][j-(i+1)/2+48]);
		}
	}
	cout << dp[2*n][48];
}

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