akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define um unordered_map
#define us unordered_set
#define f first
#define s second
#define pb push_back
#define MOD 998244353
#define eps 1e-9
#define INF 1000000002

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
const int N = 303;

int n;
int main() {
    int n;
    cin>>n;
    vector<pii> vec;
    for(int i=0;i<n;i++) {
        int x;
        cin>>x;
        vec.pb({x, i+1});
    }
    sort(vec.begin(), vec.end());
    for(pii p : vec)
        cout<<p.s<<" ";
    return 0;
}


Measured memory_bytes: 1780
#[allow(unused_imports)]
use std::cmp::Reverse;

#[allow(unused_imports)]
use proconio::{fastout, input, marker::Chars};

#[allow(unused_imports)]
use itertools::Itertools;

#[fastout]
pub fn main() {
    input! {
        n: usize,
    }
    match n % 10 {
        0 | 1 | 6 | 8 => println!("pon"),
        2 | 4 | 5 | 7 | 9 => println!("hon"),
        _ => println!("bon"),
    }
}


Measured memory_bytes: 2132
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


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

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)






int main() {
    ll n;
    cin >> n;
    vector<ll> y = {1};
    for(ll i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            y.push_back(i);
            y.push_back(n / i);
        }
    }
    sort(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    map<ll, bool> out;
    vector<ll> v;
    for(ll i = y.size() - 1; i >= 1; i--){
        if(out[y[i]]) continue;
        v.push_back(y[i]);
        for(ll j = 2; j <= sqrt(y[i]); j++){
            if(y[i] % j == 0){
                out[j] = true;
                out[y[i] / j] = true;
            }
        }
    }
    if(v.empty()) v.push_back(1);
    cout << v.size() << " " << y.size() << endl;
}



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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root, NIL;
int maxh;

Node treeSearch(Node u, int k){
  while( u != NIL && k != u->key ){
    if ( k < u->key ) u = u->left;
    else u = u->right;
  }
  return u;
}

void insert(int k){
  int H;
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while( x != NIL ){
    y = x;
    if ( z->key < x->key ){
      x = x->left;
    } else {
      x = x->right;
    }
  }

  z->parent = y;
  if ( y == NIL ){
    root = z;
  } else {
    if (z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
}

void inorder(Node u){
  if ( u == NIL ) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node u){
  if ( u == NIL ) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  maxh = 0;
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}



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

#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
int main() {
  int T;
  cin >> T;
  vector<ll> Ans(0);
  REP(i, T) {
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    Ans.push_back(floor_sum(n, m, a, b));
  }
  REP(i, T) { cout << Ans[i] << endl; }
}

Measured memory_bytes: 4240
#include<bits/stdc++.h>
#include <stdio.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define popb pop_back()
#define sz size()
using namespace std;
typedef long long ll;
///////////////////////////////////////////
string s;
int main(){
    cin>>s;
    for(int i=0;i<s.sz;i++){
        if(i%2==0) cout<<s[i];
    }
}


Measured memory_bytes: 512
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long int ull;
void power(ull m, ull n, ull mod)
{
  ull ans = 1;
  while(n > 0)
  {
    if(n & 1) ans = ans * m % mod;
    m = m * m % mod;
    n = n >> 1;
  }
  printf("%d\n", ans);
}

int main()
{
  ull m, n, mod = 1000000007;
  scanf("%llu%llu", &m, &n);
  power(m, n, mod);
  return 0;
}



Measured memory_bytes: 3212
n = int(input())
a = list(map(int, input().split()))
S = [0]*n
for i in range(0, n):
    if i > 0:
        S[i] = S[i-1] + a[i]
    else:
        S[i] = a[i]
ans = int(0)
m = int(1000000007)
for i in range(0, n):
    ans = (ans + (a[i] * (S[n-1]-S[i]))) % m
print(ans)

Measured memory_bytes: 105260
N = input()
ans = 0
def counths(n,i,j):
    s = int(n)
    bot = sum([10**x for x in range(len(n)-2)])
    if int(n[0]) > i:
        top = 10**(len(n)-2)
    elif int(n[0]) < i:
        top = 0
    else:
        a = i * 10 ** (len(n)-1) + j
        if a < s:
            top = (s-a) // 10 + 1
        elif a == s:
            top = 1
        else:
            top = 0
    if i == j:
        if len(n) > 1:
            bot += 1
        else:
            if s >= i:
                bot += 1
    return bot + top
for i in range(1,10):
    for j in range(1,10):
        ans += counths(N,i,j) * counths(N,j,i)
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n) { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x) { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int t, p, r;
	while (cin >> t >> p >> r, t) {
		vvi pena(t, vi(p, 0));
		vector<pair<int, pii>> point(t);//ac time team
		REP(i, t) {
			point[i].second.second = (i + 1);
		}
		REP(i, r) {
			int t2, p2, time;
			string res;
			cin >> t2 >> p2 >> time >> res;
			t2--;
			p2--;
			if (res == "CORRECT") {
				point[t2].first--;
				point[t2].second.first += time + pena[t2][p2]*1200;
			}
			else {
				pena[t2][p2]++;
			}
		}
		SORT(point);
		REP(i,t) {
			cout << point[i].second.second << " " << -point[i].first << " " << point[i].second.first << endl;
		}
	}
}

Measured memory_bytes: 3144
#import math
N = int(input())
T = []
for i in range(N):
  T.append(int(input()))
# output LCM(T1,T2... Tn)=LCM(Tn,LCM(Tn-1,LCM(...)))
def gcd(a,b): #Recusion!!
  if min(a,b) == 0:
    return max(a,b)
  else:
    return gcd(min(a,b),max(a,b)%min(a,b))
    
"""
  mi = min(a,b)
  ma = max(a,b)
  ans = 1
  '''for i in range(2,mi+1):
    if (mi%i)+(ma%i) == 0:
      mi /= i
      ma /= i
      ans *= i
      i -= 1'''
  while True:
    #print(ma,mi)
    if (ma % mi) == 0:
      ans = mi
      break
    else:
      mi = ma%mi
      ma = mi
      
  return ans"""


def lcm(a,b):
  #g = math.gcd(a,b)
  g = gcd(a,b)
  #print(g)
  return int(a*b//g)
ans = T[0]
for i in range(1,len(T)):
  ans = lcm(ans,T[i])
print(ans)


Measured memory_bytes: 38256
N,L=map(int,input().split())
#L+i-1,i>=1
nin=10**6
for i in range(N):
    if abs(L+i)<nin:
        nin=abs(L+i)
        nn=L+i

ans=N*(L-1)+N*(N+1)*0.5-(nn)

print(int(ans))


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

int main(void){
    int n=0;
    int h[100]={0};
    int num=0;
    int flag=0;

    cin >> n;

    for(int count=0;count<n;count++){
        cin >> h[count];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            if(h[j]<=h[i]){
                flag=1;
            }else{
                flag=0;
                break;
            }
        }
        if(flag==1)num++;
    }

    cout << num << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getC(char ch){
	if(ch=='A')return 1;
	else if(ch=='C')return 2;
	else if(ch=='G')return 3;
	else if(ch=='T')return 4;
	else return 0;
}

long long getk(char str[]){
	long long sum=0,p=1,i;
	for(i=0;i<strlen(str);i++){
		sum += p*(getC(str[i]));
		p*=5;
	}
	return sum;
}

int h1(int key){return key%M;}
int h2(int key){return 1+(key%(M-1));}
	
int find(char str[]){
	long long key,i,h;
	key=getk(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0)return 0;
	}
	return 0;
}

int insert(char str[]){
	long long key,i,h;
	key=getk(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0){
			strcpy(H[h],str);
			return 0;
		}
	}
	return 0;
}

