Submission #858210

#	Time	Username	Problem	Language	Result	Execution time	Memory
858210		Brek	Let's Win the Election (JOI22_ho_t3)	C++14	16 / 100	2577 ms	5708 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long double dp[509][509];
int best[509][509];
pair<long double, long double> t[509];
pair<pair<long double, long double>, int> t2[509];
int rel[509];
long double w;
int n, k;

bool cmp(pair<long double, long double> a, pair<long double, long double> b){
	return a.second < b.second;
}

bool cmp2(pair<pair<long double, long double>, int>  a, pair<pair<long double, long double>, int> b){
	return a.first.second < b.first.second;
}

long double reszta(int x, int lv, int a){
	long double czas = 0;
	vector<int> v;
	if(a != 0){
		int lv2 = lv - 1;
		v.push_back(rel[x]);
		v.push_back(rel[a]);
		x = best[a][lv2];
		lv2--;
		while(x > 0 && dp[x][lv2] != 0){
			v.push_back(rel[x]);
			x = best[x][lv2];
			lv2--;
		}
	}
	else{
		v.push_back(rel[x]);
	}
	//cout<<"besty : ";
	//for(int d: v) cout<<d<<" ";
	//cout<<endl;
	
	sort(v.begin(), v.end());
	int akt = 0, pot = k - lv;
	bool fin = false;
	if(v.size() == 0) fin = true;
	long double moc = lv + 1;
	for(int o = 1; o <= n; o++){
		if(pot <= 0){
			break;
		}
		if(!fin && o == v[akt]){
			akt++;
			if(akt >= (int)v.size()) fin = true;
		}
		else{
			//cout<<"dod : "<<t2[o].first.first<<" "<<o<<" "<<akt<<endl;
			czas += (long double)(t2[o].first.first / moc);
			pot--;
		}
	}
	
	return czas;
}

long double zal(int a, int b, int lv){
	long double czas = (long double)(dp[a][lv - 1] + (long double)(t[b].second / (long double)(lv)));
	//cout<<a<<" "<<b<<" "<<lv<<" "<<czas<<endl;
	if(czas >= 100000000000000000.0) return czas;
	return czas + reszta(b, lv, a);
}


int main(){
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	
	cin>>n>>k;
	for(int i = 1; i <= n; i++){
		cin>>t[i].first>>t[i].second;
		if(t[i].second == -1) t[i].second = 1000000000000000120;
		t2[i].first = t[i];
	}
	sort(t2 + 1, t2 + n + 1, cmp2);
	for(int i = 1; i <= n; i++){
		t2[i].second = i;
	}
	sort(t2 + 1, t2 + n + 1);
	for(int i = 1; i <= n; i++){
		rel[t2[i].second] = i;
	}	
	long double s = 0;
	for(int i = 1; i <= k; i++){
		//cout<<t2[i].first.first<<" "<<t2[i].first.second<<endl;
		s += t2[i].first.first;
	}
	// ssooooooooooooooooooooooort
	// rozwaz -11111
	// owalamy wiecej niz k 
	sort(t + 1, t + n + 1, cmp);
	
	//for(int i = 1; i <= n; i++){
	//	cout<<rel[i]<<" ";
	//}
	
	w = s;
	for(int i = 0; i <= n; i++){
		dp[0][i] = 1000000000000000010;
	}
	for(int i = 1; i <= n; i++){
		long double x = reszta(i, 1, 0) + (long double)(t[i].second);
		//cout<<"starter : "<<i<<" "<<x<<endl;
		w = min(w, x);
		dp[i][1] = t[i].second;
	}
		
	for(int i = 2; i <= k; i++){
		for(int j = 1; j <= n; j++){
			//if(j == 1) cout<<endl<<endl<<"NOW"<<endl;
			long double mini = 1000000000000000000;
			int kt = 0;
			for(int o = 1; o < j; o++){
				long double x = zal(o, j, i);
				//cout<<o<<" "<<j<<" "<<i<<" "<<x<<endl;
				w = min(w, x);
				if(x < mini){
					mini = x;
					kt = o;
				}
			}
			best[j][i] = kt;
			dp[j][i] = (long double)(dp[kt][i - 1] + (long double)(t[j].second / (long double)(i)));
		}
	}
	cout<<fixed<<setprecision(10)<<w<<endl;
}

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