Submission #111033

#	Time	Username	Problem	Language	Result	Execution time	Memory
111033		aleksami	Split the sequence (APIO14_sequence)	C++14	0 / 100	20 ms	4716 KiB

sequence

    #include <bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    struct lajn
    {
      ll k;
      ll n;
      int idx;
    };
    #define MAXN 100005
    #define MAXK 205
    deque <lajn> q;
    ll a[MAXN];
    ll dp[MAXN][MAXK];
    int opt[MAXN][MAXK];
     
    ll f(ll k,ll n,ll x)
    {
      return k*x+n;
    }
     
    bool useless(ll x)
    {
      lajn a = q.front();
      q.pop_front();
      lajn b = q.front();
      q.push_front(a);
      if(f(a.k,a.n,x)<f(b.k,b.n,x))return true;
      return false;
    }
     
    void calc(int idx,int n)
    {
      q.clear();
      for(int i = 1; i <= n; i++)
      {
        while(1)
        {
          if(q.size()<=1)break;
          if(useless(a[i]))q.pop_front();
          else break;
        }
        lajn aa = (q.size() > 0) ? q.front():lajn();
        dp[idx][i]=f(aa.k,aa.n,a[i]);
        opt[idx][i]=aa.idx;
        aa.k=a[i];
        aa.n=-a[i]*a[i]+dp[idx-1][i];
        aa.idx=i;
        q.push_back(aa);
      }
    }
     
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      cout.tie(NULL);
      int n,k;
      cin >> n >> k;
      for(int i = 1; i <= n; i++)
      {
        cin >> a[i];
        a[i]+=a[i-1];
      }
      for(int i = 1; i <= k; i++)
      {
        calc(i,n);
      }
      cout << dp[k][n] << "\n";
      int now = n;
      while(k > 0)
      {
        cout << opt[k][now] << " ";
        now = opt[k][now];
        k--;
      }
      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