Submission #321514

#	Time	Username	Problem	Language	Result	Execution time	Memory
321514		ronnith	Džumbus (COCI19_dzumbus)	C++14	0 / 110	46 ms	7408 KiB

dzumbus

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL 
	#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
	#define dbg2(a,b) dbg(a);dbg(b)
	#define dbg3(a,b,c) dbg2(a,b);dbg(c)
	#define dln cerr << ln
#else
	#define dbg(x) 0
	#define dbg2(a,b) 0
	#define dbg3(a,b,c) 0
	#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;

template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

/*OUTPUT

*/

#define maxn 1000

ll N, M, d[maxn], ind[maxn], ans[200000];
vector<ll> adj[maxn], arr;

void dfs(int x,int pr){
	arr.pb(d[x]);
	trav(e,adj[x]){
		if(e != pr)dfs(e,x);
	}
}

void solve(){
	cin >> N >> M;

	FOR(i,0,N) cin >> d[i];

	FOR(i,0,M){
		int x,y;
		cin >> x >> y;
		x --;y --;
		adj[x].pb(y);
		adj[y].pb(x);
		ind[x] ++;ind[y] ++;
	}

	int start = 0;FOR(i,0,N)if(ind[i] < 2)start = i;

	dfs(start,-1);

	int Q;cin >> Q;

	vector<pair<ll,int>> queries;

	FOR(i,0,Q){
		int x;
		cin >> x;
		queries.pb(mk(x,i));
	}

	sort(all(queries));

	int ptr = 0;
	ll pr = 0;
	int an = 0;
	trav(x,queries){
		if(ptr < N and pr + arr[ptr] <= x.f){
			an ++;
			ptr ++;
			pr += arr[ptr];
		}
		if(an >= 2)
		maxs(ans[x.s], an);
	}
	ptr = N - 1, pr = an = 0;
	trav(x,queries){
		if(ptr >= 0 and pr + arr[ptr] <= x.f){
			an ++;
			ptr --;
			pr += arr[ptr];
		}
		if(an >= 2)
		maxs(ans[x.s], an);
	}

	if(N >= 2){
		an = 0,pr = arr[0] + arr[N - 1];
		int p = 1, q = N - 2;
		trav(x,queries){
			if(p <= q and pr + min(arr[p],arr[q]) <= x.f){
				an ++;
				pr += min(arr[p],arr[q]);
				if(arr[p] < arr[q])p ++;
				else q --;
			}
			int crr = an;
			if(p > 1)crr ++;
			if(q < N - 2)crr ++;
			maxs(ans[x.s],crr);
		}
	}
	FOR(i,0,Q){
		cout << ans[i] << '\n';
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t --){
		solve();
	}
}

Compilation message (stderr)

dzumbus.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~

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