Submission #1050783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050783		mychecksedad	Candies (JOI18_candies)	C++17	0 / 100	50 ms	8536 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);
  vector<int> f;
  a[0] = -1;
  for(int i = 0; i < n; i++){
    int x = A[i].ss;
    int y = A[i+1].ss;
    used[x] = 1;

    vector<vector<int>> v;
    for(int j = 1; j <= n; ++j){
      if(j == 1 && used[j]) v.pb({a[1]});
      else{
        if(used[j] && used[j-1]) v.back().pb(a[j]);
        else if(used[j]) v.pb({a[j]});
      }
    }


    ll sum = 0, co = 0;
    for(auto u: v){
      ll x = 0, y = 0, xc = 0, yc = 0;
      for(int i = 0; i < u.size(); i += 2){
        x += u[i];
        ++xc;
      }
      for(int i = 1; i < u.size(); i += 2){
        y += u[i];
        ++yc;
      }
      if(u.size() % 2 == 0){
        sum += max(x, y);
        co += xc;
      }else{
        sum += x;
        co += xc;
      }
    }
    dp[co] = max(dp[co], sum);
    // 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;
  }
 for(int i = 1; i <= (n+1)/2; ++i) cout << dp[i] << '\n';
}


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:86:38: warning: narrowing conversion of 'a[1]' from 'long long int' to 'int' [-Wnarrowing]
   86 |       if(j == 1 && used[j]) v.pb({a[1]});
      |                                   ~~~^
candies.cpp:86:38: warning: narrowing conversion of 'a[1]' from 'long long int' to 'int' [-Wnarrowing]
candies.cpp:89:35: warning: narrowing conversion of 'a[j]' from 'long long int' to 'int' [-Wnarrowing]
   89 |         else if(used[j]) v.pb({a[j]});
      |                                ~~~^
candies.cpp:89:35: warning: narrowing conversion of 'a[j]' from 'long long int' to 'int' [-Wnarrowing]
candies.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       for(int i = 0; i < u.size(); i += 2){
      |                      ~~^~~~~~~~~~
candies.cpp:101:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |       for(int i = 1; i < u.size(); i += 2){
      |                      ~~^~~~~~~~~~
candies.cpp:81:9: warning: unused variable 'y' [-Wunused-variable]
   81 |     int y = A[i+1].ss;
      |         ^
candies.cpp: In function 'int main()':
candies.cpp:145:15: warning: unused variable 'aa' [-Wunused-variable]
  145 |   int tt = 1, aa;
      |               ^~

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