Submission #41632

#	Time	Username	Problem	Language	Result	Execution time	Memory
41632		funcsr	Split the sequence (APIO14_sequence)	C++14	0 / 100	1 ms	388 KiB

sequence

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
#include <map>
using namespace std;
#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
#define MOD 1000000007
#define INF (1LL<<60)

int N, K;
int B[100001];
long long dp[100001][202];
int pre[100001][202];
signed main() {
  cin >> N >> K;
  K++;
  assert(K <= N);
  assert(K <= 201);
  assert(N<=200);
  rep(i, N) cin >> B[i+1];
  rep(i, N) B[i+1] += B[i];
  rep(i, N+1) rep(j, K+1) dp[i][j] = INF, pre[i][j] = -1;
  dp[0][0] = 0;
  for (int x=1; x<=N; x++) {
    rep(k, K) {
      rep(y, x) {
        if (dp[y][k] == INF) continue;
        long long v = 1LL*B[x]*B[x] + (dp[y][k] + 1LL*B[y]*B[y] - 2LL*B[x]*B[y]);
        if (dp[x][k+1] > v) {
          dp[x][k+1] = v;
          pre[x][k+1] = y;
        }
      }
    }
  }
  long long m = (1LL*B[N]*B[N]-dp[N][K])/2LL;
  cout << m << "\n";
  return 0;
  int p = pre[N][K], k = K-1;
  vector<int> seq;
  while (k > 0) {
    assert(p != -1);
    seq.pb(p);
    p = pre[p][k];
    k--;
  }
  assert(p == 0);
  assert(seq.size() == K-1);
  reverse(all(seq));
  for (int x : seq) cout << x << " "; cout << "\n";
  return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/5/cassert:43:0,
                 from sequence.cpp:5:
sequence.cpp: In function 'int main()':
sequence.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(seq.size() == K-1);
                     ^

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