Submission #682071

#	Time	Username	Problem	Language	Result	Execution time	Memory
682071		kym	Let's Win the Election (JOI22_ho_t3)	C++14	32 / 100	1117 ms	4436 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define intd long double
#define debug(x) cout << '|' << x << '|' << '\n';
#define debug2(x, y) cout << x << " | " << y << '\n';
#define debug3(x, y, z) cout << x << " | " << y << " | " << z << '\n';

deque<pair<int, int>> v;
intd memo[510][510];
vector<int> precomp;
int N, K, intendedA;

intd dp(int idx, int sizeOfA) {
    if (memo[idx][sizeOfA] != 0) return memo[idx][sizeOfA];
    if (idx == N) return (sizeOfA == intendedA ? 0 : 1e18);
    intd res = 1e18;
    int sizeOfB = K - intendedA + 1;
    
    if (sizeOfA == intendedA && sizeOfB == 1) return 0;

    // take B
    if (idx < v.size() && v[idx].first != -1) {
        if (idx - sizeOfA + 1 >= sizeOfB) {
            res = min(res, dp(idx + 1, sizeOfA));
            // cout << idx << " " << sizeOfA << " " << "DON'T TAKE ANYTHING: " << dp(idx + 1, sizeOfA) << endl;
        }
        else {
            res = min(res, dp(idx + 1, sizeOfA) + (intd)v[idx].first / (intd)(idx - sizeOfA + 1));
            // cout << idx << " " << sizeOfA << " " << "TAKE B: " << dp(idx + 1, sizeOfA) + (intd)v[idx].first / (intd)(idx - sizeOfA + 1) << endl;
        }
    }
    // take A
    if (idx < v.size() && sizeOfA < intendedA) {
        res = min(res, dp(idx + 1, sizeOfA + 1) + (intd)v[idx].second / (intd)sizeOfB);
        // cout << idx << " " << sizeOfA << " " << "TAKE A: " << dp(idx + 1, sizeOfA + 1) + (intd)v[idx].second / (intd)sizeOfB << endl;
    }
    // take remainder of A
    if (sizeOfA < intendedA && intendedA - sizeOfA - 1 < precomp.size() && (idx - sizeOfA) >= sizeOfB - 1) {
        res = min(res, (intd)precomp[intendedA - sizeOfA - 1] / (intd)sizeOfB);
        // cout << idx << " " << sizeOfA << " TAKE REMAINDER OF A: " << (intd)precomp[intendedA - sizeOfA - 1] / (intd)sizeOfB << endl;
    }

    memo[idx][sizeOfA] = res;
    return res;
}

bool cmp(pair<int, int> a, pair<int, int> b) {
    if ((a.first == -1 && b.first == -1) || (a.first != -1 && b.first != -1)) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    }
    if (b.first == -1) return true;
    return false;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int A, B;
        cin >> A >> B;
        v.push_back(make_pair(B, A));
    }
    sort(v.begin(), v.end(), cmp);
    // for (auto i : v) cout << i.first << " " << i.second << endl;
    for (int i = 0; i < N; i++) {
        if (v[i].first == -1) {
            if (precomp.empty()) precomp.push_back(v[i].second);
            else precomp.push_back(precomp.back() + v[i].second);
        }
    }
    for (int i = N - 1; i >= 0; i--) {
        if (v[i].first == -1) v.pop_back();
    }
    // for (auto i : precomp) cout << i << endl;
    cout << fixed << setprecision(15);

    intd res = 1e18;
    for (int i = 0; i <= K; i++) {
        intendedA = i;
        memset(memo, 0, sizeof memo);
        // cout << intendedA << endl;
        res = min(res, dp(0, 0));
    }
    cout << res;
}

Compilation message (stderr)

Main.cpp: In function 'long double dp(long long int, long long int)':
Main.cpp:23:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if (idx < v.size() && v[idx].first != -1) {
      |         ~~~~^~~~~~~~~~
Main.cpp:34:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if (idx < v.size() && sizeOfA < intendedA) {
      |         ~~~~^~~~~~~~~~
Main.cpp:39:56: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if (sizeOfA < intendedA && intendedA - sizeOfA - 1 < precomp.size() && (idx - sizeOfA) >= sizeOfB - 1) {
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23