akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main() {
  int n;
  cin >> n;
  deque<int> que;
  rep(i, n) {
    int a;
    cin >> a;
    int index = lower_bound(que.begin(), que.end(), a) - que.begin();
    if (index == 0) que.push_front(a);
    else que[index-1] = a;
  }
  int ans = que.size();
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3944
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] h = new long[n];
		for (int i = 0; i < n; i++) {
			h[i] = sc.nextLong();
		}

		int max = 0;
		int count = 0;
		int i = 0;
		while (i < n - 1) {
			if (h[i] >= h[i + 1]) count++;
			else {
				max = Math.max(max, count);
				count = 0;
			}
			i++;
		}

		max = Math.max(max, count);
		System.out.println(max);
	}
}


Measured memory_bytes: 50732
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int maxx = 2e5 + 5;
//int a[101];
int main(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
       ios_base::sync_with_stdio(false);
       cin.tie(0);
  string s,t;
  cin>>s>>t;
  int a ,b;
  cin>>a>>b;
  string u;
  cin>>u;
if(u == s){
	a--;  
}
else{
	b--;
}
cout<<a<<" "<<b;
return 0;
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int

int main(){
int n,k;
cin>>n>>k;
int a[n];
map<int,int>m;
rep(i,n){
cin>>a[i];
m[a[i]]++;
}
vector<pair<int,int>>x;

for(auto i:m){
x.push_back(make_pair(i.second,i.first));

}
sort(x.begin(),x.end());
int ans=0,q=0;
for(int i=x.size();i>k;i--){
ans+=x[q].first;
q++;
}
cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 12536
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string, core.stdc.stdlib;

void main() {
    immutable long INF = 1L << 59;
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto L = s[2].to!long;
    auto G = new long[][](N, N);
    foreach (i; 0..N) foreach (j; 0..N) G[i][j] = i == j ? 0 : INF;
    foreach (_; 0..M) {
        s = readln.split.map!(to!int);
        auto a = s[0] - 1;
        auto b = s[1] - 1;
        auto c = s[2].to!long;
        G[a][b] = c;
        G[b][a] = c;
    }
    auto dist1 = warshall_floyd!(long, INF)(G);

    auto dist2 = new long[][](N, N);
    foreach (i; 0..N) foreach (j; 0..N) dist2[i][j] = i == j ? 0 : INF;
    foreach (i; 0..N) foreach (j; 0..N) if (dist1[i][j] <= L) dist2[i][j] = 1;
    auto dist3 = warshall_floyd!(long, INF)(dist2);

    auto Q = readln.chomp.to!int;
    while (Q--) {
        s = readln.split.map!(to!int);
        auto a = s[0] - 1;
        auto b = s[1] - 1;
        auto ans = dist3[a][b];
        writeln(ans >= INF ? -1 : ans - 1);
    }
}

T[][] warshall_floyd(T, T inf)(const T[][] graph) {
    import std.conv : to;

    int n = graph.length.to!int;
    auto dist = new T[][](n, n);
    foreach (i; 0..n) foreach (j; 0..n) dist[i][j] = graph[i][j];

    foreach (i; 0..n)
        foreach (j; 0..n)
            foreach (k; 0..n)
                if (dist[j][i] != inf && dist[i][k] != inf)
                    dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);

    return dist;
}


Measured memory_bytes: 8828
#include<bits/stdc++.h>
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define forout(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=1e5+1;
int f[N];
int n,k;
int a[N];
main()
{
    cin>>n>>k;
    forinc(i,1,n) cin>>a[i];
    a[0]=0;
    forinc(i,1,n) f[i]=INT_MAX;
    f[0]=0;
    f[1]=0;
    f[2]=abs(a[2]-a[1]);
    forinc(i,3,n)
    {
        forinc(j,1,k)
        {
            if(i-j>0) f[i]=min(f[i-j]+abs(a[i-j]-a[i]),f[i]);
        }
    }
    cout<<f[n];
}


Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>>v(N);
	rep(i, N)cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
	int cnt = 0;
	int money = 0;
	int i = 0;
	while (cnt < M)
	{
		cnt++;
		money += v[i].first;
		v[i].second--;
		if (v[i].second== 0)i++;
	}
	cout << money;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<utility>
#include<math.h>

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

const int INF = 1<<30;

int main(){
  int n;cin>>n;
  vector<ll> a(n), b(n);
  for(int i=0;i<n;i++)cin>>a[i]>>b[i];
  ll ans=0;
  for(int i=n-1;i>=0;i--){
    if((a[i]+ans)%b[i]==0)continue;
    ans += b[i]-(a[i]+ans)%b[i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n, a, b = [int(x) for x in input().strip().split()]
mod = 10 ** 9 + 7
ans = pow(2, n, mod) - 1

fact = [1] * (b + 1)
for i in range(1, b+1):
    fact[i] = (fact[i-1] * i) % mod

inv = [1] * (b + 1)
inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(1, b):
    inv[-1-i] = (inv[-1-i+1] * (b-(i-1))) % mod

def nCr(n, r):
    ret = 1
    for i in range(r):
        ret = (ret * (n - i) % mod) % mod
    return (ret * inv[r]) % mod

ans = (ans - nCr(n, a)) % mod
ans = (ans - nCr(n, b)) % mod
print(ans)

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

int main() {
	// your code goes here
long long l;
cin>>l;
if(l%2==1)
{
    cout<<"0";
    return 0;
}

long long  d=10,cnt=0;
while(d<=l)
{
    cnt+=l/d;
    d=d*5;
}
cout<<cnt;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

int main() {
	string str;
	int *height;
	queue<int> edge;
	int len;
	int pondNum;
	int *pondArea;
	int sumArea;
	int n;
	
	cin>>str;
	len = str.length();
	height = new int[len+1];
	
	
	height[0] = 0;
	for(int i=0;i<len;++i){
		char c = str[i];
		height[i+1] = height[i] + (c=='\\'?-1:(c=='_'?0:1));
	}
			
	pondNum = 0;
	for(int i=0;i<len;++i){
		if(height[i+1]<height[i]){
			for(int j=i+1;j<len+1;++j){
				if(height[j] >= height[i]){
					edge.push(i);
					edge.push(j);
					i = j-1;
					++pondNum;
					break;
				}
			}
		}
	}
	
	pondArea = new int[pondNum];
	n = 0;
	sumArea = 0;
	while(!edge.empty()){
		int st,end,area;
		st = edge.front();
		edge.pop();
		end = edge.front();
		edge.pop();
		
		area = 0;
		for(int i=st;i<end;++i){
			area += (abs(height[st]-height[i])+abs(height[st]-height[i+1]));
		}
		area /= 2;
		pondArea[n] = area;
		sumArea += area;
		++n;
	}
	
	cout<<sumArea<<endl;
	cout<<pondNum<<(pondNum?" ":"");
	for(int i=0;i<pondNum;++i){
		cout<<pondArea[i]<<(i!=pondNum-1?" ":"");
	}
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 1348
#include<stdio.h>
int main()
{
    int W,H,x,y,r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);
    if( (x+r)<=W && (y+r)<=H && x>=r && y>=r){
        printf("Yes\n");
    }
    else {
        printf("No\n");
    }
    return 0;
}



Measured memory_bytes: 2096
#include <stdio.h>
int main() {
	int i;
	int N;
	int H[100000];
	int move = 0;
	int ans = 0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &H[i]);
	}

	for (i = 0; i < N - 1; i++) {
		if (H[i] >= H[i + 1]) {
			move += 1;
			if (move > ans) ans = move;
		} else {
			move = 0;
		}
	}

	printf("%d", ans);

	return 0;
}

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

int main() {
    int N;
    int A[200100];
    int maxVal = 0;
    int maxDuplicatedVal = 0;
    int secondVal = 0;
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i];

    for (int i = 0; i < N; ++i){
        if (maxVal == A[i]) {
            maxDuplicatedVal = maxVal;
        }
        if (maxVal < A[i]) {
            maxVal = A[i];
        }
        if (secondVal < A[i] &&  A[i] < maxVal){
            secondVal = A[i];
        }

    }
    for (int i = 0; i < N; ++i){
        if (A[i] == maxVal) {
            if (secondVal > maxDuplicatedVal) {
                cout << secondVal << endl;
            } else {
                cout << maxDuplicatedVal << endl;
            }
        } else{
            cout << maxVal << endl;
        }
    }
    return 0;
}

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

int c[12], skill[12];
int a[12][12];
int n, m, x;
#define inf (int)2e9

int min_cost(int start) {
	bool ok = true;
	for (int j = 0; j < m; j++) {
		if (skill[j] < x)
			ok = false;
	}
	if (ok)
		return 0;
	int mn = inf;
	for (int i = start; i < n; i++) {
		for (int j = 0; j < m; j++) {
			skill[j] += a[i][j];
		}
		mn = min(mn, c[i] + min_cost(i + 1));
		for (int j = 0; j < m; j++) {
			skill[j] -= a[i][j];
		}
	}
	return mn;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	}
	int ans = min_cost(0);
	if (ans >= inf)
		cout << "-1\n";
	else 
		cout << ans << '\n';
}



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

using namespace std;

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

    int c0=0,c1=0;
    for (int i=0;i<S.length();i++) {
        S[i]=='0' ? c0++ : c1++;
    }
    cout << 2 * min(c0, c1) << endl;

    return 0;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x, y) CPP_CAT_I(x, y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x, y) x##y
#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = __float80;

constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;

#define FOR(i, start, end) for (i64 i = (start), CPP_CAT(i, xxxx_end) = (end); i < CPP_CAT(i, xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

#define ALL(f, c, ...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ##__VA_ARGS__); })(c))

template <typename C>
i64 SIZE(const C &c)
{
    return static_cast<i64>(c.size());
}

template <typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }

template <typename T, typename U, typename Comp = less<>>
bool chmax(T &xmax, const U &x, Comp comp = {})
{
    if (comp(xmax, x))
    {
        xmax = x;
        return true;
    }
    return false;
}

template <typename T, typename U, typename Comp = less<>>
bool chmin(T &xmin, const U &x, Comp comp = {})
{
    if (comp(x, xmin))
    {
        xmin = x;
        return true;
    }
    return false;
}

struct ProconInit
{
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit()
    {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

signed main()
{

    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    if (s == "AAA" || s == "BBB")
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();


		if(n < 1000) {

			System.out.println("ABC");
		} else {
			System.out.println("ABD");

		}

	}

}


Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <utility>
using namespace std;

int N, H, A[100000], B[100000];


int main(){
	int ans = 0;
	cin >> N >> H;
	
	for(int i = 0; i<N; i++){
		cin >> A[i] >> B[i];
	}
	
	//	A[i]の最大値を求める
	int max_a = 0;
	for(int i = 0; i<N; i++){ 
		if (A[i] > max_a){ max_a = A[i]; }
	}
	
	//max_aより強い"投げ刀"を投げる
	sort(B, B+N); 
	int i = N-1;
	while(B[i] > max_a && H>0){
		H -= B[i]; i--; ans++;
	}
	
	//max_aの振り刀を倒すまで振る
	while (H>0){
		H -= max_a; ans++;
	}
	
	cout << ans << endl;
	
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_str(char *str, int size)
{
    char format[100];
    if (size == 0)
        return 0;
    snprintf(format, sizeof(format), "%%%ds", size);
    scanf(format, str);
    return 0;
}

#define STR_MAX 100000
#define BUF_SIZE (STR_MAX+50)

struct pair {
    int cnt;
    char idx;
    struct pair *left;
    struct pair *right;
};

#define ROOT_NODE 1
#define HEAP_MAX 50
static struct pair *heap[HEAP_MAX];
static int hidx = ROOT_NODE;

// min-heap
int cmp(struct pair *a, struct pair *b) {
    return a->cnt < b->cnt;
}

void swap(struct pair **a, struct pair **b) {
    struct pair *tmp = *a;
    *a = *b;
    *b = tmp;
}

void enqueue(struct pair *val) {
    int node = hidx;
    heap[hidx++] = val;
    int parent;
    while((parent = node/2)) {
        if(cmp(heap[parent], heap[node])) break;
        swap(&heap[parent], &heap[node]);
        node = parent;
    }
    return;
}

struct pair *get_min(void) {
    struct pair* ans = heap[ROOT_NODE];
    heap[ROOT_NODE] = heap[--hidx];
    int node = ROOT_NODE;
    while(1) {
        int cur = node;
        int left = node*2;
        int right = node*2+1;
        if(left < hidx && !cmp(heap[cur], heap[left])) cur = left;
        if(right < hidx && !cmp(heap[cur], heap[right])) cur = right;
        if(cur == node) break;
        swap(&heap[node], &heap[cur]);
        node = cur;
    }
    return ans;
}

int get_count(void) {
    return hidx-1;
}

void get_depth(struct pair *node, int val, int *out) {
    if(node->idx != -1) out[node->idx] = val;
    if(node->left) get_depth(node->left, val+1, out);
    if(node->right) get_depth(node->right, val+1, out);
    return;
}

struct pair *create_pair(int cnt) {
    static struct pair pool[100];
    static int pidx = 0;
    struct pair *p = &pool[pidx++];
    p->cnt = cnt; p->idx = -1;
    return p;
}

int main(void) {
    char str[BUF_SIZE];
    get_str(str, BUF_SIZE);
    int len = strlen(str);

    int map[26] = {0};
    int i;
    int kinds = 0;
    for(i = 0; i < len; i++) {
        map[str[i] - 'a']++;
    }

    struct pair ps[26];
    for(i = 0; i < 26; i++) {
        if(!map[i]) continue;
        kinds++;
        ps[i] = (struct pair){map[i], i, NULL, NULL};
        enqueue(&ps[i]);
    }
    int ans = 0;
    if(kinds==1) {
        ans = len;
        goto finish;
    }

    while(get_count() > 1) {
        struct pair *p1 = get_min();
        struct pair *p2 = get_min();
        struct pair *np = create_pair(p1->cnt + p2->cnt);
#ifdef DEBUG
        printf("%d %d\n", p1->cnt, p2->cnt);
#endif
        np->left = p1; np->right = p2;
        enqueue(np);
    }
    int codes[26] = {0};
    struct pair *root = heap[ROOT_NODE];
    get_depth(root, 0, codes);

    for(i = 0; i < 26; i++) {
        ans += codes[i]*map[i];
    }
finish:
    printf("%d\n", ans);

    return 0;
}


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

struct goods{
  int weit;
  int value;
};
goods g[100];

int n,w;
int dtp[101][10001];
int rec(int now_g,int capa){
  if(dtp[now_g][capa]!=-1){
    return dtp[now_g][capa];
  }

  int total_val;
  if(now_g==n){
    total_val=0;
  }else if(capa<g[now_g].weit){
    total_val=rec(now_g+1,capa);
  }else{
    total_val=max(
      rec(now_g+1,capa),
      rec(now_g+1,capa-g[now_g].weit)+g[now_g].value
    );
  }
  return dtp[now_g][capa]=total_val;
}

int main(void){
  cin>>n>>w;
  for(int i=0;i<n;i++){
    cin>>g[i].value>>g[i].weit;
  }
  // int dp[n][w];
  for(int k=0;k<101;k++){
    for(int i=0;i<10001;i++){
      dtp[k][i]=-1;
    }
  }
  // for(int i=0;i<w;i++){
  //   dtp[i]=&(*dp)[i];
  // }
  cout <<rec(0,w)<<endl;
}



Measured memory_bytes: 7036
import collections
def resolve():
    N = int(input())
    S = [input() for i in range(N)]
    ans = 0

    for i in range(N):
        S[i]=str(sorted(S[i]))
    c = collections.Counter(S)
    for i in c.values():
        for j in range(1,i):
            ans += j
    print(ans)
    
resolve()

Measured memory_bytes: 24560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String t = sc.nextLine();

		int count = 0; 
		
		for(int i=0; i < s.length(); i++) {
			if(t.charAt(i) != s.charAt(i)) {
				count++;
			}
		}
		
		System.out.println(count);
		
	}

}

