제출 #883778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883778		vjudge1	Knapsack (NOI18_knapsack)	C++17	73 / 100	1018 ms	16180 KiB

knapsack

// Goten2308
#include<bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
//#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a <= 0) a += MOD; }

void solve() {
    int n, s;
    cin >> s >> n;
    vector<int> w, v, f(s + 1, 0);
    for(int i = 1; i <= n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        int cnt = 1;
        while(c - cnt >= 0) {
            w.pb(b * cnt);
            v.pb(a * cnt);
            c -= cnt;
            cnt *= 2;
        }
        if(c) {
            w.pb(b * c);
            v.pb(a * c);
        }
    }
    for(int i = 0; i < w.size(); i++) {
        for(int j = s; j >= w[i]; j--) {
            maximize(f[j], f[j - w[i]] + v[i]);
        }
    }
    cout << f[s] << endl;
}

signed main(){
    #define task ""
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        //freopen("task.out", "w", stdout);
    }
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int nTest = 1;
    #ifdef MULTI_TEST
    cin >> nTest;
    #endif
    while(nTest--) solve();
    return 0;
}

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

knapsack.cpp: In function 'void solve()':
knapsack.cpp:42:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < w.size(); i++) {
      |                    ~~^~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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