Submission #855412

#	Time	Username	Problem	Language	Result	Execution time	Memory
855412		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	368 ms	9440 KiB

sequence

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,mid
#define TR v+v+1,mid+1,tr

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

int rnd() {
    int x = rand() << 15;
    return rand() ^ x;
}

struct target {
    int l,r,x,y,ans;
};

bool cmp(target a, target b) {
    if (a.l==b.l)
        return a.r<b.r;
    return a.l<b.l;
}

const ll INF = 1e18+9;
const int N =  2e5+7;
const int M = 1e9+7;
const ll HZ = 1e5;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

int n,a[N],ps[N];

pair <int,vector <int>> get(set <int> v1,set <int> v2,int ansum, vector <int> ans, bool u[N], int k) {
    if (!k)
        return {ansum,ans};
    int mx = -INF, pos, pos1 = -1;
    for (int j = 1; j < n; j++) {
        if (u[j])
            continue;
        auto f = v1.upper_bound(j);
        f--;
        int z = *v2.lower_bound(j + 1), x = *f;
        if (z == j or x == j)
            continue;
        if (mx < (ps[j] - ps[x]) * (ps[z - 1] - ps[j])) {
            mx = (ps[j] - ps[x]) * (ps[z - 1] - ps[j]);
            pos = j;
            pos1 = -1;
        } else if (mx == (ps[j] - ps[x]) * (ps[z - 1] - ps[j]))
            pos1 = j;
    }
    if (pos1 == -1) {
        u[pos] = true;
        v1.insert(pos), v2.insert(pos + 1);
        ansum += mx;
        ans.push_back(pos);
        return get(v1,v2,ansum,ans,u,k-1);
    } else {
        u[pos] = true;
        v1.insert(pos), v2.insert(pos + 1);
        ansum += mx;
        ans.push_back(pos);
        pair <int,vector <int>> z1,z2;
        z1=get(v1,v2,ansum,ans,u,k-1);
        ans.pop_back();
        v1.erase(pos), v2.erase(pos+1);
        u[pos]=false;
        u[pos1] = true;
        v1.insert(pos1), v2.insert(pos1 + 1);
        ans.push_back(pos1);
        z2=get(v1,v2,ansum,ans,u,k-1);
        if (z1.first>=z2.first)
            return z1;
        else
            return z2;
    }
}

int k;
bool u[N];

void solve() {
    cin >> n >> k;
    for (int i=1;i<=n;i++)
        cin >> a[i],ps[i]=ps[i-1]+a[i];
    pair <int,vector <int>> anz=get({0},{n+1},0,{},u,k);
    int ansum=anz.first;
    vector <int> ans=anz.second;
    cout << ansum << '\n';
    for (auto now : ans)
        cout << now << ' ';
}

signed main() {
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1,count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ": ";
        solve();
        if (test)
            cout << '\n';
        count++;
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, std::vector<long long int> > get(std::set<long long int>, std::set<long long int>, long long int, std::vector<long long int>, bool*, long long int)':
sequence.cpp:76:11: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |         u[pos] = true;
      |           ^~~

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