【CF888E】Maximum Subsequence(meet in the middle)
in The maximum Subsequence
2023-09-11 14:14:41 时间
【CF888E】Maximum Subsequence(meet in the middle)
题面
题解
把所有数分一下,然后\(meet\ in\ the\ middle\)做就好了。
一侧的数正序,另一侧倒序,这样子指针单调就做完了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAX 262222
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m,k,a[50],ans;
int s1[MAX],s2[MAX],t1,t2;
void dfs1(int x,int s)
{
if(x==k+1){s1[++t1]=s;return;}
dfs1(x+1,s);dfs1(x+1,(s+a[x])%m);
}
void dfs2(int x,int s)
{
if(x==n+1){s2[++t2]=s;return;}
dfs2(x+1,s);dfs2(x+1,(s+a[x])%m);
}
int main()
{
n=read();m=read();k=(n+1)/2;
for(int i=1;i<=n;++i)a[i]=read();
dfs1(1,0);dfs2(k+1,0);
sort(&s1[1],&s1[t1+1]);t1=unique(&s1[1],&s1[t1+1])-s1-1;
sort(&s2[1],&s2[t2+1]);t2=unique(&s2[1],&s2[t2+1])-s2-1;
for(int i=1;i<=t2;++i)s2[t2+i]=s2[i];
reverse(&s1[1],&s1[t1+1]);
for(int i=1,pos=1;i<=t1;++i)
{
while((s1[i]+s2[pos])%m<(s1[i]+s2[pos+1])%m)++pos;
ans=max(ans,(s1[i]+s2[pos])%m);
if(pos>t2)pos-=t2;
}
printf("%d\n",ans);
return 0;
}
相关文章
- Solr如何使用in语法查询
- Leetcode: Find All Duplicates in an Array
- Lintcode: Search Range in Binary Search Tree
- The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path
- AuthenticationException: The remote certificate is invalid because of errors in the certificate chain: UntrustedRoot
- How to check the Shutdown and Startup Log in Windows 11/10
- API Changes in Kentico 8
- 【CF809D】Hitchhiking in the Baltic States Splay
- OpenCV 程序报错 The application has requested the Runtime to terminate it in an unusual way.
- The last access date is not changed even after reading the file on Windows 7
- iOS 7 Pushing the Limits - Good & Bad Namings in Cocoa
- .NET错误The 'targetFramework' attribute in the <compilation> element of the Web.config file is used only to target version 4.0 and later of the .NET Framework
- JAVA-错误The type BookServiceImpl must implement the inherited abstract method
- UVa 11167 Monkeys in the Emei Mountain (最大流)
- Unity Tutorial : VR, Oculus Avatar and Grabbing Object setup IN 5 MINUTES
- flink error Hadoop is not in the classpath/dependencies.
- kafka producer batch expired TimeoutException: KAFKA-5621、KIP-91(Provide Intuitive User Timeouts in The Producer)、KAFKA-5886
- 【报错系列】[system] Do not nest other components in the text component, as there may be
- Unity 报错之 The same field name is serialized multiple times in the class or its parent class.
- Redefine:Change in the Changing World
- [LeetCode] 993. Cousins in Binary Tree 二叉树的表兄弟节点
- Preventing CSRF in Java web apps---reference
- Getting over the dangers of rm command in Linux---reference
- (转+原)ipp "No dlls were found in the Waterfall procedure"
- * resolve_conffiles: Existing conffile /etc/config/dhcp is different from the conffile in the new package. The new conffile will be placed at /etc/config/dhcp-opkg.