글 읽기 - 잘 가다가 27퍼센트에서 틀리네요 ㅂㄷㅂㄷ

jack2020 5년 전 0

알고리즘은 맞는 것 같은데...O(NK)로 푸는 알고리즘이에요!

long long int 도 써봤는데 틀렸다구 나오네요 ㅠㅠ

어느 부분이 잘못 되었나요? ㅠㅠ

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

int walk_t[105];
int walk_c[105];
int bike_t[105];
int bike_c[105];
long long int dp[105][100001];
bool visit[105][100001];

int main() {
	int N, K; scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; i++) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		walk_t[i] = a; walk_c[i] = b;
		bike_t[i] = c; bike_c[i] = d;
	}
	memset(dp, 0, sizeof(dp));
	memset(visit, false, sizeof(visit));
	dp[1][walk_t[1]] = walk_c[1];
	dp[1][bike_t[1]] = bike_c[1];
    visit[1][walk_t[1]] = true;
    visit[1][bike_t[1]] = true;
	for (int i = 1; i <= N-1; i++) {
		for (int j = 0; j <= K; j++) {
			if (visit[i][j] == true) {
			    if (dp[i][j] != 0 && (j + walk_t[i+1]) <= K) {
			    	dp[i+1][j+walk_t[i+1]] = max(dp[i+1][j+walk_t[i+1]], dp[i][j] + walk_c[i+1]);
			    	visit[i+1][j+walk_t[i+1]] = true;
			    }
			    if (dp[i][j] != 0 && (j + bike_t[i+1]) <= K) {
			    	dp[i+1][j+bike_t[i+1]] = max(dp[i+1][j+bike_t[i+1]], dp[i][j] + bike_c[i+1]);
			    	visit[i+1][j+bike_t[i+1]] = true;
			    }
			}
		}
	}
	long long int answer = 0;
	for (int i = 0; i <= K; i++) {
		answer = max(answer, dp[N][i]);
	}
	printf("%lli", answer);
	return 0;
}

leehosu01 5년 전 0

이미 해결했군요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

잘 가다가 27퍼센트에서 틀리네요 ㅂㄷㅂㄷ

jack2020 5년 전 0

leehosu01 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말