結果
| 問題 | No.838 Noelちゃんと星々3 |
| ユーザー |
 laoidn
|
| 提出日時 | 2023-04-23 11:27:03 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,900 bytes |
| コンパイル時間 | 4,838 ms |
| コンパイル使用メモリ | 240,452 KB |
| 実行使用メモリ | 19,072 KB |
| 最終ジャッジ日時 | 2024-04-25 08:41:08 |
| 合計ジャッジ時間 | 6,603 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 2 ms
5,376 KB |
| testcase_17 | AC | 2 ms
5,376 KB |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | AC | 2 ms
5,376 KB |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 2 ms
5,376 KB |
| testcase_25 | AC | 2 ms
5,376 KB |
| testcase_26 | AC | 2 ms
5,376 KB |
| testcase_27 | AC | 2 ms
5,376 KB |
| testcase_28 | WA | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <iostream>
#include <vector>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define fore(i, a) for (auto &i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT \
std::ios::sync_with_stdio(false); \
std::cin.tie(0);
template <class T>
inline T CHMAX(T &a, const T b) {
return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T &a, const T b) {
return a = (a > b) ? b : a;
}
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <deque> // deque
#include <iostream> // cout, endl, cin
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <string> // string, to_string, stoi
#include <tuple> // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility> // pair, make_pair
#include <vector> // vector
using namespace std;
ll GCD(ll m, ll n) {
// ベースケース
if (n == 0) return m;
// 再帰呼び出し
return GCD(n, m % n);
}
ll minlong = 0;
long long Power(long long a, long long b, long long m) {
long long p = a, Answer = 1;
for (int i = 0; i < 63; i++) {
ll wari = (1LL << i);
if ((b / wari) % 2 == 1) {
Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき
}
p = (p * p) % m;
}
return Answer;
}
// a ÷ b を m で割った余りを返す関数
long long Division(long long a, long long b, long long m) {
return (a * Power(b, m - 2, m)) % m;
}
// nCr mod 1000000007 を返す関数
long long nCk(ll n, ll r) {
const long long M = 1000000007;
// 手順 1: 分子 a を求める
long long a = 1;
for (int i = 1; i <= n; i++) a = (a * i) % M;
// 手順 2: 分母 b を求める
long long b = 1;
for (int i = 1; i <= r; i++) b = (b * i) % M;
for (int i = 1; i <= n - r; i++) b = (b * i) % M;
// 手順 3: 答えを求める
return Division(a, b, M);
}
using Interval = pair<ll, ll>;
// nCk mint を返す関数。
ll modnCk(ll n, ll r) {
ll a = 1;
for (ll i = n; i > n - r; i--) {
a *= i;
a /= n + 1 - i;
}
return a;
}
// 終点時間でsortをかけるのに必要(区間スケジューリング問題など)
bool cmp(const Interval &a, const Interval &b) { return a.second < b.second; }
vll dycstra(vector<vector<pair<ll, ll>>> G, ll N, ll K) {
vb kaku(N, false);
vll cur(N, INF);
cur[K] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
Q.push(make_pair(cur[K], K));
while (!Q.empty()) {
ll pos = Q.top().second;
Q.pop();
if (kaku[pos]) continue;
kaku[pos] = true;
for (ll i = 0; i < G[pos].size(); i++) {
ll nex = G[pos][i].first;
ll cost = G[pos][i].second;
if (cur[nex] > cur[pos] + cost) {
cur[nex] = cur[pos] + cost;
Q.push(make_pair(cur[nex], nex));
}
}
}
return cur;
}
template <class T>
struct BIT {
int n; // 要素数
vector<T> bit[300000]; // データの格納先
BIT(int n_) { init(n_); }
void init(int n_) {
n = n_ + 1;
for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
}
void add_sub(int p, int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[p][idx] += x;
}
}
void add(int l, int r, T x) { // [l,r) に加算
add_sub(0, l, -x * (l - 1));
add_sub(0, r, x * (r - 1));
add_sub(1, l, x);
add_sub(1, r, -x);
}
T sum_sub(int p, int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[p][idx];
}
return s;
}
T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
// sum'(i)=sum(i)-x(l-i)+xi(sum'(i)は加算後の合計値sum(i)測酸前の合計値)
T query(int l, int r) { return sum(r - 1) - sum(l - 1); }
// 任意の区間を計算することが可能これは[l,r)の区間和を計算している。
int lower_bound(T w) { // a_1 + a_2 + ... + a_x >= w となるような最小の x
// を求める(ただし a_i >= 0)
if (w <= 0) {
return 0;
} else {
int x = 0, r = 1;
while (r < n) r = r << 1;
for (int len = r; len > 0;
len = len >> 1) { // 長さlenは1段下るごとに半分に
if (x + len < n && bit[x + len] < w) { // 採用するとき
w -= bit[x + len];
x += len;
}
}
return x + 1;
}
}
};
vll BFS(vvll &G, ll &x) {
vll cut(G.size(), INF);
queue<ll> Q;
Q.push(x);
cut[x] = 0;
while (!Q.empty()) {
ll a = Q.front();
Q.pop();
rep(i, G[a].size()) {
if (cut[G[a][i]] > cut[a] + 1) {
cut[G[a][i]] = cut[a] + 1;
Q.push(G[a][i]);
}
}
}
return cut;
}
template <class Abel>
struct UnionFind {
vector<int> par;
vector<int> rank;
vector<Abel> diff_weight;
vector<int> siz;
UnionFind(int n = 1, Abel SUM_UNITY = 0) { init(n, SUM_UNITY); }
void init(int n = 1, Abel SUM_UNITY = 0) {
par.resize(n);
rank.resize(n);
diff_weight.resize(n);
siz.resize(n);
for (int i = 0; i < n; ++i)
par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY, siz[i] = 1;
}
int root(int x) {
if (par[x] == x) {
return x;
} else {
int r = root(par[x]);
diff_weight[x] +=
diff_weight[par[x]]; // 累積和をとることで重みがつけられる。
return par[x] = r;
}
}
Abel weight(int x) {
root(x); // 経路圧縮
return diff_weight[x]; // 重みを返す
}
bool issame(int x, int y) {
return root(x) == root(y); // 通常時も同じ
}
// weight(y) - weight(x) = w となるように merge する
bool merge(int x, int y, Abel w) {
// x と y それぞれについて、 root との重み差分を補正
w += weight(x);
w -= weight(y);
// x と y の root へ (x と y が既につながっていたら false を返すようにした)
x = root(x);
y = root(y);
if (x == y) return false;
// rank[x] >= rank[y] となるように x と y を swap (それに合わせて w
// も符号反転します)これはUnion by
// rankと呼ばれ根の高さをO(logN)で抑えられる手法である。
if (rank[x] < rank[y]) swap(x, y), w = -w;
// y (のroot) を x (のroot)
// の下にくっつける(高さが低い方の根付き木を高いほうに併合する)
if (rank[x] == rank[y]) ++rank[x];
siz[x] += siz[y];
par[y] = x;
// x が y の親になるので、x と y の差分を diff_weight[y] に記録
diff_weight[y] = w;
return true;
}
Abel diff(int x, int y) { return weight(y) - weight(x); }
int size(int x) { return siz[root(x)]; }
};
class SegmentTree {
public:
int dat[600000], siz = 1;
// 要素 dat の初期化を行う（最初は全部ゼロ）
void init(int N) {
siz = 1;
while (siz < N) siz *= 2;
for (int i = 1; i < siz * 2; i++) dat[i] = 0;
}
// クエリ 1 に対する処理
void update(int pos, int x) {
pos = pos + siz - 1;
dat[pos] = x;
while (pos >= 2) {
pos /= 2;
dat[pos] = max(dat[pos * 2], dat[pos * 2 + 1]);
}
}
// クエリ 2 に対する処理
// u は現在のセル番号、[a, b) はセルに対応する半開区間、[l, r)
// は求めたい半開区間
int query(int l, int r, int a, int b, int u) {
if (r <= a || b <= l) return -1000000000; // 一切含まれない場合
if (l <= a && b <= r) return dat[u]; // 完全に含まれる場合
int m = (a + b) / 2;
int AnswerL = query(l, r, a, m, u * 2);
int AnswerR = query(l, r, m, b, u * 2 + 1);
return max(AnswerL, AnswerR);
}
};
void Yes(bool b) {
if (b)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
vector<long long> yaku(long long n) {
vector<long long> ret;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end()); // 昇順に並べる
return ret;
}
int main() {
ll N, M, K, a, b, c;
string S, T;
cin >> N;
vll A(N);
rep(i, N) { cin >> A[i]; }
vvvll dp(N, vvll(2, vll(2, INF)));
dp[0][0][0] = 0;
reps(i, 1, N) { dp[i][0][0] = min(dp[i - 1][1][0] , dp[i - 1][1][1]);
dp[i][1][0] = dp[i-1][0][0] + abs(A[i] - A[i - 1]);
if(i>1){
a = abs(A[i - 1] - A[i]) + abs(A[i - 2] - A[i]);
b = abs(A[i - 1] - A[i]) + abs(A[i - 2] - A[i-1]);
c = abs(A[i - 1] - A[i-2]) + abs(A[i - 2] - A[i]);
a = min(a, min(b, c));
dp[i][1][1] = min(dp[i-2][0][0], dp[i-2][0][1]) + a;
}
}
cout << min(dp[N-1][1][1],dp[N - 1][1][0]) << endl;
}