Submission #302194

#	Time	Username	Problem	Language	Result	Execution time	Memory
302194		square1001	Horses (IOI15_horses)	C++14	17 / 100	1543 ms	10356 KiB

horses

#include "horses.h"
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int N; priority_queue<int> que; vector<int> X, Y;
int solve() {
	long long mult = 1;
	vector<int> st = { N };
	while(!que.empty()) {
		int u = que.top();
		if(u == 0) break;
		if(X[u] >= 2) {
			if(mult * X[u] > 1000000000) break;
			mult *= X[u];
			st.push_back(u);
		}
		que.pop();
	}
	st.push_back(!que.empty() ? que.top() : 0);
	reverse(st.begin(), st.end());
	int ini = st[0];
	int coeff = 1;
	for(int i = 0; i <= ini; ++i) {
		coeff = int(1LL * coeff * X[i] % mod);
	}
	long long ans = 0;
	int submult = 1;
	for(int i = 0; i < int(st.size()) - 1; ++i) {
		int mx = 0;
		for(int j = st[i]; j < st[i + 1]; ++j) {
			mx = max(mx, Y[j]);
		}
		ans = max(ans, 1LL * submult * mx);
		if(i + 2 != int(st.size())) {
			submult *= X[st[i + 1]];
		}
		if(i >= 1) {
			que.push(st[i]);
		}
	}
	ans = (ans % mod) * coeff % mod;
	return int(ans);
}
int init(int N_, int X_[], int Y_[]) {
	N = N_;
	X = vector<int>(X_, X_ + N);
	Y = vector<int>(Y_, Y_ + N);
	for(int i = 0; i < N; ++i) {
		if(X[i] >= 2) {
			que.push(i);
		}
	}
	return solve();
}
int updateX(int pos, int val) {
	if(val >= 2) que.push(pos);
	X[pos] = val;
	return solve();
}
int updateY(int pos, int val) {
	Y[pos] = val;
	return solve();
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23