int main(){
	int i,n;
	char str[L],com[9];
	for(i=0;i<M;i++)H[i][0]='\0';
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s %s",com,str);
		
		if(com[0]=='i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}
	return 0;
}



Measured memory_bytes: 16056
fun main(args: Array<String>) {
    var str = readLine()!!.toString()
    val q = readLine()!!.toInt()

    (0 until q).forEach { _ ->
        val command = readLine()!!.toString().split(" ")
        val op = command[0]
        val a = command[1].toInt()
        val b = command[2].toInt()
        val s = str.slice(0 until a)
        val m = str.slice(a .. b)
        val e = str.slice(b+1 until str.length)
        when(op) {
            "print" -> println(m)
            "reverse" -> str = s + m.reversed() + e
            "replace" -> str = s + command[3] + e
        }
    }
}


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

int main() {
    int A[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            std::cin >> A[i][j];
        }
    }
    
    int N;
    std::cin >> N;

    int b;
    bool B[3][3] = {false};
    for (int i = 0; i < N; ++i) {
        std::cin >> b;

        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (A[i][j] == b) {
                    B[i][j] = true;
                    break;
                }
            }
        }
    }

    if ((B[0][0] && B[0][1] && B[0][2]) ||      
        (B[1][0] && B[1][1] && B[1][2]) ||      
        (B[2][0] && B[2][1] && B[2][2]) ||      
        (B[0][0] && B[1][0] && B[2][0]) ||      
        (B[0][1] && B[1][1] && B[2][1]) ||      
        (B[0][2] && B[1][2] && B[2][2]) ||      
        (B[0][0] && B[1][1] && B[2][2]) ||      
        (B[0][2] && B[1][1] && B[2][0])
    ) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    } 

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>

int main() {
    int S;
    scanf("%d",&S);
    int h = S / 3600;//時間
    S %= 3600;// S = S % 3600
    int m = S / 60;//分
    int s = S % 60;//秒

    printf("%d:%d:%d\n",h,m,s);
    return 0;
}


Measured memory_bytes: 2728
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> ab(N, 0);

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        ab[a]++;
        ab[b]++;
    }

    bool flag = true;
    rep(i, N) {
        if (ab[i] % 2) {
            flag = false;
            break;
        }
    }

    cout << (flag ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
	Scanner sc = new Scanner (System.in);
	ArrayList<String> slist = new ArrayList<>();

	String s = sc.next();
	boolean three = false;
	int count = 0;
	int max = 0;

	if(s.equals("RRR")) {
		max = 3;
	}else {
		for(int i = 0; i < 3; i++) {
			slist.add(s.substring(i, i+1));
		}

		for(int i = 0; i < 3; i++) {
			if(slist.get(i).equals("R")) {
				three = true;
			}else {
				three = false;
				break;
			}
		}

		for(int i = 0; i < 3; i++) {
			if(slist.get(i).equals("R")) {
				count++;
			}else if(slist.get(i).equals("S")) {
				if(max < count) {
					max = count;
					count = 0;
				}
			}
		}
	}
	if(three == true) {
		System.out.println("3");
	}else if(count > max) {
		System.out.println(count);
	}else {
		System.out.println(max);
	}

}
}


Measured memory_bytes: 35564
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author phantom11
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            String s = in.next();
            int n = s.length();
            out.printLine(s.charAt(0) + "" + (n - 2) + "" + s.charAt(s.length() - 1));
        }

    }

    static class InputReader {
        BufferedReader in;
        StringTokenizer tokenizer = null;

        public InputReader(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(in.readLine());
                }
                return tokenizer.nextToken();
            } catch (IOException e) {
                return null;
            }
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }
}



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

#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define viit vector<int>::iterator
#define MOD 1000000007
#define endl "\n"
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repe(i, a, b) for (int i = (a); i <= (b); i++)
#define repd(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vi h(n), a(n, INT_MAX);
    rep(i, 0, n) cin >> h[i];
    a[0] = 0;
    rep(i, 1, n) {
        rep(j, i > k ? (i - k) : 0, i) {
            a[i] = min(a[i], abs(h[i] - h[j]) + a[j]);
        }
    }
    cout << a[n - 1];
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                              \
  ifstream in("atcoder-problems/abc131_c.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v)                        \
  rep(l, v.size()) { cout << v[l] << " "; } \
  cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  ll A, B, C, D;
  cin >> A >> B >> C >> D;

  ll _lcm = lcm(C, D);
  ll n = B - A + 1;
  ll db = B / C + B / D - B / lcm(C, D);
  ll da = (A - 1) / C + (A - 1) / D - (A - 1) / lcm(C, D);

  ll ans = n - db + da;

  cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7
N = int(input())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(x=1,parent=None):
    b,w = 1,1 # 子がすべて白、子が何でもよい
    for y in graph[x]:
        if y == parent:
            continue
        b1,w1 = dfs(y,x)
        b *= w1
        w *= (b1+w1)
        b %= MOD
        w %= MOD
    return b,w

b,w = dfs()
answer = (b+w) % MOD
print(answer)

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

const int MAX=1e5+10;
const int MOD=1e9+7;

vector<int> g[MAX];

long long dp[MAX][2];

void dfs(int u,int pa=-1){
    dp[u][1]=dp[u][0]=1;
    for(auto v:g[u]){
        if(v==pa) continue;
        dfs(v,u);
        dp[u][1]*=(dp[v][0]+dp[v][1]);
        dp[u][1]%=MOD;
        dp[u][0]*=dp[v][1];
        dp[u][0]%=MOD;
    }
}

int main(){
    int N; cin >> N;
    for(int i=0;i<N-1;i++){
        int x,y; cin >> x >> y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(0);
    long long ans=(dp[0][0]+dp[0][1])%MOD;
    cout << ans << endl;
}

Measured memory_bytes: 14208
#include <iostream>

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

  int N, M;
  int S[11][11] = {0};
  int C[11] = {0};
  std::cin >> N >> M;

  for (int i = 0; i < M; i++) {
    std::cin >> C[i];
    for (int j = 0; j < C[i]; j++) {
      int s;
      std::cin >> s;
      S[i][j] = (s - 1);
    }
  }

  int P[11];
  for (int i = 0; i < M; i++) {
    std::cin >> P[i];
  }

  int ans = 0;
  for (int bit = 0; bit < (1 << N); bit++) {
    int on_count = 0;
    for (int i = 0; i < M; i++) {
      int c = C[i];
      int on = 0;
      for (int j = 0; j < c; j++) {
        if (bit & (1 << S[i][j])) {
          on++;
        }
      }
      if (on % 2 == P[i]) {
        on_count++;
      }
    }
    if (on_count == M) {
      ans++;
    }
  }

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#include<iostream>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
signed main(){
    ll n;cin>>n;
    vector<vector<ll> >G(n);
    map<pll,ll>idx;
    rep(i,n-1){
        ll a,b;cin>>a>>b;
        a--;
        b--;
        idx[mp(a,b)]=i;
        idx[mp(b,a)]=i;
        G[a].pb(b);
        G[b].pb(a);
    }
    ll m;cin>>m;
    vector<ll>con(m);
    rep(i,m){
        ll u,v;
        cin>>u>>v;
        u--;v--;
        queue<ll>q;
        q.push(u);
        vector<ll>pre(n);
        vector<ll>used(n);
        used[u]=1;
        while(!q.empty()){
            ll k=q.front();
            q.pop();
            used[k]=1;
            for(auto to:G[k]){
                if(used[to])continue;
                pre[to]=k;
                q.push(to);
            }
        }
        ll cnt=0;
        ll now=v;
        while(pre[now]!=u){
            cnt+=(1LL<<idx[mp(now,pre[now])]);
            now=pre[now];
        }
        cnt+=(1LL<<idx[mp(now,pre[now])]);
        con[i]=cnt;
        //cout<<con[i]<<endl;
    }
    ll ans=1LL<<(n-1);
    vector<pll>katu(m+1);
    vector<ll>d(m+1);
    rep(i,1LL<<m){
        ll now=0;
        ll cnt=0;
        rep(j,m){
            if((1LL<<j)&i){
                cnt++;
                now|=con[j];
            }
        }
        ll cnt2=0;
        rep(j,n-1){
            if(now&(1LL<<j))cnt2++;
        }
        if(cnt==0)continue;
        ll res=(1LL<<(n-1-cnt2));
        katu[cnt].first+=res;
        d[cnt]++;
    }
    rep(i,m+1){
        if(i==0)continue;
        if(i%2)katu[i].second=-1;
        else katu[i].second=1;
    }
    sort(all(katu));
    rep(i,m+1){
        ans+=katu[i].first*katu[i].second;
    }
    //cout<<ans<<endl;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cctype>

using namespace std;

bool issame(char a, char b) {
    return toupper(a) == toupper(b);
}

int main(void) {

    string w, line;
    cin >> w;

    int total = 0;
    while (true) {
        cin >> line;
        if (line == "END_OF_TEXT") { break; }
        if (line.size() == w.size()) {
            bool ok = true;
            for (int i = 0; i < w.size(); ++i) {
                if (toupper(w[i]) != toupper(line[i])) {
                    ok = false; break;
                }
            }
            if (ok) { ++total; }
        }
    }

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

    return 0;
}

Measured memory_bytes: 1200
x, y, a, b, c = map(int, input().split())
p = sorted(map(int, input().split()))
q = sorted(map(int, input().split()))
r = sorted(map(int, input().split()), reverse=True)
pi = len(p) - x
qi = len(q) - y
ri = 0
for _ in range(len(r)):
    if r[ri] <= min(p[min(pi, len(p)-1)], q[min(qi, len(q)-1)]):
        break
    else:
        if pi >= len(p) and qi >= len(q):
            break
        else:
            if pi < len(p) and qi < len(q):
                if p[pi] < q[qi]:
                    p[pi] = r[ri]
                    pi += 1
                else:
                    q[qi] = r[ri]
                    qi += 1
            elif pi < len(p) and qi >= len(q):
                p[pi] = r[ri]
                pi += 1
            else:
                q[qi] = r[ri]
                qi += 1
            ri += 1
print(sum(p[-x:]) + sum(q[-y:]))

Measured memory_bytes: 22720
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;
int main() {
    string S, T;
    cin >> S >> T;
    T.pop_back();
    if (S == T) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
    double A,B,C,D;
    cin>>A>>B>>C>>D;

    int i,j;
    i=ceil(C/B);
    j=ceil(A/D);
    
    if(j>=i){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

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

using namespace std;

void abc_150a();

void abc_151a();

void abc_152a();

void abc_154a();

int main()
{
  //abc_150a();
  //abc_151a();
  //abc_152a();
  abc_154a();

}

void abc_150a()
{
  int K, X;
  cin >> K >> X;

  if (500 * K >= X) cout << "Yes\n";
  else cout << "No\n";
}

void abc_151a()
{
  char C;
  cin >> C;

  cout << (char)((int)C + 1) << "\n";
}

void abc_152a()
{
  int N, M;
  cin >> N >> M;
  if (N == M) cout << "Yes\n";
  else cout << "No\n";
}

void abc_154a()
{
  string S, T;
  cin >> S >> T;
  int a, b;
  cin >> a >> b;
  string U;
  cin >> U;

  if (S == U) cout << a - 1 << " " << b << "\n";
  else cout << a << " " << b - 1 << "\n";

}


Measured memory_bytes: 3632
#include <iostream>
#include <array>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <climits>

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using namespace std;

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x = 0) :x((x% mod + mod) % mod) {}
	mint operator-() const { return mint(-x); }
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res /= a;
	}
};

struct combination {
	vector<mint> fact, ifact;
	combination(int n) :fact(n + 1), ifact(n + 1) {
		fact[0] = 1;
		for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
		ifact[n] = fact[n].inv();
		for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
	}
	mint operator()(int n, int k) {
		if (k < 0 || k > n) return 0;
		return fact[n] * ifact[k] * ifact[n - k];
	}
} comb(2000005);

mint g(int r, int c) {
	return comb(r + c + 2, r + 1) - 1;
}

bool comp(int i, int j) {
	return i > j;
}

int d[1000001];

int main()
{
	string s;
	cin >> s;
	int count = 0;
	for (int i = 1; i <= s.length(); i++)
	{
		d[i] = 0;
	}
	for (int i = 1; i < s.length(); i++)
	{
		if (s[i] == 'L')
		{
			count++;
			if (count % 2 == 0)
			{
				d[i - count]++;
			}
			else
			{
				d[i - count + 1]++;
			}
		}
		else
		{
			count = 0;
		}

	}
	count = 0;
	for (int i = s.length() - 2; i >= 0; i--)
	{
		if (s[i] == 'R')
		{
			count++;
			if (count % 2 == 0)
			{
				d[i + count]++;
			}
			else
			{
				d[i + count - 1]++;
			}
		}
		else
		{
			count = 0;
		}
	}

	for (int i = 0; i < s.length() - 1; i++)
	{
		cout << d[i] << " ";
	}
	cout << d[s.length() - 1];
}


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

int bun[] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };

int main(){

	int n;
	while (std::cin >> n){

		std::vector<int> res;

		for (int i = 9; i >= 0; i--){
			if (n >= bun[i]){
				res.push_back(bun[i]);
				n -= bun[i];
			}
		}

		for (int i = res.size() - 1; i >= 0; i--){
			if (i == 0)std::cout << res[i] << std::endl;
			else std::cout << res[i] << " ";
		}
	}

	return 0;
}

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

#define FOR(i,start,end) for(int i=start; i<(int)(end); i++)
#define REP(i,n) FOR(i,0,n)

int main() {


    int a, b;
    while(1) {
        scanf("%d %d", &a, &b);

        if(a == 0 && b == 0) {
            break;
        }

        if(a < b) {
            printf("%d %d\n", a, b);
        } else {
            printf("%d %d\n", b, a);
        }
    }

    return 0;
}



Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
 
int main() {
string s ;
cin >> s;
if( s ==  "a"  ||  s == "e" || s == "i" || s == "u" || s == "o"){
cout << "vowel" << endl;
}
else {
cout << "consonant" << endl;
}
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRT(v) sort(v.begin(),v.end())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;


int abc104_c(){
    //入力
    int a,b;
    cin >> a >> b;
    int ans = 0;
    for(int i=a; i<=b; i++) if(i==(i%10)*10000+((i%100)/10)*1000+((i%1000)/100)*100+((i%10000)/1000)*10+i/10000) ans++;
    
    //処理

    //出力
    cout << ans << ENT;
    return 0;
}

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


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

typedef int in;
#define int long long
int MAX=1e9;
int MAXEST=1e18;
int MOD=1e9+7;

int n;
int a[30][30];
int dp[1<<22];

int f(int mask){
    if(mask==(1<<n)-1){
        return 1;
    }
    int &ret=dp[mask];
    if(ret!=-1)
        return ret;
    ret=0;
    int men=__builtin_popcountll(mask);
    for(int i=0;i<n;i++){
        if(a[men][i]==0||((1<<i)&mask))
            continue;
        ret+=f(mask|(1<<i));
        ret%=MOD;
    }
    return ret;
}

in main()
{
    int tc=1;
//    cin>>tc>>st;
    while(tc--)
    {
        cin>>n;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cin>>a[i][j];
            }
        }
        memset(dp,-1,sizeof dp);
        cout<<f(0)<<endl;
    }
    return 0;
}


