oj.uz

Submission #496164

# Submission time Handle Problem Language Result Execution time Memory
496164 2021-12-20T20:29:50 Z f4t4nt Knapsack (NOI18_knapsack) C++11
100 / 100
 198 ms 36388 KB 
#include <algorithm>
#include <cmath>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>

#define ll long long
#define pll pair<ll, ll>
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vvvvl vector<vvvl>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define plvl pair<ll, vl>
#define vplvl vector<plvl>
#define sl set<ll>
#define spll set<pll>
#define vsl vector<sl>
#define ssl set<sl>
#define plsl pair<ll, sl>
#define vplsl vector<plsl>
#define msl multiset<ll>
#define mspll multiset<pll>
#define vb vector<bool>
#define vvb vector<vb>
#define mll map<ll, ll>
#define mlll map<ll, mll>
#define mlvl map<ll, vl>
#define mlpll map<ll, pll>
#define mlvpll map<ll, vpll>
#define mlsl map<ll, sl>
#define mpllb map<pll, bool>
#define vmll vector<mll>
#define ql queue<ll>
#define qpll queue<pll>
#define fl float
#define vf vector<fl>
#define vvf vector<vf>
#define str string
#define vstr vector<str>
#define mstrl map<str, ll>

#define pb push_back
#define elif else if
#define sz(C) (ll) C.size()
#define flip(C) reverse(C.begin(), C.end())
#define ssort(C) sort(C.begin(), C.end())
#define rsort(C) sort(C.begin(), C.end(), greater<pll>())
#define max_elem(C) *max_element(C.begin(), C.end())
#define min_elem(C) *min_element(C.begin(), C.end())

#define FOR(x, e) for(ll  x = 0; x < (ll) e; x++)
#define FORR(x, e) for(ll x = (ll) e - 1; x >= 0; x--)
#define FOB(x, b, e) for(auto x = (ll) b; x != (ll) e; x++)
#define FOE(x, e, b) for(auto x = (ll) e - 1; x >= (ll) b; x--)
#define FOI(x, e, i) for(ll x = 0; x < (ll) e; x += (ll) i)
#define FORE(x, C) for(auto& x : C)

using namespace std;

int main()
{
    ll S, N;
    cin >> S >> N;
    mlvpll W;
    FOR(n, N)
    {
        ll v, w, k;
        cin >> v >> w >> k;
        W[w].pb({ v, k });
    }
    ll M = sz(W) + 1;
    S++;
    vvl dp(M, vl(S));
    ll m = 1;
    FORE(x, W)
    {
        ll w = x.first;
        vpll &v = x.second;
        rsort(v);
        dp[m] = dp[m - 1];
        FOR(s, S)
        {
            ll i = 1, j = 0, k = 0, p = 0;
            while(i * w <= s && j < sz(v))
            {
                p += v[j].first;
                dp[m][s] = max(dp[m][s], dp[m - 1][s - i * w] + p);
                i++; k++;
                if(k == v[j].second)
                { k = 0; j++; }
            }
        }
        m++;
    }
    cout << max_elem(dp[M - 1]) << '\n';
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 208 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1740 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1700 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1740 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1700 KB Output is correct
9 Correct 3 ms 1740 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 6 ms 296 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 1740 KB Output is correct
17 Correct 2 ms 1700 KB Output is correct
18 Correct 2 ms 1740 KB Output is correct
19 Correct 2 ms 1712 KB Output is correct
20 Correct 2 ms 1868 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 2 ms 1868 KB Output is correct
12 Correct 2 ms 1700 KB Output is correct
13 Correct 3 ms 1740 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 296 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 1740 KB Output is correct
21 Correct 2 ms 1700 KB Output is correct
22 Correct 2 ms 1740 KB Output is correct
23 Correct 2 ms 1712 KB Output is correct
24 Correct 2 ms 1868 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 8 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 4 ms 1740 KB Output is correct
31 Correct 2 ms 1868 KB Output is correct
32 Correct 2 ms 1740 KB Output is correct
33 Correct 2 ms 1740 KB Output is correct
34 Correct 2 ms 1740 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct
11 Correct 2 ms 1868 KB Output is correct
12 Correct 2 ms 1700 KB Output is correct
13 Correct 3 ms 1740 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 6 ms 296 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 2 ms 1740 KB Output is correct
21 Correct 2 ms 1700 KB Output is correct
22 Correct 2 ms 1740 KB Output is correct
23 Correct 2 ms 1712 KB Output is correct
24 Correct 2 ms 1868 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 8 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 4 ms 1740 KB Output is correct
31 Correct 2 ms 1868 KB Output is correct
32 Correct 2 ms 1740 KB Output is correct
33 Correct 2 ms 1740 KB Output is correct
34 Correct 2 ms 1740 KB Output is correct
35 Correct 63 ms 3244 KB Output is correct
36 Correct 87 ms 3364 KB Output is correct
37 Correct 72 ms 3376 KB Output is correct
38 Correct 77 ms 3684 KB Output is correct
39 Correct 99 ms 4144 KB Output is correct
40 Correct 198 ms 36388 KB Output is correct
41 Correct 131 ms 35624 KB Output is correct
42 Correct 149 ms 35680 KB Output is correct
43 Correct 159 ms 35608 KB Output is correct
44 Correct 157 ms 35488 KB Output is correct
45 Correct 116 ms 7740 KB Output is correct
46 Correct 127 ms 3952 KB Output is correct
47 Correct 112 ms 11208 KB Output is correct
48 Correct 127 ms 20460 KB Output is correct
49 Correct 91 ms 4768 KB Output is correct
50 Correct 125 ms 4760 KB Output is correct