제출 #699308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699308		dattranxxx	수열 (APIO14_sequence)	C++11	22 / 100	231 ms	8636 KiB

sequence

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

const int N = 1e5 + 5;
const ll INF = 1e15;

int a[N]; ll f[N];
pair<ll, int> dp[200][N];

#define fi first
#define se second

int n, m;

void task1() {
  
  for (int k = 2; k <= m; ++k) {
    for (int i = 1; i <= n; ++i) {
      dp[k][i].fi = -INF;
      for (int j = i - 1; ~j; --j) {
        ll sum = dp[k - 1][j].fi + f[j] * (f[i] - f[j]);
        dp[k][i] = max(dp[k][i], make_pair(sum, j));
      }
    }
  }
  
  cout << dp[m][n].fi << '\n';
  vector<int> path;
  for (int j = m, i = dp[m][n].se; i; j--, i = dp[j][i].se) {
    path.emplace_back(i);
  }
  reverse(path.begin(), path.end());
  for (int i : path) cout << i << ' ';
  
}

struct Line {
  ll a, b;
  int i;
  Line(ll a, ll b, int i): a(a), b(b), i(i) {}
  ll get(int x) {
    return a * x + b;
  }
};

double inter(const Line& a, const Line& b) {
  // (a1-a2) * x = b2-b1
  // x = (b2 - b1) / (a1 - a2)
  return (a.b - b.b) / double(a.a - b.a);
}

deque<Line> dq;

void insert(ll a, ll b, int i) {
  Line l(a, b, i);
  while (dq.size() > 1 && inter(l, dq.back()) > inter(l, dq[dq.size() - 2])) {
    dq.pop_back();
  }
  dq.push_back(l);
}

pair<ll, int> get(int x) {
  while (dq.size() > 1 && dq[0].get(x) < dq[1].get(x)) {
    dq.pop_front();
  }
  return make_pair(dq[0].get(x), dq[0].i);
}


int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  
  cin >> n >> m; m++;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    f[i] = f[i - 1] + a[i];
  }
  
  if (n <= 1000) {
    task1();
    return 0;
  }
  
  for (int k = 2; k <= m; ++k) {
    
    dq.clear();
    
    for (int i = 1; i <= n; ++i) {
      
      insert(f[i - 1], dp[k - 1][i - 1].fi - f[i - 1] * f[i - 1], i - 1);
      // sum = f[j] * f[i] + dp[k - 1][j].fi - f[j] * f[j];
      auto sum = get(f[i]);
      dp[k][i] = max(dp[k][i], sum);
    }
  }
  
  cout << dp[m][n].fi << '\n';
  vector<int> path;
  for (int j = m, i = dp[m][n].se; i; j--, i = dp[j][i].se) {
    path.emplace_back(i);
  }
  reverse(path.begin(), path.end());
  for (int i : path) cout << i << ' ';
  
  
  
	return 0;
}

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