제출 #1253016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253016		kkzyr	축제 (IOI25_festival)	C++20	15 / 100	1094 ms	303672 KiB

festival

#include <iostream>
#include <algorithm>
using namespace std;

struct dp_state{
    int multiplier_ones, multiplier_twos, multiplier_threes, multiplier_fours;
};

vector<pair<int, int>> coupons_type[5];

int from_where[71][71][71][71];
long long dp[71][71][71][71];

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T){
    for (int i = 0;i < P.size();i++){
        coupons_type[T[i]].push_back({P[i], i});
    }
    for (int j = 1;j <= 4;j++){
        sort(coupons_type[j].begin(), coupons_type[j].end());
    }
    for (int i = 0;i <= coupons_type[1].size();i++){
        for (int j = 0;j <= coupons_type[2].size();j++){
            for (int k = 0;k <= coupons_type[3].size();k++){
                for (int l = 0;l <= coupons_type[4].size();l++){
                    dp[i][j][k][l] = -1;
                }
            }
        }
    }
    dp[0][0][0][0] = A;
    for (int i = 0;i <= coupons_type[1].size();i++){
        for (int j = 0;j <= coupons_type[2].size();j++){
            for (int k = 0;k <= coupons_type[3].size();k++){
                for (int l = 0;l <= coupons_type[4].size();l++){
                    if (i >= 1 and dp[i - 1][j][k][l] >= coupons_type[1][i - 1].first){
                        if (dp[i][j][k][l] < (dp[i - 1][j][k][l] - coupons_type[1][i - 1].first) * 1){
                            dp[i][j][k][l] = (dp[i - 1][j][k][l] - coupons_type[1][i - 1].first) * 1;
                            from_where[i][j][k][l] = 1;
                        }
                    }
                    if (j >= 1 and dp[i][j - 1][k][l] >= coupons_type[2][j - 1].first){
                        if (dp[i][j][k][l] < (dp[i][j - 1][k][l] - coupons_type[2][j - 1].first) * 2){
                            dp[i][j][k][l] = (dp[i][j - 1][k][l] - coupons_type[2][j - 1].first) * 2;
                            from_where[i][j][k][l] = 2;
                        }
                    }
                    if (k >= 1 and dp[i][j][k - 1][l] >= coupons_type[3][k - 1].first){
                        if (dp[i][j][k][l] < (dp[i][j][k - 1][l] - coupons_type[3][k - 1].first) * 3){
                            dp[i][j][k][l] = (dp[i][j][k - 1][l] - coupons_type[3][k - 1].first) * 3;
                            from_where[i][j][k][l] = 3;
                        }
                    }
                    if (l >= 1 and dp[i][j][k][l - 1] >= coupons_type[4][l - 1].first){
                        if (dp[i][j][k][l] < (dp[i][j][k][l - 1] - coupons_type[4][l - 1].first) * 4){
                            dp[i][j][k][l] = (dp[i][j][k][l - 1] - coupons_type[4][l - 1].first) * 4;
                            from_where[i][j][k][l] = 4;
                        }
                    }
                    dp[i][j][k][l] = min(dp[i][j][k][l], 1000000000000000LL);
                }
            }
        }
    }
    dp_state best_state = {0, 0, 0, 0};
    for (int i = 0;i <= coupons_type[1].size();i++){
        for (int j = 0;j <= coupons_type[2].size();j++){
            for (int k = 0;k <= coupons_type[3].size();k++){
                for (int l = 0;l <= coupons_type[4].size();l++){
                    if (dp[i][j][k][l] != -1){
                        if ((i + j + k + l) > (best_state.multiplier_ones + best_state.multiplier_twos + best_state.multiplier_threes + best_state.multiplier_fours)){
                            best_state = {i, j, k, l};
                        }
                    }
                }
            }
        }
    }
    vector<int> operations;
    while (best_state.multiplier_ones != 0 or best_state.multiplier_twos != 0 or best_state.multiplier_threes != 0 or best_state.multiplier_fours != 0){
        int value = from_where[best_state.multiplier_ones][best_state.multiplier_twos][best_state.multiplier_threes][best_state.multiplier_fours];
        if (value == 1){
            operations.push_back(coupons_type[1][best_state.multiplier_ones - 1].second);
            best_state.multiplier_ones--;
        }
        else if (value == 2){
            operations.push_back(coupons_type[2][best_state.multiplier_twos - 1].second);
            best_state.multiplier_twos--;
        }
        else if (value == 3){
            operations.push_back(coupons_type[3][best_state.multiplier_threes - 1].second);
            best_state.multiplier_threes--;
        }
        else{
            operations.push_back(coupons_type[4][best_state.multiplier_fours - 1].second);
            best_state.multiplier_fours--;
        }
    }
    reverse(operations.begin(), operations.end());
    return operations;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 15 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18