Submission #997955


Source Code Expand

#include <string>
#include <vector>
#include <iostream>
using namespace std;

#ifndef ___Class_RMQ
#define ___Class_RMQ

// ------ Includes ------ //
#include <limits>
#include <vector>
#include <algorithm>

// ------ RMQ Class ------ //
template<typename Type> class RMQ {
private:
	unsigned size_; std::vector<Type> dat;
	inline Type query_(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return std::numeric_limits<Type>::max();
		if (a <= l && r <= b) return dat[k];
		Type lc = query_(a, b, (k << 1), l, (l + r) >> 1);
		Type rc = query_(a, b, (k << 1) + 1, (l + r) >> 1, r);
		return std::min(lc, rc);
	}
public:
	RMQ() : size_(0), dat(std::vector<Type>()) {};
	RMQ(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat.resize(size_ << 1, std::numeric_limits<Type>::max());
	}
	template<class T>
	RMQ(T begin_, T end_) {
		int n = end_ - begin_;
		for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max());
		for (int i = 0; i < n; i++) dat[i + size_] = *(begin_ + i);
		for (int i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
	}
	inline unsigned size() { return size_; }
	inline void update(int i, Type x) {
		i += size_; dat[i] = x;
		while (i > 1) {
			i >>= 1;
			dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
		}
	}
	inline Type query(int l, int r) {
		return query_(l, r, 1, 0, size_);
	}
};

#endif

int n; string s;
int main() {
	cin >> n;
	vector<int> v(n), rv(n);
	for (int i = 0; i < n; i++) cin >> v[i], rv[i] = -v[i];
	RMQ<int> Q1(v.begin(), v.end()), Q2(rv.begin(), rv.end());
	cin >> s;
	int p = 0;
	for (int i = 1; i < s.size(); i++) {
		if (s[i - 1] != s[i]) p = i;
	}
	vector<int> w1(n - p);
	for (int i = 0; i < n - p; i++) w1[i] = -Q2.query(i, i + p + 1);
	cout << *min_element(w1.begin(), w1.end()) << endl;
	return 0;
}

Submission Info

Submission Time
Task B - Compression
User square1001
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1918 Byte
Status WA
Exec Time 50 ms
Memory 3712 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 400 / 400 0 / 800 0 / 200
Status
AC × 2
WA × 2
AC × 13
AC × 5
WA × 8
AC × 22
WA × 27
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt
subtask1 sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
Case Name Status Exec Time Memory
2_1.txt WA 3 ms 256 KB
2_2.txt AC 3 ms 256 KB
sample_1.txt AC 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
sample_3.txt WA 3 ms 384 KB
sample_4.txt WA 3 ms 256 KB
subtask_1.2_1.txt AC 3 ms 256 KB
subtask_1.2_2.txt AC 3 ms 256 KB
subtask_1_1.txt AC 50 ms 3712 KB
subtask_1_10.txt AC 44 ms 3456 KB
subtask_1_2.txt AC 39 ms 3328 KB
subtask_1_3.txt AC 37 ms 3328 KB
subtask_1_4.txt AC 37 ms 3200 KB
subtask_1_5.txt AC 8 ms 640 KB
subtask_1_6.txt AC 48 ms 3584 KB
subtask_1_7.txt AC 3 ms 256 KB
subtask_1_8.txt AC 45 ms 3584 KB
subtask_1_9.txt AC 44 ms 3456 KB
subtask_2_1.txt WA 37 ms 3328 KB
subtask_2_10.txt WA 37 ms 3328 KB
subtask_2_2.txt WA 37 ms 3328 KB
subtask_2_3.txt WA 37 ms 3328 KB
subtask_2_4.txt WA 37 ms 3328 KB
subtask_2_5.txt WA 3 ms 256 KB
subtask_2_6.txt AC 3 ms 256 KB
subtask_2_7.txt AC 3 ms 256 KB
subtask_2_8.txt WA 36 ms 3328 KB
subtask_2_9.txt WA 10 ms 1024 KB
subtask_3_1.txt WA 37 ms 3328 KB
subtask_3_10.txt WA 37 ms 3328 KB
subtask_3_11.txt WA 37 ms 3328 KB
subtask_3_12.txt WA 37 ms 3328 KB
subtask_3_13.txt WA 37 ms 3328 KB
subtask_3_14.txt WA 37 ms 3328 KB
subtask_3_15.txt WA 37 ms 3328 KB
subtask_3_16.txt WA 37 ms 3328 KB
subtask_3_17.txt AC 37 ms 3328 KB
subtask_3_18.txt AC 37 ms 3328 KB
subtask_3_19.txt AC 37 ms 3328 KB
subtask_3_2.txt WA 37 ms 3328 KB
subtask_3_20.txt AC 37 ms 3328 KB
subtask_3_21.txt AC 37 ms 3328 KB
subtask_3_3.txt WA 6 ms 640 KB
subtask_3_4.txt WA 34 ms 3200 KB
subtask_3_5.txt WA 30 ms 3072 KB
subtask_3_6.txt WA 37 ms 3328 KB
subtask_3_7.txt WA 37 ms 3328 KB
subtask_3_8.txt WA 37 ms 3328 KB
subtask_3_9.txt WA 37 ms 3328 KB