제출 #601027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601027		jjiangly	Stove (JOI18_stove)	C++14	100 / 100	224 ms	196816 KiB

stove

#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(1e5) + 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(5003, vt<ll> (5003, -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";
  }
}

namespace sub3 {
  void solve() {
    ll ans = t[n - 1] - t[0] + 1;
    priority_queue<ll> q;
    for (int i = 0; i < n; ++i) {
      q.push(t[i + 1] - t[i] - 1);
    }
    while (k > 1) {
      --k;
      ans -= q.top();
      q.pop();
    }
    cout << ans << "\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();
  } else {
    sub3::solve();
  }

  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50