test/aoj/DPL_3_B.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/3/DPL_3_B

Depends on

• Cartesian-Tree (src/Misc/CartesianTree.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Misc/CartesianTree.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int H, W;
 cin >> H >> W;
 vector<int> h(W, 0);
 int ans= 0;
 for (int i= 0; i < H; ++i) {
  for (int j= 0; j < W; ++j) {
   bool c;
   cin >> c;
   h[j]= c ? 0 : h[j] + 1;
  }
  CartesianTree ct(h);
  for (int j= 0; j < W; ++j) {
   auto [l, r]= ct.range(j);
   ans= max(ans, h[j] * (r - l));
  }
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/DPL_3_B.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <src/Misc/CartesianTree.hpp>
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int H, W;
 cin >> H >> W;
 vector<int> h(W, 0);
 int ans= 0;
 for (int i= 0; i < H; ++i) {
  for (int j= 0; j < W; ++j) {
   bool c;
   cin >> c;
   h[j]= c ? 0 : h[j] + 1;
  }
  CartesianTree ct(h);
  for (int j= 0; j < W; ++j) {
   auto [l, r]= ct.range(j);
   ans= max(ans, h[j] * (r - l));
  }
 }
 cout << ans << '\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_case_00.in	AC	4 ms	4 MB
g++-13	01_case_01.in	AC	4 ms	4 MB
g++-13	01_case_02.in	AC	4 ms	4 MB
g++-13	01_case_03.in	AC	4 ms	3 MB
g++-13	01_case_04.in	AC	4 ms	4 MB
g++-13	01_case_05.in	AC	4 ms	4 MB
g++-13	01_pattern_00.in	AC	4 ms	4 MB
g++-13	01_pattern_01.in	AC	4 ms	4 MB
g++-13	01_pattern_02.in	AC	4 ms	3 MB
g++-13	01_pattern_03.in	AC	4 ms	4 MB
g++-13	01_pattern_04.in	AC	4 ms	4 MB
g++-13	01_pattern_05.in	AC	4 ms	4 MB
g++-13	01_pattern_06.in	AC	4 ms	4 MB
g++-13	01_pattern_07.in	AC	4 ms	4 MB
g++-13	01_pattern_08.in	AC	4 ms	4 MB
g++-13	01_pattern_09.in	AC	5 ms	4 MB
g++-13	02_rand_00.in	AC	5 ms	4 MB
g++-13	02_rand_01.in	AC	5 ms	4 MB
g++-13	02_rand_02.in	AC	5 ms	4 MB
g++-13	02_rand_03.in	AC	5 ms	4 MB
g++-13	02_rand_04.in	AC	5 ms	4 MB
g++-13	02_rand_05.in	AC	5 ms	4 MB
g++-13	02_rand_06.in	AC	5 ms	4 MB
g++-13	02_rand_07.in	AC	5 ms	4 MB
g++-13	02_rand_08.in	AC	6 ms	4 MB
g++-13	02_rand_09.in	AC	6 ms	4 MB
g++-13	02_rand_10.in	AC	7 ms	4 MB
g++-13	02_rand_11.in	AC	9 ms	4 MB
g++-13	02_rand_12.in	AC	9 ms	4 MB
g++-13	02_rand_13.in	AC	11 ms	4 MB
g++-13	02_rand_14.in	AC	12 ms	3 MB
g++-13	02_rand_15.in	AC	14 ms	3 MB
g++-13	02_rand_16.in	AC	16 ms	4 MB
g++-13	02_rand_17.in	AC	18 ms	3 MB
g++-13	02_rand_18.in	AC	21 ms	4 MB
g++-13	02_rand_19.in	AC	25 ms	4 MB
g++-13	02_rand_20.in	AC	29 ms	4 MB
g++-13	02_rand_21.in	AC	35 ms	4 MB
g++-13	03_corner_00.in	AC	5 ms	4 MB
g++-13	03_corner_01.in	AC	4 ms	4 MB
g++-13	03_corner_02.in	AC	4 ms	4 MB
g++-13	03_corner_03.in	AC	4 ms	4 MB
g++-13	04_extreme_00.in	AC	81 ms	4 MB
g++-13	04_extreme_01.in	AC	85 ms	4 MB
g++-13	04_extreme_02.in	AC	74 ms	4 MB
g++-13	04_extreme_03.in	AC	106 ms	4 MB
g++-13	05_biased_00.in	AC	90 ms	4 MB
g++-13	05_biased_01.in	AC	104 ms	4 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_case_00.in	AC	4 ms	4 MB
clang++-18	01_case_01.in	AC	4 ms	4 MB
clang++-18	01_case_02.in	AC	4 ms	4 MB
clang++-18	01_case_03.in	AC	4 ms	4 MB
clang++-18	01_case_04.in	AC	4 ms	4 MB
clang++-18	01_case_05.in	AC	4 ms	4 MB
clang++-18	01_pattern_00.in	AC	4 ms	4 MB
clang++-18	01_pattern_01.in	AC	4 ms	4 MB
clang++-18	01_pattern_02.in	AC	4 ms	4 MB
clang++-18	01_pattern_03.in	AC	4 ms	4 MB
clang++-18	01_pattern_04.in	AC	4 ms	4 MB
clang++-18	01_pattern_05.in	AC	4 ms	4 MB
clang++-18	01_pattern_06.in	AC	4 ms	4 MB
clang++-18	01_pattern_07.in	AC	4 ms	4 MB
clang++-18	01_pattern_08.in	AC	4 ms	4 MB
clang++-18	01_pattern_09.in	AC	4 ms	4 MB
clang++-18	02_rand_00.in	AC	4 ms	4 MB
clang++-18	02_rand_01.in	AC	4 ms	4 MB
clang++-18	02_rand_02.in	AC	4 ms	4 MB
clang++-18	02_rand_03.in	AC	4 ms	4 MB
clang++-18	02_rand_04.in	AC	4 ms	4 MB
clang++-18	02_rand_05.in	AC	4 ms	4 MB
clang++-18	02_rand_06.in	AC	4 ms	4 MB
clang++-18	02_rand_07.in	AC	5 ms	4 MB
clang++-18	02_rand_08.in	AC	5 ms	4 MB
clang++-18	02_rand_09.in	AC	6 ms	4 MB
clang++-18	02_rand_10.in	AC	7 ms	4 MB
clang++-18	02_rand_11.in	AC	8 ms	4 MB
clang++-18	02_rand_12.in	AC	8 ms	4 MB
clang++-18	02_rand_13.in	AC	10 ms	4 MB
clang++-18	02_rand_14.in	AC	11 ms	4 MB
clang++-18	02_rand_15.in	AC	13 ms	4 MB
clang++-18	02_rand_16.in	AC	15 ms	4 MB
clang++-18	02_rand_17.in	AC	16 ms	4 MB
clang++-18	02_rand_18.in	AC	19 ms	4 MB
clang++-18	02_rand_19.in	AC	24 ms	4 MB
clang++-18	02_rand_20.in	AC	28 ms	4 MB
clang++-18	02_rand_21.in	AC	35 ms	4 MB
clang++-18	03_corner_00.in	AC	5 ms	4 MB
clang++-18	03_corner_01.in	AC	4 ms	4 MB
clang++-18	03_corner_02.in	AC	4 ms	4 MB
clang++-18	03_corner_03.in	AC	4 ms	4 MB
clang++-18	04_extreme_00.in	AC	81 ms	4 MB
clang++-18	04_extreme_01.in	AC	83 ms	4 MB
clang++-18	04_extreme_02.in	AC	74 ms	4 MB
clang++-18	04_extreme_03.in	AC	101 ms	4 MB
clang++-18	05_biased_00.in	AC	89 ms	4 MB
clang++-18	05_biased_01.in	AC	102 ms	4 MB

Back to top page