akhauriyash/Code-Regression huggingface dataset:
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	counter := make(map[int]int, n)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scan(&tmp)
		counter[tmp]++
	}

	var ans int
	for k, v := range counter {
		switch {
		case k > v:
			ans += v
		case k < v:
			ans += v - k
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5760
<?php
list($n, $m) = ints();
$w[] = 0;
$v[] = 0;
for($i = 0; $i < $n; $i++)list($w[], $v[]) = ints();
$mv = array_sum($v)+1;
$dp = array_fill(0,$n+1,array_fill(0, $mv, 10**10));
$dp[0][0] = 0;
for($i = 1; $i <= $n; $i++){
    $vi = $v[$i];
    $wi = $w[$i];
    $dp0 = $dp[$i-1];
    $dp1 = &$dp[$i];
    $dp1 = $dp0;
    for($j = 0; $j < $mv; $j++){
        if($j-$v[$i] >= 0)chmin($dp1[$j], $dp0[$j-$vi] + $wi);
    }
}
$max = 0;
for($j = 0; $j < $mv; $j++){
    if($dp[$n][$j] <= $m){
        chmax($max, $j);
    }
}
echo $max;


function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array:";
            echo implode(" ", $val)."\n";
        }else{
            echo "array:array\n";
            foreach($val as $row){
                echo implode(" ", $row)."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}

Measured memory_bytes: 651768
#include <bits/stdc++.h>
using namespace std;
int n;
int a;
int main(){
	cin>>n;
	int ct;
	for(int i=1;i<=n;i++){
		cin>>a;
		if(a!=i){
			ct++;
		}
	}
	if(ct==0||ct==2){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main () {
  int N,M,X,Y;
  cin >> N >> M >> X >> Y;
  vector<int>xco(N+1);
  vector<int>yco(M+1);
  for (int i; i < N ; i ++) {
    cin >> xco[i];
  }
  for (int j; j < M ; j ++) {
    cin >> yco[j];
  }
  xco[N] = X;
  yco[M] = Y;
  sort(xco.begin(),xco.end());
  sort(yco.begin(),yco.end());
  bool wr = true ;
  if (xco[N] < yco[0]) wr = false;
  if (wr) cout << "War" << endl;
  else cout << "No War" << endl;
}

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

using namespace std;

typedef long long ll;

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

	int N;
	cin >> N;

	vector<ll> A(N);
	rep(i, N) cin >> A[i];

	vector<vector<ll>> dp(N+1, vector<ll>(2, 0));

	dp[0][1] = INT_MIN;
	for(int i = 1; i <= N; i++){
		dp[i][0] = max(dp[i-1][0] + A[i-1], dp[i-1][1] - A[i-1]);
		dp[i][1] = max(dp[i-1][0] - A[i-1], dp[i-1][1] + A[i-1]);
	}

	cout << dp[N][0] << endl;
}


Measured memory_bytes: 6528
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

#UnionFindのクラス,0-indexed
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents = [-1,0,-4,1,1,1]のように、親の添字かマイナス要素数を表す
        self.parents = [-1] * n

    def find(self, x): # find: xの親がすべてrootになる。これにより計算量削減(O(N) for all (not each))
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n,m = map(int,ipt().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        uf.union(a-1,b-1)
    k = uf.roots()
    print(len(k)-1)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 74752
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  const inf = 2e9;
  var n = next();
  var hh = nextm(n,2);
  hh.sort((a,b)=>a[0]+a[1]-b[0]-b[1]);
  var dp = xArray(inf,n+1);
  dp[0] = 0;
  for(var i = 0; i < n; i++){
    var h = hh[i][0], p = hh[i][1];
    for(var j = i+1; j > 0; j--){
      if(dp[j-1] > h)continue;
      if(dp[j-1]+p < dp[j])dp[j] = dp[j-1]+p;
    }
  }
  for(var i = n; i >= 0; i--)if(dp[i] < inf)return i;
}

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

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

  if(N%10 == 3) cout << "bon" << endl;
  else if (N%10 == 0 || N%10 == 1 || N%10 == 6 || N%10 == 8) cout << "pon" << endl;
  else cout << "hon" << endl;

}


Measured memory_bytes: 3632
#include<stdio.h>

int main(){

	int m, f, r, sum;

	while(1){

		scanf("%d %d %d", &m, &f, &r);

		if((m == -1) && (f == -1) && (r == -1)){
			break;
		}

		sum = m + f;

		if((m == -1) || (f == -1)){
			printf("F\n");
		} else if (sum >= 80){
			printf("A\n");
		} else if (sum >= 65){
			printf("B\n");
		} else if ((sum >= 50)  || (r >= 50)){
			printf("C\n");
		} else if (sum >= 30){
			printf("D\n");
		} else {
			printf("F\n");
		}

	}

	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
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; }

bool ifPrime(ll x){
    for(ll i=2; i*i<=x; i++){
        if(x%i==0) return false;
    }
    return true;
}

int main(){
    ll x; cin>>x;
    for(ll i=x; ;i++){
        if(ifPrime(i)){
            cout<<i<<endl;
             return 0;
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define RG register
#define R RG int
#define G if(++ip==ie)fread(ip=buf,1,SZ,stdin)
#define F(S) freopen(S".in","r",stdin);freopen(S".out","w",stdout)
using namespace std;
const int SZ=1<<19,N=1e5+9;
int a[N];
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
    G;while(*ip<'-')G;
    R x=*ip&15;G;
    while(*ip>'-'){x*=10;x+=*ip&15;G;}
    return x;
}
int main(){
	R n=in(),m=(1+n)>>1;RG LL ans=0;
	for(R i=1;i<=n;++i)a[i]=in();
	sort(a+1,a+n+1);
	for(R i=m+1;i<=n;++i)ans+=2*(a[i]-a[i-m]);
	if(n&1)ans+=max(a[m]-a[m-1],a[m+1]-a[m])-a[m+1]+a[m-1];
	else ans-=a[m+1]-a[m];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
  int i1, i2;

  for(i1 = 1;i1 < 10;i1++){
    for(i2 = 1;i2 < 10;i2++){
      
      printf("%dx%d=%d\n", i1, i2, i1*i2);
      
    }
  }
  
  return(0);
}

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

int main(){
	ll N;
	cin >> N;
	if(N%2==1){
		cout << 0 << endl;
		return 0;
	}
	
	//N/2に含まれる素因数5の個数をカウントする。
	ll temp = N/2;
	
	ll ans = 0;
	
	int count = 1;
	
	while(1){
		if(pow(5,count) > temp) break;
		ll val = 1;
		rep(i,count){
			val*=5;
		}
		ans += temp/val;
		count++;
	}
	
	cout << ans << endl;
	
	return 0;
}



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

using namespace std;

double p[10][2];
int n;
int arr[10];

double sq(double x)
{
	return x*x;
}

double dist(int a,int b)
{
	return hypot(p[a][0]-p[b][0],p[a][1]-p[b][1]);
}

int main()
{
	cin >> n;
	for(int i=0;i<n;i++)
		cin >> p[i][0] >> p[i][1];
	double ans=0;
	int co=0;
	iota(arr,arr+n,0);
	do{
		co++;
		for(int i=1;i<n;i++)
			ans+=dist(arr[i],arr[i-1]);
	} while(next_permutation(arr,arr+n));
	ans/=co;
	cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
f = []
for i in range(n):
    f.append(list(int(i) for i in input().split()))

p = []
for i in range(n):
    p.append(list(int(i) for i in input().split()))

res = -10**9
for b in range(1,2**10):
    bit = bin(b)[2:]
    bit = '0'*(10-len(bit))+bit
    tmp = 0
    for i in range(n):
        count = 0
        for j in range(10):
            if int(bit[j])==f[i][j]==1:
                count += 1
        tmp += p[i][count]
    res = max(res,tmp)
print(res)
    

Measured memory_bytes: 3064
program button
    implicit none
    integer :: a=0,b=0,coins=0,i=0
    read(*,*)a,b

    if(a<3 .or. 20<b)then
    else
        do i=1,2
            if(b<a)then
                coins = coins + a
                a = a-1
            else
                coins = coins + b
                b = b-1
            endif
        enddo
    endif
    write(*,*)coins

end program button

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
int main()	{
  int n,m;
  cin>>n>>m;
  vector<int>s(m),c(m);
  rep(i,m) cin>>s[i]>>c[i];
  rep(x,1000){
    int nx=x/10;
    int digit=1;
    vector<int>d(1,x%10);
    while(nx){
      digit++;
      d.push_back(nx%10);
      nx/=10;
    }
    if(n!=digit) continue;
    reverse(all(d));
    bool ex=true;
    rep(j,m){
      if(d[s[j]-1]!=c[j])
        ex=false;
    }
    if(ex==true){
      cout<<x<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int w = sc.nextInt();
            int h = sc.nextInt();
            if (w == 0 && h == 0) break;
            int[][] wall = new int[2 * h - 1][w];//y,z
            for (int i = 0; i < 2 * h - 1; i++) {
                for (int j = 0; j < w - (i + 1) % 2; j++) {
                    wall[i][j] = sc.nextInt();
                }
            }
            System.out.println(solve(w, h, wall));
        }
    }

    private static int solve(int w, int h, int[][] wall) {
        Set<Integer> set = new HashSet<>();
        Deque<int[]> que = new ArrayDeque<>();
        int[] state = {0, 0, 1};//x,y
        que.addFirst(state);
        while (!que.isEmpty()) {
            int[] a = que.removeLast();
            if (a[0] == w - 1 && a[1] == h - 1) return a[2];
            if (0 <= a[0] + 1 && a[0] + 1 <= w - 1) {
                if (wall[2 * a[1]][a[0]] == 0) {
                    int[] b = {a[0] + 1, a[1], a[2] + 1};
                    if (!set.contains(getkey(b))) {
                        que.addFirst(b);
                        set.add(getkey(b));
                    }
                }
            }
            if (0 <= a[0] - 1 && a[0] - 1 <= w - 1) {
                if (wall[2 * a[1]][a[0] - 1] == 0) {
                    int[] b = {a[0] - 1, a[1], a[2] + 1};
                    if (!set.contains(getkey(b))) {
                        que.addFirst(b);
                        set.add(getkey(b));
                    }
                }
            }
            if (0 <= a[1] + 1 && a[1] + 1 <= h - 1) {
                if (wall[2 * a[1] + 1][a[0]] == 0) {
                    int[] b = {a[0], a[1] + 1, a[2] + 1};
                    if (!set.contains(getkey(b))) {
                        que.addFirst(b);
                        set.add(getkey(b));
                    }
                }
            }
            if (0 <= a[1] - 1 && a[1] - 1 <= h - 1) {
                if (wall[2 * a[1] - 1][a[0]] == 0) {
                    int[] b = {a[0], a[1] - 1, a[2] + 1};
                    if (!set.contains(getkey(b))) {
                        que.addFirst(b);
                        set.add(getkey(b));
                    }
                }
            }
        }
        return 0;
    }

    private static int getkey(int[] state) {
        return 100 * state[0] + state[1];
    }
}



Measured memory_bytes: 68080
#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define f0r(a, b) for (long long a = 0; a < (b); ++a)
#define f1r(a, b, c) for (long long a = (b); a < (c); ++a)
#define f0rd(a, b) for (long long a = (b); a >= 0; --a)
#define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define mp make_pair
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < (n); ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = (lb); ele <= (rb); ele++) { if (ele > (lb)) cout << " "; cout << a[ele]; } cout << '\n';}
#define vsz(x) ((long long) x.size())
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
  cin >> p.first;
  return cin >> p.second;
}
 
// mt19937 rng(steady_clock::now().time_since_epoch().count());
mt19937 rng(61378913);
/* usage - just do rng() */
 
void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const lld pi = 3.14159265358979323846;
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;


 
ll n, m, k, q, l, r, x, y, z;
ll a[1000005];
ll b[1000005];
ll c[1000005];
string s, t;
ll ans = 0;



void solve(int tc) {
  ai(a, 5);
  f0r(i, 5) {
    if (a[i] == 0) {
      cout << i + 1 << '\n';
    }
  }
}
 
int main() {
  send help
 
  // usaco("cowland");

  int tc = 1;
  // cin >> tc;
  for (int t = 0; t < tc; t++) solve(t);
} 

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

int main() {
  int s;
  int s1,s2,s3;
  cin >> s;
  if (s%2==0) {
    s3 = 0;
  }
  else{
    s3 = 1;
  }
  if (s>=100){
    s1 = 1;
  }
  else {
    s1 = 0;
  }
  s2 = (s - (s1*100 + s3))/10;
  cout << s1 + s2 + s3 << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PA;
typedef pair<PA,int> PPA;
int main(){
  int h,w;
  char masu[1001][1001];
  int suji[1001][1001]={};
  queue<PPA> que;
  PA p;
  int sum = 0;
  cin >> h >> w;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      cin >> masu[i][j];
      if(masu[i][j] == '.'){
	for(int k=-1;k<=1;k++)
	  for(int l=-1;l<=1;l++){
	    if(k==0 && l==0) continue;
	    int y = i+k;
	    int x = j+l;
	    if(y<0||y>=h||x<0||x>=w||masu[y][x]=='.') continue;
	    suji[y][x]++;
	  }
      }
    }
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      if(suji[i][j] >= masu[i][j]-'0' && masu[i][j]!='.'){
	que.push(PPA(PA(i,j),1));
      }
    }
  queue<PA> queb;
  while(!que.empty()){
    p = que.front().first;
    if(sum != que.front().second){
      while(!queb.empty()){
	masu[queb.front().first][queb.front().second] = '.';
	queb.pop();
      }
      sum++;
    }
    que.pop();
    queb.push(p);
    for(int k=-1;k<=1;k++)
      for(int l=-1;l<=1;l++){
	if(k==0 && l==0) continue;
	int y = p.first+k;
	int x = p.second+l;
	if(y<0||y>=h||x<0||x>=w||masu[y][x]=='.') continue;
	suji[y][x]++;
	if(suji[y][x] == masu[y][x]-'0'){
	  que.push(PPA(PA(y,x),sum+1));
	}
      }
  }
  cout << sum << endl;
  return (0);
}

Measured memory_bytes: 7984
#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() {
    int a;
    string s;
    cin >> a >> s;
    if(a>=3200) cout << s << endl;
    else cout << "red" << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, heapq


def solve(N: int, M: int, A: "List[int]"):
    H = [(-a, a) for a in A]
    heapq.heapify(H)
    for i in range(M):
        mx = heapq.heappop(H)
        mx = mx[1] >> 1
        heapq.heappush(H, (-mx, mx))
    print(sum([e[1] for e in heapq.nlargest(N, H)]))
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 30400
#include<iomanip>
#include <string>
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
#include<math.h>
#include <ctype.h>
#include <algorithm> // sort
#include <map> // pair
using namespace std;
int main() {
 long long int n;
  cin >> n;
  cout << (n-1)*n/2 << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int su[101]={};
	int N,K;
	cin >> N >> K;
	for(int i=1;i<=K;i++){
		int J;
		cin >> J;
		for(int j=0;j<J;j++){
			int tmp;
			cin >> tmp;
			su[tmp]++;
		}
	}
	int sum=0;
	for(int i=1;i<=N;i++){
		if(su[i]==0){
			sum++;
		}
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
const int MOD = 1000000007;
string dec(string s){
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == '0'){
            s[i] = '9';
        }else{
            s[i] = s[i] - 1;
            if(i == 0 && s[i] == '0'){
                s = s.substr(1);
            }
            break;
        }
    }
    return s;
}
void add(int& x, int y){
    x = (x + y) % MOD;
}
int solve(string s, string t){
    const int MAX_N = 10010;
    const int MAX_L = 510;

    int n = s.size();
    int m = t.size();
    // printf("s = %s t = %s\n", s.c_str(), t.c_str());
    // printf("n = %d m = %d\n", n, m);

    int next[MAX_L][10] = {};
    for(int i = 0; i <= m; i++){
        for(int c = 0; c < 10; c++){
            string r = t.substr(0, i) + string(1, '0' + c);
            for(int len = r.size(); len >= 0; len--){
                if(r.substr(r.size() - len, len) == t.substr(0, len)){
                    next[i][c] = len;
                    break;
                }
            }
        }
    }

    static int count[MAX_N][MAX_L][2] = {};
    static int match[MAX_N][MAX_L][2] = {};
    memset(count, 0, sizeof(count));
    memset(match, 0, sizeof(match));
    for(int i = 0; i < n; i++){
        for(int c = (i + 1 < n ? 1 : 0); c < 10; c++){
            int nj = next[0][c];
            if(i > 0){
                add(count[i + 1][nj][1], 1);
                if(nj == m){
                    add(match[i + 1][nj][1], 1);
                }
            }else if(c <= s[i] - '0'){
                int low = (c < s[i] - '0');
                add(count[i + 1][nj][low], 1);
                if(nj == m){
                    add(match[i + 1][nj][low], 1);
                }
            }
        }
        for(int j = 0; j <= m; j++){
            for(int lw = 0; lw < 2; lw++){
                for(int c = 0; c <= (lw ? 9 : s[i] - '0'); c++){
                    int nj = next[j][c];
                    int nlw = lw || (c < s[i] - '0');
                    add(count[i + 1][nj][nlw], count[i][j][lw]);
                    add(match[i + 1][nj][nlw], match[i][j][lw]);
                    if(nj == m){
                        add(match[i + 1][nj][nlw], count[i][j][lw]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= m; i++){
        add(ans, match[n][i][0]);
        add(ans, match[n][i][1]);
    }
    // printf("return %d\n", ans);
    return ans;
}
int main(){
    string a, b, c;
    while(cin >> a >> b >> c){
        int x = solve(b, c);
        int y = (a != "0" ? solve(dec(a), c) : 0);
        cout << (x - y + MOD) % MOD << endl;
    }
    return 0;
}

Measured memory_bytes: 81040
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
void Main(){
    int n,m;cin>>n>>m;
    if(n+m<10)cout<<n+m<<endl;
    else cout<<"error"<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 384
fun main(args: Array<String>) {
    var (n, y) = readLine()!!.split(" ").map{it.toInt()}

    for(i in 0..n) {
        for(j in 0..n) {
            if(y - i * 10000 - j * 5000 - (n - i - j) * 1000 == 0 && n - i - j >= 0) {
                println("$i $j ${n-i-j}")
                return
            }
        }
    }
    println("-1 -1 -1")
}

Measured memory_bytes: 36700
// atcoder/diverta2019/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  lli n;
  while (cin >> n) {
    set<lli> v;
    auto fn = [&] (lli x) {
      lli m = (n / x) - 1;
      if (m == 0 || n % m == 0) return 0LL;
      return n / m == n % m ? m : 0;
    };

    lli sum = 0;
    for (lli i = 1; i * i <= n; ++i) {
      if (n % i) continue;
      lli x = i;
      lli y = n / i;
      sum += (x != y ? fn(x) + fn(y) : fn(x));
    }
    cout << sum << endl;

    // lli z = 0;
    // each (m, v) {
    //   cout << m << endl;
    //   assert(n % m == n / m);
    // }

    // cout << z << endl;
    // cout << endl;
    // break;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <algorithm>
#include <ctype.h>
#include <vector>
#include <numeric>
#include <map>
#include <queue>
using namespace std;

#define ll long long int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define ALL(a) (a).begin(), (a).end()
#define sort_v(a) sort(a.begin(), a.end())
#define fi first
#define se second

void print(bool c)
{
    if (c)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

void Print(bool c)
{
    if (c)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

ll gcdll(ll a, ll b)
{
    while (1)
    {
        if (a < b)
            swap(a, b);
        if (b == 0)
            break;
        a %= b;
    }
    return a;
}

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

bool cmp(const pii &a, const pii &b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

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


Measured memory_bytes: 256
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('#')
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '#':
        continue
    if cnt > Counter[y][x]:
        continue
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    Map[y][x] = cnt
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
if Visited[H-1][W-1] == False:
    print('-1')
else:
    print(H*W-Map[H-1][W-1]-black_cnt-1)


Measured memory_bytes: 3444
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using E = System.Linq.Enumerable;
class Program
{
    static char[] abc = "abcdefghijklmnopqrstuvwxyz".ToCharArray();
    static long mod = 1000000007;
    static void Main(string[] args)
    {
        var N = long.Parse(Console.ReadLine());
        var ans = "second";
        for (int i = 0; i < N; i++)
        {
            var inp = long.Parse(Console.ReadLine());
            if(inp%2 == 1)
            {
                ans = "first";
                break;
            }
        }

        Console.WriteLine(ans);
    }



}


Measured memory_bytes: 31804
#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 getchar getchar_unlocked
#define putchar putchar_unlocked
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int getint() {
	char C;
	while (!isdigit(C = getchar()));
	int A = C - '0';
	while (isdigit(C = getchar())) A = A * 10 + C - '0';
	return A;
}

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


	int N;
	N = getint();
	int A[200000];
	rep(i, N) A[i] = getint();

	ll B[200001], C[200001];
	B[0] = 0;
	C[N] = 0;

	vector<int> V;
	ll mae = A[0];
	V.pb(0);
	rep(i, N) {
		ll a = A[i];
		B[i + 1] = B[i];
		if (mae >= a) {
			a *= 4;
			while (mae >= a) {
				V.pb(0);
				a *= 4;
			}
			V[(int)V.size() - 1]++;
		}
		else {
			while (mae < a) {
				int kari = V[(int)V.size() - 1];
				B[i + 1] += kari;
				if (V.size() > 1) {
					V.pop_back();
					V[(int)V.size() - 1] += kari;
				}
				mae *= 4;
			}
			V[(int)V.size() - 1]++;
		}
		mae = A[i];
	}
	V.clear();
	mae = A[N - 1];
	V.pb(0);
	for (int i = N - 1; i >= 0; i--) {
		ll a = A[i];
		C[i] = C[i + 1];
		if (mae >= a) {
			a *= 4;
			while (mae >= a) {
				V.pb(0);
				a *= 4;
			}
			V[(int)V.size() - 1]++;
		}
		else {
			while (mae < a) {
				int kari = V[(int)V.size() - 1];
				C[i] += kari;
				if (V.size() > 1) {
					V.pop_back();
					V[(int)V.size() - 1] += kari;
				}
				mae *= 4;
			}
			V[(int)V.size() - 1]++;
		}
		mae = A[i];
	}

	ll kotae = 1e18;
	rep(i, N + 1) {
		kotae = min(kotae, 2 * B[i] + 2 * C[i] + i);
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 4224
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#include "atcoder/all"
#else
#define NDEBUG
#include <bits/stdc++.h>
#include <atcoder/all>
#endif


using namespace std;
using namespace atcoder;

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

    auto ds = dsu(n);

    for (int i = 0; i < q; ++i) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            ds.merge(u, v);
        }
        if (t == 1) {
            cout << (ds.same(u, v) ? 1 : 0) << "\n";
        }
    }

    return 0;
}


Measured memory_bytes: 3988
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<complex>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  vector<int> a(3);cin>>a[0]>>a[1]>>a[2];
  sort(a.begin(),a.end());
  int ans=0;
  if(a[0]-a[1]==1){
    ans=a[2]-a[1]+2;
  }else if(a[2]==a[1]){
    if((a[2]-a[0])%2){
      ans=(a[2]-a[0])/2+2;
    }else{
      ans=(a[2]-a[0])/2;
    }
  }else{
    ans=(a[2]-a[1])+(a[2]-((a[2]-a[1])+a[0]))/2+2*((a[1]-a[0])%2);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
	ll n,m;
	cin>>n>>m;
	ll a[m],b[m];
	//pair<ll,ll>ab[m];
	int t[200005];
	for(ll i=0;i<200005;i++)t[i]=0;
	for(ll i=0;i<m;i++){
		cin>>a[i]>>b[i];
		//ab[i] = make_pair(a[i],b[i]);
		if(a[i]==1)t[b[i]]=1;
		//cout<<"aaa"<<endl;
	}
	//sort(ab,ab+m);
	for(ll i=0;i<m;i++){
		if(b[i]!=n)continue;
		if(t[a[i]]==1){
			cout<<"POSSIBLE"<<endl;
			return 0;
		}
	}
	cout<<"IMPOSSIBLE"<<endl;
	return 0;

}


Measured memory_bytes: 4096
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<utility>
#include<map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define all(in) in.begin(),in.end()
#define ALL(in,K) in,in+K
#define INF 100000000
#define MOD 100000007
#define SIZE 100005
#define pi 	3.14159265358979323846


int main(){
	ll n;
	cin >> n;
	ll ans1=0,ans2=0;
	REP(i,n){
		string s1,s2;
		cin >> s1 >> s2;
		if(s1==s2){
			ans1++;
			ans2++;
		}else{
			REP(i,max(s1.size(),s2.size())){
				if(s1[i]=='\0'){
					ans2 += 3;
					break;
				}
				if(s2[i]=='\0'){
					ans1 += 3;
					break;
				}
				if(s1[i]>s2[i]){
					ans1 += 3;
					break;
				}
				if(s1[i]<s2[i]){
					ans2 += 3;
					break;
				}
			}
		}
	}
	cout << ans1 << " " << ans2 << endl;
}


Measured memory_bytes: 3128
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define INF         1e9
#define EPS         1e-9
#define REP(i,n)    for(lint i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(lint i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(lint i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(lint i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define R_UP(a,b)   (((a)+(b)-1)/(b))
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP        cout << fixed << setprecision(8)
using namespace std;
using lint = long long;
template<typename T = lint>inline T in() { T x; cin >> x; return x; }
signed main()
{
	int n = in(), k = in();
	cout << (n % k == 0 ? 0 : 1) << endl;
}

Measured memory_bytes: 256
def solve(N, A, B, C):
    A.sort()
    B.sort()
    C.sort()
    def calc(xs, ys, ts):
        rs = [0] * N
        t = 0
        j = N - 1
        for i in range(N - 1, -1, -1):
            x = xs[i]
            while x < ys[j] and j >= 0:
                t += ts[j]
                j -= 1
            rs[i] = t
        return rs
    rs = [1] * N
    rs = calc(B, C, rs)
    rs = calc(A, B, rs)
    return sum(rs)

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
print(solve(N, A, B, C))


Measured memory_bytes: 23372
ary = STDIN.gets.chomp.split('').map(&:to_i)
a1 = "#{ary[0]}+#{ary[1]}+#{ary[2]}+#{ary[3]}"
a2 = "#{ary[0]}+#{ary[1]}+#{ary[2]}-#{ary[3]}"
a3 = "#{ary[0]}+#{ary[1]}-#{ary[2]}+#{ary[3]}"
a4 = "#{ary[0]}-#{ary[1]}+#{ary[2]}+#{ary[3]}"
a5 = "#{ary[0]}-#{ary[1]}-#{ary[2]}+#{ary[3]}"
a6 = "#{ary[0]}-#{ary[1]}+#{ary[2]}-#{ary[3]}"
a7 = "#{ary[0]}+#{ary[1]}-#{ary[2]}-#{ary[3]}"
a8 = "#{ary[0]}-#{ary[1]}-#{ary[2]}-#{ary[3]}"

ret = ""
[a1,a2,a3,a4,a5,a6,a7,a8].each do |item|
  if eval(item) == 7
    ret = item
    break
  end
end

STDOUT.puts "#{ret}=7"

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
long long n, arr[55];

int main(){
	IOS
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	sort(arr, arr+n);
	long double ans=(double) (arr[0]+arr[1])/2.0;
	for(int i=2;i<n;i++){
		ans=(double) (ans+arr[i])/2.0;
	}
	cout << setprecision(9) << fixed;
	cout << ans << '\n';
}


Measured memory_bytes: 3776
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
#define MAX_N (105)
typedef pair<int, int> P;

int n;
vector<int> G[MAX_N];
int dist[MAX_N];
int main()
{
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
	int u, k;
	scanf("%d %d", &u, &k);
	u--;

	for ( int j = 0; j < k; j++ ) {
	    int v;
	    scanf("%d", &v);
	    v--;
	    G[u].push_back( v );
	}
    }

    for ( int i = 0; i < n; i++ ) dist[i] = -1;
    dist[0] = 0;

    queue<int> Q;
    Q.push( 0 );

    while ( !Q.empty() ) {
	int cur = Q.front();
	Q.pop();
	for ( int i = 0; i < G[cur].size(); i++ ) {
	    int next = G[cur][i];
	    if ( dist[next] == -1 ) {
		dist[next] = dist[cur] + 1;
		Q.push( next );
	    }
	}
    }

    for ( int i = 0; i < n; i++ ) {
	printf("%d %d\n", i+1, dist[i]);
    }

    return 0;
}

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

int  main(void)
{
        int i,num,count = 0;
        string A = "A", Un = "Un";
        string input;

        cin >> num;
        for(i = 0; i < num; i++){
                cin >> input;
                if(input == A){ 
                        count += 1;
                }else{
                        count -= 1;
                }   

                if(count < 0){ 
                        cout << "NO" << endl;
                        return 0;
                }   
        }   

        if(count == 0){ 
                cout << "YES" << endl;
        }else{
                cout << "NO" << endl;
        }   
        return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll calc(ll x, ll y){ return 2 * x * y + x + y; }
int main(){
    int n;
    cin >> n;
    int ans = n;
    for(int i = 0; i < n; i++){
        int k;
        cin >> k;
        bool ok = false;
        for(int x = 1; calc(x, x) <= k; x++){
            if(k % (2 * x + 1) == x) ok = true;
        }
        if(ok) ans--;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1160
#include<set>
#include<iostream>
#include<cmath>

using namespace std;

long long f(long long n){
    if(n<2)return 0;
    if(n==2)return 1;
    if(!(n&1))return 0;
    int k = sqrt(n);
    for(int i=3;i<=k;i+=2){
        if(n%i==0)return 0;
    }
    return 1;
}
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    long long a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(f(a[i])==1)cnt++;
    }

    cout << cnt <<endl;
    return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto &x: a){
		cin >> x;
	}
	vector<int> active;
	for(int i = 0; i < n; i ++){
		auto p = upper_bound(active.begin(), active.end(), a[i], greater<int>());
		if(p == active.end()){
			active.push_back(a[i]);
		}
		else{
			*p = a[i];
		}
	}
	cout << active.size();
	return 0;
}

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    ans=0
    for i in range(1,N):
        j=N-i
        if i!=j:
            ans+=1
    print(ans//2)
        
        

main()


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


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



Measured memory_bytes: 256
N,M=[int(x) for x in str(input()).split()]
count=0
ans=[]
for i in range(1,int(M**0.5+2)):
  #print(i)
  if M%i==0 and i>=N:
    count=1
    ans.append(M//i)
    break

for i in range(1,int(M**0.5+2)):
  #print(i)
  if M%i==0 and M//i>=N:
    ans.append(i)
print(max(ans))




Measured memory_bytes: 38896
#include <bits/stdc++.h>
 
using namespace std;
 
#define cel(n, k) ((n-1)/k+1)
#define sets(a) memset(a, -1, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
 
 
#define fr(i, n) for(int i=0; i<n;i++)
#define fr1(i, n) for(int i=1; i<=n;i++) 
 
#define readf(f) freopen(f, "r", stdin)
#define writef(f) freopen(f, "w", stdout)
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define nl "\n"
 
void file(){
	readf("in.txt");
    writef("out.txt");
}
 
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
 
typedef long long ll;
typedef pair<int,int> pii;

const int mx = 3e3+5;

int L[mx][mx];
char s[mx], t[mx];


int main()
{
	//file();
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin>>s>>t;

	int sl = strlen(s), tl = strlen(t);

	

	for(int i = 0; i <= sl; i++)
		L[i][0] = 0;
	for(int i = 0; i <= tl; i++)
		L[0][i] = 0;

	for(int i = 1; i <= sl; i++){

		for(int j = 1; j <= tl; j++){
			if(s[i-1] == t[j-1])
				L[i][j] = 1 + L[i-1][j-1];
			else
				L[i][j] = max(L[i-1][j], L[i][j-1]);
		}
	}

	
 	int index = L[sl][tl];

 	char lcs[index+1];

 	lcs[index] = '\0';

 	int i = sl, j = tl;

 	while(i > 0 && j > 0){

 		if(s[i-1] == t[j-1]){
 			lcs[--index] = s[i-1];

 			i--;j--; 
 		}

 		else if(L[i-1][j] > L[i][j-1])
 			i--;
 		else
 			j--;
 	}

 	cout<<lcs;


    return 0;
 
}

Measured memory_bytes: 35456
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int i;
		int[] h = new int[n];
		for(i = 0; i < n; i++) {
			h[i] = scan.nextInt();
		}
		int sum = 0;
		int max = Integer.MIN_VALUE;
		for(i = 0; i < n - 1; i++) {
			if(h[i] >= h[i + 1]) {
				sum++;
			}else {
				if(sum > max) {
					max = sum;
				}
				sum = 0;
			}
		}
		if(sum > max)
			max = sum;
		System.out.println(max);
	}
}

Measured memory_bytes: 50208
n,t=map(int,input().split())
org_l=list(map(int,input().split()))
subl=org_l[1:]
l=[y-x for x,y in zip(org_l,subl)]
ans=0
for i in l:
    if i <t:
        ans+=i
    else:
        ans+=t
print(ans+t)


Measured memory_bytes: 26832
#pragma comment(linker, "/STACK:10240000")
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 60;

int xx[] = {0, 0, 1, -1, 1, -1, 1, -1}, yy[] = {1, -1, 0, 0, 1, -1, -1, 1};

char str[MAXN];
int w[MAXN][MAXN], ans[MAXN][MAXN];

int main ()
{
    int n, m;
    scanf ("%d%d", &n, &m);
    memset (w, 0, sizeof (w));
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%s", &str);
        for (int j = 1; j <= m; j ++)
        {
            if (str[j - 1] == '#')
            {
                w[i][j] = 1;
            }
        }
    }
    memset (ans, -1, sizeof (ans));
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (!w[i][j])
            {
                int tmp = 0;
                for (int t = 0; t < 8; t ++)
                {
                    int x = i + xx[t], y = j + yy[t];
                    if ((x > 0) && (x <= n) && (y > 0) && (y <= m) && (w[x][y]))
                    {
                        tmp ++;
                    }
                }
                ans[i][j] = tmp;
            }
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (ans[i][j] == -1)
            {
                printf ("#");
            }
            else
            {
                printf ("%d", ans[i][j]);
            }
        }
        printf ("\n");
    }
    return 0;
}


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair


typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { -1,  0, 1, 0,  1, -1,  1, -1};
static const int dy[8] = {0,  1, 0,  -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;

const int maxn = 1e5 + 5;

LL sum[maxn];
map<LL,int> mp;

LL N,X,M;




int main()
{
    cin >> N >> X >> M;
    sum[0] = 0;

    LL ans = -1;

    _rep(i,1,N){
        sum[i] = X + sum[i-1];
        if( mp.count(X) && N > 1e5){
            int loop = i - mp[X];
            ans = 0;
            LL sumone = sum[i] - sum[mp[X]];

            ans += sum[mp[X]-1];

            LL nn = N - (mp[X]-1);

            ans += (nn/loop)*sumone;
            ans += sum[mp[X] + (nn%loop) -1] - sum[mp[X] -1];

            break;
        }else{
            mp[X] = i;
        }

        X = (X * X)%M;

    }

    if(ans == -1){
        ans = sum[N];
    }

    cout << ans << endl;

    return 0;
}


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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii; typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <class F,class ...S> void dbg(const F& f, const S&...s){cerr <<f <<": "; dbg(s...);}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int s;
	cin >>s;
	VL dp(s+10);
	dp[0] = 1;
	rep(i, s+1) rep2(j, i+3, s+1){
			dp[j] = (dp[j] + dp[i])%MD;
	}
	
	cout<< dp[s] <<"\n";
	return 0;
}



Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll INF = 1e14;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;

signed main() {
    int N;
    cin >> N;
    vector<ll> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    int ret = 0;
    for(int i = 0;i < N - 1;i++) {
        if(vec.at(i) < vec.at(i + 1)) {
            ret++;
        }
    }
    cout << ret << endl;
}


Measured memory_bytes: 3620
N, M, Q = [int(str) for str in input().strip().split()]
LR = [[int(str) for str in input().strip().split()] for _ in range(M)]
pq = [[int(str) for str in input().strip().split()] for _ in range(Q)]

LRmap = [[0] * N for _ in range(N)]
for l, r in LR:
    LRmap[l - 1][r - 1] += 1

sums = [[0] * (N + 1) for _ in range(N + 1)]
sums[0][0] = 0
for l in range(1, N + 1):
    for r in range(1, N + 1):
        sums[l][r] = sums[l - 1][r] + sums[l][r - 1] - sums[l - 1][r - 1] + LRmap[l - 1][r - 1]

for p, q in pq:
    print(sums[q][q] - sums[p - 1][q] - sums[q][p - 1] + sums[p - 1][p - 1])

Measured memory_bytes: 60396
#include<stdio.h>

int main()
{
	char input[102],output[299];
	int i,j,k,num,ch;
	
	while(fgets(input,102,stdin)!=NULL)
	{
		j=0;
		for(i=0;input[i]!='\n';i++)
		{
			if(input[i]=='@')
			{
				num=(input[++i]-'0');
				ch=input[++i];
				for(k=j;k<num+j;k++)
				{
					output[k]=ch;
				}
				j=k-1;
			}
			else
			{
				output[j]=input[i];
			}
			j++;
		}
		output[j]='\0';
		puts(output);
	}
	return 0;
}

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

typedef long long int ll;


int main()
{

    int n;
    cin>>n;
    long long int m;
    ll a[n];

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



    cout<< s;
}


Measured memory_bytes: 256
s = input()
t = 'AKIHABARA'
a = 0
b = 0
while b < len(t):
    if a < len(s) and b < len(t) and s[a] == t[b]:
        a += 1
        b += 1
        continue
    if b < len(t) and t[b] == 'A':
        b += 1
        continue
    print('NO')
    exit()
print('YES' if a == len(s) else 'NO')


Measured memory_bytes: 3060