Submission #1273612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273612		44100	Knapsack (NOI18_knapsack)	C++20	Compilation error	0 ms	0 KiB

knapsack

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pub push_back
#define pob pop_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll Max=1e5+5,D=2e3+5;
ll W,n;
ll dp[Max],app[Max],c[Max],w[Max];
void sub1()
{
    ll i,j,k,cnt,ans;
    cnt=min(W/w[1],app[1]);
    ans=c[1]*cnt;
    cout<<ans;
    return;
}
void sub234()
{
    ll i,j,k,cnt,ans;
    for(i=1;i<=n;++i)
    {
        cnt=min(W/w[i],app[i]);
        for(k=1;k<=cnt;++k)
        {
            for(j=W;j>=w[i];--j)
                dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        }
    }
    /*for(i=1;i<=n;++i)
        cout<<dp[i]<<" ";
    cout<<"\n";*/
    cout<<dp[W];
    return;
}
void sub5()
{
    ///Nhận thấy với mỗi w[i] thì chỉ lấy tối đa được W/w[i] đồ như vậy, áp dụng ý tưởng này + tham lam: sort sao cho cùng w[i] thì c[i] max, sau đó làm tương tự sub 2,3,4, chú ý biến đổi app[i] theo từng lượt for
    ll i,j,k,cnt,ans,id;
    vector<pll> do[D];
    for(i=1;i<=n;++i)
    {
        if(w[i]>=D) continue;
        do[w[i]].pub({c[i],app[i]});
    }
    for(i=1;i<=W;++i)
    {
        if(do[i].empty()) continue;
        sort(do[i].begin(),do[i].end(),greater<ll>());
        id=0;
        for(k=1;k<=W/i;++k)
        {
            if(id>do[i].size()) break;
            for(j=W;j>=i;--j)
                dp[j]=max(dp[j],dp[j-i]+do[i][id].fi);
            --do[i][id].se;
            if(!do[i][id].se) ++id;
        }
    }
    cout<<dp[W];
    return;
}
int main()
{
    fast
    memset(dp,0,sizeof(dp));
    ll i,j,k,cnt,ans;
    cin>>W>>n;
    for(i=1;i<=n;++i)
        cin>>c[i]>>w[i]>>app[i];
    if(n==1)
    {
        sub1();
        return 0;
    }
    if(n<=100)
    {
        sub234();
        return 0;
    }
    sub5();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void sub5()':
knapsack.cpp:43:17: error: expected unqualified-id before 'do'
   43 |     vector<pll> do[D];
      |                 ^~
knapsack.cpp:47:12: warning: capture of variable 'w' with non-automatic storage duration
   47 |         do[w[i]].pub({c[i],app[i]});
      |            ^
knapsack.cpp:12:28: note: 'll w [100005]' declared here
   12 | ll dp[Max],app[Max],c[Max],w[Max];
      |                            ^
knapsack.cpp:47:13: error: expected ',' before '[' token
   47 |         do[w[i]].pub({c[i],app[i]});
      |             ^
      |             ,
knapsack.cpp:47:13: error: expected identifier before '[' token
knapsack.cpp: In lambda function:
knapsack.cpp:47:17: error: expected '{' before '.' token
   47 |         do[w[i]].pub({c[i],app[i]});
      |                 ^
knapsack.cpp: In function 'void sub5()':
knapsack.cpp:3:13: error: 'struct sub5()::<lambda()>' has no member named 'push_back'
    3 | #define pub push_back
      |             ^~~~~~~~~
knapsack.cpp:47:18: note: in expansion of macro 'pub'
   47 |         do[w[i]].pub({c[i],app[i]});
      |                  ^~~
knapsack.cpp:48:5: error: expected 'while' before '}' token
   48 |     }
      |     ^
knapsack.cpp:48:5: error: expected '(' before '}' token
   48 |     }
      |     ^
      |     (
knapsack.cpp:48:5: error: expected primary-expression before '}' token
knapsack.cpp:47:37: error: expected ')' before '}' token
   47 |         do[w[i]].pub({c[i],app[i]});
      |                                     ^
      |                                     )
   48 |     }
      |     ~                                
knapsack.cpp:47:37: error: expected ';' before '}' token
   47 |         do[w[i]].pub({c[i],app[i]});
      |                                     ^
      |                                     ;
   48 |     }
      |     ~                                
knapsack.cpp:51:12: error: expected primary-expression before 'do'
   51 |         if(do[i].empty()) continue;
      |            ^~
knapsack.cpp:51:12: error: expected ')' before 'do'
   51 |         if(do[i].empty()) continue;
      |           ~^~
      |            )
knapsack.cpp:52:14: error: expected primary-expression before 'do'
   52 |         sort(do[i].begin(),do[i].end(),greater<ll>());
      |              ^~
knapsack.cpp:52:28: error: expected primary-expression before 'do'
   52 |         sort(do[i].begin(),do[i].end(),greater<ll>());
      |                            ^~
knapsack.cpp:56:19: error: expected primary-expression before 'do'
   56 |             if(id>do[i].size()) break;
      |                   ^~
knapsack.cpp:56:19: error: expected ')' before 'do'
   56 |             if(id>do[i].size()) break;
      |               ~   ^~
      |                   )
knapsack.cpp:58:41: error: expected primary-expression before 'do'
   58 |                 dp[j]=max(dp[j],dp[j-i]+do[i][id].fi);
      |                                         ^~
knapsack.cpp:59:15: error: expected primary-expression before 'do'
   59 |             --do[i][id].se;
      |               ^~
knapsack.cpp:60:17: error: expected primary-expression before 'do'
   60 |             if(!do[i][id].se) ++id;
      |                 ^~
knapsack.cpp:60:17: error: expected ')' before 'do'
   60 |             if(!do[i][id].se) ++id;
      |               ~ ^~
      |                 )