oj.uz

답안 #233985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233985 2020-05-22T15:32:55 Z rupav 수열 (APIO14_sequence) C++14
0 / 100
 2000 ms 8960 KB 
#include<bits/stdc++.h>
using namespace std;

#define watch(x) cout << (#x) << " is " << (x) << endl
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i, st, en) for(int i=st; i<=en; i++)
#define repn(i, st, en) for(int i=st; i>=en; i--)
#define sq(a) (a*a)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll mod = 1e9+7;

/// given an array of n integers, you have to maximize reward by doing k splits. Each split gives a reward of product of sums of left and right bounded subarray
vector<vector<ll>> dp;
vector<ll> a;
vector<ll> pref;

ll recurse(int st, int n, int k, ll psum){
    ll &z = dp[st][k];
    if(~z) return z;
    if(!k) return z = 0ll;
    ll p1, p2;
    z = 0ll;
    for(int i=st+1; i <= n - k; ++i){
        p1 = pref[i - 1] - psum;
        ll temp = recurse(i, n, k - 1, p1 + psum);
        p2 = pref[n - 1] - pref[i - 1];
        z = max(z, temp + p1*p2);
    }
    return z;
}

void solve(){
    int n, k;
    cin>>n>>k;
    a.resize(n);
    pref.resize(n, 0);
    ll sum = 0ll;
    fr(i, n) {
        cin>>a[i];
        sum += a[i];
        pref[i] = sum;
    }

    /// order of the splits doesn't matter, associativity property holds!
    dp.resize(n, vector<ll>(k + 1, -1));

    ll res = recurse(0, n, k, 0ll);
    cout<<res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll t = 1;
    //  cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 512 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 602 ms 1280 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2087 ms 8960 KB Time limit exceeded
2 Halted 0 ms 0 KB -