Editorial for Dãy số vòng tròn


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 ladpro98

program ptqmseq;
uses    math;
const   fi='';
var     n:longint;
        a,b,min1,max1:array[0..1100000] of int64;
        inp:text;
        res,min2:int64;
procedure input;
var     i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);

        for i:=2 to n do
        begin
                inc(a[i],a[i-1]);
        end;
        min1[1]:=a[1];
        for i:=2 to n do
        begin
                min1[i]:=min(a[i],min1[i-1]);
        end;
        //min2:=a[2];
        //for i:=3 to n-1 do min2:=min(min2,a[i]);
        max1[n]:=a[n]-a[n-1];
        for i:=n-1 downto 1 do
        begin
                max1[i]:=max(a[n]-a[i-1],max1[i+1]);
        end;
end;

procedure process;
var     i:longint;
begin
        for i:=1 to n-1 do
        begin
                res:=max(res,a[i]+max1[i+2]);
                res:=max(res,a[i]-min1[i-1]);
        end;
        res:=max(res,a[n]-min1[1]);
end;

begin
        input;;
        res:=low(int64);
        process;
        write(res);
end.

Code mẫu của RR

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

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

const int MN = 2000111;

long long a[MN];

int main() {
    int n; scanf("%d", &n);
    int x;
    FOR(i,1,n) {
        scanf("%d", &x);
        a[i] = a[i-1] + x;
    }
    long long nn = 0, ln = 0;
    long long res = -1000111000111000111LL;
    FOR(i,1,n) {
        if (i < n) res = max(res, a[i] - nn);
        if (i > 1) res = max(res, a[n] - a[i-1] + ln);
        ln = max(ln, a[i-1]);
        nn = min(nn, a[i]);
    }
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#define oo 111111111
//#include<conio.h>


long long Min,Max,tong = 0,kq1 = -oo,kq2 = oo,x;
int n;

int main(){
     //freopen("PTQMSEQ.in","r",stdin); 
     bool check = false;
     scanf("%d",&n);
     scanf("%lld",&x);
     tong+=x;
     if(x>0) check = true;
     kq1 >?= tong;
     kq2 <?= tong;
     Min = x;
     Max = x;
     for(int i = 2;i<=n;i++)
     {
           scanf("%lld",&x);  
           if(x>0) check = true;
           tong+=x;
           kq1 >?= tong-Min;
           kq2 <?= tong-Max;
           Min <?= tong;
           Max >?= tong;
     }
     if(!check)
     printf("%lld\n",kq1);
     else{
     //printf("%lld %lld\n",kq1,kq2);
     kq1 >?= (tong-kq2);
     printf("%lld",kq1);
     }
    // getch();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.