akhauriyash/Code-Regression huggingface dataset:
let scan_int () = Scanf.scanf " %d" (fun x -> x)
let scan_string () = Scanf.scanf " %s" (fun x -> x)
let scan_array len read_func = Array.init len (fun _ -> read_func())
let print_int n = Printf.printf "%d\n" n

let () =
  let n = scan_int() in
  let arr = scan_array n scan_string in
  let sort_char s = 
    let a = Array.init (String.length s) (fun i -> s.[i]) in
    let _ = Array.sort compare a in
    let _ = Array.iteri (fun i x -> (s.[i] <- x)) a in s in
  let arr = Array.map sort_char arr in
  let _ = Array.fast_sort compare arr in
  let rec for_loop i st ret =
    if i == n then
      let t = i - st in ret + t * (t-1) / 2
    else
      if arr.(i) <> arr.(i-1) then
        let t = i - st in
        let ret = ret + t * (t-1) / 2 in
        for_loop (i+1) i ret
      else for_loop (i+1) st ret in
  print_int (for_loop 1 0 0)


Measured memory_bytes: 8192
#ABC051 B 
#入力
K,S = list(map(int, input().split()))

#処理
ans = 0;
for X in range(K+1):
    for Y in range(K+1):
        Z = S-X-Y
        if 0<=Z and Z<=K:
            ans +=1

#出力
print(ans)            

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    ll arr[n+1];
    arr[0]=2;
    arr[1]=1;
    for(int i=2;i<=n;i++){
        arr[i]=arr[i-1]+arr[i-2];
    }
    cout<<arr[n]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// int facctorialMethod(int k){
//     int sum = 1;
//     for (int i = 1; i <= k; ++i)
//     {
//         sum *= i;
//     }
//     return sum;
// }
int main(){
    int N;
    // int M;
    cin >> N;
    int tmp;
    vector<int> A(N-1);
    vector<int> B(N,0);
    // for(int i=0;i<N;i++){
    //     cout << B.at(i) << endl;
    // }
    // int sum = 0;
    for(int i=0;i<N-1;i++){
        cin >> A.at(i);
        tmp = A.at(i);
        B.at(tmp-1) += 1;
    }
    for(int i=0;i<N;i++){
        cout << B.at(i) << endl;
    }
}

Measured memory_bytes: 4844
N, M = map(int, input().split())
try:
  a = int(input())
except EOFError:
  a = 0
P = [0]*(N+1)
P[0] = 1
if a == 1:
  P[1] = 0
  try:
    a = int(input())
  except EOFError:
    pass
    
else:
  P[1] = 1

for i in range(2,N+1):
  if i == a:
    P[i] = 0
    try:
      a = int(input())
    except EOFError:
      continue
  else:
    P[i] = P[i-1] + P[i-2]
print(P[-1]%1000000007)

