Submission #721312

#	Time	Username	Problem	Language	Result	Execution time	Memory
721312		n0sk1ll	Split the sequence (APIO14_sequence)	C++14	71 / 100	1714 ms	131072 KiB

sequence

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#define int li

int a[100005];
li dp[100005][2]; //preth i cur
int gde[100005][202];
int pre[100005];

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

void rekurz(int n, int k)
{
    if (k==0) return;
    rekurz(gde[n][k],k-1),cout<<max(1ll,gde[n][k])<<" ";
}

int k=1;
vector<pair<pli,int>> len[271828];
vector<ld> presek[271828];
int l[271828],r[271828];

ld preseci(pli a, pli b)
{
    return (ld)(b.yy-a.yy)/(a.xx-b.xx);
}

void try_add(int i, pair<pli,int> a)
{
    if (presek[i].empty()) presek[i].pb(-1e18),len[i].pb(a);
    else
    {
        if (a.xx.xx==len[i].back().xx.xx) return;
        ld p=preseci(a.xx,len[i].back().xx);
        while (p<=presek[i].back()) presek[i].popb(),len[i].popb();
        len[i].pb(a),presek[i].pb(p);
    }
}

void merge(int i)
{
    int aa=0,bb=0;
    while (true)
    {
        bool gde=0;
        if (aa==presek[2*i].size())
        {
            if (bb==presek[2*i+1].size()) break;
            gde=1;
        }
        else if (bb==presek[2*i+1].size()) gde=0;
        else gde=(len[2*i+1][bb].xx<len[2*i][aa].xx || (len[2*i+1][bb].xx==len[2*i][aa].xx && len[2*i+1][bb].yy>len[2*i][aa].yy));

        if (gde) try_add(i,len[2*i+1][bb++]);
        else try_add(i,len[2*i][aa++]);
    }
}

pli qry(int p, li x)
{
    int bs=lower_bound(all(presek[p]),x)-presek[p].begin()-1;
    return {len[p][bs].xx.xx*x+len[p][bs].xx.yy,len[p][bs].yy};
}
pli qry(int p, int ll, int rr, li x)
{
    if (ll>r[p] || rr<l[p]) return {-1e18,-1};
    if (ll<=l[p] && rr>=r[p]) return qry(p,x);
    return max(qry(2*p,ll,rr,x),qry(2*p+1,ll,rr,x));
}

void ispisi()
{
    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk)
        {
            ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
            cout<<"; ";
        } cout<<endl;
    } cout<<endl;
}

main()
{
    FAST;

    int n,m; cin>>n>>m;
    fff(i,1,n) cin>>a[i];
    fff(i,1,n) pre[i]=pre[i-1]+a[i];

    while (k<=n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];

    bool cur=0;
    fff(j,1,m)
    {
        cur=!cur;
        if (n>1000)
        {
            ff(i,1,2*k) len[i].clear(),presek[i].clear();
            fff(i,1,n) len[i+k].pb({{pre[i],dp[i][!cur]-pre[i]*pre[i]},i}),presek[i+k].pb({-1e18});
            bff(i,1,k) merge(i);

            //ispisi();

            fff(i,2,n)
            {
                pli tmp=qry(1,1,i-1,pre[i]);
                dp[i][cur]=tmp.xx,gde[i][j]=tmp.yy;
            }
        }
        else
        {
            fff(i,2,n) ff(g,1,i)
            {
                li sta=dp[g][!cur]+cost(g+1,i);
                if (sta>=dp[i][cur]) dp[i][cur]=sta,gde[i][j]=g;
            }
        }
    }

    /*fff(j,1,m)
    {
        fff(i,1,n) cout<<dp[i][j]<<" ";
        cout<<endl;
    } cout<<endl;*/

    cout<<dp[n][cur]<<"\n";
    rekurz(n,m);

    /*int n; cin>>n;
    while (k<n) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,0,n)
    {
        int nn,kk; cin>>nn>>kk;
        len[i+k].pb({nn,kk});
        presek[i+k].pb({-1e18});
    }
    bff(i,1,k) merge(i);

    ispisi();

    while (true)
    {
        int ll,rr,x; cin>>ll>>rr>>x; ll--,rr--;
        cout<<qry(1,ll,rr,x)<<endl;
    }*/
}

//Note to self: Check for overflow

/*

7 3
4 1 3 4 0 2 3

7 6
4 1 3 4 0 2 3

4
-1 0
1 0
0 1
0 2

*/

Compilation message (stderr)

sequence.cpp: In function 'void merge(li)':
sequence.cpp:83:15: warning: comparison of integer expressions of different signedness: 'li' {aka 'long long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         if (aa==presek[2*i].size())
      |             ~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:85:19: warning: comparison of integer expressions of different signedness: 'li' {aka 'long long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             if (bb==presek[2*i+1].size()) break;
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:88:20: warning: comparison of integer expressions of different signedness: 'li' {aka 'long long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         else if (bb==presek[2*i+1].size()) gde=0;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'void ispisi()':
sequence.cpp:12:37: warning: comparison of integer expressions of different signedness: 'li' {aka 'long long int'} and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define ff(i,a,b) for (int i = a; i < b; i++)
......
  114 |             ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
      |                ~~~~~~~~~~~~~~~~~~~~  
sequence.cpp:114:13: note: in expansion of macro 'ff'
  114 |             ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
      |             ^~
sequence.cpp: At global scope:
sequence.cpp:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main()
      | ^~~~

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