제출 #581958

#제출 시각아이디문제언어결과실행 시간메모리
581958BelguteiKnapsack (NOI18_knapsack)C++17
100 / 100
67 ms5040 KiB
/* ID: belgute2 LANG: C++ TASK: cownomics */ #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef complex <double> P; typedef pair<long long, long long> Point; #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair #define X real() #define Y imag() #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define MOD 1000000007 #define MOD1 1000000009 #define sqr(x) sqr((x)*(x)) void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #ifdef BE_DEBUG #define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__) #else #define debug(...) #endif const int N = 105; int s,n; ll val, wei, num; vector<pair<ll,ll>> p[2005]; vector<ll> v[2005]; ll dp[2005]; ll ans; int main() { IOS cin >> s >> n; // s <= 2000 for(int i = 1; i <= n; i ++) { cin >> val >> wei >> num; p[wei].pb({-val, num}); } // for(int i = 1; i <= s; i ++) { sort(p[i].begin(), p[i].end()); int tmp = s / i; int pos = 0; while(tmp > 0 && pos < p[i].size()) { if(p[i][pos].ss == 0) { pos ++; continue; } tmp --; v[i].pb(-p[i][pos].ff); p[i][pos].ss --; } } // for(int i = 1; i <= s; i ++) { // cout << i << ": "; // for(auto x: v[i]) { // cout << x << ' '; // } // cout << '\n'; // } for(int i = 1; i <= s; i ++) { // weight for(int j = s; j >= 0; j --) { ll tmp = 0; for(int k = 0; k < v[i].size(); k ++) { if(j - (k + 1) * i < 0) break; //cout << j << ' ' << k << ' ' << tmp << '\n'; tmp += v[i][k]; dp[j] = max(dp[j], dp[j - (k + 1) * i] + tmp); ans = max(ans, dp[j]); } } } cout << ans; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:57:30: 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]
   57 |         while(tmp > 0 && pos < p[i].size()) {
      |                          ~~~~^~~~~~~~~~~~~
knapsack.cpp:77:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int k = 0; k < v[i].size(); k ++) {
      |                            ~~^~~~~~~~~~~~~
#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...