Submission #1306091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306091		spetr	Trains (BOI24_trains)	C++20	100 / 100	429 ms	252500 KiB

Main

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

#define ll long long
const ll mmod = 998244353; 
const ll MMOD = 1e9 + 7; 
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

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

    ll n;
    cin >> n;
    
    vl ans (n, 0);
    ans[0] = 1;
    float B = sqrt(n);
    ll b = B;
    vll skoky (n, vl (b, 0ll));

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

        ll s = 0;
        for (ll j = 0; j < skoky[i].size(); j++){
            s += skoky[i][j];
        }

        ans[i] += s%MMOD;

        for (ll j = 0; j < skoky[i].size(); j++){
            if (i + j +1< n){
                skoky[i+j+1][j] += skoky[i][j];
                skoky[i+j+1][j] = skoky[i+j+1][j] % MMOD;
            }
            else{
                break;
            }
        }

        if (d >= b){
            for (ll j = 1; j <= x && j*d + i< n; j++){
                ans[j*d + i] += ans[i];
                ans[j*d + i] = ans[j*d+i]%MMOD;
            }
        }

        else{
            
            if (d != 0){
                if (i + (x+1)*d < n){
                    skoky[i + (x+1)*d][d-1] = (skoky[i + (x+1)*d][d-1] - ans[i] + MMOD) % MMOD;
                }

                if (i + d < n){
                    skoky[i+d][d-1] += ans[i];
                    skoky[i+d][d-1] = skoky[i+d][d-1] % MMOD;
                }
            }
        }
    }
    ll s = 0;
    for (ll i = 0; i < ans.size(); i++){
        s += ans[i] % MMOD;
    }

    cout << s % MMOD << "\n";


    return 0;
}

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