akhauriyash/Code-Regression huggingface dataset:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N = I()
    AB = sorted(LIR(N), key=lambda x: x[1])

    tmp = 0
    for a, b in AB:
        tmp += a
        if tmp > b:
            print("No")
            break
    else:
        print("Yes")


if __name__ == '__main__':
    main()

Measured memory_bytes: 120720
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> COM;

bool comp(const COM& c1, const COM& c2){
  return c1.first > c2.first;
}

int main(void){
  int n, m, a;
  while(cin >> n >> m >> a && n != 0){
    vector<COM> vc;
    vector<int> bou;
    for(int i = 0; i <= n; i++){
      bou.push_back(i);
    }
    for(int i = 0; i < m; i++){
      int h, p, q;
      cin >> h >> p >> q;
      P po(p, q);  COM c(h, po);
      vc.push_back(c);
    }
    sort(vc.begin(), vc.end(), comp);
    for(int i = 0; i < vc.size(); i++){
      int s = vc[i].second.first;
      int t = vc[i].second.second;
      swap(bou[s], bou[t]);
    }
    for(int i = 0; i < bou.size(); i++){
      if(bou[i] == a){
        cout << i << endl;
        break;
      }
    }
  }
  return 0;
}

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

int main() {
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    if (x-r >= 0 && x+r <= W && y-r>=0 && y+r <=H) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3120
#include <stdio.h>
#include <stdlib.h>

int main(void){

	char sieve[1000000] = {0};
	sieve[0] = 1;
	sieve[1] = 1;

	int i, j;
	for(i = 2; i <= 1000; i++) {
		if (sieve[i] == 0) {
			for (j = i*i; j <= 999999; j += i){
				sieve[j] = 1;
			}
		}
	}

	int Num, Temp;
	while(scanf("%d", &Num) == 1){
		Temp = 0;
		for(i = 2; i <= Num; i++){
			if(sieve[i] == 0) Temp ++;
		}
		printf("%d\n", Temp);
	}

	return 0;
}

Measured memory_bytes: 1580
#include<bits/stdc++.h>
using namespace std;
     
     
//#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define sd(x) scanf("%d",&x)
#define sld(x) scanf("%lld",&x)
#define pld(x) printf("%lld\n",x)
#define pd(x) printf("%d\n",x)
     
     
int main(){

	int n; sd(n);

	pd(180*(n-2));           
           
     
     
        
    return 0;
}


Measured memory_bytes: 256
//let's do it
 #include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001
ll cnt[maxn];
set<ll>s;
int main()
{
    boost1;boost2;
    ll i,j,n,even=0,x;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        cnt[x]++;
        s.insert(x);
    }
    ll ans=s.size();
    for(i=1;i<=100000;i++)
    {
        if(!cnt[i])
        continue;
        even+=(cnt[i]%2==0);
    }
    if(even%2==0)
    cout<<ans;
    else
    cout<<ans-1;
    return 0;
}


Measured memory_bytes: 5760
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N, x;
  cin>>N>>x;
  if(x==1 || x==2*N-1){
    cout<<"No"<<endl;
    return 0;
  }
  vector<int> ans(2*N-1);
  for(int i=0;i<2*N-1;++i) ans[i] = 0;
  map<int, int> amap;
  ans[N-1] = x;
  ans[N-2] = x-1;
  ans[N] = x+1;
  amap[x-1]++;
  amap[x]++;
  amap[x+1]++;
  if(N>2){
    if(x+2<=2*N-1){
      ans[N-3] = x+2;
      amap[x+2]++;
    }
    if(x-2>0){
      ans[N+1] = x-2;
      amap[x-2]++;
    }
  }
  int index = 0;
  for(int i=1;i<=2*N-1;++i){
    if(amap[i]>0) continue;
    while(ans[index]!=0) index++;
    ans[index] = i;
  }
  cout<<"Yes"<<endl;
  for(int i=0;i<2*N-1;++i){
    cout<<ans[i]<<endl;
  }
}



Measured memory_bytes: 13496
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define endl '\n'

const int max4 = 10004;
const int maxx = 100005;
const int max6 = 1000006;
const int lg5 = 17;

const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;

/***************/

int powmod (int a, int b, int mod) {
    int res = 1; a %= mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
    }
    return res;
}
#define ll long long
ll gcd (ll a, ll b) {
    while (b > 0) {
        ll t = a % b;
        a = b, b = t;
    }
    return a;
}

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

