結果
| 問題 |
No.2100 [Cherry Alpha C] Two-way Steps
|
| コンテスト | |
| ユーザー |
 srjywrdnprkt
|
| 提出日時 | 2023-06-11 04:39:32 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 292 ms / 2,000 ms |
| コード長 | 8,562 bytes |
| コンパイル時間 | 2,490 ms |
| コンパイル使用メモリ | 205,660 KB |
| 最終ジャッジ日時 | 2025-02-14 01:30:35 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 48 |
ソースコード
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
// マクロの定義
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define unless(cond) if (!(cond))
// オーバーロードマクロ
#define overload2(_1, _2, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload5(_1, _2, _3, _4, _5, name, ...) name
// 繰り返し系
#define rep1(n) for (ll i=0; i<n; i++)
#define rep2(i,n) for (ll i=0; i<n; i++)
#define rep3(i,a,b) for (ll i=a; i<b; i++)
#define rep4(i,a,b,c) for (ll i=a; i<b; i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define foreach1(x,a) for (auto &&x: a)
#define foreach2(x,y,a) for (auto &&[x,y]: a)
#define foreach3(x,y,z,a) for (auto &&[x,y,z]: a)
#define foreach4(x,y,z,w,a) for (auto &&[x,y,z,w]: a)
#define foreach(...) overload5(__VA_ARGS__,foreach4,foreach3,foreach2,foreach1)(__VA_ARGS__)
// 除算に関する関数
template<typename T, typename U>
T floor(T x, U y){return (x>0 ? x/y: (x-y+1)/y);}
template<typename T, typename U>
T ceil(T x, U y){return (x>0 ? (x+y-1)/y: x/y);}
template<typename T, typename U>
T mod(T x, U y){
T q=floor(x,y);
return x-q*y;
}
template<typename T, typename U>
pair<T,T> divmod(T x, U y){
T q=floor(x,y);
return {q,x-q*y};
}
// 指数に関する関数
ll intpow(ll x, ll y){
ll a=1;
while (y){
if (y&1) a*=x;
x*=x;
y>>=1;
}
return a;
}
ll modpow(ll x, ll y, ll z){
ll a=1;
while (y){
if (y&1) (a*=x)%=z;
(x*=x)%=z;
y>>=1;
}
return a;
}
ll sum(vector<int> &X){
ll y=0;
for (auto &&x: X) y+=x;
return y;
}
template<typename T>
T sum(vector<T> &X){
T y=T(0);
for (auto &&x: X) y+=x;
return y;
}
// max, min
template<typename T, typename U>
inline bool chmax(T &a, const U b){
return (a<b ? a=b, 1: 0);
}
template<typename T, typename U>
inline bool chmin(T &a, const U b){
return (a>b ? a=b, 1: 0);
}
template<class... T>
constexpr auto max(T... a){
return max(initializer_list<common_type_t<T...>>{a...});
}
template<class... T>
constexpr auto min(T... a){
return min(initializer_list<common_type_t<T...>>{a...});
}
template<class T>
T max(vector<T> X){
T alpha=X[0];
for (auto x:X) chmax(alpha, x);
return alpha;
}
template<class T>
T min(vector<T> X){
T alpha=X[0];
for (auto x:X) chmin(alpha, x);
return alpha;
}
// 入出力
template<class... T>
void input(T&... a){(cin >> ... >> a);}
void print(){cout << "\n";}
template<class T, class... Ts>
void print(const T& a, const Ts&... b){
cout << a;
(cout << ... << (cout << " ", b));
cout << "\n";
}
template<typename T, typename U>
istream &operator>>(istream &is, pair<T,U> &P){
is >> P.first >> P.second;
return is;
}
template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T,U> &P){
os << P.first << " " << P.second;
return os;
}
template<typename T>
vector<T> vector_input(int N, int index){
vector<T> X(N+index);
for (int i=index; i<index+N; i++) cin >> X[i];
return X;
}
template<typename T>
istream &operator>>(istream &is, vector<T> &X){
for (auto &x: X) is >> x;
return is;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &X){
int N=(int)len(X);
rep(i,N) os << (i ? " ": "") << X[i];
return os;
}
template<typename A>
struct Extended_Algebra{
private:
A val; int inf;
public:
Extended_Algebra(): Extended_Algebra(0,0){}
Extended_Algebra(A val): Extended_Algebra(val,0){}
Extended_Algebra(A val, int inf): val(val), inf(inf>0? 1:(inf<0?-1:0)){}
// マイナス元
Extended_Algebra operator-() const { return Extended_Algebra(-val, -inf);}
// 正の元?
bool is_positive(bool zero=true) const {
if (inf==1) return true;
if (inf==-1) return false;
if (zero) return val>=0;
return val>0;
}
// 負の元?
bool is_negative(bool zero=true) const {
if (inf==-1) return true;
if (inf==1) return false;
if (zero) return val<=0;
return val<0;
}
// 0 ?
inline bool is_zero() const {return inf==0 && val==0;}
// 有界?
inline bool is_bounded() const {return inf==0;}
// 加法
Extended_Algebra& operator+=(const Extended_Algebra &y){
assert (!((inf==1 && y.inf==-1)||(inf==-1 && y.inf==1)));
if (inf==0 && y.inf==0){
val+=y.val;
}else if(inf==1 || y.inf==1){
inf=1;
}else{
inf=-1;
}
return *this;
}
friend Extended_Algebra operator+(const Extended_Algebra &x, const Extended_Algebra &y) {return Extended_Algebra(x)+=y;}
// 減法
Extended_Algebra& operator-=(const Extended_Algebra &y){
assert (!((inf==1 && y.inf==1)||(inf==-1 && y.inf==-1)));
if (inf==0 && y.inf==0){
val-=y.val;
}else if(inf==1 || y.inf==-1){
inf=1;
}else{
inf=-1;
}
return *this;
}
friend Extended_Algebra operator-(const Extended_Algebra &x, const Extended_Algebra &y) {return Extended_Algebra(x)-=y;}
// 乗法
Extended_Algebra& operator*=(const Extended_Algebra &y){
if (is_zero() || y.is_zero()){
val=0; inf=0;
}else{
if (is_bounded() && y.is_bounded()){
val*=y.val;
}
else if (!(is_positive() ^ y.is_positive())) {inf=1;}
else {inf=-1;}
}
return *this;
}
friend Extended_Algebra operator*(const Extended_Algebra &x, const Extended_Algebra &y) {return Extended_Algebra(x)*=y;}
// 除法
Extended_Algebra& operator/=(const Extended_Algebra &y){
assert (is_bounded() || y.is_bounded());
assert (!y.is_zero());
if (is_bounded()){
if (y.is_bounded()) val/=y.val;
else val=0;
}else if (y.is_negative()){
inf=-inf;
}
return *this;
}
friend Extended_Algebra operator/(const Extended_Algebra &x, const Extended_Algebra &y) {return Extended_Algebra(x)/=y;}
// 比較
friend bool operator==(const Extended_Algebra &x, const Extended_Algebra &y) {
if (x.inf!=0) return x.inf==y.inf;
return (y.inf==0) && x.val==y.val;
}
friend bool operator<(const Extended_Algebra &x, const Extended_Algebra &y){
if (x.inf==1) return false;
if (x.inf==0) return (y.inf==1) || (y.inf==0 && x.val<y.val);
return y.inf>=0;
}
friend bool operator!=(const Extended_Algebra &x, const Extended_Algebra &y) {return !(x==y);}
friend bool operator> (const Extended_Algebra &x, const Extended_Algebra &y) {return y<x;}
friend bool operator<=(const Extended_Algebra &x, const Extended_Algebra &y) {return (x<y) || (x==y);}
friend bool operator>=(const Extended_Algebra &x, const Extended_Algebra &y) {return (x>y) || (x==y);}
// 入力
friend istream &operator>>(istream &is, Extended_Algebra &x) {
is >> x.val;
return (is);
}
// 出力
friend ostream &operator<<(ostream &os, const Extended_Algebra &x) {
if (x.inf==1) {return cout << "inf";}
if (x.inf==-1) {return cout << "-inf";}
return os << x.val;
}
};
// 無限大の元
template<typename A>
Extended_Algebra<A> infinity(){return Extended_Algebra<A>(A(),1);}
using T=Extended_Algebra<ll>;
int main(){
int N,M; input(N,M);
vector<T> H=vector_input<T>(N,1);
vector<vector<int>> S(N+1);
int x,y;
rep(M){
input(x,y);
S[x].emplace_back(y);
S[y].emplace_back(x);
}
T inf=infinity<ll>();
// チェリーちゃん
vector<vector<T>> DP_c(N+1, {-inf,-inf});
DP_c[1][0]=0;
rep(a,1,N+1){
foreach(b,S[a]){
if (a<b){
if (H[a]<H[b]) chmax(DP_c[b][1], DP_c[a][0]+(H[b]-H[a]));
else chmax(DP_c[b][0], max(DP_c[a]));
}
}
}
// ゼルコバ君
vector<vector<T>> DP_z(N+1, {-inf,-inf});
DP_z[N][0]=0;
for (int a=N; a>=1; a--){
foreach(b,S[a]){
if (a>b){
if (H[a]<H[b]) chmax(DP_z[b][1], DP_z[a][0]+(H[b]-H[a]));
else chmax(DP_z[b][0], max(DP_z[a]));
}
}
}
print((max(DP_c[N])>-inf) ? max(DP_c[N]): -1);
print((max(DP_z[1])>-inf) ? max(DP_z[1]): -1);
}