题解

题意：

• 有 $3$ 道题，每题按过题人数决定分值（$500,1000,\dots,3000$）。
• 你可以 hack 某些人：每 hack 一次加 $100$ 分。
• 每个人某题得分形如：

$$score_i=\frac{x_i(250-t_i)}{250}$$

求最终排名的最小可能值。

思路要点：

• 总分最大 $9000$，因此 hack 次数最多 $90$；
• 能被 hack 的人数量也至多 $90$。
• 先枚举每道题的分值（等价于确定每题可 hack 人数），复杂度 $O(7^3)$；
• 确定后“hack 越多越好”，你的分数可直接计算；
• 再用 $dp_{i,j,k}$ 统计每题 hack 次数固定时，你能达到的最小排名，时间复杂度约为：

$$O(30^3\cdot 90)$$

总体复杂度：

$$O(7^3\cdot 30^3\cdot 90)$$

//
// Created by EDY on 2025/12/11.
//
#include<bits/stdc++.h>
using namespace std;
const int N = 5050;
vector<int> ti_A(N , 0) , ti_B(N , 0) , ti_C(N , 0);
int lim_A = 0 , lim_B = 0 , lim_C = 0;
int cnt_A = 0 , cnt_B = 0 , cnt_C = 0;
int dp[91][91][91][2];
int n;
int ans;
vector<int>t(6);
void solve(int X , int Y , int Z , int lim_x , int lim_y , int lim_z) {
    //第一题分数 ， 第二题分数 ， 第三题分数 ， 第一题hack人数 ， 第二题hack人数 ， 第三题hack人数
    int my_score = (lim_x + lim_y + lim_z) * 100;
    if (ti_A[1] != 0)
        my_score += X * (250 - ti_A[1]) / 250;
    if (ti_B[1] != 0)
        my_score += Y * (250 - ti_B[1]) / 250;
    if (ti_C[1] != 0)
        my_score += Z * (250 - ti_C[1]) / 250;
 //  cout << X << " " << Y << " " << Z << " " << my_score << " " << lim_x << " " << lim_y << " " << lim_z << endl;
    memset(dp , 0 , sizeof(dp));
    //能超过的人数
    int cnt = 0;
    int move = 0;
    for (int i = 2 ; i <= n ; i ++) {
        if (ti_A[i] >= 0 && ti_B[i] >= 0 && ti_C[i] >= 0) {
            move++;
            int score = 0;
            if (ti_A[i] != 0) {
                score += X * (250 - abs(ti_A[i])) / 250;
            }
            if (ti_B[i] != 0) {
                score += Y * (250 - abs(ti_B[i])) / 250;
            }
            if (ti_C[i] != 0) {
                score += Z * (250 - abs(ti_C[i])) / 250;
            }
            cnt += my_score >= score;
            continue;
        }
        for (int x = 0 ; x < 2 ; x ++) {
            if (x == 1 && ti_A[i] >= 0) continue;
            for (int y = 0 ; y < 2 ; y ++) {
                if (y == 1 && ti_B[i] >= 0) continue;
                for (int z = 0 ; z < 2 ; z ++) {
                    if (z == 1 && ti_C[i] >= 0) continue;
                    for (int j = max(0 , x) ; j <= min(i - 1 , lim_x) ; j ++) {
                        for (int k = max(0 , y) ; k <= min(i - 1 , lim_y) ; k ++) {
                            for (int l = max(0 , z) ; l <= min(i - 1 , lim_z) ; l ++) {
                                int score = 0;
                                if (x == 0 && ti_A[i] != 0) {
                                    score += X * (250 - abs(ti_A[i])) / 250;
                                }
                                if (y == 0 && ti_B[i] != 0) {
                                    score += Y * (250 - abs(ti_B[i])) / 250;
                                }
                                if (z == 0 && ti_C[i] != 0) {
                                    score += Z * (250 - abs(ti_C[i])) / 250;
                                }
                         //       cout << score << endl;
                                dp[j][k][l][(i - move)%2] = max(dp[j][k][l][(i - move)%2] , dp[j - x][k - y][l - z][(i-move-1)%2] + (my_score >= score));
                            }
                        }
                    }
                }
            }
        }
    }
    ans = min(ans , n -dp[lim_x][lim_y][lim_z][(n - move) % 2] - cnt);
}
void dfs(int x) {
    if (x == 4) {
        if (ans == 1) {
            return;
        }
        //每个地方最多删这么多人
        int mx_A = (n >> t[1]) + 1;//最多能够删多少人
        if (t[1] == 0) {
            if (lim_A == cnt_A)
                mx_A = 0;
            else
                return;
        }
        int li_A = min(lim_A , (cnt_A - mx_A));
        int mx_B = (n >> t[2]) + 1;
        if (t[2] == 0) {
            if (lim_B == cnt_B)
                mx_B = 0;
            else
                return;
        }
        int li_B = min(lim_B , (cnt_B - mx_B));
        int mx_C = (n >> t[3]) + 1;
        if (t[3] == 0) {
            if (lim_C == cnt_C)
                mx_C = 0;
            else
                return;
        }
        int li_C = min(lim_C , (cnt_C - mx_C));
        if (li_A < 0 || li_B < 0 || li_C < 0) {
            return;
        }
        if ((n >= ((cnt_A - li_A) << t[1]) && (cnt_A - li_A != 0)) || (n >= ((cnt_B - li_B) << t[2]) && (cnt_B - li_B != 0)) || (n >= ((cnt_C - li_C) << t[3]) && (cnt_C - li_C != 0)) || (lim_A < 0 || lim_B < 0 || lim_C < 0)
            || 2 * n < ((cnt_A - li_A) << t[1]) || 2 * n < ((cnt_B - li_B) << t[2]) || 2 * n < ((cnt_C - li_C) << t[3])) {
            return;
        }
        solve(t[1] * 500 , t[2] * 500 , t[3] * 500 , li_A , li_B , li_C);
        return;
    }
    for (int j = 0 ; j <= 6 ; j ++) {
        t[x] = j;
        dfs(x + 1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    cin >> n;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> ti_A[i] >> ti_B[i] >> ti_C[i];
        cnt_A += (ti_A[i] != 0);
        cnt_B += (ti_B[i] != 0);
        cnt_C += (ti_C[i] != 0);
        lim_A += (ti_A[i] < 0);
        lim_B += (ti_B[i] < 0);
        lim_C += (ti_C[i] < 0);
    }
    ans = n;
    if (lim_A + lim_B + lim_C >= 90) {
        ans = 1;
        cout << ans;
        return 0;
    }
    dfs(1);
    cout << ans << endl;
}