제출 #1029873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1029873		O_Elmasry	Knapsack (NOI18_knapsack)	C++17	29 / 100	6 ms	2136 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
#define endl '\n'
#define int long long
const long long mod = 998244353, Mxn = 505, INF = 1e18;
struct item{
        int w, v, k;
        friend bool operator<(const item &a, const item &b){
                if(a.w != b.w){
                        return a.w > b.w;
                }
                return a.v > b.v;
        }
        friend istream &operator>>(istream &is, item &a){
                is >> a.v >> a.w >> a.k;
                return is;
        }
        friend ostream &operator<<(ostream &os,const item &a){
                os << a.v << " " << a.w << " " << a.k;
                return os;
        }
};
template<typename T>
void smax(T &a, T b){
        a = max(a, b);
}
void solve()
{
        int n, W;
        cin >> W >> n;
        vector<item>v(n + 1);
        for(int i = 1;i <= n;i++){
                cin >> v[i];
        }
        sort(v.begin() + 1, v.end());
        vector<vector<int>>dp(n + 2,vector<int>(W + 1));
        for(int i = 1;i <= n;i++){
                for(int j = 0;j <= W;j++){
                        int left = W - j;
                        item cur = v[i];
                        int take = min(cur.k, left / cur.w);
                        int weight = take * cur.w;
                        int cost = take * cur.v;
                        if(j + weight <= W){
                                smax(dp[i][j + weight], dp[i - 1][j] + cost);
                        }
                        smax(dp[i + 1][j], dp[i][j]);
                }
        }
        int ans = *max_element(dp[n].begin(), dp[n].end());
        cout << ans << endl;
}
signed main()
{
        ios::sync_with_stdio(0);
        cin.tie(nullptr);
        cout.tie(nullptr);
#ifdef LOCAL
        FileRedirect("test");
#endif
        // freopen("revegetate.in","r",stdin);
        // freopen("revegetate.out","w",stdout);
        int tc = 1;
        // cin >> tc;
        while (tc--)
                solve();
}

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