akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
 template<class T> inline bool chmax(T&a,T&b){if(a<b){a=b;return true;}return false;}
 template<class T> inline bool chmin(T&a,T&b){if(a>b){a=b;return true;}return false;}
 const ll INF = 1LL<<60;
 const ll M = 1000000007;
 ll mpow(ll a,ll b) {ll res=1;while(b!=0){if(b&1)res=res*a%M;a=a*a%M;b=b>>1;}return res;}
 ll mcomb(ll n,ll k){if(k>n/2)return mcomb(n,n-k);ll res=1;for(ll i=0;i<k;i++){res=res*(n-i)%M;res=res*mpow(k-i,M-2)%M;}return res;}
 */

int main(){
    string s,t;cin>>s>>t;
    ll count=0;
    for(ll i=0;i!=s.length();i++){
        if(s[i]!=t[i])count++;
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3920
#include<bits/stdc++.h>
using namespace std;
int road[20][20] = {0};
int main(){
    while(1){
        int W,H;
        cin >> W;
        cin >> H;
        if(W == 0 && H == 0){
            break;
        }
        int kp;
        cin  >> kp;
        vector<int>kpp[2];//0...x,1...y
        for(int i = 0;i < kp;i++){
            int x,y;
            cin >> x;
            cin >> y;
            kpp[0].push_back(x);
            kpp[1].push_back(y);
        }
        /*for(int i = 0;i < H;i++){
            for(int j = 0;j < W;j++){
                cout << road[i][j] << ' ';//3 0:2 1:1 2:0
            }
            cout << endl;
        }*/
        for(int i = 0;i < H;i++){
            for(int j = 0;j < W;j++){
                int f = 0;
                for(int k = 0;k < kp;k++){
                    if(i+1 == kpp[1][k] && j+1 == kpp[0][k]){
                        //cout << i+1 << ':' << j+1 << endl;
                        f = 1;
                        break;
                    }
                }
                if(i == 0 && j == 0){
                    road[i][j] = 1;
                }
                else if(i == 0 && f == 0){
                    road[i][j] = road[i][j-1];
                }
                else if(j == 0 && f == 0){
                    road[i][j] = road[i-1][j];
                }
                else if(f == 0){
                    road[i][j] = road[i-1][j]+road[i][j-1];
                }
            }
        }
        /*for(int i = 0;i < H;i++){
            for(int j = 0;j < W;j++){
                cout << road[H-1-i][j] << ' ';
            }
            cout << endl;
        }*/
        cout << road[H-1][W-1] << endl;
        for(int i = 0;i < 20;i++){
            for(int j = 0;j < 20;j++){
                road[i][j] = 0;
            }
        }
    }
    return 0;
}

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

 const int Maxn=1e5+2;
 const ll Lim=1e18;

 ll Arr[Maxn];

int Veri(ll Num){

 int Res=0;

 while(Num>=10){
  Num/=10;
  Res+=1;
 }

 return Res;
}

int main(){

 int N;
 cin>>N;
 int i;
 ll Ans=1;

 for(i=1;i<=N;i++){
    cin>>Arr[i];
    if(Arr[i]==0){
      cout<<0;
      return 0;
    }
 }

 int Cant;

 for(i=1;i<=N;i++){
    if(Arr[i]>Lim/Ans){
      cout<<-1;
      return 0;
    }

   Ans*=Arr[i];
 }

 if(Ans>Lim)cout<<-1;
 else cout<<Ans;
}


Measured memory_bytes: 4384
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void) {
	cin.tie(0);
	llint H,W,ans=1,i;cin>>H>>W;
	vector<int>A(H);for(i=0;i<H;i++){cin>>A[i];}SO(A);
	vector<int>B(W);for(i=0;i<W;i++){cin>>B[i];}SO(B);
	if(unique(A.begin(),A.end())!=A.end()){cout<<0<<endl;return 0;}REV(A);
	if(unique(B.begin(),B.end())!=B.end()){cout<<0<<endl;return 0;}REV(B);
	int Adco=0,Bdco=0;
	A.pub(-mod);B.pub(-mod);
	for(i=H*W;i>0;i--){
		int pta=0;
		if(A[Adco]==i){Adco++;pta+=2;}
		if(B[Bdco]==i){Bdco++;pta+=1;}
		if(pta==0){ans*=(Adco*Bdco)-(H*W-i);ans%=mod;}
		if(pta==1){ans*=Adco;ans%=mod;}
		if(pta==2){ans*=Bdco;ans%=mod;}
		//cerr<<ans<<endl;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 384
W, B = map(int, input().split())
S = 100

#上半分を白、下半分を黒にする。
# W,B<=500に対し、マップは 100*100=10000 と十分すぎるほど大きい
# これを利用し
# ***************
# * * * * * * * *
# ***************
# * * * * * * * *
# ***************
# と、一行おきに1マスおきに反対の色をおけばいい
# こうしても一行 S // 2 = 50 個配置可能。20行あればOK
# つまり100x100なら十分たりる

#0=white, 1=blackとする。最終的に .# にする
Mij = [[0 for _ in range(S)] for _ in range(S)]
for i in range(S):
    v = 0 if i < S // 2 else 1
    for j in range(S):
        Mij[i][j] = v

# 上に黒配置
count = 1
for i in range(1, S // 2, 2):
    for j in range(0, S, 2):
        if count < B:
            Mij[i][j] = 1
            count += 1
# 下に白配置
count = 1
for i in range(S - 1, S // 2, -2):
    for j in range(0, S, 2):
        if count < W:
            Mij[i][j] = 0
            count += 1

# 出力。白=0=.  /  黒=1=#
print(S, S)
for mi in Mij:
    txt = ""
    for m in mi:
        if m == 0:
            txt += "."
        else:
            txt += "#"
    print(txt)


Measured memory_bytes: 3188
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans = count = 0

n=int(input())
n%=500
a=int(input())
if a>=n:
    print("Yes")
else:
    print("No")

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

int main(){
    int n;
    scanf("%d",&n);
    string s;
    cin >> s;
    string t;
    if(n%2==0){
        for (int i=0;i<n/2;i++) t.push_back(s[i]);
        if(s==t+t) printf("Yes\n");
        else printf("No\n");
    }
    else printf("No");
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
	int n;
	int a, b;
	
	while (1){
		cin >> n;
		if (n == 0)break;
		
		a = b = 0;
		for (int i = 0; i < n; i++){
			int ca, cb;
			cin >> ca >> cb;
			if (ca > cb){
				a += ca + cb;
			}
			else if (ca == cb){
				a += ca;
				b += cb;
			}
			else {
				b += ca + cb;
			}
		}
		
		cout << a << ' ' << b << endl;
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <functional>
#include <unordered_map>
#define int long long 
#define pi pair<int,int> 
#define endl "\n"
using namespace std ;

const int inf = 1e15 ;
const int size = 1e3 + 5 ;
const int mod = 1e9 + 7 ;
int dp[size][size] ;
char a[size][size] ;

int add(int b , int c )
{
     if(b+c >= mod ) return b+c-mod ;
     else return b+c ;
}


int32_t main() 
{


   /*  #ifndef ONLINE_JUDGE 
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     #endif*/
     int h , w ;
     cin >> h >> w ;
     for(int i = 1 ;i <= h ; i++ )
     {
         for( int j = 1; j <= w ; j++ )
         {
             cin >> a[i][j] ;
         }
     }
     dp[1][0] = 1 ;
     for(int i = 1 ; i <= h ; i ++ )
     {
         for(int j = 1; j <= w ; j++ )
         {
              if(a[i][j] != '#')dp[i][j] = add(dp[i-1][j] , dp[i][j-1]);
              // cout<<dp[i][j]<<" ";
         }//cout<<endl;
     }
     cout<<dp[h][w]<<endl;
    return 0 ;
}


Measured memory_bytes: 9088
package main

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

type Scanner struct {
  sc *bufio.Scanner
  buf []byte
}

func NewScanner(r io.Reader) *Scanner {
  s := &Scanner{
    sc: bufio.NewScanner(r),
  }
  s.sc.Split(bufio.ScanWords)
  s.sc.Buffer(s.buf, bufio.MaxScanTokenSize)
  return s
}

func (s *Scanner) nextInt() int {
  if s.sc.Scan() {
    i, err := strconv.Atoi(s.sc.Text())
    if err != nil {
      panic(err)
    }
    return i
  }
  panic("failed to scan")
}

func (s *Scanner) nextString() string {
  if s.sc.Scan() {
    return s.sc.Text()
  }
  panic("failed to scan")
}

func max(a ...int) int {
  m, s := a[0], a[1:]
  for _, v := range s {
    if m < v {
      m = v
    }
  }
  return m
}

func solve(r io.Reader) {

  sc := NewScanner(r)
  N := sc.nextInt()

  p := make([]int, 3)
  dp := make([]int, 3)

  dp[0] = sc.nextInt()
  dp[1] = sc.nextInt()
  dp[2] = sc.nextInt()
  p[0], p[1], p[2] = dp[0], dp[1], dp[2]

  for i := 1; i < N; i++ {
    a := sc.nextInt()
    b := sc.nextInt()
    c := sc.nextInt()

    dp[0] = a + max(p[1], p[2])
    dp[1] = b + max(p[0], p[2])
    dp[2] = c + max(p[0], p[1])
    
    p[0], p[1], p[2] = dp[0], dp[1], dp[2]
  }
  fmt.Println(max(dp...))  
}

func main() {
  solve(os.Stdin)
}


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



int main(){
	
	int n,m;
	map <string,int>mp;
	int o=0;
	cin>>n;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		mp[s]=1;
	}
	cin>>m;
	for(int i=0;i<m;i++){
		string s;
		cin>>s;
		if(mp[s]){
			if(o==0){
				o=1;
				cout<<"Opened by "<<s<<endl;
			}else{
				o=0;
				cout<<"Closed by "<<s<<endl;
			}
			
		}else cout<<"Unknown "<<s<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1240
from itertools import permutations

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

cnt = 0

for i in permutations([i for i in range(1, N+1)]):
    a_cnt = 0
    b_cnt = 0
    for j in range(N):
        if i[j] == P[j]:
            a_cnt += 1

        if i[j] == Q[j]:
            b_cnt += 1

    if a_cnt == N:
        a = cnt

    if b_cnt == N:
        b = cnt

    cnt += 1

print(abs(a-b))


Measured memory_bytes: 3064
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9+7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,S,T,U,V,W,x,y,z;
long long max_value = INF, max_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

template <std::int_fast64_t Modulus> class modint {
  using u64 = std::int_fast64_t;
public:
  u64 a;
  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};
#pragma endregion

map<string, int> _map;
int main() {
    cin >> N;
    char s[10];
    ll count = 0;
    rep(i, N){
        cin >> s;
        sort(s, s+10);
        if(_map.count(s) == 0){
            _map[s] = -1;
        }    
        _map[s]++;
        count += _map[s];
    }
    cout << count;
} 



Measured memory_bytes: 11136
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<ctime>
#include<cstdlib>
#include<numeric>
#include <typeinfo>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(i=a;i<b;i++)
#define rloop(i,a,b) for(i=a;i>=b;i--)
const int inf=1e8;
const ll INF=1e16;
#define MOD 1000000007
#define mod 1000000009

void bubble(char *m1,int *k1,int n);
void selection(char *m2,int *k2,int n);
void is_stable(char *m,int *k,char *m1,int *k1,int n);
int main(){
	int n,i;
	cin>>n;
	char m,m1[n],m2[n];
	int k,k1[n],k2[n];
	loop(i,0,n){
		cin>>m>>k;
		m1[i]=m;m2[i]=m;
		k1[i]=k;k2[i]=k;
	}
	bubble(m1,k1,n);
	selection(m2,k2,n);
	
}

void bubble(char *m1,int *k1,int n){
	int i,j;
	char m[n];
	int k[n];
	loop(i,0,n){
		m[i]=m1[i];
		k[i]=k1[i];
	}
	loop(i,0,n){
		rloop(j,n-1,i+1){
			if(k1[j]<k1[j-1]){
				int t=k1[j];
				k1[j]=k1[j-1];
				k1[j-1]=t;
				char a=m1[j];
				m1[j]=m1[j-1];
				m1[j-1]=a;
			}
		}
	}
	cout<<m1[0]<<k1[0];
	loop(i,1,n){
		cout<<" "<<m1[i]<<k1[i];
	}
	cout<<"\n";
	is_stable(m,k,m1,k1,n);
}

void selection(char *m2,int *k2,int n){
	int i,j;
	char m[n];
	int k[n];
	loop(i,0,n){
		m[i]=m2[i];
		k[i]=k2[i];
	}
	loop(i,0,n){
		int minj=i;
		loop(j,i,n){
			if(k2[j]<k2[minj]){
				minj=j;
			}
		}
		int t=k2[i];
		k2[i]=k2[minj];
		k2[minj]=t;
		char a=m2[i];
		m2[i]=m2[minj];
		m2[minj]=a;
	}
	cout<<m2[0]<<k2[0];
	loop(i,1,n){
		cout<<" "<<m2[i]<<k2[i];
	}
	cout<<"\n";
	is_stable(m,k,m2,k2,n);
}

void is_stable(char *m,int *k,char *m1,int *k1,int n){
	int i,j;
	int flag=0;
	loop(i,1,9){
		vector<char> a,b;
		loop(j,0,n){
			if(k1[j]==i){
				a.push_back(m1[j]);
			}
			if(k[j]==i){
				b.push_back(m[j]);
			}
		}
		if(a!=b){
			cout<<"Not stable"<<"\n";
			return;
		}
	}
	cout<<"Stable"<<"\n";
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int MOD = 1000000007;

int main()
{
	int n = 0;
	cin >> n;
	string ans = "";
	if (n == 25)
	{
		ans = "Christmas";
	}
	else if (n == 24)
	{
		ans = "Christmas Eve";
	}
	else if (n == 23)
	{
		ans = "Christmas Eve Eve";
	}
	else if (n == 22)
	{
		ans = "Christmas Eve Eve Eve";
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
N=int(input())
S=input()
ans = 0
for i in range(1,N-1):
  X = [0] * 26
  cnt = 0
  for x in range(i):
    X[ord(S[x])-ord('a')] = 1
  for y in range(i,N):
    if ( X[ord(S[y])-ord('a')] == 1 ):
      cnt += 1
      X[ord(S[y])-ord('a')] = 0
  ans = max(ans,cnt)
print(ans)

    
  

Measured memory_bytes: 3064
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;

string operator-(const string &a, const string &b) {
	char buff[128];
	sprintf(buff, "%04d", stoi(a) - stoi(b));
	return string(buff);
}

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

	const string goal = "6174";

	for(string n; cin >> n && n != "0000";) {
		if(all_of(n.begin(), n.end(), [&](char c) { return c == n.front(); })) {
			cout << "NA" << endl;
			continue;
		}

		int cnt = 0;
		while(n != goal) {
			string L(n), S(n);
			sort(L.rbegin(), L.rend());
			sort(S.begin(), S.end());
			n = L - S;
			++cnt;
		}

		cout << cnt << endl;
	}

	return EXIT_SUCCESS;
}

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

int main() {
    ll a,b,n;
    cin>>a>>b>>n;
    if(b<=n){
        cout<<floor(a*(b-1)/double(b))<<endl;
    }
    else{
        cout<<floor(a*n/double(b))<<endl;
    }
    return 0;
}


Measured memory_bytes: 3872
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int str_cmp(const void*a,const void*b)
{
  return strcmp((char*)a,(char*)b);
}
void main(void)
{
  
  int N;
  scanf("%d",&N);
  char str[N][11];
  for(int i=0;i<N;i++){
    scanf("%s",str[i]);
  }
  qsort(str,N,11,str_cmp);
  int ans=1;
  
  for(int i=0;i<(N-1);i++){
    if(strcmp(str[i],str[i+1])!=0){
      ans++;
    }
  }
  printf("%d",ans);

  //for(int i=0;i<N;i++){
   // printf("%s\n",str[i]);
  //}
}

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

int main(){
  int N, K;
  std::cin >> N >> K;
  std::vector<int> d(K);
  std::vector<bool> posess(N, false);
  for(int i = 0; i < K; ++i){
    std::cin >> d[i];
    for(int j = 0; j < d[i]; ++j){
      int num;
      std::cin >> num;
      posess[num-1] = true;
    }
  }
  int count = 0;
  for(int i = 0; i < N; ++i){
    if(!posess[i]){
      ++count;
    }
  }
  std::cout << count << std::endl;
  return 0;
}


Measured memory_bytes: 3640
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

long long int INF = 1000000000000000000LL; // 10^18
using namespace std;

typedef pair<int, int> P;

int W, H, N;

long long int X[200000], X_[200000];
long long int Y[200000], Y_[200000];

long long int dist(int cx, int cy){
	long long int D = 0;
	long long int Dmax = 0;
	for(int i = 0; i < N; i++){
		D += 2 * abs(X[i] - cx);
		D += 2 * abs(Y[i] - cy);
		Dmax = max(Dmax, abs(X[i] - cx) + abs(Y[i] - cy));
	}
	return D - Dmax;
}

int main(){
	
	cin >> W >> H >> N;
	
	for(int i = 0; i < N; i++){
		cin >> X[i] >> Y[i];
		X_[i] = X[i];
		Y_[i] = Y[i];
	}
	
	sort(X_, X_ + N);
	sort(Y_, Y_ + N);
	
	long long int cx1 = X_[(N - 1) / 2];
	long long int cx2 = X_[N / 2];
	long long int cy1 = Y_[(N - 1) / 2];
	long long int cy2 = Y_[N / 2];
	
	long long int ans = INF;
	long long int ansx, ansy;
	long long int ret;
	ret = dist(cx1, cy1);
	if(ret < ans){
		ans = ret;
		ansx = cx1;
		ansy = cy1;
	}
	ret = dist(cx1, cy2);
	if(ret < ans){
		ans = ret;
		ansx = cx1;
		ansy = cy2;
	}
	ret = dist(cx2, cy1);
	if(ret < ans){
		ans = ret;
		ansx = cx2;
		ansy = cy1;
	}
	ret = dist(cx2, cy2);
	if(ret < ans){
		ans = ret;
		ansx = cx2;
		ansy = cy2;
	}
	
	cout << ans << endl;
	cout << ansx << " " << ansy << endl;
	
	return 0;
}


Measured memory_bytes: 6292
from collections import Counter

N = int(input())
S = input()
ans = 0

for j in range(1, N-1):
    cl, cr = Counter(S[:j]), Counter(S[j+1:])
    
    for i in set(cl.keys())-set(S[j]):
        ans += cl[i]*(N-1-j-cr[S[j]]-cr[i])
            
    for i in range(1, min(j, N-1-j)+1):
        if S[j] != S[j-i] and S[j] != S[j+i] and S[j-i]!=S[j+i]:
            ans -= 1
    
print(ans)
    

Measured memory_bytes: 76808
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <memory>
#include <functional>

using namespace std;

#define ALL(a) (a).begin(),(a).end()
#define REP(index, begin, end) for (int (index) = (begin); (index) < (end); (index)++)
#define RE(index, end) REP(index, 0, end)
#define INF INT_MAX / 3
#define DINT(x) printf(#x " = %d\n", x);
#define GETINT(x) scanf("%d", &x)
#define GETSTR(x) scanf("%s", x)

typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef long long ll;

struct column_num
{
	int white,
		blue,
		red;
};

int main()
{
	int h, w;
	array<column_num, 50> row;
	GETINT(h);
	GETINT(w);
	RE(i, h)
	{
		char temp[256] = {};
		GETSTR(temp);
		column_num col = {};
		RE(j, w)
		{
			switch (temp[j])
			{
			case 'W':
				col.white++;
				break;
			case 'B':
				col.blue++;
				break;
			case 'R':
				col.red++;
				break;
			}
		}
		row[i] = col;
	}
	int result = 0;
	REP(w_len, 0, h - 2)
	{
		int w_sum = 0;
		REP(i, 0, w_len + 1)
		{
			w_sum += row[i].white;
		}
		REP(b_len, w_len + 1, h - 1)
		{
			int b_sum = 0;
			REP(i, w_len + 1, b_len + 1)
			{
				b_sum += row[i].blue;
			}
			{
				int r_sum = 0;
				REP(i, b_len + 1, h)
				{
					r_sum += row[i].red;
				}
				int sum_all = w_sum + b_sum + r_sum;
				if (result < sum_all)
				{
					result = sum_all;
				}
			}
		}
	}
	printf("%d\n", (w * h) - result);
	return 0;
}

Measured memory_bytes: 3188
#include <algorithm>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

struct S
{
  int count{0};
  long sum{0};
  int left_index{-1};
  int right_index;
  std::multiset<long> negatives;

  S(int r_index) : right_index{r_index} {}

  bool operator<(const S& rhs) const
  {
    return std::make_tuple(left_index, right_index)
        < std::make_tuple(rhs.left_index, rhs.right_index);
  }
};

void push(const S& s, std::queue<S>& q, std::set<S>& used)
{
  used.insert(s);
  q.push(s);
}

long refund(S s, int k)
{
  const auto n = std::min(
      static_cast<int>(s.negatives.size()),
      k - s.count);
  auto it = s.negatives.begin();
  for (int i = 0; i < n; ++i) {
    s.sum -= *it;
    ++it;
  }
  return s.sum;
}

long solve(int k, const std::vector<long>& values)
{
  const int n = static_cast<int>(values.size());
  std::queue<S> q;
  std::set<S> used;

  long max = 0;
  S s0(n);
  push(s0, q, used);

  while (!q.empty()) {
    S s = q.front();
    q.pop();

    if (s.count >= k) continue;

    if (s.left_index + 1 < s.right_index) {
      s.count += 1;

      {
        S s1 = s;
        s1.left_index += 1;
        if (used.count(s1) == 0) {
          long v1 = values[s1.left_index];
          s1.sum += v1;
          if (v1 < 0) s1.negatives.insert(v1);
          max = std::max(max, s1.sum);
          push(s1, q, used);

          if (v1 > 0
              && !s1.negatives.empty()
              && k - s1.count <= static_cast<int>(s1.negatives.size())) {
            max = std::max(max, refund(s1, k));
          }
        }
      }

      {
        S s2 = s;
        s2.right_index -= 1;
        if (used.count(s2) == 0) {
          long v2 = values[s2.right_index];
          s2.sum += v2;
          if (v2 < 0) s2.negatives.insert(v2);
          max = std::max(max, s2.sum);
          push(s2, q, used);

          if (v2 > 0
              && !s2.negatives.empty()
              && k - s2.count <= static_cast<int>(s2.negatives.size())) {
            max = std::max(max, refund(s2, k));
          }
        }
      }
    } else {
      max = std::max(max, refund(s, k));
    }
  }

  return max;
}

int main()
{
  int n, k;
  std::cin >> n >> k;

  std::vector<long> values(n);
  for (auto& v : values) {
    std::cin >> v;
  }

  std::cout << solve(k, values) << std::endl;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = (1e9)+7;
void fastIO(){
  ios_base::sync_with_stdio(0); cin.tie(0);
}


int main(){
  fastIO();
  int a,b,c;
  cin>>a>>b>>c;
  int cnt = 0;
  int multiple = a;
  while(cnt<=1000){
  	cnt++;
  	if((a-c)%b==0){
  		cout<<"YES"<<endl;
  		return 0;
  	}
  	a+=multiple;
  }
  cout<<"NO"<<endl;
}  





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define arep(a,i,n) for(ll i=(a);i<(n);i++)
#define rep(i,n) for(ll i=0;i<(n);i++)
#define cinf(x,n) for(ll i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(ll i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

ll cnt[100010];

int main(){
	ll n,k;
	cin >> n >> k;
	rep(i,n){
		ll a,b;
		cin >> a >> b;
		cnt[a]+=b;
	}
	ll sum=0;
	arep(1,i,100010){
		sum+=cnt[i];
		if(sum>=k){
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 4388
/*****Enigma_27*****/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pll         pair<ll,ll>
#define vll          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define f           first
#define s           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define ios        	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,i,j,k1,l,sum=0,ans=0,k,var,a[100005]={0},x,y,z,k2;
int main()
{
    ios
    ll ans=1;
    cin>>n>>k;
    while(n--)
    {
        if(ans>k) ans+=k;
        else ans*=2;
        
    }
    cout<<ans<<endl;
 	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
signed main()
{
    SPEED
    double l;
    cin>>l;
    cout<<fixed<<setprecision(6)<<(l/3)*(l/3)*(l/3);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long ll;

string beautify(string str) {
	string ret = "";
	for (int i = 0; i < str.size(); ++i) {
		char c = str[i];
		if ('a' <= c && c <= 'z') ret += c;
		else if ('A' <= c && c <= 'Z') ret += (char)(c-'A'+'a');
	}
	return ret;
}

int main() {
	string word, key; cin >> key; key = beautify(key);
	int ans = 0;
	while ( cin >> word, word != "END_OF_TEXT" ) {
//		if (word[word.size()-1] == '.') word = word.substr(0, word.size()-1);
//		if (word[0] == '\"') word = word.substr(1, word.size()-1);
//		if (word[word.size()-1] == '\"') word = word.substr(0, word.size()-1);
		word = beautify(word);
		if (word == key) {
			++ans;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 1200
#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)

int main(void) {
	int n,tmp,max;
	char s[101];
	
	scanf("%d %s",&n,s);
	
	tmp = 0;
	max = 0;
	for (int i = 0;s[i] != '\0';i++) {
		if (s[i] == 'I') {
			tmp++;
		} else {
			tmp--;
		}
		max = MAX(max,tmp);
	}
	printf("%d\n",max);
	
	return 0;
}


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

long long int main(void){
	long long int n,k;
	scanf("%lld %lld",&n,&k);
	n=n%k;
	if(n>abs(n-k)){
		n=k-n;
	}
	printf("%lld\n",n);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<math.h>

using namespace std;
#define C(_Str) cout << _Str << endl
typedef long long int lli;

int main()
{
	int Num,i=0,j=0,k=0;
	vector<int> Car(100);
	vector<int> Out(100);
	while (cin >> Num) {
		
		if (Num != 0) {
			Car[i] = Num;
			i++;
		}
		else {
			i--;
			Out[j] = Car[i];
			j++;
		}
	}
	while (Out[k]) { 
		cout << Out[k] << endl;
		k++;
	}
	return 0;
}

Measured memory_bytes: 2936
#coding: utf-8

inf = 1000000000
n = int(input())
mtrx = []
for i in range(n):
    col2 = list(map(int,input().split()))
    col = []
    for num in col2:
        if num == -1:
            num = inf
        col.append(num)
    mtrx.append(col)

def prim():
    color = ["white" for i in range(n)]
    d = [inf for i in range(n)]
    p = [None for i in range(n)]
    p[0] = -1
    d[0] = 0

    while True:
        mincost = inf
        for i in range(n):
            if color[i] != "black" and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == inf:
            break

        color[u] = "black"

        for v in range(n):
            if color[v] != "black" and mtrx[u][v] != inf:
                if mtrx[u][v] < d[v]:
                    d[v] = mtrx[u][v]
                    p[v] = u
                    color[v] = "gray"
    print(sum(d))

prim()




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

int main(){
  string N;
  cin>>N;
  int A =(int)N.size();
  if(N.at(A-1)=='3'){
    cout<<"bon"<<endl;
  }else if(N.at(A-1)=='0'||N.at(A-1)=='1'||N.at(A-1)=='6'||N.at(A-1)=='8'){
    cout<<"pon"<<endl;
  }else{
    cout<<"hon"<<endl;
  }
}
  

Measured memory_bytes: 3600
//  Author : Amit Kumar 

#include <iostream>
#include <algorithm> 
#include <string> 
#include <sstream>
#include <fstream>
#include <iomanip> 
#include <chrono> 
#include <numeric> 
#include <utility>
#include <functional>

#include <bitset>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <map>
#include <deque>
#include <list>


#include <climits>
#include <cstring>
#include <cmath>
#include <cassert>
#include <cstdio>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace std::chrono;
//  using namespace placeholders;
using namespace __gnu_pbds;
template<typename TypeInfo>
using new_set = tree< 
/* ob.order_of_key(element) -> number of element strictly less than element
 * *ob.find_by_order(n) ->  nth element in increasing order
 */
         TypeInfo ,
         null_type ,
         less<TypeInfo> ,
         rb_tree_tag ,
         tree_order_statistics_node_update 
 > ;

void show_me() { cerr << endl; }
 
template <typename HEAD, typename... TAIL>
void show_me(HEAD H, TAIL... T) {
  cerr << " " << (H);
  show_me(T...);
}
 
#ifdef HELL_JUDGE
#define show(...) cerr << "[" << #__VA_ARGS__ << "]:", show_me(__VA_ARGS__)
#else
#define show(...) 0
#endif
 
template<typename A, typename B>
ostream& operator<<(ostream&out, const pair<A, B>&p){
    out << p.first << ' ' << p.second ;
    return out;
}

template<typename A, typename B>
istream& operator>>(istream&in, pair<A, B>&p){
    in >> p.first >> p.second ;
    return in;
}

template<typename A> 
istream& operator>>(istream&in, vector<A>&vec){
    for(auto&itr:vec){
        in >> itr;
    }
    return in;
}

template<typename A>
ostream& operator<<(ostream&out,const vector<A>&vec){
    for(auto&itr:vec){
        out << itr <<' '; // VVV 
    }
    return out;
}

const int MAXM = (int)1e5+100;
const int MAXN = (int)1e5+100;
const int MOD  = (int)1e9+7;




signed main(void){
#ifdef HELL_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    freopen("error","w",stderr);
#endif 
    ios::sync_with_stdio(false); // FLUSH THE STREAM IF USING puts / printf / scanf/
    cin.tie(nullptr);            //
    cout.tie(nullptr);           //
#ifdef HELL_JUDGE
    auto INITIAL_TIME = high_resolution_clock::now();
#endif 
    char c; cin >> c; 
    if(c>='a' && c<='z'){
        cout << 'a' << '\n' ;
    }else{
        cout << 'A' << '\n' ; 
    }


#ifdef HELL_JUDGE
    auto FINAL_TIME = high_resolution_clock::now();
    cout << "Time : "
         << duration_cast<milliseconds>(FINAL_TIME-INITIAL_TIME).count() 
         << " ms" << '\n'; 
#endif 
    return 0;
}


Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i, j) FOR(i, 0, j)
#define FOR(i, j, k) for(int i = j; i < k; ++i)

using namespace std;

int main(){
  int K;
  while(scanf("%d", &K) && K){
    int sum = 0, c;
    rep(i, K*(K-1)/2){
      scanf("%d", &c);
      sum += c;
    }
    printf("%d\n", sum / (K-1));
  }
  return 0;
}

Measured memory_bytes: 1028
N,M,P = map(int,input().split())
abc = []
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    #向かってくる矢印
    edge[b-1].append(a-1)
    abc.append((a-1,b-1,P-c))

def dfs(edge,goal):
    #goal = n-1
    used = {goal}
    q = [goal]
    while q:
        v = q.pop()
        for w in edge[v]:
            if w in used:continue
            used.add(w)
            q.append(w)
    
    return used

def bellman_ford(v,s,g,e):

    '''
    v: vertex(頂点)
    s: start.  in this case,0
    g: goal. in this case,n-1
    e: (edge_start,egde_goal,score)
    今回はp-cの最小値を求めていく.
    '''
    inf = 10**10
    # cost : d[V] 
    d = [inf] * v
    #開始点のコストを0とする
    d[s] = 0
    for _ in range(v):
        flag = False
        for a,b,c in e:
            # a -> b の向きを考える
            if d[a] == inf:continue
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                flag = True
        if not flag: break
    if flag:
        return -1
    return max(-d[g],0)

vertex = dfs(edge,N-1)
abc_ = [(a,b,c) for a,b,c in abc if a in vertex and b in vertex]
print(bellman_ford(N,0,N-1,abc_))


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

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    string s;
    cin >> s;
    int in = 0;
    int out = 0;
    for (int i=0; i<s.length(); i++){
        if (s[i] == 'a'){
            if (in + out < A + B){
                cout << "Yes" << endl;
                in++;
            } else{
                cout << "No" << endl;
            }
        } else if (s[i] == 'b'){
            if ((out < B) && (in + out < A + B)){
                cout << "Yes" << endl;
                out++;
            } else{
                cout << "No" << endl;
            }
        } else{
            cout << "No" << endl;
        }
    }
    return 0;
}


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

using namespace std;

using ll = long long;

int main() {
    ll N, K;
    cin >> N >> K;
    std::string S;
    cin >> S;

    //R->L
    std::deque<ll> border_rl;

    //L->R
    std::deque<ll> border_lr;

    ll count = 0;
    for (ll i = 0; i < N - 1; ++i) {
        if (S[i] == 'R' && S[i + 1] == 'L') { border_rl.emplace_back(i); }
        else if (S[i] == 'L' && S[i + 1] == 'R') { border_lr.emplace_back(i); }
        else { ++count; }
    }

    for (ll i = 0; i < K; ++i) {
        if (!border_lr.empty() && !border_rl.empty()) {
            count += 2;
            border_lr.pop_back();
            border_rl.pop_back();
        } else if (!border_lr.empty() && border_rl.empty()) {
            if (S[N - 1] == 'R' || S[0] == 'L') {
                ++count;
                border_lr.pop_front();
            }

        }else if (border_lr.empty() && !border_rl.empty()) {
            if (S[N - 1] == 'L' || S[0] == 'R') {
                ++count;
                border_rl.pop_front();
            }
        }
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
 
void update(int q, int& last, int& d) {
    if (d != 0 and q%2 != last%2) d = 3-d;
    last = q;
}
 
pair<vector<int>, vector<int>> solve(int n, const string& T) {
    if (n == 0) {
        vector<int> P = {0};
        vector<int> W(T.size(), 0);
        return {P, W}; 
    }
    auto pp = solve(n-1, T);
    const auto& P = pp.first;
    const auto& W = pp.second;
    vector<int> new_W(W.size());
    int pot = P.size();
    vector<int> D(3*pot);
    for (int i = 0; i < 3; i++) for (int x = 0; x < pot; x++) D[i*pot + x] = i;
    vector<int> last(3*pot, 0);
    int q = 0;
    for (int i = 0; i < (int)T.size(); i++) {
        int k = W[i];
        for (int x = k; x < 3*pot; x += pot) {
            update(q, last[x], D[x]);
            if (D[x] == 2) new_W[i] = x;
        }
        if (T[i] == 'S') q++;
        if (T[i] == 'R') {
            for (int x = k; x < 3*pot; x += pot) D[x] = (D[x]+1)%3;
        }
    }
 
    vector<int> new_P(3*pot);
    for (int i = 0; i < 3*pot; i++) {
        update(q, last[i], D[i]);
        new_P[i] = P[i%pot] + D[i] * pot;
    }
 
    return {new_P, new_W};
}
 
int main() {
    int N;
    cin >> N;
    string T;
    cin >> T;
    vector<int> P = solve(N, T).first;
    for (int x: P) cout << x << " ";
    cout << "\n";
}


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

namespace TOPSIC
{
    partial class Program
    {
        static void Main(string[] args)
        {
          //入力値をスペース区切りで配列に格納
            string[] inputStr = Console.ReadLine().Split(' ');

            int A = int.Parse(inputStr[0]);
            int B = int.Parse(inputStr[1]);
            int C = int.Parse(inputStr[2]);

            if (!((A == B && B == C) || (A != B && B != C && A != C)))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }
    }
}

Measured memory_bytes: 11092
N,x = map(int, input().split())
A = [int(i) for i in input().split()]

"""
「ちょうど」でｷｬｯｷｬ
"""

A.sort()

from itertools import accumulate

A = tuple(accumulate(A))

ans = N - 1
for i,a in enumerate(A):
    if x > a:
        pass
    elif x == a:
        ans = i + 1
        break
    else:
        ans = i
        break

print(ans)

Measured memory_bytes: 3060
def main():
    n, q = map(int, input().split())
    ss = list(input())
    lrs = [list(map(int, input().split())) for _ in range(q)]
    cum_sum = [0] * n
    for i in range(1, n):
        if ss[i-1] == 'A' and ss[i] == 'C':
            cum_sum[i] += 1
        cum_sum[i] += cum_sum[i-1]
    for l, r in lrs:
        print(cum_sum[r-1]-cum_sum[l-1])


if __name__ == "__main__":
    main()


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

int main(){
    int N;
    cin >> N;
    vector<double> v(N);

    for (int i = 0;i < N;i++){
        cin >> v.at(i);
    }

    sort(v.begin(),v.end());

    double a = (v.at(0) + v.at(1)) / 2;
    for (int i = 2;i < N;i++){
        a = (a + v.at(i)) / 2;
    }

    cout << a << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int K;
double ans;
double L, R, P, T, E;

void dfs(double l, double r, int k, double p)
{
	//printf("##%f %f %d %f\n", l, r, k, p);
	double m = (l+r)/2;
	if (k==K)
	{
		if (fabs(m-T)<=E) ans += p;
		return;
	}
	if (l>=T-E && r<=T+E)
	{
		ans += p;
		return;
	}
	if (l>T+E) return;
	if (r<T-E) return;
	if (m >= T)
	{
		dfs(l, m, k+1, p*(1-P));
		dfs(m, r, k+1, p*P);
	}
	else
	{
		dfs(l, m, k+1, p*P);
		dfs(m, r, k+1, p*(1-P));
	}
}

int main()
{
	scanf("%d", &K);
	scanf("%lf%lf%lf%lf%lf", &L, &R, &P, &E, &T);
	//printf("%f %f\n", T-E, T+E);
	dfs(L, R, 0, 1);
	printf("%.7f\n", ans);
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;


//-------------------------------------------------------------------
const int MAX_V = 51;
vvi G = vv(MAX_V, 0, 0, int);
int root;
int parent[30][MAX_V];
vector<int> depth(MAX_V);

void dfs(int v, int p, int d){
  parent[0][v] = p, depth[v] = d;
  for(int i=0;i<G[v].size();i++) if(G[v][i] != p) dfs(G[v][i], v, d+1);
}
void init(int V){
  dfs(root, -1, 0);
  for(int k=0;k+1<30;k++){
    for(int v=0;v<V;v++){
      if(parent[k][v]<0) parent[k+1][v] = -1;
      else parent[k+1][v] = parent[k][parent[k][v]];
    }
  }
}
int lca(int u, int v){
  if(depth[u]>depth[v]) swap(u, v);
  for(int k=0;k<30;k++)if((depth[v]-depth[u])>>k & 1) v = parent[k][v];
  if(u==v) return u;
  for(int k=30-1;k>=0;k--){
    if(parent[k][u] != parent[k][v]){
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}
ll n, m;
vll ci{0}, cicle(51, 0);
vvl q = vv(0, 2, 0, ll);
vector<bitset<20>> x(51);

void dfs(ll now, ll from){
  ci.push_back(now);
  for(int i=0;i<G[now].size();i++){
    if(G[now][i]==from) continue;
    dfs(G[now][i], now);
  }
}

map<vll, ll> mp;
vector<ll> skil(51);
void coman(ll now, ll aim, ll num){
  if(now==aim) return ;
  skil[mp.at(vll{now, parent[0][now]})] |= (1<<num);
  coman(parent[0][now], aim, num);
}

int main(int argc, char const *argv[]) {
  ll a, b;std::cin >> n;
  re(i, n-1){
    std::cin >> a >> b;
    mp.emplace(vll{a, b}, i);
    mp.emplace(vll{b, a}, i);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(1, -1);
  root = 1;
  init(51);
  std::cin >> m;

  re(i, m){
    std::cin >> a >> b;
    ll x = lca(a, b);
    coman(a, x, i);
    coman(b, x, i);
  }
  vvl dp = vv(n+1, (1<<20), 0, ll);
  dp[0][0] = 1;

  for(int i=0;i<n;i++){
    for(int j=0;j<(1<<20);j++){
      dp[i+1][j|skil[i]] += dp[i][j];
      dp[i+1][j] += dp[i][j];
    }
  }
  std::cout << dp[n-1][(1<<m)-1] << '\n';
  return 0;
}


Measured memory_bytes: 426496
#include <stdio.h>
int matrixChainMultiplication();
#define Y 10000001
int n,p[101],m[102][102];
int main(){
  int i;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d%d",&p[i-1],&p[i]);
  printf("%d\n",matrixChainMultiplication());
  
  return 0;
}
int matrixChainMultiplication(){
  int i,l,j,k;
  for(i=1;i<=n;i++)
    m[i][i]=0;

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


Measured memory_bytes: 2144
#include<bits/stdc++.h>
#define ll long long
const int N=100005;
using namespace std;
int h[N],f[N],n,a,b,m,ans;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		f[a]=max(f[a],h[b]);
		f[b]=max(f[b],h[a]);
	}
	for(int i=1;i<=n;i++)
	    if(h[i]>f[i]) ans++;
	cout<<ans;
    return 0;
}

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

count = 0
flag = 0

for i in range(N):
  N,M = map(int, input().split())
  if N == M:
    count += 1
  else:
    count = 0
  if count >= 3:
    flag = 1
   
if flag == 1:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9100
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;

vector<ll> a,f;
int n;

ll solve(ll m) {
    ll res = 0;
    REP(i,n) {
        res += max(0LL,a[i] - m / f[i]);
    }
    return res;
}

int main() {
    
    ll k;
    cin >> n >> k;
    a.resize(n);
    f.resize(n);
    REP(i,n) cin >> a[i];
    REP(i,n) cin >> f[i];
    sort(a.begin(),a.end());
    sort(f.rbegin(),f.rend());
    ll l = -1,r = LLINF;
    while(r - l > 1) {
        ll mid = l + (r - l) / 2;
        if (solve(mid) <= k) {
            r = mid;
        }
        else {
            l = mid;
        }
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 3328
# import itertools
import math
from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

if gcd_list(A) > 1:
    print("not coprime")
    exit()


MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p, MAXN+1, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1

st = set()
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')


Measured memory_bytes: 127636
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner stdIn=new Scanner(System.in);
		int s=stdIn.nextInt();
		int h=s/3600;
		s%=3600;
		int m=s/60;
		s%=60;
		System.out.println(h+":"+m+":"+s);
	}
}

Measured memory_bytes: 26328
package main

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

var stdin = bufio.NewScanner(os.Stdin)

func main() {
	arr := scanArrayInt()
	n, k, q := arr[0], arr[1], arr[2]
	as := make([]int, q)
	for i := 0; i < q; i++ {
		as[i] = func() int { stdin.Scan(); i, _ := strconv.Atoi(stdin.Text()); return i }()
	}
	if k > q {
		for i := 0; i < n; i++ {
			fmt.Println("Yes")
		}
		return
	}
	points := map[int]int{}
	for i := 0; i < q; i++ {
		points[as[i]-1]++
	}
	for i := 0; i < n; i++ {
		if q-k < points[i] {
			fmt.Println("Yes")
			continue
		}
		fmt.Println("No")
	}
}
func scanArrayInt() []int {
	var ret = []int{}
	stdin.Scan()
	for _, s := range strings.Split(stdin.Text(), " ") {
		i, _ := strconv.Atoi(s)
		ret = append(ret, i)
	}
	return ret
}

Measured memory_bytes: 7296
# ABC169C

def intSqrt(n):
    x = 1
    while True:
        x2 = (x + n // x) // 2
        if x2 ** 2 <= n and abs(x - x2) <= 1:
            break
        x = x2
    return x2


def divisor(n):
    if n % 2 == 0:
        return 2
    elif n % 3 == 0:
        return 3
    maxitr = intSqrt(n)
    i = 1
    while True:
        i += 4
        if i > maxitr:
            return n
        elif n % i == 0:
            return i
        i += 2
        if i > maxitr:
            return n
        elif n % i == 0:
            return i


def factorization2(n):
    """
    returns [(factor, count), ...]
    factorization2(64*9) --> [(2, 6), (3, 2)]
    """
    result = []
    while n > 1:
        div = divisor(n)
        result.append(div)
        n //= div
    factors = set(result)
    result2 = []
    for f in factors:
        result2.append((f, result.count(f)))
    return result2

n = int(input())
import numpy as np
result = factorization2(n)
ans = 0
for factor, m in result:
    ans += np.floor((-1 + intSqrt(1 + 8 * m)) / 2) # n*(n+1)/2 > m の整数解
print(int(ans))


Measured memory_bytes: 29488
N, K = map(int, input().split())
H = list(map(int, input().split()))

Cost = [0 for i in range(N + 1)]
Cost[0] = 0
Cost[1] = abs(H[1] - H[0])

for i in range(2, N) :
    Step = list()
    for j in range(1, K + 1) :
        if(i - j >= 0) :
            Step.append(Cost[i - j] + abs(H[i] - H[i - j]))
        else :
            pass
    Cost[i] = min(Step)

print(Cost[N - 1])

Measured memory_bytes: 56032