제출 #1101491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101491		HuyAT	수열 (APIO14_sequence)	C++14	22 / 100	316 ms	131072 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 {
        assert(a != rhs.a);
        long long nume = b - rhs.b;
        long long denom = rhs.a - a;
        return nume / denom;
    }
};
long long a[N + 1],f[K + 1][N + 1],trace[K + 1][N + 1],s[N + 1],n,k;

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
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 o3
    if(l.a == o.a){
        return (l.b >= o.b);
    }
    long long inter = l.intersect(o1);
    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){
                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;
//                }
            }
            Line cur = {-s[j],pr[j],j};
            while((int)dq.size() >= 2 && dominate(cur,dq[0],dq[1])){
                dq.pop_front();
            }
            dq.push_front(cur);
            if(f[j] >= f[it]){
                it = j;
            }
//            std::cerr << i << " " << j << newl;
        }
        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: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29