Submission #37552

#	Time	Username	Problem	Language	Result	Execution time	Memory
37552		mirbek01	Split the sequence (APIO14_sequence)	C++14	0 / 100	0 ms	1840 KiB

sequence

# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const int inf = 1e9 + 7;
const int N = 1e5 + 5;

typedef long long ll;

int n, k, p[N][201], pref[N];
ll dp[N][201];
vector <int> ans;

ll get(int l, int r)
{
      return pref[l] * (pref[r] - pref[l]);
}

void dv(int k, int l, int r, int opl, int opr)
{
      if(l > r) return ;

      int md = (l + r) >> 1;

      for(int i = opl; i <= min(md - 1, opr); i ++)
      {
            int now = dp[i][k - 1] + get(i, md);
            if(dp[md][k] < now)
            {
                  dp[md][k] = now;
                  p[md][k] = i;
            }
      }

      dv(k, l, md - 1, opl, p[md][k]);
      dv(k, md + 1, r, p[md][k], opr);
}

int main()
{
      cin >> n >> k;

      for(int i = 1; i <= n; i ++)
      {
            cin >> pref[i];
            pref[i] += pref[i - 1];
      }

      for(int i = 1; i <= k; i ++)
            dv(i, i, n, i, n);

      cout << dp[n][k] << endl;

      for(int i = k; i >= 1; i --)
      {
            cout << p[n][i] << " ";
            n = p[n][i];
      }
}

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