oj.uz

Submission #853737

# Submission time Handle Problem Language Result Execution time Memory
853737 2023-09-25T07:09:04 Z Pratik8696 Knapsack (NOI18_knapsack) C++17
100 / 100
 496 ms 36792 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
// use less_equal to make it multiset
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
typedef pair<double, double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int>> vv32;
typedef vector<vector<ll>> vv64;
typedef vector<vector<p64>> vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<pair<p64, ll>> vpp64;
typedef set<ll> s64;
typedef set<p64> sp64;
typedef multiset<ll> ms64;
typedef multiset<p64> msp64;
typedef map<ll, ll> m64;
typedef map<ll, v64> mv64;
typedef unordered_map<ll, v64> uv64;
typedef unordered_map<ll, ll> u64;
typedef unordered_map<p64, ll> up64;
typedef unordered_map<ll, vp64> uvp64;
typedef priority_queue<ll> pq64;
typedef priority_queue<ll, v64, greater<ll>> pqs64;
const int MOD = 1000000007;
double eps = 1e-12;
#define forn(i, n) for (ll i = 0; i < n; i++)
#define forsn(i, s, e) for (ll i = s; i < e; i++)
#define rforn(i, s) for (ll i = s; i >= 0; i--)
#define rforsn(i, s, e) for (ll i = s; i >= e; i--)
struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(p64 x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM);
    }
    size_t operator()(ll x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
typedef gp_hash_table<ll, ll, custom_hash> fm64;
typedef gp_hash_table<p64, ll, custom_hash> fmp64;

#define ln "\n"
#define mp make_pair
#define ie insert
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define al(arr, n) arr, arr + n
#define sz(x) ((ll)(x).size())
#define dbg(a) cout << a << endl;
#define dbg2(a) cout << a << ' ';
using ld = long double;
using db = double;
using str = string; // yay python!
// INPUT
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
tcT > void re(T &x)
{
    cin >> x;
}
tcTUU > void re(T &t, U &...u)
{
    re(t);
    re(u...);
}

// function for prime factorization
vector<pair<ll, ll>> pf(ll n)
{
    vector<pair<ll, ll>> prime;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            int count = 0;
            while (n % i == 0)
            {
                count++;
                n = n / i;
            }
            prime.pb(mp(i, count));
        }
    }
    if (n > 1)
    {
        prime.pb(mp(n, 1));
    }
    return prime;
}

// sum of digits of a number
ll sumofno(ll n)
{
    ll sum = 0;
    while (n != 0)
    {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}

// modular exponentiation
long long modpow(long long x, long long n, long long p)
{

    if (n == 0)
        return 1 % p;

    ll ans = 1, base = x;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            ans = (ans * base) % p;
            n--;
        }
        else
        {
            base = (base * base) % p;
            n /= 2;
        }
    }
    if (ans < 0)
        ans = (ans + p) % p;
    return ans;
}

// const int N = 1e6 + 100;
// long long fact[N];
//  initialise the factorial
// void initfact(){
// fact[0] = 1;
// for (int i = 1; i < N; i++)
//{
// fact[i] = (fact[i - 1] * i);
// fact[i] %= MOD;
// }}

// formula for c
// ll C(ll n, ll i)
//{
// ll res = fact[n];
// ll div = fact[n - i] * fact[i];
// div %= MOD;
// div = modpow(div, MOD - 2, MOD);
// return (res * div) % MOD;
// }

long long CW(ll n, ll m)
{
    if (m > n - m)
        m = n - m;
    long long ans = 1;
    for (int i = 0; i < m; i++)
    {
        ans = ans * (n - i) / (i + 1);
    }
    return ans;
}

// function for fast expo
ll fastexpo(ll a, ll b)
{
    if (b == 0)
    {
        return 1;
    }
    if (a == 0)
    {
        return 0;
    }
    ll y = fastexpo(a, b / 2);
    if (b % 2 == 0)
    {
        return y * y;
    }
    else
    {
        return a * y * y;
    }
}

ll popcount(ll n)
{
    ll c = 0;
    for (; n; ++c)
        n &= n - 1;
    return c;
}

ll ce(ll x, ll y)
{
    ll res = x / y;
    if (x % y != 0)
    {
        res++;
    }
    return res;
}

bool pow2(ll x)
{
    ll res = x & (x - 1);
    if (res == 0)
    {
        return true;
    }
    return false;
}

bool isPrime(int x)
{
    for (int d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
            return false;
    }
    return true;
}

vector<vector<p64>> arr(2001);
ll sum(ll idx, ll rem, vv64 &dp)
{
    if (idx == sz(arr) || rem == 0)
    {
        return 0;
    }
    auto &x = dp[idx][rem];
    if (x != -1)
    {
        return x;
    }
    // take it
    ll ans = 0;
    ans = max(sum(idx + 1, rem, dp), ans);
    ll cc = 0, val = 0;
    for (auto t : arr[idx])
    {
        auto value = t.first;
        auto copies = t.second;
        while (copies--)
        {
            cc++;
            val += value;
            if (rem - cc * idx >= 0)
            {
                ans = max(ans, sum(idx + 1, rem - cc * idx, dp) + val);
            }
            else
            {
                break;
            }
        }
    }
    return x = ans;
}

void solve()
{
    ll s, n;
    cin >> s >> n;
    forn(i, n)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        // value weight count
        if (b > s)
            continue;
        arr[b].pb({a, c});
    }
    forsn(i, 1, 2001)
    {
        sort(all(arr[i]), greater<p64>());
    }
    vv64 dp(2001, v64(2001, -1));
    dbg(sum(0, s, dp));
}

int main()
{
    fast_cin();
    // #ifndef ONLINE_JUDGE
    //   freopen("revegetate.in", "r", stdin);
    //  freopen("revegetate.out", "w", stdout);
    // #endif
    ll t = 1;
    // cin >> t;
    for (int it = 1; it <= t; it++)
    {
        solve();
    }
    return 0;
}

