akhauriyash/Code-Regression huggingface dataset:
so, sp = list(map(int, input().split()))
orig = []
part = []
for i in range(so):
    orig.append(input())
for i in range(sp):
    part.append(input())
sd = so - sp
def check(orig, part, sd, sp):
    for x in range(sd+1):
        for y in range(sd+1):
            if [a[y:y+sp] for a in orig[x:x+sp]] == part:
                return True
    return False
print('Yes' if check(orig, part, sd, sp) else 'No')


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

int w , h , count ;
char map[21][21] = {} ;
int dx[] = { -1,0,1,0 } ;
int dy[] = { 0,1,0,-1 } ;

void move( int ny , int nx ){
	map[ny][nx] = '0' ;
	
	for( int i=0 ; i<4 ; i++ ){
		if( ny+dy[i] >= 0 && ny+dy[i] < h &&
			nx+dx[i] >= 0 && nx+dx[i] < w &&
			map[ny+dy[i]][nx+dx[i]] == '.' ){
				count++;
				move( ny+dy[i] , nx+dx[i] ) ;
		}
	}
}

int main(){
	
	int sx , sy ;
	
	while(1){
		cin >> w >> h ;
		if( w==0 && h==0 ) break ;
		
		count = 1 ;
		for( int i=0 ; i<h ; i++ ){
			for( int j=0 ; j<w ; j++ ){
				cin >> map[i][j] ;
				if( map[i][j] == '@' ){
					sx = j ;
					sy = i ;
				}
			}
		}
		
		move(sy,sx) ;
		
		cout << count << endl ;
	}
	
return 0 ;
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
using namespace std;
#define INF 2000000000
typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1LL<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1LL<<(i))))
#define setbit1(n,i) ((n)|(1LL<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define DBG(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define EN cout<<"\n"
#define fi first
#define se second
#define PI (acos(-1))
#define fastread ios::sync_with_stdio(false);cin.tie(NULL)
#define mod (998244353)
#define asz 300005
template<class T> ostream& operator<<(ostream &s,pair<T,ll> a)
{
    s<<a.fi<<' '<<a.se;
    return s;
}
vi solve(int i,int n,int x,int y)
{
    vi ans(n+1,-1);
    queue<ll> q;
    ans[i]=0;
    q.push(i);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==x&&ans[y]==-1)ans[y]=ans[u]+1,q.push(y);
        if(u==y&&ans[x]==-1)ans[x]=ans[u]+1,q.push(x);
        if(u<n&&ans[u+1]==-1)ans[u+1]=ans[u]+1,q.push(u+1);
        if(u&&ans[u-1]==-1)ans[u-1]=ans[u]+1,q.push(u-1);
    }
    return ans;
}
int main()
{
    ll n,x,y;
    cin>>n>>x>>y;
    vi ans(n-1);
    for(int i=1;i<=n;i++)
    {
        vi a=solve(i,n,x,y);
        for(int j=i+1;j<=n;j++)ans[a[j]-1]++;
    }
    for(auto x:ans)cout<<x<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int mod = 1e9+7;
ll fact(int x) {
    if (x==1) return 1;
    return x*fact(x-1)%mod;
}

int main(){
    int n, m;
    cin >> n >> m;
    int ans = 0;
    if (abs(n-m) > 1) {
        ans = 0;
    } else if (n==m) {
        ans = fact(n)*fact(n)%mod;
        ans = ans*2%mod;
    } else {
        ans = fact(n)*fact(m)%mod;
    }
    cout << ans << endl;
    return 0;
}

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




int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  int ans = 0;
  for(int i=0; i<N-1; i++) if(S.at(i) == S.at(i+1)) ans++;
  ans = min( ans + 2*K , N-1);
  
  cout << ans << endl;
}


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

int main() {
  int X;
  
  cin >> X;
  
  if(X>=400 && X<=599) cout << 8;
  else if(X>=600 && X<=799) cout << 7;
  else if(X>=800 && X<=999) cout << 6;
  else if(X>=1000 && X<=1199) cout << 5;
  else if(X>=1200 && X<=1399) cout << 4;
  else if(X>=1400 && X<=1599) cout << 3;
  else if(X>=1600 && X<=1799) cout << 2;
  else cout << 1;
  
}

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

using namespace std;

int N, K;

int main() {
	int a, b, limit;

	cin >> N >> K;
	limit = (N + 1) / 2;
	for (int i = 0; i < K; ++i) {
		cin >> a >> b;
		if (a > limit) {
			a = (N + 1) - a;
		}
		if (b > limit) {
			b = (N + 1) - b;
		}
		a = min(a, b);
		cout << (a - 1) % 3 + 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 3096
#include <iostream>

using namespace std;

int main()
{
int K,N,p[1000],Temp,min=0;
cin>>N>>K;
for( int i=0;i<N;i++){
    cin>>p[i];
}
for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
        if(p[j]<p[i]){
            Temp= p[i];
            p[i]=p[j];
            p[j]=Temp;
        }
    }
}
for(int i=0;i<K;i++){
     min=min+p[i];
}
cout<<min;
    return 0;
}

Measured memory_bytes: 3612
n=int(input())
task_list=[]
for i in range(n):
    task_list.append([int(x) for x in input().split()])
import operator
task_list.sort(key=operator.itemgetter(1))
time_now=0
for i in range(n):
    time_now+=task_list[i][0]
    if time_now>task_list[i][1]:
        print("No")
        exit()
    
