結果

問題 No.921 ずんだアロー
ユーザー EgorKulikovEgorKulikov
提出日時 2019-11-08 21:39:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 10,595 bytes
コンパイル時間 2,530 ms
コンパイル使用メモリ 208,536 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-15 01:20:31
合計ジャッジ時間 3,516 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 2 ms
5,376 KB
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 WA -
testcase_17 WA -
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 9 ms
5,376 KB
testcase_20 WA -
testcase_21 AC 9 ms
5,376 KB
testcase_22 AC 9 ms
5,376 KB
testcase_23 WA -
testcase_24 AC 9 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Egor Kulikov
 */

#include <iostream>
#include <fstream>

#ifndef JHELPER_EXAMPLE_PROJECT_INPUT_H
#define JHELPER_EXAMPLE_PROJECT_INPUT_H

//
// Created by egor on 30.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_GENERAL_H
#define JHELPER_EXAMPLE_PROJECT_GENERAL_H

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAX_INT = 2147483647;

const double PI = atan(1) * 4;

const int DX_KNIGHT[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int DY_KNIGHT[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int DX4[] = {1, 0, -1, 0};
const int DY4[] = {0, 1, 0, -1};

bool isValidCell(int x, int y, int rows, int cols) {
    return x >= 0 && y >= 0 && x < rows && y < cols;
}

void decreaseByOne() {
}

template <typename T, class...Vargs>
void decreaseByOne(vector<T>& arr, Vargs&...arrs) {
    for (int& i : arr) {
        i--;
    }
    decreaseByOne(arrs...);
}

template <typename T>
T minim(T& was, T cand) {
    return was = min(was, cand);
}

template <typename T>
T maxim(T& was, T cand) {
    return was = max(was, cand);
}

inline int bitCount(int number) {
    return __builtin_popcount(number);
}

inline int bitCount(ll number) {
    return __builtin_popcount(number);
}

#endif //JHELPER_EXAMPLE_PROJECT_GENERAL_H


class Input {
public:
    enum ErrorType {
        OK,
        END_OF_FILE,
        UNEXPECTED_SYMBOL,
        INVALID_CALL
    };

private:
    istream& in;
    bool exhausted = false;
    ErrorType error = OK;
    int get();
    template<typename T> T readInteger();
    int skipWhitespace();

public:
    Input(istream& in);
    int readInt();
    ll readLong();
    string readString();
    vector<int> readIntArray(int size);
    template<typename T> T readType();
    template<typename T, typename U> pair<T, U> readType();
    template<typename T> vector<T> readArray(int size);
    template<typename T1, typename T2> tuple<vector<T1>, vector<T2> > readArrays(int size);
    template<typename T1, typename T2, typename T3> tuple<vector<T1>, vector<T2>, vector<T3> > readArrays(int size);
    template<typename T1, typename T2, typename T3, typename T4>
        tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > readArrays(int size);
    template<typename T1, typename T2, typename T3, typename T4, typename T5>
        tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > readArrays(int size);
    template<typename T> vector<vector<T> > readTable(int rows, int cols);

    string readLine();
};

inline bool isWhitespace(int c) {
    return isspace(c) || c == EOF;
}

int Input::skipWhitespace() {
    int c;
    do {
        c = get();
        if (exhausted) {
            error = END_OF_FILE;
            return c;
        }
    } while (isWhitespace(c));
    return c;
}

Input::Input(std::istream &in) : in(in) {
}

inline int Input::get() {
    int result = in.get();
    if (result == EOF) {
        exhausted = true;
    }
    return result;
}

template<typename T>
T Input::readType() {
    error = INVALID_CALL;
    return nullptr;
}

template<typename T>
T Input::readInteger() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return 0;
    }
    int sgn = 1;
    if (c == '-') {
        sgn = -1;
        c = get();
    }
    T res = 0;
    do {
        if (!isdigit(c)) {
            error = UNEXPECTED_SYMBOL;
            return 0;
        }
        res *= 10;
        res += c - '0';
        c = get();
    } while (!isWhitespace(c));
    return res * sgn;
}

template<>
int Input::readType() {
    return readInteger<int>();
}

template<>
ll Input::readType() {
    return readInteger<ll>();
}

template<>
char Input::readType() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return 0;
    }
    return c;
}

template<>
string Input::readType() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return "";
    }
    vector<char> res;
    do {
        if (error != OK) {
            return "";
        }
        res.push_back(c);
    } while (!isWhitespace(c = get()));
    return string(res.begin(), res.end());
}

inline int Input::readInt() {
    return readType<int>();
}

inline ll Input::readLong() {
    return readType<ll>();
}

template<typename T>
vector<T> Input::readArray(int size) {
    vector<T> res;
    res.reserve(size);
    for (int i = 0; i < size; i++) {
        res.push_back(readType<T>());
        if (error != OK) {
            res.clear();
            return res;
        }
    }
    return res;
}

