제출 #1121455

#제출 시각아이디문제언어결과실행 시간메모리
1121455vjudge1Knapsack (NOI18_knapsack)C++17
100 / 100
380 ms3928 KiB
///////////////////////////////////////////////////////////////// //////// Born_To_Laugh - Hughie Do //////// ///////////////////////////////////////////////////////////////// // #pragma GCC optimize("unroll-loops") // #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll MAXN=3e5+5; const int INF=1e9+7; /* Idea: */ void solve(){ map<int,vector<pair<int,int>>> wei; int s, t; cin >> s >> t; while(t--){ int v, w, k; cin >> v >> w >> k; if(w <= s){ wei[w].push_back(make_pair(v,k)); } } vector<int> dp(s+1, 0); for(int i=0; i<=s; ++i){ if(wei[i].size() == 0)continue; sort(wei[i].begin(), wei[i].end(), greater<pair<int,int>>()); int index = 0; //xet j so dau tien co can nang i for(int j=0; j*i<=s; ++j){ if(index >= wei[i].size())break; for(int k = s; k>=i; --k){ dp[k]=max(dp[k], dp[k-i]+wei[i][index].first); } wei[i][index].second--; if(wei[i][index].second == 0)index++; } } cout << dp[s]; } int main(){ cin.tie(nullptr)->sync_with_stdio(false); solve(); return 0; } /* Use for suggestion: { while } { nullptr sync_with_stdio false return to_string length } { push_back pop_back sort reverse begin end distance assign } { insert erase lower_bound upper_bound binary_search } { first second swap } { double float unsigned } { unordered_map pair vector deque string auto cout } */

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

knapsack.cpp: In function 'void solve()':
knapsack.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             if(index >= wei[i].size())break;
      |                ~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...