#PU1517. USACO 2025 US Open Contest, Bronze — Problem 3. It's Mooin' Time III
USACO 2025 US Open Contest, Bronze — Problem 3. It's Mooin' Time III
USACO 2025 US Open Contest, Bronze — Problem 3. It's Mooin' Time III
题目描述
Elsie is trying to describe her favorite USACO contest to Bessie, but Bessie is having trouble understanding why Elsie likes it so much. Elsie says "And It's mooin' time! Who wants a mooin'? Please, I just want to do USACO". Bessie still doesn't understand, so she transcribes Elsie's description in a string of length () containing lowercase alphabetic characters . Elsie considers a string containing three characters a moo if and . A triplet is valid if and string forms a moo. For the triplet, FJ performs the following to calculate its value: FJ bends string 90-degrees at index The value of the triplet is twice the area of . In other words, the value of the triplet is . Bessie asks you () queries. In each query, she gives you two integers and (, ) and ask you for the maximum value among valid triplets such that and . If no valid triplet exists, output .
输入格式
The first line contains two integers and . The following line contains . The following lines contain two integers and , denoting each query.
输出格式
(见题面原文)
数据范围
Inputs 2-3: Inputs 4-6: and the singular query satisfies and Inputs 7-11: No additional constraints Problem credits: Chongtian Ma
样例
样例 1
12 5
abcabbacabac
1 12
2 7
4 8
2 5
3 10
28
6
1
-1
12
For the first query, ($i,j,k$) must satisfy $1 \le i < j < k \le 12$. It can be
shown that the maximum area of $\Delta ijk$ for some valid ($i,j,k$) is achieved
when $i=1$, $j=8$, and $k=12$. Note that $s_1 s_8 s_{12}$ is the string "acc"
which is a moo according to the definitions above. $\Delta ijk$ will have legs
of lengths $7$ and $4$ so two times the area of it will be $28$.
For the third query, ($i,j,k$) must satisfy $4 \le i < j < k \le 8$. It can be
shown that the maximum area of $\Delta ijk$ for some valid ($i,j,k$) is achieved
when $i=4$, $j=5$, and $k=6$.
For the fourth query, there exists no ($i,j,k$) satisfying
$2 \le i < j < k \le 5$ in which $s_i s_j s_k$ is a moo so the output to that
query is $-1$.
提示
use of 64-bit integer data types (e.g., a "long long" in C/C++).