oj.uz

Submission #976128

# Submission time Handle Problem Language Result Execution time Memory
976128 2024-05-06T08:06:30 Z vjudge1 Knapsack (NOI18_knapsack) C++17
0 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"

const int N = 2e3 + 5;

vector < pair < int, int > > a(1, {0, 0}), yes[N];

int n , s;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> s >> n;

    for ( int i = 1; i <= n; i++){
        int harga, berat, stok; cin >> harga >> berat >> stok;
        yes[berat].push_back({harga, stok});
    }

    for ( int i = 1; i <= 2000; i++) sort ( yes[i].begin(), yes[i].end(), greater<pair < int, int >>());

    for ( int i = 1; i <= 2000; i++){
        int can = 2000;

        for ( int j = 0; j < yes[i].size(); j++){
            for ( int k = 1; k <= yes[i][j].second; k++){
                if ( can <= 0 ) break;
                a.push_back({i, yes[i][j].first});

                can -= i;
                // berat, harga
            }
        }
    }

    // 2e3 . log ( 2e3 )

    vector < vector < int > > dp ( a.size() + 5, vector < int > ( s + 5, 0 ));

    for ( int i = 1; i < a.size(); i++){
        for ( int j = 0; j <= s; j++){
            dp[i][j] = dp[i-1][j];
            if ( i >= a[j].first ){
                dp[i][j] = max ( dp[i][j], dp[i - 1][j - a[i].first] + a[i].second);
            }
        }
    }

    cout << dp[a.size() - 1][s];
}

Compilation message

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for ( int j = 0; j < yes[i].size(); j++){
      |                          ~~^~~~~~~~~~~~~~~
knapsack.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for ( int i = 1; i < a.size(); i++){
      |                      ~~^~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -