fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // define
  5.  
  6. #define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
  7. #define ll long long
  8. #define ld double
  9. #define ii pair<int,int>
  10. #define se second
  11. #define fi first
  12. #define iii pair<int,ii>
  13. #define all(v) v.begin(),v.end()
  14. #define bit(x,i) (((x)>>(i))&1LL)
  15. #define flip(x,i) ((x)^(1LL<<(i)))
  16. #define ms(d,x) memset(d,x,sizeof(d))
  17. #define sitingfake 1
  18. #define orz 1
  19. #define exist __exist
  20. #define ends __ends
  21. #define visit visited
  22. #define left __left
  23. #define right __right
  24.  
  25. //constant
  26.  
  27. const ll mod = 1e9 + 7;
  28. const long long linf = 4557430888798830399;
  29. const int inf = 1061109567;
  30. const int maxarr = 1e6 + 5;
  31. int dx[] = {0 , -1 , 0 , 1};
  32. int dy[] = {-1 , 0 , 1 , 0};
  33.  
  34. template<typename T> bool maximize(T &a, const T &b)
  35. {
  36.     if(a < b) {a = b; return 1;}
  37.     return 0;
  38. }
  39.  
  40. template<typename T> bool minimize(T &a, const T &b)
  41. {
  42.     if(a > b) {a = b; return 1;}
  43.     return 0;
  44. }
  45.  
  46. inline void Plus(ll & a ,ll b)
  47. {
  48.     b %= mod;
  49.     a += b;
  50.     if(a >= mod) a -= mod;
  51.     if(a < 0) a += mod;
  52.     return;
  53. }
  54.  
  55. inline void Mul(ll & a, ll b)
  56. {
  57.     a %= mod; b %= mod;
  58.     a *= b;
  59.     a %= mod;
  60.     return;
  61. }
  62.  
  63. //code
  64.  
  65. const int maxn = 1e5 + 7;
  66.  
  67. ld t[maxn] , r[maxn] , sumt[maxn] , sumr[maxn];
  68.  
  69. int n;
  70.  
  71. void solve(void)
  72. {
  73.     cin >> n;
  74.  
  75.     for(int i = 1; i <= n; i++)
  76.     {
  77.         cin >> t[i] >> r[i];
  78.     }
  79.  
  80.     sort(t + 1, t + n + 1);
  81.     sort(r + 1, r + n + 1);
  82.  
  83.     for(int i = 1; i <= n; i++)
  84.     {
  85.         sumt[i] = sumt[i - 1] + t[n - i + 1];
  86.         sumr[i] = sumr[i - 1] + r[n - i + 1];
  87.     }
  88.  
  89.     ld ans = 0;
  90.  
  91.     for(int i = 1; i <= n; i++)
  92.     {
  93.         int pos = lower_bound(sumr + 1 , sumr + n + 1 , sumt[i]) - sumr;
  94.         if(pos <= n)
  95.         {
  96.             maximize(ans , sumt[i] - 1.0 * (i + pos));
  97.         }
  98.     }
  99.  
  100.     for(int i = 1; i <= n; i++)
  101.     {
  102.         int pos = lower_bound(sumt + 1 , sumt + n + 1 , sumr[i]) - sumt;
  103.         if(pos <= n)
  104.         {
  105.             maximize(ans , sumr[i] - 1.0 * (i + pos));
  106.         }
  107.     }
  108.     cout << setprecision(4) << fixed << ans;
  109. }
  110. /**
  111. min(sumt(i) , sumr(j)) - (i + j)
  112.  
  113. **/
  114. signed main()
  115. {
  116.    ios_base::sync_with_stdio(0);
  117.    cin.tie(0);
  118.    cout.tie(0);
  119.  
  120.    #define task "sure"
  121.  
  122.    if(fopen(task".inp","r"))
  123.    {
  124.        freopen(task".inp","r",stdin);
  125.        freopen(task".out","w",stdout);
  126.    }
  127.  
  128.    int tc; tc = 1;
  129.  
  130.    while(tc--) solve();
  131.  
  132.    //execute;
  133. }
  134.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000
https://ideone.com/FHFcRz
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!