Submission #927293

#TimeUsernameProblemLanguageResultExecution timeMemory
927293boris_mihovTwo Dishes (JOI19_dishes)C++17
0 / 100
2 ms2396 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 2000 + 10; const llong INF = 1e18; int n, m; struct Dish { int time; llong limit; int reward; int idx; bool type; }; Dish a[MAXN]; Dish b[MAXN]; llong prefixA[MAXN]; llong prefixB[MAXN]; llong dp[MAXN][MAXN]; bool bl[MAXN][MAXN]; llong f(int aPos, int bPos) { if (aPos == n + 1 && bPos == m + 1) { return 0; } if (bl[aPos][bPos]) { return dp[aPos][bPos]; } bl[aPos][bPos] = true; dp[aPos][bPos] = -INF; llong sum = prefixA[aPos - 1] + prefixB[bPos - 1]; if (aPos <= n) { dp[aPos][bPos] = std::max(dp[aPos][bPos], f(aPos + 1, bPos) + (sum + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0)); } if (bPos <= m) { dp[aPos][bPos] = std::max(dp[aPos][bPos], f(aPos, bPos + 1) + (sum + b[bPos].time <= b[bPos].limit ? b[bPos].reward : 0)); } return dp[aPos][bPos]; } void solve() { for (int i = 1 ; i <= n ; ++i) { prefixA[i] = prefixA[i - 1] + a[i].time; } for (int i = 1 ; i <= n ; ++i) { prefixB[i] = prefixB[i - 1] + a[i].time; } for (int i = 1 ; i <= n ; ++i) { for (int j = 1 ; j < m ; ++j) { assert(f(i, j) >= f(i, j + 1)); // std::cout << f(i, j) << ' '; } // std::cout << '\n'; } std::cout << f(1, 1) << '\n'; } void input() { std::cin >> n >> m; for (int i = 1 ; i <= n ; ++i) { std::cin >> a[i].time >> a[i].limit >> a[i].reward; a[i].idx = i; a[i].type = false; } for (int i = 1 ; i <= m ; ++i) { std::cin >> b[i].time >> b[i].limit >> b[i].reward; b[i].idx = i; a[i].type = true; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...