Submission #1191390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191390		Dedibeat	Trains (BOI24_trains)	C++20	71 / 100	188 ms	4024 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define F first
#define S second
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p)
{
    return os << "(" << p.F << "," << p.S << ")";
}
template<typename T>
void print(T v)
{
    for(auto x : v)
        cout << x << " ";
    cout << "\n";
}

const int M = 1e9 + 7;
void task1(int n, vector<pair<int, int>> v)
{
    vector<ll> dp(n, 1);
    for(int i = n - 1; i >= 0; i--)
    {
        auto [d, x] = v[i];
        if(d == 0) continue;
        for(int j = 1; j <= x; j++)
        {
            if(i + j * d >= n) break;
            dp[i] += dp[i + j * d];
            dp[i] %= M;
        }
    }
   // print(dp);
    cout << dp[0] << " ";
}

void task2(int n, vector<pair<int, int>> v)
{
    vector<ll> dp(n, 1), pref(n + 1, 0);
    ll sum = 0;
    for(int i = n - 1; i >= 0; i--)
    {
        auto [d, x] = v[i];
        if(d == 0)
        {
            pref[i] = (++sum) % M;
            continue;
        }
        dp[i] += pref[i + 1] - pref[min(n, x + i + 1)];
        dp[i] = (dp[i] + M) % M;
        sum = (sum + dp[i]) % M;
        pref[i] = sum;
    }

    cout << dp[0] << "\n";
}
const int N = 100005;
int dp2[400][N];
int dp[N];
void task3(int n, vector<pair<int, int>> v)
{
    auto store = [&](ll val, int idx)
    {
        val %= M;
        for(int i = 1; i * i <= n; i++)
        {
            const int rem = idx % i;
            dp2[i][rem] += val;
            dp2[i][rem] %= M;
        }
        dp[idx] = val;
    };
    for(int i = n - 1; i >= 0; i--)
    {
        auto [d, _] = v[i];
        if(d == 0)
        {
            store(1, i);
            continue;
        }

        if(d * d < n)
        {
            store(dp2[d][i % d] + 1, i);
        }
        else 
        {
            ll sum = 0;
            for(int j = i + d; j < n; j += d)
            {
                sum += dp[j];
            }
            store(sum + 1, i);
        }
    }

    cout << dp[0] << "\n";
}


int t1 = 1, t2 = 1, t3 = 1;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    for(auto &[d, x] : v)
    {
        cin >> d >> x;
        if(d != 1) t2 = 0;
        if(x < 1e9) t3 = 0;
    }
    if(n > 10000) t1 = 0;
    if(t1) task1(n, v);
    else if(t2) task2(n, v);
    else if(t3) task3(n, v);
}

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