Submission #989341

#	Time	Username	Problem	Language	Result	Execution time	Memory
989341		vjudge1	Split the sequence (APIO14_sequence)	C++17	100 / 100	854 ms	82260 KiB

sequence

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define fi first
#define se second
 
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
 
const int N = 1e5+5;
const int mod = 1e9+7;
const int SQ = 450;
const int inf = 1e16;

unsigned int n,m,a[N],dp[2][N],cur,p[N];
int32_t par[205][N];

int cost(int l,int r)
{
    return (p[r]-p[l-1])*p[l-1];
}

void dnc(int l,int r,int optl,int optr)
{
    if(l>r) return;
    int m=l+r>>1;
    pair<int,int> best={-inf,-1};
    for(int k=optl;k<=min(m,optr);k++) best=max(best,{dp[cur&1^1][k-1]+cost(k,m),k});
    dp[cur&1][m]=best.fi;
    int opt=best.se;
    par[cur][m]=opt-1;
    dnc(l,m-1,optl,opt);
    dnc(m+1,r,opt,optr);
}

signed main()
{
    fastIO
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[i]=p[i-1]+a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cur=i;
        dnc(1,n,1,n);
    }
    cout<<dp[m&1][n]<<endl;
    int x=m,y=n;
    while(x)
    {
        cout<<par[x][y]<<' ';
        y=par[x][y];
        x--;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
sequence.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int m=l+r>>1;
      |           ~^~
sequence.cpp:36:61: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   36 |     for(int k=optl;k<=min(m,optr);k++) best=max(best,{dp[cur&1^1][k-1]+cost(k,m),k});
      |                                                          ~~~^~
sequence.cpp: In function 'int main()':
sequence.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   50 |     for(int i=1;i<=n;i++)
      |                 ~^~~
sequence.cpp:55:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   55 |     for(int i=1;i<=m;i++)
      |                 ~^~~

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