看看我的教训吧,不要再走我的老路了
我一看到这道题:哇!这么简单!然后用暴力来写
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
s+=a[i]*a[j];
}
}
恭喜我,获得30分!
照这样计算,时间复杂度就是o(n2)
最坏结果是(2×105)×(2×105)也就是4×1010!
必定超时!
所以我换了一个思路,用前缀和来写,但是我没开long long,所以这样了
千万记住这句话
“十年OI一场空,不开long long见祖宗。”
尽量都开long long,不会对内存有多大影响(毕竟这道题的内存限制是128MB)