Submission #1301910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301910		hades_85	Knapsack (NOI18_knapsack)	C++20	100 / 100	67 ms	39180 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll mo = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e15;
const int N = 2e5 + 10;
int M = 1e3 + 10;

#define int long long

ll binExp(ll a, ll b , ll mo) {
    ll ans = 1;
    a %= mo;
    while (b) {
        if (b & 1) ans = ans * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return ans;
}

vector<vector<int>> div1(N);
void sieve(){
    for (int i = 1; i < N ; ++i)
    {
        for(int j = i ; j < N ; j+=i){
            div1[j].push_back(i);
        }
    }
}

int ad(int a , int b){
    return (a+b)%mo;
}

int mul(int a ,int b){
    return (a*b)%mo;
}

void solve() {
    int n,s;
    cin>>s>>n;
    map<int,vector<pair<int,int>>> m;
    for(int i = 0 ;i < n ; i++){
        int v,w,k;
        cin>>v>>w>>k;
        m[w].push_back({v,k});
    } 
    vector<vector<int>> dp(m.size()+1 , vector<int> (s+1 , -INF));
    dp[0][0] = 0;
    int at = 1;
    for(auto &[w , item]: m){
        sort(item.rbegin() , item.rend());
        for(int i = 0 ; i <= s; i++){
            dp[at][i] = dp[at-1][i];
            int co = 0 , curr_used = 0 , profit = 0  , j = 0;
            while((co+1)*w <= i && j < item.size()){
                co++;
                profit += item[j].first;
                dp[at][i] = max(dp[at][i] , dp[at-1][i-co*w]+profit);
                curr_used++;
                if(curr_used == item[j].second){
                    curr_used = 0;
                    j++;
                }
            }
        }
        at++;
    }
    int g = m.size();
    int ans = *max_element(dp[g].begin()+1 , dp[g].end());
    cout<<ans<<endl;
}


signed main() {
    // freopen("revegetate.in", "r", stdin);
    // freopen("revegetate.out", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    // sieve();
    // help();
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27