답안 #502891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
502891 2022-01-06T17:47:28 Z Kirill_Maglysh Stove (JOI18_stove) C++17
100 / 100
23 ms 2960 KB
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

#define fori(n) for(int i = 0; i < n; ++i)
#define forj(n) for(int j = 0; j < n; ++j)
#define forr(n) for(int i = n - 1; i >= 0; --i)
#define forEach(array) for(auto &item : array)
#define printSpace(a) cout << a << " "
#define printSpace2(a, b) cout << a << " " << b << " "
#define printSpace3(a, b, c) cout << a << " " << b << " " << c << " "
#define printSpace4(a, b, c, d) cout << a << " " << b << " " << c << " " << d <<" "
#define printSpace5(a, b, c, d, e) cout << a << " "<< b << " " << c << " " << d <<" " << e << " "
#define printSpace6(a, b, c, d, e, f) cout << a << " "<< b << " " << c << " " << d <<" "<< e << " " << f << " "
#define printLn(n) cout << n << '\n'
#define printNL() cout <<'\n'
#define print(n) cout << n

using namespace std;

typedef long long ll;

struct CompressedLetter {
    ll num;
    char letter;
};

ll readLL();

string readStr();

void resolve();

void resolveTest();

bool isPrime(ll n);

vector<bool> detectPrimes(ll n);

ll minPosInArray(const vector<ll> &nums);

ll maxPosInArray(const vector<ll> &nums);

ll minValInArray(const vector<ll> &nums);

ll maxValInArray(const vector<ll> &nums);

vector<ll> calcPrefixSum(const vector<ll> &nums);

vector<ll> calcSuffixSum(const vector<ll> &nums);

vector<ll> getDigits(ll n);

ll sumNumRange(ll start, ll finish);

ll calcNumLength(ll n);

vector<CompressedLetter> processCompressedStr(const string &str);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    resolve();

    return 0;
}

void resolve() {
    ll pointNum = readLL();
    ll possibleDelete = readLL() - 1;
    if (pointNum == 1) {
        printLn(1);
        return;
    }

    vector<ll> points(pointNum);
    forEach(points) {
        item = readLL();
    }

    sort(points.begin(), points.end());

    ll res = points[pointNum - 1] - points[0] + 1;
    vector<ll> segments(pointNum - 1);
    for (ll i = 1; i < pointNum; ++i) {
        segments[i - 1] = points[i] - points[i - 1] - 1;
    }

    sort(segments.begin(), segments.end());
    possibleDelete = min(possibleDelete, (ll) segments.size());
    for (ll i = (ll) segments.size() - 1; possibleDelete; --i, --possibleDelete) {
        res -= segments[i];
    }

    printLn(res);
}

ll readLL() {
    ll num;
    cin >> num;
    return num;
}

string readStr() {
    string str;
    cin >> str;
    return str;
}

bool isPrime(ll n) {
    if (n == 0 || n == 1) {
        return false;
    }

    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

vector<bool> detectPrimes(ll n) {
    vector<bool> nums(n + 1, true);
    nums[0] = false;
    nums[1] = false;
    for (ll i = 2; i <= n; ++i) {
        if (nums[i]) {
            for (ll j = i * i; j <= n; j += i) {
                nums[j] = false;
            }
        }
    }

    return nums;
}

ll minPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] > nums[i]) {
            pos = i;
        }
    }

    return pos;
}

ll maxPosInArray(const vector<ll> &nums) {
    ll pos = 0;
    for (ll i = 1; i < nums.size(); ++i) {
        if (nums[pos] < nums[i]) {
            pos = i;
        }
    }

    return pos;
}

vector<ll> getDigits(ll n) {
    vector<ll> digits;
    while (n > 0) {
        digits.push_back(n % 10);
        n /= 10;
    }

    return digits;
}

vector<ll> calcPrefixSum(const vector<ll> &nums) {
    vector<ll> prefix(nums.size());
    prefix[0] = nums[0];
    for (ll i = 1; i < nums.size(); ++i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    return prefix;
}

vector<ll> calcSuffixSum(const vector<ll> &nums) {
    vector<ll> suffix(nums.size());
    suffix[nums.size() - 1] = nums[nums.size() - 1];
    for (ll i = (ll) nums.size() - 2; i >= 0; --i) {
        suffix[i] = suffix[i + 1] + nums[i];
    }

    return suffix;
}

ll sumNumRange(ll start, ll finish) {
    if (finish < start) {
        return 0;
    }

    if (start > 1) {
        return sumNumRange(1, finish) - sumNumRange(1, start - 1);
    }

    if (finish % 2 == 1L) {
        return sumNumRange(1, finish - 1) + finish;
    } else {
        return finish * (finish + 1) / 2;
    }
}

vector<CompressedLetter> processCompressedStr(const string &str) {
    vector<CompressedLetter> res;
    ll pos = 0;

    while (pos < str.length()) {
        ll numLength = 0;
        while ('0' <= str[pos] && str[pos] <= '9') {
            numLength++;
            pos++;
        }

        if (numLength == 0) {
            res.push_back({1, str[pos]});
        } else {
            res.push_back({stoi(str.substr(pos, numLength)), str[pos + numLength]});
        }

        pos += numLength + 1;
    }

    return res;
}

ll calcNumLength(ll n) {
    ll res = 0;
    while (n > 0) {
        n /= 10;
        res++;
    }

    return res;
}

ll minValInArray(const vector<ll> &nums) {
    return nums[minPosInArray(nums)];
}

ll maxValInArray(const vector<ll> &nums) {
    return nums[maxPosInArray(nums)];
}

Compilation message

stove.cpp: In function 'll minPosInArray(const std::vector<long long int>&)':
stove.cpp:144:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
stove.cpp: In function 'll maxPosInArray(const std::vector<long long int>&)':
stove.cpp:155:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
stove.cpp: In function 'std::vector<long long int> calcPrefixSum(const std::vector<long long int>&)':
stove.cpp:177:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for (ll i = 1; i < nums.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~
stove.cpp: In function 'std::vector<CompressedLetter> processCompressedStr(const string&)':
stove.cpp:214:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |     while (pos < str.length()) {
      |            ~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 312 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 312 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 312 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 20 ms 2740 KB Output is correct
17 Correct 19 ms 2864 KB Output is correct
18 Correct 18 ms 2736 KB Output is correct
19 Correct 20 ms 2752 KB Output is correct
20 Correct 18 ms 2756 KB Output is correct
21 Correct 18 ms 2748 KB Output is correct
22 Correct 23 ms 2960 KB Output is correct
23 Correct 19 ms 2764 KB Output is correct
24 Correct 19 ms 2756 KB Output is correct