제출 #999528

#제출 시각아이디문제언어결과실행 시간메모리
999528ef10Knapsack (NOI18_knapsack)C++17
100 / 100
105 ms36176 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; #define LL long long int main() { LL S, N; cin >> S >> N; tuple<LL, LL, LL> A[N+1]; memset(A,0,sizeof(A)); for (LL i = 1; i <= N; i++) { LL v,w,k; cin >> v >> w >> k; A[i] = make_tuple(w,v,k); } sort(A+1,A+N+1,greater<tuple<LL,LL,LL> >()); LL D[S+1][S+1]; memset(D,0,sizeof(D)); LL ind = 1; while (ind <= N) { LL s = get<0>(A[ind]); LL id = 1; while (ind <= N && get<0>(A[ind]) == s) { for (LL j = 0; j < get<2>(A[ind]) && id <= S; j++) { D[s][id++] = get<1>(A[ind]); } ind++; if (id > S) break; } while (ind <= N && get<0>(A[ind]) == s) ind++; } LL dp[2][S+1]; for (LL i = 0; i < 2; i++) { dp[i][0] = 0; for (LL j = 1; j <= S; j++) { dp[i][j] = -1; } } for (LL i = 1; i <= S; i++) { LL ind = i%2; LL oi = (i+1)%2; for (LL j = S; j >= 0; j--) { dp[ind][j] = dp[oi][j]; if (dp[ind][j] < 0) continue; for (LL w = i,id=1,v=D[i][id],V=v; w+j <= S && v > 0 && id <= S; w+=i,id++,v=D[i][id],V+=v) { dp[ind][w+j] = max(dp[ind][w+j], dp[ind][j]+V); } } } LL res = 0; for (LL i = 1; i <= S; i++) { res = max(res, dp[S%2][i]); } cout << res << endl; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:10:48: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::tuple<long long int, long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   10 |  tuple<LL, LL, LL> A[N+1]; memset(A,0,sizeof(A));
      |                                                ^
In file included from /usr/include/c++/10/functional:54,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from knapsack.cpp:3:
/usr/include/c++/10/tuple:516:11: note: 'class std::tuple<long long int, long long int, long long int>' declared here
  516 |     class tuple : public _Tuple_impl<0, _Elements...>
      |           ^~~~~
#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...