Submission #568958

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

sequence

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#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 erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#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)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

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;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

int a[100005];
li dp[100005][202];
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(1,gde[n][k])<<" ";
}

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

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

void try_add(int i, pair<pii,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;
}

int 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];

    fff(j,1,m)
    {
        ff(i,1,2*k) len[i].clear(),presek[i].clear();
        fff(i,1,n) len[i+k].pb({{pre[i],dp[i][j-1]-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][j]=tmp.xx,gde[i][j]=tmp.yy;
        }

        /*fff(i,2,n) ff(g,1,i)
        {
            li sta=dp[g][j-1]+cost(g+1,i);
            if (sta>=dp[i][j]) dp[i][j]=sta,gde[i][j]=g;
        }*/
    }

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

    cout<<dp[n][m]<<"\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(int)':
sequence.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (aa==presek[2*i].size())
      |             ~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if (bb==presek[2*i+1].size()) break;
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         else if (bb==presek[2*i+1].size()) gde=0;
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'void ispisi()':
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:120:9: note: in expansion of macro 'ff'
  120 |         ff(i,kk,2*kk)
      |         ^~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:122:13: note: in expansion of macro 'ff'
  122 |             ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
      |             ^~
sequence.cpp:16:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                                       ~~~~^~~~~
sequence.cpp:122:13: note: in expansion of macro 'ff'
  122 |             ff(j,0,presek[i].size()) cout<<"("<<presek[i][j]<<"; "<<len[i][j].xx.xx<<","<<len[i][j].xx.yy<<") ";
      |             ^~
sequence.cpp: In function 'int main()':
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:133:5: note: in expansion of macro 'fff'
  133 |     fff(i,1,n) cin>>a[i];
      |     ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:134:5: note: in expansion of macro 'fff'
  134 |     fff(i,1,n) pre[i]=pre[i-1]+a[i];
      |     ^~~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:137:5: note: in expansion of macro 'ff'
  137 |     ff(i,0,k) l[i+k]=i,r[i+k]=i;
      |     ^~
sequence.cpp:18:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
      |                             ^
sequence.cpp:138:5: note: in expansion of macro 'bff'
  138 |     bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
      |     ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:140:5: note: in expansion of macro 'fff'
  140 |     fff(j,1,m)
      |     ^~~
sequence.cpp:16:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   16 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
sequence.cpp:142:9: note: in expansion of macro 'ff'
  142 |         ff(i,1,2*k) len[i].clear(),presek[i].clear();
      |         ^~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:143:9: note: in expansion of macro 'fff'
  143 |         fff(i,1,n) len[i+k].pb({{pre[i],dp[i][j-1]-pre[i]*pre[i]},i}),presek[i+k].pb({-1e18});
      |         ^~~
sequence.cpp:18:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
      |                             ^
sequence.cpp:144:9: note: in expansion of macro 'bff'
  144 |         bff(i,1,k) merge(i);
      |         ^~~
sequence.cpp:17:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
sequence.cpp:148:9: note: in expansion of macro 'fff'
  148 |         fff(i,2,n)
      |         ^~~

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