print("Yes")

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



int main()
{
string S;
cin>>S;
int length=S.size();
int record=0;
int combo=0;
for(int i=0;i<length;i++)
{
if(S[i]=='A'||S[i]=='G'||S[i]=='C'||S[i]=='T'){combo++;}
else{combo=0;}
if(combo>record){record=combo;}

}

cout<<record<<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    ll x; cin >> x;

    ll ans = 0;
    ans += (x / 500) * 1000;
    x %= 500;
    ans += (x / 5) * 5;
    cout << ans << endl;
}


Measured memory_bytes: 256
def main():
    nums = list(map(int, input().split(' ')))
    directs = input()

    d = Dice(nums)

    for c in directs:
        if 'N' == c:
            d.toN()

        if 'S' == c:
            d.toS()

        if 'E' == c:
            d.toE()

        if 'W' == c:
            d.toW()

    print(d.top)

class Dice:
    def __init__(self, labels):
        self.labels = labels

        self._top    = 0
        self._front  = 1
        self._right  = 2
        self._left   = 3
        self._back   = 4
        self._bottom = 5

    def toN(self):
        self._back, self._top, self._front, self._bottom = self._top, self._front, self._bottom, self._back
        return self

    def toS(self):
        self._back, self._top, self._front, self._bottom =  self._bottom, self._back, self._top, self._front
        return self

    def toW(self):
        self._left, self._top, self._right, self._bottom = self._top, self._right, self._bottom, self._left
        return self

    def toE(self):
        self._left, self._top, self._right, self._bottom = self._bottom, self._left, self._top, self._right
        return self

    def get_top(self):
        return self.labels[self._top]

    top = property(get_top)

if __name__ == '__main__':
    main()

Measured memory_bytes: 7780
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=1; i<(n+1)/2; ++i){
        if(i!=n-i)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;
  cin>>c>>a>>b;
  if(a-b>=0)
 	cout<<"delicious"<<endl;
 else if(a-b+c>=0)
  	cout<<"safe"<<endl;
 else
 	cout<<"dangerous"<<endl;
 
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
ans = 'No'

for i in range(n - m + 1):
    for j in range(n - m + 1):
        sub_a = [a[i + k][j:j+m] for k in range(m)]
        if sub_a == b:
            ans = 'Yes'

print(ans)


Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {
  public static void main(String args[]) {
 
	//入力値取得
	Scanner in = new Scanner(System.in);
	int num = in.nextInt();
    
    int kisuu = 0;
    //入力値の数ループする
    for (int i = 1; i <= num;  i++){
      //奇数の場合はカウントする
      if (i % 2 != 0){
        kisuu++;
      }
    }
    
    //奇数の確率を出力する
    System.out.println((double)kisuu / num);
        
  }
}

Measured memory_bytes: 22740
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	long long a, b;
	while ( scanf ( "%lld%lld", &a, &b ) != EOF )
	{
		if ( a == b )
		{
			if(a>0) printf ( "Positive\n" );
			else printf ( "Negative\n" );
		}
		else
		{
			if ( a < 0 && b > 0 )
			{
				printf ( "Zero\n" );
			}
			else if ( a > 0 )
			{
				printf ( "Positive\n" );
			}
			else
			{
				b = -b;
				a = -a;
				if ( ( a - b + 1 ) % 2 == 0 ) printf ( "Positive\n" );
				else printf ( "Negative\n" );
			}
		}
	}
	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;
typedef long long ll;
ll mod = 1000000007;

int main() {
    ll n,m; cin >> n >> m;
    ll sum = 0;
    vector<ll> a(n);
    for (int i = 0; i < n ; i++) {
        cin >> a[i];
        sum += a[i];
    }
    ll kijun;
    kijun = (sum + 4 * m - 1) / (4 * m);
    ll ninki = 0;
    for (int i = 0; i < n; i++) if (a[i] >= kijun) ninki++;
    if (ninki >= m) cout << "Yes\n";
    else cout << "No\n";
}

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

char s[100];

int main()
{
	int n,cnt=0;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n-2;++i) {
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C') cnt++;
	}
	printf("%d",cnt);
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
using namespace std;

int main(){
	int a,b,s=0,t=0,n=0;
	while(scanf("%d,%d",&a,&b)!=EOF){s+=a*b;t+=b;n++;}
	double u=(t+0.0)/n+0.5;
	cout<<s<<endl<<(int)u<<endl;
}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

int main( )
{
    int a,b;
    char op;


   for(;;) {

  cin>>a>>op>>b;
    switch(op)
    {
        case '?':
            return 0;
            break;
        case '+':
            cout<<a+b<<endl;
            break;
        case '-':
            cout<<a-b<<endl;
            break;
        case '*':
            cout<<a*b<<endl;
            break;
        case '/':
            cout<<a/b<<endl;
            break;
        }
   }
    return 0;
}




Measured memory_bytes: 3100
import bisect
s=input()
L=len(s)
s*=2
t=input()
pl={chr(i+97):[] for i in range(26)}
for i in range(len(s)):
  pl[s[i]]+=[i]
cnt=0
rem=0
for i in t:
  if pl[i]==[]:print(-1);exit()
  cnt+=pl[i][bisect.bisect_right(pl[i],rem-1)]-(rem-1)
  rem=cnt%L
print(cnt)

Measured memory_bytes: 11940
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

struct edge {
    int to, cost;
    edge(int to, int cost): to(to), cost(cost) {}
};

constexpr LL INF = 1LL << 60;

template <typename T = pair<LL,int>>
void Dijkstra(int s, vector<vector<edge>> &g, vector<LL> &d) {
    int numv = d.size();
    priority_queue<T, vector<T>, greater<T>> q;
    for (int i = 0; i < numv; ++i) d[i] = INF;
    d[s] = 0;
    q.emplace(0,s);

    while (!q.empty()) {
        T p = q.top(); q.pop();
        LL v = p.second; // vertex
        if (d[v] < p.first) continue;
        for (int i = 0; i < g[v].size(); ++i) {
            edge &e = g[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.emplace(d[e.to], e.to);
            }
        }
    }
}

void solve() {
    int n,m,l,r,c;
    cin >> n >> m;
    vector<vector<edge>> es(n);
    REP(i,0,m) {
        cin >> l >> r >> c;
        --l; --r;
        es[l].pb(r,c);
    }
    REP(i,1,n) es[i].pb(i-1,0);
    VLL d(n);
    Dijkstra(0,es,d);
    if (d[n-1] == INF) cout << -1 << endl;
    else cout << d[n-1] << endl;
}

int main() {
    solve();
    
    return 0;
}

Measured memory_bytes: 8056
import std.stdio;
import std.string;

void main() {
  char[] line = cast(char[]) readln.chomp;
  for(int i = 0; i < line.length - 4; i++) {
    char[] str = line[i..(i + 5)];
    if (str == "apple") line[i..(i + 5)] = cast(char[])"peach";
    else if (str == "peach") line[i..(i + 5)] = cast(char[])"apple";
  }
  writeln(line);
}

Measured memory_bytes: 1044
#include <stdio.h>

#define N 1000000

int main(){

  int i,n,a[N+1];

  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
  }

  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,a[i]);

    if(i/2 >= 1){
      printf("parent key = %d, ",a[i/2]);
    }

    if((i*2) <= n){
      printf("left key = %d, ",a[i*2]);
    }

    if((i*2+1) <= n){
      printf("right key = %d, ",a[i*2+1]);
    }

    printf("\n");
  }

  return 0;
  
}



