trang chủ / đề bài / twoseals

Hai con dấu

Đề bài

Mô tả

Cho một tờ giấy hình chữ nhật kích thước a×b và n con dấu. Con dấu thứ i để lại một vết mực hình chữ nhật kích thước xi×yi.

Bạn phải chọn ra hai con dấu khác nhau và đóng mỗi con dấu đúng một lần lên tờ giấy. Mỗi vết dấu phải nằm trọn trong tờ giấy, có các cạnh song song với cạnh tờ giấy, và trước khi đóng bạn được phép xoay con dấu 90∘ (vết xi×yi trở thành yi×xi). Hai vết dấu không được chồng lên nhau, nhưng được phép chạm cạnh nhau.

Lưu ý rằng việc từng con dấu riêng lẻ vừa tờ giấy là chưa đủ: hai vết dấu còn phải cùng nằm trên tờ giấy mà không đè lên nhau.

Hãy tìm tổng diện tích lớn nhất mà hai vết dấu có thể chiếm. Nếu không tồn tại cặp con dấu nào thỏa mãn, in ra 0.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên n, a, b (1≤n,a,b≤100) — số con dấu và kích thước tờ giấy.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi, yi (1≤xi,yi≤100) — kích thước vết của con dấu thứ i.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng diện tích lớn nhất mà hai vết dấu có thể chiếm, hoặc 0 nếu không chọn được hai con dấu nào.

Ràng buộc

  • 1≤n,a,b≤100
  • 1≤xi,yi≤100
  • Hai con dấu được chọn phải khác nhau (khác chỉ số), kể cả khi chúng có cùng kích thước.

Ví dụ

Input Output Giải thích
2 2 2
1 2
2 1
4 Xoay con dấu thứ hai 90∘ để nó cũng thành 1×2, rồi đặt hai vết cạnh nhau theo chiều ngang. Chúng phủ kín tờ giấy 2×2, tổng diện tích 2+2=4.
4 10 9
2 3
1 1
5 10
9 11
56 Con dấu thứ tư 9×11 không vừa tờ giấy dù xoay kiểu nào (11>10 và 11>9). Chọn con dấu thứ ba xoay thành 10×5 (diện tích 50) và con dấu thứ nhất xoay thành 3×2 (diện tích 6), xếp chồng theo chiều dọc: chiều cao 5+2=7≤9. Tổng 56.
3 10 10
6 6
7 7
20 5
0 Con dấu 20×5 không vừa tờ giấy. Hai con dấu còn lại 6×6 và 7×7 mỗi cái đều vừa tờ giấy, nhưng không thể đặt đồng thời vì 6+7=13>10 theo cả chiều ngang lẫn chiều dọc.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0