結果

問題 No.1117 数列分割
ユーザー face4
提出日時 2020-07-18 16:17:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 681 bytes
コンパイル時間 844 ms
コンパイル使用メモリ 73,728 KB
実行使用メモリ 111,616 KB
最終ジャッジ日時 2024-11-30 17:08:52
合計ジャッジ時間 48,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 8 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

// なんやかんやでO(N^2.5)になってくれないか
#include<iostream>
#include<vector>
using namespace std;

typedef long long ll;

int main(){
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> v(n+1, 0);
    for(int i = 1; i <= n; i++) cin >> v[i], v[i] += v[i-1];
    vector<vector<ll>> dp(n+1, vector<ll>(k+1, -1));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = (i+m-1)/m; j <= min(i, k-(n-i+m-1)/m); j++){
            for(int l = max(0, i-m); l < i; l++){ // 重い？
                if(dp[l][j-1] != -1)  dp[i][j] = max(dp[i][j], dp[l][j-1]+abs(v[i]-v[l]));
            } 
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}
0