Submission #895120

#	Time	Username	Problem	Language	Result	Execution time	Memory
895120		Kladness	Knapsack (NOI18_knapsack)	C++14	12 / 100	1 ms	348 KiB

knapsack

#include <bits/stdc++.h>

#include <cmath>
#include <chrono>
#include <numeric>

using namespace std;
#define fasterio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl "\n"
#define ll long long
#define testcase int t; cin>>t; for(int i=0;i<t;i++)
#define int long long
//#define double long double
#define pb push_back

#define dbugvec(v) for(int i=0;i<v.size();i++){ cout << v[i] << " ";}cout << endl;
#define dbugarr(arr) for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++){ cout << arr[i] << " ";}cout << endl;
#define dbug2dvec(v) for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++){cout << v[i][j] << " ";}cout << endl;}
ll mod= 1e9+7;
//ll N = 252000;
ll inf = 1e18;
double e=2.718281828459045235360;


//FUNCTIONS
ll inv(ll a, ll b = mod) { return 1 < a ? b - inv(b % a, a) * b / a : 1; }
// bool cmp(pair<int,int> a,pair<int,int> b){ return a.second>b.second;}

bool cmp(vector<int> alpha, vector<int> beta)
{
    return (alpha[0]*beta[1])>(beta[0]*alpha[1]);
        
}
int binpow(int a, int b, int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}


void dij(vector<int>&dist,vector<vector<pair<int,int>>> &adj,int node)
{
   vector<int> vis(dist.size(),0);
   priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
   pq.push({0,node});
   while(pq.size()!=0)
   {
      int wt=pq.top().first;
      int n=pq.top().second;
      pq.pop();
      if(vis[n]==1) continue;
      vis[n]=1;
      dist[n]=wt;
      for(int i=0;i<adj[n].size();i++)
      {
        if(dist[adj[n][i].first]>wt+adj[n][i].second)
            pq.push({wt+adj[n][i].second,adj[n][i].first});
      }
   }
}



int find_parent(int node,vector<int>&parent)
{
    if(parent[node]==node) return node;
    else
    {
        int alpha = find_parent(parent[node],parent);
        parent[node] = alpha;
        return alpha;
    }
}


int dsu(vector<int>&size, vector<int>&parent, int node1,int node2)
{
    if(find_parent(node1,parent)==find_parent(node2,parent)) return 0;
    int alpha = find_parent(node1,parent);
    int beta = find_parent(node2,parent);
    if(size[alpha]==size[beta])
    {
        size[beta]+=size[alpha];
        parent[alpha] = beta;
    }
    else
    {
        if(size[alpha]>size[beta])
        {
        size[alpha]+=size[beta];
        parent[beta] = alpha;
        }
        else
        {
        size[beta]+=size[alpha];
        parent[alpha] = beta;
        }
    }

    return 1;
}


int dfs(vector<vector<int>>&adj,vector<int>&cyc,int node,int parent,vector<int> &vis)
{
    vis[node]=1;
    int alpha =0;
    
    for(int i=0;i<adj[node].size();i++)
    {
        if(adj[node][i]==parent) continue;
        else
        {
            if(vis[adj[node][i]]==1){cyc[node]=1; alpha = 1; cout<<node<<endl;}
            else
            alpha += dfs(adj,cyc,adj[node][i],node,vis);
        }
    }
if(alpha>=1) {cyc[node]=1;return 1;}
else return 0;

}









signed main()
 {

    // fasterio
    // #ifndef ONLINE_JUDGE  
    // freopen("error.txt", "w", stderr);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif


    int s,n;
    cin>>s>>n;
    vector<vector<int>> v(n);
    for(int i=0;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        v[i].push_back(a);
        v[i].push_back(b);
        v[i].push_back(c);
    }


    sort(v.begin(), v.end(),cmp);

    // for(int i=0;i<n;i++) cout<<v[i][0]<<endl;

    int wt =0;
    int profit = 0;
    for(int i=0;i<n;i++)
    {
        int alpha = (s-wt)/v[i][1];
        int beta = v[i][2];
        wt+= min(alpha,beta)*v[i][1];
        profit+= min(alpha,beta)*v[i][0];

    }

    cout<<profit<<endl;


}




 
 

Compilation message (stderr)

knapsack.cpp: In function 'void dij(std::vector<long long int>&, std::vector<std::vector<std::pair<long long int, long long int> > >&, long long int)':
knapsack.cpp:60:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |       for(int i=0;i<adj[n].size();i++)
      |                   ~^~~~~~~~~~~~~~
knapsack.cpp: In function 'long long int dfs(std::vector<std::vector<long long int> >&, std::vector<long long int>&, long long int, long long int, std::vector<long long int>&)':
knapsack.cpp:115:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int i=0;i<adj[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~

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