제출 #897544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897544		duckindog	수열 (APIO14_sequence)	C++14	50 / 100	2043 ms	33500 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];

void tracer(int i, int j) {
  int mid = trace[i][j];
  if (mid - 1 == 0) return;
  tracer(mid - 1, j - 1);
  cout << mid - 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);

  for (int i = 0; i <= n; ++i) f[i][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= min(i, k + 1); ++j) {
      int &ret = f[i][j];
      for (int t = 1; t <= i; ++t) {
        int val = (d[i] - d[t - 1]) * (d[n] - d[i]) + f[t - 1][j - 1];
        if (ret < val) {
          ret = val;
          trace[i][j] = t;

        }
      }
    }
  }

  cout << f[n][k + 1] << '\n';
  tracer(n, k + 1);


}

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

sequence.cpp: In function 'int32_t main()':
sequence.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     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