Submission #529794

#	Time	Username	Problem	Language	Result	Execution time	Memory
529794		Doublade	Knapsack (NOI18_knapsack)	C++17	0 / 100	2 ms	588 KiB

knapsack

/* 𝔸ЦէђӨr: 𝔻𝔬ᵘ๒𝓵𝓪🅳𝕖 */

#include<bits/stdc++.h>
using namespace std;
using namespace chrono;

#pragma GCC optimize("-O2")

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<ll> vl;
typedef pair<ll, ll> pl;
typedef vector<vector<ll>> matrix;

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )
#define F                         first
#define S                         second
#define PB                        push_back
#define PPB                       pop_back
#define MP                        make_pair
#define all(c)                    c.begin(), c.end()
#define f(i,a,b)                  for(ll i=a; i<b; i++)
#define rep(i,n)                  f(i,0,n)
#define fd(i, b, a)               for(ll i=b; i>=a; i--)
#define repr(i,n)                 fd(i, n-1, 0)
#define tr(c,i)                   for(typeof(c).begin() i = c.begin(); i != c.end(); i++)
#define present(c,x)              (c.find(x) != c.end())    //for set and map
#define cpresent(c,x)             (find(all(c),x) != c.end())    //for vectors
#define ps(num, places)           fixed<<setprecision(places)<<num //use as cout<<ps(x, y)<<"\n";
#define sz(x)                     (ll)(x).size()

void setIO() { 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout); 
}

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

void amax(ll &a, ll b) { a = max(a, b); }
void amin(ll &a, ll b) { a = min(a, b); }

const lld epsilon = 1e-9;
const ll MOD = 1e9+7;
const ll INF = 1e9;

bool comp(ll a, ll b) {
    return (a > b);
}

ll POW(ll a, ll b) {
    ll res = 1;
    while(b>0) {
        if(b&1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

ll binpow(ll a, ll b, ll p=MOD) {
    ll res = 1;
    a %= p;
    while(b>0) {
        if(b&1) (res *= a)%=p;
        (a *= a)%=p;
        b >>= 1;
        a %= p;
        res %= p;
    }
    return res;
}

struct info {
    ll v, w, k;
};

void runcase() {
    ll s, n;
    cin >> s >> n;
    vector<info> a(n);
    rep(i, n) {
        ll v, w, k;
        cin >> v >> w >> k;
        a[i] = {v, w, k};
    }
    // dp[i][j] = max value till ith item and max j weight
    // ans = dp[n][s]
    // dp[i][0] = 0 for all i
    // dp[0][j] = 0 for all j
    // dp[i][j] = max(dp[i-1][j], a[i]+dp[i-1][j-a[i]], ..., k*a[i]+dp[i-1][j-k*a[i]])
    // if(a[i]>j) dp[i][j] = dp[i-1][j]
    // else dp[i][j] = max(dp[i-1][j], a[i]+dp[i-1][j-a[i]])
    matrix dp(n+1, vl(s+1, 0));
    f(i, 1, n+1) {
        ll v = a[i-1].v, w = a[i-1].w, k = a[i-1].k;
        f(j, 1, s+1) {
            ll p = min(k, j/w);
            rep(q, p+1) amax(dp[i][j], q*v+dp[i-1][j-q*w]);
        }
    }
    cout<<dp[n][s]<<"\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.precision(10);
    #ifndef ONLINE_JUDGE
        setIO();
        // usaco("");
    #endif
    time__("Main") {
        ll tests = 1;
        // cin >> tests;
        while(tests--) {
            runcase();
        }
    }
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:15: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'std::chrono::duration<long int, std::ratio<1, 1000> >::rep' {aka 'long int'} [-Wformat=]
   23 |         debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
      |               ^~~~~~~~~~~~~~~     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                                                                                                                                            |
      |                                                                                                                                            std::chrono::duration<long int, std::ratio<1, 1000> >::rep {aka long int}
knapsack.cpp:18:36: note: in definition of macro 'debug'
   18 | #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
      |                                    ^~~~~~~~~~~
knapsack.cpp:122:5: note: in expansion of macro 'time__'
  122 |     time__("Main") {
      |     ^~~~~~
knapsack.cpp:23:23: note: format string is defined here
   23 |         debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
      |                    ~~~^
      |                       |
      |                       long long int
      |                    %ld
knapsack.cpp: In function 'void setIO()':
knapsack.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void usaco(std::string)':
knapsack.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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