Measured memory_bytes: 36400
#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

char buf[20]; int w;
void mypr(int n)
{
	w = 0;
	if (!n) { buf[w++] = '0'; return; }
	while (n) buf[w++] = n%10 + '0', n/=10;
}

#define MAX_N 10000
int f[MAX_N+2];

int main()
{
	int N, i, j, c;

	N = in();
	for (i = 0; i < N; i++) f[in()]++;
	for (i = 0; ; i++) if (c = f[i]) break;
	mypr(i); j = w; while (j--) pc(buf[j]);
	while (--c) { pc(' '); j = w; while (j--) pc(buf[j]); }
	while (++i <= MAX_N) if (c = f[i]) {
		mypr(i); 
		while (c--) { pc(' '); j = w; while (j--) pc(buf[j]); }
	}
	pc('\n');
	return 0;
}



Measured memory_bytes: 2124
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use text_io::*;

fn main() {
    const U_INF: usize = 1 << 60;
    const I_INF: isize = 1 << 60;
    let n: usize = read!();
    let ans = if n % 1000 == 0 { 0 } else { 1000 - n % 1000 };
    println!("{}", ans);
}


Measured memory_bytes: 2168
import java.util.Scanner;

/** dp[n][v]: n番目の荷物までで価値がv以上の時の重さの最小値 */
public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = Integer.parseInt(scanner.next());
    int w = Integer.parseInt(scanner.next());
    int[][] wv = new int[n][2];
    int wi, vi;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2; j++) {
        wv[i][j] = Integer.parseInt(scanner.next());
      }
    }
    int v = 100001;
    long[][] dp = new long[n + 1][v + 1];
    for (int i = 0; i < n + 1; i++) {
      for (int j = 0; j < v + 1; j++) {
        dp[i][j] = 100000000000L;
      }
    }
    dp[0][0] = 0;
    for (int i = 1; i < n + 1; i++) {
      wi = wv[i - 1][0];
      vi = wv[i - 1][1];
      for (int j = 0; j < v + 1; j++) {
        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
        if (j - vi >= 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - vi] + wi);
        }
      }
    }
    for (int j = v; j >= 0; j--) {
      if (dp[n][j] > w) {
        continue;
      }
      System.out.println(j);
      break;
    }
  }
}


