oj.uz

답안 #594649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2610 ms 622900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 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 -