akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto itr : x) { debug(itr); }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

template <class T = long long>
class Union_Find {
  using size_type = std::size_t;
  using _Tp = T;
public:

  vector<_Tp> par;

  const _Tp operator[] (size_type child) {
    return -par[root(child)];
  }

  Union_Find(size_type n) : par(n, -1) {}
  void init(int n) {
    par.assign(n, -1);
  }

  _Tp root(size_type x) {
    if (par[x] < 0) return x;
    else return par[x] = root(par[x]);
  }

  bool issame(size_type x, size_type y) {
    return root(x) == root(y);
  }

  bool merge(size_type x, size_type y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (par[x] > par[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }

  _Tp size(int x) {
    return -par[root(x)];
  }
};
 
#include <map>

int main() {
  int n, m;
  cin >> n >> m;
  Union_Find<ll> uf(n);

  rep(i, m) {
    int x, y, z;
    cin >> x >> y >> z;
    x--, y--;
    uf.merge(x, y);
  }

  map<int, int> mp;
  ll ans = 0;
  for (int i = 0; i < n; ++i) {
    if (!mp[uf.root(i)]) {
      ans += uf[i] - 1;
      mp[uf.root(i)] = 1;
    }
  }

  cout << n - ans << endl;
}


Measured memory_bytes: 5760
n,m=map(int,input().split())

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())


uf=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
q=-min(uf.parents)
print(q)

Measured memory_bytes: 87128
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
    
ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll tans;
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i=1; i*i<=n; i++) {
    if(n%i==0) {
      ret.push_back(i);
      if(i*i!=n)ret.push_back(n/i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n>>k;
    rep(i,n){
        cin>>a[i];
        sum+=a[i];
    }
    vector<ll> yakusuu=divisor(sum);
    rep(i,Size(yakusuu)){
        ans=yakusuu[i];
        P dat[n+5]={};
        rep(j,n){
            dat[j]=m_p(a[j]%ans,ans-a[j]%ans);
        }
        sort(dat,dat+n);
        ll fu[n+5]={},sei[n+5]={};
        rep(j,n){
            fu[j]=dat[j].fi;
            sei[j]=dat[j].se;
        }
        rrep(j,1,n){
            fu[j]+=fu[j-1];
            sei[j]+=sei[j-1];
        }
        ll cnt=LINF;
        rep(j,n+1){
            //fuのj-1まで
            ll fu1,se1;
            if(j!=0)fu1=fu[j-1];
            else fu1=0;
            //seはj以降
            if(j!=0)se1=sei[n-1]-sei[j-1];
            else se1=sei[n-1];
            cnt=min(cnt,max(se1,fu1));
        }
        //if(ans==7)Cout(cnt);
        if(cnt<=k)tans=ans;
    }
    Cout(tans);
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
mod = 10**9+7
a = 0
for i, j, k in zip(range(n), x[:-1], x[1:]):
    a += abs(j-k) * (i+1)*(n-1-i)
b = 0
for i, j, k in zip(range(m), y[:-1], y[1:]):
    b += abs(j-k) * (i+1)*(m-1-i)
a %= mod
b %= mod
print(a*b % mod)


Measured memory_bytes: 25392
chomp($str = <STDIN>);

if($str ne reverse($str)){
	print "No\n";
	exit;
}

$a = substr($str, 0, ((length($str) - 1) / 2));
$b = substr($str, ((length($str) + 3) / 2) - 1, length($str) - 1);

foreach $one ($a, $b){
	if($one ne reverse($one)){
		print "No\n";
		exit;
	}
}

print "Yes\n";


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

int main(){
    int n,d;
    cin >> n >> d;
    vector<vector<int>> x(n,vector<int>(d));
    rep(i,n) rep(j,d) cin >> x.at(i).at(j);
    int ans =0;
    for(int i = 0; i < n;i++){
        for(int j = i+1; j < n;j++){
            int dis = 0;
            rep(k,d) {
                dis += pow(x.at(i).at(k)-x.at(j).at(k),2);
            }
            int sq = sqrt(dis);
            if(dis == sq*sq) ans++;
        }
    }
    cout << ans << endl;
}

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

int main() {
  int n; cin >> n;
  int count=1;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int Min = p[0];
  
  rep(i,n-1) {
    Min = min(Min, p[i]);
    if(Min<p[i+1]) continue;
    else count++;
  }

  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();;
		int N = int.Parse(str[0]);
		int K = int.Parse(str[1]);
		string[] str2 = Console.ReadLine().Split();
		int[] A = new int[N];
		for(var i=0;i<N;i++){
			A[i] = int.Parse(str2[i]);
		}
		int ans = 0;
		int ia = N-1;
		while(ia>0){
			ans += 1;
			ia -= K-1;
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 16864
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf

int n;
int ans = 0;

void go(long long curNum, bool three, bool five, bool seven) {
  if (curNum <= n) {
    if (three && five && seven) {
      ans++;
    }
  } else {
    return;
  }
  go(curNum * 10 + 3, true, five, seven);
  go(curNum * 10 + 5, three, true, seven);
  go(curNum * 10 + 7, three, five, true);
}

int main() { 

  cin >> n;
  go(0, false, false, false);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import deque

dll = [[-1,-1, None]]
first = 0
cursor = 0

def insert(x):
    global cursor, first
    dll.append([dll[cursor][0],cursor,x])
    new_cursor = len(dll) - 1
    if dll[cursor][0] != -1:
        dll[dll[cursor][0]][1] = new_cursor
    dll[cursor][0] = new_cursor
    if cursor == first:
        first = new_cursor
    cursor = new_cursor

def move(d):
    global cursor
    if d > 0:
        for _ in range(d):
            cursor = dll[cursor][1]
    elif d < 0:
        for _ in range(-d):
            cursor = dll[cursor][0]

def erase():
    global cursor, first
    if dll[cursor][0] != -1:
        dll[dll[cursor][0]][1] = dll[cursor][1]
    if dll[cursor][1] != -1:
        dll[dll[cursor][1]][0] = dll[cursor][0]
    if cursor == first:
        first = dll[cursor][1]
    cursor = dll[cursor][1]

def main():
    Q = int(input())
    for _ in range(Q):
        query = input().split()
        if query[0] == '0':
            insert(query[1])
        elif query[0] == '1':
            move(int(query[1]))
        elif query[0] == '2':
            erase()

    i = first
    while dll[i][2] != None:
        print(dll[i][2])
        i = dll[i][1]

main()



Measured memory_bytes: 94468
// しゃきょうおぶけんとん
#include <bits/stdc++.h>

using namespace std;
using ll =long long;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
static const ll INF = 1LL << 60;
//Write From this Line

long long rec(int n, long long x){
	long long len = (1LL <<(n+1)) -3 ;
	long long num = (1LL <<n) -1;
	if (n == 0) return 1;
	if (x == 1) return 0;
	else if (x <= len + 1) return rec(n-1, x-1);
	else if (x == len + 2) return num + 1;
	else if (x <= (len + 1) * 2) return num + 1 + rec(n-1, x - len - 2);
	else return num * 2 + 1;
}
int main()
{
	int N; 
	cin >> N; 
	ll X;
	cin >> X;
	cout << rec(N, X) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
char S[200005];
void yes() {
	printf("Yes\n");
	exit(0);
}
void no() {
	printf("No\n");
	exit(0);
}
int main() {
	int n, a, b, c, d;
	scanf("%d%d%d%d%d%s", &n, &a, &b, &c, &d, S + 1);
	for (int i = a; i + 1 <= c; ++i)
		if (S[i] == '#' && S[i + 1] == '#') no();
	for (int i = b; i + 1 <= d; ++i)
		if (S[i] == '#' && S[i + 1] == '#') no();
	if (d < c) {
		for (int i = b; i <= d; ++i) {
			if (S[i] != '#' && S[i - 1] != '#' && S[i + 1] != '#') yes();
		}
		no();
	}
	yes();
}


Measured memory_bytes: 3876
#include<bits/stdc++.h>
using namespace std;
int min(int a,int b,int c)
{   if(a<=b)
    { if(a<=c)
        return a;
      return c;
    } else
    { if(b<=c)
        return b;
    return c;
    }}

int main() {
  int n,a,b;
  cin>>n>>a>>b;
  int count[n-1];
  for(int &x:count)
      x=0;
  for(int i=1;i<n;i++)
  {
      for(int j=i+1;j<=n;j++)
      {  
        count[min(abs(j-i),abs(j-b)+abs(i-a)+1,abs(i-b)+abs(j-a)+1)-1]++;
      }
  }
  for(int i=0;i<n-1;i++)
      cout<<count[i]<<"\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=507;
int n,l,r,tot,p[N*N],dis[N][N],f[N][N],qx[N*N*5],qy[N*N*5],xa[N*N],ya[N*N];
inline void solve(){
	while(l<=r){
		int a=qx[l],b=qy[l++];
		if(a>=2&&dis[a-1][b]>dis[a][b]+f[a-1][b]){
			dis[a-1][b]=dis[a][b]+f[a-1][b];
			r++,qx[r]=a-1,qy[r]=b;
		}
		if(a<n&&dis[a+1][b]>dis[a][b]+f[a+1][b]){
			dis[a+1][b]=dis[a][b]+f[a+1][b];
			r++,qx[r]=a+1,qy[r]=b;
		}
		if(b>=2&&dis[a][b-1]>dis[a][b]+f[a][b-1]){
			dis[a][b-1]=dis[a][b]+f[a][b-1];
			r++,qx[r]=a,qy[r]=b-1;
		}
		if(b<n&&dis[a][b+1]>dis[a][b]+f[a][b+1]){
			dis[a][b+1]=dis[a][b]+f[a][b+1];
			r++,qx[r]=a,qy[r]=b+1;
		}
	}
}
int main(){
	cin>>n,l=1,r=0;
	for(int i=1;i<=n*n;i++) scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) tot++,xa[tot]=i,ya[tot]=j,f[i][j]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) dis[i][j]=n*n*n;
	for(int i=1;i<=n;i++){
		dis[i][1]=dis[1][i]=dis[i][n]=dis[n][i]=1;
		r++,qx[r]=i,qy[r]=1,r++,qx[r]=1,qy[r]=i;
		r++,qx[r]=n,qy[r]=i,r++,qx[r]=i,qy[r]=n;
	}
	solve();
	long long ans=0;
	for(int i=1;i<=n*n;i++){
		dis[xa[p[i]]][ya[p[i]]]--,f[xa[p[i]]][ya[p[i]]]=0;
		ans+=dis[xa[p[i]]][ya[p[i]]];
		l=1,r=1,qx[1]=xa[p[i]],qy[1]=ya[p[i]];
		solve();
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 10552
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int N,K;
    cin >> K >> N;
    vector<int> houses(N);
    
    //いちばん距離の遠いふたつの家（間に家を含まない）をむすぶ

    for(int i=0;i<N;i++){
        cin >> houses[i];
    }

    int diff[N];
    int max = -1;
    for(int i=0;i<N;i++){
        diff[i] = houses[i+1] - houses[i];
        if(max < diff[i]){
            max = diff[i];
        }
    } 
    if(max < (K-houses[N-1])+houses[0]){
        max = K-houses[N-1]+houses[0];
    }

    cout << K - max << endl;

    return 0;
}


Measured memory_bytes: 1792
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  (x : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  let
    n :: Int
    n | 2000 <= x = 1
      | x `elem` concatMap f [1..19] = 1
      | otherwise = 0
      where
        f :: Int -> [Int]
        f i = [(i * 100)..(i * 105)]
  print n

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
    string s, t;
    int cnt=0;
    cin >> s >> t;
    rep(i, s.size()){
        if(s.at(i) == t.at(i)) cnt++;
    }
    cout << cnt << endl;
}

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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

int dp[3030][3030];
void solve(long long N, std::string s) {
    memset(dp, 0, 3030 * 3030 * sizeof(dp[0][0]));

    rep(i, N) dp[0][i] = 1;
    rep(i, s.size()) {
        vi cum(N + 1);
        rep(j, N) {
            cum[j + 1] = dp[i][j] + cum[j];
            cum[j + 1] %= mod;
        }
        if (s[i] == '<') {
            rep(j, N - i) {
                // for (int k = j + 1; k < N - i; k++) {
                //     dp[i + 1][j] = (dp[i + 1][j] + dp[i][k]) % mod;
                // }
                dp[i + 1][j] = (dp[i + 1][j] + cum[N - i] - cum[j + 1] + mod) % mod;
            }
        } else {
            rep(j, N - i) {
                // for (int k = 0; k < j + 1; k++) {
                //     dp[i + 1][j] = (dp[i + 1][j] + dp[i][k]) % mod;
                // }
                dp[i + 1][j] = (dp[i + 1][j] + cum[j + 1] - cum[0] + mod) % mod;
            }
        }
    }

    cout << dp[s.size()][0] << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    long long N;
    cin >> N;
    std::string s;
    std::cin >> s;
    solve(N, s);
    return 0;
}


Measured memory_bytes: 72064
#include <bits/stdc++.h>
#include<math.h>
#include<queue>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
using ll = long long;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> check(1000001,0);
    cin >> A.at(0);
    ll GCD=A.at(0);
    for(ll i=0; i<N; i++){
        cin >> A.at(i);
        GCD=gcd(A.at(i),GCD);
    }
    bool pc=true;
    for(ll j=0; j<N; j++){
        ll n=A.at(j);
        for(ll i=2; i*i<=n; i++){
            if(n%i==0 && (check.at(i) != 0)){
                pc = false;
                break;
            }else if(n%i==0){
                check.at(i)=1;
                while(n%i==0){
            	    n /= i;
                }
            }
        }
        if(n != 1 && check.at(n)!=0){
            pc = false;
        }else if(n!=1){
            check.at(n)=1;
        }
        if(!pc) break;
    }
    if(pc){
        cout << "pairwise coprime";
    }else if(GCD==1){
        cout << "setwise coprime";
    }else{
        cout << "not coprime";
    }
}

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

int main(){
  int n, k, min=1000000;
  cin >> n >> k;
  
  for(int i=0;i<n;i++){
  	int s=1;
    for(int j=0;j<n-i;j++) s *= 2;
    s+=i*k;
    if(min>s) min=s;
  }
  cout << min << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define ll long long

int main(){
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++){

        if (i % 3 != 0 && i % 5 != 0) {
            sum += i;
        }
    }
    cout << sum << "\n";
}

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;

int main()
{
	int x1,y1,x2,y2;
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	int sum=x1*y1;
	sum-=x1*y2;
	sum-=x2*y1;
	sum+=x2*y2;
	printf("%d\n",sum);
}

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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define dbg(var) {std::cout << #var << "  = " << var << nl;}
#define vi vector<int>
typedef long long ll;

using namespace std;

constexpr int MOD = 1e9 + 7;

struct CNK{
	const int mod = 1000000007;
	int mx;
   
	vi fac , ifac;
	   
public:
	CNK(int max){
		mx = max;
	   
		fac.resize(max + 1);
		ifac.resize(max + 1);
	   
		fac[0] = ifac[0] = 1;
	   
		for(int i = 1 ; i <= max ; ++i){
			fac[i] = 1LL * fac[i - 1] * i % mod;
			ifac[i] = fpow(fac[i], mod - 2);
		}
	}
   
	int fpow(int a , int b){
		ll ans = 1;
		while(b > 0){
			if(b & 1){
				ans = (1LL * ans * a) % mod;
			}
			a = (1LL * a * a) % mod;
			b /= 2;
		}
		return ans;
	}
   
	int cnk(int n , int k){
		assert(mx >= n);
		if (n < 0 || k < 0 || k > n) return 0;
		return 1LL * fac[n] * ifac[n - k] % mod * ifac[k] % mod;
	}
};

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

	int n , k;
	cin >> n >> k;
	
	CNK cnk(10000);
	
	repi(i , k)
	{
		cout << (1LL * cnk.cnk(k - 1 , k - i) * cnk.cnk(n - k + 1 , i)) % MOD << nl;
	}
	
	return 0;
}

Measured memory_bytes: 384
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

static const long long mod = 1000000007;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n, m;
  cin >> n >> m;

  vll sxs(n), sys(n), cxs(m), cys(m);
  rep(i, n) cin >> sxs[i] >> sys[i];
  rep(i, m) cin >> cxs[i] >> cys[i];

  rep(i, n) {
    ll ans;
    ll dis = INF;
    rep(j, m) {
      ll tdis = abs(sxs[i] - cxs[m - 1 - j]) + abs(sys[i] - cys[m - 1 - j]);
      if (dis >= tdis) {
        ans = m - 1 - j + 1;
        dis = tdis;
      }
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    ll len = s.size();
    ll dp[len];
    fill(dp, dp + len, inf);
    ll now = 0;
    map<ll, ll> mp;
    mp[0] = 1;
    REP(i, 0, len) {
        ll chnum = s[i] - 'a';
        now = now ^ ((ll)1 << chnum);
        // cout << now << endl;
        if (now == 0) {
            mp[now] = 1;
            dp[i] = 1;
        } else {
            REP(j, 0, 26) {
                ll p = now ^ ((ll)1 << j);
                if (p == 0) {
                    mp[now] = 1;
                    dp[i] = min(dp[i], (ll)1);
                } else {
                    if (mp.count(p) != 0) {
                        if (mp.count(now) != 0) {
                            mp[now] = min(mp[now], mp[p] + 1);
                        } else {
                            mp[now] = mp[p] + 1;
                        }
                        dp[i] = min(dp[i], mp[p] + 1);
                    }
                }
            }
        }
    }
    // REP(i, 0, len) {
    //     cout << dp[i] << endl;
    // }
    ll ans = dp[len - 1];
    cout << ans << endl;
}


Measured memory_bytes: 14484
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,x;
  long long c=0;
  cin>>n>>x;
  int a[n];
  cin>>a[0];
  if(a[0]>x){
    c+=a[0]-x;
    a[0]=x;
  }
  for(int i=1;i<n;i++){
    cin>>a[i];
    if(a[i]+a[i-1]>x){
      c+=a[i]+a[i-1]-x;
      a[i]-=a[i]+a[i-1]-x;
    }
  }
  cout<<c;
}

Measured memory_bytes: 640
/*"Everything in the universe is balanced. Every disappointment
   you face in life will be balanced by something good for you!
                Keep going, never give up."            */

#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repd(i,a,b) for(int i=a; i>=b; --i)
#define nl '\n'
#define pb push_back
#define all(a) a.begin(),a.end()
#define P pair<ll,ll> 
#define F first
#define S second
const ll N=1e6+9;
const ll mod=1e9+7;
ll powerk(ll x, ll y);
ll mul(ll x, ll y);
ll add(ll x, ll y);
ll sub(ll x, ll y);

ll a[N];
ll dp[500][500],id[500][500];

void solve()
{    
  ll n,m;
  cin>>n;
  rep(i,1,n)cin>>a[i];
  rep(i,1,n)rep(j,1,n)id[i][j] = 1e18,dp[i][j]=1e18;
  
  rep(i,1,n)dp[i][i]=a[i],id[i][i]=0;
  rep(i,2,n){
  	rep(j,i,n){
  		ll k = j-i+1 ;
  		rep(l,k,j-1){
  			if(id[k][j]>dp[k][l]+dp[l+1][j]+id[k][l]+id[l+1][j]){
  				dp[k][j] = dp[k][l]+dp[l+1][j];
  				id[k][j] = id[k][l]+id[l+1][j]+dp[k][j];
  			}
  			//if(k==1 && j==4)cout<<dp[k][j]<<" "<<id[k][j]<<nl;
  		}
   	}
  }
  cout<<id[1][n];
  /*rep(i,1,n){
  	rep(j,1,n)cout<<dp[i][j]<<id[i][j]<<" ";cout<<nl;
  }*/
/*
  ll i=1,j=n,ans=0;
  while(j-i>0){
  	ll x = dp[i+1][j];
  	ll y = dp[i][j-1];
  	if(x+a[i]<=y+a[j]){
  		ans+= a[i]+x;
  		i++;
  	}
  	else {
  		ans+= a[j]+y;
  		j--;
  	}
  	cout<<i<<" "<<j<<" "<<ans<<nl;
  }
  cout<<ans<<nl;
*/
}


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t=1;
    //pre();
    //cin>>t;
    while(t--)
    {
      solve();
    }  
}
ll mul(ll x, ll y){return (x*y)%mod;}
ll add(ll x, ll y){return (x+y)%mod;}
ll sub(ll x, ll y){return (x-y+mod)%mod;}
ll powerk(ll x, ll y)
{
  if(y==0)return 1;
  if(y==1)return x%mod;
  if(y&1)
    return ((powerk((x*x)%mod, y/2)%mod)*x)%mod;
  else return powerk((x*x)%mod,y/2)%mod;
}

// Xorawar

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

namespace _0231
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int n = RInt();
                if (n == 0) break;

                List<Tuple<int, int>> events = new List<Tuple<int, int>>();
                for (int i = 0; i < n; i++)
                {
                    int[] vs = RArInt();
                    events.Add(new Tuple<int, int>(vs[1], vs[0]));
                    events.Add(new Tuple<int, int>(vs[2], -vs[0]));
                }
                Console.WriteLine(IsBreak(events) ? "NG" : "OK");
            }
        }

        private static bool IsBreak(List<Tuple<int, int>> events)
        {
            int loadWeight = 0;
            foreach (var item in events.OrderBy(x => x.Item1).ThenBy(x => x.Item2))
            {
                loadWeight += item.Item2;
                if (loadWeight > 150) return true;
            }
            return false;
        }

        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}



Measured memory_bytes: 18264
#include <bits/stdc++.h>
#define _boost ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define fi first
#define se second
#define clz __builtin_clz
#define clzll __builtin_clzll
#define bp __builtin_popcount
#define _unique(x) sort((x).begin(),(x).end()),(x).erase(unique((x).begin(), (x).end()),(x.end()))
#define all(x) (x).begin(),(x).end()
#define _rand(i,j) uniform_int_distribution<int>(i, j)(rng___)
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;
template < typename _T, typename _T2> string to_string(pair<_T,_T2> x) {return "<"+to_string(x.fi)+", "+to_string(x.se)+">";}
template < typename _T> string to_string(vector<_T> vec) {string s="[ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]=']';s[s.size()-2]=' '; return s;}
string to_string(string s) {return s;}
template < typename _T> string to_string(set<_T> vec) {string s="{ "; for(auto el:vec)s+=to_string(el)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T, typename _T2> string to_string(map<_T,_T2> vec) {string s="{ "; for(auto el:vec)s+="mp["+to_string(el.fi)+"]= "+to_string(el.se)+", "; s[s.size()-1]='}';s[s.size()-2]=' '; return s;}
template < typename _T > inline void _DBG(const char *s, _T x){cerr << s << " = " << to_string(x) << "\n";}
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a){while(*s != ',') cerr << *s++;cerr << " = " << to_string(x) << "\n";_DBG(s + 1, a...);}
#ifdef LOCAL
#define _print(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define _print(...) ;//cout<<2;//(__VA_ARGS__)
#endif
mt19937 rng___(chrono::steady_clock::now().time_since_epoch().count());


const LL MOD = 1e9+7;//998244353;
const LL LLINF = 1e18+7;
const int N=1e5+8;

vector<vector<int>> G(N);
LL ways[N][2];
void dfs(int v,int p=0)
{
    for(int u:G[v])
    {
        if(u!=p)
        {
            dfs(u,v);
        }
    }
    ways[v][0]=1;
    ways[v][1]=1;
    if(G[v].size()>1 || p==0)
    {
        for(int u:G[v])
        {
            if(u!=p)
            {
                ways[v][0]=(ways[v][0]*(ways[u][0]+ways[u][1]))%MOD;
                ways[v][1]=(ways[v][1]*ways[u][0])%MOD;
            }
        }
    }
    //_print(v,ways[v][0],ways[v][1]);
}
int main()
{
    _boost;
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    cout<<(ways[1][0]+ways[1][1])%MOD;
}




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

using namespace std;
using ll = unsigned long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 3;

void solve() {
    int n; cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    
    ll r=0, b=0, g=0;
    ll ans = 1LL;
    for (int i = 0; i < n; ++i) {
        if(a[i] == r) {
            ll tmp = 1;
            if(r == g){++tmp;}
            if(r == b){++tmp;}
            ++r;
            ans *= tmp;
        }
        else if(a[i] == g) {
            ll tmp = 1;
            if(g == b){++tmp;}
            ++g;
            ans *= tmp;
        }
        else if(a[i] == b) {
            ++b;
        }
        else{
          ans = 0;
        }
        ans %= MOD;
    }
    cout << ans << endl;
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}



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

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

map<int, int> ht;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll ans = 0;
	int N; cin >> N;
	rep1(i, N) {
		int ld = i%10;
		int v = i;
		while(v/10) v /= 10;
		ht[ld*10+v]++;
	}
	rep1(i, N) {
		int ld = i%10;
		int v = i;
		while(v/10) v /= 10;
		ans += ht[v*10+ld];
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include <numeric>
#include<map>
 
 
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 1e13
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
 
typedef long long int ll;
#define MOD 1000000007


struct Potential_UnionFind{
    vector<int> par;
    vector<int> rank;
    vector<int> diff_weight;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        diff_weight.resize(n);
        REP(i,n){
            par[i] = i;
            rank[i] = 0;
            diff_weight[i] = 0;
        }
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    int weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x,int y) {
        return root(x) == root(y);
    }

    void merge(int x, int y,int w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
    }

    int diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

Potential_UnionFind PUF;

int main(){

    int n,q;
    cin >> n >> q;
    PUF.init(n);
    
    REP(i,q){

        int num,x,y,z;
        cin >> num;
        if(!num){
            //mergeする
            cin >> x >> y >> z;
            PUF.merge(x,y,z);     

        }else{
            //diffを求める

            cin >> x >> y;
            if(!PUF.issame(x,y)){
                cout << "?" << endl;
            }else{
                cout << PUF.diff(x,y) << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3892
#include <set>
#include <iostream>
#include <iomanip>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())

set<int> s1, s2;

int main(){
	while(1){
		int n,m;
		int S1=0, S2=0;
		s1.clear();s2.clear();
		cin >> n>>m;
		if(n==0)return 0;
		REP(i,n){
			int tmp;
			cin >> tmp;
			s1.insert(tmp);
			S1 += tmp;
		}
		REP(i,m){
			int tmp;
			cin >> tmp;
			s2.insert(tmp);
			S2 += tmp;
		}
		if((S1^S2)&1){
			cout << "-1" << endl;
			continue;
		}
		int b = (S1-S2)/2;
		int flag = 0;
		for(set<int>::iterator it = s1.begin(); it!=s1.end(); it++){
			int k = (*it);
			if(EXIST(s2, k-b)){
				cout << k << " " << k-b << endl;
				flag = 1;
				break;
			}
		}
		if(!flag)cout << "-1" << endl;
	}
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef vector<int> vi;
    typedef vector<long long> vll;
    typedef vector<pair<int , int>> vpii;
    typedef pair<int , int> pii;
    typedef pair<long long  , long long> pll;
    typedef pair<double , double> pdd;
    #define eb emplace_back;
    #define mp make_pair;
     
    int main(){
        int bingo[3][3];
        for(int i = 0 ; i<3 ; i++){
            for(int j = 0 ; j<3 ; j++){
                cin>>bingo[i][j];
            }
        }
        int n;
        cin>>n;
        while(n--){
            int x;
            cin>>x;
            for(int i = 0 ; i<3 ; i++){
                for(int j = 0 ; j<3 ; j++){
                    if(bingo[i][j] == x){
                        bingo[i][j] = 0;
                    }
                }
            }
        }
        bool ok = false;
        for(int i = 0 ; i<3 ; i++){
            if(!bingo[i][0] && !bingo[i][1] && !bingo[i][2]){
                ok = true;
                break;
            }
        }
        if(!ok){
            for(int i = 0 ; i<3 ; i++){
                if(!bingo[0][i] && !bingo[1][i] && !bingo[2][i]){
                    ok = true;
                    break;
                }
            }
        }
        if((!bingo[0][0] && !bingo[1][1] && !bingo[2][2])|| (!bingo[0][2] && !bingo[1][1] && !bingo[2][0])){
            ok = true;
        }
        if(ok){
            cout<<"Yes";
        }
        else{
            cout<<"No";
        }
        return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define int          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 F           first
#define S           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007 
#define mem(x)      memset(x,0,sizeof(x));
#define what_is(x)  cout << #x << " is " << x << flush << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
 
using namespace std;
const int maxn = 100010;
int n,w;
void solve(){
	string s, t;
	cin>>s>>t;
	int n = s.length(), m = t.length();

	int dp[n+1][m+1];
	memset(dp, 0, sizeof(dp));
	rep(i, 1, n+1)
	{
		rep(j, 1, m+1)
		{
			if(s[i-1]==t[j-1])
				dp[i][j] = 1 + dp[i-1][j-1];
			else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
	}
	string ans = "";
	int i = n, j = m;
	int flag = 0;
	if(n>m)
		flag = 1;
	while(i>0 && j>0)
	{
		if(dp[i-1][j-1]+1==dp[i][j] && s[i-1]==t[j-1])
		{
			ans+=s[i-1];
			i--;
			j--;
		}
		else
		{
			if(dp[i][j] == dp[i-1][j])
			{
				i--;
			}
			else
			{
				j--;
			}
		}
	}
reverse(ans.begin(), ans.end());

	cout<<ans;



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

Measured memory_bytes: 70656
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c) {
	stack<int> S;
	S.push(r);
	color[r] = c;
	while (!S.empty()) {
		int u = S.top();
		S.pop();
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			if (color[v] == NIL) {
				color[v] = c;
				S.push(v);
			}
		}
	}
}

void assignColor() {
	int id = 1;
	for (int i = 0; i < n; i++)color[i] = NIL;
	for (int u = 0; u < n; u++) {
		if (color[u] == NIL)dfs(u, id++);
	}
}

int main(void) {
	int s, t, m, q;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &s, &t);
		G[s].push_back(t);
		G[t].push_back(s);
	}

	assignColor();

	scanf("%d", &q);

	for (int i = 0; i < q; i++) {
		scanf("%d%d", &s, &t);
		if (color[s] == color[t]) {
			printf("yes\n");
		}
		else {
			printf("no\n");
		}
	}
	return 0;
}


Measured memory_bytes: 9072
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
 int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(abs(a-c)<=d) co("Yes");
  else if(abs(a-b)<=d && abs(b-c)<=d) co("Yes");
  else co("No");
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int v[10][10],n,ans,vis[10];
void dfs(int s,int cnt)
{
    if(cnt==n)
    {
        ans++;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&(v[i][s]||v[s][i]))
        {
            vis[i]=1;
            dfs(i,cnt+1);
            vis[i]=0;
        }
    }
}
int main()
{
    int m,x,y;
    scanf("%d%d",&n,&m);
    memset(v,0,sizeof(v));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x][y]=1,v[y][x]=1;
    }
    ans=0;
    vis[1]=1;
    dfs(1,1);
    printf("%d\n",ans);
}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
nums = [0] * N
for pos in range(N):
    nums[pos] = int(input())
snums = sorted(nums[:])
rank = {}
for i,e in enumerate(snums):
    rank[e] = i+1

rev = 0
for i,e in enumerate(nums):
    if (i + rank[e]) % 2 == 0:
        rev += 1
print(rev // 2)


Measured memory_bytes: 19868
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n,m;
	string s;
	Vi ans;
	cin >>n>>m>>s;
	reverse(all(s));
	clog<<s<<endl;
	int len=0;
	int cnt=0;
	rep(i,s.size()){
		if(s[i]=='1'){
			cnt++;
		}else{
			chmax(len,cnt);
			cnt=0;
		}
	}
	chmax(len,cnt);
	if(len >= m  ){
		cout<<-1<<endl;
		return 0;
	}
	int at=0;
	int will;
	while(at < s.size()-1){
		for(int i=at;i<=at+m and i<s.size();i++){
			if(s[i]=='0'){
				will=i;
			}
		}
		ans.push_back(will-at);
		at=will;
	}
	reverse(all(ans));
	repi(itr,ans){
		cout<<(*itr);
		if(itr+1!=ans.end()){
			cout<<" ";
		}
	}
cout<<endl;
}

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

int main(){
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	int i = 0;
	while(1){
		if(i == (int)s.size()){
			cout << "YES" << endl;
			break;
		}
		if(s.at(i) == 'e'){
			if(s.substr(i, 5) == "esare"){
				i += 5;
			}
			else{
				cout << "NO" << endl;
				break;
			}
		}
		else if(s.at(i) == 'm'){
			if(s.substr(i, 5) == "maerd"){
				i += 5;
			}
			else{
				cout << "NO" << endl;
				break;
			}
		}
		else if(s.at(i) == 'r'){
			if(s.substr(i, 6) == "resare"){
				i += 6;
			}
			else if(s.substr(i, 7) == "remaerd"){
				i += 7;
			}
			else{
				cout << "NO" << endl;
				break;
			}
		}
		else{
			cout << "NO" << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9 + 7;
const int INF = 9e18;

signed main() {
    int N, x;
    cin >> N >> x;
    if (2 <= x && x <= 2 * N - 2) {
        cout << "Yes" << endl;
        set<int> check;
        check.insert(x - 1);
        check.insert(x);
        check.insert(x + 1);
        int count = 0;
        for (int i = 1; i <= 2 * N - 1; i++) {
            if (N - 1 == i) {
                for (int temp : check) {
                    cout << temp << endl;
                }
                i += 2;
                continue;
            }
            while (true) {
                ++count;
                if (check.find(count) == check.end()) {
                    cout << count << endl;
                    break;
                }
            }
        }
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 1536
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

ans = INF

for h in range(1, H+1):
	S1 = h*W
	S2 = (H-h)*(W//2)
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

H, W = W, H

for h in range(1, H+1):
	S1 = h*W
	S2 = (H-h)*(W//2)
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

	S2 = (H-h)//2*W
	S3 = H*W-S1-S2
	ans = min(ans, max(S1, S2, S3)-min(S1, S2, S3))

print(ans)


Measured memory_bytes: 3900