이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
const int MOD = 1e9+7;
const int MX = 4;
void add(int& a, int val) {
a += val;
a %= MOD;
}
void mul(int& a, int val) {
a *= val;
a %= MOD;
}
int32_t main() {
int N;
cin >> N;
vec<int> a(N), b(N);
for(int i = 0; i<N; i++) {
cin >> a[i];
};
for(int i = 0; i<N; i++) {
cin >> b[i];
};
vec<vec<int>> mxcnt_left(N+2, vec<int>(MX));
vec<vec<int>> mxcnt_right(N+2, vec<int>(MX));
mxcnt_left[0][0] = 1;
for(int i = 1; i<=N; i++) {
for(int j = 0; j<MX; j++) {
add(mxcnt_left[i][max(a[i-1], j)], mxcnt_left[i-1][j]);
add(mxcnt_left[i][max(b[i-1], j)], mxcnt_left[i-1][j]);
}
}
mxcnt_right[N+1][0] = 1;
for(int i = N; i>=1; i--) {
for(int j = 0; j<MX; j++) {
add(mxcnt_right[i][max(a[i-1], j)], mxcnt_right[i+1][j]);
add(mxcnt_right[i][max(b[i-1], j)], mxcnt_right[i+1][j]);
}
}
vec<vec<int>> mnmx_cnt(N+2, vec<int>(MX));
for(int i = 1; i<=N; i++) {
int rightsum = 0;
for(int j = MX-1; j>=0; j--) {
add(rightsum, mxcnt_right[i+1][j]);
add(mnmx_cnt[i][j], (mxcnt_left[i-1][j]*rightsum)%MOD);
}
int leftsum = 0;
for(int j = MX-1; j>=0; j--) {
add(mnmx_cnt[i][j], (mxcnt_right[i+1][j]*leftsum)%MOD);
add(leftsum, mxcnt_left[i-1][j]);
}
}
int ans = 0;
for(int i = 1; i<=N; i++) {
for(int j = a[i-1]; j<MX; j++) {
add(ans, mnmx_cnt[i][j]*(j-a[i-1]));
}
for(int j = b[i-1]; j<MX; j++) {
add(ans, mnmx_cnt[i][j]*(j-b[i-1]));
}
}
cout << ans << '\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |