답안 #99068 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99068	2019-02-28T09:03:18 Z	구재현(#2854, gs14004)	Coin Collecting (JOI19_ho_t4)	C++17	8 / 100	904 ms	110248 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][50];

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);
}

int thres[MAXN];
map<pi, lint> mp;

bool insec(int l, int r, int ll, int rr){
	return max(l, ll) <= min(r, rr) + 10;
}

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(mp.find(pi(l, r)) != mp.end()) return mp[pi(l, r)];
	int up = cnt[1][pos];
	int dn = cnt[2][pos];
	int sum = l + r + up + dn;
	lint ret = 1e18;
	vector<int> v = {0, up, up + dn, sum / 2 - 1 - l, sum / 2 - l, sum / 2 + 1 - l};
	for(auto &i : v){
		if(i > up + dn) continue;
		if(i < 0) continue;
		int nl = l + i, nr = up + dn - i + r;
		if(nl > n + 1){
			nr += (nl - (n + 1));
			nl = n + 1;
		}
		if(nr > n + 1){
			nl += (nr - (n + 1));
			nr = n + 1;
		}
		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 mp[pi(l, r)] = 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]++;
	}
	for(int i=1; i<=n; i++){
		for(int j=-2; j<=2; j++){
			if(i + j >= 1 && i + j <= n){
				thres[i] += cnt[1][i+j] + cnt[2][i+j];
			}
		}
	}
	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:66: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:70: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
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	78584 KB	Output is correct
2	Correct	62 ms	78712 KB	Output is correct
3	Correct	67 ms	78588 KB	Output is correct
4	Correct	67 ms	78584 KB	Output is correct
5	Correct	70 ms	78632 KB	Output is correct
6	Correct	74 ms	78584 KB	Output is correct
7	Correct	70 ms	78664 KB	Output is correct
8	Correct	71 ms	78788 KB	Output is correct
9	Correct	67 ms	78712 KB	Output is correct
10	Correct	67 ms	78584 KB	Output is correct
11	Correct	64 ms	78740 KB	Output is correct
12	Correct	65 ms	78584 KB	Output is correct
13	Correct	64 ms	78584 KB	Output is correct
14	Correct	67 ms	78588 KB	Output is correct
15	Correct	68 ms	78840 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	65 ms	78584 KB	Output is correct
18	Correct	70 ms	78588 KB	Output is correct
19	Correct	72 ms	78584 KB	Output is correct
20	Correct	69 ms	78712 KB	Output is correct
21	Correct	68 ms	78596 KB	Output is correct
22	Correct	74 ms	78584 KB	Output is correct
23	Correct	68 ms	78712 KB	Output is correct
24	Correct	65 ms	78556 KB	Output is correct
25	Correct	65 ms	78584 KB	Output is correct
26	Correct	63 ms	78584 KB	Output is correct
27	Correct	70 ms	78716 KB	Output is correct
28	Correct	69 ms	78712 KB	Output is correct
29	Correct	70 ms	78612 KB	Output is correct
30	Correct	62 ms	78584 KB	Output is correct
31	Correct	65 ms	78584 KB	Output is correct
32	Correct	74 ms	78712 KB	Output is correct
33	Correct	65 ms	78588 KB	Output is correct

Subtask #2
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	78584 KB	Output is correct
2	Correct	62 ms	78712 KB	Output is correct
3	Correct	67 ms	78588 KB	Output is correct
4	Correct	67 ms	78584 KB	Output is correct
5	Correct	70 ms	78632 KB	Output is correct
6	Correct	74 ms	78584 KB	Output is correct
7	Correct	70 ms	78664 KB	Output is correct
8	Correct	71 ms	78788 KB	Output is correct
9	Correct	67 ms	78712 KB	Output is correct
10	Correct	67 ms	78584 KB	Output is correct
11	Correct	64 ms	78740 KB	Output is correct
12	Correct	65 ms	78584 KB	Output is correct
13	Correct	64 ms	78584 KB	Output is correct
14	Correct	67 ms	78588 KB	Output is correct
15	Correct	68 ms	78840 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	65 ms	78584 KB	Output is correct
18	Correct	70 ms	78588 KB	Output is correct
19	Correct	72 ms	78584 KB	Output is correct
20	Correct	69 ms	78712 KB	Output is correct
21	Correct	68 ms	78596 KB	Output is correct
22	Correct	74 ms	78584 KB	Output is correct
23	Correct	68 ms	78712 KB	Output is correct
24	Correct	65 ms	78556 KB	Output is correct
25	Correct	65 ms	78584 KB	Output is correct
26	Correct	63 ms	78584 KB	Output is correct
27	Correct	70 ms	78716 KB	Output is correct
28	Correct	69 ms	78712 KB	Output is correct
29	Correct	70 ms	78612 KB	Output is correct
30	Correct	62 ms	78584 KB	Output is correct
31	Correct	65 ms	78584 KB	Output is correct
32	Correct	74 ms	78712 KB	Output is correct
33	Correct	65 ms	78588 KB	Output is correct
34	Correct	830 ms	110248 KB	Output is correct
35	Correct	75 ms	78712 KB	Output is correct
36	Correct	775 ms	105804 KB	Output is correct
37	Correct	850 ms	105864 KB	Output is correct
38	Correct	891 ms	106420 KB	Output is correct
39	Correct	832 ms	106192 KB	Output is correct
40	Correct	799 ms	105276 KB	Output is correct
41	Correct	67 ms	78712 KB	Output is correct
42	Correct	65 ms	78712 KB	Output is correct
43	Correct	77 ms	78716 KB	Output is correct
44	Correct	67 ms	78668 KB	Output is correct
45	Correct	66 ms	78684 KB	Output is correct
46	Correct	68 ms	78712 KB	Output is correct
47	Correct	64 ms	78716 KB	Output is correct
48	Correct	70 ms	78712 KB	Output is correct
49	Correct	122 ms	81500 KB	Output is correct
50	Correct	138 ms	81656 KB	Output is correct
51	Correct	407 ms	90792 KB	Output is correct
52	Correct	422 ms	90708 KB	Output is correct
53	Correct	897 ms	105812 KB	Output is correct
54	Correct	822 ms	106484 KB	Output is correct
55	Correct	904 ms	105624 KB	Output is correct
56	Correct	855 ms	106012 KB	Output is correct
57	Correct	137 ms	82040 KB	Output is correct
58	Correct	319 ms	89064 KB	Output is correct
59	Correct	109 ms	80760 KB	Output is correct
60	Correct	109 ms	81016 KB	Output is correct
61	Incorrect	174 ms	84348 KB	Output isn't correct
62	Halted	0 ms	0 KB	-

