제출 #897538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897538		duckindog	수열 (APIO14_sequence)	C++14	50 / 100	2062 ms	33516 KiB

sequence

// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e4 + 10;
int n, k;
int a[N], d[N];
int f[N][210], trace[N][210];

int dp(int i, int j) {
  if (j > n - i + 1) return -2e9;
  if (j == 1) return 0;
  int &ret = f[i][j];
  if (ret > -1) return ret;
  for (int x = i; x < n; ++x) {
    int val = (d[x] - d[i - 1]) * (d[n] - d[x]) + dp(x + 1, j - 1);
    if (ret < val) {
      ret = val;
      trace[i][j] = x;
    }
  }
  return ret;
}
void tracer(int i, int j) {
  int mid = trace[i][j];
  if (!mid) return;
  cout << mid << ' ';
  tracer(mid + 1, j - 1);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i], d[i] = d[i - 1] + a[i];
  memset(f, -1, sizeof f);
  cout << dp(1, k + 1) << '\n';
  tracer(1, k + 1);


}

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

sequence.cpp: In function 'int32_t main()':
sequence.cpp:38:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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