結果
| 問題 | No.1615 Double Down |
| ユーザー |
 iaNTU
|
| 提出日時 | 2021-06-22 08:03:35 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,279 bytes |
| コンパイル時間 | 3,573 ms |
| コンパイル使用メモリ | 222,992 KB |
| 実行使用メモリ | 177,180 KB |
| 最終ジャッジ日時 | 2023-09-24 14:53:49 |
| 合計ジャッジ時間 | 44,148 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | TLE | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
ソースコード
// Exported by Exporter.exe
// Included from KM_yosupo.cpp
// Included from C:\Users\ianli\Desktop\CP\template\Various\Pragma\Pragma.cpp
#define _GLIBCXX_GTHREAD_USE_WEAK 0
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("adx,aes,avx2,avx,bmi2,bmi,clflushopt,cx16,f16c,fma,fsgsbase,hle,lzcnt,movbe,sse4,pclmul,popcnt,prfchw,sahf,sse3,sse4.1,sse4.2,ssse3,xsavec,xsave,xsaveopt,xsaves")
// End of C:\Users\ianli\Desktop\CP\template\Various\Pragma\Pragma.cpp
#include <bits/stdc++.h>
using namespace std;
#define RP Read_P
#define RLP Read_Loop_P
// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp
bool Fast_IO_activated = false;
bool IOS_activated = false;
// --- Get ---
static inline char Get_Raw_Char() {
static bool pre = Fast_IO_activated = true;
static char buf[1 << 16], *p = buf, *end = buf;
if (p == end) {
if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
p = buf;
}
return *p++;
}
// --- Read ---
template <typename T> static inline void Read_P(T &n) {
static_assert(is_integral<T>::value, "Read_P requires an integral type");
char c;
while (!isdigit(c = Get_Raw_Char())) ;
n = int(c - '0');
while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
return ;
}
template <typename T> static inline void Read(T &n) {
static_assert(is_integral<T>::value, "Read requires an integral type");
char c;
bool neg = false;
while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
n = int(c - '0');
while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
if (neg) n = -n;
return ;
}
template <typename T> static inline void Read_Digit(T &n) {
static_assert(is_integral<T>::value, "Read_Digit requires an integral type");
char c;
while (!isdigit(c = Get_Raw_Char())) ;
n = int(c - '0');
return ;
}
static inline void Read_String(string &s) {
char c = Get_Raw_Char();
while (c == ' ' || c == '\n') c = Get_Raw_Char();
while (c != ' ' && c != '\n') {
s += c;
c = Get_Raw_Char();
}
return ;
}
// --- Read multiple ---
template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read(n); return Read(Fargs...);}
template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {Read_Digit(n); return Read_Digit(Fargs...);}
template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P(n); return Read_P(Fargs...);}
// --- Read Loop ---
template <typename T> static inline void Read_Loop_i(int i, T *a) {return Read(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_i(int i, T *a, Targs*... Fargs) {Read(a[i]); return Read_Loop_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...);}
template <typename T> static inline void Read_Loop_Digit_i(int i, T *a) {return Read_Digit(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_Digit_i(int i, T *a, Targs*... Fargs) {Read_Digit(a[i]); return Read_Loop_Digit_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_Digit(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_Digit_i(i, Fargs...);}
template <typename T> static inline void Read_Loop_P_i(int i, T *a) {return Read_P(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_P_i(int i, T *a, Targs*... Fargs) {Read_P(a[i]); return Read_Loop_P_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_P(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_P_i(i, Fargs...);}
// --- Float ---
template <int mul, typename T> static inline void Read(T &n) {
char c;
bool neg = false;
while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
n = int(c - '0');
while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
int cnt = 0;
if (c == '.') {
while (isdigit(c = Get_Raw_Char())) {
n = n * 10 + int(c - '0');
cnt++;
}
}
while (cnt++ < mul) n = n * 10;
if (neg) n = -n;
return ;
}
template <int mul, typename T> static inline void Read_P(T &n) {
char c;
while (!isdigit(c = Get_Raw_Char())) ;
n = int(c - '0');
while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
int cnt = 0;
if (c == '.') {
while (isdigit(c = Get_Raw_Char())) {
n = n * 10 + int(c - '0');
cnt++;
}
}
while (cnt++ < mul) n = n * 10;
return ;
}
template <int mul, typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read<mul>(n); return Read<mul>(Fargs...);}
template <int mul, typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P<mul>(n); return Read_P<mul>(Fargs...);}
// --- init ---
inline void IOS() {
IOS_activated = true;
ios::sync_with_stdio(false); cin.tie(0);
}
inline void Freopen(const char *in, const char *out) {freopen(in, "r", stdin); freopen(out, "w", stdout); return ;}
// --- Output ---
template <typename T> void Print(T x) {
if (x < 0) {
printf("-");
x = -x;
}
if (x == 0) printf("0");
else {
static int val[100];
int idx = -1;
while (x) {
val[++idx] = x % 10;
x /= 10;
}
while (idx >= 0) printf("%d", val[idx--]);
}
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp
typedef long long ll;
const int MAXN = 5010;
const ll INF = 0; //for maximum set INF to 0, and negate costs
int N, matchl[MAXN], matchr[MAXN];
ll cst[MAXN][MAXN];
namespace KM {
ll ds[MAXN], y[MAXN], z[MAXN];
int dad[MAXN], vis[MAXN];
}
ll hungarian(){
using namespace KM;
int mat = 0;
for (int i = 0; i < N; i++) y[i] = *min_element(cst[i], cst[i] + N);
for (int j = 0; j < N; j++){
z[j] = cst[0][j] - y[0];
for (int i = 1; i < N; i++) z[j] = min(z[j], cst[i][j] - y[i]);
}
memset(matchl, -1, sizeof matchl);
memset(matchr, -1, sizeof matchr);
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
if (matchr[j] == -1 && !(cst[i][j] - y[i] - z[j])) {
matchl[i] = j;
matchr[j] = i;
mat++;
break;
}
while (mat < N){
int s = 0, j = 0, i;
while (matchl[s] != -1) s++;
memset(dad, -1, sizeof dad);
memset(vis, 0, sizeof vis);
for (int k = 0; k < N; k++) ds[k] = cst[s][k] - y[s] - z[k];
while (true){
j = -1;
for (int k = 0; k < N; k++) if (!vis[k] && (j == -1 || ds[k] < ds[j])) {
j = k;
break;
}
vis[j] = 1;
i = matchr[j];
if (i == -1) break;
for (int k = 0; k < N; k++) if (!vis[k]) {
auto new_ds = ds[j] + cst[i][k] - y[i] - z[k];
if (ds[k] > new_ds) {
ds[k] = new_ds;
dad[k] = j;
}
}
}
for (int k = 0; k < N; k++)
if (k != j && vis[k]) {
auto w = ds[k] - ds[j];
z[k] += w;
y[matchr[k]] -= w;
}
y[s] += ds[j];
while (dad[j] >= 0) {
int d = dad[j];
matchr[j] = matchr[d];
matchl[matchr[j]] = j;
j = d;
}
matchr[j] = s;
matchl[s] = j;
mat++;
}
ll value = 0;
for (int i = 0; i < N; i++) value += cst[i][matchl[i]];
return value;
}
constexpr int kM = int(1E5 + 10);
int x[kM], y[kM], z[kM];
int main(){
int n, m, k, l; RP(n, m, k, l);
RLP(l, x, y, z);
N = max(n, m);
for (int i = 1; i <= l; i++) cst[x[i] - 1][y[i] - 1] = -(1LL << z[i]);
printf("%lld\n", -hungarian());
}
// End of KM_yosupo.cpp