ADDED SRM/582-U/1A.cpp Index: SRM/582-U/1A.cpp ================================================================== --- SRM/582-U/1A.cpp +++ SRM/582-U/1A.cpp @@ -0,0 +1,145 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +class SpaceWarDiv1 { public: + long long minimalFatigue(vector magicalGirlStrength, vector enemyStrength, vector enemyCount) + { + int M = *max_element(magicalGirlStrength.begin(), magicalGirlStrength.end()); + int E = *max_element(enemyStrength.begin(), enemyStrength.end()); + if(M > e; + for(int i=0; i1) { + LL C = (L+R)/2; + (possible(magicalGirlStrength, e, C) ? R : L) = C; + } + return R; + } + + bool possible(const vector& m, const vector >& e, LL F) + { + int ei = 0; + LL eC = e[ei].second; + for(int i=0; i m[i]) + return false; + + for(LL p = F; p; ) { + if(eC > p) { + eC -= p; + p = 0; + } + else { + ++ei; + if(ei == e.size()) + return true; + p -= eC; + eC = e[ei].second; + } + } + } + return (ei == e.size()); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, SpaceWarDiv1().minimalFatigue(magicalGirlStrength, enemyStrength, enemyCount));} +int main(){ + +CASE(0) + int magicalGirlStrength_[] = {2, 3, 5}; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = {1, 3, 4}; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = {2, 9, 4}; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = 7LL; +END +CASE(1) + int magicalGirlStrength_[] = {2, 3, 5}; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = {1, 1, 2}; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = {2, 9, 4}; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = 5LL; +END +CASE(2) + int magicalGirlStrength_[] = {14, 6, 22}; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = {8, 33}; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = {9, 1}; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = -1LL; +END +CASE(3) + int magicalGirlStrength_[] = {869, 249, 599, 144, 929, 748, 665, 37, 313, 99, 33, 437, 308, 137, 665, 834, 955, 958, 613, 417}; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = {789, 57, 684, 741, 128, 794, 542, 367, 937, 739, 568, 872, 127, 261, 103, 763, 864, 360, 618, 307}; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = {20626770196420, 45538527263992, 52807114957507, 17931716090785, 65032910980630, 88711853198687, 26353250637092, + 61272534748707, 89294362230771, 52058590967576, 60568594469453, 23772707032338, 43019142889727, 39566072849912, + 78870845257173, 68135668032761, 36844201017584, 10133804676521, 6275847412927, 37492167783296}; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = 75030497287405LL; +END +CASE(4) +int magicalGirlStrength_[] = {66,16,15,85,98,82,100,21,87,21,63,48,22,82,49,91,69,85,82,100,70,40,77,53,36,8,54,26,35,7,36,74,36,70,10,30,89,14,14,64,89,87,68,40,16,46,28,75,43,10}; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = {1}; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = {100000000000LL}; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = -1LL; +END +/* +CASE(5) + int magicalGirlStrength_[] = ; + vector magicalGirlStrength(magicalGirlStrength_, magicalGirlStrength_+sizeof(magicalGirlStrength_)/sizeof(*magicalGirlStrength_)); + int enemyStrength_[] = ; + vector enemyStrength(enemyStrength_, enemyStrength_+sizeof(enemyStrength_)/sizeof(*enemyStrength_)); + long long enemyCount_[] = ; + vector enemyCount(enemyCount_, enemyCount_+sizeof(enemyCount_)/sizeof(*enemyCount_)); + long long _ = LL; +END + */ +} +// END CUT HERE ADDED SRM/582-U/1B-U.cpp Index: SRM/582-U/1B-U.cpp ================================================================== --- SRM/582-U/1B-U.cpp +++ SRM/582-U/1B-U.cpp @@ -0,0 +1,315 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef long double LD; +typedef complex CMP; + +static const unsigned MODVAL = 1000000009; +struct mint +{ + unsigned val; + mint():val(0){} + mint(int x):val(x%MODVAL) {} + mint(unsigned x):val(x%MODVAL) {} + mint(LL x):val(x%MODVAL) {} +}; +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } +mint operator+(mint x, mint y) { return x+=y; } +mint operator-(mint x, mint y) { return x-=y; } +mint operator*(mint x, mint y) { return x*=y; } + +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); } +mint operator/(mint x, mint y) { return x/=y; } + +vector FAC_(1,1); +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; } + +mint P(LL n, LL k) { + return k<0 || n +struct DP3x +{ + int N1, N2, N3; + vector data; + DP3x(int, int N2, int N3, const T& t = T()) + : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); } + T& operator()(int i1, int i2, int i3) + { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } + void swap(DP3x& rhs) + { data.swap(rhs.data); } +}; + +template +struct DP3 +{ + int N1, N2, N3; + vector data; + DP3(int N1, int N2, int N3, const T& t = T()) + : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); } + T& operator()(int i1, int i2, int i3) + { return data[ ((i1*N2)+i2)*N3+i3 ]; } + void swap(DP3& rhs) + { data.swap(rhs.data); } +}; + +class ColorfulBuilding { public: + int count(vector color1, vector color2, int L) + { + string C1 = accumulate(color1.begin(), color1.end(), string()); + string C2 = accumulate(color2.begin(), color2.end(), string()); + int N = C1.size(); + vector C; + for(int i=0; i& C, int L) + { + int N = C.size(); + + DP3x dp(L+1, N, N+1); + for(int c=1; c<=L; ++c) + { + for(int x=0; x +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, ColorfulBuilding().count(color1, color2, L));} +int main(){ + +CASE(0) + string color1_[] = {"aaba"}; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = {"aaaa"}; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = 3; + int _ = 6; +END +CASE(1) + string color1_[] = {"aaba"}; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = {"aaba"}; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = 4; + int _ = 0; +END +CASE(2) + string color1_[] = {"ab", "ba", "a", "aab"}; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = {"bb", "ba", "a", "aba"}; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = 5; + int _ = 432; +END +CASE(3) + string color1_[] = {"xxxxxxxxxxxxxxxxxxxx", + "xxxxxxxxxxxxxxxxxxxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOxxxxxxxxxxxxxxxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxxxxxxxxxxxxxxxOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxxxxxxxxxxxxxxxxxxx", + "xxxxxxxxxxxxxxxxxxxx"}; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = {"xxxxxxxxxxxxxxxxxxxx", + "xxxxxxxxxxxxxxxxxxxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOxxxxxxxxxxxxOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxOOOOOOOOOOOOOOOOxx", + "xxxxxxxxxxxxxxxxxxxx", + "xxxxxxxxxxxxxxxxxxxx"}; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = 58; + int _ = 619787617; +END +CASE(4) + string color1_[] = {"SJXcabKTWeUXhwxGixFepQaQlFxrAedNAtVP", + "gorBIkcTlOFbLDbFeElYAyAqszQdMbpxSRdE", + "SQVHPehlNtesbJDflyGxMqvgzjXisRnqDcQO", + "pIAEBwbmpPWCooQAujbGXFGLvXxTmExLARkf", + "AFnWyWKVObfxDGCjTxdZaObgwdxlPKtIxaAd", + "uznMpJVNjAofbHJjOrZeSHgSagOCUMGbvkVR", + "LBRrDbTAyKfVnedKiRfzgRzECpcsziqaTwdo", + "JrJHvsEVVGDkNVGqLbpxyLDPloBuNDQKnReI", + "SSYpbjKHSCnQhuyYrVauWDHDyhAoGyecrZMv", + "UdetQfWEUWHHuAxRSdkJOOJSixKpQXpCFZHO", + "KXVsQbuQtIgsULOMsTvPFNUqkBldMTLCipYK", + "hoXConjnDWQkZVtyZlwSedvdVrNWqQhGUClQ", + "TpsvvyoXsXmQpBAGGVDrXCkodoRHQZmpoQDW", + "csiJspzTqeFBRmPgeEtTAzfrfCGlTZqcPuyO", + "vsPDVBJVaJmUAtDdcsKoUkPEbDmAwtZKwjjP", + "MOfoMhMiKIvGQoeIJXHzyClWRtRuKXMqxUAF", + "KyyUCkRBjsYvmPFFEGBqqVhIUdtvIyyLacfu", + "BfuwfSajSlcuTzhMufHSQLudvGEGlyHsEmBD", + "PLpIXZkdyXveTMfSvqnDGKWOZrTBMUIlZrqF", + "dzVMCqrSLbanRJTYpDJNHAOLPSzmvSEPQJYm", + "rAjRkrSjouJyFaCSPPLYSzqDmMoADyWAbobJ", + "eOCBrJNoyFnGpXpxiExXcoOHnVsaEPXhPfLe", + "XMjRksnxWssPEINhdhbiLBSYpCLtwNshFjXS", + "HnnDeUAbuswsgsYQuAaXySLkFYUwFXwYTreM", + "uqLnwOEGbwZZDgAAWEdLRZxFlogDmlhjhgHM", + "NcfaQsgPQfirkYDRFrLQpySmBGfRHumKULZf", + "mOpmmgclsxRzXskEywfryqCRyATNoJwnlHiD", + "AnoKoKAjrasttjNlHCROnvTJMhEHlVPVoVMo", + "yegLyIuRkkENFAjwzDoPLKjgUHHEkfzYDIpo", + "EcxRGGfuaBXUFXkSxctJWOLmmVbvoMkWtTvV", + "nBMkOBHgaltEVzfyGxseGhmBscfGIbxFbqRn", + "GvkEcLtqdOofGtsbWDafVMbNdJxsffKDzSiR", + "jhZQUVzTzalrZcebvyqPWtOUUyniBKTWdyLi", + "ODJLQPMdjDdTlxrfGsNmBfeGYjzeXApqKDhJ", + "vlJkWMzdVQujKdLViQClOrJXMTBkuZEasFgg", + "FAsbuzrLVIgaryqXBfuBRAbReleXSSgEKSvt"}; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = {"XAhlUHtfjOpOlQlowWppQcodMGUiqoLobxnD", + "IDzGlKrHiVGdBjZxIcoxjwagbWieKvUwZrjg", + "SkpkTVeIFeoNQzUUgmYAYskKONNZdgXxSiWd", + "rXBGhTmqnvxkmqiutoDzPusDiOUggEFXGCzm", + "fzrxVuTbFXunGbeEavjshmrIRlDorTuISCxn", + "LsvIaxTkOBjcskiekmrKNNFEXqnfMNXLWqqu", + "ekzxGIlbJPVEQPYAbTuMtZKsCiubDXDiBVzU", + "hZuOCJxvBOYENGSFcUiKKAKfCdebutVmnyvB", + "UveNkKRQmHnedrROQOpHJfrHjwcNLUShlDbn", + "ptUkvbaGDryHRkYfHKLkSgVpjWCEcgazyxGK", + "nVPYEqTTJsRPjzjfdOiULhnZPFeNcnbXaQlk", + "IPXBXRhMQIkxpygsgbcRfMuvIcuzUPPHGOWX", + "yWWlNyEyqZSIOXBFAybIuFpVqpvmKRaRFrAE", + "EvBJVtHvKhjrFcmtpdBbFTdTVtXXZQKAglKT", + "bCVjHzUvyINFkxXageZQMzCyNhcifACdJVDh", + "lZITYcDSeIbLweyFtoMAfOQyBNupKlhcNpgo", + "BduslNrJdWOUukYFFidEkMFaghfofpxVgvJd", + "YrJpDZKqdjEPzdLsOQEdkcrBfNHPemXHokCW", + "GjeUKSGjDlgKTyUGNrMQbBLxRUcgrWpkAwOD", + "wgxTcswqdJHaDugNIRMvrhBsdDaJAssVbSRW", + "qmVmqFEpvgGioMXDSFqEoQcDOAaUoGPEovSO", + "KrukPlpfOhawaovCfteTSCIdLMrtImVtiMyQ", + "ykwmxHsKMFzFHwcbyyedLvhZPnaNGqJMMCxd", + "HUNYCXjNLQIFCLLGpCXHBCHLTxLynBxnHFbx", + "uwjzbNbJepVFgMPUXVirxYHzExquBEtPmKju", + "xXAxAbJePyUsVHeLytDvAxBGMRtnvCEiZZqe", + "xMkQoIVxWPXPgaOYmDjTOXiMImVdzojERNxS", + "dwICFwMAmdOIUxyAdXdshasnzwyhfnVWVqZJ", + "etypXNVvSTEQvriGBZdSGmDEHhvpSqkFklCS", + "YkxpFBCRYUueRcKaJUXVdaMoYMYEooPQVMOr", + "DTrexDqclZNKdPuTRFHualJSFziCLPCZjpxo", + "TfEijcAsSJPikkmBSbXMqYHAhPTcpcKVSkIX", + "xKXHYPYMJxFpSbxltDKYuRiTkOLxpQKnXZPs", + "YFYuvuYHfpFJcrLNIdlNfBxRnWdppsdalBkx", + "NFTysBvNFjejdnlhRTclbcfGipNCxpFEOriY", + "thkgVflJYmbUYbIlafNUMGePQWiZyYzYXvUR"} +; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = 1200; + int _ = 396065426; +END +/* +CASE(5) + string color1_[] = ; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = ; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = ; + int _ = ; +END +CASE(6) + string color1_[] = ; + vector color1(color1_, color1_+sizeof(color1_)/sizeof(*color1_)); + string color2_[] = ; + vector color2(color2_, color2_+sizeof(color2_)/sizeof(*color2_)); + int L = ; + int _ = ; +END +*/ +} +// END CUT HERE