Submission

[TSSSSSSSSS]

Score: 0

User: Nightingale

Problemset: 02.Forbidden Boss Room

Language: cpp

Time: 1.083 second

Submitted On: 2025-04-01 15:16:41

#include <bits/stdc++.h>
#define int long long
using namespace std;

int b, c;
unordered_map<string, int> memo; // Memoization table

// Generate a unique key based on current state
string getKey(vector<int> &level, int day, int sum) {
    string key = to_string(day) + "_" + to_string(sum) + "_";
    for (int x : level) key += to_string(x) + ",";
    return key;
}

int dyna(vector<int> &level, int day, int sum) {
    if (day == b) return sum % c;
    
    string key = getKey(level, day, sum);
    if (memo.find(key) != memo.end()) return memo[key];

    int maxVal = LLONG_MIN;
    for (int i = 0; i < level.size(); i++) {
        vector<int> mem = level;
        int power = (sum + level[i]) % c;
        if (power == 0) power = -1;
        
        mem.erase(mem.begin() + i);
        maxVal = max(maxVal, dyna(mem, day + 1, power));
    }

    return memo[key] = maxVal; // Store result in memo
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int a;
    cin >> a;
    while (a--) {
        cin >> b >> c;
        vector<int> level(b);
        for (int j = 0; j < b; j++) cin >> level[j];

        memo.clear(); // Reset memoization for each test case
        cout << dyna(level, 1, 0) << '\n';
    }
}