akhauriyash/Code-Regression huggingface dataset:
// #define _GLIBCXX_DEBUG
#pragma GCC optimize("Ofast")

#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <string>
#include <vector>
#include <chrono>

#include <cmath>

#define int long long

using namespace std;

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

  auto start = chrono::system_clock::now();

  vector<int> idx[32];

  for (int i = 0; i < n; i++) {
    idx[s[i] - 'a'].push_back(i);
  }

  int ans = 0;

  for (char c = 'a'; c <= 'z'; c++) {
    int x = c - 'a';
    for (int i = 0; i < idx[x].size(); i++) {
      auto current_time = chrono::system_clock::now();
      auto elapsed = chrono::duration_cast<chrono::milliseconds>(current_time - start).count();

      if (elapsed >= 1950) {
        goto END;
      }

      int l = idx[x][i];

      if (n - l <= ans) {
        break;
      }

      for (int j = i + 1; j < idx[x].size(); j++) {
        int t = 0;

        int r = idx[x][j];

        if (r - l <= ans) {
          continue;
        }

        while (true) {
          if (l + t >= r) {
            break;
          }
          if (r + t >= n) {
            break;
          }

          if (s[l + t] != s[r + t]) {
            break;
          }

          t++;
        }

        ans = max(ans, t);
      }
    }
  }

END:

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
int main() {
	//入力
	long N,M,L[100000],R[100000],ans,s=0,e=100000;
	cin >> N >> M;
	for (long j = 0; j < M; j++) {
		cin >> L[j] >> R[j];
	}
	//処理
	for (long k = 0; k < M; k++) {
		if (s < L[k]) s = L[k];
		if (e > R[k]) e = R[k];
	}
	ans = e - s + 1;
	if (ans <= 0)ans = 0;
	//出力
	cout << ans << endl;
}

Measured memory_bytes: 1792
#組み合わせ総数
mod = 10 ** 9 + 7
def comb(n, k):
    res = 1
    for i in range(n - k + 1, n + 1):
        res = res * i % mod
    for i in range(1, k + 1):
        res = res * pow(i, mod - 2, mod) % mod
    return res

x,y = map(int,input().split())

if (x + y) % 3 != 0:
    print(0)
    exit()

m = (2 * x - y) // 3
n = x - 2 * m

if n >= 0 and m >= 0:
    print(comb(m + n,min(m,n)))
else:
    print(0)

Measured memory_bytes: 38640
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    n, m = map(int, input().split())
    
    grid = [[] for _ in range(n)]
    
    for _ in range(m):
        x, y = map(int, input().split())
        grid[x-1].append(y-1)
    
    memo = [-1]*n
    
    def dp(n):
        if memo[n] != -1:
            return memo[n]
        res = 0
        for v in grid[n]:
            res = max(res, dp(v)+1)
        memo[n] = res
        return res
    
    ans = 0
    for i in range(n):
        sub = dp(i)
        if ans < sub:
            ans = sub
        
    print(ans)
    
    
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 117924
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<random>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
typedef vector<vt>vvt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

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

	string s;
	cin>>s;
	rep(i,s.size())if(i%2&&s[i]!='i'||i%2==0&&s[i]!='h'){
		no;
		return 0;
	}
	if(s.size()%2==0)yes;
	else no;

}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <map>
using namespace std;

struct node{
    int id,parent,degree,lchild,rchild;
    string type;
};

node u[50];

void Preorder(int root){
    cout << ' ' << root;
    if(u[root].lchild != -1) Preorder(u[root].lchild);
    if(u[root].rchild != -1) Preorder(u[root].rchild);
}
void Inorder(int root){
    if(u[root].lchild != -1) Inorder(u[root].lchild);
    cout << ' ' << root;
    if(u[root].rchild != -1) Inorder(u[root].rchild);
}
void Postorder(int root){
    if(u[root].lchild != -1) Postorder(u[root].lchild);
    if(u[root].rchild != -1) Postorder(u[root].rchild);
    cout << ' ' << root;
}
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        u[i].parent = -1;
        u[i].degree = 0;
    }
    for(int i=0;i<n;i++){
        int m;
        cin >> m;
        u[m].id = m;
        int left,right;
        cin >> left >> right;
        u[m].lchild = left;
        u[m].rchild = right;
        if(left != -1){
            u[i].degree++;
            u[left].parent = m;
        }
        if(right != -1){
            u[i].degree++;
            u[right].parent = m;
        }
    }
    int root;
    for(int i=0;i<n;i++){
        if(u[i].parent == -1) root = i;
    }
    cout << "Preorder" << endl;
    Preorder(root);
    cout << endl << "Inorder" << endl;
    Inorder(root);
    cout << endl << "Postorder" << endl;
    Postorder(root);
    cout << endl;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define name(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int N=(int)1e6+7;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , m;
    cin >> n >> m;
    map<int , ll>mp;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[-x] += 1;
    }
    while(m--){
        int b,c;
        cin >> b >> c;
        mp[-c] += b;
    }
    ll sum = 0;
    int taken = 0;
    for(pair<int , ll>  p : mp) {
        p.first*= -1;
        while(p.second--){
            taken++;
            sum += p.first;
            if(taken == n)break;
        }
        if(taken == n)break;
    }
    cout << sum << '\n';
    return 0;
}



Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
int main(){
	int h=1,w=1;
	while((h!=0)&&(w!=0)){
		cin>>h>>w;
		if ((h==0)&&(w==0)){
	return 0;
	}
		for(int i=1;i<=h;i++){
			if(i%2==1){
				for (int j=1;j<=w;j++){
					if(j%2==1){
						cout<<'#';
					}
					else{
						cout<<'.';
					}
				}
				cout<<endl;
			}
			else{
				for (int k=1;k<=w;k++){
					if(k%2==1){
						cout<<'.';
					}
					else{
						cout<<'#';
					}
				}
				cout<<endl;
			}
		}
		cout<<endl;
	}
}


