oj.uz

Submission #858312

# Submission time Handle Problem Language Result Execution time Memory
858312 2023-10-08T05:45:45 Z Brek Let's Win the Election (JOI22_ho_t3) C++14
16 / 100
 2500 ms 5648 KB 
#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];
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)));
	//if(a == 1 && b == 3 && lv == 2) cout<<"NOWWWW : "<<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++){
		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;
		//cout<<"startowy dp : "<<i<<" "<<dp[i][1]<<endl;
	}
		
	for(int i = 2; i <= k; i++){
		for(int j = 1; j <= n; j++){
			//if(j == 1) cout<<endl<<endl<<"NOW"<<endl;
			double mini = 1000000000000000000;
			int kt = 0;
			long double dpp;
			for(int o = 1; o < j; o++){
				double x = zal(o, j, i);
				//cout<<o<<" "<<j<<" "<<i<<" "<<x - mini<<" ";
				//cout<<fixed<<setprecision(15)<<x<<" "<<mini<<" "<<(x < mini)<<endl;
				w = min(w, x);
				if(x == mini && dp[o][i - 1] < dpp){
					kt = o;
					dpp = dp[o][i - 1];
				}
				if(x < mini){
					mini = x;
					kt = o;
					dpp = dp[o][i - 1];
				}
			}
			best[j][i] = kt;
			dp[j][i] = (long double)(dp[kt][i - 1] + (long double)(t[j].second / (long double)(i)));
			//cout<<"dp : "<<j<<" "<<i<<" "<<dp[j][i]<<" "<<kt<<endl;
		}
	}
	cout<<fixed<<setprecision(4)<<w<<endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:127:18: warning: 'dpp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     if(x == mini && dp[o][i - 1] < dpp){
      |        ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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 0 ms 2396 KB Output is correct
5 Correct 19 ms 5208 KB Output is correct
6 Correct 46 ms 5208 KB Output is correct
7 Correct 95 ms 5460 KB Output is correct
8 Correct 135 ms 5468 KB Output is correct
9 Correct 190 ms 5460 KB Output is correct
10 Correct 155 ms 5456 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 0 ms 2396 KB Output is correct
5 Correct 19 ms 5208 KB Output is correct
6 Correct 46 ms 5208 KB Output is correct
7 Correct 95 ms 5460 KB Output is correct
8 Correct 135 ms 5468 KB Output is correct
9 Correct 190 ms 5460 KB Output is correct
10 Correct 155 ms 5456 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Execution timed out 2571 ms 5648 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2392 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 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2392 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 2396 KB Output is correct
18 Correct 1 ms 2408 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 2392 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 2392 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 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2392 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 2396 KB Output is correct
18 Correct 1 ms 2408 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 2392 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 2392 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 2561 ms 5376 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 0 ms 2396 KB Output is correct
5 Correct 19 ms 5208 KB Output is correct
6 Correct 46 ms 5208 KB Output is correct
7 Correct 95 ms 5460 KB Output is correct
8 Correct 135 ms 5468 KB Output is correct
9 Correct 190 ms 5460 KB Output is correct
10 Correct 155 ms 5456 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Execution timed out 2571 ms 5648 KB Time limit exceeded
13 Halted 0 ms 0 KB -