Submission #108498

#	Time	Username	Problem	Language	Result	Execution time	Memory
108498		E869120	Bulldozer (JOI17_bulldozer)	C++14	75 / 100	1146 ms	49920 KiB

bulldozer

#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;
vector<tuple<Fraction, int, int>>E;
SegmentTree Z;

int main() {
	// 入力部分・偏角ソート
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i] >> W[i]; }
	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());

	// 初期値を計算
	vector<pair<long long, long long>>vec;
	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);
		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]);

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

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

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:81: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:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) {
                  ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20