QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #72643 | #4815. Flower's Land | xuqin | WA | 5ms | 31720kb | C++14 | 2.6kb | 2023-01-17 17:43:09 | 2023-01-17 17:43:11 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4020, maxk=320;
struct pj{int y, nxt;} G[maxn<<1];
int len, la[maxn], a[maxn], n, k, sz[maxn], son[maxn];
long long f[maxn][maxk], g[maxn][maxk], tmp[maxk], h[maxk], u[maxn][maxk];
void add_e(int x, int y) {
G[++len].y=y; G[len].nxt=la[x]; la[x]=len;
}
void dfs(int x, int F) {
sz[x]=1;
for(int i=la[x]; i; i=G[i].nxt) {
int y=G[i].y;
if(y!=F) dfs(y, x), sz[x]+=sz[y];
}
tmp[0]=0;
int pre=0;
for(int i=la[x]; i; i=G[i].nxt) {
int y=G[i].y;
if(y==F) continue;
for(int j=0; j<=pre+sz[y]&&j<k; ++j) h[j]=-1e18;
for(int j=0; j<=pre&&j<k; ++j)
for(int l=0; l<=sz[y]&&l+j<k; ++l) h[j+l]=max(h[j+l], tmp[j]+f[y][l]);
for(int j=0; j<=pre+sz[y]&&j<k; ++j) tmp[j]=h[j];
pre+=sz[y];
}
for(int i=1; i<=k&&i<=sz[x]; ++i) f[x][i]=tmp[i-1]+a[x]; f[x][0]=0;
}
void dfs1(int x, int F) {
int cnt=0, sum=n-sz[x];
for(int i=0; i<k-1&&i<=sum; ++i) u[0][i]=g[x][i+1]-a[x];
for(int i=la[x]; i; i=G[i].nxt) {
int y=G[i].y;
if(y==F) continue;
son[++cnt]=y;
for(int j=0; j<k-1&&j<=sum; ++j)
for(int l=0; l<=sz[y]&&l+j<k-1; ++l) u[y][l+j]=max(u[y][l+j], u[son[cnt-1]][j]+f[y][l]);
sum+=sz[y];
}
tmp[0]=0;
int pre=0;
for(int i=cnt; i; --i) {
// for(int j=0; j<=pre; ++j) printf("%lld ", tmp[j]); puts("");
int y=son[i]; sum-=sz[y];
// printf("sum=%d pre=%d\n", sum, pre);
for(int j=0; j<k-1&&j<=sum; ++j)
for(int l=0; l<=pre&&l+j<k-1; ++l)
g[y][j+l+2]=max(g[y][l+j+2], a[x]+a[y]+u[son[cnt-1]][j]+tmp[l]);
g[y][1]=a[y]; g[y][0]=0;
if(i==cnt) {for(int j=1; j<k-1&&j<=sz[y]; ++j) tmp[j]=f[y][j];}
else {
for(int j=0; j<=pre+sz[y]&&j<k-1; ++j) h[j]=-1e18;
for(int j=0; j<=pre&&j<k-1; ++j)
for(int l=0; l<=sz[y]&&l+j<k-1; ++l)
h[l+j]=max(h[l+j], tmp[j]+f[y][l]);
for(int j=0; j<=pre+sz[y]&&j<k-1; ++j) tmp[j]=h[j];
}
pre+=sz[y];
}
for(int i=la[x]; i; i=G[i].nxt) {
int y=G[i].y;
if(y!=F) dfs1(y, x);
}
}
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; ++i) scanf("%d", a+i);
for(int i=1, x, y; i<n; ++i)
scanf("%d%d", &x, &y), add_e(x, y), add_e(y, x);
memset(f, 0xcc, sizeof f);
memset(g, 0xcc, sizeof g);
memset(u, 0xcc, sizeof u);
dfs(1, 0);
g[1][1]=a[1]; g[1][0]=0;
dfs1(1, 0);
// for(int i=1; i<=n; ++i)
// for(int j=1; j<=k; ++j) printf("[%d][%d]:%lld %lld\n", i, j, f[i][j], g[i][j]);
for(int i=1; i<=n; ++i) {
long long ans=-1e18;
for(int j=1; j<=k; ++j) ans=max(ans, f[i][j]+g[i][k+1-j]-a[i]);
printf("%lld ", ans);
}
return 0;
}
/*
7 4
1 3 2 1 7 12 17
4 6
1 4
5 1
2 5
7 6
3 2
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 31664kb
input:
5 3 6 10 4 3 4 3 4 4 2 2 5 5 1
output:
20 20 17 17 20
result:
ok 5 number(s): "20 20 17 17 20"
Test #2:
score: 0
Accepted
time: 1ms
memory: 31720kb
input:
7 4 1 3 2 1 7 12 17 4 6 1 4 5 1 2 5 7 6 3 2
output:
31 13 13 31 21 31 31
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 31692kb
input:
1 1 20
output:
20
result:
ok 1 number(s): "20"
Test #4:
score: 0
Accepted
time: 1ms
memory: 31700kb
input:
10 3 19 7 25 18 93 97 21 51 60 80 6 7 7 1 1 9 9 10 10 2 2 5 5 3 3 8 8 4
output:
159 180 169 94 180 137 137 169 159 180
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 5ms
memory: 31696kb
input:
20 3 932 609 248 720 831 253 418 482 1000 542 436 304 217 163 872 380 704 845 497 610 17 12 1 17 15 17 13 17 2 15 16 2 18 16 8 16 4 16 19 4 6 4 20 19 10 19 9 10 5 10 7 9 3 9 14 5 11 7
output:
2508 2185 1790 1945 2373 1470 1960 1707 2373 2373 1854 1940 1853 1536 2508 1945 2508 1945 2039 1827
result:
ok 20 numbers
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 31580kb
input:
40 5 1105 1687 737 6321 7793 7325 3443 2983 6912 6304 4211 5325 7774 7857 5121 8331 9317 1042 8291 9698 7373 440 9788 7938 7191 5563 4554 596 9733 4920 5398 3642 844 5733 4048 4417 8279 3054 4596 3153 12 17 12 36 12 15 12 13 12 2 12 30 12 18 12 33 12 4 12 39 12 25 12 20 12 10 12 9 12 23 12 29 12 3 1...
output:
35649 36231 35371 40865 42427 41959 38077 37617 41456 40848 38845 43861 42318 42491 39665 42965 43861 35586 42925 44242 42007 35074 44332 42572 41735 40197 39188 35230 44367 39464 40032 38276 35388 40367 38682 38961 42913 37688 39140 37787
result:
wrong answer 3rd numbers differ - expected: '35281', found: '35371'