Submission #501817

#	Time	Username	Problem	Language	Result	Execution time	Memory
501817		ditsipandey	Knapsack (NOI18_knapsack)	C++14	37 / 100	211 ms	262148 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack
#include<bits/stdc++.h>
using namespace std;



#define ite(i,n) for(int i=0;i<n;i++)
#define itel(i,n) for(ll i=0;i<n;i++)
#define fora(i,a,b) for(int i=a;i<b;i++)
#define fors(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll;
typedef std::set<ll>::iterator set_p ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define reached cout<<"reached"<<endl
ll MOD=1e9+7;

/*--------------------------------------Printing functions start----------------------------------------------*/
template<typename T>
void print_vec(vector<T>&vec){
    for(auto i=vec.begin();i!=vec.end();i++){
        cout<<*i<<" ";
    }
    cout<<"\n";
}

template<typename T>
void print_2Dvec(vector<vector<T>>&vec){
    for(int i=0;i<vec.size();i++){
        for(int j=0;j<vec[i].size()>0;j++){
            cout<<vec[i][j]<<"\t";
        }
        if(vec[i].size()>0)
            cout<<"\n";
    }
}
template<typename T, typename S>
void print_pair(pair<T,S> a){
    cout<<a.first<<" "<<a.second<<"\n";
}

/*---------------------------------------Printing functions end-----------------------------------------------*/
/*---------------------------------------Graph functions------------------------------------------------------*/
// vector<int>dist(1e5+1,INT_MAX);
// vector<int>par(1e5+1, INT_MAX);
// vector<bool>visited(100001,0);
// vector<vector<int>>graph(2*(1e5)+1);

// template<typename T>
// void g_input(T n,T m){
//     for(T i=0;i<m;i++){
//         int a,b;
//         cin>>a>>b;
//         graph[a].push_back(b);
//         graph[b].push_back(a);
//     }
// }

// void bfs(int s){
//     dist[s]=1;
//     queue<int>q;
//     q.push(s);
//     while(!q.empty()){
//         int t=q.front();
//         q.pop();
//         for(int i=0;i<graph[t].size();i++){
//             if(dist[graph[t][i]]==INT_MAX){
//                 dist[graph[t][i]]=dist[t]+1;
//                 par[graph[t][i]]=t;
//                 q.push(graph[t][i]);
//             }
//         }
//     }

// }

// void dfs(int n){
//     visited[n]=1;
//     // cout<<n<<"\n";
//     for(int i=0;i<graph[n].size();i++){
//         if(!visited[graph[n][i]]){
//             dfs(graph[n][i]);
//         }
//     }
// }

/*---------------------------------------Graph functions------------------------------------------------------*/

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int s,n;
    cin>>s>>n;
    vi v(n,0);
    vi w(n,0);
    vi k(n,0);
    ite(i,n){
        cin>>v[i]>>w[i]>>k[i];
    }
    vector<pii>list;
    list.push_back({0,0});
    ite(i,n){
        for(;k[i]>0;k[i]--){
            list.push_back({w[i],v[i]});
        }
    }
    sort(list.begin(), list.end());
    n=list.size()-1;
    vector<vi>dp(n+1,vi(s+1,0));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<s+1;j++){
            if(j>=list[i].first)dp[i][j]=max(dp[i-1][j-list[i].first]+list[i].second, dp[i-1][j]);
        }
    }
    // print_2Dvec(dp);
    cout<<dp[n][s]<<endl;
    return 0;
}

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