Submission #8948968
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] -= (r - l) * (lli)(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
2019-12-14 15:51:18+0900
Task
E - guruguru
User
arounderstand
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
2516 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
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
WA
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
WA
2 ms
512 KB
rnd3.txt
WA
3 ms
512 KB
rnd4.txt
WA
8 ms
512 KB
rnd5.txt
WA
1 ms
256 KB
rnd6.txt
WA
1 ms
256 KB
rnd7.txt
WA
2 ms
640 KB
rnd8.txt
WA
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