Measured memory_bytes: 42364
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	string str;
	cin >> str;
	for(int i=0;i<3;i++) {
		if (str[i] == '7') {
			cout << "Yes" <<endl;
			return 0;
		}
	}
			cout << "No" <<endl;
			return 0;
	return 0;
}


Measured memory_bytes: 3040
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

int main(){
  int N;
  cin>>N;
  VI X(100);
  rep(i,N){
    int Y=i+1;
    rep(j,10){
      rep(k,i){
        if(Y%(k+2)==0){
          X[k+1]++;
          Y/=(k+2);
          break;
        }
      }
    }
  }
  sort(all(X));
  int n2=X.end()-lower_bound(all(X),2);
  int n4=X.end()-lower_bound(all(X),4);
  int n14=X.end()-lower_bound(all(X),14);
  int n24=X.end()-lower_bound(all(X),24);
  int n74=X.end()-lower_bound(all(X),74);
  ll ans=0;
  ans+=max(0,n4*(n4-1)/2*(n2-2));
  ans+=max(0,n14*(n4-1));
  ans+=max(0,n24*(n2-1));
  ans+=max(0,n74);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
result = 0
sorted_a = sorted(a)
remain = x
for a_i in sorted_a:
    if remain >= a_i:
        result += 1
        remain -= a_i
    else:
        break

### 最後の子供にぴったりのお菓子をあげられなかった
if result == N and remain != 0:
    result -= 1
print(result)

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <iomanip>

using namespace std;

int main()
{
  int n;
  int a[10000];
  int i;
  int min;
  int max;
  long long sum=0;
  
  cin >> n;
  
  for(i=0;i<n;i++)
    {
    cin >> a[i];
    sum=sum+a[i];
    }
  
  max=a[0];
  min=a[0];
  
  for(i=0;i<n;i++)
    {
    if(a[i]<=min)
      min=a[i];
    if(a[i]>=max)
      max=a[i];
    }
  
  cout << min <<" "<< max <<" "<< sum <<"\n";
}

Measured memory_bytes: 1204
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;

	Int k;
	cin >> k;

	Int ans = 1;
	for (Int i = 0; i < k; i++) {
		if (s[i] - '0' != 1) {
			ans = s[i] - '0';
			break;
		}
	}
	cout << ans << endl;
}

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

