제출 #1260541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260541		kikitop1gg	Trains (BOI24_trains)	C++17	100 / 100	706 ms	252604 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define vpp vector<pair<ll, pair<ll, ll>>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define sc set<char>
#define mod 1000000007
#define inf INT_MAX
#define all(x) (x).begin(), (x).end()

int main() {
    ifstream in("input.txt");
    ofstream out("output.txt");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    vi d(n), x(n);
    ll limit = sqrt(n);
    si ds;
    for(int i = 0; i < n; i++) {
        cin >> d[i] >> x[i];
        if(d[i] <= limit && d[i] != 0) {
            ds.insert(d[i]);
        }
    }
    vi val(n, 0);
    vvi m(limit + 1, vi(n, 0));

    for(int i = n - 1; i >= 0; i--) {
        if(d[i] > limit) {
            for(int j = i + d[i]; j < min(n, i + d[i] * (x[i] + 1)); j += d[i]) {
                val[i] += val[j];
                val[i] %= mod;
            }
            val[i]++;
            val[i] %= mod;
        }
        else if(d[i] == 0) {
            val[i] = 1;
        }
        else {
            ll left = 0, right = 0;
            if(i + d[i] < n) left = m[d[i]][i + d[i]];
            ll rightInd = i + d[i] * (x[i] + 1);
            if(rightInd < n) right = m[d[i]][rightInd];
            val[i] = (1 + left - right + mod) % mod;
        }

        for(auto x : ds) {
            ll right = 0;
            if(i + x < n) right = m[x][i + x];
            m[x][i] = (val[i] + right) % mod;
        }
    }

    cout << val[0] << '\n';
    return 0;
}
/*
5
1 3
1 1
1 3
1 10
1 5

12
*/

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