結果
| 問題 | No.2478 Disjoint-Sparse-Table Optimization |
| ユーザー |
👑  tute7627
|
| 提出日時 | 2023-09-10 18:02:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 4 ms / 2,000 ms |
| コード長 | 5,879 bytes |
| コンパイル時間 | 2,727 ms |
| コンパイル使用メモリ | 227,652 KB |
| 最終ジャッジ日時 | 2025-02-16 21:30:19 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rng(i,a,b) for(int i=int(a);i<int(b);i++)#define rep(i,b) rng(i,0,b)#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)#define per(i,b) gnr(i,0,b)#define pb push_back#define eb emplace_back#define a first#define b second#define bg begin()#define ed end()#define all(x) x.bg,x.ed#define si(x) int(x.size())#ifdef LOCAL#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl#else#define dmp(x) void(0)#endifusing ll=long long;const ll infLL=LLONG_MAX/3;template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}template<class t> using vc=vector<t>;template<class t> using vvc=vc<vc<t>>;using pi=pair<int,int>;using vi=vc<int>;//max weight matching for general graphs O(N^3)//init with an adjacency matrix g: use none for not-connected pairs.//ans = max weight matching of size 0,1,...,M. (M = max cardinality).//sol = solutions//verify yosupo, stress-tested(without int=ll)static const ll none=-infLL/3;struct maxweight{static pi rev(pi x){return pi(x.b,x.a);}const vvc<ll>&g;const int n;vi idx,mt,bl,bs,tp;vc<ll> u,z;vc<pi> par,sf,ss;vvc<pi> me,ce;vvc<int> cb;ll p(pi e){if(e.a==e.b)return infLL;return u[e.a]+u[e.b]-g[e.a][e.b]*2;}void chme(pi&x,pi y){if(p(x)>p(y))x=y;}void match(pi e){int a=e.a,b=e.b;mt[a]=b;mt[b]=a;bs[bl[a]]=a;bs[bl[b]]=b;}void setb(int v,int b){if(v<n) bl[v]=b;else for(auto c:cb[v]) setb(c,b);}void make(const vc<pi>&es){int v=idx.back();idx.pop_back();ce[v]=es;cb[v].clear();for(auto e:es)cb[v].pb(bl[e.a]);rep(i,n)me[v][i]=pi(-1,-1);for(auto c:cb[v]){tp[c]=-2;setb(c,v);rep(i,n)chme(me[v][i],me[c][i]);}bs[v]=bs[cb[v][0]];z[v]=0;labelS(v,par[cb[v][0]]);}vc<pi> path(int v){vc<pi> es;while(par[bl[v]].a!=-1){es.pb(par[bl[v]]);v=par[bl[v]].a;}return es;}bool SS(pi e){vc<pi> x=path(e.a),y=path(e.b);while(x.size()&&y.size()&&x.back()==y.back()){x.pop_back();y.pop_back();}vc<pi> es=x;reverse(all(es));es.pb(e);for(auto f:y)es.pb(rev(f));if(bl[es.front().a]==bl[es.back().b]){make(es);return false;}else{for(int i=0;i<int(es.size());i+=2){match(es[i]);for(auto j:{bl[es[i].a],bl[es[i].b]}){expand(j,true);setb(j,j);}}return true;}}void expand(int v,bool r){if(v<n)return;for(auto c:cb[v])setb(c,c);rep(i,cb[v].size())if(bl[bs[v]]==cb[v][i]){rotate(cb[v].begin(),cb[v].begin()+i,cb[v].end());rotate(ce[v].begin(),ce[v].begin()+i,ce[v].end());break;}bs[bl[bs[v]]]=bs[v];for(int i=1;i<int(ce[v].size());i+=2)match(ce[v][i]);if(r){for(auto c:cb[v])expand(c,true);}else{int w=bl[par[v].b];labelT(w,par[v]);rep(i,cb[v].size())if(cb[v][i]==w){if(i%2==0){rep(j,i)if(j%2==0)labelT(bl[ce[v][j].a],rev(ce[v][j]));elselabelS(bl[ce[v][j].a],rev(ce[v][j]));rng(j,i+1,cb[v].size())tp[cb[v][j]]=-1;}else{rng(j,i,ce[v].size())if(j%2==0)labelT(bl[ce[v][j].b],ce[v][j]);elselabelS(bl[ce[v][j].b],ce[v][j]);rng(j,1,i)tp[cb[v][j]]=-1;}}tp[v]=-2;idx.pb(v);}}void labelS(int v,pi p){tp[v]=0;par[v]=p;ss[v]=pi(-1,-1);rep(i,n)if(bl[i]!=v){if(tp[bl[i]]==0){chme(ss[v],me[v][i]);chme(ss[bl[i]],rev(me[v][i]));}else{chme(sf[i],me[v][i]);}}}void labelT(int v,const pi&p){tp[v]=1;par[v]=p;}vc<ll> ans;vvc<int> sol;maxweight(const vvc<ll>&gg):g(gg),n(g.size()),idx(n),mt(n,-1),bl(n),bs(n*2),tp(n*2,-1),u(n),z(n*2,0),par(n*2),sf(n),ss(n*2),me(n*2,vc<pi>(n)),ce(n*2),cb(n*2){iota(all(idx),n);iota(all(bl),0);iota(all(bs),0);rng(i,n,n*2)tp[i]=-2;rep(i,n)rep(j,n)me[i][j]=pi(i,j);{ll mx=-infLL;rep(i,n)rep(j,i)chmax(mx,g[i][j]);fill(all(u),mx);}ans.pb(0);sol.pb(vi(n,-1));rep(_,n/2){rep(i,n*2)if(tp[i]!=-2) tp[i]=-1;fill(all(sf),pi(-1,-1));rep(i,n)if(mt[i]==-1)labelS(bl[i],pi(-1,-1));while(true){ll d=infLL;pi e;rep(i,n){int b=bl[i];if(tp[b]==-1){if(chmin(d,p(sf[i])))e=sf[i];}else if(tp[b]==0){if(chmin(d,p(ss[b])/2))e=ss[b];}else if(n<=b){if(chmin(d,z[b]/2))e=pi(b,-1);}}rep(i,n){int t=tp[bl[i]];if(t==0) u[i]-=d;else if(t==1) u[i]+=d;}rng(i,n,n*2)if(tp[i]==0)z[i]+=d*2;else if(tp[i]==1)z[i]-=d*2;if(e.b==-1){expand(e.a,false);}else if(tp[bl[e.b]]==0){if(SS(e)) break;}else{int t=bl[e.b],m=mt[bs[t]];labelT(t,e);labelS(bl[m],pi(bs[t],m));}}bool bad=false;ll sum=0;rep(i,n)if(i<mt[i]){if(g[i][mt[i]]==none){bad=true;break;}sum+=g[i][mt[i]];}if(bad)break;ans.pb(sum);sol.pb(mt);}}};int main(){int Q;cin >> Q;assert(1 <= Q && Q <= 100);vector<int>L(Q), R(Q);for(int i = 0; i < Q; i++){cin >> L[i] >> R[i];assert(1 <= L[i] && L[i] < R[i] && R[i] <= 2*Q);L[i] -= 1;R[i] -= 1;}vector<long long>A(2*Q);for(int i = 1; i < 2*Q; i++){cin >> A[i];assert(1 <= A[i] && A[i] <= 1e9);A[i] += A[i - 1];}vector w(Q, vector(Q, none));long long ret = 0;for(int i = 0; i < Q; i++){ret += A[R[i]] - A[L[i]];for(int j = 0; j < Q; j++){if(i == j)continue;if(L[i] < L[j] && L[j] < R[i] && R[i] < R[j]){w[i][j] = w[j][i] = A[R[i]] - A[L[j]];}}}maxweight match(w);cout << ret - *max_element(match.ans.begin(), match.ans.end()) << endl;}