Submission #1189046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189046		thelegendary08	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	604 ms	4424 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	//iterate over number of collaborators (c) to take
	//take vote if voters < k - c
	//sort by vote cost, divide by c+1
	//but collaborator order will not be optimal! (has to be in increasing collaboration cost)
	
	//what if we sort by collaborator cost?
	//we can still iterate over c, but use dp[i][j] where i = index and j = #collaborators taken, value is minimum cost for the collaborators + voters
	//then for each j from c to k, we need to calculate the array suffix (j, n) -> can precompute
	//dp[i][j] = min(dp[i-1][j] + a[i] / (c+1), dp[i-1][j-1] + b[i] / j)
	in2(n,k);
	vector<double> a;
	vector<double> b;
	
	f0r(i,n){
		in2(x,y);
		if(y == -1)y = 4e18;
		a.pb(x);
		b.pb(y);
	}
	vector<pair<double,double>> x;
	f0r(i,n){
		x.pb(mp(b[i],a[i]));
	}
	sort(all(x));
	f0r(i,n){
		b[i] = x[i].first;
		a[i] = x[i].second;
	}
	vvi suf(n+1, vi(n+1));
	vi thing;
	for(int i = n-1; i>=0; i--){
		thing.pb(a[i]);
		sort(all(thing));
		int sum = 0;
		f0r(j, thing.size()){
			sum += thing[j];
			suf[i][j+1] = sum;
		}
	}
	
	double ans = 4e18;
	for(double c = 0; c<n+1; c++){
		vector<vector<double>> dp(n, vector<double>(n+1, 4e18));
		dp[0][0] = a[0] / (c+1);
		dp[0][1] = b[0];
		
		FOR(i,1,n){
			dp[i][0] = dp[i-1][0] + a[i] / (c+1);
			FOR(j, 1, n+1){
				dp[i][j] = min(dp[i-1][j] + a[i] / (c+1), dp[i-1][j-1] + b[i] / j);
			}
		}
		
		double anss = 4e18;
		for(int j = c-1; j<k; j++){
			double thing;
			if(j == -1)thing = 0;
			else thing = dp[j][c];
			if(c == 0){
				// dout2(suf[j+1][k-c-(j+1-c)],thing);
			}
			anss = min(anss, suf[j+1][k - c - (j + 1 - c)] / (c + 1) + thing);
		}
		// dout(anss);
		ans = min(ans, anss);
		
	}
	
	cout<<fixed;
	cout<<setprecision(17);
	out(ans);
	
}

• 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