이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int32_t main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
vector<array<int, 2>> arr(N + 1);
vector<ll> dp(N + 1, 1);
priority_queue<array<int, 2>> pq;
for (int i = 1;i <= N;i ++) {
cin >> arr[i][0] >> arr[i][1];
if (i + 1LL * arr[i][0] * arr[i][1] <= N) {
pq.push({i + arr[i][0] * arr[i][1], i});
} else {
pq.push({((N - i) / arr[i][0]) * arr[i][0] + i, i});
}
}
for (int i = N;i >= 1;i --) {
while (pq.size() > 0) {
auto it = pq.top();
// cout << i << " " << it[0] << " " << it[1] << "\n";
// _time ++;
if (it[0] < i) break;
pq.pop();
if (it[1] == i) continue;
if (it[0] > i) {
assert(0);
int fi = ((i - it[1]) / arr[it[1]][0]);
if (fi * arr[it[1]][0] + it[1] < i) {
continue;
}
dp[it[1]] = (dp[it[1]] + dp[i]) % mod;
if (fi - 1 <= 0) {
continue;
}
fi --;
pq.push({fi * arr[it[1]][0] + it[1], it[1]});
} else {
int fi = ((it[0] - it[1]) / arr[it[1]][0]);
if (fi * arr[it[1]][0] + it[1] < i) {
continue;
}
dp[it[1]] = (dp[it[1]] + dp[i]) % mod;
if (fi - 1 <= 0) {
continue;
}
fi --;
pq.push({fi * arr[it[1]][0] + it[1], it[1]});
}
}
}
cout << dp[1] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |