Submission #1158619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158619		aldksw	Stove (JOI18_stove)	C++20	100 / 100	14 ms	1864 KiB

stove

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define f first  
#define s second
// ll n,a[1001000],q,b[1001000],z[8001000],ans[1001000];
// pair<ll,ll>st[4001000];
//  ll binpov( ll a,ll n,ll m){
//         if(n==0){x
//              return 1ll;
//         }
//         if(n&1)return((binpov(a,n-1,m)%m)*a%m);
//         else{
//              ll b=binpov(a,n/2,m)%m;
//              return ((b*1ll*b)%m);
//         }
//      }
// pair<ll,ll> merge(pair<ll,ll>a,pair<ll,ll>b){
//    if(a.f>b.f){
//         return a;
//    }
//    return b;
// }
// void build(ll v,ll l,ll r){
//    if(l==r){
//         st[v].f=b[l];
//         st[v].s=l;
//         //cout<<b[l]<<' '<<l<<'\n';
//         return;
//    }
//    ll mid=(r+l)/2;
//    build(v*2,l,mid);
//    build(v*2+1,mid+1,r);
//    st[v]=merge(st[v*2],st[v*2+1]);
// }
// void push(ll v,ll l,ll r){
//    st[v*2].f-=z[v];
//    st[v*2+1].f-=z[v];
//    z[v*2]+=z[v];
//    z[v*2+1]+=z[v];
//    z[v]=0;
// }
// void upd_range(ll v,ll l,ll r,ll x,ll y) {
//    if(l>y||x>r)return;
//    if(x<=l&&r<=y){
//         st[v].f--;
//         z[v]++;
//         return;
//    }
//    push(v,l,r);
//    ll mid=(r+l)/2;
//    upd_range(v*2,l,mid,x,y);
//    upd_range(v*2+1,mid+1,r,x,y);
//    st[v]=merge(st[v*2],st[v*2+1]);
// }
// void upd_pos(ll v,ll l,ll r,ll pos){
//    if(l==r){
//         st[v].f=-1e10;
//         return;
//    }
//    push(v,l,r);
//    ll mid=(r+l)/2;
//    if(pos<=mid)upd_pos(v*2,l,mid,pos);
//    else upd_pos(v*2+1,mid+1,r,pos);
//    st[v]=merge(st[v*2],st[v*2+1]);
// }
// pair<ll,ll> get(ll v,ll l,ll r,ll x,ll y){
//    if(l>y||x>r){
//         return {-1e18,-1e10};
//    }
//    if(x<=l&&r<=y){
//         return {st[v]};
//    }
//    push(v,l,r);
//    ll mid=(l+r)/2;
//    return merge(get(v*2,l,mid,x,y),get(v*2+1,mid+1,r,x,y));
// }
vector<ll>g[22];
int gcd(int a, int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return (a/gcd(a,b))*b;
}
ll q,fact[5001],inv[5001];
const ll mod=1e9+7;
 ll binpow(ll a,ll n){
        if(n==0){
             return 1ll;
        }
        if(n%2)return binpow(a,n-1)*1LL*a%mod;
        else{
             ll b=binpow(a,n/2)%mod;
             return b*1LL*b%mod;
        }
 
     }
     bool saw(vector<int>v){
          int ok=1,ok1=1;
          for(int i=1;i<=(int)v.size();i+=2){
               ok&=(v[i-1]<v[i]&&v[i]>v[i+1]);
          }
          for(int i=1;i<=(int)v.size();i+=2){
               ok1&=(v[i-1]>v[i]&&v[i]<v[i+1]);
          }
          return (ok||ok1);
     }
     bool cyc(vector<int>v){
         int cnt=0,cur=1;
          while(cur!=v[cur-1]&&cnt<=(int)v.size()){
               cur=v[cur-1];
               if(cur==1)break;
               cnt++;
          }
          return (cnt==(int)v.size()-1);
     }
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll a[n+1]={0};
    for(int i=1;i<=n;i++){
         cin>>a[i];
    }
    ll tot[n+1]={0},sum=a[n]+1-a[1],cnt=0;
    for(int i=2;i<=n;i++){
         tot[i-1]=(a[i])-(a[i-1]+1);
    }
    sort(tot+1,tot+n);
    reverse(tot+1,tot+n);
    for(int i=1;i<m;i++){
         cnt+=tot[i];
    }
    cout<<sum-cnt;
}

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