結果
問題 | No.2854 -1 Subsequence |
ユーザー |
|
提出日時 | 2024-08-25 14:06:10 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 3,288 bytes |
コンパイル時間 | 1,975 ms |
コンパイル使用メモリ | 154,388 KB |
実行使用メモリ | 17,272 KB |
最終ジャッジ日時 | 2024-08-25 14:06:18 |
合計ジャッジ時間 | 4,632 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <iostream> // cout, endl, cin#include <string> // string, to_string, stoi#include <vector> // vector#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound#include <utility> // pair, make_pair#include <tuple> // tuple, make_tuple#include <cstdint> // int64_t, int*_t#include <cstdio> // printf#include <map> // map#include <queue> // queue, priority_queue#include <set> // set#include <stack> // stack#include <deque> // deque#include <unordered_map> // unordered_map#include <unordered_set> // unordered_set#include <bitset> // bitset#include <cctype> // isupper, islower, isdigit, toupper, tolower#include <math.h>#include <cmath>#include <climits>#include <functional>#include <iomanip>#include <limits>#include <cassert>#include <random>#include <complex>#include <numeric>#include <regex>#include <list>#include <ctime>#include <chrono>#include <array>#include <cstring>using namespace std;#define ll long long#define ull unsigned long long#define ld long doubletypedef vector<long long> vll;using LL = long long; using ULL = unsigned long long;using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;using VL = vector<LL>; using VVL = vector<VL>; using VVVL = vector<VVL>;using VB = vector<bool>; using VVB = vector<VB>; using VVVB = vector<VVB>;using VD = vector<double>; using VVD = vector<VD>; using VVVD = vector<VVD>;using VC = vector<char>; using VS = vector<string>; using VVC = vector<VC>;using PII = pair<int,int>; using PLL = pair<LL,LL>; using PDD = pair<double,double>; using PIL = pair<int,LL>;using MII = map<int,int>; using MLL = map<LL,LL>;using SI = set<int>; using SL = set<LL>;using MSI = multiset<int>; using MSL = multiset<LL>;template<class T> using MAXPQ = priority_queue<T>;template<class T> using MINPQ = priority_queue< T, vector<T>, greater<T> >;const ll MOD = 1000000007;const ll MOD2 = 998244353;const ll INF = 1LL << 60;#define PI 3.14159265358979323846#define FOR(i, a, b) for(int i = (a); i < (b); ++i)#define REP(i, n) FOR(i, 0, n)#define EACH(e, v) for(auto &e : v)#define RITR(it, v) for(auto it = (v).rbegin(); it != (v).rend(); ++it)#define ALL(v) v.begin(),v.end()vector<ll> x8={1,1,1,0,0,-1,-1,-1},y8={1,0,-1,1,-1,1,0,-1};int dx4[4]={1,-1,0,0}, dy4[4]={0,0,1,-1};/*memo-uf,RMQ(segtree),BIT,BIT2,SegTree,SegTreeLazy-isprime,Eratosthenes,gcdlcm,factorize,divisors,modpow,moddiv(modpow必要)nCr(+modnCr,inverse,extend_euclid.powmod),tobaseB,tobase10-dijkstra,Floyd,bellmanford,sccd,topological,treediamiter-compress1,compress2,rotate90-co,ci,fo1,fo2,fo3,fo4-bitsearch,binaryserach-bfs(vis.assign忘れるな)-SegTreedec,SegTreeLazydec*/int main(){cin.tie(0);ios_base::sync_with_stdio(0);ll N; cin >> N;VL a(N); for(ll i = 0; i < N; i++) cin >> a[i];VL na(N); for(ll i = 0; i < N; i++) na[i] = -a[i];VVL dp(N+1,VL(2,-INF));dp[0][0]=-INF;for(ll i = 0; i < N; i++){dp[i+1][0] = max(dp[i+1][0],dp[i][1]+a[i]);dp[i+1][0] = max(dp[i+1][0],dp[i][0]);dp[i+1][1] = max(dp[i+1][1],na[i]);dp[i+1][1] = max(dp[i+1][1],dp[i][0]+na[i]);dp[i+1][1] = max(dp[i+1][1],dp[i][1]);}cout << max(dp[N][0],dp[N][1]) << endl;}