제출 #739482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739482		vjudge1	Stove (JOI18_stove)	C++17	100 / 100	62 ms	85056 KiB

stove

#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//** har vaght m2 ghabool shodi javabetoo midam (radal) **
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<ll , ll>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 5e5 + 6;
const long long mod = 998244353;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<ll> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st , wtf , ajab;
ll dp[maxm];
ll rp[maxm];
pi w[maxm],ww[maxm];
//ll rw[maxm][maxm];
set<ll> ts[maxm] , jav[maxm];
ll rgh[maxm] , lft[maxm];
ll pw(ll x , ll y){
    ll ans = 1 , ok = x;
    while (y){
        if (y%2) ans *= ok;
        ans %= mod;
        ok *= ok;
        ok %= mod;
        y/=2;
    }
    return ans;
}
ll solve(ll x){
    for (int i=1; i<=n; i++) vis[i] = 0 , darage[i] = mod , gos[i] = 0;
    ll ans = 1;
    queue<int> qu;
    qu.push(x);
    darage[x] = 1;
    ll tr = 0;
    vis[x] = 1;
    while (qu.size()){
        auto x = qu.front();
        qu.pop();
        for (auto u : g[x]){
            if (!vis[u]){
                vis[u] = 1 , darage[u] = darage[x] + 1 , gos[x] = 1 , qu.push(u) , ans++;
            }
        }
    }
    for (int i=1; i<=n; i++) tr += darage[i];
    if (ans!=n) return mod*mod;
    return tr;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    l = n;
    for (int i=1; i<=n; i++) cin>>pedaret[i] , darage[i-1] = pedaret[i] - pedaret[i-1] - 1;
    sort(darage+1,darage+n);
    for (int i=1; i<=n-m; i++) l+=darage[i];
    cout<<l<<endl;
}

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