Submission #438593

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
438593	2021-06-28 09:29:59	fleimgruber	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	2887 ms	738520 KiB

dungeons

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 "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50001; // subtasks 1, 3, 4, 5
// 2^24 > 10^7
const int MAX_LOG = 25; // ~log_2(10^7)
// dp[i][j][k] = we're at i, simulate for 2^j steps and
// win against an opponent if strength < 2^k (we don't gain strength)
struct DP {
  int end; // where do we end up at?
  long long gained; // total strength gained on the path
  // max(sum(gained) - opponent) along the simulation,
  // for all opponents we lose against
  long long max;
} dp[MAX_N][MAX_LOG][MAX_LOG];
int n, s[MAX_N], w[MAX_N];
void init(int n_, vector<int> s_, vector<int> p,
    vector<int> w_, vector<int> l) {
  n = n_;
  for (int i = 0; i < n; i++) {
    s[i] = s_[i];
    w[i] = w_[i];
  }
  w[n] = n;
  for (int j = 0; j < MAX_LOG; j++)
    for (int i = 0; i <= n; i++)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11