Submission #674922

#	Time	Username	Problem	Language	Result	Execution time	Memory
674922		ghostwriter	Candies (JOI18_candies)	C++17	100 / 100	102 ms	11044 KiB

candies

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
Okay, this is actually hard. When j = 1, the answer is clearly the biggest element in the array and after that all the work on the
solution is base on this one. Consider the biggest element (pick any) i, there are two cases: i is taken or i - 1 and i + 1 is taken (it can be
easily proven). If j > 1, take the biggest element and sum it up to the answer. After that, we ease i - 1 and i + 1 from our set, set the ith element
to a[i - 1] + a[i + 1] - a[i] (if we add new value of a[i] to the answer then it will be the same as we take i - 1 and i + 1) and transform the current
problem into a new problem with j = j - 1 and the elements might be negative (it doesn't matter though).
*/
const ll oo = 1e18;
const int N = 2e5 + 5;
int n, l[N], r[N], c[N];
ll a[N], rs = 0;
priority_queue<pll> pq;
void input(int test_id) {
	cin >> n;
	FOR(i, 1, n) cin >> a[i];
}
void solve(int test_id) {
	a[0] = a[n + 1] = -oo;
	FOR(i, 1, n) {
		l[i] = i - 1;
		r[i] = i + 1;
		pq.push({a[i], i});
	}
	FOR(j, 1, (n + 1) >> 1) {
		WHILE(c[pq.top().nd]) pq.pop();
		pll cur = pq.top();
		pq.pop();
		int i = cur.nd;
		ll ai = cur.st;
		rs += ai;
		a[i] = a[l[i]] + a[r[i]] - a[i];
		c[l[i]] = c[r[i]] = 1;
		l[i] = l[l[i]];
		r[l[i]] = i;
		r[i] = r[r[i]];
		l[r[i]] = i;
		pq.push({a[i], i});
		cout << rs << '\n';
	}
}
void reinit(int test_id) {

}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    int test_num = 1;
    // cin >> test_num; // comment if the problem does not requires multitest
    FOR(i, 1, test_num) {
        input(i); // input in noninteractive problems for case #i
        solve(i); // main function to solve case #i
        reinit(i); // reinit global data to default used in case #i
    }
    #ifdef LOCAL
        cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms.\n";
    #endif
    return 0;
}
/*
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

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