Submission #855134

#	Time	Username	Problem	Language	Result	Execution time	Memory
855134		anhphant	Fancy Fence (CEOI20_fancyfence)	C++14	73 / 100	21 ms	12968 KiB

fancyfence

#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 subtask2 {
    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 subtask3 {
    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();
    }
}

namespace subtask4 {
    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() {
        ll sum1 = H[1];
        ll sum2 = accumulate(W + 1, W + 1 + N, 0LL);

        //cerr << sum1 << " " << sum2 << endl;

        cout << (fsum(sum1) * fsum(sum2)) % mod;
    }

    void process() {
        solve();
    }
}

namespace subtask5 {
    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() {
        ll sum = accumulate(W + 1, W + 1 + N, 0LL);
        ll ans = 0;

        for(int i = 1; i <= N; ++i) {
            ll total = (fsum(sum) * fsum(H[i])) % mod;
            total -= (fsum(sum) * fsum(H[i - 1])) % mod;
            total = (total + mod) % mod;

            ans = (ans + total) % mod;
            sum -= W[i];
        }

        cout << ans;
    }

    void process() {
        solve();
    }
}

namespace subtask6 {
    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;
    }

    ll rmin[1007][1007];

    void rmin_calculate() {
        for(int i = 1; i <= N; ++i) {
            rmin[i][i] = H[i];
            for(int j = i + 1; j <= N; ++j) {
                rmin[i][j] = min(rmin[i][j - 1], H[j]);
            }
        }

        /*for(int i = 1; i <= N; ++i) {
            for(int j = i; j <= N; ++j) {
                cerr << i << " " << j << " " << rmin[i][j] << endl;
            }
        }*/
    }

    void solve() {
        ll ans = 0;

        for(int i = 1; i <= N; ++i) {
            ans += (fsum(H[i]) * fsum(W[i])) % mod;
            ans %= mod;
        }

        for(int i = 1; i <= N; ++i) {
            for(int j = i + 1; j <= N; ++j) {
                ll total = fsum(rmin[i][j]);
                total = (total * W[i]) % mod;
                total = (total * W[j]) % mod;
                ans += total;
                ans %= mod;

                /*cerr << i << " " << j << endl;
                cerr << rmin[i][j] << " " << W[i] << " " << W[j] << endl;
                cerr << endl;*/
            }
        }

        cout << ans;
    }

    void process() {
        rmin_calculate();
        solve();
    }
}

int main() {
    initialize();

    ll maxh = *max_element(H + 1, H + 1 + N);
    ll minh = *min_element(H + 1, H + 1 + N);
    ll maxw = *max_element(W + 1, W + 1 + N);
    ll minw = *min_element(W + 1, W + 1 + N);

    if (N <= 50 && maxh <= 50 && maxw == 1)
        subtask2 :: process();
    else if (maxh == 2) subtask3 :: process();
    else if (minh == maxh) subtask4 :: process();
    else if (is_sorted(H + 1, H + 1 + N)) subtask5 :: process();
    else if (N <= 1000) subtask6 :: process();
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:227:8: warning: unused variable 'minw' [-Wunused-variable]
  227 |     ll minw = *min_element(W + 1, W + 1 + N);
      |        ^~~~
fancyfence.cpp: In function 'void initialize()':
fancyfence.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("FILE.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("FILE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 0 / 27