oj.uz

답안 #411661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411661 2021-05-25T17:06:57 Z nichke Stove (JOI18_stove) C++14
100 / 100
 31 ms 6288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n, k;
vector<int> diff;
vector<pair<int, int>> a;
vector<pair<int, int>> b;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l; r = l + 1;
		a.push_back({l, r});
	}
	sort(a.begin(), a.end());
	int l = a[0].first, r = a[0].second;
	for (int i = 1; i < a.size(); i++) {
		if (a[i].first <= a[i - 1].second) {
			r = max(a[i].second, r);
		} else {
			b.push_back({l, r});
			l = a[i].first;
			r = a[i].second;
		}
	}
	b.push_back({l, r});
	for (int i = 1; i < b.size(); i++) {
		diff.push_back(b[i].first - b[i - 1].second);
	}
	sort(diff.begin(), diff.end());
	int cnt = 0;
	int res = 0;
	for (int i = 0; i < b.size(); i++) {
		res += b[i].second - b[i].first;
		cnt++;
	}
	int j = 0;
	while (cnt > k) {
		cnt--;
		res += diff[j++];
	}
	cout << res << '\n';
	return 0;
}

Compilation message

stove.cpp: In function 'int main()':
stove.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 1; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
stove.cpp:32:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 1; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
stove.cpp:38:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 456 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 456 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 28 ms 6168 KB Output is correct
17 Correct 29 ms 6208 KB Output is correct
18 Correct 29 ms 6132 KB Output is correct
19 Correct 29 ms 6288 KB Output is correct
20 Correct 28 ms 6104 KB Output is correct
21 Correct 30 ms 6176 KB Output is correct
22 Correct 28 ms 6280 KB Output is correct
23 Correct 31 ms 6116 KB Output is correct
24 Correct 28 ms 6132 KB Output is correct