제출 #1049776

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

stove

#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;
} 

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50