Submission #780932

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
vector<int> ts[500000];
vector<int> ev[500010];
int N,M[500000],T,it[500000];
ll w[500000];
ll inf=1e18;
struct starryskytree{
	static const int N=1<<19;
	ll mx[N*2],ad[N*2];
	starryskytree(){
		rep(i,N*2) ad[i]=0,mx[i]=0;
	}
	void add(int a,int b,ll v,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return;
		if(a<=l&&r<=b){
			ad[k]+=v;
			return;
		}
		add(a,b,v,l,(l+r)/2,k*2);
		add(a,b,v,(l+r)/2,r,k*2+1);
		mx[k]=max(mx[k*2]+ad[k*2],mx[k*2+1]+ad[k*2+1]);
	}
	ll getmax(int a,int b,int l=0,int r=N,int k=1){
		if(b<=l||r<=a) return -inf;
		if(a<=l&&r<=b) return mx[k]+ad[k];
		return ad[k]+max(getmax(a,b,l,(l+r)/2,k*2),getmax(a,b,(l+r)/2,r,k*2+1));
	}
}seg;
int main(){
	cin>>N;
	rep(i,N) cin>>w[i];
	rep(i,N){
		int M;
		cin>>M;
		ts[i].pb(0);
		ev[0].pb(i);
		rep(j,M){
			int t;
			cin>>t;
			t/=2;
			chmax(T,t);
			ts[i].pb(t);
			ev[t].pb(i);
		}
	}
	rep(i,N) it[i]=1;
	ll ans=0;
	rep1(i,T){
//		show(i);
		for(int v:ev[i]){
			seg.add(ts[v][it[v]-1],ts[v][it[v]],w[v]);
//			printf("add:%d,%d, w[v]=%d\n",ts[v][it[v]-1],ts[v][it[v]],w[v]);
			it[v]++;
		}
		ll tmp=seg.getmax(0,i);
//		show(tmp);
		seg.add(i,i+1,tmp);
		chmax(ans,tmp);
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result