#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 < m);
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
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")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
32460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
32460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
32528 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
32460 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
