Editorial for Bán dừa


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.

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

#include <iostream>
#include <algorithm>
#include <cstdio>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define N 1000100
using namespace std;

int re,n,a[N],m,st[N],pos[N];

int main()
{
        int i;
        cin >> n;
        fr(i,1,n) scanf("%d",&a[i]);
        st[0]=-1; m=pos[0]=0; 
        fr(i,1,n)
                if (a[i]>st[m]) 
                {
                        st[++m]=a[i]; pos[m]=i;
                }
                else
                {
                        while (a[i]<=st[m]) 
                        {
                                re=max(re,(st[m]<=i-pos[m]+(a[i]==st[m])?st[m]:0));
                                m--;
                        }
                        st[++m]=a[i];
                }
        fr(i,1,m) re=max(re,(st[i]<=n-pos[i]+1?st[i]:0));
        cout << re << endl;
        return 0;
}

Code mẫu của ladpro98

program kagain;
uses    math;
const   fi='';
        fo='';
var     a:array[0..1000009] of longint;
        left,right:array[0..1000009] 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
                t:=right[i]-left[i]-1;
                if t>=a[i] then
                area:=max(area,a[i]);
        end;
end;

begin
        openFile;
                readln(inp,n);
                for j:=1 to n do readln(inp,a[j]);
                process;
                write(oup,area);
        close(oup);
end.

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>
#include <sstream>
#include <iomanip>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}

int n, st[1000111], a[1000111], l[1000111], r[1000111], top;

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    GN(n); FOR(i,1,n) GN(a[i]);
    top = 0; st[0] = 0;
    FOR(i,1,n) {
        while (top && a[st[top]] >= a[i]) top--;
        l[i] = st[top] + 1;
        st[++top] = i;
    }
    top = 0; st[0] = n+1;
    FORD(i,n,1) {
        while (top && a[st[top]] >= a[i]) top--;
        r[i] = st[top] - 1;
        st[++top] = i;
    }
    int res = 0, u;
    FOR(i,1,n) {
        u = r[i] - l[i] + 1;
        if (u < a[i]) continue;
        res = max(res, min(u, a[i]));
    }
    cout << res;
    return 0;
}

Code mẫu của hieult

#include <stdio.h>
#include <algorithm>
//#include <conio.h>
#define Max 1111111

using namespace std;

int T,n,k,a[Max],left[Max],right[Max],r[Max],l[Max];

int main()
{
  scanf("%d",&n);
  for(int j=1;j<=n;j++)
    scanf("%d",&a[j]);
  int u = 1;
  r[1] = 1;
  for(int i = 2;i<=n;i++){
       if(a[i]<a[r[u]]){
            while(a[i]<a[r[u]] && u>0){
                 right[r[u]] = i-1;
                 u--;
            }
       }
       r[++u] = i;
       if(i==n) for(int j = 1;j<=u;j++) right[r[j]] = n; 
  }

  u = 1;
  l[1] = n;
  for(int i = n-1;i>0;i--){
       if(a[i]<a[l[u]]){
            while(a[i]<a[l[u]] && u>0){
                 left[l[u]] = i+1;
                 u--;
            }
       }
       l[++u] = i;
       if(i==1) for(int j = 1;j<=u;j++) left[l[j]] = 1; 
  }

  //printf("%ld %ld %ld",left[4],left[3],left[2]);     
  int kq = 0;        
  for(int j=1;j<=n;j++)
    {
    if(a[j]<=right[j]-left[j]+1)
        kq = max(kq,min(right[j]-left[j]+1,a[j]));
    }
    printf("%d",kq);
//getch();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.