AtCoderのRE原因

Question

AtCorderで半分REになってしまう問題があります。
範囲外へのアクセスをしていないか確認してみたりしましたが、原因がわからず困っています。

問題

ABC 175 E - Picking Goods

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (i = 0; i < n; i++)

const long long INF = 1LL << 60;

int main()
{
    int i, j, k, R, C, K;
    cin >> R >> C >> K;
    int V[R][C];
    long long dp[R+1][C+1][5];
    memset(V, 0, sizeof(V));
    memset(dp, 0, sizeof(dp));
    int r, c, v;
    rep(i, K){
        cin >> r >> c >> v;
        V[r-1][c-1]=v;
    }

    dp[0][0][1] = V[0][0];

    rep(i, R){ rep(j, C) { rep(k, 4){
        // to right
        dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+V[i][j+1]);
        dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
        // to down
        dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][k]+V[i+1][j]);
        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][k]);
    }}}

    long long ans=0;
    rep(i,4) ans=max(ans,dp[R-1][C-1][i]);

    cout << ans << endl;
    return 0;
}

補足情報

実行時間 : 157 ms
メモリ : 10136 KB
エラーメッセージ : なし

Answer 1

    int V[R][C];
    //...
    rep(i, R){ rep(j, C) { rep(k, 4){
        //...
        dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+V[i][j+1]);
        //...
        dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][k]+V[i+1][j]);
    }}}

dpは一つ多めに確保してますが、Vはまだちょうどのサイズなので、まだ範囲外のアクセスがありますね。
あとはおそらく配列の確保がそもそもできてないケースがあるはずです。メモリの使用量(どの程度性格かはわかりませんが)が10MB程度ですが、dp配列だけでその10倍は軽く超えるはずです。

Comments

[auto-blue]

Vの範囲外へのアクセス気がつきませんでした。
ありがとうございます。

メモリの確保について、main内で行おうとするとうまく行かず、main外で確保しておくとACでした。
もしご存知でしたら、main内とmain外でメモリの確保できるかできないかが異なった理由を教えていただきたいです。

[yudedako67]

頻出の話題なので、「スタック　ヒープ　静的領域」というようなワードで調べると詳しい説明が出ると思います。

[auto-blue]

スッキリしました、ありがとうございました！