Submission #1106701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106701		Acanikolic	Trains (BOI24_trains)	C++14	100 / 100	103 ms	12220 KiB

Main

#include <bits/stdc++.h>

#define int long long

#define pb push_back

#define F first

#define S second

using namespace std;

const int N = 2e5 + 10;

const int mod = 1e9 + 7;

const int inf = 1e9;

const int K = 300;

int d[N],x[N],dp[N],s[K][K];

int add(int x,int y) {
    x += y;
    if(x >= mod) x -= mod;
    return x;
}

int sub(int x,int y) {
    x -= y;
    if(x < 0) x += mod;
    return x;
}

void sadd(int &x,int y) {
    x += y;
    if(x >= mod) x -= mod;
}

void ssub(int &x,int y) {
    x -= y;
    if(x < 0) x += mod;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

 	int n;
 	cin >> n;
 	dp[1] = 1;
 	for(int i = 1; i <= n; i++) cin >> d[i] >> x[i];
 	vector<array<int,3>>qs[n + 2];
 	for(int i = 1; i <= n; i++) {
        for(auto X : qs[i]) ssub(s[X[0]][X[1]],X[2]);
        for(int o = 1; o < K; o++) sadd(dp[i],s[i % o][o]);
        if(!d[i]) continue;
        if(d[i] >= K) {
            for(int j = 1; j <= x[i] && i + j * d[i] <= n; j++) {
                sadd(dp[i + j * d[i]],dp[i]);
            }
        }else {
            sadd(s[i % d[i]][d[i]],dp[i]);
            qs[min(n + 1,i + d[i] * (x[i] + 1))].pb({i % d[i],d[i],dp[i]});
        }
 	}
 	int res = 0;
 	for(int i = 1; i <= n; i++) sadd(res,dp[i]);
 	cout << res;
    return 0;
}

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