//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int INF = 1e18;
const int mod = 1e9+7;
const int N = 501;
pair<ld,int> dp[N][N][N];
signed main() {
int n,k;
cin >> n >> k;
vector <pair<int,int>> vec(n);
for (int i = 0;i < n;i++) {
cin >> vec[i].first >> vec[i].second;
}
for (int i = 0;i < N;i++) {
for (int j = 0;j < N;j++) {
for (int z = 0;z < N;z++) {
dp[i][j][z] = {INF,INF};
}
}
}
for (int i = 0;i < n;i++) {
dp[i][0][0] = {0,0};
dp[i][1][0] = {vec[i].first,vec[i].first};
if (vec[i].second != -1)dp[i][0][1] = {vec[i].second,0};
}
for (int i = 0;i < n - 1;i++) {
for (int j = 0;j < n;j++) {
for (int z = 0;z < n;z++) {
//dp[i][j][z]
if (j != n - 1) {
pair<ld,int> res = dp[i][j][z];
res.first -= (res.second / (1.0l * (z + 1)));
res.second += vec[i+1].first;
res.first += (res.second / (1.0l * (z + 1)));
if (dp[i+1][j+1][z].first > res.first) {
dp[i+1][j+1][z] = res;
}
}
if (dp[i+1][j][z].first > dp[i][j][z].first) {
dp[i+1][j][z] = dp[i][j][z];
}
if (z != n - 1 && vec[i+1].second != -1) {
pair<ld,int> res = dp[i][j][z];
res.first -= (res.second / (1.0l * (z + 1)));
res.first += (vec[i+1].second / (1.0l * (z + 1)));
res.first += (res.second / (1.0l * (z + 2)));
if (dp[i+1][j][z+1].first > res.first) {
dp[i+1][j][z+1] = res;
}
}
}
}
}
ld best = INF;
for (int i = 0;i <= k;i++) {
best = min(best,dp[n-1][i][k-i].first);
}
cout << best << "\n";
}
Compilation message (stderr)
/tmp/cczLyvvK.o: in function `main':
Main.cpp:(.text.startup+0x8): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
Main.cpp:(.text.startup+0xbc): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
Main.cpp:(.text.startup+0x330): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x22): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2f): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f): 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/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x66): 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/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x71): 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/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x7c): 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/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa0): 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/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xab): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
