제출 #1047181

#제출 시각아이디문제언어결과실행 시간메모리
1047181raczekTrains (BOI24_trains)C++17
21 / 100
2067 ms132176 KiB
#include<bits/stdc++.h> using namespace std; #ifdef DEBUG auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";} auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";} #define debug(X) cerr<<"["#X"]: "<<X<<endl; #else #define debug(X) {} #endif #define int long long const int MOD = 1e9+7; const int SQRT = 320; struct sqrtStruct { vector<vector<int> > res; sqrtStruct() { res.resize(SQRT+1); for(int i=1;i<=SQRT;i++) res[i].resize(i); } void update(int pos, int val) { pos %= SQRT; for(int i=1;i<=SQRT;i++) { res[i][pos%i] += val; res[i][pos%i] %= MOD; } } int get(int d, int mod) { return res[d][mod]; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int> dp(n); vector<pair<int, int> > trains(n); for(auto& v : trains) cin>>v.first>>v.second; vector<sqrtStruct> sqrts(n/SQRT+1); for(int i=n-1;i>=0;i--) { int d = trains[i].first, x = trains[i].second; if(d == 0 || x == 0) continue; if(d > SQRT) { for(int k = i+d;k<=i+d*x && k < n;k+=d) { dp[i] += dp[k] + 1; dp[i] %= MOD; } } else { int k = i + d; for(;x > 0 && k < n && k < SQRT*(i/SQRT + 1);k+=d) { dp[i] += dp[k] + 1; dp[i] %= MOD; x--; } int c = SQRT*(i/SQRT + 1); for(; x >= (SQRT - 1 - (k+d)%SQRT)/d + 1 && c < sqrts.size(); c++) { x -= (SQRT - 1 - (k+d)%SQRT)/d + 1; k += ((SQRT - 1 - (k+d)%SQRT)/d + 1)*d; dp[i] += sqrts[c].get(d, (k+d)%SQRT); dp[i] %= MOD; } for(;x > 0 && k < n;k+=d) { dp[i] += dp[k] + 1; dp[i] %= MOD; x--; } } sqrts[i/SQRT].update(i, dp[i]); } debug(dp); cout<<(dp[0]+1)%MOD; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int32_t main()':
Main.cpp:68:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<sqrtStruct>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(; x >= (SQRT - 1 - (k+d)%SQRT)/d + 1 && c < sqrts.size(); c++)
      |                                                ~~^~~~~~~~~~~~~~
#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...