Editorial for Chiến trường Ô qua
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=30000; var t,i,j,re,n,lx,rx:longint; a,l,r:array[1..maxn] of longint; procedure pr; var i,j:longint; begin l[1]:=1; r[n]:=n; for i:=2 to n do if a[i]>a[i-1] then l[i]:=i else begin for j:=l[i-1] downto 1 do if a[j]<a[i] then break; if a[j]<a[i] then l[i]:=j+1 else l[i]:=j; end; for i:=n-1 downto 1 do if a[i]>a[i+1] then r[i]:=i else begin for j:=r[i+1] to n do if a[j]<a[i] then break; if a[j]<a[i] then r[i]:=j-1 else r[i]:=j; end; re:=0; for i:=1 to n do begin j:=a[i]*(r[i]-l[i]+1); if j>=re then begin if j>re then begin re:=j; lx:=l[i]; rx:=r[i]; end else begin if l[i]<lx then begin lx:=l[i]; rx:=r[i]; end; end; end; end; end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); readln(t); for i:=1 to t do begin readln(n); for j:=1 to n do read(a[j]); readln; pr; writeln(re,' ',lx,' ',rx); end; close(input); close(output); end.
Code mẫu của happyboy99x
#include<cstdio> #include<stack> using namespace std; int n, a[33333], l[33333], r[33333]; void testcase() { scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", a+i); stack<int> st; l[0] = 0; for(int i = 1; i < n; ++i) if(a[i] > a[i-1]) l[i] = i, st.push(i-1); else { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); l[i] = st.empty() ? 0 : st.top() + 1; } st = stack<int>(); r[n-1] = n-1; for(int i = n-2; i >= 0; --i) if(a[i] > a[i+1]) r[i] = i, st.push(i+1); else { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); r[i] = st.empty() ? n-1 : st.top() - 1; } int res = 0; for(int i = 1; i < n; ++i) if((r[i] - l[i] + 1) * a[i] > (r[res] - l[res] + 1) * a[res]) res = i; printf("%d %d %d\n", (r[res] - l[res] + 1) * a[res], l[res] + 1, r[res] + 1); } int main() { int tc; scanf("%d", &tc); while(tc--) testcase(); return 0; }
Code mẫu của ladpro98
program kagain; uses math; const fi=''; fo=''; var a:array[0..30001] of longint; left,right:array[0..30001] of longint; area,dau,cuoi,n,t,i,j:longint; inp,oup:text; procedure openFile; begin assign(inp,fi); reset(inp); assign(oup,fo); rewrite(oup); end; procedure closeFile; begin close(inp); close(oup); end; procedure process; var i,t:longint; begin area:=0; for i:=1 to n do begin left[i]:=0; right[i]:=0; end; left[1]:=0; for i:=2 to n do begin t:=i-1; while a[t]>=a[i] do t:=left[t]; left[i]:=t; end; right[n]:=n+1; for i:=n-1 downto 1 do begin t:=i+1; while a[t]>=a[i] do t:=right[t]; right[i]:=t; end; for i:=1 to n do begin if area<((right[i]-left[i]-1)*a[i]) then begin area:=(right[i]-left[i]-1)*a[i]; dau:=left[i]+1; cuoi:=right[i]-1; end; end; end; begin openFile; readln(inp,t); for i:=1 to t do begin readln(inp,n); for j:=1 to n do read(inp,a[j]); process; writeln(oup,area,' ',dau,' ',cuoi); end; close(oup); end.
Code mẫu của RR
var a,left,right,stack:array[0..30111] of longint; tmp,i,n,test,top:longint; lr,lu,lv:longint; begin read(test); a[0]:=0; for test:=1 to test do begin read(n); for i:=1 to n do read(a[i]); lr:=0; top:=0; stack[0]:=0; for i:=1 to n do begin while (top>0) and (a[stack[top]]>=a[i]) do dec(top); left[i]:=stack[top]+1; inc(top); stack[top]:=i; end; top:=0; stack[0]:=n+1; a[n+1]:=a[0]; for i:=n downto 1 do begin while (top>0) and (a[stack[top]]>=a[i]) do dec(top); right[i]:=stack[top]-1; inc(top); stack[top]:=i; end; for i:=1 to n do begin tmp:=a[i]*(right[i]-left[i]+1); if (tmp>lr) or ((tmp=lr) and (left[i]<lu)) then begin lr:=tmp; lu:=left[i]; lv:=right[i]; end; end; writeln(lr,' ',lu,' ',lv); end; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> main() { long T,n,a[30001],left[30001],right[30001],r[30002],l[30002]; scanf("%ld",&T); for(long i=1;i<=T;i++) { long max=0,x,y; scanf("%ld",&n); for(long j=1;j<=n;j++) scanf("%ld",&a[j]); long u=1; r[1]=1; while(r[u]!=n+1) { long t=r[u]+1; if(a[t]<a[r[u]]) { for(long j=u;j>=1;j--) { if(a[t]<a[r[j]]) { right[r[j]]=t-1; u--; } else break; } u++; r[u]=t; } else if(t==n) { for(long j=u;j>=1;j--) right[r[j]]=n; break; } else { u++; r[u]=t; } } right[n]=n; u=1; l[1]=n; //printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]); while(l[u]!=0) { long t=l[u]-1; if(a[t]<a[l[u]]) { for(long j=u;j>=1;j--) { if(a[t]<a[l[j]]) { left[l[j]]=t+1; u--; } else break; } u++; l[u]=t; } else if(t==n) { for(long j=u;j>=1;j--) left[l[j]]=n; break; } else { u++; l[u]=t; } } left[1]=1; //printf("%ld %ld %ld",left[4],left[3],left[2]); for(long j=1;j<=n;j++) if(a[j]*(right[j]-left[j]+1)>max) { max=a[j]*(right[j]-left[j]+1); x=left[j]; y=right[j]; } printf("%ld %ld %ld\n",max,x,y); } //getch(); }
Code mẫu của ll931110
Program KAGAIN; Const input = ''; output = ''; Var a,left,right,stack: array[1..30000] of longint; t,n,i,top: longint; fi,fo: text; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure closefile; Begin Close(fo); Close(fi); End; Procedure push(x: longint); Begin inc(top); stack[top]:= x; End; Procedure solveleft; Var i: longint; Begin top:= 1; stack[top]:= 1; left[1]:= 1; For i:= 2 to n do Begin While (top > 0) and (a[stack[top]] >= a[i]) do dec(top); If top = 0 then left[i]:= 1 else left[i]:= stack[top] + 1; push(i); End; End; Procedure solveright; Var i: longint; Begin top:= 1; stack[top]:= n; right[n]:= n; For i:= n - 1 downto 1 do Begin While (top > 0) and (a[stack[top]] >= a[i]) do dec(top); If top = 0 then right[i]:= n else right[i]:= stack[top] - 1; push(i); End; End; Procedure solve; Var kq,i,x,y: longint; Begin Readln(fi, n); For i:= 1 to n do read(fi, a[i]); Readln(fi); solveleft; solveright; x:= left[1]; y:= right[1]; kq:= (y - x + 1) * a[1]; For i:= 2 to n do if kq < (right[i] - left[i] + 1) * a[i] then Begin kq:= (right[i] - left[i] + 1) * a[i]; x:= left[i]; y:= right[i]; End; Writeln(fo, kq, ' ', x, ' ', y); End; Begin openfile; Readln(fi, t); For i:= 1 to t do solve; closefile; End.
Code mẫu của skyvn97
#include<stdio.h> #define MAX 33333 int a[MAX]; int stack[MAX]; int l[MAX]; int r[MAX]; int size; int n,c,t; int max,f,e; void process(void) { scanf("%d",&n); int i; for (i=1;i<=n;i=i+1) scanf("%d",&a[i]); l[1]=1; size=0; for (i=2;i<=n;i=i+1) { if (a[i]>a[i-1]) { l[i]=i; size++; stack[size]=i-1; } else { while ((size>0) && (a[stack[size]]>=a[i])) size--; if (size==0) l[i]=1; else l[i]=stack[size]+1; } } r[n]=n; size=0; for (i=n-1;i>=1;i=i-1) { if (a[i]>a[i+1]) { r[i]=i; size++; stack[size]=i+1; } else { while ((size>0) && (a[stack[size]]>=a[i])) size--; if (size==0) r[i]=n; else r[i]=stack[size]-1; } } max=0; for (i=1;i<=n;i=i+1) { if (max==a[i]*(r[i]-l[i]+1)) { if (l[i]<f) { f=l[i]; e=r[i]; } } if (max<a[i]*(r[i]-l[i]+1)) { max=a[i]*(r[i]-l[i]+1); f=l[i]; e=r[i]; } } printf("%d %d %d\n",max,f,e); } int main(void) { scanf("%d",&t); for (c=1;c<=t;c=c+1) process(); }
Code mẫu của khuc_tuan
import java.io.*; import java.util.*; import static java.lang.Integer.parseInt; class MaxArmy { public String getMax(int[] a) { int[] l, r; int n = a.length; l=new int[n]; r=new int[n]; for(int i=0;i<n;++i) { int x = i-1; while( (x>=0) && (a[x]>=a[i]) ) x = l[x] ; l[i] = x; } for(int i=n-1;i>=0;--i) { int x = i+1; while( (x<n) && (a[x]>=a[i]) ) x = r[x] ; r[i] = x; } int max=-1, left=0, right=0; for(int i=0;i<n;++i) { int x = a[i]*(r[i]-l[i]-1); if(x>max) { max=x; left = l[i] + 2; right = r[i]; } else if(x==max && left>l[i]+2) { left = l[i] + 2; right = r[i]; } } return Integer.toString(max) + " " + Integer.toString(left) + " " + Integer.toString(right); } } public class Main{ public static void main(String[] Args) throws Exception { BufferedReader kb = new BufferedReader(new InputStreamReader(System.in)); int tt = parseInt(kb.readLine()); for(int i=0;i<tt;++i) { int n = parseInt(kb.readLine()); StringTokenizer st=new StringTokenizer(kb.readLine()); int[] a=new int[n]; for(int j=0;j<n;++j) a[j] = parseInt(st.nextToken()); System.out.println( new MaxArmy().getMax(a) ); } } }
Comments