Submission #1218953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218953		cpdreamer	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	324 KiB

cake3

#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);
}
ll f(int n,int m,P<ll,ll>a[]) {
    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);
        }
    }
    return ans;
}
ll g(int n,int m,P<ll,ll>a[]) {
    sort(a+1,a+n+1);
    ll pref[n+1];
    pref[0]=0LL;
    for (int i=1;i<=n;i++) {
        pref[i]=pref[i-1]+a[i].S;
    }
    ll cost=0;
    multiset<ll>st;
    for (int i=1;i<=m;i++) {
        cost+=a[i].S;
        if (i>1) {
            st.insert(a[i].S);
        }
    }
    cost-=2*(a[m].F-a[1].F);
    ll ans=cost;
    for (int i=m+1;i<=n;i++) {
        cost-=*st.begin();
        st.erase(st.begin());
        st.insert(a[i].S);
        cost+=a[i].S;
        cost-=2*(a[i].F-a[i-1].F);
        ll x=pref[i]-pref[i-m]-2LL*(a[i].F-a[i-m+1].F);
        if (x>cost) {
            st.clear();
            for (int j=i;j>=i-m+2;j--) {
                st.insert(a[i].S);
            }
            cost=x;
        }
        ans=max(ans,cost);
    }
    return ans;
}
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;
    }
    cout<<g(n,m,a)<<endl;
}
void stress() {
    for (int j=0;j<10;j++) {
        int m=3+rand()%(int)5 ;
        int n=rand()%(int)5 + m;
        P<ll,ll>a[n+1];
        for (int i=1;i<=n;i++) {
            a[i].F=rand()%(int)100;
            a[i].S=rand()%(int)100;
        }
        if (f(n,m,a)!=g(n,m,a)) {
            cout<<n<<" "<<m<<endl;
            for (int i=1;i<=n;i++) {
                cout<<a[i].S<<" "<<a[i].F<<endl;
            }
            cout<<"correct: "<<f(n,m,a)<<endl;
            cout<<"output: "<<g(n,m,a)<<endl;
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //file();
    //stress();
    solve();
}

Compilation message (stderr)

cake3.cpp: In function 'void file()':
cake3.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76