結果

問題 No.2956 Substitute with Average
コンテスト
ユーザー lmxyue
提出日時 2025-08-25 14:16:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,320 ms / 3,000 ms
コード長 1,366 bytes
コンパイル時間 4,571 ms
コンパイル使用メモリ 256,964 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2025-08-25 14:17:23
合計ジャッジ時間 23,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 1000000000000000000LL


int main(){
        
        int n;
        cin>>n;
        vector<long long> a(n);
        rep(i,n){
                cin>>a[i];
        }
        
        long long ans = n;
        ans *= n+1;
        ans /= 2;
        ans++;
        
        for(int i=1;i<=30;i++){
                
                rep(j,2){
                        map<int,long long> mp;
                        if(a[0]!=i || j==0){
                                mp[0]++;
                        }
                        long long cur = 0;
                        rep(k,n){
                                cur += a[k]-i;
                                if(a[k]==i){
                                        ans -= mp[cur];
                                }
                                if(k!=n-1 && a[k+1]==i){
                                        if(j==0)mp[cur]++;
                                }
                                else mp[cur]++;
                        }
                        reverse(a.begin(),a.end());
                }
                
        }
        cout<<ans<<endl;
        
        
        return 0;
}
0