Submission #722039

#	Time	Username	Problem	Language	Result	Execution time	Memory
722039		Bobonbush	Split the sequence (APIO14_sequence)	C++17	100 / 100	1374 ms	81012 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MODULO = 12;
template<class X , class Y>
    bool Maximize(X &x  , Y y)
    {
        if(x < y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X ,class Y>
    bool Minimize(X &x , Y y)
    {
        if(x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X ,class Y>
    void Add(X &x ,  Y y)
    {
        x += y;
        if(x >= MODULO) x-= MODULO;
    }
template<class X ,class Y>
    void Sub(X & x , Y y)
    {
        x -= y;
        if(x < 0 ) x += MODULO;
    }
const int N = 1e5+1;
long long dp[2][N];
long long a[N];
int P[201][N];
long long cost(int l ,int r)
{
    assert(l <= r);
    return (a[r] - a[l-1]) * (a[r] - a[l-1]);
}

void conq(int l ,int r ,int opt_l , int opt_r , bool cur , int k)
{
    if(l > r)return ;
    int mid = (l+r) >> 1;

    dp[cur][mid] = (1ll << 61);
    int opt;
    for(int i = opt_l ; i <=min(mid -1 , opt_r) ; i++)
    {
        long long sta = dp[!cur][i] + cost(i +1 , mid);
        if(Minimize(dp[cur][mid] , sta))
        {
            opt = i;
        }
    }  
    P[k][mid] = opt;
    conq(l , mid-1 , opt_l , opt , cur ,  k);
    conq(mid+1 , r , opt , opt_r , cur , k );
} 
vector<int>List;

void trace(int k , int i)
{
    if(k == 0)
    {
        return ;
    }

    trace(k-1  , P[k][i] );
    cout << P[k][i] << ' ';
 
}
int n ;
int  k;


void Input()
{
    cin >> n >> k;
    for(int i = 1; i <= n ; i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
    }
}
void Process()
{
    bool cur = false;
    for(int i = 1 ; i <= n ; i++)
    {    
        dp[cur][i] = cost(1 , i);
    }
    for(int g = 1 ; g <= k ; g++)
    {
        cur ^= 1;
        conq(g +1 , n , g , n , cur , g );
    }

    cout << (cost(1 , n ) - dp[cur][n]) /2LL <<'\n';
    

    trace(k , n);
}

int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    int test = 1;
    while(test--)
    {
        Input();
        Process();
        cout <<'\n';
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void conq(int, int, int, int, bool, int)':
sequence.cpp:64:9: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     conq(mid+1 , r , opt , opt_r , cur , k );
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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