oj.uz

Submission #59728

# Submission time Handle Problem Language Result Execution time Memory
59728 2018-07-23T00:54:01 Z model_code Homecoming (BOI18_homecoming) C++17
62 / 100
 1000 ms 97028 KB 
// 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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 19 ms 696 KB Output is correct
7 Correct 9 ms 1080 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct
9 Correct 4 ms 1080 KB Output is correct
10 Correct 5 ms 1080 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 24756 KB Output is correct
2 Correct 5 ms 24756 KB Output is correct
3 Correct 294 ms 97028 KB Output is correct
4 Correct 6 ms 97028 KB Output is correct
5 Correct 14 ms 97028 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 19 ms 696 KB Output is correct
7 Correct 9 ms 1080 KB Output is correct
8 Correct 4 ms 1080 KB Output is correct
9 Correct 4 ms 1080 KB Output is correct
10 Correct 5 ms 1080 KB Output is correct
11 Correct 91 ms 24756 KB Output is correct
12 Correct 5 ms 24756 KB Output is correct
13 Correct 294 ms 97028 KB Output is correct
14 Correct 6 ms 97028 KB Output is correct
15 Correct 14 ms 97028 KB Output is correct
16 Execution timed out 1089 ms 97028 KB Time limit exceeded
17 Halted 0 ms 0 KB -