akhauriyash/Code-Regression huggingface dataset:
n,m,k = map(int,input().split())
import collections
par = []
for i in range(n):
    par.append(i)  #初期親
rank = [1 for i in range(n)] #初期ランク
flist = [[] for i in range(n)]
blist = [[] for i in range(n)]
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # ランクを2にする
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[x] = y 
    elif rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    else:
        par[y] = x
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    flist[a].append(b)
    flist[b].append(a)
    unite(a,b)
for i in range(n):
    shorten(i)
for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if par[a] == par[b]:
        blist[a].append(b)
        blist[b].append(a)
c = collections.Counter(par)
for i in range(n):
    ans = c[par[i]] -len(flist[i])-len(blist[i])-1
    print(ans,end = ' ')

Measured memory_bytes: 124644
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 
int N, H, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
int solve() {
    int ma = 0;
    rep(i, 0, N) ma = max(ma, A[i]);
    vector<int> v;
    rep(i, 0, N) if (ma < B[i]) v.push_back(B[i]);
    sort(v.begin(), v.end(), greater<int>());
 
    int ans = 0;
    fore(x, v) {
        ans++;
        H -= x;
        if (H <= 0) return ans;
    }
 
    ans += (H + ma - 1) / ma;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> H;
    rep(i, 0, N) cin >> A[i] >> B[i];
    cout << solve() << endl;
}

Measured memory_bytes: 1660
#include<stdio.h>
#include<string.h>
int main(void){
    int lens,lenp,i,j,hante=0;
    char s[101],p[101],buf[201];
 
    scanf("%s",s);
    scanf("%s",p);
    lens=strlen(s);
    lenp=strlen(p);
    strcpy(buf,s);
    strcat(buf,s);
    for(i=0;i<lens;i++){
        for(j=0;j<lenp;j++){
            if(buf[i+j]!=p[j]) break;
        }
		if(lenp==j){hante=1;break;}
    }
    printf("%s\n",hante?"Yes":"No");
    return 0;
}

Measured memory_bytes: 532
/*
	"We know what we are, but know not what we may be."
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 3;
const int M = 1e6 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 5;
const int logN = 20, BL = 400;
const double EPS = 3e-16;

/*
	"You never know how strong you are until being strong is the only choice you have."
*/

long long f(long long n){
	return (n * (n - 1)) / 2;
}

int main(){
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
/*
	"With self-discipline most anything is possible."
*/
	
	long long n; cin >> n;
	vector<long long> pref(n);
	map<long long, long long> occur;
	for(long long i = 0; i < n; i++){
		long long x; cin >> x;
		pref[i] = pref[i - (i > 0)] + x;
		occur[pref[i]]++;
	}
	
	long long ans = 0;
	for(auto it : occur){
		if(it.first == 0) ans += it.second;
		ans += f(it.second);		
	}	
	
	cout << ans;

	return 0;
}

/*
	"Reach for it. Push yourself as far as you can."
*/

Measured memory_bytes: 14336
#include"bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
using namespace __gnu_pbds; 
using namespace std;

#define double long double
#define int long long
#define pb push_back 
#define Z(c) (int)(c).size()
#define L(c) c[Z(c)-1]
#define F first
#define S second
#define nl "\n"
#define mii map<int,int> 
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define rep(i,iv,n) for(int (i)=(iv);(i)<(n);++(i))
#define FO fflush(stdout) 
#define D1(x) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<nl
#define D2(x,y) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<nl
#define D3(x,y,z) cerr <<"At line "<<__LINE__<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<nl
#define tr(it,ct) for(auto &(it) : (ct))
#define pi acos(-1)
#define prt(ct) for(auto &(it) : (ct)) cerr<<it<<" "; cerr<<nl
#define prtp(ct) for(auto &(it) : (ct)) cerr<<it.F<<" "<<it.S<<nl; cerr<<nl

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > pii;
typedef vector< pii > vp;
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> baap;

void swap(char &a,char &b)
{ auto tm=a; a=b; b=tm; }
                                   
 
  const int mod=1000000007;
  const int mod2=998244353;
  const int INF=1e16+18;
  const int N=2e5+35;
  const int M=2e4;
  
 
 void fft()           
 { 
   int n,m,k; cin>>n>>m>>k;
   string s[n];
   rep(i,0,n) cin>>s[i];

    int ans=n*m+1;

   for(int i=0;i<(1<<(n-1));++i){
        int x=__builtin_popcount(i)+1;
        vi v(x);
        bool f=true;
        int ct=x-1;
        for(int j=0;j<m;++j){
            int c=0,id=0;  
           for(int h=0;h<n;++h){
            
               if(s[h][j]=='1')
                 c++;

               if(c>k){
                 f=false;
                 j=m;
                 break;
               }
              if(i&(1<<h)){
                if(v[id]+c>k) break;
                
                v[id]+=c;
                c=0;
                id++;
              }
           }

           if(v[id]+c>k){
              --j;
             tr(ii,v) ii=0;
             ct++;
           }
           else v[id]+=c;
                                 
        }

        if(f) ans=min(ans,ct);
   }

   cout<<ans;

 }
  

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

   
   int t=1;                         
 //  cin>>t;

  rep(i,1,t+1)
  { // cout<<"Case #"<<i<<": ";
   fft();
   if(i<t)
   cout<<nl;
  }
  
 return 0; 
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#define min(a, b) (a < b ? a : b)

int main(void) {
	int n, i, j, cnt[100001];
	
	cnt[0] = 0;
	for (i = 1; i <= 100000; i++) {
		cnt[i] = i;
		for (j = 0; pow(6, j) <= i; j++)
			cnt[i] = min(cnt[i], cnt[i - (int)pow(6, j)]+1);
		for (j = 0; pow(9, j) <= i; j++)
			cnt[i] = min(cnt[i], cnt[i - (int)pow(9, j)]+1);
	}
	
	scanf("%d", &n);
	
	printf("%d\n", cnt[n]);
	
	return 0;
}

Measured memory_bytes: 512
package main

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

var (
	in  = bufio.NewReader(os.Stdin)
	out = bufio.NewWriter(os.Stdout)
)

func main() {
	coins := readInt64Slice()
	var sum, i int64
	for i = 0; i < 2; i++ {
		if coins[0] > coins[1] {
			sum += coins[0]
			coins[0]--
		} else {
			sum += coins[1]
			coins[1]--
		}
	}
	fmt.Println(sum)
}

func readInt64Slice() []int64 {
	line := readStringSlice()
	slice := make([]int64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseInt(tmp, 10, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)
	}
	return slice
}
func readFloat64Slice() []float64 {
	line := readStringSlice()
	slice := make([]float64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseFloat(tmp, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)

	}
	return slice
}
func readString() string {
	s, _, _ := in.ReadLine()
	return string(s)
}
func readStringSlice() []string {
	line := readString()
	s := strings.Split(line, " ")
	return s
}
func dump(value ...interface{}) {
	for _, v := range value {
		fmt.Printf("%#v\n", v)
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  set<pair<int, int> > ranking;
  while (cin >> n, n) {
    int p, d1, d2;
    for (int i = 0; i < n; i++) {
      cin >> p >> d1 >> d2;
      ranking.insert(pair<int, int>(d1 + d2, p));
    }
    cout << ranking.rbegin()->second << ' ';
    cout << ranking.rbegin()->first << endl;
    ranking.clear();
  }
  return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
int s;
const int nax=3005;
ll mod=998244353;
int a[nax];
inline ll adds(ll a, ll b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
} 
ll fun(int st, int end){
    if(st == end){
        return a[st]==s;
    }
    int mid=(st+end)/2;
    ll ans=(fun(st,mid)+fun(mid+1,end))%mod;
    int n=end-st+1;
    int S=0;
    for(int i=st;i<=end;i++) S+=a[i];
    S=min(S,s);
    ll dp[n][S+1];

    for(int i=mid+1;i<=end;i++){
        for(int j=0;j<=S;j++){

            if(j==0){
                dp[i-st][j]=1; continue;
            }
            if(i==mid+1){
                if(a[i]==j) dp[i-st][j]=1;
                else dp[i-st][j]=0;
            }
            else{
                dp[i-st][j]=adds(dp[i-1-st][j],(a[i]<=j ? dp[i-1-st][j-a[i]] : (ll)0));
            }
        }
    }
    for(int i=mid;i>=st;i--){
        for(int j=0;j<=S;j++){
            if(j==0){
                dp[i-st][j]=1; continue;
            }
            if(i==mid){
                if(a[i]==j) dp[i-st][j]=1;
                else dp[i-st][j]=0;
            }
            else{
                dp[i-st][j]=adds(dp[i+1-st][j],(a[i]<=j ? dp[i+1-st][j-a[i]] : (ll)0));
            }
        }
    }
    ll t1[s+1]={0};
    for(int j=0;j<=S;j++){
        for(int i=mid+1;i<=end;i++){
            t1[j]=adds(t1[j],dp[i-st][j]);
        }
    }
    for(int j=0;j<=S;j++){
        ll g=0;
        for(int i=mid;i>=st;i--){
            g=adds(g,dp[i-st][j]);
        }
        ans=adds(ans, (g*t1[s-j])%mod );
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n>>s;
    for(int i=0;i<n;i++) cin>>a[i];
    cout<<fun(0,n-1)<<"\n";
}


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

int main() {
    cout << fixed << setprecision(0);
    int N;
    cin >> N;
    int count = 0;
    string ans = "No";
    for(int i = 0; i < N; i++) {
        int d1, d2;
        cin >> d1 >> d2;
        if(d1 == d2)
            count++;
        else
            count = 0;
        if(count == 3)
            ans = "Yes";
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"

#define SORT(vec) sort(vec.begin(), vec.end());
typedef long long ll;

using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
//  --------------------------------------

	int N; cin >> N;
	ll H[100010];

	for (int i = 0; i < N; i++)
	{
		cin >> H[i];
	}
	
	int jump, max_jump;
	jump = 0;
	max_jump = 0;

	for (int i = 0; i < N-1; i++)
	{
		if (H[i+1] <= H[i])
		{
			jump += 1;
		}
		else
		{
			if (jump > max_jump)
			{
				max_jump = jump;
			}
			jump = 0;
		}
	}
	if (jump > max_jump)
	{
		max_jump = jump;
	}
	
	cout << max_jump << "\n";
	

}

Measured memory_bytes: 1024
import std.stdio;
import std.math;
import std.algorithm;

void main(){
 int n;
 readf("%d\n",&n);
 for(int i=0;i<n;i++){
	int[3] a;
	readf("%d %d %d\n",&a[0],&a[1],&a[2]);
	a.sort;
	if(pow(a[2],2) == pow(a[0],2) + pow(a[1],2))
	 writeln("YES");
	else
	 writeln("NO");
 }
}

Measured memory_bytes: 1004
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    std::deque<long long int> deq(n+1,0);
    long long int a;
    int count=0;
    std::map<long long int, int> map;
    for (int i=0;i<n;i++) {
        cin>>a;
        if (a>100000) {
            count++;
        } else {
            if (deq[a]==0) {
                map.emplace(a,1);
                deq[a]=1;
            } else {
                map.at(a)++;
            }
        }
    }
    for (auto itr=map.begin();itr!=map.end();itr++) {
        if (itr->first!=itr->second) {
            long long int a=itr->first;
            long long int b=itr->second;
            if (a>b) {
                count+=b;
            } else {
                count+=b-a;
            }
        }
    }
    cout<<count<<endl;
}

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

public class Test
{
	public static void Main()
	{
		string line = Console.ReadLine();
		int a = 0;
		for(int i = 0 ; i < line.Length ; i++)
		{
		    if(line[i] == '1')
		    {
		        a++;
		    }
		}
		Console.WriteLine(a);
	}                                                                                                                                                                       
}

Measured memory_bytes: 11092
#include <stdio.h>
int main(){
    char s[4];
    scanf("%s",s);
    int l[3]={0};
    for(int i=0;i<3;i++){
        l[s[i]-'a']++;
    }
    printf("%s\n",(l[0]==1 && l[1]==1 && l[2]==1)?"Yes":"No");
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vec=vector<ll>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define rep(i,N) for(i=0;i<(ll)N;i++)
#define rep1(i,N) For(i,1,N)
#define print(a) cout<<a<<endl
#define pb push_back
vec prime(ll N){
  ll i=2;
  vec res;
  while(i*i<=N){
    while(!(N%i)){
      res.pb(i);
      N/=i;
    }
    i++;
  }
  if(N!=1)res.pb(N);
  return res;
}
int main(){
  ll i,j,A,B,cnt=0,scnt=0,ans;
  cin>>A>>B;
  rep(i,A){
    j=i;
    cnt=1;
    cnt+=j/A+j%A;
    scnt=(i+B)/A+(i+B)%A;
    if(cnt>scnt){
      print(i+B);
      return 0;
    }
  }
  print(-1);
  // if(B>=A*2){
  //   print(-1);
  //   return 0;
  // }
  // print(A*2);
  return 0;
}


Measured memory_bytes: 3116
object Main extends App {

  val a = io.StdIn.readLine.toInt
  val b = io.StdIn.readLine.toInt
  val c = io.StdIn.readLine.toInt
  val d = io.StdIn.readLine.toInt
  val e = io.StdIn.readLine.toInt
  val k = io.StdIn.readLine.toInt

  val s = Seq(a,b,c,d,e)

  var isNG = false
  for (i <- 0 until s.size ; j <- i+1 until s.size) {
    if (s(j) - s(i) > k) isNG = true
  }

  if (isNG)
    println(":(")
  else
    println("Yay!")
}


Measured memory_bytes: 27072
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
	"math"
)

func main() {
	sc := NewScanner()

	n := sc.NextInt()

	N := sc.NextInt()
	T := sc.NextInt()

	Nf := float64(N)
	Tf := float64(T)

	ans := float64(100001)
	idx := 0
	for i := 0; i < n; i++ {
		H := sc.NextInt()
		Hf := float64(H)
		tmp := Nf - Hf*0.006
		tmp = math.Abs(tmp - Tf)
		if ans > tmp {
			idx = i + 1
			ans = tmp
		}
	}
	fmt.Printf("%v\n", idx)

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define INF (int)1e9
#define endl "\n"
#define ll long long
#define ull unsigned long long

using namespace std;

int main()
{
    ll m, n;
    cin >> m >> n;
    vector<ll> arr(n);

    for (ll &x : arr)
        cin >> x;
    ll s = accumulate(arr.begin(), arr.end(), 0LL);

    cout << (s >= m ? "Yes" : "No") << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main (){
    long h, w, n;
    vector<long> answer(10,0);
    cin >> h >> w >>n;
    answer[0]= (h-2)*(w-2);
    set<pair<int, int> > s;
    int a,b;
    set<pair<int, int> >::iterator itr;
    set<pair<int, int> >::iterator itr2;
    for(int i=0; i<n;i++){
        cin >> a >> b;
        a--;b--;
        pair<int,int> p = make_pair(a,b);
        s.insert(p);
        for(int j=0;j<9;j++){
            int da = j % 3 -1;
            int db = j / 3 -1;
            if(a+da>0 && a+da < h-1 && b+db<w-1&& b+db>0){
                int count =0;
                for(int k = 0 ; k<9;k++){
                    int dda = k % 3 -1;
                    int ddb = k / 3 -1;
                    pair<int,int> p = make_pair(a+da+dda, b+db+ddb);
                    itr = s.find(p);
                    itr2 = s.end();
                    if(itr != itr2)count++;     
                }
                answer[count]=answer[count]+1;
                answer[count-1]=answer[count-1]-1;
            }


        }
    }
    for(int i =0; i<10;i++)cout << answer[i] << endl;
    return 0;

}

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

int main() {
	int a,b,i;
	long long int c;
	cin >> a >>b;
	c=b;
	for(i=1;i<a;i++){
		c*=b-1;
	}
	cout << c << endl;
	return 0;
}

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

int main(void) {
	int N, T;
	cin >> N >> T;
	int c[N], t[N];

	for (int i = 0; i < N; i++) cin >> c[i] >> t[i];

	int mincost = 10000;

	for (int i = 0; i < N; i++) {
		if (t[i] <= T) {
			if (c[i] < mincost) mincost = c[i];
		}
	}
	
	if (mincost == 10000) {
		cout << "TLE" << endl;
	}
	else {
		cout << mincost << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))
#dp[k] 0 => lose of turn player 1 => win of turn player
dp = [-1 for i in range(K+1)]
for i in range(min(A)):
    dp[i] = 0
for k in range(1,K+1):
    if dp[k] > 0:
        continue
    if all(dp[k-a] == 1 for a in A if k - a >= 0): #どんな減らし方をしても手番が負け
        dp[k] = 0
    else:
        dp[k] = 1
print(['Second', 'First'][dp[-1]])

Measured memory_bytes: 3864
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repe(i, n) for (int i = 0; i <= (int)(n); i++)
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define ANS cout << ans << endl
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define KOZYUN(a) sort(all(a),greater<int>())
#define int ll
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORe(i, m, n) for(int i = m;i <= n;i++)
#define VIin(a) for(int i=0; i<a.size(); i++) cin >> a[i]
#define OUT(a) cout << a << endl
#define IN(a) cin >> a
#define INT(a) int a; cin >> a
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD=1e9+7;
const long long INF = 1LL << 60;
/*最大公約数*/int gcd(int x, int y) { return y ? gcd(y,x%y) : x;}
/*最小公倍数*/int lcm(int a, int b) { int g = gcd(a, b); return a / g * b; }
/*素数判定*/int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------------------------------------
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a,b; cin >> a >> b;
    int ans = lcm(a,b);
    ANS;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

int n, m, d, atari;
vector<string> input(32);

bool Input() {
	cin >> n;
	if(n == 0)
		return false;
	cin >> m >> atari >> d;
	
	for(int i = 0; i < d; i++)
		cin >> input[i];

	return true;
}

bool foo(vector<string> const & modified) {
	int cur_posn = m - 1;

	for(int i = 0; i < d; i++) {
		if(cur_posn < n - 1 && modified[i][cur_posn] == '1')
			cur_posn++;
		else if(cur_posn > 0 && modified[i][cur_posn - 1] == '1')
			cur_posn--;
	}

	return cur_posn == atari - 1;
}

string solve() {
	if(foo(input))
		return "0";

	for(int i = 0; i < d; i++) {
		for(int j = 0; j < n - 1; j++) {
			if(n == 2) {
				if(input[i][j] == '0') {
					input[i][j] = '1';
					if(foo(input)) {
						cout << i + 1 << " " << j + 1;
						return "";
					}
					input[i][j] = '0';
				}
			}
			else {
				if((j == 0 && input[i][j] == input[i][j + 1]) ||
						(j == n - 2 && input[i][j] == input[i][j - 1]) ||
						(input[i][j - 1] == input[i][j] && input[i][j] == input[i][j + 1])) {
					input[i][j] = '1';
					if(foo(input)) {
						cout << i + 1 << " " << j + 1;
						return "";
					}
					input[i][j] = '0';
				}
			}
		}
	}

	return "1";
}

int main(void) {
	while(Input()) {
		cout << solve() << endl;
	}

	return 0;
}

Measured memory_bytes: 1216
const MOD:i64 = 1_000_000_007;

fn mod_pow(a: i64, e:i64) ->i64{
    let mut ret = 1;
    if e ==0 {
        return 1;
    }
    ret = mod_pow(a * a % MOD, e / 2);
    if e % 2 == 1 {
        ret = ret * a % MOD;
    }
    ret
}

fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line);
    let mut it = line.split_whitespace();
    let mut n:i64 = 3;
    let mut k:i64 = it.next().unwrap().parse().unwrap();
    let mut add = vec![0i64; k as usize + 1];
    let mut ans = 0;
    for i in 1..=k {
        let count = k / i;
        let sum = add[i as usize];
        ans = (ans + mod_pow(count, n) * (i - sum)) % MOD;
        add[i as usize] = i - sum;
        let mut j = i;
        while j <= k {
            add[j as usize] += i-sum;
            j += i;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2168
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <string>
#include <cmath>
#include <climits>
#include <cstdint>
using namespace std;

inline namespace atcoder {
    template <typename T, size_t Depth>
    struct vector_helper { using type = vector<typename vector_helper<T, Depth - 1>::type>; };
    template <typename T>
    struct vector_helper<T, 0> { using type = T; };
    template <typename T, size_t Depth>
    using vector_t = typename vector_helper<T, Depth>::type;

    template <typename T> using vec = vector_t<T, 1>;
    template <typename T> using vvec = vector_t<T, 2>;
    template <typename T> using vvvec = vector_t<T, 3>;

    constexpr int64_t mpow(int64_t a, int64_t b, int64_t mod = 1000000007) {
        if (b <= 0) return 1; if (b == 1) return a % mod; if (b == 2) return (a * a) % mod;
        return (max(a * (b & 1), (int64_t)1) * mpow(mpow(a, b / 2, mod), 2, mod)) % mod;
    }
    constexpr int64_t mdiv(int64_t a, int64_t b, int64_t mod = 1000000007) {
        return (a * mpow(b, mod - 2, mod)) % mod;
    }
}

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

    int64_t ans = 0;
    bool p = false;
    while (n--) {
        int a; cin >> a;
        if (a != 0) {
            a -= p; ans += p;
            ans += a / 2;
        }
        p = a & 1;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3604
N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N)]


AB.sort(key=lambda x: x[1])
t = 0
for a, b in AB:
    t += a
    if t <= b:
        continue
    else:
        print("No")
        exit(0)
print("Yes")


Measured memory_bytes: 31824
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const ll MOD2=998244353;
const double PI=acos(-1);
const ll INF=1e18;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

ll N,A,B,C,D;
map<ll,ll> dp;
ll dfs(ll x){
  if(dp[x]!=0){
    return dp[x];
  }
  if(x<=0){
    return 0;
  }
  if(x==1){
    return D;
  }
  ll k=INF;
  if(x<INF/D){
    k=x*D;
  }
  k=min(min(k,A+D*(x%2)+dfs(x/2)),min(B+D*(x%3)+dfs(x/3),C+D*(x%5)+dfs(x/5)));
  if(x%2!=0){
    k=min(k,A+D*(2-(x%2))+dfs(x/2+1));
  }
  if(x%3!=0){
    k=min(k,B+D*(3-(x%3))+dfs(x/3+1));
  }
  if(x%5!=0){
    k=min(k,C+D*(5-(x%5))+dfs(x/5+1));
  }
  dp[x]=k;
  return k;
}
int main() {
  int t;
  cin >> t;
  rep(i,t){
    cin >> N >> A >> B >> C >> D;
    dp.clear();
    ll ans=dfs(N);
    cout << ans << endl;
  }
}

Measured memory_bytes: 4348
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF= 1LL << 60;

int main() {
    string a; cin >> a;
    string s=a;
    reverse(a.begin(),a.end());
    if (a[0]=='s') cout << s+"es" << "\n";
    else cout << s+"s" << "\n";
}

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

char c[110][110];

int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
string table = "NESW";

struct NODE{
	int x,y,d;
	NODE(int x,int y,int d) : x(x) , y(y) , d(d) {}
	NODE(){}
};
bool operator < (const NODE &a,const NODE &b){
	if( a.x != b.x ) return a.x < b.x;
	if( a.y != b.y ) return a.y < b.y;
	return a.d < b.d;
}
int main(){
	long long H,W,L;
	while(cin >> H >> W >> L && L ){
		L--;
		for(int i = 0 ; i < 110 ; i++)
			for(int j = 0 ; j < 110 ; j++)
				c[i][j] = '#';
		
		NODE cur(0,0,0);
		
		for(int i = 1 ; i <= H ; i++){
			for(int j = 1 ; j <= W ; j++){
				cin >> c[i][j];
				if( ~table.find(c[i][j]) ){
					cur.d = table.find(c[i][j]);
					cur.x = j;
					cur.y = i;
					c[i][j] = '.';
				}
			}
		}
		map<NODE,long long> memo;
		vector<NODE> add;
		while(L){
			while( c[cur.y+dy[cur.d]][cur.x+dx[cur.d]] == '#' ) cur.d = (cur.d+1) % 4;
			//cout << add.size() << " " << cur.x << " " << cur.y << " " << cur.d  << endl;
			if( memo.count(cur) ){
				int idx = memo[cur];
				long long r = L%(add.size() - idx);
				cur = add[idx+r];
				break;
			}
			memo[cur] = add.size();
			add.push_back(cur);
			cur.y+=dy[cur.d];
			cur.x+=dx[cur.d];
			L--;
		}
		
		while( c[cur.y+dy[cur.d]][cur.x+dx[cur.d]] == '#' ) cur.d = (cur.d+1) % 4;
		cur.y+=dy[cur.d];
		cur.x+=dx[cur.d];
		cout << cur.y << " " << cur.x << " " << table[cur.d] << endl;
		
	}
}

Measured memory_bytes: 1608
#include <stdio.h>
int main() {
  int m, f, r;
  while (scanf("%d %d %d", &m, &f, &r) && !(m == -1 && f == -1 && r == -1)) {
    if (m == -1 || f == -1) printf("F\n");
    else if (m + f >= 80) printf("A\n");
    else if (m + f >= 65) printf("B\n");
    else if (m + f >= 50) printf("C\n");
    else if (m + f >= 30) {
      if (r >= 50) printf("C\n");
      else printf("D\n");
    }
    else printf("F\n");
  }
  return 0;
}


Measured memory_bytes: 2556
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

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

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

void solve(){
     int h,w;
     cin >> h >> w;
     vector<string>s(h+1);
     for(int i = 0;i<h;i++) {cin >> s[i];}
     int aa[h+1][w+1];
     int bb[h+1][w+1];
     memset(aa,0,sizeof(aa));
     memset(bb,0,sizeof(bb));
     for(int i = 0;i<h;i++){
            int pos = 0;
            int cnt = 0;
        for(int j = 0;j<=w;j++){
            if(s[i][j]!='.'||j==w){
                for(int k = pos;k<j;k++) aa[i][k] = cnt;
                cnt = 0;
                pos = j;
            }
            else cnt++;
    }
}
    for(int i = 0;i<w;i++){
            int pos = 0;
            int cnt = 0;
        for(int j = 0;j<=h;j++){
            //cout <<i;
            if(s[j][i]!='.'||j==h){
                for(int k = pos;k<j;k++) bb[k][i] = cnt;
                cnt = 0;
                pos = j;
            }
            else cnt++;
    }}
     int ans = 0;
     for(int i = 0;i<h;i++)
        for(int j = 0;j<w;j++)
       if(s[i][j]=='.') ans = max(ans,aa[i][j]+bb[i][j]-1);
     cout << ans;


}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}


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

int main() {
  
  char b;
  cin >> b;
  
  if ( b == 'A' ){
    cout << 'T' << endl;
  }else if ( b == 'T' ){
    cout << 'A' << endl;
  }else if ( b == 'C' ){
    cout << 'G' << endl;
  }else{
    cout << 'C' << endl;
  }
  
  
}



Measured memory_bytes: 256
import itertools
N = int(input())
ans = 0
for i in range(3, 10):
    product = list(itertools.product(['3', '5', '7'], repeat=i))
    for li in product:
        if len(set(li)) == 3:
            if int(''.join(li)) <= N:
                ans += 1
print(ans)


Measured memory_bytes: 45168
import sys
sys.setrecursionlimit(10**9)
l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
def f(n,k,q):
    if k==0:
        return 1
    elif k%2==0:
        return ((f(n,k//2,q))**2)%q
    else:
        return (n*f(n,k-1,q))%q

for i in range(n):
    if l[i]=="1":
        x=n-i-1
        ans+=(f(3,x,p)*f(2,d,p))%p
        d+=1
    else:
        continue

ans+=f(2,d,p)
print(ans%p)


Measured memory_bytes: 10012
#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;
  string s, t;
  cin >> n >> s >> t;

  for (int i = n; i >= 0; --i) {
    string u = s;
    for (int j = i; j < n; ++j) u += t[j];
    bool same_t = true;
    rep(j, n) if (u[u.size() - 1 - j] != t[t.size() - 1 - j]) same_t = false;
    if (same_t) {
      cout << 2 * n - i << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3548
A,B = list(map(int,input().split()))
# A=10**10
# B=10**12

def gcd(a,b):
    x=min(a,b)
    y=max(a,b)
    
    while y%x != 0:
#         print(x,y)
        x_= y%x
        y = x
        x = x_
    return x

gcd = gcd(A,B)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

P_F=[1]
P_F.extend(prime_factorize(gcd))
print(len(set(P_F)))

Measured memory_bytes: 62208
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////




int main() {

	ll M;

	cin >> M;

	ll d[MAX], c[MAX];

	repn(i, M) {
		cin >> d[i] >> c[i];
	}

	ll sum = 0;
	repn(i, M) {
		sum += d[i] * c[i];
	}

	ll ans=0;

	repn(i, M) {
		ans += c[i];
	}
	ans--;

	ans += sum / 9;

	if (sum % 9 == 0) { ans--; }

	cout << ans;

	system("PAUSE");
}


Measured memory_bytes: 7032
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
const int inf = 1000000007;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % inf;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), inf - 2, inf) % inf * mod_pow(kai(y), inf - 2, inf) % inf;
}

signed main() {
	int n,ans=0;
	cin >> n;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			if ((n - i) / i > i)ans+= (n - i) / i;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
nk = gets
N, K = nk.split.map { |s| s.to_i }
ds =  gets
D = ds.split.map { |s| s.to_i }

L = (0..9).to_a - D

nds = N.to_s.split('').map { |s| s.to_i }

def acceptable_digit_carry_increased(test_digit)
  if test_digit == 10
    a,_,__ =acceptable_digit_carry_increased(0)
    return a,true,true
  end
  return test_digit, false, false unless D.include? test_digit
  lt, gt = * L.partition { |x| x < test_digit }
  unless gt.empty?
    return gt.first, false, true
  end
  return lt.first, true, true
end

increased = false
ihoras_digits = Array.new(nds.size + 1)
ihoras_digits[0] = 0
nds.each_with_index do |nd, i|
 if ! increased
  id,carry, inc = acceptable_digit_carry_increased(nd)
   if inc
     increased = true
   end
   if carry
     i.downto(0) do |j|
       ihoras_digits[j], carry, _ = acceptable_digit_carry_increased(ihoras_digits[j] +1)
       break unless carry
     end
   end
   ihoras_digits[i+1] = id
 else
   ihoras_digits[i+1] = L.first
 end
end

puts ihoras_digits.reduce{|v,d| v* 10 +d }



Measured memory_bytes: 1788
#include <iostream>


#define MAX_M 110
#define INF   10000

int n, m, k;
int ct[MAX_M][MAX_M];
int tm[MAX_M][MAX_M];
int d[MAX_M][MAX_M];
int e[MAX_M][MAX_M];

void warshall_floyd() {
    for (int k=1; k<=m; k++) {
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=m; j++) {
                ct[i][j] = std::min(ct[i][j], ct[i][k] + ct[k][j]);
                tm[i][j] = std::min(tm[i][j], tm[i][k] + tm[k][j]);
            }
        }
    }
}

int main() {
    while (true) {
        std::cin >> n >> m;
        if (!n && !m) break;
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=m; j++) {
                ct[i][j] = INF;
                tm[i][j] = INF;
                if (i == j) {
                    ct[i][j] = 0;
                    tm[i][j] = 0;
                }
            }
        }

        for (int i=0; i<n; i++) {
            int a, b, c, t;
            std::cin >> a >> b >> c >> t;
            ct[a][b] = c;   ct[b][a] = c;
            tm[a][b] = t;   tm[b][a] = t;
        }
        warshall_floyd();

        std::cin >> k;
        for (int i=0; i<k; i++) {
            int p, q, r;
            std::cin >> p >> q >> r;
            if (r == 0) {
                std::cout << ct[p][q] << std::endl;
            } else {
                std::cout << tm[p][q] << std::endl;
            }
        }
    }
    return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    fast;
    string s;
    string t;
    cin>>s;
    cin>>t;
    int f=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]==t[i])
        {
            continue;
        }
        else
        {
            f=1;
        }
    }
    if(f)
    {
        cout<<"No"<<endl;
    }
    else
        cout<<"Yes"<<endl;

    return 0;
}


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

