oj.uz

Submission #923877

# Submission time Handle Problem Language Result Execution time Memory
923877 2024-02-08T04:10:31 Z Webbly Stove (JOI18_stove) C++17
100 / 100
 15 ms 5336 KB 
// Problem: A. ��� ��������
// Contest: Codeforces - EDLIGHT CAMP IOI #1
// URL: https://codeforces.com/group/3wt9BX8ZwP/contest/500376/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
//                  Solution
//                    Webbly, 27.01.2023
//
//
//                    Arsen ne katai
//
//
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////



#include<bits/stdc++.h>

/**
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <time.h>
*/
//#pragma GCC optimize("O3")
//#pragma GCC optimize("fast-loops")
/**
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC target("avx")
*/
#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define flush cout.flush()

using namespace std;

const ll mod = (ll)1e9 + 7, mod3 = 998244353, inf = (ll)2e15, P = 31;

ll rnd(){
    ll x = rand();

    return rand() ^ x;
}

ll binpow (ll a, ll b){
    ll ans = 1;
    while(b){
        if (b & 1){
            ans *= a;

            ans %= mod;
        }

        b >>= 1;
        a *= a;

        a %= mod;
    }
    return ans;
}
ll gcd(ll a, ll b){
    return (b ? gcd(b, a % b) : a);
}
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

struct tr{
    ll four, seven, inc, dec;
};

struct T{
    ll l, r, val, ind;
};

ll n, m, k, a[500005], b[500005], p[500005];

string s;

void sarsen(){
    cin >> n >> k;
    
    ll ans = 0;
    
    vector <ll> v;
    
    for (ll i = 1; i <= n; i++){
    	cin >> a[i];
    	
    	if (i > 1) v.pb(a[i] - a[i - 1] - 1);
    }
    
    ans = a[n] - a[1] + 1;
    
    sort (all(v));
    
    ll r = n - 2;
    
    k--;
    
    while(r >= 0 && k--){
    	ans -= v[r--];
    }
    
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    //freopen("justforfood.in", "r", stdin);
    //freopen("justforfood.out", "w", stdout);

    ll TT = 1, tests = 1;

    //cin >> TT;

    while(TT--){
        //cout << "Case " << tests << ": ";

        sarsen();

        //tests++;
    }

    return 0;
}
/**

3 9 15 21 27 33 39 45

5 25 35 55 65 85 95


*/

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:164:16: warning: unused variable 'tests' [-Wunused-variable]
  164 |     ll TT = 1, tests = 1;
      |                ^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 15 ms 5336 KB Output is correct
17 Correct 14 ms 5244 KB Output is correct
18 Correct 14 ms 5332 KB Output is correct
19 Correct 14 ms 5336 KB Output is correct
20 Correct 15 ms 5336 KB Output is correct
21 Correct 15 ms 5336 KB Output is correct
22 Correct 15 ms 5336 KB Output is correct
23 Correct 14 ms 5336 KB Output is correct
24 Correct 14 ms 5296 KB Output is correct