Submission #908875

#	Time	Username	Problem	Language	Result	Execution time	Memory
908875		tiwerlol	Knapsack (NOI18_knapsack)	C++17	100 / 100	79 ms	35208 KiB

knapsack

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

ofstream fout("feast.out");
ifstream fin("feast.in");

#define miauDebug
#ifdef miauDebug
#define mau(x) MIAUMIAU(#x, x)
#else
#define mau(x)
#endif

void MIAUMIAU(const char* var_name, auto var_value) {
    cout << var_name << " = " << var_value << endl;
}

using ll = long long;
const int nM = 1e3+12;

const ll MOD =
1000000007;

ll dp[2001][2001];

void solve() {
    int s, n; cin >> s >> n;
    map<int, vector<pair<int, int>>> v;

    for(int z = 0; z < n; z++)
    {
        int val, g, cnt; cin >> val >> g >> cnt;

        v[g].push_back(make_pair(val, cnt));
    }

    int unde = 1;
    dp[0][0] = 1;
    for(auto &[g, prod] : v)
    {
        sort(prod.begin(), prod.end(), greater<pair<int, int>>());
        for(int i = 0; i <= s; i++)
        {
            dp[unde][i] = dp[unde-1][i];
            ll profit = 0, fol = 0, k = 0, copi = 0, sum = 0;

            while((copi + 1)*g <= i && k < prod.size())
            {
                copi++;
                sum += prod[k].first;
                dp[unde][i] = max(dp[unde][i], dp[unde-1][i- copi*g] + sum);
                fol++;
                if(fol==prod[k].second)
                {
                    fol = 0;
                    k++;
                }
            }
        }
        unde++;
    }
    ll mx = 0;
    for(int z = 0; z <= s; z++)
    {
        mx = max(mx, dp[unde-1][z]);
    }
    cout << mx-1;
}

signed main()
{
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    //cin >> p;
    int tt = 1;// cin >> tt;

    while(tt--)
        solve();
}

/*
5
3 1 6 3
iiiii
*/

Compilation message (stderr)

knapsack.cpp:14:37: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   14 | void MIAUMIAU(const char* var_name, auto var_value) {
      |                                     ^~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:47:42: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while((copi + 1)*g <= i && k < prod.size())
      |                                        ~~^~~~~~~~~~~~~
knapsack.cpp:45:16: warning: unused variable 'profit' [-Wunused-variable]
   45 |             ll profit = 0, fol = 0, k = 0, copi = 0, sum = 0;
      |                ^~~~~~

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