Submission #59727

#	Time	Username	Problem	Language	Result	Execution time	Memory
59727		model_code	Homecoming (BOI18_homecoming)	C++17	100 / 100	309 ms	96260 KiB

homecoming

// Bogdan Ciobanu
// O(N)
#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Flow {
    int64 from, to, limit;

    Flow() = default;
    Flow(int64 from_, int64 to_, int64 limit_)
        : from(from_), to(to_), limit(limit_) {}
};

int64 solve(int n, int k, int* a_, int* b_) {
    vector<int64> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        a[i] = a_[i];
        b[i] = b_[i];
    }
    int64 result = accumulate(a.begin(), a.end(), 0LL);
    deque<Flow> flows;

    int64 start_layer = 0,    end_layer = accumulate(b.begin(), b.begin() + k, 0LL);
    int64 pushed_front = 0, cycle_layer = 0;

    function<int64(int64)> PushBack = [&](int64 mx) -> int64 {
        int64 from = start_layer;
        if (not flows.empty() and from <= flows.back().to) {
            from = flows.back().to + 1;
        }

        if (mx > end_layer - from) {
            mx = end_layer - from;
        }
        if (mx <= 0) {
            return 0;
        }

        flows.emplace_back(from, from + mx - 1, end_layer);
        return mx;
    };

    function<int64(int64)> PushFront = [&](int64 mx) -> int64 {
        if (mx == 0) return 0;
        int64 r = pushed_front + mx - 1;

        int64 mn_move = 1LL << 62, sum_used = 0;
        while (not flows.empty() and flows.front().from <= r) {
            int64 dif = min(r - flows.front().from + 1,
                flows.front().limit - flows.front().to - 1);
            mx -= r - flows.front().from + 1 - dif;
            r   = flows.front().to + dif;
            mn_move   = min(mn_move, flows.front().limit - r - 1);
            sum_used += flows.front().to - flows.front().from + 1;
            flows.pop_front();
        }

        if (sum_used != 0) {
	        flows.emplace_front(pushed_front + mx,
	                pushed_front + mx + sum_used - 1,
	                pushed_front + mx + sum_used + mn_move);
        }

        return mx;
    };

    for (int i = 0; i < n; ++i) {
        int64 pushed = PushBack(a[i]);
        a[i]        -= pushed;
        result      -= pushed;

        if (i + k > n) {
            cycle_layer  += b[(i + k - 1) % n];
            pushed_front += PushFront(min(a[i], cycle_layer - pushed_front));
        }

        start_layer += b[i];
        if (i + k < n) {
            end_layer += b[i + k];
        }
    }

    result -= pushed_front;

    return result;
}

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