akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

class Main{
    static List<Integer> edges[];
    static int white[];
    static boolean nibu=true;
    static void bfs(int v, int c){
        if(white[v]>=0){
            if(c%2!=white[v])nibu=false;
            return;
        }
        white[v]=c;
        for(int u :edges[v])bfs(u, (c+1)%2);
    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        boolean[][] edge = new boolean[N][N];
        for(boolean[] arr: edge)Arrays.fill(arr, false);
        while(M-->0){
            int a = scan.nextInt()-1;
            int b = scan.nextInt()-1;
            edge[a][b]=true;
            edge[b][a]=true;
        }
        edges = new ArrayList[N];
        white = new int[N];
        Arrays.fill(white, -1);
        for(int i=0;i<N;++i)edges[i]=new ArrayList<>();
        int root = -1;
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<N;++i)for(int j=i+1;j<N;++j)if(!edge[i][j]){
            edges[i].add(j);
            edges[j].add(i);
            set.add(i);
            set.add(j);
        }
        List<Integer> n = new ArrayList<>();
        List<Integer> m = new ArrayList<>();
        for(int i=0;i<N;++i){
            if(set.contains(i) && white[i]<0){
                bfs(i, 0);
            }
            int nn=0,mm=0;
            for(int j=0;j<N;++j){
                if(white[j]==0)++nn;
                if(white[j]==1)++mm;
                if(white[j]==0||white[j]==1)white[j]=2;
            }
            if(mm>nn){
                int tmp=mm;
                mm=nn;nn=tmp;
            }
            n.add(nn);
            m.add(mm);
        }
        if(!nibu){
            System.out.println(-1);
        }else{
            int amari = 0;
            for(int i=0;i<N;++i){
                if(white[i]<0)++amari;
            }
            List<Integer> sub = new ArrayList<>();
            for(int i=0;i<n.size();++i)sub.add(n.get(i)-m.get(i));
            boolean[][] dp =new boolean[N+1][N];
            dp[0][0]=true;
            for(int i=0;i<N;++i){
                for(int j=0;j<N;++j){
                    if(dp[i][Math.abs(j-sub.get(i))])dp[i+1][j]=true;
                    if(j+sub.get(i)<N && dp[i][j+sub.get(i)])dp[i+1][j]=true;
                }
            }
            int s=0;
            for(int i=0;i<N;++i)if(dp[N][i]){
                s=i;break;
            }
            int left=0,right=N;
            if(s<amari){
                left=N/2;right=N-left;
            }else{
                s-=amari;
                while(right-left>s){
                    left++;--right;
                }
            }
            System.out.println((left*(left-1))/2 + (right*(right-1)/2));
        }
    }
}

Measured memory_bytes: 112424
#include<bits/stdc++.h>
int a[110];
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int l=0;l<n;l++){
        sum+=a[l];
    }
    cout<<(x-sum)/a[0]+n<<endl;
}

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

using namespace std;

int main()
{
	string s[3];
	for (int i = 0; i < 3; i++) {
		cin >> s[i];
		printf("%c", s[i][0] - 'a' + 'A');
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s,t;
	cin>>s;
	cin>>t;
	int ans=0;
	for(int i=0;i<3;i++)
	{
		if(s[i]==t[i])
		ans++;
	}
	cout<<ans<<endl;
	return 0;
 } 

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

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

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

    rep(i,s.size()){
        if(i%2==0){
            if(s[i]=='L'){
                puts("No");
                return 0;
            }
        }else{
            if(s[i]=='R'){
                puts("No");
                return 0;
            }
        }
    }

    puts("Yes");
    
    return 0;
}

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

int a, b, c;

int main() {
	scanf("%d %d %d", &a, &b, &c);
	long long ans = (1LL << 60);
	if (a != 1) {
		ans = std::min(ans, 1LL * (a % 2) * b * c);
	}
	if (b != 1) {
		ans = std::min(ans, 1LL * (b % 2) * a * c);
	}
	if (c != 1) {
		ans = std::min(ans, 1LL * (c % 2) * a * b);
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include<climits>
#include<cmath>
#include<cstdio>
#include<deque>
#include<map>
#include<set>
#include<vector>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<numeric>
#include<string>
#include<tuple>
using namespace std;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define BEGIN ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define END return EXIT_SUCCESS
#define rep(I,N) for(auto I=0;I<(N);++I)
#define up(I,A,B) for(auto I=(A);I<=(B);++I)
#define dw(I,A,B) for(auto I=(A);I>=(B);--I)
#define all(C) (C).begin(),(C).end()
#define rall(C) (C).rbegin(),(C).rend()
#define ft first
#define sd second
#define mp make_pair
#define mt make_tuple
#define pf push_front
#define pb push_back
#define pt pop_front
#define pk pop_back
#define lb lower_bound
#define ub upper_bound
#define rs resize
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<class T>inline void                                      in(T &p){cin>>p;}
template<class T1,class T2>inline void                            in(T1 &p1,T2 &p2){cin>>p1>>p2;}
template<class T1,class T2,class T3>inline void                   in(T1 &p1,T2 &p2,T3 &p3){cin>>p1>>p2>>p3;}
template<class T1,class T2,class T3,class T4>inline void          in(T1 &p1,T2 &p2,T3 &p3,T4 &p4){cin>>p1>>p2>>p3>>p4;}
template<class T1,class T2,class T3,class T4,class T5>inline void in(T1 &p1,T2 &p2,T3 &p3,T4 &p4,T5 &p5){cin>>p1>>p2>>p3>>p4>>p5;}
template<class T>inline void                             out(T p){cout<<p<<endl;}
template<class T1,class T2>inline void                   out(T1 p1,T2 p2){cout<<p1<<" "<<p2<<endl;}
template<class T1,class T2,class T3>inline void          out(T1 p1,T2 p2,T3 p3){cout<<p1<<" "<<p2<<" "<<p3<<endl;}
template<class T1,class T2,class T3,class T4>inline void out(T1 p1,T2 p2,T3 p3,T4 p4){cout<<p1<<" "<<p2<<" "<<p3<<" "<<p4<<endl;}

inline void solve(void){
  string S;
  in(S);
  map<char,long>m;
  long N=S.size();
  rep(i,N)m[S[i]]++;
  if(abs(m['a']-m['b'])<=1 && abs(m['a']-m['c'])<=1 && abs(m['b']-m['c'])<=1)out("YES");
  else out("NO");
}
int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 512
N, D = map(int, input().split())

X = []
for i in range(N):
    X.append(list(map(int, input().split())))

dis = []
ans = 0
for i in range(N):
    for j in range(i+1, N):
        d = 0
        for k in range(D):
            d += (X[i][k] - X[j][k]) ** 2

        d = d ** (1/2)
        if (d == int(d)):
            ans += 1

print(ans)

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

using ll=long long;
const ll MOD=1000000007;

int gcd(int x,int y){
  if(x==1||y==1)
    return 1;
  else if(x%y==0){
    return y;
  }
  else
    return gcd(y,x%y);
}

int main() {
  int k;
  cin >> k;
  ll ans =0;
  for(int i=1;i<=k;i++){
    for(int j=1;j<=k;j++){
      for(int l=1;l<=k;l++){
        ans +=gcd(gcd(j,i),l);
      }
    }
  }
  cout << ans << endl;
}


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

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

    int size = S.size();

    if(size <= K){
        cout << S << endl;
    }else{
        cout << S.erase(K) << "..." << endl;
    }
}

Measured memory_bytes: 3568
/*It’s going to be hard,
but hard does not mean impossible.*/

#include <bits/stdc++.h>

// definitions
#define __Imperial_Lord__ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define _cps CLOCKS_PER_SEC
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
#define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
#define acc(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define high(x) __builtin_popcountll(x)
#define pb push_back
#define pf push_front
#define p0(a) cout << a << " "
#define p1(a) cout << a << "\n"
#define p2(a, b) cout << a << " " << b << "\n"
#define p3(a, b, c) cout << a << " " << b << " " << c <<"\n"
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d <<"\n"
#define exec cerr<<"Time taken : "<<(ld)(clock())/_cps<<"s"<<"\n"
#define mod1 998244353
#define mod 1000000007
#define pi 3.1415926535897932384

using namespace std;

// alias name for common data types
typedef vector<long long> vl;
typedef vector<long double> vld;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector< pair<long long, long long> > vp;
typedef vector<tuple<long long , long long , long long> > vtup;
typedef deque <long long> dql;
typedef deque <char> dqc;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

const ll INF = LONG_LONG_MAX;

template <class ...Args>
istream &read_args(Args &...args) {return (cin >> ... >> args);}
#define read(...)   __VA_ARGS__; read_args(__VA_ARGS__)

// cin and cout overloaded for vectors
template<typename T>    istream& operator>>(istream& is,  vector<T>& v)
{
    for (auto& i : v)
        is >> i;
    return is;
}
template<typename T>    ostream& operator<<(ostream& os,  vector<T>& v)
{
    for (auto& i : v)
        os << i << ' ';
    return os;
}



// code beigns in main
int main()
{
    __Imperial_Lord__
    ll t = 1;
    // cin >> t;

    while(t--)
    {
        ll read(n,d);
        ll cnt=0;
        rep(i,0,n)
        {
            ll read(a,b);
            if(a*a+b*b<=d*d) cnt++;
        }

        p1(cnt);
    }
    exec;
}

Measured memory_bytes: 3804
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

int sum (int x, int a, int b)
{
    ll r=0,y=x;
    while (y)
    {
        r+=y%10;
        y/=10;
    }
    if (a<=r && r<=b)
        return x;
    else
        return 0;
}

main()
{
    fast;
    int n,a,b,i;
    cin>>n>>a>>b;
    ll ans=0;
    for (i=1;i<=n;i++)
        ans+=sum(i,a,b);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<pair<long long,int>>e;
	map<long long,int>ret;
	for(int i=0;i<n;i++)
	{
		long long x;
		cin>>x;
		ret[x]=i;
		e.push_back({x,i});
	}
	sort(e.rbegin(),e.rend());
	long long x=e.back().first;
	vector<int>sz(n,1);
	vector<long long>dp(n,0);
	vector<pair<int,int>>ans;
	for(auto c:e)
	{
		if(c.first!=x)
		{
			if(sz[c.second]*2>=n)
			{
				cout<<-1<<endl;
				return 0;
			}
			long long need=c.first-(n-2*sz[c.second]);
			if(!ret.count(need))
			{
				cout<<-1<<endl;
				return 0;
			}
			int par=ret[need];
			dp[par]+=dp[c.second]+sz[c.second];
			sz[par]+=sz[c.second];
			ans.push_back({c.second+1,par+1}); 
		}
	}
	if(dp[e.back().second]!=x)
	{
		cout<<-1<<endl;
		return 0;
	}
	for(auto c:ans)
		cout<<c.first<<' '<<c.second<<endl;
	return 0;
}


Measured memory_bytes: 12300
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;



int main()
{
    int h, n, sum = 0, t;
    cin >> h >> n;
    while (n--)
    {
        cin >> t;
        sum += t;
    }

    if (sum >= h)
        cout << "Yes";

    else
        cout << "No";

    return 0;
}

Measured memory_bytes: 256
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {
	int x,y;
	cin>>x>>y;
	int ans = 0;
	if(x==1)ans+=300000;
	else if(x==2)ans+=200000;
	else if(x==3)ans+=100000;
	if(y==1)ans+=300000;
	else if(y==2)ans+=200000;
	else if(y==3)ans+=100000;
	if(x==1&&y==1)ans+=400000;
	cout<<ans;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3644
def main():
    S = input()
    len_s = len(S)
    flag = False
    if S == S[::-1]:
        if S[0:len_s // 2] == S[len_s // 2 - 1::-1]:
            if S[len_s // 2 + 1:] == S[-1:len_s // 2:-1]:
                flag = True
    # print(S[0:len_s // 2], S[len_s // 2 - 1::-1])
    # print(S[len_s // 2 + 1:], S[-1:len_s // 2:-1])
    if flag:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const ll m = 998244353;

ll pow_mod(ll x, ll a) {
  ll an = 1, nw = x, id = 1;
  while(a > 0) {
    if (id & a) an = an * nw % m, a -= id;
    nw = nw * nw % m;
    id <<= 1;
  }
  return an;
}

int main() {
  int n; cin >> n; ll a[n];
  for(ll i=0; i<n; i++) cin >> a[i];
  if (a[0] != 0) return 0 * puts("0");
  sort(a, a+n);
  
  int n0 = distance(lower_bound(a, a+n, 0), upper_bound(a, a+n, 0));
  //cout << n0 << endl;
  if (n0 != 1) return 0 * puts("0");

  ll an = 1, bf = 1;

  for(int i=1; i<n && a[n-1] >= i; i++) {
    ll nm = distance(lower_bound(a, a+n, i), upper_bound(a, a+n, i));
    //cout << nm << endl;
    if (nm == 0) return 0 * puts("0");
    an = an * pow_mod(bf, nm) % m; bf = nm;
  }
  cout << an << endl;
}

Measured memory_bytes: 1024
## coding: UTF-8
X, K, D= map(int,input().split())


saidai = X + K * D
saisyou = X - K * D

if(saidai == 0):
    ans = 0
elif(saisyou == 0):
    ans = 0
else:
    if(saidai > 0 and saisyou > 0):
        ans = abs(saisyou)
    elif(saidai < 0 and saisyou < 0):
        ans = abs(saidai)
    else:
        L = X // D
        P = X - L * D
        #print(L)
        if(L % 2 == K % 2):
            l = [abs(P-6*D), abs(P - 4*D), abs(P-2*D), abs(P), abs(P+2*D), abs(P+4*D), abs(P+6*D)]
        else:
            l = [abs(P-5*D), abs(P - 3*D), abs(P-D), abs(P+D), abs(P+3*D), abs(P+5*D)]
        ans = min(l)
            
        '''
        a = X - L * D
        b = a + D
        c = b + D
        d = a - D
        e = d - D
        l = [abs(a), abs(b), abs(c), abs(d), abs(e)]
        ans = min(l)
        '''
        #ans = -1

print(ans)


Measured memory_bytes: 61876
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   1000000007
#define PI 2*acos(0.0)
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define N 200005
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};


ll bigmod(ll x, ll p)
{
    ll res = 1;
    while(p)
    {
        if(p&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        p >>= 1;
    }
    return res;
}



//=============================================ASIFAZAD==============================================//

int32_t main()
{
    io;
    int n, a, b;
    cin>>n>>a>>b;

    //dbg(n);

    vi fac(N);
    fac[0] = 1;
    for(int i = 1; i< N; i++)
        fac[i] = 1LL*fac[i-1]*i %mod;

    ll numa = 1, numb = 1;

    for(int i = n; i > n - a; i--)
        numa = (numa * i)%mod;

    for(int i = n; i>n-b; i--)
        numb = (numb * i)%mod;

    //dbg(fac[N-1]);

    ll c = (bigmod(2, n) - 1 + mod)%mod;

    //dbg(c);

    ll d = (numa* bigmod(fac[a], mod - 2))%mod;

    //dbg(d);

    d = ((numb * bigmod(fac[b], mod - 2))%mod + d)%mod;
    //dbg(d);

    cout<<(c - d + mod)%mod;
    return 0;
}

Measured memory_bytes: 4064
//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
double readdb()
{
    R double x=0,y=0.1,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(x=ch-'0';(ch=getc())>='0'&&ch<='9';x=x*10+ch-'0');
    for(ch=='.'&&(ch=getc());ch>='0'&&ch<='9';x+=(ch-'0')*y,y*=0.1,ch=getc());
    return x*f;
}
const int N=1e5+5;
struct node{
    double x,y;
    inline node(){} inline node(R double xx,R double yy):x(xx),y(yy){} inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
    inline double operator *(const node &b)const{return x*b.y-y*b.x;}
    inline node operator *(const double &b)const{return node(x*b,y*b);}
    inline double operator ^(const node &b)const{return x*b.x+y*b.y;}
    inline double len2(){return x*x+y*y;}
    inline node rot(){return node(-y,x);}
}p[N],o;
struct Line{
    node p,v;
    inline Line(){}
    inline Line(R node pp,R node vv):p(pp),v(vv){}
    friend node cross(const Line &a,const Line &b){return a.p+a.v*(b.v*(b.p-a.p)/(b.v*a.v));}
};
node circle(const node &a,const node &b,const node &c){
    return cross(Line((a+b)*0.5,(b-a).rot()),Line((a+c)*0.5,(c-a).rot()));
}
int n;double r;
int main(){
//  freopen("testdata.in","r",stdin);
    cin>>n;
    fp(i,1,n)cin>>p[i].x>>p[i].y;
    random_shuffle(p+1,p+1+n);
    r=0,o=node(0,0);
    fp(i,1,n)if((p[i]-o).len2()>r){
        o=p[i],r=0;
        fp(j,1,i-1)if((p[j]-o).len2()>r){
            o=(p[i]+p[j])*0.5,r=(p[j]-o).len2();
            fp(k,1,j-1)if((p[k]-o).len2()>r)
                o=circle(p[i],p[j],p[k]),r=(p[k]-o).len2();
        }
    }
    printf("%.10lf\n",sqrt(r));
    return 0;
}


Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
    .map(|e| e.parse().ok().unwrap()).collect()
}

pub fn main() {
    loop {
        let v: Vec<i32> = read_vec();
        let (h,w) = (v[0],v[1]);
        if h==0 && w==0 {
            break;
        }
        for _ in 0..h {
            for _ in 0..w {
                print!("#");
            }
            println!();
        }
        println!();
    }
}


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

int q;
long long a, b;

int main() {
	//freopen(".inp", "r", stdin); freopen(".out", "w", stdout);
	cin >> q;
	while (q--) {
		cin >> a >> b;
		if (a > b) swap(a, b);
		long long sq = sqrtl(a * b);
		if (a == b) {
			printf("%lld\n", 2 * a - 2);
			continue;
		}
		if (sq * sq == a * b) sq--;
		if (sq * (sq + 1) >= a * b) {
			printf("%lld\n", 2 * sq - 2);
		} else {
			printf("%lld\n", 2 * sq - 1);
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int maxn=2000000+10;
int n=0;
char cmd[20];
int a[maxn];
int dd;
void max_heapify(int i)
{
    int left=2*i;
    int right=2*i+1;
    int _max;
    if(left<=n&&a[left]>a[i]) _max=left;
    else _max=i;
    if(right<=n&&a[right]>a[_max]) _max=right;
    if(i!=_max)
    {
        swap(a[i],a[_max]);
        max_heapify(_max);
    }

}
void insert(int i)
{
    int p=n++;
    a[p]=i;
    while(p>=0&&a[p/2]<a[p])
    {
        swap(a[p/2],a[p]);
        p=p/2;
    }
}
int extract()
{
    int _max=a[0];
    a[0]=a[n-1];
    n--;
    max_heapify(0);
    return _max;

}
int main()
{
//    freopen("in.txt","r",stdin);
    bool bEnd=false;;
    while(~scanf("%s",cmd)&&!bEnd)
    {
        switch(cmd[2])
        {
        case 's':
        {
            scanf("%d",&dd);
            insert(dd);
            break;
        }
        case 't':
        {
            printf("%d\n",extract());
            break;
        }
        case 'd':
        {
            bEnd=true;
            break;
        }

        }
    }


    return 0;
}

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

const ll INF = 1LL << 60;

const string YES = "Yes";

struct edge { ll cost, to; };
vector<edge> g[200100];
ll dist[100100];
vector<ll> prever;
ll N;

void dijkstra(ll s) {
    dist[s] = 0;
    prever = vector<ll>(N, -1);

    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
 
    while (!que.empty()) {
        P p = que.top(); que.pop();
        ll v = p.second;
 
        if (p.first > dist[v]) continue;
        // 次の頂点へ潜る
        for (int i = 0; i < g[v].size(); i++) {
            edge e = g[v][i];
            if (e.cost + dist[v] < dist[e.to]) {
                dist[e.to] = e.cost + dist[v];
                prever[e.to] = v;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
}

int main() {
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);

    vector<ll> tmp_graph[N];

    rep(i, N) dist[i] = INF;
    rep(i, M) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back((edge){1, b});
        g[b].push_back((edge){1, a});

        tmp_graph[a].push_back(b);
        tmp_graph[b].push_back(a);
    }

    dijkstra(0);

    // cout << "Yes" << endl;
    vector<P> v;
    for (int i = 1; i < N; i++) {
        v.push_back(P(dist[i], i));
        // cout << dist[i] << endl;
    }
    sort(v.begin(), v.end());


    cout << "Yes" << endl;
    for (int i = 1; i < N; i++) {
        cout << prever[i] + 1 << endl;
    }
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int a, b, t;
	cin>>a>>b>>t;
	cout<<b*(t/a)<<'\n';
	return 0;
}


Measured memory_bytes: 256
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
#define INF 1e18
#define MAX_N 300000
vector<ll> G[MAX_N];
vector<ll> ans(MAX_N),a(MAX_N);
void dfs(ll v,ll pre,vector<ll>& dp){
  ll pre_v;
  auto itr=lower_bound(dp.begin(),dp.end(),a[v]);
  pre_v = *itr;
  *itr = a[v];
  auto inf_idx = lower_bound(dp.begin(),dp.end(),INF);
  ans[v] = distance(dp.begin(),inf_idx);
  for(auto nv:G[v]){
    if(nv!=pre){
      dfs(nv,v,dp);
    }
  }
  *itr = pre_v;
}
signed main(){
  init_io();
  ll n;
  cin >> n;
  vector<ll> dp(n+1,INF);
  vector<ll> v(n-1),u(n-1);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n-1;i++){
    cin >> v[i] >> u[i];
    u[i]--;
    v[i]--;
    G[v[i]].push_back(u[i]);
    G[u[i]].push_back(v[i]);
  }
  dfs(0,-1,dp);
  for(int i=0;i<n;i++){
    cout << ans[i]<<endl;
  }
}


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



int check(string s, string t){
  if(s.size() >= t.size()) return 0;
  for(int i=0; i<s.size(); i++){
    if(s[i]==t[i]) cnt++;
    if(cnt == s.size()) return 1;
  }
  return 0;
}


int main() {
  string s, t; cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end(), greater<char>());

  if(check(s, t)){
    cout << "Yes" << endl;
    return 0;
  }
  else{
    for(int i=0; i<min(s.size(),t.size()); i++){
      if(s[i]==t[i]) continue;
      else if(s[i]<t[i]){
        cout << "Yes" << endl;
        return 0;
      }
      else{
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


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

int main()
{
  int64_t h, w;
  cin >> h >> w;
  int64_t ans = 0;
  if (h == 1 or w == 1)
  {
    cout << "1\n";
    return 0;
  }
  if (h % 2 == 0 and w % 2 == 0)
    ans = w * h / 2;
  else if (h % 2 == 0 and w % 2 != 0)
    ans = (w / 2 + 1) * h / 2 + (w / 2) * h / 2;
  else if (h % 2 != 0 and w % 2 == 0){
    ans = (w / 2) * ((h / 2) + 1) + (w / 2) * (h / 2);
  }
  else
    ans = (w / 2 + 1) * (h / 2 + 1) + (w / 2) * (h / 2);

  cout << ans << "\n";
}


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

using namespace std;

using ll = long long;

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

    int N, T, c, t, cost = -1;
    cin >> N >> T;
    for (int i = 0; i < N; ++i) {
        cin >> c >> t;
        if (t <= T) {
            if (cost == -1 || c < cost)
                cost  = c;
        }
    }

    if (cost == -1) cout << "TLE\n";
    else cout << cost << endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())
t = [0]
x = [0]
y = [0]
for i in range(n):
  ti, xi, yi = map(int, input().split())
  t.append(ti)
  x.append(xi)
  y.append(yi)
  
ok = True
for i in range(n):
  ti = t[i+1] - t[i]
  if ((ti - (abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]))) < 0
      or (ti - (abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]))) % 2 != 0):
    ok = False
    break
if ok:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 11824
def main():
    N, M, Q = map(int, input().split())
    t = [[0] * N for _ in range(N)]
    for _ in range(M):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        t[l][r] += 1
    s = [[0] * N for _ in range(N)]
    s[0][0] = t[0][0]
    for i in range(1, N):
        s[0][i] = s[0][i-1] + t[0][i]
    for i in range(1, N):
        s[i][0] = s[i-1][0] + t[i][0]
    for i in range(1, N):
        for j in range(1, N):
            s[i][j] = s[i-1][j] + s[i][j-1] + t[i][j] - s[i-1][j-1]
    for _ in range(Q):
        p, q = map(int, input().split())
        if p == 1:
            print(s[q-1][q-1])
            continue
        p -= 1
        q -= 1
        print(s[q][q] - s[q][p-1] - s[p-1][q] + s[p-1][p-1])
main()


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

int main(){
  int n,m; cin >> n >> m;
  bool ad=1;
  vector<int> ans(n,0),s(m),c(m);
  for(int i=0;i<m;i++){
    cin >> s[i] >> c[i];
  }
  for(int i=0;i<m;i++){
    for(int j=i+1;j<m;j++){
      if((s[i]==s[j]) && (c[i]!=c[j]))ad=0;
    }
  }

  for(int i=0;i<m;i++){
    ans[s[i]-1]=c[i];
    if(s[i]==1 && c[i]==0 && n!=1)ad=0;
  }

  if(ad){
    if(ans[0]==0 && n!=1){
      cout << 1;
      for(int i=1;i<n;i++){
        cout << ans[i];
      }
    }
    else{
      for(int i=0;i<n;i++){
        cout << ans[i];
      }
    }
  }
  else{
    cout << -1 << endl;
  }

}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }

typedef long long ll;

const int MOD = 1e9+7;

bool is_integer( double x ){
    return std::floor(x)==x;
}

int facctorialMethod(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

long long combination(int n, int k){
    static const int maxi = 1e7+1;
    static vector<ll> fac(maxi,0),finv(maxi,0),inv(maxi,0);
    static const int mod = 1e9+7;
    // キャッシュされてない場合COMinit()と同様のことをする。
    if (fac[0]==0) {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < maxi; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod%i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

int main() {
    int X,Y;
    cin >> X >> Y;
    if ((X+Y)%3!=0){
        cout << 0 << endl;
        exit(0);
    }
    auto m=(2*X-Y)/3.0;
    auto n=(2*Y-X)/3.0;
    if (!is_integer(m) || !is_integer(n)) {
        cout << 0 << endl;
        exit(0);
    }
    if (n<0 || m<0) {
        cout << 0 << endl;
        exit(0);
    }


    cout << combination(n+m,min(n,m)) << endl;




    return 0;
}


Measured memory_bytes: 234624
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define rrep(i, a, b) for (int i = (a); i < (b); ++i)
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
#define fi first
#define se second

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using tl = tuple<ll, ll, ll>;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) {if (a > b) { a = b; return true; } return false; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n, d; cin>>n>>d;
    ll cnt = 0;
    rep(i, n) {
        ll x, y; cin>>x>>y;
        if (x * x + y * y <= d * d) cnt++;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
char mp[105][105];
int flag[105][105];

int main()
{
    memset(flag,0,sizeof(flag));
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>mp[i][j];
    for(int i=1; i<=n; i++)
        for(int j=2; j<=m; j++)
        {
            if(mp[i][j] == '#')
            {
                if(mp[i][j-1] == '#')
                {
                    flag[i][j] = 1;
                    flag[i][j-1] = 1;
                }
            }
        }
    for(int j=1; j<=m; j++)
        for(int i=2; i<=n; i++)
        {
            if(mp[i][j] =='#')
                if(mp[i-1][j] == '#')
                {
                    flag[i][j] = 1;
                    flag[i-1][j] = 1;
                }
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {   if(mp[i][j] == '#')
            if(flag[i][j] == 0)
            {
                cout<<"No"<<endl;
                return 0;
            }
        }
    cout<<"Yes"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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;
}

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

//----------------------------------------------------------------

int main(){
ll a,b,c,d;
cin>>a>>b>>c>>d;
cout<<max(a*b,c*d)<<endl;
}










Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    string s;
    ll k;
    cin >> s >> k;
    // k文字目までが全て1 -> 1
    // それ以外 -> それ以外のはじめの文字？
    char first_not_one = '0';
    int first_not_one_cur = -1;
    FOR(i, 1, s.size()) {
        if (s[i-1] != '1' && first_not_one == '0') {
            first_not_one = s[i-1];
            first_not_one_cur = i;
        }
    }
    if (first_not_one != '0' && first_not_one_cur <= k) {
        cout << first_not_one << endl;
    } else {
        cout << '1' << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#----------------
# coding: utf-8
# Created:     20/08/2014
# Python 3+
#-----------------
import sys
#ff = open("test.txt", "r")
ff = sys.stdin

while (True) :

    n = int(ff.readline())
    if n == 0 : break

    p1 = 0
    p2 = 0

    for x in range(0, n):
        arr = list( map(int, ff.readline().split()) )
        sum = arr[0] + arr[1]

        if arr[0] == arr[1] :
            p1 += arr[0]
            p2 += arr[1]
        elif arr[0] > arr[1] :
            p1 += sum
        else :
            p2 += sum

    print("{0} {1}".format(p1, p2))

pass

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

#define ll long long

using namespace std;

int gcd(int a, int b) {
    return b? gcd(b, a % b) : a;
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> a(n);
    int g = 0, mx = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        g = gcd(g, a[i]);
        mx = max(mx, a[i]);
    }
    if (k % g != 0 || mx < k)
        printf("IMPOSSIBLE");
    else
        printf("POSSIBLE");


    return 0;
}

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

int main()
{
    int iNumA = 0;
    int iNumB = 0;
    
    cin >> iNumA >> iNumB;
    
    if (iNumA > iNumB)
    {
        cout << "a > b" << endl;
    }
    else if (iNumA < iNumB)
    {
        cout << "a < b" << endl;
    }
    else
    {
        cout << "a == b" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3100
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const double PI = acos(-1);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

using mint = modint<MOD>;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M; cin >> N >> M;
    vector<int> S(N),T(M);
    rep(i,N) cin >> S[i];
    rep(i,M) cin >> T[i];

    vector<vector<mint>> dp(N+1, vector<mint>(M+1));
    rep(i,N+1) dp[i][0] = 1;
    rep(i,M+1) dp[0][i] = 1; 
    rep(i,N) {
        rep(j,M) {
            if (S[i] == T[j]) dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1];
            else dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j];
        }
    }

    cout << dp[N][M].a << endl;
}

Measured memory_bytes: 31616
# B
# 2020/03/09  0:11-
n = int(input())

def yakusu(x):
    l = []
    for i in range(1, x+1):
        if x%i == 0:
            l.append(i)
    return l

count = 0
for i in range(1, n+1):
    A = yakusu(i)
    if len(A) == 8 and i%2 == 1:
        count += 1
        
print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int> > X(N, vector<int>(D));
  rep(i, N) {
    rep(j, D) {
      cin >> X[i][j];
    }
  }
  int cnt = 0;
  rep(i, N) {
    REP(j, i+1, N) {
      ll tmp = 0LL;
      rep(d, D)
        tmp += pow((X[i][d] - X[j][d]), 2);
      if(tmp == pow(floor(sqrt(tmp)), 2))
        cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#ifdef __APPLE__
#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <random>
#else
#include <bits/stdc++.h>
#endif

using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define tc(t) for (int tc=1; tc<=t; tc++)
typedef vector<int> VI;
typedef vector<long long int> VLLI;
typedef vector<pair<int, int> > VPI;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll, ll> PLL;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll modInverse (ll a) {ll p = mod - 2; return powmod(a, p);}
// head

void dfs(int s, int p, int d, vector<vector<int>>& tree, vector<int>& color) {
    color[s] = d%2;
    for (auto x : tree[s]) {
        if (x == p)
            continue;
        dfs(x, s, d+1, tree, color);
    }
}

int main() {
    int n, u, v;
    cin >> n;
    vector<vector<int>> tree(n+1);
    vector<int> color(n+1);
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(1, -1, 0, tree, color);
    int b = 0, r = 0;
    for (int i = 1; i <= n; i++)
        b += color[i] == 0, r += color[i] == 1;

    if (b > r) {
        for (auto &x : color)
            if (x == 1)
                x = 0;
            else
                x = 1;
        swap(b, r);
    }

    vector<int> ans(n+1, -1);

    if (b <= n/3) {
        int k = 3, k1 = 1, k2 = 2;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                ans[i] = k;
                k += 3;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (ans[i] == -1) {
                if (k <= n) {
                    ans[i] = k;
                    k += 3;
                } else if (k1 <= n) {
                    ans[i] = k1;
                    k1 += 3;
                } else {
                    ans[i] = k2;
                    k2 += 3;
                }
            }
        }
    } else {
        int k = 3, k1 = 1, k2 = 2;
        for (int i = 1; i <= n; i++) {
            if (color[i] == 0) {
                if (k1 <= n) {
                    ans[i] = k1;
                    k1 += 3;
                } else {
                    ans[i] = k;
                    k += 3;
                }
            } else {
                if (k2 <= n) {
                    ans[i] = k2;
                    k2 += 3;
                } else {
                    ans[i] = k;
                    k += 3;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << "\n";
}



Measured memory_bytes: 22656
using System;
using System.Collections.Generic;
using System.Linq;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().Split();
            var n = int.Parse(s[0]);
            var k = int.Parse(s[1]);

            var l = new List<int>();
            while(n > 0){
                l.Add(n % k);
                n /= k;
            }

            Console.WriteLine(l.Count());
        }
    }
}


Measured memory_bytes: 13268
#include <stdio.h>

int main() {
	int N;
	scanf("%d",&N);
	char S[N];
	scanf("%s",S);
	int cnt = 0,min;
	int W[N];
	for (int i = 0; i < N; i++) {
		if (S[i] == '.') cnt++;
		W[i] = cnt;
	}
	min = cnt;
	int change = 0;
	for (int i = 0; i < N; i++) {
		change = ((i + 1) - W[i]) + (cnt - W[i]);
		if (change < min) min = change;
		change = 0;
	}
	printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
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 int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n;
    cin >> n;
    vector<int> A(n + 1), C(n - 1);
    A[n] = -1;
    int ans = 0;
    rep(i, n) cin >> A[i], A[i]--;
    rep(i, n) {
        int b;
        cin >> b;
        ans += b;
    }
    rep(i, n - 1) cin >> C[i];
    rep(i, n - 1) {
        if (A[i + 1] - A[i] == 1) ans += C[A[i]];
    }
    cout << ans << endl;
}

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



Measured memory_bytes: 3612