Submission #625572

#	Time	Username	Problem	Language	Result	Execution time	Memory
625572		Huy	Knapsack (NOI18_knapsack)	C++17	100 / 100	66 ms	3680 KiB

knapsack

/// punch then pray
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const int N = (int)1e5 ;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;
const int block_size = 710;

void InputFile()
{
    //freopen("feast.in","r",stdin);
    //freopen("feast.out","w",stdout);
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct Tdata
{
    int val,wei,cop;
};

int S,n;
Tdata a[maxN];
int dp[2][2001];
vector<int> save[2001];

bool FA(Tdata x,Tdata y)
{
    return x.val > y.val;
}

void Read()
{
    cin >> S >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].val >> a[i].wei >> a[i].cop;
    }
    sort(a + 1,a + n + 1,FA);
    for(int i = 1;i <= n;i++)
    {
        while(save[a[i].wei].size() < (S / a[i].wei) && a[i].cop > 0)
        {
            save[a[i].wei].push_back(a[i].val);
            a[i].cop--;
        }
    }

    for(int i = 1;i <= S;i++)
    {
        int cur = i & 1;
        int pre = cur ^ 1;
        for(int j = 0;j <= S;j++)
        {
            dp[cur][j] = dp[pre][j];
            int used = 0;
            int sum = 0;
            for(int k : save[i])
            {
                sum += k;
                used++;
                if(used * i > j) break;
                dp[cur][j] = max(dp[cur][j],dp[pre][j-used*i] + sum);
            }
        }
    }
    cout << dp[S&1][S];
}

void Solve()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve()
    int test;
    //cin >> test;
    test = 1;
    while(test--)
    {
        Read();
        Solve();
        //Debug();
    }
}
////
/////
//////

Compilation message (stderr)

knapsack.cpp: In function 'void Read()':
knapsack.cpp:63:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         while(save[a[i].wei].size() < (S / a[i].wei) && a[i].cop > 0)
      |               ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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