Решая вопрос о codechef , я обнаружил шаблон и обнаружил, что вместо заполнения полного массива n * m я могу ответить на него, просто построив два массива n * 3 и 3 * м размер.Поэтому я написал это так:
// #define REP(i, s, e) for(int i = s; i < e; i++)
// 1≤ N,M ≤10**5
vector< vector<int> > dp(n.size()+1, vector<int>(m.size()+1));
REP(i, 1, m.size()+1)
dp[0][i] = m[i-1]-48;
REP(i, 1, n.size()+1)
dp[i][0] = n[i-1]-48;
up = min(3, (int)(m.size()+1));
REP(j, 1, up){
REP(i, 1, n.size()+1)
dp[i][j] = (dp[i-1][j]&dp[i][j-1])^1;
}
up = min(3, (int)(n.size()+1));
REP(j, 1, up){
REP(i, 1, m.size()+1)
dp[j][i] = (dp[j-1][i]&dp[j][i-1])^1;
}
Я получил TLE в трех тестовых случаях, затем изменил его следующим образом:
// #define REP(i, s, e) for(int i = s; i < e; i++)
// 1≤ N,M ≤10**5
int rp[ns+1][3];
int cp[3][ms+1];
REP(i, 1, ms+1)
cp[0][i] = m[i-1]-48;
REP(i, 1, ns+1)
rp[i][0] = n[i-1]-48;
up = min(3, ms+1);
REP(j, 1, up){
rp[0][j] = cp[0][j];
REP(i, 1, ns+1)
rp[i][j] = (rp[i-1][j]&rp[i][j-1])^1;
}
up = min(3, ns+1);
REP(j, 1, up){
cp[j][0] = rp[j][0];
REP(i, 1, ms+1)
cp[j][i] = (cp[j-1][i]&cp[j][i-1])^1;
}
Предполагая, что обращается к элементамвектора и массива занимают одно и то же время, имеет ли значение время выделения и инициализации вектора?Я не мог сделать то, что заставляет мой код работать.