Submission #735234

#	Time	Username	Problem	Language	Result	Execution time	Memory
735234		danilovict2	Knapsack (NOI18_knapsack)	C++14	0 / 100	3 ms	340 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define mp make_pair
#define sz(a) a.size()
#define MOD 1000000007
#define forn(i, n) for (int i = 0; i < n; ++i)
#define INF 1e18
template <typename... T>
void read(T &...args){
	((cin >> args), ...);
}
template <typename... T>
void write(T... args){
	((cout << args), ...);
}
const vector<pair<int, int>> dirs1 = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
const vector<pair<int, int>> dirs2 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
const int maxN = 100001;

int dp[maxN][2001];

void solve(){
	int n,s;
	read(s,n);
	int v[n], w[n], k[n];
	forn(i,n){
		read(v[i], w[i], k[i]);
	}
	dp[0][0] = 0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=s;++j){
			dp[i][j] = dp[i-1][j];
			for(int t=1;t<=k[i-1];++t){
				if(j >= t*w[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-t*w[i-1]] + v[i-1]*t);
			}
		}
	}
	write(dp[n][s],'\n');
}

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	solve();
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void read(T& ...)':
knapsack.cpp:17:18: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   17 |  ((cin >> args), ...);
      |                  ^~~
knapsack.cpp: In function 'void write(T ...)':
knapsack.cpp:21:19: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   21 |  ((cout << args), ...);
      |                   ^~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:54:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:55:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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