Submission #1256300

#TimeUsernameProblemLanguageResultExecution timeMemory
1256300Mikael639Knapsack (NOI18_knapsack)C++20
0 / 100
0 ms1032 KiB
#include <bits/stdc++.h> #define fi first #define se second #define For(i, a, b) for (int i = (a); i <= (b); ++i) #define ForD(i, a, b) for (int i = (a); i >= (b); --i) #define rep(i, n) for (int i = 0; i < (n); ++i) #define repD(i, n) for (int i = (n) - 1; i >= 0; --i) #define coutE(x) {cout << x << '\n'; return;} #define pb push_back #define pf push_front #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define bs binary_search #define ub upper_bound #define lb lower_bound #define endl '\n' #define db long double #define ll long long #define ii pair<int, int> #define vi vector<int> #define vii vector<ii> #define int long long using namespace std; void file(string s){ if (s.empty()) return; freopen((s + ".inp").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } template <class X, class Y> bool minimize(X &x, Y y){ if (x > y) return x = y, 1; return 0; } template <class X, class Y> bool maximize(X &x, Y y){ if (x < y) return x = y, 1; return 0; } mt19937_64 rng(time(0)); const int N = 1e6 + 5; const int MOD = 1e9 + 7; //998244353; const int INF = 1e9; const long long LINF = 1e18; const int dx[] = {1, 0, 0, -1}; const int dy[] = {0, 1, -1, 0}; int s, n; set<int> st[5005]; void Add(int nw, int nv){ cout << nw << ' ' << nv << endl; if (sz(st[nw]) <= s/nw) st[nw].insert(nv); else{ if (*st[nw].begin() < nv){ st[nw].erase(st[nw].begin()); st[nw].insert(nv); } } } void solve(){ cin >> s >> n; rep(i, n){ int v, w, k; cin >> v >> w >> k; minimize(k, s/w + 1); for (int b = 1; b <= k; k -= b, b <<= 1){ Add(w * b, v * b); } if (k){ Add(w * k, v * k); } } vi dp(s + 5, 0); For(i, 1, s){ for (int v: st[i]){ ForD(j, s, i){ maximize(dp[j], dp[j - i] + v); } } } cout << dp[s]; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); file(""); int T = 1; //cin >> T; while (T--) solve(); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void file(std::string)':
knapsack.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "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...