oj.uz

Submission #148014

# Submission time Handle Problem Language Result Execution time Memory
148014 2019-08-31T11:14:45 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1114 ms 78588 KB 
#include "squad.h"
#include <algorithm>
#include <stdio.h>
using namespace std;
 
typedef long long lld;
 
struct coord {
	lld x, y; int ix;
	bool operator< (const coord& c) const {
		if(x!=c.x) return x<c.x;
		return y<c.y;
	}
} AP[1001001], DP[1001001];
 
int N;
 
lld ccw(coord a, coord b, coord c){ // clockwise < 0
	return (a.x*b.y+b.x*c.y+c.x*a.y) - (a.y*b.x+b.y*c.x+c.y*a.x);
}
 
void makehull(coord *ba, vector<int> &chk, int val, vector<coord> &cvx){
	cvx.clear();
	for(int i=0; i<N; i++){
		int sz;
		if(chk[ba[i].ix]==val) continue;
		while(1){
			sz=cvx.size();
			if(sz<2) break;
			if(ccw(cvx[sz-2], cvx[sz-1], ba[i]) < 0) break;
			cvx.pop_back();
		}
		cvx.push_back(ba[i]);
	}
}
 
void threehull(coord *ba, vector<coord> &cvx, vector<coord> &odd, vector<coord> &even){
	vector<int> chk(N,0);
	sort(ba, ba+N);
	makehull(ba, chk, 1, cvx);
	for(int i=cvx.size(); i--;){
		if(i%2) chk[cvx[i].ix]=1;
		else chk[cvx[i].ix]=2;
	}
	makehull(ba, chk, 1, odd);
	makehull(ba, chk, 2, even);
}
 
vector<coord> Acv, Aov, Aev, Dcv, Dov, Dev;
 
void Init(vector<int> A, vector<int> D, vector<int> P){
	N=A.size();
	for(int i=0; i<N; i++){
		AP[i].ix=i, AP[i].x=A[i], AP[i].y=P[i];
		DP[i].ix=i, DP[i].x=D[i], DP[i].y=P[i];
	}
	threehull(AP, Acv, Aov, Aev);
	threehull(DP, Dcv, Dov, Dev);
}
 
int getfirst(lld A, lld B, vector<coord> &cvx){
	if(cvx.size() == 1) return 0;
	int mi=0, mx=cvx.size()-2, md;
	while(mi<=mx){
		md=(mi+mx)/2;
		if(cvx[md].x*A + cvx[md].y*B < cvx[md+1].x*A + cvx[md+1].y*B) mi=md+1;
		else mx=md-1;
	}
	return mi;
}
 
coord A1, A2, D1, D2;
 
lld BestSquad(int X, int Y){
	int ix;
	ix=getfirst(X, Y, Acv), A1=Acv[ix];
	if(ix%2) ix=getfirst(X, Y, Aov), A2=Aov[ix];
	else ix=getfirst(X, Y, Aev), A2=Aev[ix];
 
	ix=getfirst(X, Y, Dcv), D1=Dcv[ix];
	if(ix%2) ix=getfirst(X, Y, Dov), D2=Dov[ix];
	else ix=getfirst(X, Y, Dev), D2=Dev[ix];
 
	if(A1.ix != D1.ix) return (A1.x+D1.x)*X + (A1.y+D1.y)*Y;
	return max((A2.x+D1.x)*X + (A2.y+D1.y)*Y, (A1.x+D2.x)*X + (A1.y+D2.y)*Y);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 283 ms 31432 KB Output is correct
4 Correct 283 ms 31256 KB Output is correct
5 Correct 20 ms 4720 KB Output is correct
6 Correct 311 ms 70328 KB Output is correct
7 Correct 310 ms 70196 KB Output is correct
8 Correct 312 ms 70428 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 427 ms 37148 KB Output is correct
4 Correct 428 ms 37152 KB Output is correct
5 Correct 23 ms 2800 KB Output is correct
6 Correct 699 ms 56400 KB Output is correct
7 Correct 702 ms 56168 KB Output is correct
8 Correct 699 ms 56188 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 283 ms 31432 KB Output is correct
4 Correct 283 ms 31256 KB Output is correct
5 Correct 20 ms 4720 KB Output is correct
6 Correct 311 ms 70328 KB Output is correct
7 Correct 310 ms 70196 KB Output is correct
8 Correct 312 ms 70428 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 427 ms 37148 KB Output is correct
12 Correct 428 ms 37152 KB Output is correct
13 Correct 23 ms 2800 KB Output is correct
14 Correct 699 ms 56400 KB Output is correct
15 Correct 702 ms 56168 KB Output is correct
16 Correct 699 ms 56188 KB Output is correct
17 Correct 79 ms 5368 KB Output is correct
18 Correct 7 ms 760 KB Output is correct
19 Correct 481 ms 39600 KB Output is correct
20 Correct 474 ms 39712 KB Output is correct
21 Correct 39 ms 3832 KB Output is correct
22 Correct 1114 ms 78588 KB Output is correct
23 Correct 1058 ms 78456 KB Output is correct
24 Correct 1081 ms 78568 KB Output is correct