akhauriyash/Code-Regression huggingface dataset:
n,k=map(int,input().split())
p=998244353
r=range
f=[1]
for i in r(k):f+=[-~i*f[i]%p]
a=0
for i in r(n-1,k):a+=f[k-1]*pow(f[i]*f[k-1-i],-1,p)
print(a%p)

Measured memory_bytes: 28728
/**
*    author:  Dooloper
*    created: 20.06.2020 20:53:55
**/

#include <bits/stdc++.h>

using namespace std;

long long gcd(int a, int b){
  if(a%b == 0){
    return (long long) b;
  }else{
    return (gcd(b,a%b));
  }
}

long long lcm(int a, int b){
  return a*b/gcd(a,b);
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int x;
  cin >> x;
  cout << lcm(x,360) / x  << endl;
  return 0;
}


Measured memory_bytes: 3632
def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()

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

using namespace std;

#define MAX_N 1000001
 
int n,k,sa[MAX_N];
int rank[MAX_N],tmp[MAX_N];
 
bool compare_sa(int i,int j){
    if(rank[i] != rank[j]){
        return rank[i] < rank[j];
    }else{
        int ri = i + k <= n ? rank[i+k] : -1;
        int rj = j + k <= n ? rank[j+k] : -1;
        return ri < rj;
    }
}

void construct_sa(string &S,int *sa){
    n = S.length();
   
    for(int i = 0 ; i <= n ; i++){
        sa[i] = i;
        rank[i] = i < n ? S[i] : -1;
    }
 
    for(k = 1 ; k <= n ; k *= 2){
        sort(sa,sa+n+1,compare_sa);
     
        tmp[sa[0]] = 0;
        for(int i = 1 ; i <= n ; i++){
            tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1],sa[i]) ? 1 : 0);
        }
        for(int i = 0 ; i <= n ; i++){
            rank[i] = tmp[i];
        }
    }
}
 
bool contain(string &S,int *sa,string &T){
    int a = 0, b = S.length();
    while(b - a > 1){
        int c = (a + b) / 2;
        if(S.compare(sa[c],T.length(),T) < 0) a = c;
        else b = c;
    }
    return S.compare(sa[b],T.length(),T) == 0;
}
 
int main(){
    ios::sync_with_stdio(0);
    
    int Q;
    string S,T;
    cin >> S >> Q;
    construct_sa(S,sa);
    while(Q--){
        cin >> T;
        if(S.size() < T.size()){ cout << '0' << endl; continue; }
        cout << (contain(S,sa,T) ? '1' : '0') << endl;
    }
    return 0;
}

Measured memory_bytes: 13920
#include <bits/stdc++.h>
using namespace std;
int main(){
int a;
  cin >>a;
  int b[110],ans=0,c=0;
  
  for (int i=0;i<a;i++)
    cin >>b[i];
  for (int i=0;i<a;i++){
    
  	if (b[i]>c) ans+=b[i]-c;
    c=b[i];
  }
  cout << ans <<endl;
}


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

typedef long long ll;
ll h, w, mn = 1e18;

ll f(ll p, ll q, ll r) {
	ll t1, t2;
	if (p >= q && p >= r) t1 = p;
	else if (q >= p && q >= r) t1 = q;
	else t1 = r;
	if (p <= q && p <= r) t2 = p;
	else if (q <= p && q <= r) t2 = q;
	else t2 = r;
	return t1 - t2;
}

int main()
{
	ll i;
	cin >> h >> w;
	for (i = 1; i < h; i++) {
		if (i < h / 2) {
			mn = min(mn, f(w * i, w / 2 * (h - i), (w + 1) / 2 * (h - i)));
			mn = min(mn, f(w * i, (h - i) / 2 * w, (h - i + 1) / 2 * w));
		} else {
			mn = min(mn, f(w * (h - i), w / 2 * i, (w + 1) / 2 * i));
			mn = min(mn, f(w * (h - i), i / 2 * w, (i + 1) / 2 * w));
		}
	}
	for (i = 1; i < w; i++) {
		if (i < w / 2) {
			mn = min(mn, f(h * i, h / 2 * (w - i), (h + 1) / 2 * (w - i)));
			mn = min(mn, f(h * i, (w - i) / 2 * h, (w - i + 1) / 2 * h));
		} else {
			mn = min(mn, f(h * (w - i), h / 2 * i, (h + 1) / 2 * i));
			mn = min(mn, f(h * (w - i), i / 2 * h, (i + 1) / 2 * h));
		}
	}
    cout << mn << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int main()
{
	int l,a,b,c,d;
	cin >> l >> a >> b >> c >> d;
	int x,y;
	if(a%c==0)x=a/c;
	else x=a/c+1;
	if(b%d==0)y=b/d;
	else y=b/d+1;
	cout << l-max(x,y) << "\n";
	return 0;
}

Measured memory_bytes: 1164
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <map>
#include <queue>
#include <set>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

const int MAX_K = 100010;
int N, K;
vector<int> A;

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

  bool dp[MAX_K];
  int a;

  for (int i = 0; i < N; ++i) {
    cin >> a;
    A.push_back(a);
  }

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

  memset(dp, false, sizeof(dp));
  dp[0] = false;

  for (int k = 1; k <= K; ++k) {
    for (int i = 0; i < N && !dp[k]; ++i) {
      int a = A[i];
      int bk = k - a;

      if (bk < 0) break;

      dp[k] = !dp[bk];
    }
  }

  if (dp[K]) {
    cout << "First" << endl;
  } else {
    cout << "Second" << endl;
  }

  return 0;
}


