QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402302#4581. Energy GenerationNahidameowWA 1ms3908kbC++202.8kb2024-04-30 11:20:382024-04-30 11:20:39

Judging History

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

  • [2024-04-30 11:20:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3908kb
  • [2024-04-30 11:20:38]
  • 提交

answer

#include<bits/stdc++.h>
#define pd push_back
#define all(A) A.begin(),A.end()
#define lb lower_bound
#define ve std::vector
typedef long long ll;
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
const int N=5e3+10;
const int M=1e6+10;
const ll inf=1e12;
struct SSP{
	ll inf;
	int S,T;
	struct node{int nxt,y;ll val;}E[M];
	int H[N],cnt;
	int dep[N],cur[N];
	void ST(int _S,int _T,ll INF){S=_S,T=_T;inf=INF;}
	void init(){cnt=1,memset(H,0,sizeof(H));}
	void add(int x,int y,ll z){E[++cnt]={H[x],y,z};H[x]=cnt;}
	void Add(int x,int y,ll z){add(x,y,z);add(y,x,0);}
	bool BFS(){
		std::queue<int> q;memset(dep,0,sizeof(dep));dep[S]=1;q.push(S);
		while(!q.empty()){
			auto x=q.front();q.pop();
			for(int i=H[x];i;i=E[i].nxt){
				int y=E[i].y;
				if(E[i].val&&!dep[y]){
					q.push(y);
					dep[y]=dep[x]+1;
					if(y==T)return true;
				}
			}
		}return false;
	}ll dfs(int x,ll mf){
		if(x==T)return mf;ll ans=0;
		for(int &i=cur[x];i;i=E[i].nxt){
			auto y=E[i].y;
			if(E[i].val&&dep[y]==dep[x]+1){
				ll f=dfs(y,std::min(mf,E[i].val));
				mf-=f;E[i].val-=f;ans+=f;E[i^1].val+=f;
				if(!mf)break;
			}
		}if(!ans)dep[x]=0;
		return ans;
	}ll Dinic(){
		ll ans=0;
		while(BFS()){
			memcpy(cur,H,sizeof(cur));
			ans+=dfs(S,inf);
		}return ans;
	}
}E;
void solve(){
	//don't forget to open long long
	int n,R,G,P;std::cin>>n>>R>>G>>P;
	int S=2*n+1,T=2*n+2;
	ve<std::array<int,3>>v(n+1);
	ve<int>opt1(n+1),opt2(n+1);
	for(int i=1;i<=n;i++)std::cin>>v[i][0]>>v[i][1]>>v[i][2],v[i][2]/=90,
		opt1[i]=(v[i][2]==1||v[i][2]==2),opt2[i]=(v[i][2]==2||v[i][2]==3);
	ll ans=P*n;
	auto check=[&](int i,int j)->bool{
		return (i!=j)&&0ll+(v[i][0]-v[j][0])*(v[i][0]-v[j][0])+(v[i][1]-v[j][1])*(v[i][1]-v[j][1])<=R*R;
	};
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(check(i,j))ans+=G*2;
	auto get=[&](ve<int>opt)->ll{
		E.init();E.ST(S,T,inf);
		for(int i=1;i<=n;i++)
			if(opt[i])E.Add(i,T,P);
			else E.Add(S,i,P);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				if(check(i,j))
					E.Add(i,j,2*G),
					E.Add(j,i,2*G);
		return E.Dinic();
	};
	return std::cout<<ans-get(opt1)-get(opt2)<<'\n',void();
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T=1;
	//std::cin>>T;
	while(T--)solve();

	return 0;
}





Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3908kb

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: 3676kb

input:

3 10 1 1000
0 0 0
2 2 0
-4 4 180

output:

2998

result:

ok single line: '2998'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3676kb

input:

4 10 1000 1
0 0 0
0 2 90
2 0 180
2 2 270

output:

12000

result:

wrong answer 1st lines differ - expected: '4002', found: '12000'