oj.uz

Submission #530542

# Submission time Handle Problem Language Result Execution time Memory
530542 2022-02-25T18:55:44 Z LFFB Hotel (CEOI11_hot) C++14
40 / 100
 8 ms 10420 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6732 KB Output is correct
2 Correct 2 ms 5152 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10188 KB Output is correct
2 Correct 8 ms 10420 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 560 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 444 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -