Submission #593913

#	Time	Username	Problem	Language	Result	Execution time	Memory
593913		GusterGoose27	Bulldozer (JOI17_bulldozer)	C++11	5 / 100	4 ms	656 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ld, int> pdi;

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

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];
pdi updates[MAXN*(MAXN-1)];
int t = 0;
int n;

ld get_ang(int i, int j) { // actually the slope but who cares
	return ((ld)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;
	ld ang = get_ang(i, j);
	updates[t++] = pdi(ang, i);
	updates[t++] = pdi(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(ld ang, int i, int j) {
	ld yval = ang*(points[j].x-points[i].x)+points[i].y;
	return (abs(yval-points[j].y) < ERROR);
}

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;) {
		ld ang = updates[i].first;
		int orig = i;
		set<int, comp> cur_vals;
		while (i < t && abs(updates[i].first-ang) < ERROR) {
			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";
}

Compilation message (stderr)

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

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