Submission #1135725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135725		floppy	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	1608 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
 
#define f(i,s,e) for(long long int i=s;i<e;i++)
#define cf(i,s,e) for(long long int i=s;i<=e;i++)
#define rf(i,e,s) for(long long int i=e-1;i>=s;i--)
#define pb push_back
#define eb emplace_back
#define ff first 
#define ss second
#define mp make_pair
 
template <class T>
void print_v(vector<T> &v) { cout << "{"; for (auto x : v) cout << x << ","; cout << "\b}"; }

template <class T> 
istream& operator>>(istream& in, vector<T>& v)
{
    for(auto&i:v)
        cin>>i; 
    return in; 
}
 
#define MOD 1000000007
#define EPS 1e-6f 
#define PI 3.1415926535897932384626433832795
ll min(ll a,int b) { if (a<b) return a; return b; }
ll min(int a,ll b) { if (a<b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool prime(ll a) { if (a==1) return 0; for (int i=2;i<=round(sqrt(a));++i) if (a%i==0) return 0; return 1; }
void yes() { cout<<"YES\n"; }
void no() { cout<<"NO\n"; }
 
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;

const int MAX_S = 2e3; 
int dp[MAX_S+2];
bool dp2[MAX_S+2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("sumdiv.in","r",stdin); 
    //freopen("sumdiv.out","w",stdout);
    
    int s, n;   
    cin >> s >> n; 

    vi w(n); 
    vi v(n); 
    vi k(n); 

    f(i,0,n)
    {
        cin >> v[i] >> w[i] >> k[i]; 
    }

    dp2[0] = true; 
    f(i,0,n)
    {
        f(j,0,min(k[i], s / w[i]))   
        {
            rf(x,s+1,0) 
            {
                if (x - w[i] < 0)
                    continue; 

                if (dp2[x - w[i]])
                {
                    dp2[x] = true; 
                    dp[x] = max(dp[x], v[i] + dp[x-w[i]]); 
                }
            }
        }
    }
    int ans = 0; 
    cf(i,0,s)
        ans = max(ans, dp[i]); 
    cout << ans << endl; 


    return 0; 
}

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