oj.uz

Submission #335363

# Submission time Handle Problem Language Result Execution time Memory
335363 2020-12-12T05:24:29 Z vkgainz Split the sequence (APIO14_sequence) C++17
0 / 100
 31 ms 6240 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
ll s[100001];
ll dp[201][100001];
int par[201][100001];
double slope(int p, int x, int y) { // x > y 
  return (double) (dp[p-1][y] - dp[p-1][x] - s[y] * s[y] + s[x] * s[x]) / (s[x] - s[y]);
}

int main() {
  int n, k; cin >> n >> k;
  s[0] = 0;
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    s[i] += s[i-1];
  }
  dp[0][0] = -1e15;
  par[0][0] = -1;
  for(int i=1;i<=n;i++) {
    dp[0][i] = 0;
    par[0][i] = -1;
  }
  for(int p=1;p<=k;p++) {
    deque<int> q;
    dp[p][0] = -1e15;
    for(int i=1;i<=n;i++) {
      bool found = false;
      if(i<=p) {
        dp[p][i] = -1e15;
        par[p][i] = -1;
        found = true;
      }
      while(q.size()>1 && slope(p, q[1], q[0])<s[i])
        q.pop_front();
      if(!found) {
        int j = q.front();
        dp[p][i] = dp[p-1][j]+(s[i]-s[j])*1LL*s[j];
        par[p][i] = j;
      }
      while(q.size()>1&&slope(p, q[q.size()-1], q[q.size()-2])>slope(p, i, q[q.size()-1]))
        q.pop_back();
      if(i>=p)
        q.push_back(i);
    }
  }
  vector<int> ans;
  int curr =n;
  for(int p=k;p>=1;p--) {
    ans.push_back(par[p][curr]);
    curr = par[p][curr];
  }
  cout << dp[k][n] << "\n";
  for(auto &a : ans) cout << a << " ";
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 364 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 364 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 492 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Incorrect 1 ms 364 KB contestant didn't find the optimal answer: 0 < 1
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB contestant didn't find the optimal answer: 252308 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB contestant didn't find the optimal answer: 484133 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB contestant didn't find the optimal answer: 395622 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 880 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6240 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -