oj.uz

Submission #130236

# Submission time Handle Problem Language Result Execution time Memory
130236 2019-07-14T10:56:16 Z spookywooky Split the sequence (APIO14_sequence) C++14
0 / 100
 2000 ms 42052 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);
        assert(k>0);
        //if(k==0)
        //    return 0LL;
        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;
        }

        pllvi ans;
        for(int k1=1; k1<k-1; k1++) {
            int k2=k-k1-1;
            /* 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Incorrect 2 ms 380 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 2 ms 376 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 11 ms 504 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 2 ms 376 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Incorrect 57 ms 1100 KB Unexpected end of file - int32 expected
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 2 ms 376 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1257 ms 7624 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 3 ms 376 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Execution timed out 2021 ms 5164 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 632 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 10 ms 604 KB contestant found the optimal answer: 140412195 == 140412195
3 Execution timed out 2053 ms 42052 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 3076 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 712 ms 3012 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2036 ms 12404 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 2492 KB Time limit exceeded
2 Halted 0 ms 0 KB -