oj.uz

답안 #130241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130241 2019-07-14T11:12:52 Z spookywooky 수열 (APIO14_sequence) C++14
0 / 100
 2000 ms 63284 KB 
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 *
 *  https://oj.uz/problem/view/APIO14_sequence
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fori(n) for(ll i=0; i<(n); i++)

typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
    int n, K;
    cin>>n>>K;
    vi a(n);
    vll pra(n+1);

    fori(n) {
        cin>>a[i];
        pra[i+1]=pra[i]+a[i];
    }

    typedef tuple<int, int, int> ti3;
    typedef pair<ll, vi> pllvi;
    map<ti3, pllvi> dp;
/* dp[(i, j, k)]= largest number (and sequence of indexes) you can get with seq
 * starting at i, of len j, with k recursions. j>k
 */

    function<ll(int, int)> sum=[&](int i, int j) {
        return pra[i+j]-pra[i];
    };
    function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
        assert(j>k);
        if(k==0) {
            vi empty;
            pllvi ret= { sum(i, j), empty };
            return ret;
        }

        auto it=dp.find({i,j,k});
        if(it!=dp.end())
            return it->second;

        if(k==1) {
            ll lans=0;
            int ansIdx=-1;
            for(int l=1; l<j; l++)  {
                ll val=sum(i, l)*sum(i+l, j-l);
                if(val>=lans) {
                    lans=val;
                    ansIdx=i+l;
                }
            }

            pllvi ans={ lans, vi({ ansIdx })};
            dp[{i,j,k}]=ans;
            return ans;
        }

        // k== k1 + k2 + 1
        pllvi ans;
        for(int k1=0, k2=k-1; k1<k; k1++, k2--) {
            /* parts must be at least size of kx+1 */
            for(int l=k1+1; j-l>k2; l++) {
                ll points=sum(i,l)*sum(i+l, j-l);
                pllvi valL=calc(i, l, k1);
                pllvi valR=calc(i+l, j-l, k2);
                ll lsum=valL.first+valR.first+points;
                if(lsum>=ans.first) {
                    vi path(valL.second);
                    for(int idx : valR.second)
                        path.push_back(idx);
                    path.push_back(i+l);
                    ans={ lsum, path };
                }
            }
        }
        dp[{i,j,k}]=ans;
        return ans;
    };
    auto ans=calc(0, n, K);
    cout<<ans.first<<endl;
    for(auto idx : ans.second)
        cout<<idx<<" ";
    cout<<endl;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB declared answer doesn't correspond to the split scheme: declared = 117, real = 108
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB declared answer doesn't correspond to the split scheme: declared = 1103994, real = 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 2808 KB declared answer doesn't correspond to the split scheme: declared = 610610353, real = 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

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