Submission #1075905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075905		PanosPask	Trains (BOI24_trains)	C++14	0 / 100	79 ms	132176 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;


int CUT = 333;

int N;
vector<int> d, x;
vector<int> dp;

vector<vector<int>> pref;

void add(int& a, int b)
{
    a += b;
    if (a > MOD) {
        a -= MOD;
    }
    if (a < 0) {
        a += MOD;
    }
}

int main(void)
{
    scanf("%d", &N);

    d.resize(N);
    x.resize(N);
    dp.assign(N, 0);
    pref.assign(N, vector<int>(CUT, 0));

    for (int i = 0; i < N; i++) {
        scanf("%d %d", &d[i], &x[i]);
    }

    dp[0] = 1;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int v = 1; v < CUT && i - v >= 0; v++) {
            add(pref[i][v], pref[i - v][v]);
            add(dp[i], pref[i][v]);
        }

        add(ans, dp[i]);

        if (d[i] == 0) {
            continue;
        }

        if (d[i] < CUT && x[i] > CUT) {
            add(pref[i][d[i]], dp[i]);

            int finish = i + d[i] * x[i] + 1;
            if (finish < N) {
                add(pref[finish][d[i]], -dp[i]);
            }
        }

        int j = i;
        while (j + d[i] < N && x[i]) {
            j = j + d[i];
            x[i]--;

            add(dp[j], dp[i]);
        }
    }

    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d", &d[i], &x[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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