이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 1e4 + 1, mod = 1e9 + 7;
const ll inf = 1e18;
bool is[N][N];
int sum(int x, int y) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
return x;
}
int n;
vector<int> d, x;
void slv() {
for (int i = 1; i <= n; i++) {
if (d[i]) {
for (int j = 1, p = i + d[i]; j <= x[i] && p <= n; j++, p += d[i]) {
is[p][i] = 1;
}
}
}
int dp[n + 1], ans = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = 0;
for (int j = 1; j < i; j++) {
if (is[i][j]) {
dp[i] = sum(dp[i], dp[j]);
}
}
ans = sum(ans, dp[i]);
}
cout << ans;
exit(0);
}
void slave() {
int dp[n + 1], sf[n + 2];
sf[n + 1] = 0;
for (int i = n; i >= 1; i--) {
dp[i] = 1;
if (x[i]) {
int l = i + 1, r = i + x[i];
dp[i] = sum(dp[i], sum(sf[l], -sf[r + 1]));
}
sf[i] = sum(sf[i + 1], dp[i]);
}
cout << sf[1];
exit(0);
}
void solve() {
cin >> n;
d.resize(n + 1);
x.resize(n + 1);
int ok = 1;
for (int i = 1; i <= n; i++) {
cin >> d[i] >> x[i];
if (d[i] != 1) ok = 0;
}
if (n < N) slv();
if (ok) slave();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
# | 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... |