Submission #789072

#	Time	Username	Problem	Language	Result	Execution time	Memory
789072		1075508020060209tc	Cake 3 (JOI19_cake3)	C++14	24 / 100	448 ms	262144 KiB

cake3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int ans;
pair<int,int>ar[500005];
int dp[5010][5010];
int sfmx[500005];
 
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>ar[i].second>>ar[i].first;
}
sort(ar+1,ar+n+1);
sfmx[n]=-ar[n].first*2+ar[n].second;
for(int i=n-1;i>=1;i--){
    sfmx[i]=max(sfmx[i+1],ar[i].second-ar[i].first*2);
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        dp[i][j]=-1e15;
    }
}
int ans=-1e16;
dp[1][1]=ar[1].first*2+ar[1].second;
ans=dp[1][m-1]+sfmx[2];
for(int i=2;i<=n-1;i++){
        dp[i][1]=max(dp[i-1][1],ar[i].first*2+ar[i].second);
    for(int j=2;j<=m-1;j++){
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+ar[i].second);
    }
    ans=max(ans,dp[i][m-1]+sfmx[i+1]);
    for(int j=2;j<=i;j++){
       // if(dp[i][j]<dp[i][j-1]){return 0;}
    }
}
cout<<ans<<endl;
 
 
}

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