Measured memory_bytes: 384
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());
		
		int []p = new int [n];
		
		for(int i = 0 ; i < n ;i++) {
			p[i] = Integer.parseInt(sc.next());
		}
		
		int cnt = 0;
		
		for(int i = 0 ; i < n-1 ;i++) {
			
			if(i+1 == n-1) {
				if(p[i] == i+1 || p[i+1] == i+2) {
					cnt++;
					int temp = p[i];
					p[i] = p[i+1];
					p[i+1] = temp;
				} 
			}
			else if(p[i] != i+1) {
				continue;
			}
			
			else {
				cnt++;
				int temp = p[i];
				p[i] = p[i+1];
				p[i+1] = temp;
			}
		}
		System.out.println(cnt);

	}

}


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

int main() {
  double x1,y1,r1,x2,y2,r2;
  cin>>x1>>y1>>r1>>x2>>y2>>r2;
  double d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  if(r1>r2)swap(r1,r2);
  int a=2;
  if(d>r1+r2)a=4;
  if(d==r1+r2)a=3;
  if(d==r2-r1)a=1;
  if(d+r1<r2)a=0;
  cout<<a<<endl;
  return 0;
}


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

int N, D;
int x[10][10];

bool is_square(int i, int j) {
    int dist = 0;
    for (int k = 0; k < D; ++k) {
        dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
    }

    for (int k = 1; k < 150; ++k) {
        if ((k * k) == dist) {
            return true;
        }
    }

    return false;
}

int count() {
    int cnt = 0;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (is_square(i, j)) {
                ++cnt;
            }
        }
    }

    return cnt;
}

int main() {
    std::cin >> N >> D;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < D; ++j) {
            std::cin >> x[i][j];
        }
    }

    std::cout << count() << std::endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

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

		int N = sc.nextInt();
		int X = sc.nextInt();
		
		long[] map = new long[N+1];
		map[N] = X;
		for (int i = 0; i < N; i++) {
			map[i] = sc.nextLong();
		}
		
		Arrays.sort(map);
		
		long[] sa = new long[N];
		for (int i = 1; i <= N; i++) {
			sa[i-1] = map[i] - map[i-1];
		}
		
		long ans = sa[0];
		for (int i = 1; i < N; i++) {
			ans = gcd(ans, sa[i]);
			if(ans == 1) {
				break;
			}
		}
		
		System.out.println(ans);
	}
	
	static long gcd (long a, long b) {
		long temp;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return b;
	}

}

Measured memory_bytes: 50544
from sys import stdin, stdout
from itertools import accumulate
from bisect import bisect

input = lambda: stdin.readline()

def main():
    N, X = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    a = list(accumulate(A))
    n = bisect(a, X)
    if n == N and a[n-1] != X:
        print(n - 1)
    else:
        print(n)

main()


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<functional>
#include<vector>
#include<map>
#include<string>
#include<set>
#include<unordered_map>
#include<math.h>
#include<stack>
#include<deque>
using namespace std;

