oj.uz

Submission #1052889

# Submission time Handle Problem Language Result Execution time Memory
1052889 2024-08-11T05:33:19 Z vjudge1 Trains (BOI24_trains) C++17
34 / 100
 51 ms 5276 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7, D = 100;
int n, dp[N], sm[D][D], a[N][2];
vector<int> del[N];

void add(int &x, int y){
    x += y;
    if (x < 0) x += mod;
    if (x >= mod) x -= mod;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i][0] >> a[i][1];

    dp[1] = 1;
    for (int i = 1; i <= n; i ++){
        for (int d = 1; d < D; d ++)
            add(dp[i], sm[d][i % d]);

        for (int l : del[i])
            add(sm[a[l][0]][l % a[l][0]], -dp[l]);

        if (!a[i][0]) continue;

        if (a[i][0] >= D){
            for (int j = i + a[i][0]; j <= n and a[i][1]; j += a[i][0], a[i][1]--)
                add(dp[j], dp[i]);
        }
        else{
            add(sm[a[i][0]][i % a[i][0]], dp[i]);
            long long r = 1ll * i + 1ll * a[i][0] * a[i][1];
            if (r <= n)
                del[r].push_back(i);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i ++)
        add(ans, dp[i]);
    cout << ans << endl;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 0 ms 2652 KB Output is correct
9 Incorrect 0 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 0 ms 2652 KB Output is correct
9 Incorrect 0 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 2652 KB Output is correct
5 Correct 30 ms 5276 KB Output is correct
6 Correct 43 ms 3728 KB Output is correct
7 Correct 51 ms 4224 KB Output is correct
8 Incorrect 1 ms 2648 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3200 KB Output is correct
2 Correct 22 ms 3212 KB Output is correct
3 Correct 50 ms 4068 KB Output is correct
4 Correct 35 ms 3544 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 5 ms 2904 KB Output is correct
8 Correct 51 ms 3908 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 0 ms 2652 KB Output is correct
4 Correct 0 ms 2652 KB Output is correct
5 Correct 0 ms 2652 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 0 ms 2652 KB Output is correct
9 Incorrect 0 ms 2652 KB Output isn't correct
10 Halted 0 ms 0 KB -