| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 541300 | eulerdesoja | Knapsack (NOI18_knapsack) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void setIO(string s) {
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
freopen((s+ ".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define endl "\n"
typedef pair<int,int>ii;
typedef vector<int> vi;
const int mxn = 2e3 + 5;
int dp[mxn][mxn], s, n;
vector<ii> p[mxn];
int cnt(int i, int cap) {
if (i == s + 1 || cap == 0) return 0;
int &ans = dp[i][cap];
if (ans != -1)return ans;
int w_sum = 0, v_sum = 0;
ans = 0;
ans = max(ans, cnt(i + 1, cap));
for (ii cur: p[i]) {
if (w_sum + i > cap)break;
int qtd = cur.second;
while(qtd-- && w_sum + i <= cap) {
w_sum += i;
v_sum += cur.first;
//cout<<i<<" "<<w_sum<<" "<<v_sum<<"\n";
ans = max(ans, cnt(i + 1, cap - w_sum) + v_sum);
}
}
return ans;
}
void solve() {
cin>>s>>n;
for (int i = 0; i < n; i++) {
int v, w, k;cin>>v>>w>>k;
p[w].pb({v, k});
}
for (int i = 0; i < mxn; i++)sort(p[i].begin(), p[i].end(), greater<ii>());
// for (int i = 0; i < mxn;i++)if(sz(p[i])) {
// for (ii j: p[i])cout<<j.first<<" "<<j.second<<" ";
// cout<<"\n";
// }
memset(dp, -1, sizeof(dp));
cout<<cnt(1, s)<<"\n";
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//setIO("convention");
int t = 1;
//cin>>t;
while(t--) solve();
}