Submission #438643

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
438643	2021-06-28 10:56:52	fleimgruber	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	7115 ms	737016 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
// this solves subtask 1, 3, 4, 5. the complexity is alright,
// but for larger n we get MLE. instead of binary lifting, we
// should probably use some other base, HLD, those linear jump pointers..
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50001; // subtasks 1, 3, 4, 5
const int MAX_LOG = 25; // 2^24 > 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 {
  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];
// because p[i] = s[i], every time we lose, our strength doubles
struct Subtask2 {
  struct {
    int end;
    long long gained;
    long long min; // min(sum(gained) - opponent)
  } dp[400001][MAX_LOG];
  int l[400001];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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