Submission #1033590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033590		trucmai	Trains (BOI24_trains)	C++17	8 / 100	2004 ms	7672 KiB

Main

#include <bits/stdc++.h>
#ifdef LOCAL
#include "/home/trcmai/code/tools.h"
#define debug(x...)                                                           \
    cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \
    _print(x);                                                                \
    cerr << "\e[39m" << endl;
#else
#define debug(x...)
#endif
using namespace std;
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
int n;

ll add(ll x, ll y) { return (x + y) % MOD; }
ll sub(ll x, ll y) { return (x - y % MOD + MOD) % MOD; }
ll mul(ll x, ll y) { return (x * y) % MOD; }
void upd(ll& x, ll y) { x = add(x, y); }
ll dp[N], d[N], x[N];

const int BS = 320;
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    auto solver = [&]() {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> d[i] >> x[i];
        dp[1] = 1;
        for (int i = 1; i <= n; ++i) {
            if (d[i] == 0)
                continue;
            if (x[i] <= BS)
                for (int j = i + d[i]; j <= min(int(i + x[i] * d[i]), n); j += d[i])
                    upd(dp[j], dp[i]);
        }
        vector<pair<ll, pair<ll, ll>>> v;
        for (ll i = 1; i <= n; i++) {
            for (pair<ll, pair<ll, ll>> j : v)
                if ((i - j.fi) % j.se.fi == 0 && (i - j.fi) / j.se.fi <= j.se.se) {
                    upd(dp[i], dp[j.first]);
                }
            if (d[i] && x[i] > BS)
                v.push_back({ i, { d[i], x[i] } });
        }
        ll res = 0;
        for (int i = 1; i <= n; ++i) {
            cerr << dp[i] << " \n"[i == n];
            upd(res, dp[i]);
        }
        cout << res << endl;
    };
    int t = 1; // cin>>t;
    while (t--)
        solver();
}

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