Submission #1184639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184639		sano	Holiday (IOI14_holiday)	C++20	24 / 100	48 ms	9916 KiB

holiday

//#pragma GCC optimize("O3")
//#pragma GCC target("tune=native")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include "holiday.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define shit short int
#define ll long long
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 47
#define prv2 43
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;
//using namespace __gnu_pbds;

//template <typename T1, typename T2>
//using indexed_set = tree<pair<T1, T2>, null_type, less<pair<T1, T2>>, rb_tree_tag, tree_order_statistics_node_update>;

class intervalac {
	int n;
	vec<ll> in, l, r, z;
	void update(int s) {
		in[s] = in[s * 2] + in[s * 2 + 1];
		z[s] = z[s * 2] + z[s * 2 + 1];
		return;
	}
public:
	intervalac(int vel) {
		n = 1;
		while (n < vel) n *= 2;
		l.resize(2 * n); r.resize(2 * n); in.resize(2 * n, 0); z.resize(2 * n, 0);
		For(i, n) {
			l[i + n] = r[i + n] = i;
		}
		rffor(i, 1, n - 1) {
			l[i] = l[i * 2];
			r[i] = r[i * 2 + 1];
		}
		return;
	}
	void zapni(int x, int k) {
		x += n;
		z[x] = 1;
		in[x] = k;
		x /= 2;
		while (x) {
			update(x);
			x /= 2;
		}
		return;
	}
	ll daj(int k, int s = 1) {
		if (k >= z[s]) return in[s];
		if (z[s * 2] >= k) return daj(k, s * 2);
		return daj(k, s * 2) + daj(k - z[s * 2], s * 2 + 1);
	}
};

ll findMaxAttraction(int n, int start, int d, int a2[]) {
	if (start == 0) {
		ll odp = -1;
		vec<ll> a;
		For(i, n) {
			a.push_back(a2[i]);
		}
		sort(all(a));
		map<ll, ll> umap;
		For(i, n) {
			umap[a[i]] = i;
		}
		intervalac seg(n);

		For(i, n) {
			seg.zapni(umap[a2[i]], a2[i]);
			int vyber = d - i;
			if (vyber == 0) break;
			odp = max(odp, seg.daj(vyber));
		}
		return odp;
	}
	vec<ll> a;
	For(i, n) a.push_back(a2[i]);
	vec<vec<ll>> dp1(2, vec<ll>(d + 1, 0));
	vec<vec<ll>> dp3(2, vec<ll>(d + 1, 0));
	int som = 0;
	rfor(i, n - start - 1) {
		som = 1 - som;
		ffor(j, 1, dp1[som].size()) {
			dp1[som][j] = a[i + start];
			dp1[som][j] = max(dp1[som][j], dp1[1 - som][j - 1]);
			if (j == 1) continue;
			dp1[som][j] = max(dp1[som][j], dp1[1 - som][j - 2] + a[i + start]);
		}
	}
	som = 0;
	rfor(i, n - start - 1) {
		som = 1 - som;
		ffor(j, 1, dp3[som].size()) {
			dp3[som][j] = a[i + start];
			if (j == 1) continue;
			dp3[som][j] = max(dp3[som][j], dp3[1 - som][j - 2]);
			if (j == 2) continue;
			dp3[som][j] = max(dp3[som][j], dp3[1 - som][j - 3] + a[i + start]);
		}
	}

	vec<vec<ll>> dp2(2, vec<ll>(d + 1, 0));
	vec<vec<ll>> dp4(2, vec<ll>(d + 1, 0));
	som = 0;
	For(i, start) {
		som = 1 - som;
		ffor(j, 1, dp2[som].size()) {
			dp2[som][j] = a[i];
			dp2[som][j] = max(dp2[som][j], dp2[1 - som][j - 1]);
			if (j == 1) continue;
			dp2[som][j] = max(dp2[som][j], dp2[1 - som][j - 2] + a[i]);
		}
	}
	som = 0;
	For(i, start) {
		som = 1 - som;
		ffor(j, 1, dp4[som].size()) {
			dp4[som][j] = a[i];
			if (j == 1) continue;
			dp4[som][j] = max(dp4[som][j], dp4[1 - som][j - 2]);
			if (j == 2) continue;
			dp4[som][j] = max(dp4[som][j], dp4[1 - som][j - 3] + a[i]);
		}
	}
	ll maxi = 0;
	maxi = dp1[(n - start) % 2][d];
	For(i, d) {
		maxi = max(maxi, dp3[(n - start) % 2][d - i - 1] + dp2[(start) % 2][i]);
		maxi = max(maxi, dp4[(start) % 2][max(0, d - i - 2)] + dp1[(n - start) % 2][i]);
	}
	return maxi;
}
/*
signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t;
	t = 1;
	For(i, t) {
		int n, d, start; cin >> n >> d >> start;
		int a[100];
		For(i, n) cin >> a[i];
		cout << findMaxAttraction(n, start, d, a);
	}
	return 0;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53