892764d484 2014-09-17 kinaba: #include <iostream> 892764d484 2014-09-17 kinaba: #include <sstream> 892764d484 2014-09-17 kinaba: #include <iomanip> 892764d484 2014-09-17 kinaba: #include <vector> 892764d484 2014-09-17 kinaba: #include <string> 892764d484 2014-09-17 kinaba: #include <map> 892764d484 2014-09-17 kinaba: #include <set> 892764d484 2014-09-17 kinaba: #include <algorithm> 892764d484 2014-09-17 kinaba: #include <numeric> 892764d484 2014-09-17 kinaba: #include <iterator> 892764d484 2014-09-17 kinaba: #include <functional> 892764d484 2014-09-17 kinaba: #include <complex> 892764d484 2014-09-17 kinaba: #include <queue> 892764d484 2014-09-17 kinaba: #include <stack> 892764d484 2014-09-17 kinaba: #include <cmath> 892764d484 2014-09-17 kinaba: #include <cassert> 892764d484 2014-09-17 kinaba: #include <tuple> 892764d484 2014-09-17 kinaba: using namespace std; 892764d484 2014-09-17 kinaba: typedef long long LL; 892764d484 2014-09-17 kinaba: typedef complex<double> CMP; 892764d484 2014-09-17 kinaba: 892764d484 2014-09-17 kinaba: class PotentialArithmeticSequence { public: 892764d484 2014-09-17 kinaba: int numberOfSubsequences(vector <int> d) 892764d484 2014-09-17 kinaba: { 892764d484 2014-09-17 kinaba: int cnt = 0; 892764d484 2014-09-17 kinaba: for(int s=0; s<d.size(); ++s) 892764d484 2014-09-17 kinaba: for(int e=s+1; e<=d.size(); ++e) 892764d484 2014-09-17 kinaba: if(incr(vector<int>(d.begin()+s, d.begin()+e))) 892764d484 2014-09-17 kinaba: ++cnt; 892764d484 2014-09-17 kinaba: return cnt; 892764d484 2014-09-17 kinaba: } 892764d484 2014-09-17 kinaba: 892764d484 2014-09-17 kinaba: bool incr(vector<int> d) 892764d484 2014-09-17 kinaba: { 892764d484 2014-09-17 kinaba: int mi = max_element(d.begin(), d.end()) - d.begin(); 892764d484 2014-09-17 kinaba: int& M = d[mi]; 892764d484 2014-09-17 kinaba: 892764d484 2014-09-17 kinaba: // Can assume a[mi] == 1<<M. 892764d484 2014-09-17 kinaba: M = min(M, 8); 892764d484 2014-09-17 kinaba: for(int i=0; i<d.size(); ++i) { 892764d484 2014-09-17 kinaba: int a = (1<<M)-mi+i; 892764d484 2014-09-17 kinaba: if(a<=0) 892764d484 2014-09-17 kinaba: return false; 892764d484 2014-09-17 kinaba: if(d[i]>M) 892764d484 2014-09-17 kinaba: return false; 892764d484 2014-09-17 kinaba: if(((a>>d[i])&1) == 0) 892764d484 2014-09-17 kinaba: return false; 892764d484 2014-09-17 kinaba: if(a & ((1<<d[i])-1)) 892764d484 2014-09-17 kinaba: return false; 892764d484 2014-09-17 kinaba: } 892764d484 2014-09-17 kinaba: return true; 892764d484 2014-09-17 kinaba: } 892764d484 2014-09-17 kinaba: }; 892764d484 2014-09-17 kinaba: 892764d484 2014-09-17 kinaba: // BEGIN CUT HERE 892764d484 2014-09-17 kinaba: #include <ctime> 892764d484 2014-09-17 kinaba: double start_time; string timer() 892764d484 2014-09-17 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 892764d484 2014-09-17 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 892764d484 2014-09-17 kinaba: { os << "{ "; 892764d484 2014-09-17 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 892764d484 2014-09-17 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 892764d484 2014-09-17 kinaba: void verify_case(const int& Expected, const int& Received) { 892764d484 2014-09-17 kinaba: bool ok = (Expected == Received); 892764d484 2014-09-17 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 892764d484 2014-09-17 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 892764d484 2014-09-17 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 892764d484 2014-09-17 kinaba: #define END verify_case(_, PotentialArithmeticSequence().numberOfSubsequences(d));} 892764d484 2014-09-17 kinaba: int main(){ 892764d484 2014-09-17 kinaba: 892764d484 2014-09-17 kinaba: CASE(0) 892764d484 2014-09-17 kinaba: int d_[] = {0,1,0,2,0,1,0}; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = 28; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: CASE(1) 892764d484 2014-09-17 kinaba: int d_[] = {0,0,0,0,0,0,0}; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = 7; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: CASE(2) 892764d484 2014-09-17 kinaba: int d_[] = {0,0,0,0,1,1,1}; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = 8; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: CASE(3) 892764d484 2014-09-17 kinaba: int d_[] = {0,100,0,2,0}; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = 11; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: CASE(4) 892764d484 2014-09-17 kinaba: int d_[] = {1,11,3,0,1,0,1,0,1,0,1,0,3,0,2,0,0,0,0,1,2,3,20}; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = 49; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: /* 892764d484 2014-09-17 kinaba: CASE(5) 892764d484 2014-09-17 kinaba: int d_[] = ; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = ; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: CASE(6) 892764d484 2014-09-17 kinaba: int d_[] = ; 892764d484 2014-09-17 kinaba: vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_)); 892764d484 2014-09-17 kinaba: int _ = ; 892764d484 2014-09-17 kinaba: END 892764d484 2014-09-17 kinaba: */ 892764d484 2014-09-17 kinaba: } 892764d484 2014-09-17 kinaba: // END CUT HERE