akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define all(x) begin((x)), end((x))
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    if (n%2==1) {
        ll sm = n/2, lg = sm+1;
        rep(i,m) {
            cout << sm << " " << lg << endl;
            sm--;lg++;
        }
    }
    else {
        ll ue = n / 2, sita = ue;
        ll lg,sm, cnt;
        if (n % 4 == 0) {
            sm = sita + 2; lg = n;
            cnt = ue / 2 - 1;
        }
        else {
            ue -= 1;
            sm = sita + 1; lg = n;
            cnt = ue / 2;
        }
        while(m>0) {
            if (cnt == 0) {
                if (n % 4 == 0) {
                    sm = 1;
                    lg = sita;
                }
                else {
                    sm = 1;
                    lg = sita-1;
                }
            }
            cout << sm << " " << lg << endl;
            sm++;lg--;cnt--;
            m--;
        }
    }
    return 0;
}


Measured memory_bytes: 3656
def bfs(graph, start, result):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        unvisited = unvisited[1:]
        if visited[now] == None:
            result[now] = 0
        else:
            result[now] = result[visited[now]] + 1
        for next in graph[now][2:]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return visited

n = int(input())
g = [[]]
r = {i: -1 for i in range(n + 1)}

for i in range(n):
    g.append(list(map(int, input().split())))

v = bfs(g, 1, r)

for i in range(1,n+1):
    print(i, r[i])

Measured memory_bytes: 7812
//============================================================================
// Name        : aoj0040.cpp
// Author      : afterCmidday
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cctype>
#include <string>

using namespace std;


int gcd(int x,int y){
	if(y == 0){
		return x;
	}
	return gcd(y,x % y);
}
int main(void){
	int a, b, n, i, j;
	string str,ans;
	cin >> n;
	getline(cin,str);
	for(i = 0;i < n;i++){
		ans = "";
		getline(cin,str);
		for(a = 0;;a++){
			if(gcd(a,26) == 1){
				for(b = 0;b < 26;b++){
					string tmp = "";
					for(j = 0;j < str.size();j++){
						if(isalpha(str[j])){
							for(char c = 'a';c <= 'z';c++){
								if((str[j] - 'a') == (a * (c - 'a') + b) % 26){
									tmp += c;
								}
							}
						}else{
							tmp += str[j];
						}
					}
					if(tmp.find("that") != -1 || tmp.find("this") != -1){
						ans = tmp;
						break;
					}
				}
				if(ans != ""){
					break;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<char> S;

int digit(int n){
    int i=0;
    while(n>0){
        n/=10;
        i++;
    }
    return i;
}


int main(){
    int n;
    cin>>n;
    int k=digit(n);
    int o=0;
    if(k==1) cout<<n<<endl;
    else if(k==2) {
        cout<<9<<endl;
    }
    else if(k==3){
        cout<<9+n-100+1<<endl;
    }
    else if(k==4){
        cout<<909<<endl;
    }
    else if(k==5){
        cout<<909+n-10000+1<<endl;
    }
    else cout<<"90909"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

int const N = 1e5 + 41;

int a[N], n, maxi, k, t, was[N];

int main(){
	scanf("%d%d",&k,&t);
	for(int i=0;i<t;++i){
		scanf("%d",&a[i]);
		maxi = max(maxi, a[i]);
	}
	if(maxi <= k/2 + k % 2){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<k;i+=2){
		was[i] = 1;
		--maxi;
	}
	if(k % 2 == 0){
		was[k-1] = 1;
		--maxi;
	}
	for(int i=0;i<k && maxi > 0;++i){
		if(!was[i]){
			was[i] = 1;
			--maxi;
		}
	}
	int ans = 0;
	for(int i=1;i<k;++i){
		ans += was[i] * was[i-1];
	}
	printf("%d\n",ans);


	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test() int t;cin>>t;while(t--)
#define forn(i,f,n) for(int i=f;i<f+n;i++)
#define rforn(i,l,n) for(int i=l;i>l-n;i--)
#define all(v) v.begin(),v.end()
#define prin(V) for(auto v:V) cout<<v<<" ";cout<<endl
#define take(V,f,n) for(int i=f;i<f+n;i++) cin>>V[i]
#define what(x) cerr<<#x<<" = "<<x<<endl
#define KStest() int t,t1;cin>>t;t1=t;while(t--)
#define KScout cout<<"Case #"<<t1-t<<": "

const int MOD = 1e9+7,MAX = 1e5+5;
/////////////////FastExp///////////////////
ll powN(ll a,ll p)
{
	if(p==0) return 1;
	ll z=powN(a,p/2);
	z=(z*z)%MOD;
	if(p%2) z=(z*a)%MOD;
	return z;
}
/////////////////FastExp///////////////////
//////////////////Sieve////////////////////
vector<bool> is_prime(MAX+1, true);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}
//////////////////Sieve////////////////////

int main()
{
	string s;
	cin>>s;
	if(s[2]==s[3]&&s[4]==s[5]) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}		

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>
#define mem(a) memset(a, 0, sizeof a)
#define Buff ios::sync_with_stdio(false)
using namespace std;
const int N = 1e5+7;
const double eps = 1e-6;
int dcmp(double x)
{
    if(fabs(x) < eps)   return 0;
    else                return x < 0 ? -1 : 1;
}
//直线，向量
struct Point
{
    double x;
    double y;
    Point(double x=0, double y=0):x(x), y(y) {}
};
typedef Point Vector;
double operator ^ (const Vector & v, const Vector & w)  {return v.x * w.y - v.y * w.x;}
double operator * (const Vector & v, const Vector & w)  {return v.x * w.x + v.y * w.y;}
Vector operator - (const Vector & v, const Vector & w)  {return Vector(v.x - w.x, v.y - w.y);}
bool OnSeg(Point O, Point A, Point B)                   {return !dcmp((A - O) ^ (B - O)) && dcmp((A - O) * (B - O)) <= 0;}
int inPolygon(Point P, int n, Point* polygon)//点与多边形的位置关系
{
    int wn = 0;
    for(int i = 0; i < n; i++)
    {
        Point P1 = polygon[i], P2 = polygon[(i + 1) % n];
        if(OnSeg(P, P1, P2))    return 1;
        int k = dcmp((P2 - P1) ^ (P - P1));
        int d1 = dcmp(P1.y - P.y);
        int d2 = dcmp(P2.y - P.y);
        if(k > 0 && d1 <= 0 && d2 > 0)   wn++;
        if(k < 0 && d2 <= 0 && d1 > 0)   wn--;
    }
    return (wn ? 2 : 0);
}
int n, m;
Point P, p[N];
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    scanf("%d", &m);
    while(m --)
    {
        scanf("%lf %lf", &P.x, &P.y);
        printf("%d\n", inPolygon(P, n, p));
    }
    return 0;
}



Measured memory_bytes: 4820
#include<stdio.h>
int main(void){
	int A, B, S, t;
	scanf("%d", &A);
	scanf("%d", &B);
	S = 0;
	t = 0;
	while(t < 2){
		if(A >= B){
			S += A--;
		}else{
			S += B--;
		}
	t++;
	}

	printf("%d", S);
	return 0;
}

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



int main(){
  int N, a, b, c; cin >> N;

  a = N / 100;
  b = (N % 100) / 10;
  c = (N % 10);
  
  cout << (10-a) * 100 + (10-b) * 10 + (10-c) << endl;

}


Measured memory_bytes: 256
[A, B, K] = list(map(int, input().split()))
if A > K :
  takahashi = A - K
  aoki = B
elif A <= K < A + B:
  takahashi = 0
  #高橋くんが食べたクッキーはA枚
  #残りの試行回数はK - A回
  aoki = B - (K - A)
else:
  takahashi = 0
  aoki = 0
print(takahashi, aoki)

Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template #


S = li()
N = len(S)
bw = []
for i in range(N):
    if i % 2 == 0:
        bw.append(1)
    else:
        bw.append(0)

# print(bw)
cnt = 0
for i in range(N):
    if S[i] != str(bw[i]):
        cnt += 1

# print(cnt)
if cnt >= N // 2 + 1:
    print(N - cnt)
else:
    print(cnt)


Measured memory_bytes: 4652
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
int N;
/* function */
int query(int x) {
    cout << x << endl;
    string ans;
    cin >> ans;
    if (ans=="Vacant")
    exit(0);
    return (ans=="Male");
}

/* main */
int main(){
    cin >> N;
    cout.flush();
    int cur;
    int left = 0, right = N - 1;
    int head = query(left), tail = query(right);
    while (1) {
        int mid = (right + left) / 2;
        cur = query(mid);
        if ( (mid - left) % 2 && head == cur || (mid - left) % 2 == 0 && head != cur ) {
            right = mid;
            tail = cur;
        }
        else {
            left = mid;
            head = cur;
        }
    }
}

Measured memory_bytes: 852
f = input().strip().split()
q = []
for e in f:
    if e == '+':
        q.append(q.pop() + q.pop())
    elif e == '-':
        q.append(-q.pop() + q.pop())
    elif e == '*':
        q.append(q.pop() * q.pop())
    else:
        q.append(int(e))

print(q[0])

Measured memory_bytes: 7636
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<pair<int, int>>>;

typedef struct edge {
    int from, to, cost;
} edge;

int main() {
    int N, M;
    bool plexist = false;
    cin >> N >> M;
    vector<edge> ed(M);
    vector<ll> dist(N, -1e13);
    vector<bool> plfl(N);
    dist[0] = 0;
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        ed[i].from = a - 1;
        ed[i].to = b - 1;
        ed[i].cost = c;
    }

    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < M; ++j) {
            edge tmp = ed[j];
            if(dist[tmp.to] < dist[tmp.from] + tmp.cost) {
                dist[tmp.to] = dist[tmp.from] + tmp.cost;
                if(i == N - 1) {
                    plfl[tmp.from] = plfl[tmp.to] = true;
                    plexist = true;
                }
            }
        }
    }

    if(plexist) {
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < M; ++j) {
                edge tmp = ed[j];
                if(plfl[tmp.from])
                    plfl[tmp.to] = true;
            }
        }
    }

    if(plfl[N - 1])
        cout << "inf" << endl;
    else
        cout << dist[N - 1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int n,i,j;
	cin>>n;
	int a[n],ans[n];
	for(i=0;i<n;i++)
		ans[i]=0;
	for(j=1;j<n;j++)
	{
		cin>>a[j];
		ans[a[j]-1]++;
	}	
	for(int k=0;k<n;k++)
		cout<<ans[k]<<endl;	
return 0;
}


Measured memory_bytes: 5160
h, w = map(int, input().split())
s = [['.' for i in range(w+2)]]
for i in range(h):
    s.append(list('.' + input() + '.'))
s.append(['.' for i in range(w+2)])
ans = 'Yes'
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == '#':
            if s[i-1][j] != '#' and s[i][j-1] != '#' and s[i+1][j] != '#' and s[i][j+1] != '#':
                ans = 'No'
                break
    else:
        continue
    break

print(ans)

Measured memory_bytes: 3064
s = int(input())

def f(n):
    if n % 2 == 0:
        return n//2
    else:
        return 3*n + 1

a = [0] * (10**6)
a[1] = s
a[0] = s
for i in range(2,10**6):
    x = f(a[i-1])
    if x in a:
        print(i)
        break
    else:
        a[i] = f(a[i-1])


Measured memory_bytes: 10868
#include<bits/stdc++.h>
using namespace std;
int n,h[100009],dp[100009];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++) cin>>h[i];
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(int i=2;i<n;i++) dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MAX_V 10000
using namespace std;
int V;                //????????°
vector<int> G[MAX_V]; //??°???????????£??\???????????¨???
int match[MAX_V];     //??????????????°????????¢
bool used[MAX_V];     //DFS??§?????§??????????????????????????°

