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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vi32 ans(n);
  rep(i, n - 1) {
    int a;
    cin >> a;
    a--;
    ans[a]++;
  }
  cout << ans << endl;
}

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

int X,Y;
string board[110];
bool goodx[110],goody[110];
int main(void){

	cin>>X>>Y;
	for(int i=0;i<X;i++){
		cin>>board[i];
	}
	
	for(int i=0;i<X;i++){
		for(int j=0;j<Y;j++){
			if(board[i][j]=='#'){
				goodx[i]=true;
				goody[j]=true;
	}	}	}
	
	for(int i=0;i<X;i++){
		if(goodx[i]){
			for(int j=0;j<Y;j++){
				if(goody[j]){
					cout<<board[i][j];
				}
			}
			cout<<endl;
	}	}
	
	return 0;
}

Measured memory_bytes: 256
import kotlin.math.*

fun list() = readLine()!!.split(" ").map {it.toInt()}

fun main() {
	val (r,c,k) = list()
	val goods = Array(r) {LongArray(c) {0L}}
	for(i in 1..k) {
		val (r,c,v) = list()
		goods[r-1][c-1] = v.toLong()
	}

	val dp = Array(r) {Array(c) {LongArray(4) {0L}}}

	for(i in 0 until r) {
		for(j in 0 until c) {
			for(k in 0..3) {
				if(i>0)
					dp[i][j][0] = max(dp[i][j][0],dp[i-1][j][k])
				if(j>0)
					dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
			}
			for(k in 3 downTo 1)
				dp[i][j][k] = max(dp[i][j][k],dp[i][j][k-1]+goods[i][j])
		}
	}
	println(dp[r-1][c-1].max())
}


Measured memory_bytes: 741532
#include<iostream>
#include<string>
using namespace std;
char a[105][105];
char b[105][105];
int n,m;
void asd(int q,int w){
    int zong=0;
    if(a[q-1][w-1]=='#')zong++;
    if(a[q-1][w]=='#')zong++;
    if(a[q-1][w+1]=='#')zong++;
    if(a[q][w-1]=='#')zong++;
    if(a[q][w+1]=='#')zong++;
    if(a[q+1][w-1]=='#')zong++;
    if(a[q+1][w]=='#')zong++;
    if(a[q+1][w+1]=='#')zong++;
    b[q][w]=zong+'0';
    return;
}
int main(){
    string s;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++){
            a[i][j]=s[j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='.')asd(i,j);
            else b[i][j]='#';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<b[i][j];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = input[0];
            var m = input[1];
            var pass = input[2];
            var c = new int[n];
            var a = new int[n, m];

            int res = int.MaxValue;

            for (int i = 0; i < n; i++)
            {
                var input1 = Console.ReadLine().Split().Select(int.Parse).ToArray();
                c[i] = input1[0];
                for (int j = 0; j < m; j++)
                    a[i, j] = input1[j + 1];
            }

            for (int i = 0; i < 1 << n; i++)
            {
                int price = 0;
                int[] skills = new int[m];
                for (int j = 0; j < n; j++)
                {
                    if ((i >> j & 1) == 1)
                    {
                        price += c[j];
                        for (int k = 0; k < m; k++)
                            skills[k] += a[j, k];
                    }
                }
                if (skills.All(x => x >= pass))
                    res = Math.Min(res, price);
            }

            if (res == int.MaxValue) res = -1;

            Console.Write(res);
        }

    }
}


Measured memory_bytes: 28692
N = int(input())
c = 0
A = list(map(int,input().split()))
ans = {}
for i in range(N):
    a = A[i]
    if a not in ans:
        ans[a] = 1
    else:
        c = 1
        break
