제출 #1049560

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049560		ymm	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	714 ms	4524 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 512;
const ll inf = 1e15;
double dp1_[N][N], dp2_[N][N];
auto dp1 = dp1_, dp2 = dp2_;
pll a[N];
int n;

#define SMIN(x, y) ((x) = min((x), (y)))

double calc(ll col_tar, ll tot_tar)
{
	dp1[0][0] = 0;
	Loop (pos,0,n) {
		Loop (col,0,pos+1) Loop (tot,col,pos+1)
			dp2[col][tot] = dp1[col][tot];
		Loop (col,0,pos+2)
			dp2[col][pos+1] = inf;
		if (a[pos].first != inf) {
			Loop (col,0,pos+1) Loop (tot,col,pos+1)
				SMIN(dp2[col+1][tot+1], dp1[col][tot] + (double)a[pos].first / (col + 1));
		}
		Loop (col,0,pos+1) Loop (tot,col,pos+1)
			SMIN(dp2[col][tot+1], dp1[col][tot] + (double)a[pos].second / (col_tar + 1));
		swap(dp1, dp2);
	}
	return dp1[col_tar][tot_tar];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int k;
	cin >> n >> k;
	Loop (i,0,n) {
		cin >> a[i].second >> a[i].first;
		if (a[i].first == -1)
			a[i].first = inf;
	}
	sort(a, a + n);
	int l = 0, r = k-1;
	while (l < r) {
		int m = (l + r)/2;
		if (calc(m, k) > calc(m+1, k))
			l = m+1;
		else
			r = m;
	}
	cout << fixed << setprecision(9);
	cout << calc(l, k) << '\n';
}

• 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