oj.uz

Submission #624578

# Submission time Handle Problem Language Result Execution time Memory
624578 2022-08-08T13:41:17 Z QwertyPi Let's Win the Election (JOI22_ho_t3) C++14
0 / 100
 2500 ms 10400 KB 
#include <bits/stdc++.h>
#define int long long
#define inf (1 << 30)
#define ld long double
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;
 
const int N = 513;
int a[N], b[N], s[N];
int id_x[N], id_y[N];
int vid_x[N], vid_y[N]; 
 
struct Pair{
	int a, b, id;
	Pair() = default;
	Pair(int _a, int _b, int _i) : a(_a), b(_b), id(_i){}; 
};
 
vector<Pair> vp;
long double dp[2][N][N];
int cnt[N][N];

int n, K;
	
long double f(int l){
	for(int i = 0; i < n; i++){
		s[i + 1] = s[i] + a[id_x[i]];
	}
	long double ans = inf;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
	      	for(int k = 0; k <= n; k++){
	        	dp[i % 2][j][k] = inf;
	      	}
	    }
	    if(i == 0) dp[0][0][0] = 0;
		for(int j = 0; j <= n; j++){
			if(i + j - cnt[i][j] > K) continue;
			for(int k = 0; k <= l; k++){
				if(i > 0){
					if(vid_y[id_x[i - 1]] < j){
						dp[i % 2][j][k] = min(dp[i % 2][j][k], dp[(i + 1) % 2][j][k]);
					}else{
						dp[i % 2][j][k] = min(dp[i % 2][j][k], dp[(i + 1) % 2][j][k] + (ld) a[id_x[i - 1]] / (k + 1));
					}
				}
				if(j > 0){
					if(vid_x[id_y[j - 1]] < i){
						dp[i % 2][j][k] = min(dp[i % 2][j][k], dp[i % 2][j - 1][k]);
					}else{
						if(k > 0 && b[id_y[j - 1]] != inf){
							dp[i % 2][j][k] = min(dp[i % 2][j][k], dp[i % 2][j - 1][k - 1] + (ld) b[id_y[j - 1]] / k);
						}
					}
				}
			}
	        if(i + j - cnt[i][j] == K){
	            for(int k = 0; k <= K; k++){
	                ans = min(ans, dp[i % 2][j][k]);
	            }
	        }
		}
	}
	return ans;
}

int32_t main(){
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n >> K;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		b[i] = (b[i] == -1) ? inf : b[i];
		vp.push_back({a[i], b[i], i});
	}
 
	sort(vp.begin(), vp.end(), [](Pair x, Pair y){
		return x.a < y.a || x.a == y.a && x.b < y.b;
	});
	
	for(int i = 0; i < n; i++){
		id_x[i] = vp[i].id;
		vid_x[vp[i].id] = i;
	}
 
	sort(vp.begin(), vp.end(), [](Pair x, Pair y){
		return x.b < y.b || x.b == y.b && x.a < y.a;
	});
	
	for(int i = 0; i < n; i++){
		id_y[i] = vp[i].id;
		vid_y[vp[i].id] = i;
	}
	
	for(int i = 0; i < n; i++){
		cnt[vid_x[i] + 1][vid_y[i] + 1] = 1;
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] + cnt[i][j] - cnt[i - 1][j - 1];
		}
	}
	
	int lb = 0, rb = K;
	while(rb - lb > 2){
		int m = (rb + lb) / 2;
		ld f1 = f(m), f2 = f(m + 1);
		if(f1 > f2){
			lb = m;
		}else{
			rb = m + 1;
		}
	}
	
	ld ans = min(min(f(lb), f((rb + lb) / 2)), f(rb));
	
	cout << fixed << setprecision(15) << ans << endl;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:79:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |   return x.a < y.a || x.a == y.a && x.b < y.b;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:88:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   88 |   return x.b < y.b || x.b == y.b && x.a < y.a;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Execution timed out 2575 ms 10324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Execution timed out 2575 ms 10324 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Incorrect 1 ms 340 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 2575 ms 10400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Execution timed out 2575 ms 10324 KB Time limit exceeded
6 Halted 0 ms 0 KB -