oj.uz

답안 #1086480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086480 2024-09-10T18:26:06 Z PikachudoraEHE Trains (BOI24_trains) C++14
42 / 100
 236 ms 252500 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;const int ee = 1e9+7;
vector<int>adj[N];long long dp[N];int d[N],x[N];
long long qs[400][N];
/*struct fenwick{
    long long f[4*N];
    void update(int idx,long long v){
        for(int i=idx;i<N;i+=i&-i){
            f[i]+=v;
        }
    return;
    }
    long long sum(int idx){
        long long s = 0;
        for(int i=idx;i>=0;i-=i&-i){
            s+=f[i];
            s%=ee;
        }
        return s;
    }
}qs[400];*/
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;int k = 1;
    while(k*k<N){
        k++;
    }
    for(int i=1;i<=n;i++){
        cin>>d[i]>>x[i];
        if(d[i]>k){
            int cnt = min(((n-i)/d[i]),x[i]);
            for(int ii=1;ii<=cnt;ii++){
                adj[((ii*d[i])+i)].push_back(i);
            }
        }
    }
    dp[1]=1;long long ans=0;
    for(int i=1;i<=n;i++){
        if(d[i]<=k&&d[i]>0){
            qs[d[i]][i]+=dp[i];
            qs[d[i]][i]%=ee;
            //cout<<"1 "<<qs[d[i]][i]<<" = "<<qs[d[i]][i]-dp[i]<<" + "<<dp[i]<<"\n";
            //qs[d[i]][i]+=qs[d[i]][i-d[i]];
            //cout<<"2 "<<qs[d[i]][i]<<" = "<<qs[d[i]][i]-qs[d[i]][i-d[i]]<<" + "<<qs[d[i]][i-d[i]]<<"\n";
            int cnt = min(((n-i)/d[i]),x[i]);
            qs[d[i]][((cnt*d[i])+i+d[i])]-=dp[i];
            //cout<<" "<<(cnt*d[i])+i+d[i]<<" "<<qs[d[i]][(cnt*d[i])+i+d[i]]<<" = "<<qs[d[i]][(cnt*d[i])+i+d[i]]+dp[i]<<" - "<<dp[i]<<"\n";
        }
        for(auto v:adj[i+1]){
            dp[i+1]+=dp[v];
            dp[i+1]%=ee;
        }
        for(int ii=1;ii<=k;ii++){
            qs[ii][i+1]+=qs[ii][i+1-ii];
            qs[ii][i+1]%=ee;
            dp[i+1]+=qs[ii][i+1];
            dp[i+1]%=ee;
            //dp[i+1]+=qs[ii][i+1-ii];
            //cout<<"4 "<<dp[i+1]<<" = "<<dp[i+1]-qs[ii][i+1-ii]<<" + "<<qs[ii][i+1-ii]<<"\n";
            //dp[i+1]%=ee;
        }
        ans+=dp[i];
        //cout<<dp[i]<<"\n";
        ans%=ee;
    }
    cout<<ans;


return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 3 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 3 ms 4444 KB Output is correct
17 Correct 3 ms 4444 KB Output is correct
18 Correct 3 ms 4444 KB Output is correct
19 Correct 3 ms 4444 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 3 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 3 ms 4444 KB Output is correct
17 Correct 3 ms 4444 KB Output is correct
18 Correct 3 ms 4444 KB Output is correct
19 Correct 3 ms 4444 KB Output is correct
20 Incorrect 22 ms 25180 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 18 ms 20596 KB Output is correct
3 Incorrect 13 ms 15628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 124500 KB Output is correct
2 Correct 96 ms 104208 KB Output is correct
3 Correct 236 ms 252500 KB Output is correct
4 Correct 168 ms 182864 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 26 ms 29476 KB Output is correct
8 Correct 233 ms 252388 KB Output is correct

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 3 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 3 ms 4444 KB Output is correct
11 Correct 3 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 3 ms 4444 KB Output is correct
15 Correct 3 ms 4444 KB Output is correct
16 Correct 3 ms 4444 KB Output is correct
17 Correct 3 ms 4444 KB Output is correct
18 Correct 3 ms 4444 KB Output is correct
19 Correct 3 ms 4444 KB Output is correct
20 Incorrect 22 ms 25180 KB Output isn't correct
21 Halted 0 ms 0 KB -