Submission #1103652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103652		khoile25108	Knapsack (NOI18_knapsack)	C++14	100 / 100	33 ms	5336 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define lcm(a,b) (a*b)/__gcd(a,b)
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int S = 2005;
const int N = 1e5 + 105;

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};
const int dxx[] = {-1,-1,0,1,1,1,0,-1};
const int dyy[] = {0,1,1,1,0,-1,-1,-1};

int n, s;
int dp[S][2];
vector<ii> a[S];

void solve()
{
    FOR(j,1,s)
    {
        sort(a[j].begin(), a[j].end(), greater<ii>());
        FOR(i,1,s)
            dp[i][0] = dp[i][1]; 
        int profit = 0;
        int weight = 0;
        for(int i = 0; i < a[j].size(); )
        {       
            if(a[j][i].se == 0)
            {
                i++;
                continue;
            }
            profit += a[j][i].fi;
            weight += j;
            a[j][i].se--;
            if(weight > s)
                break;
            for(int cur = weight; cur <= s; cur++)
                dp[cur][1] = max(dp[cur][1], dp[cur-weight][0] + profit);
        }
    }
    cout << dp[s][1];
}

void input()
{
    //freopen("TEST.INP", "r", stdin);
    //freopen("TEST.OUT", "w", stdout);
    cin >> s >> n;
    FOR(i,1,n)
    {
        int v, w, c;
        cin >> v >> w >> c;
        if(w <= 2000)
            a[w].pb({v,c});
    }
}

signed main()
{
    faster
    input();
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:41:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0; i < a[j].size(); )
      |                        ~~^~~~~~~~~~~~~

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