Решение задачи Кефа и компания с Codeforces

Без пояснения   Просмотров: 34

Кефа хочет отметить свой первый крупный заработок походом в ресторан. Однако ему нужна компания.

У Кефы есть n друзей, каждый из которых согласится пойти в ресторан, если Кефа попросит. Каждый друг характеризуется количеством денег у него и степенью дружбы с Кефой. Наш попугай не хочет, чтобы какой-то друг почувствовал себя бедным по сравнению с кем-то другим в компании (Кефа не в счет). Друг чувствует себя бедным, если в компании есть кто-то, у кого денег хотя бы на d единиц больше, чем у него. Также Кефа хочет, чтобы суммарная степень дружбы членов компании была максимальной. Помогите ему пригласить оптимальную компанию!

Код 

#include<bits/stdc++.h>
using namespace std;
long long n,d,s,m,c,mx;
int j;
pair<long long,long long> p[200000];
int main()
{
	cin>>n>>d;
	for(int i=0;i<n;i++)
	{
		cin>>m>>s;
		p[i]={m,s};
	}
	sort(p,p+n);
	for(int i=0;i<n;i++)
	{
		j=max(j,i);
		while(p[j].first-p[i].first<d&&j<n)
		{
			c+=p[j].second;
			j++;
		}
		mx=max(mx,c);
		c-=p[i].second;
	}
	cout<<mx;
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта