제출 #651473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651473		pauloamed	수열 (APIO14_sequence)	C++14	컴파일 에러	0 ms	0 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 100010;

int S[MAXN], wS[MAXN];

int query(int l, int r){
  int a = S[r];
  int b = S[r] - ((l == 0)? 0 : S[l - 1]);
  int c = wS[r] - ((l == 0)? 0 : wS[l - 1]);
  return a * b - c;
}

int last_dp[MAXN];
int curr_dp[MAXN];

const int MAXK = 250;
pair<int,int> ans[MAXN][MAXK];

int get_dp(int i){
  if(i < 0) return 0;
  else return last_dp[i];
}

int K;
void solve(int l, int r, int searchL, int searchR){
  if(l > r) return;
  int j = (l + r) / 2;
  if(curr_dp[j] == -1){
    int validR = min(j, searchR);
    pair<int,int> best = {LLONG_MAX, -1LL};
    for(int k = searchL; k <= validR; ++k){
      best = min(best, {query(k, j) + get_dp(k - 1), k});
    }
    curr_dp[j] = best.first;
    ans[j][K] = best;
    solve(l, j - 1, searchL, best.second);
    solve(j + 1, r, best.second, searchR);
  }
}

int32_t main(){
  int n, k; cin >> n >> k;
  vector<int> v(n); for(auto &x : v) cin >> x;

  int tot = 0;
  for(int i = 0; i < n; ++i){
    S[i] = v[i];
    if(i){
      S[i] += S[i - 1];
      tot += v[i] * S[i - 1];
    }
  }

  for(int i = 0; i < n; ++i){
    wS[i] = S[i] * v[i];
    if(i) wS[i] += wS[i - 1];
  }

  for(int i = 0; i < n; ++i){
    last_dp[i] = query(0, i);
  }

  for(K = 0; K < k; ++K){
    memset(curr_dp, -1, sizeof curr_dp);
    solve(0, n - 1, 0, n - 1);
    swap(curr_dp, last_dp);
  }

  cout << tot - last_dp[n - 1] << "\n";
  // cout << tot << " " << last_dp[n - 1] << "\n";

  auto curr = make_pair(-1, n);
  for(int i = 0; i < k; ++i){
    if(curr.second - 1 < 0){
      for(int j = 0; j < k; i++){
        curr++;
      }
    }
    curr = ans[curr.second - 1][k - i - 1];
    cout << curr.second << " ";
  }
  cout << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int32_t main()':
sequence.cpp:80:13: error: no 'operator++(int)' declared for postfix '++' [-fpermissive]
   80 |         curr++;
      |         ~~~~^~