Measured memory_bytes: 3064
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

void add(int & x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int sum(int x, int y) {
  add(x, y);
  return x;
}

int mult(int x, int y) {
  return (ll) x * y % mod;
}

int power(int x, ll p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
    p >>= 1;
  }
  return res;
}

int inv(int x) {
  return power(x, mod - 2);
}

void precalc() {
}

const int maxn = 1e5 + 100;
int n;
int a[maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  return true;
}

int sign(int x) {
  return (x > 0) - (x < 0);
}

void solve() {
  int dp1 = 1, dp2 = inf;
  int sgn = 0;
  for (int i = 1; i < n; i++) {
    if (a[i] == a[i - 1]) {
      continue;
    }
    int ndp1 = min(dp1, dp2) + 1;
    int ndp2 = dp1;
    int nsgn = sign(a[i] - a[i - 1]);
    if (sgn == nsgn) {
      ndp2 = min(ndp2, dp2);
    }
    dp1 = ndp1;
    dp2 = ndp2;
    sgn = nsgn;
  }
  printf("%d\n", min(dp1, dp2));
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}



Measured memory_bytes: 640
import java.util.Arrays; 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	public static class Pos{
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			final int W = sc.nextInt();
			final int H = sc.nextInt();
			
			if(W == 0 && H == 0){
				break;
			}
			
			boolean[][] is_visited = new boolean[H][W];
			boolean[][] is_wall = new boolean[H][W];
			
			int s_x = -1, s_y = -1;
			
			for(int i = 0; i < H; i++){
				char[] ch = sc.next().toCharArray();
				
				for(int j = 0; j < W; j++){
					is_visited[i][j] = false;
					is_wall[i][j] = ch[j] == '#';
					
					if(ch[j] == '@'){
						s_x = j;
						s_y = i;
					}
				}
			}
			
			LinkedList<Pos> queue = new LinkedList<Pos>();
			
			queue.add(new Pos(s_x, s_y));
			int count = 0;
			
			while(!queue.isEmpty()){
				Pos pos = queue.poll();
				
				if(is_visited[pos.y][pos.x]){
					continue;
				}
				
				is_visited[pos.y][pos.x] = true;
				count++;
				
				if(pos.x != 0 && !is_wall[pos.y][pos.x - 1] && !is_visited[pos.y][pos.x - 1]){
					queue.add(new Pos(pos.x - 1, pos.y));
				}
				
				if(pos.x != W-1 && !is_wall[pos.y][pos.x + 1] && !is_visited[pos.y][pos.x + 1]){
					queue.add(new Pos(pos.x + 1, pos.y));
				}
				
				if(pos.y != 0 && !is_wall[pos.y - 1][pos.x] && !is_visited[pos.y - 1][pos.x]){
					queue.add(new Pos(pos.x, pos.y - 1));
				}
				
				if(pos.y != H-1 && !is_wall[pos.y + 1][pos.x] && !is_visited[pos.y + 1][pos.x]){
					queue.add(new Pos(pos.x, pos.y + 1));
				}
			}
			
			System.out.println(count);
		}
		
	}
}

Measured memory_bytes: 12000
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int DFS(int L,int R,vector<vector<int> > & DP,vector<vector<int> > & flag,vector<int> &vec)
{
  if(L == R)return 0;
  if(flag[L][R]) return DP[L][R];
  flag[L][R] = 1;
  int res = INF;
  for (int i = L; i < R; i++)
  {
    res = min(res,DFS(L,i,DP,flag,vec) + DFS(i+1,R,DP,flag,vec));
  }
  res += vec[R];
  if(L>0)res -=vec[L-1];
  return DP[L][R] = res;
  
}

void solve(void)
{
  int N; cin>>N;
  vector<int> vec (N,0);
  for (int i = 0; i < N; i++)
  {
     cin>>vec[i];
     if(i) vec[i] += vec[i-1];
  } 
  vector<vector<int> > DP (N+1,vector<int>(N+1,0));
  vector<vector<int> > flag (N+1,vector<int>(N+1,0));
  cout<<DFS(0,N-1,DP,flag,vec)<<endl;
  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


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

uint64_t powmod(uint64_t x, uint64_t y, uint64_t p)
{
	if(y == 0){
		return 1;
	} else if(y % 2 == 1){
		return (powmod(x, y-1, p) * x) % p;
	} else {
		uint64_t t = powmod(x, y/2, p);
		return (t * t) % p;
	}
}

void fracs(uint64_t n, uint64_t p,
	uint64_t *pnf, uint64_t *ipnf)
{
	pnf[0] = 1;
	for(uint64_t i=0; i<n; i++){
		pnf[i+1] = (pnf[i] * (i+1)) % p;
	}
	ipnf[n] = powmod(pnf[n], p-2, p);
	for(uint64_t i=n; i>0; i--){
		ipnf[i-1] = (ipnf[i] * i) % p;
	}
}

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

	int p = 1000000007;
	uint64_t
		*pnf = new uint64_t[200001],
		*ipnf = new uint64_t[200001];
	fracs(n, p, pnf, ipnf);
	if(n-1 < k){
		k = n-1;
	}

	uint64_t res = 0;
	for(int i=0; i<k+1; i++){
		uint64_t r = 1;
		r = (pnf[n] * ipnf[n-i]) % p * ipnf[i] % p;
		r *= (pnf[n-1] * ipnf[n-1-i]) % p * ipnf[i] % p;
		r %= p;
		res += r;
	}

	cout << res % p;

	return 0;
}


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

