oj.uz

Submission #915195

# Submission time Handle Problem Language Result Execution time Memory
915195 2024-01-23T13:12:31 Z emadflash Knapsack (NOI18_knapsack) C++14
73 / 100
 1000 ms 3160 KB 
#include <bits/stdc++.h>

namespace flash {
	using namespace std;

	inline void fast_io() {
		ios_base::sync_with_stdio(false);
		cin.tie(0);
	}

	// Type Aliases
    template <typename T> using V = vector<T>;
	using ld = long double;
	using ll = long long;
	using vi = V<int>;
	using vvi = V<V<int>>;
	using vll = V<ll>;
	using vvll = V<V<ll>>;
	using pii = pair<int, int>;
	using pill = pair<int, ll>;
	using vpii = V<pii>;
	using vpill = V<pill>;
	using vvpii = V<vpii>;
    using vs = V<string>;
	using si = set<int>;
	using sll = set<ll>;
	using spii = set<pii>;
	using spill = set<pill>;
	using di = deque<int>;
	using dpii = deque<pii>;
	using dpill = deque<pill>;
	template <typename T> using hashset = unordered_set<T>;
	template <typename T1, typename T2> using hashmap = unordered_map<T1, T2>;

	// Constants
	static const ll INF = 1e18;
	static const int MOD = 1e9 + 7;

	#define gcd(x, y) (__gcd(x,y))
	#define lcm(x, y) ((1LL * (x) * (y)) / gcd(x, y))

	// Shorthands
    #define all(x) x.begin(),x.end()
    #define UB(a,x) upper_bound(all(a), x)
    #define LB(a,x) lower_bound(all(a), x)

	// Loop
	#define forx(i, a, b) for (int i = a; i < b; i++)
	#define fori(n) for (int i = 0; i < n; ++i)
	#define forj(n) for (int j = 0; j < n; ++j)
	#define fork(n) for (int k = 0; k < n; ++k)
	#define loop(n) for (int _ = 0; _ < n; ++_)
	#define endl '\n'

    template <typename T> T max(T a) { return a; }
    template <typename T> T min(T a) { return a; }

    template <typename T, typename... Param>
    T max(T a, Param... param) {
        static_assert((std::is_same<T, Param>::value && ...));
        T rest = max(param...); return (a > rest) ? a : rest;
    }

    template <typename T, typename... Param>
    T min(T a, Param... param) {
        static_assert((std::is_same<T, Param>::value && ...));
        T rest = min(param...); return (a < rest) ? a : rest;
    }

	template <typename T, typename ...Param>
    void max_self(T &a, const Param & ... param) { T rest = max(param...); if (rest > a) a = rest; }

	template <typename T, typename ...Param>
    void min_self(T &a, const Param & ... param) { T rest = min(param...); if (rest < a) a = rest; }

	template <typename T, typename Fn = function<T(T,T)>>
	inline auto prefix_sum(const vector<T> &v, Fn f = [](T x, T y) { return x + y; }) {
		vector<T> r(v.size());
		partial_sum(v.begin(), v.end(), r.begin(), f);
		return r;
	}

	template <typename T, typename Fn = function<T(T,T)>>
	inline auto suffix_sum(const vector<T> &v, Fn f = [](T x, T y) { return x + y; }) {
		vector<T> r(v.size());
		partial_sum(v.rbegin(), v.rend(), r.rbegin(), f);
		return r;
	}

    // IO
    template <typename T>
    istream& operator>>(istream &is, vector<T> &v) {
        fori(v.size()) is >> v[i];
        return is;
    }

    template <typename T1, typename T2>
    ostream& operator<<(ostream &os, const pair<T1,T2> &p) {
        os << "(" << p.first << "," << p.second << ")";
        return os;
    }

	template <typename T>
	ostream& dump_container(ostream &os, T begin, T end) {
        os << '[';
        for (; begin != end; ++begin) {
            os << *begin;
            if (end-begin != 1) os << ", ";
        }
        os << ']';
		return os;
	}

    template <typename T>
    ostream& operator<<(ostream &os, const V<T> &v) { return dump_container(os, v.begin(), v.end()); }

    template <typename T>
    ostream& operator<<(ostream &os, const deque<T> &v) {  return dump_container(os, v.begin(), v.end()); }

	template <typename T> void print(const T &t) { cout << t; }
	template <typename P1, typename ...Param>
	void print(const P1 &p1, const Param & ... param) {
		cout << p1 << ' ';
		print(param ...);
	}

	struct fmt { const string &data; fmt(const string &data) : data(data) {}};

	template <typename ...Param>
	void print(const fmt &f, const Param & ... param) { size_t i=0; print(f, i, param ...); }

	template <typename P1>
	void print(const fmt &f, size_t &i, const P1 &p1) {
		for (; i < f.data.length(); ++i) {
			if (i+1 < f.data.length() && f.data[i] == '{' && f.data[i+1] == '}') {
				cout << p1;
				i++;
			} else {
				cout << f.data[i];
			}
		}
	}

	template <typename P1, typename ...Param>
	void print(const fmt &f, size_t &i, const P1 &p1, const Param & ... param) {
		for (; i < f.data.length()-1; ++i) {
			if (f.data[i] == '{' && f.data[i+1] == '}') {
				cout << p1;
				i += 2;
				print(f, i, param ...);
			} else {
				cout << f.data[i];
			}
		}
	}

	template <typename T> void println(const T &t) { cout << t << endl; }
	template <typename P1, typename ...Param>
	void println(const P1 &p1, const Param & ... param) {
		cout << p1 << ' ';
		println(param ...);
	}

	template <typename ...Param>
	void println(const fmt &f, const Param & ... param) {
		print(f, param ...);
		cout << '\n';
	}
}; // namespace flash

using namespace flash;

// UNSOLVED

const int N = 1e5+1;
int S;
int n;
int weights[N];
ll values[N];
int copies[N];

template <const int T = 0>
void solve() {
    cin >> S >> n;
    fori(n) {
        cin >> values[i] >> weights[i] >> copies[i];
    }

    const ll INF = numeric_limits<ll>::max();
    V<ll> dp(S+1, -INF);
    dp[0] = 0;

    fori(n) {
        for (int s = S; s >= weights[i]; --s) {
            ll profit = values[i];
            int c = 1;

            for (int J = s - weights[i]; J >= 0 && c <= copies[i]; J -= weights[i]) {
                if (J < 0) break;
                if (dp[J] != -INF)
                    max_self(dp[s], profit + dp[J]);
                profit += values[i];
                ++c;
            }
        }
    }

    ll answer = 0;
    fori(S) {
        max_self(answer, dp[i+1]);
    }
    println(answer);
}

template <>
void solve<1>() {
    int tc; cin >> tc;
    while (tc-->0) {
        solve<0>();
    }
}

int main() {
	fast_io();
	solve();
	return 0;
}

Compilation message

knapsack.cpp: In function 'T flash::max(T, Param ...)':
knapsack.cpp:60:57: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   60 |         static_assert((std::is_same<T, Param>::value && ...));
      |                                                         ^~~
knapsack.cpp: In function 'T flash::min(T, Param ...)':
knapsack.cpp:66:57: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17'
   66 |         static_assert((std::is_same<T, Param>::value && ...));
      |                                                         ^~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 484 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 464 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 484 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 96 ms 464 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 464 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 484 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 96 ms 464 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 2 ms 348 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 15 ms 2908 KB Output is correct
36 Execution timed out 1028 ms 3160 KB Time limit exceeded
37 Halted 0 ms 0 KB -