Submission #113727

#	Time	Username	Problem	Language	Result	Execution time	Memory
113727		Diuven	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2023 ms	107260 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;
typedef tuple<lint, int, int> lii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 2019;
const lint LNF = 2e18;

int n, X[MAX], Y[MAX], V[MAX];

inline lint max(lint a, lint b){ return a<b ? b : a; }

lint gcd(lint a, lint b){
	if(b==0) return a;
	return gcd(b,a%b);
}

class Seg_t{
	struct node {
		lint ls, rs, ms, su;
		node operator + (const node &op) const {
			node res = {0,0,0,0};
			// ls, rs should not be empty.
			// ms may be empty
			res.ls = max(ls, su+op.ls);
			res.rs = max(op.rs, op.su+rs);
			res.ms = max(rs+op.ls, max(ms, op.ms));
			res.su = su + op.su;
			return res;
		}
	} T[1<<12];
	void upt(int v, int s, int e, int p, int x){
		if(p<s || e<p) return;
		if(s==e){ T[v]={x,x,max(0,x),x}; return; }
		upt(v*2,s,(s+e)/2,p,x); upt(v*2+1,(s+e)/2+1,e,p,x);
		T[v] = T[v*2]+T[v*2+1];
	}
  public:
    void upt(int p, int x){ upt(1,1,n,p,x); }
	lint get(){ return T[1].ms; }
} Seg;

class slope_t{
	lint dx, dy;
  public:
    slope_t(){}
    slope_t(lint a, lint b){
        assert(a!=0 || b!=0);
        lint g=gcd(abs(a), abs(b));
        if(a<0 || (a==0 && b<0)) a*=-1, b*=-1;
        dx = a/g, dy = b/g;
    }
    bool operator < (const slope_t &op) const {
        return dy*op.dx < op.dy*dx;
    }
    bool operator == (const slope_t &op) const {
        return dx==op.dx && dy==op.dy;
    }
    lii operator () (int i){
        return lii(-dy*X[i] + dx*Y[i], -X[i], Y[i]);
    }
    void show(){
        cout<<"Change: "<<dx<<' '<<dy<<'\n';
    }
};

/*
기울기: (dx, dy). dx는 항상 0 이상.
*/

int nu[MAX], re[MAX];
void ch(int a, int b){
	// a랑 b를 바꿔라.
    // cout<<"Swap: "<<V[a]<<' '<<V[b]<<'\n';
	int i=re[a], j=re[b];
	assert(a!=b);
	Seg.upt(i, V[b]), Seg.upt(j, V[a]);
	swap(nu[i], nu[j]); swap(re[a], re[b]);
}

vector<slope_t> sls;
vector<vector<pii>> W;

void debug(){
    cout<<"\nDebug!!\n";
    for(int j=1; j<=n; j++){
        int i=nu[j];
        cout<<X[i]<<' '<<Y[i]<<' '<<V[i]<<'\n';
    }
    cout<<'\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n;
	for(int i=1; i<=n; i++) cin>>X[i]>>Y[i]>>V[i];

	iota(nu+1, nu+n+1, 1);
	sort(nu+1, nu+n+1, [&](int a, int b){
		return (X[a]<X[b] || (X[a]==X[b] && Y[a]>Y[b]));
	});
	for(int i=1; i<=n; i++){
		Seg.upt(i, V[nu[i]]);
		re[nu[i]]=i;
	}

	// 기울기 (a,b)에 대해서 점의 정렬 기준: (-bx+ay, -x, y)의 오름차순
	// 의미: 기울기 (a,b)인 선을 그렸을 때, y절편이 작은거부터. 동일하다면 미소량 큰 기울기에서 y절편 작은거부터. y는 y축평행정렬을 고려한 것.


	for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
        slope_t sl = slope_t(X[i]-X[j], Y[i]-Y[j]);
        sls.push_back(sl);
        // pii p = {i,j};
        // Yea.emplace_back(sl, p);
    }

    sort(sls.begin(), sls.end());
    sls.resize(unique(sls.begin(), sls.end()) - sls.begin());
    W.resize(sls.size());


	for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++){
        slope_t sl = slope_t(X[i]-X[j], Y[i]-Y[j]);
        pii p = {i,j};
        int k = lower_bound(sls.begin(), sls.end(), sl) - sls.begin();
        W[k].push_back(p);
    }

	lint ans = Seg.get();

    // cout<<"now: "<<Seg.get()<<'\n';
    // debug();

    for(int i=0; i<int(sls.size()); i++){
		slope_t sl=sls[i]; vector<pii> &V=W[i];

		sort(V.begin(), V.end(), [&](pii a, pii b){
			int u,v, s,t; tie(u,v)=a, tie(s,t)=b;
			auto ub=sl(u), vb=sl(v), sb=sl(s), tb=sl(t);
			if(ub>vb) swap(ub,vb);
			if(sb>tb) swap(sb,tb);
			return make_pair(ub,vb) < make_pair(sb,tb);
		});
		for(pii q:V) ch(q.first, q.second);
        // sl.show();
        // debug();
        // cout<<"now: "<<Seg.get()<<'\n';
		ans = max(ans, Seg.get());
	}

	cout<<ans<<'\n';

	return 0;
}

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