Measured memory_bytes: 2104
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

MAX = 10**10 + 10

# Ai+Ajを列挙して大きいほうからM番目となるスコアSを求める
# その後S以上となるスコアを加算して合計値を求める

from bisect import bisect_left

def judge(x,key):
    # スコアx以上となるのがkey個以上あるか？
    
    num = 0
    
    for i in range(N):
        eidx = bisect_left(A,x-A[i])
        num += N-eidx
    
    if num >= key:
        return True
    else: 
        return False


def meguru(key):
    ok = -1
    ng = MAX
    
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if judge(mid,key):
            ok = mid
        else:
            ng = mid
    return ok


D = meguru(M)
ans = 0

ruisekiwa = [0]*(N+1)
for i in range(N):
    ruisekiwa[i+1] = ruisekiwa[i] + A[i]

num = 0

for i in range(N):
    eidx = bisect_left(A,D+0.5-A[i])
    ans += A[i] * (N-eidx)
    ans += ruisekiwa[N] - ruisekiwa[eidx]
    num += N-eidx

if num<M:
    ans += (M-num)*D

print(ans)
    




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

using namespace std;

int main() {
    
    int x,y;
    cin >> x >> y;

    for (int i = 0; i <= x; ++i) {
        int a = i, b = x - i;
        if(2 * a + 4 * b == y) return cout << "Yes\n",0;
    }
    cout << "No\n";
    return 0;
}


Measured memory_bytes: 3640
n,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(n):
    f+=[f[-1]*(i+1)%mod]
def combination(a,b):
    return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod

a=list(map(int,input().split()))
a.sort()
b=a[::-1]
ans=0
for i in range(k-1,n):
    ans+=((a[i]-b[i])*(combination(i,k-1)))%(10**9+7)
print(ans%(10**9+7))

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

int main()
{
	int h, w;
	cin >> h >> w;

	char field[2000][2000];
	vector< vector<int> > x(2000, vector<int>(2000, 0));
	vector< vector<int> > y(2000, vector<int>(2000, 0));

	char c;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin >> field[i][j];			
		}
	}

	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(x[i][j] == 0 && field[i][j] == '.'){
				x[i][j] = 1;
				int k=j+1;
				for(;k<w;k++){
					if(field[i][k]=='#')
						break;
					x[i][k] = x[i][k-1] + 1;
				}
				for(int l=k-1;l>=j;l--){
					x[i][l] = x[i][k-1];
				}
			}
			if(y[i][j] == 0 && field[i][j] == '.'){
				y[i][j] = 1;
				int k=i+1;
				for(;k<h;k++){
					if(field[k][j]=='#')
						break;
					y[k][j] = y[k-1][j] + 1;
				}
				for(int l=k-1;l>=i;l--){
					y[l][j] = y[k-1][j];
				}
			}
		}
	}


	int ans = 0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			ans = max(ans, x[i][j] + y[i][j]);
		}
	}
	cout << ans - 1 << endl;

	return 0;
}

