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.|

PTIT126J - Chặt gỗ

Có N cây gỗ, có chiều cao lần lượt là A[1],A[2],..,A[n]. Bạn cần lấy một lượng gỗ độ cao tối thiểu là M bằng cách chặt từ N cây theo cách như sau: chặt tất cả những phần thừa của các cây có độ cao lớn hơn H. Hãy tìm giá trị H lớn nhất để bạn có thể lấy được lượng gỗ tối thiểu là M.

Input

- Dòng 1 chứa 2 số nguyên N (1<=N<=1 000 000) và M (1 <= M <= 2 000 000 000).

- Dòng 2 chứa N số nguyên A[1],A[2],…,A[n], là chiều cao mỗi cây gỗ tương ứng (A[i] <= 1 000 000 000, i=1->n). Giả sử luôn tồn tại cách chặt.

Output

Số H duy nhất.

Example

Input:

4 7

20 15 10 17

Output: 15

Giải thích:

Cây 1 chặt được (20-15)=5.

Cây 4 chặt được (17-15)=2.

Tổng số gỗ chặt được nếu H=15 là 7.

Input:

5 20

4 42 40 26 46

Output:

36


Được gửi lên bởi:adm
Ngày:2012-03-22
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2019-03-09 14:01:55
ai chỉ cách nọop pascal với
2017-11-29 04:32:44
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
long long a[1000007];
int main()
{
long long n,m,i;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(i=n;i>=1;i--)
{
if((a[i]-a[i-1])*(n-i+1)>=m)
{
cout<<a[i]-m/(n-i+1);
return 0;
}
else
{
m=m-(a[i]-a[i-1])*(n-i+1);
}
}
}
//sai chỗ nào nhỉ :v
2017-03-16 16:35:35
accepted :)))
2017-01-05 08:58:17
mình làm lần đầu ac =))
2015-03-15 13:32:12 Banana
nhập 1 triệu phần tử như nào thế ?
2014-10-13 16:54:34 Cường D14AT1


Last edit: 2014-12-02 09:04:23
2014-05-01 04:49:21 Nguyễn Kim Long D13CN4 SRC Team X
có 1 triệu lần nhập, chắc vì thế mà lâu đấy :3
2013-05-12 06:00:18 LastShadow
sao lai sai nhi,test thu dung roi ma
2012-11-05 17:01:50 Vương Sỹ Huấn DH BK TP HCM
co ham sap xep nhanh hon SORT() trong STL
2012-09-16 06:43:28 Trần Vãn Dương D10CN2
chuan luon
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.