钓鱼1

70 分

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100;
int n, T;
int x[MAXN + 5], a[MAXN + 5], b[MAXN + 5];
priority_queue<pair<int, int>> q;
int cal(int pos, int tt)
{
    while (!q.empty())
        q.pop();
    for (int i = 1; i <= pos; i++)
        q.push(make_pair(a[i], b[i]));
    int now = 0;
    while (tt >= 5)
    {
        auto ab = q.top();
        q.pop();
        q.push(make_pair(ab.first - ab.second, ab.second));
        now += max(ab.first, 0LL);
        tt -= 5;
    }
    return now;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> T;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    // 枚举走到了第几个钓鱼点
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (x[i] * 2 > T)
            continue;
        ans = max(ans, cal(i, T - x[i] * 2));
    }
    cout << ans;
    return 0;
}

100 分

写法 1

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, T;
int x[105];
int a[105], b[105];
// x[1]~x[R] 中所有超过了 mid 条的钓鱼点，能不能再 t 次以内被钓完
int check(int mid, int t, int R)
{
    int cnt = 0; // 记录一共有多少次超过 mid 条的钓鱼点
    for (int i = 1; i <= R; i++)
    {
        if (a[i] <= mid)
            continue;
        if (b[i] == 0)
            return false;                     // 此时超过 mid 的钓鱼点有无限次
        cnt += (a[i] - (mid + 1)) / b[i] + 1; // a[i]-(cnt-1)b[i]>=mid+1
    }
    return cnt <= t;
}
// 能在 x[1]~x[R] 钓鱼，还能钓鱼 t 次
// 返回能钓多少条
int cal(int t, int R)
{
    // 1. 二分找到 siz，使得超过 siz 条的钓鱼点都能被钓完，剩余的钓鱼次数钓的必然都是 siz 条
    int l = 0;
    int r = 1'000'000'000;
    int siz;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid, t, R))
        {
            siz = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    // 2. 根据 siz 算出一共钓了多少条鱼
    int sum1 = 0; // 记录超过 siz 的点一共钓了多少条
    int cnt1 = 0; // 记录超过 siz 的点一共钓了多少次（必然不是无限次）
    int cnt2 = 0; // 等于 siz 的点一共有多少次（t-cnt1 次都会在这里消耗）
    for (int i = 1; i <= R; i++)
    {
        if (a[i] < siz)
            continue;
        if (a[i] == siz)
        {
            if (b[i] == 0)
                cnt2 = t + 1; // 等于siz的能有无限次
            else
                cnt2++;
        }
        if (a[i] > siz)
        {
            // 当前的项数
            int num = (a[i] - (siz + 1)) / b[i] + 1; // a[i]-(cnt1-1)b[i]>=siz+1
            cnt1 += num;
            // 首项为 a[i]，项数为 num -b[i]
            sum1 += (a[i] + (a[i] - (num - 1) * b[i])) * num / 2;
            if ((a[i] - siz) % b[i] == 0)
                cnt2++;
        }
    }
    // 大于 siz 的所有条数之和 + siz * 等于 siz 条的次数
    return sum1 + siz * min(t - cnt1, cnt2);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> T;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    // 记录最终答案
    int ans = 0;
    // 枚举右边界，最右能走到 x[R]
    for (int R = 1; R <= n; R++)
    {
        // 还能钓鱼的次数
        int t = (T - x[R] * 2) / 5;
        int now = cal(t, R);
        ans = max(now, ans);
    }

    cout << ans;
    return 0;
}

写法 2

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100;
int n, T;
int x[MAXN + 5], a[MAXN + 5], b[MAXN + 5];
priority_queue<pair<int, int>> q;
// siz 及以上数量的次数都钓完，时间够不够
bool calTime(int pos, int siz, int tt)
{
    int cnt = 0;
    for (int i = 1; i <= pos; i++)
    {
        if (a[i] < siz)
            continue;
        cnt += (a[i] - siz) / b[i] + 1;
    }
    return cnt * 5 <= tt;
}
// 1~pos 在 tt 的时间最多钓多少条
int cal(int pos, int tt)
{
    int minSiz = 0; // minSiz 大小的鱼可以无限钓
    for (int i = 1; i <= pos; i++)
        if (b[i] == 0)
            minSiz = max(minSiz, a[i]);

    int siz = -1; // 时间够把所有 now 条以上的次数都抓完
    int l = minSiz + 1;
    int r = 1'000'000'000;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (calTime(pos, mid, tt))
        {
            siz = mid;
            // mid 数量的都能搞完，就看看更小的全搞完时间行不行
            r = mid - 1;
        }
        else
        {
            // mid 数量的搞不完，那就看看多大的能搞完
            l = mid + 1;
        }
    }

    int now = 0; // 总鱼数
    int ttt = 0; // 总时间
    for (int i = 1; i <= pos; i++)
    {
        if (a[i] >= siz)
        {
            int num = (a[i] - siz) / b[i] + 1; // 项数
            int s = a[i];                      // 第一次
            int e = a[i] - b[i] * (num - 1);   // 最后一次
            now += (s + e) * num / 2;
            ttt += num * 5;
        }
    }
    // 多余时间不停钓 minSiz 大小的鱼
    return now + (tt - ttt) / 5 * minSiz;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> T;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    // 枚举走到了第几个钓鱼点
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (x[i] * 2 > T)
            continue;
        ans = max(ans, cal(i, T - x[i] * 2));
    }
    cout << ans;
    return 0;
}