제출 #593987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593987		GusterGoose27	Bulldozer (JOI17_bulldozer)	C++11	100 / 100	1435 ms	94672 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

class Point {
public:
	int x;
	int y;
	int v;
	Point() {}
	Point(int xn, int yn, int vn) {
		x = xn;
		y = yn;
		v = vn;
	}
};

class Frac {
public:
	ll num;
	ll denom;
	Frac() {}
	Frac(ll n, ll d) {
		num = n;
		denom = d;
		reduce();
	}
	ll gcd(ll a, ll b) {
		if (a > b) return gcd(b, a);
		if (a == 0) return b;
		return gcd(b%a, a);
	}
	void reduce() {
		if (denom < 0) {
			num *= -1;
			denom *= -1;
		}
		ll g = gcd(abs(num), abs(denom));
		num /= g;
		denom /= g;
	}
	Frac mult(ll other) {
		Frac f(num, denom);
		f.num *= other;
		f.reduce();
		return f;
	}
	bool equals(ll other) {
		return (denom == 1) && (num == other);
	}
};

bool operator<(const Frac &a, const Frac &b) {
	return (a.num*b.denom < b.num*a.denom);
}

bool operator==(const Frac &a, const Frac &b) {
	return (a.num == b.num) && (a.denom == b.denom);
}

typedef pair<Frac, int> pfi;

bool operator<(const Point &a, const Point &b) {
	return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
}

const int MAXN = 2000;
const ld ERROR = 2e-10;
Point points[MAXN];
int curpos[MAXN];
pfi updates[MAXN*(MAXN-1)];
int t = 0;
int n;

Frac get_ang(int i, int j) { // actually the slope but who cares
	return Frac(points[j].y-points[i].y, points[j].x-points[i].x);
}

class STree {
public:
	int n;
	ll *sum;
	ll *max_pre;
	ll *max_suf;
	ll *max_cont;
	STree(int nn) {
		n = pow(2, ceil(log2(nn)));
		sum = new ll[2*n];
		max_pre = new ll[2*n];
		max_suf = new ll[2*n];
		max_cont = new ll[2*n];
		for (int i = 0; i < n; i++) {
			if (i < nn) {
				sum[i+n] = points[i].v;
				max_pre[i+n] = max(0, points[i].v);
				max_suf[i+n] = max(0, points[i].v);
				max_cont[i+n] = max(0, points[i].v);
			}
			else {
				sum[i+n] = 0;
				max_pre[i+n] = 0;
				max_suf[i+n] = 0;
				max_cont[i+n] = 0;
			}
		}
		for (int i = n-1; i >= 0; i--) reset(i);
	}
	void reset(int i) {
		assert(i < n);
		sum[i] = sum[2*i]+sum[2*i+1];
		max_pre[i] = max(max_pre[2*i], sum[2*i]+max_pre[2*i+1]);
		max_suf[i] = max(max_suf[2*i+1], max_suf[2*i]+sum[2*i+1]);
		max_cont[i] = max(max(max_cont[2*i], max_cont[2*i+1]), max_suf[2*i]+max_pre[2*i+1]);
	}
	void update(int i) {
		sum[i+n] = points[i].v;
		max_pre[i+n] = max(0, points[i].v);
		max_suf[i+n] = max(0, points[i].v);
		max_cont[i+n] = max(0, points[i].v);
		i += n;
		while (i > 1) {
			i /= 2;
			reset(i);
		}
	}
	ll max_sum() {
		return max_cont[1];
	}
};

void make_upd(int i, int j) {
	if (points[i].x == points[j].x) return;
	Frac ang = get_ang(i, j);
	updates[t++] = pfi(ang, i);
	updates[t++] = pfi(ang, j);
}

void swap(int a, int b, STree &s) {
	int i = curpos[a];
	int j = curpos[b];
	Point temp = points[i];
	points[i] = points[j];
	points[j] = temp;
	s.update(i);
	s.update(j);
	curpos[a] = j;
	curpos[b] = i;
}

void swap(vector<int> &v, STree &s) {
	for (int j = 0; j < v.size()/2; j++) {
		swap(v[j], v[v.size()-1-j], s);
	}
}

bool on_line(Frac ang, int i, int j) {
	Frac f = ang.mult(points[j].x-points[i].x);
	return f.equals(points[j].y-points[i].y);
}

struct comp {
	bool operator()(const int &a, const int &b) {
		return (curpos[a] < curpos[b]);
	}
};

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		points[i] = Point(x, y, w);
	}
	sort(points, points+n);
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			make_upd(i, j);
		}
	}
	iota(curpos, curpos+n, 0);
	STree s(n);
	ll best = s.max_sum();
	sort(updates, updates+t);
	for (int i = 0; i < t;) {
		Frac ang = updates[i].first;
		int orig = i;
		set<int, comp> cur_vals;
		while (i < t && updates[i].first == ang) {
			cur_vals.insert(updates[i].second);
			i++;
		}
		vector<int> cur_line;
		for (int v: cur_vals) {
			if (cur_line.empty() || on_line(ang, curpos[cur_line.back()], curpos[v])) cur_line.push_back(v);
			else {
				swap(cur_line, s);
				cur_line.clear();
				cur_line.push_back(v);
			}
		}
		assert(cur_line.size());
		swap(cur_line, s);
		best = max(best, s.max_sum());
	}
	cout << best << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'void swap(std::vector<int>&, STree&)':
bulldozer.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int j = 0; j < v.size()/2; j++) {
      |                  ~~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:190:7: warning: unused variable 'orig' [-Wunused-variable]
  190 |   int orig = i;
      |       ^~~~

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