洛谷：去年天气旧亭台

Question

题目背景（洛谷的题：去年天气旧亭台）

依旧是过往的天气，过往的楼台烟雨。时间悄悄流逝着，山河仍在，人却已不是过去的人……
题目描述

登上楼台，旧时满面沉灰的地板映入眼帘。

共有 nn 块地板，地板分为两类，第 ii 块地板的类别用 cici​ 表示，积灰程度用 aiai​ 表示。注意 cici​ 为 00 或 11。

现在要清理这些地板上的灰尘。每次操作中，你可以：

选择两个下标 i,ji,j，满足 1≤i≤j≤n1≤i≤j≤n， ci=cjci​=cj​，且第 ii 块和第 jj 块地板上的灰尘均未被清理过；
花费 ai+ajai​+aj​ 的能量清理第 ii 块到第 jj 块所有地板上的灰尘。

求清理完所有地板上的灰尘至少要多少能量。
输入格式

本题有多组测试数据。

第一行一个整数 TT，表示测试数据组数。

对于每组测试数据：

第一行一个整数 n。
第二行 n 个整数 a1,a2,…,an
第三行 n 个整数 c1,c2,…,cn

输出格式

对于每组测试数据，一行一个整数表示最小能量。
输入输出样例
输入 #1

2
6
1 1 4 5 1 4
1 0 0 1 0 1
8
3 1 4 1 5 9 2 6
1 0 1 0 1 0 1 0

输出 #1

5
13

说明/提示

【样例 1 解释】

对于第一组数据，直接花费 a1+a6=5a1​+a6​=5 的能量清理所有灰尘。
对于第二组数据，先花费 a1+a1=6a1​+a1​=6 的能量清理第一个地板上的灰尘，再花费 a2+a8=7a2​+a8​=7 的能量清理剩余灰尘。

【数据规模与约定】

对于 10%的数据，保证 T≤10T≤10，n≤10n≤10；

对于 40% 的数据，保证 T≤20T≤20，n≤103n≤103；

另有 10% 的数据，保证 ci=1ci​=1；

对于 100% 的数据，保证 1≤T≤1051≤T≤105，1≤n,∑n≤2×106,1≤n，ci∈{0,1}}，1≤ai≤109

我的代码如下：

t=int(input())
for w in range(t):
    n=int(input())
    l1=list(map(int,input().split()))
    l2=list(map(int,input().split()))
    l3=l2[::-1]
    l4=l1[::-1]
    res=[]
    for i in range(len(l2)):
        for j in range(len(l3)):
            if l2[i]==l3[j]:
                a=l1[i]+l1[n-1-j]
                if i==j==0 or i==j==n:
                    res.append(l1[i]+l1[n-1-j])
                elif i+j==1:
                    if i>j: 
                        res.append(a+2*l1[0])
                    else:
                        res.append(a+2*l1[n-1])
                elif i+j==2:
                    if i==2:
                        if l2[0]==l2[1]:
                            res.append(a+l1[0]+l1[1])
                        else:
                            res.append(a+2*(l1[0]+l1[1]))
                    elif j==2:
                        if l3[0]==l3[1]:
                            res.append(a+l4[0]+l4[1])
                        else:
                            res.append(a+2*(l4[0]+l4[1]))
    print(min(res))

在vscode里运行样例结果正确的，我的时间复杂度应该是n**2，讲道理没有超过限制，但是提交时既显示运行错误，也显示超时是为什么？有没有强者能指点一下

Answer 1

解决了，但是只能拿80，有两个测试点内存超限。这是参考别人的思路用python写的

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))#积灰程度
    c = list(map(int, input().split()))#类别
    if c[0]==c[n-1]:
        print(a[0]+a[n-1])
    else:
        res=5000000000
        for i in range(n):  #列表中必然有一个下标为i的，满足下面这个判断式，从而两组直接解决，是除了一组直接解决的最小情况且一定存在。
            if c[0]==c[i] and c[i+1]==c[n-1]:
                res=min(res,a[0]+a[i]+a[i+1]+a[n-1])
        print(res)