Submission #345194

#	Time	Username	Problem	Language	Result	Execution time	Memory
345194		limabeans	Džumbus (COCI19_dzumbus)	C++17	0 / 110	33 ms	16236 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1010;



int n,m,q;
vector<int> g[maxn];
ll d[maxn];

vector<ll> a;

void dfs(int at, int p) {
    a.push_back(d[at]);
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }
}

ll dp[maxn][maxn][2];

void upd(ll &x, ll y) {
    x = max(x, y);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>q;

    for (int i=1; i<=n; i++) {
	cin>>d[i];
    }
    for (int i=0; i<m; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    int r = -1;
    for (int i=1; i<=n; i++) {
	if ((int)g[i].size() == 1) r = i;
    }

    assert(~r);
    dfs(r, -1);

    vector<ll> Q(q);
    ll maxq = 0;
    for (int i=0; i<q; i++) {
	cin>>Q[i];
	maxq = max(maxq, Q[i]);
    }


    // dp[i][j][k]: first i elems, j money, 
    
    for (int i=0; i<n; i++) {
	for (int j=0; j<=maxq; j++) {
	    for (int k=0; k<=1; k++) {
		
		if (i>0) {
		    upd(dp[i][j][k], dp[i-1][j][k]);
		}
		
		if (j>0) {
		    upd(dp[i][j][k], dp[i][j-1][k]);
		}

		//don't take ith element
		if (k==0 && i>0) {
		    upd(dp[i][j][k], max(dp[i-1][j][0], dp[i-1][j][1]));
		}

		//take ith element
		if (k==1 && j>=a[i]) {
		    upd(dp[i][j][k], 1);
		    if (i>0) {
			upd(dp[i][j][k], 1+max(dp[i-1][j-a[i]][0],dp[i-1][j-a[i]][1]));
		    }
		}

		//take ith element, and i-1th element
		if (k==1 && i>=1 && j>=a[i]+a[i-1]) {
		    upd(dp[i][j][k], 2);
		    if (i>=2) {
			upd(dp[i][j][k], 2+max(dp[i-2][j-a[i]-a[i-1]][0], dp[i-2][j-a[i]-a[i-1]][1]));
		    }
		}
	    }
	}
    }


    while (q--) {
	ll x;
	cin>>x;
	ll res = max(dp[n-1][x][0], dp[n-1][x][1]);
	cout<<res<<"\n";
    }
    
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30