Submission #26604

#	Time	Username	Problem	Language	Result	Execution time	Memory
26604		kriii	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1477 ms	188492 KiB

bulldozer

#include <stdio.h>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b)
{
	return b ? gcd(b, a%b) : a;
}

int N; long long A, B;

struct point{
	int x, y, c, i;
	bool operator <(const point &t) const{
		if (y != t.y) return y < t.y;
		return x < t.x;
	}
}P[2000];
int R[2000];

struct turn{
	turn(){
		dx = dy = 0;
	}
	turn(point a, point b){
		dx = b.x - a.x;
		dy = b.y - a.y;
		long long g = gcd(abs(dx), abs(dy));
		dx /= g;
		dy /= g;
		s = dx * a.x + dy * a.y;
		e = dx * b.x + dy * b.y;
		i = a.i;
		j = b.i;
		tp = type();
	}
	long long dx, dy, s, e;
	int i, j, tp;

	int type() const{
		if (dy > 0 || (dx > 0 && dy == 0)) return 0;
		return 1;
	}
	bool operator <(const turn &t) const{
		if (tp != t.tp) return tp < t.tp;
		if (dy * t.dx != t.dy * dx) return dy * t.dx < t.dy * dx;
		if (e != t.e) return e > t.e;
		return s > t.s;
	};
}T[4000000];

const int Z = 1<<11;

struct node{
	node()
	{
		l = r = s = m = 0;
	}
	node(long long x)
	{
		if (x > 0) l = r = s = m = x;
		else{
			l = r = m = 0;
			s = x;
		}
	}

	long long l,r,s,m;
	
	node operator + (const node &t) const{
		node res;
		res.l = max(l,s+t.l);
		res.r = max(r+t.s,t.r);
		res.s = s + t.s;
		res.m = max({m,t.m,r+t.l});
		return res;
	}
}IT[Z*2];

void up(int x, long long v)
{
	x += Z; IT[x] = node(v); x /= 2;
	while (x){
		IT[x] = IT[x*2] + IT[x*2+1];
		x /= 2;
	}
}

int main()
{
	scanf("%d", &N);

	for (int i=0;i<N;i++){
		scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].c);
		P[i].i = i;
	}
	sort(P, P+N);
	for (int i=0;i<N;i++){
		R[P[i].i] = i;
		IT[i+Z] = node(P[i].c);
	}
	for (int i=Z-1;i>=1;i--) IT[i] = IT[i*2] + IT[i*2+1];

	int c = 0;
	for (int i=0;i<N;i++) for (int j=0;j<N;j++) if (i < j){
		T[c++] = turn(P[i], P[j]);
	}
	sort(T, T+c);

	long long ans = max(0ll,IT[1].m);
	for (int i=0, j=0; i < c; i = j){
		while (j < c && T[i].dx == T[j].dx && T[i].dy == T[j].dy){
			int &x = R[T[j].i];
			int &y = R[T[j].j];
			swap(P[x], P[y]);
			swap(x, y);
			up(x,P[x].c);
			up(y,P[y].c);
			j++;
		}
		ans = max(ans,IT[1].m);
	}
	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

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

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