Submission #1262126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262126		gary	Sure Bet (CEOI17_sure)	C++20	100 / 100	21 ms	3400 KiB

sure

// Hazard

#include <bits/stdc++.h>

using namespace std;

#define int long long

constexpr int sizik = 1000 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

// #define GARY_DBG
#ifdef GARY_DBG

#ifndef GARY_LIB
#include <bits/stdc++.h>
#endif

// --- ANSI Color Codes ---
#define RESET "\033[0m"
#define RED "\033[31m" /* Red */
#define GREEN "\033[32m" /* Green */
#define YELLOW "\033[33m" /* Yellow */
#define BLUE "\033[34m" /* Blue */
#define MAGENTA "\033[35m" /* Magenta */
#define CYAN "\033[36m" /* Cyan */

// Overload for std::pair
template<typename T, typename U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
    return os << '(' << p.first << ", " << p.second << ')';
}

// For std::tuple
template<typename... Ts>
std::ostream& operator<<(std::ostream& os, const std::tuple<Ts...>& t) {
    os << '(';
    std::apply(
        [&os](const auto&... args) {
            bool first = true;
            ((os << (first ? "" : ", ") << args, first = false), ...);
        },
        t);
    return os << ')';
}

//  For std::bitset
template<size_t N>
std::ostream& operator<<(std::ostream& os, const std::bitset<N>& b) {
    return os << "bitset{" << b.to_string() << "}";
}

// Helper trait to detect if a type is a string
template<typename T>
struct is_string : std::false_type {};
template<>
struct is_string<std::string> : std::true_type {};
template<>
struct is_string<const char*> : std::true_type {};
template<>
struct is_string<char*> : std::true_type {};

// Overload for std::stack
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::stack<T, Container> s) {
    os << "stack{top: ";
    bool first = true;
    while (!s.empty()) {
        if (!first) os << ", ";
        first = false;
        os << s.top();
        s.pop();
    }
    os << '}';
    return os;
}

// Overload for std::queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container>
std::ostream& operator<<(std::ostream& os, std::queue<T, Container> q) {
    os << "queue{front: ";
    bool first = true;
    while (!q.empty()) {
        if (!first) os << ", ";
        first = false;
        os << q.front();
        q.pop();
    }
    os << '}';
    return os;
}

// Overload for std::priority_queue
// We pass by value to create a copy that we can pop from.
template<typename T, typename Container, typename Compare>
std::ostream& operator<<(std::ostream& os, std::priority_queue<T, Container, Compare> pq) {
    os << "pq{top: ";
    bool first = true;
    while (!pq.empty()) {
        if (!first) os << ", ";
        first = false;
        os << pq.top();
        pq.pop();
    }
    os << '}';
    return os;
}

// Overload for containers (like vector, list, set, map, and deque) excluding strings
template<typename Container, typename std::enable_if<!is_string<Container>::value && !std::is_same<Container, std::string>::value &&
                                                         !std::is_same<Container, const char*>::value && !std::is_same<Container, char*>::value &&
                                                         !std::is_same<typename Container::value_type, char>::value,
                                                     int>::type = 0>
std::ostream& operator<<(std::ostream& os, const Container& container) {
    os << '{';
    bool first = true;
    for (const auto& elem : container) {
        if (!first) os << ", ";
        first = false;
        os << elem;
    }
    os << '}';
    return os;
}

// Helper to print multiple arguments (tuple unpacking trick)
template<size_t Index = 0, typename... Ts>
typename std::enable_if<Index == sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>&) {
}

template<size_t Index = 0, typename... Ts>
    typename std::enable_if < Index<sizeof...(Ts)>::type print_tuple(const std::tuple<Ts...>& t) {
    if (Index > 0) std::cerr << ", ";
    std::cerr << std::get<Index>(t);
    print_tuple<Index + 1>(t);
}

// Debug macro
#define debug(...)                                                                                                 \
    do {                                                                                                           \
        std::cerr << MAGENTA << "[" << __FILE__ << ":" << __LINE__ << " (" << __func__ << ")]" << RESET << " -> "; \
        std::cerr << "[" << #__VA_ARGS__ << "] ~> [";                                                              \
        print_tuple(std::make_tuple(__VA_ARGS__));                                                                 \
        std::cerr << "]\n";                                                                                        \
    } while (0)
