Submission #588565

#	Time	Username	Problem	Language	Result	Execution time	Memory
588565		atom	Knapsack (NOI18_knapsack)	C++17	100 / 100	142 ms	19328 KiB

knapsack

#include<bits/stdc++.h>

using namespace std;
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int pi = 31, pii = 29, piii = 41;
const int inf = 1e9 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("feast.in", "r", stdin);
//    freopen("feast.out", "w", stdout);
}

int n, s;
vector<pair<int,int> > a[2005]; // fi -> weight, se -> value
int dp[2005][2005];

void inp(){
    cin >> s >> n;
    rep(i,1,n){
        ciii(v,w,k);
        a[w].pb(mp(k, v));
    }
    rep(i,1,s)
        sort(all(a[i]), [](pair<int,int> &a, pair<int,int> &b){return a.se > b.se;});
}

void process(){
    rep(i,1,s){
        rep(j,1,s){
            int sum = 0, val = 0;
            for(auto t : a[j]){
                rep(times,1,t.fi){
                    sum += j;
                    val += t.se;
                    if(sum > i) break;
                    dp[i][j] = max(dp[i][j], dp[i-sum][j-1] + val);
                }
                if(sum > i) break;
            }
            dp[i][j] = max(dp[i][j], dp[i][j-1]);
        }
    }
    int res = 0;
    rep(i,1,s)
        rep(j,1,s)
            res = max(res, dp[i][j]);
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
//    TC(t){
        inp();
        process();
//    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void readfile()':
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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