제출 #684864

#제출 시각아이디문제언어결과실행 시간메모리
684864Farhan_HYKnapsack (NOI18_knapsack)C++14
73 / 100
1047 ms68428 KiB
#include <bits/stdc++.h> #define int long long #define F first #define S second #define T int t; cin >> t; while(t--) #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int N = 2005; const int M = 1e3 + 3; const int mod = 1e9 + 7; int n, s, dp[N][N]; vector<pair<int, int>> vec[N]; vector<int> weights[N]; int Rec(int i, int j) { if (i > s) return 0; int &ret = dp[i][j]; if (ret != -1) return ret; ret = Rec(i + 1, j); int value = 0; for(int k = 0; k < weights[i].size(); k++) { value += weights[i][k]; if (j + (k + 1) * i <= s) ret = max(ret, Rec(i + 1, j + (k + 1) * i) + value); } return ret; } main() { IOS cin >> s >> n; for(int i = 1; i <= n; i++) { int v, w, k; cin >> v >> w >> k; vec[w].push_back({v, k}); } for(int i = 1; i <= s; i++) { sort(begin(vec[i]), end(vec[i]), greater<pair<int, int>>()); for(auto x: vec[i]) { if (weights[i].size() == s) break; for(int j = 1; j <= x.S; j++) { if (weights[i].size() == s) break; weights[i].push_back(x.F); } } } memset(dp, -1, sizeof dp); cout << Rec(1, 0); }

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

knapsack.cpp: In function 'long long int Rec(long long int, long long int)':
knapsack.cpp:22:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int k = 0; k < weights[i].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
knapsack.cpp: At global scope:
knapsack.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main() {
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:41:35: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   41 |             if (weights[i].size() == s) break;
      |                 ~~~~~~~~~~~~~~~~~~^~~~
knapsack.cpp:43:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |                 if (weights[i].size() == s) 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...