#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fi first
#define se second
#define ll long long
#define ld double
using namespace std ;
const int N = 500 ;
bool flag1 ;
int n, k ;
bool us[N + 1] ;
int a[N + 1], b[N + 1], cnt[(1 << 20)] ;
ld abu = 1e9, dp[(1 << 20)][22] ;
void bfs()
{
set<pair<ld, pair<int, int>>> s ;
s.insert({0, {0, 1}}) ;
while(s.size())
{
auto p = *s.begin() ;
int in = p.se.fi, jn = p.se.se ;
ld gr = jn ;
s.erase(s.begin()) ;
if(p.fi > dp[in][jn])
continue ;
if(cnt[in] == k)
return ;
for(int j = 0 ; j < n ; j++)
{
if(((1 << j) & in))
continue ;
if(p.fi + (ld)a[j + 1] / gr < dp[in ^ (1 << j)][jn])
{
dp[in ^ (1 << j)][jn] = p.fi + (ld)a[j + 1] / gr ;
s.insert({p.fi + (ld)a[j + 1] / gr, {in ^ (1 << j), jn}}) ;
}
if(b[j + 1] >= a[j + 1] && p.fi + (ld)b[j + 1] / gr < dp[in ^ (1 << j)][jn + 1])
{
dp[in ^ (1 << j)][jn + 1] = p.fi + (ld)b[j + 1] / gr ;
s.insert({p.fi + (ld)b[j + 1] / gr, {in ^ (1 << j), jn + 1}}) ;
}
}
}
}
pair<pair<ld, ld>, int> p[N + 1] ;
void rec(int now, ld sum, ld cnt)
{
if(now == k)
{
abu = min(abu, sum) ;
return ;
}
for(int i = 1 ; i <= n ; i++)
{
if(us[i])
continue ;
us[i] ^= 1 ;
rec(now + 1, sum + p[i].fi.fi / cnt, cnt) ;
if(p[i].fi.se != -1)rec(now + 1, sum + p[i].fi.se / cnt, cnt + 1) ;
us[i] ^= 1 ;
}
}
signed main()
{
// freopen("input.txt", "r", stdin) ;
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
cin >> k ;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i] >> b[i] ;
p[i] = {{a[i], b[i]}, i} ;
if(p[i].fi.se != -1 && p[i].fi.se != p[i].fi.fi)
flag1 = 1 ;
}
if(n <= 20)
{
ld ans = 1e9 ;
for(int i = 1 ; i < (1 << n) ; i++)
for(int j = 0 ; j < n ; j++)
dp[i][j] = 1e9, cnt[i] += ((i & (1 << j)) > 0) ;
dp[0][1] = 0 ;
bfs() ;
for(int i = 1 ; i < (1 << n) ; i++)
{
if(cnt[i] != k)
continue ;
for(int j = 0 ; j < k ; j++)
ans = min(dp[i][j], ans) ;
}
cout << fixed << setprecision(9) << ans ;
return 0 ;
}
if(n <= 7)
{
rec(0, 0, 1) ;
cout << fixed << setprecision(11) << abu ;
return 0 ;
}
if(!flag1)
{
ld ans = 1e9 ;
vector<pair<pair<ld, ld>, int>> v_pos, v_neg ;
for(int i = 1 ; i <= n ; i++)
{
if(p[i].fi.se == -1)
v_neg.push_back(p[i]) ;
else
v_pos.push_back({{p[i].fi.se, p[i].fi.fi}, i}) ;
}
sort(v_pos.begin(), v_pos.end()) ;
sort(v_neg.begin(), v_neg.end()) ;
for(int i = -1 ; i < min(k, (int)v_pos.size()) ; i++)
{
int now = i + 1, uk1 = i + 1, uk2 = 0 ;
ld sum = 0, cnt = 1 ;
for(int j = 0 ; j <= i ; j++)
{
sum += v_pos[j].fi.fi / cnt ;
cnt++ ;
}
while(now < k)
{
ld mn = 1e9 ;
if(uk1 < v_pos.size())
mn = v_pos[uk1].fi.se ;
if(uk2 < v_neg.size())
mn = min(mn, v_neg[uk2].fi.fi) ;
sum += mn / cnt ;
if(uk1 < v_pos.size() && mn == v_pos[uk1].fi.se)
uk1++ ;
else
uk2++ ;
now++ ;
}
ans = min(ans, sum) ;
}
cout << fixed << setprecision(11) << ans ;
return 0 ;
}
return 0 ;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:128:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | if(uk1 < v_pos.size())
| ~~~~^~~~~~~~~~~~~~
Main.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | if(uk2 < v_neg.size())
| ~~~~^~~~~~~~~~~~~~
Main.cpp:133:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<double, double>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | if(uk1 < v_pos.size() && mn == v_pos[uk1].fi.se)
| ~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
