제출 #557341

#제출 시각아이디문제언어결과실행 시간메모리
557341ShivanshJKnapsack (NOI18_knapsack)C++17
73 / 100
1080 ms54976 KiB
/*Segment tree really makes clean code look ugly :P*/ #include <bits/stdc++.h> //#define int long long using namespace std; const int MAXN=2e5+5; const int INF=1e18; const int MOD=1e9+7; const int MAXL=13; const int MAXW=2e3+5; int dp[2][MAXW]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //cout<<setprecision(6)<<fixed; //freopen("feast.in","r",stdin); //freopen("feast.out","w",stdout); int s,n; cin>>s>>n; vector<vector<int>>sack; for(int i=0;i<n;i++) { int v,w,k; cin>>v>>w>>k; k=min(k,s/w); int j=MAXL-1; for(j=MAXL-1;((1LL<<j)&k)==0;j--); int x=k-(1LL<<j)+1; sack.push_back({v*x,w*x}); j--; while(j>=0) { sack.push_back({v*(1LL<<j),w*(1LL<<j)}); j--; } } int curr=1; for(int i=0;i<sack.size();i++) { int nxt=(curr^1); for(int j=0;j<=s;j++) { dp[curr][j]=0; if(sack[i][1]<=j) { dp[curr][j]=max(dp[curr][j],dp[nxt][j-sack[i][1]]+sack[i][0]); } dp[curr][j]=max(dp[curr][j],dp[nxt][j]); } curr=nxt; } curr^=1; int ans=0; for(int j=0;j<=s;j++) { ans=max(ans,dp[curr][j]); } cout<<ans; return 0; }

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

knapsack.cpp:6:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int INF=1e18;
      |               ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:31:30: warning: narrowing conversion of '(((long long int)v) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
   31 |             sack.push_back({v*(1LL<<j),w*(1LL<<j)});
      |                             ~^~~~~~~~~
knapsack.cpp:31:30: warning: narrowing conversion of '(((long long int)v) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
knapsack.cpp:31:41: warning: narrowing conversion of '(((long long int)w) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
   31 |             sack.push_back({v*(1LL<<j),w*(1LL<<j)});
      |                                        ~^~~~~~~~~
knapsack.cpp:31:41: warning: narrowing conversion of '(((long long int)w) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
knapsack.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<sack.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...