답안 #130232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130232	2019-07-14T10:54:24 Z	spookywooky	수열 (APIO14_sequence)	C++14	컴파일 오류	0 ms	0 KB

sequence

using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
    tree_order_statistics_node_update> indexed_set;

typedef long long ll;
//typedef __int128 lll;

#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;
}

Compilation message

sequence.cpp:1:17: error: '__gnu_pbds' is not a namespace-name
 using namespace __gnu_pbds;
                 ^~~~~~~~~~
sequence.cpp:1:27: error: expected namespace-name before ';' token
 using namespace __gnu_pbds;
                           ^
sequence.cpp:2:9: error: 'tree' does not name a type
 typedef tree<int,null_type,less<int>,rb_tree_tag,
         ^~~~
sequence.cpp:10:9: error: 'pair' does not name a type
 typedef pair<int, int> pii;
         ^~~~
sequence.cpp:11:9: error: 'vector' does not name a type
 typedef vector<bool> vb;
         ^~~~~~
sequence.cpp:12:9: error: 'vector' does not name a type
 typedef vector<int> vi;
         ^~~~~~
sequence.cpp:13:9: error: 'vector' does not name a type
 typedef vector<ll> vll;
         ^~~~~~
sequence.cpp:14:9: error: 'vector' does not name a type
 typedef vector<vi> vvi;
         ^~~~~~
sequence.cpp:15:9: error: 'vector' does not name a type
 typedef vector<vll> vvll;
         ^~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:18:1: error: 'cin' was not declared in this scope
 cin.tie(nullptr);
 ^~~
sequence.cpp:18:1: note: suggested alternative: 'main'
 cin.tie(nullptr);
 ^~~
 main
sequence.cpp:19:6: error: 'std::ios' has not been declared
 std::ios::sync_with_stdio(false);
      ^~~
sequence.cpp:22:5: error: 'vi' was not declared in this scope
     vi a(n);
     ^~
sequence.cpp:23:5: error: 'vll' was not declared in this scope
     vll pra(n+1);
     ^~~
sequence.cpp:23:5: note: suggested alternative: 'll'
     vll pra(n+1);
     ^~~
     ll
sequence.cpp:26:14: error: 'a' was not declared in this scope
         cin>>a[i];
              ^
sequence.cpp:27:9: error: 'pra' was not declared in this scope
         pra[i+1]=pra[i]+a[i];
         ^~~
sequence.cpp:30:13: error: 'tuple' does not name a type; did you mean 'double'?
     typedef tuple<int, int, int> ti3;
             ^~~~~
             double
sequence.cpp:31:13: error: 'pair' does not name a type; did you mean 'main'?
     typedef pair<ll, vi> pllvi;
             ^~~~
             main
sequence.cpp:32:5: error: 'map' was not declared in this scope
     map<ti3, pllvi> dp;
     ^~~
sequence.cpp:32:5: note: suggested alternative: 'main'
     map<ti3, pllvi> dp;
     ^~~
     main
sequence.cpp:32:9: error: 'ti3' was not declared in this scope
     map<ti3, pllvi> dp;
         ^~~
sequence.cpp:32:14: error: 'pllvi' was not declared in this scope
     map<ti3, pllvi> dp;
              ^~~~~
sequence.cpp:32:21: error: 'dp' was not declared in this scope
     map<ti3, pllvi> dp;
                     ^~
sequence.cpp:37:5: error: 'function' was not declared in this scope
     function<ll(int, int)> sum=[&](int i, int j) {
     ^~~~~~~~
sequence.cpp:37:5: note: suggested alternative: 'union'
     function<ll(int, int)> sum=[&](int i, int j) {
     ^~~~~~~~
     union
sequence.cpp:37:25: error: expression list treated as compound expression in functional cast [-fpermissive]
     function<ll(int, int)> sum=[&](int i, int j) {
                         ^
sequence.cpp:37:16: error: expected primary-expression before '(' token
     function<ll(int, int)> sum=[&](int i, int j) {
                ^
sequence.cpp:37:17: error: expected primary-expression before 'int'
     function<ll(int, int)> sum=[&](int i, int j) {
                 ^~~
sequence.cpp:37:22: error: expected primary-expression before 'int'
     function<ll(int, int)> sum=[&](int i, int j) {
                      ^~~
sequence.cpp:37:28: error: 'sum' was not declared in this scope
     function<ll(int, int)> sum=[&](int i, int j) {
                            ^~~
sequence.cpp:37:28: note: suggested alternative: 'enum'
     function<ll(int, int)> sum=[&](int i, int j) {
                            ^~~
                            enum
sequence.cpp: In lambda function:
sequence.cpp:38:16: error: 'pra' was not declared in this scope
         return pra[i+j]-pra[i];
                ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:41:20: error: expected primary-expression before 'int'
     function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
                    ^~~
sequence.cpp:41:25: error: expected primary-expression before 'int'
     function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
                         ^~~
sequence.cpp:41:30: error: expected primary-expression before 'int'
     function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
                              ^~~
sequence.cpp:41:36: error: 'calc' was not declared in this scope
     function<pllvi(int, int, int)> calc=[&](int i, int j, int k) {
                                    ^~~~
sequence.cpp: In lambda function:
sequence.cpp:42:9: error: 'assert' was not declared in this scope
         assert(j>k);
         ^~~~~~
sequence.cpp:42:9: note: suggested alternative: 'short'
         assert(j>k);
         ^~~~~~
         short
sequence.cpp:63:25: error: 'ans' was not declared in this scope
             dp[{i,j,k}]=ans;
                         ^~~
sequence.cpp:63:25: note: suggested alternative: 'lans'
             dp[{i,j,k}]=ans;
                         ^~~
                         lans
sequence.cpp:64:20: error: unable to deduce lambda return type from 'ans'
             return ans;
                    ^~~
sequence.cpp:75:25: error: 'valL' was not declared in this scope
                 ll lsum=valL.first+valR.first+points;
                         ^~~~
sequence.cpp:75:36: error: 'valR' was not declared in this scope
                 ll lsum=valL.first+valR.first+points;
                                    ^~~~
sequence.cpp:76:26: error: 'ans' was not declared in this scope
                 if(lsum>=ans.first) {
                          ^~~
sequence.cpp:79:25: error: 'path' was not declared in this scope
                         path.push_back(idx);
                         ^~~~
sequence.cpp:80:21: error: 'path' was not declared in this scope
                     path.push_back(i+l);
                     ^~~~
sequence.cpp:85:21: error: 'ans' was not declared in this scope
         dp[{i,j,k}]=ans;
                     ^~~
sequence.cpp:86:16: error: unable to deduce lambda return type from 'ans'
         return ans;
                ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:90:5: error: 'cout' was not declared in this scope
     cout<<ans.first<<endl;
     ^~~~
sequence.cpp:90:22: error: 'endl' was not declared in this scope
     cout<<ans.first<<endl;
                      ^~~~
sequence.cpp:90:22: note: suggested alternative: 'enum'
     cout<<ans.first<<endl;
                      ^~~~
                      enum