結果
問題 |
No.921 ずんだアロー
|
ユーザー |
|
提出日時 | 2019-11-08 23:39:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,936 bytes |
コンパイル時間 | 1,930 ms |
コンパイル使用メモリ | 194,732 KB |
最終ジャッジ日時 | 2025-01-08 03:16:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vs = vector<string>; using pll = pair<ll, ll>; using vp = vector<pll>; #define rep(i, n) for(ll i = 0; i < (n); i++) #define repb(i, n) for(ll i = (n)-1; i >= 0; i--) #define repr(i, a, b) for(ll i = (a); i < (b); i++) #define reprb(i, a, b) for(ll i = (b)-1; i >= (a); i--) #define ALL(a) (a).begin(), (a).end() #define SZ(x) ((ll)(x).size()) const ll MOD = 1000000007; const ll INF = 100000000000000000LL; const ld EPS = 1e-12L; const ld PI = 3.1415926535897932385L; inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; } inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; } inline ll powint(ull x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; } inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; } template<class S, class T>inline bool chmax(S &a, const T &b){ if(a<b) { a=b; return 1; } return 0; } template<class S, class T>inline bool chmin(S &a, const T &b){ if(b<a) { a=b; return 1; } return 0; } #ifdef OJ_LOCAL #include "dump.hpp" #else #define dump(...) ((void)0) #endif const int MAX = 100010; int dp[MAX][2]; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); ll n; cin >> n; vll a(n); rep(i, n){ cin >> a[i]; } dp[0][0] = 1; dp[0][1] = 0; repr(i, 1, n){ if(a[i] == a[i-1]){ dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + 1; dp[i][1] = max(dp[i-1][0], dp[i-1][1]); }else{ dp[i][0] = dp[i-1][1] + 1; dp[i][1] = max(dp[i-1][0], dp[i-1][1]); } } cout << max(dp[n-1][0], dp[n-1][1]) << endl; return 0; }