제출 #1033602

#제출 시각아이디문제언어결과실행 시간메모리
1033602reginoxTrains (BOI24_trains)C++17
0 / 100
158 ms121980 KiB
#include<bits/stdc++.h> #define ll long long #define ld long double #define all(v) begin(v), end(v) #define pi pair<int, int> #define vi vector<int> using namespace std; const int maxn = 1e5+3, SQ = 320; const ll mod = 1e9+7; ll n, x[maxn], d[maxn], dp[maxn], pf[maxn][SQ]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(ll i = 1; i <= n; i++) cin >> d[i] >> x[i]; dp[1] = 1; if(d[1] > SQ){ for(ll j = 1+d[1]; j <= min(1+x[1]*d[1], n); j+=d[1]) dp[j] = (dp[j] + dp[1]) % mod; } else{ pf[1][d[1]] = (pf[1][d[1]] + dp[1]) % mod; if(1 + d[1] * (x[1] + 1)<= n) pf[1 + d[1] * (x[1] + 1)][d[1]] = (pf[1 + d[1] * (x[1] + 1)][d[1]] - dp[1] + mod) % mod; } for(ll i = 2; i <= n; i++){ for(ll j = 1; j <= SQ; j++) pf[i][j] = (pf[i][j] + pf[i-j][j]) % mod; for(ll j = 1; j <= SQ; j++) dp[i] = (dp[i] + pf[i][j]) % mod; if(d[i] > SQ){ for(ll j = i+d[i]; j <= min(i+x[i]*d[i], n); j+=d[i]) dp[j] = (dp[j] + dp[i]) % mod; } else{ pf[i][d[i]] = (pf[i][d[i]] + dp[i]) % mod; if(i + d[i] * (x[i] + 1)<= n) pf[i + d[i] * (x[i] + 1)][d[i]] = (pf[i + d[i] * (x[i] + 1)][d[i]] - dp[i] + mod) % mod; } } // for(int i = 1; i <= n; i++) // for(int j = 1; j <= 10; j++) cout << pf[i][j] << " \n"[j==10]; ll res = 0; for(ll i = 1; i <= n; i++) res = (res + dp[i]) % mod; cout << res; return 0; }

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

Main.cpp: In function 'int main()':
Main.cpp:26:56: warning: iteration 319 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |         for(ll j = 1; j <= SQ; j++) pf[i][j] = (pf[i][j] + pf[i-j][j]) % mod;
      |                                                 ~~~~~~~^
Main.cpp:26:25: note: within this loop
   26 |         for(ll j = 1; j <= SQ; j++) pf[i][j] = (pf[i][j] + pf[i-j][j]) % mod;
      |                       ~~^~~~~
Main.cpp:27:61: warning: iteration 319 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |         for(ll j = 1; j <= SQ; j++) dp[i] = (dp[i] + pf[i][j]) % mod;
      |                                                      ~~~~~~~^
Main.cpp:27:25: note: within this loop
   27 |         for(ll j = 1; j <= SQ; j++) dp[i] = (dp[i] + pf[i][j]) % mod;
      |                       ~~^~~~~
#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...