oj.uz

답안 #141212

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141212 2019-08-07T06:50:06 Z imsifile 최적의 팀 구성 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 322 ms 22724 KB Output is correct
4 Correct 299 ms 22832 KB Output is correct
5 Correct 21 ms 4208 KB Output is correct
6 Correct 382 ms 65144 KB Output is correct
7 Correct 322 ms 65064 KB Output is correct
8 Correct 325 ms 65144 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 10 ms 552 KB Output is correct
3 Correct 530 ms 25196 KB Output is correct
4 Correct 531 ms 25044 KB Output is correct
5 Correct 498 ms 2768 KB Output is correct
6 Execution timed out 3006 ms 45452 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 322 ms 22724 KB Output is correct
4 Correct 299 ms 22832 KB Output is correct
5 Correct 21 ms 4208 KB Output is correct
6 Correct 382 ms 65144 KB Output is correct
7 Correct 322 ms 65064 KB Output is correct
8 Correct 325 ms 65144 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 10 ms 552 KB Output is correct
11 Correct 530 ms 25196 KB Output is correct
12 Correct 531 ms 25044 KB Output is correct
13 Correct 498 ms 2768 KB Output is correct
14 Execution timed out 3006 ms 45452 KB Time limit exceeded
15 Halted 0 ms 0 KB -