oj.uz

Submission #855132

# Submission time Handle Problem Language Result Execution time Memory
855132 2023-09-30T09:10:52 Z anhphant Fancy Fence (CEOI20_fancyfence) C++14
55 / 100
 18 ms 10572 KB 
#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();
    }
}

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 :: solve();
    else if (maxh == 2) subtask3 :: solve();
    else if (minh == maxh) subtask4 :: solve();
    else if (is_sorted(H + 1, H + 1 + N)) subtask5 :: solve();
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:167:8: warning: unused variable 'minw' [-Wunused-variable]
  167 |     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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 6488 KB Output is correct
5 Correct 4 ms 6492 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 7 ms 4564 KB Output is correct
4 Correct 13 ms 8796 KB Output is correct
5 Correct 13 ms 9052 KB Output is correct
6 Correct 12 ms 8796 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 8 ms 4444 KB Output is correct
4 Correct 15 ms 8540 KB Output is correct
5 Correct 17 ms 8656 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 8 ms 4444 KB Output is correct
5 Correct 16 ms 8660 KB Output is correct
6 Correct 17 ms 8540 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 3 ms 4952 KB Output is correct
9 Correct 9 ms 5448 KB Output is correct
10 Correct 18 ms 10332 KB Output is correct
11 Correct 18 ms 10572 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -