oj.uz

Submission #674922

# Submission time Handle Problem Language Result Execution time Memory
674922 2022-12-26T15:32:10 Z ghostwriter Candies (JOI18_candies) C++17
100 / 100
 102 ms 11044 KB 
// #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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 484 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 476 KB Output is correct
15 Correct 1 ms 476 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 480 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 484 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 476 KB Output is correct
15 Correct 1 ms 476 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 480 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 86 ms 10832 KB Output is correct
22 Correct 101 ms 10908 KB Output is correct
23 Correct 95 ms 10932 KB Output is correct
24 Correct 65 ms 10752 KB Output is correct
25 Correct 64 ms 10684 KB Output is correct
26 Correct 64 ms 10744 KB Output is correct
27 Correct 75 ms 10892 KB Output is correct
28 Correct 74 ms 11044 KB Output is correct
29 Correct 73 ms 10884 KB Output is correct
30 Correct 73 ms 10904 KB Output is correct
31 Correct 80 ms 10928 KB Output is correct
32 Correct 78 ms 10936 KB Output is correct
33 Correct 79 ms 10688 KB Output is correct
34 Correct 78 ms 10712 KB Output is correct
35 Correct 81 ms 10792 KB Output is correct
36 Correct 94 ms 10924 KB Output is correct
37 Correct 102 ms 10872 KB Output is correct
38 Correct 87 ms 10880 KB Output is correct
39 Correct 67 ms 10800 KB Output is correct
40 Correct 64 ms 10816 KB Output is correct
41 Correct 67 ms 10728 KB Output is correct
42 Correct 69 ms 10848 KB Output is correct
43 Correct 70 ms 10936 KB Output is correct
44 Correct 70 ms 10860 KB Output is correct
45 Correct 72 ms 10920 KB Output is correct
46 Correct 71 ms 10864 KB Output is correct
47 Correct 75 ms 10872 KB Output is correct
48 Correct 74 ms 10684 KB Output is correct
49 Correct 80 ms 10740 KB Output is correct
50 Correct 80 ms 10680 KB Output is correct