제출 #1155658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155658		adiyer	Trains (BOI24_trains)	C++20	100 / 100	388 ms	159320 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define len(x) (ll) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

const int N = 1e5 + 11;
const int mod = 1e9 + 7;
const int SQ = 200;
const ll inf = 2e18 + 12;

ll n;
ll x[N], d[N], p[N], dp[N], s[N][SQ];

void add(ll &a, ll b){
    a += b, a %= mod, a += mod, a %= mod;
}

signed main(){
    cin >> n, dp[1] = 1;
    for(ll i = 1; i <= n; i++) cin >> d[i] >> x[i];
    for(ll i = 1; i <= n; i++){
        for(ll t = 1; t < SQ; t++) add(dp[i], s[i][t]);
        if(d[i] >= SQ){
            for(ll t = 1; t <= x[i] && i + t * d[i] <= n; t++) add(dp[i + t * d[i]], dp[i]);
        }
        else{
            if(d[i] && x[i]){
                add(s[i][d[i]], dp[i]);
                if(i + (x[i] + 1) * d[i] <= n)
                    add(s[i + (x[i] + 1) * d[i]][d[i]], -dp[i]);
            }
        }
        for(ll t = 1; t < SQ && i + t <= n; t++) add(s[i + t][t], s[i][t]);
    }
    for(ll i = 2; i <= n; i++) add(dp[1], dp[i]);
    cout << dp[1];
}

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