oj.uz

Submission #141210

# Submission time Handle Problem Language Result Execution time Memory
141210 2019-08-07T06:48:25 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 65156 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 380 KB Output is correct
3 Correct 284 ms 22692 KB Output is correct
4 Correct 284 ms 22732 KB Output is correct
5 Correct 19 ms 4204 KB Output is correct
6 Correct 323 ms 65016 KB Output is correct
7 Correct 348 ms 65156 KB Output is correct
8 Correct 363 ms 65112 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 528 ms 25004 KB Output is correct
4 Correct 529 ms 25044 KB Output is correct
5 Correct 521 ms 2516 KB Output is correct
6 Execution timed out 3047 ms 45468 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 284 ms 22692 KB Output is correct
4 Correct 284 ms 22732 KB Output is correct
5 Correct 19 ms 4204 KB Output is correct
6 Correct 323 ms 65016 KB Output is correct
7 Correct 348 ms 65156 KB Output is correct
8 Correct 363 ms 65112 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 528 ms 25004 KB Output is correct
12 Correct 529 ms 25044 KB Output is correct
13 Correct 521 ms 2516 KB Output is correct
14 Execution timed out 3047 ms 45468 KB Time limit exceeded
15 Halted 0 ms 0 KB -