답안 #953132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953132 2024-03-25T14:34:37 Z vjudge1 Homecoming (BOI18_homecoming) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;
const int M = 19;

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 ans = 0;
    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";
}

Compilation message

homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:52:8: warning: unused variable 'ans' [-Wunused-variable]
   52 |     ll ans = 0;
      |        ^~~
homecoming.cpp: In function 'll solve2(int, int, int*, int*)':
homecoming.cpp:94:8: warning: unused variable 'ans' [-Wunused-variable]
   94 |     ll ans = 0;
      |        ^~~
/usr/bin/ld: /tmp/ccX01FeS.o: in function `main':
homecoming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEWPINS.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status