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

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

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
  • Проголосовать: не нравится

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

Runtime error or memory limit exceeded

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

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

    Thanks a lot!

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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;
    }