Submission #1050761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050761		mychecksedad	Candies (JOI18_candies)	C++17	0 / 100	3 ms	8540 KiB

candies

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;


int n;
ll a[N], T[N], lazy[N], A[N];
void build(int x){
  for(int i =0; i <= 4*x; ++i) T[i] = lazy[i] = 0;
}
void push(int k){
  T[k<<1] += lazy[k];
  T[k<<1|1] += lazy[k];
  lazy[k<<1] += lazy[k];
  lazy[k<<1|1] += lazy[k];
  lazy[k] = 0;
}
void upd(int l, int r, int ql, int qr, int k, ll val){
  if(ql>r||l>qr) return;
  if(ql <= l && r <= qr){
    lazy[k] += val;
    T[k] += val;
    return;
  }
  push(k);
  int m = l+r>>1;
  upd(l, m, ql, qr, k<<1, val);
  upd(m+1, r, ql, qr, k<<1|1, val);
  T[k] = max(T[k<<1], T[k<<1|1]);
  // cout << l << ' ' << r << ' ' << T[k] << '\n';
}
void upd2(int l, int r, int ql, int qr, int k, ll val){
  if(ql>r || l>qr) return;
  if(ql <= l && r <= qr){
    T[k] = val;
    return;
  }
  push(k);
  int m = l+r>>1;
  upd2(l, m, ql, qr, k<<1, val);
  upd2(m+1, r, ql, qr, k<<1|1, val);
  T[k] = max(T[k<<1], T[k<<1|1]);
  // cout << l << ' ' << r << ' ' << T[k] << '\n';
}
ll get(int l, int r, int p, int k){
  if(l > r || l > p || r < p) return 0;
  if(l == r){
    return T[k];
  }
  push(k);
  int m = l+r>>1;
  if(p <= m) return get(l, m, p, k<<1);
  return get(m+1, r, p, k<<1|1);
}
ll dp[N];
void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  build(n);
  vector<pair<ll, ll>> A;
  for(int i = 1; i <= n; ++i){
    A.pb({a[i], i});
    dp[i] = 0;
  }
  dp[0] = 0;
  sort(all(A), greater<pair<ll, ll>>());
  vector<bool> used(n+1);
  a[0] = -1;
  for(int i = 0; i + 1 < n; i += 2){
    int x = A[i].ss;
    int y = A[i+1].ss;

    if(x > y) swap(x, y);
    for(int j = n; j >= 1; --j){
      if(j >= y + 2){
        dp[j] = max((dp[y - 2] - dp[y - 1]) + a[y], (dp[x - 2] - dp[x - 1]) + a[x]) + dp[j];
      }else if(j >= x + 2){
        dp[j] = (dp[x - 2] - dp[x - 1]) + a[x] + dp[j];
      }
    }
    dp[x] = dp[x - 2] + a[x];
    dp[y] = max(dp[y - 2] + a[y], dp[x - 2] - dp[x - 1] + a[x] + dp[y]);
    // ll addx = a[x] - (used[x-1] ? a[x] - a[x - 1]);
    // ll addy = a[y] - (used[y-1] ? a[y] - a[y - 1]);
    // if(a[x] >= a[y]){
    //   upd(1, n, x + 2, n, 1, );
    //   upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
    // }else{
    //   upd(1, n, y + 2, n, 1, a[y] - a[x]);
    //   upd(1, n, x + 2, n, 1, a[x]);
    //   upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
    //   upd2(1, n, y, y, 1, get(1, n, y - 2, 1) + a[y]);
    // }
    cout << *max_element(dp+1, dp+1+n);
    cout << '\n';
    used[x] = used[y] = 1;
  }
  if(n % 2){
    ll x = 0, y = 0;
    for(int i = 1; i <= n; i += 2) x += a[i];
    cout << x;
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

candies.cpp: In function 'void upd(int, int, int, int, int, long long int)':
candies.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l+r>>1;
      |           ~^~
candies.cpp: In function 'void upd2(int, int, int, int, int, long long int)':
candies.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int m = l+r>>1;
      |           ~^~
candies.cpp: In function 'long long int get(int, int, int, int)':
candies.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int m = l+r>>1;
      |           ~^~
candies.cpp: In function 'void solve()':
candies.cpp:108:15: warning: unused variable 'y' [-Wunused-variable]
  108 |     ll x = 0, y = 0;
      |               ^
candies.cpp: In function 'int main()':
candies.cpp:117:15: warning: unused variable 'aa' [-Wunused-variable]
  117 |   int tt = 1, aa;
      |               ^~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92