답안 #32622 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32622	2017-10-12T17:42:28 Z	aome	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	930 ms	64020 KB

bulldozer

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2005;
const int INF = 1e9;
 
struct Point {
	int x, y, w;
} a[N];
 
struct Node {
	long long s, sl, sr, mx;
 
	Node () { s = sl = sr = 0, mx = -INF; }
};
 
struct Go {
	double w;
	int x, y;
 
	Go (double w, int x, int y) :
		w(w), x(x), y(y) {}
};
 
int n, pos[N];
long long res;
Node it[4 * N];
vector<Go> go;
 
Node Merge(Node x, Node y) {
	Node z;
	z.s = x.s + y.s;
	z.sl = max(x.sl, x.s + y.sl);
	z.sr = max(x.sr + y.s, y.sr);
	z.mx = max(max(x.mx, y.mx), x.sr + y.sl);
	return z;
}
 
void build(int i, int l, int r) {
	if (l == r) {
		it[i].s = it[i].sl = it[i].sr = it[i].mx = a[l].w; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}
 
void upd(int i, int l, int r, int p, int v) {
	if (l == r) {
		it[i].s = it[i].sl = it[i].sr = it[i].mx = v; return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid) upd(i << 1, l, mid, p, v);
	else upd(i << 1 | 1, mid + 1, r, p, v);
	it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].x >> a[i].y >> a[i].w;
	}
	sort(a, a + n, [&](Point x, Point y) {
		return make_pair(x.y, x.x) < make_pair(y.y, y.x);
	});
	// for (int i = 0; i < n; ++i) {
	// 	cout << a[i].x << ' ' << a[i].y << ' ' << a[i].w << '\n';
	// }
	for (int i = 0; i < n; ++i) pos[i] = i;
	build(1, 0, n - 1);
	res = max(res, it[1].mx);
	for (int  i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			double tmp = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
			if (tmp == acos(-1)) tmp = 0;
			go.push_back(Go(tmp, i, j));
		}
	}
	sort(go.begin(), go.end(), [&](Go x, Go y) {
		return make_pair(x.w, make_pair(x.x, x.y)) < make_pair(y.w, make_pair(y.x, y.y));
	});
	for (int i = 0; i < go.size(); ++i) {
		vector<Go> _go;
		_go.push_back(go[i]);
		while (i + 1 < go.size() && go[i + 1].w == go[i].w) {
			i++, _go.push_back(go[i]);
		}
		for (auto j : _go) {
			// cout << j.x << ' ' << j.y << '\n';
			swap(pos[j.x], pos[j.y]);
			upd(1, 0, n - 1, pos[j.x], a[j.x].w);
			upd(1, 0, n - 1, pos[j.y], a[j.y].w);
		}
		// for (int j = 0; j < n; ++j) cout << pos[j] << ' '; cout << '\n';
		res = max(res, it[1].mx);
	}
	cout << res << '\n';
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < go.size(); ++i) {
                  ~~^~~~~~~~~~~
bulldozer.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i + 1 < go.size() && go[i + 1].w == go[i].w) {
          ~~~~~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	940 KB	Output is correct
2	Correct	3 ms	896 KB	Output is correct
3	Correct	3 ms	896 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	3 ms	896 KB	Output is correct
6	Correct	3 ms	900 KB	Output is correct
7	Correct	3 ms	896 KB	Output is correct
8	Correct	4 ms	896 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	3 ms	868 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	2 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	640 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	768 KB	Output is correct
2	Correct	3 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	3 ms	768 KB	Output is correct
10	Correct	3 ms	816 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	2 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	2 ms	640 KB	Output is correct
17	Correct	2 ms	640 KB	Output is correct
18	Correct	2 ms	640 KB	Output is correct
19	Correct	2 ms	640 KB	Output is correct
20	Correct	2 ms	640 KB	Output is correct
21	Correct	4 ms	816 KB	Output is correct
22	Correct	3 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	3 ms	768 KB	Output is correct
25	Correct	4 ms	768 KB	Output is correct
26	Correct	4 ms	860 KB	Output is correct
27	Correct	3 ms	768 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	812 KB	Output is correct
30	Correct	3 ms	768 KB	Output is correct
31	Correct	3 ms	808 KB	Output is correct
32	Correct	4 ms	768 KB	Output is correct

Subtask #3
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	768 KB	Output is correct
2	Correct	3 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	3 ms	768 KB	Output is correct
10	Correct	3 ms	816 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	2 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	2 ms	640 KB	Output is correct
17	Correct	2 ms	640 KB	Output is correct
18	Correct	2 ms	640 KB	Output is correct
19	Correct	2 ms	640 KB	Output is correct
20	Correct	2 ms	640 KB	Output is correct
21	Correct	4 ms	816 KB	Output is correct
22	Correct	3 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	3 ms	768 KB	Output is correct
25	Correct	4 ms	768 KB	Output is correct
26	Correct	4 ms	860 KB	Output is correct
27	Correct	3 ms	768 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	812 KB	Output is correct
30	Correct	3 ms	768 KB	Output is correct
31	Correct	3 ms	808 KB	Output is correct
32	Correct	4 ms	768 KB	Output is correct
33	Correct	835 ms	33704 KB	Output is correct
34	Correct	828 ms	33596 KB	Output is correct
35	Correct	862 ms	33600 KB	Output is correct
36	Correct	868 ms	33600 KB	Output is correct
37	Correct	847 ms	33600 KB	Output is correct
38	Correct	865 ms	33524 KB	Output is correct
39	Correct	857 ms	33600 KB	Output is correct
40	Correct	819 ms	33560 KB	Output is correct
41	Correct	841 ms	33584 KB	Output is correct
42	Correct	878 ms	33600 KB	Output is correct
43	Correct	874 ms	33604 KB	Output is correct
44	Correct	840 ms	33580 KB	Output is correct
45	Correct	818 ms	33556 KB	Output is correct
46	Correct	816 ms	33572 KB	Output is correct
47	Correct	860 ms	33640 KB	Output is correct
48	Correct	837 ms	33600 KB	Output is correct
49	Correct	817 ms	33616 KB	Output is correct
50	Correct	810 ms	33576 KB	Output is correct
51	Correct	815 ms	33532 KB	Output is correct
52	Correct	813 ms	33600 KB	Output is correct
53	Correct	839 ms	33608 KB	Output is correct
54	Correct	852 ms	33684 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	768 KB	Output is correct
2	Correct	3 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	3 ms	816 KB	Output is correct
5	Correct	3 ms	768 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	3 ms	768 KB	Output is correct
10	Correct	3 ms	816 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	2 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	512 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	2 ms	640 KB	Output is correct
17	Correct	2 ms	640 KB	Output is correct
18	Correct	2 ms	640 KB	Output is correct
19	Correct	2 ms	640 KB	Output is correct
20	Correct	2 ms	640 KB	Output is correct
21	Correct	4 ms	816 KB	Output is correct
22	Correct	3 ms	768 KB	Output is correct
23	Correct	4 ms	768 KB	Output is correct
24	Correct	3 ms	768 KB	Output is correct
25	Correct	4 ms	768 KB	Output is correct
26	Correct	4 ms	860 KB	Output is correct
27	Correct	3 ms	768 KB	Output is correct
28	Correct	3 ms	768 KB	Output is correct
29	Correct	3 ms	812 KB	Output is correct
30	Correct	3 ms	768 KB	Output is correct
31	Correct	3 ms	808 KB	Output is correct
32	Correct	4 ms	768 KB	Output is correct
33	Correct	835 ms	33704 KB	Output is correct
34	Correct	828 ms	33596 KB	Output is correct
35	Correct	862 ms	33600 KB	Output is correct
36	Correct	868 ms	33600 KB	Output is correct
37	Correct	847 ms	33600 KB	Output is correct
38	Correct	865 ms	33524 KB	Output is correct
39	Correct	857 ms	33600 KB	Output is correct
40	Correct	819 ms	33560 KB	Output is correct
41	Correct	841 ms	33584 KB	Output is correct
42	Correct	878 ms	33600 KB	Output is correct
43	Correct	874 ms	33604 KB	Output is correct
44	Correct	840 ms	33580 KB	Output is correct
45	Correct	818 ms	33556 KB	Output is correct
46	Correct	816 ms	33572 KB	Output is correct
47	Correct	860 ms	33640 KB	Output is correct
48	Correct	837 ms	33600 KB	Output is correct
49	Correct	817 ms	33616 KB	Output is correct
50	Correct	810 ms	33576 KB	Output is correct
51	Correct	815 ms	33532 KB	Output is correct
52	Correct	813 ms	33600 KB	Output is correct
53	Correct	839 ms	33608 KB	Output is correct
54	Correct	852 ms	33684 KB	Output is correct
55	Correct	856 ms	33568 KB	Output is correct
56	Correct	853 ms	33648 KB	Output is correct
57	Correct	857 ms	33576 KB	Output is correct
58	Correct	825 ms	33600 KB	Output is correct
59	Correct	834 ms	33596 KB	Output is correct
60	Correct	834 ms	33668 KB	Output is correct
61	Correct	871 ms	33592 KB	Output is correct
62	Correct	852 ms	33600 KB	Output is correct
63	Correct	833 ms	33600 KB	Output is correct
64	Correct	852 ms	33656 KB	Output is correct
65	Correct	824 ms	33600 KB	Output is correct
66	Correct	838 ms	33600 KB	Output is correct
67	Correct	821 ms	33748 KB	Output is correct
68	Correct	885 ms	33616 KB	Output is correct
69	Correct	850 ms	33572 KB	Output is correct
70	Correct	887 ms	33600 KB	Output is correct
71	Correct	830 ms	33600 KB	Output is correct
72	Correct	836 ms	33604 KB	Output is correct
73	Correct	846 ms	33576 KB	Output is correct
74	Correct	838 ms	33640 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	940 KB	Output is correct
2	Correct	3 ms	896 KB	Output is correct
3	Correct	3 ms	896 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	3 ms	896 KB	Output is correct
6	Correct	3 ms	900 KB	Output is correct
7	Correct	3 ms	896 KB	Output is correct
8	Correct	4 ms	896 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	3 ms	868 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Correct	2 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	640 KB	Output is correct
15	Correct	2 ms	640 KB	Output is correct
16	Correct	3 ms	768 KB	Output is correct
17	Correct	3 ms	768 KB	Output is correct
18	Correct	4 ms	768 KB	Output is correct
19	Correct	3 ms	816 KB	Output is correct
20	Correct	3 ms	768 KB	Output is correct
21	Correct	3 ms	768 KB	Output is correct
22	Correct	3 ms	768 KB	Output is correct
23	Correct	3 ms	768 KB	Output is correct
24	Correct	3 ms	768 KB	Output is correct
25	Correct	3 ms	816 KB	Output is correct
26	Correct	2 ms	640 KB	Output is correct
27	Correct	2 ms	640 KB	Output is correct
28	Correct	2 ms	640 KB	Output is correct
29	Correct	2 ms	512 KB	Output is correct
30	Correct	2 ms	640 KB	Output is correct
31	Correct	2 ms	640 KB	Output is correct
32	Correct	2 ms	640 KB	Output is correct
33	Correct	2 ms	640 KB	Output is correct
34	Correct	2 ms	640 KB	Output is correct
35	Correct	2 ms	640 KB	Output is correct
36	Correct	4 ms	816 KB	Output is correct
37	Correct	3 ms	768 KB	Output is correct
38	Correct	4 ms	768 KB	Output is correct
39	Correct	3 ms	768 KB	Output is correct
40	Correct	4 ms	768 KB	Output is correct
41	Correct	4 ms	860 KB	Output is correct
42	Correct	3 ms	768 KB	Output is correct
43	Correct	3 ms	768 KB	Output is correct
44	Correct	3 ms	812 KB	Output is correct
45	Correct	3 ms	768 KB	Output is correct
46	Correct	3 ms	808 KB	Output is correct
47	Correct	4 ms	768 KB	Output is correct
48	Correct	835 ms	33704 KB	Output is correct
49	Correct	828 ms	33596 KB	Output is correct
50	Correct	862 ms	33600 KB	Output is correct
51	Correct	868 ms	33600 KB	Output is correct
52	Correct	847 ms	33600 KB	Output is correct
53	Correct	865 ms	33524 KB	Output is correct
54	Correct	857 ms	33600 KB	Output is correct
55	Correct	819 ms	33560 KB	Output is correct
56	Correct	841 ms	33584 KB	Output is correct
57	Correct	878 ms	33600 KB	Output is correct
58	Correct	874 ms	33604 KB	Output is correct
59	Correct	840 ms	33580 KB	Output is correct
60	Correct	818 ms	33556 KB	Output is correct
61	Correct	816 ms	33572 KB	Output is correct
62	Correct	860 ms	33640 KB	Output is correct
63	Correct	837 ms	33600 KB	Output is correct
64	Correct	817 ms	33616 KB	Output is correct
65	Correct	810 ms	33576 KB	Output is correct
66	Correct	815 ms	33532 KB	Output is correct
67	Correct	813 ms	33600 KB	Output is correct
68	Correct	839 ms	33608 KB	Output is correct
69	Correct	852 ms	33684 KB	Output is correct
70	Correct	856 ms	33568 KB	Output is correct
71	Correct	853 ms	33648 KB	Output is correct
72	Correct	857 ms	33576 KB	Output is correct
73	Correct	825 ms	33600 KB	Output is correct
74	Correct	834 ms	33596 KB	Output is correct
75	Correct	834 ms	33668 KB	Output is correct
76	Correct	871 ms	33592 KB	Output is correct
77	Correct	852 ms	33600 KB	Output is correct
78	Correct	833 ms	33600 KB	Output is correct
79	Correct	852 ms	33656 KB	Output is correct
80	Correct	824 ms	33600 KB	Output is correct
81	Correct	838 ms	33600 KB	Output is correct
82	Correct	821 ms	33748 KB	Output is correct
83	Correct	885 ms	33616 KB	Output is correct
84	Correct	850 ms	33572 KB	Output is correct
85	Correct	887 ms	33600 KB	Output is correct
86	Correct	830 ms	33600 KB	Output is correct
87	Correct	836 ms	33604 KB	Output is correct
88	Correct	846 ms	33576 KB	Output is correct
89	Correct	838 ms	33640 KB	Output is correct
90	Correct	893 ms	33652 KB	Output is correct
91	Correct	815 ms	33600 KB	Output is correct
92	Correct	823 ms	33544 KB	Output is correct
93	Correct	872 ms	33572 KB	Output is correct
94	Correct	919 ms	33536 KB	Output is correct
95	Correct	863 ms	33728 KB	Output is correct
96	Correct	829 ms	33644 KB	Output is correct
97	Correct	860 ms	33604 KB	Output is correct
98	Correct	889 ms	33600 KB	Output is correct
99	Correct	922 ms	33580 KB	Output is correct
100	Correct	747 ms	63980 KB	Output is correct
101	Correct	766 ms	64020 KB	Output is correct
102	Correct	774 ms	63980 KB	Output is correct
103	Correct	747 ms	63972 KB	Output is correct
104	Correct	772 ms	63980 KB	Output is correct
105	Correct	785 ms	58908 KB	Output is correct
106	Correct	826 ms	58800 KB	Output is correct
107	Correct	777 ms	58732 KB	Output is correct
108	Correct	756 ms	58728 KB	Output is correct
109	Correct	766 ms	58856 KB	Output is correct
110	Correct	753 ms	33600 KB	Output is correct
111	Correct	735 ms	33600 KB	Output is correct
112	Correct	754 ms	33600 KB	Output is correct
113	Correct	797 ms	33600 KB	Output is correct
114	Correct	754 ms	33604 KB	Output is correct
115	Correct	758 ms	33600 KB	Output is correct
116	Correct	742 ms	33600 KB	Output is correct
117	Correct	743 ms	33600 KB	Output is correct
118	Correct	751 ms	33604 KB	Output is correct
119	Correct	741 ms	33632 KB	Output is correct
120	Correct	4 ms	640 KB	Output is correct
121	Correct	2 ms	640 KB	Output is correct
122	Correct	930 ms	33568 KB	Output is correct
123	Correct	860 ms	33572 KB	Output is correct
124	Incorrect	915 ms	33600 KB	Output isn't correct
125	Halted	0 ms	0 KB	-

답안 #32622

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 35.0 / 35.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
35.0 / 35.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 20.0