Submission #37576

#	Time	Username	Problem	Language	Result	Execution time	Memory
37576		mirbek01	Split the sequence (APIO14_sequence)	C++14	100 / 100	1166 ms	82880 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[201][N];
ll pref[N];
ll dp[2][N];

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, kk = 1 - (k % 2);
      p[k][md] = opl;
      for(int i = opl; i <= min(md - 1, opr); i ++)
      {
            ll now = dp[kk][i] + get(i, md);
            if(dp[k % 2][md] <= now)
            {
                  dp[k % 2][md] = now;
                  p[k][md] = i;
            }
      }

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

int main()
{
      scanf("%d %d", &n, &k);

      for(int i = 1; i <= n; i ++)
      {
            scanf("%lld", &pref[i]);
            pref[i] += pref[i - 1];
      }

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

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

      for(int i = k; i >= 1; i --)
      {
            printf("%d ", p[i][n]);
            n = p[i][n];
      }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:46:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &k);
                             ^
sequence.cpp:50:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &pref[i]);
                                    ^

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