Submission #59728

#	Time	Username	Problem	Language	Result	Execution time	Memory
59728		model_code	Homecoming (BOI18_homecoming)	C++17	62 / 100	1089 ms	97028 KiB

homecoming

// Bogdan Ciobanu
// O(NK)
#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);
    vector<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 <= 0LL) {
            return 0;
        }

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

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

        int i;
        for (i = 0; i < (int)flows.size(); ++i) {
            if (r >= flows[i].from) {
                int64 dif = min(r - flows[i].from + 1, flows[i].limit - flows[i].to - 1);
                mx       -= r - flows[i].from + 1 - dif;
                r         = flows[i].to + dif;
            } else {
                break;
            }
        }

        r = pushed_front + mx - 1;
        for (int j = 0; j < i; ++j) {
            if (r >= flows[j].from) {
                int64 push     = r - flows[j].from + 1;
                flows[j].from += push;
                flows[j].to   += push;
                r = flows[j].to;
            } else {
                break;
            }
        }
        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: 0 / 38