3-й этап Республиканской олимпиады по информатике 2022-2023, 1й тур

Задача B. Цена за мороженное

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вы продаете мороженное. Себестоимость одного мороженного $k$ тенге. Это значит, что если вы продаете одно мороженное по $x$ тенге, тогда прибыль с одного мороженного будет $x - k$ тенге. Есть $n$ клиентов, для каждого клиента $i$ известно максимальная сумма денег $s_i$ тенге, которую он готов потратить на мороженное. Каждый клиент купить столько мороженного, сколько сможет купить. Выберите цену мороженного таким образом, чтобы максимизировать суммарную прибыль.

Формат входного файла

В первой строке находятся два целых числа $n,k$($1 <= n <= 2 \cdot 10^5$, $0 <= k <= 10^6$) — количество клиентов и себестоимость одного мороженного. Во второй строке находятся $n$ целых числа $s_1, s_2, \cdots, s_n$($1 <= s_i <= 10^6$).

Формат выходного файла

Выведите максимальную возможную прибыль.

Примеры:

Вход

5 2
8 9 10 15 12

Ответ

30

Вход

3 20
15 10 20

Ответ

0

Замечание

В первом примере одно мороженное выгодно продавать по $7$ тенге. Тогда четвертый клиент купить 2 мороженное, а остальные 4 по одному. Всего продадим 6 мороженных. Прибыль с одного мороженного $5$($7 - 2$) тенге, тогда суммарная прибыль $6 \cdot 5 = 30$ тенге. ( Temirlan Satylkhanov )

Комментарий/решение

как это решается

//C.RONALDO IS G.O.A.T

//[e-mail]

//A2010

#include <bits/stdc++.h>

#define sed s.erase(unique(s.begin(),s.end()),s.end());

#define ll long long

#define sem s.emplace("To",3)

#define fi first

#define se second

#define aufi auto it = arr.find("To")

#define auer auto it = arr.erase("To")

#define cous count(s.begin(),s.end(),'N')

#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ser s.erase(remove(s.begin(),s.end(),' '),s.end());

#define KOE vector<tuple<int,int,int>> v;

using namespace std;

using ld=long double;

const ll MOD=998244353;

const ll N=3e5+10;

const ll inf=1e18;

int d[N];

int f[N];

vector<int>g[N];

int used[N];

void dfs(int v) {

used[v]=1;

for(auto to:g[v]){

if(!used[to]){

dfs(to);

}

}

}

/*ll funct(ll a){

ll s=0;

while(a!=0){

s+=a%!;

a/=!;

}

return s;

}*/

int gcd(int a,int b) {

if(b==0) return a;

return gcd(b,a%b);

}

void solve() {

string english_alphabet="abcdefghijklmnopqrstuvwxyz";

ll a,b;

cin>>a>>b;

for(int i=0;i<a;i++){

cin>>d[i];

}

ll mn=*min_element(d,d+a);

ll mx=*max_element(d,d+a);

if(b>=mx) cout<<"0\n";

else{

ll mxi=0;

ll sum=0;

while(b<mn){

for(ll i=0;i<a;i++){

sum+=d[i]/mn;

}

mxi=max(mxi,sum*(mn-b));

mn--;

sum=0;

}

cout<<mxi<<'\n';

}

}

int main() {

ios

//freopen("dining.in", "r", stdin);

//freopen("dining.out", "w", stdout);

int tt=1;

//cin>>tt;

while(tt--) {

solve();

}

}

почему не правильно на 5 тесте

показать/скрыть код

//C.RONALDO IS G.O.A.T

//[e-mail]

//A2010

#include <bits/stdc++.h>

#define sed s.erase(unique(s.begin(),s.end()),s.end());

#define ll long long

#define sem s.emplace("To",3)

#define fi first

#define se second

#define aufi auto it = arr.find("To")

#define auer auto it = arr.erase("To")

#define cous count(s.begin(),s.end(),'N')

#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ser s.erase(remove(s.begin(),s.end(),' '),s.end());

#define KOE vector<tuple<int,int,int>> v;

using namespace std;

using ld=long double;

const ll MOD=998244353;

const ll N=3e5+10;

const ll inf=1e18;

int d[N];

int f[N];

vector<int>g[N];

int used[N];

void dfs(int v) {

used[v]=1;

for(auto to:g[v]){

if(!used[to]){

dfs(to);

}

}

}

/*ll funct(ll a){

ll s=0;

while(a!=0){

s+=a%!;

a/=!;

}

return s;

}*/

int gcd(int a,int b) {

if(b==0) return a;

return gcd(b,a%b);

}

void solve() {

string english_alphabet="abcdefghijklmnopqrstuvwxyz";

ll a,b;

cin>>a>>b;

for(int i=0;i<a;i++){

cin>>d[i];

}

ll mn=*min_element(d,d+a);

ll mx=*max_element(d,d+a);

if(b>=mx) cout<<"0\n";

else{

ll mxi=0;

ll sum=0;

while(b<mn){

for(ll i=0;i<a;i++){

sum+=d[i]/mn;

}

mxi=max(mxi,sum*(mn-b));

mn--;

sum=0;

}

cout<<mxi<<'\n';

}

}

int main() {

ios

//freopen("dining.in", "r", stdin);

//freopen("dining.out", "w", stdout);

int tt=1;

//cin>>tt;

while(tt--) {

solve();

}

}

показать/скрыть код

//C.RONALDO IS G.O.A.T
//[e-mail]
//A2010
#include <bits/stdc++.h>
#define sed s.erase(unique(s.begin(),s.end()),s.end());
#define ll long long
#define sem s.emplace("To",3)
#define fi first
#define se second
#define aufi auto it = arr.find("To")
#define auer auto it = arr.erase("To")
#define cous count(s.begin(),s.end(),'N')
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ser s.erase(remove(s.begin(),s.end(),' '),s.end());
#define KOE vector<tuple<int,int,int>> v;
using namespace std;
using ld=long double;
const ll MOD=998244353;
const ll N=3e5+10;
const ll inf=1e18;
int d[N];
int f[N];
vector<int>g[N];
int used[N];
void dfs(int v) {
	used[v]=1;
	for(auto to:g[v]){
		if(!used[to]){
			dfs(to);
		}
	}
}
/*ll funct(ll a){
	ll s=0;
	while(a!=0){
		s+=a%!;
		a/=!;
	}
	return s;
}*/
int gcd(int a,int b) {
	if(b==0) return a;
	return gcd(b,a%b);
}
void solve() {
    string english_alphabet="abcdefghijklmnopqrstuvwxyz";
    ll a,b;
    cin>>a>>b;
    for(ll  i=0;i<a;i++){
        cin>>d[i];
    }
    ll mn=*min_element(d,d+a);
    ll mx=*max_element(d,d+a);
    if(b>=mx) cout<<"0\n";
    else{
        ll mxi=0;
        while(b<mx){
            ll sum=0;
            for(ll i=0;i<a;i++){
                sum+=d[i]/mx;        
            }
            mxi=max(mxi,sum*(mx-b));
            mx--;
        }
        cout<<mxi<<'\n';
    }
}
int main() {
	ios
	//freopen("dining.in", "r", stdin);
	//freopen("dining.out", "w", stdout);
	int tt=1;
	//cin>>tt;
	while(tt--) {
		solve();
	}
}