typedef tuple<int,int,int> edge;
int n,m;
vector<edge> graph;

const int nmax=510;
int par[nmax];
void init(){rep(i,nmax) par[i]=i;}
int find(int x){return (par[x]==x)?x:par[x]=find(par[x]);}
void unite(int a,int b){ a=find(a),b=find(b),par[a]=b;}
bool same(int a,int b){return find(a)==find(b);}

bool used[50010];

int main(void){
	cin >> n >> m;
	rep(i,m){
		int a,b,c;
		cin >> a >> b >> c;
		graph.push_back(edge(c,a,b));
	}
	sort(graph.begin(),graph.end());

	int mst=0;
	init();
	rep(i,m){
		int c,a,b;
		tie(c,a,b)=graph[i];
		if(same(a,b)) continue;
		used[i]=true;
		unite(a,b);
		mst+=c;
	}

	int num=0,sum=0;
	rep(i,m){
		if(!used[i]) continue;
		init();
		int cur=0;
		rep(j,m){
			if(j==i) continue;
			int c,a,b;
			tie(c,a,b)=graph[j];
			if(same(a,b)) continue;
			unite(a,b);
			cur+=c;
		}
		if(cur!=mst) num++,sum+=get<0>(graph[i]);
	}
	cout << num << " " << sum << endl;
	return 0;
}

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

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

  int ans = 0;
  rep(i, s.size()) {
    if (s[i] == t[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)

def solve():
  ans = []
  N, Q = map(int, input().split())
  data0 = BIT(N+1)
  data1 = BIT(N+1)
  for i in range(Q):
    p,*y = map(int, input().split())
    if p==0:
      l,r,x = y
      data0.add(l,-x*(l-1))
      data0.add(r+1,x*r)
      data1.add(l,x)
      data1.add(r+1,-x)
    else:
      r = y[0]
      ans.append(data1.sum(r)*r+data0.sum(r)-data1.sum(r-1)*(r-1)-data0.sum(r-1))
  return ans
print(*solve(),sep='\n')




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

using namespace std;


int X, Y, A, B, C;
vector<long long>p, q, r;

int main()
{
	cin >> X;
	cin >> Y;
	cin >> A;
	cin >> B;
	cin >> C;
	
	p = vector<long long>(A);
	q = vector<long long>(B);
	r = vector<long long>(C);

	for (int i = 0; i < A; i++) {
		cin >> p[i];
	}
	for (int i = 0; i < B; i++) {
		cin >> q[i];
	}
	for (int i = 0; i < C; i++) {
		cin >> r[i];
	}

	long long ans = 0;

	sort(p.begin(),p.end(),greater<long long>());
	sort(q.begin(),q.end(), greater<long long>());
	sort(r.begin(),r.end(), greater<long long>());

	int a = 0;
	int b = 0;
	int c = 0;

	for (;a < X;a++) {
		ans += p[a];
	}
	for (; b < Y; b++) {
		ans += q[b];
	}
	a--;
	b--;

	while (c<C) {
		long long next = ans;

		if (a>=0 && (b<0 || p[a] < q[b])) {
			next -= p[a];
			a--;
		}
		else if(b>=0){
			next -= q[b];
			b--;
		}
		else {
			break;
		}
		next += r[c];
		c++;

		if (next <= ans) {
			break;
		}

		ans = next;
	}


	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#define int long long
using namespace std;

signed main(){
    int max=1e18;    
    int N;
    cin>>N;
    vector<int> A(N);  
    int ans=1;
    for(int i=0;i<N;i++){
        cin>>A[i];
        if(A[i]==0){
            cout<<0<<endl;
            return 0;
        }
    }
    for(int i=0;i<N;i++){
        if(A[i]>max/ans){
            cout<<-1<<endl;
            return 0;
        }
        ans*=A[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int T[2],A[2],B[2];
    cin >> T[0] >> T[1] >> A[0] >> A[1] >> B[0] >> B[1];

    if(A[0] > B[0] and A[1] > B[1]){
        cout << 0 << endl;
        return 0;
    }
    if(A[0] < B[0] and A[1] < B[1]){
        cout << 0 << endl;
        return 0;
    }

    if(A[0] * T[0] < B[0] * T[0]){
        swap(A[0],B[0]);
        swap(A[1],B[1]);
    }
    
    if(A[0] * T[0] + A[1] * T[1] > B[0] * T[0] + B[1] * T[1]){
        cout << 0 << endl;
        return 0;
    }

    if(A[0] * T[0] + A[1] * T[1] == B[0] * T[0] + B[1] * T[1]){
        cout << "infinity" << endl;
        return 0;
    }
    int sa0 = A[0] * T[0] - B[0] * T[0];
    int sa1 = - (A[0] * T[0] + A[1] * T[1] - B[0] * T[0] - B[1] * T[1]);
    cout << 1 + 2 * int(sa0/ sa1) - int(sa0 %sa1 == 0)<< endl;



}

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

int main() {
    int X,N;
    cin >> X >> N;
    map<int,int> map;
    rep(i,N){
        int p;
        cin >> p;
        map[p] = 1;
    }
    if(N == 0){
        cout << X << endl;
        return 0;
    }
    for(int i=0;;i++){
        if(map[X-i] != 1){
            cout << X-i << endl;
            return 0;
        }
        if(map[X+i] != 1){
            cout << X+i << endl;
            return 0;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3632
INFO=int(input())
DATA=list(map(int, input().split(" ")))
DATA=sorted(DATA)
def Euclidean(m,n):
    while n!=0:
        temp = n
        n = m%n
        m=temp
    return m
    
output=DATA[0]
for i in range(1,INFO):
    output = Euclidean(DATA[i], output)

print(output)

Measured memory_bytes: 14224
n,a,b=gets.split.map(&:to_i)
s=gets.chomp.split(//)

s.each do |c|
    if c=='a' and a+b>0
        puts "Yes"
        a-=1
    elsif c=='b' and a+b>0 and b>0
        puts "Yes"
        b-=1
    else
        puts "No"
    end
end

Measured memory_bytes: 9852
#include <iostream>
using namespace std;
int main(void){
    string s;
    cin >> s;
    long ans = 0;
    int n = s.size();
    
    for(int i = 0;i < 1 << (n - 1);i++){
          long a = s[0] - '0';
          long b = 0;
          
          for(int j = 1;j < n;j++){
                if(i >> (j - 1) & 1){
                      b += a;
                      a = s[j] - '0';
                }else{
                      a = a * 10 + (s[j] - '0');
                }
          }
          b += a;
          ans += b;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int N= sc.nextInt();
		int l[]=new int[N];
		int r[]=new int [N];
		for(int i=0;i<N;i++) {
			l[i]=sc.nextInt();
			r[i]=sc.nextInt();
		}
		
		int c=0;
		
		for(int i=0;i<N;i++) {
			c+=r[i]-l[i]+1;
		}
		
		System.out.println(c);
		
	}
}


Measured memory_bytes: 27396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> using Graph = vector<vector<T>>;

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (__typeof(a.begin()) x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define endl '\n'

int N, T;
int l, r;
int imos[100005];

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

  cin >> N >> T;
  rep(loop, N) {
    cin >> l >> r;
    imos[l]++;
    imos[r]--;
  }

  REP(i, 1, T + 1) imos[i] += imos[i - 1];

  int ans = 0;
  rep(i, T + 1) ans = max(ans, imos[i]);

  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 3588
!function(t){var r={};function n(e){if(r[e])return r[e].exports;var o=r[e]={i:e,l:!1,exports:{}};return t[e].call(o.exports,o,o.exports,n),o.l=!0,o.exports}n.m=t,n.c=r,n.d=function(t,r,e){n.o(t,r)||Object.defineProperty(t,r,{enumerable:!0,get:e})},n.r=function(t){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(t,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(t,"__esModule",{value:!0})},n.t=function(t,r){if(1&r&&(t=n(t)),8&r)return t;if(4&r&&"object"==typeof t&&t&&t.__esModule)return t;var e=Object.create(null);if(n.r(e),Object.defineProperty(e,"default",{enumerable:!0,value:t}),2&r&&"string"!=typeof t)for(var o in t)n.d(e,o,function(r){return t[r]}.bind(null,o));return e},n.n=function(t){var r=t&&t.__esModule?function(){return t.default}:function(){return t};return n.d(r,"a",r),r},n.o=function(t,r){return Object.prototype.hasOwnProperty.call(t,r)},n.p="",n(n.s=0)}([function(t,r,n){"use strict";function e(t,r){return function(t){if(Array.isArray(t))return t}(t)||function(t,r){if("undefined"==typeof Symbol||!(Symbol.iterator in Object(t)))return;var n=[],e=!0,o=!1,i=void 0;try{for(var u,l=t[Symbol.iterator]();!(e=(u=l.next()).done)&&(n.push(u.value),!r||n.length!==r);e=!0);}catch(t){o=!0,i=t}finally{try{e||null==l.return||l.return()}finally{if(o)throw i}}return n}(t,r)||function(t,r){if(!t)return;if("string"==typeof t)return o(t,r);var n=Object.prototype.toString.call(t).slice(8,-1);"Object"===n&&t.constructor&&(n=t.constructor.name);if("Map"===n||"Set"===n)return Array.from(n);if("Arguments"===n||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n))return o(t,r)}(t,r)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}()}function o(t,r){(null==r||r>t.length)&&(r=t.length);for(var n=0,e=new Array(r);n<r;n++)e[n]=t[n];return e}function i(t){var r=t.split("\n");""==r[r.length-1]&&r.pop(),this.l=r,this.y=0}i.prototype.ints=function(){return this.l[this.y++].split(" ").map((function(t){return+t}))},i.prototype.intv=function(){var t=this.y;return this.y=this.l.length,this.l.slice(t).map((function(t){return+t}))},i.prototype.strv=function(){var t=this.y;return this.y=this.l.length,this.l.slice(t)},i.prototype.strn=function(t){var r=this.y;return this.y+=t,this.l.slice(r,r+t)};var u=new i(n(1).readFileSync("/dev/stdin","utf8"));!function(){var t,r,n=e(u.ints(),2);t=n[0],r=n[1];for(var o=u.strn(t),i=u.strn(r),l=0;l<t;++l)for(var f=0;f<t;++f)if(!(l+r-1>=t||f+r-1>=t)){for(var a=!0,c=0;c<r&&a;c++)for(var s=0;s<r&&a;s++)a=a&&o[l+c][f+s]==i[c][s];if(a)return console.log("Yes"),0}console.log("No")}()},function(t,r){t.exports=require("fs")}]);

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

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

ll n;
vector<ll> a(100000);

int main(int argc, char **argv)
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];

	ll ans = 0;
	for (int i = 0; i < n; ++i)
		ans = GCD(ans, a[i]);

	std::cout << ans << std::endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
#include<set>
using namespace std;


const long long int mod=1000000007;
const long long int INF=99999999999999999;

long long int D,E;

int main() {
	cout << fixed << setprecision(18);
	cin>>D>>E;
	
	while(D!=0){
		long double res=INF;
		for(int i=0;i<=D;i++){
			res=min(res,abs(sqrt((long double)(i*i)+(long double)(D-i)*(D-i))-E));
		}
		cout<<res<<endl;
		cin>>D>>E;
	}
} 


Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define strall(v) (v).cbegin(),(v).cend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
 ll x;
 cin >> x;
 ll fh_coin = x/500;
 x-=(fh_coin*500);
 ll f_coin = x/5;
 ll ans = fh_coin * 1000 + f_coin * 5;
 cout << ans << endl;
 

}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
#define ull unsigned long long
#define MOD 10007
int main()
{
	//----------------------------------------------------------------
	ull dp[1005][8] = { 0 };// dp[i][j]1=i??\??????????????????J???bit??§?????????
	int n;//??\??°
	int responsible[1005] = { 0 };//????????\?????¬??????
	//----------------------------------------------------------------
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;
		if (c == 'J')responsible[i] = 4;
		else if (c == 'O')responsible[i] = 2;
		else responsible[i] = 1;
	}
	//----------------------------------------------------------------
	int s = 4 | responsible[0];
	for (int i = 1; i<8; i++)
	{
		if (s == (i&s))dp[0][i] = 1;
	}
	//dp[0][4] = 1;
	//----------------------------------------------------------------
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j < 8; j++)
		{
			if (responsible[i] & j)
			{
				//cout<<j<<endl;
				for (int k = 1; k < 8; k++)
				{
					if (k&j)
					{
						// cout<<k<<endl;
						dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD;
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i < 8; i++)ans = (ans + dp[n-1][i]) % MOD;
	cout << ans << endl;
}

Measured memory_bytes: 3156
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            BigInteger a=sc.nextBigInteger();
            BigInteger b=sc.nextBigInteger();
            BigInteger ans=a.add(b);
            if(ans.toString().length()<=80){
                System.out.println(ans);
            }else{
                System.out.println("overflow");
            }
        }
        sc.close();
    }
}

Measured memory_bytes: 18524
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
string s;
ll n;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    n = s.size();
    ll dp[n + 1][2]; //j=0繰り下がりなし
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            dp[i][j] = LINF;
        }
    }
    reverse(ALL(s));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++)
    {
        ll temp = s[i] - '0';
        dp[i + 1][0] = min(dp[i][0] + temp, dp[i][1] + temp + 1);
        dp[i + 1][1] = min(dp[i][0] + 10 - temp, dp[i][1] + 10 - temp - 1);
    }
    cout << min(dp[n][0], dp[n][1] + 1) << "\n";
}


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

int main(){
  int n;
  ll x;
  cin>>n>>x;
  ll vec[n];
  for(int i=0;i<n;i++){
    cin>>vec[i];
  }
  ll sum=1e15,p=0;
  ll ans[n];
  for(int i=0;i<n;i++){
    p=0;
    if(i==0){
      for(int j=0;j<n;j++){
        ans[j]=vec[j];
        p+=ans[j];
      }
      sum=min(sum,p);
    }
    else{
      for(int j=0;j<n;j++){
        ans[j]=min(ans[j],vec[(j-i+n)%n]);
        p+=ans[j];
      }
      sum=min(sum,p+x*i);
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int n,a;
	cin >> n >> a;
	int b;
	b = n % 500;
	if (a >= b) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>          // printf(), scanf()
#include <stdlib.h>         // abs()
#include <string.h>         // memset()
#include <stdbool.h>

#define MAX_N 16
#define MAX_S (1 << MAX_N)

const double INF = 1e10;

int n;
int s[MAX_N], l[MAX_N], v[MAX_N];
double dp[MAX_N][MAX_S];
int w[MAX_N][MAX_S];
short prev[MAX_N][MAX_S][2];
int ord[MAX_N];

int
main(int argc, char **argv)
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d%d%d", &s[i], &l[i], &v[i]);

	memset(prev, -1, sizeof(prev));
	int S = 1;
	for (int i = 0; i < n; i++, S <<= 1)
		w[i][S] = v[i];

	int e = 1 << n;
	for (int k = 0; k < e; ++k)
	{
		S = 1;
		for (int i = 0; i < n; ++i, S <<= 1)
		{
			if (k & S)
				continue;

			int t = k | S;
			for (int j = 0; j < n; ++j)
			{
				if (i == j || w[j][k] == 0)
					continue;

				int d = abs(l[i] - l[j]);
				double x = dp[j][k] + (d * (7 + 2 * w[j][k])) / 200.0;
				if (dp[i][t] == 0 || x < dp[i][t])
				{
					dp[i][t] = x;
					w[i][t] = w[j][k] + v[i];
					prev[i][t][0] = j;
					prev[i][t][1] = k;
				}
			}
		}
	}

	double min = INF;
	int u = 0;
	for (int i = 0; i < n; ++i)
	{
		double y = dp[i][e - 1];
		if (y == 0)
			continue;

		if (y < min)
			min = y, u = i;
	}

	ord[0] = u;
	int v = e - 1;
	for (int k = 1; k < n; ++k)
	{
		ord[k] = prev[u][v][0];
		v = prev[u][v][1];
		u = ord[k];
	}

	for (int i = n - 1; i >= 0; --i)
		printf("%d%c", s[ord[i]], (i != 0) ? ' ' : '\n');

	return 0;
}

Measured memory_bytes: 10996
#![allow(unused_mut)]
#![allow(non_snake_case)]
#![allow(unused_macros)]
#![allow(unused_variables)]
#![allow(unused_imports)]
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
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)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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, usize1) => {
        read_value!($next, usize) - 1
    };

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

macro_rules! max {
    ($x: expr) => ($x);
    ($x: expr, $($y: expr),+) => {
        ::std::cmp::max($x, max!($($y),+))
    };
}

macro_rules! min {
    ($x: expr) => ($x);
    ($x: expr, $($y: expr),+) => {
        ::std::cmp::min($x, max!($($y),+))
    };
}

use std::cmp;
use std::collections::{HashSet, BinaryHeap, VecDeque};
use std::iter::FromIterator;
fn main() {
    input!{
        S: chars
    }
    S.reverse();
    let mut s = S.into_iter().collect::<String>();
    s.push_str("$");
    let mut ss = s.as_str();
    while ss.len() > 1 {
        if ss.starts_with("maerd") {
            ss = &ss[5..];
        } else if ss.starts_with("remaerd") {
            ss = &ss[7..];
        } else if ss.starts_with("esare") {
            ss = &ss[5..];
        } else if ss.starts_with("resare") {
            ss = &ss[6..];
        } else {
            println!("NO");
            return;
        }
    }
    println!("YES");
}

Measured memory_bytes: 4352
n = int(input())
a = list(map(int,input().split()))
s = 0
x = {}
x[0] = 1
for i in range(n):
  s += a[i]
  if s not in x.keys():
    x[s] = 1
  else:
    x[s] += 1
ans = 0
for j in x.values():
  ans += j*(j-1)//2
print(ans)
  

Measured memory_bytes: 124232
#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 1001001001
typedef pair<int,int> P;
#define mod 1000000007

int main(){
    int n;
    bool flag=true;
    cin >> n;
    vector<string>a(n);
    rep(i,n){
        string s;
        cin >> s;
        a[i]=s;
        if(i!=0){
            if(s.front()!=a[i-1].back()) flag=false;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]==a[j]) flag=false;
        }
    }
    if(flag) cout << "Yes" <<endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define p(x) cout<<(x)<<endl;
