Submission #438653

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
438653	2021-06-28 11:10:34	fleimgruber	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7076 ms	738316 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 = 400001;
const int MAX_LOG = 25; // 2^24 > 10^7
int n, s[MAX_N], p[MAX_N], w[MAX_N], l[MAX_N];
// MLE for other subtasks. probably requires smarter jump pointers
struct Subtask1345 {
  // 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 {
    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[50001][MAX_LOG][MAX_LOG];
  Subtask1345() {
    for (int j = 0; j < MAX_LOG; j++)
      for (int i = 0; i <= n; i++)
        for (int k = 0; k < MAX_LOG; k++) {
          auto& x = dp[i][j][k];
          if (j == 0)
            if (i == n) {
              x.end = n;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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