제출 #782165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782165		andecaandeci	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	2004 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
const ll INF = 1e9; //4e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll LOG = 30; //20;
const double EPS = 1e-9;
#define vi vector <int>
#define vll vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ipi pair <int, pii>
#define lpl pair <ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define apaaja                          ios_base::sync_with_stdio(0);       cin.tie(0);                         cout.tie(0);                    
ll t, n;
vector < vector <pll> > v;
vector <pll> item;
ll dp [MAXN][2005];

bool mrg (pll a, pll b){
    return a.fi > b.fi;
}

int main(){
    apaaja
    cin >> t >> n;
    v.resize(t+1);
    for(ll i = 1; i <= n; i++){
        ll l, e, k;
        cin >> l >> e >> k;
        v[e].pb(mp(l, k));
    }

    item.push_back({0, 0});
    for(ll i = 1; i <= t; i++){
        sort(v[i].begin(), v[i].end(), mrg);
        ll cnt = 0, j = 0;
        while(cnt <= t/i and j < v[i].size()){
            item.push_back({v[i][j].first, i});
            v[i][j].second--;
            cnt++;
            if(v[i][j].second == 0) j++;
        }
    }
    
    for(ll i = 1; i <= item.size(); i++){
        for(ll j = 1; j <= t; j++){
            dp[i][j] = dp[i-1][j];
            if(j >= item[i].se){
                dp[i][j] = max(dp[i][j], dp[i-1][j-item[i].second] + item[i].fi);
            }
            // cout << i << " << " << j << " << " << dp[i][j] << endl;
        }
    }
    cout << dp[item.size()][t] << endl;
}

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:45:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(cnt <= t/i and j < v[i].size()){
      |                              ~~^~~~~~~~~~~~~
knapsack.cpp:53:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(ll i = 1; i <= item.size(); i++){
      |                   ~~^~~~~~~~~~~~~~

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