fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int intervalrecur(int *a,int start,int end,int *b,int m,int turn,int *pre)
  5. {
  6. 	int sol;
  7. 	if(turn==(m+1))
  8. 	{
  9. 		return 0;
  10. 	}
  11.  
  12. 	if((turn%2)==1)
  13. 	{
  14. 		sol=INT_MIN;
  15. 		for(int i=start,j=(start+b[turn]-1);j<end;i++,j++)
  16. 		{
  17.            sol=max(sol,intervalrecur(a,i,i+b[turn],b,m,turn+1,pre)+(pre[j]-pre[i-1]));
  18. 		}
  19. 	}
  20. 	else if((turn%2)==0)
  21. 	{
  22. 		sol=INT_MAX;
  23. 		for(int i=start,j=(start+b[turn]-1);j<end;i++,j++)
  24. 		{
  25.            sol=min(sol,intervalrecur(a,i,i+b[turn],b,m,turn+1,pre)-(pre[j]-pre[i-1]));
  26. 		}
  27. 	}
  28. 	return sol;
  29. }
  30.  
  31. int interval(int *a,int n,int *b,int m)
  32. {
  33.    int *pre=new int[n+1];
  34.    for(int i=0;i<=n;i++)
  35.    {
  36.    	  pre[i]=0;
  37.    }
  38.  
  39.    for(int i=1;i<=n;i++)
  40.    {
  41.    	  pre[i]=a[i]+pre[i-1];
  42.    }
  43.    int res=intervalrecur(a,1,n+1,b,m,1,pre);
  44.    return res; 
  45. }
  46.  
  47. int main()
  48. {
  49. 	int *a,*b,n,m,t;
  50. 	cout<<"t"<<"\n";
  51. 	cin>>t;
  52. 	while(t--)
  53. 	{
  54. 	 cout<<"n?"<<"\n";
  55. 	 cin>>n;
  56. 	 cout<<"m?"<<"\n";
  57. 	 cin>>m;
  58. 	 a=new int[n+1];
  59. 	 b=new int[m+1];
  60. 	 for(int i=1;i<=n;i++)
  61. 	 {
  62. 	 	cin>>a[i];
  63. 	 }
  64. 	 for(int i=1;i<=m;i++)
  65. 	 {
  66. 	 	cin>>b[i];
  67. 	 }
  68. 	 cout<<"optimal "<<interval(a,n,b,m)<<"\n";
  69. 	}
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
8 3
3 7 5 4 9 6 1 3
6 3 1
stdout
copy 
t
n?
m?
optimal 24
https://ideone.com/VYDHkF
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!