public class C
{
    public const int INF = 999999999;
}

public static class Permi
{
    public static IEnumerable<IEnumerable<T>> Perm<T>(this IEnumerable<T> items, int? k = null)
    {
        if (k == null) k = items.Count();
        if (k == 0) yield return Enumerable.Empty<T>();
        else
        {
            var i = 0;
            foreach (var x in items)
            {
                var xs = items.Where((_, index) => i != index);
                foreach (var c in Perm(xs, k - 1))
                    yield return c.Before(x);
                i++;
            }
        }
    }
    public static IEnumerable<T> Before<T>(this IEnumerable<T> items, T first)
    {
        yield return first;
        foreach (var i in items) yield return i;
    }
}

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var m = int.Parse(line[1]);
        var r = int.Parse(line[2]);
        var dp = new int[n, n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j) dp[i, j] = C.INF; 
        string[] line2 = Console.ReadLine().Trim().Split(' ');
        var a = new int[r];
        for (int i = 0; i < r; i++) a[i] = int.Parse(line2[i])-1;
        for (int i = 0; i < m; i++)
        {
            string[] line3 = Console.ReadLine().Trim().Split(' ');
            var a1 = int.Parse(line3[0]) - 1;
            var a2 = int.Parse(line3[1]) - 1;
            var a3 = int.Parse(line3[2]);
            dp[a1, a2] = a3;
            dp[a2, a1] = a3;
        }
        goWarshall(dp);
        var ax = a.Perm();
        var ret = C.INF;
        foreach (var w1 in ax)
        {
            var w = w1.ToArray();
            ret = Math.Min(ret, getLength(dp, w));
        }
        Console.WriteLine(ret);
    }
    public static int getLength (int[,] dp, int[] w)
    {
        var ret = 0;
        for (int i = 0; i < w.Length - 1; i++)
            ret += dp[w[i], w[i + 1]];
        return ret;
    }
    public static void goWarshall(int[,] dp)
    {
        var n = dp.GetLength(0);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    dp[j, k] = Math.Min(dp[j, k], dp[j, i] + dp[i, k]);
    }
}



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

using ll = long long;

int main(){
  int n; cin >> n;
  vector<ll> v(n);
  for(auto&&e:v){
    cin >> e;
  }

  ll sum = 0, xsum = 0, ans = 0;
  int r = 0;
  for(int l = 0; l < n; ++l){
    while(r < n && (sum + v[r]) == (xsum ^ v[r])){
      sum += v[r];
      xsum ^= v[r];
      r++;
    }
    ans += r - l;
    sum -= v[l];
    xsum ^= v[l];
  }
  cout << ans << endl;
  return 0;
}


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

int main()
{
	string s;
	cin>>s;
	bool a[27];
	for(int i=1;i<=26;i++)
	{
		a[i]=false;
	}
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		char b;
		if(s.substr(i,1)=="a") b='a';
		if(s.substr(i,1)=="b") b='b';
		if(s.substr(i,1)=="c") b='c';
		if(s.substr(i,1)=="d") b='d';
		if(s.substr(i,1)=="e") b='e';
		if(s.substr(i,1)=="f") b='f';
		if(s.substr(i,1)=="g") b='g';
		if(s.substr(i,1)=="h") b='h';
		if(s.substr(i,1)=="i") b='i';
		if(s.substr(i,1)=="j") b='j';
		if(s.substr(i,1)=="k") b='k';
		if(s.substr(i,1)=="l") b='l';
		if(s.substr(i,1)=="m") b='m';
		if(s.substr(i,1)=="n") b='n';
		if(s.substr(i,1)=="o") b='o';
		if(s.substr(i,1)=="p") b='p';
		if(s.substr(i,1)=="q") b='q';
		if(s.substr(i,1)=="r") b='r';
		if(s.substr(i,1)=="s") b='s';
		if(s.substr(i,1)=="t") b='t';
		if(s.substr(i,1)=="u") b='u';
		if(s.substr(i,1)=="v") b='v';
		if(s.substr(i,1)=="w") b='w';
		if(s.substr(i,1)=="x") b='x';
		if(s.substr(i,1)=="y") b='y';
		if(s.substr(i,1)=="z") b='z';
		a[(int)(b-96)]=true;
	} 
	int f=0,k=28;
	for(int i=1;i<=26;i++)
	{
		if(a[i]==false && i<k) {k=i;f=1;} 
	} 
	if(f==1) cout<<char(k+96);
	else cout<<"None"; 
} 

Measured memory_bytes: 512
#include <iostream>
#include <numeric>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

#define sp ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(long long int yy = 0; yy < YY; ++yy)
#define prn(XX) cout << XX << endl
#define prs(XX) cout << XX << " "

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const int MOD = 1e9 + 7;
const int INF = 2e9 + 13;
const int mINF = -2e9 - 13;
const double PI = 3.14159265358979;
const double EPS = 1e-9;

int yazi = 0, N;
vector<double> p;
vector<vector<double>> DP;

double dn(int n, int yazi){
    if(n == N)
        if(yazi > n-yazi) return 1.0;
        else return 0.0;

    if(N - n + yazi < n - yazi) return 0.0;
    
    if(DP[n][yazi] != -1.0) return DP[n][yazi];
    return DP[n][yazi] = ((dn(n+1, yazi+1)*p[n]) + (dn(n+1, yazi)*(1.0 - p[n])));
}

int main(int argc, char **argv){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> N; p.resize(N); for(auto &x: p) cin >> x;
    DP.assign(N+1, vector<double>(N+1, -1.0));
    cout << setprecision(10) << dn(0, 0) << endl;

    return 0;
}

//cikisir



Measured memory_bytes: 70912
n = int(input())
a = list(map(int,input().split()))
ans = set()
def cul(x,i):
    global ans
    ans.add(x)
    if n>i:
        cul(x+a[i],i+1)
        cul(x,i+1)
cul(0,0)
q = int(input())
m = list(map(int,input().split()))
for i in m:
    if i in ans:print('yes')
    else:print('no')


Measured memory_bytes: 5656
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        String[][] s = new String[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = sc.next().split("");
        }
        sc.close();

        // 主処理
        int[] pointX = new int[] { 0, 1, 1, 1, 0, -1, -1, -1 }; // 上,右上,右,...,左上
        int[] pointY = new int[] { 1, 1, 0, -1, -1, -1, 0, 1 };
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (".".equals(s[i][j])) {
                    int count = 0;
                    for (int k = 0; k < 8; k++) {
                        int x = j + pointX[k];
                        int y = i + pointY[k];
                        if (0 <= y && y < h && 0 <= x && x < w) {
                            String target = s[y][x];
                            if ("#".equals(target)) {
                                count++;
                            }
                        }
                    }
                    s[i][j] = Integer.toString(count);
                }
            }
        }

        String[] lines = new String[h];
        for (int i = 0; i < h; i++) {
            lines[i] = String.join("", s[i]);
        }
        String result = String.join("\n", lines);

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 22440
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <numeric>
using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<((x))<<endl
#define fi first
#define se second

#define INF 2147483600
#define long long long

int main(){
  int n,k;
  cin>>n>>k;
  vector<long> vec(n);
  rep(i,n) scanf("%lld", &vec[i]);
  long acc=0;
  rep(i,n) if(vec[i]>0) acc += vec[i];


  long res=0;
  long tmp=0;
  rep(i,k-1) if(vec[i]<0) tmp+=vec[i];
  repl(i,k-1,n){
    if(vec[i]<0) tmp+=vec[i];
    res = max(res, acc + tmp);
    if(vec[i-k+1]<0) tmp -= vec[i-k+1];
  }

  tmp=0;
  rep(i,k-1) if(vec[i]>0) tmp+=vec[i];
  repl(i,k-1,n){
    if(vec[i]>0) tmp+=vec[i];
    res = max(res, acc - tmp);
    if(vec[i-k+1]>0) tmp -= vec[i-k+1];
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n-1;i>=0;i--)
#define rep_re(i,s,n)for(int i = n;i>=0;i--)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_M = 100001;

ll a[100001] = {};

//unite x and y : p[uf(x)] = uf(y)
//same x and y : uf(x) == uf(y)
static const ll MAX_N = 100001;
ll p[MAX_N] = {};
ll uf(ll i) { return (p[i] == i) ? i : p[i] = uf(p[i]); }
void init_uf() { rep(i, 1, MAX_N)p[i] = i; }

int main() {
	ll n, m; cin >> n >> m;
	repe(i, 1, n) {
		cin >> a[i];
	}
	init_uf();
	rep(i, 0, m) {
		ll x, y; cin >> x >> y;
		if (uf(x) != uf(y))p[uf(x)] = uf(y);
	}
	ll ans = 0;
	repe(i, 1, n)if (uf(i) == uf(a[i]))ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
n = int(input())

ans = [0 for i in range(n)]
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            k = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if k <= n:
                ans[k-1] += 1
for i in range(n):
    print(ans[i])

Measured memory_bytes: 69180
#include <bits/stdc++.h>
#define DEBUG 0

#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define trav(a, x) for (auto & a : x)
#define all(x) (x).begin (), (x).end ()
#define sz(x) (int) (x).size ()
#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit);

typedef long long ll;

typedef pair <int, int> pii;
#define f first
#define s second
#define mp(x) make_pair (x)

typedef vector <int> vi;
#define pb(x) push_back (x)

#define ddcout if (DEBUG) cout
#define ddprintf(fmt, ...) if (DEBUG) printf (fmt, ##__VA_ARGS__)

#define EXIT ddprintf ("\nT.E. %lf\n", 1.0 * clock () / CLOCKS_PER_SEC); exit (0)

const ll   MOD   =  1e+9+7;
const ll   INF   =  0x3f3f3f3f3f3f3f3f;
const int  INFi  =  0x3f3f3f3f;
const ll   MAXN  =  1e+6+7;

int main ()
{
    FASTIO;
    int i, j, N;
    char c;
    scanf ("%d\n", &N);
    while (scanf ("%c", &c) != EOF)
    {
        if (c >= 'A' && c <= 'Z')
            printf ("%c", (c - 'A' + N) % 26  + 'A');
    }


    EXIT;
}


Measured memory_bytes: 256
N = input()

if int(N[-1]) == 2 or int(N[-1]) == 4 or int(N[-1]) == 5 or int(N[-1]) == 7 or int(N[-1]) == 9:
	print("hon")
elif int(N[-1]) == 0 or int(N[-1]) == 1 or int(N[-1]) == 6 or int(N[-1]) == 8:
	print("pon")
else:
	print("bon")


Measured memory_bytes: 9188