if c == 0:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 32944
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n, m = map(int, raw_input().split())
            if n == 0 and m == 0:
                break
            sn = []
            for i in range(n):
                sn.append(input())
            sm = []
            for i in range(m):
                sm.append(input())
            diff = (sum(sn) - sum(sm)) * 1.0 / 2
            # if diff != int(diff):
            #     print -1
            #     continue
            ans = []
            flg = False
            for i in sn:
                for j in sm:
                    if i - j == diff:
                       flg = True
                       ans.append((i, j))
            if flg == False:
                print -1
                continue
            min_points = min(i + j for i, j in ans)
            for i, j in ans:
                if i + j == min_points:
                    print ' '.join([str(i), str(j)])
                    break
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Measured memory_bytes: 5388
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc;

	static final int INF=1<<28;
	static final double EPS=1e-9;

	void run(){
		sc=new Scanner(System.in);
		for(; sc.hasNext();){
			int n=sc.nextInt();
			String ans="";
			for(int i=0; i<10; i++){
				if((n&(1<<i))!=0)
					ans+=((1<<i)+" ");
			}
			println(ans.substring(0, ans.length()-1));
		}
		sc.close();
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 12000
a = gets.chomp.to_i

ac = 0
wa = 0
tle = 0
re = 0

a.times do |i|
  result = gets.chomp
  case result
    when 'AC'
    	ac += 1
    when 'WA'
    	wa += 1
	when 'TLE'
    	tle += 1
    when 'RE'
    	re += 1
  	else
  end
end

puts "AC x #{ac}"
puts "WA x #{wa}"
puts "TLE x #{tle}"
puts "RE x #{re}"



Measured memory_bytes: 14272
import Data.Array
import Data.Array.ST
import Control.Monad

eratos::Int->[Int]
eratos 0 = []
eratos 1 = []
eratos 2 = [2]
eratos n = sieve [2..n] n
              where
                sieve::[Int]->Int->[Int]
                sieve [] _     =[]
                sieve (x:xs) k = if  x^2 > k then (x:xs) else x:(sieve (filter (\y->mod y x /= 0) xs) k)



create_eratos_flag::Int->Array Int Bool
create_eratos_flag n =runSTArray $ do
                    ar<-newArray (2,n) False
                    forM_ (eratos n) (\p -> writeArray ar p True)
                    return ar

create_ans_sheet::Int->Array Int Int
create_ans_sheet n = let flag = create_eratos_flag n in
                     let ans_ls = fold_map_ls (\count -> \i -> count+if (flag!i) && (flag!(div (1+i) 2)) then 1 else 0) 0 [3..n] in
                     listArray (1,n) (0:0:ans_ls)


fold_map_ls::(a->b->a)->a->[b]->[a]
fold_map_ls  _ _ []     = []
fold_map_ls  f i (x:xs) = (f i x):(fold_map_ls f (f i x) xs)

ans::Int->Int->Int
ans l r = (create_ans_sheet 100000)!r -(create_ans_sheet 100000)!(max (l-1) 1)

n_treat::Int->IO()
n_treat 0 = return ()
n_treat n = do
  lrc<-getLine
  let l:r:[]= map read (words lrc)
  print (ans l r)
  n_treat (n-1)

main::IO()
main=do
  n<-getLine
  n_treat (read n)


Measured memory_bytes: 24444
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    --K;
    vec<vec<ll>> dp(H + 1, vec<ll>(W + 1, 0));
    dp[0][0] = 1;

    rep(h, H) {
        rep(i, 1 << (W - 1)) {
            bool flag = true;
            for (int j = 1; j <= (W - 1); ++j) {
                bool a = (i >> j) & 1;
                bool b = (i >> (j - 1)) & 1;
                if (a && b) flag = false;
            }
            if (!flag) continue;

            rep(j, W) {
                if (!((i >> j) & 1)) {
                    if(j==0) dp[h+1][j] += dp[h][j];
                    else if(!((i >> (j-1)) & 1)) dp[h+1][j] += dp[h][j];
                    else dp[h+1][j] += dp[h][j-1];
                } else {
                    dp[h+1][j] += dp[h][j+1];
                }
                dp[h+1][j] %= (ll)1e9+7;
            }
        }
    }

    cout << dp[H][K] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
const int maxn=1e5+10;
using namespace std;

ll quickqow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans*=a;
		a*=a;b>>=1;
	}
	return ans;
}
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{ 
	int n,m,temp;
	cin>>n>>m;
	if(m>n) temp=m,m=n,n=temp;
	for(int i=1;i<=n;i++) cout<<m;
	cout<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
    int h,w;
    cin >> h >>w;
    char s[h][w];
    REP(i,h){
        REP(j,w){
            cin >> s[i][j];
        }
    }
    REP(i,h){
        REP(j,w){
            cout <<s[i][j];
        }
        cout<<endl;
        REP(j,w){
            cout <<s[i][j];
        }
        cout<<endl;
    }
    cout << endl;
}

Measured memory_bytes: 384
#include<cstdio>
#include<vector>
#include<bitset>
#define N 100000
using namespace std;

vector<int> vecin[N+1];
bitset<N+1> viz;

int dfs(int nod=1){
    viz.set(nod);
    bool ans=false;
    
    for(int i=0;i<vecin[nod].size();i++){
        int now=vecin[nod][i];
        
        if (viz[now]==false){
            int r=dfs(now);
            
            if (r==-1) return -1;
            if (r==1 &&ans==1) return -1;
            ans|=r;
        }
    }
    
    return (ans^1);
}

int main(){
    int n,i;
    
    scanf ("%d",&n);
    
    for(i=1;i<=n;i++){
        int a,b;
        scanf ("%d%d",&a,&b);
        
        vecin[a].push_back(b);
        vecin[b].push_back(a);
    }
    
    int ans=dfs();
    
    if (ans==0) printf ("Second");
    else printf ("First");
    
    return 0;
}


Measured memory_bytes: 5888
n,m=map(int,input().split())
hlist=list(map(int,input().split()))
remlist=[]
for i in range(m):
    a,b=map(int,input().split())
    ah=hlist[a-1]
    bh=hlist[b-1]
    if ah > bh:
        remlist.append(b-1)
    elif bh > ah:
        remlist.append(a-1)
    else:
        remlist.extend([a-1,b-1])

