提出 #242469


ソースコード 拡げる

Copy
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const long long INF = 1<<25;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vertex;
typedef vector<vertex> graph;

ll dp[5010][5010], tsz[5010];

int main(){
	int n;
	cin>>n;
	vector<ll> s(n);
	for(int i = 0; i < n; i++){
		cin>>s[i];
	}
	graph g(n);
	for(int i = 0; i < n-1; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		g[a].push_back(b);
	}
	int m;
	cin>>m;
	vector<ll> t(m);
	for(int i = 0; i < m; i++){
		cin>>t[i];
	}
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	ll sum = 0;
	for(int i = 0; i < n; i++){
		sum += s[i];
	}
	ll res = sum;
	//memset(dp, -1, sizeof(dp));
	for(int i = 0; i <= n; i++){
		for(int j = 0;  j <= n; j++){
			dp[i][j] = INF;
		}
	}

	for(int i = n-1; i >= 0; i--){
		dp[i][0] = 0;
		dp[i][1] = s[i];
		tsz[i] = 1;
		for(int j = 0; j < g[i].size(); j++){
			for(int k = 1; k <= tsz[i]; k++){
				for(int l = 1; l <= tsz[j]; l++){
					dp[i][k+l] = min(dp[i][k+l], dp[i][k]+dp[j][l]);
				}
			}
			tsz[i] += tsz[j];
		}
	}
	ll sumt = 0;
	for(int i = 0; i < n; i++){
		sumt += t[i];
		if(dp[0][i+1]>=0){
			res = max(res, sum-dp[i][i+1]+sumt);
		}
	}
	cout<<res<<endl;

	return 0;
}

提出情報

提出日時
問題 D - 高橋君と木のおもちゃ
ユーザ Lepton
言語 C++ (G++ 4.6.4)
得点 0
コード長 1694 Byte
結果
実行時間 355 ms
メモリ 196832 KB

ジャッジ結果

セット名 Sample Subtask1 Subtask2 Subtask3
得点 / 配点 0 / 0 0 / 10 0 / 20 0 / 70
結果
× 1
× 1
× 1
× 31
× 1
× 61
× 1
× 91
セット名 テストケース
Sample subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
ケース名 結果 実行時間 メモリ
subtask0-sample-01.txt 27 ms 768 KB
subtask0-sample-02.txt 23 ms 932 KB
subtask1-01.txt 24 ms 796 KB
subtask1-02.txt 25 ms 800 KB
subtask1-03.txt 25 ms 928 KB
subtask1-04.txt 23 ms 928 KB
subtask1-05.txt 24 ms 932 KB
subtask1-06.txt 24 ms 928 KB
subtask1-07.txt 25 ms 804 KB
subtask1-08.txt 24 ms 932 KB
subtask1-09.txt 24 ms 812 KB
subtask1-10.txt 24 ms 804 KB
subtask1-11.txt 24 ms 928 KB
subtask1-12.txt 25 ms 744 KB
subtask1-13.txt 23 ms 924 KB
subtask1-14.txt 24 ms 932 KB
subtask1-15.txt 23 ms 924 KB
subtask1-16.txt 24 ms 812 KB
subtask1-17.txt 28 ms 740 KB
subtask1-18.txt 24 ms 800 KB
subtask1-19.txt 24 ms 932 KB
subtask1-20.txt 24 ms 928 KB
subtask1-21.txt 24 ms 804 KB
subtask1-22.txt 24 ms 808 KB
subtask1-23.txt 24 ms 932 KB
subtask1-24.txt 24 ms 804 KB
subtask1-25.txt 23 ms 800 KB
subtask1-26.txt 24 ms 796 KB
subtask1-27.txt 25 ms 928 KB
subtask1-28.txt 23 ms 932 KB
subtask1-29.txt 24 ms 932 KB
subtask1-30.txt 23 ms 812 KB
subtask2-01.txt 24 ms 800 KB
subtask2-02.txt 23 ms 804 KB
subtask2-03.txt 25 ms 780 KB
subtask2-04.txt 26 ms 732 KB
subtask2-05.txt 24 ms 928 KB
subtask2-06.txt 23 ms 800 KB
subtask2-07.txt 24 ms 800 KB
subtask2-08.txt 24 ms 928 KB
subtask2-09.txt 24 ms 808 KB
subtask2-10.txt 24 ms 928 KB
subtask2-11.txt 23 ms 924 KB
subtask2-12.txt 24 ms 932 KB
subtask2-13.txt 23 ms 800 KB
subtask2-14.txt 24 ms 924 KB
subtask2-15.txt 23 ms 932 KB
subtask2-16.txt 25 ms 820 KB
subtask2-17.txt 23 ms 932 KB
subtask2-18.txt 23 ms 928 KB
subtask2-19.txt 23 ms 928 KB
subtask2-20.txt 24 ms 928 KB
subtask2-21.txt 24 ms 808 KB
subtask2-22.txt 24 ms 804 KB
subtask2-23.txt 24 ms 928 KB
subtask2-24.txt 23 ms 868 KB
subtask2-25.txt 24 ms 804 KB
subtask2-26.txt 24 ms 924 KB
subtask2-27.txt 24 ms 928 KB
subtask2-28.txt 25 ms 804 KB
subtask2-29.txt 26 ms 924 KB
subtask2-30.txt 27 ms 928 KB
subtask3-01.txt 27 ms 2844 KB
subtask3-02.txt 39 ms 8992 KB
subtask3-03.txt 45 ms 12576 KB
subtask3-04.txt 43 ms 12576 KB
subtask3-05.txt 90 ms 40096 KB
subtask3-06.txt 161 ms 83244 KB
subtask3-07.txt 253 ms 141992 KB
subtask3-08.txt 339 ms 196784 KB
subtask3-09.txt 338 ms 196772 KB
subtask3-10.txt 339 ms 196768 KB
subtask3-11.txt 338 ms 196780 KB
subtask3-12.txt 341 ms 196772 KB
subtask3-13.txt 345 ms 196780 KB
subtask3-14.txt 349 ms 196776 KB
subtask3-15.txt 346 ms 196784 KB
subtask3-16.txt 345 ms 196776 KB
subtask3-17.txt 340 ms 196776 KB
subtask3-18.txt 344 ms 196768 KB
subtask3-19.txt 348 ms 196772 KB
subtask3-20.txt 344 ms 196780 KB
subtask3-21.txt 346 ms 196776 KB
subtask3-22.txt 344 ms 196776 KB
subtask3-23.txt 355 ms 196780 KB
subtask3-24.txt 345 ms 196768 KB
subtask3-25.txt 345 ms 196772 KB
subtask3-26.txt 343 ms 196764 KB
subtask3-27.txt 345 ms 196776 KB
subtask3-28.txt 346 ms 196772 KB
subtask3-29.txt 343 ms 196784 KB
subtask3-30.txt 347 ms 196832 KB