fork download
copy 
  1.  
  2. import java.util.*;
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.StringTokenizer;
  7.  
  8. class main
  9. {
  10. 	public static void main(String args[]) throws Exception
  11. 	{
  12. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13. 		int T = Integer.parseInt(br.readLine());
  14. 		int N,start,end,i,left_sum,right_sum,left_neg1,left_neg2,right_neg1,right_neg2,ans,sum,top,bottom;
  15. 		String s[];
  16. 		int A[] = new int[200005];
  17. 		while(T--!=0)
  18. 		{
  19.             left_neg2 = left_neg1 = right_neg2 = right_neg1 = sum = left_sum = right_sum = 0;
  20.             N = Integer.parseInt(br.readLine());
  21.             s = br.readLine().split(" ");
  22.             for (i=1;i<=N;++i)
  23.                 A[i] = Integer.parseInt(s[i-1]);
  24.             s = br.readLine().split(" ");
  25.             start = Integer.parseInt(s[0]);
  26.             end = Integer.parseInt(s[1]);
  27.             //Summing the left and right parts
  28.             for( i=start; true; ++i)
  29.             {
  30.                 if(i>N)
  31.                     i%=N;
  32.                 if(i==end)
  33.                     break;
  34.                 left_sum += A[i];
  35.             }
  36.             for( i=(start-1); true; --i)
  37.             {
  38.                 if(i==0)
  39.                     i=N;
  40.                 right_sum += A[i];
  41.                 if(i==end)
  42.                     break;
  43.             }
  44.             //System.out.println("left_sum: " + left_sum);
  45.             //System.out.println("right_sum: " + right_sum);
  46.             top = bottom = sum = 0;
  47.             // Taking manimum negative values for left part
  48.             for( i=start; true; ++i)
  49.             {
  50.                 if(i>N)
  51.                     i%=N;
  52.                 if(i==end)
  53.                     break;
  54.                 sum += A[i];
  55.                 if(left_neg1>sum)
  56.                 {
  57.                     top = i;
  58.                     left_neg1 = sum;
  59.                 }
  60.             }
  61.             sum = 0;
  62.             for( i=(end-1); true; --i)
  63.             {
  64.                 if(i==0)
  65.                     i=N;
  66.                 sum += A[i];
  67.                 if(left_neg2>sum)
  68.                 {
  69.                     bottom = i;
  70.                     left_neg2 = sum;
  71.                 }
  72.                 if(i==start )
  73.                     break;
  74.             }
  75.             //System.out.println("top: " + top);
  76.             //System.out.println("bottom: " + bottom);
  77.             if(left_neg1 < left_neg2)
  78.             {
  79.                 left_neg2 = sum = 0;
  80.                 for( i=(end-1); true; --i)
  81.                 {
  82.                     if(i==0)
  83.                         i=N;
  84.                     sum += A[i];
  85.                     if(left_neg2>sum)
  86.                         left_neg2 = sum;
  87.                     if(i==start || i==((top+1)==N+1 ? 1 : (top + 1)) )
  88.                         break;
  89.                 }   
  90.             }
  91.             else
  92.             {
  93.                 left_neg1 = sum = 0;
  94.                 for( i=start; true; ++i)
  95.                 {
  96.                     if(i>N)
  97.                         i%=N;
  98.                     if(i==end || i==bottom)
  99.                         break;
  100.                     sum += A[i];
  101.                     if(left_neg1>sum)
  102.                         left_neg1 = sum;
  103.                 }   
  104.             }
  105.             //System.out.println("left_neg1: " + left_neg1);
  106.             //System.out.println("left_neg2: " + left_neg2);
  107.             ans = right_sum + left_neg1*2 + left_neg2*2;
  108.             //Taking minimum negative values for right part
  109.             top = bottom = sum = 0;
  110.             for( i=(start-1); true; --i)
  111.             {
  112.                 if(i==0)
  113.                     i=N;
  114.                 sum += A[i];
  115.                 if(right_neg1>sum)
  116.                 {
  117.                     top = i;
  118.                     right_neg1 = sum;
  119.                 }
  120.                 if(i==end)
  121.                     break;
  122.             }
  123.             sum = 0;
  124.             for( i=end; true; ++i)
  125.             {
  126.                 if(i>N)
  127.                     i%=N;
  128.                 if(i==start)
  129.                     break;
  130.                 sum += A[i];
  131.                 if(right_neg2>sum)
  132.                 {
  133.                     bottom = i;
  134.                     right_neg2 = sum;
  135.                 }
  136.             }
  137.             if(right_neg2 < right_neg1)
  138.             {
  139.                 right_neg1 = sum = 0;
  140.                 for( i=(start-1); true; --i)
  141.                 {
  142.                     if(i==0)
  143.                         i=N;
  144.                     sum += A[i];
  145.                     if(right_neg1>sum)
  146.                         right_neg1 = sum;
  147.                     if(i==end || i==((bottom + 1)==N+1 ? N : (bottom + 1)) )
  148.                         break;
  149.                 }   
  150.             }
  151.             else
  152.             {
  153.                 sum = right_neg2 = 0;
  154.                 for( i=end; true; ++i)
  155.                 {
  156.                     if(i>N)
  157.                         i%=N;
  158.                     if(i==start || i==(top))
  159.                         break;
  160.                     sum += A[i];
  161.                     if(right_neg2>sum)
  162.                         right_neg2 = sum;
  163.                 }
  164.             }
  165.             //System.out.println("right_neg1: " + right_neg1);
  166.             //System.out.println("right_neg2: " + right_neg2);
  167.             ans = Math.min(ans,left_sum + right_neg1*2 + right_neg2*2);
  168.             System.out.println(ans);
  169.         }
  170.     }
  171. }
Success #stdin #stdout 0.04s 320576KB
comments (?)
stdin
copy 
2
4
1 2 1 1
1 3
5
-5 100 100 100 2
1 5
stdout
copy 
2
-8
https://ideone.com/E5UsdS
language:
Java (12.0.1)
created:
7 years ago
visibility:
secret

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!