remset=set(remlist)
print(n-len(remset))

Measured memory_bytes: 20108
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
// NOTE: one-indexed
template <typename T> vector<vector<T>> build(int n, int m, const vector<vector<T>>& a) {
    vector<vector<T>> s(n + 1, vector<T>(m + 1));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    return s;
}
template <typename T> T query(const vector<vector<T>>& s, int r1, int c1, int r2, int c2) {
    return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    for(int i = 0; i < m; i++) {
        int L, R;
        cin >> L >> R;
        a[L][R]++;
    }
    auto s = build(n, n, a);
    for(int i = 0; i < q; i++) {
        int p, q;
        cin >> p >> q;
        cout << query(s, p, p, q, q) << endl;
    }
    return 0;
}


Measured memory_bytes: 2944
# -*- coding: utf-8 -*-
"""
B - ATCoder
https://atcoder.jp/contests/abc122/tasks/abc122_b

"""
import sys
import re

def solve(S):
    return max([len(f) for f in re.findall(r'[ACGT]+', S)], default=0)


def main(args):
    S = input()
    ans = solve(S)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3188
import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n = int(input())
x = list(map(int, input().split()))
y = sorted(x)
a = y[n // 2 - 1]
b = y[n // 2]
# print("a =", a)
# print("b =", b)
for i in x:
    if i <= a:
        print(b)
    else:
        print(a)


Measured memory_bytes: 27248
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

int main(int argc, void **argv)
{
	long long n, i;
	long long l[10000];
    long long sum = 0;
    long long max = 0;

	scanf("%lld", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%lld", &l[i]);
	}

	for (i = 0; i < n; i++)
	{
        if( max < l[i] ) {
            sum += max;
            max = l[i];
        } else {
            sum += l[i];
        }
	}

    if( sum > max ) {
        puts("Yes");
    } else {
        puts("No");
    }

	return 0;
}


Measured memory_bytes: 128
from itertools import permutations
n, m = map(int, input().split())
edge = set()

ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    edge.add((a, b))

is_used = set([])
for per in permutations(range(2, n + 1)):
    flag = True
    if (1, per[0]) not in edge:
        continue
    for i in range(n - 2):
        if (per[i], per[i + 1]) not in edge and (per[i + 1], per[i]) not in edge:
            flag = False
            break
    if flag:
        ans += 1

print(ans)


Measured memory_bytes: 3064
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace atcoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());

            long ans = 0;

            for (int i = 1; i < N; i++)
            {
                for (int j = 1; j < N / i + 1; j++)
                {
                    if (i * j >= N) continue;

                    ans++;
                }
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 27464
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        ArrayList<Integer> h = new ArrayList<Integer>();
        for (int i = 0; i < 10; ++i) {
            h.add(s.nextInt());
        }
        Collections.sort(h);
        Collections.reverse(h);
        for (int i = 0; i < 3; ++i) {
            System.out.println(h.get(i));
        }
    }
}

Measured memory_bytes: 17192
#include <stdio.h>

int main(void){
     
	int i,n;
	char str[100];
	for( ;fgets(str,sizeof(str),stdin)!=NULL; ){
		sscanf(str,"%d",&n); i=1;
		while(n>1){
			if(n%2==1)
				printf("%d ",i);
			i*=2;
			n/=2;
		}
		printf("%d\n",i);
	}	
	return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,strt,end) for(long long i = strt;i < end;i++)

int main(){
    long n,m;
    cin >> n >> m;
    long total = 0;
    rep(i,0,m){
        long a;
        cin >> a;
        total += a;
    }
    total = n - total;
    if(total < 0){
        cout << "-1" << endl;
    }else{
    cout << total<< endl;
    }
    //--------------
    return 0;
}

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

int main(void){
    int N, M;
    std::cin >> N >> M;
    std::vector<int> roads(N, 0);
    for (int i=0; i<M; ++i){
        int a, b;
        std::cin >> a >> b;
        ++roads.at(a - 1);
        ++roads.at(b - 1);
    }
        
    for (int i=0; i<N; ++i){
        std::cout << roads.at(i) << std::endl;
    }

    return 0;
}


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

