Submission #549993

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
549993	2022-04-17 03:37:14	Deepesson	Cake 3 (JOI19_cake3)	C++17	24 / 100	167 ms	27064 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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