#668949 (C++17) No.1615 Double Down

提出ソース
結果

問題	No.1615 Double Down
コンテスト
ユーザー	iaNTU
提出日時	2021-06-22 08:03:35
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	RE
実行時間	-
コード長	7,279 bytes
コンパイル時間	3,762 ms
コンパイル使用メモリ	224,580 KB
最終ジャッジ日時	2025-01-22 11:16:46
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 8 WA * 12 RE * 27 TLE * 7
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 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
yukicoder

結果

ソースコード