//u??¨v????????¶????????°?????????????????????
void add_edge(int u,int v){
  G[u].push_back(v);
  G[v].push_back(u);
}

//?¢?????????????DFS??§??¢???
bool dfs(int v){
  used[v] = true;
  for(int i=0; i<G[v].size(); i++){
    int u = G[v][i], w = match[u];
    if(w<0 || !used[w] && dfs(w)){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

//?????¨??°??????????????§??????????????°????±???????
int bipartite_matching(){
  int res=0;
  memset(match, -1, sizeof(match));
  for(int v=0; v<V; v++){
    if(match[v] < 0){
      memset(used,0,sizeof(used));
      if(dfs(v)) res++;
    }
  }
  return res;
}


int main(){
  int n,m,l;
  cin>>n>>m>>l;
  for(int i=0,a,b;i<l;i++)cin>>a>>b,add_edge(a,n+b);
  V=n+m+2;
  cout <<bipartite_matching()<<endl;
}

Measured memory_bytes: 3528
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

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

    int N = scanner.nextInt();
    HashMap<String, Integer> S = new HashMap<String, Integer>();

    scanner.nextLine();
    for (int i = 0; i < N; i++) {
      String w = scanner.nextLine();
      Integer c = S.get(w);
      if (c == null) {
        S.put(w, 1);
      } else {
        S.remove(w);
        S.put(w, c + 1);
      }
    }

    int M = scanner.nextInt();
    HashMap<String, Integer> T = new HashMap<String, Integer>();

    scanner.nextLine();
    for (int i = 0; i < M; i++) {
      String w = scanner.nextLine();
      Integer c = T.get(w);
      if (c == null) {
        T.put(w, 1);
      } else {
        T.remove(w);
        T.put(w, c + 1);
      }

    }
    int max = 0;
    for (Map.Entry<String, Integer> entry : S.entrySet()) {
      int plus = entry.getValue();
      Integer minus = T.get(entry.getKey());
      if ( minus != null) {
        plus -= minus;
      }
      if ( plus > max ) {
        max = plus;
      }
    }
    System.out.println(max);

  }

}


Measured memory_bytes: 21844
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

bool betemp(string sleft, string sright, int left, int right)
{
  if (sleft == sright)
    return (right - left) % 2 == 1;
  else
    return (right - left) % 2 == 0;
}

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

  string vac = "Vacant";
  string sl, sr, s;
  int l = 0, r = N - 1;
  cout << l << endl;
  cin >> sl;
  if (sl == vac)
    return 0;
  cout << r << endl;
  cin >> sr;
  if (sr == vac)
    return 0;

  while (r - l > 1)
  {
    int m = (l + r) / 2;
    cout << m << endl;
    cin >> s;
    if (betemp(sl, s, l, m))
      sr = s, r = m;
    else
      sl = s, l = m;
  }

  return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N),B(N),C(N-1);
  for(int i=0; i<N; i++){
    cin >> A.at(i);
  }
  for(int i=0; i<N; i++){
    cin >> B.at(i);
  }
  for(int i=0; i<N-1; i++){
    cin >> C.at(i);
  }
  int x;
  x = A.at(0);
  int ans=0;
  ans += B.at(x-1);
  for(int i=1; i<N; i++){
    if(x == A.at(i)-1){
      ans += C.at(x-1);
    }
    x = A.at(i);
    ans += B.at(x-1);
  }
  cout << ans << endl;
  return 0;
}


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

#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  int k,n;
  cin>>k>>n;
  if(k%2==0)
    {
      cout<<k/2<<" ";
      rep(i,2,n+1) cout<<k<<" ";
      cout<<endl;
      return 0;
    }
  vi v;
  rep(i,1,n+1) v.pb((k+1)/2);
  int cnt=n/2;
  while(cnt)
    {
      if(v.back()==1)
	v.pop_back();
      else
	{
	  v.back()=v.back()-1;
	  while(sz(v)!=n) v.pb(k);
	}
      cnt--;
    }
  rep(i,0,sz(v)) cout<<v[i]<<" ";
  cout<<endl;
  return 0 ;
}


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

