Submission #857912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
857912	2023-10-07T07:14:10 Z	Brek	Let's Win the Election (JOI22_ho_t3)	C++14	11 / 100	2500 ms	195416 KB

Main

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

long double a[509];
long double b[509];
int n, k;
vector<vector<int>> komb;
long double best = 100000000000000009.0;


void gen2(set<int> s, vector<int> v, int dl){
	if(dl == n){
		komb.push_back(v);
	}
	else{
		for(int i = 1; i <= n; i++){
			if(s.find(i) == s.end()){
				s.insert(i);
				v.push_back(i);
				gen2(s, v, dl + 1);
				s.erase(i);
				v.pop_back();
			}
		}
	}
}

void gen(int il, vector<int> v){
	if((int)v.size() == n){
		if(il != k) return;
		//cout<<"v : ";
		//for(int x: v) cout<<x<<" ";
		//cout<<endl;
		//cout<<endl<<endl<<endl<<endl<<endl<<"START : "<<endl;
		for(vector<int> s : komb){
			long double moc = 1;
			long double czas = 0;
			for(int x: s){
				//cout<<x<<" ";
				x--;
				if(v[x] == 1){
					czas += (long double)(a[x + 1] / moc);
				}
				else if(v[x] == 2){
					czas += (long double)(b[x + 1] / moc);
					moc++;
				}
			}
			//cout<<"   -     "<<czas<<endl;
			best = min(best, czas);
		}
	}
	else{
		if(il < k){
			v.push_back(1);
			gen(il + 1, v);
			v.pop_back();
			if(b[v.size() + 1] != -1){
				v.push_back(2);
				gen(il + 1, v);
				v.pop_back();
			}
		}
		v.push_back(0);
		gen(il, v);
	}
}

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>>a[i]>>b[i];
	}
	
	gen2({}, {}, 0);
	
	gen(0, {});
	cout<<best<<endl;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Execution timed out	2597 ms	90976 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Execution timed out	2597 ms	90976 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #3

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	716 KB	Output is correct
2	Correct	15 ms	860 KB	Output is correct
3	Correct	27 ms	1056 KB	Output is correct
4	Correct	118 ms	856 KB	Output is correct
5	Correct	152 ms	860 KB	Output is correct
6	Correct	102 ms	880 KB	Output is correct
7	Correct	32 ms	860 KB	Output is correct
8	Correct	148 ms	860 KB	Output is correct
9	Correct	148 ms	856 KB	Output is correct
10	Correct	149 ms	880 KB	Output is correct
11	Correct	149 ms	860 KB	Output is correct
12	Correct	150 ms	884 KB	Output is correct
13	Correct	155 ms	876 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	32 ms	860 KB	Output is correct

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	716 KB	Output is correct
2	Correct	15 ms	860 KB	Output is correct
3	Correct	27 ms	1056 KB	Output is correct
4	Correct	118 ms	856 KB	Output is correct
5	Correct	152 ms	860 KB	Output is correct
6	Correct	102 ms	880 KB	Output is correct
7	Correct	32 ms	860 KB	Output is correct
8	Correct	148 ms	860 KB	Output is correct
9	Correct	148 ms	856 KB	Output is correct
10	Correct	149 ms	880 KB	Output is correct
11	Correct	149 ms	860 KB	Output is correct
12	Correct	150 ms	884 KB	Output is correct
13	Correct	155 ms	876 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	32 ms	860 KB	Output is correct
16	Execution timed out	2551 ms	195416 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	716 KB	Output is correct
2	Correct	15 ms	860 KB	Output is correct
3	Correct	27 ms	1056 KB	Output is correct
4	Correct	118 ms	856 KB	Output is correct
5	Correct	152 ms	860 KB	Output is correct
6	Correct	102 ms	880 KB	Output is correct
7	Correct	32 ms	860 KB	Output is correct
8	Correct	148 ms	860 KB	Output is correct
9	Correct	148 ms	856 KB	Output is correct
10	Correct	149 ms	880 KB	Output is correct
11	Correct	149 ms	860 KB	Output is correct
12	Correct	150 ms	884 KB	Output is correct
13	Correct	155 ms	876 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	32 ms	860 KB	Output is correct
16	Execution timed out	2551 ms	195416 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2558 ms	91812 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	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Execution timed out	2597 ms	90976 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-