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 |
|
|
|
|
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 |