Submission #319385

#TimeUsernameProblemLanguageResultExecution timeMemory
319385CodeTiger927Dostavljač (COCI18_dostavljac)C++14
140 / 140
7 ms4336 KiB
using namespace std; #include <iostream> #include <vector> #include <cstring> #define MAXN 505 long long dp[MAXN][2][MAXN],arr[MAXN],tmp[MAXN],tmp2[MAXN]; int N,M,sz[MAXN],parent[MAXN]; vector<int> edges[MAXN]; void dfs(int cur) { // cout << cur << endl; sz[cur] = 1; dp[cur][0][1] = arr[cur]; dp[cur][1][1] = arr[cur]; for(int i = 0;i < edges[cur].size();++i) { int next = edges[cur][i]; if(next == parent[cur]) continue; parent[next] = cur; dfs(next); for(int j = 0;j <= M;++j) { tmp[j] = dp[cur][0][j]; tmp2[j] = dp[cur][1][j]; } for(int j = 0;j <= 3 * sz[cur];++j) { for(int k = 0;k <= 3 * sz[next];++k) { if(cur == 2 && j + k == 5) { // cout << "hi " << j << " " << k << " " << dp[cur][0][j] << " " << dp[next][0][k] << endl; } if(j + k + 2 <= M) tmp[j + k + 2] = max(tmp[j + k + 2],dp[cur][0][j] + dp[next][0][k]); if(j + k + 1 <= M) tmp2[j + k + 1] = max(tmp2[j + k + 1],dp[cur][0][j] + dp[next][1][k]); if(j + k + 2 <= M) tmp2[j + k + 2] = max(tmp2[j + k + 2],dp[cur][1][j] + dp[next][0][k]); } } memcpy(dp[cur][0],tmp,sizeof(tmp)); memcpy(dp[cur][1],tmp2,sizeof(tmp2)); sz[cur] += sz[next]; } } int main() { cin >> N >> M; for(int i = 1;i <= N;++i) { cin >> arr[i]; } for(int i = 0;i < N - 1;++i) { int a,b; cin >> a >> b; edges[a].push_back(b); edges[b].push_back(a); } parent[1] = 1; dfs(1); long long ans = 0; for(int i = 0;i <= M;++i) { ans = max(ans,max(dp[1][0][i],dp[1][1][i])); } cout << ans << endl; return 0; }

Compilation message (stderr)

dostavljac.cpp: In function 'void dfs(int)':
dostavljac.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0;i < edges[cur].size();++i) {
      |                ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...