oj.uz

Submission #786964

# Submission time Handle Problem Language Result Execution time Memory
786964 2023-07-18T15:46:45 Z sadsa Rice Hub (IOI11_ricehub) C++17
17 / 100
 1000 ms 26032 KB 
#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = long long;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

int besthub(int R, int L, int XCa[], long long B) {
    vi X(XCa, XCa + R);
    vi hub_count(L+2);

    for (auto Xi : X) {
        ++hub_count[Xi];
    }

    vi lreward(L+2);
    vl lcost(L+2);
    for (int i = 1; i <= L; ++i) {
        lreward[i] = lreward[i-1] + hub_count[i];
        lcost[i] = lcost[i-1] + lreward[i-1];
    }

    vi rreward(L+2);
    vl rcost(L+2);
    for (int i = L; i >= 1; --i) {
        rreward[i] = rreward[i+1] + hub_count[i];
        rcost[i] = rcost[i+1] + rreward[i+1];
    }

    DBG(X);
    DBG("left:");
    DBG(lreward);
    DBG(lcost);
    DBG("right:");
    DBG(rreward);
    DBG(rcost);

    auto lquery = [&] (int Xm, int Xl) {
        i64 dist = Xm-Xl;
        i64 maxcost = lcost[Xm] - lcost[Xl] - dist*lreward[Xl-1];
        return pair{lreward[Xm]-lreward[Xl-1], maxcost};
    };

    auto rquery = [&] (int Xm, int Xr) {
        i64 dist = Xr-Xm;
        i64 maxcost = rcost[Xm] - rcost[Xr] - dist * rreward[Xr+1];
        return pair{rreward[Xm]-rreward[Xr+1], maxcost};
    };

    auto range_query = [&] (int Xm, int Xl, int Xr) {
        auto [lr, lc] = lquery(Xm, Xl);
        auto [rr, rc] = rquery(Xm, Xr);

        if (lc + rc <= B) {
            return pair{lr+rr-hub_count[Xm], lc+rc};
        } else {
            int ldist = Xm-Xl;
            int rdist = Xr-Xm;
            return pair{int(), B+1};
        }

    };

    int xbeg = X.front();
    int xend = X.back();

    int ans = 0;
    for (int xl = xbeg; xl <= xend; ++xl) if (hub_count[xl]) {
        for (int xr = xl; xr <= xend; ++xr) if (hub_count[xr]) {
            for (int x = xl; x <= xr; ++x) {
                auto [reward, cost] = range_query(x, xl, xr);
                if (cost <= B) {
                    if (reward > ans) {
                        DBG("pos:", x, xl, xr);
                        DBG("rice+cost:", reward, cost);
                        ans = reward;
                    }
                } else {
                    //xr = xend;
                    //break;
                }
            }
        }
    }

    return ans;
}

Compilation message

ricehub.cpp: In lambda function:
ricehub.cpp:89:17: warning: unused variable 'ldist' [-Wunused-variable]
   89 |             int ldist = Xm-Xl;
      |                 ^~~~~
ricehub.cpp:90:17: warning: unused variable 'rdist' [-Wunused-variable]
   90 |             int rdist = Xr-Xm;
      |                 ^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 468 KB Output is correct
2 Correct 62 ms 468 KB Output is correct
3 Execution timed out 1074 ms 26032 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 3156 KB Time limit exceeded
2 Halted 0 ms 0 KB -