//
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)

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 236,751 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: