oj.uz

답안 #443088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443088 2021-07-09T16:00:03 Z ltf0501 던전 (IOI21_dungeons) C++17
13 / 100
 201 ms 129336 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int kN = 4e5 + 10;
const int kC = 25;
// subtask 1, 2, 3
int n;
vector<int> s, p, w, l;
vector<int> uni_s;
long long suf[kN];
int climb[5][kC][kN], MAX; // 0: win, 1: lose
long long max_pow[5][kC][kN], gained_pow[5][kC][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;
  w.push_back(n), s.push_back(0);
  
  for(int i = n - 1; i >= 0; i--) suf[i] = s[i] + suf[w[i]], MAX = max(MAX, s[i]);
  for(int i = 0; i <= n; i++) uni_s.push_back(s[i]);
  sort(uni_s.begin(), uni_s.end());
  uni_s.resize(unique(uni_s.begin(), uni_s.end()) - uni_s.begin());
  int m = int(uni_s.size());
  auto get_id = [&](int x) {
    return int(lower_bound(uni_s.begin(), uni_s.end(), x) - uni_s.begin());
  };

  for(int i = 0; i <= n; i++) {
    int id = get_id(s[i]);
    for(int j = 0; j < m; j++) { 
      if(j >= id) { // dp[j][][] power at least uni_s[j]
        climb[j][0][i] = w[i];
        max_pow[j][0][i] = MAX;
        gained_pow[j][0][i] = s[i];
      }
      else {
        climb[j][0][i] = l[i];
        max_pow[j][0][i] = s[i] - 1;
        gained_pow[j][0][i] = p[i];
      }
    }
  }

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

	return;
}

long long simulate(int x, int z) {
  long long res = z;
  while(x < n && res < MAX) {
    int id = upper_bound(uni_s.begin(), uni_s.end(), res) - uni_s.begin() - 1;
    //cerr << "id = " << id << '\n';
    for(int j = kC - 1; j >= 0; j--) {
      if(res > max_pow[id][j][x]) continue;
      res += gained_pow[id][j][x], x = climb[id][j][x];
    }
    //cerr << "x = " << x << ", pow = " << res << '\n';
    res += s[x], x = w[x];
  }

  res += suf[x];
  //cerr << "Finish\n";
  return res;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Runtime error 28 ms 460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 109 ms 54336 KB Output is correct
3 Correct 101 ms 54220 KB Output is correct
4 Correct 79 ms 54212 KB Output is correct
5 Correct 82 ms 54344 KB Output is correct
6 Correct 118 ms 54204 KB Output is correct
7 Correct 151 ms 54216 KB Output is correct
8 Correct 86 ms 54212 KB Output is correct
9 Correct 87 ms 54248 KB Output is correct
10 Correct 78 ms 54212 KB Output is correct
11 Correct 93 ms 54200 KB Output is correct
12 Correct 181 ms 54280 KB Output is correct
13 Correct 142 ms 54216 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 109 ms 54336 KB Output is correct
3 Correct 101 ms 54220 KB Output is correct
4 Correct 79 ms 54212 KB Output is correct
5 Correct 82 ms 54344 KB Output is correct
6 Correct 118 ms 54204 KB Output is correct
7 Correct 151 ms 54216 KB Output is correct
8 Correct 86 ms 54212 KB Output is correct
9 Correct 87 ms 54248 KB Output is correct
10 Correct 78 ms 54212 KB Output is correct
11 Correct 93 ms 54200 KB Output is correct
12 Correct 181 ms 54280 KB Output is correct
13 Correct 142 ms 54216 KB Output is correct
14 Correct 5 ms 5708 KB Output is correct
15 Correct 164 ms 104320 KB Output is correct
16 Correct 201 ms 129336 KB Output is correct
17 Runtime error 67 ms 21692 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 109 ms 54336 KB Output is correct
3 Correct 101 ms 54220 KB Output is correct
4 Correct 79 ms 54212 KB Output is correct
5 Correct 82 ms 54344 KB Output is correct
6 Correct 118 ms 54204 KB Output is correct
7 Correct 151 ms 54216 KB Output is correct
8 Correct 86 ms 54212 KB Output is correct
9 Correct 87 ms 54248 KB Output is correct
10 Correct 78 ms 54212 KB Output is correct
11 Correct 93 ms 54200 KB Output is correct
12 Correct 181 ms 54280 KB Output is correct
13 Correct 142 ms 54216 KB Output is correct
14 Correct 5 ms 5708 KB Output is correct
15 Correct 164 ms 104320 KB Output is correct
16 Correct 201 ms 129336 KB Output is correct
17 Runtime error 67 ms 21692 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -