http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1483. 方格取数(王康宁)
时间限制:2.0s   内存限制:512.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  有一个N*N的方格表,每个格子里有一个数,第i行第j列的数等于Ai*Bj。小B从左上角走到右下角,每次只能向右或向下走一步,他会把经过的数累加起来,并使这个总和最小。他决定走T次,第i次从第Pi行第Qi列的点走到第Ri行第Si列的点,问每一次经过的数的最小总和。
输入格式
  第一行包括两个整数N, T,分别表示方格表的大小和询问数量。
  第二行N个整数,表示A1,A2, … ,AN在全部20个测试数据中,这一行的数是随机生成的。
  第三行N个整数,表示B1,B2, … ,BN在全部20个测试数据中,这一行的数是随机生成的。
  接下来T行,每行四个整数Pi,Qi,Ri,Si (Pi≤Ri,Qi≤Si),含义如题所述。
输出格式
  输出T行,每行一个整数,表示答案。
样例输入
3 4
1 2 3
2 3 4
1 1 1 1
1 3 1 3
1 1 3 3
1 1 3 1
样例输出
2
4
29
12
数据规模和约定
  对于20%的数据,N≤100,T≤100。
  对于50%的数据,N≤3000,T≤1000。
  对于70%的数据,N≤50000,T≤20000。
  对于100%的数据,N≤200000,T≤50000,1≤Ai, Bi≤106。保证询问合法,除样例外,所有的Ai, Bi均为随机生成的。