Submission #146153

#	Time	Username	Problem	Language	Result	Execution time	Memory
146153		mat_v	Split the sequence (APIO14_sequence)	C++14	28 / 100	2029 ms	65788 KiB

sequence

#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 100005

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

int n,k;
ll niz[maxn];
int smer = 0;
ll dp1[maxn][300];
bool bio1[maxn][300];
int koji1[maxn][300];
ll resi1(int x, int y){
    if(bio1[x][y])return dp1[x][y];
    if(y >= x)return -1e9;
    if(y == 0)return 0;
    ll sum = 0;
    ll tmp = 0;
    ll celsum = 0;
    int de = 0;
    for(int i=1; i<=x; i++)celsum  += niz[i];
    for(int i=1; i<=x-1; i++){
        sum += niz[i];
        if(sum * (celsum - sum) + resi1(i,y-1) > tmp)de = i;
        tmp = max(tmp, sum * (celsum - sum) + resi1(i,y-1));

    }
    bio1[x][y] = 1;
    koji1[x][y] = de;
    return dp1[x][y] = tmp;
}

ll dp2[maxn][300];
bool bio2[maxn][300];
int koji2[maxn][300];
ll resi2(int x, int y){
    if(bio2[x][y])return dp2[x][y];
    if(y == 0)return 0;
    int kolko = n-x+1;
    if(y >= kolko)return -1e9;
    ll sum = 0,tmp = 0, celsum = 0;
    int koji = 0;
    int de = 0;
    for(int i=x; i<=n; i++)celsum += niz[i];
    for(int i=x; i<=n-1; i++){
        sum += niz[i];
        if(sum * (celsum - sum) + resi2(i+1,y-1))de = i;
        tmp = max(tmp, sum * (celsum - sum) + resi2(i+1,y-1));
        //if(x == 1)cout << i << " " << " " << resi2(i+1,y-1) << endl;
    }
    bio2[x][y] = 1;
    koji2[x][y] = de;
    return dp2[x][y] = tmp;
}
vector<int>prvi;
vector<int>drugi;
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    ff(i,1,n)cin >> niz[i];
    ll pom = resi1(n,k);
    ll pom2 = resi2(1,k);
    //cout << pom << " " << pom2 << endl;
    int p = koji1[n][k];
    int d = koji2[1][k];
    int k1 = k-1;
    int k2 = k-1;

    int br = 1;
    int br2 = 1;
    prvi.pb(p);
    drugi.pb(d);
    while(br < k){
        p = koji1[p][k1];
        d = koji2[d][k1];
        k1--;
        br++;
        prvi.pb(p);
        drugi.pb(d);
    }
    cout << pom << endl;
    for(auto c:prvi)cout << c << " ";
    //cout << endl;
    //for(auto c:drugi)cout << c << " ";
    return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'll resi2(int, int)':
sequence.cpp:62:9: warning: unused variable 'koji' [-Wunused-variable]
     int koji = 0;
         ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:83:8: warning: unused variable 'pom2' [-Wunused-variable]
     ll pom2 = resi2(1,k);
        ^~~~
sequence.cpp:88:9: warning: unused variable 'k2' [-Wunused-variable]
     int k2 = k-1;
         ^~
sequence.cpp:91:9: warning: unused variable 'br2' [-Wunused-variable]
     int br2 = 1;
         ^~~

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