Submission #549993

#	Time	Username	Problem	Language	Result	Execution time	Memory
549993		Deepesson	Cake 3 (JOI19_cake3)	C++17	24 / 100	167 ms	27064 KiB

cake3

#include <bits/stdc++.h>

using ll = long long;

typedef std::pair<ll,ll> pll;
///Eu sei como resolver para um M infinito, mas como faco para um M FINITO???
///Ideia do M infinito:
///O custo do absoluto eh basicamente MAX*2 - MIN*2
///O resto N importa muito, eu tenho que pegar a soma dos M-2 maiores elementos entre L e R (alem da soma do A de L e R)
///Relaxacao lagrangiana talvez?
#define MAX 2005
int N,M;
std::vector<pll> vec;
bool existe[MAX][MAX];
ll tab[MAX][MAX];
ll inf = (1LL<<60LL);
ll dp(int pos,int pega){
    if(pega==M){
        return 0;
    }
    if(pos==N)return -inf;
    if(existe[pos][pega])return tab[pos][pega];
    existe[pos][pega]=true;
    ll resp = -inf;
    resp=std::max(resp,dp(pos+1,pega));
    if(!pega){
        resp=std::max(resp,dp(pos+1,pega+1)+(2LL*vec[pos].first)+vec[pos].second);
    }else if(pega!=M-1){
        resp=std::max(resp,dp(pos+1,pega+1)+vec[pos].second);
    }else {
        resp=std::max(resp,dp(pos+1,pega+1)+vec[pos].second-(2LL*vec[pos].first));
    }
    return tab[pos][pega]=resp;
}
int main()
{
    std::cin>>N>>M;
    for(int i=0;i!=N;++i){
        ll a,b;
        std::cin>>a>>b;
        vec.push_back({b,a});
    }
    std::sort(vec.begin(),vec.end());
    std::cout<<dp(0,0)<<"\n";
}

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