1231 - ACORN

[mehrab2603]

Getting TLE. Any help on how to make it efficient will be highly appreciated.

Code: Select all

#include <bits/stdc++.h>

using namespace std;
int t, h, f;
//vector<int> acorn[2010];
int acorn[2010][2010];
int dp[2010][2010];
bool vis[2010][2010];
int func(int, int);

int main() {
    int c;
    scanf("%d", &c);
    while(c--) {
        scanf("%d %d %d", &t, &h, &f);
        memset(acorn, 0, sizeof acorn);
        memset(vis, false, sizeof vis);
        for(int i = 0; i < t; i++) {
            int x;
            scanf("%d", &x);
            for(int j = 0; j < x; j++) {
                int height;
                scanf("%d", &height);
                acorn[i][height]++;
            }
        }
        int ans = -99999;
        for(int i = 0; i < t; i++)
            ans = max(ans, func(i, h));
        printf("%d\n", ans);
    }
    int zero;
    scanf("%d", &zero);
    return 0;
}

int func(int tree, int height) {
    if(height <= 0) {
        return 0;
    }
    if(vis[tree][height]) return dp[tree][height];
    int taken = -99999;
    taken = max(taken, acorn[tree][height] + func(tree, height - 1));
    for(int i = 0; i < t; i++) {
        if(i == tree) continue;
        if(height - f >= 0 && acorn[i][height - f])
            taken = max(taken, acorn[tree][height] + func(i, height - f));
    }
    vis[tree][height] = true;
    dp[tree][height] = taken;
    return taken;

}

[brianfry713]

If you are trying to solve a test case in O(t * t * h) plus the time to read the input you will get TLE.
It can be done in O(t * h) plus the time to read the input.

Code: Select all

DP loop:
iterate from h to 0
  iterate through each tree, keeping track of which tree has the most acorns at the current height
    set the DP array for this tree at this height to be any acorns located here plus the max of this tree at current height + 1 or the tree with the most acorns at the current height plus f.

[mehrab2603]

Thanks for the hint. I'll try it again.
However, I was wondering why my code gets TLE while this one gets AC. Seems similar to mine. Just wanted to understand how the complexity was improved.

*code removed*

[brianfry713]

If you are trying to solve a test case in O(t * t * h) plus the time to read the input you will get TLE.
It can be done in O(t * h) plus the time to read the input.