結果

問題 No.9 モンスターのレベル上げ
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2015-01-27 23:16:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 199 ms / 5,000 ms
コード長 1,937 bytes
コンパイル時間 547 ms
コンパイル使用メモリ 60,348 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-06 03:25:53
合計ジャッジ時間 3,163 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 199 ms
4,380 KB
testcase_03 AC 150 ms
4,380 KB
testcase_04 AC 80 ms
4,384 KB
testcase_05 AC 53 ms
4,380 KB
testcase_06 AC 19 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 25 ms
4,380 KB
testcase_09 AC 184 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 157 ms
4,376 KB
testcase_12 AC 19 ms
4,380 KB
testcase_13 AC 123 ms
4,384 KB
testcase_14 AC 188 ms
4,376 KB
testcase_15 AC 170 ms
4,380 KB
testcase_16 AC 4 ms
4,376 KB
testcase_17 AC 109 ms
4,376 KB
testcase_18 AC 92 ms
4,380 KB
testcase_19 AC 3 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
やっていることは10107のRubyと一緒なのに、実行速度が違いすぎて泣きたい。
*/
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstring>

const int MAX_N = 1500;

int main() {
  int n, i, j, k, pos, target;
  int n1;
  int org_mon_list[MAX_N + 2];
  int mon_list[MAX_N + 2];
  int exp_list[MAX_N];
  int low_count = MAX_N;
  int max_count;

  std::cin >> n;
  n1 = n + 1;

  org_mon_list[0] = 0;
  for (i = 0; i < n; ++i) {
    std::cin >> j;
    pos = i + 1;
    org_mon_list[pos] = j * n1;
    while (pos > 1) {
      if (org_mon_list[pos] < org_mon_list[pos / 2]) {
        std::swap(org_mon_list[pos], org_mon_list[pos / 2]);
        pos = pos / 2;
      } else {
        break;
      }
    }
  }
  org_mon_list[n + 1] = 15001 * n1;

  for (i = 0; i < n; ++i) {
    std::cin >> j;
    exp_list[i] = j / 2;
  }

  for (i = 0; i < n; ++i) {
    std::memcpy(mon_list, org_mon_list, sizeof(int) * (n + 2));
    max_count = 0;
    for (j = 0; j < n; ++j) {
      target = mon_list[1] + (exp_list[(i + j) % n] * n1) + 1;
      max_count = std::max(max_count, target % n1);
      k = 1;
      mon_list[1] = target;
      while (k * 2 <= n) {
        if (mon_list[k * 2] < target) {
          if (mon_list[k * 2 + 1] < target) {
            if (mon_list[k * 2] < mon_list[k * 2 + 1]) {
              std::swap(mon_list[k], mon_list[k * 2]);
              k = k * 2;
            } else {
              std::swap(mon_list[k], mon_list[k * 2 + 1]);
              k = k * 2 + 1;
            }
          } else {
            std::swap(mon_list[k], mon_list[k * 2]);
            k = k * 2;
          }
        } else if (mon_list[k * 2 + 1] < target) {
          std::swap(mon_list[k], mon_list[k * 2 + 1]);
          k = k * 2 + 1;
        } else {
          break;
        }
      }
    }
    low_count = std::min(low_count, max_count);
  }
  std::cout << low_count << std::endl;
  return 0;
}
0