oj.uz

Submission #709674

# Submission time Handle Problem Language Result Execution time Memory
709674 2023-03-14T07:19:52 Z ktkerem Sure Bet (CEOI17_sure) C++17
100 / 100
 136 ms 11696 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 1e6;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
    return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n;
std::vector<std::pair<ld,ld>> ar;
/**/
/*functions*/
/**/
void solve(){
    std::cin >> n;
    ar.resize(n);
    std::vector<ld> fa , fb , pfa , pfb;
    for(ll i=0;n>i;i++){
        std::cin >> ar[i].fi >> ar[i].sec;
        if(ar[i].fi >= 1.0){
            fa.pb(ar[i].fi);
        }
        if(ar[i].sec >= 1.0){
            fb.pb(ar[i].sec);
        }
    }
    if(fa.size() == 0 || fb.size() == 0){
        std::cout << 0 << "\n";
        return;
    }
    ld ans = 0;
    //std::cout << fa.size() << std::endl;
    std::sort(fa.begin() , fa.end());
    std::sort(fb.begin() , fb.end());
    std::reverse(all(fa));
    std::reverse(all(fb));
    pfa.resize(fa.size());
    pfb.resize(fb.size());
    pfa[0] = fa[0] - 1;
    pfb[0] = fb[0] - 1;
    for(ll i = 1;fa.size() > i;i++){
        pfa[i] += fa[i] + pfa[i-1] -1;
    }
    for(ll i = 1;fb.size() > i;i++){
        pfb[i] += fb[i] + pfb[i-1] -1;
    }
    ld ba = 0;
    for(ll i = 0;fa.size()>i;i++){
        ba += fa[i] - 1;
        ll l = 0 , r = (ll)fb.size() - 1; 
        while(r > l){
            ll md = (l + r + 1)/2;
            if(pfb[md] - (i+1) > ba - (md+1)){
                r = md-1;
            }
            else{
                l = md;
            }
        }
        if(pfb[l] - (i+1) > ba - (l+1)){
            continue;
        }
        ans = std::max(ans , pfb[l] - (i+1));
    }
    ba = 0;
    for(ll i = 0;fb.size()>i;i++){
        ba += fb[i] - 1;
        ll l = 0 , r = (ll)fa.size() - 1; 
        while(r > l){
            ll md = (l + r + 1)/2;
            if(pfa[md] - (i+1) > ba - (md+1)){
                r = md-1;
            }
            else{
                l = md;
            }
        }
        if(pfa[l] - (i+1) > ba - (l+1)){
            continue;
        }
        ans = std::max(ans , pfa[l] - (i+1));
    }
    std::cout << std::setprecision(4) << std::fixed;
    std::cout << ans;
    return;/**/
}
int main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    /*#ifndef ONLINE_JUDGE
        freopen("in.txt" , "r" , stdin);
        freopen("out.txt" , "w" , stdout);
    #endif*/
    ll t = 1;
    //std::cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

sure.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
sure.cpp: In function 'void solve()':
sure.cpp:54:28: warning: comparison of integer expressions of different signedness: 'std::vector<long double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   54 |     for(ll i = 1;fa.size() > i;i++){
      |                  ~~~~~~~~~~^~~
sure.cpp:57:28: warning: comparison of integer expressions of different signedness: 'std::vector<long double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   57 |     for(ll i = 1;fb.size() > i;i++){
      |                  ~~~~~~~~~~^~~
sure.cpp:61:27: warning: comparison of integer expressions of different signedness: 'std::vector<long double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   61 |     for(ll i = 0;fa.size()>i;i++){
      |                  ~~~~~~~~~^~
sure.cpp:79:27: warning: comparison of integer expressions of different signedness: 'std::vector<long double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   79 |     for(ll i = 0;fb.size()>i;i++){
      |                  ~~~~~~~~~^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 121 ms 11236 KB Output is correct
18 Correct 115 ms 11224 KB Output is correct
19 Correct 136 ms 11272 KB Output is correct
20 Correct 113 ms 11216 KB Output is correct
21 Correct 110 ms 11696 KB Output is correct
22 Correct 110 ms 11316 KB Output is correct
23 Correct 115 ms 11320 KB Output is correct
24 Correct 128 ms 11320 KB Output is correct
25 Correct 106 ms 11324 KB Output is correct
26 Correct 119 ms 11632 KB Output is correct