제출 #151463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151463		edenooo	최적의 팀 구성 (FXCUP4_squad)	C++17	0 / 100	321 ms	67076 KiB

squad

#include "squad.h"
#include<algorithm>
#include<stdio.h>
using namespace std;

#define INF 1234567890
#define ll long long

struct Line {
	ll a, b;
	double s;
	int idx;

	Line(ll ta, ll tb, double ts, int tidx) { a = ta; b = tb; s = ts; idx = tidx; }
	bool operator< (const Line &n) const
	{
		if (a != n.a) return a < n.a;
		return b > n.b;
	}
};

int N;
vector<Line> v, re;

double Cross(Line &A, Line &B)
{
	return (double)(B.b - A.b) / (A.a - B.a);
}

struct CHT {
	vector<Line> cht;
	void insert(Line &n)
	{
		while (!cht.empty())
		{
			if (cht.back().a == n.a)
			{
				if (cht.back().b < n.b)
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else return;
			}
			else
			{
				n.s = Cross(cht.back(), n);
				if (n.s < cht.back().s)
				{
					re.push_back(cht.back());
					cht.pop_back();
				}
				else break;
			}
		}
		cht.push_back(n);
	}
	int query(double x)
	{
		if (cht.empty()) return -1;

		int lo = 0, hi = (int)cht.size();
		for (int i = 0; i < 20; i++)
		{
			int mid = lo + hi >> 1;
			if (x < cht[mid].s) hi = mid;
			else lo = mid;
		}
		return lo;
	}
} x, xx, y, yy;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = A.size();
	for (int i = 0; i < N; i++)
		v.emplace_back(A[i], P[i], 0, i);
	sort(v.begin(), v.end());
	for (int i = 0; i < N; i++)
		x.insert(v[i]);
	sort(re.begin(), re.end());
	int M = re.size();
	for (int i = 0; i < M; i++)
		xx.insert(re[i]);
	
	v.clear(); re.clear();
	for (int i = 0; i < N; i++)
		v.emplace_back(D[i], P[i], 0, i);
	sort(v.begin(), v.end());
	for (int i = 0; i < N; i++)
		y.insert(v[i]);
	sort(re.begin(), re.end());
	M = re.size();
	for (int i = 0; i < M; i++)
		yy.insert(re[i]);
}

long long BestSquad(int X, int Y){
	double pos = (double)X / Y;
	int i = x.query(pos);
	int j = y.query(pos);
	if (x.cht[i].idx != y.cht[j].idx)
		return x.cht[i].a*X + x.cht[i].b*Y + y.cht[j].a*X + y.cht[j].b*Y;
	else
	{
		ll res = 0;
		int ii = xx.query(pos);
		if (ii != -1)
			res = max(res, xx.cht[ii].a*X + xx.cht[ii].b*Y + y.cht[j].a*X + y.cht[j].b*Y);

		int jj = yy.query(pos);
		if (jj != -1)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + yy.cht[jj].a*X + yy.cht[jj].b*Y);

		if (i - 1 >= 0)
			res = max(res, x.cht[i - 1].a*X + x.cht[i - 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		if (i + 1 < x.cht.size())
		{
			res = max(res, x.cht[i + 1].a*X + x.cht[i + 1].b*Y + y.cht[j].a*X + y.cht[j].b*Y);
		}
		if (j - 1 >= 0)
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j - 1].a*X + y.cht[j - 1].b*Y);
		if (j + 1 < y.cht.size())
			res = max(res, x.cht[i].a*X + x.cht[i].b*Y + y.cht[j + 1].a*X + y.cht[j + 1].b*Y);
		return res;
	}
	return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

squad.cpp: In member function 'int CHT::query(double)':
squad.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:116:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i + 1 < x.cht.size())
       ~~~~~~^~~~~~~~~~~~~~
squad.cpp:122:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (j + 1 < y.cht.size())
       ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53