oj.uz

Submission #22932

# Submission time Handle Problem Language Result Execution time Memory
22932 2017-04-30T14:00:11 Z sgc109 Unifying Values (KRIII5_UV) C++11
0 / 7
 500 ms 3120 KB 
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;	
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

int N;
ll dp[10003];
ll pSum[10003];
ll A[10003];
vl valid;

ll go(int pos, ll sum){
	if(pos > N) return 1;
	ll& cache = dp[pos];
	if(cache != -1) return cache;
	cache = 0;
	for(int i = pos; i <= N; i++){
		if(pos==1 && i==N) continue;
		if(pSum[i]-pSum[pos-1] != sum) continue;
		cache = (cache + go(i+1, sum)) % MOD;
	}

	return cache;
}
int main() {
	inp1(N);
	FOR(i,N){
		scanf("%lld",A+i);
		pSum[i+1] = pSum[i] + A[i];
		valid.pb(pSum[i+1]);
	}
	sort(all(valid));
	valid.erase(unique(all(valid)),valid.end());

	ll ans = 0 ;
	FOR(i,sz(valid)){
		memset(dp,-1,sizeof(dp));
		ans = (ans + go(1, valid[i])) % MOD;
	}

	printf("%lld",ans);
	return 0;
}

Compilation message

UV.cpp: In function 'int main()':
UV.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  inp1(N);
         ^
UV.cpp:53:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",A+i);
                    ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2252 KB Output is correct
2 Correct 0 ms 2252 KB Output is correct
3 Correct 0 ms 2252 KB Output is correct
4 Execution timed out 500 ms 3120 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 2532 KB Output is correct
2 Correct 456 ms 2540 KB Output is correct
3 Correct 469 ms 2536 KB Output is correct
4 Correct 266 ms 2524 KB Output is correct
5 Correct 293 ms 2524 KB Output is correct
6 Correct 279 ms 2524 KB Output is correct
7 Correct 439 ms 2540 KB Output is correct
8 Correct 449 ms 2528 KB Output is correct
9 Correct 153 ms 2524 KB Output is correct
10 Correct 156 ms 2524 KB Output is correct
11 Correct 189 ms 2524 KB Output is correct
12 Correct 203 ms 2524 KB Output is correct
13 Correct 206 ms 2524 KB Output is correct
14 Correct 233 ms 2524 KB Output is correct
15 Correct 216 ms 2524 KB Output is correct
16 Correct 219 ms 2524 KB Output is correct
17 Execution timed out 500 ms 3116 KB Execution timed out
18 Halted 0 ms 0 KB -