Submission #696082

#	Time	Username	Problem	Language	Result	Execution time	Memory
696082		attemptn63	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1249 ms	4644 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define double long double
#define endl '\n'
#define all(k) (k).begin(), (k).end()
#define pb push_back
#define fi first
#define se second
#define sz(k) (int)(k).size()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pi pair<long long, long long>
#define mp make_pair
#define ti tuple<long long, long long, long long>
#define INF (long long)1e18
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define sign(x) ((x > 0) - (x < 0))
template <class T>using vec = vector<T>;
template <class T>using min_heap = priority_queue<T, vec<T>, greater<T>>;
template <class T>using max_heap = priority_queue<T>;
template <class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#ifdef DEBUG
template <typename T>
inline void debug(T k){
	cout << k << " ";
}
template <typename T, typename... Args>
inline void debug(T k, Args... args){
	cout << k << " | ";
	debug(args...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "] : ";debug(__VA_ARGS__);cout << endl
template <typename T>
ostream &operator<<(ostream &o_str, const vec<T> &p){
	o_str << "{ ";
	for (auto i = 0; i < (int)p.size(); i++){
		o_str << p[i];
		if (i < (int)p.size() - 1){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T>
ostream &operator<<(ostream &o_str, const deque<T> &p){
	o_str << "{ ";
	for (auto i = 0; i < (int)p.size(); i++){
		o_str << p[i];
		if (i < (int)p.size() - 1){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const pair<T, U> &p){
	return o_str << "(" << p.fi << ", " << p.se << ")";
}
template <typename T, typename U, typename V>
ostream &operator<<(ostream &o_str, const tuple<T, U, V> &p){
	return o_str << "(" << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ")";
}
template <typename T>
ostream &operator<<(ostream &o_str, const set<T> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const map<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << i->first << ": " << i->second;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T>
ostream &operator<<(ostream &o_str, const queue<T> &p){
	queue<T> q = p;
	o_str << "{ ";
	while (!q.empty()){
		o_str << q.front();
		q.pop();
		if (!q.empty()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U, typename cmp>
ostream &operator<<(ostream &o_str, const priority_queue<T,U,cmp> &p){
	priority_queue<T,U,cmp> q = p;
	o_str << "{ ";
	while (!q.empty()){
		o_str << q.top();
		q.pop();
		if (!q.empty()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const set<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
template<typename T, typename U>
ostream &operator<<(ostream &o_str, const multiset<T, U> &p){
	o_str << "{ ";
	for (auto i = p.begin(); i != p.end(); i++){
		o_str << *i;
		if (i != --p.end()){
			o_str << ", ";
		}
	}
	return o_str << " }" << endl;
}
#else
template <typename T>
inline void debug(T k){}
template <typename T, typename... Args>
inline void debug(T k, Args... args) {}
#define debug(...)
template <typename T>
ostream &operator<<(ostream &o_str, const vec<T> &p){return o_str;}
template <typename T>
ostream &operator<<(ostream &o_str, const deque<T> &p) { return o_str; }
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const pair<T, U> &p) { return o_str; }
template <typename T, typename U, typename V>
ostream &operator<<(ostream &o_str, const tuple<T, U, V> &p) { return o_str; }
template <typename T>
ostream &operator<<(ostream &o_str, const set<T> &p) { return o_str; }
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const map<T, U> &p) { return o_str; }
template <typename T>
ostream &operator<<(ostream &o_str, const queue<T> &p) { return o_str; }
template <typename T, typename U, typename cmp>
ostream &operator<<(ostream &o_str, const priority_queue<T,U,cmp> &p){return o_str;}
template <typename T, typename U>
ostream &operator<<(ostream &o_str, const set<T, U> &p) { return o_str; }
template<typename T, typename U>
ostream &operator<<(ostream &o_str, const multiset<T, U> &p) { return o_str; }
#endif

int n,k;
vec<pi> a;
double solve(int collab){
	vec<vec<double>> dp(n + 1, vec<double>(n + 1, 1e18));
	dp[0][0] = 0;
	for(int i = 1;i <= n; i++){
		for(int anum = 0; anum <= min(i - 1, k - collab);anum++){
			int bnum = min(collab, i - 1 - anum);
			if(anum < k - collab){
				dp[i][anum + 1] = min(dp[i][anum + 1], dp[i-1][anum] + (double)a[i].fi/(collab+1));
			}
			if(bnum < collab){
				dp[i][anum] = min(dp[i][anum], dp[i-1][anum] + (double)a[i].se/(bnum+1));
			}
			else dp[i][anum] = min(dp[i][anum], dp[i-1][anum]);
		}
	}
	return dp[n][k - collab];
}
signed main(){
	speed;
	cin >> n >> k;
	a.resize(n+1, {0,0});
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		if(a[i].se == -1){
			a[i].se = INF;
		}
	}
	sort(all(a), [&](pi x, pi y){
		return (x.se == y.se ? x.fi < y.fi : x.se < y.se);
	});
	cout<<a;
	double ans = INF;
	for(int i = 0; i <= k; i++){
		ans = min(ans, solve(i));
	}
	cout << fixed << setprecision(10) << 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