1668B - Social Distance - CodeForces Solution


greedy math

Please click on ads to support us..

Python Code:




from __future__ import division, print_function

import os
import sys
import math
from io import BytesIO, IOBase
from heapq import heappush,heappop,heapify
from collections import defaultdict, Counter, deque

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")


def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = (ans * each) % mod
    return ans


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


def check_freq(x):
    freq = {}
    for c in set(x):
       freq[c] = x.count(c)
    return freq


def ii(): return int(input())
def si(): return input()
def mi(): return map(int, input().strip().split(" "))
def li(): return list(mi())
MAXX = 100000000


'''**************Solution is Here***********'''

def main():
    T = ii()
    for _ in range(T):
        n, k = li()
        soc = li()
        summ, maxx, minn = sum(soc), max(soc), min(soc)
        print("YES" if summ+maxx-minn+n <= k else "NO")


if __name__ == "__main__":
    main()


C++ Code:

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
#define int long long
#define el '\n'
#define all(x) x.begin(),x.end()
#define get_bit(n,i) ((n>>i)& 1LL)
#define clr(v , d) memset(v, d , sizeof(v))
#define gmx(x , y) x = max(x ,y)
#define gmn(x , y) x = min(x , y)
#define f first
#define s second
const int N = 1e5 + 5,  mod = 1e9 + 7 , OO = 2 * 1e9;
const ll OOLL = 6 * 1e18;
const double pi = 3.1415926535897932384;
// #ifndef ONLINE_JUDGE
// #include "debug.h"
// #else
// #define debug(...)
// #endif
ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void solve(){
	int n , m;
	cin >> n >> m;
	int ans = 0;
	vector < int > arr(n);
	for(auto &i : arr){
		cin >> i;
	}
	sort(all(arr) , greater < int >() );
	for(int i = 0;i < n - 1;++i){
		ans += arr[i] + 1;
	}
	int rem = m - (ans + 1);
	if(rem >= arr[0] and ((ans + arr.back() + 1) <= m)){
		cout << "YES\n";
	}else{
		cout << "NO\n";
	}

	//cout << (ans <= m ? "YES\n" : "NO\n");
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0);
    #ifndef ONLINE_JUDGE
     freopen("Error.in", "w", stderr);
    #endif
     int t = 1 ;
     cin >> t;
     while(t--){
        solve();
     }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1519A - Red and Blue Beans
466A - Cheap Travel
659E - New Reform
1385B - Restore the Permutation by Merger
706A - Beru-taxi
686A - Free Ice Cream
1358D - The Best Vacation
1620B - Triangles on a Rectangle
999C - Alphabetic Removals
1634C - OKEA
1368C - Even Picture
1505F - Math
1473A - Replacing Elements
959A - Mahmoud and Ehab and the even-odd game
78B - Easter Eggs
1455B - Jumps
1225C - p-binary
1525D - Armchairs
1257A - Two Rival Students
1415A - Prison Break
1271A - Suits
259B - Little Elephant and Magic Square
1389A - LCM Problem
778A - String Game
1382A - Common Subsequence
1512D - Corrupted Array
667B - Coat of Anticubism
284B - Cows and Poker Game
1666D - Deletive Editing
1433D - Districts Connection