Submission #645284

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

sequence

  #pragma GCC target ("avx2")
  #pragma GCC optimization ("O3")
  #pragma GCC optimization ("unroll-loops")
  #include<bits/stdc++.h>
  using namespace std;

  void __print(int x) {cerr << x;}
  void __print(long x) {cerr << x;}
  void __print(long long x) {cerr << x;}
  void __print(unsigned x) {cerr << x;}
  void __print(unsigned long x) {cerr << x;}
  void __print(unsigned long long x) {cerr << x;}
  void __print(float x) {cerr << x;}
  void __print(double x) {cerr << x;}
  void __print(long double x) {cerr << x;}
  void __print(char x) {cerr << '\'' << x << '\'';}
  void __print(const char *x) {cerr << '\"' << x << '\"';}
  void __print(const string &x) {cerr << '\"' << x << '\"';}
  void __print(bool x) {cerr << (x ? "true" : "false");}

  template<typename T, typename V>
  void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  template<typename T>
  void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  void _print() {cerr << "]\n";}
  template <typename T, typename... V>
  void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  #ifndef ONLINE_JUDGE
  #define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
  #else
  #define deb(x...)
  #endif

  #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--;
    }
    deb(v);
    
    
      
    return 0;
  }
  

Compilation message (stderr)

sequence.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 |   #pragma GCC optimization ("O3")
      | 
sequence.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 |   #pragma GCC optimization ("unroll-loops")
      |

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