oj.uz

Submission #624512

# Submission time Handle Problem Language Result Execution time Memory
624512 2022-08-08T11:18:37 Z QwertyPi Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 2277 ms 10444 KB 
#include <bits/stdc++.h>
#define int long long
#define inf (1 << 30)
#define ld long double
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];
 
int32_t main(){
	int n, K;
	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++){
		cout << vid_x[i] << ' ' << vid_y[i] << ' ' << id_x[i] << ' ' << id_y[i] << endl;
	}
	*/
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				dp[i][j][k] = inf;
			}
		}
	}
	dp[0][0][0] = 0; 
	for(int i = 0; i < n; i++){
		cnt[vid_x[i] + 1][vid_y[i] + 1] = 1;
	}
	
	/*
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			cout << cnt[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
	*/
	
	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];
		}
	}
	
	/*
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			cout << cnt[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
	
	for(int i = 0; i < n; i++){
		cout << a[id_x[i]] << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		cout << b[id_y[i]] << ' ';
	}
	cout << endl;
	*/
	
	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++){
			for(int k = 0; k <= n; 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]);
                }
            }
		}
	}
	/*
	for(int k = 0; k <= n; k++){
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= n; j++){
				cout << dp[i][j][k] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	cout << fixed << setprecision(15) << ans << endl;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
5 Correct 1928 ms 10416 KB Output is correct
6 Correct 1869 ms 10420 KB Output is correct
7 Correct 1955 ms 10400 KB Output is correct
8 Correct 1969 ms 10404 KB Output is correct
9 Correct 1940 ms 10420 KB Output is correct
10 Correct 1882 ms 10404 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
5 Correct 1928 ms 10416 KB Output is correct
6 Correct 1869 ms 10420 KB Output is correct
7 Correct 1955 ms 10400 KB Output is correct
8 Correct 1969 ms 10404 KB Output is correct
9 Correct 1940 ms 10420 KB Output is correct
10 Correct 1882 ms 10404 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2277 ms 10408 KB Output is correct
13 Correct 2105 ms 10444 KB Output is correct
14 Correct 1956 ms 10412 KB Output is correct
15 Correct 2195 ms 10404 KB Output is correct
16 Correct 2109 ms 10404 KB Output is correct
17 Correct 1941 ms 10400 KB Output is correct
18 Correct 2181 ms 10404 KB Output is correct
19 Correct 2063 ms 10404 KB Output is correct
20 Correct 1970 ms 10444 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 308 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 340 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 308 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 340 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 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 308 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 340 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 Incorrect 2242 ms 10396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
5 Correct 1928 ms 10416 KB Output is correct
6 Correct 1869 ms 10420 KB Output is correct
7 Correct 1955 ms 10400 KB Output is correct
8 Correct 1969 ms 10404 KB Output is correct
9 Correct 1940 ms 10420 KB Output is correct
10 Correct 1882 ms 10404 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2277 ms 10408 KB Output is correct
13 Correct 2105 ms 10444 KB Output is correct
14 Correct 1956 ms 10412 KB Output is correct
15 Correct 2195 ms 10404 KB Output is correct
16 Correct 2109 ms 10404 KB Output is correct
17 Correct 1941 ms 10400 KB Output is correct
18 Correct 2181 ms 10404 KB Output is correct
19 Correct 2063 ms 10404 KB Output is correct
20 Correct 1970 ms 10444 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 320 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 308 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Incorrect 1 ms 340 KB Output isn't correct
30 Halted 0 ms 0 KB -