akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

template<int mod>
struct ModInt{
	int x;
	ModInt () : x(0) {}
	ModInt (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {}
	ModInt &operator += (const ModInt &p){
		if ((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator -= (const ModInt &p) {
		if ((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator *= (const ModInt &p) {
		x = (int64_t) x * p.x % mod;
		return *this;
	}
	ModInt &operator /= (const ModInt &p) {
		*this *= p.inverse();
		return *this;
	}
	ModInt &operator ^= (int64_t p) {
		ModInt res = 1;
		for (; p; p >>= 1) {
			if (p & 1) res *= *this;
			*this *= *this;
		}
		return *this = res;
	}
	ModInt operator - () const { return ModInt(-x); }
	ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; }
	ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; }
	ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; }
	ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; }
	ModInt operator ^ (int64_t p) const { return ModInt(*this) ^= p; }
	bool operator == (const ModInt &p) const { return x == p.x; }
	bool operator != (const ModInt &p) const { return x != p.x; }
	explicit operator int() const { return x; }
	ModInt &operator = (const int p) { x = p; return *this;}
	ModInt inverse() const {
		int a = x, b = mod, u = 1, v = 0, t;
		while (b > 0) {
			t = a / b;
			a -= t * b;
			std::swap(a, b);
			u -= t * v;
			std::swap(u, v);
		}
		return ModInt(u);
	}
	friend std::ostream & operator << (std::ostream &stream, const ModInt<mod> &p) {
		return stream << p.x;
	}
	friend std::istream & operator >> (std::istream &stream, ModInt<mod> &a) {
		int64_t x;
		stream >> x;
		a = ModInt<mod>(x);
		return stream;
	}
};

template<int mod> struct MComb {
	using mint = ModInt<mod>;
	std::vector<mint> fact;
	std::vector<mint> inv;
	MComb (int n) { // O(n + log(mod))
		fact = std::vector<mint>(n + 1, 1);
		for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * mint(i);
		inv.resize(n + 1);
		inv[n] = fact[n] ^ (mod - 2);
		for (int i = n; i--; ) inv[i] = inv[i + 1] * mint(i + 1);
	}
	mint ncr(int n, int r) {
		return fact[n] * inv[r] * inv[n - r];
	}
	mint npr(int n, int r) {
		return fact[n] * inv[n - r];
	}
	mint nhr(int n, int r) {
		assert(n + r - 1 < (int) fact.size());
		return ncr(n + r - 1, r);
	}
};

typedef ModInt<1000000007> mint;


int main() {
	int n = ri();
	int m = ri();
	MComb<1000000007> com(n * 2);
	mint res = 0;
	mint cur = 1;
	for (int i = m; i > m - n; i--) cur *= i;
	cur *= cur;
	for (int i = 0; i <= n; i++) {
		mint tmp = com.ncr(n, i) * cur;
		if (i & 1) res -= tmp;
		else res += tmp;
		if (i != n) cur /= m - i;
	}
	printf("%d\n", res.x);
	return 0;
}


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

int main() {
    int N, K, Q, A[100000], P[100000] = {};
    cin >> N >> K >> Q;
    for(int i = 0; i < Q; i++) {
        cin >> A[i];
        P[A[i] - 1]++;
    }
    for(int i = 0; i < N; i++) {
        if((Q - P[i]) >= K) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

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

int main()
{
    int n,m;
    cin >> n >> m;
    long long a[n];
    for(int i=0;i<n;i++)    cin >> a[i];
    priority_queue<long long> p(a,a+n);
    while(m--)
    {
        long long x=p.top();
        p.pop();
        x/=2;
        p.push(x);
    }
    long long y = 0;
    while(p.empty()==false)
    {
        y+=p.top();
        p.pop();
    }
    cout << y;
    return 0;
}

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

int dp[1005][1005];
int q,n,m;
string x,y;

int main() {
	cin >> q;
	for(int a = 0; a < q; a++){
		cin >> x >> y;
		n = x.size();
		m = y.size();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
			if		(x[i] == y[j]) dp[i+1][j+1] = dp[i][j] + 1;
			else if (x[i] != y[j]) dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
			}
		}
		cout << dp[n][m] << endl;
	}
}


Measured memory_bytes: 7036
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A: 居合を終え、青い絵を覆う / UOIAUAI
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  char &c = s[0];
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
    puts("vowel");
  else
    puts("consonant");
  return 0;
}


Measured memory_bytes: 256
open Printf
open Scanf
open Num


module Pqueue = struct

  type 'a t = {mutable cnt : int; hp : 'a array; cmp : 'a -> 'a -> int}

  let create n v f = {cnt = 0; hp = Array.make n v; cmp = f}

  let push k pq =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let p = i / 2 in
      if p = 0 || pq.cmp pq.hp.(p) pq.hp.(i) >= 0 then ()
      else (swap p i; iter p)
    in
    pq.cnt <- pq.cnt + 1;
    pq.hp.(pq.cnt) <- k;
    iter (pq.cnt)

