Submission #22517

#	Time	Username	Problem	Language	Result	Execution time	Memory
22517		퍼플달고싶다 (#40)	Unifying Values (KRIII5_UV)	C++14	7 / 7	466 ms	2956 KiB

UV

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
long long sum[10002];
long long arr[10002];
int start[10002];
const long long mod=1e9+7;
long long dp[10002];
vector<long long > valid;
int n;
long long go(int idx,long long sm){
    if(dp[idx]!=-1)return dp[idx];
    if(idx==n+1)return dp[idx]=1;
    dp[idx]=0;
    for(int i=idx;i<=n;i++){
        if(sum[i]-sum[idx-1]==sm){
            dp[idx]=(dp[idx]+go(i+1,sm));
            dp[idx]%=mod;
        }
    }
    return dp[idx];
}
long long fastPow(int k){
    if(k<0)return 0;
    long long ret=1;
    long long two=2;
    for(int i=0;i<20;i++){
        if(k&(1<<i)){
            ret=(ret*two)%mod;
            k-=(1<<i);
        }
        two=(two*two)%mod;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum[i]=sum[i-1]+arr[i];
    }
    for(int i=1;i<=n;i++){
        if(sum[i]!=0 && sum[n]%sum[i]==0){
            valid.push_back(sum[i]);
        }
    }
    sort(valid.begin(),valid.end());
    valid.erase(unique(valid.begin(),valid.end()),valid.end());
    //sum[n]=0인경우 예외처리
    if(sum[n]==0)valid.clear(),valid.push_back(0);
    for(int i=0;i<valid.size();i++){
        for(int j=1;j<n;j++){
            if(sum[j]==valid[i]){
                start[i]=j;
                break;
            }
        }
    }
    long long ans=0;
    for(int i=0;i<valid.size();i++){
        memset(dp,-1,sizeof(dp));
        long long num=valid[i];
        ans=(ans+go(1,valid[i]))%mod;
    }
    cout<<(ans+mod-1)%mod;
    return 0;
}

Compilation message (stderr)

UV.cpp: In function 'int main()':
UV.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<valid.size();i++){
                  ^
UV.cpp:77:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<valid.size();i++){
                  ^
UV.cpp:79:19: warning: unused variable 'num' [-Wunused-variable]
         long long num=valid[i];
                   ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5