Submission #1105148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105148		monaxia	Stove (JOI18_stove)	C++17	100 / 100	101 ms	7684 KiB

stove

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll LIMIT = 2e3 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random (int l, int r){return uniform_int_distribution <int> (l, r)(rng);}

struct ranges{
    int range, i1, i2;
};

bool comp(ranges& a, ranges& b){
    return a.range < b.range;
}

void solve(){
    int n, k, ans = 0;
    cin >> n >> k;

    vector <int> a(n + 1);
    vector <ranges> init;
    set <pair <int, int>> range;

    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(i > 1) init.pb({a[i] - a[i - 1] - 1, i - 1, i});
        range.insert({a[i], a[i]});
    }

    sort(all(init), comp);

    for(auto& w : init){
        if(range.size() == k) break;

        auto it2 = range.lower_bound({a[w.i2], a[w.i2]});
        auto it1 = it2;
        it1 --;

        auto temp1 = *it2, temp2 = *it1;

        range.insert({it1 -> fr, it2 -> sc});
        range.erase(temp1);
        range.erase(temp2);
    }

    for(auto& x : range){
        ans += (x.sc - x.fr + 1);
    }

    cout << ans;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("blank.inp", "r")){
        freopen("blank.inp", "r", stdin);
        freopen("blank.out", "w", stdout);
    }
    
    // cout << 1; return 0;

    ll n = 1;

    // cin >> n;

    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

stove.cpp: In function 'void solve()':
stove.cpp:44:25: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if(range.size() == k) break;
      |            ~~~~~~~~~~~~~^~~~
stove.cpp: In function 'int main()':
stove.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("blank.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("blank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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