oj.uz

Submission #442984

# Submission time Handle Problem Language Result Execution time Memory
442984 2021-07-09T12:49:32 Z ltf0501 Dungeons Game (IOI21_dungeons) C++17
11 / 100
 7000 ms 178096 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int kN = 4e5 + 10;
// subtask 3
int n;
vector<int> s, p, w, l;
int suf[kN];
int climb[20][kN];
long long max_pow[20][kN], gained_pow[20][kN];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
  n = _n, s = _s, p = _p, w = _w, l = _l;
  
  for(int i = n - 1; i >= 0; i--) suf[i] = s[i] + suf[w[i]];
  for(int i = 0; i < n; i++) {
    climb[0][i] = l[i];
    max_pow[0][i] = s[i];
    gained_pow[0][i] = p[i];
  }
  climb[0][n] = n;

  for(int j = 1; j < 20; j++) {
    for(int i = 0; i < n; i++) {
      climb[j][i] = climb[j - 1][climb[j - 1][i]];
      max_pow[j][i] = min(max_pow[j - 1][i], max_pow[j - 1][climb[j - 1][i]] - gained_pow[j - 1][i]);
      gained_pow[j][i] = gained_pow[j - 1][i] + gained_pow[j - 1][climb[j - 1][i]];
    }
  }
	return;
}

long long simulate(int x, int z) {
  long long res = z;
  while(x < n && res < int(1e7)) {
    for(int j = 19; j >= 0; j--) {
      if(res >= max_pow[j][x]) continue;
      res += gained_pow[j][x], x = climb[j][x];
    }
    res += s[x], x = w[x];
  }
  res += suf[x];
  return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 2 ms 1612 KB Output is correct
4 Correct 36 ms 22844 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 36 ms 22852 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Execution timed out 7072 ms 178096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 89 ms 23632 KB Output is correct
3 Incorrect 78 ms 23636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 89 ms 23632 KB Output is correct
3 Incorrect 78 ms 23636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 89 ms 23632 KB Output is correct
3 Incorrect 78 ms 23636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Execution timed out 7072 ms 178096 KB Time limit exceeded
3 Halted 0 ms 0 KB -