제출 #1304657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304657		alex0152	Knapsack (NOI18_knapsack)	C++20	100 / 100	42 ms	1724 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int nMax=2e3+5,MOD=998244353;

ll t,n,m,k,x,y,z,a,b,c,d,cnt,ans,rez,sum,poz,p1,p2;
ll mat[21][21],dp[nMax];
bool ok;
char ch;
string s;
unordered_map<ll,int>mp[21][21];
vector<array<int,2>>adj[nMax];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>k>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a>>b>>c;
        adj[b].push_back({a,c});
    }
    for(int i=1; i<=k; ++i)
    {
        sort(adj[i].rbegin(),adj[i].rend());
        x=0,y=0;
        for(auto it : adj[i])
        {
            x=it[0];
            if(y>k)
                break;
            for(int j=1; y+i<=k && j<=it[1]; ++j)
            {
                y+=i;
                for(int p=k; p>=i; --p)
                {
                    dp[p]=max(dp[p],dp[p-i]+x);
                    ans=max(dp[p],ans);
                }
            }
        }
    }
    cout<<ans<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:21:27: warning: narrowing conversion of 'a' from 'long long int' to 'int' [-Wnarrowing]
   21 |         adj[b].push_back({a,c});
      |                           ^
knapsack.cpp:21:29: warning: narrowing conversion of 'c' from 'long long int' to 'int' [-Wnarrowing]
   21 |         adj[b].push_back({a,c});
      |                             ^

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