Submission #1315263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315263		LucaDantas	Trains (BOI24_trains)	C++20	100 / 100	125 ms	4980 KiB

Main

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9+7, B = 300, maxn = 1e5+10;

int add[B][B], dp[maxn];

vector<pair<int,int>> upd[maxn]; // add when adding the dp to remove it later, just save the value to remove and the periodicity

inline void add_self(int& a, int b) { a += b; a %= mod; }

int main() {
    int n; scanf("%d", &n);
    dp[0] = 1;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int d, x; scanf("%d %d", &d, &x);

        for(auto [period, value] : upd[i])
            add_self(add[period][i % period], mod - value);

        for(int k = 1; k < B; k++)
            add_self(dp[i], add[k][i % k]);

        add_self(ans, dp[i]);

        if(!d) continue;

        if(d >= B) for(int j = 1; j <= x && i + j * d < maxn; j++) // shouldn't need the 1ll* here
            add_self(dp[i + j * d], dp[i]);
        else {
            add_self(add[d][i % d], dp[i]);
            if(i + 1ll * (x + 1) * d < maxn)
                upd[i + (x + 1) * d].push_back({d, dp[i]});
        }
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:13:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     int n; scanf("%d", &n);
      |            ~~~~~^~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         int d, x; scanf("%d %d", &d, &x);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

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