akhauriyash/Code-Regression huggingface dataset:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    x, a, b = map(int, readline().split())

    if b <= a:
        print("delicious")
    elif b - a <= x:
        print("safe")
    else:
        print("dangerous")


if __name__ == '__main__':
    main()


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

int main(){	
	int N, M;
	cin >> N >> M;
	vector<int> value(M);
	vector<int> open(M, 0);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		value[i] = a;
		for (int j = 0; j < b; ++j) {
			int k;
			cin >> k;
			open[i] += (1 << (k-1));
		}
	}
	vector<int> dp(4096, 10000000);
    dp[0] = 0;
	for (int i = 0; i < M; ++i){
		for (int j = 0; j < 4096; ++j) {
			int k = j|open[i];
			dp[k] = min(dp[j]+value[i], dp[k]);
		}
	}
	int ans = dp[(1 << N) - 1];
	if (ans == 10000000) cout << "-1\n";
	else cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 500001

int A[MAX],H;

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i + 1;
}

void maxHeapify(int i){
  int l,r,largest,kari;
  l = left(i);
  r = right(i);
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r; 

  if(largest != i){
    kari = A[i];
    A[i] = A[largest];
    A[largest] = kari;
    maxHeapify(largest);
  }
}

void buildMaxHeap(){
  int i;   
  for(i=H/2; i>0; i--){
    maxHeapify(i);
  }
}

int main() {
  int i;
  scanf("%d",&H);
  for(i=1; i<=H; i++) scanf("%d",&A[i]);
  buildMaxHeap();
  for(i=1; i<=H; i++) printf(" %d",A[i]);
  printf("\n");

  return 0;

}

