| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 586287 | Mazaalai | Knapsack (NOI18_knapsack) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
// #pragma GCC optimize("O3, unroll-loops")
// #pragma GCC target("avx2")
// #define int long long
using namespace std;
#define _upgrade \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORB(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a) for (int i = 0; i < a; i++)
#define REP1(i, a) for (int i = 1; i < a; i++)
#define REPB(i, a) for (int i = a - 1; i >= 0; i--)
#define TRAV(a,x) for (auto& a: x)
#define LINE "---------------------\n"
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define Q queue
#define ff first
#define ss second
#define ts to_string
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
using ll = long long;
using db = double;
using ld = long double;
using uint = unsigned;
// PQ going up <int, VI, greater<int> >
using VI = vector<int>;
using VS = vector<string>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VD = vector<db>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void eraseDups(VI& a) {
a.erase(unique(a.begin(), a.end()), a.end());
}
int strToInt(string&a) {
stringstream x(a);
int b;
x >> b;
return b;
}
int bitCnt(int a) {
bitset <64> b(a);
return b.count();
}
int bitCnt(string a) {
bitset <64> b(a);
return b.count();
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
void print(VI& a) {
for (auto el : a) {
cout << el << ' ';
}
cout << '\n';
}
void print(VPI& a) {
for (auto el : a) {
cout << el.ff << ',' << el.ss << ' ';
}
cout << '\n';
}
void print(VI& a, int n) {
int cnt = 0;
for (auto el : a) {
if (cnt++ == n) break;
cout << el << ' ';
}
cout << '\n';
}
void print(VVI& a) {
for (auto el : a) {
print(el);
}
}
/*
| _
| __ _ | |
| | \| | ___ ___ | |_
| | |\ | |/ _ \/ __/| __|
| | | \ | __/\__ \| |_
| |_| \_|\___ /___/ \__|
| _ _ _
| (_) | | | |
| _ __ _ __ ___ __ _ _ __ __ _ _ __ ___ _ __ ___ _ ___ ___| |_| |_
| | '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|
| | |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_
| | .__/|_| \___/ \__, |_| \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|
| | | __/ |
| |_| |___/ _
| _ (_)
| _ __ ___ __ _ ____ __ _ __ _| | __ _ _
| | '_ ` _ \ / _` |_ / _` |/ _` | |/ _` | |
| | | | | | | (_| / / (_| | (_| | | (_| | |
| |_| |_| |_|\__,_|____\__,_|\__,_|_|\__,_|_|
*/
const db PI = acos(-1.0); //M_PI;
const ll INFF = 4e18;
const int INF = 1.07e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353; //7*19*2^23 +1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 2e3 + 5;
const int M = 2e3 + 5;
int n, m;
string s;
int dp[N];
multiset <int> val[N];
VI vals[N];
void go () {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
int v, w, q; cin >> v >> w >> q;
for (int j = 0; j < q; j++) {
if ((val[w].size()+1) * w <= m) {
val[w].insert(v);
} else {
auto it = val[w].begin();
if (*it < v) {
val[w].erase(it);
val[w].insert(v);
} else {
break;
}
}
}
}
for (int w = 1; w <= m; w++) {
vals[w].pb(0);
for (auto& el : val[w])
vals[w].pb(el+vals[w].back());
val[w].clear();
}
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int w = m; w > 0; w--) // 2e3
for (int j = m-w; j >= 0; j--) // 2e3
for (int k = 1; k < vals[w].size() && j + w*k <= m && dp[j] >= 0; k++)
dp[j + w*k)] = max(dp[j + w*k], dp[j] + vals[w][k]);
for (int i = 1; i <= m; i++) dp[i] = max(dp[i], dp[i-1]);
cout << dp[m] << '\n';
}
signed main () {
#ifndef ONLINE_JUDGE
#endif
_upgrade
int T = 1;
while(T--) go();
return (0-0); //<3
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
*/