제출 #744922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744922		zeta7532	수열 (APIO14_sequence)	C++17	0 / 100	38 ms	2380 KiB

sequence

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    vector<ll> sum(N+1);
    sum[0]=0;
    rep(i,N) sum[i+1]=sum[i]+A[i];
    ll ans=0;
    set<ll> s;
    s.insert(0);
    s.insert(N);
    rep(i,K){
        ll cnt1=0,cnt2=-1;
        auto itl=s.begin();
        auto itr=s.begin();
        itr++;
        while(itr!=s.end()){
            for(ll j=*itl+1;j<*itr;j++){
                if(cnt1<(sum[j]-sum[*itl])*(sum[*itr]-sum[j])){
                    cnt1=(sum[j]-sum[*itl])*(sum[*itr]-sum[j]);
                    cnt2=j;
                }
            }
            itl++;
            itr++;
        }
        ans+=cnt1;
        s.insert(cnt2);
    }
    cout << ans << endl;
    s.erase(0);
    s.erase(N);
    auto it=s.begin();
    while(it!=s.end()){
        cout << *it << " ";
        it++;
    }
    cout << endl;
    return 0;
}

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