Submission #673122

#	Time	Username	Problem	Language	Result	Execution time	Memory
673122		beedle	Split the sequence (APIO14_sequence)	C++17	0 / 100	281 ms	4628 KiB

sequence

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

double intersection(pair <ll,ll> c1, pair <ll,ll> c2)
{
    double lo=c2.ff;
    double hi=c2.ff;
    while(c2.ss+(c2.ff-hi)*(c2.ff-hi)>c1.ss+(c1.ff-hi)*(c1.ff-hi))
    hi*=2;
    double best=hi;
    while(hi-lo>1e-1)
    {
        double mid=(lo+hi)/2.0;
        if(c2.ss+(c2.ff-mid)*(c2.ff-mid)<=c1.ss+(c1.ff-mid)*(c1.ff-mid))
        best=mid, hi=mid;
        else
        lo=mid;
    }
    return best;
}

signed main()
{
    fast;

    // freopen("curling.in","r",stdin);
    // freopen("curling.out","w",stdout);

    ll n,k;
    cin>>n>>k;

    k+=1;

    ll arr[n+1];
    rep(i,1,n)
    cin>>arr[i];

    ll s[n+1];
    s[0]=0;
    rep(i,1,n)
    s[i]=s[i-1]+arr[i];

    deque <pair <ll,ll>> curves;    // x,y
    vector <ll> dp(n+1);
    int to[n+1][k+1];
    rep(i,1,n)
    {
        dp[i]=s[i]*s[i];
        to[i][1]=0;
        curves.push_back({i,dp[i]});
        while(sz(curves)>=3)
        {
            if(intersection(curves[sz(curves)-3],curves[sz(curves)-2])>=intersection(curves[sz(curves)-3],curves[sz(curves)-1]))
            curves.pop_back(), curves.pop_back(), curves.push_back({i,dp[i]});
            else
            break;
        }
    }
    
    deque <pair<ll,ll>> newcurves;
    rep(j,2,k)
    {
        // cout<<j<<": "<<endl;
        // for(auto x:curves)
        // cout<<x.ff<<","<<x.ss<<"  ";
        // cout<<endl;
        rep(i,j,n)
        {
            while(sz(curves)>=2)
            {
                if(curves[0].ff<i && curves[1].ff<i && curves[0].ss+(s[i]-s[curves[0].ff])*(s[i]-s[curves[0].ff])>=curves[1].ss+(s[i]-s[curves[1].ff])*(s[i]-s[curves[1].ff])) 
                curves.pop_front();
                else
                break;
            }
            dp[i]=curves[0].ss+(s[i]-s[curves[0].ff])*(s[i]-s[curves[0].ff]);
            to[i][j]=curves[0].ff;
            newcurves.push_back({i,dp[i]});
            while(sz(newcurves)>=3)
            {
                if(intersection(newcurves[sz(newcurves)-3],newcurves[sz(newcurves)-2])>=intersection(newcurves[sz(newcurves)-3],newcurves[sz(newcurves)-1]))
                newcurves.pop_back(), newcurves.pop_back(), newcurves.push_back({i,dp[i]});
                else
                break;
            }
        }
        swap(curves,newcurves);
        newcurves.clear();
    }

    cout<<(s[n]*s[n]-dp[n])/2<<endl;

    for(ll idx=n,br=k;br>=2;br--)
    {
        idx=to[idx][br];
        cout<<idx<<" ";
    }

    return 0;  
}

/*
7 3
4 1 3 4 0 2 3
*/

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