結果
| 問題 | No.2478 Disjoint-Sparse-Table Optimization |
| ユーザー |
👑  tute7627
|
| 提出日時 | 2023-09-10 18:02:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 5,879 bytes |
| コンパイル時間 | 3,122 ms |
| コンパイル使用メモリ | 235,612 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-28 09:13:54 |
| 合計ジャッジ時間 | 3,815 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 5 ms
6,944 KB |
| testcase_04 | AC | 5 ms
6,940 KB |
| testcase_05 | AC | 3 ms
6,944 KB |
| testcase_06 | AC | 4 ms
6,944 KB |
| testcase_07 | AC | 5 ms
6,940 KB |
| testcase_08 | AC | 5 ms
6,940 KB |
| testcase_09 | AC | 5 ms
6,940 KB |
| testcase_10 | AC | 5 ms
6,944 KB |
| testcase_11 | AC | 5 ms
6,940 KB |
| testcase_12 | AC | 2 ms
6,944 KB |
| testcase_13 | AC | 5 ms
6,944 KB |
ソースコード
#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)
#endif
using 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]));
else
labelS(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]);
else
labelS(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;
}