Submission #201178

#	Time	Username	Problem	Language	Result	Execution time	Memory
201178		quocnguyen1012	K blocks (IZhO14_blocks)	C++14	100 / 100	365 ms	43924 KiB

blocks

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int a[maxn], f[maxn][105];
int N, K;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> K;
  fill_n(&f[0][0], maxn * 105, 1e9 + 5);
  int mx = 0;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    mx = max(mx, a[i]);
    f[i][1] = mx;
  }
  for (int j = 2; j <= K; ++j){
    vector<pair<pair<int, int>, int>> vec;
    for (int i = 1; i <= N; ++i){
      int v = f[i - 1][j - 1];
      while (vec.size() && vec.back().fi.fi <= a[i]){
        v = min(v, vec.back().fi.se);
        vec.pop_back();
      }
      int val = v + a[i];
      if (vec.size()){
        val = min(val, vec.back().se);
      }
      f[i][j] = val;
      vec.pb(mp(mp(a[i], v), val));
    }
  }
  cout << f[N][K];
}

Compilation message (stderr)

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

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