Submission #789075

#	Time	Username	Problem	Language	Result	Execution time	Memory
789075		1075508020060209tc	Cake 3 (JOI19_cake3)	C++14	0 / 100	1 ms	724 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];
 int chk[5010][5010];
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);
        int vis=0;int v=0;
        vector<int>pl;
    for(int j=2;j<=m-1;j++){
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+ar[i].second);
        if(dp[i][j]==dp[i-1][j-1]+ar[i].second){
            pl.push_back(j);
        }
    }
    for(int j=1;j<pl.size();j++){
        if(pl[j]-pl[j-1]!=1){return 0;}
    }
    ans=max(ans,dp[i][m-1]+sfmx[i+1]);
}
cout<<ans<<endl;


}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:42:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int j=1;j<pl.size();j++){
      |                 ~^~~~~~~~~~
cake3.cpp:34:13: warning: unused variable 'vis' [-Wunused-variable]
   34 |         int vis=0;int v=0;
      |             ^~~
cake3.cpp:34:23: warning: unused variable 'v' [-Wunused-variable]
   34 |         int vis=0;int v=0;
      |                       ^

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