Submission #298525

#	Time	Username	Problem	Language	Result	Execution time	Memory
298525		LifeHappen__	Džumbus (COCI19_dzumbus)	C++14	110 / 110	63 ms	19064 KiB

dzumbus

#include<bits/stdc++.h>

using namespace std;

#define int long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}

#define forinc(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define fordec(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=1005;
const int inf=1e18;
int n,m,a[N];
vector<int> ad[N];
int f[N][N][2],dd[N],sz[N],ans[N];

void Min(int &x,int y){
   x=min(x,y);
}

void dfs(int u){
   dd[u]=1;
   sz[u]=1;
   forinc(i,1,n) f[u][i][0]=f[u][i][1]=inf;
   f[u][0][1]=inf;
   forv(v,ad[u]) if(!dd[v]){
      dfs(v);
      fordec(i,sz[u],0){
         for(int j=0; j<=sz[v] && i+j<=n; ++j){
            Min(f[u][i+j][0], f[u][i][0]+min(f[v][j][1],f[v][j][0]));
            Min(f[u][i+j][1], f[u][i][1]+min(f[v][j][1],f[v][j][0]));
            Min(f[u][i+j+1][1], f[u][i][0]+f[v][j][1]+a[u]);
            Min(f[u][i+j+1][1], f[u][i][1]+f[v][j][0]+a[v]);
            Min(f[u][i+j+2][1], f[u][i][0]+f[v][j][0]+a[v]+a[u]);
         }
      }
      sz[u]+=sz[v];
   }
}

int32_t main(){
   fasty;

   cin>>n>>m;
   forinc(i,1,n) cin>>a[i];
   forinc(i,1,m){
      int u,v; cin>>u>>v;
      ad[u].pb(v); ad[v].pb(u);
   }
   forinc(i,1,n) ans[i]=inf;
   forinc(i,1,n) if(!dd[i]){
      dfs(i);
      fordec(j,n,0){
         for(int u=0; u+j<=n && u<=sz[i]; ++u){
            Min(ans[j+u], ans[j]+min(f[i][u][0], f[i][u][1]));
         }
      }
   }
   fordec(i,n-1,0) ans[i]=min(ans[i],ans[i+1]);
   int ri=n;
   //forinc(i,1,n) cerr<<ans[i]<<' ';
   forinc(i,0,n) if(ans[i]>1e9){
      ri=i-1;
      break;
   }
   int que; cin>>que; forinc(_,1,que){
      int x; cin>>x;
      int l=0, r=ri, ret=0;
      while(l<=r){
         int mid=l+(r-l)/2;
         if(ans[mid]<=x) ret=mid, l=mid+1;
         else r=mid-1;
      }
      cout<<ret<<'\n';
   }
}

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