제출 #1332864

#제출 시각아이디문제언어결과실행 시간메모리
1332864dorkikannTrains (BOI24_trains)C++20
100 / 100
153 ms7408 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int Root = 300 + 5;

pair<int, int> Trains[N];

int DP[N];
int Helper[Root][Root];

vector<int> Events[N];

int Solve(int n)
{
    DP[0] = 1;

    int sol = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 1; j < Root; j++) {
            int idx = i % j;
            DP[i] = (DP[i] + Helper[j][idx]) % MOD;
        }

        if(Trains[i].first > 0 && Trains[i].first < Root) {
            int idx = i % Trains[i].first;
            Helper[Trains[i].first][idx] = (Helper[Trains[i].first][idx] + DP[i]) % MOD;
            int lim = i + Trains[i].first * Trains[i].second;

            if(lim < n)
                Events[lim].push_back(i);
        } else if(Trains[i].first > 0) {
            for(int j = 1; j <= Trains[i].second; j++) {
                int pos = i + j*Trains[i].first;
                if(pos >= n)
                    break;
                DP[pos] = (DP[pos] + DP[i]) % MOD;
            }
        }

        for(auto e : Events[i]) {
            int idx1 = Trains[e].first, idx2 = e % Trains[e].first;
            Helper[idx1][idx2] = ((Helper[idx1][idx2] - DP[e]) % MOD + MOD) % MOD;
        }

        sol = (sol + DP[i]) % MOD;
    }
    return sol;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> Trains[i].first >> Trains[i].second;

    cout << Solve(n) << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...