akhauriyash/Code-Regression huggingface dataset:
n = int(input())
s = input()
temp = []
c = 0
pitem = ''
s2 = '.' + s + 'a'
for item in s2:
    if pitem == '' or item == pitem:
        c += 1
        pitem = item
    if item != pitem:
        temp.append(c)
        c = 1
        pitem = item
        continue

# print(temp)
# print(temp2)

t = s2.count('.')
c = 0
c2 = 0
cs = []
for i in range(len(temp)):
    c2 += temp[i]
    if i % 2 == 1:
        c += temp[i]
    cs.append(c + t - (c2 - c))
print(min(cs))


Measured memory_bytes: 13160
/**
     **author : _KMS_
     **created : 05-03-2020
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =6e5,MOD=1e9+7;
typedef long long ll;
int arr[M];
int res;
int mx=M;
int main() {
      
   ios::sync_with_stdio(false);
   cin.tie(0);
   int n;
   cin>>n;
   for(int i=0;i<n;i++)cin>>arr[i];
   for(int i=0;i<n;i++)if(arr[i]<mx){res++;mx=arr[i];}
  
   cout<<res<<"\n";
  
   
   return 0;
}

Measured memory_bytes: 1024
n=input().split(' ')
for i in range(0,2):
    if(int(n[i])==1):
        n[i]=14
    n[i]=int(n[i])
if(n[0]>n[1]):
    print("Alice")
elif(n[1]>n[0]):
    print("Bob")
else:
    print("Draw")
        

Measured memory_bytes: 3060
# https://atcoder.jp/contests/abc112/tasks/abc112_d

# 答えansの満たす条件
# ans<=M//Nである
# M%ans==0である


# 仮説:M//Nからansを--して、M%ans==0となるansが答え
# でももしN=2, M=10*9+7とかだったらTLEしそう→しなかった(コーナーケースに助けられた？)
# 2 999999937でTLEしてしまうのでこれは嘘解答

N, M = list(map(int, input().split()))

# 以下嘘解答
# ans = M // N
# for a in range(ans, 0, -1):
#     if M % a == 0:
# print(a)
# exit()

# 本当の解答
ans_temp = M // N
if M % N == 0:
    print(ans_temp)
    exit()


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


def make_divisors(n, sort=False):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    if sort:
        divisors.sort()
    return divisors


print(max(make_divisors(M), key=lambda x: 0 if x > ans_temp else x))


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#include<random>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vector<ll> v(n);
	REP(i,n) cin>>v[i];
	map<ll,ll> ma1;
	map<ll,ll> ma2;
	for(ll i=0; i<n; i+=2) {
		ma1[v[i]]++;
	}
	for(ll i=1; i<n; i+=2) {
		ma2[v[i]]++;
	}
	priority_queue<P> q1;
	priority_queue<P> q2;
	for(auto x: ma1) {
		q1.push(P(x.second,x.first));
	}
	for(auto x: ma2) {
		q2.push(P(x.second,x.first));
	}
	q1.push(P(0,INF));
	q2.push(P(0,INF));
	ll ans=INF*INF;
	P v1=q1.top();
	q1.pop();
	P v2=q1.top();
	P v3=q2.top();
	q2.pop();
	P v4=q2.top();
	if(v1.second!=v3.second) {
		ans=(n/2-v1.first+n/2-v3.first);
	} else {
		ans=(n/2-v1.first+n/2-v4.first);
		ans=min(ans,n/2-v2.first+n/2-v3.first);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 9592
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	string s;
	cin >> s;
	vector<int> t(26, 0);
	for (int i = 0; i < s.size(); i++)
		t[s[i] - 97]++;
	for (int i = 0; i < 26; i++) {
		if (t[i] == 0) {
			cout << char(i + 97) << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}


Measured memory_bytes: 512
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   1000000000
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};

ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}



//=============================================ASIFAZAD==============================================//

const int N = 2000100;
vi inp(N);
int n, k;

bool ok(ll mid)
{
    ll an = 0;
    for(int i = 0;i < n;i++)
        an += (inp[i] - 1)/mid;
    return an <= k;
}



int32_t main()
{
    io;
    //int n, k;
    cin>>n>>k;
    //vi a(n);
    for(int i= 0;i < n;i++)
        cin >>inp[i];

    ll l = 1, h = 1000000000, mid, ans;
    while(l <= h)
    {
        mid = (l + h)/2;
        /*ll s = 0;
        for(int i = 0; i< n;i++)
            s += (a[i] - 1)/mid;*/
        if(ok(mid))
        {
            ans = mid;
            h = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 10960
n = int(input())
w = [int(i) for i in input().split()]
s1, s2, dif = 0, 0, []
for i in range(n):
    s1 = sum(w[:i+1])
    s2 = sum(w) - s1
    dif.append(abs(s1 - s2))
print(min(dif))


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

int main() {
    cout << fixed << setprecision(5);
    long long n;
    cin >> n;
    vector<int> a(n);
    double sum = 0;
    for (long long i = 0; i < n; ++i) {
        cin >> a[i];
        sum += (1.0 / a[i]);
    }
    cout << 1 / sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double

#define pll pair<ll,ll>
#define ff first
#define ss second

#define pb push_back
#define all(x) x.begin(),x.end()

#define MOD  1000000007
const int N = 300050; 

#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

struct segTree
{
    vector<ll> a,t;
    ll n;
    segTree(ll sz)
    {
        n = sz;
        a.resize(n, 0);
        t.resize(4*n, 0);
    }
    ll merge(ll left,ll right)
    {
        ll ans = max(left , right);
        return ans;
    }
    void build(ll v,ll tl,ll tr)
    {
        if(tl==tr)
        {
            t[v] = a[tl];
        }
        else
        {
            ll tm = (tl + tr)/2;
            build(2*v,tl,tm);
            build(2*v+1,tm+1,tr);
            t[v] = merge(t[2*v],t[2*v+1]);
        }
    }
    void update(ll v,ll tl,ll tr,ll pos,ll new_val)
    {
        if(tl==tr)  
        {
            t[v] = new_val;
        }
        else
        {
            ll tm = (tl + tr)/2;
            if(pos<=tm)
            {
                update(2*v,tl,tm,pos,new_val);
            }
            else
            {
                update(2*v+1,tm+1,tr,pos,new_val);
            }
            t[v] = merge(t[2*v],t[2*v+1]);
        }
    }
    ll query(ll v,ll tl,ll tr,ll l,ll r)
    {
        if(l>r)   return 0;
        if(l==tl && r==tr)   return t[v];
        ll tm = (tl + tr)/2;
        return merge(query(v*2, tl, tm, l, min(r, tm)),query(v*2+1, tm+1, tr, max(l, tm+1), r));
    }
};


void solve()
{
    ll n,k;
    cin >> n >> k;
    ll a[n];
    segTree s(N);
    ll dp[n];
    for(ll i=0;i<n;i++)
    {
        cin >> a[i];
        ll mini = a[i] - k;
        ll maxi = a[i] + k;
        mini = max(mini,0LL);
        maxi = min(maxi,(ll)N-10);
        ll ans = s.query(1,0,N-1,mini,maxi);
        ans++;
        s.update(1,0,N-1,a[i],ans);
    }
    ll ans = s.query(1,0,N-1,0,N-1);
    cout<<ans;
}

int main()
{
    FAST;
    int t = 1;
 // cin >> t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
}

Measured memory_bytes: 17200
#include<iostream>
#define MAX_k 9

int n,k;
int d[MAX_k];

int check(int a)
{
    int i,p,m;
    p = a;
    while(p!=0)
    {
        m = p%10;
        for(i=0; i<k; i++)
            if(m==d[i])
            return 1;
        p = p/10;
    }
    return 0;
}
using namespace std;
int main()
{
    int n,i,j;

    cin >> n >> k;

    for(i=0; i<k; i++)
        cin >> d[i];

    j = n;
    while(1)
    {
        if(check(j)==0)
            break;
        else
            j++;
    }
    cout << j << endl;
}


Measured memory_bytes: 3596
N = int(input())
S = list(input())

r, g, b = 0, 0, 0
ans = 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

ans += r*g*b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i < N:
            if (S[i] != S[j]) and (S[j] != S[2*j-i]) and (S[i] != S[2*j-i]):
                ans -= 1

print(ans)


Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll a,b,k;
  cin>>a>>b>>k;
  if(b-a<2*k){
    for(int i=a;i<=b;i++){
      cout<<i<<endl;
    }
  }
  else{
    for(int i=0;i<k;i++){
      cout<<a<<endl;
      a++;
    }
    for(int i=0;i<k;i++){
      cout<<b-k+1<<endl;
      b++;
    }
  }
}

Measured memory_bytes: 3576
import math
def getInput():
    return [int(i) for i in input().rstrip().split(' ')]
N, M = getInput()
A = getInput()
_4M = math.ceil(sum(A) / (4*M))
A.sort(reverse=True)
cnt = 0
for i in A:
    if i >= _4M:
        cnt += 1
print('Yes') if cnt >= M else print('No')

Measured memory_bytes: 3060
import math
import heapq
import sys
from collections import Counter
import numpy as np

#N,K=map(int, input[0].split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
#x=list(map(int, input[1].split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#s = [input() for i in range(3)]

s=input()

S=sorted(s)

if S[0]==S[1] and S[2]==S[3] and S[0]!=S[3]:
    print('Yes')
else:
    print('No')

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

#define int long long int
using namespace std;

void solve() {
  int N;
  cin >> N;

  vector<int> v(100);
  v[0] = 2;
  v[1] = 1;

  for (int i = 2; i <= N; i++) {
    v[i] = v[i-1] + v[i-2];
  }

  cout << v[N] << endl;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 256
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10**7)

ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

x, y = na()
x -= 1
y -= 1
c = [300000, 200000, 100000]
ans = 0
if x < 3:
    ans += c[x]
if y < 3:
    ans += c[y]
if x == 0 and y == 0:
    ans += 400000

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;

int gcd(int a,int b) {
  if (a % b == 0) return b;
  else return gcd(b, a % b);
}

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

int main() {
  int n;
  cin >> n;
  vector<int> v1(n);
  for(int i = 0; i < n; ++i) {
	cin >> v1[i];
  }

  int ans;
  for(int j = 1; j < n; ++j) {
	if(j == 1) ans = lcm(v1[j - 1], v1[j]);
	else {
	  ans = lcm(ans, v1[j]);
	}
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()		// begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)				// repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)			// repeat reverse

#endif

int main(void)
{
	ll n; cin >> n;
	vector<ll> p(n);
	vector<ll> ans(n);

	rep(i, 0, n)
	{
		cin >> p[i];
		ans[i] = i+1;
	}

	ll count = 0;
	rep(i, 0, n)
	{
		if (p[i] != ans[i])
			count++;
	}

	if (count <= 2)
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

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

typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
/*--------------------------------------------*/

int main(){
  int n;
  cin >> n;
  cout << (n - 1)/2 << endl;
}

Measured memory_bytes: 256
N,M = map(int,input().split())

# parent(親)
par = [i for i in range(N+1)]
# rank(深さ)
rank = [0 for i in range(N+1)]
# 同グループの頂点数
size = [1 for i in range(N+1)]

# 木の根を求める
def root(x):
    if par[x] == x:             # 根の時
        return x
    else:
        par[x] = root(par[x])   # 経路圧縮
        return par[x]

# xとyの属する集合を併合(ランク有)
def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              # xの親をyに
        size[y] += size[x]      # yの頂点数+=xの頂点数
    else:
        par[y] = x              # yの親をxに
        size[x] += size[y]      # xの頂点数+=yの頂点数
        if rank[x] == rank[y]:
            rank[x] += 1

for _ in range(M):
    x,y,z = map(int,input().split())
    unite(x,y)
ans = 0
for i in range(1,N+1):
    if par[i] == i:
        ans += 1
print(ans)

Measured memory_bytes: 8624
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >>t;

    int cnt = 0;
    rep(i, s.size()) {
        if(s[i] != t[i]) cnt++;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3784
N, K = map(int, input().split())
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()
ans = 10**10
for i in range(N-K+1):
    hmin = h[i]
    hmax = h[i+K-1]
    ans = min(ans, (hmax-hmin))
print(ans)

Measured memory_bytes: 80972
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

use std::cmp;

fn main() {
    let N = get!(usize);
    let mut L = get!(Vec<usize>);

    L.sort();
    let mut ans = 0;
    for i in 0..N {
        ans += cmp::min(L[2 * i], L[2 * i + 1]);
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
//  @ /\/\ BESH //

#include <bits/stdc++.h>
#define inp_out_work ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testCase    int T; cin>>T; while(T--)
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,s,e) for(int i=s;i<=e;i++)
#define endl '\n'
#define debug(P) cout<<#P<<" = "<<P<<endl;
#define pb push_back


using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 100001;
const int mod = 1000000007;

int main(){
    int n;
    cin>>n;
    int a[n];
    fr(i,n)cin>>a[i];

    ll dp[n][n];

    fr(i,n)dp[i][i] = (n&1)? a[i] : 0;
    fr(i,n-1)dp[i][i+1] = (n&1)?  min(a[i] , a[i+1]) : max(a[i], a[i+1]);

    for(int len = 3; len <= n; len++){
        for(int i = 0; i <= n - len; i++){
            int j = i + len - 1;
            if((len&1) == (n&1))dp[i][j] = max(a[i] + dp[i+1][j], a[j] + dp[i][j-1]);
            else dp[i][j] = min(dp[i+1][j], dp[i][j-1]);
        }
    }

    ll ans = dp[0][n-1];

    ans = 2*ans - accumulate(a, a+n, 0LL);

    cout<< ans << endl;

}


Measured memory_bytes: 70144
def topological_sort(G):
  d = {}
  nodes = set()
  for i in G:
    if i not in d:
      d[i] = set()
    for j in G[i]:
      if j not in d:
        d[j] = set()
      d[j].add(i)
  for i in d:
    if len(d[i]) == 0:
      nodes.add(i)
  visited = set()
  ret = []
  while len(visited) < len(G):
    n = nodes.pop()
    if n not in visited:
      for j in G[n]:
        d[j].discard(n)
        if len(d[j]) == 0 and j not in visited:
          nodes.add(j)
      ret.append(n)
      visited.add(n)
  return ret




n,m = list(map(int, input().split(' ')))
G = {}
for i in range(n):
  G[i] = set()
for _ in range(m):
  s,t = list(map(int, input().split(' ')))
  G[s].add(t)

L = topological_sort(G)

for n in L:
  print(n)

Measured memory_bytes: 19272
#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,N) for(int i=0;i<((int)N);i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
int main(void){
  char s[52]; cin>>s;
  char t[52]; cin>>t;
  int slen=strlen(s);
  int tlen=strlen(t);
  int max=-1;
  for(int i=0;i<=slen-tlen;i++){
      int check=0;
      for(int j=i;j<i+tlen;j++){
          if(s[j]==t[j-i]||s[j]=='?') check++;
      }
      if(check==tlen) max=i;
  }
  if(max==-1) cout<<"UNRESTORABLE";
  else {
      for(int i=max;i<max+tlen;i++){
        s[i]=t[i-max];
      }
      for(int i=0;i<slen;i++){
          if(s[i]=='?') s[i]='a';
      }
      cout<<s;
  }
  return 0;
}


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

int main(void)
{
    int N, T;

    cin >> N >> T;

    vector<int> v(N,0);
    int vl = 1e9;

    for(int i = 0; i < N; ++i)
    {
        int a;
        cin >> a;
        vl = min(vl, a);
        v[i] = a - vl;
    }

    sort(v.begin(), v.end());
    vector<int>::iterator it1 = lower_bound(v.begin(), v.end(), v.back());

    cout << v.end() - it1 << endl;

    return 0;
}



Measured memory_bytes: 3768
n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
    ans = 0
else:
    a.sort(reverse=True)
    for i in a:
        if(i==0):
            ans = 0;break
        if ans>(10**18):
            ans = -1;break
        ans = ans*i
print(-1 if ans>(10**18) else ans)

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

int main(){
  int n;
  string s;
  cin>>n>>s;
  string res=s;
  int lef=0;
  int lefson=0;
  int rig=0;
  int rigson=0;
  for(int i=0;i<n;i++){
    if(s[i]=='(') lef++;
    else rig++;
    lefson=max(lefson,rig-lef);
  }
  lef=0;
  rig=0;
  for(int i=n-1;i>=0;i--){
    if(s[i]=='(') lef++;
    else rig++;
    rigson=max(rigson,lef-rig);
  }
  for(int i=0;i<lefson;i++){
    res="("+res;
  }
  for(int i=0;i<rigson;i++){
    res=res+")";
  }
  cout<<res<<endl;
  return 0;

}


Measured memory_bytes: 256
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
    private static int MAX = 300;
    private static int MIN = 1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        try {
            while (sc.hasNext()) {
                int[] h_w = Stream.of(sc.nextLine().split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray();
                if (h_w.length != 2) {
                    throw new IllegalTestCaseException();
                }
                int h = h_w[0];
                int w = h_w[1];
                if (h == 0 && w == 0) {
                    break;
                }
                if (h > MAX || h < MIN || w > MAX || w < MIN) {
                    throw new IllegalTestCaseException();
                }
                String r = "";
                for (int i = 0; i < w; i++) {
                    r += "#";
                }
                for (int i = 0; i < h; i++) {
                    System.out.println(r);
                }
                System.out.println();
            }
        } catch (IllegalTestCaseException
                | NoSuchElementException
                | NumberFormatException e) {
            System.out.println(e);
        }
    }

    private static class IllegalTestCaseException extends RuntimeException {
        IllegalTestCaseException() {
            super("Illegal condition.");
        }
    }
}



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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 h, w;
	while (cin >> h >> w && h+w) {
		int64 rw = 150, rh = 150;
		FOR(hh, 1, 151) {
			FOR(ww, hh+1, 151) {
				if (h*h+w*w < hh*hh+ww*ww || (h*h+w*w == hh*hh+ww*ww && h < hh)) {
					if (rw*rw+rh*rh > ww*ww+hh*hh) {
						rw = ww;
						rh = hh;
					}
				}
			}
		}
		cout << rh << " " << rw << endl;
	}
}



Measured memory_bytes: 3076
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;

int main(){
    int n;
    stack<int> s;
    cin >> n;
    while(cin >> n){
        s.push(n);
    }
    cout << s.top(); s.pop();
    while(!s.empty()){
        cout << " " << s.top(); s.pop();
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>pppp(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
 
int main() {
  int N;
  cin>>N;
  vector<int>A(N+2);
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  int sum=0;
  for(int i=0;i<=N;i++){
    sum+=abs(A[i+1]-A[i]);
  }
  for(int i=1;i<=N;i++){
    int disp=A[i]-A[i-1];
    int disn=A[i+1]-A[i];
    if(disp*disn<0){cout<<sum-2*min(abs(disp),abs(disn))<<endl;}
    else{cout<<sum<<endl;}
  }
 return 0;
}

Measured memory_bytes: 3788
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define N 200020
using namespace std;

int d[N];

int main(void)
{
    int n, x;
    int i;

    scanf("%d", &n);
    for(i = 2; i <= n; i ++)
    {
        scanf("%d", &x);
        d[x] ++;
    }
    for(i = 1; i <= n; i ++)
        printf("%d\n", d[i]);

    return 0;
}


Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int H,W;
    cin>>H>>W;
    string S[H];
    rep(i,H){
        cin>>S[i];
    }

    vector<vector<int>> dist(H,vector<int>(W,-1));
    queue<pair<int,int>> q;
    rep(i,H){
        rep(j,W){
            if(S[i][j]=='#') {
                q.push(make_pair(i,j));
                dist[i][j]=0;
            }
        }
    }
    int ans=0;
    while ((!q.empty())){
        pair<int,int> v=q.front();
        int h=v.first;
        int w=v.second;
        q.pop();
        rep(j,4){
            int nh=h+dx[j];
            int nw=w+dy[j];
            if(nh<0||nw<0||nh>=H||nw>=W) continue;
            if(S[nh][nw]=='#') continue;
            if(dist[nh][nw]==-1){
                q.push(make_pair(nh,nw));
                dist[nh][nw]=dist[h][w]+1;
            }
        }
    }
    rep(i,H){
        rep(j,W){
            ans=max(ans,dist[i][j]);
        }
    }
    cout << ans << endl;




}


Measured memory_bytes: 25524
use std::io::*;
use std::str::FromStr;
 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


//main function
fn main() {
    let n: usize = read();
    let mut bcount:i32 = 0;
    for _i in 0..n{
	let a:i32 = read();
	if a%2!=0{
	    bcount+=1;
	}
    }
    bcount%=2;
    if bcount==0{
	println!("YES");
    }else{
	println!("NO");
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<queue<pair<int, int> > > edges(N+1);
    for (int i = 0; i < N-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].push(make_pair(b, c));
        edges[b].push(make_pair(a, c));
    }
    int Q, K;
    cin >> Q >> K;
    vector<long long> distances(N+1, -1);
    distances[K] = 0;
    queue<int> current;
    current.push(K);
    while (!current.empty()) {
        int a = current.front();
        while(!edges[a].empty()) {
            auto edge = edges[a].front();
            int b = edge.first, c = edge.second;
            if (distances[b] == -1) {
                distances[b] = distances[a]+c;
                current.push(b);
            }
            edges[a].pop();
        }
        current.pop();
    }
    vector<pair<int, int> > XY(Q);
    for (auto &xy : XY) cin >> xy.first >> xy.second;
    for (const auto &xy : XY) printf("%lld\n", distances[xy.first]+distances[xy.second]);
    return 0;
}

Measured memory_bytes: 70912
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <list>
#include <math.h>
#include <string.h>
#include <bitset>
#include <queue>
using namespace std;

typedef pair<int, int> P;
#define INF (1LL<<60)
#define int long long
#define ll long long
#define mod 1000000007




signed main(){

	int N, a[123456];
	cin >> N;
	int ans = 0, tmp=0;
	for (int i = 0; i < N; i++){
		cin >> a[i];
		if (a[i] == 0){
			ans += tmp / 2;
			tmp = 0;
		}
		else
			tmp += a[i];
	}

	ans += tmp / 2;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
	"sort"
)

func main() {
	var a, b, c int
	var arr []int
	var ans = []int{5, 5, 7}
	fmt.Scan(&a, &b, &c)
	arr = append(arr, a, b, c)
	sort.Ints(arr)
	for i, v := range arr {
		if v != ans[i] {
			fmt.Println("NO")
			return
		}
	}
	fmt.Println("YES")
}


Measured memory_bytes: 512
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,a,b = map(int, input().split())
    print(min(a,b), max(0, a+b-n))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
int dy[] = {1, 0, 0, -1};
int dx[] = {0, 1, -1, 0};
int b[110][110];
int w, h;
int xs, ys, xg, yg;
int color;
bool flag = false;
bool used[110][110];

void dfs(int y, int x, int py, int px){
	rep(i, 4){
		int ny = y + dy[i], nx = x + dx[i];
		if(used[ny][nx]) continue;//???????????¨???????????????????????????
		if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
		if(b[ny][nx] != color) continue;
		if(ny == py && nx == px) continue;
		if(ny == yg && nx == xg){
			used[ny][nx] = true;
			flag = true; return;//????????????
		}
		used[ny][nx] = true;
		dfs(ny, nx, y, x);
	}
	return;//????????¢?????¨???????????????
}

int main(void){
	while(1){
		rep(i, 110)rep(j, 110){
			b[i][j] = -1; used[i][j] = false;
		}
		cin >> w >> h;
		if(w == 0 && h == 0) return 0;
		cin >> xs >> ys >> xg >> yg;
		xs--; ys--; xg--; yg--;
		int n; cin >> n;
		rep(i, n){
			int c, d, x, y;
			cin >> c >> d >> x >> y;
			x--; y--;
			if(d == 0){//?¨?
				b[y][x] = b[y][x + 1] = b[y][x + 2] = b[y][x + 3] = c;
				b[y + 1][x] = b[y + 1][x + 1] = b[y + 1][x + 2] = b[y + 1][x + 3] = c;
			}else{//???
				b[y][x] = b[y][x + 1] = c;
				b[y + 1][x] = b[y + 1][x + 1] = c;
				b[y + 2][x] = b[y + 2][x + 1] = c;
				b[y + 3][x] = b[y + 3][x + 1] = c;
			}
		}
		color = b[ys][xs];
		if(color == -1) {//?????????????????????????????????
			printf("NG\n"); continue;
		}
		used[ys][xs] = true; flag = false;
		dfs(ys, xs, -1, -1);
		if(flag) printf("OK\n");
		else printf("NG\n");
	}
}

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A.at(i);
    }

    for(int i = 0; i < (N - K); i++) {
        if(A.at(i) < A.at(i + K)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 4052
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
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> A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    vector<int> sub(N);
    vector<ll> sub_sum(N+1, 0);
    rep(i, N) sub[i] = A[i] - B[i];
    sort(sub.begin(), sub.end(), greater<int>());
    for(int i = 1; i < N+1; i++){
        sub_sum[i] = (ll)sub_sum[i-1] + sub[i-1];
    }
    ll lack_sum = 0;
    ll margin = 0;
    int ans = 0;
    rep(i, N){
        if(A[i] < B[i]){
            lack_sum += (ll)B[i] - A[i];
            ans++;
        }else{
            margin += (A[i] - B[i]);
        }
    }
    if(margin < lack_sum){
        cout << -1 << endl;
        return 0;
    }
    rep(i, N+1){
        if(lack_sum <= sub_sum[i]){
            ans += i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5104
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
struct Graph {
    std::vector<std::vector<Edge<Cost>>> graph;

    Graph(int n = 0) : graph(n) {}

    void span(bool direct, int src, int dst, Cost cost = 1) {
        graph[src].emplace_back(src, dst, cost);
        if (!direct) graph[dst].emplace_back(dst, src, cost);
    }

    std::vector<Edge<Cost>>& operator[](int v) { return graph[v]; }
    std::vector<Edge<Cost>> operator[](int v) const { return graph[v]; }

    int size() const { return graph.size(); }
};

constexpr int INF = 1 << 30;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> xs(n);
    for (auto& x : xs) std::cin >> x;

    Graph<> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;

        --u, --v;
        graph.span(false, u, v);
    }

    std::vector<int> ans(n, -1);
    std::vector<int> dp(n + 1, INF);
    dp[0] = 0;

    std::function<void(int)>
        dfs = [&](int v) -> void {
        auto x = xs[v];

        int i = std::lower_bound(dp.begin(), dp.end(), x) - dp.begin();
        ans[v] = std::max(ans[v], i);

        int px = dp[i];
        dp[i] = x;

        for (auto e : graph[v]) {
            int u = e.dst;
            if (ans[u] != -1) continue;
            ans[u] = ans[v];
            dfs(u);
        }
        dp[i] = px;
    };

    dfs(0);
    for (auto x : ans) std::cout << x << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 33608
#include <bits/stdc++.h>

using namespace std;
#define lint long long
#define P pair<int, int>


int main() {
    int N;
    cin >> N;
    
    int ans = 0;
    for(int i = 1; i <= N; ++i){
        if(i % 2 == 0){
            continue;
        }
        int cnt = 0;
        for(int j = 1; j <= i; ++j){
            if(i % j == 0){
                cnt++;
            }
        }
        if(cnt == 8){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q1;
int main(){
	int n,m;
	LL a,b,c;
	int i,j,k;
	LL s=0;
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>a>>b;
		q1.push(make_pair(a,b));
	}
	while(!q1.empty()){
		a=q1.top().first,b=q1.top().second,q1.pop();
		if(b>=m){
			s+=a*m;
			break;
		}
		m-=b,s+=a*b;
	}
	cout<<s<<endl;
	return 0;
}


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

int main()
{
	int N,M;
	cin>>N>>M;
	
	int A[M],i,j,tot=0;
	for(i=0;i<M;++i)
	{
		cin>>A[i];
		tot+=A[i];
	}
	
	if(tot>N)
	{
		cout<<-1<<endl;
	}
	else
	{
		cout<<(N-tot)<<endl;
	}
	
}

Measured memory_bytes: 3676
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
 
ll dp[302][302];
bool f[302][302];
vector<ll>a;
ll n;

ll Abs(ll x,ll y){
    if(x>=y)return x-y;
    else return y-x;
}


ll rec(ll l,ll r){
    if(f[l][r])return dp[l][r];
    if(l==r)return dp[l][r]=0;
    if(l>r)return dp[l][r]=0;
    if(l<=0)return 0;
    if(r>n)return 0;
    if(r-l==1){
        f[l][r]=true;
        if(Abs(a[l],a[r])<=1)return dp[l][r]=2;
        else return dp[l][r]=0;
    }
    if(Abs(a[l],a[r])<=1){
        dp[l+1][r-1] = rec(l+1,r-1);
        f[l+1][r-1]=true;
        if(dp[l+1][r-1]==r-l-1){
            f[l][r]=true;
            return dp[l][r]=r-l+1;
        }
    }
    ll ans = 0;
    for(ll k=l;k<r;k++){
        ans = max(ans,rec(l,k)+rec(k+1,r));
    }
    f[l][r]=true;
    return dp[l][r]=ans;
}


int main(void){
    while(true){
        for(ll i=0;i<302;i++){
            for(ll j=0;j<302;j++){
                dp[i][j]=0;
                f[i][j]=false;
            }
        }
        cin>>n;
        if(n==0)break;
        a.resize(n+1,0);
        for(ll i=0;i<n;i++){
            ll x;
            cin>>x;
            a[i+1]=x;
        }
        ll ans = 0;
        cout<<rec(1,n)<<endl;
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }*/
    }
    return 0;
}




Measured memory_bytes: 3940
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
pair<double,double> dots[300];
#define EPS (1e-6)


int main(){

	while(cin >> N && N != 0){
		for(int i = 0; i < N; i++){
			pair<double,double> p;
			cin >> dots[i].second >> dots[i].first;
		}
		int maxCnt = 1;
		// ~ðìé½ßÌQ_ðßé
		for(int i = 0; i < N; i++){
			for(int j = i+1; j < N; j++){
				pair<double,double> dot1,dot2;
				dot1 = dots[i];
				dot2 = dots[j];

				double v = sqrt((dot1.first - dot2.first)*(dot1.first - dot2.first)
					+(dot1.second - dot2.second)*(dot1.second - dot2.second));
				// ñ_Ô£ª2æè¨¨«¯êÎÂ­êÈ¢
				if(v > 2.0 + EPS){
					continue;
				}

				double x = sqrt(1 - (v/2)*(v/2));

				// ñgÌPÊ@üxNg
				pair<double,double> hose[2];
				hose[0].first = -1.0/(dots[i].first - dots[j].first);
				hose[0].second = 1.0/(dots[i].second - dots[j].second);
				hose[1].first = 1.0/(dots[i].first - dots[j].first);
				hose[1].second = -1.0/(dots[i].second - dots[j].second);

				double dd1 = sqrt((hose[0].second)*(hose[0].second)+(hose[0].first)*(hose[0].first));
				double dd2 = sqrt((hose[1].second)*(hose[1].second)+(hose[1].first)*(hose[1].first));
				hose[0].first /= dd1; hose[0].second /= dd1;
				hose[1].first /= dd2; hose[1].second /= dd2;

				// x{·é
				hose[0].first *= x;hose[1].first *= x;
				hose[0].second *= x;hose[1].second *= x;

				// mð«·
				hose[0].first += (dot1.first + dot2.first)/2;
				hose[0].second += (dot1.second + dot2.second)/2;
				hose[1].first += (dot1.first + dot2.first)/2;
				hose[1].second += (dot1.second + dot2.second)/2;

				// hose[0]Æhose[1]Í~ÌSÀW
				// e_ÉÖµÄ~ÌÉ¶Ý·é©Ç¤©ðßé
				for(int k = 0; k < 2; k++){
					int cnt = 0;
					for(int l = 0; l < N; l++){
						double dist = sqrt((dots[l].first -hose[k].first)*(dots[l].first -hose[k].first)
							+ (dots[l].second -hose[k].second)*(dots[l].second -hose[k].second));
						if(dist <= 1.0 + EPS){
							cnt++;
						}
					}
					maxCnt = max(maxCnt,cnt);
				}
			}
		}
		cout << maxCnt << endl;
	}

	return 0;
}

Measured memory_bytes: 968
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    cout << n * (n - 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)

cakes = []
n.times do
  cakes << gets.split.map(&:to_i)
end

p [-1, 1].repeated_permutation(3).map { |cx, cy, cz|
  cs = cakes.sort_by {|x, y, z| cx * x + cy * y + cz * z }[0, m]
  value = cs.reduce([0, 0, 0]) { |as, bs|
    as.zip(bs).map { |a, b| a + b }
  }.map(&:abs).reduce(:+)
}.max


Measured memory_bytes: 4216
#include <iostream>
#include <sstream>

using namespace std;

int main()
{
	string str = "";

	while (getline (cin, str) ) {
		int n = 0;
		int res = 0;
		stringstream ss(str );
		ss >> n;

		for (int i = 0; i < 10000; ++i ){
			int a = i/1000;
			int b = (i/100) % 10;
			int c = (i/10) % 10;
			int d = i % 10;
			
			if (a + b + c + d == n ){
				++res;
			} // end if
		} // end for
		cout << res << endl;	
	} // end while

	return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int H[] = new int[N];
        for (int i = 0; i < N; i++) {
            H[i] = s.nextInt();
        }
        int cnt = 0;
        List<Integer> l = new ArrayList<>();

            for (int j = 0; j < N; j++) {
                if(j==0)
                    continue;
                if (H[j-1] >= H[j])
                cnt++;
                else {
                    l.add(cnt);
                    cnt=0;
                }
            }
            l.add(cnt);
        Collections.sort(l, Collections.reverseOrder());
        System.out.print(l.get(0));
    }
}


Measured memory_bytes: 50476
#include <iostream>
using namespace std;

int main(int argc, char const* argv[])
{
	int r, c;
	cin >> r >> c;
	int array[100][100] = {{}};
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++) {
			cin >> array[i][j];
		}
	}

	int row_sum = 0;
	for (int i=0; i<r; i++) {
		int tmp_sum = 0;
		for (int j=0; j<c; j++) {
			cout << array[i][j] << " ";
			tmp_sum += array[i][j];
		}
		cout << tmp_sum << endl;
		row_sum += tmp_sum;
	}

	for (int j=0; j<c; j++) {
		int tmp_sum = 0;
		for (int i=0; i<r; i++) {
			tmp_sum += array[i][j];
		}
		cout << tmp_sum << " ";
	}
	cout << row_sum << endl;

	return 0;
}


Measured memory_bytes: 1208
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 120

int main(){
  int n,ans=0,count=0;
  cin>>n;
  for(int i=3;i<=n;i+=2,count=0){
    for(int j=1;j<=i;j+=2){
      if(i%j==0) count++;
    }
    if(count==8) ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

constexpr int inf = 2147483647;
constexpr int64_t inf64 = 9223372036854775807;
constexpr int mod = 1e9+7;

int n, a, b, c;

int dfs(vector<int> &dist, vector<int> &l);

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

  cin >> n >> a >> b >> c;
  vector<int> l(n);
  vector<int> dist = {};
  rep(i,n) cin >> l[i];

  cout << dfs(dist, l) << endl;
  return 0;
}



int dfs(vector<int> &dist, vector<int> &l) {

  if (dist.size() == n) {
    int A = 0, B = 0, C = 0;
    int cnt = 0;
    rep(i,n) {
      if (dist[i] == 1) { A += l[i]; cnt++; }
      if (dist[i] == 2) { B += l[i]; cnt++; }
      if (dist[i] == 3) { C += l[i]; cnt++; }
    }

    if (A == 0) return inf;
    if (B == 0) return inf;
    if (C == 0) return inf;

    int ret = 0;
    ret += abs(A-a);
    ret += abs(B-b);
    ret += abs(C-c);
    ret += (cnt-3) * 10;
    return ret;

  }

  int res = inf;
  rep(i,4) {
    dist.push_back(i);
    res = min(res, dfs(dist, l));
    dist.pop_back();
  }

  return res;
}

Measured memory_bytes: 256
import std.stdio,std.string,std.conv;
int main(){
    auto input=readln.chomp.split;
    auto a=input[0].to!int;
    auto b=input[1].to!int;
    auto at=(a*13).to!int;
    auto bt=(b*10).to!int;
    foreach(y;bt..at+1){
        if((y*0.08).to!int==a&&(y*0.1).to!int==b){
            y.writeln;
            return 0;
        }
    }
    "-1".writeln;
    return 0;
}


Measured memory_bytes: 256
# include"stdio.h"

void swap(int a,int b,int c[]){
    int t=c[a];
    c[a]=c[b];
    c[b]=t;
}

int main(){
    int n;
    scanf("%d",&n);
    int v[n];
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);
    for(int i=0;i<n;i++){
        for(int j=n-1;j>i;j--){
            if(v[j-1]>v[j])
                swap(j-1,j,v);
        }
    }
    double max=0;
    max=(double)(v[0]+v[1])/2;
    for(int i=2;i<n;i++)
        max=(double)(max+v[i])/2;
    printf("%f\n",max);


}


Measured memory_bytes: 128
#include <stdio.h>

int main(){
    int i,j,k,ans=1;
    int w,h,x,y,judge;
    double s=0.0;


    scanf("%d %d %d %d",&w,&h,&x,&y);

    s = (double)w*(double)h/2.0;

    judge=0;
//        if((w%2==0)&&(h%2==0)){
            // if((2*x==w)&&(2*y==h)){
            //     judge=1;
            // }   
//        }

	if( !(w==0||h==0) ){
//        printf("ok.\n");
  	if((w%2==0)&&(h%2==0)){
//          printf("ok.\n");
            if((w/2==x)&&(h/2==y)){
//                printf("ok.\n");
                judge=1;
            }   
        }
    }

    printf("%lf %d",s,judge);

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <utility>
#include<string>
#include <algorithm>


using namespace std;
int main(void){

    int N;
    cin>>N;
    //int data[1000000000];
    vector<int> data;
    
    for(int i=0;i<N;i++)
    {
        int a;
        cin>>a;//data[i];
        int count =0;
        
        if(a%2 !=0) 
        {
            cout<<0<<endl;
            return 0;
        }
        
        while(a%2==0)
        {
        a /=2;
        count++;
        }
              
        data.emplace_back(count);
            
        
    }
    
     std::sort(data.begin(), data.end() );
    
    cout<<data[0]<<endl;
    
    return 0;
}

Measured memory_bytes: 256