int is_prime (int n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/******Don't forget to use long long when needed!!******/

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m; string s, t;
    cin >> n >> m >> s >> t;
    int N = n / gcd(n, m), M = m / gcd(n, m);
    for (int i = 0; i < gcd(n, m); i++) {
        if (s[i * N] != t[i * M]) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << lcm(n, m) << endl;
    return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		String S = sc.next();
		sc.close();
		
		boolean check = true;
		for(int i = 0; i < S.length(); i++) {
			if(i == A) {
				if(S.charAt(i) == '-') {
					continue;
				}else {
					check = false;
					break;
				}
			}else {
				if(S.substring(i, i + 1).matches("[0-9]")) {
					continue;
				}else {
					check = false;
					break;
				}
			}
		}
		System.out.println(check ? "Yes" : "No");
	}

}


Measured memory_bytes: 23252
n, m = map(int, input().split())
ans_dict = {}
for _ in range(m):
    p, s = input().split()
    if p not in ans_dict:
        ans_dict[p] = [s]
    else:
        ans_dict[p].append(s)

ac_cnt = 0
wa_cnt = 0

ac_ans = 0
wa_ans = 0

for key in ans_dict.keys():
    ac_cnt = ans_dict[key].count('AC')
    wa_cnt = ans_dict[key].count('WA')
    if ac_cnt != 0:
        ac_ans += 1
        # その問題の解答一覧で最初にACとなったインデックスを取得
        ac_index = ans_dict[key].index('AC')
        wa_ans += ans_dict[key][:ac_index].count('WA')
    
print(ac_ans, wa_ans) 

Measured memory_bytes: 34448
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String S = sc.next();
		String T = sc.next();
		int A = sc.nextInt();
		int B = sc.nextInt();
		String U = sc.next();
		
		System.out.println((U.equals(S) ? A-1 : A) + " " + (U.equals(T) ? B-1 : B));
		
		sc.close();
	}
}


Measured memory_bytes: 21588
#include <iostream>

using namespace std;

int main(){
	int x,y,z;
	int E;
	int min;
	int b=0;
	while(cin>>E&&E>0){
		int b=0;
		for(z=0; z*z*z<=E; z++){
			for(y=0; y*y<=E-z*z*z; y++){
				x=E-z*z*z-y*y;
				if(x<0)break;
				if(!b){
					min=x+y+z;
					b=1;
				}
				else{
					if(min>(x+y+z)){
						min=x+y+z;
					}
				}
			}
		}
		cout<<min<<endl;
	}
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef long double ld;

struct dset{
	vector<int> p, s;
	dset(int n){
		p.resize(n, -1);
		s.resize(n, 1);
	}
	int find(int x){
		if (p[x] == -1) return x;
		return p[x] = find(p[x]);
	}
	void join(int x, int y){
		x = find(x), y = find(y);
		if (x != y){
			if (s[x]<s[y]) swap(x,y);
			s[x]+= s[y];
			p[y] = x;
		}
	}
};

const int maxn = 1e5+5;
int n, a[maxn][2], coords[2][maxn];
set<int> C[maxn][2];

int main(){
	memset(coords, -1, sizeof(coords));
	scanf("%d", &n);
	dset dsu(n+1);
	for(int i = 0; i<n; i++){
		for(int j = 0; j<2; j++){
			int &x = a[i][j];
			scanf("%d", &x);
			if (coords[j][x] == -1) coords[j][x] = i;
			else dsu.join(i, coords[j][x]);
		}
	}
	for(int i = 0; i<n; i++)
		for(int j = 0; j<2; j++)
			C[dsu.find(i)][j].insert(a[i][j]);

	ll ans = -n;
	for(int i = 0; i<n; i++){
		ll p = 1;
		for(int j = 0; j<2; j++) p*= ll(C[i][j].size());
		ans+= p;
	}
	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 16640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=305;
int f[N][N],s[N][N],C[N][N],n,m,p;
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    C[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<n;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    }
    for(int i=0;i<=m;i++)f[1][i]=1,s[1][i]=m-i+1;
    for(int i=2;i<=n+1;i++)
    {
        for(int j=0;j<=m;j++)
            for(int l=1;l<i;l++)
                f[i][j]=(f[i][j]+1ll*C[i-2][l-1]*f[i-l][j]%p*s[l][j+1])%p;
        for(int j=m;j>=0;j--)s[i][j]=(s[i][j+1]+f[i][j])%p;
    }
    printf("%d\n",f[n+1][0]);
}


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

class UniTree { 
    public:
     
    // par[i]       : ノードiの親
    // hight[i]     : ノードiの高さ
    vector<int> par, hight;
 
    /*_______________________________________________________________*/
    // UniTree()
    //  [引数]   
    //          int size            : UnionFind木の大きさ
    //
    //  [機能]   
    //          UnionFind木の初期化（親と高さの初期化）
    /*_______________________________________________________________*/
    UniTree() {}
    UniTree(int size){
        par = vector<int>(size + 1, 0);
        hight = vector<int>(size + 1, 0);
 
        for(int i=0 ;i<=size ;i++ ){
            par[i] = i;
        }
    }
 
    /*____________________________________________________________*/
    // FindSet()
    //  [引数]   
    //          int x   : 親を求めたいノードの番号
    //
    //  [機能]   
    //          ノードxの親を求めながら、再帰的に経路圧縮を行う
    /*_____________________________________________________________*/
    int FindSet(int x){
        if(par[x] != x){
            par[x] = FindSet(par[x]);
        } 
         
        return (par[x]);
    }
 
    /*_______________________________________________________________*/
    // Same()
    //  [引数]   
    //          int x   : ノードx
    //          int y   : ノードy
    //
    //  [機能]   
    //          ノードxとノードyが同じグループならtrue、
    //          そうでなければfalseを返す
    /*_______________________________________________________________*/
    bool Same(int x, int y){
        int X, Y;
 
        X = FindSet(x);
        Y = FindSet(y);
 
        if(X == Y){
            return (true);
        } else {
            return (false);
        }
    }
 
    /*_______________________________________________________________*/
    // Link()
    //  [引数]   
    //          int x   : ノードx
    //          int y   : ノードy
    //
    //  [機能]   
    //          ノードxとノードyが同じグループに属するようにする
    /*_______________________________________________________________*/
    void Link(int x, int y){
        int X, Y;
 
        X = FindSet(x);
        Y = FindSet(y);
 
        if(hight[X] > hight[Y]){
            par[Y] = X;
        } 
        else if(hight[Y] > hight[X]){
            par[X] = Y;    
        } else {
            par[X] = Y;
            hight[Y] = X;
        }
 
        return ;
    }
};


signed main()
{
    int n, m, a, b, ans;
    
    cin >> n >> m;
    UniTree road = UniTree(n);
    
    for ( int i = 0; i < m; i++ ) {
        cin >> a >> b;
        
        road.Link(a, b);
    }
    
    ans = -1;
    for ( int i = 0; i < n; i++ ) {
        if ( road.FindSet(i+1) == i+1 ) {
            ans ++;
        }
    }
    
    cout << ans << endl;
     
    return (0);
}

Measured memory_bytes: 4052
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
//typedef tree<int,null_type,less<int >,rb_tree_tag,tree_order_statistics_node_update>indexed_set;
template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);
#define debug(a) cerr<<#a<<" --> "<<(a)<<endl;
#define fastInput ios_base::sync_with_stdio(false);cin.tie(0)
#define INPUT freopen("input.txt","r",stdin)
#define OUTPUT freopen("output.txt","w",stdout)
#define ERROR  1e-9
#define pi (2*acos(0))
const ll mod = 998244353;
const int N = 2e5 +5;

