結果
| 問題 | No.2366 登校 |
| ユーザー |
 ebi_fly
|
| 提出日時 | 2023-06-30 22:35:43 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,410 bytes |
| コンパイル時間 | 1,552 ms |
| コンパイル使用メモリ | 151,988 KB |
| 実行使用メモリ | 19,552 KB |
| 最終ジャッジ日時 | 2023-09-22 05:17:36 |
| 合計ジャッジ時間 | 2,653 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | AC | 2 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,376 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,376 KB |
| testcase_08 | AC | 1 ms
4,376 KB |
| testcase_09 | AC | 1 ms
4,380 KB |
| testcase_10 | AC | 2 ms
4,376 KB |
| testcase_11 | AC | 2 ms
4,380 KB |
| testcase_12 | WA | - |
| testcase_13 | AC | 5 ms
6,796 KB |
| testcase_14 | AC | 5 ms
6,436 KB |
| testcase_15 | AC | 5 ms
6,956 KB |
| testcase_16 | AC | 5 ms
7,240 KB |
| testcase_17 | WA | - |
| testcase_18 | AC | 5 ms
6,204 KB |
| testcase_19 | WA | - |
| testcase_20 | AC | 5 ms
6,800 KB |
| testcase_21 | AC | 5 ms
6,692 KB |
| testcase_22 | WA | - |
| testcase_23 | AC | 19 ms
19,536 KB |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
ソースコード
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/* macro */
#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)
#define Rep(i, a, n) for (i64 i = (i64)(a); i < (i64)(n); i++)
#define RRep(i, a, n) for (i64 i = ((i64)(n)-i64(1)); i >= (i64)(a); i--)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
/* macro end */
/* template */
namespace ebi {
#ifdef LOCAL
#define debug(...) \
std::cerr << "LINE: " << __LINE__ << " [" << #__VA_ARGS__ << "]:", \
debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
void debug_out() {
std::cerr << std::endl;
}
template <typename Head, typename... Tail> void debug_out(Head h, Tail... t) {
std::cerr << " " << h;
if (sizeof...(t) > 0) std::cerr << " :";
debug_out(t...);
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &pa) {
return os << pa.first << " " << pa.second;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &os, std::pair<T1, T2> &pa) {
return os >> pa.first >> pa.second;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &vec) {
for (std::size_t i = 0; i < vec.size(); i++)
os << vec[i] << (i + 1 == vec.size() ? "" : " ");
return os;
}
template <typename T>
std::istream &operator>>(std::istream &os, std::vector<T> &vec) {
for (T &e : vec) std::cin >> e;
return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::optional<T> &opt) {
if (opt) {
os << opt.value();
} else {
os << "invalid value";
}
return os;
}
using std::size_t;
using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T> inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T> inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T> T pow(T x, i64 n) {
T res = 1;
while (n > 0) {
if (n & 1) res = res * x;
x = x * x;
n >>= 1;
}
return res;
}
template <class T> struct Edge {
int to;
T cost;
Edge(int _to, T _cost = 1) : to(_to), cost(_cost) {}
};
template <class T> struct Graph : std::vector<std::vector<Edge<T>>> {
using std::vector<std::vector<Edge<T>>>::vector;
void add_edge(int u, int v, T w, bool directed = false) {
(*this)[u].emplace_back(v, w);
if (directed) return;
(*this)[v].emplace_back(u, w);
}
};
struct graph : std::vector<std::vector<int>> {
using std::vector<std::vector<int>>::vector;
void add_edge(int u, int v, bool directed = false) {
(*this)[u].emplace_back(v);
if (directed) return;
(*this)[v].emplace_back(u);
}
};
constexpr i64 LNF = std::numeric_limits<i64>::max() / 4;
constexpr int INF = std::numeric_limits<int>::max() / 2;
const std::vector<int> dy = {1, 0, -1, 0, 1, 1, -1, -1};
const std::vector<int> dx = {0, 1, 0, -1, 1, -1, 1, -1};
} // namespace ebi
namespace ebi {
void main_() {
int n,m,k;
i64 t;
std::cin >> n >> m >> k >> t;
std::vector magic(n, std::vector<std::pair<i64,i64>>(m, {-1, -1}));
rep(i,0,k) {
int a,b;
i64 c,d;
std::cin >> a >> b >> c >> d;
a--; b--;
magic[a][b] = {c - 1, d};
}
if(n + m <= t) {
std::cout << 0 << '\n';
return;
}
int buff = n + m;
std::vector dp(n, std::vector(m, std::vector<i64>(buff + t + 1, LNF)));
dp[0][0][buff] = 0;
rep(i,0,n) {
rep(j,0,m) {
rrep(l, 0, buff + t + 1) {
if(dp[i][j][l] == LNF) continue;
if(l + 1 < buff + t + 1) {
if(i + 1 < n) {
chmin(dp[i+1][j][l + 1], dp[i][j][l]);
}
if(j + 1 < m) {
chmin(dp[i][j+1][l+1], dp[i][j][l]);
}
}
if(magic[i][j].first != -1) {
auto [c, d] = magic[i][j];
int nxt = std::max(i64(0), l-c);
chmin(dp[i][j][nxt], dp[i][j][l] + d);
}
}
}
}
i64 ans = LNF;
rep(l,0,buff+t+1) {
chmin(ans, dp[n-1][m-1][l]);
}
std::cout << ans << '\n';
}
} // namespace ebi
int main() {
std::cout << std::fixed << std::setprecision(15);
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int t = 1;
// std::cin >> t;
while (t--) {
ebi::main_();
}
return 0;
}