Submission #438602

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
438602	2021-06-28 09:37:07	fleimgruber	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7075 ms	737112 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 correct,
// but for larger n we get MLE. instead of binary lifting, we
// should probably use some other base..
#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 {
  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
  // it can be capped at 10^7
  int 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];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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