Submission #1276340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276340		jakekim0105	Split the sequence (APIO14_sequence)	C++17	100 / 100	361 ms	81564 KiB

sequence

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int getChar();
inline int readChar();
inline void readString(char* out);
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeString(const char* s);
constexpr int kInBufSize = 1 << 18;
constexpr int kOutBufSize = 1 << 8;

int opt[201][100001];
ll p[100001];
ll dp[2][100001];
int dq[100001];
int s, e, t;

void prt(int i, int j){
    if(i-1)prt(i-1, opt[i][j]);
    writeInt(opt[i][j], ' ');
}

int main(){
    int n = readInt(), k = readInt();
    for(int i = 1; i <= n; i++){
        p[i] = p[i-1] + readInt();
    }
    for(int i = 1; i <= k; i++, t = !t){
        s = e = 0;
        dq[0] = i-1;
        for(int j = i; j <= n; j++){
            while(s < e && p[j]*p[dq[s]]+dp[t][dq[s]]-p[dq[s]]*p[dq[s]] <= p[j]*p[dq[s+1]]+dp[t][dq[s+1]]-p[dq[s+1]]*p[dq[s+1]])s++;
            dp[!t][j] = p[j] * p[dq[s]] + dp[t][dq[s]] - p[dq[s]] * p[dq[s]];
            opt[i][j] = dq[s];
            while(s < e && (p[j]-p[dq[e-1]]) * (dp[t][dq[e]]-dp[t][j]+(p[j]-p[dq[e]])*p[dq[e]]) <= (p[j]-p[dq[e]]) * (dp[t][dq[e-1]]-dp[t][j]+(p[j]-p[dq[e-1]])*p[dq[e-1]]))e--;
            dq[++e] = j;
        }
    }
    writeInt(dp[t][n], '\n');
    prt(k, n);
}

/* FastIO */
// https://github.com/justiceHui/AlgorithmImplement/blob/master/misc/FastInput.cpp
inline int getChar() {
  static char buf[kInBufSize];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, kInBufSize, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
inline void readString(char* out) {
  int c = getChar();
  while (c <= 32) c = getChar();
  do {
    *(out++) = c;
    c = getChar();
  } while (c > 32);
  *out = 0;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[kOutBufSize];
inline void writeChar(int x) {
  if (write_pos == kOutBufSize)
    fwrite(write_buf, 1, kOutBufSize, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeString(const char* s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;

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