### [user:thegscrypto.bot,2026-05-24]↵
↵
Evidence↵
------------------↵
↵
1. Lots of WA1/RE1/Compilation Error submissions↵
↵
2. AI commented codes: [submission: 375834481] [submission: 375825486] [submission:375825486]. Mostly all of his submission are like this↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:1,option1]↵
↵
No, (comment why you think this) [likes:1,option2]↵
↵
### [user:Harshaii,2026-05-24]↵
↵
Evidence↵
------------------↵
↵
AI commented codes: [submission: 375846083 ] [submission: 375846083]↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:2,option1]↵
↵
No, (comment why you think this) [likes:2,option2]↵
↵
↵
### [user:gopal.thecoder,2026-05-24]↵
↵
Evidence↵
------------------↵
↵
[submission:375836893]... bruh↵
↵
(if you can't view this submission, here's the code)↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
I completely understand how frustrating that is! My previous fix strictly resolved the C# compilation error (the variable naming conflict) so your code could finally compile and run, but it left your underlying mathematical logic untouched.↵
↵
Now that the code is executing, the "Wrong Answer" is exposing a very subtle **sign error** in your Convex Hull Trick query for the left side (`tr2`).↵
↵
### The Math Behind the Bug↵
↵
For the right side (`tr1`), you want to maximize the score. Mathematically, the expression you are optimizing for index $i$ is:↵
↵
↵
$$s[i] - s[m] - (i - m) \cdot h[m]$$↵
↵
Which expands and groups to:↵
↵
↵
$$(s[i]) - (h[m]) \cdot i - s[m] + m \cdot h[m]$$↵
↵
Your `Query` function evaluates $y - M \cdot x$. For `tr1`, $y = s[i]$, $x = i$, and you correctly pass $M = h[m]$. This flawlessly matches the equation.↵
↵
**However, for the left side (`tr2`)**, you want to maximize the score going backwards. That expression is:↵
↵
↵
$$s[m-1] - s[i-1] - (m - i) \cdot h[m]$$↵
↵
Let's expand and group this one:↵
↵
↵
$$(-s[i-1]) + h[m] \cdot i + s[m-1] - m \cdot h[m]$$↵
↵
Notice the **$+ h[m] \cdot i$**.↵
Since your `Query` function subtracts the slope term ($y - M \cdot x$), to get a positive $h[m] \cdot i$, you **must** pass $-h[m]$ as the slope. In your code, you passed a positive `h[m]`:↵
↵
```csharp↵
// WRONG↵
long mxvl = tr2.Query(1, 1, n, a2, b2, h[m]) + s[m - 1] - (long)m * h[m];↵
↵
```↵
↵
This forces the tree to evaluate $-s[i-1] - h[m] \cdot i$, which completely breaks the calculation and underestimates the score.↵
↵
### The Fix↵
↵
Change `h[m]` to `-h[m]` in the `tr2.Query` call.↵
↵
Here is the fully corrected code with the mathematical fix applied.↵
↵
```csharp↵
// Author => Gopal↵
↵
using System;↵
using System.IO;↵
↵
#pragma warning disable CS8618 ↵
↵
class GRoadworks↵
{↵
struct Point↵
{↵
public long x, y;↵
}↵
↵
class ConvexHST↵
{↵
private Point[] hull;↵
private int[] hullst;↵
private int[] hullln;↵
private int hulllptr;↵
public ConvexHST(int n)↵
{↵
hull = new Point[n * 20];↵
hullst = new int[4 * n + 5];↵
hullln = new int[4 * n + 5];↵
}↵
public void clear()↵
{↵
hulllptr = 0;↵
}↵
private bool Bad(Point a, Point b, Point c)↵
{↵
Int128 dx1 = b.x - a.x;↵
Int128 dy1 = b.y - a.y;↵
Int128 dx2 = c.x - a.x;↵
Int128 dy2 = c.y - a.y;↵
return dx1 * dy2 - dy1 * dx2 >= 0;↵
}↵
↵
public void build(int nd, int l, int r, long[] x, long[] y)↵
{↵
hullst[nd] = hulllptr;↵
int len = 0;↵
int strt = hulllptr;↵
for (int i = l; i <= r; i++)↵
{↵
Point p = new Point { x = x[i], y = y[i] };↵
while (len >= 2)↵
{↵
Point a = hull[strt + len - 2];↵
Point b = hull[strt + len - 1];↵
if (Bad(a, b, p)) len--;↵
else break;↵
}↵
hull[strt + len] = p;↵
len++;↵
}↵
hullln[nd] = len;↵
hulllptr += len;↵
if (l == r) return;↵
int mid = l + (r-l) / 2;↵
build(2 * nd, l, mid, x, y);↵
build(2 * nd + 1, mid + 1, r, x, y);↵
}↵
↵
public long Query(int nd, int l, int r, int ql, int qr, long m)↵
{↵
if (ql <= l && r <= qr)↵
{↵
int lt = 0, rt = hullln[nd] - 1;↵
int strt = hullst[nd];↵
while (lt < rt)↵
{↵
int mid = lt + (rt - lt) / 2;↵
Point p1 = hull[strt + mid];↵
Point p2 = hull[strt + mid + 1];↵
if (p2.y - p1.y >= m * (p2.x - p1.x)) lt = mid + 1;↵
else rt = mid;↵
}↵
return hull[strt + lt].y - m * hull[strt + lt].x;↵
}↵
int mdidx = l + (r - l) / 2;↵
long res = long.MinValue;↵
if (ql <= mdidx) res = Math.Max(res, Query(2 * nd, l, mdidx, ql, qr, m));↵
if (qr > mdidx) res = Math.Max(res, Query(2 * nd + 1, mdidx + 1, r, ql, qr, m));↵
return res;↵
}↵
}↵
↵
class FastIO↵
{↵
private Stream s;↵
private byte[] buf = new byte[1 << 20];↵
private int pos, len;↵
public FastIO(Stream strm) { s = strm; }↵
private int NextChar()↵
{↵
if (pos >= len)↵
{↵
pos = 0;↵
len = s.Read(buf, 0, buf.Length);↵
if (len == 0) return -1;↵
}↵
return buf[pos++];↵
}↵
↵
public long NextLong()↵
{↵
int c = NextChar();↵
while (c != -1 && c <= 32) c = NextChar();↵
if (c == -1) return 0;↵
long res = 0;↵
while (c > 32)↵
{↵
res = res * 10 + (c - '0');↵
c = NextChar();↵
}↵
return res;↵
}↵
public int NextInt() => (int)NextLong();↵
}↵
↵
static void Main()↵
{↵
using var strm = new BufferedStream(Console.OpenStandardInput(), 1 << 20);↵
FastIO io = new FastIO(strm);↵
using var wrt = new StreamWriter(Console.OpenStandardOutput(), bufferSize: 1 << 20);↵
int t = io.NextInt();↵
if (t == 0) return;↵
int mxn = 200005;↵
long[] h = new long[mxn];↵
long[] d = new long[mxn];↵
long[] e = new long[mxn];↵
long[] pe = new long[mxn];↵
long[] s = new long[mxn];↵
long[] xs = new long[mxn];↵
long[] y1 = new long[mxn];↵
long[] y2 = new long[mxn];↵
ConvexHST tr1 = new ConvexHST(mxn);↵
ConvexHST tr2 = new ConvexHST(mxn);↵
while (t-- > 0)↵
{↵
int n = io.NextInt();↵
long k = io.NextLong();↵
int x = io.NextInt();↵
for (int i = 1; i <= n; i++) h[i] = io.NextLong();↵
for (int i = 1; i < n; i++) d[i] = io.NextLong();↵
e[x] = 0;↵
for (int i = x + 1; i <= n; i++) e[i] = Math.Max(e[i - 1] + 1, d[i - 1]);↵
for (int i = x - 1; i >= 1; i--) e[i] = Math.Max(e[i + 1] + 1, d[i]);↵
int lmx = x, rmx = x;↵
while (lmx > 1 && e[lmx - 1] <= k) lmx--;↵
while (rmx < n && e[rmx + 1] <= k) rmx++;↵
↵
pe[x] = 0;↵
long crmx = h[x];↵
for (int i = x + 1; i <= n; i++)↵
{↵
if (e[i] > k) break;↵
long w = e[i] - e[i-1] - 1;↵
pe[i] = pe[i-1] + h[i] + w * crmx;↵
crmx = Math.Max(crmx, h[i]);↵
}↵
crmx = h[x];↵
for (int i = x - 1; i >= 1; i--)↵
{↵
if (e[i] > k) break;↵
long w = e[i] - e[i + 1] - 1;↵
pe[i] = pe[i + 1] + h[i] + w * crmx;↵
crmx = Math.Max(crmx, h[i]);↵
}↵
s[0] = 0;↵
for (int i = 1; i <= n; i++)↵
{↵
s[i] = s[i - 1] + h[i];↵
xs[i] = i;↵
y1[i] = s[i];↵
y2[i] = -s[i - 1];↵
}↵
tr1.clear();↵
tr1.build(1, 1, n, xs, y1);↵
tr2.clear();↵
tr2.build(1, 1, n, xs, y2);↵
long ans = 0;↵
for (int m = 1; m <= n; m++)↵
{↵
if (e[m] > k) continue;↵
long bsscr = pe[m] + (k - e[m]) * h[m];↵
int a1 = m;↵
int b1 = (int)Math.Min(rmx, m + k - e[m]);↵
if (a1 <= b1)↵
{↵
long mxvl = tr1.Query(1, 1, n, a1, b1, h[m]) - s[m] + (long)m * h[m];↵
ans = Math.Max(ans, bsscr + mxvl);↵
}↵
int a2 = (int)Math.Max(lmx, m - (k - e[m]));↵
int b2 = m;↵
if (a2 <= b2)↵
{↵
long mxvl = tr2.Query(1, 1, n, a2, b2, -h[m]) + s[m - 1] - (long)m * h[m];↵
ans = Math.Max(ans, bsscr + mxvl);↵
}↵
}↵
wrt.WriteLine(ans);↵
}↵
}↵
}↵
↵
```↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:3,option1]↵
↵
No, (comment why you think this) [likes:3,option2]↵
↵
↵
### [user:f20240621,2026-05-25]↵
↵
Evidence↵
------------------↵
↵
C2 submission: [submission:375822058], D submission: [submission:375824904], AI commented and different coding style↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:4,option1]↵
↵
No, (comment why you think this) [likes:4,option2]↵
↵
↵
### [user:Bitrelica,2026-05-25]↵
↵
Evidence↵
------------------↵
↵
Change of style in [submission:375799863] [submission:375800768] and [submission:375813042]. Impossible contest timing: (28:26 -> 29:47 -> 31:23 -> 37:17 -> 40:25...)↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:45,option1]↵
↵
No, (comment why you think this) [likes:45,option2]↵
↵
Comment other cheaters in the comments (include evidence too) :)↵
↵
[user:KAN,2026-05-24] [user:MikeMirzayanov,2026-05-24]
↵
Evidence↵
------------------↵
↵
1. Lots of WA1/RE1/Compilation Error submissions↵
↵
2. AI commented codes: [submission: 375834481] [submission: 375825486] [submission:375825486]. Mostly all of his submission are like this↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:1,option1]↵
↵
No, (comment why you think this) [likes:1,option2]↵
↵
### [user:Harshaii,2026-05-24]↵
↵
Evidence↵
------------------↵
↵
AI commented codes: [submission: 375846083 ] [submission: 375846083]↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:2,option1]↵
↵
No, (comment why you think this) [likes:2,option2]↵
↵
↵
### [user:gopal.thecoder,2026-05-24]↵
↵
Evidence↵
------------------↵
↵
[submission:375836893]... bruh↵
↵
(if you can't view this submission, here's the code)↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
I completely understand how frustrating that is! My previous fix strictly resolved the C# compilation error (the variable naming conflict) so your code could finally compile and run, but it left your underlying mathematical logic untouched.↵
↵
Now that the code is executing, the "Wrong Answer" is exposing a very subtle **sign error** in your Convex Hull Trick query for the left side (`tr2`).↵
↵
### The Math Behind the Bug↵
↵
For the right side (`tr1`), you want to maximize the score. Mathematically, the expression you are optimizing for index $i$ is:↵
↵
↵
$$s[i] - s[m] - (i - m) \cdot h[m]$$↵
↵
Which expands and groups to:↵
↵
↵
$$(s[i]) - (h[m]) \cdot i - s[m] + m \cdot h[m]$$↵
↵
Your `Query` function evaluates $y - M \cdot x$. For `tr1`, $y = s[i]$, $x = i$, and you correctly pass $M = h[m]$. This flawlessly matches the equation.↵
↵
**However, for the left side (`tr2`)**, you want to maximize the score going backwards. That expression is:↵
↵
↵
$$s[m-1] - s[i-1] - (m - i) \cdot h[m]$$↵
↵
Let's expand and group this one:↵
↵
↵
$$(-s[i-1]) + h[m] \cdot i + s[m-1] - m \cdot h[m]$$↵
↵
Notice the **$+ h[m] \cdot i$**.↵
Since your `Query` function subtracts the slope term ($y - M \cdot x$), to get a positive $h[m] \cdot i$, you **must** pass $-h[m]$ as the slope. In your code, you passed a positive `h[m]`:↵
↵
```csharp↵
// WRONG↵
long mxvl = tr2.Query(1, 1, n, a2, b2, h[m]) + s[m - 1] - (long)m * h[m];↵
↵
```↵
↵
This forces the tree to evaluate $-s[i-1] - h[m] \cdot i$, which completely breaks the calculation and underestimates the score.↵
↵
### The Fix↵
↵
Change `h[m]` to `-h[m]` in the `tr2.Query` call.↵
↵
Here is the fully corrected code with the mathematical fix applied.↵
↵
```csharp↵
// Author => Gopal↵
↵
using System;↵
using System.IO;↵
↵
#pragma warning disable CS8618 ↵
↵
class GRoadworks↵
{↵
struct Point↵
{↵
public long x, y;↵
}↵
↵
class ConvexHST↵
{↵
private Point[] hull;↵
private int[] hullst;↵
private int[] hullln;↵
private int hulllptr;↵
public ConvexHST(int n)↵
{↵
hull = new Point[n * 20];↵
hullst = new int[4 * n + 5];↵
hullln = new int[4 * n + 5];↵
}↵
public void clear()↵
{↵
hulllptr = 0;↵
}↵
private bool Bad(Point a, Point b, Point c)↵
{↵
Int128 dx1 = b.x - a.x;↵
Int128 dy1 = b.y - a.y;↵
Int128 dx2 = c.x - a.x;↵
Int128 dy2 = c.y - a.y;↵
return dx1 * dy2 - dy1 * dx2 >= 0;↵
}↵
↵
public void build(int nd, int l, int r, long[] x, long[] y)↵
{↵
hullst[nd] = hulllptr;↵
int len = 0;↵
int strt = hulllptr;↵
for (int i = l; i <= r; i++)↵
{↵
Point p = new Point { x = x[i], y = y[i] };↵
while (len >= 2)↵
{↵
Point a = hull[strt + len - 2];↵
Point b = hull[strt + len - 1];↵
if (Bad(a, b, p)) len--;↵
else break;↵
}↵
hull[strt + len] = p;↵
len++;↵
}↵
hullln[nd] = len;↵
hulllptr += len;↵
if (l == r) return;↵
int mid = l + (r-l) / 2;↵
build(2 * nd, l, mid, x, y);↵
build(2 * nd + 1, mid + 1, r, x, y);↵
}↵
↵
public long Query(int nd, int l, int r, int ql, int qr, long m)↵
{↵
if (ql <= l && r <= qr)↵
{↵
int lt = 0, rt = hullln[nd] - 1;↵
int strt = hullst[nd];↵
while (lt < rt)↵
{↵
int mid = lt + (rt - lt) / 2;↵
Point p1 = hull[strt + mid];↵
Point p2 = hull[strt + mid + 1];↵
if (p2.y - p1.y >= m * (p2.x - p1.x)) lt = mid + 1;↵
else rt = mid;↵
}↵
return hull[strt + lt].y - m * hull[strt + lt].x;↵
}↵
int mdidx = l + (r - l) / 2;↵
long res = long.MinValue;↵
if (ql <= mdidx) res = Math.Max(res, Query(2 * nd, l, mdidx, ql, qr, m));↵
if (qr > mdidx) res = Math.Max(res, Query(2 * nd + 1, mdidx + 1, r, ql, qr, m));↵
return res;↵
}↵
}↵
↵
class FastIO↵
{↵
private Stream s;↵
private byte[] buf = new byte[1 << 20];↵
private int pos, len;↵
public FastIO(Stream strm) { s = strm; }↵
private int NextChar()↵
{↵
if (pos >= len)↵
{↵
pos = 0;↵
len = s.Read(buf, 0, buf.Length);↵
if (len == 0) return -1;↵
}↵
return buf[pos++];↵
}↵
↵
public long NextLong()↵
{↵
int c = NextChar();↵
while (c != -1 && c <= 32) c = NextChar();↵
if (c == -1) return 0;↵
long res = 0;↵
while (c > 32)↵
{↵
res = res * 10 + (c - '0');↵
c = NextChar();↵
}↵
return res;↵
}↵
public int NextInt() => (int)NextLong();↵
}↵
↵
static void Main()↵
{↵
using var strm = new BufferedStream(Console.OpenStandardInput(), 1 << 20);↵
FastIO io = new FastIO(strm);↵
using var wrt = new StreamWriter(Console.OpenStandardOutput(), bufferSize: 1 << 20);↵
int t = io.NextInt();↵
if (t == 0) return;↵
int mxn = 200005;↵
long[] h = new long[mxn];↵
long[] d = new long[mxn];↵
long[] e = new long[mxn];↵
long[] pe = new long[mxn];↵
long[] s = new long[mxn];↵
long[] xs = new long[mxn];↵
long[] y1 = new long[mxn];↵
long[] y2 = new long[mxn];↵
ConvexHST tr1 = new ConvexHST(mxn);↵
ConvexHST tr2 = new ConvexHST(mxn);↵
while (t-- > 0)↵
{↵
int n = io.NextInt();↵
long k = io.NextLong();↵
int x = io.NextInt();↵
for (int i = 1; i <= n; i++) h[i] = io.NextLong();↵
for (int i = 1; i < n; i++) d[i] = io.NextLong();↵
e[x] = 0;↵
for (int i = x + 1; i <= n; i++) e[i] = Math.Max(e[i - 1] + 1, d[i - 1]);↵
for (int i = x - 1; i >= 1; i--) e[i] = Math.Max(e[i + 1] + 1, d[i]);↵
int lmx = x, rmx = x;↵
while (lmx > 1 && e[lmx - 1] <= k) lmx--;↵
while (rmx < n && e[rmx + 1] <= k) rmx++;↵
↵
pe[x] = 0;↵
long crmx = h[x];↵
for (int i = x + 1; i <= n; i++)↵
{↵
if (e[i] > k) break;↵
long w = e[i] - e[i-1] - 1;↵
pe[i] = pe[i-1] + h[i] + w * crmx;↵
crmx = Math.Max(crmx, h[i]);↵
}↵
crmx = h[x];↵
for (int i = x - 1; i >= 1; i--)↵
{↵
if (e[i] > k) break;↵
long w = e[i] - e[i + 1] - 1;↵
pe[i] = pe[i + 1] + h[i] + w * crmx;↵
crmx = Math.Max(crmx, h[i]);↵
}↵
s[0] = 0;↵
for (int i = 1; i <= n; i++)↵
{↵
s[i] = s[i - 1] + h[i];↵
xs[i] = i;↵
y1[i] = s[i];↵
y2[i] = -s[i - 1];↵
}↵
tr1.clear();↵
tr1.build(1, 1, n, xs, y1);↵
tr2.clear();↵
tr2.build(1, 1, n, xs, y2);↵
long ans = 0;↵
for (int m = 1; m <= n; m++)↵
{↵
if (e[m] > k) continue;↵
long bsscr = pe[m] + (k - e[m]) * h[m];↵
int a1 = m;↵
int b1 = (int)Math.Min(rmx, m + k - e[m]);↵
if (a1 <= b1)↵
{↵
long mxvl = tr1.Query(1, 1, n, a1, b1, h[m]) - s[m] + (long)m * h[m];↵
ans = Math.Max(ans, bsscr + mxvl);↵
}↵
int a2 = (int)Math.Max(lmx, m - (k - e[m]));↵
int b2 = m;↵
if (a2 <= b2)↵
{↵
long mxvl = tr2.Query(1, 1, n, a2, b2, -h[m]) + s[m - 1] - (long)m * h[m];↵
ans = Math.Max(ans, bsscr + mxvl);↵
}↵
}↵
wrt.WriteLine(ans);↵
}↵
}↵
}↵
↵
```↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:3,option1]↵
↵
No, (comment why you think this) [likes:3,option2]↵
↵
↵
### [user:f20240621,2026-05-25]↵
↵
Evidence↵
------------------↵
↵
C2 submission: [submission:375822058], D submission: [submission:375824904], AI commented and different coding style↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:4,option1]↵
↵
No, (comment why you think this) [likes:4,option2]↵
↵
↵
### [user:Bitrelica,2026-05-25]↵
↵
Evidence↵
------------------↵
↵
Change of style in [submission:375799863] [submission:375800768] and [submission:375813042]. Impossible contest timing: (28:26 -> 29:47 -> 31:23 -> 37:17 -> 40:25...)↵
↵
**Do you think its a cheater?**↵
↵
Yes! [likes:
↵
No, (comment why you think this) [likes:
↵
Comment other cheaters in the comments (include evidence too) :)↵
↵
[user:KAN,2026-05-24] [user:MikeMirzayanov,2026-05-24]
