Submission #855423

#	Time	Username	Problem	Language	Result	Execution time	Memory
855423		vjudge1	Split the sequence (APIO14_sequence)	C++17	50 / 100	310 ms	32684 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")


using namespace std;

using lol= long long int;

typedef long long ll;
typedef long double ld;
typedef long long unsigned lli;
// #define _MAXM 16000
#define cl clear
#define int ll
#define db double
#define pb push_back
#define ers erase
#define ds resize
#define W INT_MIN
#define mp make_pair
#define pll pair< long , long >
#define pii pair<ll, ll>
#define bc back()
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
#define doc (clock() * 1.0 / CLOCKS_PER_SEC) < 1.0
#define all(v) v.begin(),v.end()





const int MAX = 100 + 5;
const int LOG = 18;
const ll INF = 1e18;
const ll inf = 1e18;
const int maxn = 1e5+5;
const double me = 1e-9;
const double PI=acos(-1.0);
const int M= 1e6;
const int mod =  998244353;
const int mxn=2e5+3;
const int MAXA = 1e6 + 10;
const int MOD =  1e9 + 7;
const int DN = 4008;
const int N = 1000 + 5;

int n, k;
int dp[N][N];
int opt[N][N];
vector< int > ps(N);
 
int go(int i , int j){
    if(j > k+ 1){
        return -INF;
    }
    if(i == n + 1){
        if(j < k + 1){
            return -INF;
        }
        return 0;
    }
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    int ans = -INF;
    int ind;
    for(int k = i; k <= n; k++){
        int cur = go(k + 1, j + 1) + (ps[k] - ps[i - 1]) * (ps[n] - ps[k]);
        if(cur > ans){
            ans = cur;
            ind = k + 1;
        }
    }
 
    opt[i][j] = ind;
    return dp[i][j] = ans;
}

void kick(){

    cin >> n >> k;
 
    vector< int > a(n + 5);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        ps[i] = ps[i - 1] + a[i];
    }
 
    memset(dp, -1 ,sizeof dp);
    cout << go(1,0) << '\n';
 
    int curi = 1 ;
    int curj = 0;
 
    while(true){
        curi = opt[curi][curj];
        curj++;
        if(curi == n + 1){
            break;
        }
        cout << curi - 1  << " ";
    }


}




    
signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 



    int T = 1;

    // cin >> T; 
    // cout.flush();

    
    while(T--){

        kick();
       
        
    }


    

    return 0;

    
}

Compilation message (stderr)

sequence.cpp: In function 'll go(ll, ll)':
sequence.cpp:76:15: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     opt[i][j] = ind;
      |     ~~~~~~~~~~^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29