Submission #779308

#	Time	Username	Problem	Language	Result	Execution time	Memory
779308		yash_babel	Knapsack (NOI18_knapsack)	C++14	100 / 100	192 ms	252792 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define f(i, a, b) for (ll i = a; i < b; i++)
#define fr(i, a, b) for (ll i = b - 1; i >= a; i--)
#define fx(i, a, b, x) for (ll i = a; i < b; i += x)
#define fa(x) for (auto ele : x)
#define fav(tmp, x) for (auto tmp : x)

#define all(x) (x).begin(), (x).end()
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppiii pair<pair<int, int>, int>
#define p(e1, e2) pair<e1, e2>

#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define v(ele) vector<ele>

#define sei set<int>
#define sel set<ll>
#define ses set<string>
#define sec set<char>
#define se(ele) set<ele>

#define mii map<int, int>
#define mll map<ll, ll>
#define mp(e1, e2) map<e1, e2>
#define mcpci map<char, pair<char, int>>
#define mic map<int, char>
#define mci map<char, int>
#define mcsei map<char, sei>
#define mcvi map<char, vi>
#define mci map<char, int>
#define msi map<string, int>

#define qi queue<int>
#define ql queue<ll>
#define qpii queue<pair<int, int>>

const ll mod = 1e9 + 7;
const ll INF = 1e16;
const ll NEG_INF = LONG_LONG_MIN;

const ll N = 2e5 + 20;
// const int N = 11;

ll knapsack(v(vl) vec, ll s)
{
    ll n = vec.size();
    v(vl) dp(n, vl(s + 1));
    f(i, 0, n)
    {
        dp[i][0] = 0;
    }
    f(j, vec[0][0], s + 1)
    {
        dp[0][j] = vec[0][1];
    }
    f(i, 1, n)
    {
        f(j, 1, s + 1)
        {
            if (j - vec[i][0] >= 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - vec[i][0]] + vec[i][1]);
            }
            if (i > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            }
        }
    }
    return dp[n - 1][s];
}

void solve()
{
    ll s, n;
    cin >> s >> n;
    v(vl) arr;
    f(i, 0, n)
    {
        ll v, w, k;
        cin >> v >> w >> k;
        if (w <= s)
        {
            arr.push_back({-v, w, k});
        }
    }
    v(vl) vec;
    vl cnt(s + 1);
    f(i, 1, s + 1)
    {
        cnt[i] = s / i;
    }
    sort(all(arr));
    fa(arr)
    {
        ll lim = min({ele[2], cnt[ele[1]]});
        f(i, 0, lim)
        {
            vec.push_back({ele[1], -ele[0]});
            cnt[ele[1]]--;
        }
    }
    cout << knapsack(vec, s) << '\n';
    return;
}

void sig_handler(int signum)
{
    printf("Inside handler function\n");
    exit(0);
}
int main()
{
    time_t begin, end;
    time(&begin);
    // signal(SIGALRM, sig_handler);
    // alarm(2);
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    time(&end);
    time_t elapsed = end - begin;
    // printf("Time measured: %ld seconds.\n", elapsed);
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:141:12: warning: unused variable 'elapsed' [-Wunused-variable]
  141 |     time_t elapsed = end - begin;
      |            ^~~~~~~

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