Submission #1123071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123071		notece	Stove (JOI18_stove)	C++20	100 / 100	23 ms	2316 KiB

stove

// Author: ChungNotTrung;
// Created: 2024-12-02 14:33:08
// Problem: None
// Tag: None
// Source: None
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "C:\DEBUG\debugtemplate.cpp"
#else
#define debug(...)
#endif

#define ll long long
#define db long double
#define int long long

#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define All(x) x.begin(), x.end()

#define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
#define file_trau(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".ans", "w", stdout) : 0
#define Faster ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Run_time cerr << " Time : " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n"

#define bit(i, n) (1ll && ((1ll << i) & (n)))
#define ONBIT(i, mask) ((1ll << i) | (mask))
#define OFFBIT(i, mask) ((~(1ll << i)) & (mask))
#define MASK(n) (1ll << (n))
#define cnt_bit(n) (__builtin_popcountll(n))
#define Lg2(n) (63 - __builtin_clzll(n))

#define rep(i, x, n) for (int i = x; i <= n; ++i)
#define repd(i, n, x) for (int i = n; i >= x; --i)
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define repv(i, n) for (auto &i : n)

#define as_vi(v, n, val) v.assign(n + 1, val)
#define as_vvi(v, n, m, val) v.assign(n + 1, vi(m + 1, val))
#define as_vvvi(v, n, m, k, val) v.assign(n + 1, vvi(m + 1, vi(k + 1, val)))

#define left(id) (id << 1ll)
#define right(id) (id << 1ll | 1)

mt19937 rd(chrono::steady_clock().now().time_since_epoch().count());
int rng(int l, int r) { return uniform_int_distribution<int>(l, r)(rd); }
vi dx{0, 0, 1, -1, 1, 1, -1, -1};
vi dy{1, -1, 0, 0, -1, 1, -1, 1};

template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>>
{
    static_assert(D >= 1, "Vector dimension must be greater than zero!");
    template <typename... Args>
    Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...))
    {
    }
};
template <typename T>
struct Vec<1, T> : public vector<T>
{
    Vec(int n = 0, const T &val = T()) : vector<T>(n, val)
    {
    }
};

template <class X, class Y>
bool maximize(X &a, const Y &b)
{
    if (a < b)
        return a = b, true;
    return false;
}

template <class X, class Y>
bool minimize(X &a, const Y &b)
{
    if (a > b)
        return a = b, true;
    return false;
}
const int base = 311;
const int nmax = 1e6 + 10;
const int oo = 1e18 + 100;
const int MOD = 1e9 + 7;
int sqr(int x)
{
    return x * x;
}

int POW(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        n /= 2;
    }
    return res;
}

void fixmod(int &val)
{
    if (val < 0)
        val = (val + MOD * MOD) % MOD;
    if (val >= MOD)
        val %= MOD;
}

int ntest;
int n, k;
int a[nmax];
namespace sub2
{
    int f[5005][5005];
    void solve()
    {
        rep(i, 1, n)
        {
            f[1][i] = a[i] - a[1] + 1;
        }
        rep(c, 2, k)
        {
            rep(i, 1, n)
            {
                f[c][i] = oo;
                repd(j, i - 1, 1)
                {
                    minimize(f[c][i], f[c - 1][j] + a[i] - a[j + 1] + 1);
                }
            }
        }
        cout << f[k][n];
    }
}
namespace full
{
    void solve()
    {
        priority_queue<int> pq;
        int sum = 0;
        rep(i, 1, n - 1)
        {
            pq.push(a[i + 1] - a[i] - 1);
        }
        sum = a[n] - a[1] + 1;
        rep(i, 2, k)
        {
            int x = pq.top();
            pq.pop();
            sum -= x;
        }
        cout << sum;
    }
};
void TryHard()
{
    cin >> n >> k;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    // sub2::solve();
    full::solve();
}
main()
{

    // Learning is like rowing upstream, not to advance is to drop back .
    // A winner never stops trying .
    Faster;
    file("JOI18_stove");
    // file_trau("");
    ntest = 1;
    // cin >> ntest;
    while (ntest--)
    {
        TryHard();
        cout << "\n";
    }
}

// LIMIT :

/*   /\_/\
    ( ._. )
    / >C< \
*/

Compilation message (stderr)

stove.cpp:198:11: warning: backslash-newline at end of file
  198 |     / >C< \
      |            
stove.cpp:177:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  177 | main()
      | ^~~~
stove.cpp: In function 'int main()':
stove.cpp:29:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:183:5: note: in expansion of macro 'file'
  183 |     file("JOI18_stove");
      |     ^~~~
stove.cpp:29:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:183:5: note: in expansion of macro 'file'
  183 |     file("JOI18_stove");
      |     ^~~~

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