Submission #122124

#	Time	Username	Problem	Language	Result	Execution time	Memory
122124		mosesmayer	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1333 ms	32452 KiB

bulldozer

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define DEBUG
#define fi first
#define se second
#define pb push_back
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;
//template<typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
//		tree_order_statistics_node_update>; // find_by_order, order_of_key

template<class F, class S>
ostream& operator<< (ostream& os, const pair<F, S> p){
	os << '{' << p.fi << ", " << p.se << '}';
	return os;
}
template<class T>
ostream& operator<< (ostream& os, const vector<T>& v){
	os << '{';
	for (int i = 0, t = v.size(); i < t; i++) os << v[i] << (i+1==t?", " : "}");
	return os;
}
const int INF = 0x3f3f3f3f;
const LL LINF = 1e18;
//////////////////END OF TEMPLATE//////////////////////////////

void read();
struct pt{
	int x, y, v;
	pt(int x = 0, int y = 0, int v = 0): x(x), y(y), v(v) {}
	bool operator== (const pt &rhs) const{ return x == rhs.x && y == rhs.y;}
	bool operator< (const pt &rhs) const{ return x == rhs.x ? y < rhs.y : x < rhs.x; }
	pt operator+ (const pt &rhs){
		return pt(x + rhs.x, y + rhs.y, 0);
	}
	pt operator- (const pt &rhs){
		return pt(x + rhs.x, y + rhs.y, 0);
	}
	LL operator* (const pt &rhs){
		return x * rhs.y - y * rhs.x;
	}
};

struct Node{
	LL a, p, s, b;
	Node(LL v = 0): b(v), a(v), p(v), s(v) {}
};
inline Node merge(Node l, Node r){
	Node x;
	x.a = l.a + r.a;
	x.p = max(l.p, l.a + r.p);
	x.s = max(l.s + r.a, r.s);
	x.b = max(l.b, r.b);
	x.b = max(x.b, l.s + r.p);
	return x;
}


int n;
pt pts[2005];
Node st[2005 << 2];
void build(int p = 1, int l = 1, int r = n){
	if (l ==r){
		st[p] = Node(pts[l].v);
		//cout << l << ' ' << st[p].v << ' ' << st[p].b << '\n';
		return;
	}
	int md = (l + r) >> 1;
	build(p<<1, l, md);
	build(p<<1|1, md+1, r);
	st[p] = merge(st[p<<1], st[p<<1|1]);
}

void upd(int i, int v, int p = 1, int l = 1, int r = n){
	if (l == r) return void(st[p] = Node(v));
	int md = (l + r) >> 1;
	if (i <= md) upd(i, v, p<<1, l, md);
	else upd(i, v, p<<1|1, md+1, r);
	st[p] = merge(st[p<<1], st[p<<1|1]);
}

Node query(int i, int j, int p = 1, int l = 1, int r = n){
	if (j < l || i > r){
		Node ret(-LINF); ret.a = 0;
		return ret;
	}
	if (i <= l && j >= r) return st[p];
	int md = (l + r) >> 1;
	return merge(query(i, j, p<<1, l, md), query(i, j, p<<1|1, md+1, r));
}

void printTree(int p = 1, int l = 1, int r = n){
	cout << "pos " << p << " rng " << make_pair(l, r) << " : " ;
	cout << st[p].a << ' ' << st[p].b << ' ' << st[p].p << ' ' << st[p].s << '\n';
	if (l == r) return;
	int md = (l + r) >> 1;
	printTree(p<<1, l, md);
	printTree(p<<1|1, md+1, r);
}

LL get(){
	return st[1].b;
}
int pos[2005], rpos[2005];
vector<pii> vec;
bool eqv(pii a, pii b){
	LL dxa = pts[a.se].x - pts[a.fi].x;
	LL dya = pts[a.se].y - pts[a.fi].y;
	LL dxb = pts[b.se].x - pts[b.fi].x;
	LL dyb = pts[b.se].y - pts[b.fi].y;
	if (dxa < 0) dxa = -dxa, dya = -dya;
	if (dxb < 0) dxb = -dxb, dyb = -dyb;
	return dya * dxb == dyb * dxa;
}
bool cmp(pii a, pii b){
	if (eqv(a, b)){
		if (pts[a.fi] < pts[a.se]) swap(a.fi, a.se);
		if (pts[b.fi] < pts[b.se]) swap(b.fi, b.se);
		return pts[a.fi] == pts[a.se] ? pts[b.fi] < pts[b.se] : pts[a.fi] < pts[a.se];
	}
	LL dxa = pts[a.se].x - pts[a.fi].x;
	LL dya = pts[a.se].y - pts[a.fi].y;
	LL dxb = pts[b.se].x - pts[b.fi].x;
	LL dyb = pts[b.se].y - pts[b.fi].y;
	if (dxa < 0) dxa = -dxa, dya = -dya;
	if (dxb < 0) dxb = -dxb, dyb = -dyb;
	return dya * dxb < dyb * dxa;
}
bool cmp2(pii a, pii b){
	if (a.fi > a.se) swap(a.fi, a.se);
	if (b.fi > b.se) swap(b.fi, b.se);
	return a < b;
}
vector<pii> curr;
#undef DEBUG
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	read();
	build();
	for (int i = 1; i <= n; i++){
		pos[i] = rpos[i] = i;
		for (int j = i+1; j <= n; j++){
			vec.push_back(make_pair(i, j));
		}
	}
	LL mx = 0LL;
	mx = max(mx, get());
	sort(vec.begin(), vec.end(), cmp);
	for (pii v : vec){
		if (curr.empty() || eqv(curr.back(), v)){
			curr.push_back(v);
		} else {
			sort(curr.begin(), curr.end());
			for (pii ii : curr){
				swap(pos[ii.fi], pos[ii.se]);
				upd(pos[ii.fi], pts[ii.fi].v);
				upd(pos[ii.se], pts[ii.se].v);
			}
			mx = max(mx, get());
			curr.clear();
			curr.push_back(v);
		}
	}
	cout << mx << '\n';
	return 0;
}

inline void read(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> pts[i].x >> pts[i].y >> pts[i].v;
	sort(pts+1, pts+n+1);
}

Compilation message (stderr)

bulldozer.cpp: In constructor 'Node::Node(LL)':
bulldozer.cpp:50:14: warning: 'Node::b' will be initialized after [-Wreorder]
  LL a, p, s, b;
              ^
bulldozer.cpp:50:5: warning:   'LL Node::a' [-Wreorder]
  LL a, p, s, b;
     ^
bulldozer.cpp:51:2: warning:   when initialized here [-Wreorder]
  Node(LL v = 0): b(v), a(v), p(v), s(v) {}
  ^~~~

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