#define pv(v) for(auto a: v){ cout << a << endl; }

int main() {
  int h,w; cin >> h >> w;
  vector <string> ls(h);
  rep(i, h){
    cin >> ls[i];
  }

  rep(i, w+2) {
    if (i == w+1)cout << "#" << endl;
    else cout << "#";
  }
  
  rep(i, h) {

    cout << "#" << ls[i] << "#" << endl;
  }

  rep(i, w+2) {
    if (i == w+1)cout << "#" << endl;
    else cout << "#";
  }
}


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

int main(){
  int N,sum;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
    for(;;){
      if(a.at(i)%2==1)break;
      sum++;
      a.at(i)=a.at(i)/2;
    }
  }
  cout<<sum<<endl;
  
}

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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  if(s[s.size()-1] == 's') s += "es";
  else s += "s";
  cout << s;
}


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

int main() {
    int n, A[10001], q, T[501], key;
    int c = 0;

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

    for (int i = 0; i < q; i++) {
        key = T[i];
        A[n] = key;
        int j = 0;
        while (A[j] != key) {
            j++;
        }
        if (j != n) {
            c++;
        }
    }
    cout << c << endl;
}



Measured memory_bytes: 3140
// Author:: Mohammad Faisal
#include<bits/stdc++.h>
using namespace std;

