Submission #1328247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328247		Kerim	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	936 ms	503452 KiB

Main

// 【サンプルコードに関する注意】
//
// このサンプルコードは，整数のみを使用した実装となっています．理由としては，
//   - IOI シラバスでは小数があまり好まれないこと
//   - 整数だけでも解けるのであれば，それをサンプルコードにした方が良いとされていること
// などが挙げられます．
// 
// そのため，dp[i][j][k] の値は実際の値に CONST = 1000000000 を掛けた値をメモしています．
// たとえば dp[i][j][k] = 1450000000 ã®å ´åˆï¼Œå®Ÿéš›ã®å€¤ã¯ãŠã‚ˆã 1.45 です．
// なお，この実装方法でも，本問題の制約を満たす全てのテストケースで，正解との絶対誤差が 0.01 未満となるような解を出力することが証明できます．

#include <iostream>
#include <algorithm>
using namespace std;

struct Election {
	int a, b;
};

bool operator<(const Election &a1, const Election &a2) {
	if (a1.b < a2.b) return true;
	if (a1.b > a2.b) return false;
	if (a1.a < a2.a) return true;
	return false;
}

int N, K;
Election X[509];
long long dp[509][509][509]; // (pos, total votes, cooperator)
long long CONST = 1000000000;

long long solve(int Goal) {
	// Initialize [1]
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= min(i, K); j++) {
			if (i == j) {
				for (int k = 0; k <= min(j, Goal); k++) dp[i][j][k] = (1LL << 60);
			}
			else {
				dp[i][j][Goal] = (1LL << 60);
			}
		}
	}
	
	// Dynamic Programming
	dp[0][0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = max(0, K - N + i); j <= min(i, K); j++) {
			if (i == j) {
				for (int k = max(0, Goal - N + i); k <= min(j, Goal); k++) {
					dp[i + 1][j + 0][k + 0] = min(dp[i + 1][j + 0][k + 0], dp[i][j][k]);
					dp[i + 1][j + 1][k + 0] = min(dp[i + 1][j + 1][k + 0], dp[i][j][k] + CONST * X[i + 1].a / (Goal + 1));
					dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + CONST * X[i + 1].b / (k + 1));
				}
			}
			else {
				dp[i + 1][j + 0][Goal] = min(dp[i + 1][j + 0][Goal], dp[i][j][Goal]);
				dp[i + 1][j + 1][Goal] = min(dp[i + 1][j + 1][Goal], dp[i][j][Goal] + CONST * X[i + 1].a / (Goal + 1));
			}
		}
	}
	
	// Return Value
	return dp[N][K][Goal];
}

int main() {
	// Step #1. Input
	cin >> N;
	cin >> K;
	for (int i = 1; i <= N; i++) {
		cin >> X[i].a >> X[i].b;
		if (X[i].b == -1) X[i].b = 1000000;
	}
	
	// Step #2. Sorting
	sort(X + 1, X + N + 1);
	
	// Step #3. Brute Force
	long long Answer = (1LL << 60);
	for (int i = 0; i <= K; i++) {
		long long ret = solve(i);
		Answer = min(Answer, ret);
	}
	
	// Step #4. Output
	printf("%lld.%09lld\n", Answer / CONST, Answer % CONST);
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23