제출 #703099

#제출 시각아이디문제언어결과실행 시간메모리
703099Quan2003Knapsack (NOI18_knapsack)C++17
0 / 100
7 ms10004 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<long long,long long> pii; const int N = 1e5 + 100; const int INF = 1e7 + 10; const int mod = 1e9 + 7; long long n,m,k,tot; int timer = 1; vector<long long>lf,ri; long long a[N + 1]; long long V[N + 1],W[N + 1],C[N + 1]; map<long long,long long>dp[N + 1]; int main(){ scanf("%d%d",&n,&k); map<long long,vector<pii>>books; long long high = 0; for(int i = 1; i <= n; i++) scanf("%d",&W[i]); for(int i = 1; i <= n; i++) scanf("%d",&V[i]); for(int i = 1; i <= n; i++) scanf("%d",&C[i]); for(int i = 1; i <= n; i++){ high = max(high ,W[i]); books[W[i]].push_back({V[i],C[i]}); } dp[0][0] = 0; int pos = 0; for(auto [cur,lst] : books){ sort(lst.rbegin(),lst.rend()); for(int i = 0; i <= k; i++){ dp[cur - 1][i] = dp[cur][i] = dp[pos][i]; int page = 0; int copy = 1; int ptr = 0; while(ptr < lst.size() and copy * cur <= i){ page += lst[ptr].first; if(dp[cur - 1].count(i - copy * cur)){ dp[cur][i] = max(dp[cur][i],dp[cur - 1][i - copy * cur] + page); // if(cur == 3) cout<<dp[cur][i]<<' '<<cur<<' '<<i<<endl; } copy++; if(copy == lst[ptr].second + 1){ copy = 1; ptr++; } } } pos = cur; } long long ans = dp[high][k]; printf("%d \n",ans); }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:15:15: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   15 |       scanf("%d%d",&n,&k);
      |              ~^    ~~
      |               |    |
      |               int* long long int*
      |              %lld
knapsack.cpp:15:17: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   15 |       scanf("%d%d",&n,&k);
      |                ~^     ~~
      |                 |     |
      |                 int*  long long int*
      |                %lld
knapsack.cpp:18:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   18 |       for(int i = 1; i <= n; i++) scanf("%d",&W[i]);
      |                                          ~^  ~~~~~
      |                                           |  |
      |                                           |  long long int*
      |                                           int*
      |                                          %lld
knapsack.cpp:19:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   19 |       for(int i = 1; i <= n; i++) scanf("%d",&V[i]);
      |                                          ~^  ~~~~~
      |                                           |  |
      |                                           |  long long int*
      |                                           int*
      |                                          %lld
knapsack.cpp:20:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   20 |       for(int i = 1; i <= n; i++) scanf("%d",&C[i]);
      |                                          ~^  ~~~~~
      |                                           |  |
      |                                           |  long long int*
      |                                           int*
      |                                          %lld
knapsack.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                while(ptr < lst.size() and copy * cur <= i){
      |                      ~~~~^~~~~~~~~~~~
knapsack.cpp:49:16: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   49 |       printf("%d \n",ans);
      |               ~^     ~~~
      |                |     |
      |                int   long long int
      |               %lld
knapsack.cpp:15:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |       scanf("%d%d",&n,&k);
      |       ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:18:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |       for(int i = 1; i <= n; i++) scanf("%d",&W[i]);
      |                                   ~~~~~^~~~~~~~~~~~
knapsack.cpp:19:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |       for(int i = 1; i <= n; i++) scanf("%d",&V[i]);
      |                                   ~~~~~^~~~~~~~~~~~
knapsack.cpp:20:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |       for(int i = 1; i <= n; i++) scanf("%d",&C[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...