Submission #71727106

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, L, T;
    ll K;
    cin >> N >> L >> T >> K;

    vector<ll> A(N);
    for (int j = 0; j < N; j++) cin >> A[j];

    vector<vector<ll>> C(L, vector<ll>(N));
    for (int i = 0; i < L; i++) {
        for (int j = 0; j < N; j++) cin >> C[i][j];
    }

    vector<vector<ll>> P(L, vector<ll>(N, 0)); // パワー
    ll apple = K;

    for (int t = 0; t < T; t++) {
        ll bestScore = 0;
        int best_i = -1, best_j = -1;

        ll rem = T - t;

        // 強化候補を全探索（L*N <= 40）
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < N; j++) {
                ll cost = C[i][j] * (P[i][j] + 1);
                if (cost > apple) continue;

                ll gain;
                if (i == 0) {
                    gain = rem * A[j];
                } else {
                    // 簡易評価：下位へ伝播する期待値
                    gain = rem * A[j] / (i + 1);
                }

                ll score = gain - cost;
                if (score > bestScore) {
                    bestScore = score;
                    best_i = i;
                    best_j = j;
                }
            }
        }

        if (bestScore > 0) {
            // 強化
            ll cost = C[best_i][best_j] * (P[best_i][best_j] + 1);
            apple -= cost;
            P[best_i][best_j]++;
            cout << best_i << " " << best_j << "\n";
        } else {
            cout << -1 << "\n";
        }

        // 生産フェーズ
        for (int j = 0; j < N; j++) {
            apple += A[j] * P[0][j];
        }
        for (int i = 1; i < L; i++) {
            for (int j = 0; j < N; j++) {
                P[i - 1][j] += P[i][j];
            }
        }
    }
}

Submission Info

Judge Result