akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

inline int suit_to_id(char c) {
  switch (c) {
    case 'S':
      return 0;
    case 'H':
      return 13;
    case 'C':
      return 26;
    case 'D':
      return 39;
  }
  // should not reach here
  return 0;
}

inline char id_to_suit(int i) {
  switch (i) {
    case 0 ... 12:
      return 'S';
    case 13 ... 25:
      return 'H';
    case 26 ... 38:
      return 'C';
    case 39 ... 51:
      return 'D';
  }
  // should not reach here
  return 'S';
}

int main() {
  // 0..12 => S1..S13
  // 13..25 => H1..H13
  // 26..38 => C1..C13
  // 39..51 => D1..D13
  char bits[8] = {0};

  int n;
  cin >> n;

  char c;
  int x;
  for (int i = 0; i < n; ++i) {
    cin >> c >> x;
    const int offset = suit_to_id(c);
    const int bitpos = offset + x - 1;
    bits[bitpos / 8] |= (1 << (bitpos % 8));
  }

  for (int i = 0; i < 52; ++i) {
    int y = 1 << (i % 8);
    if (!(bits[i/8] & y)) {
      const char s = id_to_suit(i);
      const int v = i - suit_to_id(s) + 1;
      cout << s << " " << v << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3088
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
//const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main () {
    int n, s; cin >> n >> s;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<vector<mint>> dp(n+1, vector<mint> (s+1));
    dp[0][0] = 1;
    rep(i, n) {
        rep(j, s+1) {
            dp[i+1][j] += dp[i][j]*2;
            if (j+a[i] <= s) {
                dp[i+1][j+a[i]] += dp[i][j];
            } 
        }
    }
    cout << dp[n][s] << endl;

    return 0;
}

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

int main()
{
	vector<long long> dp(2020, 0);
	string s;
	cin >> s;
	int len = s.length();
	long long cnt = 0;
	for(int i = 0; i < len; i++) {
		vector<long long> new_dp(2020, 0);
		dp[0] += 1;
		for(int j = 0; j < 2019; j++) {
			new_dp[((j*10)+s[i]-'0')%2019] += dp[j];
		}
		dp = new_dp;
		cnt += dp[0];
	}
	printf("%lld\n", cnt);
}

Measured memory_bytes: 3772
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
#include <sys/time.h>
#include <fstream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define REP(i,n)  FOR(i,0,n)
#define each(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
#define sz(s) (int)((s).size())


#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(x,y) make_pair((x),(y))

double pi=3.14159265358979323846;

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
	os << "[ ";
	REP(i,z.size())os << z[i] << ", " ;
	return ( os << "]" << endl);
}

template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
	os << "set( ";
	EACH(p,z)os << (*p) << ", " ;
	return ( os << ")" << endl);
}

template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
	os << "{ ";
	EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;
	return ( os << "}" << endl);
}

template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
	return ( os << "(" << z.first << ", " << z.second << ",)" );
}

double get_time(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec*1e-6;
}

typedef unsigned int uint32_t;
struct RND{
	uint32_t x;
	uint32_t y;
	uint32_t z;
	uint32_t w;
	RND(){
		x=123456789;
		y=362436069;
		z=521288629;
		w=88675123;
	}
	void init(int seed){
		x=123456789;
		y=362436069;
		z=521288629;
		w=seed+100;
		REP(i,10)get();
	}
	uint32_t get(){
		uint32_t t;
		t=x^(x<<11);
		x=y;y=z;z=w;
		w=(w^(w>>19))^(t^(t>>8));
		return w;
	}
};
RND rnd;

void _main(istream &inp){
	int x[3];
	rep(i,3){
		inp >> x[i];
	}
	sort(x,x+3);
	cout <<  (2*x[2]-x[0]-x[1])/2 + (2*x[2]-x[0]-x[1])%2*2 << endl;

}

int main(){
	if(0){
		ifstream ifs("test.txt");
		_main(ifs);
	}
	else{
		_main(cin);
	}
	return 0;
}


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

int main() {

    ll h, n; cin >> h >> n;

    for (ll i = 0; i < n; ++i) {
        ll a; cin >> a;

        h -= a;
    }

    if (h <= 0) {
        puts("Yes");
    } else {
        puts("No");
    }
}

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

int main() {
  int n; cin >> n;
  string S[n]; int a[n][26]; rep(i,0,n) cin >> S[i];
  rep(i,0,n) rep(j,0,26) a[i][j] = 0;
  rep(i,0,n) {
    int size = S[i].size();
    rep(j,0,size) {
      int b = (int)S[i][j] - 'a';
      a[i][b]++;
    }
  }
  
  rep(i,0,26) {
    int ans =a[0][i];
    rep(j,0,n) {
      ans = min(ans,a[j][i]);
    }
    rep(k,0,ans) {
      if (ans != 0) {
        char c = (char)(i + 'a'); cout << c;
      }
    }
  }
  cout << endl; 
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

vector<vector<pair<int,int>>> to(1e5+7, vector<pair<int,int>>());
vector<int> ans;
int n;

void bfs(int x){
    queue<int> q;
    q.push(x);
    vector<int> dis(n,-1); dis[x] = 0;
    ans.push_back(x);
    while(!q.empty()){
        int num = q.front(); q.pop();
        for(int i = 0; i < to[num].size(); i++){
            int a=to[num][i].first, b=to[num][i].second;
            if(dis[a] != -1) continue;
            q.push(a);
            dis[a] = dis[num] + b;
            if(dis[a] % 2 == 0) ans.push_back(a);
        }
    }
}

int main(){
    cin >> n;
    rep(i,n-1){
        int a,b,c;
        cin >> a >> b >> c; a--; b--;
        to[a].push_back(make_pair(b,c));
        to[b].push_back(make_pair(a,c));
    }
    bfs(0);
    vector<int> list(n);
    for(int i: ans) list[i] = 1;
    rep(i,n) cout << list[i] << endl;
    return 0;
}

Measured memory_bytes: 7040
v[81],e[81];
B(p,s0,s1){
	int f[10]={0},i,j;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			if(f[v[p]])
				e[~f[v[p]]]=e[p]=1;
			else
				f[v[p]]=~p;
			p+=s0;
		}
		p+=s1-3*s0;
	}
}
main(i,f){
	scanf("%*d\n");
	for(f=i=0;~scanf("%d",v+i);){
		if(++i==81){
			memset(e,0,sizeof(e));
			for(i=0;i<9;i++){
				B(0+i*9,1+0*9,3+0*9);
				B(i+0*9,0+1*9,0+3*9);
				B(i%3*3+i/3*3*9,1+0*9,0+1*9);
			}
			if(f++)
				puts("");
			for(i=0;i<81;i++){
				printf("%c%d",e[i]?'*':' ',v[i]);
				if(i%9==8)
					puts("");
			}
			i=0;
		}
	}
}

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

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> L(M);
  vector<int> R(M);
  for(int i=0;i<M;i++){
    cin>>L.at(i)>>R.at(i);
  }
  sort(L.begin(),L.end());
  sort(R.begin(),R.end());
  int D=R.at(0)-L.at(M-1)+1;
  if(D>0){
    cout<<D<<endl;
  }
  if(D<=0){
    cout<<0<<endl;
  }
}

Measured memory_bytes: 1024
n,k=map(int,input().split())
h=list(map(int,input().split()))

dp=[0]
for i in range(1,n): # dp[i]の最小を決めていく。
    dpi=float('inf')
    for j in range(1,k+1):
        if i<j:
            break
        else:
            dpi=min(dp[i-j]+abs(h[i]-h[i-j]),dpi)
    dp.append(dpi)
print(dp[-1])

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

using namespace std;

using lint = long long;
using ldouble = long double;

const int INF = 1 << 30;

int N, M;
vector<int> A, B;
int dp[51][51][51][51][2][2];

// 1がスタックに積んでいるのが[l1, r1)
// 2がスタックに積んでいるのが[l2, r2)
// 今t+1のターン
// p : スタックが空になってからパスしたか
int rec(int l1, int l2, int r1, int r2, int t, int p) {
    int& ret = dp[l1][l2][r1][r2][t][p];
    if (ret > -INF) return ret;

    if (t == 0) {  // スコアを最大化
        // パスする場合
        if (p == 1) {
            ret = 0;  // ゲーム終了
        } else {
            int score = 0;
            for (int i = l1; i < r1; ++i) score += A[i];
            for (int j = l2; j < r2; ++j) score -= B[j];
            bool empty = (l1 == r1) && (l2 == r2);  // スタックが空か
            ret = score + rec(r1, r2, r1, r2, 1 - t, empty);
        }

        // カードを出す場合
        if (r1 < N) {
            if (A[r1] == 0) {
                // 「相手の」カードを全部消す
                ret = max(ret, rec(l1, r2, r1 + 1, r2, 1 - t, 0));
            } else {
                ret = max(ret, rec(l1, l2, r1 + 1, r2, 1 - t, 0));
            }
        }

    } else {  // スコアを最小化
        if (p == 1) {
            ret = 0;
        } else {
            int score = 0;
            for (int i = l1; i < r1; ++i) score += A[i];
            for (int j = l2; j < r2; ++j) score -= B[j];
            bool empty = (l1 == r1) && (l2 == r2);  // スタックが空か
            ret = score + rec(r1, r2, r1, r2, 1 - t, empty);
        }

        if (r2 < M) {
            if (B[r2] == 0) {
                ret = min(ret, rec(r1, l2, r1, r2 + 1, 1 - t, 0));
            } else {
                ret = min(ret, rec(l1, l2, r1, r2 + 1, 1 - t, 0));
            }
        }
    }
    return ret;
}

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

    A.resize(N);
    for (auto& a : A) {
        cin >> a;
        if (a < 0) a = 0;
        // 区間和を求めるために都合が悪いので、妨害カードを0にする
    }
    B.resize(M);
    for (auto& b : B) {
        cin >> b;
        if (b < 0) b = 0;
    }

    fill(dp[0][0][0][0][0], dp[51][0][0][0][0], -INF);
    cout << rec(0, 0, 0, 0, 0, 0) << endl;
    return 0;
}



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

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

   if (n >= 10) {
       cout << r << endl;
   } else {
       cout << r + (100 * (10 - n)) << endl;
   }
}

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

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

