Submission

Score: 0

User: goine

Problemset: ฮีโร่และมอนสเตอร์

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-11 10:09:42

// 0/1 knapsack

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

int main() {
    int hero_count, monster_count;
    cin >> hero_count >> monster_count;

    vector<int> heros(hero_count);
    int maximum = 0;

    for (int i = 0; i < hero_count; i++) {
        cin >> heros[i];
        if (heros[i] > maximum) {
            maximum = heros[i];
        }
    }

    // monsters
    vector<pair<int, int>> monsters(monster_count, pair<int, int>());
    for (int i = 0; i < monster_count; i++) {
        cin >> monsters[i].first >> monsters[i].second;
    }
    
    vector<vector<int>> dp(maximum + 1, vector<int>(monster_count, 0));
    for (int i = 0; i < monster_count; i++) {
        for (int j = 1; j <= maximum; j++) {
            if (j >= monsters[i].first) {
                dp[j][i] = dp[j][i] + monsters[i].second;
            }

            if (i > 0) {
                dp[j][i] = dp[j][i] + dp[j][i - 1];
            }
        }
    }


    for (int i = 0; i < hero_count; i++) {
        cout << dp[heros[i]][monster_count - 1] << ' ';
    }

    return 0;
}