#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
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
109 ms |
4604 KB |
Output is correct |
| 2 |
Correct |
114 ms |
4560 KB |
Output is correct |
| 3 |
Execution timed out |
20085 ms |
6060 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
300 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
12 ms |
552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
299 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
