oj.uz

답안 #335362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335362 2020-12-12T05:05:04 Z vkgainz 수열 (APIO14_sequence) C++17
0 / 100
 31 ms 6220 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;
    q.push_back(0);
    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[0], q[1])<s[i])
        q.pop_front();
      int j = q.front();
      if(!found) {
        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, q[q.size()-1], i))
        q.pop_back();
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 384 KB contestant found the optimal answer: 999 == 999
3 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Integer -1 violates the range [1, 199]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Integer -1 violates the range [1, 999]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1004 KB contestant didn't find the optimal answer: 1187850 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 6220 KB contestant didn't find the optimal answer: 5054352 < 19795776960
2 Halted 0 ms 0 KB -