akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

class Main {
	Scanner sc = new Scanner(System.in);

	public void run() {
		while (true) {
			int H = sc.nextInt(), W = sc.nextInt();
			if (H == 0 && W == 0) {
				break;
			}
			for (int h = 0; h < H; h++) {
				for (int w = 0; w < W; w++) {
					pr((h+w)%2==0 ? "#"
							: ".");
				}
				ln();
			}
			ln();
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

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

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

string bd[500];

int main() {
	int H,W;
	cin >> H >> W;
	for (int c=0;c<H;c++) cin >> bd[c];
	for (int i=0;i<H;i++) {
		for (int j=0;j<W;j++) {
			if ((i%2 || j==0 || bd[i][j]=='#') && j+1!=W) cout << '#';
			else cout << '.';
		}
		cout << endl;
	}
	cout << endl;

	for (int i=0;i<H;i++) {
		for (int j=0;j<W;j++) {
			if ((i%2==0 || j==W-1 || bd[i][j]=='#') && j) cout << '#';
			else cout << '.';
		}
		cout << endl;
	}

}

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

using namespace std;

int N;
pair<double,double> dots[300];
#define EPS (1e-6)


int main(){

	while(cin >> N && N != 0){
		for(int i = 0; i < N; i++){
			pair<double,double> p;
			cin >> dots[i].second >> dots[i].first;
		}
		int maxCnt = 1;
		// ~ðìé½ßÌQ_ðßé
		for(int i = 0; i < N; i++){
			for(int j = i+1; j < N; j++){
				pair<double,double> dot1,dot2;
				dot1 = dots[i];
				dot2 = dots[j];

				double v = sqrt((dot1.first - dot2.first)*(dot1.first - dot2.first)
					+(dot1.second - dot2.second)*(dot1.second - dot2.second));
				// ñ_Ô£ª2æè¨¨«¯êÎÂ­êÈ¢
				if(v > 2.0 + EPS){
					continue;
				}

				double x = sqrt(1 - (v/2)*(v/2));

				// ñgÌPÊ@üxNg
				pair<double,double> hose[2];
				hose[0].first = -1.0/(dots[i].first - dots[j].first);
				hose[0].second = 1.0/(dots[i].second - dots[j].second);
				hose[1].first = 1.0/(dots[i].first - dots[j].first);
				hose[1].second = -1.0/(dots[i].second - dots[j].second);

				double dd1 = sqrt((hose[0].second)*(hose[0].second)+(hose[0].first)*(hose[0].first));
				double dd2 = sqrt((hose[1].second)*(hose[1].second)+(hose[1].first)*(hose[1].first));
				hose[0].first /= dd1; hose[0].second /= dd1;
				hose[1].first /= dd2; hose[1].second /= dd2;

				// x{·é
				hose[0].first *= x;hose[1].first *= x;
				hose[0].second *= x;hose[1].second *= x;

				// mð«·
				hose[0].first += (dot1.first + dot2.first)/2;
				hose[0].second += (dot1.second + dot2.second)/2;
				hose[1].first += (dot1.first + dot2.first)/2;
				hose[1].second += (dot1.second + dot2.second)/2;

				// hose[0]Æhose[1]Í~ÌSÀW
				// e_ÉÖµÄ~ÌÉ¶Ý·é©Ç¤©ðßé
				for(int k = 0; k < 2; k++){
					int cnt = 0;
					for(int l = 0; l < N; l++){
						double dist = sqrt((dots[l].first -hose[k].first)*(dots[l].first -hose[k].first)
							+ (dots[l].second -hose[k].second)*(dots[l].second -hose[k].second));
						if(dist <= 1.0 + EPS){
							cnt++;
						}
					}
					maxCnt = max(maxCnt,cnt);
				}
			}
		}
		cout << maxCnt << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll N;
    cin >> N;
    vector<ll> A(N+1);
    vector<ll> B(N);
    for (int i = 0; i < N+1; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];

    ll ans = 0;
    for (int i = 0; i < N; i++){
        ll left = min(A[i], B[i]);
        ans += left;
        A[i] -= left;
        B[i] -= left;

        ll right = min(A[i+1], B[i]);
        ans += right;
        A[i+1] -= right;
        B[i] -= right;
    }
    cout << ans << endl;
}

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

int main(){
  int N, P;
  scanf("%d", &N);
  scanf("%d", &P);
  std::string S;
  std::cin >> S;
  std::vector<int > s(N);
  for (int i=0; i<N; i++){
    s[i] = int(S[i])-int('0');
  }
  std::reverse(s.begin(), s.end());
  if (10%P!=0){
    std::vector<int > amari(N+1);
    amari[0] = 0;
    int power10 = 1;
    for (int i=0; i<N; i++){
      amari[i+1] = (amari[i]+ power10*s[i])%P;
      power10 = (power10*10)%P;
      //printf("s[%d]=%d\n",i,s[i]);
      //printf("amari[%d]=%d\n", i+1, amari[i+1]);
    }
    std::map<int, int > mp;
    for (int i=1; i<=N; i++){
      mp[amari[i]]++;
    }
    long long ans = 0;
    for (auto entry: mp){
      if(entry.first==0){
        ans += entry.second;
      }
      ans += (long long)entry.second*(entry.second-1)/2;
    }
    printf("%lld\n", ans);
  } else {
    long long ans = 0;
    for (int i=0; i<N; i++){
      if (s[i]%P==0){
        ans += (N-i);
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}


Measured memory_bytes: 2428
n,s,i,j;
main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		printf("Case %d:\n",i);
		scanf("%d",&s);
		for(j=0;j<10;j++){
			s=s*s/100%10000;
			printf("%d\n",s);
		}
	}
	exit(0);
}

Measured memory_bytes: 0
# B

N = int(input())
A = list(map(int,input().split()))

pears = {}
for index,a in enumerate(A):
  pears[index+1] = a


cnt = 0
for key,value in pears.items():
  if key == pears.get(pears.get(key)):
    cnt += 1
print(cnt//2)


Measured memory_bytes: 24096
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }


    Scanner cin;

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int A = cin.nextInt();
        int B = cin.nextInt();
        long ans = 0;
        for (int i = 1; i <= N; i++)
        {
            int t = i;
            int sum = 0;
            while(t > 0)
            {
                sum += t % 10;
                t /= 10;
            }
            if (A <= sum && sum <= B) ans += i;
        }
        Console.WriteLine(ans);
    }

}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


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

struct node{
	int u,v,w;
};
node a[65];

int main()
{
	int L,n=1,s=0;
	scanf("%d",&L);
	int t=1,m=--L;
	while(t<=m){
		a[s++]=node{n,n+1,t};
		a[s++]=node{n,n+1,0};
		++n;
		m-=t;	t<<=1;
	}
	int xi=t,p=t/2,k=n-1;
	while(k>=1&&m){
		if(p<=m){
			a[s++]=node{k,n,xi};
			xi+=p;	m-=p;
		}
		p/=2;	--k;
	}
	printf("%d %d\n",n,s);
	for(int i=0;i<s;++i)
		printf("%d %d %d\n",a[i].u,a[i].v,a[i].w);
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <cmath>
#include <array>
#include <list>
#include <set>
const int MOD=1000000007;
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int> tup;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> p;
typedef vector<p> vp;
const int INF=1e9;
int n,ans=0;
int h[105];
int main(int argc,char const* argv[])
{
  cin >> n;
  for(int i=0;i<n;i++)
    {
      cin >> h[i];
    }
  while(1)
    {
      bool clear=true;
      for(int i=0;i<n;i++)
	{
	  if(h[i]!=0) clear=false;
	}
      if(clear)
	{
	  cout << ans << endl;
	  return 0;
	}
      int l=0;
      int r=n-1;
      for(int i=0;i<n;i++)
	{
	  if(h[i]!=0) 
	    {
	      l=i;
	      int minus=min(1000,h[i]);
	      for(int j=l;j<n;j++)
		{
		  if(h[j]==0)
		    {
		      r=j-1;
		      break;
		    }
		  else
		    {
		      minus=min(minus,h[j]);
		    }
		}
	      for(int j=l;j<=r;j++)
		{
		  h[j]-=minus;
		}
	      ans+=minus;
        
	      
	      /*for(int j=0;j<n;j++)
		{
		  cout << h[j] << ' ';
		}
	      cout << l << ' ' << r << ' ' << ans << endl;
	      cout << endl;*/
	      break;
	    }
	}
    }
  return 0; 
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int a[105];
int main(){
	int n,d,x,sum;
	sum=0;
	scanf("%d",&n);
	scanf("%d%d",&d,&x);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum=sum+(d-1)/a[i]+1;
	}
	printf("%d\n",sum+x);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int Maxn=2005,p=1e9+7;
int n,m;
long long inv[Maxn],fac[Maxn];
long long fast_pow(long long x,long long y)
{
	long long ans=1,now=x;
	while(y)
	{
		if(y&1) ans=(ans*now)%p;
		now=(now*now)%p;
		y>>=1;
	}
	return ans;
}
void init(void)
{
	fac[0]=1;
	inv[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%p,inv[i]=fast_pow(fac[i],p-2);
}
long long C(int x,int y)
{
	if(x>y) return 0;
	return fac[y]*inv[x]%p*inv[y-x]%p;
}
int main()
{
	scanf("%d%d",&n,&m);
	init();
	for(int i=1;i<=m;i++)
		printf("%lld\n",C(i,n-m+1)*C(i-1,m-1)%p);
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[21]:


N,K = map(int, input().split())
R,S,P = map(int,input().split())
T = input()


# In[22]:


points = {}
points["r"] = P
points["s"] = R
points["p"] = S

ans = 0
mylist = []
for i in range(N):
    mylist.append(T[i])
    if i >= K:
        if T[i] == mylist[-K-1]:
            mylist[-1] = "x"
        else:
            ans += points[T[i]]
    else:
        ans += points[T[i]]
print(ans)


# In[ ]:






Measured memory_bytes: 9820
function Main(input){
    input = input.split("\n");
    var s = parseInt(input[0],10);

    console.log(Math.floor(s / 3600) + ':' + Math.floor(s % 3600 / 60) + ':' + Math.floor(s %  3600 % 60));
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 15576
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

//頂点vが葉の時，頂点vを削除
int dfs(vector<set<int> > &G, int v, vector<int> &deg){
  if(deg[v] != 1) return 0;  //頂点vが葉以外
  deg[v] = 0;

  //頂点vから辿れる頂点に移動
  int num = 1;
  for(const int& u : G[v]){
    //辺の削除
    G[v].erase(u);
    G[u].erase(v);
    --deg[u];
    num += dfs(G, u, deg);
  }
  return num;
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N,M;cin >> N >> M;
  vector<set<int> >G(N);
  vector<int> deg(N,0); //頂点の次数
  //グラフの構築1
  rep(j,M){
    int x,y;cin >> x >> y;
    --x;--y;
    G[x].insert(y);
    G[y].insert(x);
  }

  //次数の確認
  rep(i,N) deg[i] = G[i].size();

  //橋の数カウント
  int num = 0;
  rep(i,N) num += dfs(G,i,deg);

  cout << num << endl;
  return 0;
}


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

using namespace std;

template <int MOD>
class mod_calc
{
public:
	mod_calc(int n)
		: m_fact(n + 1)
		, m_ifact(n + 1)
	{
		m_fact[0] = 1;

		for (int i = 1; i <= n; ++i) {
			m_fact[i] = mul(m_fact[i - 1], i);
		}

		m_ifact[n] = inv(m_fact[n]);
		for (int i = n - 1; i >= 0; --i) {
			m_ifact[i] = mul(i + 1, m_ifact[i + 1]);
		}
	}

	int pow(int a, int n) const
	{
		if (n == 0) {
			return 1;
		}
		int t = pow(mul(a, a), n / 2);
		if (n % 2 != 0) {
			t = mul(t, a);
		}
		return t;
	}

	int inv(int n) const
	{
		return pow(n, MOD - 2);
	}

	int mul(int x, int y) const
	{
		return (1LL * x * y) % MOD;
	}

	int fact(int n) const
	{
		return m_fact[n];
	}

	int ifact(int n) const
	{
		return m_ifact[n];
	}

	int comb(int n, int r) const
	{
		int ans = fact(n);
		ans = mul(ans, ifact(n - r));
		ans = mul(ans, ifact(r));
		return ans;
	}

public:
	vector<int> m_fact;
	vector<int> m_ifact;
};

int solve(int X, int Y)
{
	if ((X + Y) % 3 != 0) {
		return 0;
	}
	if (Y < X) {
		swap(X, Y);
	}
	int a = (X + Y) / 3;

	if (X < a) {
		return 0;
	}
	mod_calc<1000 * 1000 * 1000 + 7> m(1000000);
	return m.comb(a, X - a);
}

int main()
{
	int X, Y;
	cin >> X >> Y;
	cout << solve(X, Y) << endl;
}


Measured memory_bytes: 8064
n=int(input())
l=['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']
z=[]
while n>26:
  r=n%26
  n=n//26
  if r==0:
    n-=1
  z.append(r)
z.append(n)
s=''
for x in z:
  let=l[x-1]
  s=let+s
print(s)


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

using namespace std;

int main(){
    long long N;

    cin >> N;

    int S = 0;
    int tmp = N;
    while((N / 10) != 0){
      S += N % 10;
      N /= 10;
    }
    S+=N;
    if((tmp % S) == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

int main() {
    long long N;
    cin >> N;
    long long ans = 1000000000000;
    for (long long a=1; a*a<=N; a++) {
        if ((N/a)*a==N) ans = min(ans, a+(N/a)-2);
    }
    cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
#define rep(i,N) for(int i=0;i<(int)N;++i)
//cout << fixed << setprecision(20) << *** << endl;
typedef long long ll;
using namespace std;
int main()
{
	ll N,T,ANS=0;
	vector<ll>vec;
	cin>>N>>T;
	rep(i,N){
		ll t;
		cin>>t;
		vec.push_back(t);
	}
	rep(i,N-1){
		//cout<<ANS<<endl;
		if(vec[i]+T<=vec[i+1])ANS=ANS+T;
		else{
			ANS=ANS+vec[i+1]-vec[i];
		}
		
	}
	cout<<ANS+T<<endl;
}

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


#define ALL(a) 		(a.begin() , a.end())
#define ll 			long long int
#define ff          first
#define ss          second
#define pb          push_back
#define ar 			array
#define mp 			make_pair
#define f(i,a,b)   	for(ll i =a;i<=b;i++)
#define inf 		INT_MAX
#define pll 		pair<ll,ll>
#define mat 		vector<vector<ll>>

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define deb(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 //debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
 

const ll INF = 1e18;
void init(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE 
		freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
}
 
bool checkp2(ll n){
	return n && !(n & (n-1));
}

ll numsetbit(ll n){
	ll count = 0;
	for(;n;count++){
		n = n & (n-1);
	}
	return count;
}
 
ll power(ll x , ll n , ll mod){
    x = x % mod;
	ll po = 1;
	while(n){
		if(n & 1){
			po = (po*x) % mod;
		}
		n = n>>1;
		x = ((x % mod) * (x % mod)) % mod;
	}
	return po;
}
 
bool isPrime(ll x){
	if(x < 2)
		return 0;
	for(ll y = 2; y * y <= x; y++){
		if(x % y == 0){
			return 0;
		}
	}
	return true;
}







void solve(){

		ll d,t,s;
		cin>>d>>t>>s;

		ll time = d / s;

		if(d % s != 0)
			time++;
		
		if(time <= t){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}



}

int main(){
	
	init();
	ll t = 1;
	//cin>>t;
	for(ll i=1;i<=t;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class node{
private:
public:
  node(){done = true;cost = 9999999;from = 0;}
  vector<int> to_c;
  vector<int> to_node;
  int from;
  int cost;
  bool done;
};
int main(){
  int n,m;
  node P[400];
  cin >>n>>m;
  while(m--){
    int a,b,p;
    cin >>a>>b>>p;
    P[a].to_node.push_back(b);
    P[a].to_c.push_back(p);
    P[b].from++;
  }
  P[0].cost = 0;
  for(int c=0; c<n; c++){
    int x = 9999999,y = -1;
    for(int i=0; i<n; i++){
      if(P[i].done && P[i].from == 0){
	if(P[i].cost<x){x = P[i].cost;y = i;}
      }
    }
    P[y].done = false;
    for(int i=0; i<P[y].to_c.size(); i++){
      P[P[y].to_node[i]].from--;
      if(P[P[y].to_node[i]].cost == 9999999) P[P[y].to_node[i]].cost = 0;
      P[P[y].to_node[i]].cost = max(P[P[y].to_node[i]].cost,P[y].cost+P[y].to_c[i]);
    }
  }
  cout <<P[n-1].cost<<endl;
  return 0;
}

Measured memory_bytes: 1260
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = input()
    print(S.count('1'))

if __name__ == '__main__':
    main()


Measured memory_bytes: 9036
#include "stdio.h"
#include "string.h"

char s[1111111];

int main()
{
	scanf("%s",s);
	char c = 'w';
	int k = 0;
	int nk = 0;
	char o;
	int n = 0;
	for(int i = 0; i < strlen(s); i++)
	{
		o = c;
		c = s[i];
		if(c == o)
		{
			n++;
		}
		else
		{
			if(c == 'J')
			{
				nk = 0;
				n = 1;
			}
			if(c == 'O')
			{
				if(o == 'J')
				{
					nk = n;
					n = 1;
				}
				else
				{
					nk = 0;
				}
			}
			if(c == 'I')
			{
				if(o == 'O' && nk >= n)
				{
					nk = n;
					n = 1;
				}
				else
				{
					nk = 0;
				}
			}
		}
		if(c == 'I' && nk <= n && k < nk)
		{
			k = nk;
		}
	}
	printf("%d\n",k);
	return 0;
}

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

int main(){
  int64_t N,K;
  cin>>N>>K;
  vector<int64_t> amari(K);
  for(int i=0;i<K;++i){
    amari.at(i)=(N-i)/K;
    if(i!=0 && i<=N){++amari.at(i);}
  }

  int64_t count=amari.at(0)*amari.at(0)*amari.at(0);
  for(int i=1;i<K;++i){
    if((2*(K-i))%K==0){
      count += amari.at(i)*amari.at(K-i)*amari.at(K-i);
    }
  }

  cout<<count<<endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
#define pb(a) push_back(a)
#define pr(a) cout<<(a)<<endl
#define PR(a,b) cout<<(a)<<" "<<(b)<<endl
#define R cin>>
#define F first
#define S second
#define ll long long
bool check(int n,int m,int x,int y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<60,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

int main() {
  int n,m;
  while(cin >> n >> m && n) {
    ll l[n][n],s[n][n];
    rep(i,n)rep(j,n)l[i][j]=s[i][j]=MAX;
    rep(i,m) {
      ll x,y,z;
      char c;
      cin >> x >> y >> z >> c;
      x--,y--;
      if(c=='L') l[x][y]=l[y][x]=min(l[x][y],z);
      else s[x][y]=s[y][x]=min(s[x][y],z);
    }
    rep(k,n)rep(i,n)rep(j,n) {
      if(l[i][k]!=MAX && l[k][j]!=MAX) l[i][j]=min(l[i][j],l[i][k]+l[k][j]);
      if(s[i][k]!=MAX && s[k][j]!=MAX) s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
    }
    int k;
    R k;
    vector<int> a(k);
    rep(i,k) {
      R a[i];
      a[i]--;
    }
    ll d[k][n];
    rep(i,k)rep(j,n) d[i][j]=MAX;
    d[0][a[0]]=0;
    REP(i,1,k) {
      rep(j,n) {
	rep(t,n) {
	  int d1=l[a[i]][t],d2=l[j][a[i-1]];
	  if(t==a[i]) d1=0;
	  if(j==a[i-1]) d2=0;
	  d[i][t]=min(d[i][t],d[i-1][j]+d1+s[t][j]+d2);
	}
	d[i][j]=min(d[i][j],d[i-1][j]+l[a[i]][a[i-1]]);
      }
    }
    ll ans=MAX;
    rep(i,n) ans=min(ans,d[k-1][i]);
    pr(ans);
  }  
  return 0;
}


Measured memory_bytes: 3388
#include <iostream>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdarg>
#include <set>
#include <limits>
#include <iomanip>

using namespace std;
#define INF 2e9 + 9
#define MOD 1000000007
#define ALL(v) v.begin() , v.end()
#define Int int64_t
#define pll pair<Int,Int>
template<class T> using pql = priority_queue<T, vector<T>>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define ll(n) Int n; cin >> n;
#define LL(...) Int __VA_ARGS___; cin >> __VA_ARGS___;
#define OUT(...) cout << __VA_ARGS___;
#define RP(n, i, s) for(Int i = s ;i < n ;i++)
#define REP(n, i) for (Int i = 0; i < n; i++)
#define REPe(n, i) for (Int i = 1; i <= n; i++)
#define RPe(n, i, s) for (Int i = s; i <= n; i++)
#define upd_max(maxer, updater) if (maxer < updater) maxer = updater;

void ansYes(bool flag){
    if (flag) cout << "Yes" << endl; else  cout << "No" << endl;
}

void ansYES(bool flag){
    if (flag) cout << "YES" << endl; else  cout << "NO" << endl;
}

struct node {
    Int to;
    Int length;
};


vector<Int> divisor(Int n) {
    vector<Int> ret;
    for (Int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    return (ret);
}

/*
vector<vector<int>> to;
vector<int> flag;
vector<int> c;


Int dfs(int from, int mae) {
    flag[from] = 1;
    Int mini = 0;
    for (auto next : to[from]) {
        if (next == mae) continue;
        if (flag[next] == 1) {
            return -1;
        } else {
            mini = min(mini, dfs(next, from));
        }
    }
    return mini;
}*/

int dx8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

struct datas{
    Int max;
    Int size;
};


int main(void) {
    Int q;
    string s;
    cin >> s;
    cin >> q;
    deque<char> dq;
    for (auto z : s){
        dq.push_back(z);
    }
    bool mae = true;
    REP(q,i){
        Int t;
        cin >> t;
        if (t == 1) mae = !mae; else{
            Int f;
            char c;
            cin >> f >> c;
            if (f == 1) {
                if (mae) {
                    dq.push_front(c);
                }else{
                    dq.push_back(c);
                }
            }else{
                if (mae) {
                    dq.push_back(c);
                }else{
                    dq.push_front(c);
                }
            }
        }
    }
    if (!mae) {
        reverse(dq.begin(),dq.end());
    }
    for(auto z : dq){
        cout << z;
    }
    cout << endl;
}




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

int main() {
  int n;
  cin >> n;
  vector<tuple<string, int, int>> vec;
  for (int i = 1; i <= n; i++) {
    int point;
    string name;
    cin >> name >> point;
    point = -point;
    vec.push_back(tie(name, point, i));
  }

  sort(vec.begin(), vec.end());
  int number;
  for (int i = 0; i < n; i++) {
    number = get<2>(vec.at(i));
    cout << number << endl;
  }
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;
 
class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    Random rnd = new Random();
    Stopwatch sw = new Stopwatch();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
    int N;
    void solve()
    {
        N = cin.nextint;
        if (N % 10 == 9 || N / 10 == 9)
        {
            WriteLine("Yes");
        }
        else
        {
            WriteLine("No");
        }
    }
 
}
 
class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

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

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;

    map<int, int> mp;
    rep(i, n) {
        int x;
        cin >> x;
        mp[x]++;
    }

    map<int, int> mpe, mpo;
    for (auto& p: mp) {
        mpe[p.first % m] += p.second - p.second % 2;
        if (p.second % 2 > 0) mpo[p.first % m]++;
    }

    ll ans = mpo[0] / 2 + mpe[0] / 2;
    if (m % 2 == 0) {
        ans += mpo[m / 2] / 2 + mpe[m / 2] / 2;
    }

    for (int i = 1; i <= (m - 1) / 2; i++) {
        if (mpo[i] > mpo[m - i]) {
            int x = min(mpe[m - i], mpo[i] - mpo[m - i]);
            ans += mpo[m - i] + x;
            mpe[m - i] -= x;
        } else {
            int x = min(mpe[i], mpo[m - i] - mpo[i]);
            ans += mpo[i] + x;
            mpe[i] -= x;
        }
    }

    for (int i = 1; i < m; i++) {  
        if (m % 2 == 0 and i == m / 2) continue;
    // rep(i, m) {
        // cout << i << " " << mpe[i] << endl;
        ans += mpe[i] / 2;
    }

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


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  int desCnt = 0;
  sort(a.begin(), a.end());
  while (true) {
    sort(a.begin(), a.end());
    for (int i = 1; i < n; i++) {
      if (a[i] == INT_MAX) continue;
      a[i] = a[i] % a[0];
      if (a[i] == 0) {
        desCnt++;
        a[i] = INT_MAX;
      }
    }
    if (desCnt == n - 1) break;
  }
  cout << a[0] << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b) for(int a = 0;a < b;++a)
string se[7] ={"SAT","FRI","THU","WED","TUE","MON","SUN"};
int main(){
   string s;
cin >> s;
REP(i,7){
if(s == se[i]) cout << i+1 << endl;
}
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define MOD 1000000007
#define enld endl
typedef long long ll;
using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll X; cin >> X;
    for(ll A=-999;A<=1000;A++){
        for(ll B=-1000;B<A;B++){
            if(pow(A,5)-pow(B,5) == X){
                cout << A << " " << B << endl;
                return 0;
            }
        }
    }
}

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

int main() {
  int x, n, ans1,ans2;
  bool a1 = true, a2 = true;
  cin >> x >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++)
  {
     cin >> p.at(i);
  }
  for (int ans = x; ans >= 0; ans--)
  {
     for (int i = 0; i < n; i++)
     {
        if (p.at(i) == ans)
        {
           a1 = false;
        }
        
     }
     if (a1 == true)
     {
        ans1 = ans;
        break;
     }
     a1 = true;
  }
  for (int ans = x+1; ans <= 101; ans++)
  {
     for (int i = 0; i < n; i++)
     {
        if (p.at(i) == ans)
        {
           a2 = false;
        }
        
     }
     if (a2 == true)
     {
        ans2 = ans;
        break;
     }
     a2 = true;
  }
  if (x-ans1 <= ans2 -x)
  {
     cout << ans1 << endl;
  }else if (x-ans1 > ans2 -x)
   {
     cout << ans2 << endl;
   }
  
  
  return 0;

}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define pb(a) push_back(a)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

typedef long long unsigned int ll;
typedef pair<ll, ll> P;

int main(){
  int N,n;
  cin >>N;
  vector<int> H;
  REP(i,N){
    int a;
    cin >>a;
    H.push_back(a);
  }
  REP(i,N){
    //cout << i << "回目" << endl;
    int f=1;
    REP(j,i){
      if(H[j]>H[i]){
        //cout << "だめだったよ" << endl;
        f=0;
        break;
      }
    }
    if(f) n++;
  }
  cout<<n<<endl;
}


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

int main(){
    int n;
    cin >> n;
    vector<string> S(2*n);
    for (auto i = 0; i < 2*n; i++)
    {
        string s;
        cin >> s;
        S[i] = s;
    }

    for (auto i = 0; i < 2*n; i += 2)
    {
        string x = S[i];
        string y = S[i + 1];
        int sizex = x.size();
        int sizey = y.size();

        vector<vector<int>> m(sizex+1, vector<int>(sizey+1));

        for (auto j = 0; j < sizex+1; j++)
        {                
                m[j][0] = 0;   
        }

        for (auto j = 0; j < sizey+1; j++)
        {
                m[0][j] = 0;
        }


        for (auto j = 1; j < sizex+1; j++)
        {
            for (auto k = 1; k < sizey+1; k++)
            {
                if(x[j-1] == y[k-1]){
                    m[j][k] = m[j - 1][k - 1] + 1;
                }else{
                    m[j][k] = max(m[j - 1][k], m[j][k - 1]);
                }
            }
        }

        cout << m[sizex][sizey] << endl;

    }   
    
}


Measured memory_bytes: 6860
#include <cstdio>

int main(void){
		int H, W;
		scanf("%d %d", &H, &W);
		while(H != 0 || W != 0){
				for(int i = 0; i < H; i++){
						for(int j = 0; j < W; j++){
								if((i + j) % 2 == 0)printf("#");
								else printf(".");
						}
						printf("\n");
				}
				printf("\n");
				scanf("%d %d", &H, &W);
		}

		return 0;
}



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

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  int res = 1;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    res += i and a[i - 1] >= a[i];
  }
  cout << res << '\n' << n << '\n';
}



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

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x, y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x, y, z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define db4(x, y, z, w) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<","<<#w<<"="<<w<<'\n'
#define sz(a) int((a).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
#define PR(a, n) {cout<<#a<<"="; for(int __=0;__<n;__++)cout<<a[__]<<' '; cout<<"\n"; }
using namespace std;
using ll = unsigned long long;
int arr[100005];

int dfs(int u, const vector<vector<int>> &graph, vector<bool> &vis) {
    if (arr[u] != -1)return arr[u];
    int M = 0;
    for (auto v: graph[u]) {
        M = max(M, dfs(v, graph, vis));
    }
    vis[u] = true;
    arr[u] = M + 1;
    return arr[u];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    memset(arr, -1, sizeof(arr));
    vector<vector<int>> graph(n);
    vector<bool> vis(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        --u;
        --v;
        graph[u].push_back(v);
    }
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            dfs(i, graph, vis);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, arr[i]);
    }
    cout << max(0, ans - 1) << '\n';

//    for (int i = 0;i < n;    ++i){
//        cout << vis[i] << ' ';
//    }
//    cout << '\n';
    return 0;
}

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

using namespace std;

/*-------------------------------*/
#define FOR(i, a, b) for(int i = (a); i < (b); i++)  //a~(b - 1)?????§
#define print(i) cout << i << endl //?°??????????Python?????????
#define all(i) (i).begin(),(i).end() //??¨??????(sort??¨???)
#define mp make_pair //mp(OO, OO)??¨???:::pint??¨???

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> llv;
typedef vector<pint> vpint;
/*-------------------------------*/

int main(void)
{
  vi a;
  int b;
  FOR(i, 0, 5){
    cin >> b;
    a.push_back(b);
  }
  sort(all(a));
  reverse(all(a));
  FOR(i, 0, 5){
    if (i < 4){
      cout << a[i] << " ";
    }
    else{
      cout << a[i] << endl;
    }
  }
  return 0;
}

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

int a[110];

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", a+ i);
	sort(a, a+n, greater<int>());
	int ans = 0;
	for(int i = 0; i < n; i++)
		ans += (i%2) ? -a[i] : a[i];
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
    while (1) {
        int H, W;
        cin >> H >> W;
        if (H == 0 && W == 0) { break; }
        for (int i = 0; i<H; i++) {
            for (int j = 0; j<W; j++) {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3112
main :: IO ()
main = do
  [n, _, x] <- readInts
  as <- readInts
  print $ solve n x as

readInts :: IO [Int]
readInts = map read . words <$> getLine

solve :: Int -> Int -> [Int] -> Int
solve n x as = (step 0 x as) `min` (step x n as)

step :: Int -> Int -> [Int] -> Int
step p q as = length [ a | a <- as, p < a, a < q ]


Measured memory_bytes: 892
<?php
$conditions = trim(fgets(STDIN));
$array = explode(' ', $conditions);
$N = $array[0];
$K = $array[1];
$Q = $array[2];

$scores = array_fill(0, $N, 0);

for ($i = 0; $i < $Q; $i++) {
    $answer = trim(fgets(STDIN)) - 1;
    $scores[$answer] += 1;
}

for ($i = 0; $i < $N; $i++) {
     if ($scores[$i] + $K - $Q > 0) {
         echo('Yes');
     }else {
         echo('No');
     }
     if($i !== $N - 1) {
         echo("\n");
     }
}

Measured memory_bytes: 16756
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int64_t a[200'000];
int64_t psum[200'000 + 1];
int64_t rpsum[200'000 + 1];

int sln[200'000 + 1];
int rsln[200'000 + 1];

int64_t ss = 0;

int main()
{
    int n;
    cin >> n;
    rep(i, n)
    {
        cin >> a[i];
    }

    irep(i, n)
    {
        if (i == 0) {
            psum[i] = 0;
            rpsum[i] = 0;
        } else {
            psum[i] = psum[i - 1] + a[i - 1];
            rpsum[i] = rpsum[i - 1] + a[n - i];
        }
    }

    int j = 0, k = 0;
    irep(i, n)
    {
        while (j < n && abs(psum[j] - (psum[i] - psum[j])) >= abs(psum[j + 1] - (psum[i] - psum[j + 1]))) {
            j++;
        }
        sln[i] = j;
        while (k < n && abs(rpsum[k] - (rpsum[i] - rpsum[k])) >= abs(rpsum[k + 1] - (rpsum[i] - rpsum[k + 1]))) {
            k++;
        }
        rsln[i] = k;
    }

    int64_t result = 1e15;
    for (int i = 2; i <= n - 2; i++) {
        int j = sln[i], k = rsln[n - i];
        int64_t p = psum[j];
        int64_t q = psum[i] - psum[j];
        int64_t r = rpsum[k];
        int64_t s = rpsum[n - i] - rpsum[k];

        int64_t M = max(max(p, q), max(r, s));
        int64_t m = min(min(p, q), min(r, s));
        int64_t d = M - m;
        result = min(result, d);
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
template<class T> inline bool chmax(T &a,T b){
  if (a<b){
    a=b;
    return 1;
  }
  return 0;
}
const int MAX_DIGIT = 50;
long long dp[100][2]; // dp[上から i 桁まで][ smaller ]

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    memset(dp, -1, sizeof(dp)); // DP 配列を -1 で初期化
    dp[0][0] = 0; // 初期条件
    for (int d = 0; d < MAX_DIGIT; ++d) {
        long long mask = 1LL<<(MAX_DIGIT - d - 1);
        
        // A で元々 d 桁目にビットが立っているものの個数
        int num = 0;
        for (int i = 0; i < N; ++i) if (A[i] & mask) ++num;
        
        // X の d 桁目を 0, 1 にしたときのコスト
        long long cost0 = mask * num;
        long long cost1 = mask * (N - num);
        
        // smaller -> smaller
        if (dp[d][1] != -1) {
            chmax(dp[d+1][1], dp[d][1] + max(cost0, cost1)); // 0 でも 1 でも自在に大きい方
        }
        
        // exact -> smaller
        if (dp[d][0] != -1) {
            if (K & mask) { // K の d 桁目が 1 だったら、X の d 桁目は 0 にする
                chmax(dp[d+1][1], dp[d][0] + cost0);
            }
        }
        
        // exact -> exact (K にぴったり合わせる)
        if (dp[d][0] != -1) {
            if (K & mask) chmax(dp[d+1][0], dp[d][0] + cost1);
            else chmax(dp[d+1][0], dp[d][0] + cost0);
        }
    }
    cout << max(dp[MAX_DIGIT][0], dp[MAX_DIGIT][1]) << endl;
}

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

const int MAXN = 1e5 + 6.66;
long long val [ MAXN ] ;
vector<int> tree [ MAXN ] ;

long long dfs ( int v,int p ) {
  if ( tree[v].size ( ) == 1 ) return val [ v ] ;
  if ( p != -1 && tree[v].size ( ) == 2 ) {
    int u = tree[v][0] ;
    if ( u == p ) u = tree[v][1] ;
    if ( dfs ( u , v ) != val [ v ] ) { printf("NO\n") ; exit ( 0 ) ; }
    return val [ v ];
  }
  long long sum = 0,mx = 0;
  for ( auto u : tree[v] )
    if ( u != p )
    {
      long long x = dfs ( u , v ) ;
      sum += x;mx = max ( mx , x ) ;
    }
  if(2 * val[v] - sum < 0){
    printf("NO\n");exit(0);
  }
  mx = max(mx,val[v] * 2 - sum);
  if(mx > val[v] * 2 - mx){ 
    printf ( "NO\n" ) ; exit ( 0 ) ;
  }
  return val[v] * 2 - sum;
}

int main ( ) {
  int n;scanf ( "%d" , &n ) ;
  for ( int i = 0;i<n;i++ ) scanf ( "%lld",val + i );
  for ( int i = 1;i<n;i++ ) {
    int x,y; scanf ( "%d %d",&x,&y ) ;
    tree[--x].push_back( --y );
    tree[  y].push_back(   x );
  }
  if ( n == 2 ) {
    if ( val[0] == val[1] ) printf ( "YES\n" );
    else printf ( "NO\n" ) ;
  } else {
    int root = 0;
    while ( tree[root].size ( ) == 1 ) root ++ ;
    if ( dfs ( root, -1 ) ) printf ( "NO\n" ) ;
    else printf ( "YES\n" ) ;
  }
  return 0;
}


Measured memory_bytes: 13184
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=jp>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

int n,w,d;
vector<ll> solve(){
    vector<ll> res;
    vector<pll> ps(n);
    for(auto& in:ps){cin >> in.first >> in.second; in.first--; }
    vector<pll> pieces; pieces.push_back({w,d});
    for(auto query:ps){
        ll p,s; tie(p,s) = query;
        ll W,D; tie(W,D) = pieces[p];
        pieces.erase(pieces.begin()+p);

        s %= 2*(W+D);
        
        ll W1,W2,D1,D2;
        if(s <= W){
            W1 = s; W2 = W - W1;
            D1 = D2 = D;
        }else if(s <= W+D){
            W1 = W2 = W;
            D1 = s - W; D2 = W+D-s;
        }else if(s <= W+D+W){
            W1 = s - (W+D); W2 = (W+D+W) - s;
            D1 = D2 = D;
        }else{
            W1 = W2 = W;
            D1 = s - (W+D+W); D2 = (W+D+W+D) - s;
        }
        
        if(W1*D1 > W2*D2){
            swap(W1,W2); swap(D1,D2);
        }
        pieces.push_back({W1,D1});
        pieces.push_back({W2,D2});
    }
    
    sort(pieces.begin(),pieces.end(),
         [](const pll& c1,const pll& c2){
             return c1.first*c1.second < c2.first*c2.second;
         });
    for(auto p:pieces){
        res.push_back(p.first*p.second);
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> n >> w >> d,n|w|d){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3000
import itertools
import heapq
from heapq import heappush, heappop
global G, inp_x, inp_y

def input_graph(N):
  global G, inp_x, inp_y
  inp_x = []
  inp_y = []
  for i in range(N):
    x, y = map(int, input().split())
    inp_x.append((x, i))
    inp_y.append((y, i))
  inp_x.sort()
  inp_y.sort()
  for i in range(N-1):
    xa = inp_x[i][1]
    xb = inp_x[i+1][1]
    ya = inp_y[i][1]
    yb = inp_y[i+1][1]
    cost_x = abs(inp_x[i][0]-inp_x[i+1][0])
    cost_y = abs(inp_y[i][0]-inp_y[i+1][0])
    G[xa] += [(cost_x, xb)]
    G[xb] += [(cost_x, xa)]
    G[ya] += [(cost_y, yb)]
    G[yb] += [(cost_y, ya)]

  
def prim(V):
  global G, used
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N)
  print(prim(N))

if __name__ == "__main__":
  main()


Measured memory_bytes: 74600
// C.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[])
{
  string s;
  long long k;
  cin >> s;
  cin >> k;
  char c;
  for (int i = 0; i != s.length(); ++i) {
    c = s[i];
    if (c == '1') {
      --k;
      if (k <= 0) {
        break;
      }
    } else {
      break;
    }
  }
	cout << c << endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}
func fSum(a []float64) float64 {
	x := 0.
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	r1, c1, r2, c2 := iScan(), iScan(), iScan(), iScan()
	f := make([]int, 2100000)
	inv := make([]int, 2100000)
	f[0], inv[0] = 1, 1
	for i := 1; i < 2100000; i++ {
		f[i] = f[i-1] * i % mod
		inv[i] = modinv(f[i], mod)
	}
	ans := path(r2, c2, f, inv) - path(r2, c1-1, f, inv) - path(r1-1, c2, f, inv) + path(r1-1, c1-1, f, inv)
	ans %= mod
	if ans < 0 {
		ans += mod
	}
	fmt.Println(ans)
}
func path(r int, c int, f []int, inv []int) int {
	ret := 0
	for i := c; i <= r+c+1; i++ {
		ret += f[i] * inv[i-c] % mod * inv[c] % mod
		ret %= mod
	}
	return ret
}
func modinv(a, m int) int {
	b, u, v := m, 1, 0
	for {
		t := a / b
		a -= t * b
		u -= t * v
		a, b, u, v = b, a, v, u
		if b == 0 {
			break
		}
	}
	u %= m
	if u < 0 {
		u += m
	}
	return u
}


Measured memory_bytes: 35724