Submission #113725

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
113725	2019-05-28T06:04:58 Z	Diuven	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2000 ms	120292 KB

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;
    }
    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]);
}

map<slope_t, vector<pii>> mp;

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++)
		mp[slope_t(X[i]-X[j], Y[i]-Y[j])].push_back({i,j});

	lint ans = Seg.get();

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

	for(auto p:mp){
		slope_t sl; vector<pii> V; tie(sl,V) = p;
		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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	4 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	896 KB	Output is correct
2	Correct	7 ms	896 KB	Output is correct
3	Correct	7 ms	896 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	6 ms	896 KB	Output is correct
8	Correct	7 ms	896 KB	Output is correct
9	Correct	6 ms	896 KB	Output is correct
10	Correct	7 ms	896 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	5 ms	896 KB	Output is correct
22	Correct	5 ms	896 KB	Output is correct
23	Correct	6 ms	896 KB	Output is correct
24	Correct	5 ms	896 KB	Output is correct
25	Correct	6 ms	896 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	6 ms	896 KB	Output is correct
29	Correct	6 ms	896 KB	Output is correct
30	Correct	6 ms	896 KB	Output is correct
31	Correct	6 ms	896 KB	Output is correct
32	Correct	6 ms	896 KB	Output is correct

Subtask #3
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	896 KB	Output is correct
2	Correct	7 ms	896 KB	Output is correct
3	Correct	7 ms	896 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	6 ms	896 KB	Output is correct
8	Correct	7 ms	896 KB	Output is correct
9	Correct	6 ms	896 KB	Output is correct
10	Correct	7 ms	896 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	5 ms	896 KB	Output is correct
22	Correct	5 ms	896 KB	Output is correct
23	Correct	6 ms	896 KB	Output is correct
24	Correct	5 ms	896 KB	Output is correct
25	Correct	6 ms	896 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	6 ms	896 KB	Output is correct
29	Correct	6 ms	896 KB	Output is correct
30	Correct	6 ms	896 KB	Output is correct
31	Correct	6 ms	896 KB	Output is correct
32	Correct	6 ms	896 KB	Output is correct
33	Execution timed out	2127 ms	120292 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	896 KB	Output is correct
2	Correct	7 ms	896 KB	Output is correct
3	Correct	7 ms	896 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	6 ms	896 KB	Output is correct
8	Correct	7 ms	896 KB	Output is correct
9	Correct	6 ms	896 KB	Output is correct
10	Correct	7 ms	896 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	5 ms	896 KB	Output is correct
22	Correct	5 ms	896 KB	Output is correct
23	Correct	6 ms	896 KB	Output is correct
24	Correct	5 ms	896 KB	Output is correct
25	Correct	6 ms	896 KB	Output is correct
26	Correct	5 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	6 ms	896 KB	Output is correct
29	Correct	6 ms	896 KB	Output is correct
30	Correct	6 ms	896 KB	Output is correct
31	Correct	6 ms	896 KB	Output is correct
32	Correct	6 ms	896 KB	Output is correct
33	Execution timed out	2127 ms	120292 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	4 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	4 ms	512 KB	Output is correct
5	Correct	4 ms	512 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	4 ms	512 KB	Output is correct
8	Correct	4 ms	512 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	7 ms	896 KB	Output is correct
17	Correct	7 ms	896 KB	Output is correct
18	Correct	7 ms	896 KB	Output is correct
19	Correct	7 ms	896 KB	Output is correct
20	Correct	6 ms	896 KB	Output is correct
21	Correct	6 ms	896 KB	Output is correct
22	Correct	6 ms	896 KB	Output is correct
23	Correct	7 ms	896 KB	Output is correct
24	Correct	6 ms	896 KB	Output is correct
25	Correct	7 ms	896 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	384 KB	Output is correct
28	Correct	2 ms	384 KB	Output is correct
29	Correct	2 ms	384 KB	Output is correct
30	Correct	2 ms	384 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct
33	Correct	2 ms	384 KB	Output is correct
34	Correct	2 ms	384 KB	Output is correct
35	Correct	2 ms	384 KB	Output is correct
36	Correct	5 ms	896 KB	Output is correct
37	Correct	5 ms	896 KB	Output is correct
38	Correct	6 ms	896 KB	Output is correct
39	Correct	5 ms	896 KB	Output is correct
40	Correct	6 ms	896 KB	Output is correct
41	Correct	5 ms	896 KB	Output is correct
42	Correct	6 ms	896 KB	Output is correct
43	Correct	6 ms	896 KB	Output is correct
44	Correct	6 ms	896 KB	Output is correct
45	Correct	6 ms	896 KB	Output is correct
46	Correct	6 ms	896 KB	Output is correct
47	Correct	6 ms	896 KB	Output is correct
48	Execution timed out	2127 ms	120292 KB	Time limit exceeded
49	Halted	0 ms	0 KB	-

Submission #113725

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0