QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376724#4581. Energy GenerationschrodingerstomTL 1ms3944kbC++143.4kb2024-04-04 15:49:402024-04-04 15:49:41

Judging History

你现在查看的是最新测评结果

  • [2024-04-04 15:49:41]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3944kb
  • [2024-04-04 15:49:40]
  • 提交

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...

output:


result: