[ICPC2024 Xi'an I] Make Them Straight

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n;
int a[MAXN + 5], b[MAXN + 5];
// f[首项、公差]：不用改的部分的 b 之和
map<pair<int, int>, long long> f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    long long sum = 0;
    for (int i = 1; i <= n; i++)
        sum += b[i];

    for (int d = 0; d <= 1000000; d++) // 公差
    {
        for (int i = 1; i <= n; i++)
        {
            // 如果 0 为首项都会超过 a[i] 就不用看后面的了
            if (0 + (i - 1) * d > 1000000)
                break;
            // 如果 a[i] 命中了的话的首项
            long long a1 = a[i] - (long long)(i - 1) * d;
            if (a1 < 0)
                continue;
            // 如果 a1 为首项，d 为公差，就不用修改 b[i]
            f[make_pair(a1, d)] += b[i];
        }
    }

    long long ans = sum;
    for (auto x : f)
        ans = min(ans, sum - x.second);
    cout << ans;

    return 0;
}