|
|
I need help, I got WA on test case 5, and I do not know what's the problem. Here my code: #include <bits/stdc++.h> using namespace std; string getPrefix(string s, int n){ string result; if(n >= s.size())result = s; else result = s.substr(0,n); return result; } string getSuffix(string s, int n){ int newN; string result; if(n >= s.size()) result = s; else result = s.substr(s.size() - n); return result; } int main(){ string s, a, b; int m; while(cin>>s>>a>>b>>m){ vector<pair<string, string> > v(m + 10, {"",""}); vector<long long int> cnt(m + 10, 0); v[1] = {a, a}; cnt[1] = 0; v[2] = {b, b}; cnt[2] = 0; long long int maxi = 0; for(int i = 3, from, to; i <= m + 2;i++){ cin>>from>>to; string text = v[from].second + v[to].first; string text2 = v[from].first + v[to].second; string prefix = getPrefix(text, s.size() - 1); string suffix = getSuffix(text, s.size() - 1); string prefixNew = getPrefix(text2, s.size() - 1); string suffixNew = getSuffix(text2, s.size() - 1); v[i] = {prefixNew, suffixNew}; cnt[i] = (cnt[from] + cnt[to]) % 1000000007; if(text.size() >= s.size()){ for(int j = 0 ; j < text.size() - s.size() + 1; j++){ if(s == text.substr(j,s.size()) ) cnt[i] = (cnt[i] + 1) % 1000000007; } } } long long int sol = 0; for(int i = 1; i <= m + 2; i++){ sol = max(sol, cnt[i]); } cout<<sol<<endl; } return 0; } WHY Crash (access violation) on test 5. Please help me. length of array must be m+2 (two DNAs of the mutant pangolins, which were initially in the bank) godzillagodzilla godz illa 4 1 2 3 3 4 4 5 5 Edited by author 05.08.2009 18:11 Edited by author 05.08.2009 18:11 TT AC T 6 2 1 3 2 1 4 2 5 2 2 6 7 2 Edited by author 28.03.2010 19:19 I use map<int,string> why it got MLE 5???? Edited by author 25.10.2008 18:30 In maxitest length of the string may be as large as 10*2^100 =) so and what kind of problems it is???? Dynamic programming really?? I can't imagine how it could be solve with the help of dynamic.... could you tell me your idea???? for each DNA you must store number of occurences Godzilla's DNA in it, and prefix and suffix of this DNA, which length is less by one, than Godzilla's DNA s length. with this information you can easily compute next DNA Edited by author 27.10.2008 16:41 Thank you!!! Now AC :) !!! MOiAIS 1646 Java Memory limit exceeded 5 0.125 40 330 КБ My program used 40 MB, but restrictions - 64 MB. Why MLE? what mean "Output the number one modulo 10^9 + 7"? pascal answer mod 1000000007; C++ answer % 1000000007; |
|
|