Thanks to everyone who participated in the Fall 2025 PHSCO! Over 40 teams participated across both divisions, which is a new record and extremely inspiring for our second-ever hosted contest. Things went a lot more smoothly this year and we hope that all (or at least a majority) of the problems were enjoyable. On a personal note, being able to run PHSCO is an amazing opportunity and I can't thank all of you enough for making it possible.
Anyways, without further ado, congratulations to all of the winners in each prize pool! Please check your emails for prizes, which should be sent out within this week. (If you don't receive anything after a week, please contact me!)
Standard Division (Pre-College):
- 1st — Entropy — TheInfiniteLoop — Narayana Educational Institution
- 2nd — 1 orz 1 norz — Eason Li, Ethan Chang (easonli416, spoonspoon1006) — Ellen Fletcher Middle School, Davidson Academy
- 3rd — Exertxfy — Somil Varshney, Shiven Khurana (Exertxfy, BlackPearls) — Montgomery Blair High School
Advanced Division (Pre-College):
- 1st — ecnerwala orz — Vihaan Sharma, Jason Shnaper (WorldWarV, silverkeep) — Piedmont Hills High School
- 2nd — Why always me? — Nathan Katov, Marcus Liu (NK_, Sucram314) — Colonel By S.S, University of Toronto Schools
- 3rd — Roman Mielamud (rrmpwn_) — Mariupol Lyceum of Kyiv City
Advanced Division (Global):
- 1st — Necromancer — Jhao Wei Fan (SorahISA) — National Yang Ming Chiao Tung University
- 2nd — Bar of USACO Camp — Yiming Li, Xianghong Luo (liympanda, lxhgww)
- 3rd — ecnerwala orz — Vihaan Sharma, Jason Shnaper (WorldWarV, silverkeep) — Piedmont Hills High School
And a huge shoutout to everyone who helped prepare the contest:
- Problems were written and prepared by me, William Park (pilliamw)
- Standard Division was tested by Aanshi Patel (shilab) and Ben Ross (benmross)
- Advanced Division was tested by Anna Zhou (the_808808th_user)
- Problems were proofread by Nicole Sabova (._nicolesss_.) and Brooke Yin
- Announcement banner was drawn by Brooke Yin
- Prize pool sponsored by the Poolesville HS Science, Math, and Computer Science magnet program
Below are editorials to each problem across all divisions, roughly ordered by difficulty. If you liked/disliked a specific problem, please leave feedback using the "Rate the problem" widget! Anyone can access and submit to problems via the public group link.
We hope to see you again for the Spring Fall 2026 PHSCO. Onwards and upwards! — William Park ---
General Feedback
If PHS sells $$$n$$$ tickets, then they will earn $$$2*n$$$ dollars. So, output $$$2*n$$$.
print(int(input())*2)
If every visitor takes one piece of candy, then $$$a-b=c$$$ must hold. So, output YES if $$$a-b \neq c$$$, and NO otherwise.
a,b,c = map(int, input().split())
if (a-b) == c:
print("NO")
else:
print("YES")
Refer to your language's documentation for how to check for the presence of a substring in a string. Note that even though $$$x$$$ is an integer, it is much easier to treat it as a string.
t = int(input())
for _ in range(t):
num = input()
print("YES" if "67" in num else "NO")
Note that Polly cannot get more than $$$a+d$$$ Skittles, $$$b+e$$$ Kit Kats, and $$$c+f$$$ Reeses Cups. Additionally, since Polly's candy total cannot change, $$$x$$$ cannot be greater than $$$(a+b+c)/3$$$ floored. So, the answer is the minimum of those four expressions.
t = int(input())
for _ in range(t):
a,b,c,d,e,f = map(int, input().split())
print(min((a+b+c)//3, a+d, b+e, c+f))
Note that if $$$n \gt m$$$, it is clearly impossible to give all $$$n$$$ students at least 1 serving of food. Otherwise, it is always possible. One trivial construction is to initially give every student $$$1$$$ serving, and then give all leftover servings to the first student.
t = int(input())
for _ in range(t):
n,m = map(int, input().split())
if n > m:
print(-1)
else:
print(m-n+1, end=" ")
for i in range(1, n):
print(1, end=" ")
print()
Adv. B — A Tale of Silk & Song
Assume the starting note is $$$1$$$, and build the song accordingly. Then, find the minimum note frequency in the song, and increase all frequencies in the song by the smallest $$$k$$$ such that the minimum note frequency becomes $$$1$$$.
t = int(input())
for _ in range(t):
n = int(input())
a = input()
b = [1]
for c in a:
if c == "0":
b.append(b[-1]-1)
else:
b.append(b[-1]+1)
upshift = 1-min(b)
for i in range(n+1):
b[i] += upshift
print(" ".join(map(str, b)))
Std. G — Trick-Or-Treat Lane (Standard Div.)
Note that it is never optimal to move left (except perhaps if all houses are visited and Polly has extra time), since Polly could have just visited the house as she was passing by. So, loop through each house and set it as a "stopping" point, and see how much time Polly has left after moving to that house and visiting that house only. Then, take the maximum-quality houses among the houses Polly passed by (depending on how much time she has left), and add that to her total candy yield.
t = int(input())
for _ in range(t):
n, x = map(int, input().split())
a = list(map(int, input().split()))
best = 0
for d in range(n):
time = x - d
if time <= 0:
break
passed = sorted(a[:d+1], reverse=True) # sort houses in range [0, d]
best = max(best, sum(passed[:min(time, d+1)])) # sum of min(time, d) highest-value houses
print(best)
Note that all nodes are on a distinct "ring" (hexagon), and the only way to move between rings is through one of the six radial lines. So, one way to construct an optimal path is to move onto the right ring, and then choose whichever rotation direction (clockwise or counter-clockwise) reaches the goal node in the shortest time.
Although unintended, building the graph locally and running BFS for each pair is another valid way to solve this problem. (The original harder version of this problem would have had infinitely many hexagons in the spiderweb, but I decided to only use 3 hexagons to simplify the diagram.)
t = int(input())
for _ in range(t):
a,b = map(int, input().split())
# Move onto same ring
path = [a]
a -= 1
b -= 1
if (a//6) != (b//6):
while (a//6) < (b//6):
a += 6
path.append(a+1)
while (a//6) > (b//6):
a -= 6
path.append(a+1)
a += 1
b += 1
# Calculate CW and CCW paths
path1 = path.copy()
path2 = path.copy()
temp = a
while (a % 6) != (b % 6):
a += 1
if (a % 6 == 1):
a -= 6
path1.append(a)
a = temp
while (a % 6) != (b % 6):
a -= 1
if (a % 6 == 0):
a += 6
path2.append(a)
# Output more optimal path
if len(path1) < len(path2):
print(len(path1)-1)
print(" ".join(map(str, path1)))
else:
print(len(path2)-1)
print(" ".join(map(str, path2)))
How many moves can a game take if played optimally?
Consider proof by induction.
Find a situation where Polly loses on her first turn.
If Polly loses when she increases the strength to 1 on her first turn, then Stanley must win (since Polly can't make any valid starting move that doesn't cause her to lose). Otherwise, Polly can force a win since there must exist an integer $$$X$$$ that Polly can choose to force Stanley to lose on his next turn. (We don't have to find this integer under the constraints of the problem.)
Proof: Since Polly makes a move of $$$X$$$ that doesn't consume all the firewood, then $$$X-1$$$ also does not consume the firewood, and if $$$X$$$ does consume the firewood, then $$$X+1$$$ must also consume the firewood. Let $$$Y$$$ be the first $$$X$$$ where all firewood is consumed on Polly's move. Then, Polly should choose $$$Y-1$$$ as her first move. Then, Stanley will lose on his turn. (If $$$Y$$$ causes a loss, then an increment of $$$Y-1$$$ and then $$$1$$$ will also cause a loss).
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
x = 1
i = 0
while i < len(a):
if x < a[i]:
break
x += a[i]
i += 1
if i == len(a):
print("Stanley")
else:
print("Polly")
Adv. E — Bewitching Bitwise Game
For a fixed $$$a+b$$$, which values of $$$a$$$ and $$$b$$$ maximize the score?
What is said maximum score?
0 AND (expr with only ANDs) = 0
If $$$b=0$$$, then the answer is $$$0$$$. If $$$b=1$$$, then the answer is $$$a+b$$$, as we place the OR gate to the left of the last number. (Note that $$$x & y \leq x$$$ for all positive $$$x$$$ and $$$y$$$.)
If $$$b \gt =2$$$, the answer is the smallest number that is one less than a power of two, that is not included in the interval $$$0$$$ to $$$(a+b)$$$. This is trivial to prove for $$$b \gt =3$$$, since we can surround the largest number with a bitstring of all $$$1$$$s and the number directly after it (which contains a $$$1$$$ in the leftmost bit). For $$$b=2$$$, note that we can surround the last occurrence of an all-1 bitstring in the interval with ORs and achieve the same result, since the expression to the right will have a 1 in its leftmost bit.
t = int(input())
for _ in range(t):
a,b = map(int, input().split())
n = a+b
ans = 0
if b == 0:
pass
elif b == 1:
ans = n
else:
ans = 2
while (ans-1) < n:
ans*=2
ans -= 1
print(ans)
When is the answer $$$1$$$?
Imagine a checkerboard.
Note that if the tree is directly adjacent to the starting cell $$$(1, 1)$$$, then the answer is $$$1$$$, since any path longer than $$$1$$$ must exit the starting cell through either $$$(1, 2)$$$ or $$$(2, 1)$$$ and re-enter through the other.
Otherwise, view the plot as an $$$n$$$ by $$$n$$$ checkerboard with the starting cell colored white, and count the number of unoccupied white and black cells. Since any valid path (longer than 1) must visit an equal number of black and white cells, the answer is $$$\min(w, b) * 2$$$.
As a bonus, try to construct such a path. It can be shown that such a path can always be constructed.
t = int(input())
for _ in range(t):
n,x,y = map(int,input().split())
if n == 2 or (x == 1 and y == 2) or (x == 2 and y == 1):
print(1)
else:
white = (n*n)//2
black = white
if n%2 == 1:
white += 1
if (x+y)%2 == 0:
white -= 1
else:
black -= 1
print(2*min(white, black))
A continuous segment of symbols of length $$$n$$$ contains $$$(n-2)(n-1)/2$$$ patterns.
We should only flip bits that are at the end of a continuous segment of symbols.
Instead of counting every pattern, note that a continuous segment of symbols of length $$$n$$$ contains $$$(n-2)(n-1)/2$$$ patterns. Patterns cannot contain symbols of different types, so to calculate the base score, it is enough to calculate the score for each continuous segment of symbols.
Also, note that it is always optimal to change bits that are at the "end" of a continuous segment of symbols. (Otherwise, Stanley would be splitting a segment into two segments, which would cause a decrease in his score.)
To efficiently check the score after flipping each endpoint, precompute the score of each segment, and store the base score. Then, for each flipped symbol, calculate the change in the score caused by the flip. (This is efficient because each flip can affect the length at most three continuous segments.)
The final answer is the maximum change across all flips (including no flip, which changes the score by $$$0$$$), added to the base score.
t = int(input())
for _ in range(t):
n = int(input())
a = input()
b = []
last = a[0]
count = 0
for i in range(n):
if a[i] == last:
count += 1
else:
b.append(count)
last = a[i]
count = 1
b.append(count)
base = 0
for i in b:
if i >= 3:
base += (i - 2) * (i - 1) // 2
bestd = 0
ni = len(b)
for i in range(ni - 1):
delta = 0
if b[i + 1] > 1:
if b[i + 1] >= 3:
delta -= (b[i + 1] - 2)
delta += b[i] - 1
else:
if i < ni - 2:
delta -= (b[i] - 2) * (b[i] - 1) // 2
delta -= (b[i + 2] - 2) * (b[i + 2] - 1) // 2
delta += (b[i] + b[i + 2] - 1) * (b[i] + b[i + 2]) // 2
else:
delta += b[i] - 1
bestd = max(bestd, delta)
for i in range(1, ni):
delta = 0
if b[i - 1] > 1:
if b[i - 1] >= 3:
delta -= (b[i - 1] - 2)
delta += b[i] - 1
else:
if i > 1:
delta -= (b[i] - 2) * (b[i] - 1) // 2
delta -= (b[i - 2] - 2) * (b[i - 2] - 1) // 2
delta += (b[i] + b[i - 2] - 1) * (b[i] + b[i - 2]) // 2
else:
delta += b[i] - 1
bestd = max(bestd, delta)
print(base+bestd)
Adv. H — The Mist (Easy Version)
What information is preserved?
Solve the problem for a 10-digit combination.
$$$N \lt = 300$$$ is the effective constraint on the intended solution.
We can use the frequency of each digit to encode a digit in the original combination. So, the number of zeros in the encoding is the first digit, the number of ones in the encoding is the second digit, and so on. To deal with the 11th and 12th digits, one way is to multiply their frequencies by 10 and add them to the zero and one counts. For example, if there were 67 zeros in our encoding, we'd interpret that as the first digit being 7 and the eleventh digit being 6.
For 000000000000, to avoid outputting an empty line, instead output an otherwise nonsensical encoding (such as 333 zeroes), and check for that specific case in the decoder.
I actually didn't think of this solution. Such is the beauty of an open-ended interactive problem!
Since $$$16^{10} \gt 10^{12}$$$, we can encrypt the original combination in hexadecimal. Then, our encoding can use the frequencies of each digit to encode a 10-digit hexadecimal number.
def encode(a):
counts = [0] * 10
for i in range(12):
if i >= 10:
counts[i % 10] += 10 * (int(a[i]) - int('0'))
else:
counts[i] = int(a[i]) - int('0')
if a == "000000000000":
counts[0] = 100
for i in range(10):
for j in range(counts[i]):
print(i, end="")
print()
def decode(a):
counts = [0] * 10
for c in a:
counts[int(c)] += 1
if counts[0] == 100:
print("000000000000")
return
ans = [0] * 12
for i in range(10):
ans[i] = counts[i] % 10
ans[10] = counts[0] // 10
ans[11] = counts[1] // 10
for x in ans:
print(x, end="")
print()
mode = input()
n = int(input())
for _ in range(n):
a = input().strip()
if mode == "encode":
encode(a)
elif mode == "decode":
decode(a)
Given a $$$k$$$, how can we efficiently check if every cell is lit up?
Let $$$f(k)$$$ return whether the grid is lit up for a given $$$k$$$. $$$f(k)$$$ is monotonic.
To find the minimum necessary $$$k$$$, we can binary search for the smallest value that lights up the entire grid. So, now the problem is to efficiently check whether the grid is lit up for a given $$$k$$$, since checking all $$$10^8$$$ cells is too slow.
Well, instead of going cell-by-cell, how about going column-by-column? For column $$$c$$$ and generator strength $$$k$$$, note that a lamp at $$$(x, y)$$$ does not light up any cells in the column if $$$|y-c| \geq k$$$. Otherwise, the lamp must light up all cells $$$(a, c)$$$ in the column where $$$x - (k - |y - c|) \lt a \lt x + (k - |y-c|)$$$. Now, we simply need to check if the intervals covered by each lamp fully light up the column, which can be done in $$$O(m \log m)$$$. This means we can check the entire grid for a given $$$k$$$ in $$$O(nm \log m)$$$. For $$$\log n$$$ queries for $$$k$$$ from binary search, this gives a final time complexity of $$$O(nm \log(n+m))$$$.
A similar approach can be used to check row-by-row instead, with identical time complexity.
Another solution is to binary search for the smallest $$$k$$$ for each column, where the maximum across all columns is the final answer. Code for this solution is given below.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pairll = pair<ll, ll>;
#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);
bool islit(ll n, ll m, ll row, ll k, const vector<pairll>& towers) {
vector<pairll> segs;
for (pairll t : towers) {
ll dy = abs(t.second-row);
if (dy >= k) continue; // out of range
ll diff = k-dy-1;
segs.push_back({t.first-diff,t.first+diff});
}
if (segs.size() == 0) return false;
sort(segs.begin(), segs.end()); // by left endpoint
if (segs[0].first > 0) return false; // non-lit at left
ll r = segs[0].second;
for (pairll seg : segs) {
if (seg.first > (r+1)) break; // break on gap
r = max(r, seg.second);
}
if (r >= (n-1)) return true; // lit from 0 to n-1
return false;
}
int main() {
io_optimize();
int t;
cin >> t;
for (int _ = 0; _ < t; _++) {
ll n, m;
cin >> n >> m;
vector<pairll> towers(m);
for (ll i = 0; i < m; i++) {
ll x, y;
cin >> x >> y;
x--;
y--;
towers[i] = {x, y};
}
ll ans = 0;
for (ll r = 0; r < n; r++) {
ll lk = 0;
ll rk = 2*n-1;
while (lk < rk) {
ll mk = lk + (rk-lk)/2;
if (islit(n, m, r, mk, towers)) rk = mk;
else lk = mk+1;
}
ans = max(ans, lk);
}
cout << ans << endl;
}
}
A more in-depth tutorial for this problem will be written soon.
Which ghost should Stanley steal from each turn?
What is the state of Polly's ghosts after she splits and Stanley takes his turn?
When should Polly start choosing pairs of ghosts instead of splitting?
Note that it is always optimal for Polly to split a ghost as evenly as possible, and for Stanley to steal from the ghost with the most spirits. Polly should also avoid choosing a pair of ghosts to add to until she has enough ghosts to win ($$$6*{ghosts} + 5 \geq x$$$), unless she needs a ghost with more than one spirit in order to split.
From there, a recursive implementation will pass under the constraints, keeping track of Stanley's total and the highest-value ghost that Polly has, along with the total number of ghosts. (Note that we don't need to keep track of all ghosts, because all but one of them will be holding $1$s due to Stanley stealing, until Polly decides to start adding pairs.)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);
void solve(ll ghosts, ll highest, ll stanley, ll goal, ll round) {
// Assume Calvin has 1,1,1,1,...,1,highest
// (It can be shown that this is always optimal for Calvin)
//cerr << ghosts << " " << highest << " " << stanley << " " << goal << " " << round << endl;
if (stanley >= goal) {
// Stanley won on his turn last round
cout << "Stanley " << endl << (round-1) << endl;
} else if (ghosts == 1) {
// Stanley cannot win off of Calvin's first move, so no need to check
solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
} else if (highest + 10 + ghosts - 1 >= goal) {
// Calvin can immediately choose a pair and +5 +5 to win
cout << "Calvin " << endl << round << endl;
} else {
if (6*ghosts + 5 >= goal) {
// if we're here, note that we cannot win from a single +5/+5
// ignore the base 1s in this calculation (5 10s instead of 6 11s, easier)
ll needed = goal - ghosts;
ll turns = 0;
ll stanleydelta = 0;
// who wins first
if (highest >= 6) {
// Calvin immediately wins on his final +10, otherwise we net +5 every turn
// Note that Calvin also starts with +10, since Stanley will spend his turn stealing from highest
// (This does not win for Stanley, see first comment of parent "if")
// add 10, stanley takes highest-1
needed-=10;
stanleydelta+=(highest-1);
// inefficient but fine in the slow sol
while (needed > 10) {
needed-=5;
stanleydelta+=5;
turns++;
}
// Calvin wins on this turn
if (stanley + stanleydelta < goal) {
cout << "Calvin" << endl << (round+turns) << endl;
return;
}
} else {
// Calvin immediately wins on his final +10, otherwise we net +5 every turn
// In this case, highest is left alone unless Calvin +5s on it
needed -= (highest-1);
ll gleft = ghosts-1;
while (needed > 10) {
if (gleft == 1) {
// we dont win when +10
needed -= 10;
needed += (5 + highest - 1);
stanleydelta += (5 + highest - 1);
} else {
needed -= 5;
stanleydelta += 5;
}
gleft--;
turns++;
}
// Calvin wins on this turn
if (stanley + stanleydelta < goal) {
cout << "Calvin" << endl << (round+turns) << endl;
return;
}
}
// If doing so would hand a win to Stanley, then he will delay
// Note that at this point, it can be shown that it is impossible for Calvin to win
// So, he will "stall" as long as possible
if (highest == 1) {
// O(1) calculation to determine how much Calvin can stall
// Every 3 turns
// 1 1 -> 1 6 (+5) -> 1 1 3 (+7) -> 1 1 1 1 (+8)
ll stanleyleft = goal - stanley;
ll stall = 3 * (stanleyleft/8);
stanleyleft %= 8;
if (stanleyleft > 5) stall+=2;
else if (stanleyleft != 0) stall += 1;
cout << "Stanley " << endl << (round+stall-1) << endl;
} else {
// Highest/2 with each iteration, so efficient
solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
}
} else {
if (highest == 1) {
// Calvin is forced to +5 + 5
solve(ghosts, 6, stanley+5, goal, round+1);
} else {
solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
}
}
}
}
int main() {
io_optimize();
// io_file("input.txt", "output.txt");
// ----- WRITE CODE HERE ----- //
int t;
cin >> t;
for (int _ = 0; _ < t; _++) {
ll n, x;
cin >> n >> x;
//cerr << "test case " << n << " " << x << endl;
solve(1, n, 0, x, 1);
}
}
Adv. K — The Mist (Hard Version)
A more in-depth tutorial for this problem will be written soon.
Treat each encoding as being sorted rather than shuffled.
Besides the digits themselves, there is one more piece of information that is preserved during a shuffle (or sort).
Treat each encoding as being sorted rather than shuffled. We can now assign an ordering number to each sorted arrangement. Note that because we don't need to use all 67 trees, we can encode additional information via the length of our encoding. Via stars-and-bars and combinations, we have enough possible sorted arrangements to assign each an ordering number from 1 to $$$10^{12}$$$. Now, all one needs to do is to write a function that determines what ordering number corresponds to a sorted arrangement. This can be done by going left-to-right through the sorted encoding and using combinations to count how many sorted orderings are lexographically less than the given encoding.
from math import comb
def encode(a):
assert len(a) == 12
num = int(a) + 1
x = 0
digits = 1
next_comb = comb(digits + 9, 9)
while x + next_comb < num:
digits += 1
x += next_comb
next_comb = comb(digits + 9, 9)
assert digits <= 67
i = 0
for d in range(digits, 0, -1):
next_comb = comb(d - 1 + 9 - i, 9 - i)
while x + next_comb < num:
i += 1
x += next_comb
next_comb = comb(d - 1 + 9 - i, 9 - i)
print(i, end='')
print()
def decode(a):
a = sorted(a)
x = 0
i = 0
digits = len(a)
assert digits <= 67
for d in range(1, digits):
next_comb = comb(d + 9, 9)
x += next_comb
for d in range(digits, 0, -1):
val = int(a[digits - d])
while i < val:
next_comb = comb(d - 1 + 9 - i, 9 - i)
x += next_comb
i += 1
print(f"{x:012}")
mode = input().strip()
n = int(input().strip())
for _ in range(n):
a = input().strip()
if mode == "encode":
encode(a)
elif mode == "decode":
decode(a)
Adv. L — Trick-or-Treat Lane (Advanced Division)
A more in-depth tutorial for this problem will be written soon.
Moving left is never optimal.
When should Polly change costumes?
Read the editorial for the Standard Division version of this problem. A similar "stopping point" approach works here, but what does the stopping point signify this time?
Our stopping point is the only house Polly should change costumes at.
The stopping point should be a cumulative maximum of all houses Polly has visited so far.
How should Polly use her leftover time?
Placeholder
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* one-indexed */
struct Fenwick {
vector<ll> bits;
ll n;
Fenwick(ll n) {
this->n = n;
bits.assign(n+1, 0);
}
void add(ll idx, ll val) {
for (; idx <= n; idx += idx & -idx) bits[idx] += val;
}
ll sum(ll idx) {
ll res = 0;
for (; idx > 0; idx -= idx & -idx) res += bits[idx];
return res;
}
ll revsum(ll idx) {
if (idx <= 0) return -1;
return sum(n) - sum(idx-1);
}
};
#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);
const ll maxQual = 1e4;
int main() {
io_optimize();
int t;
cin >> t;
for (int _ = 0; _ < t; _++) {
ll n, x;
cin >> n >> x;
vector<ll> a(n);
for (ll i = 0; i < n; i++) cin >> a[i];
Fenwick csum(maxQual);
Fenwick ccnt(maxQual);
ll best = 0;
ll curmax = 0;
for (ll i = 0; i < n; i++) {
// optimal solution repeats at a prefix max
if (a[i] <= curmax) {
csum.add(a[i], a[i]);
ccnt.add(a[i], 1);
continue;
}
curmax = a[i];
// stopping at i
ll score = 0;
ll time = 0;
// movement + first claim
time += (i+1);
score += a[i];
ll left = x - time;
if (left < 0) break;
ll req = (a[i]/2) + 1; // minimum quality to consider visiting
ll psum = csum.revsum(req);
ll pcnt = ccnt.revsum(req);
if (pcnt > left) {
// find smallest req (> baseline) such that ccnt.revsum(req) <= left
ll lo = req;
ll hi = a[i];
while (lo < hi) {
ll mid = (lo+hi)/2;
if (ccnt.revsum(mid) > left) {
lo = mid+1;
} else if (ccnt.revsum(mid) <= left) {
hi = mid;
}
}
req = lo;
psum = csum.revsum(req);
pcnt = ccnt.revsum(req);
// todo: compensate for partial sum?
}
ll margin = left - pcnt;
if (margin % 2 == 0) {
// always optimal to choose these, and use remainders to cleanly get repeats
// check if we can partially use the "next highest house"
// i.e. 5 5 5 5 5 6 with x = 10
if (req > (a[i]/2 + 1)) {
ll cand = req-1;
// note that due to how we choose req, we don't have the margin to choose EVERY house with quality cand
// instead, we choose as many as we can
psum += cand*margin;
margin = 0;
}
score += psum;
score += (margin/2)*a[i];
} else {
// case 1: visit 1 more house
// case 2: visit 1 less house, get 1 more repetition
score += psum;
score += ((margin-1)/2)*a[i];
//cout << i << " ";
//cout << score << " " << margin << endl;
// case 1
// binary search for last candidate such that ccnt.revsum(cand) > pcnt; that's the next highest house
// note that there may be multiple of these! (see the pcnt > left binsearch at the start)
// however, an optimal solution won't take ALL of these, because we'd either run out of time
// or at least tie by taking repetitions of stopping point instead
ll temp1 = score;
ll lo = 1;
ll hi = req;
while (lo < hi) {
ll mid = (lo+hi+1)/2;
if (ccnt.revsum(mid) > pcnt) {
lo = mid;
} else if (ccnt.revsum(mid) <= pcnt) {
hi = mid-1;
}
}
ll cand = lo;
if (ccnt.revsum(cand) > pcnt) {
// a "next highest house" exists
ll candcnt = ccnt.revsum(cand) - pcnt;
temp1 += cand;
candcnt--;
if (candcnt > 0 && (cand * 2 > a[i])) {
ll reps = (margin-1)/2;
temp1 -= min(reps, candcnt/2)*a[i];
temp1 += min(reps, candcnt/2)*2*cand;
}
} else {
// a "next highest house" doesn't exist
// case 2 will be better in this case
// (unless first element, in which score is the answer)
}
// case 2
// find the smallest candidate such that ccnt.revsum(cand) < pcnt; (cand-1) is the smallest house
ll temp2 = score;
lo = req;
hi = a[i];
while (lo < hi) {
ll mid = (lo+hi)/2;
if (ccnt.revsum(mid) >= pcnt) {
lo = mid+1;
} else if (ccnt.revsum(mid) < pcnt) {
hi = mid;
}
}
cand = lo-1;
if (pcnt == 0) {
// we never picked anything in the first place
// case 1 will be better in this case
// (unless first element, in which score is the answer)
} else if (ccnt.revsum(cand+1) < pcnt) {
// exists
temp2 -= cand;
temp2 += a[i];
}
score = max(temp1, temp2);
}
csum.add(a[i], a[i]);
ccnt.add(a[i], 1);
best = max(score, best);
}
cout << best << endl;
}
}
Auto comment: topic has been updated by pilliamw (previous revision, new revision, compare).