제출 #1315506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315506		herominhsteve	Knapsack (NOI18_knapsack)	C++20	100 / 100	47 ms	8228 KiB

knapsack

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "Knapsack"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(FNAME".inp","r")){
        freopen(FNAME".inp","r",stdin);
        freopen(FNAME".out","w",stdout);
    }
}

const long long INF = (long long) 1e16 + 15092007;

struct Goods{
    long long val,weight,quantity;
    Goods(long long v,long long w,long long q):val(v),weight(w),quantity(q) {}
    bool operator < (const Goods &other) const{
        if (val != other.val) return val > other.val;
        if (quantity != other.quantity) return quantity > other.quantity;
        return weight > other.weight;
    }
};

int numGoods,maxWeight;
vector<Goods> goods;

void init(){
    cin>>maxWeight>>numGoods;
    for (int i = 0; i < numGoods; i++){
        long long v,w,q; cin>>v>>w>>q;
        goods.emplace_back(v,w,q);
    }
}

void sol(){
    vector<long long> dp(maxWeight + 1, 0);

    vector<vector<Goods>> goodsByW(maxWeight + 1);
    vector<int> ws;
    for (const Goods &g : goods){
        goodsByW[g.weight].emplace_back(g);
        ws.push_back(g.weight);
    }

    sort(allof(ws)); 
    ws.resize(unique(allof(ws)) - ws.begin());

    for (int w : ws){
        vector<Goods> &curGoods = goodsByW[w];
        sort(allof(curGoods));
        int totalTake = 0, cnt = 0, ptr = 0;

        while (totalTake * w <= maxWeight and ptr < (int)curGoods.size()){
            for (int j = maxWeight; j >= w; j--){
                maximize(dp[j], dp[j - w] + curGoods[ptr].val);
            }
            cnt++;
            totalTake++;
            if (cnt >= curGoods[ptr].quantity){
                cnt = 0;
                ptr++;
            }
        }
    }

    cout<<dp.back();
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'void setup()':
knapsack.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen(FNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(FNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27