oj.uz

답안 #222011

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222011 2020-04-11T19:39:24 Z ZwariowanyMarcin Dostavljač (COCI18_dostavljac) C++17
140 / 140
 1660 ms 4272 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
 
using namespace std;

const int nax = 505;

void maxi(int &a, const int b) {
	a = max(a, b);
}

int n, m;
int a, b;
int cost[nax];
vector <int> g[nax];

int dp[nax][nax][2][2];
int dp2[nax][2][2];

// 0 to musze wrocic -> 0
// 1 to nie musze -> 0 / 1

void dfs(int v, int p) {
	rep(i, 0, m)
		rep(a, 0, 1)
			rep(b, 0, 1)
				dp[v][i][a][b] = -1e9;
	dp[v][0][0][0] = 0;
	dp[v][0][1][0] = 0;
	dp[v][1][0][0] = cost[v];
	dp[v][1][1][0] = cost[v]; 
	
	for (auto it : g[v]) {
		if (it == p) continue;
		
		dfs(it, v);
		
		rep(i, 0, m)
			rep(a, 0, 1)
				rep(b, 0, 1)
					dp2[i][a][b] = dp[v][i][a][b];
		int s, e;
		rep(i, 0, m)
			rep(j, 0, m - i)
				rep(a, 0, 1)
					rep(b, 0, 1) {
						if (a == 0 && b == 1) continue;
						rep(c, 0, 1) {
							if (a == 0 && c == 1) continue;
							if (a == 1 && b == 1 && c == 1) continue;
							if (a == 0 && c == 0) {
								s = i + j + 2;
								if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][0]);
							}
							if (a == 1) {
								e = (b | c);
								s = i + j + 1 + !(c == 1);
								if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + max(dp[it][j][c][0], dp[it][j][c][1]));
							}
							
						}
					}
		rep(i, 0, m)
			rep(a, 0, 1)
				rep(b, 0, 1)
					dp[v][i][a][b] = dp2[i][a][b];
		}
}

int main() {		
	scanf ("%d%d", &n, &m);
	rep(i, 1, n) scanf ("%d", cost + i);
	rep(i, 1, n - 1) {
		scanf ("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}	
	dfs(1, 0);
	int res = 0;
	rep(i, 0, m)
		rep(a, 0, 1)
			rep(b, 0, 1)
				maxi(res, dp[1][i][a][b]);
	printf ("%d\n", res);
	
	return 0;
}

Compilation message

dostavljac.cpp: In function 'int main()':
dostavljac.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:83:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", cost + i);
               ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 640 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1016 KB Output is correct
2 Correct 19 ms 896 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1152 KB Output is correct
2 Correct 244 ms 1492 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 2128 KB Output is correct
2 Correct 143 ms 1888 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 2424 KB Output is correct
2 Correct 1016 ms 2756 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 863 ms 3440 KB Output is correct
2 Correct 340 ms 3596 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1660 ms 4272 KB Output is correct
2 Correct 164 ms 3576 KB Output is correct