char s[105][105];

int main(){
	int a,b,k = 0; cin >> a >> b; a--,b--;
	cout << 100 << ' ' << 100 << endl;
	for(int i = 1;i <= 50;i++) 
		for(int j = 1;j <= 100;j++) s[i][j] = '#',s[i + 50][j] = '.';
	for(int i = 1;i <= 50;i += 2){
		for(int j = k + 1;j <= 100;j += 2){
			if(a > 0) s[i][j] = '.',a--;
		}
		k ^= 1;
	}
	k = 0;
	for(int i = 100;i >= 51;i -= 2){
		for(int j = 100 - k;j >= 1;j -= 2){
			if(b > 0) s[i][j] = '#',b--;
		}
		k ^= 1;
	}
	for(int i = 1;i <= 100;i++){
		for(int j = 1;j <= 100;j++){
			cout << s[i][j];
		}
		cout << endl;
	}
}

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


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

    char maze[h][w];
    int dist[h][w];

    vector <pair<int, int> > black;

    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
            cin >> maze[y][x];
            dist[y][x] = 1e9;
            if(maze[y][x] == '#'){
                black.push_back(make_pair(y, x));
                dist[y][x] = 0;
            }
        }
    }

    queue <pair<int, int> > q;

    for(int i = 0; i < black.size(); i++){
        q.push(black[i]);
    }

    pair<int, int> top;

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

        if(top.first-1 >= 0 and maze[top.first-1][top.second] == '.' and dist[top.first-1][top.second] == 1e9){
            q.push(make_pair(top.first-1, top.second));
            dist[top.first-1][top.second] = dist[top.first][top.second] + 1;
            maze[top.first-1][top.second] = '#';
        }
        if(top.first+1 < h and maze[top.first+1][top.second] == '.' and dist[top.first+1][top.second] == 1e9){
            q.push(make_pair(top.first+1, top.second));
            dist[top.first+1][top.second] = dist[top.first][top.second] + 1;
            maze[top.first+1][top.second] = '#';
        }
        if(top.second-1 >= 0 and maze[top.first][top.second-1] == '.' and dist[top.first][top.second-1] == 1e9){
            q.push(make_pair(top.first, top.second-1));
            dist[top.first][top.second-1] = dist[top.first][top.second] + 1;
            maze[top.first][top.second-1] = '#';
        }
        if(top.second+1 < w and maze[top.first][top.second+1] == '.' and dist[top.first][top.second+1] == 1e9){
            q.push(make_pair(top.first, top.second+1));
            dist[top.first][top.second+1] = dist[top.first][top.second] + 1;
            maze[top.first][top.second+1] = '#';
        }
    }

    int maxv = 0;

    for(int y = 0; y < h; y++){
        for(int x = 0; x < w; x++){
           
            maxv = max(dist[y][x], maxv);
           
        }
    }

    printf("%d\n", maxv);

    return 0;


}

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

int main(){
  int n;
  string s,ans;
  cin>>s;
  n=s.size();

  REP(i,n){
    if(s.at(i)=='0') ans+='0';
    else if(s.at(i)=='1') ans+='1';
    else if(ans.size()>0) ans.pop_back();
  }

  cout<<ans<<endl;
}

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

#define         ld                  long double
#define         lli                 long long int
#define         vi                  vector<int>
#define         vlli                vector<lli>
#define         vvi                 vector<vi >
#define         vvl                 vector<vlli >
#define         str                 string
#define         vs                  vector<str>
#define         vb                  vector<bool>
#define         mp                  make_pair
#define         pii                 pair<int, int>
#define         pll                 pair<lli, lli>
#define         vpii                vector<pii>
#define         vpll                vector<pll>
#define         pb                  push_back
#define         all(a)              a.begin(),a.end()
#define         rev(a)              reverse(all(a))
#define         min3(a, b, c)       min(a, min(b, c))
#define         max3(a, b, c)       max(a, max(b, c))
#define         ft                  first
#define         sd                  second

#define         loop(i, s, l, j)    for(int i = s; i < l; i += j)
#define         rloop(i, s, l, j)   for(int i = s; i >= l; i -= j)
#define         rep(i, n)           loop(i,0,n,1)
#define         rrep(i, n)          rloop(i,n-1,0,1) 

#define fastio() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)

#define mod 1000000007
#define inf 10000000
#define limit 2000006


void solve(int test_case)
{
    int k;
    cin >> k;
    str tmp = "ACL";
    str ans = "";
    rep(i,k)
        cout << tmp;
    cout << '\n';
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    fastio();
    int q = 1;
    //cin >> q;
    rep(i,q)
        solve(i+1);
}


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

