제출 #1095243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095243		nmts	Knapsack (NOI18_knapsack)	C++17	100 / 100	167 ms	199068 KiB

knapsack

#include <bits/stdc++.h>
 
#define file(name) freopen(name".inp" , " r " , stdin),freopen(name".out" , " w " , stdout)
#define faster    ios_base :: sync_with_stdio(false) , cin.tie(0) , cout.tie(0) 
#define pii pair < int , int >
#define fi first
#define se second
#define endl '\n'    
#define ll long long
#define int ll
const int maxn = 5e3 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
const int block_sz = 316;
 
 
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
using namespace std;
 
int limit , n;
 
map<int , vector<pii>> m;
 
ll dp[maxn][maxn];
 
    ll ans = 0;
void solve()
{
 
    cin >> limit >> n ;
 
    for (int i = 1 ; i <= n ; ++i)
        {
            int v , w , k ; cin >> v >> w >> k ;
            if (w <= limit ) m[w].push_back(make_pair(v , k));
        }
 
    memset(dp , -0x3f , sizeof dp);
 
    dp[0][0] = 0;
 
    int id = 1;
    for (auto&[w , item] : m)
        {
 
            sort(item.rbegin() , item.rend());
 
            
            for (int j = 0 ; j <= limit ; ++j)
                {
 
                    int k = 0;
                    int profit = 0;
                    int cur = 0;
                    dp[id][j] = dp[id - 1][j];
                    
                    int id_item = 0;
 
                    while (w * (k + 1) <= j && id_item < item.size())
                        {
 
                            k++;
                            profit += item[id_item].fi;
                            dp[id][j] = max(dp[id][j] , dp[id - 1][j - k * w] + profit);
                            maximize(ans , dp[id][j]);
                            cur++;
 
                            if (cur == item[id_item].se)    
                                {
                                    cur = 0;
                                    ++id_item;
                                }
 
                        }
                }
            ++id;
 
        }
 
 
    
 
    cout << ans << endl;
 
}   
 
 
int32_t main()
{
    faster;
    // file("txt");
    // int t ; cin >> t ; while (t--)
    solve();
    return 0;
}

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

knapsack.cpp: In function 'void solve()':
knapsack.cpp:63:56: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                     while (w * (k + 1) <= j && id_item < item.size())
      |                                                ~~~~~~~~^~~~~~~~~~~~~

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