1040A - Palindrome Dance - CodeForces Solution


greedy *1000

Please click on ads to support us..

Python Code:

n, a, b = map(int, input().split())
l = list(map(int, input().split()))
sum = 0
costs = {0: a, 1: b}

for i in range(len(l) // 2 if len(l) % 2 == 0 else (len(l) // 2) + 1):
    if l[i] == l[-(i+1)] and l[i] != 2:
        continue
    elif l[i] == l[-(i+1)] and l[i] == 2 and ( i == len(l) - (i+1) ):
        sum += min(a, b)
    elif l[i] == l[-(i+1)] and l[i] == 2:
        sum += 2*min(a, b)
    elif l[i] == 2 or l[-(i+1)] == 2:
        if l[i] == 2:
            sum += costs[l[-(i+1)]]
        else:
            sum += costs[l[i]]
    else:
        print(-1)
        exit()

print(sum)

C++ Code:

/** Read statement carefully **/

#include <bits/stdc++.h>
using namespace std;

#define     debug(x)            cout<< #x << " = " << x <<endl;
#define     ll                  long long
#define     yes                 cout<< "Yes" << "\n"
#define     no                  cout<< "No"  << "\n"
#define     eps                 1e-7
#define     pb                  push_back
#define     F                   first
#define     S                   second
#define     endl                "\n"

const int sz  = 2e5 + 5;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll  Inf = 1e18;
ll dr[] = {-1, +1, 0,   0};
ll dc[] = { 0,  0, +1, -1};


void solve() {
    ll n, aa, bb; cin>> n >> aa >> bb;
    ll ara[n];

    for(ll i = 0; i <n; i ++) cin>> ara[i];
    ll ans = 0;
    if(n % 2) {
        if(ara[n / 2] == 2) {
            ans = min(aa, bb);
        }
    }

    for(ll i = 0; i < n / 2; i ++) {
        if(ara[i] == ara[n - i - 1]) {
            if(ara[i] == 2)
                ans += 2 * min(aa, bb);
        }
        else {
            if((ara[i] ^ ara[n - i - 1]) == 1) {
                cout<< -1 << endl; return;
            }
            else {
                ll a;
                if(ara[i] ==  2) a = ara[n - i - 1];
                else a = ara[i];

                if(a == 0) ans += aa;
                else ans += bb;

            }
        }
    }

    cout<< ans << endl;
}


int32_t main()
{

    ios::sync_with_stdio(false);cin.tie(0);
    ll T; T = 1;
   // cin >> T;
    while(T --) {
        solve();

    }


    return 0;

}


Comments

Submit
0 Comments
More Questions

701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number
279. Perfect Squares
275. H-Index II
274. H-Index
260. Single Number III
240. Search a 2D Matrix II
238. Product of Array Except Self
229. Majority Element II
222. Count Complete Tree Nodes