frank1369blogger's blog

By frank1369blogger, history, 4 years ago, In English

Hi. I've been solving this problem in USACO named snakes. when I want to submit this is what I write for input output stuff:

freopen("snakes.in", "r", stdin); freopen("snakes.out", "w", stdout);

ans this model has always worked and I don't know whats wrong with this problem. and this is what usaco gives me when submitted:

` Runtime error or memory limit exceeded on sample input case -- details below Your output file snakes.out: [File missing!]

The correct answer: 3`

and this is exact code for the problem(if you want to check):

#include <bits/stdc++.h> 

#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;

const int N = 410, inf = (int) 2e9;

int dp[N][N][N];
int dp_min[N][N];
int a[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  freopen("snakes.in", "r", stdin);
  freopen("snakes.out", "w", stdout);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k <= m; k++) {
        dp[i][j][k] = -1;
        dp_min[i][k] = inf;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= m; j++) {
      if (a[i] < a[0]) {
        continue;
      }
      dp[0][i][j] = a[i] - a[0];
      dp_min[0][j] = min(dp_min[0][j], dp[0][i][j]);
    }
  }
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k <= m; k++) {
        if (a[j] < a[i]) {
          continue;
        }
        if (k == 0) {
          if (dp[i - 1][j][k] == -1) {
            dp[i][j][k] = -1;
          } else {
            dp[i][j][k] = dp[i - 1][j][k] + a[j] - a[i];
            dp_min[i][k] = min(dp_min[i][k], dp[i][j][k]);
          }
          continue;
        }
        if (dp[i - 1][j][k] != -1) {
          dp[i][j][k] = min(dp[i - 1][j][k] + a[j] - a[i], dp_min[i - 1][k - 1] + a[j] - a[i]);
        } else {
          dp[i][j][k] = dp_min[i - 1][k - 1] + a[j] - a[i];
        }
        dp_min[i][k] = min(dp_min[i][k], dp[i][j][k]);
      }
    }
  }
  /*
  debug("dp");
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k <= m; k++) {
        debug(i);
        debug(j);
        debug(k);
        debug(dp[i][j][k]);
      }
    }
  }
  debug("dp_min");
  for (int i = 0; i < n; i++) {
    for (int k = 0; k <= m; k++) {
      debug(i);
      debug(k);
      debug(dp_min[i][k]);
    }
  }
  */
  cout << dp_min[n - 1][m] << '\n';
  return 0;
}

PLEASE HELP!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Runtime error or memory limit exceeded

Your dp array is using more than 256 MB, so that's probably the culprit

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Thanks a lot!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know how to appreciate that... It got AC when I changed all arrays to vectors. but I'm pretty confused now... I stopped using vectors because of TLE and now I got ME because of arrays. so what should I use?? and this is my AC code:

    //\\//\\ * * * //\\// ||
    #include <bits/stdc++.h> 
    
    #define debug(x) cerr << #x << ": " << x << endl
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 410, inf = (int) 2e9;
    
    int main() {
      ios::sync_with_stdio(false);
      cin.tie(0);
      freopen("snakes.in", "r", stdin);
      freopen("snakes.out", "w", stdout);
      int n, m;
      cin >> n >> m;
      vector<int> a(n);
      vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(m + 1)));
      vector<vector<int>> dp_min(n, vector<int>(m + 1));
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          for (int k = 0; k <= m; k++) {
            dp[i][j][k] = -1;
            dp_min[i][k] = inf;
          }
        }
      }
      for (int i = 0; i < n; i++) {
        cin >> a[i];
      }
      for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
          if (a[i] < a[0]) {
            continue;
          }
          dp[0][i][j] = a[i] - a[0];
          dp_min[0][j] = min(dp_min[0][j], dp[0][i][j]);
        }
      }
      for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
          for (int k = 0; k <= m; k++) {
            if (a[j] < a[i]) {
              continue;
            }
            if (k == 0) {
              if (dp[i - 1][j][k] == -1) {
                dp[i][j][k] = -1;
              } else {
                dp[i][j][k] = dp[i - 1][j][k] + a[j] - a[i];
                dp_min[i][k] = min(dp_min[i][k], dp[i][j][k]);
              }
              continue;
            }
            if (dp[i - 1][j][k] != -1) {
              dp[i][j][k] = min(dp[i - 1][j][k] + a[j] - a[i], dp_min[i - 1][k - 1] + a[j] - a[i]);
            } else {
              dp[i][j][k] = dp_min[i - 1][k - 1] + a[j] - a[i];
            }
            dp_min[i][k] = min(dp_min[i][k], dp[i][j][k]);
          }
        }
      }
      /*
      debug("dp");
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          for (int k = 0; k <= m; k++) {
            debug(i);
            debug(j);
            debug(k);
            debug(dp[i][j][k]);
          }
        }
      }
      debug("dp_min");
      for (int i = 0; i < n; i++) {
        for (int k = 0; k <= m; k++) {
          debug(i);
          debug(k);
          debug(dp_min[i][k]);
        }
      }
      */
      cout << dp_min[n - 1][m] << '\n';
      return 0;
    }
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I guess that's because there's no test case with $$$n = k = 400$$$, and your solution only barely MLE's, so when you use the exact amount of memory that you need it squeezes through.

      Also, when pasting long (or any) code in comments, please use spoilers

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Ok again thanks a lot for you advice!