signed main() {
	int n; cin >> n;
	unordered_map<int, int>U;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		U[a]++;
	}
	int ans = 0;
	for (auto i : U) {
		if (i.second & 1) {
			ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4388
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#define INF 1<<10
using namespace std;

int n,m;
int dp[1<<12][1<<12];
int data[150];
vector<int> dif;

int memo(int used,int yn){
	if(dp[used][yn]!=INF)return dp[used][yn];
	int cnt=0;
	for(int i=0;i<n;i++){
		if((used&data[i])==yn)cnt++;
	}
	if(cnt<=1)return dp[used][yn]=0;
	int res=INF;
	for(int i=0;i<m;i++){
		if(used>>i & 1)continue;
		res=min(res,max(memo(used|(1<<i),yn),memo(used|(1<<i),yn|(1<<i))));
	}
	return dp[used][yn]=(res+1);
}

int main(void){
	while(1){
		scanf("%d%d",&m,&n);
		if(n+m==0)break;
		memset(data,0,sizeof(data));
		for(int i=0;i<n;i++){
			string str;
			cin >> str;
			for(int j=0;j<m;j++){
				if(str[j]=='1')data[i]+=(1<<j);
			}
		}
		for(int i=0;i<(1<<m);i++){
			for(int j=0;j<(1<<m);j++){
				dp[i][j]=INF;
			}
		}
		printf("%d\n",memo(0,0));
	}
	return 0;
}

Measured memory_bytes: 33488
x, y, a, b, c = map(int, input().split())
pa = sorted(list(map(int, input().split())), reverse=True)
pb = sorted(list(map(int, input().split())), reverse=True)
pc = sorted(list(map(int, input().split())), reverse=True)
ans = sorted(pa[:x] + pb[:y])
for i in range(min(len(ans), len(pc))):
    if pc[i] > ans[i]:
        ans[i] = pc[i]
    else:
        break
print(sum(ans))

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

using namespace std;

int main() {
    int n, k;
    string s;
    cin >> n >> s >> k;
    for (int i = 0; i < n; ++i) {
        if (s[i] != s[k - 1]) s[i] = '*';
    }
    cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, D, P=0, Ans=0;
    cin >> N >> D;
    
    vector<vector<int>> vec(N,vector<int>(D));
    
    for(int i=0 ; i < N ; ++i){
        for(int j=0 ; j < D ; ++j){
            cin >> vec.at(i).at(j);
        }
    }
    
    for(int i=0; i < N; ++i){
        for(int j=i+1; j < N; ++j){
            P=0;
            for(int k=0; k < D; ++k){
                P +=(vec.at(i).at(k) - vec.at(j).at(k)) * (vec.at(i).at(k) - vec.at(j).at(k));  
            }
            for(int l=1;l<130;++l){
                if(l*l==P){
                    Ans+=1;
                    break;
                }
            }
            
        }
    }
    
    cout << Ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
using namespace std; 
typedef long long ll;
ll prime[1000001];
ll length = 0;
void insert(ll p) { prime[length] = p; length++; return; }
int main() {
	insert(2);
	for (ll i = 3; i < 1000000; i += 2) {
		for (ll j = 0; j < length; j++)
			if (i%prime[j] == 0)goto cont;
			else if (prime[j] > sqrt(i))break;
			insert(i);
		cont:;
	}
	ll a, b;
	while (cin >> a >> b){
		if (!a && !b)return 0;
		ll am, bm, ac = 0, bc = 0;
		int i = 0;
		while (prime[i] <= a){
			if (a%prime[i] == 0) {
				am = prime[i];
				ac += prime[i];
				while (a%prime[i] == 0)a /= prime[i];
				if (a == 1)break;
			}
			i++;
		}
		ac -= am; am -= ac;
		i = 0;
		while (prime[i] <= b) {
			if (b%prime[i] == 0) {
				bm = prime[i];
				bc += prime[i];
				while (b%prime[i] == 0)b /= prime[i];
				if (b == 1)break;
			}
			i++;
		}
		bc -= bm; bm -= bc;
		if (am > bm)cout << "a\n";
		else cout << "b\n";
	}
}

Measured memory_bytes: 3652
#include <iostream>
using namespace std;
int main(){
	int S, h, m, s;
	cin >> S;
	h = S / 3600;
	m = S % 3600 / 60;
	s = S % 3600 % 60;
	cout << h << ":" << m << ":" << s << endl;
	return 0;
}

Measured memory_bytes: 1168
fun main(arr: Array<String>) {
    val n = readLine()!!.toLong()
    var ans = n - 1
    for(i in (2..n)) {
        if(i*i>n) {
            break
        }
        if(n%i==0L) {
            ans = i + (n/i) - 2
        }
    }
    println(ans)
}


Measured memory_bytes: 34544
#include<bits/stdc++.h>
using namespace std;
#define M 1001
int main(){
  int n,m,a,p,q,h,max=0,b[M][3]={};
  while(1){
    cin>>n>>m>>a;
    if(n==0 && m==0 && a==0)break;
    for(int i=0;i<m;i++){
      cin>>h>>p>>q;
      b[i][0]=h;
      b[i][1]=p;
      b[i][2]=q;
      if(max<h)max=h;
    }
    
    for(int j=max;j>=0;j--)
      for(int i=0;i<m;i++)
	if(b[i][0]==j)
	  if(b[i][1]==a)a=b[i][2];
	  else if(b[i][2]==a)a=b[i][1];
      
    cout<<a<<endl;
  }
  return 0;
}

Measured memory_bytes: 3120
import numpy as np
N=int(input())
T,A=map(int, input().split())
H=list(map(int, input().split()))

temp_dif = np.zeros(N)
for i in range(N):
  temp_dif[i] = abs ( (T - H[i] * 0.006) - A )
ind=np.where(temp_dif==min(temp_dif))
print(ind[0][0]+1)

Measured memory_bytes: 12424
from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))


Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#define _USE_MATH_DEFINES
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { -1, 0, 1,0 };
const ll INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
double mysqrt(double x) {
	double l = 0, r = x;
	for (int i = 0; i < 64; ++i) {
		double m = (l + r) / 2.0;
		if (m*m < x)l = m;
		else r = m;
	}
	return l;
}
///////////////////////////////////////

int main() {
	int n; cin >> n;
	int d[310][310];
	bool d_n[310][310];
	memset(d_n, false, sizeof(d_n));
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> d[i][j];
		}
	}
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (d[i][j] > d[i][k] + d[k][j]) {
					cout << -1 << endl;
					return 0;
				}
				if (d[i][j] == d[i][k] + d[k][j] && d[i][k] > 0 && d[k][j] > 0) {
					d_n[i][j] = true;
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (d_n[i][j] == false) {
				ans += d[i][j];
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 768
function main()
  
  N = parse(Int,readline())
  A = map(x -> parse(Int,x), split(readline()))
  B = map(x -> parse(Int,x), split(readline()))
  
  ans = 0

  for i in 1:N
    ans += min(A[i], B[i])
    B[i] -= min(A[i], B[i])
    ans += min(A[i+1], B[i])
    A[i+1] -= min(A[i+1], B[i])
  end
  
  println(ans)
  
end

main()

Measured memory_bytes: 166340
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long int ll;
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
	return a*b/gcd(a,b);
}
ll n,m,arr[100006];
int main()
{
	ios;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		cin>>arr[i];
	}
	ll now=1;
	for(int i=1;i<=n;++i)
	{
		now=lcm(now,arr[i]/2);
		if(now>m)break;
	}
	if(now>m){cout<<0<<'\n';return 0;}
	int flag=1;
	for(int i=1;i<=n;++i)
	{
		int temp=now*2/arr[i];
		if(temp%2==0){flag=0;break;}
	}
	if(flag==0){cout<<0<<'\n';return 0;}
	else
	{
		int num=m/now;
		if(num&1){cout<<num/2+1<<'\n';}
		else cout<<num/2<<'\n';
	}
}

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

