oj.uz

Submission #1049776

# Submission time Handle Problem Language Result Execution time Memory
1049776 2024-08-09T04:54:20 Z vjudge1 Stove (JOI18_stove) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<long long,long long> pl;

#define all(s) s.begin(),s.end()
#define F first
#define S second
#define sz(a) int(a.size())

const ll mod = 998244353;
const ll mod1 = 1e9+7;
const ll INF = 1e18;
const int N = 100200;
const int inf = 1e9+200;

long long binpow(long long a, long long b,ll mod) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n,k;
int a[N];

vector<pi> p;

void solve() {
    cin>>n>>k;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
    }
    a[n+1]=inf;
    for(int i=1,mn=1,mx=1,ok=1;i<=n;++i) {
        if(a[i]+1==a[i+1]) {
            mx=i+1;
        }
        else {
            p.push_back({mn,mx});
            mn=i+1;
            mx=i+1;
        }
    }
    if(sz(p)<=k) {
        int cnt=0;
        for(auto u:p) {
            cnt+=(a[u.S]-a[u.F]+1);
        }
        cout<<cnt<<'\n';
        return;
    }
    else {
        int cnt=sz(p)-k;
        int ans=0;
        vector<pi> d;
        for(int i=1;i<sz(p)-1;++i) {
            d.push_back({a[p[i].F]-a[p[i-1].S+1],i-1});
            d.push_back({a[p[i+1].F]-a[p[i].S+1],i});
        }
        sort(all(d));
        for(auto u:d) {
            if(cnt>0) {
                ans+=(a[p[u.S+1].F]-a[p[u.S].S]-1);
                --cnt;
            }
        }
        for(auto u:p) {
            ans+=(a[u.S]-a[u.F]+1);
        }
        cout<<ans<<'\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

Compilation message

stove.cpp: In function 'void solve()':
stove.cpp:43:27: warning: unused variable 'ok' [-Wunused-variable]
   43 |     for(int i=1,mn=1,mx=1,ok=1;i<=n;++i) {
      |                           ^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -