Submission #224799

#TimeUsernameProblemLanguageResultExecution timeMemory
224799Haunted_CppVisiting Singapore (NOI20_visitingsingapore)C++17
23 / 100
281 ms640 KiB
#include <iostream> #include <vector> #include <algorithm> #include <bitset> #include <cassert> #include <cstring> typedef long long i64; using namespace std; const int N = 5e3 + 5; int cur [N][2][2]; int nxt [N][2][2]; int k, n, m, a, b; int felicidade_evento [N]; int dia_evento [N]; int tarefas [N]; int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> k >> n >> m >> a >> b; for (int i = 1; i <= k; i++) cin >> felicidade_evento[i]; for (int i = 0; i < n; i++) cin >> dia_evento[i]; for (int i = 0; i < m; i++) cin >> tarefas[i]; for (int j = 0; j < N; j++) { nxt[j][0][0] = cur[j][0][0] = -1e9; nxt[j][0][1] = cur[j][0][1] = -1e9; nxt[j][1][0] = cur[j][1][0] = -1e9; nxt[j][1][1] = cur[j][1][1] = -1e9; } cur[0][0][0] = nxt[0][0][0] = 0; // Day / Task / Jump Task / Jump day int mn = a + (m * b); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { if (tarefas[j] == dia_evento[i]) { nxt[j + 1][0][0] = max (nxt[j + 1][0][0], cur[j][x][y] + felicidade_evento[tarefas[j]]); } } } for (int x = 0; x < 2; x++) { // Start to jump task cur[j + 1][1][x] = max (cur[j + 1][1][x], cur[j][0][x] + a + b); // Continue to jump task cur[j + 1][1][x] = max (cur[j + 1][1][x], cur[j][1][x] + b); } for (int x = 0; x < 2; x++) { // Start to jump day nxt[j][x][1] = max (nxt[j][x][1], cur[j][x][0] + a + b); // Continue to jump day nxt[j][x][1] = max (nxt[j][x][1], cur[j][x][1] + b); } } for (int j = 0; j < m; j++) { for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { cur[j][x][y] = nxt[j][x][y]; mn = max (mn, cur[m][x][y]); mn = max (mn, nxt[m][x][y]); } } } for (int j = 0; j < N; j++) { for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { nxt[j][0][0] = -1e9; nxt[j][0][1] = -1e9; nxt[j][1][0] = -1e9; nxt[j][1][1] = -1e9; } } } cur[0][0][0] = 0; nxt[0][0][0] = 0; } cout << mn << '\n'; 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...