oj.uz

Submission #624511

# Submission time Handle Problem Language Result Execution time Memory
624511 2022-08-08T11:18:10 Z QwertyPi Let's Win the Election (JOI22_ho_t3) C++14
0 / 100
 2317 ms 20896 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2317 ms 20896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -