445abb9772 2015-05-31 kinaba: #include <iostream> 445abb9772 2015-05-31 kinaba: #include <sstream> 445abb9772 2015-05-31 kinaba: #include <iomanip> 445abb9772 2015-05-31 kinaba: #include <vector> 445abb9772 2015-05-31 kinaba: #include <string> 445abb9772 2015-05-31 kinaba: #include <map> 445abb9772 2015-05-31 kinaba: #include <set> 445abb9772 2015-05-31 kinaba: #include <algorithm> 445abb9772 2015-05-31 kinaba: #include <numeric> 445abb9772 2015-05-31 kinaba: #include <iterator> 445abb9772 2015-05-31 kinaba: #include <functional> 445abb9772 2015-05-31 kinaba: #include <complex> 445abb9772 2015-05-31 kinaba: #include <queue> 445abb9772 2015-05-31 kinaba: #include <stack> 445abb9772 2015-05-31 kinaba: #include <cmath> 445abb9772 2015-05-31 kinaba: #include <cassert> 445abb9772 2015-05-31 kinaba: #include <tuple> 445abb9772 2015-05-31 kinaba: using namespace std; 445abb9772 2015-05-31 kinaba: typedef long long LL; 445abb9772 2015-05-31 kinaba: typedef complex<double> CMP; 445abb9772 2015-05-31 kinaba: 445abb9772 2015-05-31 kinaba: class ApplesAndOrangesEasy { public: 445abb9772 2015-05-31 kinaba: int maximumApples(int N, int K, vector <int> info) 445abb9772 2015-05-31 kinaba: { 445abb9772 2015-05-31 kinaba: vector<bool> ate_apple(N, false); 445abb9772 2015-05-31 kinaba: for(auto i: info) 445abb9772 2015-05-31 kinaba: ate_apple[i-1] = true; 445abb9772 2015-05-31 kinaba: for(int i=0; i<N; ++i) 445abb9772 2015-05-31 kinaba: if(!ate_apple[i]) { 445abb9772 2015-05-31 kinaba: ate_apple[i] = true; 445abb9772 2015-05-31 kinaba: if(!ok(N,K,ate_apple)) 445abb9772 2015-05-31 kinaba: ate_apple[i] = false; 445abb9772 2015-05-31 kinaba: } 445abb9772 2015-05-31 kinaba: return count(ate_apple.begin(), ate_apple.end(), true); 445abb9772 2015-05-31 kinaba: } 445abb9772 2015-05-31 kinaba: 445abb9772 2015-05-31 kinaba: bool ok(int N, int K, const vector<bool>& A) 445abb9772 2015-05-31 kinaba: { 445abb9772 2015-05-31 kinaba: int cnt = 0; 445abb9772 2015-05-31 kinaba: for(int i=0; i<N; ++i) { 445abb9772 2015-05-31 kinaba: if(A[i]) cnt++; 445abb9772 2015-05-31 kinaba: if(i-K>=0 && A[i-K]) cnt--; 445abb9772 2015-05-31 kinaba: if(cnt>K/2) 445abb9772 2015-05-31 kinaba: return false; 445abb9772 2015-05-31 kinaba: } 445abb9772 2015-05-31 kinaba: return true; 445abb9772 2015-05-31 kinaba: } 445abb9772 2015-05-31 kinaba: }; 445abb9772 2015-05-31 kinaba: 445abb9772 2015-05-31 kinaba: // BEGIN CUT HERE 445abb9772 2015-05-31 kinaba: #include <ctime> 445abb9772 2015-05-31 kinaba: double start_time; string timer() 445abb9772 2015-05-31 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 445abb9772 2015-05-31 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 445abb9772 2015-05-31 kinaba: { os << "{ "; 445abb9772 2015-05-31 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 445abb9772 2015-05-31 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 445abb9772 2015-05-31 kinaba: void verify_case(const int& Expected, const int& Received) { 445abb9772 2015-05-31 kinaba: bool ok = (Expected == Received); 445abb9772 2015-05-31 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 445abb9772 2015-05-31 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 445abb9772 2015-05-31 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 445abb9772 2015-05-31 kinaba: #define END verify_case(_, ApplesAndOrangesEasy().maximumApples(N, K, info));} 445abb9772 2015-05-31 kinaba: int main(){ 445abb9772 2015-05-31 kinaba: 445abb9772 2015-05-31 kinaba: CASE(0) 445abb9772 2015-05-31 kinaba: int N = 3; 445abb9772 2015-05-31 kinaba: int K = 2; 445abb9772 2015-05-31 kinaba: vector <int> info; 445abb9772 2015-05-31 kinaba: int _ = 2; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: CASE(1) 445abb9772 2015-05-31 kinaba: int N = 10; 445abb9772 2015-05-31 kinaba: int K = 3; 445abb9772 2015-05-31 kinaba: int info_[] = {3, 8}; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = 2; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: CASE(2) 445abb9772 2015-05-31 kinaba: int N = 9; 445abb9772 2015-05-31 kinaba: int K = 4; 445abb9772 2015-05-31 kinaba: int info_[] = {1, 4}; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = 5; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: CASE(3) 445abb9772 2015-05-31 kinaba: int N = 9; 445abb9772 2015-05-31 kinaba: int K = 4; 445abb9772 2015-05-31 kinaba: int info_[] = {2, 4}; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = 4; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: CASE(4) 445abb9772 2015-05-31 kinaba: int N = 23; 445abb9772 2015-05-31 kinaba: int K = 7; 445abb9772 2015-05-31 kinaba: int info_[] = {3, 2, 9, 1, 15, 23, 20, 19}; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = 10; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: /* 445abb9772 2015-05-31 kinaba: CASE(5) 445abb9772 2015-05-31 kinaba: int N = ; 445abb9772 2015-05-31 kinaba: int K = ; 445abb9772 2015-05-31 kinaba: int info_[] = ; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = ; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: CASE(6) 445abb9772 2015-05-31 kinaba: int N = ; 445abb9772 2015-05-31 kinaba: int K = ; 445abb9772 2015-05-31 kinaba: int info_[] = ; 445abb9772 2015-05-31 kinaba: vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); 445abb9772 2015-05-31 kinaba: int _ = ; 445abb9772 2015-05-31 kinaba: END 445abb9772 2015-05-31 kinaba: */ 445abb9772 2015-05-31 kinaba: } 445abb9772 2015-05-31 kinaba: // END CUT HERE