oj.uz

Submission #59727

# Submission time Handle Problem Language Result Execution time Memory
59727 2018-07-23T00:53:45 Z model_code Homecoming (BOI18_homecoming) C++17
100 / 100
 309 ms 96260 KB 
// 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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 3 ms 416 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 3 ms 416 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 800 KB Output is correct
8 Correct 4 ms 800 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 5 ms 848 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 24444 KB Output is correct
2 Correct 7 ms 24444 KB Output is correct
3 Correct 309 ms 96260 KB Output is correct
4 Correct 5 ms 96260 KB Output is correct
5 Correct 16 ms 96260 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 3 ms 416 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 800 KB Output is correct
8 Correct 4 ms 800 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 5 ms 848 KB Output is correct
11 Correct 91 ms 24444 KB Output is correct
12 Correct 7 ms 24444 KB Output is correct
13 Correct 309 ms 96260 KB Output is correct
14 Correct 5 ms 96260 KB Output is correct
15 Correct 16 ms 96260 KB Output is correct
16 Correct 300 ms 96260 KB Output is correct
17 Correct 160 ms 96260 KB Output is correct
18 Correct 284 ms 96260 KB Output is correct
19 Correct 188 ms 96260 KB Output is correct
20 Correct 196 ms 96260 KB Output is correct
21 Correct 184 ms 96260 KB Output is correct