Measured memory_bytes: 128084
#include <stdio.h>

int main(void)
{
  int a, b;

  scanf("%d %d", &a, &b);

  for (int i = 0; i < 1100; i++){
    if (i * 2 / 25 == a && i / 10 == b){
      printf("%d", i);
      return 0;
    }
  }

  printf("%d", -1);

  return 0;
}

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

int gcd(int x,int y){
  if (y==0){
    return x;
  }
  return gcd(y,x%y);
}
 
int main() {
  int N,X;
  cin >> N >> X;
  vector<int> pos(N);
  for (int i=0;i<N;i++){
    int x;
    cin >> x;
    x-=X;
    pos[i]=abs(x);
  }
  int ans=pos[0];
  for (int i=1;i<N;i++){
    ans=gcd(ans,pos[i]);
  }
  cout << ans << endl;
}

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

string FILENAME = "template";
#define io ifstream fin(FILENAME + ".in"); ofstream fout(FILENAME + ".out")
#define fwrite(X) fout << X;
#define fwriteln(X) fout << X << endl;

#define forl(V, N) for(int V = 0; V < N; V++)
#define fore(E, X) for(auto &E:X)
#define print(X) cout << X
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
#define rem(X) X.top(); X.pop()
#define mid(A, B) ((A+B) / 2)
#define setmin(A, B) A = min(A, B)
#define setmax(A, B) A = max(A, B)
#define graph unordered_map<int, unordered_set<int>>
#define vi vector<int>
#define pb push_back
#define ll long long

int main() {
    int N;
    cin >> N;
    vector<vi> active;
    forl(i, N) {
        int A, B, C;
        cin >> A >> B >> C;
        active.pb({A, B, C});
    }
    ll dp[200006][4];
    dp[0][0] = active[0][0];
    dp[0][1] = active[0][1];
    dp[0][2] = active[0][2];
    forl(i, N-1) {
        forl(j, 3){
            forl(k, 3) {
                if(k == j) continue;
                setmax(dp[i+1][k], active[i+1][k] + dp[i][j]);
            }
        }
    }
    println(max(dp[N-1][0], max(dp[N-1][1], dp[N-1][2])));
}

Measured memory_bytes: 10672
import java.util.*;
import java.io.*;

public class Main {
	static int mod = (int) 1e9 + 7;
	static List<ArrayList<Integer>> to;
	static int dp[];
	public static void main(String[] args) {
		FastScanner fs = new FastScanner(System.in);
		int N = fs.nextInt();
		to = new ArrayList<>();
		for(int i=0;i<N;i++) to.add(new ArrayList<Integer>());
		int edges[][] = new int[N-1][2]; //どちらが子になるかdfsするまでわからないので両方持っておく
		for(int i=0;i<N-1;i++) {
			int A = fs.nextInt()-1, B = fs.nextInt()-1;
			to.get(A).add(B);
			to.get(B).add(A);
			edges[i][0] = B;
			edges[i][1] = A;
		}
		dp = new int[N];
		rec(0, -1);
		long mulsum = 0;
		for(int e[]:edges) {
			//子の配下の頂点数を知りたいので、どちらが子頂点か調べる
			int candidate1 = e[0];
			int candidate2 = e[1];
			int child = candidate1;
			if(dp[candidate1]>dp[candidate2])child = candidate2;
			
			long a = dp[child];
			long b = N - a;

			//mulは、全ケース(2^n通り)における、この辺が部分木Sに含まれる回数		
			//この辺を境にしてできる部分木2つについてそれぞれ、1つ以上黒を含む確率を求めて、掛け合わせた物に
			//2^nをかけて場合の数にした
			long mul = (modpow(2, a) - 1)*(modpow(2, b) - 1)%mod;			
			mulsum += mul;
			mulsum %= mod;
		}
		long cases = modpow(2, N);
		//PN:全ケースにおける、部分木Sに含まれる頂点数の総和
		//頂点の数は、辺の数＋１であり、辺の数が０の場合でも、黒頂点１個の空グラフがSに含まれるので問題ないが、
		//全部白頂点の場合だけはSに含まれない頂点を足してしまうことになるので、そのケースの１通りを引く
		long PN = (mulsum + (cases - 1 + mod)%mod)%mod ;//全ケースの含まれる頂点の合計
		
		//Sに含まれる黒頂点は全頂点数の半分になる（黒頂点なら必ずSに含まれるため）
		long BN = N * modpow(2, N-1) %mod;
		//Sに含まれる白頂点は、全頂点数ー黒頂点数
		long WN = (PN - BN + mod)%mod;
		long ans = WN * modpow(cases, mod-2);
		ans %= mod;
		
		System.out.println(ans);
	}
	