//bil[0][n] : A  bil[1][n] : B
int bil[4][128], num;

//pl = 0 : A  pl = 1: B  cnt : count of jump  floor : now floor
int climb(int pl, int cnt, int floor)
{
	if(floor >= num-1)
	{
		return cnt;
	}
	else if(bil[0][floor+1] == 2 && bil[0][floor+2] == 2 && bil[1][floor+1] == 2 && bil[1][floor+2] == 2)
	{
		return 10000;
	}
	else if(bil[pl][floor] == 2)
	{
		return climb(pl, cnt, floor-1);
	}
	else if(bil[pl][floor] == 1 && bil[pl][floor+1] == 1)
	{
		return climb(pl, cnt, floor+1);
	}
	else
	{
		if(pl == 0)
		{
				return climb(1, cnt+1, floor+2);
			/*
			else if(bil[1][floor+1] != 2)
			{
				return climb(1, cnt+1, floor+1);
			}
			else
			{
				return climb(1, cnt+1, floor);
			}
			*/
		}
		else
		{	
			return climb(0, cnt+1, floor+2);
			
			/*
			else if(bil[0][floor+1] != 2)
			{
				return climb(0, cnt+1, floor+1);
			}
			else
			{
				return climb(0, cnt+1, floor);
			}
			*/
		}
	}
}

int main()
{
	int ans;
	while(cin >> num ,num)
	{
		for(int i = 0; i < num; i++)
		{
			cin >> bil[0][i];
		}
		for(int i = 0; i < num; i++)
		{
			cin >> bil[1][i];
		}
		ans = min( climb(0, 0, 0) , climb(1, 0, 0) );
		if(ans == 10000)
		{
			cout << "NA" << endl;
		}
		else
		{
			cout << ans << endl;
		}
	}
}

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

using namespace std;


int main() {
    long long D = 30LL;
    while(true) {
        long long N; cin >> N;
        if(N == 0LL) return 0;
        vector<long long> free_days;
        for(long long i = 0LL; i < N; ++i) {
            long long m; cin >> m;
            long long day = 0LL;
            for(long long j = 0LL; j < m; ++j) {
                long long f; cin >> f;
                day |= (1LL << f);
            }
            free_days.emplace_back(day);
        }
        vector<vector<long long>> dp_maps;

        vector<long long> day_maps;
        for(long long n = 0LL; n < N; n++) {
            day_maps.emplace_back(1LL << n);
        }
        dp_maps.emplace_back(day_maps);

        for(long long d = 1; d <= D; ++d) {
            long long day_map = 0LL;
            for(long long n = 0LL; n < N; n++) {
                if(free_days[n] & (1LL << d)) {
                    day_map |= dp_maps[d-1][n];
                }
            }
            for(long long n = 0LL; n < N; n++) {
                if(free_days[n] & (1LL << d)) {
                    day_maps[n] = day_map;
                } else {
                    day_maps[n] = dp_maps[d-1][n];
                }
                if(day_maps[n] + 1LL == 1LL << N) {
                    cout << d << endl;
                    goto end;
                }
            }
            dp_maps.emplace_back(day_maps);
        }
        cout << -1 << endl;
        end: continue;
    }
    return 0;
}



Measured memory_bytes: 3180
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define nl '\n'
#define AC ios_base::sync_with_stdio(0); cin.tie(NULL);
using namespace std;
const int M = 1e9+7;
const int N = 2*1e5;

