Submission #1160421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160421		lumaticss	Sure Bet (CEOI17_sure)	C++20	100 / 100	86 ms	6472 KiB

sure

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<long double> a(n), b(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
    a[i] -= 1;
    b[i] -= 1;
  }
  
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());

  vector<long double> pref_a(n + 1), pref_b(n + 1);
  for (int i = 1; i <= n; ++i) {
    pref_a[i] = pref_a[i - 1] + a[i - 1];
    pref_b[i] = pref_b[i - 1] + b[i - 1];
  }

  long double ans = 0;
  for (int i = 1; i <= n; ++i) {
    int L = 1, R = n;
    while (R - L + 1 > 3) {
      int m1 = L + (R - L) / 3;
      int m2 = R - (R - L) / 3;

      long double val1 = min(pref_a[i] - m1, pref_b[m1] - i);
      long double val2 = min(pref_a[i] - m2, pref_b[m2] - i);

      if (val1 < val2) {
        L = m1;
      } else {
        R = m2;
      }
    }

    for (int j = L; j <= R; ++j) {
      ans = max(ans, min(pref_a[i] - j, pref_b[j] - i));
    }
  }

  cout << fixed << setprecision(4) << ans << '\n';
}

int main() {
  ios::sync_with_stdio(0);  
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

/**
                                                                                   .@@
                                                                                  .@@@@
                                                     :--:::::::-----==:           %%@@@%
                                             :*++*+==--========----------:-==:    @%@@@@.
                                        .:. ..-=+=+*+==---=----------------------:*@%@@@@         .:..
                                    .::::-----==+++====+***#+----=------:--------:-=%%@@@#+%@@@@@@@@@@@@@@@@@@@@@@@
                :+%@@@@@@@@@@@@@@%::::=*=+++++=++==*%*=-:=*#+##=-----------------:::-@%@@@@@@@@@@@@@@@@@@@@@@@@@@@*
             %%%%%%%%%%%%@@@@@@= .:=%@@@@@%#+=+++%@@@%+-==--++-=*=-------------:-----:*@@@@@@@@@@@@@@@@@@@@@@@@@@%
             .@%%%%%%%%%@@@@%-  .-+%@@@%@%%%####%#*#%%%%==----+=:-++-::------=----:::-:=@@@@@@@@@@@@@@@@@@@@@@@@%
               %%%%%%%%@%@@+  .::*%@@@@%#**#####******+*%+===---+=..:==---------:---::::-@@@@@@@@@@@@@@@@@@@@@@@
                %%%@%@%@@@:  .:.%%%%%#=+*+*+*#*+=+***+*#+##=--=-:-+.   ==--------::::--::-@@@@@@@@@@@@@@@@@@@@@
                .#%%%@%@%   . -@%%%*==+*++++**+++=+*++=++=+#--=----=:    +---:-::::::::--:-%@@@@@@@@@@@@@@@@@@=
                 :@%%%@=   . =%%%#---======+=========++=====*+--=-=--=.    --::::::::::::--=@@@@@@@@@@@@@@@@@@@:
                  @%@#   .  -%%*+---========-:===++======-==-==--=-----:     :-::::::::::::-=@@@@@@@@@@@@@@@@@@@=
                  @#.   .  .#*=+.-=-==-==-=-::===+=-==-=--=--==+=:------=     .-:::::::-:--:--#@@@@@@@@@@@@@@@@@@#
                 -         #+=-.:----=------.:-=-*===----==--==-+=-:::-::-:     :-::::::::::::==+@@@@@@@@@@@@@@@@@@
                     .    -==:..-=--==--:--:.-===+====----=====--=--::::::--      ::::::::::--:=%*=*@@@@@@@@@@@@@@@@.
                .+: .    .==-. :----==-::--:.---==-===---:------:----::::::-+       -:::------=--+#+#@@@@@@@@@@@@@@@@.
              .  . -    ::--. .::---:-:.-=-: :--==--==:=--:-::::::--=-:::-:::*.      :::-==-==--:--**@@@@@@@%@@@@@@@@@=
                :.:     :::.. .--:::::: --::.:-:---:--:--:::::::::--:==:::::::+.       -:-=-=------:*+@@@@@@@@+ #@@@@@@
               #-.     -::.. .=+:::::-:.--:-:.::::::::::+:::::::::::::=-:::::::=.       :=-=---------=%@@@@@@@@@  :@@@@
             =@-.     :=..   -=::::-:=.:::::-.::::::::::%.::::::::::::-=:::::::-+-        *%+=-------::%@@@@@@@@@:   :.
            #@*.      +-..  :-:::::::-..::::::.:::::::::%:-==:..::::::--+:::-:-====        :*%*+--------@@@@@@@@@@@
          .@@#       :=:   .::::::::-:.::::::-.::::::.::#.:-=-.:..::-.::-+:-=--===-=         -#++*+===-:#@@@@@@@@@@@@
         *@@*.    .  --.  .:::::::::-..::::.:::.::..:..-+:: :.......=-.::==--==-====-         .**++++++=*@@@@@@@@@@@@@@:
       =@@@==.   .: .=-.  ::::::.:::= .::::...::.-.....+::.  - :....:*::--==--=======-          -*++=+=++@@@@@@@@@@@@@@@@@@%-
     +@@@@::- . .:- :=-. .::::::.::=- .::......=.=.....+ :.  :  ... - -:-==+---==-=--*: .        .*++++=+%@@@@@@@@@@@@@@@
   :@@@@%.=.. : :--.-=:..:.::.:....-  ......... --:   ::.:.  .  :::.-  ----=#+====-==-*.           :*++=++@@@@@@@@@@@@@.
     +*#-- :.:: :-::==..::.:..:...:: .:....... . ::   :. :.      -::. ..:#=-=+-==-===-=+.+       ..  -+=++%#=-+=%@@@@#
        . ...::.--::==: ::........-:..=-   :  .   .   . .:.      :-*-    .:=-+====-==--=-+#       :.   +++++==+++++*@@*
          :.::.::-.-==-.=-:...--.: :.::-.  :            .:    :+--:.     ::.==+===---=-=+--%.      +@@=. :=*+++++++*++*
          .::::::::==---=-:.. =- .  ..: :..:  .:...  :  -. .+.   -*=:.+@@@@@@@@*====---=+*:**. .    =@@**%+:-+*%*++***+=
       . ...::::::-+=--+-=:--.+:.    ..  :.-.:::::. .:  :.*.  :-:+#@@%#++=%:-@##+===-==-=+--==+ ..   .###*+++**#@%#+*+++*=
       ..::::::::.*+--:=-----:=:-....::=:--=:....:..=. :.    ..+@@@*+==---#-=@*+*====-===+:-=*@% ::    *#*+*#+*++#%%%%##*+++-
       .::.:::::::%=--:-------: .     : -:-+#+-....= ..:     -*#::%+-:=+---:+**-+==-===-=-+-=@@@@ -#    =***#%#+*+#%==*+
      :.:::::::::-+=:---=-----. .      :. ::=..:..:   .       :   -=--:..:--+#-:-+=======-%==#@@@@:.@=   :#***%%#*+=#-==
      :-::-::::.:--*:---=-=---: . ..-+*#%#=-+:...:.                :+-....-+=::::#=======-*%-+@@@%@@-%%-  .#++*%%#*+#*+-
    . =-:::=:::::-:+.:--=-=--:- .=**+-:::+++%-..:.   .               ::..--:....:=#-=====-#@+=@@@%*%@%%@%-  -*+#%:*%++*=
      =:::---:------::-:==-=--+.      ....:  :.:.                     .   ......::*=-====-*@#-%@@%#*%%%%%%@*. +**- .*#**=
     +:::. :---=--=:=:-:==-==-:@.    .....:. ..:.                       ...::...--:*=====-+@@-*@%%*##%%*###+#*= +-  ::-:**
     ::-:   .:---.#:=.:-==-==-:%%    ....  ..:  :                              :=  ==-+==-*@@=*@%#**#%#****##*++**- .:     .
    .--      .:--:=:=-.-==-==-:%@+   ....   .:                                ::   :=--===#@@**%%**#*##***++**+=+*- ::
   :.         :----=.- -=-====-%@@:   ...   .      .                         .     :---==-@@@#%%%#*#*******+++***+# :
 .             -:--: .:-+--==-:%@@@                                              . #%:-===@@@#%##*##**+++#*+*+*+****-
                ::-:  *:%==----*+%@%   .                                        . #@%--+=*@%@%%##**#**+++%#*==+*++*+=
                -=:-. #:+#+---:#%++%#.                      . .:. .:+          ..#@@@--**%%%%%###*+#++*++*--+*==+++-+.
                . =:: -==%@--=-=%**%%+                 =@+ .....:.:.:.         .*:@@%--%%@%%%####**#++*+++--:   .+*-==
                   :---+**%%---:@**%%#+     .      :@%%%::.:::::..:.:         .-::%%%-:@%%%%%###**#*+++=*+-::    :==:-=
               .    :=-+*##*#:-:**+*%**@:           =@#*:.::::::::::        .:...:@%%-+%%%%%###**+%*==+=%=:-.    ..    :.
               .     +*=+**%**-:=***##*+%%.        . .*%.:::::::::..       :. ....@%%=%%%#*#####+#%+===+:-:-.    .
                     .+-++**#+** +*-*++++%%%.    ..     --:.::.:::       =: .    .%%#+%%####*+@*++%+=-+. .:-
                      --++=**#*+*-++==+++%%%#@+..         .:::.        :=.  .    .%%%#*#*##*#+#=++#===:  .-
               .    . =-=+****+**+#:+==++#%%#%%%@%=. ..              :-:       .  %#%###%*##.:*+==#++-    :
                    .  :-=+=++***++#-:+++*++*#%%%%@@%=.. ..       :---.           #@@%@@@@=  :=  .+-+-
                .    . :.-===++**+==*+::+#++++*#%%%%%%%%-.     .*=:-:.            *%%%##*==+**#*+==*+=
                     :  -::====++*=+=+*==*=-=#**##%#%%%%%*+-:%#--:-. ..           .%#*=-==-*#*++==++-=#*:
                     :*::**=====+**==+=++*##*+++**##%%%%%%. :::.:. ..             .:=--===+@#*+++=+*+=-=+=*#=
                     #-=+==*=-++++#++==-++++*++++*#%%%%%%=-  .:.... .            .  -=--=+@#*#%@@%+==+=====+*+
                   ..*++==+**+:=*++%++++#++++++*+**#%%%%#-=. .:........              .@-=+++#%%@@%@=======++*@+
                .+-.-+*==*++#+-:=++*%+=**++++++*++**%%%%--=-.::..........            .: ==++*%@@%@+========+*#@@+
               -:--.=-*+*+++++=:.:-+*#+++*****=+*##%+#%==---::...........           :    .+%@@@%@#+======++*#%%@@#%=
              +::-:==--=*==**=#=:::-+#**+*+**++**%=.-++-:::--... ..  ....          :.     ..-@@@*++====++++*#%@@@%*=+.
              =---.=--:*+=+#*+=:-:--=++=**+++++*#+:=-.--:.:::..........           +        ..*%-+=-====+++*###@@@#+=+#*
              =----==-*+===@%:..-=---++##=+++***#-. .:=::...:..........         :=          :*:==-=====+++*%#%@@*++++##@*
             .+=-=*=+#*---==%:.:-=%+#+-:--+++*+*%:..  -::.............         :.          .--==-=======+*#*%@%+++==+##@#%+
             -:=##*+=-::-===+:.--+*#---::+*++++#+ ....-  .:.........  ..   . :+. .         =============+**#*++++===*%%#%###.
             :--*#@*+-::::-==-:-=#=.---:-+*==+#-......-:  ..........        :.            +============+*##**++====*%%%#**+=+
            .:---%=@*+-::--:-:.-*=:=:--=#++*@%-... . .-:.... ......       .:.           .=-===========+**+++===-===*#***+++=-:
            ..:-==+*#+*=:-::--.=+=::-=+*+%@+#@%.... ..-:.  .........     .-            .+============++========--===++**++==--
             .:----++%**-::  .+=+=++++++*%#+@@@%......-:.  .            =. .          .+-===-===-==++==--===------==+++====--:
              ..:--=*#%*+=   .=%##-:-+++*##+@@@@@.... -:.  .         ..-             -+==-======++*=======------==++======+*#*
               .::=-=#+#-  .::=#-:-:=++=+##*@@@@@@.. .::.  .         -:      .     .=+==-==+-==++=:=---=----========+**+=----:=
                .::--=+#=.:::-*=:::::++=+*#*%.#@@@@:..::.   .   .  .+           .=#*++++*+=====--=-=---=--=+**##*+=====-------:-
                 ..::-=*+::::=:.::::--===**+*. -@@@@:.::  ...  .  -.. .  .  .-%@@@*+*#*#*+====--=-:----*##*+==--==---======----:
                   ..:-:+:-:--:::--:::-+#*+++:   @@@@+:-  ..  .  +. ..   -@@@@@@@*@%*###*======*+-=-=%#=-=======-====-=======-:-+
                     ..:=::::::::::-:**++=-++.   .@@@@#= . .   :+    :#@@@@@@@@@%##%%%%#+++==#@%%@=**+==========-------=====-=+==
                       .  .:::::::--+==----+#++.  .@@@@@ .. ..:::+#%@%@@@@@@@#@%%%%%%@%*=+#@@@%@#%@=============------=====++++=+
                          ....  ..::=-:----+*=+**=++@@@@@:.-*@@%%%%%@@@@*:. .@@%%@%%@%**%@@@@@##@@*========--------=====+++*#*+==
                           .    ...::=:--==++=+++=+++%@@@@@@@%%@%@@#-      :%#%%%%@%#@@@@@@@%#@*@@+--===-----------======*##**=--
                                ...:.--:--=*+===++=++=#@@@@@%%%#*++=.     :%%%@@%%@@@@@@@@+@@#+*@@+===-----------====+++*##**+=-:
                                ....:+=:-==#++===+++===%@@%#*+==+++++++*##@@@%@@@@@@@@@**%##+=-%@#=-------------====+++*##*++=-:.
                                 ..:-+#===+#  .-:=+=*+*+#*+==+++++++++**%@@@@@@@@@@@*-@@#+=+==+@@=--------------===+++*##*+=-:.
                                  ..:=%+==+%       =#*-##*#+=%+++=++*+#%@@@@@@@@@@:%@#*=+=-+=#@@+-=-------------====+*#*++=-:.
                                     .=*===*      .--#:..-#@@-.   .:=**@@@@@@@@*@@@%+%+@@=--#@%=--:----------------=+++==-:.
                                       =::--         :*-##==-.        -@@@@@@@@@@@@@@@@@@@@@%+=::::::::::::::::::--====-:..
                                           ...        *%=-.....       %@@@@@@@@@@@@@@@@@@@@@*-::..:.............:::--:..      .-:
                                                  ::  ==.   .....    +@%@@@@@@@@@@@@@@@@@@@@*.:. . ...          .... .     =@*-:
                                                      ::..:---::... :#*#@@@@@@@@@%%@@@@@@@@@@+ .                  :*    ##+%+:
                                                             ...::::*-:::@@@@@@%##%%%%@@@@@@@#                   -+. *+ =  -:
                                                                   ..  .#@@%%%%##*+*#%@@@%%%=                    . :     ::
                                                                        @@@%%%######%%%%#####%=                =        #
                                                                          @@@@@%@@%%%###*##*-                 . .     =
                                                                          :@@%%%%###******+=-                 .
                                                                            *@###***+**+++:
                                                                               -*- =*++*:
 
 
                                         Credit for the pic: J5-daigada from deviantart
*/

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40