Submission #684864

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
6848642023-01-22 17:38:45Farhan_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() {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (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...