제출 #1153009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153009		chthonic_cream	Stove (JOI18_stove)	C++20	100 / 100	12 ms	1476 KiB

stove

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int

using namespace __gnu_pbds;
using namespace std;
const int maxn=1e5;
const int maxm=1e3;
const int di[4]={-1, 0, 1, 0};
const int dj[4]={0, 1, 0, -1};
const ll mod=1e9+9;
typedef pair<ll, ll> pll;
struct PairCompare {
    bool operator()(const pll &a, const pll &b) const {
        return (a.first == b.first) ? a.second < b.second : a.first < b.first;
    }
};
typedef tree<
    pll,
    null_type,
    PairCompare,
    rb_tree_tag,
    tree_order_statistics_node_update>
ordered_multiset;

ll mulmod(ll a, ll b, ll mod) {
    ll res = 0;
    a = a % mod;
    while (b > 0) {
        if (b % 2 == 1)
            res = (res + a) % mod;
        a = (a * 2) % mod;
        b = b / 2;
    }
    return res % mod;
}

ll powmod(ll base, ll expo, ll mod) {
    ll res = 1;
    base = base % mod;
    while (expo > 0) {
        if (expo % 2 == 1)
            res = mulmod(res, base, mod);
        base = mulmod(base, base, mod);
        expo = expo / 2;
    }
    return res;
}

bool miller_rabin(ll n, ll d) {
    ll a = 2 + rand() % (n - 4);
    ll x = powmod(a, d, n);

    if (x == 1 || x == n - 1)
        return true;

    while (d != n - 1) {
        x = mulmod(x, x, n);
        d = d * 2;

        if (x == 1)
            return false;
        if (x == n - 1)
            return true;
    }
    return false;
}

bool is_prime(ll n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;

    for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}) {
        if (n % p == 0)
            return n == p;
    }

    ll d = n - 1;
    while (d % 2 == 0)
        d = d / 2;

    for (int i = 0; i < 10; i++) {
        if (!miller_rabin(n, d))
            return false;
    }
    return true;
}

class DSU
{
    vector<ll> rank, parent;
    public:
    DSU(ll x)
    {
        rank.resize(x, 0);
        parent.resize(x);
        for (int i=0; i<x; i++)
        {
            parent[i]=i;
        }
    }
    ll find(ll x)
    {
        ll root=parent[x];
        if (parent[root] != root)
        {
            return parent[x]=find(root);
        }
        return root;
    }
    void uni(ll x, ll y)
    {
        ll xroot=find(x);
        ll yroot=find(y);
        if (xroot == yroot)
        {
            return;
        }
        if (rank[xroot] < rank[yroot])
        {
            parent[xroot]=yroot;
        }
        else if (rank[xroot] > rank[yroot])
        {
            parent[yroot]=xroot;
        }
        else
        {
            parent[yroot]=xroot;
            rank[xroot]++;
        }
    }
};

void procedure()
{
    ll n, k, sum;
    cin>>n>>k;
    vector<ll> v;
    ll a[maxn+5];
    for (int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    sum=a[n]-a[1]+1;
    for (int i=2; i<=n; i++)
    {
        v.push_back(a[i]-a[i-1]);
    }
    sort(v.begin(), v.end(), greater<ll>());
    k--;
    for (auto i:v)
    {
        if (k>0)
        {
            sum=sum-i+1;
            k--;
        }
        else break;
    }
    cout<<sum;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    t=1;
    while (t--)
    {
        procedure();
    }
    return 0;
}

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