int main(){
  int n,m;
  cin>>n>>m;
  vector<set<int>> edge(n);
  for(int i=0;i<m;i++){
    int b,c;
    cin>>b>>c;
    edge.at(b-1).insert(c-1);
    edge.at(c-1).insert(b-1);
  }
  int ans=0;
  
    vector<int> a(n-1);
    for(int i=0;i<n-1;i++){
      a.at(i)=i+1;
    }
    do{
        vector<int> e(n);
        bool cur=true;
        for(int i=0;i<n-1;i++){
            e.at(i+1)=a.at(i);
            if(!edge.at(e.at(i+1)).count(e.at(i))){
                cur=false;
            }
        }
        if(cur){
            ans++;
        }
    }while(next_permutation(a.begin(),a.end()));
  cout<<ans<<endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	a := nextInt()
	b := nextInt()
	c := nextInt()

	// a<=b<=c にする
	if a > b {
		a, b = b, a
	}
	if b > c {
		b, c = c, b
	}
	if a > b {
		a, b = b, a
	}

	cnt := 0
	for i := 0; i < 50; i++ {
		if a < c && b < c {
			a++
			b++
			cnt++
		}
	}

	for i := 0; i < 50; i++ {
		if a < b {
			a += 2
			cnt++
			if a > b {
				cnt++
			}
		}
	}

	fmt.Println(cnt)

}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // Default=64
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


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

int main() {
  int H,W;
  while(cin >>H>>W){
  if((H==0)&(W==0)){
    return 0;
  }
  for(int j=0;j<H;j++){
  for(int i=0;i<W;i++){
    cout <<"#";
  }
  cout <<endl;
  }
    cout <<endl;
  }
  
	return 0;
}




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

int n, a[4010][20] = {0};
string s;
map<char, int> m;
long long ans = 0;
int main() {
    cin >> n >> s;
    m['R'] = 1;
    m['G'] = 2;
    m['B'] = 3;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= 3; j++) a[i][j] = a[i - 1][j];
        a[i][m[s[i - 1]]]++;
    }
    for(int i = 2; i < n; i++) {
        for(int j = 1; j < i; j++) {
            if(m[s[i]] == m[s[j]]) continue;
            int c = 6 - m[s[i]] - m[s[j]];
            ans += a[j][c];
            if(2 * j - i > -1 && m[s[2 * j - i]] == c) ans--;
        }
    }
    cout << ans;
}

Measured memory_bytes: 3872
h,w=gets.split.map(&:to_i)
c=[]
10.times do
  c << gets.split.map(&:to_i)
end
10.times do |k|
  10.times do |i|
    10.times do |j|
      if c[j][i]>c[k][i]+c[j][k]
        c[j][i]=c[k][i]+c[j][k]
      end
    end
  end
end
l=[0]*10
h.times do
  a=gets.split.map(&:to_i)
  a.each do |aa|
    next if aa==-1||aa==1
    l[aa]+=1
  end
end
ans=0
10.times do |i|
  ans+=l[i]*c[i][1]
end
puts ans


Measured memory_bytes: 2300
import           Control.Monad (replicateM)

main :: IO ()
main = do
  n <- readLn
  playlist <- replicateM n $ do
    [s, t] <- words <$> getLine
    pure (s, read t)
  x <- getLine
  print $ solve x playlist

solve :: String -> [(String, Int)] -> Int
solve x = sum . map snd . drop 1 . dropWhile (\(title, _) -> title /= x)


Measured memory_bytes: 1020
def gcd(a, b) :
    if b == 0 :
        return a
    ret = gcd(b, a % b)
    return ret

def main( ) :


    n = int(input())
    v = [int(i) for i in input().split()]
    
    l, r = [0], [0]
    for x in v :
        l.append(gcd(l[-1], x))
    l.append(0)
    for x in v[::-1] :
        r.append(gcd(r[-1], x))
    r = [0] + r[::-1]

    ans = 0
    for i in range(1, n+1) :
        ans = max(ans, gcd(l[i-1], r[i+1]))

    print(ans)
                 

main()


Measured memory_bytes: 14052
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * (n + 1)
bit = [0] * (n + 1)
for x, y in zip(h, a):
    a = x
    t = 0
    while a > 0:
        t = max(t, bit[a])
        a -= a & -a
    t += y
    dp[x] = t
    while x <= n:
        bit[x] = max(bit[x], t)
        x += x & -x
x = n
ans = 0
while x > 0:
    ans = max(ans, bit[x])
    x -= x & -x
print(ans)


Measured memory_bytes: 121424
import java.util.Scanner;

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

    long M = 1_000_000_007;
    int N = scanner.nextInt();
    int K = scanner.nextInt();
    long[][] dp = new long[N][K + 1];
    for (int i = 0; i < N; i++) {
      int a = scanner.nextInt();
      if (i == 0) for (int j = 0; j <= a; j++) dp[0][j] = 1;
      else {
        long sum = 0;
        for (int j = 0; j <= K; j++) {
          sum += dp[i - 1][j];
          if (j > a) sum -= dp[i - 1][j - a - 1];
          dp[i][j] = sum % M;
        }
      }
    }

    System.out.println(dp[N - 1][K]);
  }
}


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

int main(){
  int n, x, t;
  cin >> n >> x >> t;
  if (n % x == 0){
    cout << n / x * t << endl;
  } else{
    cout << ((n / x) + 1) * t << endl;
  }
  return 0;
}

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

int main(void){

    long long N;
    double maxDiviser;
    cin >> N;

    double sqrtN = sqrt((double)N);

    for(int i=(int)floor(sqrtN); i>0; i--){
        if(N%i==0){
            maxDiviser = (double)(N/(long long)i);
            break;
        }
    }

    int res = (int)floor(log10(maxDiviser)) + 1;

    cout << res << endl;

    return 0;
}

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