int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<char>>a(h,vector<char>(w));
  for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin >> a.at(i).at(j);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a.at(i).at(j)=='.'){
        int n=0;
        for(int k=-1;k<2;k++){
          for(int l=-1;l<2;l++){
            if(i+k>=0&&i+k<h&&j+l>=0&&j+l<w){
              n+=(a.at(i+k).at(j+l)=='#');
            }
          }
        }
        a.at(i).at(j)=n+'0';
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout << a.at(i).at(j);
    }
    cout << '\n';
  }
  return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  long long ans=0;
  int t=n-1;
  sort(a.rbegin(),a.rend());
  for(int i=0;i<n;i++){
    int lim=2;
    if(i==0) lim=1;
    for(int j=0;j<lim;j++){
      if(t>0){
        ans+=a[i];
        t--;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4044
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		if(N <= 999) {
			System.out.println("ABC");
		} else {
			System.out.println("ABD");
		}
		
	}
}


Measured memory_bytes: 21716
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		
		if ( a < b && b < c) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 26212
N=gets.to_i
n1 = N - 1
n2 = n1
res = 0
ans = []
tmp = 0
[*1..n1].each do |a|
  [*1..n2].each do |b|
    tmp = b
    #p "#{a} #{b}"
    if a * b <= (N - 1)
      res += 1
      #ans << [a, b]
    else
      break
    end
  end
  n2 = tmp
end
p res
#abc = (N-1) * 2 # [*1..[*1..N-1].size].size
#p abc
#p ([*1..N-1].sum * 2) + (N / 2 - 1) + 1
=begin
res = 0
ans = []
ab=[*1..(N-1)].repeated_permutation(2).to_a

ab.each do |a, b|
  if a * b <= (N - 1)
    res += 1
    ans << [a, b]
  end
end
=end
#p ans
#p res

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

const int maxn = 100010;
int n, fa[maxn];
long long ans;
struct node { int x, y, id; };
node p[maxn];
struct edge { int u, v, w; };
vector<edge> E;

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &p[i].x, &p[i].y), p[i].id = fa[i] = i;
    }
    sort(p + 1, p + n + 1, [&](node x, node y) { return x.x < y.x; });
    for (int i = 1; i < n; i++) {
        E.push_back((edge){p[i].id, p[i + 1].id, p[i + 1].x - p[i].x});
    }
    sort(p + 1, p + n + 1, [&](node x, node y) { return x.y < y.y; });
    for (int i = 1; i < n; i++) {
        E.push_back((edge){p[i].id, p[i + 1].id, p[i + 1].y - p[i].y});
    }
    sort(E.begin(), E.end(), [&](edge x, edge y) { return x.w < y.w; });
    for (auto e : E) {
        if (find(e.u) == find(e.v)) continue;
        fa[find(e.u)] = find(e.v), ans += e.w; 
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 6516
n = int(input())
t_l = list(map(int, input().split()))
m = int(input())
x_l = [list(map(int, input().split())) for _ in range(m)] #n行にmつずつ入力される整数
for p, x in x_l:
    cnt = 0
    for i in range(1, n+1):
        if p == i:
            cnt += x
        else:
            cnt += t_l[i-1]
    print(cnt)


Measured memory_bytes: 38512
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

ll V[51];
vector<pair<int, int>> E[51];
void dfs(int p, ll v, int mae) {
	V[p] = v;
	for (auto pr : E[p]) {
		int to = pr.first;
		if (mae != to) {
			v ^= 1ll << pr.second;
			dfs(to, v, p);
			v ^= 1ll << pr.second;
		}
	}
}

//包除原理でもできるらしいのでがんばる
int N, M;
int kazoeru[51];
ll seiyaku[20];
void keisan(int i, bool k, ll are) {
	if (i == M) {
		kazoeru[__builtin_popcountll(are)] += 1 - k * 2;
	}
	else {
		keisan(i + 1, k, are);
		keisan(i + 1, !k, are | seiyaku[i]);
	}
}

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


	cin >> N;
	rep(i, N - 1) {
		int a, b;
		cin >> a >> b;
		E[a].pb(mp(b, i));
		E[b].pb(mp(a, i));
	}

	dfs(1, 0, 0);

	cin >> M;
	rep(i, M) {
		int u, v;
		cin >> u >> v;
		seiyaku[i] = V[u] ^ V[v];
	}

	keisan(0, 1, 0);

	ll kotae = 0;
	rep1(i, N) {
		ll tmp = (1ll << N - 1) - (1ll << (N - i - 1));
		kotae += tmp * kazoeru[i];
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
N = int(input())
hoge = input().split()
H = []
for i in range(N):
  H.append(int(hoge[i]))

_max = 0
pivot = 0
count = 0
while 1 == 1:
  if pivot == N - 1:
    if _max < count:
      _max = count
    break
  if H[pivot] >= H[pivot+1]:
    count += 1
    pivot = pivot + 1
  else:
    pivot = pivot + 1
    if _max < count:
      _max = count
    count = 0

print(_max)

Measured memory_bytes: 14252
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

int n, half;

char s[100005];
int uf[50015];
int val[50005];
int dif[50005];
int ans[50005];

int fin(int a)
{
    if (uf[a] == a) return a;
    return uf[a] = fin(uf[a]);
}

void un(int a, int b)
{
    a = fin(a); b = fin(b);
    if (a == b) return;
    uf[a] = b;
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    half = n / 2;
    for (int i = 1; i <= half + 3; i++) uf[i] = i;
    int q; scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        if (l <= n - r + 1) {
            /* towards left */
            if (r > half) r = n - r;
        } else {
            //printf("%d\n", ((half + 1) - l) * 2 + (n % 2));
            if (l < half + 1 + (n % 2)) l += ((half + 1) - l) * 2 + (n % 2);
            int nl = n - r + 1;
            int nr = n - l + 1;
            l = nl; r = nr;
        }
        //printf("%d %d\n", l, r);
        un(l, r + 1);
    }
    for (int i = 1; i <= half; i++) {
        val[i] = (s[i] - s[n-i+1] + 26) % 26;
    }
    for (int i = 1; i <= half + 1; i++) {
        dif[i] = (val[i] - val[i-1] + 26) % 26;
        ans[fin(i)] += dif[i];
        ans[fin(i)] %= 26;
    }
    for (int i = 1; i <= half + 1; i++) {
        if (ans[i]) {
            printf("NO"); return 0;
        }
    }
    printf("YES");
    return 0;
}


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

int Manhattan_d(int a,int b,int c,int d){
  return abs(a-c)+abs(b-d);
}

class CheckPoint{
 public:
  int ikisaki;
  int kyori;
};

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> a(N),b(N);
  rep(i,N) cin >> a[i] >> b[i];
  vector<int> c(M),d(M);
  rep(i,M) cin >> c[i] >> d[i];

  CheckPoint P[N];
  rep(i,N){P[i].ikisaki=-1;P[i].kyori=1000000000;}

  int Md;
  rep(i,N){
    rep(j,M){
    Md = Manhattan_d(a[i],b[i],c[j],d[j]);
      if(Md < P[i].kyori){
        P[i].kyori = Md;
        P[i].ikisaki = j+1;
      }
    }
  }

  rep(i,N){cout << P[i].ikisaki << endl;}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repd(i, n) for (int i = n; i >= 1; i--)
#define mod 1000000007
#define MOD 998244353
#define inf 1e20
typedef long long int ll;
typedef pair<ll, ll> p;


int main() {
	string a, b;
	cin >> a >> b;
	int check = stoi(a + b);
	rep(i, 334) {
		if (i*i == check) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

//Ctrl+Aを使わない

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

using namespace std;

#define MAX_N 32768

bitset<MAX_N> primes;

void make_cache() {
    primes.set(); primes.reset(0); primes.reset(1);
    for (int i = 2; i < MAX_N; i++) {
        if (primes[i]) {
            for (int j = i + i; j < MAX_N; j += i) {
                primes.reset(j);
            }
        }
    }
}

int solve(int n) {
    if (n == 4) return 1;
    int count = 0;
    for (int i = 3; i <= n / 2; i+=2) {
        if (primes[i] && primes[ n - i ]) count++;
    }
    return count;
}

int main() {
    int n;
    make_cache();
    while (cin >> n) {
        if (n == 0) break;
        cout << solve(n) << endl;
    }
    return 0;
}

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

using namespace std;

#define fastio cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(0)
typedef long long ll;
//#define int ll
#define swap(x, y)((x)^=(y)^=(x)^=(y))
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> matrix;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(c) c.begin(),c.end()
#define mp make_pair
#define pb push_back
#define f first
#define tcase int _; cin>> _; for( ; _; --_)
#define s second
#define endl '\n'
const int MAX = 1e6+1;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const double DEG = 180/PI;
const int MOD = 1e9+7;
int mod(int x, int m){ if(x >= 0) return x % m; if(-x < m) return m-(-x); return mod(x%m, m);}
int gcd (int a, int b) {while(b){a = mod(a, b); swap(a, b);} return a;}
int lcm (int a, int b) {return a / gcd(a, b) * b;}
int fexp(int base, int exp, int m){
	int total = 1;
	while(exp > 0){
		if(exp % 2 == 1){
			total = mod(((mod(total, m)) * (mod(base, m))), m);
			exp--;
		}
		base= mod((mod(base, m) * mod(base, m)), m);
		exp /= 2;
	}
	return mod(total, m);
}

int n;

void solve(){
	int k;
	cin>> n>> k;

	vi h(n);

	for(int &i: h) cin>> i;

	int dp[n+1];
	for(int i = 0; i<n; ++i) dp[i] = INF;
	dp[0] = 0;
	dp[1] = abs(h[0] - h[1]);
	for(int i = 0; i<n; ++i)
		for(int j = 1; j<=k && i+j < n; ++j) dp[i+j] = min(dp[i] + abs(h[i] - h[i+j]), dp[i+j]);

	cout<< dp[n-1]<< endl;

}

int32_t main(){
	fastio;
	solve();
	return 0;
}


Measured memory_bytes: 4008
from collections import Counter
n = int(input())
data = [k for k in input()]

ans = Counter(data)
for i in range(n-1):
  tmp = Counter([k for k in input()])
  for j in set(data):
    ans[j] = min(ans[j], tmp[j])
#    print(j, ans[j], tmp[j], min(ans[j], tmp[j]))
ans_list = list(set(list(ans.elements())))
ans_list.sort()
answer = ""
for i in ans_list:
  answer += i*ans[i]
print(answer)


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

int main()
{
    string str;
    int a, b;
    cin>>a>>b;
    string StringArray[a];
    for(int i=0; i<a; i++){
        cin>>str;
        StringArray[i] = str;
    }
    sort(StringArray,StringArray+a);

    for(int i = 0; i < a; i++){
    cout << StringArray[i];
    }


    return 0;
}


Measured memory_bytes: 256
N = gets.chomp.to_i

word = gets.chomp

count = 0

def get_leftmost_w_and_rightmost_r(word)
  [word.index('W'), word.rindex('R')]
end

leftmost_w, rightmost_r = get_leftmost_w_and_rightmost_r(word)

while !leftmost_w.nil? && !rightmost_r.nil? && leftmost_w < rightmost_r
  word[leftmost_w] = 'R'
  word[rightmost_r] = 'W'
  count += 1
  leftmost_w, rightmost_r = get_leftmost_w_and_rightmost_r(word)
end

puts count

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

#define ll long long

using namespace std;

ll a,b,k;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b>>k;
    if (k>=a) {
          k-=a;
        a=0;
        if (k>=b) b=0;
        else b=b-k;
    }
    else a=a-k;
    
    cout<<a<<" "<<b;
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args){
  
    Scanner sc = new Scanner(System.in);
    Integer cost = sc.nextInt();
    Double d = Math.ceil(cost/1000.0);
   
    System.out.println(new Double((d*1000)-cost).intValue());
  }
}

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

using namespace std;


int main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    
    int n, c1 = 0, c2 = 0, c3 = 0, c4 = 0;
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        if(s == "AC")
            c1 += 1;
        if(s == "WA")
            c2 += 1;
        if(s == "TLE")
            c3 += 1;
        if(s == "RE")
            c4 += 1;

    }
    cout << "AC " << "x " << c1 << "\n" << "WA " << "x " << c2 << "\n"
         << "TLE " << "x " << c3 << "\n" << "RE " << "x " << c4 << "\n";

}

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

