Submission #1007253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007253		Trisanu_Das	Flooding Wall (BOI24_wall)	C++17	58 / 100	5048 ms	31892 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long twok[500005];

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    pair<long long, long long> arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i].first;
    for (int i = 0; i < n; i++) cin >> arr[i].second;

    vector<pair<long long, int>> hei;
    for (int i = 0; i < n; i++) {
        if (arr[i].first > arr[i].second) swap(arr[i].first, arr[i].second);
        hei.push_back({arr[i].first, i});
        hei.push_back({arr[i].second, i});
    }

    sort(hei.begin(), hei.end(), greater<pair<long long, int>>());

    long long ans = 0;
    int st[n], add1[n], add2[n];

    memset(add1, 0, sizeof(add1));
    memset(add2, 0, sizeof(add2));
    for (int i = 0; i < n; i++) st[i] = 2;

    for (auto [h, i] : hei) {
        long long mult = 1;

        for (int j = 0; j < i; j++) mult = mult * st[j] % mod;
        for (int j = i + 1; j < n; j++) {
            if (h > arr[j].first) {
                ans = (ans + mult * add1[j] % mod * (h - arr[j].first) % mod) % mod;
            }
            if (h > arr[j].second) {
                ans = (ans + mult * add1[j] % mod * (h - arr[j].second) % mod) % mod;
            }
            add2[j] = (add2[j] + mult) % mod;
            mult = mult * st[j] % mod;
        }

        mult = 1;

        for (int j = i + 1; j < n; j++) mult = mult * st[j] % mod;
        for (int j = i - 1; j >= 0; j--) {
            if (h > arr[j].first) {
                ans = (ans + mult * add2[j] % mod * (h - arr[j].first) % mod) % mod;
            }
            if (h > arr[j].second) {
                ans = (ans + mult * add2[j] % mod * (h - arr[j].second) % mod) % mod;
            }
            add1[j] = (add1[j] + mult) % mod;
            mult = mult * st[j] % mod;
        }

        st[i]--;
    }

    ans = (ans + mod) % mod;
    cout << ans;

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30