Submission #100901

#	Time	Username	Problem	Language	Result	Execution time	Memory
100901		cki86201	Bulldozer (JOI17_bulldozer)	C++11	100 / 100	1046 ms	17016 KiB

bulldozer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

pii operator-(pii a, pii b) { return pii(a.Fi - b.Fi, a.Se - b.Se); }
ll operator/(pii a, pii b) { return (ll)a.Fi * b.Se - (ll)a.Se * b.Fi; }

pii P[2020];
ll C[2020];
int N;
struct node {
	node(){}
	node(ll x) {
		sum = x;
		lv = rv = val = max(0LL, x);
	}
	ll lv, rv, sum, val;
};
node operator+(const node &a, const node &b) {
	node res;
	res.sum = a.sum + b.sum;
	res.lv = max(a.lv, a.sum + b.lv);
	res.rv = max(b.rv, b.sum + a.rv);
	res.val = max({a.val, b.val, a.rv + b.lv});
	return res;
}
node T[1<<12]; const int ADD = 1<<11;

void update(int l, ll x) {
	l += ADD; T[l] = node(x); l >>= 1;
	while(l) T[l] = T[l<<1] + T[l<<1|1], l >>= 1;
}

ll read() { return T[1].val; }

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c);
		P[i] = pii(x, y);
		C[i] = c;
	}
	vector <pii> O;
	for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) {
		if(P[i] < P[j]) O.pb(pii(i, j));
		else O.pb(pii(j, i));
	}
	sort(all(O), [](pii a, pii b) {
		pii p1 = P[a.Se] - P[a.Fi];
		pii p2 = P[b.Se] - P[b.Fi];
		ll v = p1 / p2;
		if(v != 0) return v > 0;
		pii q1 = min(P[a.Fi], P[a.Se]);
		pii q2 = min(P[b.Fi], P[b.Se]);
		if(q1 != q2) return q1 < q2;
		q1 = max(P[a.Fi], P[a.Se]);
		q2 = max(P[b.Fi], P[b.Se]);
		return q1 < q2;
	});
	int ord[2020], ro[2020];
	for(int i=1;i<=N;i++) ord[i] = i;
	sort(ord+1, ord+1+N, [](int a, int b) {
		return P[a] < P[b];
	});
	for(int i=1;i<=N;i++) ro[ord[i]] = i;
	for(int i=1;i<=N;i++) update(i, C[ord[i]]);
	ll ans = read();
	rep(i, szz(O)) {
		pii e = O[i];
		int x = ro[e.Fi], y = ro[e.Se];
		swap(ord[x], ord[y]);
		swap(ro[e.Fi], ro[e.Se]);
		update(ro[e.Fi], C[e.Fi]);
		update(ro[e.Se], C[e.Se]);
		int ok = 0;
		if(i == szz(O)-1) ok = 1;
		else {
			pii f = O[i+1];
			pii p1 = P[e.Se] - P[e.Fi];
			pii p2 = P[f.Se] - P[f.Fi];
			if(p1 / p2 != 0) ok = 1;
		}
		if(ok) ans = max(ans, read());
	}
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:66:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, c; scanf("%d%d%d", &x, &y, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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