Submission #690651

#	Time	Username	Problem	Language	Result	Execution time	Memory
690651		browntoad	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1453 ms	132236 KiB

bulldozer

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=2005;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}

//=======================================================================================

struct Point{
	int x, y, w;
	Point operator -(Point b){
		return {x-b.x, y-b.y};
	}
};
struct Seg{
	Point a, b; 
	int ida, idb;
};
struct Node{
	int v, pf, sf, sm;
};
bool operator ==(Point a, Point b){
	if (a.x==b.x && a.y==b.y) return 1;
	return 0;
}
bool operator <(Point a, Point b){
	if (a.y == b.y) return a.x<b.x;
	return a.y<b.y;
}
int cross(Point a, Point b){
	return a.x*b.y - a.y*b.x;
}

vector<int> pos(maxn);
vector<Node> seg(4*maxn);
vector<Point> vc;
vector<Seg> segs;
int compslop(Seg A, Seg B){
	Point ta=A.b-A.a, tb=B.b-B.a;
	if (cross(ta, tb)==0) return 0;
	else if (cross(ta, tb)<0) return -1;
	else return 1;
}
bool shareline(Seg A, Seg B){
	int tmp2 = cross(A.b-A.a, B.a-A.a), tmp3 = cross(A.b-A.a, B.b-A.a);
	if (tmp2 == 0 && tmp3 == 0) return 1;
	return 0;
}
bool cmp(Seg A, Seg B){
	int tmp=compslop(A, B);
	if (tmp == 0){
		if (shareline(A, B)){
			// on the same line
			if (A.a == B.a) return A.b<B.b;
			else return A.a<B.a;
		}
		else{
			// doesn't matter how its ordered except for x-axis
			return A.a<B.a;
		}
	}	
	else return (tmp+1)/2; // 1 means its smaller, -1 means its bigger
}	

int n, fans = 0;

// seg treeeee
void pull(int x){
	seg[x].pf = max(seg[x+x].pf, seg[x+x].sm+seg[x+x+1].pf);
	seg[x].sf = max(seg[x+x+1].sf, seg[x+x].sf+seg[x+x+1].sm);
	seg[x].sm = seg[x+x].sm+seg[x+x+1].sm;
	seg[x].v = max({seg[x+x].v, seg[x+x+1].v, seg[x+x].sf+seg[x+x+1].pf});
}
void build(int l, int r, int x){
	// use vc's order
	if (l==r){
		seg[x].v = seg[x].pf = seg[x].sf = max(0ll, vc[l].w);
		seg[x].sm = vc[l].w;
		return;
	}
	int mid = (l+r)>>1;
	build(l, mid, x+x); 
	build(mid+1, r, x+x+1);
	pull(x);
}
void modify(int l, int r, int pos, int val, int x){
	if (l==r){
		seg[x].v = seg[x].pf = seg[x].sf = max(0ll, val);
		seg[x].sm = val;
		return;
	}
	int mid = (l+r)>>1;
	if (l<=pos && pos<=mid){
		modify(l, mid, pos, val, x+x);
	}
	else modify(mid+1, r, pos, val, x+x+1);
	pull(x);
}

void swapp(int a, int b){
	// index a and b
	modify(1, n, pos[b], vc[a].w, 1);
	modify(1, n, pos[a], vc[b].w, 1);
	swap(pos[a], pos[b]);
}
void check(){
	fans = max(fans, seg[1].v);
}

signed main (){
    // IOS();
    cin>>n;
    vc.resize(n+1);
    vc[0].x=-inf;
    vc[0].y=-inf;
    REP1(i, n){
    	cin>>vc[i].x>>vc[i].y>>vc[i].w;
    }
    sort(ALL(vc));
    REP1(i, n){
    	pos[i]=i;
    	// rank of point indexed as i is pos[i]
    }
    REP1(i, n){
    	FOR(j, i+1, n+1){
    		segs.pb({vc[i], vc[j], i, j});
    	}
    }
    sort(ALL(segs), cmp);
    /*REP(i, SZ(segs)){
    	// cout<<segs[i].ida<<' '<<segs[i].idb<<endl;
    	// cout<<segs[i].a.x<<' '<<segs[i].a.y<<" con "<<segs[i].b.x<<' '<<segs[i].b.y<<endl;
    }
    */
    build(1, n, 1);
    fans = seg[1].v;
    REP(i, SZ(segs)){
    	swapp(segs[i].ida, segs[i].idb);
    	if (i==SZ(segs)-1 || compslop(segs[i], segs[i+1])!=0) {
    		check();
    	}
    }
    cout<<fans<<endl;
}
/*
1:15
*/

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