QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402302 | #4581. Energy Generation | Nahidameow | WA | 1ms | 3908kb | C++20 | 2.8kb | 2024-04-30 11:20:38 | 2024-04-30 11:20:39 |
Judging History
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'