Submission #394812

#	Time	Username	Problem	Language	Result	Execution time	Memory
394812		juggernaut	Split the sequence (APIO14_sequence)	C++14	0 / 100	1491 ms	131080 KiB

sequence

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
//using namespace __gnu_pbds;
typedef long long ll;
//template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>bool umax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,k,a[12];
pair<int,int>path[12][12][12];
ll dp[12][12][12];
ll rec(int l,int r,int k){
    if(k==1)return 0ll;
    if(k>r-l+1)return -1e15;
    ll &res=dp[l][r][k];
    if(~res)return res;
    ll sum=0,pref=0;
    res=0;
    for(int i=l;i<=r;i++)sum+=a[i];
    for(int i=l;i<r;i++){
        sum-=a[i];
        pref+=a[i];
        for(int j=1;j<k;j++)if(umax(res,sum*pref+rec(l,i,j)+rec(i+1,r,k-j))){
            path[l][r][k]={i,j};
        }
    }
    return res;
}
int main(){
    memset(dp,-1,sizeof dp);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ll ans=rec(1,n,k+1);
    printf("%lld\n",ans);
    queue<array<int,3>>q;
    q.push({1,n,k+1});
    while(!q.empty()){
        auto v=q.front();
        q.pop();
        if(v[2]==1)continue;
        printf("%d ",path[v[0]][v[1]][v[2]].fr);
        q.push({v[0],path[v[0]][v[1]][v[2]].fr,path[v[0]][v[1]][v[2]].sc});
        q.push({path[v[0]][v[1]][v[2]].fr+1,v[1],v[2]-path[v[0]][v[1]][v[2]].sc});
    }
}

Compilation message (stderr)

sequence.cpp: In function 'void usaco(std::string)':
sequence.cpp:6:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:6:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29