Submission #1217816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217816		asdfghqwert	Trains (BOI24_trains)	C++20	16 / 100	113 ms	144300 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
typedef long long ll;

const int T = 350;
const int MOD = 1e9 + 7;

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

    int n; cin >> n;
    vector<pair<int , int >> se(n + 1);
    for(int i = 1 ; i <= n ; i++){
        cin >> se[i].first >> se[i].second;
    }
    vector<vector<int>> a(n + 2 * T + 1 ,vector<int>(T + 1));
    vector<int> dp(n + 2 *T + 1);
    for(int i = n ;i >= 1 ; i--){
        if(se[i].first == 0)dp[i] = 1;
        else{
            if(se[i].first <= T){
                dp[i] = a[i + se[i].first][se[i].first] + 1;
                if(i + se[i].first * (se[i].second + 1) <= n)
                    dp[i] = (dp[i] - a[i + se[i].first * (se[i].second + 1)][se[i].first] + MOD ) % MOD;
            }
            else{
                dp[i] = 1;
                for(int j = i + se[i].first; j <= min(n , i + se[i].first * se[i].second) ; j += se[i].first){
                    dp[i] = (dp[i] + dp[j]) % MOD;
                }
            }
        }
        for(int j = 1 ; j <= T ; j++){
            a[i][j] = (a[i + j][j] + dp[i]) % MOD;
        }
    }
    cout << dp[1] << '\n';
}

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