Nội dung Bài tập
Mã:
GROUP
Tên:
GROUP - Phân nhóm
Dạng thi:
oi
Thang điểm:
10 điểm
Giới hạn thời gian:
1 giây
Giới hạn bộ nhớ:
256 MB
Được tạo bởi:
admin
Share

Cho n<=300000 cặp số (x,y) (1<=x, y<=1000000). Ta có thể nhóm một vài cặp số lại thành một nhóm. Giả sử một nhóm gồm các cặp số thứ a1, a2, ..., am thì chi phí cho nhóm này sẽ là max(xa1, xa2, ..., xam) * max(ya1, ya2, ..., yam).

Yêu cầu: tìm cách phân nhóm có tổng chi phí bé nhất.

Dữ liệu

  • Dòng đầu tiên là số nguyên dương N.
  • N dòng tiếp theo dòng thứ i ghi 2 số xi và yi.

Kết quả

  • Gồm 1 số duy nhất là kết quả tìm được.

Ví dụ


InputOutput
4
100 1
15 15
20 5
1 100


500
Giải thích: Có 3 nhóm lần lượt là (1), (2,3) và (4).
Nguồn: http://vn.spoj.com/problems/GROUP/
    Quảng cáo
       Ngôn ngữ : 

       Theme : 
Mời bạn soạn code 



				
		

		

		

		

			

		

	

		



















 


















      Ai có thể xem bài này : 
















Thông tin

















    

	



Phần thảo luận



























       	
	














































 



					


		
	


Bài tập mới





C4.DQ.20: 
Tính giá trị






HARDCANDY: 
Chọn cách mua kẹo (khó)




BORINGCANDY: 
Chọn cách mua kẹo




olpacm_planetmapping: 
Vẽ bản đồ hành tinh




BSTree_TEST: 
Cây nhị phân tìm kiếm




OLP24_Toan01: 
Đậu thần kì




XOACHUOITVB: 
Xóa càng nhiều càng được nhiều điểm




GTCD: 
Giai thừa chia dư




Luythuatb: 
Lũy thừa 




GOM_DUA: 
Gom Đũa




thamlamcb2: 
Phân số đơn vị (egyptian fractions)







Coder tích cực





4901104081: 1480 bài
CODER PHÓ GIÁO SƯ[20160♥]







4601103044: 1607 bài
CODER PHÓ GIÁO SƯ[19580♥]







4901104074: 1111 bài
CODER PHÓ GIÁO SƯ[15610♥]







(≧ω≦)ゞ: 814 bài
CODER PHÓ GIÁO SƯ[15175♥]







Hanabi: 972 bài
CODER PHÓ GIÁO SƯ[14960♥]



Xem thêm



    Quảng cáo