Measured memory_bytes: 460020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int main(){
  ll N,A,B; cin>>N>>A>>B;
  if(A>B) cout<<0<<endl;
  else if(N==1){
    if(A!=B) cout<<0<<endl;
    else cout<<1<<endl;
  }else{
    ll mi=(N-1)*A+B;
    ll ma=A+(N-1)*B;
    cout<<ma-mi+1<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define N 200005
const int INF=0x3f3f3f3f;
const int mod=1e9 + 7;
using namespace std;
ll a[N];
int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	ll sum = INF;
	for(int i = m; i <= n; i++) {
		sum = min(sum, a[i] - a[i - m + 1]);
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#define N 100000

int partition(int *A,int p,int r){
    int x,i,j,temp;
    x=A[r];
    i=p-1;
    for(j=p;j<r;j++){
        if(A[j]<=x){
            i=i+1;
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
    }
    temp=A[i+1];
    A[i+1]=A[r];
    A[r]=temp;
    return i+1;
}

int main(){
    int n,i,x,q;
    int A[N];
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&A[i]);
    x=partition(A,0,n-1);
    for(i=0;i<n;i++){
        if(x==i)printf("[%d",A[i]);
        else if(i!=n-1)printf("%d ",A[i]);
        else printf("%d",A[i]);
        if(x==i)printf("] ");
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 2188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
using LL = long long;

int main(){
    set<int> st;
    int a,b,c;
    cin >> a >> b >> c;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    if(st.size()==2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>

int n,A[50];

int so(int i,int j){
  if(j==0)return 1;
  if(i>=n)return 0;
  int re=so(i+1,j)||so(i+1,j-A[i]);
  return re;
}

int main(){
  int i,n2,B;

    scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&n2);
  for(i=0;i<n2;i++){
     scanf("%d",&B);
     if(so(0,B))printf("yes\n");
     else printf("no\n");
  }
  return 0;
}



Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <algorithm>
#define int long long

using namespace std;

int N;
int A[202020];

signed main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    sort(A, A + N, greater<int>());

    if (N == 2)
    {
        cout << A[0] << endl;
    }
    else if (N == 3)
    {
        cout << A[0] + A[1] << endl;
    }
    else if (N == 4)
    {
        cout << A[0] + 2 * A[1] << endl;
    }
    else
    {
        int idx = 1;
        int ans = A[0];
        for (int i = 2; i < N; i++)
        {
            if (i % 2 == 0)
            {
                ans += A[idx];
            }
            else
            {
                ans += A[idx];
                idx++;
            }
        }
        cout << ans << endl;
    }

    // for (int i = 0; i < N; i++)
    // {
    //     cout << A[i] << endl;
    // }
}

Measured memory_bytes: 4752
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

N,K = map(int,input().split())
A = list(map(int,input().split()))
if K == 0:
    print(max(A))
else:
    s = 0
    g = 10**9
    mae = -1
    now = 1
    while now != mae:
        mae = now
        c = 0
        if (s + g)%2 == 0:
            now = (s + g)//2
        else:
            now = (s + g)//2+1        
        for i in range(N):
            if A[i]%now == 0:
                c += (A[i]//now)-1
            else:
                c += A[i]//now
        if c > K:
            s = now
        else:
            g = now
        #print(now,c)
    print(now)

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

using namespace std;

using int64 = long long;

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
  using P = function< OperatorMonoid(OperatorMonoid, int) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F &f;
  const G &g;
  const H &h;
  const P &p;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F &f, const G &g, const H &h, const P &p,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), p(p), M1(M1), OM0(OM0) {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x) {
    data[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int len) {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], p(lazy[k], len));
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, r - l);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x) {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b) {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k) {
    return query(k, k + 1);
  }
};

using int64 = long long;
const int64 INF = 1LL << 60;

int main() {
  int N, Q;
  scanf("%d %d", &N, &Q);
  auto f = [&](int64 x, int64 y) { return min(x, y); };
  auto g = [&](int64 x, int64 y) { return x + y; };
  auto p = [&](int64 x, int64 y) { return x; };
  LazySegmentTree< int64 > seg(N, f, g, g, p, INF, 0);
  for(int i = 0; i < N; i++) seg.set(i, 0);
  seg.build();
  while(Q--) {
    int P;
    scanf("%d", &P);
    if(P == 0) {
      int S, T, X;
      scanf("%d %d %d", &S, &T, &X);
      seg.update(S, T + 1, X);
    } else {
      int S, T;
      scanf("%d %d", &S, &T);
      printf("%lld\n", seg.query(S, T + 1));
    }
  }

}


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

int leng=0;
int b[15];
int f[3],ttl=0,a=0,n;
void backt(int poz){
    if(poz>=3){
        for(int i=0; i<poz; i++){
            if(b[i]==3){
                f[0]++;
            }
            else if(b[i]==5){
                f[1]++;
            }
            else if(b[i]==7){
                f[2]++;
            }
            a*=10;a+=b[i];
        }
        if(f[0]>0&&f[1]>0&&f[2]>0&&a<=n){
            ttl++;
        }
        f[0]=0;
        f[1]=0;
        f[2]=0;
        a=0;
    }
    if(poz==leng+1){
        return;
    }
    b[poz]=3;
    backt(poz+1);
    b[poz]=5;
    backt(poz+1);
    b[poz]=7;
    backt(poz+1);
}
int main()
{
    cin>>n;
    int cn=n;
    while(cn!=0){
        cn/=10;
        leng++;
    }
    backt(1);
    cout<<ttl;
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.lang.*;

class Main{
  public static void main(String[] args) throws IOException{
    Scanner scan=new Scanner(System.in);
    int n=Integer.parseInt(scan.next());
    int[] S=new int[n+1];
    for(int i=0;i<S.length-1;i++){
      S[i]=Integer.parseInt(scan.next());
    }
    int q=Integer.parseInt(scan.next());
    int[] T=new int[q];
    for(int i=0;i<T.length;i++){
      T[i]=Integer.parseInt(scan.next());
    }

    int count=0;
    for(int i=0;i<T.length;i++){
      int j=0;
      S[n]=T[i];
      while(S[j]!=T[i]){
        j++;
      }
      if(j==n){
        continue;
      }
      count++;
    }
    System.out.println(count);
  }
}



Measured memory_bytes: 38888
#include <cstdio>
#include <vector>

using namespace std;

class Edge{
public:
	int from,to,cost;
	void Swap(){
		int a = from;
		from = to;
		to = a;
	}
};

vector<Edge> edges;

const int INF = 999999999;

int solve(int s,int g,int c){
	int d[101][11];
	bool flag[101][11];
	for(int i=0;i<101;i++){
		for(int j=0;j<11;j++){
			d[i][j] = INF;
			flag[i][j] = false;
		}
	}
	d[s][c] = 0;
	
	vector<Edge>::iterator eit;
	
	while(1){
		int no,nc;
		bool f = true;
		for(int i=0;i<101;i++){
			for(int j=c;j>=0;j--){
				if(d[i][j] != INF && flag[i][j] == false){
					if(f){
						no = i;
						nc = j;
					}else if(d[no][nc] > d[i][j]){
						no = i;
						nc = j;
					}
					f = false;
				}
			}
		}
		if(f){break;}
		flag[no][nc] = true;
		for(eit = edges.begin();eit != edges.end(); eit++){
			if(eit->from == no){
				if(d[eit->to][nc] > d[eit->from][nc] + eit->cost){
					d[eit->to][nc] = d[eit->from][nc] + eit->cost;
				}
				if(nc > 0){
					if(d[eit->to][nc - 1] > d[eit->from][nc] + eit->cost / 2){
						d[eit->to][nc - 1] = d[eit->from][nc] + eit->cost / 2;
					}
				}
			}
		}
	}
	int ans = INF;
	for(int i=0;i<c;i++){
		if(d[g][i] < ans){
			ans = d[g][i];
		}
	}
	return ans;
}

int main(){
	int c,n,m,s,d;
	int a,b,f;
	while(1){
		scanf("%d %d %d %d %d",&c,&n,&m,&s,&d);
		if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0){
			break;
		}
		edges.clear();
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&a,&b,&f);
			Edge e;
			e.from = a;
			e.to = b;
			e.cost = f;
			edges.push_back(e);
			e.Swap();
			edges.push_back(e);
		}
		printf("%d\n",solve(s,d,c));
	}
	return 0;
}

