Submission #490958

#	Time	Username	Problem	Language	Result	Execution time	Memory
490958		TranGiaHuy1508	Sure Bet (CEOI17_sure)	C++17	100 / 100	118 ms	5164 KiB

sure

// C++ Template

#include "bits/stdc++.h"
using namespace std;

// Type
typedef long long ll;
typedef long double ld;

// Pair/Vector
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

// Priority Queue
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

// Macro
#define stat(x) (x) && cout << "YES\n" || cout << "NO\n";
#ifdef LOCAL
    #define debug(x) cout << #x << " = " << x << "\n";
#else
    #define debug(x) ;
#endif

// Custom output
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
    out << "(" << x.first << ", " << x.second << ")";
    return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> x){
    out << "[";
    for (int i=0; i<x.size(); i++){
        if (i) out << ", ";
        out << x[i];
    }
    out << "]";
    return out;
}

void fastio(string finp = "", string fout = ""){
    if (fopen(finp.c_str(), "r")){
        freopen(finp.c_str(), "r", stdin);
        freopen(fout.c_str(), "w", stdout);
    }
}

// Const
const int interactive = 0;
const ld PI = acos(-1.0);
const ll allmod[2] = {int(1e9)+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const ld ldinf = 1e12;
const int multitest = 0;
#define mid ((l+r)/2)

#define int long long

vector<ld> a, b, val;
int n;
ld sm = 0.0;

// int it = 0;

pair<ld, ld> get(int x){
	if (x > n) return {-ldinf, ldinf};
	else return {sm-x, val[x]};
}

void main_program(){
    cin >> n;
    a.assign(n+1, 0.0);
    b.assign(n+1, 0.0);
    val.assign(n+1, 0.0);

    for (int i=1; i<=n; i++) cin >> a[i] >> b[i];

    sort(a.begin()+1, a.end(), greater<ld>());
	sort(b.begin()+1, b.end(), greater<ld>());

	for (int i=1; i<=n; i++) val[i] = val[i-1] + b[i] - 1;

	debug(a); debug(b); debug(val);

	ld res = 0.0;

	for (int cnt = 0; cnt <= n; cnt++){
		sm += a[cnt];

		int l = 0, r = n;
		while (r - l > 1){
			debug(l); debug(r); debug(cnt);
			// it++; if (it >= 200) return;

			// ld vala, valb;
			// tie(vala, valb) = get(mid);
			pair<ld, ld> k = get(mid);

			// debug(vala); debug(valb);

			if (k.first < k.second) r = mid;
			else l = mid;
		}

		debug(l); debug(r); debug(cnt);

		res = max(res, max(min(get(l).first, get(l).second), min(get(r).first, get(r).second)) - cnt);
	}

	cout << fixed << setprecision(4) << res;
}

void pre_main(){
    
}

signed main(){

    #ifdef LOCAL
        auto start_time = chrono::high_resolution_clock::now();
    #endif

    if (!interactive) {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
    #ifndef ONLINE_JUDGE
        fastio(".inp", ".out");
    #endif

    int t = 1;
    if (multitest) cin >> t;
    pre_main();
    while (t--) main_program();

    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        cout << "\n[" << duration << "ms]\n";
    #endif
}

Compilation message (stderr)

sure.cpp: In function 'void fastio(std::string, std::string)':
sure.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(finp.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sure.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(fout.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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