string to_string(string s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define db(...) 42
#endif

using ll = long long;

#define X first
#define Y second
#define pnt pair<int,int>

int dist(pnt a, pnt b) {
  return abs(b.X - a.X) + abs(b.Y - a.Y);
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<pnt> s(n), c(m);
  for (auto &i : s)
    cin >> i.X >> i.Y;
  for (auto &i : c)
    cin >> i.X >> i.Y;
  for (int i = 0; i < n; i++) {
    int mind = INT_MAX;
    int pntid = 0;
    for (int j = 0; j < m; j++) {
      int curdis = dist(s[i], c[j]);
      if (mind > curdis) {
        mind = curdis;
        pntid = j;
      }
    }
    cout << pntid + 1 << '\n';
  }
  return 0;
}


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

struct data{
    int y,x,cost;
    data(int a,int b,int c):y(a),x(b),cost(c){}
    bool operator<(const data &d)const{
        return cost>d.cost;
    }
};

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

char fld[50][50];
int H,W;
int sx,sy,gx,gy;
int main(){
    cin>>H>>W;
    for(int i=0;i<H;i++)cin>>fld[i];

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            if(fld[i][j]=='S'){
                sy=i;sx=j;
            }
            if(fld[i][j]=='G'){
                gy=i;gx=j;
            }
        }
    }


    int dist[50][50];
    fill_n(*dist,50*50,1001001001);

    priority_queue<data>Q;
    Q.push(data(sy,sx,0));
    dist[sy][sx]=0;

    while(Q.size()){
        data d=Q.top();Q.pop();

        if(dist[d.y][d.x]<d.cost)continue;

        for(int i=0;i<4;i++){
            int o=0,x=0;
            for(int j=1;j<=3;j++){
                int ny=d.y+dy[i]*j;
                int nx=d.x+dx[i]*j;
                if(ny<0||ny>=H||nx<0||nx>=W||fld[ny][nx]=='#')break;

                if(fld[ny][nx]=='o')o++;
                if(fld[ny][nx]=='x')x++;
                int ncost=d.cost+(x?j+2:min(o+(j-o)*2,2+j));
                if(dist[ny][nx]<=ncost)continue;
                dist[ny][nx]=ncost;
                Q.push(data(ny,nx,ncost));
            }
        }
    }
    
    cout<<dist[gy][gx]<<endl;
    return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long int
int32_t main()
{
    IOS;
    string s;cin>>s;
    for(ll i=0;i<s.length();++i)
    {
        if(s[i]=='?')
        cout<<"D";
        else
        cout<<s[i];
    }

} 


Measured memory_bytes: 3784
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <float.h>
using namespace std;

#define N 100

char s[N];

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

	bool b = false;
	for( int i = 0; i < n; i++ ) {
		if( s[i] == 'Y' ) {
			b = true;
			break;
		}
	}
	if( b == false ) {
		cout << "Three" << endl;
	}
	else {
		cout << "Four" << endl;
	}
 
	return 0;
}


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

constexpr ll INF = 1e9 + 7;

void dfs(ll node, ll pnode, ll lis_len, vector<ll>& dp, vector<ll>& ans, const vector<vector<ll>>& edges, const vector<ll>& a)
{
    auto num = a[node];

    auto it = lower_bound(begin(dp) + 1, begin(dp) + 1 + lis_len, num);

    auto reserve = *it;
    *it = num;

    lis_len = max((ll)distance(begin(dp), it), lis_len);
    ans[node] = lis_len;

    for (auto&& e : edges[node]) {
        if (e != pnode) {
            dfs(e, node, lis_len, dp, ans, edges, a);
        }
    }

    *it = reserve;
}

void solve(long long N, std::vector<long long> a, std::vector<long long> u, std::vector<long long> v)
{
    vector<vector<ll>> edges(N+1);
    for (ll i = 0; i < N - 1; i++) {
        edges[u[i]].push_back(v[i]);
        edges[v[i]].push_back(u[i]);
    }

    vector<ll> dp(N + 1, INF);
    vector<ll> ans(N + 1);

    dfs(1, 0, 0, dp, ans, edges, a);
    copy(begin(ans) + 1, end(ans), ostream_iterator<ll>(cout, "\n"));
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
#pragma GCC diagnostic ignored "-Wunused-result"
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N+1);
    for(int i = 1 ; i <= N ; i++){
        scanf("%lld",&a[i]);
    }
    std::vector<long long> u(N-1);
    std::vector<long long> v(N-1);
    for(int i = 0 ; i < N-1 ; i++){
        scanf("%lld",&u[i]);
        scanf("%lld",&v[i]);
    }
    solve(N, std::move(a), std::move(u), std::move(v));
    return 0;
}


Measured memory_bytes: 42020
N, Y = (int(i) for i in input().split())

is_completed = False
ans = [-1, -1, -1]
for x in range(N+1):
    if is_completed:
        break
    for y in range(N+1):
        z = N - (x+y)
        if not (0 <= z <= N):
            continue
        if 10000*x + 5000*y + 1000*z == Y:
            is_completed = True
            ans = [x, y, z]
            break
print(*ans, sep=" ")

Measured memory_bytes: 40812
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n;
int arr[200005];
vector<int>v[200005];
int dp[200005];
int values[200005];
int tree[1000005];

