Submission #645293

#	Time	Username	Problem	Language	Result	Execution time	Memory
645293		mohit409194487	Split the sequence (APIO14_sequence)	C++17	0 / 100	1338 ms	16480 KiB

sequence

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

  #define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
  #define pb push_back
  #define endl "\n"
  typedef long long int  ll;
  typedef long long LL; 
  typedef pair<int, int> pii; 
  typedef pair<LL, LL> pll; 
  typedef pair<string, string> pss; 
  typedef vector<int> vi; 
  typedef vector<vi> vvi; 
  typedef vector<pii> vii; 
  typedef vector<ll> vl; 
  typedef vector<pll> vll;
  typedef vector<vl> vvl;
  #define all(x) (x).begin(),(x).end()
  #define rall(x) (x).rbegin(),(x).rend()
  #define  mem(a,x)  memset(a,x,sizeof(a))
 
 
  #define ff first
  #define ss second
 
  #define w(t)  int t; cin>>t; while(t--)
  #define maxe *max_element
  #define mine *min_element
  #define sz(x) (int)(x).size()
  #define lb lower_bound
  #define ub upper_bound
  #define setbits(x)  __builtin_popcountll(x)
  #define zrobits(x)  __builtin_ctzll(x)
  const long long INFF=1e18;
  const int INF=INT_MAX;
  const int N = 50001;
  const int M = 1e9+7;
  ll dp[1005][1005];
  int arr[10000];
  ll pf[10000];
    int n,k;
  int ind[1003][1003];
  ll fun(int idx,int parts,stack<int> &st){
    if(idx>n)
        return 0;
    if(parts==0){
      return 0;
    }
    if(n-idx<parts)
        return -1;
    ll ans=0;
    for(int i=idx;i<=n;i++){
        ll sum1=pf[i]-pf[idx-1];
        ll sum2=pf[n]-pf[i];
        ll tem_ans=sum1*sum2;
        ll val=fun(i+1,parts-1,st);
        if(val!=-1){
            tem_ans+=val;
 
        if(tem_ans>ans){
            // if(ans>0 )
            // st.pop();
            // st.push(i);
            ind[idx][parts]=i;
            ans=tem_ans;
        } 
                // ans=max(ans,sum1*sum2+fun(i+1,parts-1,st));
        }
    }
    return dp[idx][parts]=ans;
 
  }
   
  int32_t main()
  {
    /****************************************/
    /****************************************/
    fast;
   
    /****************************************/
    /****************************************/
    cin >> n >> k;
    for(int i=0;i<n+3;i++){
        for(int j=0;j<n+3;j++)
            dp[i][j]=-1;
    }
    for(int i=0;i<n;i++)
        cin >> arr[i+1];
    for(int i=1;i<=n;i++)
        pf[i]=pf[i-1]+arr[i];
    stack<int> st;
    cout << fun(1,k,st) << endl;
    vi v;
    int parts=k;
    int i=1;
    while(parts){
        v.pb(ind[i][parts]);
        i=ind[i][parts]+1;
        parts--;
    }
 
    
    
      
    return 0;
  }

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