  let max_heapify pq n =
    let swap i j =
      let t = pq.hp.(i) in
      pq.hp.(i) <- pq.hp.(j);
      pq.hp.(j) <- t in
    let rec iter i =
      let l = 2 * i in
      let r = 2 * i + 1 in
      let mi =
        let ti = if l <= pq.cnt && pq.cmp pq.hp.(l) pq.hp.(i) > 0 then l else i in
        if r <= pq.cnt && pq.cmp pq.hp.(r) pq.hp.(ti) > 0 then r else ti in
      if mi <> i then
        begin
          swap mi i;
          iter mi
        end
    in
    iter n

  let pop pq =
    let ret = pq.hp.(1) in
    pq.hp.(1) <- pq.hp.(pq.cnt);
    pq.cnt <- pq.cnt - 1;
    max_heapify pq 1;
    ret

  let top pq = pq.hp.(1)

  let is_empty pq = pq.cnt = 0

  let length pq = pq.cnt

end

let id x = x

let dijkstra g n s =
  let d = Array.make n (num_of_string "200000000000000") in
  let av = Array.make n true in
  let pq = Pqueue.create 2000000 ((num_of_int 0),0) (fun x y -> let x1 = fst x and y1 = fst y in if y1 >/ x1 then 1 else if y1 =/ x1 then 0 else (-1)) in
  let rec loop () =
    if Pqueue.is_empty pq then d
    else let du, u = Pqueue.pop pq in
         if av.(u) then begin
             av.(u) <- false;
             List.iter (fun (v, c) ->
                        if du +/ c </ d.(v) then begin
                            d.(v) <- du +/ c;
                            Pqueue.push (d.(v), v) pq
                          end
                       ) g.(u);
             loop ()
           end
         else loop ()
  in
  d.(s) <- num_of_int 0;
  Pqueue.push (d.(s), s) pq;
  loop ()

let () =
  let n = scanf "%d " id in
  let g = Array.make n [] in
  let rec make_g x =
    if x = 0 then ()
    else
      let a, b, c = scanf "%d %d %s " (fun i j k -> (i-1, j-1, num_of_string k)) in
      g.(a) <- (b, c) :: g.(a);
      g.(b) <- (a, c) :: g.(b);
      make_g (x-1) in
  make_g (n-1);
  let q, k = scanf "%d %d " (fun i j -> (i, j-1)) in
  let d = dijkstra g n k in
  let rec loop z =
    if z = 0 then ()
    else
      let x, y = scanf "%d %d " (fun i j -> (i-1, j-1)) in
      printf "%s\n" (string_of_num (d.(x) +/ d.(y)));
      loop (z-1)
  in
  loop q


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

class _C
{
	void _()
	{

		var n = _Ns();

		var a = n[0];
		var b = n[1];

		long c = (long)a * (long)b;

		if (c <= 0)
			Console.WriteLine("Zero");
		else if (a > 0)
			Console.WriteLine("Positive");
		else {
			if(Math.Abs((long)a-(long)b)%2==0)
				Console.WriteLine("Negative");
			else
				Console.WriteLine("Positive");
		}
	}

	static void Main(string[] args)
  {
    new _C()._();
  }

  #region

  string _S()
  {
    return Console.ReadLine();
  }

  string[] _Ss()
  {
    return Console.ReadLine().Split();
  }

  int[] _N(int n)
  {
    var x = new int[n];
    for (var i = 0; i < n; i++)
    {
      x[i] = int.Parse(Console.ReadLine());
    }
    return x;
  }

