제출 #586285

#제출 시각아이디문제언어결과실행 시간메모리
586285MazaalaiKnapsack (NOI18_knapsack)C++17
0 / 100
2 ms468 KiB
#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++) { for (auto& el : val[w]) vals[w].pb(el); val[w].clear(); int pre = 0; for (auto& el : vals[w]) pre = el = pre+el; } 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 = 0; k < vals[w].size() && j + w*(k+1) <= m && dp[j] >= 0; k++) dp[j + w*(k+1)] = 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 freopen("0.in", "r", stdin); freopen("0.out", "w", stdout); #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?) */

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'void go()':
knapsack.cpp:149:39: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |             if ((val[w].size()+1) * w <= m) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:172:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for (int k = 0; k < vals[w].size() && j + w*(k+1) <= m && dp[j] >= 0; k++)
      |                     ~~^~~~~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:185:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     freopen("0.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:186:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |     freopen("0.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...