oj.uz

Submission #904311

# Submission time Handle Problem Language Result Execution time Memory
904311 2024-01-12T03:21:43 Z nguyen31hoang08minh2003 Pareto (COCI17_pareto) C++17
80 / 80
 39 ms 3164 KB 
#include <bits/stdc++.h>

/**

    Use dynamic programing

        f(x, y, v, h)
            x:  row
            y:  column
            v:  vertical tapes currently in used
            h:  boolean indicating horizontal tape currently in used

**/

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

using namespace std;

constexpr int MAX_N = 300005;

int N;
long long sum, total;
vector<int> balances;
double maximum, A, B, a, b;

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cout.precision(9);
    cout.setf(ios::fixed, ios::floatfield);

    cin >> N;

    balances.resize(N);

    for (int &balance : balances) {
        cin >> balance;
        sum += balance;
    }

    sort(balances.rbegin(), balances.rend());

    for (int i = 0; i < N; ++i) {
        total += balances[i];
        a = (i + 1.0) / N;
        b = 1.0 * total / sum;
        if (maximize(maximum, b - a)) {
            A = a;
            B = b;
        }
    }

    cout << A * 100 << '\n' << B * 100 << '\n';

    return 0;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 13 ms 1116 KB Output is correct
7 Correct 26 ms 2396 KB Output is correct
8 Correct 39 ms 3164 KB Output is correct