oj.uz

Submission #888639

# Submission time Handle Problem Language Result Execution time Memory
888639 2023-12-18T04:55:43 Z IBory Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 189564 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -