Submission #113741

#	Time	Username	Problem	Language	Result	Execution time	Memory
113741		Diuven	Bulldozer (JOI17_bulldozer)	C++14	60 / 100	1253 ms	17172 KiB

bulldozer

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

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

const int MAX = 2019;

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

inline lint _max(lint a, lint b){ return a<b ? b : a; }
inline int _abs(int a){ return a<0 ? -a : a; }

int gcd(int a, int 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(s==e){ T[v]={x,x,_max(0,x),x}; return; }
        int mid = (s+e)/2;
        if(p<=mid) upt(v*2,s,(s+e)/2,p,x);
        else 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(int a, int b){
        int g=gcd(_abs(a), _abs(b));
        if(a<0 || (a==0 && b<0)) a*=-1, b*=-1;
        dx = a/g, dy = b/g;
    }
    slope_t(pii p): slope_t(X[p.first]-X[p.second], Y[p.first]-Y[p.second]) {}
    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];
	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 cmp(pii a, pii b){
    int u,v, s,t; tie(u,v)=a, tie(s,t)=b;
    if(X[u]<X[v]) swap(u,v);
    if(X[s]<X[t]) swap(s,t);
    lint w = 1LL*(X[s]-X[t])*(Y[u]-Y[v]) - 1LL*(X[u]-X[v])*(Y[s]-Y[t]);
    return w==0 ? 0 : (w<0 ? 1 : -1);
}

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

    clock_t t_start = clock();

	cin>>n;
	for(int i=1; i<=n; i++) cin>>X[i]>>Y[i]>>V[i];
    int rnk[MAX], tmp[MAX];
    iota(tmp+1, tmp+n+1, 1);
    sort(tmp+1, tmp+n+1, [](int a, int b){ return pii(-X[a],Y[a]) < pii(-X[b],Y[b]); });
    for(int i=1; i<=n; i++) rnk[tmp[i]]=i;

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

    clock_t t_1 = clock();

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

    vector<pii> P;

    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) P.emplace_back(i,j);

    sort(P.begin(), P.end(), [&](pii a, pii b){
        int z = cmp(a,b);
        if(z!=0) return z>0;
        int u,v, t,s; tie(u,v)=a, tie(t,s)=b;
        pii p={rnk[u],rnk[v]}, q={rnk[t],rnk[s]};
        if(p.first>p.second) swap(p.first, p.second);
        if(q.first>q.second) swap(q.first, q.second);
        return p<q;
    });

    clock_t t_2 = clock();

    clock_t t_3 = clock();

	lint ans = Seg.get();

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

    for(int i=0; i<int(P.size());){
        pii st = P[i];
        while(i<int(P.size()) && cmp(st, P[i])==0){
            ch(P[i].first, P[i].second); i++;
        }
        ans = _max(ans, Seg.get());
    }

	cout<<ans<<'\n';

    clock_t t_4 = clock();

    // cout<<"Time elapsed: "<<t_1-t_start<<", "<<t_2-t_1<<", "<<t_3-t_2<<", "<<t_4-t_3<<"\n";
    // cout<<"Total: "<<double(t_4-t_start)/CLOCKS_PER_SEC<<'\n';


	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:96:13: warning: unused variable 't_start' [-Wunused-variable]
     clock_t t_start = clock();
             ^~~~~~~
bulldozer.cpp:114:13: warning: unused variable 't_1' [-Wunused-variable]
     clock_t t_1 = clock();
             ^~~
bulldozer.cpp:133:13: warning: unused variable 't_2' [-Wunused-variable]
     clock_t t_2 = clock();
             ^~~
bulldozer.cpp:135:13: warning: unused variable 't_3' [-Wunused-variable]
     clock_t t_3 = clock();
             ^~~
bulldozer.cpp:152:13: warning: unused variable 't_4' [-Wunused-variable]
     clock_t t_4 = clock();
             ^~~

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