Submission #46343

#TimeUsernameProblemLanguageResultExecution timeMemory
46343RezwanArefin01Palindromic Partitions (CEOI17_palindromic)C++17
0 / 100
6 ms5240 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; const int maxn = 1e5 + 10; vector<int> adj[maxn]; ll p[maxn], s[maxn], mx; multiset<ll> st; int n, v; void solve(int u, int par) { st.insert(s[u] - p[par]); ll tot = 0; int tk = v; for(auto it = --st.end(); it != st.begin() && tk; it--, tk--) { tot += *it; } mx = max(mx, tot); for(int v : adj[u]) if(v - par) solve(v, u); st.erase(st.find(s[u] - p[par])); } int main(int argc, char const *argv[]) { #ifdef LOCAL_TESTING freopen("in", "r", stdin); #endif scanf("%d %d", &n, &v); for(int i = 1; i <= n; i++) scanf("%lld", &p[i]); for(int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } for(int i = 1; i <= n; i++) { for(int v : adj[i]) s[i] += p[v]; } if(n > 1000) solve(1, 0); else for(int i = 1; i <= n; i++) { st.clear(); solve(i, 0); } printf("%lld\n", mx); }

Compilation message (stderr)

palindromic.cpp: In function 'int main(int, const char**)':
palindromic.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &v);
  ~~~~~^~~~~~~~~~~~~~~~~
palindromic.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i]);
   ~~~~~^~~~~~~~~~~~~~~
palindromic.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v); 
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...