Submission #3076442


Source Code Expand

Copy
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N, K;
    std::cin >> N >> K;

    std::vector<int64_t> posX;
    std::vector<int64_t> negX;
    for (decltype(N) i = 0; i < N; ++i) {
        int64_t t;
        std::cin >> t;
        if (t > 0) {
            posX.push_back(t);
        }
        else if (t < 0) {
            negX.push_back(t* (-1));
        }
        else {
            // 0
            K--;
        }
    }

    std::sort(std::begin(negX), std::end(negX));


    std::vector<int64_t> cands;

    #if 0
    // 片側通行
    if (posX.size() >= K) {
        cands.push_back(posX[K-1]);
    }

    if (negX.size() >= K) {
        cands.push_back(negX[K-1]);
    }
    #endif


    // 折り返し
    int64_t ans = INT64_MAX;
    for (int64_t i = 0; i <= std::min(posX.size(), (size_t)K); ++i) {
        // i 個 プラス側
        int64_t t = 0;
        if (i > 0) {
            t += posX[i-1] * 2;

        }

        if (i == K) {
            // 折り返しなし
            ans =std::min(ans, t);

        }
        else {
            // K - i 個、マイナス側
            if (negX.size() >= K - i) {
                t += negX[K-i -1];

                ans =std::min(ans, t);
            }
        }

    }
    cands.push_back(ans);

    ans = INT64_MAX;
    for (int64_t i = 0; i <= std::min(negX.size(), (size_t)K); ++i) {
        int64_t t = 0;
        if (i > 0) {
            t += negX[i-1] * 2;
        }
        if (i == K) {
            // 折り返しなし
            ans =std::min(ans, t);
        }
        else {
            if (posX.size() >= K - i) {
                t += posX[K-i -1];
                ans =std::min(ans, t);
            }
        }
    }

    cands.push_back(ans);

    std::cout << *std::min_element(cands.begin(), cands.end()) << std::endl;

    return 0;
}

Submission Info

Submission Time
Task C - Candles
User sumomoneko
Language C++14 (GCC 5.4.1)
Score 300
Code Size 2446 Byte
Status AC
Exec Time 43 ms
Memory 1656 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 4
AC × 12
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 40 ms 1400 KB
1_01.txt AC 40 ms 1400 KB
1_02.txt AC 43 ms 1400 KB
1_03.txt AC 43 ms 1400 KB
1_04.txt AC 38 ms 1400 KB
1_05.txt AC 38 ms 1400 KB
1_06.txt AC 39 ms 1656 KB
1_07.txt AC 41 ms 1524 KB