  int[] _Ns()
  {
    var ss = Console.ReadLine().Split();

    var x = new int[ss.Length];
    for (var i = 0; i < ss.Length; i++)
      x[i] = int.Parse(ss[i]);

    return x;
  }
  #endregion
}

Measured memory_bytes: 2772
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

int main() {
    int N, K;
    cin >> N >> K;
    if (K > (N - 1) * (N - 2) / 2) {
        cout << -1 << "\n";
        return 0;
    }
    vector<pair<int, int>> ans;
    REP(i, N) ans.push_back(pair<int, int>{0, i});
    int X = (N - 1) * (N - 2) / 2 - K;
    int a = 1, b = 2;
    while (X) {
        ans.push_back(pair<int, int>{a, b});
        ++b;
        if (b >= N) {
            ++a;
            b = a + 1;
        }
        --X;
    }
    cout << SZ(ans) << "\n";
    rep(i, SZ(ans)) cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
    return 0;
}


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

int main(){
  constexpr int Nbit= 10;
  constexpr int Npat= Nbit+ 1;
  int N;
  cin >> N;

  vector<bitset<Nbit>> stores(N);
  vector<vector<int>> rewards(N, vector<int>(Npat));
  for(int i=0; i<N; i++){
    int buf;
    for(int b=0; b<Nbit; b++){
      cin >> buf;
      if(buf==1){ stores.at(i).set(b); }
    }
  }
  for(int i=0; i<N; i++){
    for(int j=0; j<Npat; j++){
      cin >> rewards.at(i).at(j);
    }
  }

  int ans= INT_MIN;
  for(int tmp=1; tmp<(1 << Nbit); tmp++){/* 全部閉めるのはNG */
    bitset<Nbit> mystore(tmp);
    int cand= 0;
    for(int i=0; i<N; i++){
      bitset<Nbit> both= stores.at(i) & mystore;
      cand+= rewards.at(i).at(both.count());
    }
    ans= max(ans, cand);
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn= 5e5+5;
#define mod 1000000007
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main(){
    rishabh();
    int n;
    cin>>n;
    int arr[n],brr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        brr[i]=arr[i];
    } 
    sort(brr,brr+n);
    for(int i=0;i<n;i++){
        if(arr[i]==brr[n-1]){
            cout<<brr[n-2]<<endl;
        }
        else cout<<brr[n-1]<<endl;
    }
}



Measured memory_bytes: 5204
#include <bits/stdc++.h>
using namespace std;
  int N,A,B ;
  int main() {
    cin >> N >> A >> B;
    if (N * A == B) {
  cout << B << endl;
}
else if (N * A >= B) {
  cout << B << endl;
}
else if (N * A <= B) {
  cout << N * A << endl;
  }
return 0;
  }

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;
using intk = int64_t;

int main() {
intk a,b,c,k;
  cin >>a>>b>>c>>k;
  if(k%2 ==0) cout << a-b <<endl;
  else cout << b-a <<endl;
}
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int k,s;
    cin>>k>>s;
    int counter=0;
    for(int x=0;x<=k;x++){
        for(int y=0;y<=k;y++){
            int z=s-x-y;
            if(0<=z && z<=k){
                counter++;
            }
        }
    }
    cout<<counter<<endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <unordered_set>
#include <vector>
#include<valarray>
#include<map>
#include <bits/stdc++.h>
#include <utility>
#include<bits/stdc++.h>
int a[4];
using namespace std;

int main()
{
int t;
cin>>t;
string s;
while (t--)
{
    cin>>s;
    if(s=="AC")
    {
        a[0]++;
    }
    if(s=="WA")
    {
        a[1]++;
    }
    if(s=="TLE")
    {
        a[2]++;
    }
    if(s=="RE")
    {
        a[3]++;
    }

}
cout<<"AC x "<<a[0]<<endl;
    cout<<"WA x "<<a[1]<<endl;
    cout<<"TLE x "<<a[2]<<endl;
    cout<<"RE x "<<a[3]<<endl;


    return 0;
}

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

using namespace std;

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

typedef struct Node {
  int cost;
  Node* left;
  Node* right;
  Node* parent;
}node;

node nodes[1000];
int nodenum=-1;

int constructGraph(string s){
  int i=0;
  int left,right;
  int par = 0;
  if (s=="")return -1;
  while(1){
    char c=s[i];
    if (c=='('){
      par++;
    } else if (c==')') {
      par--;
    }
    i++;
    if (par==0){left=i;i++;break;}
  }
  string num{s[i]};
  i++;
  while(1){
    if (isdigit(s[i])){
      num += s[i];
      i++;
    } else {
      right = i+1;
      break;
    }
  }
  int cost=stoi(num);
  node n={cost,NULL,NULL,NULL};
  nodenum++;
  nodes[nodenum] = n;
  int ret = nodenum;
  int ileft = constructGraph(s.substr(1,left-2));
  int iright = constructGraph(s.substr(right+1,s.size()-right-2));
  if (ileft>0){
    nodes[ret].left = &nodes[ileft];
  } else { 
    nodes[ret].left = NULL;
  }
  if (iright > 0) {
    nodes[ret].right = &nodes[iright];
  } else {
    nodes[ret].right = NULL;
  }
  return ret;
}

string inorder(pair<node*,node*> p){
  int cost = p.first->cost+p.second->cost;
  string ret = "(";
  if (p.first->left != NULL && p.second->left != NULL){
    ret += inorder(make_pair(p.first->left,p.second->left));
  }
  ret += ")["+to_string(cost)+"](";
  if (p.first->right != NULL && p.second->right != NULL){
    ret += inorder(make_pair(p.first->right,p.second->right));
  }
  ret += ")";
  return ret;
}

int main(){

  string s1,s2;
  cin >> s1 >> s2;
  int ind1,ind2;
  ind1 = constructGraph(s1);
  ind2 = constructGraph(s2);
  string ret = inorder(make_pair(&nodes[ind1],&nodes[ind2]));
  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 3352
from copy import deepcopy
from math import ceil
n, p = map(int, input().split())
ans = 1
q = deepcopy(p)
for i in range(2, int(p ** 0.5) + 2):
    cnt = 0
    while p % i == 0:
        p //= i
        cnt += 1
    if cnt > 0:
        ans *= i ** (cnt // n)

print(ans if p != q and n != 1 else q)


Measured memory_bytes: 9508
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    std::cout << std::fixed << std::setprecision(10);
    int N, K;
    cin >> N >> K;

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

    vector<double> kitaichi(N);
    for (int i = 0; i < N; i++)
    {
        kitaichi[i] = (1 + p[i]) / 2;
    }

    // debug
    // for (int i = 0; i < N; i++)
    // {
    //     cout << kitaichi[i] << " ";
    // }

    vector<double> ruiseki(N + 1, 0);
    for (int i = 0; i < N; ++i)
    {
        ruiseki[i + 1] = ruiseki[i] + kitaichi[i];
    }

    // debug for kitaichi
    // for (int i = 0; i <= N; ++i)
    // {
    //     cout << ruiseki[i] << " ";
    // }

    // K差を見る
    double ans = 0;
    for (int i = 0; i + K <= N; i++)
    {
        if (ans < ruiseki[i + K] - ruiseki[i])
        {
            ans = ruiseki[i + K] - ruiseki[i];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define int long long

template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  int n;cin>>n;
  for(int i=1;i<=100000;i++){
    int a=i*108;a/=100;
    if(n==a)fin(i);
  }
  fin(":(");
}


Measured memory_bytes: 256
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;
import std.ascii;


void main()
{
  int a, b, c, d;
  readf("%s %s %s %s\n", &a, &b, &c, &d);

  auto l = a + b;
  auto r = c + d;
  if (l < r) {
    writeln("Right");
  } else if (l > r) {
    writeln("Left");
  } else {
    writeln("Balanced");
  }
}


Measured memory_bytes: 256
// https://ynucpc.github.io/blog/2018/04/15/cp_vscode/
// http://www.atmarkit.co.jp/ait/articles/1509/08/news019.html

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,n,m) for(ll i=(n);i<(ll)(m);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b)) 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int stoi (string s, int tmp=10){
	istringstream stm(s);
	int res;
	stm >> res;
	return res;
}
double stod(string s, int tmp=10){
	istringstream stm(s);
	double res;
	stm >> res;
	return res;
}


// 配列の総和
// greater


ll H[101010];
ll dp[101010][3];

int main(){	
	// ll A;
    // cin >> A;
	// cout << "hello" << endl;
	// cout << stoi("14") << endl;
	// cout << max({1,3}) << endl;
	ll N, K;
	cin >> N;
	rep(i, 3)dp[0][i]=0;
	rep1(i, N){
		rep(j, 3){
			cin >> dp[i][j];
			ll ma = 0;
			rep(k, 3){
				if(k!=j)chmax(ma, dp[i-1][k]);
			}
			dp[i][j] += ma;
		}
	}
	cout << *max_element(dp[N], dp[N]+3) << endl;
	
}








Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define in insert
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e9 + 5;
const int  N = 2e5 + 314;
void foo(){
    string s, t;
    int a, b;
    cin>>s>>t>>a>>b;
    string x;
    cin>>x;
    if(x==s)a--;
    else b--;
    cout<<a<<" "<<b;
}
int main(){
    speed;
    int t=1;
    //cin>>t;
    while(t--)foo();
}

Measured memory_bytes: 256
N = int(input())
x = 1
y = 1
for i in range(N):
    T, A = map(int, input().split())
    p = (T + x - 1) // T
    q = (A + y - 1) // A
    x = T * max(p, q)
    y = A * max(p, q)
    #print(f"[{x} {y}]")
print(x + y)


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

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> l(N);
	for (int i = 0; i < N; i++) {
		cin >> l[i];
	}

	sort(l.begin(), l.end(), greater<int>());
	int ans = 0;
	for (int i = 0; i < K; i++)
	{
		ans += l[i];
	}

	cout << ans << endl;

	return 0;
}

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

int main()
{
  string w;
  cin>>w;
  if(w=="Sunny")
  {
    cout<<"Cloudy"<<endl;
  }
  if(w=="Cloudy")
  {
    cout<<"Rainy"<<endl;
  }
  if(w=="Rainy")
  {
    cout<<"Sunny"<<endl;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <string>
using namespace std;
//
const int inf=1e9+7;
//
int main(){
	int N;
	string now,cur;
	cin>>N;
	cin>>cur;
	set<string> S;
  S.insert(cur);
	for(int i=1;i<N;i++){
		cin>>now;
		if(S.find(now)==S.end()){
			if(cur[(int)cur.size()-1]==now[0]){
              S.insert(now);
			}else{
				cout<<"No"<<endl;
				return 0;
			}
		}else{
			cout<<"No"<<endl;
			return 0;
		}
		cur=now;
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define  mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int a,b;cin>>a>>b;
    if(a==b)
        cout<<"Draw"<<endl;
    else if(a>b&b!=1)
        cout<<"Alice"<<endl;
    else if(b==1)
        cout<<"Bob"<<endl;
    else if(a==1)
        cout<<"Alice"<<endl;
    else
        cout<<"Bob"<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------






Measured memory_bytes: 256
#include <vector>
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long long> w(n+1,0);
    for(int i=0;i<n;i++) cin >> w[i+1];
    for(int i=0;i<n;i++) w[i+1]+=w[i];
    vector<vector<long long> > dp(n,vector<long long>(n,0));
    vector<vector<int> > a(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        a[i][0]=i;
    }
    for(int i=1;i<n;i++){
        a[i-1][1]=i-1;
        dp[i-1][1]=w[i+1]-w[i-1];
    }
    for(int l=2;l<n;l++){
        for(int i=0;i<n-l;i++){
            long long m=dp[i][a[i][l-1]-i]+dp[a[i][l-1]+1][(i+l)-(a[i][l-1]+1)];
            int argm=a[i][l-1];
            for(int k=a[i][l-1]+1;k<a[i+1][l-1]+1;k++){
                if(dp[i][k-i]+dp[k+1][i+l-(k+1)]<m){
                    m=dp[i][k-i]+dp[k+1][i+l-(k+1)];
                    argm=k;
                }
            }
            a[i][l]=argm;
            dp[i][l]=m+w[i+l+1]-w[i];
        }
    }
    cout << dp[0][n-1] << endl;
}


Measured memory_bytes: 190872
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>

using namespace std;
const long long mod = 1e9 + 7;

void solve();

void solve(int N, int M, vector<int> A) {
  vector<long long int> dp(N + 1);
  dp[0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j <= min({N, i + 2}); j++) {
      if (A[j]) {
        dp[j] += dp[i];
        dp[j] %= mod;
      }
    }
  }
  cout << dp[N] << endl;
}

int main() {
  int N, M;
  cin >> N >> M;
  int a;
  vector<int> A(N + 1, true);
  for (int i = 0; i < M; i++) {
    cin >> a;
    A[a] = false;
  }
  solve(N, M, A);
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//long long MOD = 1e9 + 7;

long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;


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

    ll n;
    cin >> n;
    vector<ull> d(n);

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

    //if (d[0] != 0) {
    //    cout << 0 << endl;
    //    return 0;
    //}

    int max = 0;
    vector<ull> count(n, 0);
    for (const auto e : d) {
        if (max < e) {
            max = e;
        }
        
        count[e]++;
    }

    if (d[0] != 0 || max == 0 || count[0] != 1) {
        cout << 0 << endl;
        return 0;
    }
    
    ull ans = 1;
    for (int i = 0; i < max; i++)
    {
        for (int j = 0; j < count[i+1]; j++)
        {
            ans = ans * count[i] % MOD;
        }
    }

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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int digit_cnt(int x) {
  int ret=0;
  while(x>0) {
    ret++;
    x/=10;
  }
  return ret;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  int n;
  cin>>n;
  int c=0;
  repeat(i,1,n+1) {
    if(digit_cnt(i)%2==1) {
      c++;
    }
  }
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f(i,a,n) for(int i=a;i<n;i++)
#define ve vector
#define ss second 
#define ff first
#define pf pop_front
#define pob pop_back
#define psf push_front
#define res(x) cout<<x<<'\n'
#define read(t) ll t;cin>>t

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
read(k);
read(r);
ll mult=1;
if(k==1){
    cout<<"1"<<endl;
}
else{
  f(i,1,1000){
     mult=mult*r;
     if(mult==k){
        cout<<i+1<<endl;
        break;
     }
     else if(mult>k){
         cout<<i<<endl;
         break;
     }
     else{

     }
     
  }
}
    


   

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define endl '\n'
#define pb push_back
#define mod 10000007
#define mp make_pair
#define pi acos(-1)
#define line cout<<"----------------------------"<<endl
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
using namespace std;
int  main()
{
    int n;
    cin>>n;
    set<int> s;
    for(int i=0;i<n;i++)
    {
        int x; cin>>x; s.insert(x);
    }
    if(s.size()==n) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 9600
#include <cstdio>

int SG(int a,int k)
{
    int x=a/k,b=a%k;
    if(!b) return x;
    int t=(b+x)/(x+1);
    return SG(a-t*(x+1),k);
}

int main()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int a,k;
        scanf("%d%d",&a,&k),ans^=SG(a,k);
    }
    puts(ans?"Takahashi":"Aoki");
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		ArrayDeque<String> deque = new ArrayDeque<String>();
		String s = sc.next();

		int q = sc.nextInt();
		int top = 1; // 反転情報を持つ
		deque.add(s);

		for (int i = 0; i < q; i++) {
			int t = sc.nextInt();
			if (t == 1) {
				top *= -1; // 反転情報を更新
			} else {
				int f = sc.nextInt();
				String c = sc.next();
				if (f == 1) { // 先頭にcを追加
					if (top > 0) {
						deque.addFirst(c);
					} else {
						deque.addLast(c);
					}
				} else { // 末尾にcを追加
					if (top > 0) {
						deque.addLast(c);
					} else {
						deque.addFirst(c);
					}
				}
			}
		}
		// 出力
		StringBuffer sb = new StringBuffer();
		int m = deque.size();
		for (int i = 0; i < m; i++) {
			sb.append(deque.pollFirst());
		}
		if (top < 0) {
			sb.reverse();
		}

		System.out.println(sb.toString());
		sc.close();
	}
}


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

#include<random> 

#define int long long 

#define pp pair<int,int> 

#define ss second 

#define ff first 

#define pb push_back 

#define mod 1000000007 

using namespace std; 

void fastio() 

{ 

    #ifndef ONLINE_JUDGE 

        freopen("INPUT.txt","r",stdin); 

            freopen("OUTPUT.txt","w",stdout); 

                #endif 

                    ios_base :: sync_with_stdio(false); 

                        cin.tie(NULL) ; 

                            cout.tie(NULL); 

                            }

signed main() 

{ 

    fastio(); 

        int t=1;

           // cin>>t;

                while(t--)

                    {

                         int a,b;

                         cin>>a>>b;

                         a--;b--;

                         cout<<(b%a>0)  + b/a;

                                                                                                      

    }

    }

    

Measured memory_bytes: 3648
#include <iostream>
#include <queue>
#include <complex>
#include <map>
#include <set>

using namespace std;

typedef complex<int> C;
typedef pair<C, C> P;
typedef pair<int, P> D;

namespace std {
    template<class T>
        bool operator<(const complex<T> &a, const complex<T> &b) {
            return a.real() == b.real()? a.imag() < b.imag(): a.real() < b.real();
        }
}

int main() {
    C dr[] = {C(1, 0), C(0, 1), C(-1, 0), C(0, -1)};
    int x, y, tx, ty, kx, ky;
    int map_[50][50];
    while (true) {
        cin >> x >> y;
        if (x == 0) {
            break;
        }
        cin >> tx >> ty >> kx >> ky;
        for (int i=0; i<y; i++) {
            for (int j=0; j<x; j++) {
                cin >> map_[j][i];
            }
        }
        bool is_found = false;
        set<P> visited;
        visited.insert(P(C(tx-1, ty-1), C(kx-1, ky-1)));
        queue<D> q;
        q.push(D(0, P(C(tx-1, ty-1), C(kx-1, ky-1))));
        while (q.size() > 0 && !is_found) {
            D d = q.front();
            int t = d.first;
            C tr_origin = d.second.first;
            C kr_origin = d.second.second;
            if (t == 99) {
                break;
            }
            for (int i=0; i<4; i++) {
                C tr = tr_origin+dr[i];
                C kr = kr_origin-dr[i];
                if (tr.real() < 0 || tr.imag() < 0 ||
                    tr.real() >= x || tr.imag() >= y ||
                    map_[tr.real()][tr.imag()] == 1) {
                    tr = tr_origin;
                }
                if (kr.real() < 0 || kr.imag() < 0 ||
                    kr.real() >= x || kr.imag() >= y ||
                    map_[kr.real()][kr.imag()] == 1) {
                    kr = kr_origin;
                }
                if (tr == kr) {
                    cout << t+1 << endl;
                    is_found = true;
                    break;
                }
                if (visited.find(P(tr, kr)) == visited.end()) {
                    visited.insert(P(tr, kr));
                    q.push(D(t+1, P(tr, kr)));
                }
            }
            q.pop();
        }
        if (!is_found) {
            cout << "NA" << endl;
        }
    }
    return 0;
}

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

#include <set>
#include <iterator>
using namespace std;
// using namespace __gnu_pbds;


#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define INF (ll)1e17
#define matrix vector<vector<ll> >

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )
#define maxbits 9
#define maxmask (1ll<<maxbits)
// typedef tree<pll, null_type, less<pll>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
const int  N=1e6 +10, M=(ll)1e9+1 ;
const int mod =998244353 ,sz=5, MAX=(ll)1e6+10;
string fir="Monocarp",sec="Bicarp";

void work(){
	ll n;
	cin >> n;
	vl a(n),ans(n+1,0);
	for(ll i=2;i<=n;i++){
		ll x;
		cin >> x;
		ans[x]++;
	}

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

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

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	// precomp();
	ll t;
	// cin >> t;
	t=1;
	while(t--){
	        work();
	
	}
return 0;
}
	

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

// definitions
#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 high(x) __builtin_popcountll(x)
#define pb push_back
#define pf push_front
#define mod1 998244353
#define mod 1000000007
#define MAX_CHAR 256
#define pi 3.1415926535897932384



using namespace std;
typedef vector<long long> vl;
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;

ll INF=1e18;



// prevent collisions in unordered_map
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <class T>
void read(T arr[],ll n) {rep(i,0,n) cin>> arr[i];}

typedef unordered_map <long long, long long, custom_hash> umap;


// standard functions
ll mystoi(string str)
{
    stringstream ss(str);
    ll ans=0;
    ss >> ans;

    return ans;
}

ll exp(ll x, ll ex, ll p) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x)%p;
        ex >>= 1ll;
        x = (x * x)%p;
    }
    return ans;
}

