akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<queue>
#include<set>

using namespace std;
using ll=long long;
using vll=vector<ll>;
using vvll=vector<vll>;
using pill=pair<int,ll>;
using vpill=vector<pill>;
using vvpill=vector<vpill>;

const long long inf=1000000000*300LL;


struct qm_t
{
	int p;
	ll d;
	bool operator<(const qm_t&rhs) const
	{
		return d>rhs.d;
	}
};


class q_t
{
	priority_queue<qm_t> q;
public:
	void push(int p, ll d)
	{
		q.push((qm_t){p, d});
	}
	bool pop(int&p, ll&d)
	{
		if(q.empty()) return false;
		p=q.top().p;
		d=q.top().d;
		q.pop();
		return true;
	}
};


bool min_u(ll&m, ll v)
{
	if(m>v)
	{
		m=v;
		return true;
	}
	return false;
}


ll calc(vvpill&w, int s, int e)
{
	int n=w.size();
	vll dp(n, inf);
	int p=s;
	ll d=0;
	q_t q;

	dp[p]=d;
	q.push(p, d);
	while(q.pop(p, d))
	{
		if(p==e) return d;
		if(dp[p]<d) continue;

		for(auto&we:w[p])
		{
			int i=we.first;
			ll ad=we.second;
			if(min_u(dp[i], dp[p]+ad))
			{
				q.push(i, dp[i]);
			}
		}
	}
/*
	printf("s=%d e=%d d=%lld : ", s, e, d);
	for(auto dpe:dp) printf("%lld ", dpe); printf("\n");
*/
	return inf;
}


struct x_t
{
	int s, e;
	ll d;
	bool operator<(const x_t&rhs) const
	{
		if(d!=rhs.d) return d<rhs.d;
		if(s!=rhs.s) return s>rhs.s;
		return e>rhs.e;
	}
};


ll solve(vvll&a)
{
	int n=a.size();
	ll ret=0;
	set<x_t> s;
	vector<vector<pair<int,ll>>> w(n);

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			s.insert((x_t){i, j, a[i][j]});
		}
	}
	for(auto it=s.begin();it!=s.end();++it)
	{
		ll d=it->d;
		int i=it->s;
		int j=it->e;
		ll d2=calc(w, i, j);
		if(d2<d)
		{
			return -1;
		}
		if(d2>d)
		{
			w[i].push_back(make_pair(j, d));
			w[j].push_back(make_pair(i, d));
			ret+=d;
		}
	}
	return ret;
}


int main(void)
{
	int n;

	while(scanf("%d", &n)==1)
	{
		vvll a(n);

		for(int i=0;i<n;i++)
		{
			a[i].resize(n);
			for(int j=0;j<n;j++)
			{
				scanf("%lld", &a[i][j]);
			}
		}
		printf("%lld\n", solve(a));
/*
for(auto ae:a)
{
	for(auto aee:ae) printf("%lld ", aee);
	printf("\n");
}
*/
	}

	return 0;
}


Measured memory_bytes: 3840
//#define NDEBUG
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

struct rep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr rep(const usize f, const usize l) noexcept
      : f(std::min(f, l)), l(l) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
struct revrep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr revrep(const usize f, const usize l) noexcept
      : f(l - 1), l(std::min(f, l) - 1) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) noexcept {
  return a < b ? b - a : a - b;
}
template <class T> void chmin(T &a, const T &b) noexcept {
  if (b < a)
    a = b;
}
template <class T> void chmax(T &a, const T &b) noexcept {
  if (a < b)
    a = b;
}
template <class F> class rec_lambda {
  F f;

public:
  rec_lambda(F &&f) : f(std::move(f)) {}
  template <class... Args> auto operator()(Args &&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template <class F> auto make_rec(F &&f) { return rec_lambda<F>(std::move(f)); }
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}
constexpr char eoln = '\n';
template <class T> T ceildiv(const T &l, const T &r) {
  return l / r + (l % r != 0 ? 1 : 0);
}

} // namespace n91

namespace n91 {

void main_() {
  /*
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //*/
  const i64 a = scan<i64>();
  const i64 v = scan<i64>();
  const i64 b = scan<i64>();
  const i64 w = scan<i64>();
  const i64 t = scan<i64>();
  bool f = true;
  if (w >= v) {
    f = false;
  } else if ((v - w) * t >= difference(a, b)) {
    f = true;
  } else {
    f = false;
  }
  std::cout << (f ? "YES" : "NO") << eoln;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <map>
#include <set>
#include <queue>
using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

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

    printf("%f\n", double(L*L*L)/27);

    return 0;
}



Measured memory_bytes: 256
import sys
import numpy as np
from itertools import permutations
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = int(1e+9 + 7)


class Comb(object):
    def __init__(self, n, MOD=1e9+7):
        self.n = n
        self.MOD = MOD

        fac = [0] * self.n
        finv = [0] * self.n
        inv = [0] * self.n

        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1

        for i in range(2, n):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[(MOD % i)] * (MOD // i) % MOD
            finv[i] = finv[i-1] * inv[i] % MOD
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calv(self, k):
        if self.n < k:
            return 0

        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.MOD) % self.MOD


N, *X = map(int, read().split())
X = np.array(X)
X_diff = np.diff(X)

comb = Comb(N+5, MOD)

acc = 0
ans = 0
for i in range(1, N):
    acc += comb.fac[N-1] * comb.inv[i]
    acc %= MOD

    ans += acc * (X_diff[i-1])
    ans %= MOD


print(ans % MOD)


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

int main()
{
    string S, T;
    cin >> S >> T;
    int ans = 0;
    rep(i, 3) if (S[i] == T[i]) ans++;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())

exp_list = [0]*1010

def prime_factorize(N): 
    exponent = 0
    while N%2 == 0:
        exponent+=1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i != 0: continue
        exponent = 0
        while N%i == 0:
            exponent+=1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    for p,e in factorization:
        exp_list[p] += e

for i in range(2,n+1):
    prime_factorize(i)
#print(exp_list)

MOD = 10**9+7
ans = 1
for i in exp_list:
    ans *= i+1
    ans %= MOD
print(ans)
    








Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 自分の得意な言語で
		// Let's チャレンジ！！

		Scanner sc = new Scanner(System.in);

		int h = sc.nextInt();
		int n = sc.nextInt();

		String re = "No";
		int k = 0;
		for (int i = 0; i < n; i++) {
			k = k + sc.nextInt();
		}
		if (k >= h) {
			re = "Yes";
		}

		System.out.println(re);

	}

}

Measured memory_bytes: 48540
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
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;
}

int main(){
  cout << fixed << setprecision(15);
  double ans = 0;
  
  int n; cin >> n;
  vector<pair<int, int>> cities(n);
  rep(i, n){
    int x, y; cin >> x >> y;
    cities[i] = mp(x, y);
  }

  rep(i, n){
    rep(j, n){
      if (i == j) continue;
      double x = sqrt(pow(cities[i].first - cities[j].first, 2.0) + pow(cities[i].second - cities[j].second, 2.0));
      ans += x;
    }
  }
  ans /= n;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,cnt=0; cin>>n;
    rep(i,n){
        int a; cin>>a;
        if(a%2) cnt++;
    }
    cout<<(cnt%2==0 ? "YES" : "NO")<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n;  scanf("%d", &n);
  int a[100003];
  for(int i=1; i<=n; i++)  scanf("%d", a+i);

  int count = n;
  int now = 1;
  while(count--){
    now = a[now];
    if(now == 2){
      printf("%d\n", n-count);
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}
    


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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
string s;
int d,dp[10005][101][2];
int sol(int pos,int sum,int f){
    if(pos==sz(s)) return sum==0;
    int &ans=dp[pos][sum][f];
    if(ans!=-1) return ans;
    ans=0;
    rep(i,0,10){
        if(f){
            ans=(ans+sol(pos+1,(sum+i)%d,f))%hell;
        }
        else{
            if(i<s[pos]-'0'){
                ans=(ans+sol(pos+1,(sum+i)%d,1))%hell;   
            }
            else if(i==s[pos]-'0'){
                ans=(ans+sol(pos+1,(sum+i)%d,0))%hell;
            }
            else break;
        }
    }
    return ans;
}
void solve(){
    cin>>s>>d;
    memset(dp,-1,sizeof dp);
    cout<<(sol(0,0,0)-1+hell)%hell<<endl; 
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define ABS(x, y) ((x) > (y) ? ((x) - (y)) : ((y) - (x)))

#define MOD(x, y) ((x) % (y))
#define DIVCEIL(x, y) (((x) + ((y) - 1)) / (y))
#define DIVFLOOR(x, y) (((x) + ((y) / 2)) / (y))
#define DIVROUND(x, y) ((x) - MOD(x, y) >= MOD(x, y) ? DIVCEIL(x, y) : DIVFLOOR(x, y))

constexpr int C = 5;

int main() {
  long N; cin >> N;
  long capa{N};
  for (int i{}; i < C; ++i) {
    long temp; cin >> temp;
    capa = min(capa, temp);
  }

  cout << DIVCEIL(N, capa) + 4 << endl;
}


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

int main() {

	int a, b;
	scanf("%d %d", &a, &b);
	char s[a + b + 1];
	scanf("%s", s);
	int cnt = 0;
	for(int i = 0; i < a; i++) {
		if('0' <= s[i] && s[i] <= '9') {
			cnt++;
		}
	}
	if(s[a] == '-') {
		cnt++;
	} 
	for(int i = a + 1; i < a + b + 1; i++) {
		if('0' <= s[i] && s[i] <= '9') {
			cnt++;
		}
	}
	if(cnt == a + b + 1) {
		printf("%s\n", "Yes");
	}else {
		printf("%s\n", "No");
	}
}

Measured memory_bytes: 256
#include<stdlib.h>
#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;

struct good{
	int value;
	int weight;
	good(int _value,int _weight){
		value = _value;
		weight = _weight;
	}
};

vector<good> goods;

int main(){
	int N,W;
	int value,weight;
	vector<vector<int> > TT; 
	cin >> N >> W;
	for(int i = 0;i < N;i++){
		cin >> value >> weight;
		goods.push_back(good(value,weight));
	}
	vector<int>T;
	for(int i = 0;i <= W;i++){
		if(i >= goods[0].weight)T.push_back(goods[0].value);
		else T.push_back(0);
	}
//	for(int s = 0;s <= W;s++)cout << T[s] << " ";
//	cout << endl;
	TT.push_back(T);
	T.clear();
	for(int j = 1;j < N;j++){
		for(int i = 0;i <= W;i++){
			if(goods[j].weight > i){
				T.push_back(TT[j - 1][i]);
				continue;
			}
			int temp = TT[j - 1][i - goods[j].weight] + goods[j].value;
			if(TT[j - 1][i] > temp){
				T.push_back(TT[j - 1][i]);
			}else{
				T.push_back(temp);
			}
		}
//		for(int s = 0;s <= W;s++)cout << T[s] << " ";
//		cout << endl;
		TT.push_back(T);
		T.clear();
	}
	cout << TT[N - 1][W] << endl;
}


Measured memory_bytes: 7880
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int R = sc.nextInt();
        int G = sc.nextInt();
        int B = sc.nextInt();
        int K = sc.nextInt();
        int count = 0;
        while (G <= R) {
            G *= 2;
            count++;
        }
        while (B <= G) {
            B *= 2;
            count++;
        }
        System.out.println(K < count ? "No" : "Yes");
    }
}

Measured memory_bytes: 35636
S = input()
counter = 0
max_ = 0
for s in S:
  if s == "A" or s == "G" or s == "C" or s == "T":
    counter += 1
  else:
    if max_ < counter:
      max_ = counter
    counter = 0
if max_ < counter:
  max_ = counter
print(max_)

Measured memory_bytes: 3060
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
visited=[[-1]*w for _ in range(h)]
queue=deque()
for i in range(h):
  for j in range(w):
    if a[i][j]=='#':
      visited[i][j]=0
      queue.append([i,j])
while queue:
  y,x=queue.popleft()
  for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
    n_y,n_x=y+j,x+k
    if 0<=n_y<h and 0<=n_x<w and a[n_y][n_x]=='.' and visited[n_y][n_x]<0:
      visited[n_y][n_x]=visited[y][x]+1
      queue.append([n_y,n_x])
ans=0
for l in visited:
  ans=max([ans]+l)
print(ans)

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

const int INF = 1e9+7 ;
int di[4] = { 1 , -1 , 0 , 0   } ;
int dj[4] = { 0 , 0  , 1 , -1  } ;

int main(){
    int H , W ;
    cin >> H >> W ;
    vector<string> S(H) ;
    rep(i,H) cin >> S.at(i) ;
    int count = 0 ;
    rep(i,H){
        rep(j,W) if(S[i][j] == '#' )count++ ;
    }
    vector<vector<int>> dist(H,vector<int>(W,INF)) ;
    queue<P> Q ;
    auto update = [&] (int i , int j ,int x ){
        if(dist[i][j] != INF ) return ;
        dist[i][j] = x ;
        Q.push(P(i,j)) ;
    };
    update(0,0,0) ;
    while(!Q.empty()){
        int i = Q.front().first ;int j = Q.front().second ;
        Q.pop() ;
        rep(dir,4){
            int new_i = i + di[dir] ;int new_j = j + dj[dir] ;
            if(new_i < 0 || new_i >= H || new_j < 0 || new_j >= W  ) continue ;
            if(S[new_i][new_j] == '#' ) continue ;
            update(new_i,new_j,dist[i][j] + 1 ) ;
        }
    }
    if(dist[H-1][W-1] == INF ){
        cout << -1 << endl;
        return 0 ;
    }
    cout << H * W  - dist[H-1][W-1] - count - 1 << endl;
}

Measured memory_bytes: 764
// be name khoda
#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define int long long
#define mpr make_pair 
typedef long long ll;
#pragma GCC optimize("Ofast")

const int maxn = 1e6+10;
const int mod = 998244353;
const int inf = 1e18+10;

int n, k;
int a[maxn], ps[maxn], sf[maxn];

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n >> k;
    int sm = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>> a[i];
        ps[i] = ps[i-1] + max(a[i],0ll);
        if(i < k) sm += a[i];
    }
    for(int i = n; i >= 1; i--) sf[i] = sf[i+1] + max(a[i],0ll);

    ll ans = 0;
    for(int i = k; i <= n; i++)
    {
        sm -= a[i-k]; sm += a[i];
        ans = max(ans, ps[i-k] + sf[i+1] + max(sm,0ll));
    }
    cout<< ans;
}




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

using namespace std;

int main(void){
  int n,l,pos,cnt,ret;
  string str;
  while(cin >> n && n){
    pos=0;
    cnt=0;
    ret=0;

    cin >> l;
    cin >> str;
    while(pos < l-2){
      if(str[pos] == 'O'){
	pos++;
      }else{
	if(str[pos+1] == 'O' && str[pos+2] == 'I'){
	  pos += 2;
	  cnt++;
	}else{
	  if(cnt > 0){
	    if(cnt >= n){
	      ret += cnt-n+1;
	    }
	  }
	  cnt = 0;
	  pos++;
	}
      }
    }
    if(cnt > 0){
      if(cnt >= n){
	ret += cnt-n+1;
      }
    }
    cout << ret << endl;
  }
}

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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
using lint=long long;

template<class T>
class Fenwick_tree_dual{
	vector<T> a;
public:
	Fenwick_tree_dual(int n):a(n){}
	void add(int l,int r,T val){
		if(l==0){
			for(r--;r>=0;r=(r&(r+1))-1) a[r]+=val;
			return;
		}
		add(0,r,val);
		add(0,l,-val);
	}
	T sum(int i){
		T res{};
		for(;i<a.size();i|=i+1) res+=a[i];
		return res;
	}
};

int main(){
	int n,m; scanf("%d%d",&n,&m);
	vector<int> a(n);
	rep(i,n) scanf("%d",&a[i]), a[i]--;

	Fenwick_tree_dual<lint> F1(m),F2(m);
	rep(i,n-1){
		int l=a[i],r=a[i+1];
		if(a[i]<a[i+1]){
			if(a[i]+2<=a[i+1]){
				F1.add(a[i]+2,a[i+1]+1,1);
				if(a[i+1]<m-1) F1.add(a[i+1]+1,a[i+1]+2,-(a[i+1]-a[i]-1));
			}
		}
		else{
			if(a[i]+2<=m){
				F1.add(a[i]+2,m,1);
			}
			if(a[i+1]>=0){
				if(a[i]<m-1){
					F1.add(0,a[i+1]+1,1);
					F1.add(a[i+1]+1,a[i+1]+2,-(a[i+1]+1));
					F2.add(0,a[i+1]+1,m-a[i]-2);
				}
				else{
					F1.add(1,a[i+1]+1,1);
					F1.add(a[i+1]+1,a[i+1]+2,-a[i+1]);
				}
			}
		}
	}
	rep(i,m-1) F1.add(i+1,i+2,F1.sum(i));

	lint mx=0;
	rep(i,m) mx=max(mx,F1.sum(i)+F2.sum(i));

	lint ans=-mx;
	rep(i,n-1) ans+=(a[i+1]-a[i]+m)%m;
	cout<<ans<<endl;

	return 0;
}


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

vector<int> adj[100001];
int dp[100004];

int solve(int n)
{

	if (dp[n] != -1)
		return dp[n];

	bool isChild = 0;
	int bestChild = 0;

	for (int i = 0; i < adj[n].size(); i++)
	{
		isChild = 1;
		int child = adj[n][i];

		bestChild =  max(bestChild, 1 + solve(child));
	}
	if (!isChild)
		return 0;
	else
		return dp[n] = bestChild;
}


int main()
{
	int n, m;

	cin >> n >> m;

	memset(dp, -1, sizeof(dp));

	while (m--)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = max(ans, solve(i));
	cout << ans ;
}

Measured memory_bytes: 11488
#include<bits/stdc++.h>
#define ll          long long
#define dl          double
#define pb          push_back
#define mp          make_pair
#define pll         pair<long long,long long>
#define vll          vector<long long>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (long long)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
	int n;cin>>n;
	priority_queue<dl, vector<dl>, greater<dl> > q;
	for(int i=0;i<n;i++){
		dl x;cin>>x;
		q.push(x);
	}	
	while(q.size()>1){
		dl x=q.top();
		q.pop();
		dl y=q.top();
		q.pop();
		q.push((x+y)/2.0);
	}
	cout<<setprecision(10);
	cout<<q.top()<<endl;
}

Measured memory_bytes: 256
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define ALL(n) begin(n),end(n)
#define IN(a, x, b) (a<=x && x<b)
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
template<class T> inline T CHMAX(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T & a, const T b) { return a = (a > b) ? b : a; }

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const long long MOD = 1000000007;

