Submission #520600

#	Time	Username	Problem	Language	Result	Execution time	Memory
520600		Cyanmond	Wombats (IOI13_wombats)	C++17	0 / 100	20085 ms	8724 KiB

wombats

#include "wombats.h"
#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/infty.hpp"

template <typename T, T Div = 2> constexpr T infty = std::numeric_limits<T>::max() / Div;
#line 3 "library2/utility/int_alias.hpp"

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 3 "library2/utility/revrep.hpp"

class ReversedRange {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            --itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(std::min(f, l) - 1) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept {
    return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
    return ReversedRange(0, n);
}
#line 2 "library2/utility/setmin.hpp"

template <typename T> bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
#line 9 "paper.cpp"

int R, C;
std::vector<std::vector<int>> H, V;

std::vector<int> calc_mincost_c(const std::vector<int> &l, const std::vector<int> &c) {
    assert(len(l) == len(c));
    const int n = len(l);
    std::vector<int> ret = l;
    for (const int i : rep(n)) {
        ret[i] += c[i];
    }
    return ret;
}

std::vector<int> calc_mincost_r(const std::vector<int> &l, const std::vector<int> &c) {
    assert(len(l) - 1 == len(c));
    const int n = len(c);
    std::vector<int> ret = l;
    {
        // left
        int sum = 0, min = l[0];
        for (const int i : rep(n)) {
            sum += c[i];
            setmin(min, l[i] - sum);
            setmin(ret[i + 1], min + sum);
        }
    }
    {
        // right
        int sum = 0, min = l[n];
        for (const int i : revrep(n)) {
            sum += c[i];
            setmin(min, l[i] - sum);
            setmin(ret[i], min + sum);
        }
    }
    return ret;
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r;
    C = c;
    H.resize(R);
    V.resize(R - 1);
    for (const int i : rep(R)) {
        H[i].resize(C - 1);
        for (const int j : rep(C - 1)) {
            H[i][j] = h[i][j];
        }
    }
    for (const int i : rep(R - 1)) {
        V[i].resize(C);
        for (const int j : rep(C)) {
            V[i][j] = v[i][j];
        }
    }
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
}

std::vector<int> first_set(const int v) {
    std::vector<int> ret(C);
    ret[v] = 0;
    int sum = 0;
    for (const int i : revrep(v)) {
        sum += H[0][i];
        ret[i] = sum;
    }
    sum = 0;
    for (const int i : rep(v + 1, C)) {
        sum += H[0][i - 1];
        ret[i] = sum;
    }
    return ret;
}

int escape(int V1, int V2) {
    auto dp = first_set(V1);
    for (const int i : rep(R - 1)) {
        dp = calc_mincost_c(dp, V[i]);
        dp = calc_mincost_r(dp, H[i + 1]);
    }
    return dp[V2];
}
/*

int h[5000][200], v[5000][200];

int main() {
    int r, c;
    std::cin >> r >> c;
    for (const int i : rep(r)) {
        for (const int j : rep(c - 1)) {
            std::cin >> h[i][j];
        }
    }
    for (const int i : rep(r - 1)) {
        for (const int j : rep(c)) {
            std::cin >> v[i][j];
        }
    }
    init(r, c, h, v);
    int e;
    std::cin >> e;
    while (e--) {
        int t;
        std::cin >> t;
        if (t == 3) {
            int v1, v2;
            std::cin >> v1 >> v2;
            std::cout << escape(v1, v2) << std::endl;
        } else {
            int p, q, w;
            std::cin >> p >> q >> w;
            t ? changeH(p, q, w) : changeV(p, q, w);
        }
    }
}
*/

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24