Subtask #3
0 / 63.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	78584 KB	Output is correct
2	Correct	62 ms	78712 KB	Output is correct
3	Correct	67 ms	78588 KB	Output is correct
4	Correct	67 ms	78584 KB	Output is correct
5	Correct	70 ms	78632 KB	Output is correct
6	Correct	74 ms	78584 KB	Output is correct
7	Correct	70 ms	78664 KB	Output is correct
8	Correct	71 ms	78788 KB	Output is correct
9	Correct	67 ms	78712 KB	Output is correct
10	Correct	67 ms	78584 KB	Output is correct
11	Correct	64 ms	78740 KB	Output is correct
12	Correct	65 ms	78584 KB	Output is correct
13	Correct	64 ms	78584 KB	Output is correct
14	Correct	67 ms	78588 KB	Output is correct
15	Correct	68 ms	78840 KB	Output is correct
16	Correct	67 ms	78584 KB	Output is correct
17	Correct	65 ms	78584 KB	Output is correct
18	Correct	70 ms	78588 KB	Output is correct
19	Correct	72 ms	78584 KB	Output is correct
20	Correct	69 ms	78712 KB	Output is correct
21	Correct	68 ms	78596 KB	Output is correct
22	Correct	74 ms	78584 KB	Output is correct
23	Correct	68 ms	78712 KB	Output is correct
24	Correct	65 ms	78556 KB	Output is correct
25	Correct	65 ms	78584 KB	Output is correct
26	Correct	63 ms	78584 KB	Output is correct
27	Correct	70 ms	78716 KB	Output is correct
28	Correct	69 ms	78712 KB	Output is correct
29	Correct	70 ms	78612 KB	Output is correct
30	Correct	62 ms	78584 KB	Output is correct
31	Correct	65 ms	78584 KB	Output is correct
32	Correct	74 ms	78712 KB	Output is correct
33	Correct	65 ms	78588 KB	Output is correct
34	Correct	830 ms	110248 KB	Output is correct
35	Correct	75 ms	78712 KB	Output is correct
36	Correct	775 ms	105804 KB	Output is correct
37	Correct	850 ms	105864 KB	Output is correct
38	Correct	891 ms	106420 KB	Output is correct
39	Correct	832 ms	106192 KB	Output is correct
40	Correct	799 ms	105276 KB	Output is correct
41	Correct	67 ms	78712 KB	Output is correct
42	Correct	65 ms	78712 KB	Output is correct
43	Correct	77 ms	78716 KB	Output is correct
44	Correct	67 ms	78668 KB	Output is correct
45	Correct	66 ms	78684 KB	Output is correct
46	Correct	68 ms	78712 KB	Output is correct
47	Correct	64 ms	78716 KB	Output is correct
48	Correct	70 ms	78712 KB	Output is correct
49	Correct	122 ms	81500 KB	Output is correct
50	Correct	138 ms	81656 KB	Output is correct
51	Correct	407 ms	90792 KB	Output is correct
52	Correct	422 ms	90708 KB	Output is correct
53	Correct	897 ms	105812 KB	Output is correct
54	Correct	822 ms	106484 KB	Output is correct
55	Correct	904 ms	105624 KB	Output is correct
56	Correct	855 ms	106012 KB	Output is correct
57	Correct	137 ms	82040 KB	Output is correct
58	Correct	319 ms	89064 KB	Output is correct
59	Correct	109 ms	80760 KB	Output is correct
60	Correct	109 ms	81016 KB	Output is correct
61	Incorrect	174 ms	84348 KB	Output isn't correct
62	Halted	0 ms	0 KB	-

답안 #99068

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 0 / 63.0

Subtask #1
8.0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
0 / 63.0