void update(int i,int l,int r,int x,int val)
{
    if(x<l || x>r)
        return;
    if(l==r)
    {
        tree[i]=val;
        return;
    }
    int mid=(l+r)/2;
    update(i*2,l,mid,x,val);
    update(i*2+1,mid+1,r,x,val);
    tree[i]=max(tree[i*2],tree[i*2+1]);
}
int query(int i,int l,int r,int l1,int r1)
{
    if(l1>r1 || l>r1 || l1>r)
        return 0;
    if(l1<=l && r<=r1)
        return tree[i];
    int mid=(l+r)/2;
    return max(query(i*2,l,mid,l1,r1),query(i*2+1,mid+1,r,l1,r1));
}
void dfs(int pos,int par)
{
    int ans=query(1,1,n+5,1,arr[pos]-1);
    update(1,1,n+5,arr[pos],ans+1);
    dp[pos]=query(1,1,n,1,n);
    int curr=values[arr[pos]];
    values[arr[pos]]=ans+1;
    for(auto i:v[pos])
        if(i!=par)
            dfs(i,pos);
    values[arr[pos]]=curr;
    update(1,1,n+5,arr[pos],curr);
}
int32_t main() 
{
    IOS;
    cin>>n;
    set<int>s;
    map<int,int>mp;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        s.insert(arr[i]);
    }
    int ct=0;
    for(auto i:s)
        mp[i]=++ct;
    for(int i=1;i<=n;i++)
        arr[i]=mp[arr[i]];

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        print(dp[i]);
}   


Measured memory_bytes: 54764
#include<stdio.h>
#include<iostream>
#include<algorithm> // sort(ALL())
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue> // push(), front(), pop() 先入れ先出し
#include<map> // 連想配列 map<string, int>
#include<iomanip>
#include<set>
#include<utility>
using namespace std;
#define FOR(i, a, b) for(int i=(a); i<(b);  i++)
#define REP(i, n)    for(int i=0;   i<(n);  i++)
#define REP1(i, n)   for(int i=1;   i<=(n); i++)
#define pb push_back
#define mp make_pair
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define EPS 1e-7
#define ALL(obj) (obj).begin(), (obj).end()
#define MAX_INDEX(arg) distance(arg.begin(), max_element(arg.begin(), arg.end()))
using ul    = unsigned long;
using ll    = long long;
using ld    = long double;
using vint  = vector<int>;
using vll   = vector<ll>;
using pint  = pair<int, int>;
using pll   = pair<ll, ll>;
using vpint = vector<pint>;
using vpll  = vector<pll>;
const int INF = (int)1e9 + 1;
const int MOD = (int)1e9 + 7;
#define INT(argu) (int)(argu+EPS)

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

  int n;
  scan(n);
  n /= 2;
  vint a(100002), b(100002);
  int x, y;
  REP(i, n){
    cin >> x >> y;
    a[x]++; b[y]++;
  }

  vint::iterator itrmaxa = max_element(ALL(a));
  vint::iterator itrmaxb = max_element(ALL(b));

  bool find_2_a = find(next(itrmaxa), a.end(), *itrmaxa) != a.end();
  bool find_2_b = find(next(itrmaxb), b.end(), *itrmaxb) != b.end();
  if( !(find_2_a || find_2_b) && (distance(a.begin(), itrmaxa) == distance(b.begin(), itrmaxb)) ){
    cout <<
    n*2 -
    max(
      max(*max_element(a.begin(), prev(itrmaxa)), *max_element(next(itrmaxa), a.end())) + *itrmaxb
    , max(*max_element(b.begin(), prev(itrmaxb)), *max_element(next(itrmaxb), b.end())) + *itrmaxa
    )
    << endl;
  }else{
    cout << n*2 - *itrmaxa - *itrmaxb << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);
		int n, m;
		int totalTokuhyo = 0;

		n = scan.nextInt();
		m = scan.nextInt();

		int[] a = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			a[i] = scan.nextInt();
			totalTokuhyo += a[i];
		}

		final int f_total = totalTokuhyo;

		long count = Arrays.stream(a).filter(item -> item >= f_total * (1 / ((double) 4 * m))).count();

		if (count >= m) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 27348
#include <iostream>

using namespace std;
int main() {
	int n;
	cin >> n;
	int mini;
	int a[n], b[n];
	char A[n], B[n];
	bool stable;
	for(int i = 0; i < n; i++){
		cin >> A[i] >> a[i];
		B[i] = A[i];
		b[i] = a[i];
	}
	for(int i = 0; i < n; i++){
		for(int j = n-1; j > i; j--){
			if(a[j] < a[j-1]){
				swap(A[j], A[j-1]);
				swap(a[j], a[j-1]);
			}
		}
	}
	for(int i = 0; i < n; i++){
		if(i) cout << " ";
		cout << A[i] << a[i];
	}
	cout << endl;
	cout << "Stable" << endl;
	for(int i = 0; i < n; i++){
		mini = i;
		for(int j = i; j < n; j++){
			if(b[j] < b[mini])
			{
				mini = j;
			}
		}
		swap(b[i], b[mini]);
		swap(B[i], B[mini]);
	}
	for(int i = 0; i < n; i++){
		if(i) cout << " ";
		cout << B[i] << b[i];
	}
	cout << endl;
	for(int i = 0; i < n; i++){
		if(A[i] == B[i] && a[i] == b[i]){
			stable = true;
		}else{
			stable = false;
			break;
		}
	}
	if(stable == true) cout << "Stable" << endl;
	else cout << "Not stable" << endl;
}


