oj.uz

Submission #556966

# Submission time Handle Problem Language Result Execution time Memory
556966 2022-05-04T13:09:17 Z luka1234 Let's Win the Election (JOI22_ho_t3) C++14
16 / 100
 284 ms 2344 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define db double 
using namespace std;
int n,m;
vector<pair<db,db> > a;
db dp[501][501];
bool comp(pair<db,db> p1,pair<db,db> p2){
	if(p1.ss<p2.ss)
	   return 1;
	else{
		if(p1.ss==p2.ss){
			if(p1.ff<p2.ff)
			   return 1;
			else
			   return 0;
		}
		else
		   return 0;
	}
}
void make(){
	for(int i=0;i<=500;i++){
			for(int j=0;j<=500;j++)
			    dp[i][j]=1e18;
		}
}
int main(){
	cin>>n>>m;
	a.push_back({-1,-1});
	for(int k=1;k<=n;k++){
		db x,y;
		cin>>x>>y;
		if(y==-1)
		   y=1e18;
		a.push_back({x,y});
	}
	db p1,p2;
	set<db> s;
	set<db>::iterator it;
	db das;
	db mn=1e18;
	db cnt=0;
	db cur=0;
	db cnt1=0;
	db ans1=0;
	sort(a.begin()+1,a.end());
	for(int k=1;k<=m;k++){
		ans1+=a[k].ff;
	}
	sort(a.begin()+1,a.end(),comp);
	for(int k=1;k<=m;k++){	
	    make();
		dp[0][0]=0;
		cnt1=0;
		for(int i=1;i<=n;i++){
			cnt1+=a[i].ff;
			dp[i][0]=cnt1;
			for(int j=1;j<=min(k,i);j++){
				p1=dp[i-1][j]+a[i].ff/(k+1);
				if(i-1<j)
				   p1=1e18;
				p2=dp[i-1][j-1]+a[i].ss/j; 
				if(a[i].ss==1e18)
				   p2=1e18;
				dp[i][j]=min(p1,p2);
				   
			}
		}
		s.clear();
		for(int i=n;i>=k;i--){
			das=m-i;
			cnt=0;
			if(das<0){
				mn=min(mn,dp[i][k]);
				s.insert(a[i].ff);
				continue;
			}
			if(s.size()<das){
				s.insert(a[i].ff);
				continue;
			}
			cur=dp[i][k];
			for(it=s.begin();it!=s.end();it++){
			    if(cnt==das)
				   break;
				db ddd=*it;
				cur+=(*it)/(k+1);
				cnt++;
				
			}
			s.insert(a[i].ff);
			mn=min(mn,cur);
		}
	}
	mn=min(mn,ans1);
	cout<<fixed<<setprecision(5)<<mn;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:89:8: warning: unused variable 'ddd' [-Wunused-variable]
   89 |     db ddd=*it;
      |        ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 2 ms 2224 KB Output is correct
5 Correct 15 ms 2260 KB Output is correct
6 Correct 35 ms 2260 KB Output is correct
7 Correct 90 ms 2272 KB Output is correct
8 Correct 173 ms 2344 KB Output is correct
9 Correct 173 ms 2268 KB Output is correct
10 Correct 106 ms 2260 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 2 ms 2224 KB Output is correct
5 Correct 15 ms 2260 KB Output is correct
6 Correct 35 ms 2260 KB Output is correct
7 Correct 90 ms 2272 KB Output is correct
8 Correct 173 ms 2344 KB Output is correct
9 Correct 173 ms 2268 KB Output is correct
10 Correct 106 ms 2260 KB Output is correct
11 Correct 2 ms 2228 KB Output is correct
12 Correct 53 ms 2272 KB Output is correct
13 Incorrect 52 ms 2268 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 2276 KB Output is correct
2 Correct 284 ms 2272 KB Output is correct
3 Correct 249 ms 2268 KB Output is correct
4 Correct 247 ms 2264 KB Output is correct
5 Correct 231 ms 2264 KB Output is correct
6 Correct 224 ms 2260 KB Output is correct
7 Correct 249 ms 2260 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 2 ms 2224 KB Output is correct
5 Correct 15 ms 2260 KB Output is correct
6 Correct 35 ms 2260 KB Output is correct
7 Correct 90 ms 2272 KB Output is correct
8 Correct 173 ms 2344 KB Output is correct
9 Correct 173 ms 2268 KB Output is correct
10 Correct 106 ms 2260 KB Output is correct
11 Correct 2 ms 2228 KB Output is correct
12 Correct 53 ms 2272 KB Output is correct
13 Incorrect 52 ms 2268 KB Output isn't correct
14 Halted 0 ms 0 KB -