Submission #676571

#	Time	Username	Problem	Language	Result	Execution time	Memory
676571		shantol	Stove (JOI18_stove)	C++14	100 / 100	19 ms	2772 KiB

stove

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

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef array<int,3> triple;

#define log(x) 32 - __builtin_clz(x) - 1
#define ff first
#define sc second
#define pb push_back
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) x*(y/gcd(x,y))
#define mx(m) *max_element(m.begin(),m.end())
#define mn(m) *min_element(m.begin(),m.end())
#define fr(i,n) for(ll i=0;i<n;i++)
#define rfr(i,n) for(ll i=n-1;i>=0;i--)
#define cmp compare
#define elif else if
#define minv(x,y) (x<y? x:y)
#define vctr vector<ll>
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.rbegin(),a.rend())
#define sum(a) accumulate(a.begin(),a.end(),0)
#define chk(a,x) find(a.begin(),a.end(),x)!=a.end()
#define inf LLONG_MAX
#define pw(n,p)(p>=n? p:pw(n,2*p))
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define inv(x,mod) powermod(x,mod-2,mod)
#define sz size()
//fill(&a[0][0],&a[0][0]+100000*512,100000) a[100000][512]
//const ll N=500*10000+13;
//ll p[N];
const ll mod=1e9+7;

ll powermod(ll x,ll y,ll mod)
{
    ll res=1;
    while(y>0)
    {
        if(y&1)
        {
            if(mod)
            {
                res=(res*x)%mod;
            }
            else
            {
                res*=x;
            }
        }
        y>>=1;
        if(mod)
        {
            x=(x*x)%mod;
        }
        else
        {
            x*=x;
        }
    }
    return res;
}

vector<int> tr;
vector<int> cnt;

void build(int low,int high,int pos)
{
    if(low==high)
    {
        tr[pos]=cnt[low];
    }
    else
    {
        int mid=(low+high)/2;
        build(low,mid,pos*2+1);
        build(mid+1,high,pos*2+2);
        tr[pos]=tr[pos*2+1]+tr[pos*2+2];
    }
}

int query(int low,int high,int st,int en,int pos)
{
    if(low>en || high<st)return 0;
    if(low>=st && high<=en)
    {
        return tr[pos];
    }
    int mid=(low+high)/2;
    return query(low,mid,st,en,pos*2+1)+query(mid+1,high,st,en,pos*2+2);
}

void update(int low,int high,int ind,int val,int pos)
{
    if(low>ind || high<ind)return;
    if(low==high)tr[pos]+=val;
    else
    {
        int mid=(low+high)/2;
        update(low,mid,ind,val,pos*2+1);
        update(mid+1,high,ind,val,pos*2+2);
        tr[pos]=tr[pos*2+1]+tr[pos*2+2];
    }
}


void solve()
{
    int n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    vector<ll> v(n-1);
    for(int i=0;i<n-1;i++)v[i]=a[i+1]-a[i];
    sort(v.rbegin(),v.rend());
    ll cnt=0;
    for(int i=0;i<k-1;i++)cnt+=v[i]-1;
    cout<<a[n-1]-a[0]+1-cnt;
}


int main()
{
    fast;
    int t=1;
    //cin>>t;
    while(t--)solve();
}

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