Submission #1119774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119774		barkolorious	Knapsack (NOI18_knapsack)	C++17	0 / 100	993 ms	262144 KiB

knapsack

// barkolorious - 27 November 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define int long long
#define pb  push_back
#define fr  first
#define sc  second
#define __  << " " << 

const int N = 2e5 + 5;

struct Item {
  int v, w, k;
};

void solve () {
  int n, s; cin >> s >> n;
  Item item[n + 1];
  for (int i = 1; i <= n; i++) cin >> item[i].v >> item[i].w >> item[i].k;
  int dp[n + 1][s + 1]{};
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= s; j++) {
      int count = min(j / item[i].w, item[i].k);
      for (int k = 0; k <= count; k++) {
        int weight = k * item[i].w, value = k * item[i].v;
        if (j - weight < 0) break;
        dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
      }
      if (j) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
    }
  }
  // for (int i = 0; i <= n; i++) 
  //   for (int j = 0; j <= s; j++)  
  //     cout << setfill(' ') << setw(4) << dp[i][j] << " \n"[j == s];
  cout << dp[n][s] << endl;
}

/*
-- Sample 1 --
Input:
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
Output:
15

-- Sample 2 --
Input:
20 3
5000 15 1
100 1 3
50 1 4
Output:
5400
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\oj.uz\NOI18\NOI18_knapsack.cpp" -o _run
*/

int32_t main () {
  #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #ifdef LOCAL
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #else
    #ifndef ONLINE_JUDGE
      FILE* __FILE_IN__ = FIN("usaco");
      FILE* __FILE_OUT__ = FOUT("usaco");
    #endif
  #endif

  solve();

  #ifdef LOCAL
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #else
    #ifndef ONLINE_JUDGE
      fclose(__FILE_IN__);
      fclose(__FILE_OUT__);
    #endif
  #endif

  return 0;
}

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