제출 #111106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
111106		aleksami	수열 (APIO14_sequence)	C++14	33 / 100	51 ms	2368 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;
        }

		bool provera()
        {
          if(q.size()<3)return false;
          lajn a = q.back();
          q.pop_back();
          lajn b = q.back();
          q.pop_back();
          lajn c = q.back();
          q.push_back(b);
          q.push_back(a);
          if((a.n-b.n)*(c.k-b.k) <= (b.n-c.n) * (b.k-a.k))return true;
          return false;
        }
         
        void calc(int idx,int n)
        {
          q.clear();
          for(int i = idx; i <= n; i++)
          {
            lajn 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;
            }
            aa.k=a[i];
            aa.n=-a[i]*a[i]+dp[idx-1][i];
            aa.idx=i;
            q.push_back(aa);
            while(provera())
            {
              lajn z = q.back();
              q.pop_back();
              q.pop_back();
              q.push_back(z);
            }
          }
        }
         
        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: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29