oj.uz

Submission #594649

# Submission time Handle Problem Language Result Execution time Memory
594649 2022-07-12T19:05:22 Z 1ne Let's Win the Election (JOI22_ho_t3) C++14
5 / 100
 2500 ms 633344 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,k;cin>>n>>k;
	vector<pair<double long,double long>>arr,temp;
	for (int i = 0;i<n;++i){
		double long x,y;cin>>x>>y;
		if (y == -1){
			temp.push_back({x,y});
		}
		else{
			arr.push_back({x,y});
		}
	}
	sort(arr.begin(),arr.end(),[&](auto x,auto y){
		if (x.second == y.second)return x.first < y.first;
		return x.second < y.second;
	});
	sort(temp.begin(),temp.end(),[&](auto x,auto y){
		return x.first < y.first;
	});
	for (auto x:temp)arr.push_back(x);
	double long mxn = 1e8;
		vector<vector<unordered_map<int,double long>>>dp(n + 1,vector<unordered_map<int,double long>>(k + 1));
		function<double long(int,int,double long)>solve = [&](int i,int j,double long p){
			if (i == n){
				if (j == k)return (double long)0.0;
				return mxn;
			}
			if (j == k){
				return (double long)0.0;
			}
			if (dp[i][j][p])return dp[i][j][p];
			double long ans = solve(i + 1,j,p);
			ans = min(ans,solve(i + 1,j + 1,p) + (double long)(arr[i].first / p));
			if (arr[i].second!=-1){
				ans = min(ans,solve(i + 1,j + 1,p + 1) + (double long)(arr[i].second / p));
			}
			return dp[i][j][p] = ans;
		};
	cout<<fixed<<setprecision(15)<<solve(0,0,1)<<'\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 16 ms 5952 KB Output is correct
6 Correct 39 ms 13300 KB Output is correct
7 Correct 66 ms 23440 KB Output is correct
8 Correct 86 ms 30928 KB Output is correct
9 Correct 86 ms 35760 KB Output is correct
10 Correct 85 ms 29648 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 16 ms 5952 KB Output is correct
6 Correct 39 ms 13300 KB Output is correct
7 Correct 66 ms 23440 KB Output is correct
8 Correct 86 ms 30928 KB Output is correct
9 Correct 86 ms 35760 KB Output is correct
10 Correct 85 ms 29648 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1799 ms 344712 KB Output is correct
13 Correct 1771 ms 345356 KB Output is correct
14 Correct 1731 ms 307804 KB Output is correct
15 Execution timed out 2596 ms 633344 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 1 ms 212 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 16 ms 5952 KB Output is correct
6 Correct 39 ms 13300 KB Output is correct
7 Correct 66 ms 23440 KB Output is correct
8 Correct 86 ms 30928 KB Output is correct
9 Correct 86 ms 35760 KB Output is correct
10 Correct 85 ms 29648 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1799 ms 344712 KB Output is correct
13 Correct 1771 ms 345356 KB Output is correct
14 Correct 1731 ms 307804 KB Output is correct
15 Execution timed out 2596 ms 633344 KB Time limit exceeded
16 Halted 0 ms 0 KB -