Submission #290395

#	Time	Username	Problem	Language	Result	Execution time	Memory
290395		Dymo	K blocks (IZhO14_blocks)	C++14	100 / 100	325 ms	96488 KiB

blocks

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define all(n) n.begin(),n.end()
#define endl "\n"
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
const ll maxn=2e5+500;
const ll mod=1e9+7 ;
const ll base=500;
/// con 9 ngay

ll a[maxn];
ll dp[maxn][120];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.txt","r",stdin);
    if (fopen("Farm.INP","r"))
    {
        freopen("Farm.INP","r",stdin);
        freopen("Farm.OUT","w",stdout);
    }
    ll n, k;
     cin>> n>> k;
     for (int i=1;i<=n;i++)
     {
       cin>>a[i];
     }
     for (int i=0;i<=n;i++)
     {
         for (int j=1;j<=k;j++)
         {
             dp[i][j]=1e15;

         }
     }
     dp[0][1]=1e15;
     for (int i=1;i<=n;i++)
     {
         if (i!=1) dp[i][1]=max(dp[i-1][1],a[i]);
         else dp[i][1]=a[i];
     }
     for (int j=2;j<=k;j++)
     {
         stack<pll> st;

         for (int i=j;i<=n;i++)
         {
             ll nw=dp[i-1][j-1];
             while (st.size()&&a[st.top().ss]<=a[i])
             {
                 nw=min(nw,st.top().ff);

                 st.pop();
             }
             ll t;
             if (st.size()) t=st.top().ss;
             else t=0;
             dp[i][j]=min(nw+a[i],dp[t][j]);
             st.push(make_pair(nw,i));
         }
     }
     cout <<dp[n][k];



}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         freopen("Farm.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         freopen("Farm.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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