int main(){

  int n;
  cin >> n;
  int firstplace = n%10;
  if(firstplace==3)
    cout<<"bon";
  else if(firstplace==0 || firstplace==1 || firstplace==6 || firstplace==8)
    cout<<"pon";
  else
    cout<<"hon";
	
  return 0; 
}

Measured memory_bytes: 3604
#pragma GCC target ("arch=ivybridge,tune=ivybridge")
#include <cstdio>
#include <vector>
#include <utility>
#include <map>

/*
\cap_{u,v} \cup_{i\in (u,v) path} E_i

g(N) = |{E | {u,v\in M | \cup_{i\in (u,v) path} E_i} = N}|
G(N) = |{E | {u,v\in M | \cup_{i\in (u,v) path} E_i} \subseteq N}|
     = |{E | {u,v\in M-N | \cap_{i\in (u,v) path} !E_i}}|
*/

int n, m;
std::vector<int> E[50];

long long int M[20];
long long int A[1<<20];
std::map<std::pair<int, int>, int> edges;

long long int dfs(int u, int v, int p){
  if(u == v) return 0;
  for(int x: E[u]){
    if(x == p) continue;
    long long int b = dfs(x, v, u);
    if(b != -1) return (1LL << edges[{u, x}]) | b;
  }
  return -1;
}

