Submission #531716

#	Time	Username	Problem	Language	Result	Execution time	Memory
531716		errorgorn	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	386 ms	3444 KiB

Main

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
ii arr[505];

int speed;
float memo[505][505];

float dp(int j,int k){ //we consider j A and k B
	if (j+k==0) return 0;
	if (memo[j][k]!=-1) return memo[j][k];
	
	float res=1e6;
	if (j) res=min(res,dp(j-1,k)+(float)arr[j+k].fi/speed);
	if (k) res=min(res,dp(j,k-1)+(float)arr[j+k].se/k);
	
	return memo[j][k]=res;
}

int best[505][505];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	
	int num=0;
	rep(x,1,n+1){
		if (arr[x].se!=-1) num++;
		else arr[x].se=1e9;
	}
	
	sort(arr+1,arr+n+1,[](ii i,ii j){
		return i.se<j.se;
	});
	
	vector<int> v;
	rep(x,n+1,1){
		v.pub(arr[x].fi);
		sort(all(v));
		
		int curr=0;
		rep(y,0,sz(v)){
			curr+=v[y];
			best[x][y+1]=curr;
		}
	}
	
	float ans=1e6;
	
	rep(x,0,min(num,k)+1){
		speed=x+1;
		
		rep(x,0,505) rep(y,0,505) memo[x][y]=-1;
		
		rep(y,x,k+1){
			ans=min(ans,dp(y-x,x)+(float)best[y+1][k-y]/speed);
		}
	}
	
	cout<<fixed<<setprecision(12)<<ans<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23