int main() {
  ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	ll k;
	cin>>s>>k;
	ll c=0,n=s.size();
	if(n==1) {
		c=k/2;
	}
	else {
		if(k==1) {
			for(int i=1;i<n;i++) {
				if(s[i]==s[i-1]) {
					c++;
				}
			}
			c*=k;
		}
		else if(n==3 && s[0]==s[1] && s[1]==s[2]) {
			c+=3*(k/2);
			if(k&1) {
				c++;
			}
		}
		else {
			
			ll c1=0,c2=0;
			string s2=s+s;
			for(int i=1;i<n;i++) {
				if(s2[i]==s2[i-1]) {
					c1++;
					if(s2[i-1]!='a' && s2[i+1]!='a') {
						s2[i]='a';
					}
					else if(s2[i-1]!='b' && s2[i+1]!='b') {
						s2[i]='b';
					}
					else {
						s2[i]='c';
					}
				}
			}
			for(int i=n;i<2*n;i++) {
				if(s2[i]==s2[i-1]) {
					c2++;
					if(s2[i-1]!='a' && s2[i+1]!='a') {
						s2[i]='a';
					}
					else if(s[i-1]!='b' && s[i+1]!='b') {
						s2[i]='b';
					}
					else {
						s2[i]='c';
					}
				}
			}
			if(s[0]==s[n-1]) {
				if(s2[2*n-1]!=s[n-1]) {
					c=(c1+c2)*(k/2);
					if(k&1) {
						c+=c1;
					}
				}
				else {
					c=c1;
					c+=(k-1)*c2;
				}
			}
			else {
				c=(c1+c2)*(k/2);
				if(k&1) {
					c+=c1;
				}
			}
//			if(n>2 && s[0]==s[1] && s[0]==s[n-1]) {
//				if(s[0]=='a') {
//					s[0]='b';
//				}
//				else {
//					s[0]='a';
//				}
//				c++;
//			}
//	//		cout<<c<<"\n";
//			for(ll i=1;i<n;i++) {
//				if(s[i]==s[i-1]) {
//					if(s[i-1]!='a' && s[(i+1)%n]!='a') {
//						s[i]='a';
//					}
//					else if(s[i-1]!='b' && s[(i+1)%n]!='b') {
//						s[i]='b';
//					}
//					else {
//						s[i]='c';
//					}
//					c++;
//				}
//			}
////		cout<<c<<"\n";
//			c*=k;
//			if(k>1 && s[0]==s[n-1]) {
//					c+=k-1;
//			}
		}
	}
	cout<<c<<"\n";
}

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

int main() {
  int64_t a,b,c;
  cin>>a>>b;
  if (a==1&&b==1) c=1;
  else if(a==1||b==1) c=a*b-2;
  else if(a==2||b==2) c=(a-2)*(b-2);
  else c=a*b-(a+b)*2+4;
  cout << c << endl;
}


Measured memory_bytes: 256
# coding: utf-8
N=int(input())
L=[[0 for i in range(10)] for j in range(10)]

for i in range(N):
    num=i+1
    s_num=str(num)
    t=int(s_num[0])
    b=int(s_num[-1])
    L[t][b]+=1

ans=0
for i in range(N):
    num=i+1
    s_num=str(num)
    t=int(s_num[0])
    b=int(s_num[-1])
    ans+=L[b][t]
    # print(num,ans,L[t][b],L[b][t])
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
using namespace std;
int rm,n,k;
long long ans;
int a[100010],b[100010];
int main()
{
	scanf("%d%d",&n,&k);
	k++;
	for(int i=1;i<=n;i++)scanf("%d%d",a+i,b+i);
	for(int i=30;i>=0;i--)
	{
		if((k>>i)&1)
		{
			rm^=(1<<i);
			long long res=0;
			for(int j=1;j<=n;j++)
			{
				if(a[j]&rm)continue;
				res+=b[j]; 
			}
			ans=max(ans,res);
		}
		rm^=(1<<i);
	}
	printf("%lld",ans);
	return 0;
} 

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