/*
1. Check borderline constraints. Can a variable you are dividing by be 0?
2. Use ll while using bitshifts
3. Do not erase from set while iterating it
4. Initialise everything
5. Read the task carefully, is something unique, sorted, adjacent, guaranteed??
6. DO NOT use if(!mp[x]) if you want to iterate the map later
7. Are you using i in all loops? Are the i's conflicting?
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32088 KB Output is correct
2 Correct 11 ms 32088 KB Output is correct
3 Correct 15 ms 32088 KB Output is correct
4 Correct 12 ms 32092 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32096 KB Output is correct
2 Correct 14 ms 32088 KB Output is correct
3 Correct 15 ms 32088 KB Output is correct
4 Correct 12 ms 32092 KB Output is correct
5 Correct 13 ms 32088 KB Output is correct
6 Correct 61 ms 32144 KB Output is correct
7 Correct 68 ms 32140 KB Output is correct
8 Correct 52 ms 32088 KB Output is correct
9 Correct 65 ms 32092 KB Output is correct
10 Correct 68 ms 32144 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32096 KB Output is correct
2 Correct 14 ms 32088 KB Output is correct
3 Correct 15 ms 32088 KB Output is correct
4 Correct 12 ms 32092 KB Output is correct
5 Correct 13 ms 32088 KB Output is correct
6 Correct 61 ms 32144 KB Output is correct
7 Correct 68 ms 32140 KB Output is correct
8 Correct 52 ms 32088 KB Output is correct
9 Correct 65 ms 32092 KB Output is correct
10 Correct 68 ms 32144 KB Output is correct
11 Correct 11 ms 32088 KB Output is correct
12 Correct 42 ms 32088 KB Output is correct
13 Correct 15 ms 32088 KB Output is correct
14 Correct 11 ms 32088 KB Output is correct
15 Correct 12 ms 32088 KB Output is correct
16 Correct 73 ms 32092 KB Output is correct
17 Correct 73 ms 32088 KB Output is correct
18 Correct 62 ms 32088 KB Output is correct
19 Correct 73 ms 32088 KB Output is correct
20 Correct 72 ms 32088 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32088 KB Output is correct
2 Correct 11 ms 32088 KB Output is correct
3 Correct 15 ms 32088 KB Output is correct
4 Correct 12 ms 32092 KB Output is correct
5 Correct 11 ms 32096 KB Output is correct
6 Correct 14 ms 32088 KB Output is correct
7 Correct 15 ms 32088 KB Output is correct
8 Correct 12 ms 32092 KB Output is correct
9 Correct 13 ms 32088 KB Output is correct
10 Correct 61 ms 32144 KB Output is correct
11 Correct 68 ms 32140 KB Output is correct
12 Correct 52 ms 32088 KB Output is correct
13 Correct 65 ms 32092 KB Output is correct
14 Correct 68 ms 32144 KB Output is correct
15 Correct 11 ms 32088 KB Output is correct
16 Correct 42 ms 32088 KB Output is correct
17 Correct 15 ms 32088 KB Output is correct
18 Correct 11 ms 32088 KB Output is correct
19 Correct 12 ms 32088 KB Output is correct
20 Correct 73 ms 32092 KB Output is correct
21 Correct 73 ms 32088 KB Output is correct
22 Correct 62 ms 32088 KB Output is correct
23 Correct 73 ms 32088 KB Output is correct
24 Correct 72 ms 32088 KB Output is correct
25 Correct 11 ms 32088 KB Output is correct
26 Correct 82 ms 32148 KB Output is correct
27 Correct 14 ms 32088 KB Output is correct
28 Correct 12 ms 32124 KB Output is correct
29 Correct 11 ms 32176 KB Output is correct
30 Correct 75 ms 32088 KB Output is correct
31 Correct 69 ms 32088 KB Output is correct
32 Correct 64 ms 32088 KB Output is correct
33 Correct 66 ms 32088 KB Output is correct
34 Correct 65 ms 32088 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32088 KB Output is correct
2 Correct 11 ms 32088 KB Output is correct
3 Correct 15 ms 32088 KB Output is correct
4 Correct 12 ms 32092 KB Output is correct
5 Correct 11 ms 32096 KB Output is correct
6 Correct 14 ms 32088 KB Output is correct
7 Correct 15 ms 32088 KB Output is correct
8 Correct 12 ms 32092 KB Output is correct
9 Correct 13 ms 32088 KB Output is correct
10 Correct 61 ms 32144 KB Output is correct
11 Correct 68 ms 32140 KB Output is correct
12 Correct 52 ms 32088 KB Output is correct
13 Correct 65 ms 32092 KB Output is correct
14 Correct 68 ms 32144 KB Output is correct
15 Correct 11 ms 32088 KB Output is correct
16 Correct 42 ms 32088 KB Output is correct
17 Correct 15 ms 32088 KB Output is correct
18 Correct 11 ms 32088 KB Output is correct
19 Correct 12 ms 32088 KB Output is correct
20 Correct 73 ms 32092 KB Output is correct
21 Correct 73 ms 32088 KB Output is correct
22 Correct 62 ms 32088 KB Output is correct
23 Correct 73 ms 32088 KB Output is correct
24 Correct 72 ms 32088 KB Output is correct
25 Correct 11 ms 32088 KB Output is correct
26 Correct 82 ms 32148 KB Output is correct
27 Correct 14 ms 32088 KB Output is correct
28 Correct 12 ms 32124 KB Output is correct
29 Correct 11 ms 32176 KB Output is correct
30 Correct 75 ms 32088 KB Output is correct
31 Correct 69 ms 32088 KB Output is correct
32 Correct 64 ms 32088 KB Output is correct
33 Correct 66 ms 32088 KB Output is correct
34 Correct 65 ms 32088 KB Output is correct
35 Correct 40 ms 33780 KB Output is correct
36 Correct 103 ms 34984 KB Output is correct
37 Correct 105 ms 34748 KB Output is correct
38 Correct 36 ms 34992 KB Output is correct
39 Correct 41 ms 35648 KB Output is correct
40 Correct 487 ms 36432 KB Output is correct
41 Correct 446 ms 35532 KB Output is correct
42 Correct 483 ms 35776 KB Output is correct
43 Correct 483 ms 35776 KB Output is correct
44 Correct 496 ms 35784 KB Output is correct
45 Correct 418 ms 36488 KB Output is correct
46 Correct 41 ms 35512 KB Output is correct
47 Correct 399 ms 36792 KB Output is correct
48 Correct 403 ms 36480 KB Output is correct
49 Correct 54 ms 35920 KB Output is correct
50 Correct 368 ms 35668 KB Output is correct