#include <bits/stdc++.h>
#define pb push_back
#define rs resize
#define debug printf("Hello\n")
#define Pi 3.141592653589793
#define sz(a) ll((a).size())
#define all(x) (x).begin(), (x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
#define mp make_pair
#define f first
#define s second
#define vt vector
#define rst(a,b) memset((a),(b), sizeof(a))
#define FOR(a, b, c) for (ll a = (b); (a) < (c); ++(a))
#define FORE(a, b, c) for (ll a = (b); (a) <= (c); ++(a))
#define FORR(a, b, c) for (ll a = (b); (a) >= (c); --(a))
#define umap unordered_map
#define len(a) (a).length()
#define pqueue priority_queue
using namespace std;
using vi = vector<int>;
using ui = unsigned int;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
using pii = pair<int, int>;
ll e(ll base, ll pwr, ll mm = LLONG_MAX){
if(pwr == 1) return base%mm;;
if(pwr == 0) return 1;
if(pwr % 2 == 1){
ull t = e(base, (pwr-1)/2,mm)%mm;
return (t*t)%mm*base%mm ;
}
if(pwr % 2 == 0){
ull t = e(base, pwr/2, mm)%mm;
return (t*t)%mm;
}
return 0;
}
ll flt(ll a, ll p){
return e(a,p-2,p);
}
ll combination(ll n, ll r){
if(r>n/2)return combination (n,n-r);
ll k=1;
for(ll x=n,j=1;x>n-r||j<=r;--x,++j){
if(x>n-r)k*=x;
if(j<=r)k/=j;
}
return k;
}
vector<ll> getFactor(ll n){
vector<ll> tmp;
vector<ll> ans;
if(n == 1)return vt<ll>{1};
else if(n==2) return vt<ll> {1,2};
for(ll i = 1;i<=ceil(sqrt(n));++i){
if(!(n%i)){
ans.pb(i);
if(i!=n/i && abs(i-(n/i)) != 1)tmp.pb(n/i);
}
}
for(ll i=tmp.size()-1;i>-1;--i){
ans.pb(tmp[i]);
}
return ans;
}
bool isPrime(ll n) {if(n == 1)return 0;for(ll i = 2;i*i <= n;++i){if(!(n%i))return 0;}return 1;}
const int dx[4] = {0,0,-1,1};
const int dy[4] = {1,-1,0,0};
const char dir[4] = {'R', 'L', 'U', 'D'};
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5+1;
ll parent[N];
ll delta[N];
ll acc[N];
ll arr[N], szz[N];
ll find(ll n){
if(parent[n] == -1)return n;
return parent[n] = find(parent[n]);
}
void un(ll a, ll b){
ll u = find(a);
ll v = find(b);
parent[v] = u;
acc[u] = acc[v] + delta[v];
szz[u] += szz[v];
}
void solve(){
rst(parent,-1);
rst(delta,0);rst(acc,0);
ll n,k;cin >> n >> k;
FOR(i,0,n){
cin >> arr[i];
szz[i] = 1;
}
vt<pll> s;
FOR(i,1,n){
delta[i] = arr[i] - arr[i-1] - 1;
s.pb(mp(delta[i], i));
}
if(k>=n){
cout << n << endl;
return;
}
sort(all(s));
ll times = n-k;
ll j = 0;
while(times--){
un(s[j].s-1, s[j].s);
j++;
}
unordered_map<ll,ll> mpp;
ll ans = 0;
FOR(i,0,n){
ll w = find(i);
if(mpp[w] == 0){
ans += szz[w] + acc[w];
mpp[w]++;
}
}
cout << ans << endl;
}
int main(){
fastio;
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
