Submission #927509

#	Time	Username	Problem	Language	Result	Execution time	Memory
927509		AlphaMale06	Split the sequence (APIO14_sequence)	C++17	100 / 100	375 ms	83996 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

#define pb push_back
#define F first
#define S second

struct line{
    int slope;
    ll c;
    ll eval(int x){
        return slope*1ll*x+c;
    }
    ld interx(line & a){
        return (ld)(a.c-c)/(ld)(slope-a.slope);
    }
};
const int N = 1e5+10;
ll dp[N];
int red[205][N];
line chtl[N];
int chtr[N];
int a[N];
ll pref[N];


signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i=0; i< n; i++){
        cin >> a[i];
        pref[i+1]=pref[i]+a[i];
    }
    for(int j=1; j<=k; j++){
        int r=n+5;
        int l=n+5;
        chtl[l]={-pref[j-1], dp[j]};
        chtr[l]=j;
        l--;
        for(int i=j+1; i<=n; i++){
            int x = pref[n]-pref[i-1];
            while(r-l>=2){
                if(chtl[r].eval(x)>chtl[r-1].eval(x))break;
                r--;
            }
            pair<line, int> np = {{-pref[i-1], dp[i]}, i};
            dp[i]=chtl[r].eval(x)+pref[i-1]*(pref[n]-pref[i-1]);
            red[j][i]=chtr[r];
            while(r-l>=2){
                if(chtl[l+1].slope==np.F.slope){
                    if(chtl[l+1].c<=np.F.c){
                        l++;
                        continue;
                    }
                    else break;
                }
                ld inter1 = chtl[l+1].interx(chtl[l+2]);
                ld inter2 = np.F.interx(chtl[l+2]);
                if(inter2<inter1)break;
                l++;
            }
            chtl[l]=np.F;
            chtr[l]=np.S;
            l--;
        }
    }
    ll ans=0;
    int ind=0;
    for(int i=1; i<=n; i++){
        if(dp[i]>=ans){
            ans=dp[i];
            ind=i;
        }
    }
    cout << ans << '\n';
    vector<int> con;
    con.pb(ind);
    for(int i=k; i>1; i--){
        con.pb(red[i][ind]);
        ind=red[i][ind];
    }
    sort(con.begin(), con.end());
    for(int i=0; i<k; i++){
        cout << con[i]-1 << " ";
    }
    cout << '\n';

}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44:18: warning: narrowing conversion of '- pref[(j - 1)]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   44 |         chtl[l]={-pref[j-1], dp[j]};
      |                  ^~~~~~~~~~
sequence.cpp:53:36: warning: narrowing conversion of '- pref[(i - 1)]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   53 |             pair<line, int> np = {{-pref[i-1], dp[i]}, 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