Submission #111116

#	Time	Username	Problem	Language	Result	Execution time	Memory
111116		aleksami	Split the sequence (APIO14_sequence)	C++14	33 / 100	112 ms	2364 KiB

sequence

    #include <bits/stdc++.h>
     
    using namespace std;
    #define MAXN 100005
    #define MAXK 205
    typedef long long ll;
    ll dp[MAXN][MAXK];
    ll s[MAXN];
    int opt[MAXN][MAXK];
     
    struct lajn 
    {
      ll k;
      ll n;
      int idx;
    };
     
    ll f(lajn a,ll x)
    {
      return a.k*x+a.n;
    }
     
    bool bad(lajn a,lajn b,lajn c)
    {
      return (a.n-b.n)*(c.k-b.k) >= (b.n-c.n)*(b.k-a.k);
    }
     
    lajn prev_back(deque <lajn> q)
    {
      lajn x = q.back();
      q.pop_back();
      lajn y = q.back();
      q.push_back(x);
      return y;
    }
     
    void calc(int idx,int n)
    {
      deque <lajn> q;
      for(int i = idx; i <= n; i++)
      {
        while(1)
        {
          if(q.size()<=1)break;
          lajn a=q.front();
          q.pop_front();
          lajn b=q.front();
          if(f(a,s[i])<=f(b,s[i]))continue;
          q.push_front(a);
          break;
        }
        if(q.size())
        {
          dp[idx][i]=f(q.front(),s[i]);
          opt[idx][i]=q.front().idx;
        }
        lajn a;
        a.k=s[i];
        a.n=-s[i]*s[i]+dp[idx-1][i];
        a.idx=i;
        while(q.size()>1 && bad(prev_back(q),q.back(),a))q.pop_back();
        q.push_back(a);
      }
    }
     
    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 >> s[i];
        s[i]+=s[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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29