oj.uz

Submission #201175

# Submission time Handle Problem Language Result Execution time Memory
201175 2020-02-09T15:15:44 Z quocnguyen1012 K blocks (IZhO14_blocks) C++14
0 / 100
 229 ms 5112 KB 
#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 opt[2][maxn], a[maxn];
int rmq[maxn][18], Log[maxn];
int N, f[2][maxn], K;

int query(int l, int r)
{
  int len = r - l + 1;
  int k = Log[len];
  return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}

bool Min(int & a, int b)
{
  if (a > b){
    a = b;
    return true;
  }
  return false;
}

void calc(int lev, int i, int L, int R)
{
  f[1][i] = 1e9 + 5;
  for (int j = L; j <= min(i - 1, R); ++j){
    if (Min(f[1][i], f[0][j] + query(j + 1, i))){
      opt[1][i] = j;
    }
  }
}

void solve(int lev, int l, int r, int L, int R)
{
  if (l > r) return;
  int mid = (l + r) / 2;
  calc(lev, mid, L, R);
  solve(lev, l, mid - 1, L, opt[1][mid]);
  solve(lev, mid + 1, r, opt[1][mid], R);
}

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;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    Log[i] = log2(i);
    rmq[i][0] = a[i];
  }
  for (int j = 1; (1 << j) <= N; ++j){
    for (int i = 1; i + (1 << j) - 1 <= N; ++i){
       rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    }
  }
  f[0][0] = 0;
  for (int i = 1; i <= K; ++i){
    fill_n(&f[1][0], maxn, 1e9 + 5);
    solve(i, 1, N, 0, N - 1);
    memcpy(f[0], f[1], sizeof f[0]);
  }
  cout << f[1][N];
}

Compilation message

blocks.cpp: In function 'int main()':
blocks.cpp:56: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:57: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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1144 KB Output is correct
2 Incorrect 5 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Incorrect 5 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2044 KB Output is correct
2 Correct 18 ms 5112 KB Output is correct
3 Correct 32 ms 5112 KB Output is correct
4 Incorrect 229 ms 5112 KB Output isn't correct
5 Halted 0 ms 0 KB -