基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
佳佳有一个n*m的带权矩阵，她想从(1,1)出发走到(n,m)且只能往右往下移动，她能得到的娱乐值为所经过的位置的权的总和。
有一天，她被下了恶毒的诅咒，这个诅咒的作用是将她的娱乐值变为对p取模后的值，这让佳佳十分的不开心，因为她无法找到一条能使她得到最大娱乐值的路径了！
她发现这个问题实在是太困难了，既然这样，那就只在3*n的矩阵内进行游戏吧！
现在的问题是，在一个3*n的带权矩阵中，从(1,1)走到(3,n)，只能往右往下移动，问在模p意义下的移动过程中的权总和最大是多少。
样例解释：
移动的方案为“下下右”。
Input
单组测试数据 第一行两个数n(1<=n<=100000),p(1<=p<=1000000000)。 接下来3行，每行n个数，第i行第j列表示a[i][j]表示该点的权(0<=a[i][j]<p)。
Output
一个整数表示答案。
Input示例
2 3
2 2
2 2
0 1
Output示例
2
//以前竟然都没遇到过，set中竟然也有lower_bound(x) ,可以返回最小的大于等于 x 的迭代器
iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>= key的第一个元素。
iterator upper_bound( const key_type &key ):返回一个迭代器，指向键值> key的第一个元素。
先码住，这题，很容易想到 N^2 解法，然而只需要枚举其中一个拐点即可，另一部分二分得出
1 # include <cstdio> 2 # include <cstring> 3 # include <cstdlib> 4 # include <iostream> 5 # include <vector> 6 # include <queue> 7 # include <stack> 8 # include <map> 9 # include <bitset> 10 # include <sstream> 11 # include <set> 12 # include <cmath> 13 # include <algorithm> 14 using namespace std; 15 # define LL long long 16 # define pr pair 17 # define mkp make_pair 18 # define lowbit(x) ((x)&(-x)) 19 # define PI acos(-1.0) 20 # define INF 0x3f3f3f3f3f3f3f3f 21 # define eps 1e-8 22 # define MOD 1000000007 23 24 inline LL scan() { 25 LL x=0,f=1; char ch=getchar(); 26 while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} 27 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 28 return x*f; 29 } 30 inline void Out(int a) { 31 if(a<0) {putchar('-'); a=-a;} 32 if(a>=10) Out(a/10); 33 putchar(a%10+'0'); 34 } 35 # define MX 100005 36 /**************************/ 37 38 int n,p; 39 LL sum[3][MX]; 40 41 int main() 42 { 43 n=scan(); p=scan(); 44 for (int i=0;i<3;i++) 45 { 46 for (int j=1;j<=n;j++) 47 { 48 sum[i][j]=scan(); 49 sum[i][j]=(sum[i][j]+sum[i][j-1])%p; 50 } 51 } 52 int ans = (sum[0][1]+sum[1][1]+sum[1][n])%p; 53 set<int> s; 54 for (int i=1;i<=n;i++) 55 { 56 int tp = (sum[0][i]-sum[1][i-1]+p)%p; 57 s.insert( tp ); 58 int dat = (sum[1][i]+sum[2][n]-sum[2][i-1]+p)%p; 59 set<int>::iterator it = s.lower_bound(p-dat); 60 if (it!=s.end()) 61 { 62 if (it!=s.begin()) 63 { 64 it--; 65 ans = max((LL)ans,(*it+sum[1][i]+sum[2][n]-sum[2][i-1]+p)%p); 66 } 67 } 68 } 69 printf("%d ",ans); 70 return 0; 71 }