akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; cin >> N;
    vector<ii> T[N];
    FOR(i,0,N-1){
        int A; cin >> A;
        FOR(j,0,A-1){
            int x, y; cin >> x >> y;
            --x;
            T[i].emplace_back(x,y);
        }
    }

    int maxi = 0;
    FOR(i,0,(1<<N)-1){
        bool ok = true;
        FOR(j,0,N-1) if (i&(1<<j)) {
            for(auto& x : T[j]) {
                if ((i&(1<<x.fi))^(x.sc<<x.fi)) { ok = false; break; }
            }
            if (!ok) break;
        }
        if (ok) maxi = max(maxi, __builtin_popcount(i));
    }
    cout << maxi;
}



Measured memory_bytes: 256
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)

	fmt.Println(solve("0", n))
}

func num753(s string) bool {
	seven := false
	five := false
	three := false
	for _, n := range s {
		switch n {
		case '7':
			seven = true
		case '5':
			five = true
		case '3':
			three = true
		}
	}
	return seven && five && three
}

func solve(s string, n int) int {
	intS, _ := strconv.Atoi(s)
	if intS > n {
		return 0
	}

	res := 0
	if num753(s) {
		res = 1
	}
	for _, c := range []string{"7", "5", "3"} {
		res += solve(s+c, n)
	}

	return res
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    int ans = 2 * n;
    for (int i = n; i < 2 * n; ++i) {
        string ss = s.substr(i - n, 2 * n - i);
        string tt = t.substr(0, 2 * n - i);

        if (ss == tt) {
            ans = i;
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
        #define ll long long
        #define f   first
        #define s   second
        #define pb          push_back
        #define mod        1000000007
        #define mod1       1000000009
        #define hell        998244353
        #define inf         1000000000000000000LL
        #define pi          3.14159265358979323
        #define N           9
        using namespace std;
        ll n,k,sum,q,res,m,val;
        ll x,y;
        void solve()    
        {   
            string s;
            cin>>s;
            n=s.size();
            for(int i=0;i<3;i++) cout<<s[i];


        }
        int main()
        {   ios_base::sync_with_stdio(false);
            cin.tie(0);cout.tie(0);
            ll t=1;
            //cin>>t;
            for(int i=1;i<=t;i++)
                solve();
            

        }            

Measured memory_bytes: 3640
#include <iostream>
#include <vector>

int main(int argc, char** argv)
{
	int n, m, l;
	std::cin >> n >> m >> l;

	std::vector<std::vector<long long>> matA;
	for (int i = 0; i < n; ++i)
	{
		std::vector<long long> vec;
		for (int j = 0; j < m; ++j)
		{
			int val;
			std::cin >> val;
			vec.push_back(val);
		}
		matA.push_back(vec);
	}

	std::vector<std::vector<long long>> matB;
	for (int i = 0; i < m; ++i)
	{
		std::vector<long long> vec;
		for (int j = 0; j < l; ++j)
		{
			int val;
			std::cin >> val;
			vec.push_back(val);
		}
		matB.push_back(vec);
	}

	std::vector<std::vector<long long>> matC;
	for (int i = 0; i < n; ++i)
	{
		std::vector<long long> vec;
		for (int j = 0; j < l; ++j)
		{
			long long val = 0;
			for (int k = 0; k < m; ++k)
			{
				val += (matA[i][k] * matB[k][j]);
			}
			vec.push_back(val);
		}
		matC.push_back(vec);
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < l; ++j)
		{
			std::cout << matC[i][j];

			if (j < l - 1)
			{
				std::cout << " ";
			}
		}

		std::cout << std::endl;
	}

	return 0;
}


Measured memory_bytes: 3280
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

fn main() {
    let mut scan = Scan::new();

    let N = scan.word::<usize>();
    let a = scan.list::<usize>(N);

    let t = (0..N).fold(0, |x, i| x ^ a[i]);
    let x = (0..N).map(|i| t ^ a[i]);

    println!("{}", x.map(|x| x.to_string()).collect::<Vec<_>>().join(" "));
}


Measured memory_bytes: 21540
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <map>
#include <set> 
#include <bitset>
#include <cmath>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)

int main () {
    
    int n; cin >> n;
    vector<int> x(n); REP(i,n) cin >> x[i];

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += x[i]-1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    X = LMIIS()
    to2 = 0
    sumX = sum(X)
    for x in X:
        to2 += x**2
    
    P = round(sumX / N)
    

    print(to2 -2*sumX*P + N*P**2)


if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
#include<stdio.h>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<random>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<immintrin.h>
#include<stdio.h>

using namespace std;

int main (){

	int R;
	int G;
	int a;
	scanf("%d",&R);
	scanf("%d",&G);

	a = 2 * G - R;

	printf("%d\n",a);


	return 0;









}

Measured memory_bytes: 128
import sys

input = sys.stdin.readline

def main():

    ma = 10**18
    N = int(input())
    A = list(map(int,input().split()))
    ans =1

    if 0 in A:
        print(0)
        exit()

    for i in A:
        ans *= i
        if ans >ma:
            print(-1)
            exit()

    if ans >ma:
        print(-1)
    else:
        print(ans)




if __name__ == "__main__":
    main()

Measured memory_bytes: 21604
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {

    input!{
        n: String,
    }
    let result:usize = n.match_indices("2").count();
    println!("{}", result);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;

int main() {
  long long N,M,A,B;
  cin >> N >> M;

  vector<pair<long,long>> vec;
  for(int i = 0; i < N; i++) {
      cin >> A >> B;
      vec.push_back(make_pair(A,B));
  }

  sort(vec.begin(),vec.end());
   long long sum = 0,ans = 0;
  for(int i = 0; i < N;i++) {
      ans += vec.at(i).first * vec.at(i).second;
      sum += vec.at(i).second;
      if(sum >= M) {
          long rest = sum - M;
          ans -= vec.at(i).first * rest;
          break;
      }
  }
    cout << ans << endl;
}

Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <list>

static const int MAX = 100000;
using namespace std;

vector<int> G[MAX];
bool Visited[MAX];
list<int> result;
void dfs(int u)
{
    Visited[u]=true;
    for(int i=0;i<G[u].size();i++)
        if(Visited[G[u][i]]==false)  dfs(G[u][i]);

    //result.push_back(u);
    result.push_front(u);
}
int main()
{
    int n,e;
    cin>>n>>e;
    //init
    for(int i=0;i<n;i++)
       Visited[i]=false;
    int s,t;
    for(int i=0;i<e;i++)
    {
        cin>>s>>t;
        G[s].push_back(t);
    }

    //begin
    //pay attention to the forest!!
    for(int i=0;i<n;i++)
    {
        if(Visited[i]==false)
            dfs(i);
    }
    //print
    for(list<int>::iterator it=result.begin();it!=result.end();it++)
        cout<<*it<<endl;
}

Measured memory_bytes: 6212
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
 
  int sz;
  vector< Monoid > seg;
 
  const F f;
  const Monoid M1;
 
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
 
  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }
 
  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
 
  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);

    int N; cin >> N;
    VI h(N); VL a(N);
    REP(i,N) cin >> h[i];
    REP(i,N) cin >> a[i];
    auto f = [](LL a, LL b) {return max(a,b);};
    SegmentTree<LL> seg(N+1,f,0);
    seg.build();
    REP(i,N){
        seg.update(h[i],seg.query(0,h[i]) + a[i]); 
        //REP(j,5){
        //    cout << seg[j] << " ";
        //}
        //cout << endl;
        
    }
    cout << seg.query(0,N+1) << endl;

}


Measured memory_bytes: 6656
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {

	public static void main(String[] args) {
		new Main().run();
	}

	FastScanner sc;
	int[] ns;

	void run() {
		sc = new FastScanner();
		int n = sc.nextInt();
		ns = new int[n];

		int sum = 0;
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			ns[i] = tmp;
			sum += tmp;
		}

		int mid = sum / n;

		int ans = Integer.MAX_VALUE;
		for (int i = mid; i <= 100; i++) {
			int c = 0;
			for (int j = 0; j < n; j++) {
				c += Math.pow((ns[j] - i), 2);
			}
			ans = Math.min(ans, c);
		}
		
		System.out.println(ans);
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 8020
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2000+50;
const ll mod=1000000007;
ll s[maxn],t[maxn],dp[maxn][maxn];
ll read()
{
    ll s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
int main()
{
    int n,m;
    cin>>n>>m;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++) s[i]=read();
    for(int i=1;i<=m;i++) t[i]=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i]==t[j]) dp[i][j]=dp[i-1][j]+dp[i][j-1]+1;
            else dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            dp[i][j]%=mod;
        }
    }
    cout<<(dp[n][m]+1+mod)%mod<<endl;
    return 0;
}

Measured memory_bytes: 33280
#include<iostream>
using namespace std;
int arg=101;
int cost=1001;


int main() {
  int N, T, c, t;
  cin >> N >> T;
  for (int i=0; i<N; i++) {
    cin >> c >> t;
    if (t<=T) {
      if (c<cost) {
        cost = c;
        arg = i;
      }
    }
  }
  if (cost==1001) {
    cout << "TLE" << endl;
  } else {
    cout << cost << endl;
  }
  return 0;
}


Measured memory_bytes: 256
from itertools import combinations_with_replacement


n, m, q = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(q)]

points = []
for A in combinations_with_replacement(range(1, m + 1), n):
    # print(A)
    point = 0
    for a, b, c, d in Q:
        if A[b-1] - A[a-1] == c:
            point += d
    points.append(point)

print(max(points))


Measured memory_bytes: 74168
import sys

class Card:
	def __init__(self, card):
		self.card = card
		self.mark = card[0]
		self.value = int(card[1])

	def __str__(self):
		return self.card

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def bubble_sort(arr):
	n = len(arr)
	for i in range(0, n):
		for j in range(n - 1, i, -1):
			if arr[j].value < arr[j - 1].value:
				swap(arr, j, j - 1)

def selection_sort(arr):
	n = len(arr)
	for i in range(n):
		minj = i
		for j in range(i, n):
			if arr[j].value < arr[minj].value:
				minj = j
		if minj != i:
			swap(arr, i, minj)

