Submission #953135

#	Time	Username	Problem	Language	Result	Execution time	Memory
953135		vjudge1	Homecoming (BOI18_homecoming)	C++17	0 / 100	60 ms	50356 KiB

homecoming

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll solve(int n, int k, int *a, int *b) {
    vector<ll> a_pre(1);
    for (int i = 0; i < n; i++)
        a_pre.push_back(a_pre.back() + a[i]);
    for (int i = 0; i < n; i++)
        a_pre.push_back(a_pre.back() + a[i]);
    vector<ll> first_cost(n);
    for (int i = 0; i < k; i++)
        first_cost[0] += b[i];
    for (int i = 1; i < n; i++) {
        first_cost[i] = first_cost[i - 1] + b[(i + k - 1) % n] - b[i - 1];
    }
    vector<ll> self_profit(n);
    vector<ll> self_profit_pre(1);
    for (int i = 0; i < n; i++) {
        self_profit[i] = a[i] - b[(i + k - 1) % n];
        self_profit_pre.push_back(self_profit_pre.back() + self_profit[i]);
    }
    for (int i = 0; i < n; i++) {
        self_profit_pre.push_back(self_profit_pre.back() + self_profit[i]);
    }
    vector<ll> max_total_self_profit(2 * n, -1);
    deque<array<ll, 2>> q;
    for (int i = 2 * n - 1; i >= 0; i--) {
        while (q.size() && q.front()[0] - i > n - k)
            q.pop_front();
        ll pre = self_profit_pre[i + 1];
        while (q.size() && q.back()[1] < pre)
            q.pop_back();
        if (q.size())
            max_total_self_profit[i] = q.front()[0];
        else
            max_total_self_profit[i] = i;
        // max_total_self_cost[i] = max(max_total_self_cost[i], self_profit_pre[max(0, i + 1 - (n - k))]);
        q.push_back({i, pre});
    }
    // cout << "max_total_self_profit ";
    // for (int i = 0; i < n; i++) {
    //     cout << max_total_self_profit[i] << " ";
    // }

    // cout << "\n";

    ll dp[n + 1] = {};
    for (int i = 0; i < n; i++) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        ll cur = a[i] - first_cost[i];

        // self cost: i+1 ... i+n-k
        // a only: i+n-k+1 ... i+n-1

        ll a1 = cur;
        ll a2 = cur + self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1];
        ll a3 = cur + self_profit_pre[i + n - k + 1] - self_profit_pre[i + 1] + a_pre[i + n] - a_pre[i + n - k + 1];
        int nxt = i;
        ll best = 0;
        if (a1 > a2 && a1 > a3 && a1 >= 0) {
            nxt = (i + k - 1) % n;
            best = a1;
        } else if (a2 >= a1 && a2 > a3 && a2 >= 0) {
            nxt = (max_total_self_profit[i] + k - 1) % n;
            best = a2;
        } else if (a3 >= a2 && a3 >= a1 && a3 >= 0) {
            nxt = (i + n - 1) % n;
            best = a3;
        }
        // cout << i << " " << a1 << " " << a2 << " " << a3 << " " << nxt << " " << best << "\n";
        dp[nxt + 1] = max(dp[nxt + 1], dp[i] + best);

        // cout << i << " " << cur << " " << max_total_self_profit[i] << " "
        //      << self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1] << "\n";
        // ans =
        //     max({ans, cur, cur + self_profit_pre[max_total_self_profit[i] + 1] - self_profit_pre[i + 1],
        //          cur + self_profit_pre[i + n - k + 1] - self_profit_pre[i + 1] + a_pre[i + n] - a_pre[i + n - k +
        //          1]});
    }

    // for (ll x : dp)
    //     cout << x << " ";
    // cout << "\n";
    return *max_element(dp, dp + n + 1);
}

// ll solve2(int n, int k, int *a, int *b) {
//     ll ans = 0;
//     ll dp[n + 1] = {};
//     for (int i = 0; i < n; i++) {
//         // for(int j = i; j < n; j++){
//         //     ll cur = 0;
//         //     for(int jj = i; jj <= j)
//         //     bool vis[n] = {};
//         //     for(int offset = 0; offset < k + j-i; offset++){
//         //         int idx = (j + offset) % n;
//         //         if(vis[idx]) continue;
//         //         vis[idx] = 1;
//         //         cur -= b[idx];
//         //     }
//         //     dp[]
//         // }
//     }

//     // cout << "solve2 dp ";
//     // for (int x : dp)
//     //     cout << x << " ";
//     // cout << "\n";

//     return *max_element(dp, dp + n + 1);
// }

// int main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0);
//     srand(time(0));
//     int n = 10; // + rand() % 5;
//     int k = 2;  // rand() % n + 1;
//     cin >> n >> k;
//     vector<int> a(n), b(n);
//     for (int i = 0; i < n; i++) {
//         // a[i] = rand() % 2;
//         a[i] = i % 3 == 0;
//         // cout << a[i] << " ";
//         cin >> a[i];
//     }
//     for (int i = 0; i < n; i++) {
//         // b[i] = rand() % 2;
//         b[i] = i % 3 > 0;
//         // b[1] = b[4] = 0;
//         // cout << b[i] << " ";
//         cin >> b[i];
//     }
//     // int a[] = {40, 80, 100};
//     // int b[] = {140, 0, 20};
//     ll a1 = solve(n, k, a.data(), b.data());
//     cout << a1 << "\n";
//     // cout << "ans1 " << a1 << "\n";
//     // ll a2 = solve2(n, k, a.data(), b.data());
//     // cout << "ans2 " << a2 << "\n";
// }

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38