int main(){
  scanf("%d", &n);
  for(int i = 0; i < n-1; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    E[a-1].push_back(b-1);
    E[b-1].push_back(a-1);
    edges[{a-1,b-1}] = i;
    edges[{b-1,a-1}] = i;
  }
  scanf("%d", &m);
  for(int i = 0; i < m; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    M[i] = dfs(a-1, b-1, -1);   
  }
  long long int ans = 1LL << (n-1);
  for(int i = 1; i < (1<<m); i++){
    A[i] = A[i&(i-1)] | M[__builtin_ctzll(i)];
    long long int x = 1LL << (n-1-__builtin_popcountll(A[i]));
    ans += (1-2*__builtin_parity(i))*x;
  }

  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
 
 
int main()
{
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> cards(N + M);
	for (int i = 0; i < N; i++)
	{
		int temp = 0;
		cin >> temp;
		cards[i] = make_pair(temp, 1);
	}
	for (int i = N; i < M + N; i++)
	{
		int a, b;
		cin >> a >> b;
		cards[i] = make_pair(b, a);
	}
	sort(cards.begin(), cards.end());
	reverse(cards.begin(), cards.end());
	N = N;
	long long added = 0;
	long long sum = 0;
	int counter = 0;
	while (added != N)
	{
		//cards[looking]は、lookingが書かれたカードの枚数
		//card は カードに書かれた整数
		long long card = cards[counter].first;
		long long quantity = cards[counter].second;
		if (added + quantity < N)
		{
			if (quantity != 1)
			{
				added += quantity;
				sum += quantity * card;
			}
			else
			{
				added++;
				sum += card;
			}
		}
		else if (added + quantity == N)
		{
			added += quantity;
			sum += quantity * card;
			break;
		}
		else
		{
			long this_quantity = N - added;
			sum += this_quantity * card;
			break;
		}
		counter++;
	}
	cout << sum << endl;
  	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main (){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if(1<=a,b,c && a,b,c<=10000){
		if(a<=b && b<=c){
		printf("%d %d %d\n",a,b,c);
		}else if(a<=c && c<=b){
		printf("%d %d %d\n",a,c,b);
		}else if(b<=a && a<=c){
		printf("%d %d %d\n",b,a,c);
		}else if(b<=c && c<=a){
		printf("%d %d %d\n",b,c,a);
		}else if(c<=a && a<=b){
		printf("%d %d %d\n",c,a,b);
		}else if(c<=b && b<=a){
		printf("%d %d %d\n",c,b,a);
		}
	}else{
	printf("NOT\n");
	}
	return 0;
}

Measured memory_bytes: 596
N = int(input())

if N == 3:
  print(2)
  print(1, 3)
  print(2, 3)
  exit()

if N == 4:
  print(4)
  print(1, 2)
  print(1, 3)
  print(2, 4)
  print(3, 4)
  exit()


L = []
M = 0
if N % 2 == 1:
  L.append([N])
  N -= 1

for i in range(1, N // 2 + 1):
  L.append([i, N + 1 - i])



M += 2 * N

print(M)
for i in range(len(L)):
  for j in L[i]:
    for k in L[i - 1]:
      print(j, k)



Measured memory_bytes: 3064