oj.uz

Submission #601011

# Submission time Handle Problem Language Result Execution time Memory
601011 2022-07-21T10:07:18 Z jjiangly Stove (JOI18_stove) C++14
50 / 100
 220 ms 197012 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define siz(x) int(x.size())
#define ll long long
#define ar array
#define vt vector
#define inf INT_MAX
#define lnf (long long) 1e16

const int nxm = int(5e3) + 7;

int n, k, t[nxm];

namespace sub1 {
  void solve() {
    vt<bool> f(25, false);
    for (int i = 0; i < n; ++i) {
      --t[i];
      f[t[i]] = true;
    }
    int ans = 21;
    for (int mask = 0; mask < (1<<20); ++mask) {
      int lbit = 0;
      int ton = 0;
      bool ok = true;
      for (int i = 0; i < 20; ++i) {
        if (mask >> i & 1) {
          if (!lbit) {
            ++ton;
          }
        }
        if (!(mask >> i & 1) && f[i]) {
          ok = false;
        }
        lbit = mask >> i & 1;
      }
      if (ton <= k && ok) {
        ans = min(ans, __builtin_popcount(mask));
      }
    }
    cout<< ans << "\n";
  }
};

namespace sub2 {
  void solve() {
    vt<vt<ll>> dp(nxm, vt<ll> (nxm, -1));
    function<ll(int, int)> work = [&](int x, int y) {
      ll &r = dp[x][y];
      if (r != -1) {
        return r;
      }
      r = lnf;
      if (!y) {
        return r;
      }
      if (!x) {
        return r = 1;
      }
      r = min(r, work(x - 1, y - 1) + 1);
      r = min(r, work(x - 1, y) + t[x] - t[x - 1]);
      return r;
    };
    cout << work(n - 1, k) << "\n";
  }
}

int subtask() {
  if (n <= 20) {
    return 1;
  } else if (n <= 5000) {
    return 2;
  }
  return 3;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
  }
  if (subtask() == 1) {
    sub1::solve();
  } else if(subtask() == 2) {
    sub2::solve();
  }

  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 212 KB Output is correct
2 Correct 59 ms 304 KB Output is correct
3 Correct 59 ms 304 KB Output is correct
4 Correct 58 ms 308 KB Output is correct
5 Correct 58 ms 212 KB Output is correct
6 Correct 61 ms 304 KB Output is correct
7 Correct 75 ms 304 KB Output is correct
8 Correct 66 ms 304 KB Output is correct
9 Correct 67 ms 304 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 212 KB Output is correct
2 Correct 59 ms 304 KB Output is correct
3 Correct 59 ms 304 KB Output is correct
4 Correct 58 ms 308 KB Output is correct
5 Correct 58 ms 212 KB Output is correct
6 Correct 61 ms 304 KB Output is correct
7 Correct 75 ms 304 KB Output is correct
8 Correct 66 ms 304 KB Output is correct
9 Correct 67 ms 304 KB Output is correct
10 Correct 88 ms 197000 KB Output is correct
11 Correct 97 ms 196912 KB Output is correct
12 Correct 170 ms 196968 KB Output is correct
13 Correct 220 ms 197012 KB Output is correct
14 Correct 216 ms 196940 KB Output is correct
15 Correct 194 ms 196952 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 212 KB Output is correct
2 Correct 59 ms 304 KB Output is correct
3 Correct 59 ms 304 KB Output is correct
4 Correct 58 ms 308 KB Output is correct
5 Correct 58 ms 212 KB Output is correct
6 Correct 61 ms 304 KB Output is correct
7 Correct 75 ms 304 KB Output is correct
8 Correct 66 ms 304 KB Output is correct
9 Correct 67 ms 304 KB Output is correct
10 Correct 88 ms 197000 KB Output is correct
11 Correct 97 ms 196912 KB Output is correct
12 Correct 170 ms 196968 KB Output is correct
13 Correct 220 ms 197012 KB Output is correct
14 Correct 216 ms 196940 KB Output is correct
15 Correct 194 ms 196952 KB Output is correct
16 Runtime error 2 ms 724 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -