Submission #1349391

#TimeUsernameProblemLanguageResultExecution timeMemory
1349391dodjingJobs (BOI24_jobs)C++20
0 / 100
96 ms23792 KiB
#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_map>

#define ll long long

using namespace std;

ll mod = 1000000007;

int main() {
    int n; cin >> n;
    vector <ll> d(n + 1);
    vector <ll> x(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> x[i];
    }
    vector <ll> dp(n + 1, 0);
    dp[1] = 1;
    vector <unordered_map<ll, ll>> m(n + 1);
    for (int i = 1; i <= n; i++) {
        for (auto j : m[i]) {
            dp[i] += j.second;
            dp[i] %= mod;
            if (i + j.first <= n) {
                if (m[i + j.first].count(j.first)) {
                    m[i + j.first][j.first] += j.second;
                    m[i + j.first][j.first] %= mod;
                } else {
                    m[i + j.first][j.first] = j.second;
                    m[i + j.first][j.first] %= mod;
                }
            }
        }
        if (d[i] != 0) {
            if (i + d[i] <= n) {
                if (m[i + d[i]].count(d[i])) {
                    m[i + d[i]][d[i]] += dp[i];
                    m[i + d[i]][d[i]] %= mod;
                } else {
                    m[i + d[i]][d[i]] = dp[i];
                    m[i + d[i]][d[i]] %= mod;
                }
            }
            if (i + d[i] * (x[i] + 1) <= n) {
                if (m[i + d[i] * (x[i] + 1)].count(d[i])) {
                    m[i + d[i] * (x[i] + 1)][d[i]] += -dp[i] + mod;
                    m[i + d[i] * (x[i] + 1)][d[i]] %= mod;
                } else {
                    m[i + d[i] * (x[i] + 1)][d[i]] = -dp[i] + mod;
                    m[i + d[i] * (x[i] + 1)][d[i]] %= mod;
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dp[i];
        ans %= mod;
    }
    cout << ans;
    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...