제출 #1257207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257207		fv3	Trains (BOI24_trains)	C++20	100 / 100	510 ms	252488 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll N; cin >> N;
    const ll sqrtN = sqrt(N);

    // DP forward or backwards?
    // d[i] > sqrtN - DP forward

    ll res = 0;
    vector<vector<ll>> fw(N, vector<ll>(sqrtN + 1));
    vector<ll> DP(N);

    DP[0] = 1;

    for (ll i = 0; i < N; i++)
    {
        ll d, x;
        cin >> d >> x;

        for (int j = 1; j <= sqrtN; j++)
        {
            DP[i] = (DP[i] + fw[i][j]) % mod;
        }

        for (int j = 1; j <= sqrtN; j++)
        {
            if (i + j >= N)
                break;
            fw[i+j][j] = (fw[i+j][j] + fw[i][j]) % mod;
        }

        res = (res + DP[i]) % mod;

        if (d > sqrtN)
        {
            ll next = i + d;
            int t = 0;
            while (next <= N-1ll && t < x)
            {
                DP[next] = (DP[next] + DP[i]) % mod;
                next += d; t++;
            }
        }
        else // d <= sqrtN
        {
            if (i + d >= N || d == 0)
                continue;

            fw[i+d][d] = (fw[i+d][d] + DP[i]) % mod;

            ll last = i + (x + 1ll) * d;

            if (last >= N)
                continue;

            fw[last][d] = (mod + fw[last][d] - DP[i]) % mod;
        }
    }

    cout << res << '\n';

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29