提出 #70296332

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()

#define MODE 0 // 0ならローカル

/* ---------- 焼きなましゾーン ---------- */
// 定数
constexpr int END_TIME = 1985; // 処理を打ち切る時間
const auto START_TIME = chrono::system_clock::now(); // 開始時刻
constexpr double start_temp = 110, end_temp = 0; // 最大点数変化、最小点数変化

// XorShift128
unsigned int randxor() {
    static unsigned int x=123456789, y=362436069, z=521288629, w=88675123;
    unsigned int t;
    t=(x^(x<<11)); x=y; y=z; z=w;
    return(w=(w^(w>>19))^(t^(t>>8)));
}

// 経過時間取得関数
int getTime() {
    auto end_time = chrono::system_clock::now();
    return chrono::duration_cast<chrono::milliseconds>(end_time-START_TIME).count();
}

// 温度関数
double get_temp() {
  /*
  // 指数的に下げる
  double timeRate = getTime()/(double)END_TIME;
  return pow(start_temp, 1-timeRate)*pow(end_temp, timeRate);
  //*/
  //*
  // 一定に下げる
  return start_temp + (end_temp-start_temp) * getTime() / END_TIME;
  //*/
}

// 遷移確率
double prob(double new_score, double pre_score) {
  double temp = get_temp();
  return exp((new_score-pre_score)/temp);
}
/* ---------- 焼きなましゾーンここまで ---------- */

class State {
public:
  // 入力データ
  int N;
  vector<int> H, C;
  vector<vector<int>> A;

  // 前処理固定データ

  // 可変データ
  vector<pair<int,int>> ans;

  void input() {
    cin >> N;
    H.resize(N);
    rep(i, 0, N) cin >> H[i];
    C.resize(N);
    rep(i, 0, N) cin >> C[i];
    A.resize(N);
    rep(i, 0, N) {
      A[i].resize(N);
      rep(j, 0, N) cin >> A[i][j];
    }
  }

  void output() {
    for (auto i : ans) cout << i.first << " " << i.second << endl;
  }

  // 可変データの復元
  void reset() {
  }

  void solve() {
    vector<pair<int,int>> memo(N);
    rep(i, 0, N) memo[i] = {H[i], i};
    sort(all(memo));
    vector<int> box(N);
    rep(i, 0, N) box[i] = memo[i].second;

    set<pair<int,int>> rem;
    for (int i=N-1; i>=0; i--) {
      int num = box[i];
      rep(j, 0, C[num]) {
        int maxi = 0;
        pair<int,int> best = {-1, -1};
        for (auto k : rem) {
          int tmp = min(k.second, A[num][k.first]);
          if (tmp > maxi) {
            maxi = tmp;
            best = k;
          }
        }
        if (best.first == -1) break;
        ans.push_back({num, best.first});
        rem.erase(best);
        if (maxi != best.second) rem.insert({best.first, best.second-maxi});
      }
      rem.insert({num, H[num]});
    }
    for (auto i : rem) {
      rep(j, 0, i.second) ans.push_back({-1, i.first});
    }
    reverse(all(ans));

    vector<int> cnt(N);
    rep(i, 0, ans.size()) {
      auto ope = ans[i];
      if (cnt[ope.second] >= H[ope.second]) {
        ans.erase(ans.begin()+i);
        i--;
        continue;
      }
      if (ope.first == -1) cnt[ope.second]++;
      else cnt[ope.second] += A[ope.first][ope.second];
    }
  }
};

int main() {
  State state;
  state.input();
  state.solve();
  state.output();
}

提出情報

ジャッジ結果