Measured memory_bytes: 840
N = int(input())
A = list(map(int, input().split()))

ret = 0
flag = True
while(flag):
  for i in range(N):
    if(A[i] % 2 != 0):
      flag = False
    else:
      A[i] /= 2
  if(flag):
    ret += 1  
print(ret)

Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
    if(a%b==0||b%a==0) return min(a,b);
    if(a>=b) return gcd(b,a%b);
    else return gcd(a,b%a);
}

int main(void){
    int n,m;
    cin>>n>>m;
    cout<<gcd(n,m)<<'\n';
    return 0;
}


Measured memory_bytes: 3092
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            long a = long.Parse(input[0]);
            long b = long.Parse(input[1]);
            long x = long.Parse(input[2]);

            int count = 0;

            if (a == 0)
            {
                Console.WriteLine(b/x + 1);
            }
            else
                Console.WriteLine(b/x - (a-1)/x);





        }
    }
}


Measured memory_bytes: 11092
#!/usr/bin/env python3
from collections import deque

N = int(input().split()[0])

# ノードの情報
node_dict = {i + 1: dict(parent=None, children=[]) for i in range(N)}

a_list = []
b_list = []
edge_dict = {}
edge_list = []

# エッジの情報
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    edge_list.append((a, b))
    edge_dict[(a, b)] = dict(a=a, b=b, color=None)
    a_list.append(a)
    b_list.append(b)

    node_dict[a]["children"].append(b)
    node_dict[b]["parent"] = a

# ルートを探す
root = list(set(a_list) - set(b_list))[0]

max_color_degree = -float("inf")

# 最悪で10 ** 5
for k, v in node_dict.items():
    d = len(v["children"])
    # 親がいない場合は、親の数も含める
    d = d + 1 if v["parent"] else d
    max_color_degree = max(max_color_degree, d)

COLOR_LIST = list(range(max_color_degree))


def color_edge(parent):
    next_node_list = node_dict[parent]["children"]
    parent_parent = node_dict[parent]["parent"]
    parent_edge_color = edge_dict[(parent_parent, parent)]["color"]
    ng_color = parent_edge_color

    # 最悪で10 ** 5
    color_index = 0
    for child in next_node_list:
        color = COLOR_LIST[color_index]
        if color == ng_color:
            color_index += 1
            color = COLOR_LIST[color_index]

        edge_dict[(parent, child)]["color"] = color
        color_index += 1
    return


parent = root
next_node_list = node_dict[root]["children"]
next_next_node_list = []

# 最悪で10 ** 5
color_index = 0
for node in next_node_list:
    color = COLOR_LIST[color_index]
    color_index += 1
    edge_dict[(parent, node)]["color"] = color

# 最悪で10 ** 5
while next_node_list:
    next_parent_list = []
    # 最悪で10 ** 5
    for node in next_node_list:
        color_edge(node)
        next_parent_list += node_dict[node]["children"]
    next_node_list = next_parent_list

color_list_str = ""
for edge in edge_list:
    a, b = edge
    color_list_str += str(edge_dict[(a, b)]["color"] + 1) + "\n"

print(max_color_degree)
print(color_list_str)


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

