Submission #441964

#	Time	Username	Problem	Language	Result	Execution time	Memory
441964		Yomapeed	Džumbus (COCI19_dzumbus)	C++17	0 / 110	515 ms	524292 KiB

dzumbus

#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 1e3 + 5;
ll dp[N][N][2];
void chmin(ll &a, ll b){
	a = min(a, b);
} 
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	fast;
	ll T = 1;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k < 2; k++){
				dp[i][j][k] = INF;
			}
		}
	}
	//cin >> T;
	while (T--) {
		ll n, m;
		cin >> n >> m;
		assert(n != 1);
		vector<ll> c(n + 1);
		for(int i = 1; i <= n; i++){
			cin >> c[i];
		}
		vector<vector<ll>> adj(n + 1);
		for(int i = 1; i <= m; i++){
			ll a, b;
			cin >> a >> b;
			adj[a].pb(b);
			adj[b].pb(a);
		}
		ll g = -1;
		for(int i = 1; i <= n; i++){
			if((int)adj[i].size() == 1){
				g = i;
				break;
			}
		}
		assert(g != -1);
		vector<ll> v;
		v.pb(g);
		ll p = -1;
		while((int)v.size() != n){
			
			for(auto u : adj[g]){
				if(u != p){
					v.pb(u);
					p = g;
					g = u;
				}
			}
		}
		
		dp[0][0][0] = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= n; j++){
				chmin(dp[i + 1][j][0], dp[i][j][0]);
				chmin(dp[i + 1][j][0], dp[i][j][1]);
				
				chmin(dp[i + 1][j + 1][1], dp[i][j][1] + c[v[i]]);
				
				if(i >= 1){
					chmin(dp[i + 1][j + 2][1], dp[i][j][0] + c[v[i - 1]] + c[v[i]]);
				}
			}
		}
		
		ll q;
		cin >> q;
		while(q--){
			ll s;
			cin >> s;
			ll ans = 0;
			for(int i = n; i >= 0; i--){
				
				if(dp[n][i][0] <= s || dp[n][i][1] <= s){
					ans = i;
					break;
				}
			}
			assert(ans != 1);
			cout << ans << "\n";
		}
	}
	return 0;
}

Compilation message (stderr)

dzumbus.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
dzumbus.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

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