Submission #1224665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224665		gurt_yo	Knapsack (NOI18_knapsack)	C++20	100 / 100	74 ms	42056 KiB

knapsack

#include <bits/stdc++.h>
// #include <vector>
// #include <iostream>
// #include <map>

using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
typedef pair<ll,ll> pll;
typedef pair<char,char> pcc;
int h[] = {1,-1,0,0};
int v[] = {0,0,1,-1};

const ll N = 1e6+1;
const ll INF = LLONG_MAX;

ll p[N];
vector<vector<pair<ll,ll>>> adj;
// ll dist[N];
vector<ll> dist(N, INF);
void dijkstra(ll s, vector<ll> &parent){
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    dist[s] = 0;
    pq.push({0, s});

    while(!pq.empty()){
        ll vert = pq.top().second;
        ll dv = pq.top().first;
        pq.pop();
        if(dist[vert]!=dv) continue;
        for(auto x : adj[vert]){
            if(dist[x.first] > dist[vert]+x.second){
                dist[x.first] = dist[vert]+x.second;
                pq.push({dist[x.first], x.first});
            }
        }
    }

}
void printv(vector<ll> a)
{
    for(ll i=0; i<a.size(); i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
}
string operator * (string a, unsigned int b) {
    string output = "";
    while (b--) {
        output += a;
    }
    return output;
}
// const int INF = 1000000000;
// vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<ll> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    vector<bool> u(n, false);

    d[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,s});
    while(!pq.empty()){
        int v = pq.top().second;
        int dv = pq.top().first;
        pq.pop();
        if(dv!=d[v])continue;
        u[v]=true;
        for(auto e : adj[v]){
            if(d[e.first] > d[v]+e.second){
                d[e.first] = d[v]+e.second;
                pq.push({d[e.first],e.first}); 
            }
        }
    }
}

int dp[N] = {0};

ll logg = 50;
// vector<vector<int>> grid(N, vectr);
const ll yo = 2e5 + 1;
ll lookup_table[yo] = {};
ll fib_mem(ll n);
ll fib(ll n) { return n <= 1 ? n : fib_mem(n-1) + fib_mem(n-2); }

ll fib_mem(ll n)
{
    if (lookup_table[n] == 0) {
        lookup_table[n] = fib(n);
    }
    return lookup_table[n];
}
void solve()
{
    ll s, n; cin >> s >> n;
    map<ll, vector<pll>> mp;
    for(ll i=0; i<n; i++){
        ll v, w, k;
        cin >> v >> w >> k;
        if(k>=1)mp[w].push_back(make_pair(v, k));
    }
    vector<vector<ll>> dp(mp.size()+1, vector<ll>(s+1, LLONG_MIN));
    dp[0][0] = 0;
    ll allowed = 1;
    for(auto &[weight, items] : mp){
        sort(items.begin(), items.end(), greater<pll>());
        for(ll i=0; i<=s; i++){
            dp[allowed][i] = dp[allowed-1][i];
            ll cnt = 0, curitem = 0;
            ll earn = 0;
            ll used =0;
            while((cnt+1)*weight <= i && curitem<items.size()){
                cnt++;
                auto [val, maxcopies] = items[curitem];
                earn+=val;
                if(dp[allowed-1][i-cnt*weight]!=LLONG_MIN){
                    dp[allowed][i] = max(dp[allowed][i], dp[allowed-1][i-cnt*weight] + earn);
                }
                used++;
                if(used==maxcopies){
                    used = 0;
                    curitem++;
                }
            }
        }       
        allowed++;
    }
    cout << *max_element(dp.back().begin(), dp.back().end()) << '\n';

}
//dsu
/*
ll parent[N];
ll si[N];
ll sets = 0;
void make_set(ll v) 
{ //size based
    parent[v] = v;
    si[v] = 1;
    sets++; 
}

ll find_set(ll v)
{
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]); //path compression
}

void union_sets(ll a, ll b) 
{
    a = find_set(a);
    b = find_set(b);
    if (a != b) 
    {
        if (si[a] < si[b])
            swap(a, b);
        parent[b] = a;
        if (si[a] == si[b])
            si[a]++;
        sets--;
    }
}
*/


/*
// to use unordered hash map on a pair
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        // Hash the first element
        size_t hash1 = hash<T1>{}(p.first);
        // Hash the second element
        size_t hash2 = hash<T2>{}(p.second);
        // Combine the two hash values
        return hash1
               ^ (hash2 + 0x9e3779b9 + (hash1 << 6)
                  + (hash1 >> 2));
    }
};
// unordered_map<pair<int,int>, string, hash_pair> paths;
*/

// bool dfs(ll start, ll parent, vector<ll> &ans)
// {
    // vis[row][col] = 1;
    // cout << "visiting " << g[x][y] << " curvol = " << curvol;
    // for(ll i=0; i<4; i++)
    // {
    //     ll dx = h[i]; ll dy = v[i];
    //     if(x+dx<n && y+dy<m && x+dx>=0 && y+dy>=0 && g[x+dx][y+dy] && !vis[x+dx][y+dy])
    //     {
            
    //         dfs(g,x+dx,y+dy,n,m);
    //     }
    // }
// }



int main()
{
    // cout << log2(9)/log2(3) << '\n';
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ll t;
    // cin >> t;
    // while(t--)
    // {
    //     solve();
    // }
    solve();
}

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