void SOLVE(int cas)
{
    ll n;
    scanf("%lld",&n);
    vector< pair<ll,ll> >pii(n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld %lld",&pii[i].first,&pii[i].second);
    }
    ll now =0;
    for(ll i=n-1;i>=0;i--)
    {
        ll ff = pii[i].first + now;
        ll ss = pii[i].second;
        if(ff%ss ==0)
            continue;
        ll d = ff/ss;
        d++;
        now+= ss*d - ff;
    }
    printf("%lld\n",now);









}


/*


*/



int main()
{
    //INPUT;
    //OUTPUT;
    int t=1,cas=0;
    //scanf("%d",&t);
    while(t--)
    {
        SOLVE(++cas);
    }

    return 0;
}



//os.order_of_key(v): returns how many elements strictly less than v
//os.find_by_order()

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main(){
	int n,a[10000],q,q1,q2,q3,q3s;
	cin >> n >> q;
	for (int i = 0; i < n; i++){
		a[i] = i;
	}
	for (int i = 0; i < q; i++){
		cin >> q1 >> q2 >> q3;
		if (q1){
			if (a[q2] == a[q3]){
				cout << 1 << endl;
			} else{
				cout << 0 << endl;
			}
		} else {
			q3s = a[q3];
			for (int j = 0; j < n; j++){
				if (a[j] == q3s){
					a[j] = a[q2];
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1200
n=int(input())
m={} 
ans=0
a=list(map(int,input().split()))
for i in range(1,n+1):
	x=a[i-1]
	if i-x in m:
		ans+=m[i-x]
	if i+x in m:
		m[i+x]+=1
	else:
		m[i+x]=1
print(ans)

Measured memory_bytes: 40288
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll N;
  cin >> N;

  string ans="";
  while(N>0){
    int tmp;
    if(N%26==0) tmp=26;
    else  tmp=N%26;

    ans+=(tmp-1+'a');
    N-=tmp;
    N/=26;
  }
  reverse(all(ans));
  cout << ans << endl;

  return 0;
}

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

int main(void){
  std::string S,T,U;
  int A,B;
  std::cin >> S >> T;
  std::cin >> A >> B;
  std::cin >> U;
  if(!U.compare(S)){
    A = A - 1;
  }else{
    B = B - 1;
  }
  std::cout << A << " " << B << std::endl;
  return 0;
}


Measured memory_bytes: 256
// 2014/07/16 Tazoe

#include <iostream>
using namespace std;

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

	int a_min = 1000001;
	int a_max = -1000001;
	long long a_sum = 0;

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

		if(a<a_min){
			a_min = a;
		}

		if(a>a_max){
			a_max = a;
		}

		a_sum += a;
	}

	cout << a_min << ' ' << a_max << ' ' << a_sum << endl;

	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pow(x) x*x
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

using Graph = vector<vector<int>>;
// 入力
int H, W;
vector<vector<char>> field;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};


int main() {

    string S;
    cin >> S;
    ll sum = 0, t = 0;
    vector<int> num(S.size()+1);
    REP(i, S.size()){
        num[i] = stoi(S.substr(i, 1));
    }


    // {0, 1, ..., n-1} の部分集合の全探索
    for (int bit = 0; bit < (1<<S.length()-1); ++bit) {
        t  = num[0];
        for (int i = 0; i < S.length()-1; ++i) {
            if (bit & (1<<i)) { // 列挙に i が含まれるか
                sum += t;
                t = num[i+1];
            } else {
                t *= 10;
                t += num[i+1];
            }
        }
        sum += t;
    }

    cout << sum << endl;

    
    return 0;
}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
        (source = $s:expr, $($r:tt)*) => {
            let mut iter = $s.split_whitespace();
            let mut next = || { iter.next().unwrap() };
            input_inner!{next, $($r)*}
        };
        ($($r:tt)*) => {
            let stdin = std::io::stdin();
            let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
            let mut next = move || -> String{
                bytes
                    .by_ref()
                    .map(|r|r.unwrap() as char)
                    .skip_while(|c|c.is_whitespace())
                    .take_while(|c|!c.is_whitespace())
                    .collect()
            };
            input_inner!{next, $($r)*}
        };
    }

#[allow(unused_macros)]
macro_rules! input_inner {
        ($next:expr) => {};
        ($next:expr, ) => {};

        ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };

        ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = read_value!($next, $t);
            input_inner!{$next $($r)*}
        };
    }

