#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long
#define ld long double
const int MAXN = 502;
int N, K;
struct State{ld vote, colab;};
bool cmpStates (const State& a, const State& b) {
if (a.colab == -1) return false;
else if (b.colab == -1) return true;
else return a.colab < b.colab;
}
vector<State> states;
struct Situ{
ld sumVote, sumColab;
ld sum(){return sumVote+sumColab;}
bool operator< (const Situ& other) const {
if (sumVote+sumColab < other.sumVote+other.sumColab) return true;
else if (sumVote+sumColab > other.sumVote+other.sumColab) return false;
else return sumColab < other.sumColab;
}
bool operator> (const Situ& other) const {
if (sumVote+sumColab > other.sumVote+other.sumColab) return true;
else if (sumVote+sumColab < other.sumVote+other.sumColab) return false;
else return sumColab > other.sumColab;
}
};
Situ dp[MAXN][MAXN][MAXN];
ld ans = (ld)1e18;
signed main() {
fastIO();
cin >> N >> K;
states.assign(N, State{0,0});
for (int i = 0; i < N; i++) {
cin >> states[i].vote >> states[i].colab;
}
sort(states.begin(), states.end(), cmpStates);
// for (int i = 0; i < N; i++) cerr << states[i].vote << " " << states[i].colab << "\n";
for (int idx = 0; idx <= N; idx++) {
for (int numVote = 0; numVote <= K; numVote++) {
for (int numColab = 0; numColab <= K; numColab++) {
dp[idx][numVote][numColab] = Situ{(ld)1e18, (ld)1e18};
}
}
}
dp[0][0][0] = Situ{0, 0};
for (int idx = 0; idx < N; idx++) {
for (int numVote = 0; numVote <= K; numVote++) {
for (int numColab = 0; numColab <= K; numColab++) {
Situ situOn = dp[idx][numVote][numColab];
if (dp[idx+1][numVote][numColab] > Situ{situOn.sumVote, situOn.sumColab}) {
dp[idx+1][numVote][numColab] = dp[idx][numVote][numColab];
}
if (numVote+1 <= K && dp[idx+1][numVote+1][numColab] > Situ{situOn.sumVote + states[idx].vote, situOn.sumColab}) {
dp[idx+1][numVote+1][numColab] = dp[idx][numVote][numColab];
dp[idx+1][numVote+1][numColab].sumVote += states[idx].vote;
}
if (numVote+1 <= K && numColab+1 <= K && states[idx].colab != -1 && dp[idx+1][numVote+1][numColab+1] > Situ{situOn.sumVote, situOn.sumColab + states[idx].colab/(numColab+1)}) {
dp[idx+1][numVote+1][numColab+1] = dp[idx][numVote][numColab];
dp[idx+1][numVote+1][numColab+1].sumColab += states[idx].colab/(numColab+1);
}
}
}
}
for (int numColab = 0; numColab <= K; numColab++) {
ans = min(ans, dp[N][K][numColab].sumColab + dp[N][K][numColab].sumVote/(numColab+1));
}
cout << fixed << setprecision(12) << ans << "\n";
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xdb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe2): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
