Submission #37563

#	Time	Username	Problem	Language	Result	Execution time	Memory
37563		mirbek01	Split the sequence (APIO14_sequence)	C++14	0 / 100	116 ms	82488 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[2][N];

ll get(int l, int r)
{
      return pref[l] * 1ll * (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[md][k] = 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[md][k] = i;
            }
      }

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

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

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

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

      printf("%d\n", dp[k & 1][n]);

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

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:56:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
       printf("%d\n", dp[k & 1][n]);
                                  ^
sequence.cpp:45: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:49:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &pref[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