oj.uz

Submission #141238

# Submission time Handle Problem Language Result Execution time Memory
141238 2019-08-07T07:25:53 Z imsifile Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 65240 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){
	int mx=0;
	for(int i=cvx.size(); --i;){
		if(cvx[mx].x*A + cvx[mx].y*B < cvx[i].x*A + cvx[i].y*B) mx=i;
	}
	return mx;
}

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 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 287 ms 22688 KB Output is correct
4 Correct 283 ms 22704 KB Output is correct
5 Correct 19 ms 4204 KB Output is correct
6 Correct 341 ms 65092 KB Output is correct
7 Correct 331 ms 65092 KB Output is correct
8 Correct 337 ms 65240 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 554 ms 25016 KB Output is correct
4 Correct 573 ms 24968 KB Output is correct
5 Correct 2023 ms 2860 KB Output is correct
6 Execution timed out 3058 ms 45308 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 348 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 287 ms 22688 KB Output is correct
4 Correct 283 ms 22704 KB Output is correct
5 Correct 19 ms 4204 KB Output is correct
6 Correct 341 ms 65092 KB Output is correct
7 Correct 331 ms 65092 KB Output is correct
8 Correct 337 ms 65240 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 554 ms 25016 KB Output is correct
12 Correct 573 ms 24968 KB Output is correct
13 Correct 2023 ms 2860 KB Output is correct
14 Execution timed out 3058 ms 45308 KB Time limit exceeded
15 Halted 0 ms 0 KB -