Submission #99047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99047	2019-02-28T07:59:46 Z	구재현(#2854, gs14004)	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	22 ms	20736 KB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
using lint = long long;
using pi = pair<int, int>;

struct pnt{
	int x, y;
	bool operator<(const pnt &p)const{
		return pi(x, y) < pi(p.x, p.y);
	}
}a[MAXN];

int n;
int cnt[3][MAXN];
lint dp[MAXN][13];

lint sum(int x){ return 1ll * x * (x + 1) / 2; }

lint sum_intv(int l, int r, int x){
	if(l <= x && x < r){
		return sum(x - l) + sum(r - 1 - x);
	}
	if(x >= r) return sum(x - l) - sum(x - r);
	return sum(r - x - 1) - sum(l - x - 1);
}

lint f(int l, int r, int pos){
	if(pos == n + 1) return l == r ? 0 : 1e18;
	if(cnt[1][pos] == 0 && cnt[2][pos] == 0) return f(l, r, pos + 1);
	if(~dp[l][r-l+6]) return dp[l][r-l+6];
	int up = cnt[1][pos];
	int dn = cnt[2][pos];
	int sum = (l + r + up + dn);
	lint ret = 1e18;
	for(int i=sum/2-2; i<=sum/2+2; i++){
		int nl = i, nr = sum - i;
		if(l > nl || r > nr) continue;
		lint cost = f(nl, nr, pos + 1);
		cost += abs(up - (nl - l));
		cost += sum_intv(l, nl, pos);
		cost += sum_intv(r, nr, pos);
		ret = min(ret, cost);
	}
	return dp[l][r-l+6] = ret;
}

int main(){
	scanf("%d",&n);
	memset(dp, -1, sizeof(dp));
	lint cdap = 0;
	for(int i=0; i<n*2; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
		if(a[i].x < 1){
			cdap += 1 - a[i].x;
			a[i].x = 1;
		}
		if(a[i].x > n){
			cdap += a[i].x - n;
			a[i].x = n;
		}
		if(a[i].y < 1){
			cdap += 1 - a[i].y;
			a[i].y = 1;
		}
		if(a[i].y > 2){
			cdap += a[i].y - 2;
			a[i].y = 2;
		}
		cnt[a[i].y][a[i].x]++;
	}
	sort(a, a + n + n);
	cout << cdap + f(1, 1, 1) << endl;
}

Compilation message

joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:49: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:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].x,&a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	20736 KB	Output is correct
2	Correct	19 ms	20736 KB	Output is correct
3	Correct	19 ms	20628 KB	Output is correct
4	Correct	19 ms	20736 KB	Output is correct
5	Correct	18 ms	20736 KB	Output is correct
6	Correct	19 ms	20736 KB	Output is correct
7	Correct	17 ms	20736 KB	Output is correct
8	Correct	17 ms	20736 KB	Output is correct
9	Correct	18 ms	20736 KB	Output is correct
10	Correct	19 ms	20736 KB	Output is correct
11	Correct	22 ms	20736 KB	Output is correct
12	Correct	17 ms	20736 KB	Output is correct
13	Correct	17 ms	20728 KB	Output is correct
14	Correct	18 ms	20736 KB	Output is correct
15	Correct	19 ms	20736 KB	Output is correct
16	Correct	21 ms	20736 KB	Output is correct
17	Correct	17 ms	20736 KB	Output is correct
18	Correct	17 ms	20736 KB	Output is correct
19	Correct	18 ms	20736 KB	Output is correct
20	Correct	21 ms	20732 KB	Output is correct
21	Correct	21 ms	20736 KB	Output is correct
22	Correct	18 ms	20736 KB	Output is correct
23	Correct	19 ms	20736 KB	Output is correct
24	Correct	18 ms	20708 KB	Output is correct
25	Correct	19 ms	20660 KB	Output is correct
26	Correct	17 ms	20736 KB	Output is correct
27	Correct	17 ms	20716 KB	Output is correct
28	Incorrect	20 ms	20736 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #2
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	20736 KB	Output is correct
2	Correct	19 ms	20736 KB	Output is correct
3	Correct	19 ms	20628 KB	Output is correct
4	Correct	19 ms	20736 KB	Output is correct
5	Correct	18 ms	20736 KB	Output is correct
6	Correct	19 ms	20736 KB	Output is correct
7	Correct	17 ms	20736 KB	Output is correct
8	Correct	17 ms	20736 KB	Output is correct
9	Correct	18 ms	20736 KB	Output is correct
10	Correct	19 ms	20736 KB	Output is correct
11	Correct	22 ms	20736 KB	Output is correct
12	Correct	17 ms	20736 KB	Output is correct
13	Correct	17 ms	20728 KB	Output is correct
14	Correct	18 ms	20736 KB	Output is correct
15	Correct	19 ms	20736 KB	Output is correct
16	Correct	21 ms	20736 KB	Output is correct
17	Correct	17 ms	20736 KB	Output is correct
18	Correct	17 ms	20736 KB	Output is correct
19	Correct	18 ms	20736 KB	Output is correct
20	Correct	21 ms	20732 KB	Output is correct
21	Correct	21 ms	20736 KB	Output is correct
22	Correct	18 ms	20736 KB	Output is correct
23	Correct	19 ms	20736 KB	Output is correct
24	Correct	18 ms	20708 KB	Output is correct
25	Correct	19 ms	20660 KB	Output is correct
26	Correct	17 ms	20736 KB	Output is correct
27	Correct	17 ms	20716 KB	Output is correct
28	Incorrect	20 ms	20736 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	20736 KB	Output is correct
2	Correct	19 ms	20736 KB	Output is correct
3	Correct	19 ms	20628 KB	Output is correct
4	Correct	19 ms	20736 KB	Output is correct
5	Correct	18 ms	20736 KB	Output is correct
6	Correct	19 ms	20736 KB	Output is correct
7	Correct	17 ms	20736 KB	Output is correct
8	Correct	17 ms	20736 KB	Output is correct
9	Correct	18 ms	20736 KB	Output is correct
10	Correct	19 ms	20736 KB	Output is correct
11	Correct	22 ms	20736 KB	Output is correct
12	Correct	17 ms	20736 KB	Output is correct
13	Correct	17 ms	20728 KB	Output is correct
14	Correct	18 ms	20736 KB	Output is correct
15	Correct	19 ms	20736 KB	Output is correct
16	Correct	21 ms	20736 KB	Output is correct
17	Correct	17 ms	20736 KB	Output is correct
18	Correct	17 ms	20736 KB	Output is correct
19	Correct	18 ms	20736 KB	Output is correct
20	Correct	21 ms	20732 KB	Output is correct
21	Correct	21 ms	20736 KB	Output is correct
22	Correct	18 ms	20736 KB	Output is correct
23	Correct	19 ms	20736 KB	Output is correct
24	Correct	18 ms	20708 KB	Output is correct
25	Correct	19 ms	20660 KB	Output is correct
26	Correct	17 ms	20736 KB	Output is correct
27	Correct	17 ms	20716 KB	Output is correct
28	Incorrect	20 ms	20736 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Submission #99047

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 0 / 63.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
0 / 63.0