int main(void){
    ll n;
    cin >> n;
    vector<ll> input;
    REP(i,n){
        ll tmp;
        cin >> tmp;
        input.push_back(tmp);
    }
    ll ans =0;
    if( n<3){
        cout << 0 << endl;
        return 0;
    }
    for(ll i=0; i<input.size()-2; i++){
        for(ll j=i+1; j<input.size()-1; j++){
            for(ll k=j+1; k<input.size(); k++){
                if(input[i] == input[j] || input[j] == input[k] || input[k] == input[i]){
                    continue;
                }
                if(input[i] < input[k] + input[j]){
                    if(input[k] < input[i] + input[j]){
                        if(input[j] < input[k]+input[i]){
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3216
# include <bits/stdc++.h>
# define ll long long
# define f first
# define s second
const ll N = 3e5 + 10 , mod = 1e9 + 7 , INF = 1e9 + 100;
using namespace std;
double x[15] , y[15];
double sq(double a , double b){
	return sqrt(a * a + b * b);
}
int main(){
	double n , res = 0;
	cin >> n;
	vector < pair < int , int > > v; 
	for(int i = 1; i <= n; i ++){
		int x , y;
		cin >> x >> y;
		v.push_back({x , y});
	}
	sort(v.begin() , v.end());
	ll x = 1 , y = 1;
	for(int i = 1; i <= n; i ++) x *= i , y *= i;
	while(x --){
		for(int i = 1; i < v.size(); i ++) res += sq(v[i].f - v[i - 1].f , v[i].s - v[i - 1].s);
		next_permutation(v.begin() , v.begin() + n);  
	}
	cout << setprecision(10) << res / y << '\n';
}

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

namespace So {
using namespace std;
class Solution {
  //
  public:
    bool coffeeLike(string instr) {
        return instr[2] == instr[3] && instr[4] == instr[5];
    }
};
}

int main() {
  using namespace std;
  So::Solution sol;
  string instr;
  cin >> instr;
  cout << (sol.coffeeLike(instr) ? "Yes" : "No") << endl;
  return 0;
}

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

using namespace std;

#define LL long long
#define ULL unsigned LL
#define LD long double
#define debug(x) cerr << #x << " " << x << endl;

const int MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int h, w;
	cin>>h>>w;
	int dp[h+1][w+1];
	for(int i=0; i<=h; i++) {
		for(int j=0; j<=w; j++) {
			dp[i][j] = 0;
		}
	}
	string a[h];
	for(int i=0; i<h; i++)
		cin>>a[i];
	dp[1][1] = 1;
	for(int i=1; i<=h; i++) {
		for(int j=1; j<=w; j++) {
			if(i != 1 || j != 1) {
				if(a[i-1][j-1] == '#')
					dp[i][j] = 0;
				else {
					dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % MOD;
				}
			}
		}
	}
	cout<<dp[h][w];
}


Measured memory_bytes: 5248
import std.stdio;
import std.conv;
import std.algorithm;
import std.range;
import std.string;
import std.typecons;
import std.math;
import std.random;
import std.range;
import std.functional;
import std.container;
void main()
{
    auto c = readln.strip.to!int;
    auto k = [0] ~ readln.strip.split(' ').map!(to!int).array;
    foreach (i; 1..c + 1)
    {
        write("node ", i, ": key = ", k[i], ", ");
        auto parent = i / 2;
        auto left = 2 * i;
        auto right = 2 * i + 1;
        if (parent >= 1)
            write("parent key = ", k[parent], ", ");
        if (left <= c)
            write("left key = ", k[left], ", ");
        if (right <= c)
            write("right key = ", k[right], ", ");
        writeln;
    }
}


Measured memory_bytes: 2504
#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll  long long
#define PB push_back
#define ld long double
#define ff first
#define ss second
# define st(v) (v).begin(),(v).end()
#define   pr pair<int,int>
const int N = 1e5+4 , M=N,inf=(int)1e9;
const ll mod=1e9+7;
int fastAbs(int n) { return (n ^ (n >> 31)) - (n >> 31); }
ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
int ans = INT_MAX;
map< pair<int,int> , int > mp;
const int dx[4] = {1,0,0,-1};
const int dy[4] = {0,-1,1,0};
void solve(){
	int n , k ;
	cin >> n >> k ;
	vector < int > a(n) ;
	for( int i = 0 ; i<n ;i++)
		cin >> a[i] ;
	vector < bool > dp(k+1,false);
	for( int i = 1 ; i <= k ; i++){
		for( int j = 0 ; j < n ; j++){
			if(i-a[j]>=0 && !dp[i-a[j]]){
				dp[i] = true ;
			}
		}
	}
	if(dp[k]) cout << "First";
	else cout << "Second";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q=1;
    //cin >> q;
    while(q--)
        solve();
}


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

int main() {
    string s;
    cin >> s;
    int counter = 0;
    if (s[0] == 'o') ++counter;
    if (s[1] == 'o') ++counter;
    if (s[2] == 'o') ++counter;
    cout << 700 + 100*counter << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  char c;
  while(c=getchar(),c!=EOF){
    if(c>='a'&&c<='z') c-=32,cout<<c;
    else if(c>='A'&&c<='Z') c+=32,cout<<c;
    else cout<<c;
  }
}


Measured memory_bytes: 3016
#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;

using ll = long long;

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

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

struct FastPrimeFactorization {
  /**
   * @brief n (<=10^6) 以下の数について高速で素因数分解を行う
   * 
   */
  int n;
  vector<int> divides; // その数を割り切る最小の素因数
  FastPrimeFactorization(int n) : n(n), divides(n+1) {
    // エラトステネスの篩にかけ、最小の素因数をdividesに書き込んでいく
    for (int i = 2; i <= n; ++i) {
      if (divides[i] > 0) continue;
      int j = i;
      while (j <= n) {
        if (divides[j] == 0) {
          divides[j] = i;
        }
        j += i;
      }
    }
    // for (int i = 0; i <= n; ++i) { 
    //   cout << i << " " << divides[i] << endl;
    // }
  }

  map<int, int> calc(int a) {
    map<int, int> ret;
    if (a < 2) return ret;
    int tmp = a;
    while (tmp > 1) {
      int d = divides[tmp];
      ++ret[d];
      assert(d > 0);
      tmp /= d;
    }
    return ret;
  }
};


int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n; cin >> n;
  bool pairwise = true;
  FastPrimeFactorization pf(1000000);
  vector<bool> primes(1000001);

  int g = -1;
  for (int i = 0; i < n; ++i) {
    int a; cin >> a;
    if (g == -1) g = a;
    auto fact = pf.calc(a);
    for (auto it: fact) {
      if (!pairwise) break;
      int d = it.first;
      if (primes[d]) { 
        pairwise = false;
      }
      primes[d] = true;
    }
    if (g > 1) {
      g = gcd(a, g);
    }
  }
  bool setwise = (g == 1);
  if (pairwise) {
    cout << "pairwise coprime" << endl;
  }
  else if (setwise) {
    cout << "setwise coprime" << endl;
  }
  else {
    cout << "not coprime" << endl;
  }
}



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

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var a = int.Parse(line[0]);
        var b = int.Parse(line[1]);
        var c = int.Parse(line[2]);
        var x = int.Parse(line[3]);
        var y = int.Parse(line[4]);
        var ret = new int[3];
        ret[2] = x * a + y * b;
        if (x > y)
        {
            ret[0] = x * 2 * c;
            ret[1] = y * 2 * c + (x - y) * a;
        }
        else
        {
            ret[0] = y * 2 * c;
            ret[1] = x * 2 * c + (y - x) * b;
        }
        Console.WriteLine(ret.Min());
    }
}


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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    int a,b,c;
    cin >> a >> b >> c;
    if (a == b) {
        cout << c << endl;
    } else if (b == c) {
        cout << a << endl;
    } else {
        cout << b << endl;
    }

    return 0;
}


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

int main(){
  int N; cin >> N;
  string S; cin >> S;
  for (int i=0;i<S.size();i++){
    S.at(i)+=N;
    if (S.at(i)>'Z')
      S.at(i)-=26;
  }
  cout << S << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

const int MOD7 = (int)1e9 + 7;
int Fact[100011];

int getpow(int a, int x)
{
    if (x == 0)
        return 1;

    if (x % 2 == 1)
        return (int)(a * 1LL * getpow(a, x - 1) % MOD7);

    int t = getpow(a, x / 2);
    return (int)(t * 1LL * t % MOD7);
};

int getinv(int a)
{
    return getpow(a, MOD7 - 2);
};

void init()
{
    Fact[1] = 1;
    Fact[0] = 1;
    FOR(i, 2, 100011) {
        lint t = Fact[i - 1] * 1LL * i % MOD7;
        Fact[i] = (int) t;
    }
};

int choose(int n, int k)
{
    if (k < 0 || k > n)
        return 0;

    lint ret = Fact[n];
    ret = ret * getinv(Fact[k]) % MOD7;
    ret = ret * getinv(Fact[n - k]) % MOD7;
    return (int) ret;
};

void solveSingleCase(int caseNo)
{
    int N;
    cin >> N;
    VEC(int) V(N + 1);
    READVEC(V);

    init();

    map<int, int> pos;
    int L = 0, R = 0;
    FOR(i, 0, N + 1) {
        if (pos.count(V[i])) {
            L = pos[V[i]];
            R = N - i;
            break;
        }

        pos[V[i]] = i;
    }

    // L, R
    VEC(int) Dups(N + 2, 0);
    FOR(l, 0, L + R + 1) {
        // (L + R choose l)
        Dups[l + 1] = choose(L + R, l);
    }

    FOR(i, 1, N + 2) {
        lint seq = choose(N + 1, i);
        seq = (seq + MOD7 - Dups[i]) % MOD7;
        cout << seq << endl;
    }
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 7040
// AOJ 2197 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2197)
#include<cstdio>
#define rep(i,a) for(int i=0;i<(a);++i)

int N;

int main()
{
	while( scanf( "%d", &N ), N )
	{
		int s = 1, t = 2, S = 1, ans = 0;

		while( s < t )
		{
			while( S < N )
				S += t++;

			if( t-s >= 2 && S == N )
				++ans;

			S -= --t;
			S -= s++;
		}

		printf( "%d\n", ans );
	}

	return 0;
}

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

int main()
{
	string s;
	cin >> s;
	int na = 0;
	int nb = 0;
	for (int i = 0; i < s.size(); i += 2)
	{
		na += (s[i] == '1');
		nb += (s[i] == '0');
	}
	for (int i = 1; i < s.size(); i += 2)
	{
		na += (s[i] == '0');
		nb += (s[i] == '1');
	}
	cout << min(na, nb) << endl;
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main(){
  int n,t;
  int a;
  int i;
  scanf("%d%d",&n,&t);
  int ans=0;
  for(i=0;i<n;i++){
    scanf("%d",&a);
    ans+=(a>=t);
  }
  
  printf("%d\n",ans);
}


Measured memory_bytes: 128
//It doesn't matter how slow you go, Unless you don't stop.
#include<iostream>
#include<algorithm>
#include<bitset>
 
#include<cmath>
#include<cstring>
#include<climits>
 
#include<deque>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
 
#include<fstream>
#include<chrono>
using namespace std;
 
typedef long long LL;
typedef pair<LL,LL> p64;
typedef vector<LL> v64;
typedef map<LL,LL> mp64;
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,s,e) for(long long i=s;i<=e;i++)
#define brep(i,s,e) for(long long i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
void solve()
{
     int n;cin>>n;
     int k;cin>>k;
     LL a[n];
     for(int i=0;i<n;i++)
     {
         cin>>a[i];
     }
     LL dp[n] = {1000000};

    dp[0] = 0;
    dp[1] = abs(a[1]-a[0]);
    for(int i=1;i<n;i++)
    {
        dp[i] = dp[i-1]+abs(a[i]-a[i-1]);
        for(int jump = k; jump >1; jump--)
        {
            if(i-jump>=0)
            {
                dp[i] = min(dp[i],dp[i-jump]+abs(a[i]-a[i-jump]));
            }  
        }
    }
    // for(int i=0;i<n;i++)
    // {
    //     cout<<dp[i]<<" ";
    // }
    //cout<<endl;
    cout<<dp[n-1]<<endl;
     

}
 
int main()
{
    DANGER;
    ofstream out("output.txt");
 
    auto start = chrono::high_resolution_clock::now();
    
    LL t = 1;
    // cin>>t;
    rep(test,1,t)
    {
        solve();
    }
    
    auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int n, m;
  cin >> n >> m;

  vector<string> mat(n);
  rep(i,0,n) {
    cin >> mat[i];
  }

  vvl dp(n, vl(m));
  dp[0][0] = 1LL;
  const ll mod = 1e9+7;
#define in(i,j) (i>=0 and i < n and j >=0  and j < m)
  rep(i,0,n) rep(j,0,m) {
    if (mat[i][j] == '#') continue;
    if (in(i+1, j)) {
      dp[i+1][j] += dp[i][j];
      dp[i+1][j] %= mod;
    }
    if (in(i, j+1)) {
      dp[i][j+1] += dp[i][j];
      dp[i][j+1] %= mod;
    }
  }

  cout << dp[n-1][m-1] << '\n';
}

Measured memory_bytes: 9216
#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 pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

map<pair<string,string>,ll> m1,m2;
int main(){
    int n;
    string s,t;
    cin>>n>>s;
    t=s.substr(n);
    reverse(t.begin(),t.end());
    s=s.substr(0,n);
    rep(i,1<<n){
        string ts1,tt1,ts2,tt2;
        rep(j,n){
            if(i>>j&1){
                ts1+=s[j],tt1+=t[j];
            }
            else{
                ts2+=s[j],tt2+=t[j];
            }
        }
        ++m1[make_pair(ts1,ts2)],++m2[make_pair(tt1,tt2)];
    }
    ll ans=0;
    for(auto it:m1){
        ans+=it.second*m2[it.first];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 108288
#include<bits/stdc++.h>
using namespace std;
#define vb __int128
#define ll long long
#define ld long double
#define full(a) a.begin(),a.end()
#define stoink stack<ll>
#define vec vector <ll>
#define vg vector<vector<ll> >
#define vgw vector<vector<pair<ll,ll> >
#define pa pair<ll,ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define pre 0.00000000000000000001
#define inf 1000000000000
#define mod 998244353
string s1;
string s2;
string ans="";
vg dp;
ll func(ll ind1,ll ind2) {
	if(ind1 == -1 || ind2 == -1)
		return 0;
	if(dp[ind1][ind2] != -1)
		return dp[ind1][ind2];
	ll res;
	if(s1[ind1] == s2[ind2])
		res = func(ind1-1,ind2-1) + 1;
	else {
		res = max(func(ind1-1,ind2),func(ind1,ind2-1));
	}
	return dp[ind1][ind2] = res;
}
void ansfunc(ll i,ll j) {
	if(s1[i] == s2[j]) {
		ans += s1[i];
		if(i > 0 && j > 0)
			ansfunc(i-1,j-1);
	}
	else {
		if(dp[i][j] == 0)
			return;
		if(i > 0 && j > 0) {
			if(dp[i-1][j] > dp[i][j-1])
				ansfunc(i-1,j);
			else
				ansfunc(i,j-1);
		}
		else {
			if(i == 0)
				if(j == 0)
					return;
				else
					ansfunc(i,j-1);
			else
				ansfunc(i-1,j);
		}
	}
}
int main()
{	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> s1;
	cin >> s2;
	ll i,j;
	ll len1 = s1.size();
	ll len2 = s2.size();
	dp.resize(len1,vector<ll>(len2,-1));
	ll len = func(len1 - 1, len2 - 1);
	if(len != 0) {
		ansfunc(len1-1,len2-1);
	}	
	reverse(full(ans));
	cout << ans;
	return 0;
}

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

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main(){
	string s;
	cin >> s;
	vector<int> a(4);
	rep(i,4) a[i] = s[i]-'0';
	vector<char> op(3);
	rep(bit,1<<3){
		int sum=a[0];
		rep(i,3){
			if(bit&1<<i) sum+=a[i+1], op[i]='+';
			else sum-=a[i+1], op[i]='-';
		}
		if(sum==7){
			cout << a[0];
			rep(i,3) cout << op[i] << a[i+1];
			cout << "=7" << endl;
			return 0;
		}
	}

	return 0;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC() ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL);

const int N = 110;
int w[N];
int val[N];
ll dp[N][100005];

int main()
{
    int i = 0, j = 0, cs = 0, in;
    int n, maxw; cin>>n>>maxw;
    for(i = 0; i < n; i++) cin>>w[i]>>val[i];
    for(i = w[0]; i <= maxw; i++) dp[0][i] = val[0];
    for(i = 1; i < n; i++){
        for(j = 0; j <= maxw; j++){
            dp[i][j] = dp[i-1][j];
            if(j >= w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + val[i]);
        }
    }
    cout << dp[n-1][maxw] << endl;
    return 0;
}


Measured memory_bytes: 80128
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
b = [list(map(int,input().split())) for i in range(m)]
for i in range(n):
    c = float("inf")
    e = 0
    g = 0
    for j in range(m):
        d = abs(a[i][0]-b[j][0])+abs(a[i][1]-b[j][1])
        g+=1
        if d <c:
            c,e=d,g
    print(e)

Measured memory_bytes: 9212
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
d=min(a)+min(b)


f=10000000000000000000000000
for i in range(M):
    
    c=list(map(int,input().split()))
    
    h=a[c[0]-1]+b[c[1]-1]-c[2]
    
    if f >= h:
        f=h
        


if d>f:
    d=f
print(d)

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

const int N_MAX = 100000;

set<int> s;
int n;
int h[N_MAX + 10];

int main(){
  cin >> n;
  for(int i = 0;i<n;i++){
    int tmp;
    cin >> tmp;
    h[i] = tmp - 1;
  }

  int corrent = 0;
  int count = 0;
  while(true){
    if(corrent == 1){
      cout << count << endl;
      return 0;
    }else{
      if(s.find(corrent) != s.end()){
	cout << -1 << endl;
	return 0;
      }else{
	s.insert(corrent);
	corrent = h[corrent];
	count++;
      }
    }
  }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N;
    cin >> N;
    vector<P> A;
    rep(i, N) {
        ll a;
        cin >> a;
        A.push_back(make_pair(a, i));
    }
    sort(A.rbegin(), A.rend());
    vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, 0));
    rep(k, N) {
        ll a = A[k].first;
        ll idx = A[k].second;
        rep(i, k + 1) {
            ll j = k - i;
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * abs(idx - i));
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * abs(idx - (N - 1 - j)));
        }
    }
    ll ans = 0;
    rep(i, N + 1) {
        rep(j, N + 1) {
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

class ModInt {
    const int M;
    int value;
public:
    ModInt(long long n, int m) : M(m), value((n % m + m) % m) {}
    ModInt& operator*=(long long x) {
        x %= M;
        if (x < 0) x += M;
        value = static_cast<long long>(value) * x % M;
        return *this;
    }
    int get() { return value; }
};

int main() {
    int n; cin >> n;
    string s; cin >> s;
    char c1, c2;
    int k1 = 0, k2 = 0;
    ModInt ans(1, 998244353);
    for (char c : s) {
        if (k2 > 0) {
            if (c1 != c && c2 != c) {
                ans *= k2;
                k2--;
            } else if (k1 > 0 && c1 != c) {
                assert (c2 == c);
                ans *= k1;
                k1--; k2++;
            } else {
                if (k1 == 0 && c1 != c) swap(c1, c2);
                assert (c1 == c);
                k1++;
            }
        } else if (k1 > 0 && c1 != c) {
            assert (k2 == 0 || c2 == c);
            c2 = c;
            ans *= k1;
            k1--;
            k2++;
        } else {
            assert (k1 == 0 || c1 == c);
            c1 = c;
            k1++;
        }
    }
    for (int i = 1; i <= n; i++) ans *= i;
    cout << ans.get() << endl;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
#define ll long long
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define pb push_back
#define Max(x,y,z) max(x,max(y,z))
#define f first
#define s second
#define lbd lower_bound
#define sz(x)       (ll)x.size()
#define pi 3.1415926536
#define mod 1000000007
using namespace std;
 
void solve ()
{
    ll n,m,k,x,y = 0,res = 0,l,cnt = 0,sum = 0,z,sum1 = 0,cnt1 = 0,h,res1;
    cin >> n;
    ll pre[n],suf[n];
    ll ar[n];
    
	rep ( i , 0 , n )
        cin >> ar[i];
    
	pre[0] = ar[0];suf[n-1] = ar[n-1];
    
	rep ( i , 1 , n ) 
	    pre[i] = __gcd ( pre[i-1] , ar[i] );
    
	for ( ll i = n - 2 ; i >= 0 ; -- i ) 
	    suf[i] = __gcd ( ar[i] , suf[i+1] );
    
	ll ans = max ( suf[1] , pre[n-2] );
    
	rep ( i , 1 , n )
        ans = max ( ans , __gcd ( pre[i-1] , suf[i+1] ) );
    
	cout << ans;
	
}
 
int main ()
{
    ll t;
    
    t = 1;
    while ( t -- )
        solve ();
    
    return 0;
	 
}

Measured memory_bytes: 2560