# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1218907 | cpdreamer | Cake 3 (JOI19_cake3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
void file() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
void solve() {
int n;
cin>>n;
int m;
cin>>m;
P<ll,ll>a[n+1];
for (int i=1;i<=n;i++) {
cin>>a[i].S>>a[i].F;
}
sort(a+1,a+n+1);
ll ans=LLONG_MIN;
for (int i=1;i<=n;i++) {
for (int j=i+m-1;j<=n;j++) {
ll s=a[i].S+a[j].S;
V<ll>v;
for (int g=i+1;g<j;g++) {
v.pb(a[g].S);
}
sort(all(v));
reverse(all(v));
for (int g=0;g<m-2;g++) {
s+=v[g];
}
s-=2*(a[j].F-a[i].F);
ans=max(ans,s);
}
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//file();
solve();
}#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
void file() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}
void solve() {
int n;
cin>>n;
int m;
cin>>m;
P<ll,ll>a[n+1];
for (int i=1;i<=n;i++) {
cin>>a[i].S>>a[i].F;
}
sort(a+1,a+n+1);
ll ans=LLONG_MIN;
for (int i=1;i<=n;i++) {
for (int j=i+m-1;j<=n;j++) {
ll s=a[i].S+a[j].S;
V<ll>v;
for (int g=i+1;g<j;g++) {
v.pb(a[g].S);
}
sort(all(v));
reverse(all(v));
for (int g=0;g<m-2;g++) {
s+=v[g];
}
s-=2*(a[j].F-a[i].F);
ans=max(ans,s);
}
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//file();
solve();
}