Submission #726386

#	Time	Username	Problem	Language	Result	Execution time	Memory
726386		NothingXD	Candies (JOI18_candies)	C++14	0 / 100	103 ms	152892 KiB

candies

/*

   Wei Wai Wei Wai
   Zumigat nan damu dimi kwayt rayt

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
  struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
  ull q = (ull)((L(m) * a) >> 64);
  ull r = a - q * b; // can be proven that 0 <= r < 2*b
  return r >= b ? r - b : r;
  }
  };
  FastMod FM(2);
  */
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 2e5 + 10;

int n, a[maxn];

vector<ll> dp[maxn << 2][4];

vector<ll> merge(vector<ll> a, vector<ll> b){
	vector<ll> res;
	if (a.empty() || b.empty()) return res;
	res.push_back(0);
	res.resize(a.size() + b.size() - 1, 0);
	int pta = 1, ptb = 1;
	for (int i = 1; i < res.size(); i++){
		assert(pta < a.size() || ptb < b.size());
		if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
			res[i] = res[i-1] + a[pta] - a[pta-1];
			pta++;
		}
		else{
			res[i] = res[i-1] + b[ptb] - b[ptb-1];
			ptb++;
		}
	}
	return res;
}

void solve(int v, int l, int r){
	if (l + 1 == r){
		dp[v][0].push_back(0);
		dp[v][3].push_back(0);
		dp[v][3].push_back(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	int lc = v << 1;
	int rc = lc | 1;
	solve(lc, l, mid);
	solve(rc, mid, r);
	for (int i = 0; i < 4; i++){
		int sz = (r - l == 2? (i&1) + (i&2): (r - l == 3? max(1, (i&1) + (i&2)): (r - l - 2 - (i&1) - (i&2) + 1) / 2 + (i&1) + (i&2))) + 1;
		dp[v][i].resize(sz, 0);
		for (int j = 0; j < 3; j++){
			vector<ll> tmp = merge(dp[lc][(i&2)+(j&1)], dp[rc][(j&2)+(i&1)]);
			for (int k = 0; k < tmp.size(); k++){
				dp[v][i][k] = max(dp[v][i][k], tmp[k]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	solve(1, 1, n+1);
	for (int i = 1; i <= (n+1)/2; i++){
		ll res = 0;
		for (int j = 0; j < 4; j++){
			if (dp[1][j].size() > i) res = max(res, dp[1][j][i]);
		}
		cout << res << '\n';
	}

	return 0;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 1; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from candies.cpp:8:
candies.cpp:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   assert(pta < a.size() || ptb < b.size());
      |          ~~~~^~~~~~~~~~
candies.cpp:58:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   assert(pta < a.size() || ptb < b.size());
      |                            ~~~~^~~~~~~~~~
candies.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
      |       ~~~~^~~~~~~~~~~
candies.cpp:59:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if (ptb >= b.size() || (pta < a.size() && a[pta] - a[pta-1] > b[ptb] - b[ptb-1])){
      |                           ~~~~^~~~~~~~~~
candies.cpp: In function 'void solve(int, int, int)':
candies.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for (int k = 0; k < tmp.size(); k++){
      |                    ~~^~~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:104:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  104 |    if (dp[1][j].size() > i) res = max(res, dp[1][j][i]);
      |        ~~~~~~~~~~~~~~~~^~~

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