oj.uz

Submission #1052877

# Submission time Handle Problem Language Result Execution time Memory
1052877 2024-08-11T05:24:53 Z vjudge1 Trains (BOI24_trains) C++17
34 / 100
 52 ms 5208 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;
    int last = 0;
    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]][i % 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;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:20:9: warning: unused variable 'last' [-Wunused-variable]
   20 |     int last = 0;
      |         ^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2648 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 0 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 1 ms 2648 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 0 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 2776 KB Output is correct
5 Correct 30 ms 5208 KB Output is correct
6 Correct 42 ms 3932 KB Output is correct
7 Correct 50 ms 4180 KB Output is correct
8 Incorrect 0 ms 2652 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 30 ms 3160 KB Output is correct
2 Correct 20 ms 3244 KB Output is correct
3 Correct 50 ms 3920 KB Output is correct
4 Correct 36 ms 3408 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 5 ms 2836 KB Output is correct
8 Correct 52 ms 3752 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 1 ms 2648 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 0 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 -