Measured memory_bytes: 2552
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
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(void){
  int n; cin >> n;
  vector<vector<int>> to(n,vector<int>());
  int a[n-1],b[n-1];
  rep(i,n-1){
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    to[a[i]].push_back(b[i]);
    to[b[i]].push_back(a[i]);
  }
  queue<int> q;
  q.push(0);
  int color_num = 0;
  vector<int> ans(n);
  ans[0]=0;
  vector<int> parent(n,-1);
  queue<int> p;
  p.push(0);
  while(!p.empty()){
    int k = p.front();
    p.pop();
    for(int c: to[k]){
      if(parent[c] == -1){
        parent[c] = k;
      }
      else continue;
      p.push(c);
    }
  }
  parent[0] = -1;
  while(!q.empty()){
    int k = q.front();
    q.pop();
    int count = 1;
    int i = 1;
    for(int c : to[k]){
      if(c == parent[k]) continue;
      if(i == ans[k]){
        i++;
        ans[c] = i;
      }
      else{
        ans[c] = i;
      }
      q.push(c);
      i++;
      count++;
    }
    if(k == 0) count--;
    color_num = max(color_num,count);
  }
  cout << color_num << endl;
  for(int i = 0; i < n-1; i++){
    if(parent[a[i]] == b[i]){
      cout << ans[a[i]] << endl;
    }
    else if(parent[b[i]] == a[i]){
      cout << ans[b[i]] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 7680
import itertools
from collections import deque
N=int(input())
tp=("3","5","7")
#7,5,3が最低一回登場し、それ以外の数字は登場しない
ans=0
for j in itertools.product(tp, repeat=3):#重複組み合わせで検証
    q=deque()
    q.append(''.join(j))
    while(len(q)>0):
        pos=q.popleft()#現在の数字を出す
        #[真のときの値 if 条件式 else 偽のときの値 for 任意の変数名 in イテラブルオブジェクト]
        if int(pos)<=N and all([ True if k in pos else False for k in tp]):#現在の数字が条件を満たすなら
            ans+=1
        if len(pos)<len(str(N)):
            for i in tp:
                q.append(i+pos)
print(ans)


Measured memory_bytes: 46940
n,m = map(int,input().split())
l,r = [],[]
for i in range(m):
    a,b = map(int,input().split())
    l.append(a)
    r.append(b)
num = list(range(1,n+1))
lmax = max(l)
rmin = min(r)
if lmax > rmin:
    print(0)
else:
    gate = set(range(lmax,rmin+1))
    ans = list(set(num) & gate)
    print(len(ans))

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

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  
  int count=0;
  
  for(int i=0;i<S.size()-2;i++){
    if(S.at(i)=='A'&&S.at(i+1)=='B'&&S.at(i+2)=='C'){
      count++;
    }
  }
  
  cout << count << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <random>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int a,b,c,d,e; cin >> a >> b >> c >> d >> e;
	if(a*b>0){
		if(a<0){
			cout << -(a-b)*c << endl;
		}
		else{
			cout << -(a-b)*e << endl;
		}
	}
	else{
		cout << d+(-a)*c+b*e << endl;
	}
}



Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll n,k;
	cin>>n>>k;
	deque<ll> a(n);
	rep(i,n){
		cin>>a[i];
	}
	ll ans=0;
	rep(l,k+1)rep(r,k+1){
		if(l+r>k) continue;
		priority_queue<ll,vector<ll>,greater<ll>> pq;
		deque<ll> que(a);
		ll now=0;
		rep(i,l){
			if(que.empty()) break;
			pq.push(que.front());
			now+=que.front();
			que.pop_front();
		}
		for(int i=n-1;i>n-1-r;i--){
			if(que.empty()) break;
			pq.push(que.back());
			now+=que.back();
			que.pop_back();
		}
		if(pq.empty()) continue;
		ll cnt=min(k-(l+r),ll(pq.size()));
		while(cnt--){
			if(pq.empty()) break;
			ll tmp=pq.top();
			pq.pop();
			if(tmp<0) now-=tmp; 
			else break;
		}
		chmax(ans,now);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb emplace_back
#define rt(v) return cout<<v,0
#define sz(v) (int)(v.size())
#define all(a) a.begin(),a.end()
#define endl '\n'
#define space " "
typedef long long ll;
typedef unsigned long long ull;
const int N = 10 + 1e5;
const int mod = 1e9 + 7;
/*

███╗   ███╗███████╗███╗   ███╗███████╗    ██╗      ██████╗ ██████╗ ██████╗
████╗ ████║██╔════╝████╗ ████║██╔════╝    ██║     ██╔═══██╗██╔══██╗██╔══██╗
██╔████╔██║█████╗  ██╔████╔██║█████╗      ██║     ██║   ██║██████╔╝██║  ██║
██║╚██╔╝██║██╔══╝  ██║╚██╔╝██║██╔══╝      ██║     ██║   ██║██╔══██╗██║  ██║
██║ ╚═╝ ██║███████╗██║ ╚═╝ ██║███████╗    ███████╗╚██████╔╝██║  ██║██████╔╝
╚═╝     ╚═╝╚══════╝╚═╝     ╚═╝╚══════╝    ╚══════╝ ╚═════╝ ╚═╝  ╚═╝╚═════╝

*/

using namespace std;
void Ferrari() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
long long fact(int x) {
	long long res = 1;
	for (int i = 1; i <= x; ++i) {
		res *= i;
		res %= mod;
	}
	return res;
}
int main() {
	Ferrari();
	int x; cin >> x;
	cout << fact(x);
	return 0;
}





/* stuff you should look for
	* keepin sharp mind.
	* int overflow, array bounds.
	* special cases (n=1?), set tle , make sure you understand the problem correctly.
	* don`t stuck in a problem.
	* test the idea on samples.
	*/

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

int main(void) {
    int input, ans = 0, flag;
    int ans2, ans3 = 0;
    cin >> input;

    vector<int> side(input);
    for (int i = 0; i < input; i++) {
        cin >> side.at(i);
    }

    sort(side.begin(), side.end());
    reverse(side.begin(), side.end());

    vector<int> num;
    num.push_back(0);
    num.push_back(1);
    for (int i = 0; i < input; i++) {
        flag = 0;
        for (int j = i + 1; j < input; j++) {
            for (int k = j + 1; k < input; k++) {
                if (side.at(i) < side.at(j) + side.at(k) && side.at(j) < side.at(k) + side.at(i) && side.at(k) < side.at(i) + side.at(j)) {
                    ans++;
                    ans2++;
                    ans3++;
                }
                else {
                    break;
                    flag++;
                }
            }
            if (flag != 0) {
                break;
            }
        }
    }

    cout << ans << endl;

}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int x,n; cin>>x>>n;
	vector<bool>p(102,true);
	for(int i=0;i<n;++i){
		int P; cin>>P;
		p.at(P)=false;
	}
	int ans;
	for(int i=0;;++i){
		if(p.at(x-i)){
			ans=x-i;
			break;
		}
		else if(p.at(x+i)){
			ans=x+i;
			break;
		}
	}
	cout<<ans<<"\n"s;
}

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

using namespace std;

typedef vector< vector<int> > Graph;

int n, m;
Graph g;

bool judge(vector<int>& route) {
	if (route[0] != 0) return false;
	for (int i = 1; i < n; i++) {
		if (find(g[route[i - 1]].begin(), g[route[i - 1]].end(), route[i]) != g[route[i - 1]].end()) continue;
		return false;
	}
	return true;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	g.resize(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
 	vector<int> route(n);
	for (int i = 0; i < n; i++) route[i] = i;
	int ans = 0;
	do {
		ans += judge(route);
	} while (next_permutation(route.begin(), route.end()));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

x = INT()
a = 100
for i in range(100000):
    a *= 1.01
    a = int(a)
    if a >= x:
        print(i + 1)
        exit()

Measured memory_bytes: 68992
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  l.sort()
  ln=len(l)

  ans=0
  for i,x in enumerate(l):
    for j,y in enumerate(l[i+1:]):
      ans+=bisect.bisect_left(l,x+y)-(i+j+2)

  return ans

# main()
print(main())


Measured memory_bytes: 7116
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iomanip>
#include <bitset>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

const int N = 1e5 + 7;

vector <pair <int, int> > g[N];
ll d[N];
bool u[N];

void dfs(int v, ll x)
{
    if (u[v])
    {
        if (x != d[v])
        {
            cout << "No\n";
            exit(0);
        }
    }
    else
    {
        u[v] = true;
        d[v] = x;
        for (auto c : g[v])
        {
            int to = c.first;
            ll nx = x + c.second;
            dfs(to, nx);
        }
    }
}

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int l, r, d;
        cin >> l >> r >> d;
        l--, r--;
        g[l].push_back({r, d});
        g[r].push_back({l, -d});
    }
    for (int i = 0; i < n; i++)
    {
        if (!u[i])
        {
            dfs(i, 0);
        }
    }
    cout << "Yes\n";
}


Measured memory_bytes: 11520
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

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

#define all(c) (c).begin(), (c).end()
#define pb push_back
#define mp make_pair
#define EXIST(v,i) (find(all(v), i) != (v).end())
#define ERASE(v,i) (v).erase(remove(all(v), i), (v).end())
#define INDEX(v,i) (find(all(v), i) - (v).begin())
#define rep(i,n) for(int i = 0; i < (int)n; ++i)
#define debug(x) cerr << #x << " = " << (x) << endl;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

const int INF = 100000000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-10;

int main() {
	int days[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	string week[] = {"Wednesday", "Thursday", "Friday", "Saturday", "Sunday", "Monday", "Tuesday"};
	for(int month, day; cin >> month >> day && month && day;) {
		int sum = 0;
		rep(i,month - 1) {
			sum += days[i];
		}
		sum += day;
		sum %= 7;
		cout << week[sum] << endl;
	}
	return 0;
}

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

using ll=int64_t;

int main() {
  ll A;
  string B; cin >>A >>B;
  string temp=B.erase(B.size()-3,1);
  ll temp2=stoll(temp);
  ll ans=A*temp2/100;
  cout <<ans <<endl;
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int N;
int ans = 0;


int main(){
  cin >> N;
  pair<int,int> P[N];
  for(int i = 0; i < N;i++){
    int a,b;
    cin >> a >> b;
    P[i].first = a + b;
    P[i].second = a - b;
  }
  sort(P,P+N);
  int start = P[0].first;
  for(int i = 1;i < N;i++){
    if (start <= P[i].second){
      start = P[i].first;
      ans++;
    }
  }
  cout << ans+1 << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y;
    cin >> X >> Y;
    int cnt = 1;
    while(X * 2 <= Y) {X *= 2; cnt++;}
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int x;
    cin >> x;
    cout << !x << endl;
}


Measured memory_bytes: 3616
N = int(input())
p = list(map(int, input().split()))

index_not_equal_value_counter = 0
yes_or_no_flag = True
for i, v in enumerate(p):
    i = i + 1
    if i != v:
        index_not_equal_value_counter += 1
    if index_not_equal_value_counter > 2:
        yes_or_no_flag = False

if yes_or_no_flag:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 2940
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
using namespace std;
using ll=long long;

int main(){
    int k;
    int n;
    cin>>n>>k;
    if(k==1) cout<<0<<endl;
    else cout<<n-k<<endl;
    return 0;
}

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

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

using namespace std;

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<pii, int> para;
const int inf = 1e9 + 7;
const int maxN = 5e6 + 5;
const ll MOD = 1e9 + 7;

ll n, arr[maxN];
ll cnt[3][maxN];

void count(ll num) {
	REP(i, 61) {
		if (num & (1LL << (ll)i)) {
			cnt[1][i]++;
		} else {
			cnt[0][i]++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	REP(i, n) {
		cin >> arr[i];
		count(arr[i]);
	}
	ll ans = 0;
	REP(i, 61) {
		ll pot = (1LL << (ll)i) % MOD;
		ans += (((cnt[0][i] * cnt[1][i]) % MOD) * pot) % MOD;
		ans %= MOD;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 6400
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
const int INF=2<<20;
typedef long long int llf;
int main() {
	// your code goes here
	int num[8]={0,1,2,3,5,7,8,9};
	llf x=50,y,tx,ty,kx,ky,ans;
	llf n;
	while(cin >> n && n!=0){
		x=50;
		while(n/(llf)pow((llf)8,(llf)x)==0)
		x--;
		while(x!=-1){
			cout << num[(n%((llf)pow((llf)8,(llf)x+1)))/(llf)pow((llf)8,(llf)x)];
			x--;
		}
		cout << endl;
		
	}
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	int h, w, t;
	cin >> h >> w >> t;
	vector<string> s(h);
	for (int i = 0; i < h; i++) {
		cin >> s[i];
	}

	int ans = 0;
	for (int i = 0; i < (1 << h); i++) {
		vector<int> a(h);
		for (int j = 0; j < h; j++) {
			if (((i >> j) & 1) == 1) {
				a[j] = 1;
			}
		}
		for (int j = 0; j < (1 << w); j++) {
			vector<int> b(w);
			for (int k = 0; k < w; k++) {
				if (((j >> k) & 1) == 1) {
					b[k] = 1;
				}
			}

			int now = 0;
			for (int k = 0; k < h; k++) {
				for (int l = 0; l < w; l++) {
					if (a[k] == 0 && b[l] == 0 && s[k][l] == '#') {
						now++;
					}
				}
			}

			if (now == t) {
				ans++;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

typedef long long int ll;
typedef vector<int> vi;
typedef set<int> si;
typedef set<ll> sll;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pvec(v) for(auto e: v) cout << e << " ";
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i, a, b) for(int i = (a); i<(b); ++i)
#define pb push_back
#define INF 1000000005
#define MOD 1000000007
#define all(v) v.begin(), v.end()

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

ll power(ll x, ll y, ll p = MOD){  
    ll res = 1LL; 
    x = x % p;
    if (x == 0) return 0;
    while (y > 0){
        if (y & 1LL)  
            res = (res*x) % p;
        y = y>>1LL; 
        x = (x*x) % p;  
    }  
    return res;  
}  

int main(){
	IO
	int H, W;
	cin >> H >> W;

	char mat[H][W];
	string tmp;
	for(int i = 0; i<H; ++i) {
		cin >> tmp;
		for(int j = 0; j<W; ++j) {
			mat[i][j] = tmp[j];
		}
	}

	vll prev(W, 1), curr(W, 0);
	bool poss = true;
	for(int i = 0; i < W; ++i) {
		if(mat[0][i] == '#' && poss) {
			prev[i] = 0;
			poss = false;
		}
		if(!poss) 
			prev[i] = 0;
		// cout << prev[i] << " ";
	}
	// cout << endl;

	for(int i = 1; i<H; ++i) {
		if(mat[i][0] != '#') curr[0] = prev[0];
		else curr[0] = 0;
		
		for(int j = 1; j<W; ++j) {
			if(mat[i][j] == '#')
				curr[j] = 0;
			else
				curr[j] = (prev[j] + curr[j - 1])%MOD;
		}

		for(int j = 0; j < W; ++j) {
			// cout << curr[j] << " ";
			prev[j] = curr[j];
		}
		// cout << endl;
	}

	cout << prev[W - 1] << endl;
	return 0;
}

Measured memory_bytes: 4596
import java.util.*

val sc = Scanner(System.`in`)
val X = sc.nextInt()

fun main(args: Array<String>) {
    var ans = 1

    var i = 2
    while (i * i <= X) {
        var j = i * i
        while (j <= X) {
            ans = Math.max(ans, j)
            j *= i
        }
        i++
    }

    println(ans)
}


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

using ll = long long;

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

    ll N;
    cin >> N;
    
    ll h, n, w;
    ll h_max, n_max;
    ll deno;
    ll w_nume, w_deno;
    
    h_max = 3 * N / 4;
    for (h = 1; h <= h_max; h++) {
        deno = 4 * h - N;
        if (deno <= 0)
            continue;
        n_max = 2 * N * h / deno;
        for (n = h; n <= n_max; n++) {
            w_deno = 4 * h * n - N * n - N * h;
            if (w_deno <= 0)
                continue;
            w_nume = N * h * n;
            if (w_nume % w_deno == 0) {
                w = w_nume / w_deno;
                cout << h << " " << n << " " << w << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <stack>

#define N 100

using namespace std;

int d[N],f[N],m[N][N],ucolor[N],t,n,nt[N];

int next(int u2){
	int r;
	for(r=nt[u2];r<n;r++){
		nt[u2] = r+1;
		if(m[u2][r]){
			return r;
		}
	}
	return -1;
}

void dfsvisit(int uu){
	int u3=0,v,i;
	for(i=0;i<n;i++){
		nt[i] = 0;
	}
	stack<int> s;
	s.push(uu);
	ucolor[uu] = 1;
	d[uu] = ++t;
	while( !s.empty() ){
		u3 = s.top();
		v = next(u3);
		if(v != -1){
			if(ucolor[v] == 0){
				ucolor[v] = 1;
				d[v] = ++t;
				s.push(v);
			}
		}else{
			s.pop();
			ucolor[u3] = 2;
			f[u3] = ++t;
		}
	}
}

void dfs(){
	int i,j;
	for(i=0;i<n;i++){
		ucolor[i] = 0;
		nt[i] = 0;
	}
	for(j=0;j<n;j++){
		if(ucolor[j]==0){
			dfsvisit(j);
		}
	}
	for(i=0;i<n;i++){
		printf("%d %d %d\n",i+1,d[i],f[i]);
	}
}

int main(void){
	int i,j,u1,k,box;
	t = 0;// 時間の初期化
	for(i=0;i<N;i++){
		for(j=0;j<N;j++)m[i][j]=0;
	}
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d",&u1,&k);
		u1--; //頂点番号、その隣接する頂点の数
		for(j=0;j<k;j++){
			scanf("%d",&box);
			box--; // 隣接する頂点の番号
			m[u1][box] = 1;
		}
	}
	dfs();
	return 0;
}


Measured memory_bytes: 2740
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int n = Integer.parseInt(sc.next());
	restaurant[] res = new restaurant[n];

	for(int i = 0; i < n; i++) {
		res[i] = new restaurant(sc.next(),sc.nextInt(),i+1);
	}

	Arrays.sort(res, new Comparator<restaurant>(){
		public int compare(restaurant R1, restaurant R2) {
			if(R1.name.equals(R2.name)) {
				return R2.point - R1.point;
			}
			return R1.name.compareTo(R2.name);
		}});
	for(restaurant r : res)
		System.out.println(r.num);

	sc.close();
	}

	static class restaurant{
		private final String name;
		private final int point;
		private final int num;
		restaurant(String name, int point, int num){
			this.name = name; this.point = point; this.num = num;
		}
	}
}


Measured memory_bytes: 21332
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<set>
#include<cstdlib>
#include<cctype>
#include<ctime>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 2e5 + 5;
const ll maxm = 1e3 + 5;
template<class T>
inline T qread(T &IEE){
	register T x = 0, f = 1;
	register char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-'){
			f = -f;
		}
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return IEE = x * f;
}
template<class T>
inline void qwrite(T a){
	if(!a){
		putchar('0');
		return ;
	}
 	if(a < 0){
		putchar('-');
		a = -a;
	}
	if(a > 9) qwrite(a / 10);
	putchar(a % 10 + 48);
	return ;
}
template<class T>
inline T ab(T a){
	return (a > 0) ? a : -a;
}
ll p = 1, ans = 0, len;
char ch[maxn];
ll f[maxn], cnt[2020];
int main(){
	cin >> (ch + 1);
	len = strlen(ch + 1);
	for(int i = len;i >= 1;i--){
		f[i] = (f[i + 1] + (ch[i] - '0') * p) % 2019;
		p *= 10;
		p %= 2019;
		cnt[f[i]]++;
	}
	cnt[0]++;
	for(int i = 0;i <= 2019;i++){
		ans += (cnt[i] - 1) * cnt[i] / 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5380
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
//予想として、最小の値が正か負かで決まってくるはず
//負の数が偶数なら全て正になる。

int main()
{
    int n;
    cin >> n;
    ll count = 0;
    ll e = 0;
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    rep(i, n)
    {
        ll u;
        cin >> u;
        if (u < 0)
        {
            e++; //マイナスが0ならeは偶数
        }
        count += labs(u);
        pq.push(labs(u));
    }
    if (e % 2 == 0)
    {
        cout << count;
    }
    else
    {
        cout << count - 2 * pq.top();
    }
}

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

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

int A, B;
string op;
cin >> A >> op >> B;
if (op == "+") {
cout << A + B;
} else {
cout << A - B;
}

}


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 all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX/2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

struct UnionFind {

	vi data;

	UnionFind(int n = 0) {
		data.assign(n, -1);
	}

	int find(int k) {
		if (data[k] < 0) return k;
		return data[k] = find(data[k]);
	}
	bool unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) return false;
		if (data[x] > data[y]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		return true;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int k) { return -data[find(k)]; }

};

int main() {

	int n, m;
	cin >> n >> m;
	vi p(n);
	rep(i, n) { cin >> p[i];p[i]--; }

	UnionFind uf(n);

	rep(i, m) {
		int x, y;
		cin >> x >> y;
		uf.unite(x - 1, y - 1);
	}

	int ans = 0;
	rep(i, n)if (uf.same(i, p[i]))ans++;

	cout << ans << endl;

}

Measured memory_bytes: 1024
k,n = map(int, input().split())
a = list(map(int, input().split()))

kyori=[0]*len(a)

for i in range(1,len(a)):
    kyori[i]=a[i]-a[i-1]

kyori[0]=a[0]+k-a[-1]

print(sum(kyori)-max(kyori))

Measured memory_bytes: 32316
#include<iostream>
#include<string>
using namespace std;
int main()
{
  int n,i;
  long long t=0,res=0;
  string s;
  cin >> s;
  n=s.size();
  for(i=0;i<n;i++)
    if(s[i]=='A'){
      t++;
    }else if(i<n-1&&s.substr(i,2)=="BC"){
      res+=t;
      i++;
    }else{
      t=0;
    }
  cout << res << endl;
  return 0;
}

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

int main(){
  int N;
  cin>>N;
  int D[N];
  int A[25];
  for(int i=0;i<24;i++){
    A[i]=0;
  }
  A[0]=1; 
  A[24]=1;
  int flag=1;
  map<int,int>mp;
  for(int i=0;i<N;i++){
    cin>>D[i];
    if(D[i]==0){
      cout<<0<<endl;
      return 0;
    }
  }
  sort(D,D+N);
  for(int i=0;i<N;i++){
    if(flag==1){
      A[D[i]]=1;
      mp[D[i]]++;
    }
    else{
      A[24-D[i]]=1;
      mp[24-D[i]]++;
    }
    flag*=(-1);
  }
  int maxans=12;
  vector<int>T;
  
  for(int i=0;i<24;i++){
    if(A[i]==1){
      T.emplace_back(i);
      //cout<<i<<"#"<<endl;
    }
  }
  T.push_back(24);
  for(int i=0;i<T.size();i++){
     maxans=min(maxans,abs(T[i+1]-T[i]));
  }
  
  for(auto itr=mp.begin();itr !=mp.end();itr++){
    if((itr->second)>1){
      cout<<0<<endl;
      return 0;
    }
  }

  
  cout<<maxans<<endl; 

  return 0;
}

    
    

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int left1, left2;
    int right1, right2;
    int left, right;

    cin >> left1 >> left2 >> right1 >> right2;
    left = left1 + left2;
    right = right1 + right2;

    if (left > right) {
        cout << "Left" << endl;
    }
    else if(left < right) {
        cout << "Right" << endl;
    }
    else if (left == right) {
        cout << "Balanced" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
  char s[4];
  cin>>s;
  bool flag=false;
  for(int i=0;i<3;i++){
    if(s[i]==s[(i+1)%3])flag=true;
  }
  if(flag)cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
def abs(a):
    return a if a > 0 else -a

def main():
    MAX = 10**5 * 10**6
    n = int(input())
    h = list(map(int, input().split()))
    a = [MAX] * n
    a[0] = 0
    for i in range(n):
        if i + 1 < n:
            a[i + 1] = min(a[i + 1], abs(h[i + 1] - h[i]) + a[i])
        if i + 2 < n:
            a[i + 2] = min(a[i + 2], abs(h[i + 2] - h[i]) + a[i])
    print(a[-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 13908
#include<iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
    int saikoro,point,i,j=0;
    double rate,result=0;
    cin >> saikoro >> point;
    cout<< fixed;
    for( i = 1 ;i <= saikoro ;i++){
      if( point > i){
        for( j = 1; point > i * std::pow( 2.0, j ); j++){
        }
      }
      rate = saikoro  * std::pow( 2.0 , j );
      result  += (1/rate);
      j=0;
    }
    cout << std::setprecision(12)<<result << endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
        n: usize,
    }
    let mut ans = 0;
    for i in 1..=n {
        let m = n / i;
        ans += m * (i + (i * m)) / 2;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,x,n) for(ll i=x;i<n;i++)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    ll a,b;
    cin>>a>>b;
    cout<<a*b;

}   

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int d[4] = {};
    rep(i, 0, 4) cin >> d[i];
    int n;
    cin >> n;
    n *= 4;
    int ans = 0;
    repb(i, 3, 0){
        int tmp = 1 << i;
        int MIN = INF;
        rep(j, 0, i + 1){
            int now = d[j] * (1LL << (i - j));
            chmin(MIN, now);
        }
        ans += MIN * (n / tmp);
        n %= tmp;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var mod = 2019;
            var LR = Sarray();
            var L = LR[0];
            var R = LR[1];
            if (mod <= R - L)
            {
                WriteLine(0);
                return;
            }
            var min = 2018L;
            for (var i = L; i < R; ++i)
            {
                for (var j = i + 1; j <= R; ++j)
                {
                    min = Min(min, (((i % mod) * (j % mod)) % mod));
                }
            }
            WriteLine(min);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13268
#include<stdio.h>

int A[1000000], n;

/*二分探索*/

int binarySearch(int key){
	int left = 0;
	int right = n;
	int mid;
	
	while( left < right ){
		mid = (left + right) / 2;
		if( key == A[mid] ) return 1; /*keyを発見*/
		if( key > A[mid] ) left = mid + 1; /*後半を探索*/
		else if( key < A[mid] ) right =mid; /*前半を探索*/
	}
	return 0;
}

int main(){
	int i, q, k, sum=0;
	
	scanf("%d", &n);
	for( i=0; i<n; i++){
		scanf("%d",&A[i]);
	}
	
	scanf("%d",&q);
	for(i=0; i<q; i++){
		scanf("%d",&k);
		if(binarySearch(k))sum++;
	}
	printf("%d\n",sum);
	
	return 0;
}



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

#define ll long long
#define mod 1000000007
#define pb push_back
#define UM unordered_map

int main()
{
  ll a,b;
  cin>>a>>b;
  ll c[b],sum=0;
  for(ll i=0;i<b;i++)
  {
    cin>>c[i];
    sum+=c[i];
  }
  if(sum>=a)
  cout<<"Yes"<<endl;
  else
  cout<<"No"<<endl;

}


Measured memory_bytes: 1024
n = input()
if n[-1]=="2" or n[-1]=="4" or n[-1]=="5" or n[-1]=="7" or n[-1]=="9":
    print("hon")
elif n[-1]=="0" or n[-1]=="6" or n[-1]=="1" or n[-1]=="8":
    print("pon")
else:
    print("bon")


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

int main(){
	double d;
	while(cin >> d && d){
		if( d < 1.0 - 1e-9 ){
			printf("%.10lf\n",d*sqrt(2));
		}else{
			double x = (int)(d+1e-9);
			printf("%.10lf\n",max(x+1,d*sqrt(2)));
		}
	}
}

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

bool vist[25][25];
char table[25][25];
int row, colam;
int rx[] = {0,0,1,-1};
int cy[] = {1,-1,0,0};

bool check( int r, int c ){
    if( r < 0 || r >= row || c < 0 || c >= colam || table[r][c] == '#' || vist[r][c] == true ){
        return false;
    }
    return true;
}

int bfs( int sx, int sy ){
    memset( vist, false, sizeof vist );
    queue<pair<int,int>>q;
    vist[sx][sy] = true;
    int dis[row][colam];
    for( int i = 0; i < row; i++ ){
        for( int j = 0; j < colam; j++ ){
            dis[i][j] = 10000;
        }
    }
    dis[sx][sy] = 0;
    q.push( make_pair(sx,sy) );
    int res = 0;
    while( !q.empty() ){
        sx = q.front().first;
        sy = q.front().second;
        q.pop();
        for( int i = 0; i < 4; i++ ){
            int ux = sx+rx[i];
            int vx = sy+cy[i];
            if( check( ux, vx ) == true ){
                dis[ux][vx] = min( dis[ux][vx], dis[sx][sy]+1 );
                res = max( dis[ux][vx], res );
                vist[ux][vx] = true;
                q.push( make_pair( ux, vx ) );
            }
        }
    }
    return res;
}

int main(){
    while( cin >> row >> colam ){
        vector<pair<int,int>>v;
        for( int i = 0; i < row; i++ ){
            for( int j= 0; j < colam; j++ ){
                cin >> table[i][j];
                if( table[i][j] == '.' ){
                    v.push_back( {i,j} );
                }
            }
        }
        int res = 0;
        for( int i = 0; i < v.size(); i++ ){
            res = max( res, bfs( v[i].first, v[i].second ) );
        }
        cout << res << endl;
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 998244353;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	int n; cin >> n;
	string s[10]={"pon","pon","hon","bon","hon","hon","pon","hon","pon","hon"};
	cout << s[n%10] << endl;
	return 0;
}

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

int main() {

	int N;
	cin >> N;
    int maxCount = 0;
  	int number = N;
  	
  	for(int i=0; i<N; i++){
      int count = 0;
      int num = i+1;
      while(num%2 == 0){
        num /= 2;
        count++;  
      }
      if(count > maxCount){
        maxCount = count;
        number = i+1;
      }
    }
  
   	 cout << number << endl;

}


Measured memory_bytes: 256
// D.

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

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	while (true) {
		LL n = -1, m = -1;
		cin >> n >> m;
		if (n <= 0) break;
		vector<LL> a(m), b(m), c(m), d(n, 1LL << 60);
		d[0] = 0;
		for (LL i = 0; i < m; ++i) {
			cin >> a[i] >> b[i] >> c[i];
			--a[i], --b[i];
			c[i] = -c[i];
		}
		auto update = [&]() {
			for (LL j = 0; j < m; ++j) {
				if (d[b[j]] > d[a[j]] + c[j]) {
					d[b[j]] = d[a[j]] + c[j];
				}
			}
		};
		for (LL i = 0; i < n - 1; ++i) {
			update();
		}
		vector<LL> first = d;
		for (LL i = 0; i < n; ++i) {
			update();
		}
		LL ans = -d[n - 1];
		if (ans > -first[n - 1]) {
			cout << "inf" << endl;
		} else {
			cout << ans << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

int main() {
  int h,w;
  cin>>h>>w;
  int ans[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      ans[i][j]=1000;
    }
  }
  char memo[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>memo[i][j];
    }
  }
  ans[0][0]=0;
  deque<int> route;
  route.push_back(0);route.push_back(0);
  while(!route.empty()){
    int y=route.front();route.pop_front();
    int x=route.front();route.pop_front();
    int dy[2]={0,1};
    int dx[2]={1,0};
    for(int i=0;i<2;i++){
      int ny=y+dy[i],nx=x+dx[i];
      if(ny>=h||nx>=w) continue;
      if(ans[ny][nx]!=1000) continue;
      if(memo[y][x]==memo[ny][nx]) {
        ans[ny][nx]=ans[y][x];
        route.push_front(nx);route.push_front(ny);
      }
      else {
        ans[ny][nx]=ans[y][x]+1;
        route.push_back(ny);route.push_back(nx);
      }
    }
  }
  if(memo[0][0]=='.'&&memo[h-1][w-1]=='.')
  cout<<(ans[h-1][w-1]-ans[0][0])/2<<endl;
  else if(memo[0][0]=='#'&&memo[h-1][w-1]=='#')
  cout<<(ans[h-1][w-1]-ans[0][0])/2+1<<endl;
  else cout<<(ans[h-1][w-1]-ans[0][0]+1)/2<<endl;
  return 0;
}


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

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;

 main()

{
    fast
    int n;
    cin>>n;
    int a[n+2];
    int flag=0;
    f(i,1,n)
    {
        cin>>a[i];
        if(a[i]%2==0)
        {
            if(!(a[i]%3==0 || a[i]%5==0))flag=1;
        }
    }
    if(!flag)cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
    return 0;

}





































Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll one = 1;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    int N, K;
    cin >> N >> K;
    int ans = 0;
    while(N>0){
        ans++;
        N = N / K;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 3744
using System;
using System.Linq;
class sol
{
    static void Main()
    {
        var s = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int N = s[0];
        int A = s[1];
        int B = s[2];
        int ans = N*A <= B ? N*A : B;
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#include <queue>
#define int long long
using namespace std;
int MOD = 1000000007;
int calc(int n){
    int dp[n+1][n/3 + 1];
    for (int i=0; i <= n; i++){
        for (int j=0; j <= n/3; j++){
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;
    for (int i=1; i <= n; i++){
        for (int j=0; j <= n/3; j++){
            if (3 * j < i || j > i) continue;
            int sv = 3*j - i + 1;
            dp[i][j] += dp[i-1][j] * sv + dp[i-1][j-1];
            dp[i][j] %= MOD;
        }
    }
    return dp[n][n/3];
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i=0; i < n; i++) cin >> a[i];
    for (int i=0; i < n; i++) cin >> b[i];
    vector<int> fa(n), fb(n);
    for (int i=0; i < n; i++){
        fa[a[i]-1]=i;
        fb[b[i]-1]=i;
    }
    vector<bool> used(n);
    int P[n][n];
    for (int i=0; i < n; i++){
        for (int j=0; j < n; j++){
            fill(used.begin(), used.end(), false);
            int C = 0;
            for (int k=i; k >= 0; k--){
                C += (!used[a[k]-1]);
                used[a[k]-1] = true;
            }
            for (int k=j; k >= 0; k--){
                C += (!used[b[k]-1]);
                used[b[k]-1] = true;
            }
            P[i][j] = C;
        }
    }
    int RES = calc(n);
    int dp[n][n];
    for (int i=0; i < n; i++){
        for (int j=0; j < n; j++){
            if (fb[a[i]-1] <= j || fa[b[j]-1] <= i){
                dp[i][j] = 0;
                continue;
            }
            dp[i][j] = max((int) 0, 3-P[i][j]);
        }
    }
    for (int i=0; i < n; i++){
        for (int j=1; j < n; j++){
            dp[i][j] += dp[i][j-1];
            dp[i][j] %= MOD;
        }
        for (int j=0; j < n; j++){
            if (i > 0) dp[i][j] += dp[i-1][j];
            dp[i][j] %= MOD;
        }
    }
    for (int it=1; it < n/3; it++){
        for (int i=n-1; i >= 0; i--){
            for (int j=n-1; j >= 0; j--){
                if (fb[a[i]-1] <= j || fa[b[j]-1] <= i || i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = max((int) 0, 3*(it+1)-P[i][j]) * dp[i-1][j-1];
                dp[i][j] %= MOD;
            }
            //for (int j=0; j < n; j++){
               // cout << dp[i][j] << " ";
            //}
            //cout << endl;
        }
        for (int i=0; i < n; i++){
            for (int j=1; j < n; j++){
                dp[i][j] += dp[i][j-1];
                dp[i][j] %= MOD;
            }
            for (int j=0; j < n; j++){
                if (i > 0) dp[i][j] += dp[i-1][j];
                dp[i][j] %= MOD;
            }
        }
    }
    int ans = dp[n-1][n-1];
    ans *= RES;
    cout << ans % MOD << endl;
    return 0;
}



Measured memory_bytes: 2816
n,m = gets.split.map &:to_i
if n > 1
  sta = 1 * 10**(n-1)
else
  sta = 0
end
su = sta.to_s.split('')
check = 0
num = Array.new(n){[]}
m.times do
  a,b = gets.split.map &:to_i
  num[a-1] << b
  num[a-1].uniq!
end

n.times do |i|
  check = 1 if num[i].size > 1
  check = 1 if num[i].include?(0) && i.zero? && n > 1
end

if check > 0
  puts -1
  exit
end

n.times do |i|
  if num[i].empty?
    print su[i]
  else
    print num[i].join('')
  end
end

Measured memory_bytes: 1788
//
//  main.cpp
//  CP
//
//  Created by Shiv Pavan Raj on 22/02/20.
//  Copyright © 2020 Shiv Pavan Raj. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)(x).size())
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define M 1000000007
#define MM 998244353
#define SZ(a) int((a).size())

using ll = long long;
using VI = vector<int>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using VLL = vector<ll>;
using ld = long double;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
      
}
const int MX = 2e5+10;
const int MX2 = 1e6+5;

ll INF= 4 * (ll)1e18;
int mx = 2 * (ll)1e9 + 10;


int main(int argc, const char * argv[]) {
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); // insert code here...
    int n;
    cin >> n;
    vector<int> a(2*n);
    for(int i = 0; i < 2 *n; ++i) cin >> a[i];
    sort(a.begin(),a.end());
    int ans= 0;
    for (int i=2*n - 2; i >= 0; i-=2) {
        ans = ans + a[i];
    }
    cout << ans << endl;
    return 0;
}







Measured memory_bytes: 256
x,n=map(int,input().split())
p=list(map(int,input().split()))
if(n==0):
    print(x)
    exit()
ans=1000
c=1000
for i in range(-1,102):
    b=1
    for j in range(n):
        if(p[j]==i):
            b=0
    if(b==0):
        continue
    else:
        a=abs(x-i)
        if(ans==a):
            if(c>i):
                c=i
        elif(a<ans):
            ans=a
            c=i
print(c)

Measured memory_bytes: 9112
// abc131c.cpp : Anti-Division
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b){
  if(a<b) swap(a,b);
  while(b){ ll r = a%b; a = b; b = r; }
  return a;
}

int main(){
  ll A,B,C,D; cin>>A>>B>>C>>D;
  ll E = C/gcd(C, D)*D;
	ll n = B-A+1;
	ll c = (B/C-(A-1)/C) + (B/D-(A-1)/D) - (B/E-(A-1)/E);
	cout<< n-c << endl;
}

Measured memory_bytes: 256