int main()
{
  int x, y, sum=0;
  cin >> x >> y;
  if(x==3){
    sum += 100000;
  }else if(x==2){
    sum += 200000;
  }else if(x==1){
    sum += 300000;
  }else{
    sum += 0;
  }

  if(y==3){
    sum += 100000;
  }else if(y==2){
    sum += 200000;
  }else if(y==1){
    sum += 300000;
  }else{
    sum += 0;
  }

  if(y==1 && x==1){
    sum += 400000;
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
const ll INF=1e15+7;
const ll N = 100001;
ll n,a,b,x[N],ans=0;

int main(){
	cin>>n>>a>>b;
	FOR(i,1,n+1){
		cin>>x[i];
	}
	FOR(i,2,n+1){
		ans+=min(a*(x[i]-x[i-1]),b);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#ifndef JHELPER1_COMMON_H
#define JHELPER1_COMMON_H

#include <algorithm>
#include <iostream>
#include <map>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

typedef long long ll;
using namespace std;

constexpr ll MOD = 1000 * 1000 * 1000 + 7;

// Returns x^y modulo MOD. O(log2(y)).
ll modPow(ll x, ll y) {
  ll res = 1, a = x;
  while (y > 0) {
    if ((y & 1) > 0) {
      res = (res * a) % MOD;
    }
    a = (a * a) % MOD;
    y >>= 1;
  }
  return res;
}

// Returns a^-1 module MOD.
ll inverse(ll a) {
  /*
   * Fermat's little theorem
   * http://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem
   *
   * <pre>
   * a^p = a (mod p)
   * a^(p-1) = 1 (mod p)
   * ..
   * 1/a = a^(p-2) (mod p)
   * </pre>
   */
  return modPow(a, MOD - 2);
}

#endif //JHELPER1_COMMON_H


class BMinorChange {
public:
  void solve(std::istream& in, std::ostream& out) {
    string S, T;
    in >> S;
    in >> T;
    ll cnt = 0;
    for (int i = 0; i < S.size(); ++i) {
      if (S[i] != T[i]) cnt++;
    }
    out << cnt << endl;
  }
};


int main() {
	BMinorChange solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <algorithm>

using namespace std;

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

    int Q;
    scanf("%d", &Q);

    bool rev = false;

    for(int i = 0; i < Q; i++){
        int t;
        scanf("%d", &t);

        if(t == 2){
            int f;
            scanf("%d", &f);
            string c;
            cin >> c;

            if(rev == false){
                if(f == 1){
                    s.insert(0, c);
                }else{
                    s.append(c);
                }
            }else{
                if(f == 2){
                    s.insert(0, c);
                }else{
                    s.append(c);
                }
            }
        }else{
            rev = !rev;
        }
    }

    if(rev == false){
        cout << s << "\n";
    }else{
        reverse(s.begin(), s.end());
        cout << s << "\n";
    }

    return 0;
}


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

int main() {
    int n, cnt = 0;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i < n - 1; i++) {
        if ((p[i - 1] > p[i] and p[i] > p[i + 1]) or
            (p[i - 1] < p[i] and p[i] < p[i + 1])) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3528
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int beg[1010];

int main() {
	int n,m;
	while(n=in(),m=in()){
		int i;
		for(i=0;i<n;i++)beg[i]=in();
		sort(beg,beg+n,greater<int>());
		int res=0;
		for(i=0;i<n;i++){
			if((i+1)%m==0)continue;
			res+=beg[i];
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define ll long long
#define vi vector<int>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int X, Y, Z, K;
vector<ll> A, B, C, AB, ABC;

void solve(){
    rep(i,X){
        rep(j,Y)
            AB.push_back(A[i]+B[j]);
    }

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

    rep(i, min(K, X * Y)){
        rep(j,Z)
            ABC.push_back(AB[i]+C[j]);
    }

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

    rep(i,K)
        cout << ABC[i] << endl;
}

int main(){
    cin >> X >> Y >> Z >> K;

    A.resize(X,0), B.resize(Y,0), C.resize(Z,0);

    rep(i,X) cin >> A[i];

    rep(i,Y) cin >> B[i];

    rep(i,Z) cin >> C[i];

    solve();
}


Measured memory_bytes: 43368
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
// typedef long  l;
typedef pair<int,int> P;
const ll INF=100000000000000001;
const double PI=3.141592653589;


int main(){
  double n; cin>>n;
  double l=n/1.08;
  double r=(n+1)/1.08;
  // cout<<l<<" "<<r<<endl;
  int nn=n;
  int cl=ceil(l);
  // cout<<nn<<" "<<cl<<endl;
  if(nn==cl*108/100){
    cout<<cl<<endl;
  }else{
    // cout<<ceil(l)<<endl;
    cout<<":("<<endl;
  }

  return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n;
void solve(){
	cin >> n;
	
	if(n%2==0) printf("0.500000000\n");
	else printf("%.10f\n", 0.5+0.5/n);
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

#define int int64_t

int MOD = 1000000007;

int minCost(int *A, int N, int *dp)
{
    if(N == 0)
        return 0;
    
    if(N == 1)
        return abs(A[1] - A[0]);

    if(dp[N] != -1)
        return dp[N];

    int option1 = minCost(A, N - 1, dp);
    int option2 = minCost(A, N - 2, dp);

    return dp[N] = min(option1 + abs(A[N]-A[N-1]), option2 + abs(A[N]-A[N-2]));
}

int32_t main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    int N;
    cin >> N;

    int *A = new int[N]();
    for(int i=0; i<N; i++)
        cin >> A[i];

    int *dp = new int[N]();
    for(int i=0; i<N; i++)
        dp[i] = -1;

    int ans = minCost(A, N - 1, dp);

    cout << ans;

    delete [] dp;
    delete [] A;

    return 0;
}


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

int main() {
   string N;
   cin >> N;
   ll num = 0;
   if(N == "0"){
       cout << "Yes" << endl;
       return 0;
   }
   for(int i = 0; i < N.size(); i++){
       num += N.at(i) - '0';
   }
    if(num % 9 == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3716
import fractions
N = int(input())
A = [int(i) for i in input().split()]
gcd_left = [0] * N
gcd_right = [0] * N
chk = 1
for i in range(N):
	if i == 0:
		chk = A[0]
	else:
		chk = fractions.gcd(chk,A[i])
	gcd_left[i] = chk
temp = 0
for i in range(N):
	num = N-1-i
	if i == 0 :
		temp = A[num]
	else:
		temp = fractions.gcd(temp,A[num])
	gcd_right[num] = temp
ans = 0
for i in range(N):
	if i == 0:
		ans = max(ans,gcd_right[1])
	elif i == N-1:
		ans = max(ans,gcd_left[N-2])
	else:
		ans = max(ans,fractions.gcd(gcd_left[i-1],gcd_right[i+1]))
print(ans)

Measured memory_bytes: 89580
import sys

d = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}

for s in sys.stdin:
    s = [d[c] for c in s.strip()] + [0]
    n = 0
    for i, x in enumerate(s[:-1]):
        if x >= s[i + 1]:
            n += x
        else:
            n -= x
    print(n)

Measured memory_bytes: 6720
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
ll pow_mod(ll fi,ll se,ll mod){
  if(se==0){
    return 1;
  }
  if(se%2){
    return pow_mod(fi,se-1,mod)*fi%mod;
  }
  ll t=pow_mod(fi,se/2,mod);
  return t*t%mod;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}

vector<pair<int,int>> Dir={{-1,0},{1,0},{0,1},{0,-1}};
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/


int main(){
  ll n;
  cin>>n;
  vec(w,n);
  ll sum=0;
  rep(i,n){
    cin>>w[i];
    sum+=w[i];
  }
  ll ans=LLONG_MAX;
  ll tmp=0;
  rep(i,n){
    tmp+=w[i];
    ans=min(ans,abs(sum-tmp*2));
  }
  op(ans);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main(){
  int N; cin>>N;
  vector<ll> A;
  rep(i,N){
    ll a;
    cin>>a;
    A.push_back(a);
  }
  sort(A.begin(),A.end());
  ll ans=A[N-1]-A[0];
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;
#define fori(i,a,b) for(int i=(a);i<(int)(b);i++)
#define repi(i,n) fori(i,0,n)
#define forr(i,a,b) for(int i=int(b-1);i>=int(a);i--)
#define repr(i,n) forr(i,0,n)
#define all(x) (x).begin(),(x).end()
#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define mp make_pair
#define pcnt __builtin_popcount
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
const ll MOD = 1000000007;

#define MAX 100010
ll x[MAX];
void solve(){
    ll n;cin>>n;
    repi(i,n)cin>>x[i];

    ll ans=1;
    ll cnt=0;
    repi(i,n){
        if(x[i]>2*cnt)cnt++;
        else (ans*=cnt+1)%=MOD;
    }
    repi(i,cnt)(ans*=i+1)%=MOD;
    cout<<ans<<endl;
}

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


Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<algorithm>
#include<set>

using namespace std;
int main()
{

    int n;
    cin >> n;

    int d[100];

    for (int i=0;i<n;i++){
        cin >> d[i];
    }

    set<int> v;
    for (int i=0;i<n;i++){
        v.insert(d[i]);
    }

    cout << v.size();

    return 0;

}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

typedef pair<int, int> pii;

int encode(int *tile) {
	int res = tile[0];
	
	FOR(i, 1, 8) {
		res <<= 3;
		res |= tile[i];
	}
	return res;
}

void decode(int x, int *tile) {
	for (int i = 7; i >= 0; i--) {
		tile[i] = x & 7;
		x >>= 3;
	}
}

int main() {
	map<int, int> m;
	int tile[8];
	
	REP(i, 8) tile[i] = i;
	
	queue<pii> que;
	que.push(pii(encode(tile), 0));
	while (!que.empty()) {
		int now = que.front().first;
		int t = que.front().second;
		que.pop();
		
		if (m.find(now) != m.end()) continue;
		
		m[now] = t;
		decode(now, tile);
		
		int x, y;
		REP(i, 8) if (tile[i] == 0) {
			x = i % 4;
			y = i / 4;
			break;
		}
		
		int dx[4] = {1,0,-1,0};
		int dy[4] = {0,1,0,-1};
		REP(i, 4) {
			int nx = x + dx[i], ny = y + dy[i];
			if (!(nx >= 0 && nx < 4 && ny >= 0 && ny < 2)) continue;
			swap(tile[y * 4 + x], tile[ny * 4 + nx]);
			que.push(pii(encode(tile), t + 1));
			swap(tile[y * 4 + x], tile[ny * 4 + nx]);
		}
	}
	
	while (cin >> tile[0]) {
		FOR(i, 1, 8) cin >> tile[i];
		cout << m[encode(tile)] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 2168
use std::cmp::*;
use std::collections::*;
use std::io::*;
use std::str::*;
use std::string::*;
use std::f64::consts::PI;

struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }

    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }

    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let s: String = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        return s.parse::<T>().ok().unwrap();
    }

    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn prime_factorization(n: i64) -> HashMap<i64, i64> {
    let mut n = n;
    let mut res = HashMap::new();
    let mut i = 2;
    while i * i <= n {
        while n % i == 0 {
            n /= i;
            let count = res.entry(i).or_insert(0);
            *count += 1;
        }
        i += 1;
    }

    if n > 1 {
        res.insert(n, 1);
    }

    return res;
}

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let m1: i64 = sc.read();
    let d1: i64 = sc.read();
    let m2: i64 = sc.read();
    let d2: i64 = sc.read();

    println!("{}", if m2 > m1 { 1 } else { 0 });
}


Measured memory_bytes: 4352