Go to diff to previous submission
#include <iostream> #include <set> #include <stdio.h> #include <utility> #include <map> #include <string> #include <sstream> #include <algorithm> #include <vector> #include <climits> using namespace std; int main(){ int H, W; while(cin >> H >> W){ int h, w; cin >> h >> w; vector<vector<int> > pref(H+2*h+2000, vector<int>(W+2*w+2000)); vector<vector<bool> > image(H, vector<bool>(W)); for(int i=0; i<H; ++i){ string s; cin >> s; for(int j=0; j<W; ++j){ if(s[j] == '.') image[i][j] = false; else image[i][j] = true; } } for(int i=0; i<H; ++i){ for(int j=0; j<W; ++j){ pref[i+h+1][j+w+1] = pref[i+h-1+1][j+w+1] + pref[i+h+1][j+w-1+1] - pref[i+h-1+1][j+w-1+1]; if(image[i][j]) pref[i+h+1][j+w+1]++; } } for(int i=H+h; i<H+2*h; ++i){ for(int j=0; j<W+2*w; ++j){ pref[i+1][j+1] = pref[i-1+1][j+1]; } } for(int j=W+w; j<W+2*w; ++j){ for(int i=0; i<H+2*h; ++i){ pref[i+1][j+1] = pref[i+1][j-1+1]; } } int minimum = INT_MAX; for(int i=0; i<h; ++i){ for(int j=0; j<w; ++j){ int num = 0; for(int k=0; k<H/h+2; ++k){ for(int l=0; l<W/w+2; ++l){ //if(com_pref(i+k*h, j+l*w) > 0) num++; int p1 = i+k*h, p2 = j+l*w; int x = 0; if(p1 == 0 && p2 == 0){ x = pref[p1+h-1+1][p2+w-1+1]; } else if(p1 == 0){ x = pref[p1+h-1+1][p2+w-1+1] - pref[p1+h-1+1][p2-1+1]; } else if(p2 == 0){ x = pref[p1+h-1+1][p2+w-1+1] - pref[p1-1+1][p2+w-1+1]; } else{ x = pref[p1+h-1+1][p2+w-1+1] - pref[p1-1+1][p2+w-1+1] - pref[p1+h-1+1][p2-1+1] + pref[p1-1+1][p2-1+1]; } if(x>0) num++; } } minimum = min(num, minimum); } } cout << minimum << '\n'; } }
--- c5.s1128.cteam026.fm.cpp.0.fm.cpp +++ c5.s1133.cteam026.fm.cpp.0.fm.cpp @@ -16,5 +16,5 @@ int h, w; cin >> h >> w; - vector<vector<int> > pref(H+2*h+20, vector<int>(W+2*w+20)); + vector<vector<int> > pref(H+2*h+2000, vector<int>(W+2*w+2000)); vector<vector<bool> > image(H, vector<bool>(W)); for(int i=0; i<H; ++i){