Submission #1111609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111609		kxd	Trains (BOI24_trains)	C++17	100 / 100	161 ms	13028 KiB

Main

#include <bits/stdc++.h>
//#define DEBUG 1106
#define int long long
#define ll long long
#define ld long double
#define pb emplace_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif

using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;

int d[N], x[N];
int dp[N];
vector<pair<pii,int>> v[N];
int a[311][311];

signed main() {
	INIT
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif
	///////////
	int n;
	cin >> n;
	forn1(i,n) {
		cin >> d[i] >> x[i];
	}
    int ans = 0;
    dp[1] = 1;
    forn1(i,n){
        forn1(j,310) dp[i] = (dp[i]+a[j][i%j])%MOD;
        if(d[i]<=310 && d[i]) {
            a[d[i]][i%d[i]] += dp[i];
			a[d[i]][i%d[i]] %= MOD;
            if(i+(x[i]*d[i]) <= n) {
            	v[i+(x[i]*d[i])].pb(m_p(m_p(d[i],i%d[i]),dp[i]));
			}
        } else if(d[i]) {
            for(int j = 1; i+(j*d[i])<=n && j<=x[i]; j++) {
				dp[i+(j*d[i])]=(dp[i+(j*d[i])]+dp[i])%MOD;
			}
        }
        for(auto j: v[i]) {
            a[j.ft.ft][j.ft.sd] -= j.sd;
			a[j.ft.ft][j.ft.sd] %= MOD;
            if(a[j.ft.ft][j.ft.sd] < 0) {
            	a[j.ft.ft][j.ft.sd] = (a[j.ft.ft][j.ft.sd]+MOD+MOD) %MOD;
			}
        }
        ans += dp[i];
		ans %= MOD;
    }
    cout << ans;
}

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