Submission #876540

#	Time	Username	Problem	Language	Result	Execution time	Memory
876540		MinaRagy06	Peru (RMI20_peru)	C++17	0 / 100	5 ms	8792 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long

const int N = 2'500'005, mod = 1e9 + 7;
const ll inf = 1e18;
struct Stack {
	stack<array<ll, 2>> s;
	//{mn, actual}
	Stack() {
		s.push({inf, inf});
	};
	void push(ll x) {
		s.push((array<ll, 2>) {min(s.top()[0], x), x});
	}
	ll pop() {
		ll x = s.top()[1];
		s.pop();
		return x;
	}
	bool empty() {
		return s.size() == 1;
	}
	int size() {
		return (int)s.size() - 1;
	}
	ll getmn() {
		return s.top()[0];
	}
	ll top() {
		return s.top()[1];
	}
};
struct Deque {
	Stack l, r;
	void process() {
		int doswap = 0;
		if (r.empty()) {
			doswap = 1;
			swap(l, r);
		}
		int sz = r.size() / 2;
		Stack temp;
		while (sz--) {
			temp.push(r.pop());
		}
		while (!r.empty()) {
			l.push(r.pop());
		}
		while (!temp.empty()) {
			r.push(temp.pop());
		}
		if (doswap) {
			swap(l, r);
		}
	}
	void push_back(ll x) {
		r.push(x);
	}
	void push_front(ll x) {
		l.push(x);
	}
	void pop_back() {
		if (r.empty()) {
			process();
		}
		r.pop();
	}
	void pop_front() {
		if (l.empty()) {
			process();
		}
		l.pop();
	}
	ll back() {
		if (r.empty()) {
			process();
		}
		return r.top();
	}
	ll front() {
		if (l.empty()) {
			process();
		}
		return l.top();
	}
	ll getmn() {
		return min(l.getmn(), r.getmn());
	}
	int size() {
		return l.size() + r.size();
	}
};

ll dp[N], a[N];
Deque mndp, ans, active;
int solve(int n, int k, int *v) {
	for (int i = 0; i < n; i++) {
		a[i + 1] = v[i];
	}
	deque<int> s;
	bool bad = 0;
	auto addbad = [&] (int l) {
		int r = l - 1;
		while (r < s[0]) {
			r++;
			active.push_back(dp[r - 1]);
		}
		ans.pop_front();
		mndp.pop_front();
	};
	for (int i = 1; i <= n; i++) {
		dp[i] = inf;
		ll mn = dp[i - 1];
		while (s.size() && a[i] >= a[s.back()]) {
			mn = min(mn, mndp.back());
			if (s.size() > 1 || !bad) {
				mndp.pop_back();
				ans.pop_back();
			} else if (s.size() == 1 && bad) {
				int r = s.back();
				while (r < i) {
					r++;
					active.push_back(dp[r - 1]);
				}
			}
			s.pop_back();
		}
		s.push_back(i);
		mndp.push_back(mn);
		if (s.size() > 1 || i - k < 1) {
			ans.push_back(a[i] + mn);
		}
		if (i - k >= 1) {
			if (i - k != 1) active.pop_front();
			if (i - k == s.front() || i - k == 1) {
				if (i - k != 1) {
					s.pop_front();
				}
				bad = 1;
				addbad(i - k + 1);
			}
		}
		dp[i] = ans.getmn();
		dp[i] = min(dp[i], active.getmn() + a[s[0]]);
// 		ll c = 0;
// 		for (int j = i; j > max(0, i - k); j--) {
// 			c = max(c, a[j]);
// 			dp[i] = min(dp[i], dp[j - 1] + c);
// 		}
	}
	int ret = 0;
	ll pw = 1;
	for (int i = n; i >= 1; i--) {
		ret += pw * (dp[i] % mod) % mod;
		ret %= mod;
		pw = pw * 23 % mod;
	}
	return ret;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51