제출 #90092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90092		mra2322001	수열 (APIO14_sequence)	C++14	0 / 100	97 ms	132096 KiB

sequence

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, a[N], k, pos[N][202];
ll f[N][202], t[N];

void solve(int lo, int hi, int l, int r, int j){
    if(lo > hi) return ;
    int mid = (lo + hi) >> 1;
    int x = min(mid - 1, r);
    for(x; x >= l; x--){
        if(x <= j - 1) break;
        ll cur = f[x][j - 1] + (t[mid] - t[x])*1ll*(t[n] - t[mid]);
        f[mid][j] = max(f[mid][j], cur);
        if(f[mid][j]==cur){
            pos[mid][j] = x;
        }
    }
    solve(lo, mid - 1, l, pos[mid][j], j);
    solve(mid + 1, r, pos[mid][j], r, j);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    f1(i, n) cin >> a[i];
    f1(i, n) t[i] = t[i - 1] + a[i];

    f1(i, n) f[i][0] = (t[i])*1ll*(t[n] - t[i]);
    f1(i, k){
        solve(i + 1, n, i, n, i);
    }
    /*f1(i, n){
        f[i][0] = (t[i])*1ll*(t[n] - t[i]);
        for(int j = 1; j < i; j++){
            if(j > k) break;
            for(int x = i - 1; x >= 1; x--){
                /// f[x][j - 1]
                if(x > j - 1){
                    ll cur = f[x][j - 1] + (t[i] - t[x])*(t[n] - t[i]);
                    f[i][j] = max(f[i][j], cur);
                    if(cur == f[i][j]){
                        pos[i][j] = x;
                    }
                }
                else break;
            }
        }
    }*/
    cout << f[n][k] << endl;
    int now = pos[n][k];
    while(k--){
        cout << now << " ";
        now = pos[now][k];
    }
}

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

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:16:10: warning: statement has no effect [-Wunused-value]
     for(x; x >= l; x--){
          ^

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