oj.uz

답안 #222009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222009 2020-04-11T19:33:40 Z ZwariowanyMarcin Dostavljač (COCI18_dostavljac) C++17
126 / 140
 2000 ms 3704 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, 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];
		
		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;
							rep(d, 0, 1) {
								if (c == 0 && d == 1) continue;
								if (a == 1 && b == 1 && c == 1) continue;
								if (a == 0 && c == 0) {
									int s = i + j + 2;
									if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][d]);
								}
								if (a == 1) {
									int e = (b | c);
									int s = i + j + 1 + !(c == 1);
									if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + dp[it][j][c][d]);
								}
							}
						}
					}
		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:84: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:85: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:87: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 19 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1152 KB Output is correct
2 Correct 442 ms 1504 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 889 ms 2040 KB Output is correct
2 Correct 259 ms 1816 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 2424 KB Output is correct
2 Correct 1860 ms 2680 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1704 ms 3692 KB Output is correct
2 Correct 672 ms 3604 KB Output is correct

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2080 ms 3704 KB Time limit exceeded
2 Halted 0 ms 0 KB -