답안 #888639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888639	2023-12-18T04:55:43 Z	IBory	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2000 ms	189564 KB

bulldozer

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int SZ = 1 << 11;
int PN[SZ], IP[SZ];

struct Point {
	ll x, y, s;
	Point(ll x = 0, ll y = 0, ll s = 0) : x(x), y(y), s(s) {};
} P[SZ];

struct Seg {
	struct Data {
		ll LS, RS, T, S;
		Data(ll LS = 0, ll RS = 0, ll T = 0, ll S = 0) : LS(LS), RS(RS), T(T), S(S) {};
		Data operator+(const Data& a) {
			Data ret;
			ret.LS = max(LS, T + a.LS);
			ret.RS = max(a.RS, RS + a.T);
			ret.S = max({S, a.S, RS + a.LS});
			ret.T = T + a.T;
			return ret;
		}
	} T[SZ << 1];

	void Update(int i, int v) {
		T[i += SZ - 1] = Data(max(0, v), max(0, v), v, max(0, v));
		while (i >>= 1) T[i] = T[i * 2] + T[i * 2 + 1];
	}

	ll Query() { return T[1].S; }
} T;

struct Comp {
	bool operator()(const pii& a, const pii& b) const {
		return a.second * b.first > a.first * b.second;
	}
};

void Swap(int a, int b) {
	ll sa = P[a].s, sb = P[b].s;
	swap(IP[PN[a]], IP[PN[b]]);
	swap(PN[a], PN[b]);
	swap(P[a], P[b]);
	T.Update(a, sb);
	T.Update(b, sa);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> P[i].x >> P[i].y >> P[i].s;
		PN[i] = IP[i] = i;
	}
	
	sort(P + 1, P + N + 1, [&](Point a, Point b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});
	for (int i = 1; i <= N; ++i) T.Update(i, P[i].s);
	ll ans = T.Query();

	map<pii, vector<pii>, Comp> ord;
	for (int a = 1; a <= N; ++a) for (int b = a + 1; b <= N; ++b) {
		ll xd = P[b].x - P[a].x, yd = P[b].y - P[a].y;
		if (xd < 0) xd *= -1, yd *= -1;
		ll g = gcd(abs(xd), abs(yd)); xd /= g; yd /= g;
		if (xd == 0) yd = 1LL << 31;
		ord[pii{xd, yd}].emplace_back(a, b);
	}

	for (auto& [_, V] : ord) {
		for (auto [a, b] : V) Swap(IP[a], IP[b]);
		ans = max(ans, T.Query());
	}

	cout << ans;
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	1036 KB	Output is correct
3	Correct	2 ms	852 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	784 KB	Output is correct
7	Correct	2 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	756 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1112 KB	Output is correct
2	Correct	3 ms	1112 KB	Output is correct
3	Correct	3 ms	1116 KB	Output is correct
4	Correct	4 ms	1116 KB	Output is correct
5	Correct	3 ms	1148 KB	Output is correct
6	Correct	3 ms	1116 KB	Output is correct
7	Correct	3 ms	1116 KB	Output is correct
8	Correct	3 ms	1116 KB	Output is correct
9	Correct	3 ms	1148 KB	Output is correct
10	Correct	3 ms	1116 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	3 ms	1184 KB	Output is correct
22	Correct	2 ms	1116 KB	Output is correct
23	Correct	3 ms	1112 KB	Output is correct
24	Correct	3 ms	1112 KB	Output is correct
25	Correct	2 ms	1116 KB	Output is correct
26	Correct	2 ms	1116 KB	Output is correct
27	Correct	3 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Correct	3 ms	1116 KB	Output is correct
30	Correct	3 ms	1036 KB	Output is correct
31	Correct	3 ms	1116 KB	Output is correct
32	Correct	2 ms	1008 KB	Output is correct