n = int(input())
arr = list(map(str, input().split()))
cards1 = [None] * n
cards2 = [None] * n
for i in range(n):
	cards1[i] = Card(arr[i])
	cards2[i] = Card(arr[i])

bubble_sort(cards1)
selection_sort(cards2)

for i in range(n):
	sys.stdout.write(cards1[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
print('Stable')

stable = True
for i in range(n):
	if cards1[i].card != cards2[i].card: stable = False
	sys.stdout.write(cards2[i].card)
	if i != n - 1:
		sys.stdout.write(' ')
print()
if stable == True:
	print('Stable')
else:
	print('Not stable')



Measured memory_bytes: 5616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    ll n, a;
    cin >> n;
    map<ll, ll> m;
    rep1(i, n){
        cin >> a;
        if (m[a]==0) m[a] = 1;
        else m[a] = 0;
    }
    ll ans = 0;
    for (auto x: m){
        if (x.second == 1) ans++;
    }
    cout << ans << endl;
    //printf("%.12f", ans);
}

Measured memory_bytes: 9860
N=int(input())
L = list(map(int,input().split()))

ans = 0
if N<=2:
  print(0)
  exit()
for i1 in range(N-2):
  l1 = L[i1]
  for i2 in range(i1+1,N-1):
    l2 = L[i2]
    for i3 in range(i2+1,N):
      l3 = L[i3]
      if l1==l2 or l2==l3 or l3==l1: continue
      tmp = sorted([l1,l2,l3])
      if tmp[0]+tmp[1]>tmp[2]:
        ans += 1
print(ans)

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll int res[200000];
ll int add[200000];
vector<int> edges[200000];
bool visit[200000];

int n,q;

void solve(int nownode, int nowcnt){
  visit[nownode] = true;
  res[nownode] = nowcnt + add[nownode];
  nowcnt = res[nownode];
  if(edges[nownode].size() == 0) return;
  for(int i = 0; i < edges[nownode].size(); i++){
    int to = edges[nownode][i];
    if(visit[to]) continue;
    // cout << "nownode : " << nownode << " to: " << to << " nowcnt: " << nowcnt << endl;
    solve(to, nowcnt);
  }
}
int main(){
  cin >> n >> q;
  REP(i, n-1){
    int from, to;
    cin >> from >> to;
    edges[from-1].pb(to-1);
    edges[to-1].pb(from-1);
  }
  REP(i, 200000){
    res[i] = 0;
    add[i] = 0;
  }
  REP(i, q){
    int node, amount;
    cin >> node >> amount;
    add[node-1] += amount;
  }
  solve(0, 0);
  REP(i, n){
    cout << res[i];
    if(i != n-1) cout << " ";
    else cout << endl;
  }
}

Measured memory_bytes: 25984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


template <typename T>
class Seg_Tree{
public: // 0-index
  vector<T> dat;
  T initial,M;
  int n;
  T unite(T a,T b){//
    return min(a,b);
  }
  Seg_Tree(int n0_=1,T initial_=1,T M_=1){
    initsize(n0_,initial_,M_);
  }
  void initsize(int n0,T initial_,T M_){
    M = M_;
    initial = initial_;
    int k=1;
    while(1){
      if(n0<=k){
        n=k;
        dat.resize(2*n-1);
        for(int i=0;i<2*n-1;i++)dat[i]=initial;
        break;
      }
      k*=2;
    }
  }
 
  //i banme wo x nisuru
  void update(int i,T x){
    i += n-1;
    dat[i] = x;
    while(i>0){
      i = (i-1) / 2;
      dat[i] = unite(dat[i*2+1],dat[i*2+2]);
    }
  }
 
  //[a,b)
  T query0(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return initial;
    if(a<=l && r<=b)return dat[k];
    else{
      T vl = query0(a,b,k*2+1,l,(l+r)/2);
      T vr = query0(a,b,k*2+2,(l+r)/2,r);
      return unite(vl,vr);
    }
  }
 
  //return unite[a,b)
  T query(int a,int b){
    return query0(a,b,0,0,n);
  }
};

int main(){
	ll N,M;
	string S;
	cin >> N >> M >> S;

	Seg_Tree<ll> sg(N+2,MOD,MOD+5);
	FOR(i,0,N+1)if(S[i]=='0')sg.update(i,i);
	vector<ll> ans;
	ll now = N;
	while(now){
		ll to = sg.query(now-M,now);
		if(to == MOD){
			cout << -1 << endl;
			return 0;
		}
		ans.push_back(now - to);
		now = to;
	}
	REV(ans);
	cout << ans[0];
	FOR(i,1,ans.size()){
		cout << " " << ans[i];
	}
	cout << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k, q;
  cin >> n >> k >> q;
  
  int a;
  vector<int> b(n);
  for(int i=0; i<q; i++) {
    cin >> a;
    b[a-1]++;
  }
  
  for(int i=0; i<n; i++) {
    if(k-q+b[i]>0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3764
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long long x[210000];
int sa[210000];
int nx_L[19][210000];
int nx_R[19][210000];

int d[20];
int L[1<<19];
int R[1<<19];
pair<int,int>p[1<<19];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%lld",x+i);
	}
	d[0]=b;
	int n=1;
	for(int i=0;d[i];i++){
		d[i+1]=d[i]/2;
		n=i+2;
	}
	for(int i=0;i<n;i++){
		int to=a;
		nx_L[i][a]=a;
		for(int j=a-1;j>=0;j--){
			nx_L[i][j]=to;
			if(j&&x[j]-x[j-1]>d[i])to=j;
		}
	}
	for(int i=0;i<n;i++){
		int to=a;
		nx_R[i][a]=a;
		for(int j=a-1;j>=0;j--){
			nx_R[i][j]=to;
			if(j&&x[a-j]-x[a-1-j]>d[i])to=j;
		}
	}
	for(int i=0;i<(1<<n);i++){
		int at=L[i];
		for(int j=0;j<n;j++){
			if(i&(1<<j))continue;
			int to=nx_L[j][at];
			L[i+(1<<j)]=max(L[i+(1<<j)],to);
		}
	}
	for(int i=0;i<(1<<n);i++){
		int at=R[i];
		for(int j=0;j<n;j++){
			if(i&(1<<j))continue;
			int to=nx_R[j][at];
			R[i+(1<<j)]=max(R[i+(1<<j)],to);
		}
	}
	int sz=0;
	for(int i=0;i<(1<<n);i++){
		if(i&1);
		else{
			p[sz++]=make_pair(L[i],i);
		}
	}
	/*for(int i=0;i<n;i++){
		printf("%d: ",d[i]);
		for(int j=0;j<a;j++)printf("%d ",nx_L[i][j]);
			printf("\n");
	}
	for(int i=0;i<n;i++){
		printf("%d: ",d[i]);
		for(int j=0;j<a;j++)printf("%d ",nx_R[i][j]);
			printf("\n");
	}
	*/
	std::sort(p,p+sz);
	set<pair<int,int> >S;
	for(int i=0;i<(1<<n);i++){
		if(i&1);
		else{
			S.insert(make_pair(R[i],i));
		}
	}
	int at=0;
	for(int i=0;i<a;i++){
		int lq=a-nx_R[0][a-1-i];
		int rq=a-nx_L[0][i];
		while(at<sz&&p[at].first<lq){
			S.erase(make_pair(R[(1<<n)-2-p[at].second],(1<<n)-2-p[at].second));
			at++;
		}
		//printf("%d %d\n",lq,rq);
		if(S.size()){
			pair<int,int> tp=*(S.rbegin());
			if(tp.first>=rq)printf("Possible\n");
			else printf("Impossible\n");
		}else{
			if(at<sz&&rq==0)printf("Possible\n");
			else printf("Impossible\n");
		}
	}
}

Measured memory_bytes: 56448
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f(const void *a,const void *b){	return *(int*)b-*(int*)a;}
int main()
{
	int a,b,c,d,n,i,j,r[101]={0},s[101]={0};
	scanf("%d",&n);
	for(i=0;i<n*(n-1)/2;i++,c==d?r[a]++,r[b]++:c>d?r[a]+=3:(r[b]+=3))
		scanf("%d%d%d%d",&a,&b,&c,&d);
	memcpy(s,r,n*4+4);
	qsort(s,n+1,4,f);
	for(i=1;i<=n;i++)
	{
		for(j=0;s[j]!=r[i];j++);
			printf("%d\n",j+1);
	}
	return 0;
}

Measured memory_bytes: 616
import sys

n,a,b,c,d=map(int, input().split()) 
s=input()

sl=list(s)

sl[a-1]="A"
sl[b-1]="B"
sl[c-1]="a"
sl[d-1]="b"
#print(sl)

if c>d:
    g_far=c
else:
    g_far=d

#連続して"#"が来た場合はクリア不可
for i in range(a-1,g_far-2):
    if sl[i]=="#" and sl[i+1]=="#":
        print("No")
        sys.exit()

#c>dの場合、連続3マスの"."が必要

if c>d:
    for j in range(b-1-1,d-1):
        #print(sl[j],sl[j+1],sl[j+2])
        if sl[j] !="#" and sl[j+1] !="#" and sl[j+2] !="#":
            print("Yes")
            sys.exit()
else:
    print("Yes")
    sys.exit()

print("No")



Measured memory_bytes: 4924
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll dp[5000];
ll N, M;
vector<ll> cov(1010), val(1010);
const ll INF = (1ll<<60);

ll rec(ll mask){
	//dump(mask)
	if(dp[mask] >= 0) return dp[mask];
	if(mask == 0) return 0;
	ll res = INF;
	REP(i, M){
		if((mask&cov[i]) != 0){
			ll tmp = 0;
			tmp += rec((mask&(~cov[i])));
			tmp += val[i];
			res = min(tmp, res);
		}
	}
	dp[mask] = res;
	return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    REP(i, M){
    	ll a, b;
    	cin >> a >> b;
    	val[i] = a;
    	ll tmp = 0;
    	REP(i, b){
    		ll c;
    		cin >> c;
    		c--;
    		tmp += (1ll<<c);
    	}
    	cov[i] = tmp;
    }

    REP(i, 5000){
    	dp[i] = -1;
    }

    ll ans = rec((1ll<<N)-1);

    cout << (ans == INF ? -1 : ans) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
  ll n ; cin>> n ;
  vector<ll> A(n) ; rep(i,n) cin>>A[i] ;
  sort(A.rbegin(),A.rend()) ;
  ll ans= 0 ;
  rep(i,n){
   ans += A[i/2] ;
  }
  ans -= A[0] ;
  cout<<ans<<endl ;
 return 0 ; 
}



Measured memory_bytes: 4840
arr = gets.strip.split(" ").map!(&:to_i)
n = arr[0]
str = Array.new(n)
n.times do |i|
  str[i] = gets.strip
end

n.times do |i|
  min = i
  i.step(n-1) do |j|
    if(str[min] > str[j]) then
      min = j
    end
  end
  s = str[i]
  str[i] = str[min]
  str[min] = s
end

n.times do |i|
  print str[i]
end
puts


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007

void solve()
{
	ll a,b,x;
	cin>>a>>b>>x;
    if(a%x==0)
        cout<<b/x-a/x+1;
    else 
    	cout<<b/x-a/x<<endl;
	return;
}

int main()
{
	fast;
	ll q=1;
	// cin>>q;
	while(q--)
		solve();
	return 0;
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mr  make_pair
using namespace std;
int mod = 1e9+7;
int inf = 1e18;
const int N = 5e5+999;
int powmod(int a,int b) {int res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
int arr[N];
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        int ct = 0;

        rep(i,0,n)
        {
            if(s.substr(i,3)=="ABC")
                ++ct;
        }
        cout<<ct<<el;
    }
   return 0;
}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main(int argc, const char * argv[]) {
    int W, a, b;
    scanf("%d %d %d", &W, &a, &b);
    if(a+W<b)       printf("%d\n", b-(a+W));
    else if(b+W<a)  printf("%d\n", a-(b+W));
    else            printf("0\n");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <ctime>

#ifndef _USEFUL_MACROS_
#define _USEFUL_MACROS_
#define INF INT_MAX/3
#define N_PRIME 1000000007
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
//#define OUTPUT_DEBUG
#ifdef OUTPUT_DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x) do{}while(false)
#endif
#endif 

using namespace std;

int64_t nmax = 100008;              // 0!からnmax!までの表を作る
int64_t prime = N_PRIME;            // 倍数が含まれてはいけないのでnより大きい必要がある
bool isCombPreProcess = false;      // 前処理が終わっているかどうか
vector<int64_t> fact(nmax+1);       // fact[i] = iの階乗 mod prime
vector<int64_t> fact_inv(nmax+1);   // fact_inv[i] = fact[i]^(-1) mod prime

// x^n ( mod p )
int64_t power(int64_t x,int64_t n,int64_t p){
    int64_t ret = 1;
    
    while(n){
        if(n%2)ret=(ret*x)%p;
        x = (x * x) % p;
        n/=2;
    }
    
    return ret;
}

void CombPreProcess(){
    fact[0] = 1;
    FOR(i,1,nmax+1)
        fact[i] = (i*fact[i-1])%prime;
    
    fact_inv[nmax] = power(fact[nmax],prime-2,prime);
    RFOR(i,0,nmax)
        fact_inv[i] = ((i+1)*fact_inv[i+1])%prime;
    isCombPreProcess = true;
}

// a C b
int64_t Combination(int64_t a,int64_t b){
    if( isCombPreProcess ){
        return ((((fact[a]*fact_inv[b]) % prime)*fact_inv[a-b]) % prime);
    }else{
        CombPreProcess();
        return Combination(a,b);
    }
}

void test(){
    debug(Combination(5,3));
    debug(Combination(5,2));
    debug(Combination(5,1));
    debug(Combination(5,0));
    debug(Combination(5,5));
}

int main(void){
    
    //test();
    
    int n;
    cin >> n;
    vector<int> a(n+1);
    vector<int> b(n);
    vector<int> c(n+1);
    int p1,p2;
    
    
    REP(i,n)
        b[i]=-1;
    
    REP(i,n+1){
        cin >> a[i];
        a[i]--;
        if( b[a[i]] == -1 ){
            b[a[i]] = i;
        }else{
            p1 = b[a[i]];
            p2 = i;
        }
    }
    
    debug(p1);
    debug(p2);
    
    //cout << "A" << Cmb(1,0) << endl;
    ///cout << "A" << Cmb(1,1) << endl;
    
    int t =  p1+n-p2;
    debug(t);
    FOR(k,1,n+2){
        int64_t right;
        if( t < k-1 ) right=0;
        else right = Combination(t,k-1);
        int64_t left = Combination(n+1,k);
        
        debug(t);
        debug(k-1);
        debug(right);
        
        debug(n+1);
        debug(k);
        debug(left);
        
        cout << ((left-right+prime)%prime) << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3968
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9)+7)

int main(){
    string s;
    cin >> s;
    for(int i = 0;i < s.size();i++)
    {
      cout << "x";
    }
    cout << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

void sorting(int x[], int first, int end){
	int t;
	int i = first;
	int j = end;
	int p = (first + end)/2;
	int pivot = x[p];

	while(1){
		while(x[i] < pivot)
			i++;
		while(x[j] > pivot)
			j--;
		if(i >= j)
			break;
		t = x[i];
		x[i] = x[j];
		x[j] = t;
		i++;
		j--;
	}
	if(first < i-1)
		sorting(x, first, i-1);
	if(j+1 < end)
		sorting(x, j+1, end);
}

int exchange(int flag, int n[], int m[], int n_num, int m_num, int dif){
	int i=0, j;
	if(dif%2 == 1)
		goto notfound;
	while(i<m_num){
		for(j=0; j<n_num; j++){
			/*printf("dif:%d n:%d m:%d\n",dif/2, j, i);*/
			if(n[j] == m[i] + dif/2)
				goto found;
			if(n[j] > m[i] + dif/2)
				break;
		}
		i++;
	}
	notfound:
	printf("-1\n");
	return 0;
	found:
	if(flag == 0)
		printf("%d %d\n", n[j], m[i]);

	else
		printf("%d %d\n", m[i], n[j]);

	return 0;
}


int main(){
	int n[100] = {0};
	int m[100] = {0};
	int n_sum, m_sum;
	int n_num, m_num, i;
	int dif;



	scanf("%d %d", &n_num, &m_num);
	while(n_num != 0){
		n_sum = 0;
		m_sum = 0;
		for(i=0; i < n_num; i++){
			scanf("%d", &n[i]);
			n_sum += n[i];
		}
		for(i=0; i<m_num; i++){
			scanf("%d", &m[i]);
			m_sum += m[i];
		}

		/**printf("%d %d\n",n_sum, m_sum);*/
		sorting(n, 0, n_num-1);
		/*for(i=0; i< n_num; i++){
			printf("%d ",n[i]);
		}
		printf("\n");*/
		sorting(m, 0, m_num-1);
		/*for(i=0; i<m_num; i++){
			printf("%d ",m[i]);
		}
		printf("\n");*/
		if(n_sum >= m_sum){
			dif = n_sum - m_sum;
			exchange(0, n, m, n_num, m_num, dif);
		}
		else{
			dif = m_sum - n_sum;
			exchange(1, m, n, m_num, n_num, dif);
		}
		scanf("%d %d", &n_num, &m_num);
	}
	return 0;
}

Measured memory_bytes: 612
#include <bits/stdc++.h> 
using namespace std;

int main(){
    int n, m, p, n_ac=0, n_wa=0;
    string s;
    cin >> n >> m;
    vector<bool> aclist(n, false);
    vector<int> walist(n, 0);

    for(int i=0; i<m;i++){
        cin >> p >> s;
        if (aclist[p-1] == true){
            continue;
        }
        else{
            if (s == "AC"){
                n_ac++;                
                aclist[p-1] = true;
                n_wa += walist[p-1];
            }
            else{ 
                walist[p-1]++;
            }
        }        
    }
    cout << n_ac << " " << n_wa;
} 

Measured memory_bytes: 640
/*
オーダー
10**6	余裕を持って間に合う	
10**7	おそらく間に合う	余裕を持って間に合う
10**8	非常にシンプルな処理でない限り厳しい	おそらく間に合う
10**9		非常にシンプルな処理でない限り厳しい
logn	:OK
n		:10^7
nlogn	:10^6
n**2	:10^4
n**3	:300
2**n	:20
n!		:10



// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/

#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18
// int 
// // 各桁の和を計算する関数
// int findSumOfDigits(int n) {
//   int amari = 0;
//   int keta = 0;
//   while (n > 0) { // n が 0 になるまで
//     amari += n % 2;
//     if (keta%2==0)
//     n /= 10;
//   }
//   return sum;
// }
 
ll gcd(ll a, ll b) {
	if(b == 0) return a;
	return gcd(b, a % b);
}

// const ll MAX_N = 1e5;
// ll N;
// ll h[MAX_N];
// ll dp[MAX_N+1]; // メモ化テーブル
 
// // i番目以降の品物から重さの総和がj以下になるように選ぶ
// void rec(ll i){
// 	if (i==0) dp[i] = 0;
// 	else if (i==1) dp[i] = abs(h[1]-h[0]);
// 	else dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
// 	return;
// }
 
 
int main() {
	// 入力
	ll N;
	cin >> N;
	ll a[N];
	for (ll i = 0; i < N; ++i) cin >> a[i];
 
	// 解法
	sort(a, a+N);
	// a が1種類の場合
	if (a[0]==a[N-1]){
		ll a1 = a[0];
		// a1に属する猫はサイズ2以上のグループ
		// なので 全猫の数 >= a1 x 2である必要がある
		bool judge = a1*2<=N;
		// 別の可能性として全猫がサイズ1グループ
		if (a1+1==N) judge = true;
		if (judge) printf("Yes\n");
		else printf("No\n");
	}
	else if (a[0]+1<a[N-1]){
		printf("No\n");
	}
	// aが2種類の場合
	else{
		ll a1 = a[0];
		ll a2 = a[N-1];
		ll count_a1 = 0;
		REP(i,N) if(a[i]==a1) count_a1++;
		// コーナーケース1_16 (No)
		// a1に属する猫はサイズ1のグループ
		// なので全ての種類数=a2>a1グループの数である必要がある
		bool judge = a2>count_a1;
		// num_group2 = サイズ1でないグループの数 = a2 - count_a1
		// num_group2 * 2<= count_a2
		ll count_a2 = N - count_a1;
		ll num_group2 = a2 - count_a1;
		if (num_group2*2>count_a2) judge = false;
		if (judge) printf("Yes\n");
		else printf("No\n");
	}
}


Measured memory_bytes: 1024
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

vector<int> v;

void init_uf(int n){
    v.assign(n,-1);
}

int find_(int x){
    if(v[x]<0) return x;
    v[x]=find_(v[x]);
    return v[x];
}

int same_(int a,int b){
    if(find_(a)==find_(b)) return 1;
    return 0;
}

void union_(int a,int b){
    if(same_(a,b)) return;
    int a_p=find_(a),b_p=find_(b);
    if(a_p>b_p) swap(a_p,b_p);
    v[a_p]+=v[b_p]; v[b_p]=a_p;
}

int main(){
    ll n; cin>>n;
    init_uf(n);
    vector<pair<ll,ll>> x(n),y(n);
    rep(i,n){
        ll X,Y; cin>>X>>Y;
        x[i]=mk(X,i); y[i]=mk(Y,i);
    }
    sort(al(x)); sort(al(y));
    set<pair<ll,ll>> xt,yt;
    rep(i,n-1){
        xt.insert(mk(x[i+1].first-x[i].first,i));
        yt.insert(mk(y[i+1].first-y[i].first,i));
    }
    ll dx,dy,sx,sy,ans=0;
    while(!(xt.empty()) || !(yt.empty())){
        dx=dy=INF; sx=sy=-1;
        if(!(xt.empty())){
            tie(dx,sx)=*begin(xt);
        }
        if(!(yt.empty())){
            tie(dy,sy)=*begin(yt);
        }
        if(dx<dy){
            if(same_(x[sx].second,x[sx+1].second)==0){
                union_(x[sx].second,x[sx+1].second);
                ans+=dx;
            }
            xt.erase(mk(dx,sx));
        }
        else{
            if(same_(y[sy].second,y[sy+1].second)==0){
                union_(y[sy].second,y[sy+1].second);
                ans+=dy;
            }
            yt.erase(mk(dy,sy));
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 19416
import scala.collection.mutable.Queue
import io.StdIn

object Main extends App {
  val n = StdIn.readInt
  val seq = StdIn.readLine.split(" ").map(_.toInt % 3)
  val a = for(i <- 0 until 3) yield seq.count(_ == i)

  def bfs(first:Tuple5[Int,Int,Int,Int,Int]):Int = {

    val que = new Queue[Tuple5[Int,Int,Int,Int,Int]]
    que += first
    var cur = (0,0,0,0,0)

    var isCnt = true
    while(isCnt || !que.isEmpty) {
      cur = que.dequeue

      if(cur._2 == 0 || (cur._3 == 0 && cur._4 == 0 && cur._5 == 0)) isCnt = false
      else {
        cur match {
          case (acc, 1, c0, c1, c2) if c0 != 0 => que += {(acc+1, 1, c0-1, c1, c2)}
          case (acc, 2, c0, c1, c2) if c0 != 0 => que += {(acc+1, 2, c0-1, c1, c2)}
          case (acc, 1, c0, c1, c2) if c1 != 0 => que += {(acc+1, 2, 0, c1-1, c2)}
          case (acc, 2, c0, c1, c2) if c2 != 0 => que += {(acc+1, 1, 0, c1, c2-1)}
          case (acc, 2, c0, c1, c2) if c1 != 0 => que += {(acc+1, 0, 0, c1-1, 0)}
          case (acc, 1, c0, c1, c2) if c2 != 0 => que += {(acc+1, 0, 0, 0, c2-1)}
        }
      }
    }
    cur._1
  }

  val res1 = if(a(1) == 0) 0 else bfs(0,1,a(0),a(1)-1,a(2)) + 1
  val res2 = if(a(2) == 0) 0 else bfs(0,2,a(0),a(1),a(2)-1) + 1
  val ans = if(a.drop(1).sum == 0) 1 else math.max(res1,res2)
  println(ans)
}


Measured memory_bytes: 200208
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    ll ans = 0;
    vector<ll> s(n), t(n);
    rep(i, n) cin >> s[i];
    rep(i, n) t[i] = s[i] + s[n - 1 - i];

    forx(c, 1, n)
    {
        ll d = 0, e = 0;
        if ((n - 1) % c == 0)
        {
            rep(k, n - 1)
            {
                if (c * (k + 1) >= (n - 1) / 2)
                    break;
                e += t[c * (k + 1)];
                d = max(d, e);
            }
        }
        else
            rep(k, n - 1)
            {
                if (c * (k + 2) > n)
                    break;
                e += t[c * (k + 1)];
                d = max(d, e);
            }
        ans = max(ans, d);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(){
  int n,a=0;
  char c,d='-';
  scanf("%d",&n);
  for(;n>0;n--){
    scanf("%c",&c);
    if((c>='a')&(c<='z')){
      if((c!=d)&(d!='-')){
        a++;
      }
      d=c;
    }else{
      n++;
    }
  }
  printf("%d",a+1);
  return(0);
}


Measured memory_bytes: 128
n = int(input())
v = list(map(int,input().split()))
kati = 0

v.sort()
kati = (v[0] + v[1]) / 2

if n == 2:
  print(kati)
else:
  for i in range(2,n):
    kati = (kati + v[i]) / 2
  print(kati)


Measured memory_bytes: 3060
#include <iostream>

using namespace std;

int main() {
    int count = 0;
    int a;
    int b;
    cin >> a;
    cin >> b;

    if(a<9 && b<9){
        cout << "Yay!" << endl;
    }else {
        cout << ":(" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


int main() {
	init();
	
	string s; cin >> s;
	bool is = false;
	rep(i, 0, s.size()) {
		if (s.substr(i, 2) == "AC")is = true;
	}
	cout << (is ? "Yes" : "No") << "\n";

	return 0;
}

Measured memory_bytes: 256
a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
c=[2]
x,y=map(int, input().split())
ans_a, ans_b = '', ''
if x in a:
    ans_a = 'a'
elif x in b:
    ans_a = 'b'
else:
    ans_a = 'c'
if y in a:
    ans_b = 'a'
elif y in b:
    ans_b = 'b'
else:
    ans_b = 'c'
if ans_a == ans_b:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll a, b, c;
    cin>>a>>b>>c;
    if(4*a*b<(c-a-b)*(c-a-b) && c-a-b>0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int height, width;
	cin >> height >> width;
	
	vector<string> target(height);
	vector<vector<bool>> canvas(height, vector<bool>(width, false));
	
	for (auto&& e : target) {
		cin >> e;
	}
	
	bool no = false;
	for (int i = 0; i < height && !no; ++i) {
		for (int j = 0; j < width && !no; ++j) {
			if (canvas[i][j]) {
				continue;
			}
			
			if (target[i][j] == '#') {
				if (i + 1 < height && target[i + 1][j] == '#') {
					canvas[i][j] = true;
					canvas[i + 1][j] = true;
				} else if (j + 1 < width && target[i][j + 1] == '#') {
					canvas[i][j] = true;
					canvas[i][j + 1] = true;
				} else if (i - 1 >= 0 && target[i - 1][j] == '#') {
					canvas[i][j] = true;
					canvas[i - 1][j] = true;
				} else if (j - 1 >= 0 && target[i][j - 1] == '#') {
					canvas[i][j] = true;
					canvas[i][j - 1] = true;
				} else {
					no = true;
				}
			}
		}
	}
	
	cout << (no ? "No" : "Yes") << endl;
	return 0;
}

Measured memory_bytes: 256