Measured memory_bytes: 35584
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi 3.14159265358979323846
int main() 
{
    int n;
    cin>>n;
     string s;
     cin>>s;
     vector<int> pre(n,0);
     vector<int> pre1(n,0);
     vector<int> suf(n,0);
     vector<int> suf1(n,0);
     if(s[0]=='W')pre[0]=1;
     else pre1[0]=1;
     for(int i=1;i<n;i++)
     {
     	if(s[i]=='W')pre[i]++;
     	else pre1[i]++;
     	pre[i]+=pre[i-1];
     	pre1[i]+=pre1[i-1];
	 }
	 if(s[n-1]=='R')suf[n-1]=1;
	 else suf1[n-1]=1;
	 for(int i=n-2;i>=0;i--)
	 {
	 	if(s[i]=='R')suf[i]++;
	 	else suf1[i]++;
	 	suf1[i]+=suf1[i+1];
	 	suf[i]+=suf[i+1];
	 }
	 
	 int ans=INT_MAX;
	 for(int i=0;i<n;i++)
	 {
	 	int x=pre[i];
	 	if(pre[n-1]==n)x=0;
	 	int y=0;
	 	if(i+1<n && suf[i+1]-pre[i]>=0 && suf1[i+1]>0)y=suf[i+1]-pre[i];
	 	//cout<<x<<" "<<y<<"\n";
	 	ans=min(ans,x+y);
	 }
	 cout<<ans;
}

Measured memory_bytes: 6772
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }

