oj.uz

Submission #224765

# Submission time Handle Problem Language Result Execution time Memory
224765 2020-04-18T18:33:08 Z Haunted_Cpp Visiting Singapore (NOI20_visitingsingapore) C++17
29 / 100
 1039 ms 197112 KB 
#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 dp [N][N][2];

int k, n, m, a, b;

int felicidade_evento [N];
int dia_evento [N];
int tarefas [N];

int solve (int p, int task, bool is_skip) {
  if (task >= m) {
    return 0;
  }
  
  if (p >= n) {
    if (!is_skip) {
      return ( a + (m - task) * b);
    } else {
      return ( (m - task) * b );
    }
  }
  
  int &res = dp[p][task][is_skip];
  if (~res) return res;
  res = -1e9;
  

  if (tarefas[task] == dia_evento[p]) {
    res = max (res, felicidade_evento[tarefas[task]] + solve (p + 1, task + 1, false));
  } else {
    if (is_skip == false) {
      res = max (res, a + b + solve (p, task + 1, true));
      res = max (res, a + b + solve (p + 1, task, true));
    } else {
      res = max (res, b + solve (p, task + 1, true));
      res = max (res, a + b + solve (p + 1, task, true));
    }
  }
  return res;
}

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];
  memset (dp, -1, sizeof(dp));
  int mn = -1e9;
  for (int i = 0; i < n; i++) {
    mn = max (mn, solve (i, 0, false));
  }
  cout << mn << '\n';
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 196472 KB Output is correct
2 Correct 98 ms 196472 KB Output is correct
3 Correct 95 ms 196344 KB Output is correct
4 Correct 91 ms 196472 KB Output is correct
5 Correct 95 ms 196480 KB Output is correct
6 Correct 102 ms 196472 KB Output is correct
7 Correct 94 ms 196472 KB Output is correct
8 Correct 95 ms 196472 KB Output is correct
9 Correct 101 ms 196472 KB Output is correct
10 Correct 99 ms 196600 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 196472 KB Output is correct
2 Correct 95 ms 196472 KB Output is correct
3 Correct 103 ms 196472 KB Output is correct
4 Correct 93 ms 196472 KB Output is correct
5 Correct 96 ms 196472 KB Output is correct
6 Correct 95 ms 196472 KB Output is correct
7 Correct 95 ms 196472 KB Output is correct
8 Correct 99 ms 196460 KB Output is correct
9 Correct 97 ms 196472 KB Output is correct
10 Correct 100 ms 196600 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 196600 KB Output is correct
2 Correct 119 ms 196600 KB Output is correct
3 Correct 267 ms 196984 KB Output is correct
4 Correct 622 ms 196996 KB Output is correct
5 Correct 200 ms 196728 KB Output is correct
6 Correct 287 ms 196728 KB Output is correct
7 Correct 514 ms 196984 KB Output is correct
8 Correct 237 ms 196728 KB Output is correct
9 Correct 371 ms 196856 KB Output is correct
10 Correct 735 ms 197048 KB Output is correct
11 Correct 744 ms 196984 KB Output is correct
12 Correct 858 ms 197020 KB Output is correct
13 Correct 1033 ms 196984 KB Output is correct
14 Correct 401 ms 196860 KB Output is correct
15 Correct 396 ms 196856 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 196600 KB Output is correct
2 Correct 119 ms 196600 KB Output is correct
3 Correct 267 ms 196984 KB Output is correct
4 Correct 622 ms 196996 KB Output is correct
5 Correct 200 ms 196728 KB Output is correct
6 Correct 287 ms 196728 KB Output is correct
7 Correct 514 ms 196984 KB Output is correct
8 Correct 237 ms 196728 KB Output is correct
9 Correct 371 ms 196856 KB Output is correct
10 Correct 735 ms 197048 KB Output is correct
11 Correct 744 ms 196984 KB Output is correct
12 Correct 858 ms 197020 KB Output is correct
13 Correct 1033 ms 196984 KB Output is correct
14 Correct 401 ms 196860 KB Output is correct
15 Correct 396 ms 196856 KB Output is correct
16 Correct 468 ms 196856 KB Output is correct
17 Correct 561 ms 196984 KB Output is correct
18 Correct 481 ms 196984 KB Output is correct
19 Correct 153 ms 196712 KB Output is correct
20 Correct 326 ms 196820 KB Output is correct
21 Correct 113 ms 196600 KB Output is correct
22 Correct 161 ms 196724 KB Output is correct
23 Correct 251 ms 196728 KB Output is correct
24 Correct 165 ms 196600 KB Output is correct
25 Correct 758 ms 197064 KB Output is correct
26 Correct 756 ms 197024 KB Output is correct
27 Correct 670 ms 196988 KB Output is correct
28 Correct 1039 ms 197112 KB Output is correct
29 Correct 407 ms 196856 KB Output is correct
30 Correct 393 ms 196728 KB Output is correct

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 196600 KB Output is correct
2 Correct 119 ms 196600 KB Output is correct
3 Correct 267 ms 196984 KB Output is correct
4 Correct 622 ms 196996 KB Output is correct
5 Correct 200 ms 196728 KB Output is correct
6 Correct 287 ms 196728 KB Output is correct
7 Correct 514 ms 196984 KB Output is correct
8 Correct 237 ms 196728 KB Output is correct
9 Correct 371 ms 196856 KB Output is correct
10 Correct 735 ms 197048 KB Output is correct
11 Correct 744 ms 196984 KB Output is correct
12 Correct 858 ms 197020 KB Output is correct
13 Correct 1033 ms 196984 KB Output is correct
14 Correct 401 ms 196860 KB Output is correct
15 Correct 396 ms 196856 KB Output is correct
16 Incorrect 565 ms 196984 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 196600 KB Output is correct
2 Incorrect 98 ms 196424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 196472 KB Output is correct
2 Correct 98 ms 196472 KB Output is correct
3 Correct 95 ms 196344 KB Output is correct
4 Correct 91 ms 196472 KB Output is correct
5 Correct 95 ms 196480 KB Output is correct
6 Correct 102 ms 196472 KB Output is correct
7 Correct 94 ms 196472 KB Output is correct
8 Correct 95 ms 196472 KB Output is correct
9 Correct 101 ms 196472 KB Output is correct
10 Correct 99 ms 196600 KB Output is correct
11 Correct 95 ms 196472 KB Output is correct
12 Correct 95 ms 196472 KB Output is correct
13 Correct 103 ms 196472 KB Output is correct
14 Correct 93 ms 196472 KB Output is correct
15 Correct 96 ms 196472 KB Output is correct
16 Correct 95 ms 196472 KB Output is correct
17 Correct 95 ms 196472 KB Output is correct
18 Correct 99 ms 196460 KB Output is correct
19 Correct 97 ms 196472 KB Output is correct
20 Correct 100 ms 196600 KB Output is correct
21 Correct 150 ms 196600 KB Output is correct
22 Correct 119 ms 196600 KB Output is correct
23 Correct 267 ms 196984 KB Output is correct
24 Correct 622 ms 196996 KB Output is correct
25 Correct 200 ms 196728 KB Output is correct
26 Correct 287 ms 196728 KB Output is correct
27 Correct 514 ms 196984 KB Output is correct
28 Correct 237 ms 196728 KB Output is correct
29 Correct 371 ms 196856 KB Output is correct
30 Correct 735 ms 197048 KB Output is correct
31 Correct 744 ms 196984 KB Output is correct
32 Correct 858 ms 197020 KB Output is correct
33 Correct 1033 ms 196984 KB Output is correct
34 Correct 401 ms 196860 KB Output is correct
35 Correct 396 ms 196856 KB Output is correct
36 Correct 468 ms 196856 KB Output is correct
37 Correct 561 ms 196984 KB Output is correct
38 Correct 481 ms 196984 KB Output is correct
39 Correct 153 ms 196712 KB Output is correct
40 Correct 326 ms 196820 KB Output is correct
41 Correct 113 ms 196600 KB Output is correct
42 Correct 161 ms 196724 KB Output is correct
43 Correct 251 ms 196728 KB Output is correct
44 Correct 165 ms 196600 KB Output is correct
45 Correct 758 ms 197064 KB Output is correct
46 Correct 756 ms 197024 KB Output is correct
47 Correct 670 ms 196988 KB Output is correct
48 Correct 1039 ms 197112 KB Output is correct
49 Correct 407 ms 196856 KB Output is correct
50 Correct 393 ms 196728 KB Output is correct
51 Incorrect 565 ms 196984 KB Output isn't correct
52 Halted 0 ms 0 KB -