Submission #1128006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128006		HuyAT	Split the sequence (APIO14_sequence)	C++17	100 / 100	996 ms	82956 KiB

sequence

#include<bits/stdc++.h>
#define newl '\n'

const int N = 1e5 + 10;
const int K = 2e2 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

struct Line{
    long long a,b,it;
    long long operator ()(long long x){
        return a * x + b;
    }
    long long intersect(const Line &rhs) const {
        if(a == rhs.a){
//            std::cout << -1;
            exit(0);
        }
        long long nume = b - rhs.b;
        long long denom = rhs.a - a;
        return nume / denom;
    }
};
long long a[N + 1],s[N + 1],n,k;
int trace[K + 1][N + 1];

void readData(){
    std::cin >> n >> k;
    for(int i = 1;i <= n;++i){
        std::cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
}

///(s[r] - s[l]) * (s[n] - s[r])
///(s[r] * s[n] - s[r] * s[r] - s[l] * s[n] + s[l] * s[r] + f[l]
///-s[r] * s[r] //meh not important
///s[r] * s[n] // also not important
///-s[l] * s[n] + s[l] * s[r] = -s[l] * s[n] + -s[l] * -s[r],-s[l] = a,(s[n] - s[r]) = x
///f[l] = b
void brute(){
    std::vector<long long> pr(n + 1,0);
    int it = 0;
    for(int i = 1;i <= k;++i){
        std::vector<long long> f(n + 1,0);
        for(int j = 1;j < n;++j){
            trace[i][j] = j - 1;
            for(int j1 = j - 1;j1 >= 0;--j1){
                long long t = (s[j] - s[j1]) * (s[n] - s[j]) + pr[j1];
                if(t > f[j]){
                    f[j] = t;
                    trace[i][j] = j1;
                }
                if(f[j] >= f[it]){
                    it = j;
                }
            }
//            if(i == 3 && j == 5){
//                std::cout << f[j] << newl;
//            }
        }
        pr.swap(f);
    }
    std::cout << pr[it] << newl;
    int t = k;
    while(t > 0){
        std::cout << it << " ";
        it = trace[t--][it];
    }
}
bool dominate(const Line &l,const Line &o,const Line &o1){
//    if(l.a == o.a && l.b == o.b){
//        return true;
//    }
    ///line lhs dominate line o
//    if(l.a == o.a){
//        return (l.b >= o.b);
//    }
    long long inter = l.intersect(o);
    long long inter1 = o.intersect(o1);
    return inter >= inter1;
}
void solve(){
    long long it = 0;
    std::deque<Line> dq;
    std::vector<long long> pr(n + 1,0);
    for(int i = 1;i <= k;++i){
        std::vector<long long> f(n + 1,0);
        for(int j = 0;j <= n;++j){
            if(j > 0 && j < n){
                long long x = s[n] - s[j];
                while((int)dq.size() >= 2 && dq.end()[-1](x) <= dq.end()[-2](x)){
                    dq.pop_back();
                }
                f[j] = dq.end()[-1](x) + s[j] * x;
                trace[i][j] = dq.end()[-1].it;
//                if(i == 3 && j == 5){
//                    std::cerr << "IMP " << f[j] << newl;
//                }
                if(f[j] >= f[it]){
                    it = j;
                }
                if(s[i] == s[j]){

                    assert(f[j] >= f[j - 1]);
                }
//                std::cout << f[j] << " ";
            }
            Line cur = {-s[j],pr[j],j};
            while((int)dq.size() > 0){
                if(cur.a == dq[0].a){
                    if(cur.b >= dq[0].b){
                        dq.pop_front();
                        continue;
                    }
                }else if((int)dq.size() > 1 && dominate(cur,dq[0],dq[1])){
                    dq.pop_front();
                    continue;
                }
                break;
            }
//            if((int)dq.size() > 0 && cur.a == dq[0].a){
//                assert(cur.b < dq[0].b);
//            }
            if((int)dq.size() == 0 || cur.a != dq[0].a){
                dq.push_front(cur);
            }
        }
        dq.clear();
        pr.swap(f);
    }
    std::cout << pr[it] << newl;
    int t = k;
    while(t > 0){
        std::cout << it << " ";
        it = trace[t--][it];
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    solve();
    return 0;
}

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