oj.uz

답안 #286503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286503 2020-08-30T13:49:15 Z BeanZ 수열 (APIO14_sequence) C++14
0 / 100
 352 ms 131076 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'

const int N = 1e5 + 5;
ll dp[N][2];
ll opt[N][205];
ll a[N];
void DP(ll k, ll l, ll r, ll optl, ll optr){
        cout << l << " " << r << endl;
        if (l > r) return;
        ll mid = (l + r) >> 1;
        dp[mid][1] = -1e18;
        ll best = optl;
        for (int i = optl; i <= min(r - 1, optr); i++){
                if (dp[mid][1] < (dp[i][0] + a[i] * (a[mid] - a[i]))){
                        dp[mid][1] = dp[i][0] + a[i] * (a[mid] - a[i]);
                        opt[mid][k] = i;
                }
        }
        DP(k, l, mid, optl, best);
        DP(k, mid + 1, r, best, optr);
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("VietCT.INP", "r")){
                freopen("VietCT.INP", "r", stdin);
                freopen("VietCT.OUT", "w", stdout);
        }
        ll n, k;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i], a[i] = a[i] + a[i - 1];
        for (int i = 1; i <= k; i++){
                DP(i, 1, n, 1, n);
                for (int j = 1; j <= n; j++){
                        dp[j][0] = dp[j][1];
                }
        }
        cout << dp[n][1] << endl;
        for (int i = k; i >= 1; i--){
                cout << opt[n][i] << " ";
                n = opt[n][i];
        }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:31:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |                 freopen("VietCT.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:32:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   32 |                 freopen("VietCT.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 332 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 336 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 333 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 336 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 352 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 339 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -