Submission #71720023

---

Source Code Expand

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

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>> B(L, vector<ll>(N, 1)); // 個数
    vector<vector<ll>> P(L, vector<ll>(N, 0)); // パワー
    ll apples = K;

    for (int t = 0; t < T; t++) {
        int R = T - t - 1;

        int best_i = -1, best_j = -1;
        ld best_score = 0.0;

        // 全候補を評価
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < N; j++) {
                // 強化コスト
                ll cost;
                // オーバーフロー回避
                if (P[i][j] >= (ll)4e18 / C[i][j]) continue;
                cost = C[i][j] * (P[i][j] + 1);

                if (cost > apples) continue;

                // 効果見積もり
                ld delta = 0.0;
                if (R > 0) {
                    if (i == 0) {
                        // 即効
                        delta = (ld)A[j] * B[0][j] * R;
                    } else if (i == 1) {
                        delta = (ld)A[j] * B[1][j] * (ld)R * (R + 1) / 2.0;
                    } else if (i == 2) {
                        delta = (ld)A[j] * B[2][j] * (ld)R * R * R / 6.0;
                    } else if (i == 3) {
                        delta = (ld)A[j] * B[3][j] * (ld)R * R * R * R / 24.0;
                    }
                }

                if (delta <= 0) continue;

                ld score = delta / (ld)cost;
                if (score > best_score) {
                    best_score = score;
                    best_i = i;
                    best_j = j;
                }
            }
        }

        // 行動
        if (best_i != -1) {
            ll cost = C[best_i][best_j] * (P[best_i][best_j] + 1);
            apples -= cost;
            P[best_i][best_j]++;
            cout << best_i << " " << best_j << "\n";
        } else {
            cout << -1 << "\n";
        }

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

    return 0;
}

Submission Info

Judge Result