oj.uz

Submission #106698

# Submission time Handle Problem Language Result Execution time Memory
106698 2019-04-19T18:04:25 Z Frankenween Sure Bet (CEOI17_sure) C++17
100 / 100
 65 ms 4092 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define ull unsigned long long
#define pll pair<ll, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define deb(x) cout << #x << " = " << x << endl
#define all(x) x.begin(), x.end()
#define ld long double
const ll mod = (ll)1e9 + 7;
const ll BASE = 47;
const ll inf = (ll)1e18;
const long double e = 2.718281828459;
const long double pi = 3.141592653;
const ld EPS = 1e-9;


using namespace std;


template <class T>
istream& operator>>(istream &in, vector<T> &arr) {
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};


ll get_val(string s) {
    string real, fr;
    int i = 0;
    while (i < s.size() and s[i] != '.') {
        real.pb(s[i]);
        i++;
    }
    i++;
    while (i < s.size()) {
        fr.pb(s[i]);
        i++;
    }
    while (fr.size() < 4) {
        fr.pb('0');
    }
    real += fr;
    return stoll(real);
}


void solve() {
    ll n;
    cin >> n;
    vector<ll> a, b;
    for (int i = 0; i < n; i++) {
        string sa, sb;
        cin >> sa >> sb;
        a.pb(get_val(sa));
        b.pb(get_val(sb));
    }
    sort(all(a));
    sort(all(b));
    ll cost = 10000;
    ll answer = 0;
    ll sum_a = 0, sum_b = 0, pay = 0;
    while (!a.empty() or !b.empty()) {
        if (a.empty()) {
            sum_b += b.back();
            b.pop_back();
            pay++;
        } else if (b.empty()) {
            sum_a += a.back();
            a.pop_back();
            pay++;
        } else {
            if (sum_a < sum_b) {
                sum_a += a.back();
                a.pop_back();
                pay++;
            } else {
                sum_b += b.back();
                b.pop_back();
                pay++;
            }
        }
        answer = max(answer, min(sum_a, sum_b) - pay * cost);
    }
    string real, fr;
    string ans = to_string(answer);
    int sz = ans.size();
    for (int i = 0; i < min(4, sz); i++) {
        fr.push_back(ans.back());
        ans.pop_back();
    }
    while (fr.size() != 4) {
        fr.push_back('0');
    }
    reverse(all(fr));
    if (ans.empty()) {
        ans = "0";
    }
    cout << ans + "." + fr;
}


int main() {
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout.precision(30);
    ll seed = time(0);
    //cerr << "Seed: " << seed << "\n";
    srand(seed);
    solve();
    return 0;
}

Compilation message

sure.cpp: In function 'long long int get_val(std::__cxx11::string)':
sure.cpp:37:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < s.size() and s[i] != '.') {
            ~~^~~~~~~~~~
sure.cpp:42:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i < s.size()) {
            ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 300 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 46 ms 3560 KB Output is correct
18 Correct 59 ms 3552 KB Output is correct
19 Correct 48 ms 3556 KB Output is correct
20 Correct 45 ms 3556 KB Output is correct
21 Correct 52 ms 4092 KB Output is correct
22 Correct 49 ms 3560 KB Output is correct
23 Correct 50 ms 3552 KB Output is correct
24 Correct 55 ms 3556 KB Output is correct
25 Correct 50 ms 3556 KB Output is correct
26 Correct 65 ms 3900 KB Output is correct