int main() {
	int n,a=0,b,k=1000000000;

	std::array<int,10> ar;

	std::cin >> n;

	b = n;

	for (int i = 0; i < ar.size(); i++) {
		ar[i] = n / k;
		n = n % k;
		k = k / 10;
	}

	for (int i = 0; i < ar.size(); i++) {
		a = a + ar[i];
		
	}


	std::cout<<(0==b%a? "Yes":"No")<<std::endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
#define MAXX 200010
 
#define PI   3.14159265358979323846264338327950
 
#define PB push_back 
#define F first
#define S second
 
#define ll 	long long int
 
#define mod  1000000007
 
 
int main()
{
	FAST;
	int n;
	cin >> n;
	int a[n+5];
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 1; i < n; i ++){
		if(a[i] > a[i-1]){
			a[i] -= 1;
		}
		
	}
	for(int i = 1; i < n; i++){
		if(a[i] < a[i-1]){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 3996
from collections import deque

N = int(input())
FF = [list(map(int, input().split())) for _ in range(N)]
P = [list(map(int, input().split())) for _ in range(N)]

ans = -10**10
q = deque()
q.append([])
while q:
  x = q.pop()
  if len(x) == 10:
    tmp = 0
    i = 0
    while i < N:
      tmp += P[i][sum([x[j]*FF[i][j] for j in range(10)])]
      i += 1
    ans = max(ans, -10**10 if sum(x) < 1 else tmp)
  else:
    q.append(x+[0])
    q.append(x+[1])
print(ans)

Measured memory_bytes: 42604
R,G,B,N=[int(c) for c in input().split()]

C=sorted([R,G,B])



if(C==[1,1,1]):
	print((N+2)*(N+1)//2)
	exit()






count=0
for i in range(N//C[2]+1):
	for j in range(N//C[1]+1):
		if(N-C[2]*i-C[1]*j>=0 and (N-C[2]*i-C[1]*j)%C[0]==0):
			count+=1
print(count)



Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
//#define _USE_MATH_DEFINES
#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
#include<string.h>
#define P(type,x) fprintf(stdout,"%"#type"\n",x)
int main() {
	int n;
	int m, e, j;
	while (~fscanf(stdin, "%d", &n), n != 0){
		while (n--) {
			fscanf(stdin, "%d%d%d", &m, &e, &j);
			if (m == 100 || e == 100 || j == 100 || (m + e) / 2 >= 90.0 || (m + e + j) / 3 >= 80.0) puts("A");
			else if ((m + e + j) / 3 >= 70.0 || (((m + e + j) / 3 >= 50.0) && (m >= 80 || e >= 80))) puts("B");
			else puts("C");
		}
	}
	return 0;
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD=1e9+7;
 
//const int MOD=998244353;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    long long d,a;
    
    cin>>n>>d>>a;
    
    vector<pair<long long,long long>> vp(n);
    
    for(auto &p:vp){
        long long x,y;
        cin>>x>>y;
        p={x,y};
    }
    long long ans=0;
    sort(vp.begin(),vp.end());
    queue<pair<long long,long long>> ops;
    long long ptot=0;
    for(auto p:vp){
        while(ops.size() && ops.front().first<p.first){
            ptot-=ops.front().second;
            ops.pop();
        }
        long long rem=p.second-ptot;
        
        if(rem>0){
            long long mult=(rem/a)+(bool)(rem%a);
            ans+=mult;
            ptot+=mult*a;
            ops.push({p.first+2*d,mult*a});
        }
    }
    cout<<ans;
    
    
    
    
    
    return 0;
}


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define ld long double
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
#define dbg2(a,b) cerr << #a << " = " << a << " " << #b << " = " << b << '\n';              

typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

int main(){

	IOS
	int a,b,c;
	cin >> a >> b >> c;
	int ans = a + b;
	ans = min(ans,b + c);
	ans = min(ans,a + c);

	cout << ans << '\n';

}

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

using namespace std;
int a[1005],b[1005];
int dp[10005];
int main(){
	int h,n;
	cin>>h>>n;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=0;i<=h;i++)dp[i]=1e9;
	dp[0]=0;
	for(int i=0;i<=h;i++){
		for(int j=0;j<n;j++)
		dp[i]=min(dp[max(0,i-a[j])]+b[j],dp[i]);
	}
	cout<<dp[h];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long int ll;
int a[200006],b[200006],c[200006],n;
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	ios;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		int x,y;
		cin>>x>>y;
		a[i]=x+y;
		b[i]=x-y;
		c[i]=y-x;
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	sort(c+1,c+1+n);
	int mx=a[n]-a[1];
	mx=max(mx,abs(b[n]+c[n]));
	cout<<mx<<'\n';
}

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

int main() {
    string S;
    cin >> S;

    int N = S.size();
    int W = 0, B = 0;
    vector<int> place(N);
    rep(i, N) {
        if (S[i] == 'W') {
            place[i] = W;
            ++W;
        } else {
            place[i] = B;
            ++B;
        }
    }
    ll ans = 0;
    rep(i, N) {
        if (S[i] == 'W') {
            ans += i - place[i];
        } else {
            ans += W + place[i] - i;
        }
    }
    cout << ans / 2 << endl;
}

Measured memory_bytes: 4456
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            // while (true)
            solve(in);
        }
    }

    private static void solve(Scanner in) {
        int K = in.nextInt(), S = in.nextInt();
        int count = 0;
        for (int x = 0; x < K + 1; x++) {
            for (int y = 0; y < K + 1; y++) {
                int z = S - (x + y);
                if (z >= 0 && z <= K) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 9300
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
#define INF 10000000


int main(){
	int n;
	while(cin>>n){
		if(n==0)break;
		int t=1000-n;
		int res=0;
		while(t>=500)res++,t-=500;
		while(t>=100)res++,t-=100;
		while(t>=50)res++,t-=50;
		while(t>=10)res++,t-=10;
		while(t>=5)res++,t-=5;
		res+=t;
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
N = int(input())
Red, Blue = [], []
for i in range(N):
    a, b = map(int, input().split())
    Red.append((a, b))
for i in range(N):
    c, d = map(int,input().split())
    Blue.append((c, d))
Blue.sort()

Ans = 0
for b in Blue:
    temp = (-1, -1)
    for r in Red:
        if r[0] < b[0] and r[1] < b[1]:
            if temp[1] < r[1]:
                temp = r
    if temp != (-1, -1):
        Ans += 1
        Red.remove(temp)
  
print(Ans)

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

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

	int l=s.size();
	if (l==1)
	{
		cout << s << endl;
		return 0;
	}
	uint64_t bit_max=1<<(l-1);
	uint64_t total_sum=0;
	for (uint64_t i=0;i<bit_max;++i)
	{
		uint64_t sum=0, u=0;
		int j;
		for (j=0;j<l-1;++j)
		{
			u*=10;
			u+=s.at(j)-'0';
			if ( (i&(1<<j)) !=0)
			{
				sum+=u;
				u=0;
			}
		}
		u*=10;
		u+=s.at(j)-'0';
		sum+=u;
		//fprintf(stderr,"bitmap: %lu, sum: %lu\n",i,sum);

		total_sum+=sum;
	}
	cout << total_sum << endl;


}



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

using namespace std;

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

  int n;
  cin >> n;
  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i].second >> v[i].first;
  }
  sort(v.begin(), v.end());
  int t = 0;
  for (int i = 0; i < n; i++) {
    t += v[i].second;
    if (t > v[i].first) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <queue>
#include <stack>
#include <climits>
#include <array>
using namespace std;

typedef long long ll;
#define pb push_back

#define rep(i, n) for (int i=0;i<(n);++i)
#define rep2(i, s, n) for (int i=s;i<(n);++i)
#define rev(i, n) for (int i=(n);i>0;--i)
#define INF (1e9+1e9)

int main() {
    int H,W; cin>>H>>W;

    array<int, 10> c[10];
    rep(i,10) rep(j,10) {
        int cij; cin >> cij;
        c[i][j] = cij;
    }
    rep(k, 10) rep(i, 10) rep(j, 10)
        if( c[i][j] > c[i][k] + c[k][j]) c[i][j] = c[i][k] + c[k][j];

    //vector<int, W> A[H];
    int total = 0;

    rep(i, H) rep(j, W) {
        int Aij; cin >> Aij;
        if (Aij != -1) total += c[Aij][1];
    }
    cout << total << endl;
}

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

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

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

const double eps = 1e-10;

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

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

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

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

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

int64 N;
vector<int64> a;
vector<int64> G[212345];
vector<int64> res;
stack<PLL> undo;
vector<int64> lis;

void dfs(int64 v, int64 p) {
  int64 idx = lower_bound(all(lis), a[v]) - lis.begin();
  undo.emplace(idx, lis[idx]);
  lis[idx] = a[v];
  res[v] = lower_bound(all(lis), INF_LL) - lis.begin();

  for (auto& u: G[v]) {
    if (u == p) continue;
    dfs(u, v);
  }

  lis[undo.top().fs] = undo.top().sc;
  undo.pop();
}

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

	cin >> N;
	a.resize(N);
	res.resize(N, 0);
	lis.resize(N, INF_LL);
	REP(i, N) cin >> a[i];
	REP(i, N-1) {
	  int64 u, v;
	  cin >> u >> v; u--; v--;
	  G[u].push_back(v);
	  G[v].push_back(u);
	}
	dfs(0, -1);
	REP(i, N) {
	  cout << res[i] << endl;
	}
}


Measured memory_bytes: 39264
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef pair<int,int> pii;
const int N = 5e5 + 7;
//--------head---------
struct Edge {
	int u, v, c;
	void in() {
		cin >> u >> v >> c;	
	}
} E[N];
int n, m, tot;
map<pii, int> R;
map<pii, int>::iterator it;
vector<pii> e[N];
void ins(int u, int c) {
	pii p = mp(u, c);
	if (R.find(p) == R.end())
		R[p] = ++tot;
}
void addEdge(int u, int v, int c) {
	int x = R[mp(u, c)], y = R[mp(v, c)];
	e[x].pb(mp(v, 0)), e[x].pb(mp(y, 0));
}
bool vis[N];
int dis[N];
priority_queue<pii> que;
int solve() {
	rep(i, 0, tot + 1)
		vis[i] = false, dis[i] = -1;
	que.push(mp(0, 1));
	while (!que.empty()) {
		int u = que.top().second, d = -que.top().first;
		que.pop();
		if (vis[u])
			continue;
		dis[u] = d, vis[u] = true;
		rep(i, 0, sz(e[u])) {
			int v = e[u][i].first, w = e[u][i].second;
			if (!vis[v])
				que.push(mp(-(d + w), v));
		}
	}
	int ans = dis[n];
	rep(i, 0, sz(e[n])) {
		int v = e[n][i].first;
		if (~dis[v] && (ans == -1 || dis[v] < ans))
			ans = dis[v];
	}
	return ans;
}
int main() {
	cin >> n >> m;
	tot = n;
	rep(i, 0, m) {
		E[i].in();
		ins(E[i].u, E[i].c), ins(E[i].v, E[i].c);
	}
	for (it = R.begin(); it != R.end(); ++it) {
		pii p = it->first;
		int v = it->second;
		e[p.first].pb(mp(v, 1));
	}
	rep(i, 0, m) {
		int u, v, c;
		u = E[i].u, v = E[i].v, c = E[i].c;
		addEdge(u, v, c), addEdge(v, u, c);
	}
	cout << solve() << endl;
	return 0;
}


Measured memory_bytes: 62844
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        char[] S = scanner.next().toCharArray();
        int N = S.length;

        int half = (N - 1) / 2;
        int quat = half / 2;

        // N = 11 half = (11 - 1)/2 = 5 quat = 5 / 2 = 2.5 = 2
        // N = 13 half = (13 - 1)/2 = 6 quat = 6 / 2 = 3

        for (int i = 0 ; i < half ; i++) {
            if (S[i] != S[N - 1 - i]) {
                System.out.println("No");
                return;
            }
        }

        // 0 1 2 3 4 5 6 7 8 9 10
        // 0-4 6-10
        // 1-3 7-9

        for (int i = 0 ; i < quat ; i++) {
            if (S[i] != S[half - 1 - i] || S[half + 1 + i] != S[N - 1 - i]) {
                System.out.println("No");
                return;
            }
        }

        System.out.println("Yes");

        // akasaka Yes
        // level No
        //
    }
}


Measured memory_bytes: 22100
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
 
#define PB push_back
#define MP make_pairA
#define REP(i,n) for(int i=0;i<(n);i++)
int main()
{
    int n,k;
    string s;
    cin>>n>>k;
    cin>>s;
    k--;
    s[k]=(char)(s[k]-'A'+'a');
    cout<<s<<endl;
}

Measured memory_bytes: 256
n=int(input())
list=[list(map(int,input().split())) for _ in range(n)]
list1=sorted(list, key=lambda x:x[1])
t=0
for i in range(n):
  t+=list1[i][0]
  if not t<=list1[i][1]:
    print("No")
    break
else:
  print("Yes")


Measured memory_bytes: 48588
S = input()
L = int(S[0:2])
R = int(S[2:4])
if 0 < L <= 12 and 0 < R <= 12:
    print("AMBIGUOUS")
elif 0 < L <= 12:
    print("MMYY")
elif 0 < R <= 12:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 9160
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    string s;
    int n;
    cin >> s >> n;
    /*
    string copyed;
    copyed.resize(s.size());
    copy(s.begin(), s.end(), copyed.begin());
    sort(copyed.begin(), copyed.end());
    */
    set<string> sub;
    rep(i, s.size()){
        rep(j, min(5, (int)(s.size() - i))){
            sub.insert(s.substr(i, j + 1));
        }
    }
    int num = 0;
    repi(i, sub){
        ++num;
        if(num == n){
            cout << *i << endl;
            return 0;
        }
    }
    return 0;
}


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

int ans[200005];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x;
		cin >> x;
		ans[x] ++;
	}
	for (int i = 1; i <= n; i++)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}


