oj.uz

Submission #779688

# Submission time Handle Problem Language Result Execution time Memory
779688 2023-07-11T16:30:58 Z RonTheprogrammer Stove (JOI18_stove) C++17
100 / 100
 18 ms 1864 KB 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <set>
#include <limits>
#include <string>
#include <deque>
#include <cassert>
#include <math.h>
#include <list>
#include<numeric>
#include<map>
#include<set>
//#include <bits/stdc++.h>

typedef long long ll;
const int maxn = 2e5 + 5;
const int MOD =(1e9 + 7);
const int INF = 1e9+1;
#define srt(a) sort(a.begin(),a.end());
#define rev(a) reverse(a.begin(),a.end());
#define eb(a) emplace_back(a);
#define nl "\n"

//typedef  {int, int} p;

using  namespace std;
/**/
struct DSU
{
	vector<int>parent;
	vector<int>size;

	void dsuinit(int n)
	{
		parent.resize(n);
		size.resize(n);
		for (int i = 0; i < n; i++)
		{
			make_set(i);
		}
	}

	int find_set(int v) {
		if (v == parent[v])
			return v;
		return parent[v] = find_set(parent[v]);
	}

	void make_set(int v)
	{
		parent[v] = v;
		size[v] = 1;
	}

	bool unite(int a, int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (size[a] < size[b])
				swap(a, b);
			parent[b] = a;
			size[a] += size[b];
			return true;
		}
		return false;
	}
};
int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e - 1);
}
int __gcd(int a, int b)
{
	if (b > a)
	{
		swap(a, b);
	}
	if (a % b == 0)
		return b;
	return __gcd(a, a % b);
}
ll __lcm(int a, int b)
{
	return ((ll)a *(ll)  b) / __gcd(a, b);
}
struct price {
	int cost, cnt;
	bool  operator < (const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
	bool compare(const price& other) const
	{
		if (cost == other.cost)
			return cnt < other.cnt;
		return  cost < other.cost;
	}
};
struct range {
	int l, r, thief, change;
	bool operator <(const range& other) const
	{
		if (l == other.l)
			return r < other.r;
		return l < other.l;
	}

};
struct hole {
	int c1,  c2;
	ll w;
};


void solve()
{
	int n, k; cin >> n >> k;
	int mx, mn, last;
	vector<int>dif;
	for (int i = 0; i < n; i++)
	{
		int t; cin >> t;
		if (i == 0)
			mn = t;
		if (i ==n-1)
			mx = t+1;
		if (i > 0)
			dif.emplace_back(t - last - 1);
		last = t;
	}
	srt(dif);
	rev(dif);
	int ans = mx - mn;
	for (int i = 0; i < k - 1; i++)
	{
		ans -= dif[i];
	}
	cout << ans << nl;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	//freopen("pcb.in", "r", stdin);
	//freopen("pcb.out", "w", stdout);
	int t=1;

	while (t--)
		solve();
	return 0;

}
/**
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4




*/

Compilation message

stove.cpp: In function 'void solve()':
stove.cpp:139:6: warning: 'mn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |  int ans = mx - mn;
      |      ^~~
stove.cpp:139:6: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 360 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 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 360 KB Output is correct
16 Correct 15 ms 1856 KB Output is correct
17 Correct 14 ms 1832 KB Output is correct
18 Correct 14 ms 1740 KB Output is correct
19 Correct 18 ms 1840 KB Output is correct
20 Correct 14 ms 1864 KB Output is correct
21 Correct 14 ms 1860 KB Output is correct
22 Correct 15 ms 1836 KB Output is correct
23 Correct 14 ms 1832 KB Output is correct
24 Correct 15 ms 1828 KB Output is correct