Submission #839113

#	Time	Username	Problem	Language	Result	Execution time	Memory
839113		detroiddh	Knapsack (NOI18_knapsack)	C++17	100 / 100	114 ms	36272 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const ll maxn = 2003;
const ll mod = 1e9 + 7;

struct TPair
{
   ll v , k;
};

bool ss(TPair i , TPair j)
{
    return i.v > j.v;
}

ll dp[maxn][maxn] , inf = 1e18;
vector<TPair>a[maxn];

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   //freopen("","r",stdin);
   //freopen("","w",stdout);

   int s , n;
   cin>>s>>n;

   ll v , w , k;
   for(int i = 1 ; i <= n ; ++i)
   {
       cin>>v>>w>>k;
       a[w].push_back({v , k});
   }

   for(int i = 1 ; i <= s ; ++i)
       sort(a[i].begin() , a[i].end() , ss);

   ll kq = 0;
   for(int i = 1 ; i <= s ; ++i)
    dp[i][0] = -inf;

   for(int i = 0 ; i <= s ; ++i)
    dp[0][i] = 0;

   for(int j = 1 ; j <= s ; ++j)
   {
       for(int i = 1 ; i <= s ; ++i)
       {
           dp[i][j] = dp[i][j - 1];
           ll so1 = 0 , so2 = 0;

           for(TPair h : a[j])
           {
               int dem = 0;
               while(dem < h.k)
               {
                   ++dem;
                   so1 += j;
                   so2 += h.v;
                   if(so1 > i) goto done;
                   dp[i][j] = max(dp[i][j] , dp[i - so1][j - 1] + so2);
               }
           }

           done:;

           kq = max(kq , dp[i][j]);
       }
   }

   cout<<kq;
}

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