Measured memory_bytes: 3924
import java.util.*;

public class Main {
  private static long INF = 1_000_000_000_000L;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int Q = sc.nextInt();
    
    long[] s = new long[A+2];
    s[0] = -INF;
    s[A+1] = INF;
    for (int i = 1; i <= A; i++) {
      s[i] = sc.nextLong();
    }
    
    long[] t = new long[B+2];
    t[0] = -INF;
    t[B+1] = INF;
    for (int i = 1; i <= B; i++) {
      t[i] = sc.nextLong();
    }
    
    for (int i = 0; i < Q; i++) {
      long x = sc.nextLong();
      int sr = search(s, x);
      int tr = search(t, x);
      long min = INF;
      min = Math.min(min, x-Math.min(s[sr-1], t[tr-1]));
      min = Math.min(min, Math.max(s[sr], t[tr])-x);
      min = Math.min(min, 2*(x-s[sr-1])+(t[tr]-x));
      min = Math.min(min, (x-s[sr-1])+2*(t[tr]-x));
      min = Math.min(min, 2*(x-t[tr-1])+(s[sr]-x));
      min = Math.min(min, (x-t[tr-1])+2*(s[sr]-x));
      
      System.out.println(min);
    }
  }
  
  private static int search(long[] a, long x) {
    int ng = 0;
    int ok = a.length-1;
    while (Math.abs(ok-ng) > 1) {
      int m = (ok+ng)/2;
      if (x <= a[m]) {
        ok = m;
      } else {
        ng = m;
      }
    }
    
    return ok;
  }
}

Measured memory_bytes: 92720
#include<iostream>
#define ll long long
using namespace std;
ll gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
} 
   
int main(){
	int n;
	cin >> n;
	long long sum = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++){
				sum += gcd(i, gcd(j, k));
			}
		}
	}
	cout << sum;
}

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(i,s,e) for(ll i=s;i<e;i++ )
typedef pair<ll,ll> P;
const ll mod = 1000000007;
const ll INF = 1000000009;
ll i;

int main(){
    ll A,B;
    char c;
    cin>>A>>c>>B;
    if(c=='+')cout<<A+B;
    else cout<<A-B;
    cout<<endl;
}



Measured memory_bytes: 256