int main(){
    AC
    int n;
    cin>>n;
    ll res;
    cin>>res;
    if(res==0){
        cout<<0<<endl;
        return 0;
    }
    bool flag = false;
    for(int i=1; i<n; i++){
        ll x;
        cin>>x;
        if(x>0 && res>9223372036854775807/x){
            // overflow
            flag = true;
        }
        res*=x;
        if(x==0){
            cout<<0<<endl;
            return 0;
        }
        else if(res>1000000000000000000){
            flag = true;
        }
    }
    if(flag)
        cout<<-1<<endl;
    else
        cout<<res<<endl;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<ll> vl;
typedef std::vector<vl> vvl;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define RREP(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, n, m) for (ll i = n; i < m; i++)
#define RFOR(i, n, m) for (ll i = n - 1; i >= m; i--)

void output() { std::cout << std::endl; }
void input() {}

template <typename Head, typename... Tail>
void input(Head &&head, Tail &&... tail) {
  std::cin >> head;

  input(std::forward<Tail>(tail)...);
}
template <typename Head, typename... Tail>
void input(std::vector<Head> &head, Tail &&... tail) {
  std::for_each(head.begin(), head.end(), [](int &elem) { std::cin >> elem; });

  input(std::forward<Tail>(tail)...);
}
template <typename Head, typename... Tail>
void output(Head &&head, Tail &&... tail) {
  std::cout << head;
  if (sizeof...(tail))
    std::cout << " ";

  output(std::forward<Tail>(tail)...);
}
template <typename Head, typename... Tail>
void output(std::vector<Head> &head, Tail &&... tail) {
  bool first = true;
  for (int &elem : head) {
    if (!first)
      printf(" ");
    std::cout << elem;
    first = false;
  }
  if (sizeof...(tail))
    std::cout << " ";

  output(std::forward<Tail>(tail)...);
}

int main() {
  ll n;
  input(n);
  REP(i, n) {

    int gx, gy, p;
    input(gx, gy, p);
    vvi map(p, vi(4));
    REP(i, p) { input(map[i]); }

    vvi mat(gx + 1, vi(gy + 1, 0));

    for (vi &a : map) {
      int x = max(a[0], a[2]);
      int y = max(a[1], a[3]);
      if (a[0] != a[2]) {
        mat[x][y] += 1;
      } else if (a[1] != a[3]) {
        mat[x][y] += 2;
      }
    }

    vvi ans(gx + 1, vi(gy + 1, 0));
    ans[0][0] = 1;

    FOR(x, 1, gx + 1) if (mat[x][0] == 0) ans[x][0] = ans[x - 1][0];
    FOR(y, 1, gy + 1) if (mat[0][y] == 0) ans[0][y] = ans[0][y - 1];

    FOR(x, 1, gx + 1) FOR(y, 1, gy + 1) {
      switch (mat[x][y]) {
      case 0:
        ans[x][y] = ans[x][y - 1] + ans[x - 1][y];
        break;
      case 1:
        ans[x][y] = ans[x][y - 1];
        break;
      case 2:
        ans[x][y] = ans[x - 1][y];
        break;
      case 3:
        ans[x][y] = 0;
        break;
      }
    }
    if (ans[gx][gy] == 0)
      output("Miserable Hokusai!");
    else
      output(ans[gx][gy]);
  }

  return 0;
}


Measured memory_bytes: 3004
import math
n = int(input())
edge_s = (0.0, 0.0)
edge_e = (100.0, 0.0)

def print_tuple(tup):
    print("%.8f %.8f"%(tup[0],tup[1]))

def koch(start, end, n):
    if(n == 0):
        return
    s = ((2*start[0] + end[0]) / 3, (2*start[1] + end[1])/3)
    t = ((start[0] + 2*end[0]) / 3, (start[1] + 2*end[1])/3)
    u = (s[0] +  (t[0]-s[0])*math.cos(math.pi/3)-(t[1]-s[1])*math.sin(math.pi/3), s[1] + (t[0]-s[0]) * math.sin(math.pi/3) + (t[1]-s[1]) * math.cos(math.pi/3))
    n -= 1
    koch(start, s, n)
    print_tuple(s)
    koch(s, u, n)
    print_tuple(u)
    koch(u, t, n)
    print_tuple(t)
    koch(t, end, n)
print_tuple(edge_s)
koch(edge_s, edge_e, n)
print_tuple(edge_e)



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

int main() {
	long long n , k, x;
  cin >> n >> k;

  if(n < k ) x = n;
  else x = n % k;
  if(n != k)cout << min(x,k - x) << endl;
  else cout << 0 << endl;
}

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

int main(){
    string s, t;
    cin >> s >> t;
    if(s.size() + 1 == t.size()){
        bool ok = 1;
        for(int i = 0; i < s.size(); i ++)
            if(s[i] != t[i]) ok = 0;
        if(ok) cout << "Yes";
        else cout << "No";
    }
    else cout << "No";
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    const ll inf = LONG_LONG_MAX / 2 - 1;
    ll h, n;
    cin >> h >> n;
    vector<pair<ll, ll>> ab(n);
    rep(i, n) cin >> ab[i].first >> ab[i].second;
    vector<ll> dp(h + 1, inf);
    dp[0] = 0;
    rep(i, n) {
        ll a = ab[i].first, b = ab[i].second;
        rep(j, h) {
            ll idx = min(h, j + a);
            dp[idx] = min(dp[idx], dp[j] + b);
        }
    }
    cout << dp[h] << endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    int r=a+b+c;
    if(r>=22)
        printf("bust\n");
    else
        printf("win\n");
    return 0;
}


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

namespace AOJ.Volume0
{
    class Program0002
    {
        static void Main(string[] args)
        {
            const int N = 2;
            string input;
            Queue<int[]> queue = new Queue<int[]>();

            while ((input = Console.ReadLine()) != null)
            {
                string[] splitedInput = input.Split(' ');
                int[] pair = new int[N];

                for (int i = 0; i < N; i++)
                {
                    pair[i] = int.Parse(splitedInput[i]);
                }

                queue.Enqueue(pair);
            }

            foreach (var pair in queue)
            {
                Console.WriteLine("{0}", pair.Sum().ToString().Length);
            }
        }
    }
}

Measured memory_bytes: 6184
#include<iostream>
#include<cstdio>
using namespace std;
int a[99999999];
int main()
{
  int n,b=0;
  cin>>n; 
  for(int i=1;i<=n;i++)
  {
  	cin>>a[i];
  	while(a[i]%2==0)
  	{
  		a[i]=a[i]/2;
  		b++;
  		
  	}
  }
  cout<<b;
}

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

int calc(int N, int M) {
	int ans = 0, i;
	for (i = 1;i <= N;i *= M);
	for (i /= M;i >= 1;i /= M) {
		ans += N / i;
		N %= i;
	}
	return ans;
}
int main() {
	int N;
	cin >> N;
	int ans = N;
	for (int i = 0;i <= N;i ++) {
		ans = min(ans, calc(i, 6) + calc(N - i, 9));
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

別解法、2つに分けると解けるっていう方法だねー
*/

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

int main(){
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll res = 0;
    rep(i,n){
        res = res^a[i];
    }
    if(res==0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<stack>
#include<iterator>
#include<functional>
#include<string.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//namespace mp = boost::multiprecision;

int binarysearch(vector<int>a, int key) {
	int left = 0;
	int right = a.size();
	while (left < right) {
		int mid = (left + right) / 2;
		if (a[mid] == key) {
			return mid;
		}
		else if (key < a[mid]) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return -1;
	
}

int main() {
	int n, q;
	cin >> n;
	vector<int>s(n);
	int count = 0;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	cin >> q;

	for (int i = 0; i < q; i++) {
		int key; cin >> key;
		int ans=binarysearch(s, key);
		if (ans != -1) {
			count++;
		}
	}
	cout << count << endl;
}


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

typedef double elm;
typedef vector<elm> vec;
typedef vector<vec> mat;

const double eps = 1e-8;

bool equals(double a, double b) {
  return abs(a - b) < eps;
}

vec gauss_jordan(const mat &A, const vec &b) {
  int n = A.size();
  mat B(n, vec(n+1));
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < n; ++j) {
      B[i][j] = A[i][j];
    }
  }

  for(int i = 0; i < n; ++i) B[i][n] = b[i];

  for(int i = 0; i < n; ++i) {
    int pivot = i;
    for(int j = i; j < n; ++j) {
      if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j;
    }
    swap(B[i], B[pivot]);

    if(abs(B[i][i]) < eps) return vec();

    for(int j = i+1; j <= n; ++j) B[i][j] /= B[i][i];
    for(int j = 0; j < n; ++j) {
      if(i != j) {
        for(int k = i + 1; k <= n; ++k) {
          B[j][k] -= B[j][i] * B[i][k];
        }
      }
    }
  }
  vec x(n);
  for(int i = 0; i < n; ++i) {
    x[i] = B[i][n];
  }
  return x;
}

int d;
double fx[10];

double check(int w) {
  mat a;
  vec b;
  vec p;
  double q;
  for (int x = 0; x < d+3; ++x) {
    if (x == w) continue;
    vec v;
    for (int j = d; j >= 0; --j) {
      v.push_back(pow(x, j));
    }
    if (a.size() == d+1) {
      p = v;
      q = fx[x];
    } else {
      a.push_back(v);
      b.push_back(fx[x]);
    }
  }

  vec c = gauss_jordan(a, b);
  if (c.empty()) return 1.0 / 0.0;
  double r = 0;
  for (int i = 0; i < d+1; ++i) {
    r += c[i] * p[i];
  }
  return abs(q - r);
}

int main() {
  for (; cin >> d && d; ) {
    for (int i = 0; i < d+3; ++i) {
      cin >> fx[i];
    }
    int ans = 0;
    double mini = check(0);
    for (int i = 1; i < d+3; ++i) {
      double diff = check(i);
      if (mini > diff) {
        ans = i;
        mini = diff;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1320
// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
template <class t> inline void read(t &s)
{
	s=0;
	reg int f=1;
	reg char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(isdigit(c))
		s=(s<<3)+(s<<1)+(c^48),c=getchar();
	s*=f;
	return;
}
int a[300050];
inline bool cmp(int a,int b)
{
	return a>b;
}
signed main(void)
{
	int n,k;
	cin>>n>>k;
	reg int ans=0;
	for(int i=1;i<=n;++i)
		read(a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=k+1;i<=n;++i)
		ans+=a[i];
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 1792
def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    inf = float('inf')
    #dp = [inf] * n
    #dp[0] = 0
    dp = [0] * n

    for i1 in range(1, n):
        #print(i1, dp)
        start = max(0, i1 - k)
        dp[i1] = dp[start] + abs(h[start] - h[i1])
        for i2 in range(start, i1):
            dp[i1] = min(dp[i1], dp[i2] + abs(h[i1] - h[i2]))
    print(dp[n - 1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 54880
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <numeric>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

#define rep(i, n) for(int i = 0;i < n;i++)
const int INF = 1LL << 30;
const int MOD = 1000000007;

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

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int a,p; cin >> a >> p;

    cout <<(a*3+p)/2 << endl;
    

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
  public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   int c0 = 0;
   int c1 = 0;
   int c2 = 0;
   int c3 = 0;
   for(int i = 0; i < n+1; i++){
     String s = sc.nextLine();
     if(s.equals("AC")){
      ++c0; 
     }else if(s.equals("WA")){
      ++c1;
     }else if(s.equals("TLE")){
      ++c2;
     }else if(s.equals("RE")){
      ++c3;
     }
   }
   System.out.println("AC x " + c0);
   System.out.println("WA x " + c1);
   System.out.println("TLE x " + c2);
   System.out.println("RE x " + c3);
  }
}



Measured memory_bytes: 60296
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC134A
{
    class Program
    {
        static void Main(string[] args)
        {
            int r = int.Parse(Console.ReadLine());
            Console.WriteLine(r*r*3);
            Console.ReadKey();
        }
     }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std; 
#define ll long long int
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define INF LLONG_MAX
#define PI acos(-1)
#define MOD 1e9 + 7
#define fir first
#define sec second
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
bool cmp(ll a,ll b)
{
	return (a>b);
}
int main()
{
	IOS
	ll n,h,w;
	cin>>n>>h>>w;
	cout<<(n-h+1)*(n-w+1);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int  long long int
#define fi first
#define se second
#define pb push_back
#define soo(v) sort(v.rbegin(),v.rend())
#define so(v) sort(v.begin(),v.end())
#define lb(v,x) lower_bound(v.begin(),v.end(),x)
#define ub(v,x) upper_bound(v.begin(),v.end(),x)
#define endl '\n'
#define dbv(v) cout<<endl;cout<<#v<<"-->> ";for(auto it:v){cout<<it<<" ";}cout<<endl;
#define dbm(m)cout<<endl;cout<<#m<<"-->> ";for(auto it:m){cout<<it.fi<<" "<<it.se<<endl;}
#define dbs(s)cout<<endl;cout<<#s<<"-->> ";for(auto it:s){cout<<it<<" ";}cout<<endl;
#define mod 2019
#define db1(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<endl;
#define mx 1e18
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v)  *min_element(v.begin(),v.end())
#define double long double
#define re(s) reverse(s.begin(),s.end())
#define io std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
int powe(int x,int n)
{
  if(n==0)return 1;
  if(n%2==0)
    return powe((x%mod*x%mod)%mod,n/2)%mod;
  return (x%mod*powe((x%mod*x%mod)%mod,(n-1)/2))%mod;
}
int gcd(int A,int B)
{
  if(B==0)return A;
  return gcd(B,A%B);
}


int32_t main()
{
  io
  string s;
  cin>>s;
  int n=s.length();
   map<int,int>mm;int pp=0;mm[pp]++;
   for(int i=n-1;i>=0;i--)
   {
    pp=(pp%mod+(powe(10,n-i-1)%mod*(s[i]-'0')%mod)%mod)%mod;
  //  cout<<pp<<" ";
       mm[pp]++;
   }
  int ans=0;
  //dbm(mm)
  for(auto it:mm)
  {
    int cc=it.second;
    ans+=cc*(cc-1)/2;
  }
  cout<<ans<<endl;
}

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

public class Main {
	static boolean check(int arr[] ) {
	   
	    for(int i = 0; i<arr.length; i++) {
	    	if(arr[i] % 2 != 0) 
	    		return false;  
	    }
	    return true; 
	}
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader(System.in);
		int n = in.readInt();
		int arr[] = new int[n]; 
		for(int i = 0; i<n; i++) {
			arr[i] = in.readInt(); 
		}
		int ans = 0; 
		while(check(arr)) {
			for(int i = 0; i<arr.length; i++) {
				arr[i] = arr[i]/2; 
			}
			ans++;
		}
		System.out.println(ans);
	}
}
class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	
	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
int main(void){

  int X; cin >> X;
  int max = 1;
  for(int i = 2 ; i < X / 2 ; i++){
    int a = i;
    while(a <= X)  a *=i;
    a /= i;
    max = (max < a)? a : max;
  }

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

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <limits>
#include <iterator>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	vector<long long> a(N);
	for (auto &x : a) {
		cin >> x;
	}

	vector<long long> b;
	for (int l = 0; l < N; ++l) {
		partial_sum(a.begin() + l, a.end(), back_inserter(b));
	}

	for (int i = 40; i >= 0; --i) {
		vector<long long> t;
		for (auto x : b) {
			if (x & (1LL << i)) {
				t.push_back(x);
			}
		}
		if ((int)t.size() >= K) {
			b = move(t);
		}
	}

	long long ans = -1;
	for (auto x : b) {
		ans &= x;
	}
	cout << ans << endl;
}


Measured memory_bytes: 6516
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
use proconio::{fastout, input};
 
#[fastout]
fn main() {
  input! {
    s: String,
    mut k: usize
  }
  
  let s = s.chars().collect::<Vec<char>>();
  for i in 0..s.len() {
    let c = s[i];
    if c == '1' {
      k -= 1;
    } else {
      println!("{}", c);
      return
    }
    
    if k == 0 {
      println!("1");
      return
    }
  }
}

Measured memory_bytes: 2176
X,Y,A,B,C = map(int,input().split())
p = input().split()
q = input().split()
r = input().split()
p = [int(val) for val in p]
q = [int(val) for val in q]
r = [int(val) for val in r]
p.sort()
q.sort()
p_candidate = p[len(p)-X::]
q_candidate = q[len(q)-Y::]
candidate = []
candidate.extend(p_candidate)
candidate.extend(q_candidate)
candidate.extend(r)
candidate.sort()
print(sum(candidate[len(candidate)-X-Y::]))

Measured memory_bytes: 28992
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
 int N;
 cin >> N;
 int count = 0;
 int highest =0;
 int H;

 for(int i=0;i<N;i++){
   cin>> H;
   if(H>=highest){
     highest=H;
     count++;
   }
   } 
   
    
 
 
   
 
cout<< count <<endl;

  }


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

inline char get(void) {
  static char buf[100000], *S = buf, *T = buf;
  if (S == T) {
    T = (S = buf) + fread(buf, 1, 100000, stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
inline void read(int &x) {
  static char c; x = 0; int sgn = 0;
  for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
  for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
  if (sgn) x = -x;
}

string a, b, c;

int main(void) {
  cin >> a >> b >> c;
  if (a[a.size() - 1] != b[0] || b[b.size() - 1] != c[0]) puts("NO");
  else puts("YES");
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var inputs = new List<string>();
            for(var i = 0;i<N;i++)
            {
                inputs.Add(Console.ReadLine());
            }
            Console.WriteLine(inputs.Distinct().Count());
        }
    }

Measured memory_bytes: 13396
n,x=map(int,input().split())
donut=[]
ans=0
sum_num=0
for i in range(n):
    m=int(input())
    ans+=1
    donut.append(m)
sum_num+=sum(donut)
min_num=min(donut)
while(1):
    if sum_num>x:
        break
    ans+=1
    sum_num+=min_num
print(ans-1)

Measured memory_bytes: 9076
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

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

  vector<int> A(N, 0);
  for (int i = 1; i < N; i++) {
    cin >> A.at(i);
  }
  
  vector<int> B(N, 0);
  for (int i = 1; i < N; i++) {
    B.at(A.at(i)-1)++;
  }
  
  for (int i = 0; i < N; i++) {
    cout << B.at(i) << endl;
  }
}

Measured memory_bytes: 4808
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;

template<ll LOG=60>
struct doubling {
    // nxt[i][j] = (j番目の要素に関数fを2^i回適用した要素は何番目の要素か)
    vector<vector<ll>> nxt; 
    doubling(vector<ll> nxt0) : nxt(LOG, vector<ll>(nxt0.size())) {
        REP(i, nxt0.size()) nxt[0][i] = nxt0[i];
        FOR(k, 1, LOG) REP(j, nxt0.size()) nxt[k][j] = nxt[k-1][nxt[k-1][j]];
    }
    // x番目の要素に関数fをk回適用した要素は何番目の要素か？
    ll query(ll x, ll k) {
        for(ll i=LOG-1; i>=0; --i) if(k&1LL<<i) x = nxt[i][x];
        return x;
    }
};

int main(void) {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for(auto &i: a) cin >> i, i--;

    doubling dbl(a);
    cout << dbl.query(0, k)+1 << endl;

    return 0;
}

Measured memory_bytes: 101680
def main(str)
  n = str.to_i
  sum = 0
  (1..n).each do |a|
    (1..n).each do |b|
      (1..n).each do |c|
        sum += a.gcd(b).gcd(c)
      end
    end
  end
  sum
end

puts main($stdin.read.chomp)

Measured memory_bytes: 14456
#include<iostream>
using namespace std;
int main() {

	//B
	int n, l;
	cin >> n >> l;
	int k = n * l + n * (n - 1) / 2;
	//cout << k;
	int i;
	int min = l;
	for (i = 0; i < n; i++) {
		if (abs(l + i) < abs(min)) {
			min =  l + i;
		}
	}
	cout << k - min << endl;
	return 0;

	//A
	/*
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++) {
		if (s[i] == s[i + 1]) {
			cout << "Bad" << endl;
			return 0;
		}
	}
	cout << "Good" << endl;
	return 0;
	*/
}

Measured memory_bytes: 3632
/**
>>> In The Name Of GOD
**/
#include <bits/stdc++.h>

using namespace std;

//freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

///ifstream fin("input.txt");
///ofstream fout("output.txt");

vector <int> mark;

vector < vector <int> > adj;
vector < pair <int,int> > edge;
vector <int> h;

int dfs(int v)
{
    mark[v-1]=1;
    int m1,m2;
    m1=m2=h[v-1];
    //int check=1;
    for (auto i:adj[v-1])
        if (!mark[i-1])
        {
            h[i-1]=h[v-1]+1;
            int x=dfs(i);
           // if (v-1==3)
             //   cout << '#'<< x << ' ' << h[v-1] << endl;
            if ((x>h[v-1] || adj[i-1].size()==1))
            {
                edge.push_back(make_pair(min(i,v)-1,max(i,v)-1));
                //check=0;
            }
            m1=min(m1,x);
        }
        else
            if (h[i-1]!=h[v-1]-1)
                m2=min(m2,h[i-1]);

    return min(m1,m2);
}


int main()
{
    int n,i,m;
    cin >> n >> m;
    for (i=0;i<n;i++)
        mark.push_back(0), h.push_back(0), adj.push_back({});
    int x,y;
    for (i=0;i<m;i++)
        cin >> x >> y, adj[x].push_back(y+1), adj[y].push_back(x+1);
    dfs(1);
    sort(edge.begin(),edge.end());
    for (auto j:edge)
        cout << j.first << ' ' << j.second <<endl;
    return 0;
}



Measured memory_bytes: 4880
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, ans=0;
  cin >> n;

  vector<int> a(n), b(n), c(n-1);
  
  for(int i=0;i<(n);i++){
    cin >> a.at(i);
  }
  
  for(int i=0;i<(n);i++){
    cin >> b.at(i);
  }
  
  for(int i=0;i<(n-1);i++){
  cin >> c.at(i);
  }
  

  ans += accumulate(b.begin(), b.end(), 0);
  
  for(int i=0;i<(n-1);i++){
    if(a.at(i) == a.at(i+1)-1) ans+=  c.at(a.at(i)-1);
  }

  cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool ispalindrome(string str)
{
    int l=0;
    int h=str.length()-1;
    while(h>l)
    {
        if(str[l++]!=str[h--])
         return 0;

    }
    return true;
}
int main()
{
string s;
cin>>s;
int n=s.length();
string st=s;
if(ispalindrome(st)==false)
{
    cout<<"No";return 0;

}
st=s.substr(0,(n-1)/2);
if(ispalindrome(st)==false)
{
    cout<<"No";return 0;

}
int a=(n+3)/2;
st=s.substr(a-1,n-a+1);
if(ispalindrome(st)==false)
{
    cout<<"No";return 0;

}
cout<<"Yes";
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

struct UnionFind{
    std::vector<int> parent, rank, cnt;

    UnionFind(int n) : parent(n), rank(n, 0), cnt(n, 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int v){
        if(v == parent[v]){return v;}
        return parent[v] = find(parent[v]);
    }

    bool same(int v, int w){
        return find(v) == find(w);
    }

    void unite(int v, int w){
        v = find(v);
        w = find(w);

        if(v == w){return;}

        if(rank[v] > rank[w]){
            parent[w] = v;
            cnt[v] += cnt[w];
        }else{
            parent[v] = w;
            cnt[w] += cnt[v];
            if(rank[v] == rank[w]){rank[w] += 1;}
        }
    }

    int count(int v){
        return cnt[find(v)];
    }
};

int N, M, K;
std::vector<int> G[100100], H[100100];
UnionFind uf(100100);

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

    std::cin >> N >> M >> K;

    for(int i=0;i<M;++i){
        int a, b;
        std::cin >> a >> b;

        G[a].emplace_back(b);
        G[b].emplace_back(a);

        uf.unite(a, b);
    }

    for(int i=0;i<K;++i){
        int a, b;
        std::cin >> a >> b;

        H[a].emplace_back(b);
        H[b].emplace_back(a);        
    }

    for(int i=1;i<=N;++i){
        int n = uf.count(i), m = 0, l = 0;

        for(int j : G[i]){
            if(uf.same(j, i)){
                m += 1;
            }
        }

        for(int j : H[i]){
            if(uf.same(j, i)){
                l += 1;
            }
        }

        int res = (n - 1) - m - l;

        std::cout << res << " \n"[i == N];
    }
}



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

using namespace std;
using ll = long long;

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

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

  set<char> a{'A', 'C', 'G', 'T'};

  int n = s.size();
  int ans = 0;
  rep(i, n) {
    int now = 0;
    for (int j = i; j < n; ++j) {
      if (a.find(s[j]) == a.end()) break;
      ++now;
    }
    ans = max(ans, now);
  }

  cout << ans << endl;
  return 0;
}


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

unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

int main() {
  ll n; cin >> n;
  ll cnt=0;
  
  for(int i=1; i<n+1; i++){
    if(GetDigit(i)%2 == 1)
      cnt++;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3528
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;

    int main(){
      int sx,sy,tx,ty;
      cin>>sx>>sy>>tx>>ty;
      string ans;
      int dx = tx-sx;
      int dy = ty-sy;
      rep(i,dy)ans += 'U';
      rep(i,dx)ans += 'R';
      rep(i,dy)ans += 'D';
      rep(i,dx)ans += 'L';
      ans += 'L';
      rep(i,dy+1)ans += 'U';
      rep(i,dx+1)ans += 'R';
      ans += 'D';
      ans += 'R';
      rep(i,dy+1)ans += 'D';
      rep(i,dx+1)ans += 'L';
      ans += 'U';
      cout<<ans<<endl;

    }


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

using ll = long long;
using ld = long double;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
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;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';

void solve();

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

void solve() {
    int n;
    cin >> n;
    int mn = INF;
    int mx = -1;
    int a;
    REP(i, n) {
        cin >> a;
        chmin(mn, a);
        chmax(mx, a);
    }
    cout << mx - mn << EOL;

}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a = list(input())
b = list(input())
l = []
# count = 0
while len(a) != 0 or len(b) != 0:
    # print(a.pop(0))
    if len(a) != 0:
        l.append(a.pop(0))
        # print(a.pop(0))
    if len(b) != 0:
        l.append(b.pop(0))
        # print(b.pop(0))
    # print(l)
print("".join(l))


  


Measured memory_bytes: 5192