Submission #224804

#TimeUsernameProblemLanguageResultExecution timeMemory
224804Haunted_CppVisiting Singapore (NOI20_visitingsingapore)C++17
100 / 100
701 ms760 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]]);
          }
          // 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);
          // 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 = 1; j < m; j++) {
      for (int x = 0; x < 2; x++) {
        for (int y = 0; y < 2; y++) {
          mn = max (mn, nxt[m][x][y]);
          cur[j][x][y] = nxt[j][x][y];
          nxt[j][x][y] = -1e9;
          mn = max (mn, cur[m][x][y]);
        }   
      }
    }
  }
  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...