Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

INVESHOP - Chuỗi cửa hàng

Bờm vừa mới nhận được một khoản tiền thù lao lớn từ bản thiết kế công viên giải trí trong thành phố. Bây giờ, Bờm muốn sử dụng khoản tiền này để đầu tư vào việc phát triển chuỗi cửa hàng bán thực phẩm sạch. Bờm quyết định mua một dãy các cửa hàng liên tiếp dọc theo đại lộ thương mại của thành phố.

Để có được quyền sử dụng một cửa hàng trên đại lộ này, Bờm phải trả tiền cho chủ sở hữu hiện tại của nó. Tuy nhiên, cũng có một số cửa hàng do việc kinh doanh thua lỗ trong nhiều năm, chủ sở hữu của nó đồng ý nhượng lại quyền sử dụng cho Bờm chỉ để cắt lỗ, thậm chí còn trả tiền để hỗ trợ chủ mới thuê cửa hàng của mình. Cụ thể, dọc theo đại lộ có N cửa hàng liên tiếp được đánh số từ 1 đến N theo thứ tự đi dọc theo đại lộ. Cửa hàng thứ i gắn với số nguyên si là chi phí mà Bờm phải trả để có được quyền sử dụng nó. Nếu si là số âm thì điều đó có nghĩa là Bờm không những không phải trả tiền mà còn được chủ sở hữu của cửa hàng i hỗ trợ lượng tiền là si để thay chủ cũ tiếp tục sử dụng cửa hàng này.

Yêu cầu: Biết S là tổng lượng tiền mà Bờm có thể chi cho việc mở hoạt động kinh doanh, hãy giúp Bờm xác định cách mua được dãy gồm một số nhiều nhất các cửa hàng liên tiếp trên đại lộ với tổng chi phí không vượt quá S. Thông tin này sẽ hỗ trợ Bờm rất nhiều trong việc lựa chọn cách đầu tư tối ưu.

Input:

  • Dòng đầu tiên chứa hai số nguyên dương NS (N ≤ 500000; S ≤ 109) theo thứ tự là số lượng cửa hàng trên đại lộ và tổng lượng tiền mà Bờm có thể đầu tư;
  • Dòng thứ hai chữa dãy số nguyên s1, s2, …, sn (| si | ≤ 106) là lượng tiền Bờm phải chi (hoặc thu được nếu là số âm) để sở hữu các cửa hàng tương ứng.

Output:

Ghi ra hai số nguyên ab, trong đó a là số lượng cửa hàng trong các mua tìm được, còn b là chỉ số của cửa hàng đầu tiên trong dãy các cửa hàng liên tiếp tìm được (nếu có nhiều dãy như vậy hãy đưa ra dãy với chỉ số b là nhỏ nhất).

Ví dụ:

Input:
15 666
101 42 -132 17 404 -13 55 222 89 11 -66 91 -9 21 4

Output:
10 2

Giải thích: Có thể mua dãy 10 cửa hàng liên tiếp bắt đầu từ cửa hàng thứ 2 (có giá 42) với tổng chi phí là 42 – 132 + 17 + 404 – 13 + 55 + 222 + 89 + 11 – 66 = 629 (không vượt quá tổng vốn đầu tư 666). Có thể mua dãy 10 cửa hàng liên tiếp bắt đầu từ cửa hàng 6 với chi phí nhỏ hơn (-13 + 55 + 222 + 89 + 11 – 66 + 91 – 9 + 21 + 4 = 405), nhưng bạn cần đưa ra lời giải với chỉ số của cửa hàng bắt đầu là nhỏ nhất.


Được gửi lên bởi:noname00.pas
Ngày:2017-11-26
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập Ôn HN 01/2017 (Thầy Nguyễn Đức Nghĩa)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.