#616815 (C++17) No.1391 ±1 Abs Sum

提出ソース

結果

問題	No.1391 ±1 Abs Sum
ユーザー	Cyanmond
提出日時	2021-02-12 21:57:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	6,411 bytes
コンパイル時間	2,159 ms
コンパイル使用メモリ	201,512 KB
実行使用メモリ	4,688 KB
最終ジャッジ日時	2023-09-27 03:54:08
合計ジャッジ時間	5,294 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	AC	81 ms 4,684 KB
testcase_12	AC	62 ms 4,376 KB
testcase_13	AC	75 ms 4,484 KB
testcase_14	AC	46 ms 4,376 KB
testcase_15	AC	48 ms 4,380 KB
testcase_16	AC	62 ms 4,380 KB
testcase_17	AC	54 ms 4,376 KB
testcase_18	AC	73 ms 4,420 KB
testcase_19	AC	54 ms 4,380 KB
testcase_20	AC	79 ms 4,568 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	80 ms 4,616 KB
testcase_32	AC	42 ms 4,380 KB
testcase_33	AC	47 ms 4,380 KB
testcase_34	AC	77 ms 4,628 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	87 ms 4,688 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma region library
#ifdef __GNUC__
//#pragma GCC target("avx")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#endif
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
// #include <boost/range/irange.hpp>
// using boost::irange;
#pragma region Macros
#define itrall(x) std::begin(x), std::end(x)
#define FOR(A,...) std::for_each(std::begin(A), std::end(A), [&]__VA_ARGS__ )
using i64 = long long;
using cint = const int;
using ci64 = const long long;
using uint = unsigned int;
using u64 = unsigned long long;
using cuint = const unsigned int;
using cu64 = const unsigned long long;
#pragma endregion
#ifndef CnM_library
#define debug(x)
constexpr int dx[] = { 1, 0, -1, 0 };
constexpr int dy[] = { 0, 1, 0, -1 };
template <class T> constexpr T INF_func() { return std::numeric_limits<T>::max(); }
template <> constexpr int INF_func() { return 1001001001; }
template <> constexpr long long INF_func() { return 1501501501501501501ll; }
template <> constexpr unsigned int INF_func() { return 1001001001; }
template <> constexpr unsigned long long INF_func() { return 1501501501501501501ll; }
template <class T> constexpr T INF = INF_func<T>();
constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;
#define elif else if
#define len(T) (int)(T).size()
template <class T, class U, class Comp = std::less<>>
constexpr inline bool chmin(T& xmin, const U& x, Comp comp = {}) noexcept { return comp(x, xmin) ? xmin = x, true : false; }
template <class T, class U, class Comp = std::less<>>
constexpr inline bool chmax(T& xmax, const U& x, Comp comp = {}) noexcept { return comp(xmax, x) ? xmax = x, true : false; }
namespace lib {
    template <class T, class U> inline T Pow(T A, U B) { T res(1); while (B) { if (B & 1) res *= A; A *= A; B >>= 1; } return res; }
    inline long long gcd(long long A, long long B) { while (B) { const long long C = A; A = B; B = C % B; } return A; }
    inline long long lcm(const long long A, const long long B) { return A / gcd(A, B) * B; }
    inline long long extgcd(long long A, long long B, long long& X, long long& Y) {
        long long D = A; if (B != 0) { D = extgcd(B, A % B, Y, X); Y -= (A / B) * X; return D; }
        else { X = 1; Y = 0; return A; }
    }
    inline long long modpow(long long A, long long B, const long long MOD) {
        long long res(1); while (B) { if (B & 1) res *= A, res %= MOD; A *= A; A %= MOD; B >>= 1; } return res;
    }
    template <class T> inline T inverse(T A, const T M) {
        T B = M, U = 1, V = 0; while (B) { T t = A / B; A -= t * B; std::swap(A, B); U -= t * V; std::swap(U, V); }
        U %= M; return U < 0 ? U += M, U : U;
    }
}
template <class T> inline void read(T& Tar) { std::cin >> Tar; return; }
template <class T, class... Ts> inline void read(T& Tar, Ts&... ts) { std::cin >> Tar; read(ts...); return; }
template <class T> inline void print(T Tar) { std::cout << Tar; return; }
template <class T, class... Ts> inline void print(T Tar, Ts... ts) { std::cout << Tar; print(ts...); return; }
#endif
#pragma endregion
class ProCon_all_init {
    static constexpr bool float_fixed = false;
    static constexpr int ios_perc = 15;
    static constexpr bool ios_fast = false;
    static constexpr bool flush_auto = false;
public:
    ProCon_all_init() {
        if (ios_fast) { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); }
        if (float_fixed) { std::cout << std::fixed << std::setprecision(ios_perc); }
        if (flush_auto) { std::cout << std::unitbuf; }
    }
} PROCON_ALL_INIT_;
template <class T> std::vector<int> arg_sort(std::vector<T>& v, bool isgreater = false) {
    std::vector<int> res(v.size());
    std::iota(res.begin(), res.end(), 0);
    std::sort(res.begin(), res.end(), [&](int i, int j) {return isgreater ? v[i] > v[j] : v[i] < v[j]; });
    return res;
}
template <class T = long long> class range {
    const T First, Last;
public:
    class iter {
        friend range;
        T itr;
        constexpr iter(T x) noexcept : itr(x) {}
    public:
        void operator ++() noexcept { itr++; }
        constexpr T operator *() const noexcept { return itr; }
        constexpr bool operator != (const iter x) const noexcept { return itr != x.itr; }
    };
    constexpr range(const T F, const T L) noexcept : First(F), Last(std::max(F, L)) {}
    constexpr range(const T L) noexcept :First(0), Last(std::max((T)0, L)) {}
    constexpr iter begin() const noexcept { return iter(First); }
    constexpr iter end() const noexcept { return iter(Last); }
    /*
    * range(l, r) -> [l, r)
    * l < r
    */
};
template <class T = long long> class revge {
    const T First, Last;
public:
    class reviter {
        friend revge;
        T itr;
        constexpr reviter(T x) noexcept : itr(x) {}
    public:
        void operator ++() noexcept { itr--; }
        constexpr T operator *() const noexcept { return itr; }
        constexpr bool operator != (const reviter x) const noexcept { return itr != x.itr; }
    };
    constexpr revge(const T F, const T L) noexcept : First(std::max(L - 1, F)), Last(L) {}
    constexpr revge(const T F) noexcept : First(std::max((T)0, F)), Last(0) {}
    constexpr reviter begin() const noexcept { return reviter(First); }
    constexpr reviter end() const noexcept { return reviter(Last - 1); }
    /*
    * revge(r, l) -> [l, r] reverse
    * l >= r
    */
};

class Abs_sum {
public:
    i64 N, K;
    std::vector<i64> A;

    Abs_sum() {
        read(N, K);
        A.resize(N);
        for (auto& e : A) read(e);
    }

    void solve() {
        i64 ans = INF<i64>;
        // right

        auto solve_sub = [&]() {
            i64 now = 0;
            for (int i : range(N)) {
                i64 C = abs(A[0] - A[i]);
                now += (i < K ? C : -C);
            }
            for (int i : range(N - 1)) {
                chmin(ans, now);
                i64 C1 = std::min(K, i + 1ll);
                i64 C2 = std::max(0ll, i + 1 - K);
                i64 S = abs(A[i + 1] - A[i]);
                now += C1 * S;
                now -= (K - C1) * S;
                now -= C2 * S;
                now += (N - K - C2) * S;
            }
            chmin(ans, now);
        };
        solve_sub();
        std::reverse(itrall(A));
        solve_sub();
        print(ans, '\n');
    }
};

int main(void) {
    Abs_sum solver;
    solver.solve();

    return 0;
}

yukicoder

結果

テストケース

ソースコード