제출 #1191349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191349		Dedibeat	Trains (BOI24_trains)	C++20	21 / 100	2096 ms	1860 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;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    for(auto &[d, x] : v) cin >> d >> x;
    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] << " ";

}

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