int main() {
    int n;
    vector<int> l;
    int i, j, k;
    int a, b ,c;
    int sum = 0;
    int tmp;

    cin >> n;
    for(i = 0; i < n; i++) {
        cin >> tmp;
        l.push_back(tmp);
    }
    sort(l.begin(), l.end());

    for(i = 0; i < (n - 2); i++) {
        a = l[i];
        for(j = i + 1; j < (n - 1); j++) {
            b = l[j];
            for( k = j + 1; k < (n - 0); k++) {
                c = l[k];
                if((a < b + c) && (b < a + c) && (c < a + b)) {
                    sum += 1;
                } else {
                    break;
                }
            }
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;

static const int tx[] = {+0,+1,+0,-1};
static const int ty[] = {-1,+0,+1,+0};

ll GCD(ll a ,ll b){
  return b > 0 ? GCD(b,a%b) : a;
}

ll LCM(ll a ,ll b){
  return a / GCD(a,b) * b;
}

class Student {
public:
  ll distance;
  ll velocity;
  Student(ll distance,ll velocity) 
    : distance(distance), velocity(velocity) {}
};

int main(){
  int total_students;
  while(~scanf("%d",&total_students)){
    if(total_students == 0) break;

    vector<Student> students;
    for(int student_i = 0; student_i < total_students; student_i++){
      ll distance;
      ll velocity;
      scanf("%lld %lld",&distance,&velocity);
      int gcd = GCD(distance,velocity);
      students.push_back(Student(distance / gcd,velocity / gcd));
    }

    ll reference_distance = students[0].distance;
    for(int student_i = 0; student_i < total_students; student_i++){
      reference_distance = LCM(reference_distance,
                               students[student_i].distance);

    }

    for(int student_i = 0; student_i < total_students; student_i++){
      students[student_i].velocity
        = students[student_i].velocity * (reference_distance / students[student_i].distance);
    }

    ll gcd = students[0].velocity;
    for(int student_i = 0; student_i < total_students; student_i++){
      gcd = GCD(gcd,students[student_i].velocity);
    }
        
    for(int student_i = 0; student_i < total_students; student_i++){
      printf("%lld\n",students[student_i].velocity / gcd);
    }
  }
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

// const int offset = 30;
// const int SIZE = 2 * offset + 1;
const int offset = 100;
const int SIZE = 2 * offset + 1;
const int INF = 1e9;
int dx[] = {1, 0, -1, 0, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1};

bool inside(int x, int y) {
    return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
}

int bfs(int t, int n) {
    set<P> blocks;
    rep(i, n) {
        int x, y;
        cin >> x >> y;
        blocks.insert(P(x + offset, y + offset));
    }

    int sx, sy;
    cin >> sx >> sy;
    sx += offset;
    sy += offset;

    queue<P> que;
    que.push(P(sx, sy));
    VV d(SIZE, V(SIZE, INF));
    d[sx][sy] = 0;

    while (!que.empty()) {
        P p = que.front(); que.pop();
        rep(k, 6) {
            int nx = p.first + dx[k], ny = p.second + dy[k];
            if (inside(nx, ny) && blocks.count(P(nx, ny)) == 0 && d[nx][ny] == INF) {
                que.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }

    int ans = 0;
    rep(i, SIZE) {
        rep(j, SIZE) {
            if (d[i][j] <= t) {
                ans++;
            }
        }
    }

    return ans;
}

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

    int t, n;
    while (cin >> t >> n, t) {
        cout << bfs(t, n) << endl;
    }
}

Measured memory_bytes: 3296
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long n,a,b,i,j,ans,p[100005];
int main()
{
	cin>>n>>a>>b;
	for (i=1;i<=n;i++) cin>>p[i];
	for (i=2;i<=n;i++) ans+=min(b,a*(p[i]-p[i-1]));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) > (b) ? (b) : (a))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define MOD (ll)1000000007 //10^9 + 7
#define endl printf("\n")
typedef long long ll;
#define MAX_N (1 << 17)

int
main(int argc, char *argv[])
{
  ll x, y;
  scanf("%lld %lld", &x, &y);

  if (abs(x - y) <= 1) printf("Brown\n");
  else printf("Alice\n");

  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

  
int main(){
  int x;
  cin>>x;
  int ans=1;
  for(int i=2;i<=x;i++){
    for(int j=2;j<=9;j++){
      int q=(int)pow(i,j);
      if(q<=x) ans=max(ans,q);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
X,Y,Z,K=map(int,input().split())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
C=[int(i) for i in input().split()]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
SUM=[]
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)<=K:
        SUM.append(A[i]+B[j]+C[k])
      else:
        break
SUM.sort(reverse=True)
for i in range(K):
  print(SUM[i])

Measured memory_bytes: 8768
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<set>
#include<tuple>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
char che[4] = { 'A','C','G','T' };
int main(void) {
	string s;
	cin >> s;
	ll ans = -inf;
	ll count = 0;
	for (int i = 0; i < s.size(); i++) {
		bool ok = false;
		for (int j = 0; j < 4; j++) {
			if (s[i] == che[j]) {
				ok = true;
			}
		}
		if (ok) {
			count++;
		}
		ans = max(ans, count);
		if (!ok) {
			count = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3616
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
	"strings"

)


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

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func(int)
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	var wordsCnt int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx = (idx + 1) % wordsCnt
		return cur
	}
	this.initWordIdx = func(wc int) {
		idx = 0
		wordsCnt = wc
	}
	return &this
}

func (me *ReaderEx) Scan(doSplit bool) (isScanned bool) {
	isScanned = me.baseScanner.Scan()
	if doSplit {
		me.words = strings.Fields(me.baseScanner.Text())
	} else {
		me.words = []string{me.baseScanner.Text()}
	}
	me.initWordIdx(len(me.words))
	return
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []*factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, &fa)
		}
	}
	if n > 1 {
		facts = append(facts, &factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func b2i(b bool) (i int) {
	if b {
		i = 1
	} else {
		i = 0
	}
	return
}

func solve(stdin io.Reader, stdout io.Writer) {

	r := NewScannerEx(stdin)
	r.Scan(true)
	r.Scan(true)
	a := r.nextStringArray().toInts()

	p := 1
	for i:=range a{
		if p == a[i]{
			p++
		}
	}

	ans :=-1
	if p>1 {
		ans = len(a)-(p-1)
	}
	fmt.Fprintln(stdout, ans)
}


Measured memory_bytes: 9344
#include<bits/stdc++.h>
using namespace std;
#define INS(x) x.begin(),x.end()
    
int a[4][4];
int pd[4][4];
    
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            cin>>a[i][j];
    
    int n;
    cin>>n;
    while (n--)
    {
        int b;
        cin>>b;

        for (int i=1;i<=3;i++)
            for (int j=1;j<=3;j++)
                if (a[i][j]==b) pd[i][j]=1;
    }

    int p=0;
    for (int i=1;i<=3;i++)
    {
        if (pd[i][1]&&pd[i][2]&&pd[i][3]) p=1;
        if (pd[1][i]&&pd[2][i]&&pd[3][i]) p=1;
    }


    if (pd[1][1]&&pd[2][2]&&pd[3][3]) p=1;
    if (pd[1][3]&&pd[2][2]&&pd[3][1]) p=1;

    if (p) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

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

using namespace std;

const int maxn = 200010;
typedef pair<int,int> pi;

int n, a[maxn];

vector<pi> cal(int lasta, int lastb, int s, int _) {
	vector<pi> ret;
	// 先判断是否可能不增加
	// x >= lasta, s - x <= lastb
	// x >= lasta, x >= s - lastb;
	if (max(lasta, s - lastb) <= s) ret.push_back(make_pair(_, max(lasta, s - lastb)));
	// 再判断只增加一项，x 的最小值（显然可以只增加一项）
	ret.push_back(pi(_ + 1, max(0, min(lasta, s - lastb))));
	ret.push_back(pi(_ + 2, 0));
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	pi mn0(0, 0), mn1(0, 0), mn2(0, 0);
	for (int i = 1; i <= n+1; i++) {
		vector<pi> v0 = cal(mn0.second, a[i-1] - mn0.second, a[i], mn0.first);
		vector<pi> v1 = cal(mn1.second, a[i-1] - mn1.second, a[i], mn1.first);
		vector<pi> v2 = cal(mn2.second, a[i-1] - mn2.second, a[i], mn2.first);
		vector<pi> ch;
		ch.insert(ch.end(), v0.begin(), v0.end());
		ch.insert(ch.end(), v1.begin(), v1.end());
		ch.insert(ch.end(), v2.begin(), v2.end());
		sort(ch.begin(), ch.end());
		int mn = ch[0].first;
		pi nmn0(0x3f3f3f3f, 0), nmn1(0x3f3f3f3f, 0), nmn2(0x3f3f3f3f, 0);
		for (int i = 0; i < ch.size(); i++) {
			if (ch[i].first == mn) nmn0 = min(nmn0, ch[i]);
			else if (ch[i].first == mn + 1) nmn1 = min(nmn1, ch[i]);
			else if (ch[i].first == mn + 2) nmn2 = min(nmn1, ch[i]);
		}
		mn0 = nmn0, mn1 = nmn1, mn2 = nmn2;
	}
	printf("%d\n", mn0.first);
	return 0;
}

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

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

const int N = int(5e5) + 2;
const int LG = 20;
const ll mod = 998244353;
const int INF = 2147483647;
const ll linf = 1e18;
const ld pi = acos(-1);
const ld EPS = 1e-10;

int n, pref[N], suff[N];
string s;
int main (){
    cin >> n >> s;
    for (int i = 1; i <= n; ++i){
        if (s[i - 1] == '.') pref[i] += 1;
        pref[i] = pref[i - 1] + pref[i];
    }
    for (int i = n; i >= 1; --i){
        if (s[i - 1] == '.') suff[i] += 1;
        suff[i] = suff[i + 1] + suff[i];
    }
    int ans = n;
    for (int i = 0; i <= n; ++i) ans = min(i - pref[i] + suff[i + 1], ans);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 2180
#include <iostream>
#include <vector>
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int a, b;
    cin >> a >> b;
    if(a > 12){
        cout << b << endl;
    }
    else if(a < 6){
        cout << 0 << endl;
    }
    else{
        cout << b / 2 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<vector>

using namespace std;

int x[20000],y[20000];
char dir[20000];
int p[20000];
vector<vector<int> >G;

int dst(int x1,int y1,int x2,int y2){
  return abs(x1-x2)+abs(y1-y2);
}

bool dfs(int v){
  for(auto e:G[v]){
    int sp=(dst(x[v],y[v],x[e],y[e])==2)?-1:1;
    if(p[e]==0){
      p[e]=sp*p[v];
      if(!dfs(e))return false;
    }else{
      if(p[e]*p[v]!=sp)return false;
    }
  }
  return true;
}

int main(){
  for(int n;cin>>n,n;){
    for(int i=0;i<n;i++){
      cin>>x[i]>>y[i]>>dir[i];
    }
    G=vector<vector<int> >(n);
    for(int i=0;i<n;i++){
      for(int j=i+1;j<n;j++){
	if(min({dst(x[i],y[i],x[j],y[j]),
		dst(x[i],y[i],x[j]+(dir[j]=='x'),y[j]+(dir[j]=='y')),
		dst(x[i]+(dir[i]=='x'),y[i]+(dir[i]=='y'),x[j],y[j]),
		dst(x[i]+(dir[i]=='x'),y[i]+(dir[i]=='y'),x[j]+(dir[j]=='x'),y[j]+(dir[j]=='y'))
		})==1){
	  G[i].push_back(j);
	  G[j].push_back(i);
	}
      }
    }
    fill(begin(p),end(p),0);
    bool f=false;
    for(int i=0;i<n;i++){
      if(p[i]==0){
	p[i]=1;
      }
      f|=!dfs(i);
    }
    cout<<(f?"No":"Yes")<<endl;
  }
}  
    

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

using namespace std;

int main()
{
    map<int,int>m;
    int c,t,N,T,a[101],idx;
    cin>>N>>T;
    for(int i=0;i<N;i++){
        cin>>c>>t;
        m[c]=t;
        a[i]=c;
    }
    sort(a,a+N);
    int chk=0;
    for(int i=0;i<N;i++){
            if(m[a[i]]<=T){
                idx=i;
                chk=1;
                break;
            }
        }
        if(chk==1)
        cout<<a[idx];
        else cout<<"TLE";
    return 0;
}


Measured memory_bytes: 3572
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;

int a;
string s;

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

	if (a >= 3200)cout << s << endl;
	else cout << "red" << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}



int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<std::string> S(N);
    map<string,ll> m;
    for(int i = 0 ; i < N ; i++){
        std::cin >> S[i];
        m[S[i]]++;
    }
    cout << "AC x " << m["AC"] << endl;
    cout << "WA x " << m["WA"] << endl;
    cout << "TLE x " << m["TLE"] << endl;
    cout << "RE x " << m["RE"] << endl;

    return 0;
}


Measured memory_bytes: 6452
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int a,b,k;
    vector<int> res;
    cin >> a >> b >> k;
    int m = min(a,b);
    for(int i=1;i<=m;i++){
        if(a%i==0&&b%i==0){
            res.push_back(i);
        }
    }
    reverse(res.begin(),res.end());
    cout << res[k-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/c++io.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <vector>
using namespace std;

int main()
{
int n,maxs=0,t=0,m,c,j=0,z=0;
cin>>n;
m=c=n;
for(int i=0;i<c;i++)
{
    j++;
      while(n%2==0)
   {
       t++;
       n/=2;
   }

   if(t>maxs)
    {
        maxs=t;

    }
n=m;
   n-=j;
   t=0;
}
cout<<pow(2.0,maxs)<<endl;
}


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

def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

import numpy as np
L = []
for n in range(3, 10):
    for i in range(3**n):
        i3 = Base_10_to_n(i, 3).zfill(n)
        num = ''
        for j in range(n):
            if i3[j] == '0':
                num += '3'
            elif i3[j] == '1':
                num += '5'
            elif i3[j] == '2':
                num += '7'
        if '3' in num and '5' in num and '7' in num:
            L.append(int(num))
L = np.array(L)
#print(L[L<=N])
print(np.count_nonzero(L[L<=N]))


Measured memory_bytes: 14600
#include <iostream>

int calcGcd(int m, int n){
    return n == 0 ? m : calcGcd(n, m%n);
}

inline int calcLcm(int m, int n, int gcd){
    return m / gcd * n;
}

int main(){
    int x, y;
	
    while(std::cin >> x >> y){
		int gcd, lcm;
        if(x > y) gcd = calcGcd(x, y);
        else gcd = calcGcd(y, x);
        lcm = calcLcm(x, y, gcd);
         
        std::cout << gcd << " " << lcm << std::endl;
    }
     
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iomanip>

#include <map>
#include <set>
#include <queue>
#include <stack>

#define ALL(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdbl vector<double>
#define vstr vector<string>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int colors[100001];
vint edge[100001];
int dp[100000][11];

int v[100001];
int d[100001];
int c[100001];

const int INF = 1e9;

void dfs(int vv,int depth,int c){
	dp[vv][depth] = c;
	if(depth == 0) return;
	for(int to : edge[vv]){
		if(dp[to][depth-1] == 0){
			dfs(to, depth-1, c);
		}
	}
	if(dp[vv][depth-1] == 0) dfs(vv,depth-1,c);
}

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

	int N,M;
	cin >> N >> M;
	fill(dp[0], dp[N],0);
	rep(i,M){
		int a,b;
		cin >> a >> b;
		a--;
		b--;

		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	int Q;
	cin >> Q;

	rep(i,Q){
		cin >> v[i] >> d[i] >> c[i];
		v[i]--;	
	}

	rrep(i,Q){
		if(dp[v[i]][d[i]] == 0) {			
			dfs(v[i], d[i], c[i]);
		}
	}

	rep(i,N){
		cout << dp[i][0] << endl;
	}

}

Measured memory_bytes: 12408
#include <stdio.h>

int main(void){
  int sx,sy,tx,ty;
  scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
  int i;
  for(i=1;i<=tx-sx;i++){
    printf("R");
  }
  for(i=1;i<=ty-sy;i++){
    printf("U");
  }
  for(i=1;i<=tx-sx;i++){
    printf("L");
  }
  for(i=1;i<=ty-sy;i++){
    printf("D");
  }
  printf("DR");
  for(i=1;i<=tx-sx;i++){
    printf("R");
  }
  for(i=1;i<=ty-sy;i++){
    printf("U");
  }
  printf("ULUL");
  for(i=1;i<=tx-sx;i++){
    printf("L");
  }
  for(i=1;i<=ty-sy;i++){
    printf("D");
  }
  printf("DR\n");

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define DEBUG

#define _GLIBCXX_DEBUG
#ifdef DEBUG
#define s(...) show(__VA_ARGS__);
#define sl(...) show(__VA_ARGS__);cout<<endl;
#else
#define s(...)
#define sl(...)
#endif
void show() {}
template <class Head,class... Args>void show(Head t,Args... args){std::cout<<t<<" ";show(args...);}
#define REP(i, n) for(ll i = 1; i <= n; i++)
#define REPR(i, n) for(ll i = n; i >= 1; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define INF 1e9+123
#define VEC(type,A,N) vector<type> A(N+10)
#define VECi(type,A,N,i) vector<type> A(N+10,i)
#define VEC2(type,A,N,M) vector<vector<type>> A(N+10,vector<type>(M+10))
#define ALL(v) v.begin()+1, v.end()-9

int main(){
    ll N;
    cin>>N;
    
    
    VEC(ll,A,N);
    VEC(ll,B,N);
    REPR(i,N){
        cin>>A[i]>>B[i];
    }
    
    ll cnt=0;
    REP(i,N){
        A[i]+=cnt;
        if(A[i]%B[i]!=0){
            cnt+=B[i]-(A[i]%B[i]);
            A[i]+=B[i]-(A[i]%B[i]);
        }
    }
    cout<<cnt<<endl;
    //sort(ALL(C),[](auto& a, auto& b) {return a[2] < b[2];});
    //if(equal(D.begin(), D.end()-1, K.begin()))cout<<"Yes";else cout<<"No";
    return 0;
}


Measured memory_bytes: 1792
string = input()
k = int(input())
ans = list(string)

alpha = "abcdefghijklmnopqrstuvwxyz"
alpha_to_num = {}
for i in range(26):
    alpha_to_num[alpha[i]] = i
    
for i, s in enumerate(ans):
    if s == "a":
        continue
    pos = alpha_to_num[s]
    kk = 26 - pos
    if kk > k:
        continue
    k -= kk
    ans[i] = "a"
    
pos = alpha_to_num[ans[-1]]
new_pos = (k + pos) % 26
ans[-1] = alpha[new_pos]
print("".join(ans))

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

int main() {
    
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    
    int dp[n];
    dp[0]=0;
    for(int i=1;i<n;i++){
        int temp=INT_MAX;
        for(int j=1;(j<=k&&(i-j)>=0);j++){
            temp=min(temp,dp[i-j]+abs(arr[i]-arr[i-j]));
        }
        dp[i]=temp;
    }
    //for(int i=0;i<n;i++)cout<<dp[i]<<" ";
    cout<<dp[n-1]<<endl;
    }

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

using namespace std;
int main(){
	int h;
	int n;
	cin>>h>>n;
	vector<int> a(n+1);
	int s=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s+=a[i];
	}
	cout<<(s>=h?"Yes":"No")<<endl;
	return 0;
}


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

int main()
{
	int N, K;
	string rslt;
	std::cin >> N >> K;
	if (N % 2 == 1) N += 1;
	rslt = ((N / 2) >= K) ? "YES" : "NO";
	std::cout << rslt;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;

int main() {
	int N, A, B, C, D;
	string s;
	cin >> N >> A >> B >> C >> D;
	cin >> s;
	A--; B--; C--; D--;
	bool ok = true;
	if (C > D) {
		ok = false;
		while (B <= D) {
			if (B + 1 >= s.size())break;
			if (s[B - 1] == '.' && s[B] == '.' && s[B + 1] == '.') {
				ok = true;
				break;
			}
			B++;
		}
		while (A < C) {
			if (A + 1 < s.size()) {
				if (s[A + 1] == '#') {
					if (A + 2 < s.size()) {
						if (s[A + 2] == '#') {
							ok = false;
						}
						else {
							A += 2;
						}
					}
					else {
						ok = false;
					}
				}
				else {
					A++;
				}
			}
			else {
				ok = false;
			}
			if (!ok)break;
		}
		while (B < D) {
			if (B + 1 < s.size()) {
				if (s[B + 1] == '#') {
					if (B + 2 < s.size()) {
						if (s[B + 2] == '#') {
							ok = false;
						}
						else {
							B += 2;
						}
					}
					else {
						ok = false;
					}
				}
				else {
					B++;
				}
			}
			else {
				ok = false;
			}
			if (!ok)break;
		}
	}
	//(D>C)
	else {
		ok = true;
		while (B < D) {
			if (B + 1 < s.size()) {
				if (s[B + 1] == '#') {
					if (B + 2 < s.size()) {
						if (s[B + 2] == '#') {
							ok = false;
						}
						else {
							B += 2;
						}
					}
					else {
						ok = false;
					}
				}
				else {
					B++;
				}
			}
			else {
				ok = false;
			}
			if (!ok)break;
		}
		while (A < C) {
			if (A + 1 < s.size()) {
				if (s[A + 1] == '#') {
					if (A + 2 < s.size()) {
						if (s[A + 2] == '#') {
							ok = false;
						}
						else {
							A += 2;
						}
					}
					else {
						ok = false;
					}
				}
				else {
					A++;
				}
			}
			else {
				ok = false;
			}
			if (!ok)break;
		}
	}
	cout << (ok ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 640
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C, X, Y = MAP()

ans = 0
if A + B > 2 * C:
	ans += 2 * C * min(X, Y)
	idx = (X, Y).index(max(X, Y))
	left = abs(X - Y)
	if 2 * C < (A, B)[idx]:  # C を購入
		ans += 2 * C * left
	else:
		ans += (A, B)[idx] * left
else:
	ans = A * X + B * Y
print(ans)


Measured memory_bytes: 5328
import math
import string
import collections
from collections import Counter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n, m = map(int, input().split())
if m <= 2*n:
    print(m//2)
else:
    print(n+math.ceil((m-2*n)//4))


Measured memory_bytes: 38768
#include <stdio.h>
   
int main(void){
   
  int H,W;
  register int i,s;
   
  while(1){
    scanf("%d %d",&H,&W);
    if((H == 0) & (W == 0)){
      break;
    }
    for(i = 0;i < H;i++){
      for(s = 0;s < W;s++){
        if( ( i % 2 ) == 1 ){
          if( ( ( s % 2 ) == 0 ) ){
            printf(".");
          }else{
            printf("#");
          }
        }else{
          if( ( ( s % 2 ) == 0 ) ){
            printf("#");
          }else{
            printf(".");
          }
        }
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
maze = [list(input())[: -1] for _ in range(H)]
#print(maze)
res = 0
d = [-1, 0, 1, 0]
for s in range(H * W):
  sy = s // W
  sx = s % W
  if maze[sy][sx] == "#": continue
  Q = dq([])
  Q.append(s)
  dist = [float("inf")] * (H * W)
  dist[s] = 0
  while len(Q):
    p = Q.popleft()
    py = p // W
    px = p % W
    for k in range(4):
      qy = py + d[k]
      qx = px + d[-1 - k]
      if 0 <= qy < H and (0 <= qx < W):
        if maze[qy][qx] == "#": continue
        if dist[qy * W + qx] > dist[p] + 1:
          Q.append(qy * W + qx)
          dist[qy * W + qx] = dist[p] + 1
  for x in dist:
    if x != float("inf"): res = max(res, x)
print(res)

Measured memory_bytes: 46940
#include <stdio.h>

int conv(char *s)
{
	int out;
	int p;
	

	out = 0;
	
	p = 0;
	
	if (s[p] == 'm'){
		p++;
		out += 1000;
	}
	if ('2' <= s[p] && s[p] <= '9' && s[p + 1] == 'm'){
		out += ((s[p] - '0') * 1000);
		p += 2;
	}
	
	if (s[p] == 'c'){
		p++;
		out += 100;
	}
	if ('2' <= s[p] && s[p] <= '9' && s[p + 1] == 'c'){
		out += ((s[p] - '0') * 100);
		p += 2;
	}
	
	if (s[p] == 'x'){
		p++;
		out += 10;
	}
	if ('2' <= s[p] && s[p] <= '9' && s[p + 1] == 'x'){
		out += ((s[p] - '0') * 10);
		p += 2;
	}

	if (s[p] == 'i'){
		out++;
	}
	if ('2' <= s[p] && s[p] <= '9' && s[p + 1] == 'i'){
		out += (s[p] - '0');
	}
	
//printf("<%d>\n", out);

	return (out);
}

	
	


int main(void)
{
	int n;
	char m1[10], m2[10];
	int result;
	int i;
	
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%s%s", m1, m2);
		
		result = conv(m1) + conv(m2);
		
		if (result >= 1000){
			if (result / 1000 >= 2){
				printf("%d", result / 1000);
			}
			printf("m");
		}
		result %= 1000;
		
		if (result >= 100){
			if (result / 100 >= 2){
				printf("%d", result / 100);
			}
			printf("c");
		}
		result %= 100;
		
		if (result >= 10){
			if (result / 10 >= 2){
				printf("%d", result / 10);
			}
			printf("x");
		}
		result %= 10;
		
		if (result > 0){
			if (result >= 2){
				printf("%d", result);
			}
			printf("i");
		}
		printf("\n");
		
	}
	
	return (0);
}

Measured memory_bytes: 604
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    if (a%2 == 1 && b%2 == 1){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long INF = (long)Math.pow(10, 9) + 7;
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextLong();
        }
        long sum = 0;
        for (int i = 0; i < a.length; i++) {
            sum += a[i];
        }
        long res = 0;
        for (int i = 0; i < a.length - 1; i++) {
            sum -= a[i];
            res += a[i] * (sum % INF);
            res %= INF;
        }
        System.out.println(res);
        sc.close();
    }
}

Measured memory_bytes: 61280