飽きた

これは、報告兼けじめです。

重大な報告だと思った？

残念！！！重大じゃないです。

この前取り組んでた

ABC 032 D ナップサック問題

これですけど、飽きたので、飛ばします。

以上、報告です。

バグ取りで、無理やなと感じたので、供養。南無。

#include <cstdio>
#include <map>
#include <cstring>
using namespace std;

#define N_MAX 250
#define W_MAX 1500
#define V_MAX 1000
#define INF 10000000000LL
#define ull unsigned long long

long long N, W;
long long v[N_MAX], w[N_MAX];
map<long long, map<long long, long long> > mp;
long long dp[N_MAX][W_MAX];
unsigned long long dp2[N_MAX][N_MAX*V_MAX];


long long rec(long long pos, long long rest) {
    if (pos == N) {
        return 0;
    }
    const_iterator itr = mp.find(pos);
    if (itr != mp.end()) {
        const_iterator itr2 = itr->second.find(rest);
        if (itr2 != itr->second.end()) {
            return itr2->second;
        }
    }

    long long ans = rec(pos+1, rest);
    if (rest-w[pos] >= 0) {
        long long tmp = rec(pos+1, rest-w[pos])+v[pos];
        ans = ans > tmp ? ans : tmp;
    }
    mp[pos][rest] = ans;
    return ans;
}


int main() {
    scanf("%lld %lld", &N, &W);
    for (int i = 0; i < N; i++) {
        scanf("%lld %lld", &v[i], &w[i]);
    }
    if (1 <= w[0] && w[0] <= 1000) {
        for (int i = N-1; i > -1; i--) {
            for (int j = 0; j <=W; j++) {
                if (j-w[i] >= 0) {
                    long long tmp = dp[i+1][j-w[i]]+v[i];
                    dp[i][j] = (dp[i+1][j] > tmp) ? dp[i+1][j] : tmp;
                } else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        printf("%lld\n", dp[0][W]);
    } else if (0 <= v[0] && v[0] <= 1000) {
        memset(dp2, -1, sizeof(dp2));
        dp2[N][0] = 0;
        for (int i = N-1; i > -1; i--) {
            for (unsigned long long j = 0; j <= V_MAX * N_MAX; j++) {
                if (j-v[i] >= 0) {
                    unsigned long long tmp = dp2[i+1][j-v[i]]+w[i];
                    dp2[i][j] = (dp2[i+1][j] < tmp)?dp2[i+1][j]:tmp;
                } else {
                    dp2[i][j] = dp2[i+1][j];
                }
            }
        }
        unsigned long long res = 0;
        for (int i = 0; i <= V_MAX * N_MAX; i++) {
            if (dp2[0][i] <= W) {
                res = i;
            }
        }
        printf("%lld\n", res);
    } else {
        printf("%lld\n", rec(0, W));
    }
    return 0;
}

サクサクいけそうなのをやっていこう！！！