oj.uz

Submission #592631

# Submission time Handle Problem Language Result Execution time Memory
592631 2022-07-09T11:39:17 Z VasLemmy Sure Bet (CEOI17_sure) C++17
60 / 100
 2000 ms 14396 KB 
/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;
using db = long double;
//#define int long long

#define ll long long
#define pdb pair<db,db>
#define fi first
#define se second
#define pb push_back

const ll mod = 1e9 + 7;
const int maxN = 5000005;

int n;
pdb a[maxN];
vector<pdb> bet2;
vector<pdb> bet1;
vector<pdb> subet2;
vector<pdb> subet1;

bool FA(pdb x,pdb y)
{
    return (x.fi > y.fi || (x.fi == y.fi && x.se > y.se));
}

void read()
{
    cout << fixed << setprecision(4);
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i].fi >> a[i].se;
        bet2.push_back({(db)-1,(db)(a[i].se-1)});
        bet1.push_back({(db)(a[i].fi-1),(db)-1});
    }
    sort(bet2.begin(),bet2.end(),FA);
    sort(bet1.begin(),bet1.end(),FA);
    /*for(pdb x : bet2)
    {
        cout << x.fi <<' '<< x.se <<'\n';
    }
    cout <<'*'<<'\n';
    for(pdb x : bet1)
    {
        cout << x.fi <<' '<< x.se <<'\n';
    }*/
    subet1.resize(bet1.size());
    for(int i = 0;i < bet1.size();i++)
    {
        if(i == 0) subet1[i] = bet1[i];
        else
        {
            subet1[i].fi = subet1[i-1].fi + bet1[i].fi;
            subet1[i].se = subet1[i-1].se + bet1[i].se;
        }
    }

    //cout <<"dark";return;
    pdb tmp = {0,0};
    db res = 0;
    for(int i = 0;i < bet2.size();i++)
    {
        tmp.fi += bet2[i].fi;
        tmp.se += bet2[i].se;
        /*int low = 0;
        int high = bet1.size() - 1;
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(tmp.fi + subet1[mid].fi <= tmp.se + subet1[mid].se)
            {
                low = mid + 1;
            }
            else high = mid - 1;
        }
        if(high >= 0 && high < bet1.size())
        {
            res = max(res,tmp.fi + subet1[high].fi);
        }
        else if(low >= 0 && low < bet1.size())
        {
            res = max(res,tmp.se + subet1[low].se);
        }*/
        for(int j = 0;j < subet1.size();j++)
        {
            res = max(res,min(subet1[j].fi + tmp.fi,subet1[j].se + tmp.se));
            //if(res == ((db)2.1886)) {cout << i <<' '<< j;return;}
            //cout << i <<' '<< j <<' '<< res <<'\n';
        }
    }
    cout << res;
}

void sol()
{

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Compilation message

sure.cpp: In function 'void read()':
sure.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0;i < bet1.size();i++)
      |                   ~~^~~~~~~~~~~~~
sure.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0;i < bet2.size();i++)
      |                   ~~^~~~~~~~~~~~~
sure.cpp:86:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int j = 0;j < subet1.size();j++)
      |                       ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 508 KB Output is correct
13 Correct 11 ms 468 KB Output is correct
14 Correct 6 ms 388 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 7 ms 596 KB Output is correct
17 Execution timed out 2071 ms 14396 KB Time limit exceeded
18 Halted 0 ms 0 KB -