Submission #166392

#	Time	Username	Problem	Language	Result	Execution time	Memory
166392		Trickster	K blocks (IZhO14_blocks)	C++14	100 / 100	487 ms	2808 KiB

blocks

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <numeric>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)
#ifdef WIN32
#define I64d "%I64d"
#else
#define I64d "%lld"
#endif

typedef pair <int, int> pi;
typedef vector <int> vi;
typedef long long ll;

const int inf = int(1e9);
int n, k;
vector <int> prv, cur, a;
vector <pi> st;

int main()
{
	scanf("%d%d", &n, &k);
    
	a.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    
	a[0] = inf;

    prv.assign(n + 1, inf);
    
	prv[0] = 0;
    cur.resize(n + 1);
    
	for (int iter = 1; iter <= k; ++iter)
	{
        st.clear();
        
		st.pb(mp(0, prv[0]));
        
		cur[0] = inf;
        
        
        for (int i = 1; i <= n; ++i)
		{
            int mn = inf;
            
			while (a[st.back().f] <= a[i])
			{
                mn = min(mn, st.back().s);
                st.pop_back();
            }
            
			cur[i] = min(cur[st.back().f], min(mn, prv[st.back().f]) + a[i]);
            
			st.push_back(mp(i, min(mn, prv[i])));
        }
        swap(prv, cur);
    }
    cout << prv[n] << endl;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 1; i <= n; ++i)
     ^~~
blocks.cpp:47:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  a[0] = inf;
  ^
blocks.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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