제출 #1362681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1362681		mariaclara	Trains (BOI24_trains)	C++20	42 / 100	77 ms	4180 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
typedef vector<int> vi;
const int MOD = 1e9+7;
const int MAXN = 1e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair 
#define pb push_back
#define fr first 
#define sc second

ll d[MAXN], x[MAXN];
ll dp[MAXN], sum[305][305];
vector<trio> rem[MAXN];

int main() {

    int N;
    cin >> N;

    for(int i = 1; i <= N; i++)
        cin >> d[i] >> x[i];

    ll tot = 0;
    dp[1] = 1;

    for(int i = 1; i <= N; i++) {
        for(auto [a, b, c] : rem[i])
            sum[a][b] = (sum[a][b] - c) % MOD;
        
        for(int div = 1; div <= 300; div++)
            dp[i] += sum[div][i%div];

        dp[i] %= MOD;
        tot = (tot  + dp[i]) % MOD;

        if(d[i] == 0) continue;
        if(d[i] <= 300) {
            int r = i%d[i];
            sum[d[i]][r] = (sum[d[i]][r] + dp[i]) % MOD;

            int max_pos = min(i + d[i] * x[i], (ll)N);
            rem[max_pos+1].pb({d[i], r, dp[i]});
        }
        else {
            for(int j = i+d[i], cnt = 1; j <= N and cnt < x[i]; j += d[i], cnt++)
                dp[j] = (dp[j] + dp[i]) % MOD;
        }
    }

    cout << tot << "\n";
}

• 서브태스크 1: 8 / 8
• 서브태스크 2: 0 / 13
• 서브태스크 3: 0 / 16
• 서브태스크 4: 34 / 34
• 서브태스크 5: 0 / 29