有没有跌跌帮忙调调 6k 代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdlib>
#include<map>
#include<ctime>
#define x1 adsf
#define y1 jdaiofjio
#define x2 dffffff
#define y2 aidsjfiaojfoiajpfejaw
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
#define yes puts("YES")
#define no puts("NO")
using namespace std;
typedef long long ll;
const int INF(1e9+10);
const ll LLINF(1e18+10);
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){T t=x;x=y;y=t;return;}
template<typename T>
inline T Abs(T x){return x<0?-x:x;}

const int MAXN(110);
const int MAXM(110);
typedef pair<int,int> P;

int n,m,k;
char s[MAXN];
bool a[MAXN],b[MAXN];
int c1[MAXN],c2[MAXN][2];
int x1[MAXN],y1[MAXN],x2[MAXN],y2[MAXN];
bool common;
bool vis[MAXN][2];
int ansa[MAXN],ansb[MAXN];
P pre[MAXN][MAXN][2];

int ans(INF);

struct node
{
	int l;
	bool v;
	node(){}
	node(int l,bool v):l(l),v(v){}
};
vector<node>G[MAXM];

inline void add(int l,int r,bool v)
{
//	q[++tot]=node(l,r,f);
	printf("%d %d %d\n",l,r,v);
	G[r].push_back(node(l,v));
	if(l==r&&vis[l][v^1]) common=true; 
	if(l==r) vis[l][v]=true;
	return;
}

int f[MAXN][MAXN][2];

inline void do1(int i,int j,int k)
{
	
	if(f[i+1][i][k^1]!=-1)
	{
		if(f[i+1][i][k^1]>f[i][j][k]+c2[i+1][k^1])
		{
			f[i+1][i][k^1]=f[i][j][k]+c2[i+1][k^1];
			pre[i+1][i][k^1]=make_pair(j,k);
		}
	}
	if(f[i+1][j][k]!=-1)
	{
		if(f[i+1][j][k]>f[i][j][k]+c2[i+1][k])
		{
			f[i+1][j][k]=f[i][j][k]+c2[i+1][k];
			pre[i+1][j][k]=make_pair(j,k);
		}
	}
	return;
}

inline void do2(int i,int j,int k)
{
	if(f[i+1][i][k^1]!=-1)
	{
		if(f[i+1][i][k^1]>f[i][j][k]+c2[i+1][k^1])
		{
			f[i+1][i][k^1]=f[i][j][k]+c2[i+1][k^1];
			pre[i+1][i][k^1]=make_pair(j,k);
		}
	}
	return;
}

inline void solve(int res)
{
	if(ans<res) return;
	
	common=false;
	rep(i,1,m) G[i].clear();
	memset(f,0x3f,sizeof(f)),Clear(vis);
	
	puts("begina:");
	rep(i,1,n) printf("%d ",a[i]);
	puts("");
	printf("res:%d\n",res);
	rep(i,1,k)
	{
		int A=x1[i],B=y1[i],C=x2[i],D=y2[i];
		if(A==C)
		{
			if(B<D&&!a[A]) return;
			if(B>D&&a[A]) return;
			continue;
		}
		if(B==D)
		{
			if(A<C) add(B,B,true);
			else add(B,B,false);
			continue;
		}
		if(B<D)
		{
			if(a[A]&&a[C]) add(B,D,true);
			else if(a[A]&&!a[C]) add(D,D,true);
			else if(!a[A]&&a[C]) add(B,B,true);
			else
			{
				bool flag=false;
				rep(j,A+1,C-1) if(a[j]) {flag=true;break;}
				if(!flag) return;
				add(B,B,true),add(D,D,true);
			}
		}
		else
		{
			Swap(A,C),Swap(B,D);
			if(a[A]&&a[C])
			{
				bool flag=false;
				rep(j,C+1,A-1) if(!a[j]) {flag=false;break;}
				if(!flag) return;
				add(B,B,true),add(D,D,true);
			}
			else if(a[A]&&!a[C]) add(B,B,true);
			else if(!a[A]&&a[C]) add(D,D,true);
			else if(!a[A]&&!a[C]) add(B,D,true);
		}
	}
	if(common) return;
	
	//f[i][j][k] 考虑了前i个，第i个是j，上一个j^1的位置是k 
	
	
	rep(i,2,m)
		for(auto x:G[i])
			if(x.l==i) f[i][i-1][!x.v]=-1;
	if(G[1].empty()) f[1][0][0]=c2[1][0],f[1][0][1]=c2[1][1];
	else f[1][0][G[1][0].v]=c2[1][G[1][0].v];
	
	
//	yes;
	
	rep(i,1,m-1)
	{
		rep(j,0,i-1)
		{
			rep(k,0,1) if(f[i][j][k]!=0x3f3f3f3f&&f[i][j][k]!=-1)
			{
				if(G[i+1].empty())
				{
					do1(i,j,k);
				}
				for(auto x:G[i+1])
				{
					int l=x.l;bool v=x.v;
					if(l==i+1) continue;
					if(j>=l)
					{
						do1(i,j,k);
					}
					else
					{
						if(k==v)
						{
							do1(i,j,k);
						}
						else
						{
							do2(i,j,k);
						}
					}
				}
			}
		}
	}
	
//	printf("special:%d\n",f[2][0][0]);
	rep(i,0,m-1) printf("%d %d\n",f[m][i][0],f[m][i][1]);
	
	rep(i,0,m-1)
	{
		if(f[m][i][0]!=-1)
		{
			if(ans>res+f[m][i][0])
			{
				ans=res+f[m][i][0];
				rep(j,1,n) ansa[j]=a[j];
				ansb[m]=0;
				int now=m,j=i,k=0;
				while(now!=1)
				{
					P p=pre[now][j][k];
					j=p.first,k=p.second;
					now=now-1;
					ansb[now]=k;
				}
			}
		}
		if(f[m][i][1]!=-1)
		{
			if(ans>res+f[m][i][1])
			{
				ans=res+f[m][i][1];
				rep(j,1,m) ansa[j]=a[j];
				ansb[m]=1;
				int now=m,j=i,k=1;
				while(now!=1)
				{
					P p=pre[now][j][k];
					j=p.first,k=p.second;
					now=now-1;
					ansb[now]=k;
				}
			}
		}
	}
	return; 
}

inline void dfs(int i,int res)
{
	if(i>n)
	{
//		printf("res:%d\n",res);
		solve(res);
		return;
	}
	dfs(i+1,res);
	a[i]^=1;
	dfs(i+1,res+c1[i]);
	a[i]^=1;
	return;
}

int main()
{
	n=read(),m=read();
	scanf("%s",s+1);
	rep(i,1,n) if(s[i]=='E') a[i]=true;
	scanf("%s",s+1);
	rep(i,1,m) if(s[i]=='S') b[i]=true;
	rep(i,1,n) c1[i]=read();
	rep(i,1,m)
	{
		int x=read();
		if(s[i]=='S') c2[i][0]=x;
		else c2[i][1]=x;
	}
	k=read();
	rep(i,1,k)
	{
		x1[i]=read(),y1[i]=read(),x2[i]=read(),y2[i]=read();
		if(x1[i]>x2[i]) Swap(x1[i],x2[i]),Swap(y1[i],y2[i]);
	}
	dfs(1,0);
	if(ans!=INF)
	{
		puts("possible");
		printf("%d\n",ans);
		rep(i,1,n) if(ansa[i]) putchar('E');else putchar('W');
		putchar('\n');
		rep(i,1,m) if(ansb[i]) putchar('S');else putchar('N');
	}
	else puts("impossible");
	return 0;
}
/*
5 10
WWWWE
SSNSSSNNSS
8385 9667 1660 7509 6047
8320 1501 570 9157 1517 1022 4606 3914 816 9760
8
5 1 1 2
3 2 1 8
2 9 1 3
4 2 5 4
2 9 2 5
1 8 3 6
2 10 2 9
5 1 1 2

possible
10670
WWEEE
SNNSSSNNSS
*/