제출 #1095240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095240		nmts	Knapsack (NOI18_knapsack)	C++17	0 / 100	96 ms	196440 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);
                            cur++;

                            if (cur == item[id_item].se)    
                                {
                                    cur = 0;
                                    ++id_item;
                                }

                        }
                }
            ++id;

        }

    for (int i = 1 ; i <= limit ; ++i)
        maximize(ans , dp[id - 1][i]);
    

    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: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27