QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376724 | #4581. Energy Generation | schrodingerstom | TL | 1ms | 3944kb | C++14 | 3.4kb | 2024-04-04 15:49:40 | 2024-04-04 15:49:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool memBeg;
template<typename T,typename TT> void chkmin(T &x,TT y) {if(x>y) x=y;}
template<typename T,typename TT> void chkmax(T &x,TT y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
return ret;
}
constexpr int maxn=55;
constexpr int inf=0x3f3f3f3f;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
int n,R,G,P,x[maxn],y[maxn],O[maxn],o[maxn];
namespace network_flow {
constexpr int maxnodes=maxn;
constexpr int maxedges=maxn*maxn+2*maxn;
int head[maxnodes],to[maxedges<<1],nxt[maxedges<<1],tot;
ll c[maxedges<<1];
void add_edge(int u,int v,ll w) {
to[tot]=v; c[tot]=w; nxt[tot]=head[u]; head[u]=tot++;
to[tot]=u; c[tot]=0; nxt[tot]=head[v]; head[v]=tot++;
}
int S,T,fir[maxnodes],dis[maxnodes],que[maxnodes];
bool bfs() {
for(int i=S;i<=T;i++) {fir[i]=head[i]; dis[i]=inf;}
int tead=0,rail=0;
dis[S]=0; que[rail++]=S;
while(tead<rail) {
int cur=que[tead++];
for(int i=head[cur];~i;i=nxt[i]) {
if(c[i]&&dis[cur]+1<dis[to[i]]) {
dis[to[i]]=dis[cur]+1;
que[rail++]=to[i];
}
}
}
return dis[T]<inf;
}
ll dfs(int u,ll limit) {
if(u==T) return limit;
ll flow=0ll;
for(int i=fir[u];~i;i=nxt[i]) {
fir[u]=i;
if(c[i]&&dis[u]+1==dis[to[i]]) {
ll add=dfs(to[i],min(limit-flow,c[i]));
c[i]-=add; c[i^1]+=add; flow+=add;
if(flow==limit) return flow;
}
}
return flow;
}
ll Dinic() {
ll flow=0ll,cur=0ll;
while(bfs()) while((cur=dfs(S,INF))) flow+=cur;
return flow;
}
} // namespace network_flow
ll work() {
using namespace network_flow;
memset(head,-1,sizeof(head));
tot=0; S=0; T=2*n+1;
for(int i=1;i<=n;i++) {
if(o[i]==1) {
add_edge(S,i,-P+inf);
add_edge(i,i+n,INF);
add_edge(i+n,T,P+inf);
} else {
add_edge(S,i,P+inf);
add_edge(i,i+n,INF);
add_edge(i+n,T,-P+inf);
}
}
ll ret=0ll;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
if(x[i]!=x[j]&&y[i]!=y[j]&&(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])<=R*R) {
ret+=2*G; add_edge(i,j+n,4*G); add_edge(j,i+n,4*G);
}
}
}
ll cut=Dinic();
cut-=1ll*n*inf;
ret-=cut;
// printf("ret = %lld\n",ret);
return ret;
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
scanf("%d%d%d%d",&n,&R,&G,&P);
for(int i=1;i<=n;i++) {
scanf("%d%d%d",&x[i],&y[i],&O[i]);
}
for(int i=1;i<=n;i++) {
int t=O[i]/90;
if(t<2) o[i]=1;
else o[i]=-1;
}
ll ret=work();
for(int i=1;i<=n;i++) {
int t=O[i]/90;
if(!t||t==3) o[i]=1;
else o[i]=-1;
}
ret+=work();
assert(!(ret&1));
printf("%lld\n",ret>>1);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
3 10 10 15 0 0 0 2 2 180 100 100 180
output:
35
result:
ok single line: '35'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
3 10 1 1000 0 0 0 2 2 0 -4 4 180
output:
2998
result:
ok single line: '2998'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
4 10 1000 1 0 0 0 0 2 90 2 0 180 2 2 270
output:
4002
result:
ok single line: '4002'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
10 1000 1 2 186 98 180 206 689 270 695 90 90 292 247 90 -405 -125 270 928 -887 90 -45 -233 270 58 625 90 -215 136 270 -858 672 90
output:
62
result:
ok single line: '62'
Test #5:
score: -100
Time Limit Exceeded
input:
50 322 127 256 -418 -408 0 -317 -390 90 -208 -295 270 -187 -379 90 -343 -395 0 -278 -279 270 -191 -239 270 -192 -411 180 -203 -181 90 -330 -231 0 387 -416 180 352 -402 270 138 -181 0 299 -435 180 261 -273 0 191 -433 270 430 -182 0 290 -375 90 293 -426 90 458 -297 270 -416 278 270 -411 167 90 -312 23...