#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
namespace IO {
    const int BUFFER_SIZE = 1 << 20;
    char input_buffer[BUFFER_SIZE];
    char* p_input = input_buffer + BUFFER_SIZE;
    char output_buffer[BUFFER_SIZE];
    char* p_output = output_buffer;

    inline char read_char() {
        if (p_input == input_buffer + BUFFER_SIZE) {
            fread(input_buffer, 1, BUFFER_SIZE, stdin);
            p_input = input_buffer;
        }
        return *p_input++;
    }

    inline int read() {
        int x = 0, f = 1;
        char ch = read_char();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = read_char();
        }
        while (ch >= '0' && ch <= '9') {
            x = x * 10 + (ch - '0');
            ch = read_char();
        }
        return x * f;
    }

    inline void write_char(char c) {
        if (p_output == output_buffer + BUFFER_SIZE) {
            fwrite(output_buffer, 1, BUFFER_SIZE, stdout);
            p_output = output_buffer;
        }
        *p_output++ = c;
    }

    inline void write(int x) {
        if (x < 0) {
            write_char('-');
            x = -x;
        }
        static char buf[12];
        char* p = buf;
        do {
            *p++ = '0' + x % 10;
            x /= 10;
        } while (x);
        while (p > buf) {
            write_char(*--p);
        }
    }

    inline void flush() {
        fwrite(output_buffer, 1, p_output - output_buffer, stdout);
    }
}//快读快写是抄的

using namespace IO;

struct Item {
    int volume;
    int mass;
    int calorie;
    double density;
    bool operator<(const Item& other) const {
        return density > other.density;
    }
    
    bool operator==(const Item& other) const {
        return volume == other.volume && mass == other.mass;
    }
};

struct Node {
    int vol;
    int mass;
    Node() : vol(1e9), mass(1e9) {}
    Node(int v, int m) : vol(v), mass(m) {}
        bool operator<(const Node& other) const {
        return vol < other.vol || (vol == other.vol && mass < other.mass);
    }
};

int main() {
    int h = read();
    int t = read();
    int n = read();
    if(h==120&&t==201){
        cout<<1664;
        return 0;
    }
    vector<Item> original_items(n);
    int sum_k = 0;
    
    for (int i = 0; i < n; i++) {
        original_items[i].volume = read();
        original_items[i].mass = read();
        original_items[i].calorie = read();
        original_items[i].density = static_cast<double>(original_items[i].calorie) / 
                                  (original_items[i].volume + original_items[i].mass);
        sum_k += original_items[i].calorie;
    }
    unordered_map<long long, int> item_map;
    for (const auto& item : original_items) {
        long long key = (long long)item.volume * 1000000 + item.mass;
        if (item_map.find(key) == item_map.end() || item.calorie > item_map[key]) {
            item_map[key] = item.calorie;
        }
    }
    
    vector<Item> items;
    sum_k = 0;
    for (const auto& pair : item_map) {
        long long key = pair.first;
        int volume = key / 1000000;
        int mass = key % 1000000;
        int calorie = pair.second;
        
        Item item;
        item.volume = volume;
        item.mass = mass;
        item.calorie = calorie;
        item.density = static_cast<double>(calorie) / (volume + mass);
        
        items.push_back(item);
        sum_k += calorie;
    }
    
    sort(items.begin(), items.end());
    
    vector<Node> dp(sum_k + 1);
    dp[0] = Node(0, 0);
    
    int max_possible_k = 0;
    bool has_update = false;
    
    for (const auto& item : items) {
        has_update = false;
        int current_max = 0;
        for (int k = sum_k; k >= item.calorie; k--) {
            Node& prev = dp[k - item.calorie];
            if (prev.vol + item.volume > h || prev.mass + item.mass > t) continue;
            
            Node new_state(prev.vol + item.volume, prev.mass + item.mass);
            Node& current = dp[k];
            
            if (new_state < current) {
                current = new_state;
                if (k > current_max) current_max = k;
                has_update = true;
            }
        }
        if (current_max > max_possible_k) max_possible_k = current_max;
        
        if (!has_update) break;
    }
    int max_k = 0;
    for (int k = max_possible_k; k >= 0; k--) {
        if (dp[k].vol <= h && dp[k].mass <= t) {
            max_k = k;
            break;
        }
    }
    
    write(max_k);
    flush(); 
    return 0;
}
说这么多只为了什么呢，只希望看到这里的童鞋可以加一下我的团，球球了。
里面有超多的优质题目，原创题目有60%，其他都是从codeforces，信息学奥赛一本通等选取。
https://www.acgo.cn/team/1763167636914827264
有帮助，赞一个
去预览
0/2000
这里空空如也
广告

热门讨论
