Submission #464538

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
464538	2021-08-13 11:18:16	amunduzbaev	Game (eJOI20_game)	C++14	100 / 100	6 ms	972 KiB

game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
using namespace std;
const int N = 25;
vector<int> edges[N*N], cycle, path;
int used[N*N], cntv, cnte;
map<array<int, 4>, int> mem;
//~ 0 cycle
//~ 1 path
//~      cycle, path, left for us, type
int rec(int i, int j, int left, int t){
  //~ cout<<i<<" "<<j<<" "<<left<<" "<<t<<"\n";
  if(i + 1 == (int)cycle.size() && j + 1 == (int)path.size()) return left;
  if(mem.count({i, j, left, t})) return mem[{i, j, left, t}];
  int& res = mem[{i, j, left, t}];
  res = -(1e9+7);
  
  if(t == 0 && left >= 4){
    res = max(res, left - 4 - rec(i, j, 4, -1));
  } if(t == 1 && left > 2){
    res = max(res, left - 2 - rec(i, j, 2, -1));
  }
  
  if(i + 1 < (int)cycle.size()){
    res = max(res, left - rec(i + 1, j, cycle[i + 1], 0));
  } if(j + 1 < (int)path.size()){
    res = max(res, left - rec(i, j + 1, path[j + 1], 1));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20