Submission #530542

#	Time	Username	Problem	Language	Result	Execution time	Memory
530542		LFFB	Hotel (CEOI11_hot)	C++14	40 / 100	8 ms	10420 KiB

hot

#include <iostream>
#include <algorithm>

#define debug(args...) //printf(args)

typedef long long llong;

const int MAX_N = 100 + 10;
const llong INF = 1000000000000000000;

int n, m, o;

std::pair<int, int> rooms[MAX_N]; // (upkeep, capacity)
std::pair<int, int> offers[MAX_N]; // (pay, demand)

bool  isStored[MAX_N][MAX_N][MAX_N];
llong storedDP[MAX_N][MAX_N][MAX_N];

void setMax(llong& a, llong b) {
    a = std::max(a, b);
}
void setMin(int& a, int b) {
    a = std::min(a, b);
}

// dp[i][j][k] = max profit with only first i room and first j offer with at max k accepted offer
llong dp(int room, int offer, int accept) {

    if (accept == 0) return 0;
    if (offer == -1) return 0;
    if (room == -1) return 0;

    setMin(accept, offer + 1);

    if (isStored[room][offer][accept]) return storedDP[room][offer][accept];

    llong answer = 0;

    setMax(answer, dp(room - 1, offer, accept));
    setMax(answer, dp(room, offer - 1, accept));
    if (rooms[room].second >= offers[offer].second) {
        debug("capacity of %d > demand of %d\n", room, offer);
        setMax(answer, dp(room - 1, offer - 1, accept - 1) + offers[offer].first - rooms[room].first);
    }

    isStored[room][offer][accept] = true;
    storedDP[room][offer][accept] = answer;
    debug("dp[%d][%d][%d] = %lld\n", room, offer, accept, answer);
    return answer;

}

bool sortingFunction(std::pair<int, int> a, std::pair<int, int> b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first < b.first;
}

int main() {

    scanf("%d %d %d", &n, &m, &o);

    for (int i = 0; i < n; i++) {
        scanf("%d %d", &rooms[i].first, &rooms[i].second);
    }

    for (int i = 0; i < m; i++) {
        scanf("%d %d", &offers[i].first, &offers[i].second);
    }

    std::sort(rooms, rooms + n, sortingFunction);
    std::sort(offers, offers + m, sortingFunction);

    llong answer = dp(n - 1, m - 1, o);

    printf("%lld\n", answer);

}

Compilation message (stderr)

hot.cpp: In function 'int main()':
hot.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d %d %d", &n, &m, &o);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d %d", &rooms[i].first, &rooms[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d %d", &offers[i].first, &offers[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10