oj.uz

Submission #1075905

# Submission time Handle Problem Language Result Execution time Memory
1075905 2024-08-26T09:42:55 Z PanosPask Trains (BOI24_trains) C++14
0 / 100
 79 ms 132176 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Runtime error 0 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Runtime error 0 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 52 ms 9052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 132176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Runtime error 0 ms 348 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -