제출 #1191468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191468		Dedibeat	Trains (BOI24_trains)	C++20	100 / 100	545 ms	280160 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int 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;
vector<vector<int>> dp2[400];
int dp[N];
void final(int n, vector<pair<int, int>> v)
{
    for(int i = 1; i * i <= n; i++)
    {
        int m = n / i;
        m += 5;
        dp2[i].assign(i + 5, vector<int>(m, 0));
    }
    auto store = [&](ll val, int idx)
    {
        val %= M;
        for(int i = 1; i * i <= n; i++)
        {
            int j = idx % i;
            int k = idx / i;
            dp2[i][j][k] = (dp2[i][j][k + 1] + val) % M;
        }
        dp[idx] = val;
    };

    auto query = [&](int d, int x, int idx)
    {
        if(d == 0 || x == 0) return 1LL;
        x = min(x, n);
        if(d * d >= n)
        {
            int sum = 0;
            for(int j = idx + d; j < n; j += d)
            {
                if(x-- == 0) break;
                sum = (sum + dp[j]) % M;
            }
            return sum + 1;
        }
        int j = idx % d;
        int k = idx / d;
        int lim = dp2[d][j].size();
        return (dp2[d][j][k + 1] - dp2[d][j][min(lim - 1, k + x + 1)] + M + 1) % M;
    };

    for(int i = n - 1; i >= 0; i--)
    {
        auto [d, x] = v[i];
        int ret = query(d, x, i);
      //  cout << d << " " << x << " " << i << " ret :" << ret << endl;
        store(ret, i);
    }

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


int t1 = 1, t2 = 1, t3 = 1;
signed 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;
    final(n, v);
}

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