Submission #471053

#	Time	Username	Problem	Language	Result	Execution time	Memory
471053		Evang	Knapsack (NOI18_knapsack)	C++17	73 / 100	1097 ms	316 KiB

knapsack

#include "bits/extc++.h"
using namespace std;

#ifdef LOCAL
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

#define inf 1000000000
#define llinf 1000000000000000000ll
#define uset unordered_set
#define umap unordered_map
#define mp(a,b) make_pair(a,b)
#define mt(x...) make_tuple(x)
#define eb(x...) emplace_back(x)
#define pb(x) push_back(x)
#define ff first
#define ss second
const char el = '\n', sp = ' ';
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
template<class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

const int S = 2005;
int s, n, dp[S];

void fun(int a, int c){
    for(int i = s; i >= c; --i)
        dp[i] = max(dp[i], dp[i-c] + a);
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif

    cin >> s >> n;
    while(n--){
        int a, c, k;
        cin >> a >> c >> k;
//        while(k--) {
//            fun(a, c);
//        }
        int b[35] = {0};
        for(int i = 0; k > 0; ++i) {
            b[i] = k&1;
            k/=2;
        }
        for(int i = 1; i < 35; ++i)
            if(b[i]&&!b[i-1]){
                b[i] = 0;
                for(int j = i-1; j >= 0 && !b[j]; --j){
                    if(j==0||b[j-1])
                        b[j] = 2;
                    else
                        b[j] = 1;
                }
            }

        for(int& i : b) {
            if(c>s)
                break;
            while (i--)
                fun(a, c);
            a *= 2;
            c *= 2;
        }
    }
    cout << dp[s];
}

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