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!
Your
dp
array is using more than 256 MB, so that's probably the culpritThanks a lot!
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:
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
Ok again thanks a lot for you advice!