oj.uz

Submission #141200

# Submission time Handle Problem Language Result Execution time Memory
141200 2019-08-07T06:15:12 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 65144 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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 284 ms 22676 KB Output is correct
4 Correct 285 ms 22604 KB Output is correct
5 Correct 19 ms 4208 KB Output is correct
6 Correct 335 ms 65076 KB Output is correct
7 Correct 327 ms 65016 KB Output is correct
8 Correct 328 ms 65144 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 527 ms 25060 KB Output is correct
4 Correct 528 ms 24992 KB Output is correct
5 Correct 505 ms 2600 KB Output is correct
6 Execution timed out 3097 ms 45436 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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 284 ms 22676 KB Output is correct
4 Correct 285 ms 22604 KB Output is correct
5 Correct 19 ms 4208 KB Output is correct
6 Correct 335 ms 65076 KB Output is correct
7 Correct 327 ms 65016 KB Output is correct
8 Correct 328 ms 65144 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 527 ms 25060 KB Output is correct
12 Correct 528 ms 24992 KB Output is correct
13 Correct 505 ms 2600 KB Output is correct
14 Execution timed out 3097 ms 45436 KB Time limit exceeded
15 Halted 0 ms 0 KB -