Submission #38904212 - AtCoder Grand Contest 031

Contest Duration: 2019-03-16 21:00:00+0900 - 2019-03-16 23:40:00+0900 (local time) (160 minutes) Back to Home

Submission #38904212

Source Code Expand

// LUOGU_RID: 102197646
#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;using LL=__int128;
using namespace std;const int N=320+5,M=N*N+5,K=50+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n,m,k,x,y,z,Op[N],X[N],Y[N],L[N],R[N],match[N];ll Ans;char c;
struct Node{int x,y;ll z;}P[N];
struct yyy{int to;ll w;int g,z;};struct ljb{int head=1,h[N];yyy f[M];void add(int x,int y,ll w,int g){f[++head]=(yyy){y,w,g,h[x]};h[x]=head;}}s,Cl;
int S,T;void con(int x,int y,ll w,int g){s.add(x,y,w,g);s.add(y,x,-w,0);}
namespace EK{
	ll d[N];int g[N],pre[N];queue<int> Q;
	int BFS(){
		Me(d,-0x3f);d[S]=0;g[S]=INF;Q.push(S);while(!Q.empty()){
			int x=Q.front();Q.pop();yyy tmp;for(int i=s.h[x];i;i=tmp.z){
				tmp=s.f[i];if(!tmp.g||d[tmp.to]>=d[x]+tmp.w) continue;
				d[tmp.to]=d[x]+tmp.w;g[tmp.to]=min(g[x],tmp.g);pre[tmp.to]=i;Q.push(tmp.to);
			}
		}
		return d[T]>=0;
	}
	pair<int,ll> calc(){
		ll Ans=0;int Ag=0;while(BFS()){
			Ag+=g[T];Ans+=g[T]*d[T];for(int p=T;p^S;p=s.f[pre[p]^1].to) s.f[pre[p]].g-=g[T],s.f[pre[p]^1].g+=g[T];
		}return {Ag,Ans};
	}
}
void calc(int k){
	int i,j;s=Cl;S=0;T=2*n+2*k+1;
	for(i=1;i<=n;i++) con(i,i+n,P[i].z,1);
	Me(L,-0x3f);Me(R,0x3f);for(i=1;i<=m;i++){
		if(Op[i]==1) for(j=Y[i]+1;j<=k;j++) L[j]=max(L[j],X[i]+1);
		if(Op[i]==2) for(j=k-Y[i];j>=1;j--) R[j]=min(R[j],X[i]-1);
	} 
	for(i=1;i<=k;i++) for(con(S,i+2*n,0,1),j=1;j<=n;j++) if(P[j].x>=L[i]&&P[j].x<=R[i]) con(i+2*n,j,0,1);
	Me(L,-0x3f);Me(R,0x3f);for(i=1;i<=m;i++){
		if(Op[i]==3) for(j=Y[i]+1;j<=k;j++) L[j]=max(L[j],X[i]+1);
		if(Op[i]==4) for(j=k-Y[i];j>=1;j--) R[j]=min(R[j],X[i]-1);
	}
	for(i=1;i<=k;i++) for(con(i+2*n+k,T,0,1),j=1;j<=n;j++) if(P[j].y>=L[i]&&P[j].y<=R[i]) con(j+n,i+2*n+k,0,1);
	auto p=EK::calc();if(p.first==k) Ans=max(Ans,p.second);
}
int main(){
	int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d%lld",&P[i].x,&P[i].y,&P[i].z);
	match['L']=1;match['R']=2;match['D']=3;match['U']=4;
	scanf("%d",&m);for(i=1;i<=m;i++)cin>>c,Op[i]=match[c],scanf("%d%d",&X[i],&Y[i]);
	for(i=1;i<=n;i++) calc(i);printf("%lld\n",Ans);
}

Submission Info

Submission Time	2023-02-15 19:10:33+0900
Task	E - Snuke the Phantom Thief
User	fangxintong
Language	C++ (GCC 9.2.1)
Score	1300
Code Size	2391 Byte
Status	AC
Exec Time	385 ms
Memory	6260 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:53:53: warning: array subscript has type ‘char’ [-Wchar-subscripts]
   53 |  scanf("%d",&m);for(i=1;i<=m;i++)cin>>c,Op[i]=match[c],scanf("%d%d",&X[i],&Y[i]);
      |                                                     ^
./Main.cpp:54:2: warning: this ‘for’ clause does not guard... [-Wmisleading-indentation]
   54 |  for(i=1;i<=n;i++) calc(i);printf("%lld\n",Ans);
      |  ^~~
./Main.cpp:54:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘for’
   54 |  for(i=1;i<=n;i++) calc(i);printf("%lld\n",Ans);
      |                            ^~~~~~
./Main.cpp:51:8: warning: unused variable ‘j’ [-Wunused-variable]
   51 |  int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d%lld",&P[i].x,&P[i].y,&P[i].z);
      |        ^
./Main.cpp:51:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   51 |  int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d%lld",&P[i].x,&P[i].y,&P[i].z);
      |          ~~~~~^~~~~~~~~
./Main.cpp:51:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   51 |  int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d%lld",&P[i].x,&P[i].y,&P[i].z);
      |                                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:53:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d",&m);for(i=1;i<=m;i++)cin>>c,Op[i]=match[c],scanf("%d%d",&X[i],&Y[i]);
      |  ~~~~~^~~~~~~~~
