oj.uz

Submission #490958

# Submission time Handle Problem Language Result Execution time Memory
490958 2021-11-30T02:08:01 Z TranGiaHuy1508 Sure Bet (CEOI17_sure) C++17
100 / 100
 118 ms 5164 KB 
// 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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 264 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 264 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 96 ms 5112 KB Output is correct
18 Correct 118 ms 5148 KB Output is correct
19 Correct 96 ms 5068 KB Output is correct
20 Correct 101 ms 5148 KB Output is correct
21 Correct 106 ms 5164 KB Output is correct
22 Correct 94 ms 5068 KB Output is correct
23 Correct 94 ms 5148 KB Output is correct
24 Correct 97 ms 5116 KB Output is correct
25 Correct 107 ms 5068 KB Output is correct
26 Correct 110 ms 5156 KB Output is correct