long long keta[4*12];
int main(){
	long long N, K; cin >> N >> K;

	vector<long long> A(N);
	for(int i=0; i<N; ++i){
		cin >> A[i];
		for(int k=0; k<4*12; ++k) keta[k] += ((A[i] >> k) & 1);
	}

	long long X = 0, ans = 0;
	for(int i=4*12-1; i>=0; --i){
		long long work = powl(2, i);
		if(keta[i] < (N + 1)/2 && X + work <= K){
			X += work;
			ans += (N-keta[i])*work;
		}else{
			ans += keta[i]*work;
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 1152
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
// #define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --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)
#define ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int dh[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dw[] = {-1, 0, 1, -1, 1, -1, 0, 1};

vvi m;
int cnt;
vector<vector<bool>> visited;

void next(int h, int w) {
    if (m[h][w] == 0) return;
    if (visited[h][w]) return;
    visited[h][w] = true;

    REP(i, 8) {
        int nh = h + dh[i];
        int nw = w + dw[i];
        if (!INRANGE(nh, 0, (int)m.size()-1)) continue;
        if (!INRANGE(nw, 0, (int)m[0].size()-1)) continue;
        next(nh, nw);
    }
}

void dfs(int h, int w) {
    if (m[h][w] == 0) return;
    if (visited[h][w]) return;
    visited[h][w] = true;

    cnt++;
    REP(i, 8) {
        int nh = h + dh[i];
        int nw = w + dw[i];
        if (!INRANGE(nh, 0, (int)m.size()-1)) continue;
        if (!INRANGE(nw, 0, (int)m[0].size()-1)) continue;
        next(nh, nw);
    }
}

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

    while (true)
    {
        int w, h;
        cin >> w >> h;
        if (w == 0 and h == 0) break;

        m = vvi();
        REP(_, h) {
            vi l(w);
            //cin >> l;
            REP(i, w) cin >> l[i];
            m.emplace_back(l);
        }

        visited = vector<vector<bool>>(h, vector<bool>(w, false));
        cnt = 0;
        REP(hi, h) {
            REP(wi, w) {
                dfs(hi, wi);
            }
        }

        cout << cnt << endl;
    }
    
    


    return 0;
}



Measured memory_bytes: 3296
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;

static const int INTINF = (2147483647);
static const ll LLINF = (9223372036854775807);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;

namespace Printer{
    template<class T>
    void print(T x){
        cout << x << endl;
    }

    template<class T>
    void print(T x, T y){
        cout << x << "," << y << endl;
    }

    template<class T>
    void print(vector<T> v){
        rep(i, v.size()){
            if(i) cout << " ";
            cout<< v[i];
        }
        cout << endl;
    }

    template<class T>
    void print(vector<vector<T> > vv){
        rep(i, vv.size()){
            rep(j, vv[i].size()){
                if(j) cout << " ";
                cout << vv[i][j];
            }
            cout << endl;
        }
    }

    void print(pair<int, int> p){
        cout << "(" << p.first << ", " << p.second << ")" << endl;
    }
};
using namespace Printer;

//--global--//



//----------//
vector<vector<int> > vv;
int ans[MAX*2];

void solve(int v, int bef, int x){
    ans[v] += x;
    rep(i, vv[v].size()){
        int u = vv[v][i];
        if(u == bef) continue;
        solve(u, v, ans[v]);
    }
    return;
}

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//

    int n, q;
    cin >> n >> q;
    vv.resize(n);
    rep(i, n-1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        vv[a].push_back(b);
        vv[b].push_back(a);
    }
    fill(ans, ans+n, 0);
    rep(i, q){
        int p, x;
        cin >> p >> x;
        p--;
        ans[p] += x;
    }
    solve(0, -1, 0);
    rep(i, n){
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << endl;
    
    return 0;
}


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> P(0);
  rep(i,n){
    int pi; cin>>pi;
    P.push_back(pi);
  }
  vector<int> Q(n);
  rep(i,n) Q.at(i)=P.at(i);
  sort(Q.begin(),Q.end());
  int ans;
  rep(i,n) if(P.at(i)!=Q.at(i)) ans++;
  if(ans<=2){
    cout<<"YES"<<endl;
  }else cout<<"NO"<<endl;
}

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

int main() {
  char X,Y;
  cin >> X >> Y;
  
  
  if(X == Y){
    cout << '=' << endl;
  }else{
    if(X > Y){
      cout << '>' << endl;
    }else{
      cout << '<' << endl; 
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
typedef long long int lld;
typedef unsigned long long int llu;
using namespace std;
const int m=1e9+7;

int main()
{ 
   int n;
   cin>>n;
   int a[n+1],i;
   a[0]=0;
   for(i=1;i<=n;i++) cin>>a[i];
   int cost[n+1];
   cost[0]=0;
   for(i=n;i>0;i--)
   {
   	  if(i==n) cost[i]=0;
   	  else if(i==n-1) cost[i]=abs(a[i]-a[i+1]);
   	  else
   	  {
   	  	cost[i]=min(abs(a[i]-a[i+1])+cost[i+1],abs(a[i]-a[i+2])+cost[i+2]);
		 }
   }
   cout<<cost[1]<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
    int i,h,len,j,n;
    h=3;
        scanf("%d",&i);
        j=i%10;
        n=i/10;
        if(j==9||n==9){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }

    return 0;
}


Measured memory_bytes: 128
import java.util.*;
import java.lang.*;

class Main {
    public static void main (String[] args)  {
        Scanner scanner = new Scanner(System.in);
        int numberOfCoins = scanner.nextInt();
        int total = scanner.nextInt();
        if((numberOfCoins*500)>=total){
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }


    }
}



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

int main() {
 int a,b,c,d;
 cin >> a >> b >> c >> d;
  if(a <=b){
    if(c <= d ){
    cout << a+c << endl;
    }
    else{
    cout << a+d << endl;
    }
  }
  
  else{
   if(c <= d){
   cout << b+c << endl;
   }
   else{
   cout << b+d << endl;
   }
  }

}

Measured memory_bytes: 256
#include<iostream>
#define _USE_MATH_DEFINES
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;
typedef pair<ll,ll> P;
typedef map<ll,ll> MP;
typedef priority_queue<ll> PQ;
typedef stack<ll> ST;
typedef queue<ll> QUE;
#define pb push_back
#define st first
#define nd second
#define SZ(x) ((int)(x).size())
#define FOR(i,s,n) for(int i=(int)(s); i< (int)(n); i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define each(x,c) for(auto x: (c))
#define LB(x,a) lower_bound(all(x), a)
#define UB(x,a) upper_bound(all(x), a)
const ll mod=1e9+7;
const ll INF=1e18;
const double EPS=1.0e-10;
const double PI=M_PI;

int N;
vector<char> C={'a','b','c','d','e','f','g','h','i','j'};
void f(string S,int k){
    if(SZ(S)==N){
        cout<<S<<endl;
        return;
    }
    rep(i,k){
        f(S+C[i],k);
    }
    f(S+C[k],k+1);
    return;
}

int main(){
    cin>>N;
    string S;
    f(S,0);
    return 0;
}

Measured memory_bytes: 1536
H, W, K = map(int, input().split())
c = [input() for _ in range(H)]

ans = 0
for R in range(2**H):
    for C in range(2**W):
        black = 0
        for i in range(H):
            for j in range(W):
                if (not (R >> i) & 1) and (not (C >> j) & 1) and (c[i][j] == '#'):
                    black += 1
        if black == K:
            ans += 1
print(ans)


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N;
  cin>>N;
  vector<int>H(N);
  for(int i=0;i<N;i++)cin>>H[i];
  int memo=0;
  bool ok=true;
  for(int i=0;i<N;i++){
    if(memo<=H[i]-1)memo=H[i]-1;
    else if(memo<=H[i])memo=H[i];
    else ok=false;
  }
  if(ok)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
char s[103];
int n;
int main()
{
  scanf("%d\n",&n);
  for (int a=1;a<=n;a++)
  {
    s[a]=getchar();
  }
  int tmp=0;
  for (int i=1;i<=n;i++)
  {
    if (s[i]=='(') tmp++; else tmp--;
    if (tmp<0)
    {
      putchar('(');
      tmp++;
    }
  }
  for (int a=1;a<=n;a++) putchar(s[a]);
  for (int a=1;a<=tmp;a++) putchar(')');
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]
    a_list = [[int(x) for x in sys.stdin.readline().split()][0]
              for _ in range(N)]

    logger.debug('{} {}'.format(N, a_list))

    max1, max2 = sorted(a_list, reverse=True)[:2]

    for a in a_list:
        if a == max1:
            print(max2)

        else:
            print(max1)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
1
4
3"""
        output = """4
3
4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
5
5"""
        output = """5
5"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
1"""
        output = """1
1"""
        self.assertIO(input, output)

Measured memory_bytes: 122072
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cmath>
#include <string>
#include <cstdio>
using namespace std;
typedef long long int ll;
static const int N = 1000;

int lcs(string X, string Y) {
	int C[N + 1][N + 1];
	int M = X.size();
	int N = Y.size();
	int maxL = 0;
	X = ' ' + X;
	Y = ' ' + Y;
	for (int i = 0; i <= M; i++) C[i][0] = 0;
	for (int i = 1; i <= N; i++) C[0][i] = 0;

	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			if (X[i] == Y[j]) {
				C[i][j] = C[i - 1][j - 1] + 1;
			}
			else {
				C[i][j] = max(C[i - 1][j], C[i][j - 1]);
			}
			maxL = max(maxL, C[i][j]);
		}
	}
	return maxL;
}

int main() {
	string S1, S2;
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> S1 >> S2;
		cout << lcs(S1, S2) << endl;
	}
}



Measured memory_bytes: 7080
#include <iostream>
#include <vector>
#include <string>

int main()
{
  int A, B;
  std::cin >> A >> B;

  if (A % 2 == 1 && B % 2 == 1) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdlib.h>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main(void) {
	unsigned long int N = 0;
	double a[1001], sum = 0;
	cin >> N;
	
	for(int i = 0 ; i < N ; i++){
	    cin >> a[i];
	    sum += 1.000000 / a[i];
	}
    
    cout << 1.000000 / sum << endl;
	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
p=[0]*(n+1)
for _ in range(m):
  l,r=map(int,input().split())
  p[l-1]+=1
  p[r]-=1
for i in range(n):
  p[i+1]+=p[i]
print(p.count(m))

Measured memory_bytes: 12852
#include<stdio.h>
#include<stdlib.h>

#define N 100
void print(int A[], int m){
  int i;
  for(i = 0; i < m; i++){
    if(i > 0 && i < m) printf(" ");
    printf("%d",A[i]);  
  }
  printf("\n");
}


main(){
  int i,n;
  int j=0;
  int v=0;
  int A[N];
  scanf("%d",&n);
  

  for (i= 0; i < n;i++) {
    scanf("%d",&A[i]);
    if(i<n-1) printf("%d ",A[i]);
    else printf("%d",A[i]);      
  }
  printf("\n");
  for (i= 1; i < n; i++){ //Sorting starts after A[0].
    v = A[i]; //A[i] records to v
    j = i - 1;
    while (j >= 0 && A[j] > v){
      A[j+1] = A[j];
      j--;
    }
      A[j+1] = v;
      print(A, n);
  }
  return 0;    
}

Measured memory_bytes: 604
def main():
    a=[int(input()) for _ in range(int(input()))]
    idx = -1
    m = -1
    n = -1
    for i, v in enumerate(a):
        if v >= m:
            idx = i
            n = m
            m = v
        elif v >= n:
            n = v
    for i, v in enumerate(a):
        if idx == i:
            print(n)
        else:
            print(m)
    
if __name__ == "__main__":
    main()

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

int main()
{
    string s[12];
    int h,w,k;
    cin>>h>>w>>k;
    for(int i=0;i<h;i++)
        cin>>s[i];
    int ans=1e9;
    for(int i=0;i<(1<<(h-1));i++){
        int x=__builtin_popcount(i);
        //cout<<x<<endl;
        int a[x+1]={0},ok=1,cnt=x;
        for(int j=0;j<w;j++){
            int c[x+1]={0},p=0,mx=0;
            for(int u=0;u<h;u++){
                c[p]+=s[u][j]-'0';
                mx=max(mx,c[p]);
                if(i&(1<<u)) p++;
            }
            if(mx>k) {ok=0;break;}
            mx=0;
            for(int u=0;u<=x;u++){
                mx=max(a[u]+c[u],mx);
            }
            if(mx>k) memset(a,0,sizeof(a)),cnt++;
            for(int u=0;u<=x;u++) a[u]+=c[u];
        }
        if(ok) ans=min(ans,cnt);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
// ~/SolverToBe/Developers/Corvus
// ~/sudo apt-get verdict Accpeted

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>
#include <assert.h>
#include <complex>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 200005, M = 505;
const ll MOD = 1e9 + 7;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n, m, cnt, cmp, idx[N], low[N], comp[N], val[N], compH[N];
bool inStack[N];
stack<int> stk;
vector<vector<int> > g;

inline int Not(int u) {
	return u >= n ? u - n : u + n;
}

inline void add(int a, int b) {
	g[Not(a)].push_back(b);
	g[Not(b)].push_back(a);
}

void dfs(int u) {
	idx[u] = low[u] = ++cnt;
	inStack[u] = 1;
	stk.push(u);
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!idx[v])
			dfs(v);
		if (inStack[v])
			low[u] = min(low[u], low[v]);
	}
	if (idx[u] == low[u]) {
		while (1) {
			int v = stk.top();
			stk.pop();
			inStack[v] = 0;
			comp[v] = cmp;
			if (v == u) break;
		}
		compH[cmp++] = u;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	g.resize(2 * n);
	for (int i = 0, a, b, c; i < m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		a--, b--;
		if (c & 1) {
			add(Not(a), Not(b));
			add(a, b);
		}
		else {
			add(Not(a), b);
			add(a, Not(b));
		}
	}
	for (int i = 0; i < 2 * n; i++)
		if (!idx[i]) 
			dfs(i);
	printf("%d\n", cmp / 2);
	return 0;
}

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

bool solve (const vector<string>& W){
  const int n = W.size();
  for(int i = 0; i < n-1; i++){
    if(W[i].back() != W[i + 1].front()){
      return false;
    }
  }
  
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      if(W[i] == W[j]){
        return false;
      }
    }
  }
  return true;
}
vector<string> input(){
  int n;
  cin>> n;
  vector<string>W(n);
  for(int i= 0; i < n; i++){
    cin >> W[i];
  }
  return W;
}
int main(){
  const vector <string> W = input();
  if(solve(W)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}
      

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
a.sort()
yaku = set()


import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
#a = factorization(n)
#b = []
#for i,j in a:
#  b.append(i)
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
#素因数列挙
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  table = set(table)
  table = list(table)
  return table


a1 =divisor(a[0])
a2 = divisor(a[1])
for i in a1:
    yaku.add(i)
for i in a2:
    yaku.add(i)
yaku = list(yaku)
yaku.sort()
yaku = yaku[::-1]
for i in yaku:
    flag = 1
    for j in range(n):
        if a[j] % i == 0:
            continue
        else:
            if flag:
                flag = 0
            else:
                break
    else:
        print(i)
        exit()

Measured memory_bytes: 59632
using static System.Math;
using System.Linq;
using System;

public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, int.Parse);
        var ans = int.MaxValue;
        for (int i = 0; i <= 3; i++)
        {
            var t = getAns(a, n, i);
            if (t != -1) ans = Min(ans, t);
            var t2 = getAns2(a, n, i);
            if (t2 != -1) ans = Min(ans, t2);
        }
        Array.Reverse(a);
        for (int i = 0; i <= 3; i++)
        {
            var t3 = getAns(a, n, i);
            if (t3 != -1) ans = Min(ans, t3);
            var t4 = getAns2(a, n, i);
            if (t4 != -1) ans = Min(ans, t4);
        }
        Console.WriteLine(ans);
    }
    static int getAns2(int[] a, int n, int L)
    {
        if (L < a[0]) return -1;
        var b = new int[n];
        b[0] = L;
        var p = 1;
        while (p < n - 1)
        {

            var d = Max(0, a[p] - b[p]);
            b[p] += d;
            b[p + 1] = d;
            p++;
        }
        if (a[n - 1] > b[n - 1]) b[n - 1] = a[n - 1];
        return b.Sum();

    }
    static int getAns(int[] a, int n, int L)
    {
        var b = new int[n];

        b[0] = L;
        if (a[0] > L) b[0] = a[0];
        b[1] = L;
        var p = 1;
        while (p < n - 1)
        {

            var d = Max(0, a[p] - b[p]);
            b[p] += d;
            b[p + 1] = d;
            p++;
        }
        if (a[n - 1] > b[n - 1]) b[n - 1] = a[n - 1];
        return b.Sum();
    }
}


Measured memory_bytes: 18276
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <numeric>
#include <tuple>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

int main() {
  size_t h, w, k;
  scanf("%zu %zu %zu", &h, &w, &k);

  std::vector<std::string> s(h);
  std::vector<std::vector<int>> a(h, std::vector<int>(w, 0));
  int st = 0;
  for (size_t i = 0; i < h; ++i) {
    char buf[312];
    scanf("%s", buf);
    s[i] = buf;
    for (size_t j = 0; j < w; ++j) {
      if (s[i][j] == '#') {
        a[i][j] = ++st;
      }
    }
  }

  for (size_t j = 0; j < w; ++j) {
    for (size_t i = 1; i < h; ++i) {
      if (a[i][j] == 0) a[i][j] = a[i-1][j];
    }
    for (size_t i = h-1; i--;) {
      if (a[i][j] == 0) a[i][j] = a[i+1][j];
    }
  }

  for (size_t i = 0; i < h; ++i) {
    for (size_t j = 1; j < w; ++j) {
      if (a[i][j] == 0) a[i][j] = a[i][j-1];
    }
    for (size_t j = w-1; j--;) {
      if (a[i][j] == 0) a[i][j] = a[i][j+1];
    }
  }

  for (size_t i = 0; i < h; ++i)
    for (size_t j = 0; j < w; ++j)
      printf("%d%c", a[i][j], j+1<w? ' ': '\n');
}


Measured memory_bytes: 1152
#include <stdio.h>
int main(void){
    int i, N, A[200], c[200], min;

    scanf("%d",&N);

    for (i = 0; i < N;i++){
        c[i] = 0;
    }

    for (i = 0; i < N; i++)
    {
        scanf("%d", &A[i]);
        while (A[i]%2 != 1 && A[i]/2>=1)
        {
            A[i] /= 2;
            c[i]++;
        }
    }

    min = c[0];

    for (i = 1; i < N;i++){
        if(min>c[i]){
            min = c[i];
        }
    }

    printf("%d", min);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

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;
}
void cmps(vector<int>&v,int &i){
	i=lower_bound(all(v),i)-v.begin();
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;

int N,K;
int cnt[105];
signed main(){
	cin>>N>>K;
	rep(i,K){
		int d;cin>>d;
		while(d--){
			int j;cin>>j;j--;cnt[j]++;
		}
	}
	int ans=0;
	rep(i,N)if(!cnt[i])ans++;
	cout<<ans<<endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
/*bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
} */
int main()
{
     ll t,b;
     cin>>t>>b;
     cout<<min(t%b,abs((t%b)-b))<<endl;

}


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

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    int res=(1<<30);
    for(int i=-100;i<=100;i++)
    {
        int x=0;
        for(int j=0;j<n;j++) x+=(a[j]-i)*(a[j]-i);
        res=min(res,x);
    }
    cout << res << "\n";
    return 0;
}


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

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    int cnt = 0;
    for (int i = 0; i < n-2; i++) {
        if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') {
            cnt++;
        }
    }
    cout << cnt;

    return 0;
}


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

int main() {
	int n;cin>>n;
	map<int,int> m;
	int ans=0;
	for(int i=0;i<n;i++){
		int a;cin>>a;
		if(m[a]==0){
			ans++;
			m[a]=1;
		}else{
			ans--;
			m[a]=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 4864
#include<iostream>
#include<climits>
using namespace std;
int main(){
    int n,x;
    cin >> n >> x;
    int ans=0;
    int min = INT_MAX;
    int m[n];
    for (int i=0; i<n; i++){
        cin >> m[i];
        if(min > m[i]){
            min = m[i];
        }
        ans += m[i];
    }
    n +=  (x - ans) / min;
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
a,b,k = map(int,input().split())

for i in range(k):
    if i%2 == 0:
        if a%2:
            a -= 1
        a -= a//2
        b += a
    else:
        if b%2:
            b -= 1
        b -= b//2
        a += b
    
print(a,b)

Measured memory_bytes: 9176
n=int(input())
k=[]
def a(i):
    if i==0:
        return 26
    else:
        return i
while n>26:
    k+=[chr(96+a(n%26))]
    if n%26==0:
        n=n//26-1
    else:
        n//=26
k+=[chr(96+a(n))]
print("".join(k[::-1]))

Measured memory_bytes: 9180
#include <bits/stdc++.h>
#define INF 1e15
using namespace std;

typedef long long ll;

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

    int n,m;
    cin>>n>>m;
    ll d[n][n]={};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            d[i][j]=INF;
        }
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        d[a-1][b-1]=-c;
    }
    
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]*=-1;
        }
    }

    if(d[0][0]==0)cout<<d[0][n-1]<<endl;
    else cout<<"inf"<<endl;
}

Measured memory_bytes: 8064
input = raw_input


N = int(input())
A = list(map(int, input().split(" ")))

L = [[0,0] for i in range(N)]
for i in range(N):
    L[i][0] = i + 1
    L[i][1] = A[i]
L.sort(key = lambda x: x[1])
print(" ".join(map(lambda x: str(x[0]), L)))


Measured memory_bytes: 54860
import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])

if __name__ == '__main__':
	main()

Measured memory_bytes: 14328
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <bitset>
#include <iterator>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <random>
#include <numeric>
#include <set>
#include <cassert>
#include <cmath>
#include <cinttypes>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}
template<class T> T read_val() { throw 1; }
template<> int read_val() { int tmp; scanf("%" PRId32, &tmp); return tmp; }
template<> long long read_val() { long long tmp; scanf("%" PRId64, &tmp); return tmp; }
auto read_int = read_val<int>; auto read_long = read_val<long long>;
template<class T> void scanf_vec(vector<T>& vec) { for (int i = 0; i < vec.size(); i++) vec[i] = read_val<T>(); }

#define MOD 1000000007
#define inf 2000000000
#define FWT_SIZE 2000000
#define pii pair<int,int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define sort_all(x) sort(all(x))
#define make_unique(x) (x).erase(unique(all(x)), (x).end())



int main() {

#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;
	vector<int> p(n);

	cin >> p;
	stack<int> min_p;
	int nearest = n, ans = 0, been_none=0;

	stack<pii> max_a, max_b;

	for (int j = p.size() - 1; j >= 0; j--)
	{
		while (min_p.size() > 0 && p[min_p.top()] >= p[j])
			min_p.pop();

		bool changes = false;
		if (min_p.size() > 0 && p[j] > p[min_p.top()])
		{
			changes = min_p.top() < j + k;
			nearest = min(nearest, min_p.top());
		}
		int curr_max = 0;
		if (max_a.size() > 0) curr_max = max(curr_max, max_a.top().second);
		if (max_b.size() > 0) curr_max = max(curr_max, max_b.top().second);
		if (j + k < n && p[j + k] < curr_max)
			changes = true;

		min_p.push(j);

		if (j + k - 1 < n && nearest < j + k && (j+k==n || changes))
		{
			ans++;
		}

		if (j + k - 1 < n && nearest >= (j + k))
			been_none = 1;

		if (k > 1)
		{
			if (max_a.size() > 0) max_a.push({ p[j], max(p[j],max_a.top().second) });
			else max_a.push({ p[j], p[j] });

			while (max_a.size() + max_b.size() > (k - 1))
				max_b.pop();

			if (max_a.size() == (k - 1))
			{
				while (max_b.size()) max_b.pop();
				int max_v = 0;
				while (max_a.size() > 0)
				{
					max_v = max(max_v, max_a.top().first);
					max_b.push({ max_a.top().first, max_v });
					max_a.pop();
				}
			}
		}
	}

	cout << ans+been_none;

	return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const ll mol = 1e9 + 7;
const int maxn = 2e5;
 
int a[maxn + 11],b[maxn + 11];
 
int main() {
	int k,n;
	scanf("%d %d",&n,&k);
	int ca = 0 , cb = 0;
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d",&x);
		if (x >= 0) a[++ca] = x;
		else b[++cb] = -x;
	}
	sort(a + 1 , a + 1 + ca , [&](int x,int y) { return x > y; });
	sort(b + 1 , b + 1 + cb , [&](int x,int y) { return x > y; });
	if (ca == 0) {
		ll ans = 1;
		if (k % 2 == 1) {
			for (int i = cb; i >= cb - k + 1; i--)
				ans = ans * b[i] % mol;
			ans = mol - ans;
		}
		else {
			for (int i = 1; i <= k; i++)
				ans = ans * b[i] % mol;
		}
		printf("%lld\n" , ans);
		return 0;
	}
	if (n == k) {
		ll ans = 1;
		for (int i = 1; i <= ca; i++)
			ans = ans * a[i] % mol;
		for (int i = 1; i <= cb; i++)
			ans = ans * b[i] % mol;
		if (cb & 1) ans = mol - ans;
		printf("%lld\n" , ans);
		return 0;
	}
	int u,d;
	if (ca >= k) { u = k; d = 0; }
	else if ((k - ca) % 2 == 0) {
		u = ca; d = k - ca;
	}
	else {
		u = ca - 1; d = k - ca + 1;
	}
	while (1) {
		if (u < 2 || d + 2 > cb) break;
		if (1ll * a[u] * a[u - 1] > 1ll * b[d + 1] * b[d + 2]) break;
		u -= 2; d += 2;
	} 
	ll ans = 1;
	for (int i = 1; i <= u; i++) ans = ans * a[i] % mol;
	for (int i = 1; i <= d; i++) ans = ans * b[i] % mol;
	printf("%lld\n" , ans);
} 


Measured memory_bytes: 4608
#include<iostream>
using namespace std;
#define MAX 100000
int A[MAX],n;

int partition(int p,int r){
    int a=0,b=0,t;
    int x=A[r];
    for(int i=p;i<=r;i++){
        if(A[i]<=x){
            t=A[a];
            A[a] = A[i];
            A[i]=t;
            a++;
        }
    }
    return a-1;
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> A[i];
    int idx = partition(0,n-1);
    for(int i=0;i<n;i++){
        cout << (i?" ":"") << (i==idx?"[":"") << A[i] << (i==idx?"]":"");
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3376