./Main.cpp:53:61: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d",&m);for(i=1;i<=m;i++)cin>>c,Op[i]=match[c],scanf("%d%d",&X[i],&Y[i]);
      |                                                        ~~~~~^~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

1300 / 1300

Status

× 4

× 71

Set Name	Test Cases
Sample	example_00, example_01, example_02, example_03
All	example_00, example_01, example_02, example_03, fixed_00, fixed_01, fixed_02, fixed_03, fixed_04, fixed_05, fixed_06, fixed_07, fixed_08, fixed_09, fixed_10, fixed_11, manyrand_00, manyrand_01, manyrand_02, manyrand_03, manyuse_00, manyuse_01, manyuse_02, manyuse_03, naname_00, naname_01, naname_02, naname_03, naname_04, naname_05, naname_06, naname_07, naname_08, naname_09, naname_10, naname_11, naname_line_00, naname_line_01, perm_00, perm_01, perm_02, perm_03, perm_04, perm_05, perm_06, perm_07, perm_08, perm_09, perm_10, perm_11, rand_00, rand_01, square_00, square_01, square_02, square_03, twinkle2_00, twinkle2_01, twinkle2_02, twinkle_00, twinkle_01, twinkle_02, twinkle_03, twinkle_04, twinkle_05, twinkle_06, twinkle_07, twinkle_08, twinkle_09, verysmall_rand_00, verysmall_rand_01

Case Name	Status	Exec Time	Memory
example_00	AC	10 ms	6152 KiB
example_01	AC	9 ms	6256 KiB
example_02	AC	6 ms	6096 KiB
example_03	AC	8 ms	6228 KiB
fixed_00	AC	22 ms	6192 KiB
fixed_01	AC	164 ms	6096 KiB
fixed_02	AC	62 ms	6240 KiB
fixed_03	AC	26 ms	6160 KiB
fixed_04	AC	21 ms	6196 KiB
fixed_05	AC	136 ms	6096 KiB
fixed_06	AC	20 ms	6244 KiB
fixed_07	AC	152 ms	6256 KiB
fixed_08	AC	83 ms	6096 KiB
fixed_09	AC	214 ms	6124 KiB
fixed_10	AC	17 ms	6100 KiB
fixed_11	AC	131 ms	6256 KiB
manyrand_00	AC	343 ms	6100 KiB
manyrand_01	AC	326 ms	6100 KiB
manyrand_02	AC	385 ms	6124 KiB
manyrand_03	AC	354 ms	6160 KiB
manyuse_00	AC	13 ms	6256 KiB
manyuse_01	AC	18 ms	6156 KiB
manyuse_02	AC	13 ms	6124 KiB
manyuse_03	AC	20 ms	6256 KiB
naname_00	AC	16 ms	6240 KiB
naname_01	AC	160 ms	6196 KiB
naname_02	AC	52 ms	6228 KiB
naname_03	AC	20 ms	6196 KiB
naname_04	AC	143 ms	6140 KiB
naname_05	AC	16 ms	6104 KiB
naname_06	AC	15 ms	6124 KiB
naname_07	AC	152 ms	6236 KiB
naname_08	AC	18 ms	6156 KiB
naname_09	AC	19 ms	6252 KiB
naname_10	AC	47 ms	6100 KiB
naname_11	AC	106 ms	6224 KiB
naname_line_00	AC	42 ms	6100 KiB
naname_line_01	AC	40 ms	6208 KiB
perm_00	AC	13 ms	6232 KiB
perm_01	AC	16 ms	6236 KiB
perm_02	AC	14 ms	6096 KiB
perm_03	AC	13 ms	6224 KiB
perm_04	AC	14 ms	6096 KiB
perm_05	AC	21 ms	6184 KiB
perm_06	AC	20 ms	6132 KiB
perm_07	AC	13 ms	6184 KiB
perm_08	AC	14 ms	6204 KiB
perm_09	AC	15 ms	6256 KiB
perm_10	AC	13 ms	6164 KiB
perm_11	AC	17 ms	6124 KiB
rand_00	AC	17 ms	6128 KiB
rand_01	AC	10 ms	6204 KiB
square_00	AC	16 ms	6208 KiB
square_01	AC	15 ms	6100 KiB
square_02	AC	16 ms	6156 KiB
square_03	AC	16 ms	6224 KiB
twinkle2_00	AC	36 ms	6100 KiB
twinkle2_01	AC	36 ms	6252 KiB
twinkle2_02	AC	36 ms	6196 KiB
twinkle_00	AC	25 ms	6100 KiB
twinkle_01	AC	29 ms	6228 KiB
twinkle_02	AC	26 ms	6128 KiB
twinkle_03	AC	25 ms	6256 KiB
twinkle_04	AC	31 ms	6160 KiB
twinkle_05	AC	27 ms	6260 KiB
twinkle_06	AC	28 ms	6096 KiB
twinkle_07	AC	29 ms	6256 KiB
twinkle_08	AC	26 ms	6240 KiB
twinkle_09	AC	27 ms	6128 KiB
verysmall_rand_00	AC	6 ms	6152 KiB
verysmall_rand_01	AC	7 ms	6192 KiB