Submission #228762

#	Time	Username	Problem	Language	Result	Execution time	Memory
228762		davitmarg	K blocks (IZhO14_blocks)	C++17	100 / 100	163 ms	167332 KiB

blocks

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

int n, k;
LL a[N], lst[N], dp[N][105], mindp[N][105];

vector<int> s;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        scanf("%lld", a + i);

    a[0] = mod;
    s.PB(0);

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = mindp[i][j] = mod * mod;
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        while (a[s.back()] <= a[i])
        {
            for (int j = 0; j <= k; j++)
                mindp[i][j] = min(mindp[i][j], min(mindp[s.back()][j], dp[s.back()][j]));
            s.pop_back();
        }
        lst[i] = s.back();
        for (int j = 0; j <= k; j++)
            mindp[i][j] = min(mindp[i][j], dp[lst[i]][j]);
        s.PB(i);

        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = min(dp[i][j], dp[lst[i]][j]);
          /*  for (int x = i; x > lst[i]; x--)
                dp[i][j] = min(dp[i][j], dp[x - 1][j - 1] + a[i]);*/
            dp[i][j] = min(dp[i][j], mindp[i][j - 1] + a[i]);
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

/*

2 4
9 10
5 4 5 5


*/

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", a + i);
         ~~~~~^~~~~~~~~~~~~~~

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