Решите задачу на C++ пожалуйста

Question

Решите задачу на C++ пожалуйста

Влад Иванов Ученик (93), на голосовании 5 месяцев назад

В ресторане собираются N посетителей. Посетитель с номером i, имеющий сумму денег Pi и полноту Si,
подходит к двери ресторана во время Ti. Входная дверь ресторана имеет K состояний открытости.
Состояние открытости двери может изменяться на одну единицу за единицу времени: дверь открывается
на единицу или остается в том же состоянии. В начальный момент времени дверь закрыта(состояние 0). Посетитель с номером i входит в ресторан только в том случае, если дверь открыта специально для него, то есть когда состояние открытости двери совпадает с его степенью полноты Si. Если в момент прихода посетителя состояние двери не совпадает с его степенью полноты, то посетитель уходит и больше не возвращается.
Ресторан работает в течение времени T.
Требуется, правильно открывая и закрывая дверь, добиться того, чтобы за время работы ресторана в нем собрались посетители, общая сумма денег у которых максимальна.

Технические требования:
Входные данные - устройство стандартного ввода.
Выходные данные - устройство стандартного вывода.
Ограничение по времени тестирования: 5 секунд на один тест.

Входные данные

В первой строке находятся значения N, K, T, разделенные пробелами (1<=N<=100,1<=K<=100;0<=T<=10000)
Во второй строке находятся времена прихода посетителей T1, T2,..., TN, разделенные пробелами
( 0<=Ti<=T, для всех i=1, 2, ..., N)
В третьей строке находятся величины суммы денег у посетителей P1, P2,..., PN, разделенные
пробелами(0<=Pi<=300, для всех i=1, 2, ..., N)).
В четвертой строке находятся значения степени полноты посетителей S1, S2,..., SN, разделенные пробелами (1<=Si<=K, для всех i=1, 2, ..., N). Все исходные данные - целые числа
Выходные данные

Выводится одно число - максимальная сумма денег у посетителей ресторана. В случае, если нельзя добиться прихода в ресторан ни одного посетителя, выходной файл должен содержать значение 0.

Answer 1

 #include  
#include  
#include  
 
struct Visitor { 
    int time; 
    int money; 
    int fullness; 
}; 
 
int maxMoney(int N, int K, int T, std::vector& times, std::vector& money, std::vector& fullness) { 
    std::vector> dp(N + 1, std::vector(K + 1, 0)); 
 
    for (int i = 1; i <= N; ++i) { 
        for (int j = 1; j <= K; ++j) { 
            if (times[i - 1] <= T && j == fullness[i - 1]) { 
                dp[i][j] = std::max(dp[i - 1][j - 1] + money[i - 1], dp[i - 1][j]); 
            } else { 
                dp[i][j] = dp[i - 1][j]; 
            } 
        } 
    } 
 
    int maxSum = 0; 
    for (int j = 1; j <= K; ++j) { 
        maxSum = std::max(maxSum, dp[N][j]); 
    } 
 
    return maxSum; 
} 
 
int main() { 
    int N, K, T; 
    std::cin >> N >> K >> T; 
 
    std::vector times(N); 
    std::vector money(N); 
    std::vector fullness(N); 
 
    for (int i = 0; i < N; ++i) { 
        std::cin >> times[i]; 
    } 
    for (int i = 0; i < N; ++i) { 
        std::cin >> money[i]; 
    } 
    for (int i = 0; i < N; ++i) { 
        std::cin >> fullness[i]; 
    } 
 
    std::cout << maxMoney(N, K, T, times, money, fullness) << std::endl; 
 
    return 0; 
}

сделано с помощью ИИ (более подробно здесь: https://habab.ru/pomoshchnik-v-napisanie-koda-na-c/ )

Answer 2

Лови:

 #include  
#include  
#include  
 
using namespace std; 
 
struct Visitor { 
    int arrivalTime; 
    int money; 
    int completeness; 
}; 
 
int main() { 
    int N, K, T; 
    cin >> N >> K >> T; 
 
    vector visitors(N); 
    for (int i = 0; i < N; ++i) { 
        cin >> visitors[i].arrivalTime; 
    } 
 
    for (int i = 0; i < N; ++i) { 
        cin >> visitors[i].money; 
    } 
 
    for (int i = 0; i < N; ++i) { 
        cin >> visitors[i].completeness; 
    } 
 
    sort(visitors.begin(), visitors.end(), [](const Visitor &a, const Visitor &b) { 
        return a.arrivalTime < b.arrivalTime; 
    }); 
 
    vector> dp(T + 1, vector(K + 1, 0)); 
 
    for (int t = 0; t <= T; ++t) { 
        for (int k = 0; k <= K; ++k) { 
            if (t > 0) { 
                dp[t][k] = dp[t - 1][k]; 
                if (k > 0) dp[t][k] = max(dp[t][k], dp[t - 1][k - 1]); 
                if (k < K) dp[t][k] = max(dp[t][k], dp[t - 1][k + 1]); 
            } 
        } 
 
        for (const auto &visitor : visitors) { 
            if (visitor.arrivalTime == t && visitor.completeness <= t) { 
                dp[t][visitor.completeness] = max(dp[t][visitor.completeness], dp[t][visitor.completeness] + visitor.money); 
            } 
        } 
    } 
 
    int maxMoney = 0; 
    for (int k = 0; k <= K; ++k) { 
        maxMoney = max(maxMoney, dp[T][k]); 
    } 
 
    cout << maxMoney << endl; 
 
    return 0; 
}