vector<int> Input::readIntArray(int size) {
    return readArray<int>(size);
}

template<typename T1, typename T2>
tuple<vector<T1>, vector<T2> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    v1.reserve(size);
    v2.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
    }
    return make_tuple(v1, v2);
}

string Input::readString() {
    return readType<string>();
}

template<typename T>
vector<vector<T>> Input::readTable(int rows, int cols) {
    vector<vector<T> > result;
    result.reserve(rows);
    for (int i = 0; i < rows; ++i) {
        result.push_back(readArray<T>(cols));
    }
    return result;
}

string Input::readLine() {
    error = OK;
    int c = skipWhitespace();
    if (error != OK) {
        return "";
    }
    int length = 0;
    vector<char> res;
    do {
        if (error != OK) {
            return "";
        }
        res.push_back(c);
        if (!isWhitespace(c)) {
            length = res.size();
        }
        c = get();
    } while (c != '\n' && c != '\r' && c != EOF);
    return string(res.begin(), res.begin() + length);
}

template<typename T1, typename T2, typename T3>
tuple<vector<T1>, vector<T2>, vector<T3> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
    }
    return make_tuple(v1, v2, v3);
}

template<typename T1, typename T2, typename T3, typename T4>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    vector<T4> v4;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    v4.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
        v4.push_back(readType<T4>());
    }
    return make_tuple(v1, v2, v3, v4);
}

template<typename T1, typename T2, typename T3, typename T4, typename T5>
tuple<vector<T1>, vector<T2>, vector<T3>, vector<T4>, vector<T5> > Input::readArrays(int size) {
    vector<T1> v1;
    vector<T2> v2;
    vector<T3> v3;
    vector<T4> v4;
    vector<T5> v5;
    v1.reserve(size);
    v2.reserve(size);
    v3.reserve(size);
    v4.reserve(size);
    v5.reserve(size);
    for (int i = 0; i < size; ++i) {
        v1.push_back(readType<T1>());
        v2.push_back(readType<T2>());
        v3.push_back(readType<T3>());
        v4.push_back(readType<T4>());
        v5.push_back(readType<T5>());
    }
    return make_tuple(v1, v2, v3, v4, v5);
}

#endif //JHELPER_EXAMPLE_PROJECT_INPUT_H

//
// Created by egor on 31.10.2019.
//

#ifndef JHELPER_EXAMPLE_PROJECT_OUTPUT_H
#define JHELPER_EXAMPLE_PROJECT_OUTPUT_H



class Output {
private:
    ostream& out;
    template<typename T> void printSingle(const T& value);
    template<typename T> void printSingle(const vector<T>& value);
    template<typename T, typename U> void printSingle(const pair<T, U>& value);

public:
    Output(ostream& out);
    void print();
    template<typename T, typename...Targs>void print(const T& first, const Targs... args);
    template<typename...Targs>void printLine(const Targs... args);
    void flush();
};

Output::Output(ostream &out) : out(out) {
    out << setprecision(12);
}

void Output::print() {
}

template<typename T, typename... Targs>
void Output::print(const T& first, const Targs... args) {
    printSingle(first);
    if (sizeof...(args) != 0) {
        out << ' ';
        print(args...);
    }
}

template<typename T>
void Output::printSingle(const T& value) {
    out << value;
}

template<typename... Targs>
void Output::printLine(const Targs... args) {
    print(args...);
    out << '\n';
}

void Output::flush() {
    out.flush();
}

template<typename T>
void Output::printSingle(const vector<T>& array) {
    unsigned int size = array.size();
    for (int i = 0; i < size; ++i) {
        out << array[i];
        if (i + 1 != size) {
            out << ' ';
        }
    }
}

template<typename T, typename U>
void Output::printSingle(const pair<T, U>& value) {
    out << value.first << ' ' << value.second;
}

#endif //JHELPER_EXAMPLE_PROJECT_OUTPUT_H


class b {
public:
	void solve(istream& inp, ostream& outp) {
        Input in(inp);
        Output out(outp);

        int n = in.readInt();
        auto a = in.readIntArray(n);

        vi answer(n + 1);

        for (int i = 0; i < n; i++) {
            bool canRemoveLeft = i == 0 || a[i] >= a[i - 1] || i >= 2 && a[i - 2] > a[i - 1];
            bool canRemoveRight = i == n - 1 || a[i] >= a[i + 1] || i < n - 2 && a[i + 2] > a[i + 1];
            if (canRemoveLeft && canRemoveRight) {
                if (i == 0 || a[i] == a[i - 1]) {
                    answer[i + 1] = 1 + answer[i];
                } else {
                    answer[i + 1] = max(1 + answer[i - 1], answer[i]);
                }
            } else {
                answer[i + 1] = answer[i];
            }
        }
        out.printLine(answer[n]);
	}
};


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	b solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
0