oj.uz

Submission #40119

# Submission time Handle Problem Language Result Execution time Memory
40119 2018-01-27T11:29:55 Z toonewbie Sure Bet (CEOI17_sure) C++14
100 / 100
 140 ms 5304 KB 
/*
ID: usaco.t3
TASK: test
LANG: C++14
*/

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _CRT_SECURE_NO_WARNINGS
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define pii pair<intt,intt>
#define vi vector<intt>
#define vii vector<pii>

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();
#define endl '\n'

#define wtfis(x) cerr << "at line " << __LINE__ << ": " << #x << " = " << (x) << endl

const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;

const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;

const intt INF = 2LL * 1000000000;
const intt INFLL = 9LL * 1000000000 * 1000000000;
/***************/

intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

intt gcd (intt a, intt b) {
    while (b > 0) {
        intt t = a % b;
        a = b, b = t;
    }
    return a;
}

intt lcm (intt a, intt b) {
    return (a / gcd (a, b)) * b;
}

intt is_prime (intt n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (intt i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/**************************/

int n;
double arr[maxx], brr[maxx];
double pa[maxx], pb[maxx];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    IO;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i] >> brr[i];
    }
    sort (arr + 1, arr + n + 1); reverse (arr + 1, arr + n + 1);
    sort (brr + 1, brr + n + 1); reverse (brr + 1, brr + n + 1);
    for (int i = 1; i <= n; i++) {
        pa[i] = pa[i - 1] + arr[i];
        pb[i] = pb[i - 1] + brr[i];
    }
    double res = 0;
    for (int i = 0; i <= n; i++) {
        int l = 0, r = n, j;
        while (r - l >= 0) {
            int mid = (l + r) >> 1;
            if (min (pa[i] - (i + mid), pb[mid] - (i + mid)) >= min (pa[i] - (i + mid + 1), pb[mid + 1] - (i + mid + 1))) {
                j = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        res = max (res, min (pa[i] - (i + j), pb[j] - (i + j)));
    }
    cout << fixed << setprecision(4) << res << endl;
    return 0;
}

Compilation message

sure.cpp:7:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 ^
sure.cpp: In function 'long long int is_prime(long long int)':
sure.cpp:74:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
                         ^
sure.cpp: In function 'int main()':
sure.cpp:113:51: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
         res = max (res, min (pa[i] - (i + j), pb[j] - (i + j)));
                                                   ^

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5304 KB Output is correct
2 Correct 0 ms 5304 KB Output is correct
3 Correct 0 ms 5304 KB Output is correct
4 Correct 0 ms 5304 KB Output is correct
5 Correct 0 ms 5304 KB Output is correct
6 Correct 0 ms 5304 KB Output is correct
7 Correct 0 ms 5304 KB Output is correct
8 Correct 0 ms 5304 KB Output is correct
9 Correct 0 ms 5304 KB Output is correct
10 Correct 0 ms 5304 KB Output is correct
11 Correct 0 ms 5304 KB Output is correct
12 Correct 1 ms 5304 KB Output is correct
13 Correct 1 ms 5304 KB Output is correct
14 Correct 1 ms 5304 KB Output is correct
15 Correct 1 ms 5304 KB Output is correct
16 Correct 1 ms 5304 KB Output is correct
17 Correct 140 ms 5304 KB Output is correct
18 Correct 104 ms 5304 KB Output is correct
19 Correct 100 ms 5304 KB Output is correct
20 Correct 100 ms 5304 KB Output is correct
21 Correct 102 ms 5304 KB Output is correct
22 Correct 117 ms 5304 KB Output is correct
23 Correct 98 ms 5304 KB Output is correct
24 Correct 110 ms 5304 KB Output is correct
25 Correct 116 ms 5304 KB Output is correct
26 Correct 112 ms 5304 KB Output is correct