Measured memory_bytes: 3100
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int d = sc.NextInt();
        int x = sc.NextInt();


        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            int a = sc.NextInt();
            answer += 1 + (d - 1) / a;
        }
        answer += x;

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <tuple>
#include <functional>

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define rep(i,n) for(long long  i = 0; i < n; i++)
#define rep2(i,a,n) for(long long  i = a; i < n; i++)
#define in(a) cin >> a
#define out(a) cout << a << endl

using namespace std;

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

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

    cout << lcm(2,n) << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    std::cin >> n;
    int h[100000];
    int ans=0;
    int cnt=0;
    std::cin >> h[0];
    for (int i = 1; i < n; i++) {
        std::cin >> h[i];
        if(h[i]<=h[i-1]){
            cnt++;
            if(ans<cnt){
                ans=cnt;
            }
        }else{

            cnt=0;
        }
    }
    
    std::cout << ans << std::endl;
    
}


Measured memory_bytes: 640
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
T = getList()
A = getList()

"""
山の高さの列が何通りあるか　dp? 組み合わせ?
dpなら漸化式を考える

5
1 3 3 3 3 高橋くんは左 → 右
3 3 2 2 2 青木くんは右 → 左
最大値のみをレコード

最大値が更新された時のみ高さがわかる
1 3 ? ? ?
? 3 ? ? 2

1 3 ? ? 2
3番目は3以下かつ2以下
4番目は3以下かつ2以下

5
1 1 1 2 2
3 2 1 1 1

1 ? ? 2 ?
3 2 ? ? 1 矛盾
"""

c_t = [-1] * N
c_t[0] = T[0]
for i in range(1, N):
    if T[i] > T[i - 1]:
        c_t[i] = T[i]

c_a = [-1] * N
c_a[N - 1] = A[N - 1]
for i in range(N - 2, -1, -1):
    if A[i] > A[i + 1]:
        c_a[i] = A[i]

c_det = [-1] * N
for i in range(N):
    if c_t[i] >= 0 and c_a[i] >= 0:
        if c_t[i] != c_a[i]:
            print(0)
            exit()
        else:
            c_det[i] = c_t[i]
    elif c_t[i] >= 0:
        c_det[i] = c_t[i]
    elif c_a[i] >= 0:
        c_det[i] = c_a[i]

for i in range(N):
    if c_det[i] > min(T[i], A[i]):
        print(0)
        exit()

ans = 1
for i in range(N):
    if c_det[i] == -1:
        ans *= min(T[i], A[i])
        ans %= mod
print(ans)

Measured memory_bytes: 102068
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
#include <queue>
#include <math.h>
#define ll long long
#define INF 100000000000
#define N 10000000
using namespace std;


