Submission #574430

#	Time	Username	Problem	Language	Result	Execution time	Memory
574430		Bad_day_toCode	Knapsack (NOI18_knapsack)	C++17	100 / 100	117 ms	36212 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;

#define ll long long int
#define fo(i, n) for (ll i = 0; i < n; i++)
#define Fo(i, k, n) for (ll i = k; i < n; i++)
#define fvr(it, v) for (auto it = v.rbegin(); it != v.rend(); ++it)
#define ALL(c) (c).begin(), (c).end() // handy for function like "sort()"
#define mod 1000000007
#define ff first
#define ss second
const long long MOD = 998244353;
const long long INF = 1e9 + 7;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vli;
typedef pair<int, int> pii;
long long sq(int x) { return 1ll * x * x; }
const int MAXN = 20000001;

// Sieve
// ll d[MAXN], divCnt[MAXN];
// vector<ll> primes;
// void sieve(ll n)
// {

//     fo(i, n)
//     {
//         d[i] = i;
//     }
//     Fo(i, 2, n)
//     {
//         if (d[i] == i)
//             primes.push_back(i);

//         for (ll j = 0; j < ((ll)primes.size()) && primes[j] <= d[i] && primes[j] * i < n; j++)
//         {
//             d[i * primes[j]] = primes[j];
//         }
//     }
//     Fo(i, 2, n)
//     {
//         ll j = i / d[i];
//         divCnt[n] = divCnt[j] + (d[i] != d[j]);
//     }
// }
// ll primeFactors(ll n)
// {
//     set<ll> factors;
//     while (n != 1)
//     {
//         factors.insert(d[n]);
//         n /= d[n];
//     }
//     return factors.size();
// }
ll mul(ll x, ll y)
{
    return (x * 1ll * y) % MOD;
}

ll binpow(ll a, ll b, ll c)

{
    ll res = 1;
    a = a % c;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % c;

        b = b >> 1;
        a = (a * a) % c;
    }
    return res;
}
long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// int fact[200043];

// void precalc()
// {
//     fact[0] = 1;
//     for (int i = 1; i < 200043; i++)
//         fact[i] = mul(fact[i - 1], i);
// }

// Function to return LCM of two numbers
// int lcm(int a, int b)
// {
//     return (a / gcd(a, b)) * b;
// }
ll inv(ll x, ll c)
{
    return binpow(x, c - 2, c);
}

// int divide(int x, int y, int c)
// {
//     return mul(x, inv(y, c));
// }
// int nCr(int n, int r, int c)
// {
//     return divide(fact[n], mul(fact[r], fact[n - r]), c);
// }
bool cmp1(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
    if (a.first == b.first)
    {
        return a.second > b.second;
    }
    return a.first > b.first;
}
bool cmp2(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
    if (a.second == b.second)
    {
        return a.first < b.first;
    }
    return a.second > b.second;
}
ll find_sum(ll idx, vector<ll> &bit)
{
    ll ans = 0;
    for (; idx > 0; idx -= idx & (-idx))
        ans += bit[idx];
    return ans;
}
void update(ll pos, ll val, vector<ll> &bit)
{
    for (; pos <= bit.size(); pos += pos & (-pos))
    {
        bit[pos] += val;
    }
}



void solve()
{
    ll S,n;
    cin>>S>>n;
    map<ll,vector<pair<ll,ll>>> weight;
    fo(i,n){
        ll v,w,k;
        cin>>v>>w>>k;
        weight[w].push_back({v,k});
    }
    ll cur=1;
    ll dp[weight.size()+1][S+1];
    fo(i,weight.size()+1){
        fo(j,S+1)dp[i][j]=-LONG_LONG_MAX;
    }
    dp[0][0]=0;
    ll ans=0;
    for(auto& x:weight){
        ll w=x.first;
        auto k=x.second;
        sort(ALL(k),cmp1);
        
       
        fo(i,S+1){
            dp[cur][i]=dp[cur-1][i];
            ll amount=0, a=0,p=0,used=0;
            while((amount+1)*w<=i && a<k.size()){
                amount++;
                p+=k[a].first;
                if(dp[cur-1][i-amount*w]!=-LONG_LONG_MAX){
                    
                    // cout<<dp[cur][i]<<" "<<i<<" "<<amount<<" "<<w<<" "<<cur<<endl;
                    dp[cur][i]=max(dp[cur][i],dp[cur-1][i-amount*w]+p);
                    ans=max(ans,dp[cur][i]);
                }
                used++;
                if(used==k[a].second){
                    used=0;
                    a+=1;
                }

            }
        }
        cur+=1;
    }
    cout<<ans<<endl;
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, i = 0;
    t = 1;
    // freopen("feast.in", "r", stdin);

    // freopen("feast.out", "w", stdout);
    // cin >> t;

    while (t--)
    {
        i++;
        // cout<<"Case #"<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void update(long long int, long long int, std::vector<long long int>&)':
knapsack.cpp:148:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (; pos <= bit.size(); pos += pos & (-pos))
      |            ~~~~^~~~~~~~~~~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:17:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::map<long long int, std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | #define fo(i, n) for (ll i = 0; i < n; i++)
......
  168 |     fo(i,weight.size()+1){
      |        ~~~~~~~~~~~~~~~~~           
knapsack.cpp:168:5: note: in expansion of macro 'fo'
  168 |     fo(i,weight.size()+1){
      |     ^~
knapsack.cpp:182:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |             while((amount+1)*w<=i && a<k.size()){
      |                                      ~^~~~~~~~~

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