Tutorial for Codeforces 747D - Winter Is Coming

Solution #

First, let’s force Vasya to change tire on everyday with negative temperature (even on consecutive days) so she will change tire for $2\cdot cnt$ time where $cnt$ is the number of days with negative temperature. If $cnt>k$ obviously the answer is -1, otherwise the winter tire can still last for some extra days. Now let’s see if we can use the winter tire on days with non-negative temperature. We can sort all the length of the consecutive days with non-negative temperature, so we can greedily use winter tires on those segments. For each segment we use, we save tire change twice. Finally let’s see if we can use the winter tire until the last day after the last negative-temperature day.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template<typename... Args> void rd(Args&... args) {((cin >> args), ...);}
template<typename... Ar> void wr(Ar... ar) {((cout<<ar<<" "),...);cout<<endl;}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int> a(n),neg;
    forn(i,n){
        cin>>a[i];
        if(a[i]<0) neg.push_back(i);
    }
    if(neg.empty()) return cout<<0,0;
    if(neg.size()>k) return cout<<-1,0;
    vector<int> xs;
    for(int i=1;i<(int)size(neg);i++) xs.push_back(neg[i]-neg[i-1]-1);
    sort(all(xs));
    int ans=int(size(neg))*2;
    k-=size(neg);
    for(auto i:xs){
        if(k>=i){
            k-=i;
            ans-=2;
        }else break;
    }
    if(n-neg.back()-1<=k) ans--;
    cout<<ans;
    return 0;
}