oj.uz

Submission #888654

# Submission time Handle Problem Language Result Execution time Memory
888654 2023-12-18T05:04:22 Z IBory Bulldozer (JOI17_bulldozer) C++17
0 / 100
 3 ms 1112 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;

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

	vector<pair<pii, pii>> 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;
		pii p = {xd, yd};
		ord.emplace_back(p, pii{a, b});
	}
	sort(ord.begin(), ord.end(), [&](pair<pii, pii>& pa, pair<pii, pii>& pb) {
		auto& [a, _1] = pa;
		auto& [b, _2] = pb;
		return a.second * b.first > a.first * b.second;
	});

	ll ans = 0;
	pii p = {-1, -1};
	for (auto& [g, _] : ord) {
		auto [a, b] = _;
		if (p != g) ans = max(ans, T.Query());
		Swap(IP[a], IP[b]);
		p = g;
	}
	// ans = max(ans, T.Query());

	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 640 KB Output is correct
12 Incorrect 0 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 0 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 0 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 2 ms 1112 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Incorrect 0 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 640 KB Output is correct
12 Incorrect 0 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -