Submission #1265959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265959		nhathanh	Knapsack (NOI18_knapsack)	C++20	12 / 100	30 ms	55368 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define el "\n"
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
const int N=1e6+10;
int s,n,a,b,c,cnt=1,trueans;
vector<pii>w[N];
int ans[2005][2005];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    file("a");

    cin>>s>>n;

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

    memset(ans,-1,sizeof(ans));
    ans[0][0]=0;
    for(int i=1;i<=s;i++)
        sort(w[b].begin(),w[b].end(),greater<pii>());

    for(int i=1;i<=s;i++)
    {
        if(w[i].empty()) continue;
        for(int lim=0;lim<=s;lim++)
        {
            ans[cnt][lim]=ans[cnt-1][lim];
            int cur_w=0, cur_val=0;
            for(int k=0;k<w[i].size();k++)
            {
                if(cur_w>lim) break;
                for(int f=1;f<=w[i][k].se;f++)
                {
                    cur_val+=w[i][k].fi;
                    cur_w+=i;
                    if(cur_w>lim) break;
                    if(ans[cnt-1][lim-cur_w]!=-1)
                    {
                      ans[cnt][lim]=max(ans[cnt][lim],ans[cnt-1][lim-cur_w]+cur_val);
                      trueans=max(ans[cnt][lim],trueans);
                    }
                }
            }
        }
        cnt++;
    }

    cout<<trueans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:8:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:17:5: note: in expansion of macro 'file'
   17 |     file("a");
      |     ^~~~
knapsack.cpp:8:83: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
      |                                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:17:5: note: in expansion of macro 'file'
   17 |     file("a");
      |     ^~~~

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