oj.uz

Submission #659921

# Submission time Handle Problem Language Result Execution time Memory
659921 2022-11-19T17:32:11 Z red24 Stove (JOI18_stove) C++14
100 / 100
 20 ms 3232 KB 
#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repr(i, a, b) for (int i = b; i >= a; i--)

#define pi pair<int, int>
#define ppi pair<pi, int>
#define pip pair<int, pi>
#define mp make_pair
#define ff first
#define ss second

#define vi vector<int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvi vector<vi>
#define pob pop_back
#define pb push_back

#define NO cout << "NO" << '\n'
#define YES cout << "YES" << '\n'
#define No cout << "No" << '\n'
#define Yes cout << "Yes" << '\n'
#define nl cout << '\n'
#define ok cerr << "OK" << endl
#define all(x) x.begin()+1, x.end()

void print(vi &a)
{
	rep(i, 1, a.size()-1) cout << a[i] << ' ';nl;
}

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

#define int long long
void solve()
{
	// CHECK IF PROGRAM HAS TESTCASES
	int n, k; cin >> n >> k;
	k--;
	
	vi a(n+1);
	rep(i, 1, n) cin >> a[i];
	vi d(1);
	rep(i, 2, n) d.pb(a[i] - a[i-1] - 1);

	sort(all(d), greater<int>());
	int res = 0;
	rep(i, 1, k) res += d[i];

	cout << a[n]-a[1]+1-res;
}

int32_t main()
{
	auto begin = std::chrono::high_resolution_clock::now();
	// FASTIO
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);



	int T = 1;
	//cin >> T;
	rep(i, 1, T)
	{
		//cout << "Case #" << i << ": ";
		solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

Compilation message

stove.cpp: In function 'void print(std::vector<int>&)':
stove.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i, a, b) for (int i = a; i <= b; i++)
......
   31 |  rep(i, 1, a.size()-1) cout << a[i] << ' ';nl;
      |      ~~~~~~~~~~~~~~~~                   
stove.cpp:31:2: note: in expansion of macro 'rep'
   31 |  rep(i, 1, a.size()-1) cout << a[i] << ' ';nl;
      |  ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 17 ms 3148 KB Output is correct
17 Correct 18 ms 3228 KB Output is correct
18 Correct 17 ms 3148 KB Output is correct
19 Correct 17 ms 3156 KB Output is correct
20 Correct 18 ms 3148 KB Output is correct
21 Correct 18 ms 3156 KB Output is correct
22 Correct 17 ms 3212 KB Output is correct
23 Correct 19 ms 3232 KB Output is correct
24 Correct 20 ms 3144 KB Output is correct