test/aoj/DPL_1_H.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:17:48+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H

Depends on

• 0-1 ナップサック問題 (半分全列挙) (src/Optimization/Knapsack.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Optimization/Knapsack.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 Knapsack<int64_t, int64_t> K;
 int N;
 int64_t W;
 cin >> N >> W;
 for (int i= 0; i < N; ++i) {
  int64_t v, w;
  cin >> v >> w;
  K.add(v, w);
 }
 K.build();
 cout << K.solve(W) << '\n';
 return 0;
}

#line 1 "test/aoj/DPL_1_H.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Optimization/Knapsack.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 Knapsack<int64_t, int64_t> K;
 int N;
 int64_t W;
 cin >> N >> W;
 for (int i= 0; i < N; ++i) {
  int64_t v, w;
  cin >> v >> w;
  K.add(v, w);
 }
 K.build();
 cout << K.solve(W) << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	5 ms	4 MB
g++-13	00_sample_01.in	AC	4 ms	4 MB
g++-13	01_small_00.in	AC	4 ms	4 MB
g++-13	01_small_01.in	AC	4 ms	4 MB
g++-13	01_small_02.in	AC	4 ms	4 MB
g++-13	01_small_03.in	AC	4 ms	4 MB
g++-13	02_corner_00.in	AC	4 ms	4 MB
g++-13	02_corner_01.in	AC	4 ms	4 MB
g++-13	04_rand_00.in	AC	4 ms	4 MB
g++-13	04_rand_01.in	AC	4 ms	4 MB
g++-13	04_rand_02.in	AC	4 ms	4 MB
g++-13	04_rand_03.in	AC	4 ms	4 MB
g++-13	04_rand_04.in	AC	4 ms	4 MB
g++-13	04_rand_05.in	AC	4 ms	4 MB
g++-13	05_large_00.in	AC	4 ms	4 MB
g++-13	05_large_01.in	AC	4 ms	4 MB
g++-13	05_large_02.in	AC	4 ms	4 MB
g++-13	05_large_03.in	AC	4 ms	4 MB
g++-13	05_large_04.in	AC	5 ms	4 MB
g++-13	05_large_05.in	AC	5 ms	4 MB
g++-13	06_maximum_00.in	AC	7 ms	6 MB
g++-13	06_maximum_01.in	AC	33 ms	52 MB
g++-13	06_maximum_02.in	AC	34 ms	52 MB
g++-13	06_maximum_03.in	AC	34 ms	52 MB
g++-13	06_maximum_04.in	AC	34 ms	52 MB
g++-13	06_maximum_05.in	AC	35 ms	52 MB
g++-13	07_extreme_00.in	AC	6 ms	4 MB
g++-13	07_extreme_01.in	AC	5 ms	5 MB
g++-13	07_extreme_02.in	AC	22 ms	52 MB
g++-13	07_extreme_03.in	AC	21 ms	52 MB
g++-13	07_extreme_04.in	AC	22 ms	52 MB
g++-13	07_extreme_05.in	AC	26 ms	52 MB
clang++-18	00_sample_00.in	AC	5 ms	4 MB
clang++-18	00_sample_01.in	AC	4 ms	4 MB
clang++-18	01_small_00.in	AC	4 ms	4 MB
clang++-18	01_small_01.in	AC	4 ms	4 MB
clang++-18	01_small_02.in	AC	4 ms	4 MB
clang++-18	01_small_03.in	AC	4 ms	4 MB
clang++-18	02_corner_00.in	AC	4 ms	4 MB
clang++-18	02_corner_01.in	AC	4 ms	4 MB
clang++-18	04_rand_00.in	AC	4 ms	4 MB
clang++-18	04_rand_01.in	AC	4 ms	4 MB
clang++-18	04_rand_02.in	AC	4 ms	4 MB
clang++-18	04_rand_03.in	AC	4 ms	4 MB
clang++-18	04_rand_04.in	AC	4 ms	4 MB
clang++-18	04_rand_05.in	AC	4 ms	4 MB
clang++-18	05_large_00.in	AC	4 ms	4 MB
clang++-18	05_large_01.in	AC	4 ms	4 MB
clang++-18	05_large_02.in	AC	4 ms	4 MB
clang++-18	05_large_03.in	AC	5 ms	4 MB
clang++-18	05_large_04.in	AC	5 ms	4 MB
clang++-18	05_large_05.in	AC	5 ms	4 MB
clang++-18	06_maximum_00.in	AC	7 ms	6 MB
clang++-18	06_maximum_01.in	AC	31 ms	52 MB
clang++-18	06_maximum_02.in	AC	33 ms	52 MB
clang++-18	06_maximum_03.in	AC	34 ms	52 MB
clang++-18	06_maximum_04.in	AC	33 ms	52 MB
clang++-18	06_maximum_05.in	AC	33 ms	52 MB
clang++-18	07_extreme_00.in	AC	6 ms	4 MB
clang++-18	07_extreme_01.in	AC	5 ms	5 MB
clang++-18	07_extreme_02.in	AC	23 ms	52 MB
clang++-18	07_extreme_03.in	AC	20 ms	52 MB
clang++-18	07_extreme_04.in	AC	22 ms	52 MB
clang++-18	07_extreme_05.in	AC	25 ms	52 MB

Back to top page