[校内训练20_09_29]ABC

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1E6+5;
 4 int n,m,tot;
 5 int totT,tmp[maxn],jump[maxn][20];
 6 struct line
 7 {
 8     int l,r;
 9     bool operator<(const line&A)const
10     {
11         return r<A.r;
12     }
13 }a[maxn];
14 int t[maxn*4];
15 void change(int l,int r,int pos,int x,int num)
16 {
17     if(t[num]==0||a[x].r<a[t[num]].r)
18         t[num]=x;
19     if(l==r)
20         return;
21     int mid=(l+r)>>1;
22     if(pos<=mid)
23         change(l,mid,pos,x,num<<1);
24     else
25         change(mid+1,r,pos,x,num<<1|1);
26 }
27 int ask(int L,int R,int l,int r,int num)
28 {
29     if(L<=l&&r<=R)
30         return t[num];
31     int mid=(l+r)>>1;
32     if(R<=mid)
33         return ask(L,R,l,mid,num<<1);
34     else if(mid<L)
35         return ask(L,R,mid+1,r,num<<1|1);
36     int x=ask(L,R,l,mid,num<<1),y=ask(L,R,mid+1,r,num<<1|1);
37     if(x==0)
38         return y;
39     else if(y==0)
40         return x;
41     else if(a[x].r<a[y].r)
42         return x;
43     return y;
44 }
45 inline void solve()
46 {
47     for(int i=1;i<=tot;++i)
48         tmp[++totT]=a[i].l,tmp[++totT]=a[i].r;
49     sort(tmp+1,tmp+totT+1);
50     totT=unique(tmp+1,tmp+totT+1)-tmp-1;
51     sort(a+1,a+tot+1);
52     int ans=0;
53     for(int i=tot;i>=1;--i)
54     {
55         int pos=lower_bound(tmp+1,tmp+totT+1,a[i].r)-tmp;
56         int x=ask(pos,totT,1,totT,1);
57         jump[i][0]=x;
58         pos=lower_bound(tmp+1,tmp+totT+1,a[i].l)-tmp;
59         change(1,totT,pos,i,1);
60     }
61     for(int j=1;j<20;++j)
62         for(int i=1;i<=tot;++i)
63             jump[i][j]=jump[jump[i][j-1]][j-1];
64     for(int i=1;i<=tot;++i)
65     {
66         int s=1;
67         int u=i;
68         for(int j=19;j>=0;--j)
69             if(jump[u][j]&&a[jump[u][j]].r-a[i].l<=m)
70             {
71                 s+=1<<j;
72                 u=jump[u][j];
73             }
74         ans=max(ans,s);
75     }
76     cout<<ans<<endl;
77 }
78 int main()
79 {
80     freopen("circular.in","r",stdin);
81     freopen("circular.out","w",stdout);
82     ios::sync_with_stdio(false);
83     cin>>m>>n;
84     for(int i=1;i<=n;++i)
85     {
86         int l,r;
87         cin>>l>>r;
88         if(l<r)
89         {
90             a[++tot]=(line){l,r};
91             a[++tot]=(line){l+m,r+m};
92         }
93         else
94             a[++tot]=(line){l,r+m};
95     }
96     solve();
97     return 0;
98 }

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long int ll;
  4 const int maxn=1E6+5;
  5 const ll inf=1E12;
  6 int tot,n,m,k,a[505][505],id1[505][505],id2[505][505];
  7 int dx[4]={0,1,0,-1};
  8 int dy[4]={1,0,-1,0};
  9 bool ban[505][505];
 10 namespace FLOW
 11 {
 12     int S,T;
 13     int size=1,head[maxn],from[maxn];
 14     ll dis[maxn],maxF[maxn];
 15     bool vis[maxn];
 16     struct edge
 17     {
 18         int to,next;
 19         ll cost,flow;
 20     }E[maxn*2];
 21     inline void addE(int u,int v,int c,int f)
 22     {
 23         E[++size].to=v;
 24         E[size].next=head[u];
 25         E[size].cost=c;
 26         E[size].flow=f;
 27         head[u]=size;
 28     }
 29     inline void add(int u,int v,int c,int f)
 30     {
 31 //        cout<<"ADD "<<u<<" "<<v<<" "<<c<<" "<<f<<endl;
 32         addE(u,v,c,f);
 33         addE(v,u,-c,0);
 34     }
 35     inline bool bfs()
 36     {
 37         for(int i=0;i<=T;++i)
 38             maxF[i]=0,dis[i]=-inf;
 39         queue<int>Q;
 40         Q.push(S);
 41         dis[S]=0;
 42         maxF[S]=inf;
 43         while(!Q.empty())
 44         {
 45             int u=Q.front();
 46             Q.pop();
 47             vis[u]=0;
 48             for(int i=head[u];i;i=E[i].next)
 49             {
 50                 int v=E[i].to;
 51                 ll nw=E[i].cost+dis[u];
 52                 if(E[i].flow==0||nw<=dis[v])
 53                     continue;
 54                 dis[v]=nw;
 55                 from[v]=i;
 56                 maxF[v]=min(maxF[u],E[i].flow);
 57                 if(!vis[v])
 58                     Q.push(v);
 59                 vis[v]=1;
 60             }
 61         }
 62         return dis[T]>0;
 63     }
 64     inline void MCMF()
 65     {
 66         ll s=0;
 67         for(int i=1;i<=n;++i)
 68             for(int j=1;j<=n;++j)
 69                 s+=a[i][j];
 70         while(bfs())
 71         {
 72             int pos=T,f=maxF[T];
 73             s-=f*dis[T];
 74             while(pos!=S)
 75             {
 76                 E[from[pos]].flow-=f;
 77                 E[from[pos]^1].flow+=f;
 78                 pos=E[from[pos]^1].to;
 79             }
 80         }
 81         cout<<s<<endl;
 82     }
 83 }
 84 int main()
 85 {
 86     freopen("marshland.in","r",stdin);
 87     freopen("marshland.out","w",stdout);
 88     ios::sync_with_stdio(false);
 89     cin>>n>>m>>k;
 90     ++tot;
 91     for(int i=1;i<=n;++i)
 92         for(int j=1;j<=n;++j)
 93         {
 94             cin>>a[i][j];
 95             id1[i][j]=++tot;
 96         }
 97     for(int i=1;i<=n;++i)
 98         for(int j=1;j<=n;++j)
 99             if((i+j)&1)
100                 id2[i][j]=++tot;
101     for(int i=1;i<=k;++i)
102     {
103         int x,y;
104         cin>>x>>y;
105         ban[x][y]=1;
106     }
107     FLOW::S=0,FLOW::T=tot+1;
108     FLOW::add(0,1,0,m);
109     for(int x=1;x<=n;++x)
110         for(int y=1;y<=n;++y)
111         {
112             if(ban[x][y])
113                 continue;
114             if((x+y)&1)
115             {
116                 if(x&1)
117                 {
118                     if(id1[x-1][y]&&!ban[x-1][y])
119                         FLOW::add(id1[x][y],id1[x-1][y],0,1);
120                     if(id1[x+1][y]&&!ban[x+1][y])
121                         FLOW::add(id1[x][y],id1[x+1][y],0,1);
122                 }
123                 else
124                 {
125                     if(id1[x][y-1]&&!ban[x][y-1])
126                         FLOW::add(id1[x][y],id1[x][y-1],0,1);
127                     if(id1[x][y+1]&&!ban[x][y+1])
128                         FLOW::add(id1[x][y],id1[x][y+1],0,1);
129                 }
130                 FLOW::add(id2[x][y],id1[x][y],a[x][y],1);
131             }
132             else
133             {
134                 if(x&1)
135                 {
136                     FLOW::add(1,id1[x][y],0,1);
137                     for(int i=0;i<4;++i)
138                     {
139                         int nx=x+dx[i],ny=y+dy[i];
140                         if(ban[nx][ny]||id2[nx][ny]==0)
141                             continue;
142                         FLOW::add(id1[x][y],id2[nx][ny],0,1);
143                     }
144                 }
145                 else
146                     FLOW::add(id1[x][y],tot+1,0,1);
147             }
148         }
149     FLOW::MCMF();
150     return 0;
151 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int ll;
 4 const ll inf=1E15;
 5 int tot,n,len,a[55][55],r[55][55];
 6 ll ans,tmp[(1<<18)+1];
 7 inline ll what(int x,int y)
 8 {
 9     if(r[x][y]==1)
10         return -a[x][y];
11     return a[x][y];
12 }
13 inline ll get(int col)
14 {
15     ll s=0;
16     for(int i=0;i<len-1;++i)
17     {
18         r[i][col]=0;
19         r[i][col+len]=r[i][col]^r[i][len-1];
20         r[i+len][col]=r[i][col]^r[len-1][col];
21         r[i+len][col+len]=r[i+len][col]^r[i+len][len-1];
22         ll g=what(i,col)+what(i,col+len)+what(i+len,col)+what(i+len,col+len);
23         
24         r[i][col]=1;
25         r[i][col+len]=r[i][col]^r[i][len-1];
26         r[i+len][col]=r[i][col]^r[len-1][col];
27         r[i+len][col+len]=r[i+len][col]^r[i+len][len-1];
28         g=max(g,what(i,col)+what(i,col+len)+what(i+len,col)+what(i+len,col+len));
29         
30         s+=g;
31     }
32     return s;
33 }
34 inline void solve(int S)
35 {
36     ll s=0;
37     for(int i=0;i<len;++i)
38         if(S&(1<<i))
39             r[i][len-1]=1;
40         else
41             r[i][len-1]=0;
42     for(int i=len;i<n;++i)
43         r[i][len-1]=r[i-len][len-1]^r[len-1][len-1];
44     for(int i=0;i<n;++i)
45         s+=what(i,len-1);
46     for(int i=0;i<len-1;++i)
47     {
48         r[len-1][i]=0;
49         r[len-1][i+len]=r[len-1][i]^r[len-1][len-1];
50         ll g=get(i)+what(len-1,i)+what(len-1,i+len);
51         
52         r[len-1][i]=1;
53         r[len-1][i+len]=r[len-1][i]^r[len-1][len-1];
54         g=max(g,get(i)+what(len-1,i)+what(len-1,i+len));
55         
56         s+=g;
57     }
58     ans=max(ans,s);
59 }
60 int main()
61 {
62     freopen("s.in","r",stdin);
63     freopen("s.out","w",stdout);
64     ios::sync_with_stdio(false);
65     cin>>n;
66     len=(n+1)/2;
67     for(int i=0;i<n;++i)
68         for(int j=0;j<n;++j)
69             cin>>a[i][j];
70     for(int S=0;S<(1<<len);++S)
71         solve(S);
72     cout<<ans<<endl;
73     return 0;
74 }