#else
#define debug(...) ((void)0)
#endif

typedef vec<vec<int>> _kra;

inline int readChar() {
    static char buf[1 << 16];
    static int idx = 0, n = 0;
    if (idx >= n) {
        n = fread(buf, 1, sizeof(buf), stdin);
        idx = 0;
        if (n == 0) return EOF;
    }
    return buf[idx++];
}

inline long long readInt() {
    int c = readChar();
    while (c <= ' ') {
        if (c == EOF) return 0;
        c = readChar();
    }
    bool neg = false;
    if (c == '-') {
        neg = true;
        c = readChar();
    }
    long long x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readChar();
    }
    return neg ? -x : x;
}

inline int readDecimal() {
    int c;
    do {
        c = readChar();
    } while (c != '-' && (c < '0' || c > '9'));

    bool neg = false;
    if (c == '-') {
        neg = true;
        c = readChar();
    }

    long long val = 0;
    while (c >= '0' && c <= '9') {
        val = val * 10 + (c - '0');
        c = readChar();
    }
    val *= 10000;

    if (c == '.') {
        int mul = 1000;
        c = readChar();
        while (mul >= 1 && c >= '0' && c <= '9') {
            val += (c - '0') * mul;
            mul /= 10;
            c = readChar();
        }
        while (c >= '0' && c <= '9')
            c = readChar();
    }

    return neg ? -val : val;
}

inline void printScaled(long long x) {
    if (x < 0) {
        putchar_unlocked('-');
        x = -x;
    }
    long long intPart = x / 10000;
    long long fracPart = x % 10000;

    char buf[32];
    int len = 0;
    do {
        buf[len++] = '0' + intPart % 10;
        intPart /= 10;
    } while (intPart > 0);
    while (len--)
        putchar_unlocked(buf[len]);

    putchar_unlocked('.');

    for (int p = 1000; p > 0; p /= 10) {
        putchar_unlocked('0' + (fracPart / p) % 10);
    }
}

void solve() {
    int n = readInt();

    int sum = 0, sum_a = 0, sum_b = 0;

    std::vector<int> a(n), b(n);
    std::vector<int> a_pref(n + 1), b_pref(n + 1);
    for (int i = 0; i < n; i++) {
        a[i] = readDecimal();
        b[i] = readDecimal();
        sum += a[i] + b[i];
        sum_a += a[i];
        sum_b += b[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>());
    std::sort(b.begin(), b.end(), std::greater<int>());

    for (int i = 1; i <= n; i++) {
        a_pref[i] = a_pref[i - 1] + a[i - 1];
        b_pref[i] = b_pref[i - 1] + b[i - 1];
    }

    int maxi = 0;
    for (const auto& c : b_pref) {
        maxi = std::max(maxi, c);
    }

    // debug(a, b, a_pref, b_pref);
    debug(sum, sum_a, sum_b);
    debug(a);
    debug(b);
    debug(a_pref);
    debug(b_pref);

    int wyn = 0;
    for (int x = 1; x <= 2 * n; x++) {
        debug(x, "NEW");
        int L = std::max(0ll, x - n), R = std::min(x, n);
        while (L < R) {
            int s = (L + R + 1) / 2;
            debug(L, R, s, a_pref[s], b_pref[x - s]);
            if (a_pref[s] <= b_pref[x - s]) {
                L = s;
            } else {
                R = s - 1;
            }
        }
        int i = L;
        int ans = std::min(a_pref[i], b_pref[x - i]);
        debug(x, i);
        debug(i, x - i);
        if (i + 1 <= n && (x - (i + 1)) >= 0) {
            ans = std::max(ans, std::min(a_pref[i + 1], b_pref[x - (i + 1)]));
        }
        if (i - 1 >= 0 && (x - (i - 1)) <= n) {
            ans = std::max(ans, std::min(a_pref[i - 1], b_pref[x - (i - 1)]));
        }

        int local_wyn = ans - (x * 10000);

        wyn = std::max(wyn, local_wyn);
    }

    printScaled(wyn);
    putchar_unlocked('\n');
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}

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