Submission #113758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
113758	2019-05-28T07:23:44 Z	Diuven	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1418 ms	48112 KB

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;

/*
기울기: (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<vector<pii>> W;

pii D[MAX][MAX];

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;
    pii l1=D[a.first][a.second], l2=D[b.first][b.second];
    lint w = 1LL*l1.second*l2.first - 1LL*l1.first*l2.second;
    return w==0 ? 0 : (w<0 ? -1 : 1);
}

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

	// 기울기 (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);
        int dx=X[i]-X[j], dy=Y[i]-Y[j];
        if(dx<0 || (dx==0 && dy>0)) dx=-dx, dy=-dy;
        D[i][j] = D[j][i] = {dx,dy};
    }

    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;
        lint dx,dy; tie(dx,dy) = D[u][v];

        lint ub = -dy*X[u] + dx*Y[u];
        lint tb = -dy*X[t] + dx*Y[t];
        if(ub!=tb) return ub<tb;

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

	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';

	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	896 KB	Output is correct
2	Correct	4 ms	896 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	4 ms	1024 KB	Output is correct
5	Correct	3 ms	944 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	3 ms	896 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	4 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	3 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	3 ms	896 KB	Output is correct
2	Correct	3 ms	1024 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	4 ms	1024 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	4 ms	996 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	3 ms	896 KB	Output is correct
22	Correct	3 ms	896 KB	Output is correct
23	Correct	4 ms	896 KB	Output is correct
24	Correct	3 ms	896 KB	Output is correct
25	Correct	4 ms	896 KB	Output is correct
26	Correct	4 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	3 ms	896 KB	Output is correct
29	Correct	3 ms	1024 KB	Output is correct
30	Correct	4 ms	1024 KB	Output is correct
31	Correct	3 ms	896 KB	Output is correct
32	Correct	3 ms	896 KB	Output is correct

Subtask #3
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	896 KB	Output is correct
2	Correct	3 ms	1024 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	4 ms	1024 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	4 ms	996 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	3 ms	896 KB	Output is correct
22	Correct	3 ms	896 KB	Output is correct
23	Correct	4 ms	896 KB	Output is correct
24	Correct	3 ms	896 KB	Output is correct
25	Correct	4 ms	896 KB	Output is correct
26	Correct	4 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	3 ms	896 KB	Output is correct
29	Correct	3 ms	1024 KB	Output is correct
30	Correct	4 ms	1024 KB	Output is correct
31	Correct	3 ms	896 KB	Output is correct
32	Correct	3 ms	896 KB	Output is correct
33	Correct	1365 ms	48024 KB	Output is correct
34	Correct	1418 ms	47964 KB	Output is correct
35	Correct	1378 ms	47972 KB	Output is correct
36	Correct	1381 ms	47976 KB	Output is correct
37	Correct	1359 ms	47928 KB	Output is correct
38	Correct	1388 ms	47844 KB	Output is correct
39	Correct	1349 ms	47964 KB	Output is correct
40	Correct	1348 ms	47968 KB	Output is correct
41	Correct	1327 ms	48068 KB	Output is correct
42	Correct	1313 ms	47924 KB	Output is correct
43	Correct	1228 ms	47868 KB	Output is correct
44	Correct	1239 ms	47956 KB	Output is correct
45	Correct	1210 ms	47936 KB	Output is correct
46	Correct	1235 ms	48036 KB	Output is correct
47	Correct	1197 ms	47936 KB	Output is correct
48	Correct	1174 ms	47908 KB	Output is correct
49	Correct	1197 ms	47956 KB	Output is correct
50	Correct	1206 ms	47964 KB	Output is correct
51	Correct	1201 ms	47940 KB	Output is correct
52	Correct	1238 ms	47928 KB	Output is correct
53	Correct	1228 ms	48112 KB	Output is correct
54	Correct	1234 ms	47936 KB	Output is correct

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	896 KB	Output is correct
2	Correct	3 ms	1024 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	3 ms	896 KB	Output is correct
5	Correct	4 ms	1024 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	4 ms	996 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	3 ms	896 KB	Output is correct
22	Correct	3 ms	896 KB	Output is correct
23	Correct	4 ms	896 KB	Output is correct
24	Correct	3 ms	896 KB	Output is correct
25	Correct	4 ms	896 KB	Output is correct
26	Correct	4 ms	896 KB	Output is correct
27	Correct	6 ms	896 KB	Output is correct
28	Correct	3 ms	896 KB	Output is correct
29	Correct	3 ms	1024 KB	Output is correct
30	Correct	4 ms	1024 KB	Output is correct
31	Correct	3 ms	896 KB	Output is correct
32	Correct	3 ms	896 KB	Output is correct
33	Correct	1365 ms	48024 KB	Output is correct
34	Correct	1418 ms	47964 KB	Output is correct
35	Correct	1378 ms	47972 KB	Output is correct
36	Correct	1381 ms	47976 KB	Output is correct
37	Correct	1359 ms	47928 KB	Output is correct
38	Correct	1388 ms	47844 KB	Output is correct
39	Correct	1349 ms	47964 KB	Output is correct
40	Correct	1348 ms	47968 KB	Output is correct
41	Correct	1327 ms	48068 KB	Output is correct
42	Correct	1313 ms	47924 KB	Output is correct
43	Correct	1228 ms	47868 KB	Output is correct
44	Correct	1239 ms	47956 KB	Output is correct
45	Correct	1210 ms	47936 KB	Output is correct
46	Correct	1235 ms	48036 KB	Output is correct
47	Correct	1197 ms	47936 KB	Output is correct
48	Correct	1174 ms	47908 KB	Output is correct
49	Correct	1197 ms	47956 KB	Output is correct
50	Correct	1206 ms	47964 KB	Output is correct
51	Correct	1201 ms	47940 KB	Output is correct
52	Correct	1238 ms	47928 KB	Output is correct
53	Correct	1228 ms	48112 KB	Output is correct
54	Correct	1234 ms	47936 KB	Output is correct
55	Correct	1344 ms	47936 KB	Output is correct
56	Correct	1418 ms	47860 KB	Output is correct
57	Correct	1315 ms	47892 KB	Output is correct
58	Correct	1355 ms	47952 KB	Output is correct
59	Correct	1317 ms	47936 KB	Output is correct
60	Correct	1339 ms	47872 KB	Output is correct
61	Correct	1371 ms	47952 KB	Output is correct
62	Correct	1383 ms	47940 KB	Output is correct
63	Correct	1369 ms	47936 KB	Output is correct
64	Correct	1378 ms	47936 KB	Output is correct
65	Correct	1257 ms	47968 KB	Output is correct
66	Correct	1344 ms	47928 KB	Output is correct
67	Correct	1295 ms	47936 KB	Output is correct
68	Correct	1258 ms	47936 KB	Output is correct
69	Correct	1337 ms	47860 KB	Output is correct
70	Correct	1305 ms	47956 KB	Output is correct
71	Correct	1337 ms	47904 KB	Output is correct
72	Correct	1312 ms	47936 KB	Output is correct
73	Correct	1326 ms	47864 KB	Output is correct
74	Correct	1329 ms	47908 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	896 KB	Output is correct
2	Correct	4 ms	896 KB	Output is correct
3	Correct	4 ms	896 KB	Output is correct
4	Correct	4 ms	1024 KB	Output is correct
5	Correct	3 ms	944 KB	Output is correct
6	Correct	4 ms	896 KB	Output is correct
7	Correct	3 ms	896 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	3 ms	896 KB	Output is correct
10	Correct	4 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	3 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	3 ms	896 KB	Output is correct
17	Correct	3 ms	1024 KB	Output is correct
18	Correct	4 ms	896 KB	Output is correct
19	Correct	3 ms	896 KB	Output is correct
20	Correct	4 ms	1024 KB	Output is correct
21	Correct	4 ms	896 KB	Output is correct
22	Correct	4 ms	896 KB	Output is correct
23	Correct	4 ms	1024 KB	Output is correct
24	Correct	3 ms	896 KB	Output is correct
25	Correct	4 ms	996 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	3 ms	896 KB	Output is correct
37	Correct	3 ms	896 KB	Output is correct
38	Correct	4 ms	896 KB	Output is correct
39	Correct	3 ms	896 KB	Output is correct
40	Correct	4 ms	896 KB	Output is correct
41	Correct	4 ms	896 KB	Output is correct
42	Correct	6 ms	896 KB	Output is correct
43	Correct	3 ms	896 KB	Output is correct
44	Correct	3 ms	1024 KB	Output is correct
45	Correct	4 ms	1024 KB	Output is correct
46	Correct	3 ms	896 KB	Output is correct
47	Correct	3 ms	896 KB	Output is correct
48	Correct	1365 ms	48024 KB	Output is correct
49	Correct	1418 ms	47964 KB	Output is correct
50	Correct	1378 ms	47972 KB	Output is correct
51	Correct	1381 ms	47976 KB	Output is correct
52	Correct	1359 ms	47928 KB	Output is correct
53	Correct	1388 ms	47844 KB	Output is correct
54	Correct	1349 ms	47964 KB	Output is correct
55	Correct	1348 ms	47968 KB	Output is correct
56	Correct	1327 ms	48068 KB	Output is correct
57	Correct	1313 ms	47924 KB	Output is correct
58	Correct	1228 ms	47868 KB	Output is correct
59	Correct	1239 ms	47956 KB	Output is correct
60	Correct	1210 ms	47936 KB	Output is correct
61	Correct	1235 ms	48036 KB	Output is correct
62	Correct	1197 ms	47936 KB	Output is correct
63	Correct	1174 ms	47908 KB	Output is correct
64	Correct	1197 ms	47956 KB	Output is correct
65	Correct	1206 ms	47964 KB	Output is correct
66	Correct	1201 ms	47940 KB	Output is correct
67	Correct	1238 ms	47928 KB	Output is correct
68	Correct	1228 ms	48112 KB	Output is correct
69	Correct	1234 ms	47936 KB	Output is correct
70	Correct	1344 ms	47936 KB	Output is correct
71	Correct	1418 ms	47860 KB	Output is correct
72	Correct	1315 ms	47892 KB	Output is correct
73	Correct	1355 ms	47952 KB	Output is correct
74	Correct	1317 ms	47936 KB	Output is correct
75	Correct	1339 ms	47872 KB	Output is correct
76	Correct	1371 ms	47952 KB	Output is correct
77	Correct	1383 ms	47940 KB	Output is correct
78	Correct	1369 ms	47936 KB	Output is correct
79	Correct	1378 ms	47936 KB	Output is correct
80	Correct	1257 ms	47968 KB	Output is correct
81	Correct	1344 ms	47928 KB	Output is correct
82	Correct	1295 ms	47936 KB	Output is correct
83	Correct	1258 ms	47936 KB	Output is correct
84	Correct	1337 ms	47860 KB	Output is correct
85	Correct	1305 ms	47956 KB	Output is correct
86	Correct	1337 ms	47904 KB	Output is correct
87	Correct	1312 ms	47936 KB	Output is correct
88	Correct	1326 ms	47864 KB	Output is correct
89	Correct	1329 ms	47908 KB	Output is correct
90	Correct	1416 ms	47968 KB	Output is correct
91	Correct	1334 ms	47936 KB	Output is correct
92	Correct	1302 ms	48064 KB	Output is correct
93	Correct	1330 ms	47936 KB	Output is correct
94	Correct	1315 ms	47936 KB	Output is correct
95	Correct	1300 ms	47980 KB	Output is correct
96	Correct	1325 ms	47876 KB	Output is correct
97	Correct	1316 ms	47924 KB	Output is correct
98	Correct	1324 ms	47932 KB	Output is correct
99	Correct	1307 ms	47844 KB	Output is correct
100	Correct	1334 ms	47940 KB	Output is correct
101	Correct	1318 ms	48060 KB	Output is correct
102	Correct	1329 ms	47936 KB	Output is correct
103	Correct	1264 ms	47936 KB	Output is correct
104	Correct	1271 ms	47936 KB	Output is correct
105	Correct	1267 ms	47936 KB	Output is correct
106	Correct	1300 ms	47936 KB	Output is correct
107	Correct	1331 ms	47936 KB	Output is correct
108	Correct	1327 ms	47936 KB	Output is correct
109	Correct	1313 ms	47956 KB	Output is correct
110	Correct	1070 ms	47896 KB	Output is correct
111	Correct	1067 ms	47936 KB	Output is correct
112	Correct	1014 ms	47936 KB	Output is correct
113	Correct	983 ms	47940 KB	Output is correct
114	Correct	965 ms	47968 KB	Output is correct
115	Correct	1014 ms	47936 KB	Output is correct
116	Correct	1068 ms	48064 KB	Output is correct
117	Correct	1046 ms	47972 KB	Output is correct
118	Correct	1049 ms	47936 KB	Output is correct
119	Correct	975 ms	47848 KB	Output is correct
120	Correct	2 ms	384 KB	Output is correct
121	Correct	2 ms	384 KB	Output is correct
122	Correct	1188 ms	47936 KB	Output is correct
123	Correct	1212 ms	47932 KB	Output is correct
124	Correct	1169 ms	47964 KB	Output is correct
125	Correct	1168 ms	47936 KB	Output is correct
126	Correct	1199 ms	48068 KB	Output is correct
127	Correct	1304 ms	48064 KB	Output is correct
128	Correct	1250 ms	47948 KB	Output is correct
129	Correct	1288 ms	47936 KB	Output is correct
130	Correct	1277 ms	47940 KB	Output is correct
131	Correct	1145 ms	47940 KB	Output is correct
132	Correct	1145 ms	47940 KB	Output is correct
133	Correct	1158 ms	47992 KB	Output is correct

Submission #113758

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 20.0 / 20.0

Subtask #3 35.0 / 35.0

Subtask #4 20.0 / 20.0

Subtask #5 20.0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
20.0 / 20.0

Subtask #3
35.0 / 35.0

Subtask #4
20.0 / 20.0

Subtask #5
20.0 / 20.0