#include<bits/stdc++.h>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 2e5 + 7 , mod = 1e9 + 7 ;
const ll inf = 2e18 ;
// How interesting!
int n ;
vector<double> d[2], pd[2];
double ans ;
void solve(){
double pref = 0.0 ;
for(int i = 0 ; i < n; ++ i){
pref += d[0][i] ;
double sum = -(i+1) ;
for(int j = 0 ;j < n ; ++ j){
sum += d[1][j];
if(sum < pref)continue ;
ans = max(ans , pref - double(j + 1) ) ;
}
}
}
void solve2(){
double sum1 = 0.0 ;
for(int i = 0 ;i < n; ++ i){
sum1 += d[0][i] ;
for(int j = 0 ;j < n ; ++ j){
if(sum1 <= pd[1][j] - (i+1))
ans = max(ans , sum1 - (j + 1) ) ;
}
}
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n;
for(int i = 0 ;i < n; ++ i){
double a , b;
cin >> a >> b ;
a-=1.0 ; b-=1.0 ;
d[0].push_back(a) ;
d[1].push_back(b) ;
}
for(int i = 0 ;i < 2 ; ++ i){
sort(d[i].begin() , d[i].end(), greater<double>()) ;
pd[i].resize(n) ;
}
pd[0][0] = d[0][0] +1.0;
pd[1][0] = d[1][0] +1.0;
for(int i = 0 ; i < 2 ; ++ i){
for(int j = 1 ;j < n ; ++ j)
pd[i][j] = pd[i][j-1] + d[i][j] +1.0;
}
solve2() ;
swap(d[0] , d[1]) ;
swap(pd[0] , pd[1]) ;
solve2() ;
cout<< fixed <<setprecision(4) << ans ;
return 0 ;
}
/*
- bounds sir (segtree = 4N, eulerTour = 2N, ...)
- a variable defined twice?
- will overflow?
- is it a good complexity?
- don't mess up indices (0-indexed vs 1-indexed)
- reset everything between testcases.
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
384 KB |
Output is correct |
13 |
Correct |
10 ms |
384 KB |
Output is correct |
14 |
Correct |
10 ms |
384 KB |
Output is correct |
15 |
Correct |
10 ms |
384 KB |
Output is correct |
16 |
Correct |
10 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
384 KB |
Output is correct |
13 |
Correct |
10 ms |
384 KB |
Output is correct |
14 |
Correct |
10 ms |
384 KB |
Output is correct |
15 |
Correct |
10 ms |
384 KB |
Output is correct |
16 |
Correct |
10 ms |
384 KB |
Output is correct |
17 |
Execution timed out |
2082 ms |
3684 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |