# 题解害淫不浅

@xbz也能爆装备 2020-09-16 15:57 回复

QAQ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 16, MAX = 1e3;

typedef pair<int, bool> pib;
int au[MAXN], ag[MAXN], cu[MAXN];
int tot[MAXN];
pib temp[MAXN];

int n;

int ans = 0, ansx = 1, ansy = 1, ansz = 1;

inline bool Compare(pib a, pib b)
{
return a.first < b.first;
}

inline void Solve(int x, int y)
{
int num = 0, tail = 0;

for (int i = 1; i <= n; i++)
tot[i] = au[i] * x + ag[i] * y;

for (int i = 2; i <= n; i++)
{
double delta = tot[i] - tot[1], k = cu[1] - cu[i];

if (!k)
{
num += (tot[i] >= tot[1]);
continue;
}
if (k < 0 && delta > 0)
continue;
if (k > 0 && delta < 0)
{
num++;
continue;
}

if (k > 0)
temp[++tail] = make_pair(ceil(delta / k), true);
else
temp[++tail] = make_pair(floor(delta / k), false);
}

sort(temp + 1, temp + tail + 1, Compare);

for (int i = 1; i <= tail; i++)
if (!temp[i].second)
num++;

for (int i = 1; i <= tail; i++)
{
int j = i, cnt = 0;
while (temp[j + 1].first == temp[i].first && j + 1 <= tail)
j++;

for (int k = i; k <= j; k++)
if (temp[k].second)
num++;
else
cnt++;

if (num > ans && temp[i].first > 0 && temp[i].first <= y)
ans = num, ansx = x, ansy = y, ansz = temp[i].first;

i = j, num -= cnt;
}

return;
}

signed main(void)
{
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%d %d %d", au + i, ag + i, cu + i);

for (int i = 1; i <= MAX; i++)
for (int j = 1; j <= i; j++)
Solve(i, j);

printf("%d %d %d\n", ansx, ansy, ansz);

return 0;
}

4
2 5 6
9 3 2
9 9 6
3 1 7