oj.uz

Submission #994559

# Submission time Handle Problem Language Result Execution time Memory
994559 2024-06-08T01:13:05 Z emptypringlescan Trains (BOI24_trains) C++17
34 / 100
 146 ms 6760 KB 
#include <bits/stdc++.h>
using namespace std;
const long long buc=316,mod=1000000007;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	pair<long long,long long> arr[n+1];
	for(int i=1; i<=n; i++) cin >> arr[i].first >> arr[i].second;
	long long dp[n+1];
	memset(dp,0,sizeof(dp));
	dp[1]=1;
	long long smol[buc+5][buc+5]; //div, rem
	memset(smol,0,sizeof(smol));
	vector<pair<int,long long> > stop[n+1];
	long long ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<buc; j++){
			dp[i]+=smol[j][i%j];
			dp[i]%=mod;
		}
		ans+=dp[i];
		ans%=mod;
		for(auto j:stop[i]){
			smol[j.first][i%j.first]-=j.second;
			smol[j.first][i%j.first]%=mod;
			if(smol[j.first][i%j.first]<0) smol[j.first][i%j.first]+=mod;
		}
		if(arr[i].first==0) continue;
		else if(arr[i].first<buc){
			smol[arr[i].first][i%arr[i].first]+=dp[i];
			smol[arr[i].first][i%arr[i].first]%=mod;
			if(i+arr[i].first*arr[i].second<=n){
				stop[i+arr[i].first*arr[i].second].push_back({arr[i].first,dp[i]});
			}
		}
		else{
			for(int j=1; j<=arr[i].second; j++){
				if(i+j*arr[i].first>n) break;
				dp[i+j*arr[i].first]+=dp[i];
				dp[i+j*arr[i].first]%=mod;
			}
		}
	}
	cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Incorrect 1 ms 1116 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 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Incorrect 1 ms 1116 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 1112 KB Output is correct
2 Correct 10 ms 1372 KB Output is correct
3 Correct 8 ms 1372 KB Output is correct
4 Correct 13 ms 1628 KB Output is correct
5 Correct 114 ms 6760 KB Output is correct
6 Correct 146 ms 5720 KB Output is correct
7 Correct 145 ms 6148 KB Output is correct
8 Incorrect 1 ms 1116 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 69 ms 3492 KB Output is correct
2 Correct 58 ms 2908 KB Output is correct
3 Correct 146 ms 5720 KB Output is correct
4 Correct 102 ms 4444 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 16 ms 1724 KB Output is correct
8 Correct 146 ms 5724 KB Output is correct

Subtask #5
0 / 29.0

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