Submission #63598856

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
const ll mod=998244353;
struct mint{
  ll v;
  mint():v(0){}
  mint(ll val):v(val%mod){}
  friend mint operator+(const mint&a,const mint&b){return a.v+b.v;}
  friend mint operator-(const mint&a,const mint&b){return a.v-b.v;}
  friend mint operator*(const mint&a,const mint&b){return a.v*b.v;}
  ll val(){if(v<0)v+=mod;return v;}
};
vector<mint>power(2e6);
struct hanoi{
  int size,fst;
  vector<mint>ans,top;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
const ll mod=998244353;
struct mint{
  ll v;
  mint():v(0){}
  mint(ll val):v(val%mod){}
  friend mint operator+(const mint&a,const mint&b){return a.v+b.v;}
  friend mint operator-(const mint&a,const mint&b){return a.v-b.v;}
  friend mint operator*(const mint&a,const mint&b){return a.v*b.v;}
  ll val(){if(v<0)v+=mod;return v;}
};
vector<mint>power(2e6);
struct hanoi{
  int size,fst;
  vector<mint>ans,top;
  vector<int>nec;
};
hanoi op(hanoi&a,hanoi&b){
  if(a.nec[0]==-1)return b;
  if(b.nec[0]==-1)return a;
  vector<mint>ans(3),top(3);
  vector<int>nec(3);
  rep(i,0,3){
    if(b.nec[i]==3)ans[i]=a.ans[i];
    else ans[i]=a.ans[b.nec[i]]+(power[a.size+1]-2)*b.top[i]+b.ans[i]-(b.fst==b.nec[i]?0:power[a.size]-1);
  }
  rep(i,0,3){
    if(b.nec[i]==3)top[i]=a.top[i];
    else top[i]=a.top[b.nec[i]]+b.top[i]*power[a.size]-(b.fst==b.nec[i]?0:power[a.size-1]);
  }
  rep(i,0,3){
    if(b.nec[i]==3)nec[i]=a.nec[i];
    else if(a.nec[b.nec[i]]==3)nec[i]=b.nec[i];
    else nec[i]=a.nec[b.nec[i]];
  }
  return hanoi{a.size+b.size,a.fst,ans,top,nec};
}
hanoi e(){
  return hanoi{0,0,{0,0,0},{0,0,0},{-1,-1,-1}};
}
struct segtree{
  ll n=1;
  vector<hanoi>tree;
  segtree(ll N){
    while(n<N)n*=2;
    tree.assign(2*n,e());
  }
  void set(ll i,hanoi&x){
    i+=n;
    tree[i]=x;
    while(i>1){
      i/=2;
      tree[i]=op(tree[2*i],tree[2*i+1]);
    }
  }
  hanoi prod(ll l,ll r){
    l+=n;r+=n;
    hanoi L=e(),R=e();
    while(l<r){
      if(l%2)L=op(L,tree[l]),l++;
      if(r%2)r--,R=op(tree[r],R);
      l/=2;r/=2;
    }
    return op(L,R);
  }
  hanoi get(ll i){return tree[i+n];}
};
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  ll N;cin>>N;
  vector<ll>A(N);
  rep(I,0,N)cin>>A[I];
  ll a=0,b=-1e18;
  rep(I,0,N){
    ll c=a;
    a=max(a+A[I],b);
    b=c;
  }
  cout<<a<<endl;
}

Submission Info

Judge Result