제출 #1028707

#제출 시각아이디문제언어결과실행 시간메모리
1028707isaachewTrains (BOI24_trains)C++17
16 / 100
127 ms4688 KiB
#include <bits/stdc++.h> /* Go from city i to i + k*d_i Sqrt */ int midc=300; int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); int n; std::cin>>n; std::vector<std::vector<int>> mods(1); std::vector<int> specials(n); std::vector<std::vector<std::pair<int,int>>> events(n); for(int i=1;i<=midc;i++){ mods.emplace_back(i+1); } int result=0; for(int i=0;i<n;i++){ int a,b; std::cin>>a>>b; int curtot=(i==0); for(int j=0;j<midc;j++){ curtot+=mods[j+1][i%(j+1)]; curtot%=1000000007; } curtot+=specials[i]; curtot%=1000000007; result+=curtot; result%=1000000007; if(a>0){ if(a<=midc){ mods[a][i%a]+=curtot; mods[a][i%a]%=1000000007; if(i+a*b<n)events[i+a*b].push_back({a,(1000000007-curtot)%1000000007}); }else{ for(int j=1;j<=b&&(i+a*j)<n;j++){ specials[i+a*j]+=curtot; specials[i+a*j]%=1000000007; } } } for(std::pair<int,int> j:events[i]){ mods[j.first][i%j.first]+=j.second; mods[j.first][i%j.first]%=1000000007; } } std::cout<<result<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...