# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
855130 | anhphant | Fancy Fence (CEOI20_fancyfence) | C++14 | 13 ms | 10076 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;
#define endl '\n'
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 subtask1 {
ll A[1007][1007];
void solve() {
ll lastw = 0;
for(int i = 1; i <= N; ++i) {
for(int h = 1; h <= H[i]; ++h) {
for(int w = lastw + 1; w <= lastw + W[i]; ++w) {
A[h][w] = 1;
}
}
lastw += W[i];
}
/*for(int i = 1; i <= 50; ++i) {
for(int j = 1; j <= 50; ++j) {
cerr << A[i][j];
}
cerr << endl;
}*/
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() {
memset(A, 0, sizeof(A));
solve();
}
}
namespace subtask2 {
ll fsum(ll n) {
ll x1 = n;
ll x2 = n + 1;
if (x1 % 2 == 0) x1 /= 2;
else x2 /= 2;
x1 %= mod;
x2 %= mod;
return (x1 * x2) % mod;
}
void solve() {
vector<ll> split;
split.push_back(0);
for(int i = 1; i <= N; ++i) {
if (H[i] == 1 && split.back() > 0) split.push_back(0);
if (H[i] == 2) split[split.size() - 1] += W[i];
}
ll sum1 = accumulate(W + 1, W + 1 + N, 0LL);
sum1 = fsum(sum1);
ll sum2 = 0;
for(ll c : split) {
sum2 = (sum2 + fsum(c));
sum2 %= mod;
}
sum2 = (sum2 * 2) % mod;
cout << (sum1 + sum2) % 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)
subtask1 :: solve();
else subtask2 :: 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... |