oj.uz

Submission #625372

# Submission time Handle Problem Language Result Execution time Memory
625372 2022-08-10T09:41:42 Z iomoon191 Let's Win the Election (JOI22_ho_t3) C++17
11 / 100
 173 ms 2304 KB 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
using ll = long long;
// #define int ll;

#define sz(a) (int)a.size()
#define fi first
#define se second
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
#define pi pair<int, int>
#define vi vector<int>

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const ll N = 505;
const ll inf = 1e18;
const ll mod = 1e9 + 7;

using namespace std;

ll n, k;
vector<pi> state(N);
double dp[N][N];
 
void solve(){
	cin >> n >> k;
	state.resize(n);
	foru(i, 0, n - 1){
		cin >> state[i].fi >> state[i].se;
		if(state[i].se == -1){
			state[i].se = inf;
		}
	}
	sort(state.begin(), state.end(), [&](pi a, pi b){
		return a.se < b.se;
	});
	double res = inf;
	foru(i, 0, k){
		dp[0][0] = 0;
		foru(j, 1, k - i) dp[0][j] = inf;
		foru(j, 1, n){
			foru(f, 0, k - i){
				ll zz = j - f;
				auto kap = ((1 <= zz and zz <= i) ? 1.0 * state[j - 1].se / zz : 0);
				dp[j][f] = dp[j - 1][f] + kap; 
				if(f){
					dp[j][f] = min(dp[j][f], dp[j - 1][f - 1] + 1.0 * state[j - 1].fi / (i + 1));
				}
			}
		}
		res = min(res, dp[n][k - i]);
	}
	cout << fixed << setprecision(100) << res;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t = 1; 
	while(t--){
		solve();
	}
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:40:18: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   40 |    state[i].se = inf;
      |                  ^~~

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 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2288 KB Output is correct
2 Correct 171 ms 2292 KB Output is correct
3 Correct 172 ms 2304 KB Output is correct
4 Correct 158 ms 2260 KB Output is correct
5 Correct 160 ms 2288 KB Output is correct
6 Correct 166 ms 2292 KB Output is correct
7 Correct 161 ms 2288 KB Output is correct

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 -