Submission #108544

#TimeUsernameProblemLanguageResultExecution timeMemory
108544E869120Bulldozer (JOI17_bulldozer)C++14
100 / 100
1126 ms50104 KiB
#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
#include <algorithm>
using namespace std;

class SegmentTree {
public:
	vector<long long>dat1, dat2, dat3; int size_ = 1;

	void init(int sz) {
		while (size_ <= sz) size_ *= 2;
		dat1.resize(size_ * 2, 0);
		dat2.resize(size_ * 2, 0);
		dat3.resize(size_ * 2, 0);
	}

	void update(int pos, long long x) {
		pos += size_;
		dat1[pos] = x; dat2[pos] = x;
		while (pos >= 2) {
			pos >>= 1;
			dat1[pos] = min(dat1[pos * 2], dat1[pos * 2 + 1]);
			dat2[pos] = max(dat2[pos * 2], dat2[pos * 2 + 1]);
			dat3[pos] = max({ dat3[pos * 2], dat3[pos * 2 + 1], dat2[pos * 2 + 1] - dat1[pos * 2] });
		}
	}

	long long get_val() {
		return dat3[1];
	}
};

struct Fraction {
public:
	long long cx, cy;
};

bool operator<(const Fraction &a1, const Fraction &a2) {
	// a1 < a2
	if (a1.cx * a2.cy > a1.cy * a2.cx) return true;
	return false;
}

bool operator==(const Fraction &a1, const Fraction &a2) {
	// a1 == a2
	if (a1.cx * a2.cy == a1.cy * a2.cx) return true;
	return false;
}

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

Fraction teisei(Fraction A) {
	if (A.cx < 0) { A.cx *= -1; A.cy *= -1; }
	long long E = gcd(A.cx, A.cy); E = abs(E);
	A.cx /= E; A.cy /= E;
	return A;
}

long long N, X[2009], Y[2009], W[2009], order[2009], ichi[2009], ruiseki[2009], ans; bool ok = false;
vector<tuple<Fraction, int, int>>E;
SegmentTree Z;

long long solve_1() {
	long long res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (X[i] > X[j]) continue;
			long long sm = 0; for (int k = 0; k < N; k++) { if (X[i] <= X[k] && X[k] <= X[j]) sm += W[k]; }
			res = max(res, sm);
		}
	}
	return res;
}

int main() {
	// 入力部分・偏角ソート
	vector<tuple<long long, long long, long long>> vec1;
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i] >> W[i]; vec1.push_back(make_tuple(X[i], Y[i], W[i])); if (Y[i] != 0) ok = true; }
	sort(vec1.begin(), vec1.end());
	for (int i = 0; i < N; i++) { X[i] = get<0>(vec1[i]); Y[i] = get<1>(vec1[i]); W[i] = get<2>(vec1[i]); }

	ok = true;
	if (ok == false) {
		cout << solve_1() << endl;
		return 0;
	}

	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) E.push_back(make_tuple(teisei(Fraction{ X[j] - X[i],Y[j] - Y[i] }), i, j));
	}
	sort(E.begin(), E.end());

	// 初期値を計算 ① ~ Y 座標編 ~
	vector<pair<long long, long long>>vec;
	for (int i = 0; i < N; i++) vec.push_back(make_pair(Y[i], i));
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++) { ichi[vec[i].second] = i; order[i] = vec[i].second; }

	Z.init(N + 2);
	for (int i = 0; i < N; i++) ruiseki[i + 1] = ruiseki[i] + W[order[i]];
	for (int i = 0; i <= N; i++) Z.update(i, ruiseki[i]);
	for (int i = N + 1; i < Z.size_; i++) Z.update(i, -(1LL << 60));

	ans = max(ans, Z.get_val());

	// 初期値を計算 ② ~ X 座標編 ~
	vec.clear();
	for (int i = 0; i < N; i++) vec.push_back(make_pair(X[i], i));
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); i++) { ichi[vec[i].second] = i; order[i] = vec[i].second; }
	
	Z.init(N + 2);
	for (int i = 0; i < N; i++) ruiseki[i + 1] = ruiseki[i] + W[order[i]];
	for (int i = 0; i <= N; i++) Z.update(i, ruiseki[i]);
	for (int i = N + 1; i < Z.size_; i++) Z.update(i, -(1LL << 60));

	// 値を更新
	ans = max(ans, Z.get_val());
	for (int i = 0; i < E.size(); i++) {
		int u1 = ichi[get<1>(E[i])], u2 = ichi[get<2>(E[i])]; if (u1 > u2) swap(u1, u2);
		if (X[order[u1]] < X[order[u2]]) {
			swap(order[u1], order[u2]);
			swap(ichi[get<1>(E[i])], ichi[get<2>(E[i])]);
			ruiseki[u1 + 1] = ruiseki[u1] + W[order[u1]];
			Z.update(u1 + 1, ruiseki[u1 + 1]);
		}

		if (i == E.size() - 1 || !(get<0>(E[i]) == get<0>(E[i + 1]))) ans = max(ans, Z.get_val());
	}

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) { ichi[vec[i].second] = i; order[i] = vec[i].second; }
                  ~~^~~~~~~~~~~~
bulldozer.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) { ichi[vec[i].second] = i; order[i] = vec[i].second; }
                  ~~^~~~~~~~~~~~
bulldozer.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) {
                  ~~^~~~~~~~~~
bulldozer.cpp:134:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == E.size() - 1 || !(get<0>(E[i]) == get<0>(E[i + 1]))) ans = max(ans, Z.get_val());
       ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...