Slime



 

n რაოდენობის სლაიმი არის თითოეულ რიგში , თითო სლაიმს მინიჭებული აქვს მთელი რიცხვი(შეიძლება იყოს უარყოფითიც და 0-ც), თითოეულ სლაიმს შეუძლია რომ შეჭამოს მის გვერდით მყოფი სლაიმი. როცა სლაიმი ,რომლის მნიშვნელობაც არის x ჭამს სლაიმს რომლის მნიშვნელობაც არის y , შეჭმული სლაიმი ქრება და დარჩენილ სლაიმს ენიჭება მნიშვნელობა x-y .

სლაიმები ერთმანეთს ჭამენ ,სანამ არ დარჩება ერთი სლაიმი.

იპოვეთ მაქსიმალური შესაძლო მნიშვნელობა დარჩენილი სლაიმის.

 

შემომავალი მნიშვნელობები:

პირველად შემოდის მთელი რიცხვი n (1<=n<=500000) სლაიმების რაოდენობას აღნიშნავს.

შემდეგი ხაზი შეიცავს n მთელ რიცხვს, თითოელი აღნიშნავს სლაიმების მნიშვნელბებს (-10^9<=ai<=10^9) ai არის i სლაიმი.

 

გამომავალი მნიშვნელობა:

მხოლოდ ერთი მთელი რიცხვი-მაქსიმალური შესაძლო მნიშვლენობა დარჩენილი სლაიმის.

მაგალითი:

input

4

2 1 2 1

output

4

  1. მეორე ჭამს მესამეს და რჩება 2 -1 1
  2. მეორე ჭამს მესამეს ისევ და რჩება 2 -2
  3. პირველი ჭამს მეორეს და რჩება 4


 

თითოეული სლაიმი ან ემატება საბოლოო პასუხს ან აკლდება, ამიტომაც თითოეულ სლაიმს ვანიჭებთ + ან – იმის აღსანიშნავად თუ რამდენად დაემატება ან დააკლდება საბოლოო პასუხს მოცემული სლაიმი.

მთავარი გასაღები ამოცანის გადასაჭრელად არის ის რომ ყველა კომბინაცია (+/-)-ების არის მიღწევადი, გარდა ერთდროულად ყველა +-სა და ერთდროულად ყველა (-)-სა , რათქმა უნდა როცა n!=1-ს, როცა n=1-ს პასუხი თავად ეს სლაიმია.

თუ მოცემული მასივი შეიცავს რიცხვებს გვაქვს 0-სგან განსხვავებული დადებითი და უარყოფითი რიცხვები ,მაშინ ჩვენ შეგვიძლია მათი აბსოლიტური მნიშვნელობის პირდაპირ შეკრება(+ დავწერთ დადებითი რიცხვების წინ, და -ებს უარყოფითების წინ)

თუ მასივი შეიცავს მხოლოდ დადებით რიცხვებს, მაშინ – ვუწერთ მხოლოდ უმცირესი მნიშვნელობის მქონეს, და + დანარჩენს, იმავე ნაირად ვიქცევით უარყოფითი რიცხვებისთვის, + ვუწერთ უმცირესს (მოდულით). ალგორითმის სირთულე არის O(n)

კოდი:

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "n"
#define int long long

const int N=5e5+5;

int n, minval=1e9, ans=0;
int a[N];
bool checkpos=0, checkneg=0;

int32_t main()
{
        IOS;
        cin>>n;
        if(n==1)
        {
            int k;
            cin>>k;
            cout<<k;
            exit(0);
        }
        for(int i=1;i<=n;i++)
        {
                cin>>a[i];
                minval=min(abs(a[i]), minval);
                checkpos|=(a[i]>=0);
                checkneg|=(a[i]<=0);
                ans+=abs(a[i]);
        }
        if(checkpos&&checkneg)
                cout<<ans;
        else
                cout<<ans-2*minval;
        return 0;
}

 

ციკლში თანდათან კითხულობს სლაიმების მნიშვნელობებს, და თან მათ აბსოლიტურს უმატებს პასუხს და ასევე ინახავს მოდულით უმცირეს მნიშვნელობას, თუ (+/-) გვქონდა მაშინ პირდაპირ წერს პასუხს, თუ არადა აკლებს მინიმალურ მნიშვნელობას (2-ჯერ რადგან ერთხელ მიუმატა ციკლში).