Subtask #3
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1112 KB	Output is correct
2	Correct	3 ms	1112 KB	Output is correct
3	Correct	3 ms	1116 KB	Output is correct
4	Correct	4 ms	1116 KB	Output is correct
5	Correct	3 ms	1148 KB	Output is correct
6	Correct	3 ms	1116 KB	Output is correct
7	Correct	3 ms	1116 KB	Output is correct
8	Correct	3 ms	1116 KB	Output is correct
9	Correct	3 ms	1148 KB	Output is correct
10	Correct	3 ms	1116 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	3 ms	1184 KB	Output is correct
22	Correct	2 ms	1116 KB	Output is correct
23	Correct	3 ms	1112 KB	Output is correct
24	Correct	3 ms	1112 KB	Output is correct
25	Correct	2 ms	1116 KB	Output is correct
26	Correct	2 ms	1116 KB	Output is correct
27	Correct	3 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Correct	3 ms	1116 KB	Output is correct
30	Correct	3 ms	1036 KB	Output is correct
31	Correct	3 ms	1116 KB	Output is correct
32	Correct	2 ms	1008 KB	Output is correct
33	Execution timed out	2024 ms	189564 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1112 KB	Output is correct
2	Correct	3 ms	1112 KB	Output is correct
3	Correct	3 ms	1116 KB	Output is correct
4	Correct	4 ms	1116 KB	Output is correct
5	Correct	3 ms	1148 KB	Output is correct
6	Correct	3 ms	1116 KB	Output is correct
7	Correct	3 ms	1116 KB	Output is correct
8	Correct	3 ms	1116 KB	Output is correct
9	Correct	3 ms	1148 KB	Output is correct
10	Correct	3 ms	1116 KB	Output is correct
11	Correct	0 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	0 ms	604 KB	Output is correct
16	Correct	1 ms	604 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	0 ms	604 KB	Output is correct
19	Correct	0 ms	604 KB	Output is correct
20	Correct	1 ms	600 KB	Output is correct
21	Correct	3 ms	1184 KB	Output is correct
22	Correct	2 ms	1116 KB	Output is correct
23	Correct	3 ms	1112 KB	Output is correct
24	Correct	3 ms	1112 KB	Output is correct
25	Correct	2 ms	1116 KB	Output is correct
26	Correct	2 ms	1116 KB	Output is correct
27	Correct	3 ms	1116 KB	Output is correct
28	Correct	2 ms	1116 KB	Output is correct
29	Correct	3 ms	1116 KB	Output is correct
30	Correct	3 ms	1036 KB	Output is correct
31	Correct	3 ms	1116 KB	Output is correct
32	Correct	2 ms	1008 KB	Output is correct
33	Execution timed out	2024 ms	189564 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	1 ms	1036 KB	Output is correct
3	Correct	2 ms	852 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	784 KB	Output is correct
7	Correct	2 ms	604 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	2 ms	604 KB	Output is correct
11	Correct	1 ms	756 KB	Output is correct
12	Correct	0 ms	604 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Correct	0 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	3 ms	1112 KB	Output is correct
17	Correct	3 ms	1112 KB	Output is correct
18	Correct	3 ms	1116 KB	Output is correct
19	Correct	4 ms	1116 KB	Output is correct
20	Correct	3 ms	1148 KB	Output is correct
21	Correct	3 ms	1116 KB	Output is correct
22	Correct	3 ms	1116 KB	Output is correct
23	Correct	3 ms	1116 KB	Output is correct
24	Correct	3 ms	1148 KB	Output is correct
25	Correct	3 ms	1116 KB	Output is correct
26	Correct	0 ms	604 KB	Output is correct
27	Correct	1 ms	604 KB	Output is correct
28	Correct	0 ms	604 KB	Output is correct
29	Correct	1 ms	604 KB	Output is correct
30	Correct	0 ms	604 KB	Output is correct
31	Correct	1 ms	604 KB	Output is correct
32	Correct	1 ms	604 KB	Output is correct
33	Correct	0 ms	604 KB	Output is correct
34	Correct	0 ms	604 KB	Output is correct
35	Correct	1 ms	600 KB	Output is correct
36	Correct	3 ms	1184 KB	Output is correct
37	Correct	2 ms	1116 KB	Output is correct
38	Correct	3 ms	1112 KB	Output is correct
39	Correct	3 ms	1112 KB	Output is correct
40	Correct	2 ms	1116 KB	Output is correct
41	Correct	2 ms	1116 KB	Output is correct
42	Correct	3 ms	1116 KB	Output is correct
43	Correct	2 ms	1116 KB	Output is correct
44	Correct	3 ms	1116 KB	Output is correct
45	Correct	3 ms	1036 KB	Output is correct
46	Correct	3 ms	1116 KB	Output is correct
47	Correct	2 ms	1008 KB	Output is correct
48	Execution timed out	2024 ms	189564 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-

답안 #888639

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0