# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1218927 | abdelhakim | Sequence (APIO23_sequence) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)(1e10)
#define mod (ll)(1e9 + 7)
#define dbg(x) cerr<<#x << ' ' << x << endl;
using v = vector<vector<vector<ll>>>;
ll sum(ll a, ll b)
{
cout << a-b << endl;
return a+b;
}
void printvec(vector<ll>& a)
{
ll n=a.size();
for (int i=0;i<n;i++)
{
cout <<a[i] << ' ';
}
cout << endl;
}
ll gcd(ll a, ll b)
{
if(b>a)swap(a,b);
if(b==0)return a;
return gcd(a%b,b);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
// cin>>t;
t=1;
while(t--)
{
ll n,m;
cin>>n>>m;
vector<pair<ll,ll>> p(n);
for (int i=0;i<n;i++){
cin>>p[i].second >> p[i].first;
}
sort(p.begin(),p.end());
ll ans=0;
for (int i=0;i<n;i++)
{
ll val=2*p[i].first+p[i].second;
set<ll,greater<ll>> st;
ll sm=0;
for (int j=i+1;j<n;j++)
{
if(st.size()>=m-2)
{
ll cur=0;
sm=0;
for (auto &&e : st)
{
sm+=e;
cur++;
if(cur==m-2)break;
}
ans=max(ans,val+sm+p[j].second-2*p[j].first);
}
st.insert(p[j].second);
// if(st.size()==m-2)
// {
// ans=max(ans,val+sm+p[j].second-2*p[j].first);
// if(*st.begin() < p[j].second)
// {
// sm+=-*st.begin()+p[j].second;
// st.erase(*st.begin());
// st.insert(p[j].second);
// }
// }
// else
// {
// sm+=p[j].second;
// st.insert(p[j].second);
// }
}
}
cout << ans << endl;
}
}