Submission #858210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858210	2023-10-07T15:21:12 Z	Brek	Let's Win the Election (JOI22_ho_t3)	C++14	16 / 100	2500 ms	5708 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	44 ms	4952 KB	Output is correct
6	Correct	110 ms	5264 KB	Output is correct
7	Correct	220 ms	5456 KB	Output is correct
8	Correct	334 ms	5456 KB	Output is correct
9	Correct	447 ms	5708 KB	Output is correct
10	Correct	312 ms	5496 KB	Output is correct

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	44 ms	4952 KB	Output is correct
6	Correct	110 ms	5264 KB	Output is correct
7	Correct	220 ms	5456 KB	Output is correct
8	Correct	334 ms	5456 KB	Output is correct
9	Correct	447 ms	5708 KB	Output is correct
10	Correct	312 ms	5496 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Execution timed out	2577 ms	5180 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2408 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2408 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2392 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2392 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	2396 KB	Output is correct
27	Correct	1 ms	2396 KB	Output is correct
28	Correct	1 ms	2396 KB	Output is correct
29	Correct	1 ms	2396 KB	Output is correct
30	Correct	1 ms	2396 KB	Output is correct
31	Correct	1 ms	2396 KB	Output is correct
32	Correct	1 ms	2396 KB	Output is correct
33	Correct	1 ms	2396 KB	Output is correct
34	Correct	1 ms	2396 KB	Output is correct
35	Correct	1 ms	2396 KB	Output is correct
36	Correct	1 ms	2396 KB	Output is correct
37	Correct	1 ms	2396 KB	Output is correct
38	Incorrect	1 ms	2396 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2408 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2392 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2648 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	0 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	0 ms	2396 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	2392 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2392 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	1 ms	2396 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	2396 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	2396 KB	Output is correct
27	Correct	1 ms	2396 KB	Output is correct
28	Correct	1 ms	2396 KB	Output is correct
29	Correct	1 ms	2396 KB	Output is correct
30	Correct	1 ms	2396 KB	Output is correct
31	Correct	1 ms	2396 KB	Output is correct
32	Correct	1 ms	2396 KB	Output is correct
33	Correct	1 ms	2396 KB	Output is correct
34	Correct	1 ms	2396 KB	Output is correct
35	Correct	1 ms	2396 KB	Output is correct
36	Correct	1 ms	2396 KB	Output is correct
37	Correct	1 ms	2396 KB	Output is correct
38	Incorrect	1 ms	2396 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2507 ms	5388 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	44 ms	4952 KB	Output is correct
6	Correct	110 ms	5264 KB	Output is correct
7	Correct	220 ms	5456 KB	Output is correct
8	Correct	334 ms	5456 KB	Output is correct
9	Correct	447 ms	5708 KB	Output is correct
10	Correct	312 ms	5496 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Execution timed out	2577 ms	5180 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-