#[allow(unused_macros)]
macro_rules! read_value {
        ($next:expr, ( $($t:tt),* )) => {
            ( $(read_value!($next, $t)),* )
        };

        ($next:expr, [ $t:tt ; $len:expr ]) => {
            (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        };

        ($next:expr, chars) => {
            read_value!($next, String).chars().collect::<Vec<char>>()
        };

        ($next:expr, bytes) => {
            read_value!($next, String).into_bytes()
        };

        ($next:expr, usize1) => {
            read_value!($next, usize) - 1
        };

        ($next:expr, $t:ty) => {
            $next().parse::<$t>().expect("Parse error")
        };
    }

fn main() {
    input! {
            predict: chars,
            actual: chars,
        }

    let mut answer = 0;

    for idx in 0..predict.len() {
        let p = &predict[idx];
        let a = &actual[idx];

        answer += if p == a { 1 } else { 0 }
    }

    println!("{}", answer);
}

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

int main() {
    int K;
    cin >> K; //文字列の長さ
    
    string S;
    cin >> S;
    
    if (S.size() <= K) {
        cout << S;
    } else {
        while (S.size() > K) {
            S.pop_back();
        }
        cout << S + "...";
    }

    return 0;
}

Measured memory_bytes: 3596
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> veci;
typedef vector<long long> vecl;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
	if (y == 0) 
		return 1; 
	ll p = power(x, y/2) % MOD; 
	p = (p * p) % MOD; 
  
	return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
	#ifndef ONLINE_JUDGE
	if (fopen("INPUT.txt", "r"))
	{
		freopen ("INPUT.txt" , "r" , stdin);
		//freopen ("OUTPUT.txt" , "w" , stdout);
	}
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	clock_t clk;
	clk = clock();
//-----------------------------------------------------------------------------------------------------------//

	ll A[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	READV(K);
	cout<<A[K-1]<<endl;

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


	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;
const int mod = 1e9+7;

vll sum_bc;
vll a, b, c;

bool check(ll x, int k) {
    int num = 0;
    rep(i,a.size()) {
        num += sum_bc.end()-lower_bound(all(sum_bc),x-a[i]);
    }
    return num >= k;
}

int main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    a.resize(x); b.resize(y); c.resize(z);
    rep(i,x) cin >> a[i];
    rep(i,y) cin >> b[i];
    rep(i,z) cin >> c[i];
    rep(i,y)rep(j,z) sum_bc.push_back(b[i]+c[j]);
    sort(all(sum_bc));
    ll l = 0;
    ll r = inf_l;
    while (r-l > 1) {
        ll mid = (r+l)/2;
        if (check(mid,k)) l = mid;
        else r = mid;
    }
    vll ans_tmp;
    rep(i,x) {
        ll search = l - a[i];
        for (auto ptr = lower_bound(all(sum_bc),search); ptr != sum_bc.end(); ptr++) {
            ans_tmp.push_back(*ptr+a[i]);
        }
    }
    sort(rall(ans_tmp));
    vll ans;
    ans.assign(ans_tmp.begin(),ans_tmp.begin()+k);
    rep(i,ans.size()) printf("%lld\n",ans[i]);
}

Measured memory_bytes: 140640
#include <stdio.h>
#define MAX 1000
#define INF 100000

int	m[MAX][MAX];
int p[MAX];

int matrixChainOrder(int n){
	int i;
	int j;
	int l;
	int k;
	int q;

	for (i = 1; i < n+1; ++i){
		m[i][i]=0;
	}

	for (l = 2; l < n+1; ++l){
		for (i = 1; i < n-l+2; ++i){
			j = i+l-1;
			m[i][j] = INF;
			for (k = i; k < j; ++k)
			{
				q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
				if (m[i][j]>q){
					m[i][j] = q;
				}
			}
		}
	}

	return m[1][n];
}

int main(){

  	int n;
  	int i;
  	int pEnd;

  	scanf("%d",&n);

  	for(i=0;i<n;i++){
    	scanf("%d%d",&p[i],&pEnd);
  	}

  	p[n] = pEnd;

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

  	return 0;
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    ll ans = 0, sum = 0, r = 0;
    
    rep(i, n) {
        ans += r - i + 1;
        
        if (r == i) {
            sum = a[i];
        }
        else {
            sum -= a[i - 1];
        }
        
        reps(ii, r + 1, n) {
            if ((sum + a[ii]) != (sum ^ a[ii])) {
                r = ii - 1;
                break;
            }
            
            sum += a[ii];
            r++;
            ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <string>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long LL;

int main() {
  LL H, ret = 0, count = 1;
  cin >> H;
  while(H > 0) {
    ret += count;
    H >>= 1;
    count <<= 1;
  }
  cout << ret << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.first+a.second > b.first+b.second; }
vector<int> sieve(int n) {
  vector<int> res(n);
  iota(res.begin(), res.end(), 0);
  for (int i = 2; i*i < n; ++i) {
    if (res[i] < i) continue;
    for (int j = i*i; j < n; j += i)
      if (res[j] == j) res[j] = i;
  }
  return res;
}
vector<int> factor(int n, const vector<int>& min_factor) {
  // min_factor は sieve() で得られたものとする
  std::vector<int> res;
  while (n > 1) {
    res.push_back(min_factor[n]);
    n /= min_factor[n];
  }
  return res;
}
//2,2,2..と素因数を列挙.map型ではないので注意
vector<int> cnt(1000001);
signed main() {
SS(ll,n);
SV(ll,a,n);
ll f=a[0];
rep(i,n)f=__gcd(f,a[i]);
auto min_factor=sieve(1000001);
rep(i,n){
    ll before=1;
for (auto p : factor(a[i],min_factor))
        {
            if(before!=p)cnt[p]++;
            before=p;
        }
}
if(*max_element(all(cnt)) <= 1){
 p("pairwise coprime");
}else if(f==1){
 p("setwise coprime");
}else{
 p("not coprime");
}
}

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

int main() {
    int N,K,count=0;
    cin >> N>>K;
    vector<int> data(N);
    for(int i=0; i<N;i++){
        cin >> data.at(i);
        if(data.at(i)>=K) count++;
    }
    cout << count <<endl;
}

Measured memory_bytes: 640
N=int(input())
K=int(input())
import sys
sys.setrecursionlimit(10**6)
def solve(N, K):
    if K==1:
        l=len(str(N))
        ans=0
        for i in range(l):
            if i!=l-1:
                ans+=9
            else:
                ans+=int(str(N)[0])
        #print(ans)
        return ans
    else:
        nextK=K-1
        l=len(str(N))
        ini=int(str(N)[0])
        res=ini*(10**(l-1))-1
        #print(res)
        if l>=K:
            ans=solve(res, K)
        else:
            ans=0
        if l-1>=nextK:
            nextN=int(str(N)[1:])
            ans+=solve(nextN, nextK)
            return ans
        return ans
ans=solve(N,K)
print(ans)

Measured memory_bytes: 116572
/*input
1700
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	bool MMYY = false;
	bool YYMM = false;
	if ((s[0] - '0') * 10 + (s[1] - '0') <= 12 && (s[0] - '0') * 10 + (s[1] - '0') >= 1)
		MMYY = true;
	if ((s[2] - '0') * 10 + (s[3] - '0') <= 12 && (s[2] - '0') * 10 + (s[3] - '0') >= 1)
		YYMM = true;
	if (MMYY && YYMM)
		cout << "AMBIGUOUS\n";
	else if (MMYY)
		cout << "MMYY\n";
	else if (YYMM)
		cout << "YYMM\n";
	else
		cout << "NA\n";
}

Measured memory_bytes: 256
import sys

s = int(sys.stdin.readline().strip())
a = s
a_all = []
a_all.append(a)

def fnc_odd(n):
    return 3*n+1
    
def fnc_even(n):
    return int(n/2)
    
i = 2

while (i<120):
    if(a%2==0):
        a = fnc_even(a)
        a_all.append(a)
    else:
        a = fnc_odd(a)
        a_all.append(a)
    if(i>3 and a_all[(i-3)-1]==a):
        break
    i += 1
        
print(i)

Measured memory_bytes: 3064
N, K = map(int, input().split())
S = input()

lst = []
b = S[0]
if b == '0':
  lst.append(0)
  
cnt = 1
for i in range(1, len(S)):
  if b != S[i]:
    lst.append(cnt)
    cnt = 1
  else:
    cnt += 1
  b = S[i]
lst.append(cnt)

if b == '0':
  lst.append(0)

l = len(lst)
if K >= l//2:
  print(N)
else:
  tmp = sum(lst[:2*K+1])
  rlt = tmp
  for i in range(2,l-2*K,2):
    tmp += lst[2*K+i-1] + lst[2*K+i] - lst[i-1] - lst[i-2]
    rlt = max(rlt, tmp)
  print(rlt)

Measured memory_bytes: 78976
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
  int i;
  string s[2];
  cin >> s[0] >> s[1];
  for (i=0;i<3;i++) if (s[0][i]!=s[1][2-i]) break;
  if (i==3) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9+7

if n%2 == 0:
    for i in range(n//2):
        if 2*i+1 == a[2*i] == a[2*i+1]:
            ans *= 2
            ans %= mod
        else:
            print(0)
            sys.exit()
    print(ans)
else:
    if a[0] != 0:
        print(0)
        sys.exit()
    for i in range(1, n//2+1):
        if 2*i == a[2*i-1] == a[2*i]:
            ans *= 2
            ans %= mod
        else:
            print(0)
            sys.exit()
    print(ans)
    


Measured memory_bytes: 20576
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

EPS = 1e-9

#http://www.deqnotes.net/acmicpc/2d_geometry/lines
def dot(a, b):
    return a.real * b.real + a.imag * b.imag

def cross(a, b):
    return a.real * b.imag - a.imag * b.real

def distance(a, b, c):
    if dot(b-a, c-a) <= EPS:
        return abs(c-a)
    if dot(a-b, c-b) <= EPS:
        return abs(c-b)
    return abs(cross(b-a, c-a)/(b-a))

K, T = ln()
A = ln()

A.sort(reverse=True)

f = A[0]
S = sum(A) - f

print max(0, f - S - 1)

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


int N, K;
pll sushi[100000];
map<int, int> m;


signed main(){
    cin >> N >> K;
    ll t, d;
    REP(i, N){
        cin >> t >> d;
        t--;
        sushi[i] = {d, t};
    }
    sort(sushi, sushi + N, greater<pint>());
    ll var = 0;
    ll ans, sum = 0;
    REP(i, K){
        sum += sushi[i].first;
        m[sushi[i].second]++;
        if(m[sushi[i].second] == 1) var++;
    }
    sum += var * var;
    ans = sum;
    int j = K - 1;
    FOR(i, K, N){   
        if(m[sushi[i].second] > 0) continue;
        while(m[sushi[j].second] <= 1 && j >= 0) j--;
        if(j < 0) break;
        m[sushi[i].second]++;
        m[sushi[j].second]--;
        sum = sum + sushi[i].first - sushi[j].first + 2 * var + 1;
        j--; var++;
        ans = max(ans, sum);
    }
    PRINT(ans);
    return 0;
}

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

char in[8];
bool get(){
    // cout<<"inside get\n";
    int i=0;
    char c;
    c=getchar();
    // cout<<"first char\n"<<c<<endl;
    while(c != ' ' and c != '\n'){
        if(i>=6) break;
        in[i++] = c;
        c = getchar();
        // cout<<(c==' ')<<endl;
    }
    return c=='\n';
}

int convert(){
    int i=0;
    int out=0;
    while(isdigit(in[i]) and i<7){
        out = out*10 + (in[i++]-'0');
    }
    return out;
}

bool isOp(char c){
    if(c=='+' || c=='-' || c=='*') return true;
    return false;
}
int op(int f, int s, char c){
    if(c=='+') return f+s;
    else if(c=='-') return  s-f;
    else return f*s;
}
int main(){
    stack<int> st;
    // cout<<"start\n";
    while(!get()){
        // cout<<"ok "<<endl;
        if(isOp(in[0])){
            int f = st.top(); st.pop();
            int s = st.top(); st.pop();
            int res = op(f, s, in[0]);
            st.push(res);
        }
        else{
            st.push(convert());
        }
        // cout<<st.top()<<" ";
        memset(in, '#', sizeof in);
    }
    if(isOp(in[0])){
        int f = st.top(); st.pop();
        int s = st.top(); st.pop();
        int res = op(f, s, in[0]);
        st.push(res);
    }
    cout<<st.top()<<endl;
    return 0;
}


Measured memory_bytes: 3120
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List
import Data.List.Split (splitOn)

main :: IO ()
main = do
  (lm, tm) <- gettd . lines <$> getContents
  mapM_ (\(x, y) -> putStrLn $ unwords [show x, show y]) $ solve lm tm

solve :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
solve lm tm = map g isd
  where
    f = map (\x -> ((fst . head) x, length x)) . groupBy (\x y -> fst x == fst y) . sort
    lis = f lm
    tis = f tm
    isd = intersect (map fst lis) (map fst tis)
    g i = (i, x + y)
      where
        (Just x) = lookup i lis
        (Just y) = lookup i tis
        
gettd :: [String] -> ([(Int, Int)], [(Int, Int)])
gettd ss = (f lm, f (tail tm))
  where
    (lm, tm) = span (/= "") ss
    f = map $ (\[x,y] -> (x,y)) . map toInt . splitOn ","

toInt :: String -> Int
toInt s = read s

Measured memory_bytes: 3916
S = int(input())
dp = (S+1)*[0]

for n in range(S+1):
  if 0<=n<=2:
    dp[n] = 0
  elif 3<=n<=5:
    dp[n] = 1
  else:
    dp[n] = (dp[n-3]+dp[n-1])%(10**9+7)

print(dp[S])

Measured memory_bytes: 9160
K, S = [int(i) for i in input().split()]
t = 0
for a in range(K+1):
    for b in range(a, K+1):
        c = S - a - b
        if 0 <= c <= K and c >= a and c >= b:
            if a == b == c:
                t += 1
            elif a == b or b == c:
                t += 3
            else:
                t += 6
print(t)

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

int main(){
    int S,h,M,m,s;
    cin >> S;
    s = S % 60;
    M = S / 60;
    m = M % 60;
    h = M / 60;
    cout << h << ":" << m << ":" << s << endl;
    return 0 ;
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL mod = 1000000007;

LL n, p;


LL C(LL n, LL m){
    LL temp = n - m;
    temp = min(temp, m);
    LL res = 1;
    for(LL i = n, k = 1;k <= temp;k++, i--)
    {
        res *= i;
        res /= k;
    }
    return res;
}

int main(){
    LL ou = 0, ji = 0, x, res;
    scanf("%lld%lld",&n, &p);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(x % 2 == 0) ou++;
        else ji++;
    }
    if(p){
        res = 0;
        for(LL i=1;i<=ou;i++){
            for(LL j = 1;j <= ji; j+=2LL){
                res = res + C(ou, i)* C(ji, j);
            }
        }
        for(int j = 1;j <= ji; j += 2LL){
            res = res + C(ji, j);
        }
    }
    else{
        res = 0;
        for(LL i=1;i<=ou;i++){
            res = res + C(ou, i);
            for(LL j = 2;j <= ji; j+=2LL){
                res = res + C(ou, i)* C(ji, j);
            }
        }
        for(int j = 2;j <= ji; j += 2LL){
            res = res + C(ji, j);
        }
        res = res + 1LL;
    }
    printf("%lld\n",res);
    return 0;
}



Measured memory_bytes: 256
### subroutines

def lower_bound(arr, key)
  lb = - 1
  ub = arr.length - 1

  while lb + 1 < ub
    m = (lb + ub) / 2
    if arr[m] <= key
      ub = m
    else
      lb = m
    end
  end
  ub
end

### main

while true
  n = gets.strip.to_i
  break if n == 0

  as = gets.strip.split(' ').map{|s| s.to_i}.sort{|a, b| b <=> a}
  bs = gets.strip.split(' ').map{|s| s.to_i}.sort{|a, b| b <=> a}

  done = false
  bwin = 0
  k = 1

  while k < n
    pos = lower_bound(bs, as[k - 1] - 1) - 1
    if bwin <= pos
      bwin += 1
    end

    if (k - bwin) > k / 2
      done = true
      break
    end

    k += 1
  end

  puts (done ? k : 'NA')
end

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

using namespace std;

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

int dp[100005];

void search(vector<vector<int>> &edges, int v) {
  if (dp[v] != -1) {
    return;
  }
  if (edges[v].size() == 0) {
    dp[v] = 0;
    return;
  }
  for (int e : edges[v]) {
    search(edges, e);
    chmax(dp[v], dp[e] + 1);
  }
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> edges(N, vector<int>());
  for (int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    edges[x].push_back(y);
  }
  for (int i = 0; i < 100005; i++) {
    dp[i] = -1;
  }
  for (int i = 0; i < N; i++) {
    search(edges, i);
  }
  int ans = 0;
  for (int i = 0; i < 100005; i++) {
    chmax(ans, dp[i]);
  }
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 8192
require 'matrix'


n, m = gets.split.map(&:to_i)

a = n.times.map do
      gets.split.map(&:to_i)
    end

b = m.times.map do
      gets.split.map(&:to_i)
    end

ma = Matrix.rows(a)
mb = Matrix.rows(b)
mc = ma * mb

mc.row_vectors.each {|row| puts row.to_a.join("\s")}


Measured memory_bytes: 9156
#include <bits/stdc++.h>
//#define int long long

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

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = (int)1e9 + 7;

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

    int n, c;
    cin >> n >> c;

    vector<vector<int>> imos(c, vector<int>(100005, 0));
    REP(i, n){
        int s, t, cha;
        cin >> s >> t >> cha;
        cha--;
        imos[cha][s]++;
        imos[cha][t]--;
    }

    REP(i, c) REP(j, 100005) imos[i][j+1] += imos[i][j];
    REP(i, c) REP(j, 100005) if(imos[i][j] == 0 && imos[i][j+1] >= 1) imos[i][j]++;
    REP(i, c-1){
        REP(j, 100005){
            imos[0][j] += imos[i+1][j];
        }
    }
    int ans = 0;
    REP(i, 100005) ans = max(ans, imos[0][i]);
    cout << ans << endl;
}

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

l=r=0
count=0


while any(h)==True:
    for i in range (n):
        if h[i]!=0:
            l = i
            break
    if all(h[l+1:n])==True:
        r = n-1
    else:
        for k in range (l+1,n):
            if h[k] == 0:
                r = k-1
                break

    for s in range (l,r+1):
        h[s] = h[s]-1

    count += 1
print(count)


Measured memory_bytes: 3064
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() { 
    int a,b,c,d,e,f;cin >> a >> b >> c >> d >> e >> f;
    vector<long double> suger;vector<long double> water;
    for(int i = 0;i*a<=f;i+=100){
        for(int j = 0;j*b<=f;j+=100) {
            // if(i==0&&j==0)continue;
            if(i*a+j*b<=f) water.pb(i*a+j*b);
            else break;
        }
    } 
    for(int i = 0;i*c<=f;i++){
        for(int j = 0;j*d<=f;j++) {
            // if(i==0&&j==0)continue;
            if(i*c+j*d<=f) suger.pb(i*c+j*d);
            else break;
        }
    } 
    long double ma = -1;
    P ans;
    for(auto p:water) {
        for(auto q:suger) {
            if(p+q<=f&&p/100*e>=q) {
                if(chmax(ma,q/(p+q))){
                    // cout << "OK\n";
                    ans={p+q,q};
                }
            }
        }
    }
    // cout << water.size() << ' ' << suger.size() << endl;
    cout << ans.first << ' ' << ans.second << endl;
    // cout << ma << endl;
    return 0;
}

Measured memory_bytes: 7200
S = input()
 
 
D = S.count("R")
 
if D == 1:
    print(1)
 
elif D == 3:
    print(3)
 
elif D == 2:
    for i in range(3):
        if S[i] =="R":
            if S[i+1] =="R":
                print(2)
                break
 
            else:
                print(1)
                break
 
elif D == 0:
    print(0)    


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

const int MAXN = 3010;

string s,t;
int dp[MAXN][MAXN],N,M;
stack<char> resposta;

int solve(int a,int b){

	if(a < 0 || b < 0) return 0;

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

	if(s[a] == t[b]) return dp[a][b] = 1 + solve(a-1,b-1);

	return dp[a][b] = max(solve(a-1,b),solve(a,b-1));

}

void build(int a,int b){

	if(a < 0 || b < 0) return;

	if(s[a] == t[b]){
		resposta.push(s[a]);
		build(a-1,b-1);
		return;
	}

	if(solve(a-1,b) > solve(a,b-1)) build(a-1,b);
	else build(a,b-1);

}

int main(){

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

	cin >> s;
	cin >> t;

	N = (int)s.size();
	M = (int)t.size();

	build(N-1,M-1);

	while(!resposta.empty()){
		cout << resposta.top();
		resposta.pop();
	}
	cout << endl;

	return 0;

}

Measured memory_bytes: 39272
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, n;
  cin >> n;
  a = n / 100;
  b = (n - a * 100) / 10;
  c = n - a * 100 - b * 10;
  cout << a + b + c << endl;
}

Measured memory_bytes: 256