Submission #8950299


Source Code Expand

#include <iostream>
#include <limits>
#include <cfenv>
#include <cmath>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <tuple>
#include <queue>
#include <vector>
#include <cmath>
#include <random>
#include <math.h>
#include <list>
#include <random>
#include <functional>


#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))
#define ALL(TheArray) TheArray.begin(), TheArray.end()

using lli = long long int;
using pii = std::pair<int, int>;

template <class T> inline bool chmax(T& a, T b){
    if(a < b){a = b; return true;}
    return false;
}
template <class T> inline bool chmin(T& a, T b){
    if(a > b){a = b; return true;}
    return false;
}


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

constexpr int N = 1e5;
std::array<int, N> A;
std::array<int, N+1> Count, Wait;
std::array<lli, N+1> S;

int main(void){
    int n, m; scanf("%d%d", &n, &m);
    REP(i, n) scanf("%d", &A[i]), A[i]--;
    // a -> b に遷移する場合 | お気に入り設定でどれだけ変化するか考えよう
    // a < b の場合 : a < j ≤ b なる全ての j に関してコストが j - a - 1 だけ減少する
    // a > b の場合 : 1, a < j < m なるすべての j に関してコストが j - a - 1だけ減少する
    //               2, a < j + m ≤ b + m なる全ての j に関して ( : 0 ≤ j < m)
    //                     コストが j + m - a - 1 だけ減少する
    lli T = 0;
    for(int i = 1; i < n; ++i){
        if(A[i-1] < A[i]){
            int l = A[i-1] + 2;
            int r = A[i] + 1;
            Count[l]++; Count[r]--;
            Wait[r] += r - l;
            T += A[i] - A[i-1];
        }
        else{
            int l = A[i-1] + 2;
            int r = m;
            Count[l]++; Count[r]--;
            Wait[r] += r - l;
            l = 0; r = A[i] + 1;
            Count[l]++; Count[r]--;
            Wait[r] += r - l;
            S[l] += m - A[i-1] - 2;
            S[r] -= m - A[i-1] - 2;
            T += (A[i] + m - A[i-1]);
        }
    }

    REP(i, m) Count[i+1] += Count[i], S[i+1] += S[i];


    REP(i, m) Count[i+1] += Count[i] - Wait[i+1], S[i+1] += Count[i+1];
    lli mx = 0;
    REP(i, m) if(mx < S[i]) mx = S[i];
    printf("%lld\n", T - mx);
    
    return 0;
}

Submission Info

Submission Time
Task E - guruguru
User arounderstand
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2501 Byte
Status WA
Exec Time 12 ms
Memory 2176 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d%d", &n, &m);
                                    ^
./Main.cpp:50:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP(i, n) scanf("%d", &A[i]), A[i]--;
                                         ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 2
AC × 17
WA × 5
Set Name Test Cases
Sample sample1.txt, sample2.txt
All half0.txt, half1.txt, half2.txt, half3.txt, half4.txt, min_m.txt, min_n.txt, mx0.txt, mx1.txt, mx2.txt, rnd0.txt, rnd1.txt, rnd2.txt, rnd3.txt, rnd4.txt, rnd5.txt, rnd6.txt, rnd7.txt, rnd8.txt, rnd9.txt, sample1.txt, sample2.txt
Case Name Status Exec Time Memory
half0.txt WA 4 ms 1024 KB
half1.txt AC 3 ms 1536 KB
half2.txt AC 6 ms 1408 KB
half3.txt AC 9 ms 1152 KB
half4.txt WA 9 ms 1792 KB
min_m.txt AC 1 ms 256 KB
min_n.txt AC 2 ms 1408 KB
mx0.txt WA 12 ms 2176 KB
mx1.txt WA 12 ms 2176 KB
mx2.txt WA 12 ms 2176 KB
rnd0.txt AC 1 ms 512 KB
rnd1.txt AC 1 ms 384 KB
rnd2.txt AC 2 ms 512 KB
rnd3.txt AC 3 ms 512 KB
rnd4.txt AC 8 ms 512 KB
rnd5.txt AC 1 ms 256 KB
rnd6.txt AC 1 ms 256 KB
rnd7.txt AC 1 ms 640 KB
rnd8.txt AC 2 ms 384 KB
rnd9.txt AC 1 ms 384 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB