NOI2023题解

到不了的彼岸，雨一直下。

方格染色

形式化题意

评测链接：https://www.luogu.com.cn/problem/P9478

给定一个 的棋盘，共 次操作：

1. 将某一行的一个区间染黑，即 ；
2. 将某一列的一个区间染黑，即 ；
3. 将左下到右上的某一斜线染黑，即 到 ，满足 。

求黑点个数，保证操作 不会超过 次。

数据范围：

这题有个 的 ，赚麻了，直接将操作 转化成 个单点修改，然后维护扫描线面积并即可，时间复杂度 。

然后考虑操作 只有 个，所以完全可以暴力，我们对每个操作 枚举操作 计算重复部分，然后加上剩余部分，可以用 std::set 或者 std::map 来去重，而对于剩余的操作 我们加上一个离散化后再做扫描线即可。

需要注意扫描线的离散化，以及能够合并的线段一定要合并（尤其是斜线），因为我们对于每一个操作统计的都是不同操作对其的贡献，所以不会统计同类贡献。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P9478 [NOI2023] 方格染色
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9478
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-20 19:34:39
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=1e6+10;
std::set<Pir>Hash;
int Case,N,M,Q,Idx,Cnt,Tot,Total;
int Val[MAXN];
struct Query
{
	int pos,l,r,val;
	bool operator<(const Query &x) const
	{ return pos<x.pos; }
}Qry[MAXN];
struct Line
{ int opt,x,l,r; }Bl[MAXN];
struct Cross
{ int lx,rx,ly,ry; }Cr[6];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{ int l,r,val,tag; }Tr[MAXN<<2];
inline void pushUp(int p)
{
	if(Tr[p].tag>0) Tr[p].val=Val[Tr[p].r+1]-Val[Tr[p].l];
	else Tr[p].val=Tr[ls].val+Tr[rs].val;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].val=Tr[p].tag=0;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
void modifyAdd(int p,int l,int r,int v)
{
	if(Val[Tr[p].r+1]<=l||r<=Val[Tr[p].l]) return ;
	if(l<=Val[Tr[p].l]&&Val[Tr[p].r+1]<=r)
	{
		Tr[p].tag+=v;
		return pushUp(p);
	}
	modifyAdd(ls,l,r,v),modifyAdd(rs,l,r,v);
	pushUp(p);
}
bool Del[6];
int main()
{
	// freopen("color.in","r",stdin);
	// freopen("color.out","w",stdout);
	read(Case,N,M,Q);
	for(int i=1,opt,lx,rx,ly,ry;i<=Q;++i)
	{
		read(opt,lx,ly,rx,ry);
		if(opt<=2)
		{
			Qry[++Idx]=(Query){ly,lx,rx+1,1};
			Qry[++Idx]=(Query){ry+1,lx,rx+1,-1};
			Val[++Total]=lx,Val[++Total]=rx+1;
			if(opt==1) Bl[++Cnt]=(Line){1,ly,lx,rx};
			else Bl[++Cnt]=(Line){2,lx,ly,ry};
		}
		else Cr[++Tot]=(Cross){lx,rx,ly,ry};
	}
	std::sort(Qry+1,Qry+Idx+1);
	std::sort(Val+1,Val+Total+1);
	Total=std::unique(Val+1,Val+Total+1)-Val-1;
	build(1,1,Total-1);
	ll ans=0;
	for(int i=1;i<=Idx;++i)
	{
		ans+=1ll*Tr[1].val*(Qry[i].pos-Qry[i-1].pos);
		modifyAdd(1,Qry[i].l,Qry[i].r,Qry[i].val);
	}
	for(int i=1;i<=Tot;++i)
		for(int j=i+1;j<=Tot;++j)
		{
			if(Del[i]||Del[j]) continue;
			auto a=Cr[i],b=Cr[j];
			if(a.ly-a.lx==b.ly-b.lx)
				if(std::max(a.lx,b.lx)<=std::min(a.rx,b.rx))
				{
					checkMin(Cr[i].lx,Cr[j].lx),
					checkMax(Cr[i].rx,Cr[j].rx),
					checkMin(Cr[i].ly,Cr[j].ly),
					checkMax(Cr[i].ry,Cr[j].ry);
					Del[j]=1;
				}
		}
	for(int i=1;i<=Tot;++i)
	{
		if(Del[i]) continue;
		auto c=Cr[i];
		int res=0;Hash.clear();
		for(int j=1;j<=Cnt;++j)
		{
			auto b=Bl[j];
			if(b.opt==1)
			{
				if(c.ly<=b.x&&b.x<=c.ry)
					if(b.l<=(c.lx+b.x-c.ly)&&(c.lx+b.x-c.ly)<=b.r)
						if(Hash.find(Mkr(c.lx+b.x-c.ly,b.x))==Hash.end())
						{
							Hash.insert(Mkr(c.lx+b.x-c.ly,b.x));
							++res;
						}
			}
			else
			{
				if(c.lx<=b.x&&b.x<=c.rx)
					if(b.l<=(c.ly+b.x-c.lx)&&(c.ly+b.x-c.lx)<=b.r)
						if(Hash.find(Mkr(b.x,c.ly+b.x-c.lx))==Hash.end())
						{
							Hash.insert(Mkr(b.x,c.ly+b.x-c.lx));
							++res;
						}
			}
		}
		ans+=c.rx-c.lx+1-res;
	}
	write(ans,'\n');
	return 0;
}
/*

*/

---

桂花树

---

深搜

---

贸易

形式化题意

评测链接：https://www.luogu.com.cn/problem/P9481

存在一个有 个结点的完全二叉树，子结点对父结点连有单向边，具体而言，就是存在边 ，边带权。除此之外，存在 条额外的单向边，一定是从祖先结点连向子结点。设 表示 到 的最短路，无法到达则 ，求：

$$\sum_{u=1}^{2^n-1}\sum_{v=1}^{2^n-1}\mathrm{dist}(u,v)$$

对 取模。

数据范围：

感觉和前两天做的某道题有点相似，但这道题显然不能那样做，毕竟图的形态不同。但我们还是可以考虑拆贡献。将 拆分为 。

对于 ，此时只会从子结点向上走，所以最优策略下不会存在环，所以最短路直接就是一直往父结点跳的边权和。这一部分可以直接进行统计。

对于 ，我们考虑通过 的形式进行维护，记 表示从 的深度为 的祖先 到 的最短路。问题在于若干二类边（从祖先结点到子结点的边）会互相影响，但更新形式都形如 的 ，然后若干转移的形式与 相似，所以我们枚举中转点后枚举起点终点即可。

时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P9481 [NOI2023] 贸易
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9481
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// Written by: Eternity
// Time: 2023-08-20 19:33:11
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1<<18|10,MAXM=20,Mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M;
struct G
{ int next,to,val; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
int Log2[MAXN],Siz[MAXN];
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
inline int getLca(int u,int v)
{
	while(u!=v) u>>=1,v>>=1;
	return u;
}
ll Dist[MAXN],Sum[MAXN],val[MAXN],f[MAXN][MAXM],ans;
bool Vis[MAXN];
struct Node
{
	int pos;ll val;
	Node(int _pos=0,ll _val=0):pos(_pos),val(_val){}
	bool operator<(const Node &x) const
	{ return val>x.val; }
};
inline void Dijkstra(int st)
{
	std::memset(Dist,0x3f,sizeof(Dist));
	Dist[st]=0;
	std::priority_queue<Node>Pq;
	Pq.push(Node(st,Dist[st]));
	while(!Pq.empty())
	{
		int u=Pq.top().pos;Pq.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(checkMin(Dist[v],Dist[u]+Edge[e].val)) Pq.push(Node(v,Dist[v]));
		}
	}
}
inline void init()
{
	for(int i=2;i<(1<<N);++i) Log2[i]=Log2[i>>1]+1;
	for(int i=1;i<(1<<N);++i) Siz[i]=qPow(2,N-Log2[i])-1;
	std::memset(f,0x3f,sizeof(f));
}
inline ll calc(int x){ return (Sum[x]+(ll)Siz[x]*val[x]); }
int main()
{
	// freopen("trade.in","r",stdin);
	// freopen("trade.out","w",stdout);
	read(N,M);
	init();
	for(int i=2;i<(1<<N);++i) read(val[i]),Dist[i]=Dist[i>>1]+val[i];
	for(int i=(1<<N)-1;i>1;--i) Sum[i>>1]=(Sum[i>>1]+calc(i));
	for(int i=1,u,v,w;i<=M;++i)
	{
		read(u,v,w);
		for(int x=v;x>u;x>>=1)
			for(int y=x>>1;y>=u;y>>=1)
				checkMin(f[x][Log2[y]],Dist[v]+Dist[y]-Dist[x]-Dist[u]+w);
	}
	for(int u=1;u<(1<<N);++u)
		for(int i=Log2[u]-1,v=u>>1;v;--i,v>>=1)
			for(int j=i-1;~j;--j)
				checkMin(f[u][j],f[u][i]+f[v][j]);
	for(int u=(1<<N)-1;u;--u)
	{
		ans=(ans+Sum[u])%Mod;
		for(int i=Log2[u]-1,v=u;v>1;--i,v>>=1)
			if(f[u][i]!=INF) ans=(ans+f[u][i]%Mod*(Siz[v]+1)+calc(v^1))%Mod;
	}
	write(ans,'\n');
	return 0;
}
/*

*/

---

字符串

形式化题意

评测链接：https://www.luogu.com.cn/problem/P9482

给定一个长度为 的字符串。共 次询问，每次询问二元组 ，求有多少个 满足 是 ，注意 是 的翻转。

数据范围：

佳老师 爆踩标算，我也来逝世。

我们用 表示 是否合法，所以答案就是 。这个是可以通过递推出来的：

$$f(i,l)= \begin{cases} 0&,s[i]>s[i+2l-1]\\ 1&,s[i]<s[i+2l-1]\\ f(i+1,l-1)&,s[i]=s[i+2l-1] \end{cases}$$

那显然我们把 全部求出来这道题就结束了，考虑暴力求铁定寄，所以我们离线通过扫描线维护，发现从 向 转移时，相当于将 左移后求出 位的答案。

那么这个只有 还支持位运算的数据结构哪里找！！！那么，大名鼎鼎的 std::bitset！！！所以就可以做到 ，然后我们适当卡常，压位用 unsigned long long 手写 std::bitset，然后奇偶位独立处理。

AC Code

// ----- Eternally question-----
// Problem: P9482 [NOI2023] 字符串
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9482
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-21 08:03:10
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define popcount(x) __builtin_popcountll(x)
const int MAXN=1e5+10,MAXM=1e3+10,Omega=64;
int Case,Test,N,Q,Bit,ans[MAXN];
char Str[MAXN];
std::vector<Pir>vec[MAXN];
struct Bitset
{
	ull bit[MAXM];
	inline void clear(){ std::memset(bit,0,sizeof(bit)); }
	inline void set(int x){ bit[x>>6]|=1ull<<(x&63); }
	inline void move()
	{
		int p=0;
		for(int i=0;i<=Bit;++i)
		{
			int c=bit[i]>>63&1;
			bit[i]=bit[i]<<1|p;
			p=c;
		}
	}
	inline int count(int k)
	{
		++k;
		int p=k>>6,q=k&63,r=0;
		for(int i=0;i<p;++i) r+=popcount(bit[i]);
		r+=popcount(bit[p]&((1ull<<q)-1));
		return r;
	}
}A[2][27],B[2][27],f;
inline void And(Bitset &p,Bitset &q,int k)
{
	int u=k>>6,v=k&63;
	for(int i=0;i<=Bit;++i)
	{
		if(i+u>800) break;
		ull nw=(q.bit[i+u]>>v);
		if(v) nw|=(q.bit[i+u+1]<<(64-v));
		p.bit[i]&=~nw;
	}
}
inline void Or(Bitset &p,Bitset &q,int k)
{
	int u=k>>6,v=k&63;
	for(int i=0;i<=Bit;++i)
	{
		if(i+u>800) break;
		ull nw=(q.bit[i+u]>>v);
		if(v) nw|=(q.bit[i+u+1]<<(64-v));
		p.bit[i]|=nw;
	}
}
inline void solve()
{
	read(N,Q),scanf("%s",Str+1);
	for(int i=1;i<=N;++i) vec[i].clear();
	for(int i=1,ql,qr;i<=Q;++i) read(ql,qr),vec[ql].emplace_back(qr,i);
	f.clear();
	for(int o:{0,1}) for(int c=0;c<26;++c) A[o][c].clear(),B[o][c].clear();
	int tmp[]={50000,50000};
	for(int i=N-1;i;--i)
	{
		int o=i&1,c=Str[i+1]-'a';
		Bit=(N-i+1)>>7;f.move();--tmp[o];
		for(int j=0;j<c;++j) A[o][j].set(tmp[o]+1);
		for(int j=c+1;j<26;++j) B[o][j].set(tmp[o]+1);
		c=Str[i]-'a';
		if(c>0) And(f,B[o][c],tmp[o]);
		if(c<25) Or(f,A[o][c],tmp[o]);
		for(auto q:vec[i]) ans[q.sec]=f.count(q.fir);
	}
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Case,Test);
	while(Test--) solve();
	return 0;
}
/*

*/

---

合并书本

形式化题意

评测链接：https://www.luogu.com.cn/problem/P9483

给定 个元素，每个元素的贡献由一个二元组 组成，将 元素合并到 中产生的代价为 ，而合并之后的元素为 。初始 ， 给出。求只剩下一个元素的最小代价。多测。

数据范围：

场上在想有没有什么 的区间 暴力，结果发现 的范围……看来是想简单了。

考虑 重构树的过程，我们将原本的每摞书视作一棵树的叶结点，每合并两摞书就新建一个非叶结点将两个结点连接起来，那么最后操作序列会形成一棵树，结点定义：

• 叶结点，初始的一摞书。
• 非叶结点，表示将左儿子表示的书堆到右儿子上形成新的一摞书。

其中 的质量为子树叶结点质量和，磨损度为 。最终贡献由 部分组成，其一为所有左儿子质量和，其二为非根的磨损度和。

设 表示叶结点 到根结点的路径上作为左儿子的次数，则第一部分的代价为 。

但显然，在 未知的情况下，重构树的状态不确定，所以我们要选取求解方式，但考虑到 很小，所以我们可以求出所有可能作为最优解的结构可重集，而求解则可以自下而上和自上而下两种方法。

考虑当前存在一棵子树 的可重集为 ，最大深度为 ，现在要将 放入一棵可重集为 ，最大深度为 的子树 上。

如果自下而上，那么得到的子树形如 。显然这是一个可接受范围的状态，所以可以尝试 。

令 表示可重集状态为 ，最大深度 的最小磨损，然后模拟上述过程进行转移，但 的状态过多，需要考虑将 内部排序后去重，且剪枝所有 的 ，因为这样合并一定不优。

然后考虑自上而下的转移，也就是对叶结点进行分裂。在当前可重集 中构造出满足 的点。而 是上一次分裂操作后根结点的最大深度。我们首先选择 中靠前的较小元素分裂，将 分裂得到 ，得到可重集 。

但显然分裂后的权值不太好计算，所以我们考虑反向来做，将分裂视作反向删除，直到把一棵树删完，此时我们直接构造好重构树，然后从 的结点开始将其删除，此时 为最后分裂的点。然后重复该操作直到只剩下根结点。

我们要求每次操作后除了根结点与叶结点之外的所有结点的 都要被改变，所以我们钦定让所有上次被分裂出的结点至少有一个在这次也被分裂，而之前的叶结点则不做要求。

那么我们每次都会有 个结点的 改变，从 ，那么磨损值从 变成了 。那么此时的状态可以直接设为 ，然后枚举分裂元素即可。

此时的剪枝有两种，我们可以钦定一个阈值 ，答案不会超过 ，所以我们可以扔掉所有 的状态，可以取 ，然后我们令分裂的叶结点数量单调不降，设定分裂叶结点的下限，可以大量减少冗余状态。

AC Code

// ----- Eternally question-----
// Problem: P9483 [NOI2023] 合并书本
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9483
// Memory Limit: 512 MB
// Time Limit: 1500 ms
// Written by: Eternity
// Time: 2023-08-22 20:13:34
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=1e2+10,S=100;
const ll INF=0x3f3f3f3f3f3f3f3f;
int Test,N,val[MAXN];
std::map<std::vector<int>,std::pair<ll,int>>Mp[MAXN];
int main()
{
	// freopen("book.in","r",stdin);
	// freopen("book.out","w",stdout);
	read(Test);
	Mp[1][std::vector<int>(1)]=Mkr(0,1);
	for(int i=1;i<S;++i)
		for(auto j=Mp[i].begin();j!=Mp[i].end();j++)
		{
			std::vector<int>vec=j->fir,vec2=vec;
			for(int k=1;k<=i;++k)
			{
				int siz=i+k;
				if(siz>S) break;
				int v=vec[k-1]+1;
				vec2.insert(std::lower_bound(vec2.begin(),vec2.end(),v),v);
				if(k>=j->sec.sec)
				{
					std::pair<ll,int>pr(j->sec.fir*2+(siz-2),k);
					if(pr.fir>INF) break;
					if(Mp[siz].find(vec2)==Mp[siz].end()) Mp[siz][vec2]=pr;
					else
					{
						std::pair<ll,int>&p=Mp[siz][vec2];
						checkMin(p.fir,pr.fir),checkMin(p.sec,pr.sec);
					}
				}
			}
		}
	while(Test--)
	{
		read(N);
		ll ans=INF;
		for(int i=1;i<=N;++i) read(val[i]);
		std::sort(val+1,val+N+1);
		for(auto j=Mp[N].begin();j!=Mp[N].end();j++)
		{
			ll cur_ans=j->sec.fir;
			std::vector<int>vec=j->fir;
			for(int k=1;k<=N;++k) cur_ans+=(ll)val[k]*vec[N-k];
			checkMin(ans,cur_ans);
		}
		write(ans,'\n');
	}
	return 0;
}
/*

*/

---