Submission #529810

#	Time	Username	Problem	Language	Result	Execution time	Memory
529810		Doublade	Knapsack (NOI18_knapsack)	C++17	100 / 100	96 ms	36348 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;
}

void runcase() {
    ll s, n;
    cin >> s >> n;
    map<ll, vector<pl>> a;
    rep(i, n) {
        ll v, w, k;
        cin >> v >> w >> k;
        a[w].PB({v, k});
    }
    ll nItems = sz(a);
    matrix dp(nItems+1, vl(s+1, 0));
    ll idx = 1;
    for(auto x:a) {
        ll wt = x.F;
        vector<pl> items = x.S;
        sort(all(items), [&](const pl &a, const pl &b) {
            if(a.F==b.F) return (a.S > b.S);
            return (a.F > b.F);
        });
        f(j, 1, s+1) {
            dp[idx][j] = dp[idx-1][j];
            ll prev = 0, copies = 0, arrIdx = 0, currCopies = 0;
            while(arrIdx<sz(items) && j>=((copies+currCopies)*wt)) {
                ll currVal = items[arrIdx].F;
                amax(dp[idx][j], prev+(currCopies*currVal)+dp[idx-1][j-(copies+currCopies)*wt]);
                currCopies++;
                if(currCopies>items[arrIdx].S) {
                    prev += (items[arrIdx].F*items[arrIdx].S);
                    copies += items[arrIdx].S;
                    arrIdx++;
                    currCopies = 0;
                }
            }
        }
        idx++;
    }
    cout<<dp[nItems][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:130:5: note: in expansion of macro 'time__'
  130 |     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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27