Submission #806804

#TimeUsernameProblemLanguageResultExecution timeMemory
806804loveubotaKnapsack (NOI18_knapsack)C++17
49 / 100
1082 ms12332 KiB
// In the name of God #include <bits/stdc++.h> using namespace std ; #define ll long long #define pb push_back #define ld long double #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define remove(x) x.erase(unique(all(x)), x.end()) #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, b, a) for (int i = (b); i >= (a); i--) const int N = 1e5 + 1, inf = (1 << 30) , L = 20 ; const ld eps = 1e-6 ; const ll INF = 1e18 + 123 , mod = 1e9 + 7 ; int s , n , v[N] , w[N] , k[N] ; unordered_map<int,ll> dp[N] ; ll go(int i , int j) { if (i > n) return 0 ; if (dp[i].find(j) != dp[i].end()) return dp[i][j] ; ll ans = 0 ; rep(c, 0, k[i]) { if (c * w[i] > j) break ; ans = max(ans , go(i + 1, j - (1ll * c * w[i])) + 1ll * c * v[i]) ; } dp[i][j] = ans ; int n ; cin >> n ; return ans ; } /* 15 5 4 12 1 2 1 1 10 4 1 1 1 1 2 2 1 */ void solve(int &tc) { cin >> s >> n ; rep(i , 1 , n) { cin >> v[i] >> w[i] >> k[i] ; } // memset(*dp, -1, sizeof(dp)) ; cout << go(1,s) ; return ; } int main() { #ifdef ONPC freopen("inp", "r", stdin) ; #endif ios_base::sync_with_stdio(false) ; cin.tie(0) ; int T = 1 ; // cin >> T ; rep(i, 1 ,T) { solve(i) ; } return 0; }
#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...