Блог пользователя frank1369blogger

Автор frank1369blogger, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Runtime error or memory limit exceeded

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Thanks a lot!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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