제출 #111042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111042		aleksami	수열 (APIO14_sequence)	C++14	22 / 100	19 ms	3584 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++)
      {
        lajn aa;
        if(i!=n){aa.k=a[i];
        aa.n=-a[i]*a[i]+dp[idx-1][i];
        aa.idx=i;
        q.push_back(aa);
        }
        while(1)
        {
          if(q.size()<=1)break;
          if(useless(a[i]))q.pop_front();
          else break;
        }
        if(q.size()>0)
        {
          lajn aa = q.front();
          dp[idx][i]=f(aa.k,aa.n,a[i]);
          opt[idx][i]=aa.idx;
        }
      }
    }
     
    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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29