QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212364#4581. Energy Generationucup-team1004AC ✓1ms3936kbC++142.7kb2023-10-13 15:16:552023-10-13 15:16:56

Judging History

你现在查看的是最新测评结果

  • [2023-10-13 15:16:56]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3936kb
  • [2023-10-13 15:16:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
ostream& operator << (ostream &out,const pair<T,T>&x){
	return out<<'['<<x.first<<','<<x.second<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
const int N=55,Inf=1e9;
const ll INF=1e18;
namespace Flow{
	const int V=N*2,E=N*2*2+N*N*2;
	int s,t,kk,head[V],d[V],cur[V];
	struct edges{
		int to;
		ll c;
		int nex;
	}edge[E];
	void init(int x,int y){
		s=x,t=y,kk=1;
		fill(head+s,head+1+t,0);
	}
	int add(int u,int v,ll c){
		// debug(u,v,c);
		edge[++kk]={v,c,head[u]},head[u]=kk;
		edge[++kk]={u,0,head[v]},head[v]=kk;
		return kk-1;
	}
	bool bfs(){
		queue<int>q;
		q.push(s);
		copy(head+s,head+1+t,cur+s);
		fill(d+s,d+1+t,-1),d[s]=0;
		for(int u;!q.empty();){
			u=q.front(),q.pop();
			for(int i=head[u];i;i=edge[i].nex){
				int v=edge[i].to;
				if(edge[i].c&&!~d[v])d[v]=d[u]+1,q.push(v);
			}
		}
		return ~d[t];
	}
	ll dfs(int u,ll lim=INF){
		if(u==t)return lim;
		ll flow=0;
		for(int i=cur[u];i&&flow<lim;i=edge[i].nex){
			cur[u]=i;
			int v=edge[i].to;
			ll c=edge[i].c;
			if(!c||d[v]!=d[u]+1)continue;
			ll f=dfs(v,min(lim-flow,c));
			if(!f)d[v]=-1;
			edge[i].c-=f,edge[i^1].c+=f,flow+=f;
		}
		return flow;
	}
	ll dinic(){
		ll flow=0;
		for(;bfs();)flow+=dfs(s);
		return flow;
	}
}
const int ax[4]={1,1,-1,-1},ay[4]={1,-1,-1,1};
int n,R,G,P,a[N];
struct vec{
	int x,y,arg;
}p[N];
vector<pair<int,int> >E;
ll solve(){
	ll ans=1ll*E.size()*G;
	int s=0,t=n+n+1;
	Flow::init(s,t);
	// debug(ary(a,1,n));
	for(int i=1;i<=n;i++)Flow::add(s,i,Inf-a[i]*P);
	for(int i=1;i<=n;i++)Flow::add(i+n,t,Inf+a[i]*P);
	for(int i=1;i<=n;i++)Flow::add(i,i+n,INF);
	for(auto e:E){
		int u,v;
		tie(u,v)=e;
		Flow::add(u,v+n,G*4);
	}
	ll res=Flow::dinic();
	// debug(ans,res);
	return ans-res+1ll*Inf*n;
}
int main(){
	cin>>n>>R>>G>>P;
	for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y>>p[i].arg;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int dx=p[i].x-p[j].x,dy=p[i].y-p[j].y;
			if(!dx||!dy)continue;
			if(dx*dx+dy*dy<=R*R)E.push_back({i,j});
		}
	}
	// debug(E);
	ll ans=0;
	for(int i=1;i<=n;i++)a[i]=ax[p[i].arg/90];
	ans+=solve();
	for(int i=1;i<=n;i++)a[i]=ay[p[i].arg/90];
	ans+=solve();
	cout<<ans/2<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3576kb

input:

3 10 10 15
0 0 0
2 2 180
100 100 180

output:

35

result:

ok single line: '35'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

3 10 1 1000
0 0 0
2 2 0
-4 4 180

output:

2998

result:

ok single line: '2998'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

4 10 1000 1
0 0 0
0 2 90
2 0 180
2 2 270

output:

4002

result:

ok single line: '4002'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

10 1000 1 2
186 98 180
206 689 270
695 90 90
292 247 90
-405 -125 270
928 -887 90
-45 -233 270
58 625 90
-215 136 270
-858 672 90

output:

62

result:

ok single line: '62'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

50 322 127 256
-418 -408 0
-317 -390 90
-208 -295 270
-187 -379 90
-343 -395 0
-278 -279 270
-191 -239 270
-192 -411 180
-203 -181 90
-330 -231 0
387 -416 180
352 -402 270
138 -181 0
299 -435 180
261 -273 0
191 -433 270
430 -182 0
290 -375 90
293 -426 90
458 -297 270
-416 278 270
-411 167 90
-312 23...

output:

66300

result:

ok single line: '66300'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

50 322 127 256
-246 -215 90
-368 -267 90
-291 -404 0
-369 -356 0
-417 -399 90
-407 -388 180
-383 -332 0
-198 -285 270
-311 -205 270
-341 -386 0
278 -230 90
235 -291 90
393 -441 90
263 -217 270
145 -412 90
167 -170 90
424 -178 180
199 -237 270
385 -162 180
285 -345 180
-336 341 90
-285 261 90
-301 19...

output:

68332

result:

ok single line: '68332'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

50 165 547 231
-471 31 0
-494 -43 0
-556 46 180
-463 71 90
-508 -3 0
-479 -1 270
-373 6 90
-351 -60 90
-373 -33 0
-392 53 0
-417 79 270
-402 -33 0
-373 -77 90
-297 -66 180
-402 -11 90
-217 16 0
-211 45 180
-373 72 90
-333 72 180
-336 -42 90
-297 -79 0
-149 23 90
-240 32 180
-204 52 180
-144 6 90
-13...

output:

470372

result:

ok single line: '470372'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

50 322 547 231
-206 -278 270
-281 -242 90
-331 -319 180
-335 -296 270
-241 -183 270
-385 -422 180
-196 -255 0
-205 -248 0
-304 -215 180
-392 -389 90
444 -260 0
343 -161 90
247 -236 0
292 -267 270
184 -272 90
202 -380 270
297 -255 270
254 -169 0
311 -231 180
402 -357 90
-315 214 270
-368 281 90
-180 ...

output:

318415

result:

ok single line: '318415'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

50 322 547 231
-210 -328 180
-281 -284 90
-339 -348 270
-282 -236 90
-261 -190 180
-284 -296 90
-201 -411 0
-272 -287 270
-244 -243 0
-185 -414 270
207 -221 0
348 -167 0
245 -353 180
328 -432 90
405 -216 90
442 -366 0
244 -138 0
304 -197 0
210 -180 90
215 -442 180
-330 367 270
-299 245 180
-347 269 ...

output:

303962

result:

ok single line: '303962'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3524kb

input:

50 165 543 121
-490 35 180
-467 71 90
-438 -23 180
-511 56 0
-455 -14 90
-508 -81 90
-475 -73 270
-397 1 180
-497 -45 0
-507 2 270
-405 -3 180
-294 30 180
-442 70 90
-288 -4 180
-436 8 180
-344 63 180
-368 -64 0
-353 -46 270
-276 -46 180
-229 -66 90
-227 49 0
-187 -80 90
-222 -76 270
-173 -43 180
-1...

output:

457088

result:

ok single line: '457088'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

50 322 543 121
-247 -393 90
-401 -286 180
-320 -367 180
-293 -422 0
-297 -288 270
-408 -403 0
-185 -200 180
-265 -211 0
-423 -416 270
-417 -191 90
197 -403 270
177 -237 0
223 -334 270
321 -144 180
307 -224 0
271 -334 270
182 -301 0
464 -146 270
339 -244 270
265 -450 180
-181 423 90
-399 307 90
-410 ...

output:

273070

result:

ok single line: '273070'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

50 322 543 121
-274 -220 90
-332 -392 180
-423 -235 180
-322 -374 270
-342 -383 270
-281 -266 90
-189 -360 0
-313 -244 90
-228 -324 0
-191 -397 90
208 -206 90
243 -240 0
266 -405 0
215 -373 180
251 -392 180
389 -232 0
344 -345 0
348 -389 90
399 -355 270
395 -150 90
-206 441 270
-443 186 180
-227 173...

output:

288153

result:

ok single line: '288153'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

50 165 122 531
-472 29 180
-454 -36 0
-517 -60 90
-457 -32 270
-435 -26 180
-410 60 180
-456 -34 90
-399 8 270
-497 46 180
-449 50 0
-307 -78 270
-442 51 0
-339 -66 270
-433 0 0
-419 64 270
-364 46 180
-209 75 180
-373 81 270
-354 4 90
-209 73 0
-227 -40 90
-288 43 0
-209 63 0
-175 -52 0
-284 -37 0
...

output:

103384

result:

ok single line: '103384'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

50 322 122 531
-415 -196 180
-399 -233 180
-229 -359 0
-270 -239 270
-349 -385 90
-287 -226 180
-307 -367 0
-358 -257 0
-398 -202 180
-392 -351 270
181 -397 270
258 -356 0
244 -349 90
265 -359 270
414 -353 90
421 -339 0
409 -236 0
451 -247 0
463 -194 270
215 -432 270
-359 354 270
-408 281 270
-249 3...

output:

66109

result:

ok single line: '66109'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

50 1000 1 2
296 -826 0
666 -264 270
-720 557 270
958 741 90
602 599 90
561 41 180
441 -764 180
-714 164 180
517 890 180
-171 -789 90
-628 -471 270
-88 474 0
-730 137 0
235 -352 0
-556 224 180
888 -227 270
-100 364 90
-126 226 270
-802 395 0
334 940 180
-659 341 0
-743 -284 270
216 -369 90
140 -350 0...

output:

1190

result:

ok single line: '1190'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

50 322 122 531
-360 -299 0
-417 -292 180
-189 -403 90
-296 -252 270
-382 -264 90
-261 -331 90
-254 -423 0
-225 -350 90
-336 -272 270
-330 -223 180
160 -267 90
374 -439 90
388 -432 0
403 -238 180
370 -370 180
314 -292 270
420 -221 270
227 -209 270
393 -204 180
326 -277 180
-312 379 270
-434 387 180
-...

output:

67243

result:

ok single line: '67243'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

50 165 122 175
-476 -33 90
-455 -63 90
-573 5 270
-417 -48 0
-551 -70 0
-356 31 0
-496 -48 0
-370 -61 90
-464 -71 270
-387 -41 270
-277 -16 0
-325 6 270
-377 12 0
-339 -66 90
-394 26 270
-297 -1 180
-297 2 270
-332 73 270
-256 -40 270
-311 -2 0
-237 45 90
-267 34 90
-286 -32 180
-266 68 180
-201 38 ...

output:

112314

result:

ok single line: '112314'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

50 322 122 175
-225 -304 270
-362 -331 90
-330 -257 270
-195 -261 90
-201 -361 180
-328 -181 0
-376 -236 0
-183 -396 0
-367 -387 180
-338 -313 270
208 -403 90
455 -302 270
355 -427 0
397 -202 180
458 -195 90
452 -271 0
201 -258 180
410 -331 180
389 -464 0
230 -329 180
-216 285 0
-196 247 270
-257 36...

output:

64384

result:

ok single line: '64384'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

50 322 122 175
-409 -235 270
-267 -337 270
-186 -390 0
-330 -265 180
-413 -301 0
-305 -296 180
-339 -306 90
-347 -407 0
-335 -187 180
-229 -316 180
373 -295 90
258 -360 90
142 -375 180
417 -451 90
379 -452 270
393 -258 270
388 -335 180
264 -183 180
458 -361 0
400 -169 180
-275 164 0
-357 165 270
-40...

output:

63859

result:

ok single line: '63859'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

50 165 251 175
-444 82 180
-442 7 0
-528 46 90
-437 15 270
-547 -76 0
-468 -76 180
-423 -6 180
-497 -16 270
-499 29 270
-483 75 0
-353 -14 180
-368 74 90
-425 50 270
-310 78 90
-307 -70 270
-362 30 90
-209 -44 0
-341 26 270
-370 5 180
-295 18 270
-263 77 0
-176 -42 270
-146 62 180
-227 -21 180
-151 ...

output:

226798

result:

ok single line: '226798'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

50 322 251 175
-287 -233 270
-415 -246 0
-421 -347 180
-321 -218 270
-330 -366 90
-190 -192 270
-345 -351 90
-423 -276 90
-395 -215 0
-373 -322 270
308 -381 270
203 -264 90
193 -202 270
440 -277 180
450 -426 0
380 -461 270
440 -400 90
190 -385 0
415 -408 90
172 -409 90
-314 248 90
-437 249 90
-355 2...

output:

135411

result:

ok single line: '135411'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

50 322 251 175
-261 -270 180
-308 -325 180
-354 -236 0
-381 -350 90
-319 -317 90
-405 -287 90
-212 -215 270
-289 -267 270
-333 -182 0
-234 -180 180
388 -377 90
208 -274 270
168 -205 0
412 -208 180
402 -175 90
452 -258 270
382 -197 270
140 -280 270
227 -153 90
343 -285 90
-165 287 180
-277 221 0
-350...

output:

141762

result:

ok single line: '141762'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

50 165 669 699
-498 47 90
-482 18 0
-467 -48 90
-565 65 0
-493 -30 90
-439 82 180
-498 72 0
-446 46 180
-495 19 270
-491 3 270
-424 70 0
-363 -24 0
-418 -8 0
-385 -75 0
-368 -8 270
-214 49 180
-275 3 270
-272 81 90
-221 -25 0
-305 -27 90
-237 4 0
-279 16 270
-175 17 0
-164 56 270
-145 -29 0
-220 -64...

output:

593034

result:

ok single line: '593034'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

50 322 669 699
-199 -409 180
-378 -238 0
-233 -421 270
-291 -312 180
-248 -401 270
-181 -287 180
-267 -313 0
-394 -255 0
-236 -329 270
-387 -302 0
238 -193 0
286 -260 270
197 -252 0
338 -170 180
299 -154 0
376 -343 0
175 -264 0
138 -421 0
416 -461 180
446 -384 90
-175 342 180
-302 294 180
-205 324 0...

output:

370806

result:

ok single line: '370806'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

50 322 669 699
-390 -201 0
-207 -258 0
-216 -417 180
-321 -408 270
-387 -228 180
-305 -385 0
-386 -264 180
-223 -282 90
-193 -306 180
-362 -333 270
155 -265 90
325 -392 270
189 -409 0
273 -379 90
328 -324 90
179 -335 90
296 -452 0
225 -290 270
358 -313 180
292 -401 270
-161 417 0
-392 199 0
-411 253...

output:

347880

result:

ok single line: '347880'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

50 1000 100 133
-737 685 180
683 433 90
-634 -471 90
106 173 0
658 -670 90
-707 -991 180
-460 139 180
-423 471 270
-503 -133 270
-208 152 180
145 792 180
784 -554 270
-106 360 90
958 693 180
-405 -768 270
-176 628 90
763 351 0
-374 163 270
385 931 180
319 451 180
913 66 0
-210 288 90
213 238 90
-60 ...

output:

118598

result:

ok single line: '118598'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

50 165 111 321
-552 -21 180
-472 8 0
-455 57 90
-518 -18 0
-535 -59 270
-394 51 0
-385 -15 180
-402 44 0
-375 -56 0
-460 -55 0
-416 16 90
-328 -83 180
-382 53 90
-421 -60 270
-359 59 180
-250 -25 180
-238 34 270
-324 -55 270
-276 34 90
-307 19 180
-267 -45 90
-145 -53 90
-244 -35 0
-206 -43 180
-161...

output:

99531

result:

ok single line: '99531'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

50 322 111 321
-324 -245 0
-380 -226 0
-188 -345 270
-290 -260 90
-303 -412 90
-255 -358 90
-266 -291 180
-368 -257 90
-418 -214 180
-247 -330 90
271 -141 90
425 -147 270
184 -462 0
330 -164 270
220 -362 0
227 -221 0
291 -360 180
323 -265 0
316 -205 270
413 -221 180
-262 275 90
-177 190 270
-404 347...

output:

60882

result:

ok single line: '60882'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

50 322 111 321
-301 -328 180
-264 -187 0
-316 -191 180
-272 -320 180
-255 -407 270
-293 -368 180
-196 -226 0
-320 -366 0
-355 -360 90
-228 -287 90
280 -259 90
139 -249 270
197 -147 270
207 -350 90
186 -451 180
449 -172 270
464 -165 180
235 -386 0
184 -356 270
297 -194 270
-342 193 0
-365 434 270
-18...

output:

60312

result:

ok single line: '60312'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

50 100 123 565
128 136 180
-13 -6 180
91 -54 0
112 6 90
42 67 270
-128 26 270
-135 -56 90
139 123 180
-146 27 180
-69 -47 180
-3 -73 90
-125 145 90
-52 132 90
-90 97 180
55 -47 0
-73 92 180
-23 78 0
60 -113 180
120 28 0
79 -24 270
1 106 270
138 36 270
19 62 90
-139 -123 270
-76 -33 180
133 63 180
-6...

output:

75068

result:

ok single line: '75068'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

50 100 123 565
151 -17 270
43 -70 270
190 -159 90
199 -20 0
-84 107 270
169 111 90
-48 92 270
-40 -9 180
199 -40 270
103 -107 90
-95 -12 90
-194 -56 0
-56 -108 90
-83 156 90
-51 193 0
2 178 180
7 -197 90
-111 111 0
-14 42 270
27 -153 0
-144 58 90
-77 -55 90
179 0 180
19 -95 90
125 -96 0
-53 127 270
...

output:

46805

result:

ok single line: '46805'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

50 100 123 565
621 538 0
-495 901 0
868 97 270
-761 548 90
818 544 180
702 -408 90
-807 779 270
802 314 0
-30 962 90
858 367 270
-700 896 180
329 508 180
119 -283 180
205 169 0
201 573 0
630 -237 270
-374 447 180
-481 153 90
753 -805 90
-711 -492 0
498 524 270
641 -174 180
-948 -339 0
-985 905 270
2...

output:

28250

result:

ok single line: '28250'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

50 500 1000 1000
911 274 90
-352 -480 0
-376 597 180
-746 -484 270
466 174 0
738 340 0
724 -742 180
794 914 180
299 -804 180
917 1 90
-428 -444 90
-60 -373 0
804 896 270
-458 717 90
-266 -537 0
-141 879 0
107 616 0
234 -891 0
208 -55 180
-193 325 180
740 520 90
445 987 270
-70 920 180
269 668 0
367 ...

output:

373000

result:

ok single line: '373000'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

50 69 453 998
-459 -10 0
-423 -13 270
-463 -13 180
-527 74 180
-450 -3 270
-486 -30 90
-447 49 90
-471 -15 0
-427 31 0
-488 -67 270
-433 -28 90
-322 -8 90
-418 44 0
-315 47 180
-419 -41 0
-256 22 270
-244 62 180
-217 -68 180
-254 28 270
-287 60 180
-226 64 0
-239 78 270
-210 -35 0
-279 -28 270
-227 ...

output:

123244

result:

ok single line: '123244'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

50 143 1 2
-480 18 0
-491 -11 90
-512 19 90
-460 18 180
-450 6 90
-457 2 90
-395 -6 90
-402 -3 0
-394 -14 180
-336 -5 270
-353 10 90
-364 0 270
-302 9 0
-300 19 270
-287 18 90
-240 19 90
-247 18 0
-246 8 180
-181 3 90
-200 -9 90
-183 -4 0
-162 12 0
-147 -18 270
-170 10 90
-103 -11 270
-83 3 90
-90 -...

output:

704

result:

ok single line: '704'

Test #36:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

50 1000 1000 1000
236 55 0
64 -158 0
-123 129 0
200 -211 0
-75 224 0
-173 -16 0
241 -82 0
-192 -192 0
37 -34 0
125 80 0
216 -203 0
-195 -97 0
14 168 0
-184 73 0
136 -147 0
-148 -170 0
-137 203 0
250 -107 0
173 -161 0
75 250 0
70 -96 0
49 -188 0
227 -19 0
180 -33 0
55 214 0
-182 -183 0
-66 -205 0
231...

output:

2500000

result:

ok single line: '2500000'

Test #37:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

50 1000 1000 690
250 230 0
21 -161 90
-161 -446 0
-482 -321 0
-37 294 0
-155 375 270
108 429 180
-469 97 270
0 -336 180
77 -450 180
493 -262 270
114 -233 180
365 36 180
230 251 270
54 -188 90
-290 -288 0
-282 -314 270
240 70 90
471 -10 0
-246 181 0
-444 -442 90
-188 -12 270
477 197 90
-321 118 180
3...

output:

2400760

result:

ok single line: '2400760'

Test #38:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

50 1000 1000 1000
-143 7 0
195 -181 0
115 75 0
-62 178 0
-6 -204 0
-149 127 0
-228 95 0
-89 184 0
67 -198 0
-109 -97 0
243 97 0
-200 -239 0
73 117 0
23 179 0
-249 -23 0
171 -33 0
-46 -111 0
7 -248 0
113 -157 0
112 240 0
-193 -117 0
233 232 0
185 -66 0
193 -101 0
76 -174 0
-106 201 90
102 244 90
137 ...

output:

2471000

result:

ok single line: '2471000'

Test #39:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

50 1000 1000 1000
35 -168 0
133 -21 0
-126 183 0
-214 101 0
180 174 0
107 -136 0
136 115 0
-165 210 0
-14 -110 0
-22 96 0
2 -50 0
210 -105 0
246 235 0
-235 -76 0
-158 -196 0
171 -56 0
-207 -26 0
238 126 0
102 225 0
-245 159 0
99 216 0
-96 -12 0
1 110 0
-181 -96 0
52 -216 0
-144 -67 0
-109 99 0
98 -1...

output:

2498000

result:

ok single line: '2498000'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1 1000 1000 1000
0 0 0

output:

1000

result:

ok single line: '1000'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

50 123 1000 44
0 -216 0
0 471 270
0 218 270
0 111 270
0 195 270
0 -62 180
0 -127 270
0 436 90
0 -168 270
0 -459 90
0 -99 270
0 291 90
0 149 180
0 463 90
0 -394 90
0 412 180
0 -131 270
0 -26 0
0 -72 90
0 -384 180
0 -252 90
0 243 180
0 -477 270
0 -366 270
0 -475 180
358 0 0
117 0 270
-330 0 270
269 0 ...

output:

45760

result:

ok single line: '45760'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

50 123 1000 526
0 68 0
0 -361 0
0 305 180
0 459 270
0 -154 90
0 -207 180
0 -419 180
0 165 180
0 -364 270
0 -15 90
0 -402 270
0 -466 270
0 368 90
0 -163 90
0 376 270
0 -383 0
0 -262 0
0 402 90
0 9 180
0 108 270
0 -462 270
0 -372 0
0 -445 0
0 405 0
0 -366 270
350 0 90
-149 0 270
301 0 0
-135 0 180
-23...

output:

73566

result:

ok single line: '73566'

Test #43:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

50 1000 1 1000
174 -215 270
46 -347 270
345 -177 270
198 364 90
150 -86 180
279 -404 270
-91 352 270
-334 45 180
136 329 0
-300 -422 0
-423 123 0
103 -316 90
-103 -192 90
-185 -189 270
345 -430 180
464 -407 0
-482 112 90
457 -364 90
110 -111 180
134 -20 270
-490 453 270
-352 178 0
-72 -415 270
405 2...

output:

49948

result:

ok single line: '49948'

Test #44:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

50 1000 1000 1
172 -92 0
51 -355 90
-79 -46 90
393 418 270
327 -117 0
-118 282 270
431 -76 270
299 66 90
337 -300 270
-252 -66 90
-8 -158 0
-445 -139 180
1 181 270
-7 34 0
-262 344 270
165 -169 0
99 479 270
-225 -331 0
-13 289 180
-101 -63 180
471 -424 0
298 -460 90
315 -252 270
194 -152 90
-388 -23...

output:

2398006

result:

ok single line: '2398006'

Test #45:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

50 1000 1 1000
-93 -23 0
-168 -12 0
-41 -136 0
-193 -31 0
-185 -28 0
-30 -79 0
-131 -87 0
-3 -85 0
-153 -140 0
-20 -76 0
-85 -152 0
-121 -165 0
-46 -117 0
-32 -59 0
-105 -7 0
-65 -71 0
-60 -172 0
-140 -168 0
-182 -182 0
-122 -162 0
-86 -120 0
0 -88 0
-48 -38 0
-134 -138 0
-117 -81 0
123 134 180
261 ...

output:

49950

result:

ok single line: '49950'

Test #46:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

50 1000 1000 1
-23 -69 0
-88 -139 0
-116 -198 0
-174 -158 0
-77 -60 0
-137 -84 0
-54 -145 0
-4 -113 0
-163 -68 0
-193 -175 0
-160 -114 0
-87 -117 0
-126 -96 0
-161 -127 0
-200 -187 0
-192 -193 0
-53 -116 0
-6 -20 0
-186 -166 0
-40 -14 0
-195 -167 0
-105 -54 0
-80 -148 0
-120 -154 0
-72 -121 0
204 25...

output:

2450000

result:

ok single line: '2450000'

Test #47:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

50 100 1 1000
-578 -560 270
-482 -550 0
-547 -406 270
-563 -583 90
-461 -408 0
-595 -418 180
-579 -411 270
-571 -493 0
-485 -512 90
-428 -494 0
602 551 270
494 557 90
668 560 180
595 481 90
365 300 0
445 566 0
424 324 90
456 580 90
541 669 180
583 691 0
458 655 90
300 660 180
677 414 270
661 681 270...

output:

50014

result:

ok single line: '50014'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3736kb

input:

50 1000 234 123
-356 -295 0
-376 -12 90
441 222 0
247 266 180
404 -408 0
250 -417 180
85 232 0
-291 462 90
-259 -213 180
-437 -400 0
430 56 0
333 170 270
-218 485 180
-319 86 0
-14 12 180
288 478 270
-162 107 0
450 379 90
216 442 270
131 -14 180
-2 375 90
349 345 0
274 118 0
-153 475 270
281 -352 27...

output:

561057

result:

ok single line: '561057'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

50 100 1000 1
-467 -524 180
-450 -540 180
-528 -466 90
-541 -517 0
-546 -453 90
-521 -464 270
-478 -519 90
-454 -534 0
-514 -451 90
-515 -495 90
-433 505 0
-630 411 90
-698 675 0
-660 557 270
-333 468 180
-593 535 0
-536 422 90
-351 443 0
-695 390 180
-300 424 180
591 637 90
660 659 270
770 773 90
6...

output:

154022

result:

ok single line: '154022'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3720kb

input:

50 1000 1000 1000
-83 -476 90
367 49 90
706 391 90
-240 -133 270
19 -638 270
-887 -828 180
-587 394 270
555 695 180
-644 -481 90
175 -861 0
784 -455 90
-606 -733 270
851 -80 0
600 431 90
-61 -847 180
-387 766 90
-171 155 270
291 -652 90
568 -930 90
20 113 0
-713 72 180
-445 299 180
-349 -743 90
913 ...

output:

1139000

result:

ok single line: '1139000'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

50 100 1 2
-478 -580 270
-426 -581 0
-589 -509 90
-554 -583 0
-432 -477 0
-597 -496 180
-470 -514 0
-550 -491 0
-484 -556 90
-574 -446 90
496 304 0
548 693 0
450 690 270
464 318 90
633 365 180
496 623 180
447 696 0
614 425 270
328 415 0
565 574 90
554 398 180
507 671 270
499 470 180
415 471 270
596 ...

output:

338

result:

ok single line: '338'

Test #52:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

50 100 200 500
-537 -453 270
-505 -479 180
-489 -543 90
-535 -483 90
-480 -508 0
-489 -512 0
-454 -512 270
-453 -543 0
-452 -495 90
-491 -536 90
-614 659 90
-479 532 270
-591 408 90
-539 689 0
-344 399 180
-576 584 90
-342 449 180
-400 310 180
-568 433 270
-355 687 0
741 229 90
468 398 270
507 262 9...

output:

43300

result:

ok single line: '43300'

Test #53:

score: 0
Accepted
time: 1ms
memory: 3936kb

input:

50 165 127 256
-507 -68 0
-515 55 180
-435 21 270
-480 63 90
-516 -61 270
-368 7 180
-450 0 270
-423 7 0
-400 71 270
-352 -36 0
-424 70 0
-414 -66 90
-402 -19 270
-393 10 270
-347 -57 270
-299 16 0
-276 68 0
-263 -59 90
-269 -10 0
-257 -23 270
-157 -42 0
-293 -11 180
-224 -73 270
-180 -53 90
-272 66...

output:

115320

result:

ok single line: '115320'