oj.uz

Submission #1011694

# Submission time Handle Problem Language Result Execution time Memory
1011694 2024-07-01T06:29:23 Z ttamx Trains (BOI24_trains) C++17
58 / 100
 131 ms 128084 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int K=320;
const int MOD=1e9+7;

int n;
int d[N],x[N];
int dp[N],add[N][K];
int ans;

void norm(int &x){
    if(x<0)x+=MOD;
    if(x>=MOD)x-=MOD;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++)cin >> d[i] >> x[i];
    dp[1]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<K;j++){
            if(i-j>=0)norm(add[i][j]+=add[i-j][j]);
            norm(dp[i]+=add[i][j]);
        }
        if(d[i]<K){
            if(i+d[i]<=n)norm(add[i+d[i]][d[i]]+=dp[i]);
            if(i+1LL*d[i]*(x[i]+1)<=n)norm(add[i+1LL*d[i]*(x[i]+1)][d[i]]-=dp[i]);
        }else{
            for(int j=1;j<=x[i]&&i+1LL*j*d[i]<=n;j++){
                norm(dp[i*j*d[i]]+=dp[i]);
            }
        }
        norm(ans+=dp[i]);
    }
    cout << ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2552 KB Output is correct
3 Correct 0 ms 2520 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2512 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2524 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 ms 2552 KB Output is correct
3 Correct 0 ms 2520 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2512 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2524 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 10 ms 12888 KB Output is correct
21 Runtime error 6 ms 7512 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2520 KB Output is correct
2 Correct 7 ms 10588 KB Output is correct
3 Correct 5 ms 8028 KB Output is correct
4 Correct 10 ms 13148 KB Output is correct
5 Correct 98 ms 100424 KB Output is correct
6 Correct 113 ms 127568 KB Output is correct
7 Correct 131 ms 127824 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 13 ms 15020 KB Output is correct
12 Correct 114 ms 128084 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 13 ms 15044 KB Output is correct
15 Correct 107 ms 127980 KB Output is correct

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63764 KB Output is correct
2 Correct 51 ms 53420 KB Output is correct
3 Correct 127 ms 127984 KB Output is correct
4 Correct 82 ms 93760 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 13 ms 15196 KB Output is correct
8 Correct 118 ms 128084 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 2552 KB Output is correct
3 Correct 0 ms 2520 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2512 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2524 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 10 ms 12888 KB Output is correct
21 Runtime error 6 ms 7512 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -