E 题 这样是正解吗 感觉怪怪的

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;

int n, m, k;
int a[N];
int ans = 0;
int s[N];
int cnt[N];

signed main(){
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i] , cnt[i] = cnt[i - 1] + (a[i] > 0);
    
    for(int i = 1; i + 2 <= n; i++)
    {
        if(s[n] != 3 * s[i] || !cnt[i])continue;
        for(int j = i + 1; j + 1 <= n; j++)
        {
            int l = s[i], mid = s[j] - s[i], r = s[n] - s[j];
            if(l == r && l == mid && cnt[i] && cnt[j] - cnt[i] && cnt[n] - cnt[j]) ans ++;
        }
    }
    
    cout << ans;
    return 0;
}

全部评论
如果是一个2e5长度的1 -1重复的串,那么ans的大小将来到组合数C(1e5-1,2),会超时
1 回复 分享
发布于 2024-11-25 08:25 河南
不知道啊,但是O(n)能写
1 回复 分享
发布于 2024-11-24 21:19 浙江
至少存在一个正数  0 不是正数 赛时取到等号了  如果不是负数 那么区间是3倍数的情况很少 应该是可以证明出来的吗?
点赞 回复 分享
发布于 2024-11-24 21:16 湖南

相关推荐

不愿透露姓名的神秘牛友
今天 11:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务