Submission #766520

#	Time	Username	Problem	Language	Result	Execution time	Memory
766520		Andrei_Calota	Split the sequence (APIO14_sequence)	C++14	100 / 100	857 ms	83116 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

const int N_MAX = 1e5;

struct defLine {
    int64 slope, h; int index;
    int64 getEval (int64 t) {return slope * t + h;}
    long double intersectX (defLine aux) {return (long double)(aux.h - h) / (slope - aux.slope);}
    bool getIn (defLine first, defLine second) {return first.intersectX ({slope, h}) <= first.intersectX (second);}
};

deque<defLine> CHT;
void push (defLine newLine) {
   while (CHT.size () >= 2 && newLine.getIn (CHT[CHT.size () - 2], CHT[CHT.size () - 1]))
      CHT.pop_back ();
   CHT.push_back (newLine);
}

const int NONE = -1;
const int64 INF = 1e18;
defLine query (int64 target) {
   if (CHT.size () == 0)
     return {0, -INF, NONE};
   while (CHT.size () >= 2 && CHT[0].getEval (target) <= CHT[1].getEval (target))
      CHT.pop_front ();
   return CHT[0];
}


int n, k; int64 input[1 + N_MAX], pSum[1 + N_MAX];
void initInput (void) {
   cin >> n >> k;
   for (int i = 1; i <= n; i ++)
      cin >> input[i];
   for (int i = 1; i <= n; i ++)
      pSum[i] = pSum[i - 1] + input[i];
}

const int K_MAX = 200;
int pointTo[1 + K_MAX][1 + N_MAX];

int64 DP[1 + N_MAX], prevDP[1 + N_MAX];
void solve (void) {

   for (int t = 1; t <= k; t ++) {
      for (int i = 1; i <= t; i ++) {
         DP[i] = -INF;
         defLine line = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
         push (line);
      }
      for (int i = t + 1; i <= n; i ++) {

         defLine bestLine = query (pSum[i]);
         pointTo[t][i] = bestLine.index;
         DP[i] = bestLine.getEval (pSum[i]);

         ///if (t == 1 && i == 3)
          /// cout << DP[i] << "\n";

         defLine newLine = {pSum[i], prevDP[i] - pSum[i] * pSum[i], i};
         push (newLine);
      }
      CHT.clear ();
      for (int i = 1; i <= n; i ++)
         prevDP[i] = DP[i];
   }
   cout << DP[n] << "\n";

   int t = k, p = n;
   while (t > 0) {
      cout << pointTo[t][p] << " ";
      p = pointTo[t][p], t --;
   }
}

int main()
{
   initInput ();
   solve ();
    return 0;
}

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