bool isprime(int x) {
    for(int i = 2; i*i < x; i++) {
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int x; cin >> x;
    for(int y = x; y < x * 2; y++) {
        if(isprime(y)) {
            cout << y << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){

   int W , H , x , y , r;
   scanf("%d%d%d%d%d" , &W , &H , &x , &y , &r);
   if ( 0 + r <= x && x <= W - r && 0 + r <= y && y <= H - r) { 
   printf ("Yes\n");
  } else {
   printf ("No\n");
  }

   
  return 0;
}






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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<bool>> v(h, vector<bool>(w, false));
  rep (i, h) {
    rep (j, w) {
      char c;
      cin >> c;
      if (c == '#') v[i][j] = 1;
    }
  }
  int ans = 0;
  rep (i, 1<<h) {
    rep (j, 1<<w) {
      int cnt = 0;
      rep(l, h) {
        if ((i>>l)&1) continue;
        rep (m, w) {
          if ((j>>m)&1) continue;
          if (v[l][m]) cnt++;
        }
      }
      if (cnt == k) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
	int n,m,A[100][100],B[100],C[100]={0};
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>A[i][j];
		}
	}
	for(int i=0;i<m;i++){
		cin>>B[i];
	}
	
	for(int i=0;i<n;i++){
		int x=0;
		for(int j=0;j<m;j++){
			x=A[i][j]*B[j];
			C[i]+=x;	
		}
	}
	for(int i=0;i<n;i++){
		cout<<C[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3080
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<int,P> PP;
struct edge { int to, cor; };

int a[55], b[55];
vector<int>G[55];
int graf[55][55];
int used[55];//0...つかっていい

signed main() {
	int n; cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	rep(i, n)G[i].push_back(a[i]);
	int ans = 0;

	for (int m = 50; m >= 0; m--) {//mまで使う
		rep(i, 51)rep(j, 51)graf[i][j] = inf;
		rep(i, 51) {
			for (int k = 0; k <= 50; k++) {
				if (k == 0)graf[i][i] = 0;
				else if (!used[k])graf[i][i%k] = min(graf[i][i%k], 1ll << k);
			}
		}

		rep(i, 51)rep(j, 51)rep(k, 51)graf[j][k] = min(graf[j][k], graf[j][i] + graf[i][k]);

		int flg = 0;
		rep(i, n) { if (graf[a[i]][b[i]] == inf)flg++; }
		if (flg) {
			if (m == 50) {
				cout << -1 << endl;
				return 0;
			}
			else used[m + 1] = 0;
		}
		used[m]++;
	}

	rep(i, 51)if (!used[i])ans += 1ll << i;
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  S = input()
  L = len(S)
  ans = 'Yes'
  for i in range(L):
    if i %2==0:
      if S[i]=='L':
        ans = 'No'
        break
    else:
      if S[i] == 'R':
        ans = 'No'
        break
  print(ans)
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3064
#include <stdio.h>

#define N 12345

int main() {
	int n;
	float sum;

	scanf("%d\n", &n);
	sum = 0;
	while (n--) {
		static char s[N + 1];
		float x;

		scanf("%f%s", &x, s);
		sum += (s[0] == 'J' ? x : 380000.0 * x);
	}
	printf("%f\n", sum);
	return 0;
}


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

using namespace std;

int main()
{
  string arg = "";
  int search = 0;
  int i = 0;
  cin >> arg;
  cin.ignore(101, '\n');
  cin >> search;
  for(i = 0; i < arg.length(); ++i)
  {
    if(stoi(arg.substr(i, 1)) > 1 || i == search - 1)
    {
      break;
    }
  }
  cout << arg[i] << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>                                             
#include <vector>                                               
using namespace std;                                            
                                                                
int main() {                                                    
  int n, m;                                                     
  while (true) {                                                
    cin >> n;                                                   
    if (n==0) {                                                 
      break;                                                    
    }                                                           
    vector<char> from(n);                                       
    vector<char> to(n);                                         
    for (int i=0; i<n; i++) {                                   
      cin >> from[i] >> to[i];                                  
    }                                                           
    cin >> m;                                                   
    vector<char> v(m);                                          
    for (int i=0; i<m; i++) {                                   
      cin >> v[i];                                              
      for (int j=0; j<n; j++) {                                 
        if (v[i]==from[j]) {                                    
          v[i] = to[j];                                         
          break;                                                
        }                                                       
      }                                                         
    }                                                           
    for (int i=0; i<m; i++) {                                   
      cout << v[i];                                             
    }                                                           
    cout << "\n";                                               
  }                                                             
  return 0;                                                     
}                                                               
                              

Measured memory_bytes: 3056
// ------------------------------------
// Date:2018/ 3/13
// Problem:back and forth a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

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

  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  int h = tx - sx;
  int w = ty - sy;

  REP(i, h) {
    cout << "R";
  }
  REP(i, w) {
    cout << "U";
  }
  REP(i, h) {
    cout << "L";
  }
  REP(i, w) {
    cout << "D";
  }
  cout << "D";
  REP(i, h + 1) {
    cout << "R";
  }
  REP(i, w + 1) {
    cout << "U";
  }
  cout << "LU";
  REP(i, h + 1) {
    cout << "L";
  }
  REP(i, w + 1) {
    cout << "D";
  }
  cout << "R" << endl;
  return 0;
}



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

int main() {
    int n, m;
    
    cin >> n >> m;
    
    if(n == m) cout << "Yes";
    else cout << "No";
    
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int64_t n,i,j,m,ans=0;
  cin>>n;
  map<int64_t,int64_t> mp;
  for(i=2;i*i<=n;i++){
    if(n%i==0){
      m=0;
      while(n%i==0){
        n/=i;
        m++;
      }
      mp[i]=m;
    }
  }
  if(n>1) mp[n]=1;
  for(auto z:mp){
    int64_t j=z.second;
    for(i=1;i<1000000000000;i++){
      j-=i;
      if(j<0) break;
    }
    ans+=i-1;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;


int main(){
	int N, M;
	cin >> N >> M;
	vector<int> a(M), b(M), c;
	int i,j;
	for (i = 0;i < M;i++) {
		cin >> a[i] >> b[i];
		c.push_back(a[i]);
		c.push_back(b[i]);
	}
	sort(c.begin(), c.end());
	for (i = 1;i <= N;i++) {
		int res = 0;
		for (j = 0;j < 2 * M;j++) {
			if (c[j] == i) res++;
			if (c[j] > i) break;
		}
		cout << res << endl;
	}
	return 0;
}


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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<int> v(n), c(n), sa(n);
    REP(i,n) cin>>v[i];
    REP(i,n) cin>>c[i];
    REP(i,n) sa[i] = v[i]-c[i];
    int ans = 0;
    REP(i,n){
        if(sa[i]>0) ans+=sa[i];
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
const int mod = 1000000007;
int N,K,ans;
int main() {
    scanf("%d%d",&N,&K);
    for (int i = K;i <= N + 1;i++) {
        ans += (((1LL * (N - i + 1 + N) * i) >> 1) - ((1LL * (i - 1) * i) >> 1) + 1) % mod;
        ans %= mod;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 1704
s=input()
l=int(s[:2])
r=int(s[2:])
if 1<=l<=12 and 1<=r<=12:
    print("AMBIGUOUS")
elif 1<=l<=12:
    print("MMYY")
elif 1<=r<=12:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 38384
#include <stdio.h>

int main(void) {
  int a, b;
  scanf("%d %d", &a, &b); 
  if (a == b)
    printf("a == b\n");
  if (a < b)
    printf("a < b\n");
  if (a > b)
    printf("a > b\n");

return 0;
}



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

int main(){
    int n,m;
    cin >> n >> m;
    if(n-m!=0 && n-m!=-1 && n-m!=1) cout << 0 << endl;
    ll sn=1,sm=1;
    if(n-m==0) {
        rep(i,n) {
            sn*=i;
            ll b=pow(10,9);
            if(sn>pow(10,9)+7) sn=sn%(b+7);
        }
        rep(i,m) {
            sm*=i;
            ll b=pow(10,9);
            if(sm>pow(10,9)+7) sm=sm%(b+7);
        }
        ll a=2*sn*sm;
        ll b=pow(10,9);
        if(a>pow(10,9)+7) a=a%(b+7);
        cout << a << endl;
        //2*n!*m!
    }
    if(n-m==1 || n-m==-1){
        rep(i,n) {
            sn*=i;
            ll b=pow(10,9);
            if(sn>pow(10,9)+7) sn=sn%(b+7);
        }
        rep(i,m) {
            sm*=i;
            ll b=pow(10,9);
            if(sm>pow(10,9)+7) sm=sm%(b+7);
        }
        ll a=sn*sm;
        ll b=pow(10,9);
        if(a>pow(10,9)+7) a=a%(b+7);
        cout << a << endl;
        //n!*m!
    }
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <complex>
#define ll long long
#define ld long double
#define F first
#define S second
#define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
#define pi acos(-1)
#define X real()
#define Y imag()
#define angle(a) (atan2((a).imag(),(a).real()))
#define vec(a,b) ((b)-(a))
#define lenght(a) (hypot((a).imag(),(a).real()))
#define normalize(a) (a)/length(a)
#define point complex<long double>
#define dP(a,b)((conj(a)*(b)).real())
#define cP(a,b)((conj(a)*(b)).imag())
#define same(p1,p2)  (dP(vec(p1,p2),vec(p1,p2)) < EPS)
#define lengthsqr(p)   dP(p,p)
#define rotate0(p,ang)  ((p)*exp(point(0,ang)))
#define rotataA(p,ang,about) (rotate0(vec(about,p),ang)+about)
#define reflect0(v,m) (conj((v)/(m))*(m))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const ld EPS = (1e-10);
using namespace std;
using namespace __gnu_pbds;
const ll N = 2e5+50, inf = 1e3+5, mod = 1e9+7, NN = 1e5+10;
int Floor(double num)
{
    if ( num > 0.0 )
        return floor(num + 0.5);
    else
        return -1.0 * floor(fabs(num) + 0.5);
}
int main()
{
    double x1, y1, x2, y2 ;
    cin >> x1 >> y1 >> x2 >> y2 ;
    point a = {x1,y1}, b = {x2,y2} ;
    point c = rotataA(a,3*pi/2.0,b);
    cout << Floor(c.real()) << " " << Floor(c.imag()) << " " ;
    double z = c.imag(), zz = c.real() ;
    cout << Floor(zz - x2 + x1) << " " << Floor(z - y2 + y1);
}


Measured memory_bytes: 3776
from collections import Counter


N = int(input())
ball = [[] for i in range(N)]
for i in range(N):
    ball[i] = list(map(int, input().split()))

vector = [0] * ((N * (N - 1)) // 2)
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        x = ball[i][0] - ball[j][0]
        y = ball[i][1] - ball[j][1]
        if x < 0:
            x, y = -x, -y
        elif x == 0:
            if y < 0:
                y = -y
        vector[cnt] = x * (10 ** 10) + y
        cnt += 1
C = Counter(vector)
if N == 1:
    print(1)
else:
    print(N - C.most_common()[0][1])


Measured memory_bytes: 39280
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define double long double
#define rep(i,n) for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define repii(i,a,b) for(ll i=a;i<=b;i++)
#define pb push_back
#define in insert
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl "\n"
int main()
{
    fastIO;
    int n;
    cin>>n;
    ll a[n];
    rep(i,n)cin>>a[i];
    ll cur=a[0],c=0,ans=0;
    repii(i,1,n-1)
    {
        if(a[i]<=cur)
        {
            c++;
            cur=a[i];
        }
        else{
            c=0;
            cur=a[i];
        }
        ans=max(ans,c);
    }
    cout<<ans;
    return 0;
}


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

int main() {
    int N;
    int M;
    int X;
    int Y;
	cin >> N;
	cin >> M;
	cin >> X;
	cin >> Y;
	int x[N];
	int y[M];
	for (int i = 0; i < N; i++) {
	    cin >> x[i];
	}
	for (int i = 0; i < M; i++) {
	    cin >> y[i];
	}
	int xmax = -101;
	for (int i = 0; i < N; i++) {
	    if (x[i] > xmax) {
	        xmax = x[i];
	    }
	}
	int ymin = 101;
	for (int i = 0; i < M; i++) {
	    if (y[i] < ymin) {
	        ymin = y[i];
	    }
	}

	bool war = false;
	if (xmax >= ymin) {
	    war = true;
	}
	if (xmax >= Y) {
	    war = true;
	}
	if (ymin <= X) {
	    war = true;
	}

	if (war) {
	    cout << "War" << endl;
	} else {
	    cout << "No War" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	map<string, ll> mp;
	
	for(int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		
		sort(s.begin(), s.end());
		mp[s]++;
	}
	
	ll ans = 0;
	for(auto& x : mp) {
		ans += (x.second * (x.second - 1) / 2);
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 11136
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		s = s.replace('1','x');
		s = s.replace('9','1');
		s = s.replace('x','9');
		System.out.println(s);
	}
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

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

  cout << s.substr(0, 3) << endl;

  return 0;
}


Measured memory_bytes: 3620
import numpy as np
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
N = int(input())
b = []
for i in range(N):
  b.append(int(input()))

flag = 0
for i in range(N):
  for j in range(3):
    if b[i] == A1[j]:
      A1[j] = 0
    elif b[i] == A2[j]:
      A2[j] = 0
    elif b[i] == A3[j]:
      A3[j] = 0
if A2[1] == 0:
  if A2[0] == 0 and A2[2] == 0:
    flag = 1
  elif A1[1] == 0 and A3[1] == 0:
    flag = 1
  elif A1[0] == 0 and A3[2] == 0:
    flag = 1
  elif A1[2] == 0 and A3[0] == 0:
    flag = 1
elif A1[0] == 0 and A1[1] == 0 and A1[2] == 0:
  flag = 1
elif A1[0] == 0 and A2[0] == 0 and A3[0] == 0:
  flag = 1
elif A1[2] == 0 and A2[2] == 0 and A3[2] == 0:
  flag = 1
elif A3[0] == 0 and A3[1] == 0 and A3[2] == 0:
  flag = 1
  
if flag == 1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 12504
# ABC159c


def main():
    import sys
    import math
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))
    l = int(input())
    print((l/3)**3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)
N,M=LI()
if abs(N-M) >= 2:
    print(0)
else:
    ans=math.factorial(N)*math.factorial(M)
    if abs(N-M) == 0:
        ans *= 2
    print(ans%mod)


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

int main() {
  string a,b,mess;
  bool flag=true;
  cin >> a >> b;
  if(a.size()>b.size()) {
    mess="GREATER";
  }else if(a.size()<b.size()) {
    mess="LESS";
  } else {
    for(int i=0;i<a.size();i++) {
      if(a[i]>b[i]) {
        mess="GREATER";
        flag=false;
        break;
      }else if(a[i]<b[i]) {
        mess="LESS";
        flag=false;
        break;
      }
    }
    if(flag) mess="EQUAL";
  }
  cout << mess << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
 
typedef struct{
  double x;
  double y;
}Point;
 
void koch(int n, Point a, Point b){
  Point s, t, u;
  double th = M_PI * 60.0 / 180.0;
 
  if(n==0)return;
 
  s.x=(2.0*a.x+1.0*b.x)/3.0;
  s.y=(2.0*a.y+1.0*b.y)/3.0;
 
  t.x=(1.0*a.x+2.0*b.x)/3.0;
  t.y=(1.0*a.y+2.0*b.y)/3.0;
 
  u.x=(t.x-s.x)*cos(th)-(t.y-s.y)*sin(th)+s.x;
  u.y=(t.x-s.x)*sin(th)+(t.y-s.y)*cos(th)+s.y;
 
  koch(n-1,a,s);
  printf("%.8f %.8f\n", s.x, s.y);
 
  koch(n-1,s,u);
  printf("%.8f %.8f\n", u.x, u.y);
 
  koch(n-1,u,t);
  printf("%.8f %.8f\n", t.x, t.y);
 
  koch(n-1,t,b);
}
 
int main(){
  Point a, b;
  int n;
 
  scanf("%d", &n);
 
  a.x = 0;
  a.y = 0;
 
  b.x = 100;
  b.y = 0;
 
  printf("%.8f %.8f\n", a.x, a.y);
 
  koch(n,a,b);
 
  printf("%.8f %.8f\n", b.x, b.y);
 
  return 0;
}

Measured memory_bytes: 644
N = int(input())
a = list(map(int, input().split()))

b = [0]*N

xorsum = 0
for i in range(1,N):
    b[i] = b[i-1] ^ a[i-1] ^ a[i]
    xorsum = xorsum ^ b[i]

b[0] = xorsum ^ a[0]

for i in range(1,N):
    b[i] = b[i-1] ^ a[i-1] ^ a[i]

print(" ".join(map(str, b)))

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


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

  int i, sum = 0;
  char last = S[0];
  for(i = 1; i < S.length(); i++){
    if(S[i]!=last) sum++;
    last = S[i];
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c * c == a * a + b * b)
    cout << a * b / 2 << endl;

  else if (a * a == b * b + c * c)
    cout << c * b / 2 << endl;
  else
    cout << a * c / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
def main(N, c2, c3, c5, c):
    m = dict()
    m[0] = 0
    m[1] = c

    def f(n):
        if n in m: return m[n]
        res = c * n
        e5 = n % 5
        e3 = n % 3
        e2 = n % 2
        if e5 != 0:
            res = min(res, (5 - e5) * c + f(n // 5 + 1) + c5)
        if e3 != 0:
            res = min(res, (3 - e3) * c + f(n // 3 + 1) + c3)
        if e2 != 0:
            res = min(res, (2 - e2) * c + f(n // 2 + 1) + c2)
        if n >= 5:
            res = min(res, e5 * c + f(n // 5) + c5)
        if n >= 3:
            res = min(res, e3 * c + f(n // 3) + c3)
        if n >= 2:
            res = min(res, e2 * c + f(n // 2) + c2)
        m[n] = res
        return res

    return f(N)

if __name__ == '__main__':
    input = sys.stdin.readline
    T = int(input())
    for t in range(T):
        n, a, b, c, d = map(int, input().split())
        ans = main(n, a, b, c, d)
        print(ans)


Measured memory_bytes: 101720
#include <stdio.h>
#include <string.h>

#define MAX 24414070

void insert(char []);
int find(char []);
int getNum(char []);

int hash[MAX];

int main(){
  int i, n;
  char str[15], cmd[10];
  
  for(i=0; i<MAX; i++) hash[i] = 0;
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%s%s", cmd, str);
    if(cmd[0] == 'i') insert(str);
    else printf(find(str)?"yes\n":"no\n");
  }
  
  return 0;
}

void insert(char str[]){
  int num;
  num = getNum(str);
  hash[num] = 1;
}

int find(char str[]){
  int num;
  num = getNum(str);
  if(hash[num] == 1) return 1;
  return 0;
}

int getNum(char str[]){
  int i, sum = 0, code, x = 1;
  for(i=0; i<strlen(str); i++){
    switch(str[i]){
    case 'A':
      code = 1;
      break;
    case 'C':
      code = 2;
      break;
    case 'G':
      code = 3;
      break;
    case 'T':
      code = 4;
      break;
    }
    sum += code * x;
    x *= 5;
  }
  return sum;
}

Measured memory_bytes: 95960
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "
#define A(a, i) #a "[" #i " =", i, "] =", a[i], " "

const int MXN = 1e5+5;
VI V[MXN];
int pop[MXN];
int done[MXN];

int main()
  {
  ios_base::sync_with_stdio(0); 
  int n, m;
  cin >> n >> m;
  REP(i, m)
    {
    int a, b;
    cin >> a >> b;
    V[a].PB(b);
    V[b].PB(a);
    }
  
  queue<int> q;
  q.push(1);
  done[1] = 1;
  int cnt = 1;
  while(q.size())
    {
    int v = q.front();
    q.pop();
    for(auto i: V[v])
      {
      if(done[i] == 0)
        {
        pop[i] = v;
        done[i] = 1;
        q.push(i);
        cnt++;
        }
      }

    }
  if(cnt != n)
    {
    cout << "No" << endl;
    return 0;
    }
  cout << "Yes" << endl;
  FOR(i, 2, n)cout << pop[i] << endl;

  }


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

int main() {
  int W, H, N;
  cin >> W >> H >> N;
  int x, y, a;

  int w[] = {0,W};
  int h[] = {0,H};

  for (int i = 0; i < N; i++) {
    cin >> x >> y >> a;
    if(a == 1){
      w[0] = max(w[0], x);
    }else if(a == 2){
      w[1] = min(w[1], x);
    }else if(a == 3){
      h[0] = max(h[0], y);
    }else if(a == 4){
      h[1] = min(h[1], y);
    }
  }

  if(w[1] - w[0] > 0 && h[1] - h[0] > 0){
    cout << (w[1] - w[0]) * (h[1] - h[0]) << endl;
  }else{
    cout << 0 << endl;
  }
}

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

using graph = vector<vector<int>>;

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
    }

    vector<int> used(n);
    function<vector<int>(vector<int>&)> find_cycle = [&] (vector<int>& path) {
        assert(!path.empty());
        used[path.back()] = 1;
        for(auto to : g[path.back()]) {
            if(used[to] == 2) continue;
            if(used[to] == 1) {
                reverse(path.begin(), path.end());
                while(path.back() != to) path.pop_back();
                reverse(path.begin(), path.end());
                return path;
            } else {
                path.push_back(to);
                auto vs = find_cycle(path);
                if(!vs.empty()) {
                    return vs;
                }
                path.pop_back();
            }
        }
        used[path.back()] = 2; // searched
        return std::vector<int>{};
    };

    vector<int> cycle, nxt(n, -1);
    for(int i = 0; i < n; ++i) {
        if(used[i]) continue;
        vector<int> path = {i};
        cycle = find_cycle(path);
        if(!cycle.empty()) {
            for(int j = 0; j < (int)cycle.size(); ++j) {
                nxt[cycle[j]] = cycle[(j + 1) % (int)cycle.size()];
            }
            break;
        }
    }

    if(cycle.empty()) {
        cout << -1 << endl;
        return 0;
    }

    // remove
    bool update = true;
    while(update) {
        update = false;
        vector<int> nnxt(n, -1);
        //for(int i = 0; i < n; ++i) {
        //    cout << nxt[i] << " \n"[i + 1 == n];
        //}
        for(int from = 0; from < n && !update; ++from) {
            if(nxt[from] == -1) continue;
            for(auto to : g[from]) {
                if(nxt[to] == -1) continue;
                if(nxt[from] == to) continue; // on cycle
                nxt[from] = to;
                update = true;
                int cur = from;
                do {
                    nnxt[cur] = nxt[cur];
                    cur = nxt[cur];
                } while(cur != from);
                break;
            }
        }
        if(update) {
            nxt = move(nnxt);
        }
    }

    vector<int> ans;
    for(int i = 0; i < n; ++i) {
        if(nxt[i] == -1) continue;
        ans.push_back(i);
    }
    cout << ans.size() << endl;
    for(auto v : ans) {
        cout << v + 1 << endl;
    }
}


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

mon = list(map(int,input().split()))

hero = list(map(int,input().split()))

ans = 0
for i in range(len(hero)):
	if mon[i]+mon[i+1] >= hero[i]:
		ans += hero[i]
		mon[i+1] = min(mon[i+1],mon[i]+mon[i+1]-hero[i])
	else:
		ans += mon[i]+mon[i+1]
		mon[i+1] = 0

print(ans)

Measured memory_bytes: 18624
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)] # a[h][w]

row, col = [False]*h, [False]*w
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            row[i], col[j] = True, True
for i in range(h):
    if row[i]:
        for j in range(w):
            if col[j]:
                print(a[i][j], end='')
        print()

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

#define dv(i) for (int c=0; c<(int)(i).size(); c++) cout<<(i)[c]<<(c==(int)(i).size()-1?"\n":" ")
#define dm(i) for (auto f: i) cout<<f.first<<" "<<f.second<<"\n"
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define alp(i) (i),(i)+sizeof((i))/sizeof((i)[0])

const int MOD = 1000000007;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N; cin>>N; string A; cin>>A;
    int prefW[N],prefE[N]; fill(alp(prefW),0); fill(alp(prefE),0);
    FOR(i,0,N) {
        if (i==0) {
            prefW[i]=(int)(A[i]=='W');
            prefE[i]=~prefW[i];
        } else {
            prefW[i]=prefW[i-1]+(int)(A[i]=='W');
            prefE[i]=prefE[i-1]+(int)(A[i]=='E');
        }
    }
    int ret=INT_MAX;
    FOR(i,0,N) {
        ret=min(ret,prefW[i-1]+prefE[N-1]-prefE[i]);
    }
    cout<<ret<<'\n';
    return 0;
}

Measured memory_bytes: 2964