Submission #315254


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int N,M;
ll t[5050];
int G[5005];

ll sumNum(vector<int>s){
  ll res = 0;
  //  rep(i,N) cout << s[i] << " "; cout << endl;
  rep(i,N) res += s[i];
  return res;
}

ll dfs(int n, vector<int>s){
  if(M==n) return sumNum(s);
  //  rep(i,N) cout << s[i] << " "; cout << endl;
  //  cout << n << endl;
  ll res = 0;
  res = max(res, dfs(n+1, s));
  //  if(n==0 || n==2 || n==3 || n==5) return res;
  vector<int>ns;
  for(int i=0;i<N;i++){
    //    if(n==1&&i!=3) continue;
    //    if(n==4&&i!=5) continue;
    //    if(n==6&&i!=1) continue;
    //    if(n==7&&i!=0) continue;
    ns = s;
    int cur = i;
    int tmp = ns[cur]; ns[cur] = t[n];
    //    cout << n << " " << cur << endl;
    while(G[cur]>=0){
      //      if(n==6 && cur == 1) cout << "ok\n";
      cur = G[cur];
      swap(tmp, ns[cur]);
    }
    res = max(res, dfs(n+1, ns));
  }
  return res;
}

int main(){
  cin >> N;
  vector<int>s(N);
  rep(i,N) cin >> s[i];

  G[0] = -1;
  rep(i,N-1){
    int a,b;
    cin >> a >> b; a--; b--;
    G[b] = a;
  }
  //  rep(i,N) cout << G[i] << " "; cout << endl;
  cin >> M;
  rep(i,M) cin >> t[i];

  cout << dfs(0, s) << endl;
  return 0;
}

Submission Info

Submission Time
Task D - 高橋君と木のおもちゃ
User raven38
Language C++ (G++ 4.6.4)
Score 0
Code Size 2073 Byte
Status
Exec Time 2053 ms
Memory 99696 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt
Subtask1 0 / 10 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 0 / 20 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 0 / 70 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
Case Name Status Exec Time Memory
subtask0-sample-01.txt 2036 ms 1004 KB
subtask0-sample-02.txt 36 ms 808 KB
subtask1-01.txt 32 ms 808 KB
subtask1-02.txt 43 ms 860 KB
subtask1-03.txt 99 ms 884 KB
subtask1-04.txt 100 ms 912 KB
subtask1-05.txt 99 ms 812 KB
subtask1-06.txt 327 ms 808 KB
subtask1-07.txt 330 ms 868 KB
subtask1-08.txt 336 ms 876 KB
subtask1-09.txt 330 ms 920 KB
subtask1-10.txt 315 ms 920 KB
subtask1-11.txt 345 ms 840 KB
subtask1-12.txt 26 ms 872 KB
subtask1-13.txt 26 ms 900 KB
subtask1-14.txt 30 ms 868 KB
subtask1-15.txt 1049 ms 868 KB
subtask1-16.txt 172 ms 872 KB
subtask1-17.txt 2035 ms 1000 KB
subtask1-18.txt 2034 ms 1000 KB
subtask1-19.txt 26 ms 920 KB
subtask1-20.txt 25 ms 924 KB
subtask1-21.txt 26 ms 928 KB
subtask1-22.txt 26 ms 920 KB
subtask1-23.txt 31 ms 924 KB
subtask1-24.txt 31 ms 920 KB
subtask1-25.txt 73 ms 924 KB
subtask1-26.txt 401 ms 920 KB
subtask1-27.txt 2032 ms 1008 KB
subtask1-28.txt 2034 ms 1004 KB
subtask1-29.txt 2034 ms 1008 KB
subtask1-30.txt 2033 ms 1000 KB
subtask2-01.txt 26 ms 924 KB
subtask2-02.txt 24 ms 856 KB
subtask2-03.txt 2034 ms 1000 KB
subtask2-04.txt 2035 ms 992 KB
subtask2-05.txt 2035 ms 996 KB
subtask2-06.txt 2032 ms 1004 KB
subtask2-07.txt 2034 ms 1012 KB
subtask2-08.txt 2032 ms 1008 KB
subtask2-09.txt 41 ms 880 KB
subtask2-10.txt 2034 ms 1004 KB
subtask2-11.txt 2035 ms 1000 KB
subtask2-12.txt 26 ms 920 KB
subtask2-13.txt 2034 ms 1004 KB
subtask2-14.txt 2033 ms 1004 KB
subtask2-15.txt 2035 ms 1004 KB
subtask2-16.txt 2034 ms 996 KB
subtask2-17.txt 2037 ms 992 KB
subtask2-18.txt 2035 ms 996 KB
subtask2-19.txt 2036 ms 1004 KB
subtask2-20.txt 2035 ms 996 KB
subtask2-21.txt 2034 ms 1012 KB
subtask2-22.txt 2034 ms 892 KB
subtask2-23.txt 2034 ms 1000 KB
subtask2-24.txt 2033 ms 936 KB
subtask2-25.txt 2041 ms 1004 KB
subtask2-26.txt 2032 ms 1004 KB
subtask2-27.txt 2034 ms 996 KB
subtask2-28.txt 2036 ms 1704 KB
subtask2-29.txt 2036 ms 2272 KB
subtask2-30.txt 2034 ms 2284 KB
subtask3-01.txt 2034 ms 1620 KB
subtask3-02.txt 2034 ms 2904 KB
subtask3-03.txt 2035 ms 3436 KB
subtask3-04.txt 2034 ms 3816 KB
subtask3-05.txt 2040 ms 16956 KB
subtask3-06.txt 2042 ms 36708 KB
subtask3-07.txt 2039 ms 24804 KB
subtask3-08.txt 2039 ms 20832 KB
subtask3-09.txt 2045 ms 20848 KB
subtask3-10.txt 2042 ms 28660 KB
subtask3-11.txt 2040 ms 36592 KB
subtask3-12.txt 2040 ms 38508 KB
subtask3-13.txt 2044 ms 50408 KB
subtask3-14.txt 2046 ms 60256 KB
subtask3-15.txt 2045 ms 60264 KB
subtask3-16.txt 2049 ms 89828 KB
subtask3-17.txt 2052 ms 99696 KB
subtask3-18.txt 2052 ms 99696 KB
subtask3-19.txt 2051 ms 99696 KB
subtask3-20.txt 2047 ms 99612 KB
subtask3-21.txt 2052 ms 99696 KB
subtask3-22.txt 2050 ms 99692 KB
subtask3-23.txt 2053 ms 99688 KB
subtask3-24.txt 2051 ms 99692 KB
subtask3-25.txt 2050 ms 99692 KB
subtask3-26.txt 2050 ms 99628 KB
subtask3-27.txt 2051 ms 99672 KB
subtask3-28.txt 2053 ms 99688 KB
subtask3-29.txt 2051 ms 99680 KB
subtask3-30.txt 2053 ms 99692 KB