bool sort_cond(const pair<ll,ll> &a, const pair <ll,ll> &b)
{
    return ((a.f-a.s)>(b.f-b.s));
}

// code beigns in main
int main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    while(t--)
    {
        ll a,b;
        cin >> a >>b;

        cout << a*b << endl;
    }
}

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

int main() {
	int N;
	cin>>N;
	
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		if(a%2==0&&a%5!=0&&a%3!=0){
			cout<<"DENIED"<<endl;
			return 0;
		}
	}
	cout<<"APPROVED"<<endl;
}


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

int main() {
	int a;
	string s;
	cin>>a>>s;
	if(a>=3200)
		cout<<s;
	else cout<<"red";
	
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const ll INF = 1e+18;


int main(){
	int n;
	cin>>n;
	vector<int>h(n,0);
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	ll ans=0;
	for(int i=1;i<=100;i++){
		ll k=0;
		ll p=0;
		for(int j=0;j<n;j++){
			if(k==0&&h[j]>=i)k=1,p=1;
			if(k==1&&h[j]<i){
				ans++;
				k=0;
			}
		}
		if(k==1)ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
//(????????°, ?????¨????????????????????°)??§??´?????????????????¨, ???????????¢????????????????????????????????????????????§??????
//????????¨, ????????????????????????3?§???¢??¨4?§???¢????????????????????????
//A * B ??? 25000^2 ??? min(A, B) ??? 25000???????????¢???????°??????????????????????????????¨??£?§£???????????¨?????????????????????

#include <iostream>
#include <vector>
#define int long long
using namespace std;

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

//ax + by = gcd(a, b)??¨????????´??°???(x, y)??????????±?????????????.
void extgcd(int a, int b, int &x, int &y) {
	int r[100];
	int q[100];
	int cnt;
	
	r[0] = a;
	r[1] = b;
	cnt = 2;
	while (r[cnt - 2] % r[cnt - 1] != 0) {
		q[cnt - 1] = r[cnt - 2] / r[cnt - 1];
		r[cnt] = r[cnt - 2] - q[cnt - 1] * r[cnt - 1];
		cnt++;
	}
	q[cnt - 1] =r[cnt - 2] /  r[cnt - 1];
	
	x = 0;
	y = 1;
	for (int i = 0; i < cnt - 2; i++) {
		int nx = y;
		int ny = x - y * q[cnt - 2 - i];
		x = nx;
		y = ny;
	}
}

signed main() {
	int n, w, h;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> w >> h;
		int g = gcd(w, h);
		if (g < (w + h) / (2 * g)) {
			int x, y;
			extgcd(w, -h, y, x);
			cout << 3 << endl;
			cout << 0 << " " << 0 << endl;
			cout << w << " " << h << endl;
			cout << x << " " << y << endl;
		}
		else {
			cout << 4 << endl;
			cout << 0 << " " << 0 << endl;
			cout << w << " " << h - 1 << endl;
			cout << w / g << " " << h / g << endl;
			cout << w - 1 << " " << h << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3088
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <tuple>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    //    ifstream in("input.txt");
    //    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, k;
    cin >> n >> k;
    
    int ans = 0;
    if (n % k == 0)
    {
        ans = 0;
    }
    else
    {
        ans = 1;
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	char al,a,e,i,o,u;
	scanf("%c",&al);
	if(al == 'a' || al == 'e' || al == 'i' || al == 'o' || al == 'u'){
     printf("vowel\n");
	}
	else
		printf("consonant\n");
	return 0;
}

Measured memory_bytes: 128
n, m = map(int, input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]


for i in range(n-m+1):
    for j in range(n-m+1):
        flag = 0
        for k in range(m):
            for l in range(m):
                if a[i + k][j + l] != b[k][l]:
                    flag = 1
        if flag == 0:
            print('Yes')
            exit()


print('No')


Measured memory_bytes: 3060
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop, core.thread;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) throw new EOFException; tokens = readln.split; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


immutable MO = 10L^^9 + 7;

int N;
string S;

void main() {
  try {
    for (; ; ) {
      N = readInt();
      S = readToken();
      auto dp = new long[][](N, N + 1);
      dp[0][0 .. N] = 1;
      foreach (i; 0 .. N - 1) {
        foreach (x; 0 .. N - i) {
          switch (S[i]) {
            case '<': {
              (dp[i + 1][x] += dp[i][x]) %= MO;
              (dp[i + 1][N - i] -= dp[i][x]) %= MO;
            } break;
            case '>': {
              (dp[i + 1][0] += dp[i][x]) %= MO;
              (dp[i + 1][x] -= dp[i][x]) %= MO;
            } break;
            default: assert(false);
          }
        }
        foreach (x; 1 .. N - i) {
          (dp[i + 1][x] += dp[i + 1][x - 1]) %= MO;
        }
        debug {
          writefln("dp[%s] = %s", i + 1, dp[i + 1]);
        }
      }
      auto ans = dp[N - 1][0];
      ans = (ans % MO + MO) % MO;
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 73852
#include<stdio.h>

int main()
{
    int sx,sy,tx,ty,i;
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

    for(i=sy+1; i<=ty; i++)
        printf("U");

    for(i=sx+1; i<=tx; i++)
        printf("R");
    for(i=ty-1; i>=sy; i--)
        printf("D");
    for(i=tx-1; i>=sx; i--)
        printf("L");

    printf("L");
    for(i=sy+1; i<=ty+1; i++)
        printf("U");

    for(i=sx+1; i<=tx+1; i++)
        printf("R");

    printf("D");

    printf("R");
    for(i=ty-1; i>=sy-1; i--)
        printf("D");

    for(i=tx; i>=sx; i--)
        printf("L");

    printf("U");
    return 0;

}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <cmath>

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    map<long long, long long> m;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        m.insert(make_pair(i + 1, x));
    }
    map<long long, long long> lp;
    int start = 1;
    vector<long long> v;
    lp.insert(make_pair(start, 0));
    v.push_back(1);
    int ch = 0;
    for(int i = 0; i < n + 1; i++){
        start = m.at(v[i]);
        if(lp.find(start) != lp.end()){
            for(int j = 0; j < n; j++){
                if(v[j] == start){
                    ch = j;
                    break;
                }
            }
            break;
        } else {
            lp.insert(make_pair(start, 0));
            v.push_back(start);
        }
    }
    if(ch > k){
        cout << v[k] << endl;
    } else {
        long long new_k = k - ch;;
        int b = new_k % (v.size() - ch);
        cout << v[ch + b] << endl;
    }
}

Measured memory_bytes: 29528
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;

typedef long long ll;

ll n, m, crp, ans, a[N], b[N];

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld",&n ,&m);
	for(int i = 1; i <= n; i++)
		scanf("%lld",a + i);
	for(int i = 1; i <= m; i++)
		scanf("%lld",b + i);
	for(int i = 1; i < n; i++)
		crp = (crp + ((a[i + 1] - a[i])*i%mod)*(n - i)%mod)%mod;
	for(int i = 1; i < m; i++)
		ans = (ans + (((b[i + 1] - b[i])*crp%mod)*i%mod)*(m - i)%mod)%mod;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 5120
import numpy as np

MAX_VALUE = 100100
INF_WEIGHT = 1 << 30


def main(n, w, items):
    dp = np.full(
        shape=(n + 1, MAX_VALUE),
        fill_value=INF_WEIGHT,
        dtype=int,
    )
    dp[0][0] = 0
    for i in range(0, n):
        weight, value = items[i]
        dp[i + 1][:value] = np.minimum(dp[i][:value], dp[i + 1][:value])
        dp[i + 1][value:] = np.minimum(dp[i][value:], dp[i][:MAX_VALUE - value] + weight)

    return np.max(np.where(dp[-1] <= w))


if __name__ == '__main__':
    N, W = map(int, input().split())
    I = []
    for _ in range(N):
        I.append(tuple(map(int, input().split())))
    print(main(N, W, I))


Measured memory_bytes: 93108
"""
memo1[i] => i列目とi+1列目の間に横棒があるような場合の数
memo2[i] => i列目の両サイドに横棒がないような場合の数
"""

H,W,K = map(int,input().split())
if W == 1:
    print(1)
    exit()
mod = 10**9 +7
memo1 = [0]*(W-1)
memo2 = [0]*W
for i in range(2**(W-1)):
    #bin(i)が横棒の配置パターンを表す
    binI = format(i,"0"+str(W-1)+"b")
    #パターンが正しいかを確かめる
    for j in range(W-2):
        if binI[j]=="1" and binI[j+1]=="1":
            break
    else:
        for j in range(W-1):
            if binI[j] == "1":
                memo1[j] += 1
        if binI[0] == "0":
            memo2[0] += 1
        if binI[-1] == "0":
            memo2[-1] += 1
        for j in range(1,W-1):
            if binI[j-1]=="0" and binI[j]=="0":
                memo2[j] += 1


#dp[i][j] => i回目の移動が終わったタイミングで、j列目にいるような場合の数
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        #真下に移動する場合の数
        dp[i+1][j] += dp[i][j]*memo2[j]
        dp[i+1][j] %= mod

        #右に移動する場合の数
        if j != W-1:
            dp[i+1][j+1] += dp[i][j]*memo1[j]
            dp[i+1][j+1] %= mod

        #左に移動する場合の数
        if j != 0:
            dp[i+1][j-1] += dp[i][j]*memo1[j-1]
            dp[i+1][j-1] %= mod

print(dp[-1][K-1])

Measured memory_bytes: 63248
n = int(input())
g = [[0]*n for i in range(n)]
for s in range(n-1):
  for t in range(s+1,n):
    i,j = s,t
    ed = 1
    while j-i > 3:
      ed += 2
      i //= 4
      j //= 4
    g[s][t] = ed + 1 - (j-i)%2
for i in range(n):
  print(" ".join(map(str,g[i][i+1:])))

Measured memory_bytes: 5236
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int INF=1e9-5;
int cmp(int x,int y)
{
    return x>y;
}
int s[105];
int main()
{
   int a,b,k;
   cin>>a>>b>>k;
   int r=0;
   for(int i=1;i<=min(a,b);i++)
   {
       if(a%i==0&&b%i==0)
         s[r++]=i;
   }
   sort(s,s+r,cmp);
   cout<<s[k-1]<<endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    bool found[3]; F0R(i, 3) found[i] = false;
    F0R(i, 2) {
        int X; cin >> X; X--; found[X] = true;
    }

    F0R(i, 3) {
        if (found[i] == false) {
            cout << i+1 << endl;
        }
    }
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 256