	static int rec(int v, int parent) {
		int res = 1;
		for(int next:to.get(v)) {
			if(next == parent) continue;
			res += rec(next, v);
		}
		return dp[v] = res;
	}
	

	static long modpow(long x, long y) {
		if(y==0) return 1;
		if(y%2!=0) return x * modpow(x, y-1) % mod;
		long tmp = modpow(x, y/2);
		return tmp * tmp % mod; 
	}
}

//高速なScanner
class FastScanner {
	private BufferedReader reader = null;
	private StringTokenizer tokenizer = null;

	public FastScanner(InputStream in) {
		reader = new BufferedReader(new InputStreamReader(in));
		tokenizer = null;
	}

	public String next() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public String nextLine() {
		if (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken("\n");
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

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

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = nextInt();
		return a;
	}

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nextLong();
		return a;
	}
}

Measured memory_bytes: 115344
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priority_queue
#define P pair<int,int>
#define P2 pair<int,P>
#define P3 pair<int,P2>
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ll LINF=1e18;
const ld PI=abs(acos(-1));

int main(){
	ll x, y; cin >> x >> y;
	
	cout << (x%y?x:-1) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#入力をN Kで受ける
N,K = map(int,input().split())
#N,Kの場合分けで最小値算出
if N <= K / 2:
    print(N)
elif N < K:
    print(K-N)
else:
    if N - N // K * K <=K /2:
        print(N - N // K * K)
    else:
        print((1 + N // K) * K - N)

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

#define SIZE 100

void insertionSort(int n, int* A){
	int v, k;
	for(int i = 1; i < n; ++i){
		v = A[i];
		k = i - 1;
		while(k >= 0 && A[k] > v) {
			A[k + 1] = A[k];
			--k;
		}
		A[k + 1] = v;
		
		for(int j = 0; j < n; ++j){
			if(j != n - 1)
				cout << A[j] << ' ';
			else
				cout << A[j] << endl;
		}
	}
}

int main(void){
	int n;
	int A[SIZE];
	
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> A[i];
	
	for(int i = 0; i < n; ++i) {
		if(i != n - 1)
			cout << A[i] << ' ';
		else
			cout << A[i] << endl;
	}
	
	insertionSort(n, A);
	
	return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    int sum = 0;
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        sum += A[i];
    }
    bitset<2002000> bs;
    bs[0] = true;
    for (int i = 0; i < N; i++) {
        bs |= (bs << A[i]); 
    }
    int ans = (sum+1)/2;
    while (!bs[ans])ans++;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=100010;

ll n;
ll a[N][3];

ll dp[N][3];

ll func(ll idx,ll t)
{
    if(idx<0){return 0;}

    if(dp[idx][t]==-1){
    ll ans=INT_MIN;
    if(t==0){
        ans=max(func(idx-1,1),func(idx-1,2));
    }
    else if(t==1){
        ans=max(func(idx-1,0),func(idx-1,2));
    }
    else{
        ans=max(func(idx-1,0),func(idx-1,1));
    }
    ans+=a[idx][t];
    dp[idx][t]=ans;
    }
    return dp[idx][t];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    for(ll i=0;i<n;++i){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        dp[i][0]=dp[i][1]=dp[i][2]=-1;
    }

    ll ans=max(func(n-1,0),max(func(n-1,1),func(n-1,2)));
    cout<<ans<<endl;

    return (0);
}


Measured memory_bytes: 9600
#include<iostream>
#include<cstring>
#include<ctime>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<map>
using namespace std;
#define MAXN 100010
#define MAXM 1010
#define eps 1e-8
#define ll long long
#define MOD 1000000007
#define INF 1000000000
int n;
int A,B;
int a[MAXN];
bool OK(int x){
	int i;
	ll re=0;
	int hh=A-B;
	for(i=1;i<=n;i++){
		ll t=a[i]-(ll)x*B;
		if(t>0){
			re+=(t+hh-1)/hh;
		}
	}
	if(re<=x){
		return 1;
	}
	return 0;
}
int main(){
	int i,x;
	scanf("%d%d%d",&n,&A,&B);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int l=0,r=1000000000;
	int ans;
	while(l<=r){
		int mid=l+r>>1;
		if(OK(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	
	printf("%d\n",ans);
	return 0;
}

/*

*/


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////


int main(){

	double R;
	cin >> R;

	cout << fixed << setprecision(10);

	double ans = R * 2.0*acos(-1);

	cout << ans;


	system("PAUSE");
}


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

using namespace std;

int MurbleCount(string ss);

int main(void){
  string ss;
  cin >> ss;
  cout << MurbleCount(ss);
  return 0;
}

int MurbleCount(string ss){
  int counter = 0;
  for(int i = 0; i < 3; i++){
    if(ss[i] == '1'){
      counter++;
    }
  }
  return counter;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>	
#include <cmath>
#include <string>
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define Cout(s) cout<<s<<endl
using namespace std;
typedef long long ll;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

ll a = 1, b = 0, c, d, n, k = 0, ans = 0;
string s, t;

int main()
{
	int a, b, n; cin >> n >> a >> b;
	cin >> s;
	int x = 0, B = 0;
	rep(i, n) {
		if (s[i] == 'a' && x < a + b) { cout << "Yes" << endl; x++; }
		else if (s[i] == 'b' && x < a + b && B < b) { cout << "Yes" << endl; x++; B++; }
		else cout << "No" << endl;
	}

	return 0;
}


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

int n,k=0,cnt=0,u,v,maxv=0,pos;
int head[100005],de[100005];

map<pair<int,int>,int> m;

struct node
{
	int u,v;
}a[200005];

struct edge
{
	int next;
	int to;
	int color;
}e[200005];

inline void add_edge(int u,int v)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline void dfs(int now,int fath,int last)
{
	int num=0;
	for (int i=head[now];i;i=e[i].next)
	{
		if (e[i].to!=fath)
		{
			num++;
			while (num==last)  num++;
			e[i].color=num;
			m[make_pair(now,e[i].to)]=e[i].color;
			dfs(e[i].to,now,num);
		}
	}
}

signed main()
{
	cin>>n;
	for (int i=1;i<n;i++)
	{
		cin>>u>>v;
		a[i].u=u,a[i].v=v;
		add_edge(u,v);
		add_edge(v,u);
		de[u]++,de[v]++;
	}
	for (int i=1;i<=n;i++)
	{
		if (de[i]>maxv)  maxv=de[i],pos=i;
	}
	for (int i=head[pos];i;i=e[i].next)  e[i].color=++k,m[make_pair(pos,e[i].to)]=e[i].color;
	for (int i=head[pos];i;i=e[i].next)  dfs(e[i].to,pos,e[i].color);
	
	cout<<k<<endl;
	for (int i=1;i<n;i++)
	{
		if (m[make_pair(a[i].u,a[i].v)]==0)  cout<<m[make_pair(a[i].v,a[i].u)]<<endl;
		else cout<<m[make_pair(a[i].u,a[i].v)]<<endl;
	}
	return 0;
}

Measured memory_bytes: 18036
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL

ll ncr(ll n, ll r){
  if(n < r) return 0;
  if(r > n-r) r = n-r;

  ll a = 1, b = 1;
  for(int i = 0; i < r; i++){
    a *= (n - i);
  }
  for(int i = 0; i < r; i++){
    b *= (i + 1);
  }
  return a/b;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;
  vll a(n);
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  sort(ALL(a));

  ll aa = a.at(n-1);
  auto ite = lower_bound(ALL(a), aa/2);
  ll bb = *ite;
  if(ite != a.begin()){
    auto ite2 = ite - 1;
    if(aa - *ite <= *ite2) bb = *ite2;
  }
  cout << aa << ' ' << bb << endl;
}

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


int main() {
int n;
cin>>n;
vector<vector<int>> a(n, vector<int>(2));
for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
sort(a.begin(),a.end());
int t=a[n-1][0],s=a[n-1][1];
long ans=0;
cout<<t+s<<endl;
}


Measured memory_bytes: 5760
# coding: utf-8


def main():
    s = str(input())
    t = str(input())

    if len(s) != len(t):
        print('No')
        return

    ds = dict()
    dt = dict()
    for i in range(len(s)):
        if s[i] in ds.keys() and ds[s[i]] != t[i]:
            print('No')
            return
        if t[i] in dt.keys() and dt[t[i]] != s[i]:
            print('No')
            return

        ds[s[i]] = t[i]
        dt[t[i]] = s[i]

    print('Yes')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3632