Submission #105368

#	Time	Username	Problem	Language	Result	Execution time	Memory
105368		thanhtraf	K blocks (IZhO14_blocks)	C++11	100 / 100	681 ms	41116 KiB

blocks

 #include<bits/stdc++.h>
 using namespace std;

 #define task "data"

 const int maxn=1e5+5;
 const int vc=-1e9+5;
 int dp[maxn][100] , n , a[maxn] , k ;
  typedef pair<int,int> ii;
  #define fi first
  #define se second

  main()
   {
       //freopen(task".inp","r",stdin);
      // freopen(task".out","w",stdout);

       scanf("%d%d",&n,&k);

       for (int i=1;i<=n;i++) scanf("%d",&a[i]);

       memset(dp, 0x3f, sizeof dp);
       //cout<<dp[1][0];
        dp[0][1]=0;

          for (int i=1;i<=n;i++)
           {
                dp[i][1]=max(a[i],dp[i-1][1]);
                // cout<<dp[i][1];
           }

        for (int i=2;i<=k;i++)
        {
            stack<ii> s;
            for (int j=i;j<=n;j++)
            {
                int minf=dp[j-1][i-1];
                while (s.size()&&a[j]>=a[s.top().se])
                {
                    minf=min(minf,s.top().fi);
                    s.pop();
                }
                //cout<<minf<<endl;
                    if(s.size()==0)
                    dp[j][i]=dp[0][i];
                    else
                        dp[j][i]=dp[s.top().se][i];
                dp[j][i]=min(minf+a[j],dp[j][i]);
                s.push(ii(minf,j));;
            }
        }

        cout<<dp[n][k];

        return 0;
   }

Compilation message (stderr)

blocks.cpp:14:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   main()
        ^
blocks.cpp: In function 'int main()':
blocks.cpp:19:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d%d",&n,&k);
        ~~~~~^~~~~~~~~~~~~~
blocks.cpp:21:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
                               ~~~~~^~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47