Submission #224798

#	Time	Username	Problem	Language	Result	Execution time	Memory
224798		Haunted_Cpp	Visiting Singapore (NOI20_visitingsingapore)	C++17	10 / 100	243 ms	568 KiB

VisitingSingapore

#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 = -1e9;
  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 i = 0; i < n + 1; i++) {
    //mn = max ({mn, dp[i][m][0][0], dp[i][m][0][1], dp[i][m][1][1], dp[i][m][1][0]});
  }
  cout << mn << '\n';
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50