Submission #332172

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332172	2020-12-01T15:15:43 Z	Valera_Grinenko	K blocks (IZhO14_blocks)	C++17	Compilation error	0 ms	0 KB

blocks

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 1e5 + 42, K = 102;
ll dp[K][N], a[N];
int main() {

  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, k;

  cin >> n >> k;

  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = 1; i <= k; i++)
    for(int j = 1; j <= n; j++)
      dp[i][j] = 1e18 + 42;

  dp[1][1] = a[1];

  for(int i = 2; i <= n; i++) dp[1][i] = max(dp[1][i - 1], a[i]);

  for(int ck = 2; ck <= k; ck++) {
    stack<pair<ll,llt> > av;
    for(int j = ck; j <= n; j++) {
      ll cur = dp[ck - 1][j - 1];
      while(!av.empty() && a[av.top().se] <= a[j]) {
        cur = min(cur, av.top().se);
        av.pop();
      }
      if(!av.empty()) dp[ck][j] = min(dp[ck][j], dp[ck][av.top().fi]);
      dp[ck][j] = min(dp[ck][j], cur + a[j]);
      av.push(mp(j, cur));
    }
  }

  cout << dp[k][n];

  return 0;
}
/*

*/

Compilation message

blocks.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
blocks.cpp: In function 'int main()':
blocks.cpp:58:19: error: 'llt' was not declared in this scope; did you mean 'll'?
   58 |     stack<pair<ll,llt> > av;
      |                   ^~~
      |                   ll
blocks.cpp:58:22: error: template argument 2 is invalid
   58 |     stack<pair<ll,llt> > av;
      |                      ^
blocks.cpp:58:24: error: template argument 1 is invalid
   58 |     stack<pair<ll,llt> > av;
      |                        ^
blocks.cpp:58:24: error: template argument 2 is invalid
blocks.cpp:61:17: error: request for member 'empty' in 'av', which is of non-class type 'int'
   61 |       while(!av.empty() && a[av.top().se] <= a[j]) {
      |                 ^~~~~
blocks.cpp:61:33: error: request for member 'top' in 'av', which is of non-class type 'int'
   61 |       while(!av.empty() && a[av.top().se] <= a[j]) {
      |                                 ^~~
blocks.cpp:62:27: error: request for member 'top' in 'av', which is of non-class type 'int'
   62 |         cur = min(cur, av.top().se);
      |                           ^~~
blocks.cpp:63:12: error: request for member 'pop' in 'av', which is of non-class type 'int'
   63 |         av.pop();
      |            ^~~
blocks.cpp:65:14: error: request for member 'empty' in 'av', which is of non-class type 'int'
   65 |       if(!av.empty()) dp[ck][j] = min(dp[ck][j], dp[ck][av.top().fi]);
      |              ^~~~~
blocks.cpp:65:60: error: request for member 'top' in 'av', which is of non-class type 'int'
   65 |       if(!av.empty()) dp[ck][j] = min(dp[ck][j], dp[ck][av.top().fi]);
      |                                                            ^~~
blocks.cpp:67:10: error: request for member 'push' in 'av', which is of non-class type 'int'
   67 |       av.push(mp(j, cur));
      |          ^~~~