제출 #1043190

#제출 시각아이디문제언어결과실행 시간메모리
1043190vjudge1Knapsack (NOI18_knapsack)C++17
73 / 100
226 ms262144 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define bip(i) __builtin_popcount(i) #define gb(i,j) ((i>>j)&1) #define se second #define fi first using namespace std; const int N=2005; int n , S; ll f[2][N] , res; vector<pair<int,int>>vec[N] , prc; int main() { cin.tie(0) -> sync_with_stdio(false); cin >> S >> n; for( int i=1 ; i<=n ; i++ ){ int v , w , fre; cin >> v >> w >> fre; vec[w].push_back({v , fre}); } prc.push_back({0,0}); for( int i=1 ; i<=S ; i++ ) // weight if(vec[i].size()){ sort(vec[i].begin() , vec[i].end() , greater<pair<int,int>>() ); for( auto [val , fr]: vec[i] ){ int tmp=0 , ch=0; for( int k=1 ; k<=fr ; k++ ){ tmp+=i; if(tmp<=S) prc.push_back({val , i}); else{ ch=1; break; } } if(ch)break; } } for( int i=1 ; i<prc.size() ; i++ ){ int val = prc[i].fi , wei = prc[i].se; for( int j=S ; j>=0 ; j-- )f[i%2][j]=f[(i-1)%2][j]; // truong hop ko chon i for( int j=S ; j>=0 ; j-- )if(j>=wei){ f[i%2][j] = max( f[i%2][j] , f[(i-1)%2][j-wei]+val ); // truong hop chon i res = max( res , f[i%2][j] ); }else break; } cout << res; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for( int i=1 ; i<prc.size() ; i++ ){
      |                    ~^~~~~~~~~~~
#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...