//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Cắt dãy

 

Cho số nguyên N và một dãy số nguyên a1, a2, …, aN. Nhiệm vụ của bạn là phải cắt dãy số trên thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:

  • Tổng của mỗi dãy số không lớn hơn số nguyên M.
  • Tổng của các số lớn nhất trong các dãy trên là nhỏ nhất.

InputCUTSEQ.INP

  • Dòng đầu gồm 2 số nguyên N và M.
  • Dòng thứ hai gồm N số nguyên của dãy a1, a2, …, aN.

Output:            CUTSEQ.OUT

  • Gồm một số duy nhất là tổng của các số lớn nhất trong các dãy số trên. Nếu không có cách cắt nào thỏa mãn hai điều kiện trên, in ra -1.

Giới hạn:

  • 1 ≤ N ≤ 100000.
  • 0 ≤ ai ≤ 106.
  • M  < 263.
  • Thời gian: 3 s/test
  • Bộ nhớ: 32MB

Ví dụ:

CUTSEQ.INP CUTSEQ.OUT
8 172 2 2 8 1 8 2 1 12

(Cắt thành 3 dãy 2 2 2, 8 1 8, 2 1)

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: