# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
854901 | anhphant | Fancy Fence (CEOI20_fancyfence) | C++14 | 4 ms | 2548 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, H[500007], W[500007];
const ll mod = 1e9 + 7;
void initialize() {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("FILE.INP", "r")) {
freopen("FILE.INP", "r", stdin);
freopen("FILE.OUT", "w", stdout);
}
cin >> N;
for(int i = 1; i <= N; ++i) cin >> H[i];
for(int i = 1; i <= N; ++i) cin >> W[i];
}
namespace subtask2 {
ll A[57][57];
void solve() {
for(int i = 1; i <= N; ++i) {
for(int j = 1; j <= H[i]; ++j) {
A[i][j] = 1;
}
}
for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
A[i][j] = A[i][j - 1] + A[i - 1][j] + A[i][j] - A[i - 1][j - 1];
}
}
ll ans = 0;
for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
for(int k = i; k <= 50; ++k) {
for(int l = j; l <= 50; ++l) {
ans += (A[k][l] - A[i - 1][l] - A[k][j - 1] + A[i - 1][j - 1])
== ((k - i + 1) * (l - j + 1));
}
}
}
}
cout << ans;
}
void process() {
solve();
}
}
namespace subtask3 {
void solve() {
ll ans = 0;
vector<ll> segment;
for(int i = 1, sdw = 0; i <= N + 1; ++i) {
if (i == N + 1 || H[i] == 1) {
segment.push_back(sdw);
sdw = 0;
}
else {
sdw += W[i];
}
}
for(ll c : segment) {
ll k = (c * (c + 1)) / 2;
k %= mod;
ans += (k * 2) % mod;
ans %= mod;
}
ll k = accumulate(W + 1, W + 1 + N, 0LL);
k = (k * (k + 1)) / 2;
k %= mod;
cout << (ans + k) % mod;
}
void process() {
solve();
}
}
int main() {
initialize();
if (N <= 50 && *max_element(H + 1, H + 1 + N) <= 50 && *max_element(W + 1, W + 1 + N) == 1)
subtask2 :: solve();
else subtask3 :: solve();
}
Compilation message (stderr)
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |