oj.uz

Submission #676571

# Submission time Handle Problem Language Result Execution time Memory
676571 2022-12-31T10:10:35 Z shantol Stove (JOI18_stove) C++14
100 / 100
 19 ms 2772 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 17 ms 2728 KB Output is correct
17 Correct 17 ms 2740 KB Output is correct
18 Correct 16 ms 2736 KB Output is correct
19 Correct 17 ms 2728 KB Output is correct
20 Correct 18 ms 2772 KB Output is correct
21 Correct 17 ms 2760 KB Output is correct
22 Correct 18 ms 2740 KB Output is correct
23 Correct 17 ms 2772 KB Output is correct
24 Correct 19 ms 2736 KB Output is correct