oj.uz

Submission #141257

# Submission time Handle Problem Language Result Execution time Memory
141257 2019-08-07T08:13:14 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1133 ms 64028 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(int N_, vector<int> A, vector<int> D, vector<int> P){
	N=N_;
	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 376 KB Output is correct
3 Correct 286 ms 22668 KB Output is correct
4 Correct 287 ms 22768 KB Output is correct
5 Correct 19 ms 4208 KB Output is correct
6 Correct 318 ms 61652 KB Output is correct
7 Correct 371 ms 61620 KB Output is correct
8 Correct 319 ms 61596 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 504 KB Output is correct
3 Correct 493 ms 25084 KB Output is correct
4 Correct 434 ms 25092 KB Output is correct
5 Correct 24 ms 2300 KB Output is correct
6 Correct 892 ms 43996 KB Output is correct
7 Correct 722 ms 44016 KB Output is correct
8 Correct 719 ms 44016 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 376 KB Output is correct
3 Correct 286 ms 22668 KB Output is correct
4 Correct 287 ms 22768 KB Output is correct
5 Correct 19 ms 4208 KB Output is correct
6 Correct 318 ms 61652 KB Output is correct
7 Correct 371 ms 61620 KB Output is correct
8 Correct 319 ms 61596 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 493 ms 25084 KB Output is correct
12 Correct 434 ms 25092 KB Output is correct
13 Correct 24 ms 2300 KB Output is correct
14 Correct 892 ms 43996 KB Output is correct
15 Correct 722 ms 44016 KB Output is correct
16 Correct 719 ms 44016 KB Output is correct
17 Correct 79 ms 2888 KB Output is correct
18 Correct 6 ms 636 KB Output is correct
19 Correct 477 ms 25020 KB Output is correct
20 Correct 481 ms 24992 KB Output is correct
21 Correct 37 ms 3060 KB Output is correct
22 Correct 1124 ms 63896 KB Output is correct
23 Correct 1111 ms 64028 KB Output is correct
24 Correct 1133 ms 63860 KB Output is correct