int main(void){
    map <long,long> data;
    long n;
    cin>>n;
    for (long i=0; i<n; i++){
        long p;
        cin>>p;
        data[p]++;
    }
    
    long q;
    cin>>q;
    
    ll ans=0;
    for (auto it=data.begin(); it!=data.end(); it++){
        ans+=(it->first)*(it->second);
    }
    
    for (long i=0; i<q; i++){
        long x,y;
        cin>>x>>y;
        ans=ans-x*data[x]+y*data[x];
        data[y]+=data[x];
        data[x]=0;
        
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 9500
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>
using namespace std;
using P = pair<int,int>;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){
    int r; cin >> r;
    cout << 3*r*r << endl;
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct T
{
    int l,r;
}a[N];
int cmp(T x,T y)
{
    return x.r<y.r;
}
int main()
{
    int s=0,m,l=0;
    cin>>m>>m;
    for(int i=0;i<m;i++)cin>>a[i].l>>a[i].r;
    sort(a,a+m,cmp);
    for(int i=0;i<m;i++)if(a[i].l>=l)l=a[i].r,s++;
    cout<<s;
}


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

int main(){ 
	ll a,b,c;
	cin >> a >> b >> c;
	cout << c-min(c,a-b) << endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
sushi = [None] * N
for i in range(N):
    t, d = map(int, input().split())
    sushi[i] = (d, t)
sushi.sort(reverse=True)

types = set()
cand = []
s = x = 0

for d, t in sushi[:K]:
    if t in types:
        cand.append(d)
    else:
        types.add(t)
        x += 1
    s += d
cand.sort(reverse=True)

ans = s + x*x
for d, t in sushi[K:]:
    if t in types:
        continue
    if not cand:
        break
    dr = cand.pop()
    s += d - dr
    types.add(t)
    x += 1
    ans = max(ans, s + x*x)
print(ans)

Measured memory_bytes: 49500
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 100000 + 10000;

int n;
vector<int> edg[MAXN];
int f[MAXN], v[MAXN];

void dfs(int x, int fa)
{
	f[x] = 0, v[x] = 0;
	int cover = 0;
	for(int i = 0; i < edg[x].size(); i++)
		if(edg[x][i] != fa)
		{
			int y = edg[x][i];
			dfs(y, x);
			cover |= f[y] & f[x];
			f[x] |= f[y];
		}
	while((1 << v[x]) < cover || (f[x] & (1 << v[x])))
		v[x]++;
	f[x] &= ~((1 << v[x]) - 1);
	f[x] |= 1 << v[x];
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n;
	for(int i = 1; i <= n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		edg[x].push_back(y), edg[y].push_back(x);
	}
	dfs(1, 0);
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, v[i]);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 12416
ashiba_num, jump_num = gets.split(' ').map(&:to_i)
ashiba_cost = gets.split(' ').map(&:to_i)

dP = []
dP[0] = 0
dP[1] = (ashiba_cost[1] - ashiba_cost[0]).abs

range = 2..ashiba_num - 1 
range2 = 1..jump_num
range.each do |move|

    dP_min = Float::INFINITY
    
    range2.each do |jump|
        if move - jump >= 0
            dP_now = dP[move - jump] + (ashiba_cost[move] - ashiba_cost[move - jump]).abs
        else
            dP_now = (ashiba_cost[move] - ashiba_cost[0]).abs
        end
        
        if dP_min >= dP_now || dP_min < 0
            dP_min = dP_now 
        end

    end

   dP[move] = dP_min

end

p dP.last

Measured memory_bytes: 9044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
#define pi 3.141592653589793
#define mod 998244353
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;

int main() {
	fast_io;
	ll n, k;
	cin >> n >> k;
	vl a(n);
	for (int i = 0;i < n;i++)
		cin >> a[i];
	vl dp(n, 0);
	for (int i = 1;i < n;i++) {
		dp[i] = dp[i - 1] + abs(a[i] - a[i - 1]);
		for (int j = 2;j <= k && i - j >= 0;j++)
			dp[i] = min(dp[i], dp[i - j] + abs(a[i] - a[i - j]));
	}
	cout << dp[n - 1] << '\n';
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    vector<int> c{1, 9, 6, 4, 6, 6, 4, 6, 9, 1};
    string s;
    while(cin >> s){
        int ans = 0;
        for (int i = 0; i < 10; ++i) ans += c[i]*(s[i]-'0');
        cout << ans%10 << "\n";
    }
    return 0;
}


Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
char s[15];
int l;
ll ans;
int a[15];
ll f[15];

void dfs(int x, int cnt) { //x表示加号位置, cnt表示加号个数
	if(x == l) {
		int pos = cnt;
		pos--;
		int dd = 1;
		//int tmp = ans;
		for(int i = l; i >= 1; i--) {
			if(i == a[pos]) dd = 1, pos--;
			ans += f[dd] * (s[i] - '0');
			dd++;
		}
		//printf("%lld\n", ans - tmp);
	}
	for(int i = x + 1; i <= l; i++) {
		a[cnt] = x;
		dfs(i, cnt + 1);
	}
}

int main() {
	f[1] = 1;
	for(int i = 2; i <= 10; i++) f[i] = f[i - 1] * 10;
	scanf("%s", s + 1);
	l = strlen(s + 1);
	dfs(0, 0);
	//printf("ans = ")
	printf("%lld\n", ans);
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
public class Main {
	public static void main(String[] args)
	{	Scanner sc = new Scanner(System.in);
		int N,L;
		N = sc.nextInt();
		L = sc.nextInt();
		String[] s = new String[N];
		for(int i=0;i<N;i++)
		{
			s[i] = sc.next();
		}
		
		Arrays.sort(s);
		for(int i=0;i<N;i++)
		{
			System.out.print(s[i]);
			
		}
		
		
	}
}

Measured memory_bytes: 10996
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define INF 1LL<<60

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    ll total = 0;
    REP(i, N){
        cin >> A[i];
        total += A[i];
    }

    ll tmp = 0, ans = 0;
    int i = 0;
    while(tmp + A[i] < total/2) {
        tmp += A[i++];
    }

    ll cost1 = max(total/2 - tmp, total/2 - (total - tmp));
    ll cost2 = max(total/2 - tmp - A[i], total/2 - (total - tmp - A[i]));

    if(cost2 < cost1) {
        tmp += A[i];
    }


    ll tgt_length = min(tmp, total - tmp);
    ans = max(tmp - tgt_length, total - tmp - tgt_length);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
//#define vi vector<int>
#define all(a) a.begin(),a.end()
typedef pair<int,int> P;
const long long mod1=998244353;
const long long mod2=924844033;
const long long base1=1007;
const long long base2=2009;
const long long inf=1ll<<61;

struct RH{
	int hash1,hash2,bit;
};
string s[200006];
int hash1[1000006],hash2[1000006];
map<P,int>hashs;
RH koho[1000006];


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;cin>>n;
	rep(i,n){
		cin>>s[i];
		reverse(all(s[i]));
	}
	
	int ci=0;
	rep(i,n){
		int z=s[i].size();
		rep(j,z){
			hash1[j+1]=hash1[j]*base1+s[i][j];
			hash1[j+1]%=mod1;
			hash2[j+1]=hash2[j]*base2+s[i][j];
			hash2[j+1]%=mod2;
		}
		
		hashs[P(hash1[z],hash2[z])]++;
		int fil=0;
		for(int j=z-1;j>=0;j--){
			fil|=(1<<(s[i][j]-'a'));
			koho[ci]={hash1[j],hash2[j],fil};
			ci++;
		}
	}

	int ans=0;

	rep(i,ci){
		int h1=koho[i].hash1,h2=koho[i].hash2;
		rep(j,26){
			if(koho[i].bit&(1<<j)){
				int i1=h1*base1+j+'a';
				int i2=h2*base2+j+'a';
				i1%=mod1;i2%=mod2;
				auto itr=hashs.find(P(i1,i2));
				if(itr!=hashs.end())ans+=itr->second;
			}
		}
	}
	cout<<ans-n<<'\n';
}

Measured memory_bytes: 49244
abc="abcdefghijklmnopqrstuvwxyz"
import collections
table=collections.defaultdict(int)
for i in range(26):
  table[abc[i]]=i
table2=collections.defaultdict(int)
s=input()
for i in reversed(range(len(s)+1)):
  k=0
  if i < len(s):
    k=table[s[i]]+1
  for j in range(k,26):
    if abc[j] in s[:i]:
      continue
    else:
      print(s[:i]+abc[j])
      exit(0)
print(-1)

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

using namespace std;

long long dp(int N, int h[]) {
  long long c[N + 1];
  c[1] = 0;
  c[2] = c[1] + abs(h[2] - h[1]);
  for (int i = 3; i <= N; i++) {
    c[i] = min(c[i - 1] + abs(h[i] - h[i - 1]), c[i - 2] + abs(h[i] - h[i - 2]));
  }
  return c[N];
}

int main()
{
  int N; cin >> N;
  int h[N + 1];

  for (int i = 1; i <= N; i++) {
    cin >> h[i];
  }
  cout << dp(N, h) << endl;
  return 0;
}


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

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

  int M=0;
  for(int i=0; i<N-1; i++){
    M= max(M,S.at(i+1)-S.at(i));
  }
  M=max(M,K+S.at(0)-S.at(N-1));
  cout<<K-M;
  
}

Measured memory_bytes: 1024
#include<stdio.h>

#define NIL -1
#define MAX 10000

typedef struct Node{
  int id;
  int p;
  int left;
  int right;
  int s;
  int deg;
  int dep;
  int h;
  char* type;
}Node;

Node T[MAX];

int getdeg(int);
int getdep(int);
int geth(int);
char* gettype(int);

int d;

int main(){
  int n,i,u;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    T[i].p=NIL;
    T[i].s=NIL;
    T[i].left=NIL;
    T[i].right=NIL;
    T[i].deg=0;
    T[i].dep=0;
    T[i].h=0;
  }
  
  for(i=0;i<n;i++){
    scanf("%d",&u);
    T[u].id=u;
    scanf("%d%d",&T[u].left,&T[u].right); 
    T[T[u].left].p=T[u].id;
    T[T[u].left].s=T[u].right;
    T[T[u].right].p=T[u].id;
    T[T[u].right].s=T[u].left;
  }

  for(i=0;i<n;i++){
    T[i].deg=getdeg(i);
    T[i].dep=getdep(i);
    T[i].h=geth(i);
    T[i].type=gettype(i);
    d=0;
  }

  for(i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n",i,T[i].p,T[i].s,T[i].deg,T[i].dep,T[i].h,T[i].type);
  }

  return 0;
}

int getdeg(int u){
  if((T[u].left==NIL)&&(T[u].right==NIL))
    return 0;
  else if((T[u].left!=NIL)&&(T[u].right!=NIL))
    return 2;
  else 
    return 1;
}


int getdep(int u){
  if(T[u].p==NIL)
    return d;
  else{
    d++;
    return getdep(T[u].p);
  }
}

int geth(int u){
  int h1=0,h2=0;
  if(T[u].right!= NIL)
    h1=geth(T[u].right)+1;
  if(T[u].left!=NIL)
    h2=geth(T[u].left)+1;
  return (h1 > h2 ? h1 : h2);
}
char* gettype(int u){
  if(T[u].p != NIL){
    if((T[u].left == NIL)&&(T[u].right == NIL))
      return "leaf";
    else
      return "internal node";
  }
  else
    return "root";
}
    
      

  



Measured memory_bytes: 2112