Submission #880109

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880109	2023-11-28T18:00:53 Z	serifefedartar	Let's Win the Election (JOI22_ho_t3)	C++17	Compilation error	0 ms	0 KB

Main

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 550;

vector<pair<int,int>> v;
float dp[MAXN][MAXN][MAXN];
int mn[MAXN][MAXN], N, K;
multiset<int> in;
void precalc() {
	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++)
			mn[i][j] = 1000000000;
	}

	for (int k = 1; k <= K; k++) {
		in = multiset<int>();
		int sum = 0;
		for (int i = N; i >= 1; i--) {
			in.insert(v[i].f);
			sum += v[i].f;
			if (in.size() > k) {
				sum -= *prev(in.end());
				in.erase(prev(in.end()));
			}
			mn[k][i] = sum;
		}
	}
}

int main() {
	fast
	cin >> N >> K;

	v = vector<pair<int,int>>(N);
	for (int i = 0; i < N; i++)
		cin >> v[i].f >> v[i].s;
	sort(v.begin(), v.end(), [&](pair<int,int> a, pair<int,int> b) {
		if (a.s == -1 && b.s != -1)
			return false;
		if (b.s == -1)
			return true;
		return (a.s < b.s);
	});
	reverse(v.begin(), v.end());
	v.push_back({-1.0, -1.0});
	reverse(v.begin(), v.end());

	precalc(); 

	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			for (int k = 0; k < MAXN; k++)
				dp[i][j][k] = 1000000000.0;
		}
	}
	for (int i = 0; i < MAXN; i++)
		dp[0][0][i] = 0;

	for (int i = 1; i <= N; i++) {
		if (v[i].s == -1)
			continue;
		for (int exp = 1; exp <= K; exp++) {
			for (int selected = 0; selected < exp; selected++) {
				// A kullan
				dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
				// B kullan
				dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
			}
		}
	}

	double ans = 1000000000.0;
	for (int i = 0; i <= N; i++) {
		for (int exp = 0; exp <= K; exp++) {
			if (dp[i][exp][exp] != 1000000000.0) {
				int rem_req = K - i;
				if (rem_req < 0)
					continue;
				ans = min(ans, dp[i][exp][exp] + mn[rem_req][i+1] * 1.0 / (exp + 1));
			}
		}
	}

	cout << setprecision(15) << fixed << ans << "\n";
}

Compilation message

Main.cpp: In function 'void precalc()':
Main.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |    if (in.size() > k) {
      |        ~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:72:103: error: no matching function for call to 'min(float&, double)'
   72 |     dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
      |                                                                                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
Main.cpp:72:103: note:   deduced conflicting types for parameter 'const _Tp' ('float' and 'double')
   72 |     dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
      |                                                                                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
Main.cpp:72:103: note:   deduced conflicting types for parameter 'const _Tp' ('float' and 'double')
   72 |     dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
      |                                                                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
Main.cpp:72:103: note:   mismatched types 'std::initializer_list<_Tp>' and 'float'
   72 |     dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
      |                                                                                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
Main.cpp:72:103: note:   mismatched types 'std::initializer_list<_Tp>' and 'float'
   72 |     dp[i][selected][exp] = min(dp[i][selected][exp], dp[i-1][selected][exp] + 1.0 * v[i].f / (exp + 1));
      |                                                                                                       ^
Main.cpp:74:112: error: no matching function for call to 'min(float&, double)'
   74 |     dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
      |                                                                                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
Main.cpp:74:112: note:   deduced conflicting types for parameter 'const _Tp' ('float' and 'double')
   74 |     dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
      |                                                                                                                ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
Main.cpp:74:112: note:   deduced conflicting types for parameter 'const _Tp' ('float' and 'double')
   74 |     dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
      |                                                                                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
Main.cpp:74:112: note:   mismatched types 'std::initializer_list<_Tp>' and 'float'
   74 |     dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
      |                                                                                                                ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
Main.cpp:74:112: note:   mismatched types 'std::initializer_list<_Tp>' and 'float'
   74 |     dp[i][selected+1][exp] = min(dp[i][selected+1][exp], dp[i-1][selected][exp] + 1.0 * v[i].s / (selected + 1));
      |                                                                                                                ^