Submission #1173641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173641		ivaziva	Split the sequence (APIO14_sequence)	C++20	71 / 100	2097 ms	54884 KiB

sequence

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001
#define MAXM 201
#define int long long
const int MIN=-1e9,MAX=1e9;

struct Node {
    pair<int,int> line;
    Node *left, *right;
    bool active;
    Node():line({0,-LLONG_MAX}),left(nullptr),right(nullptr),active(false){}
};

class LiChaoTree {
private:
    Node* root;
    int minX,maxX;
    int get(int x,pair<int,int> line) {return line.first*x+line.second;}
    void update(Node*& node,int l,int r,pair<int,int> line)
    {
        if (!node) node=new Node();
        if (!node->active) {node->active=true;node->line=line;return;}
        int mid=(l+r)/2;
        bool leftBetter=get(l,line)>get(l,node->line);
        bool midBetter=get(mid,line)>get(mid,node->line);
        if (midBetter) swap(node->line,line);
        if (l==r) return;
        if (leftBetter!=midBetter) update(node->left,l,mid,line);
        else update(node->right,mid+1,r,line);
    }
    pair<int,int> query(Node* node,int l,int r,int x)
    {
        if (!node or !node->active) return {0,-LLONG_MAX};
        int mid=(l+r)/2;pair<int,int> bestLine=node->line;
        if (x<=mid)
        {
            pair<int,int> leftLine=query(node->left,l,mid,x);
            if (get(x,leftLine)>get(x,bestLine)) bestLine=leftLine;
        }
        else
        {
            pair<int,int> rightLine=query(node->right,mid+1,r,x);
            if (get(x,rightLine)>get(x,bestLine)) bestLine=rightLine;
        }
        return bestLine;
    }
    void clear(Node* &node)
    {
        if (!node) return;
        clear(node->left);clear(node->right);delete node;node=nullptr;
    }
public:
    LiChaoTree(int minX,int maxX):root(nullptr),minX(minX),maxX(maxX){}
    void addLine(pair<int,int> line) {update(root,minX,maxX,line);}
    pair<int,int> getMax(int x) {return query(root,minX,maxX,x);}
    void clear(){clear(root);root=nullptr;}
};

int n,k;
int pref[MAXN],dp[2][MAXN],where[MAXM][MAXN];
map<pair<int,int>,int> mapa;
LiChaoTree tree(MIN,MAX);
vector<int> ans;

int eval(pair<int,int> linija,int x){return (long long)(linija.first*x)+linija.second;}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);cin>>n>>k;pref[0]=0;
    for (int i=1;i<=n;i++) {cin>>pref[i];pref[i]+=pref[i-1];}
    for (int i=1;i<n;i++) dp[0][i]=(long long)(pref[i]*(pref[n]-pref[i]));
    for (int br=2;br<=k;br++)
    {
        for (int pos=br;pos<n;pos++)
        {
            tree.addLine({pref[pos-1],dp[0][pos-1]-(long long)(pref[pos-1]*pref[n])});
            mapa[{pref[pos-1],dp[0][pos-1]-(long long)(pref[pos-1]*pref[n])}]=pos-1;
            pair<int,int> resenje=tree.getMax(pref[pos]);dp[1][pos]=(long long)(pref[pos]*(pref[n]-pref[pos]))+eval(resenje,pref[pos]);
            where[br][pos]=mapa[resenje];
        }
        for (int pos=br;pos<n;pos++) dp[0][pos]=dp[1][pos];
        tree.clear();mapa.clear();
    }
    int maks=dp[0][k],pos=k;
    for (int i=k+1;i<n;i++)
    {
        if (dp[0][i]>maks) {maks=dp[0][i];pos=i;}
    }
    cout<<maks<<endl;ans.push_back(pos);
    for (int i=k;i>=2;i--) {ans.push_back(where[i][pos]);pos=where[i][pos];}
    for (int pos=ans.size()-1;pos>=0;pos--) cout<<ans[pos]<<" ";
    cout<<endl;return 0;
}

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