akhauriyash/Code-Regression huggingface dataset:
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define bged(v) (v).begin(),(v).end()
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
typedef long long ll;
const int Imx=2147483647;
const ll Lbig=2e18;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c==' '||c=='\n')c=_buff.get();return c;}
char s[2011],t[2011];
int n;
int diff[2011],dis[2011];
int ld[2011],rd[2011];
int main()
{
	scanf("%s",s);
	scanf("%s",t);
	n=strlen(s);
	
	bool ok=1;
	for(int i=0;i<n;i++)ok&=t[i]=='0';
	if(ok)
	{
		for(int i=0;i<n;i++)
		{
			if(s[i]=='1')
			{
				puts("-1");
				return 0;
			}
		}
		puts("0");
		return 0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			diff[i]+=s[(j-i+n)%n]!=t[j];
		}
	}
	for(int i=0;i<n;i++)
	{
		dis[i]=Imx;
		for(int j=0;j<n;j++)
		{
			dis[i]=min(dis[i],diff[(i+j)%n]+j);
		}
		for(int j=0;j<n;j++)
		{
			dis[i]=min(dis[i],diff[(i-j+n)%n]+j);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(s[i]=='0')continue;
		for(int j=0;j<n;j++)if(t[(i+j)%n]=='1')
		{
			rd[i]=j;
			break;
		}
		for(int j=0;j<n;j++)if(t[(i-j+n)%n]=='1')
		{
			ld[i]=j;
			break;
		}
	}
	int ans=Imx;
	for(int i=0;i<n;i++)
	{
		int mxr=0;
		for(int j=0;j<n;j++)
		{
			if(ld[j]<=i)continue;
			mxr=max(mxr,rd[j]+i);
		}
		ans=min(ans,i+mxr+dis[(-i+mxr+n)%n]);
	}
	for(int i=0;i<n;i++)
	{
		int mxl=0;
		for(int j=0;j<n;j++)
		{
			if(rd[j]<=i)continue;
			mxl=max(mxl,ld[j]+i);
		}
		ans=min(ans,i+mxl+dis[(i-mxl+n)%n]);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

int main(){
        string s;
        cin>>s;
        int gu=0, pa=0;
        int res=0;
        for(int i=0;i<(int)s.length();i++){
                if(s[i]=='g'){
                        if(pa+1<=gu){
                                pa++;
                                res++;
                        }
                        else{
                                gu++;
                        }
                }
                else{
                        if(pa+1<=gu){
                                pa++;
                        }
                        else{
                                res--;
                                gu++;
                        }
                }
        }
        cout<<res<<endl;
        return 0;
}


Measured memory_bytes: 512
n, m = map(int, input().split())
cs = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    cs[i][i] = 0
es = []
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    es.append((a, b, c))
    cs[a][b] = cs[b][a] = c
for k in range(n):
    for i in range(n):
        for j in range(n):
            cs[i][j] = min(cs[i][j], cs[i][k] + cs[k][j])
print(sum([1 for a, b, c in es if cs[a][b] != c]))

Measured memory_bytes: 3444
import fractions
from functools import reduce


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


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


N, X = (int(i) for i in input().split())
A = [int(i) for i in input().split()]


def aho(x):
  return x - X


B = list(map(aho, A))

C = gcd_list(B)

print(abs(C))

Measured memory_bytes: 16268
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

sys.setrecursionlimit(1000000)
# MOD = 10 ** 9 + 7
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

A, B, C, D = [int(x) for x in input().split()]


def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x


def lcm(x, y):
    return (x * y) // gcd(x, y)


def f(a, b, c):
    if a % c == 0:
        a1 = a // c
    else:
        a1 = a // c + 1
    b1 = b // c
    r = b1 - a1 + 1
    return r


# c = (B - A + 1) // C
# d = (B - A + 1) // D
# cd = (B - A + 1) // (C * D)

c = f(A, B, C)
d = f(A, B, D)
cd = f(A, B, lcm(C, D))

n = B - A + 1
print(n - c - d + cd)


Measured memory_bytes: 4020
#include <bits/stdc++.h>
#include <algorithm>  
#include <unordered_set>

#define ll long long

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll a;

	cin >> a;

	cout << a * a * a + a * a + a << endl;
	return 0;
}

Measured memory_bytes: 3604
s = input()
q = int(input())

pres = []
posts = []
mode = 0
for _ in range(q):
    query = input().split()
#     print(s, query, mode, pres, posts)
    if len(query) == 1:
        mode = 1 - mode
    else:
        if mode == 0:
            if query[1] == "1":
                pres.append(query[2])
            else:
                posts.append(query[2])
        else:
            if query[1] == "1":
                posts.append(query[2])
            else:
                pres.append(query[2])
s = "".join(pres[::-1]) + s + "".join(posts)
if mode == 1:
    s = s[::-1]
print(s)

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

using namespace std;

void Run()
{
	int N{};
	map<string, int> con;
	con["AC"] = 0;
	con["WA"] = 0;
	con["TLE"] = 0;
	con["RE"] = 0;

	cin >> N;
	for(int i = 0; i < N; ++i)
	{
		string S;
		cin >> S;

		auto it = con.find(S);
		if(it != con.end())
		{
			(it->second)++;
		}
	}

	
		cout << "AC" << " x " << con["AC"] << "\n";
		cout << "WA" << " x " << con["WA"] << "\n";
		cout << "TLE" << " x " << con["TLE"] << "\n";
		cout << "RE" << " x " << con["RE"] << "\n";

}


int main()
{
	//cout << "this is my test file\n";

	Run();


	return 0;
}

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

using namespace std;

long long dp[100010][4];
int getTheAnswer(string S) {
    int n = S.size(), MOD = 1000000007;
    memset(dp, 0, sizeof(dp));
    for(int i = n; i >= 0; --i){
        for(int j = 3; j >= 0; --j){
            if(i == n){
                dp[i][j] = (j == 3 ? 1 : 0);
            }else{
                dp[i][j] = dp[i+1][j] * (S[i] == '?' ? 3LL : 1LL);
                if(j < 3 && (S[i] == '?' || S[i] == "ABC"[j])){
                    dp[i][j] += dp[i+1][j+1];
                }
                dp[i][j] %= MOD;
            }
        }
    }
    return dp[0][0];
}

class DWeLoveABC {
public:
    void solve(std::istream& in, std::ostream& out) {
        string x;
        in >> x;
        out << getTheAnswer(x) << '\n';
    }
};


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

Measured memory_bytes: 3584
#include <stdio.h>
int main(void)
{
	char A[102],B[102];
	int Ac,Bc;
	int i;
	
	scanf("%s",A);
	scanf("%s",B);
	for(i=0;i<100;i++){
		if(A[i]=='\0')
			break;
	}
	Ac=i;
	for(i=0;i<100;i++){
		if(B[i]=='\0')
			break;
	}
	Bc=i;
	if(Ac>Bc){
		printf("GREATER");
	}else if(Ac<Bc){
		printf("LESS");
	}else{
		for(i=0;i<100;i++){
			if(A[i]>B[i]){
				printf("GREATER");
				break;
			}else if(A[i]<B[i]){
				printf("LESS");
				break;
			}
			if(Ac==i){
				printf("EQUAL");
				break;
			}
		}
				
	}

	return 0;
}
		

Measured memory_bytes: 128
import math
memo = {}
mod = 998244353
"""
def choose(n,k):
    x = ",".join([str(n),str(k)])
    if x not in memo:
        memo[x] = math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    return memo[x]
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
N = 2 * 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

X,M,K = map(int,input().split())
ans = 0
for k in range(K+1):
    ans += M*pow((M-1),X-k-1,mod)*cmb(X-1,k,mod)

print(ans%mod)

Measured memory_bytes: 112680
#include<iostream>
#include<array>
#include<math.h>
#include<iomanip>

using namespace std;

int main(){
    int n;
    array<long double,8>x;
    array<long double,8>y;

    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>x.at(i)>>y.at(i);
    }
    long double d = 0;
    for(int i = 0; i < n - 1; i++){
        for (int j = i+1; j < n; j++){
            d = d + pow(pow(x.at(j) - x.at(i),2.0)+pow(y.at(j) - y.at(i),2.0),0.5);
        }
    }
    d = d*2/n;
    cout<<setprecision(11)<<d<<endl;
}

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

int main() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> a(n, vector<int>(d));
  for(int i=0; i<n; i++) {
    for(int j=0; j<d; j++) {
      cin >> a[i][j];
    }
  }
  
  int sum = 0;
  int count = 0;
  for(int i=0; i<n-1; i++) {
    for(int j=1; j<n; j++) {
      if(i<j) {
        for(int k=0; k<d; k++) {
          sum += abs(a[i][k]-a[j][k])*abs(a[i][k]-a[j][k]);
          if(k==d-1) {
            if(int(sqrt(sum))*int(sqrt(sum))==sum) {
              count++;
              sum = 0;
            }
            else sum = 0;
          }
        }
      }
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 3628
import math


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def main():
    X = int(input())

    while True:
        if is_prime(X):
            print(X)
            break

        X += 1


main()


Measured memory_bytes: 2940
#include <algorithm>
#include <assert.h>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <list>
#include <memory.h>
#include <stack>
#include <string>
#include <time.h>
#include <vector>

using namespace std;

const int N = 1e5 + 1;
vector<int> g[N];
bool vis[N];
int dp[N];

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

#ifdef _DEBUG
	(void)freopen("in.txt", "r", stdin);
#endif

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
	}

	for (int i = 1; i <= n; ++i)
		g[0].push_back(i);
	
	stack<int> st;
	st.push(0);

	while (!st.empty()) {
		int u = st.top();
		if (vis[u]) {
			st.pop();
			for (auto& v : g[u])
				dp[u] = max(dp[u], 1 + dp[v]);
		}
		else {
			vis[u] = true;
			for (auto& v : g[u]) {
				if (!vis[v]);
					st.push(v);
			}
		}
	}

	cout << dp[0] - 1 << '\n';

	return 0;
}

Measured memory_bytes: 7160
#include <bits/stdc++.h>
#define x first
#define y second
#define y1 secondy1
#define rank tipa_rank
#define pb push_back
#define mp make_pair
#define pow10 tipa_pow10
#define ll long long
#define INF 1000000000
#define EPS 1e-9
#define EPS2 1e-8
#define PI acos(-1.0)
using namespace std;
const int MOD = INF + 7;
const int base = 2;
ll ans;
int n , a , b;
int main()
{
	scanf("%d %d %d" , &n , &a , &b);
	if(a > b)
	{
		printf("0\n");
		return 0;
	}
	if(n == 1)
	{
		if(a != b)
			printf("0\n");
		else
			printf("1\n");
		return 0;
	}
	if(n == 2)
	{
		printf("1\n");
		return 0;
	}
	printf("%lld\n" , (ll)(b - a) * max(0 , n - 2) + 1);
}


Measured memory_bytes: 256
import numpy as np

hour = 30
minute = 6

A, B, H, M = list(map(int, input().split()))

ath = H * hour + M * 0.5
bth = M * minute

ax = np.sin(np.radians(ath)) * A
ay = np.cos(np.radians(ath)) * A

bx = np.sin(np.radians(bth)) * B
by = np.cos(np.radians(bth)) * B

ans = np.sqrt(((max(ax, bx) - min(ax, bx))**2) + ((max(ay, by) - min(ay, by))**2))

print(ans)


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

vector<pair<int, int>> prime_factorize(int n) {
  vector<pair<int, int>> res;
  for (int p = 2; p*p <= n; p++) {
    if (n % p != 0) continue;
    int num = 0;
    while (n % p == 0) { num++; n /= p; }
    res.push_back(make_pair(p, num));
  }
  if (n != 1) res.push_back(make_pair(n, 1));
  return res;
}

int main() {
  int N; cin >> N;
  vector<int> cnt(N+1);
  if (N == 1) { cout << 0 << endl; return 0; }
  for (int i = 2; i <= N; i++) {
    vector<pair<int, int>> pf = prime_factorize(i);
    for (auto p : pf) cnt.at(p.first) += p.second;
  }
  int ans = 0;
  for (int i = 2; i <= N; i++) {
    if (cnt.at(i) < 2) continue;
    for (int j = 2; j <= N; j++) {
      if (i == j) continue;
      if (cnt.at(j) < 4) continue;
      for (int k = j + 1; k <= N; k++) {
        if (i == k) continue;
        if (cnt.at(k) >= 4) ans++;
      }
    }
  }
  for (int i = 2; i <= N; i++) {
    if (cnt.at(i) < 4) continue;
    for (int j = 2; j <= N; j++) {
      if (i == j) continue;
      if (cnt.at(j) >= 14) ans++;
    }
  }
  for (int i = 2; i <= N; i++) {
    if (cnt.at(i) < 2) continue;
    for (int j = 2; j <= N; j++) {
      if (i == j) continue;
      if (cnt.at(j) >= 24) ans++;
    }
  }
  for (int i = 2; i <= N; i++) {
    if (cnt.at(i) >= 74) ans++;
  }
  cout << ans << endl;
}

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

long long int niche(long long int a, long long int m) {
  long long int w = a, n = 1;
  while (w % m != 1) {
    n++;
    w = (w % m) * a;
  }
  return n;
}

long long int gcd(long long int a, long long int b) {
  return (b == 0) ? a:gcd(b, a % b);
}

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

long long int lcm(long long int a, long long int b, long long int c) {
  return lcm( lcm(a, b), c);
}

int main() {
  long long int a1, m1, a2, m2, a3, m3;

  while (cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3) {
    if (a1 * m1 * a2 * m2 * a3 * m3 == 0)
      break;

    cout << lcm(niche(a1, m1), niche(a2, m2), niche(a3, m3)) << endl;
  }
}

Measured memory_bytes: 1152
import scala.io.StdIn.readInt

object Main {
  def fib(a:Int, b: => Int, n:Int):Int = {
    if (n ==  0)
      a
    else
      fib(a+b, a, n-1)
  }

  def main(args: Array[String]) = {
    val n = readInt()
    println(fib(1, 0, n))
  }
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> x(N);
  for(int i=0; i<N; i++){
    cin >> x.at(i);
  }
  int ans = 0;
  for(int i=0; i<N; i++){
    ans += min(x.at(i), K-x.at(i));
  }
  cout << 2*ans;
  return 0;
}

Measured memory_bytes: 3576
using System;
using System.Collections.Generic;
using System.Linq;

class E
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var p = Console.ReadLine().Split().Select(int.Parse).ToArray();
		var q = new int[n + 1];
		for (int i = 0; i < n; i++) q[p[i]] = i;

		var bigs = new List<int> { q[n] };
		var s = 0L;
		for (int i = n - 1; i > 0; i--)
		{
			var bi = ~bigs.BinarySearch(q[i]);
			if (bi > 0)
			{
				var li = bigs[bi - 1];
				var li2 = bi - 2 >= 0 ? bigs[bi - 2] : -1;
				var ri2 = bi < bigs.Count ? bigs[bi] : n;
				s += (long)i * (li - li2) * (ri2 - q[i]);
			}
			if (bi < bigs.Count)
			{
				var ri = bigs[bi];
				var ri2 = bi + 1 < bigs.Count ? bigs[bi + 1] : n;
				var li2 = bi - 1 >= 0 ? bigs[bi - 1] : -1;
				s += (long)i * (q[i] - li2) * (ri2 - ri);
			}
			bigs.Insert(bi, q[i]);
		}
		Console.WriteLine(s);
	}
}


Measured memory_bytes: 21472
#!/usr/bin/env python
# coding: utf-8

# In[4]:


N = int(input())
A = []
for _ in range(N):
    A += [int(input())]


# In[6]:


A.sort()
ans = 0
if N%2 == 0:
    ans = 2*(sum(A[N//2:]) - sum(A[:N//2])) + A[N//2 - 1] - A[N//2]
else:
    ans = 2*(sum(A[N//2 + 1:]) - sum(A[:N//2]))
    ans -= min(A[N//2 + 1] - A[N//2], A[N//2] - A[N//2 - 1])
print(ans)



Measured memory_bytes: 13392
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] ans = new int[m];
        Arrays.fill(ans, 0);
        for (int i = 0; i < n; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                int b = sc.nextInt();
                ans[b - 1]++;
            }
        }
        int answe = 0;
        for (int i = 0; i < m; i++) {
            if (ans[i] == n) {
                answe++;
            }
        }
        System.out.println(answe);

    }
}

Measured memory_bytes: 22740
package main

import "fmt"

func concatenate(a, b int) int {
	d := b
	i := 0
	for d != 0 {
		i++
		d /= 10
	}
	return a*pow(10, i) + b
}

func pow(a, b int) int {
	result := 1
	for i := 0; i < b; i++ {
		result *= a
	}
	return result
}

func judgeSquare(a int) bool {
	for i := 1; i*i <= a; i++ {
		if i*i == a {
			return true
		}
	}
	return false
}

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	c := concatenate(a, b)

	if judgeSquare(c) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;

// ====================================================================

int main() {
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<int> dp(s.size());
  for (int i = 1; i < n; i++) {
    dp[i] = dp[i - 1];
    if (s[i] == 'C' && s[i - 1] == 'A') dp[i]++;
  }

  int l, r;
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    cout << dp[r - 1] - dp[l - 1] << endl;
  }
}


Measured memory_bytes: 1408
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
vector<P> edge={P(1,0),P(-1,0),P(0,1),P(0,-1)};
int H,W,K,gx,gy;
P st;
bool ch(int a,int b){
  return !(a>=0&b>=0&a<H&b<W);
}
int main(){
  cin>>H>>W>>K>>st.first>>st.second>>gx>>gy;
  vector<vector<int>> dist(H,vector<int>(W));
  for(int i=0;i<H;++i){
    string s;
    cin>>s;
    for(int j=0;j<W;++j){
      dist[i][j]=(s[j]=='.')*1e6;
    }
  }
  queue<P> que;
  dist[--st.first][--st.second]=0;
  que.push(st);
  while(!que.empty()){
    P x=que.front();que.pop();
    for(auto d:edge){
      for(int i=1;i<=K;++i){
        int a=x.first+d.first*i,b=x.second+d.second*i;
        if(ch(a,b)||dist[a][b]<=dist[x.first][x.second])break;
        if(dist[a][b]!=dist[x.first][x.second]+1){
          que.push(P(a,b));
          dist[a][b]=dist[x.first][x.second]+1;
        }
      }
    }
  }
  cout<<((dist[--gx][--gy]==1e6)?-1:dist[gx][gy])<<endl;
}

Measured memory_bytes: 11168
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=100000+10;

int n,m=0,x[N],y[N],Sx[N],Sy[N];

struct edge { int u,v,w; } e[N<<2];

int f[N*3];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

int Kruskal() {
	sort(e+1,e+m+1,[](edge a,edge b) { return a.w<b.w; });
	for (int i=1;i<=n*3;++i) f[i]=i;
	int ans=0;
	for (int i=1;i<=m;++i) {
		int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
		if (u!=v) ans+=w,f[u]=v;
	}
	return ans;
}

int main() {
	n=read();
	for (int i=1;i<=n;++i) Sx[i]=x[i]=read(),Sy[i]=y[i]=read();
	sort(Sx+1,Sx+n+1); int cx=unique(Sx+1,Sx+n+1)-Sx-1;
	sort(Sy+1,Sy+n+1); int cy=unique(Sy+1,Sy+n+1)-Sy-1;
	for (int i=1;i<=n;++i) {
		x[i]=lower_bound(Sx+1,Sx+cx+1,x[i])-Sx;
		y[i]=lower_bound(Sy+1,Sy+cy+1,y[i])-Sy;
		e[++m]=(edge){i,x[i]+n,0};
		e[++m]=(edge){i,y[i]+n+cx,0};
	}
	for (int i=1;i<cx;++i) e[++m]=(edge){i+n,i+n+1,Sx[i+1]-Sx[i]};
	for (int i=1;i<cy;++i) e[++m]=(edge){i+n+cx,i+n+cx+1,Sy[i+1]-Sy[i]};
	printf("%d\n",Kruskal());
	return 0;
}

Measured memory_bytes: 11124
import bisect
N = int(input())
l_list = sorted(map(int,input().split()))
ans = 0
#print(l_list)
for i in range(N):
    for j in range(i+1,N):
        sum_ij = l_list[i]+l_list[j]
        bi_num = bisect.bisect_left(l_list,sum_ij)
        #print(i,j,sum_ij,bi_num,bi_num-j)
        ans += bi_num-j-1
print(ans)

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

typedef long long ll;

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,l,n) for(int i=(l);i<=(n);i++)

template<class T>
using vt = vector<T>;
template<class T>
using vvt = vector<vector<T>>;

int main(){
    int n,search=0,prev=0,ans=0,one=0,renzoku=0,prev_num=0;
    cin >> n;
    vt<int> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n){
        if(a[i]==1) one++;
        if(a[i]-prev_num==1){
            prev_num = a[i];
            renzoku++;
        }
    }
    if(one == 0) {
        cout << -1 << endl;
        return 0;
    }
    if(renzoku == a.size()) {
        cout << 0 << endl;
        return 0;
    } 
    reps(i,1,n){
        while(a[search]!=i && search < a.size()) search++;
        if(search >= a.size()){
            cout << ans+(a.size()-prev) << endl;
            return 0;
        }
        ans = ans + (search-prev);
        prev = search + 1;
    }
    return 0;  
}




Measured memory_bytes: 1024
package main

import "fmt"

var w [4]int
var v [4]int
var dp [5][5001]int

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func knp(n int) int {
	w[3] = 1
	v[3] = 1

	for i := 3; i >= 0; i-- {
		for j := 0; j <= n; j++ {
			if j < w[i] {
				dp[i][j] = dp[i+1][j]
			} else {
				dp[i][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
			}
		}
	}
	return dp[0][n]
}

func set(wa, wb, wc, va, vb, vc int) int {
	num_pos := 0
	if va-wa > 0 {
		w[num_pos] = wa
		v[num_pos] = va
		num_pos++
	}
	if vb-wb > 0 {
		w[num_pos] = wb
		v[num_pos] = vb
		num_pos++
	}
	if vc-wc > 0 {
		w[num_pos] = wc
		v[num_pos] = vc
		num_pos++
	}
	return num_pos
}

func greedy(n int) int {
	return n/w[0]*v[0] + n%w[0]
}

func all(n int) int {
	max := 0
	for i := 0; i*w[0] <= n; i++ {
		rem := n - i*w[0]
		v := v[0]*i + rem/w[1]*v[1] + rem%w[1]
		if v > max {
			max = v
		}
	}
	return max
}

func main() {
	var n, ga, sa, ba, gb, sb, bb int
	fmt.Scan(&n, &ga, &sa, &ba, &gb, &sb, &bb)
	dng := n

	p := set(ga, sa, ba, gb, sb, bb)
	if p == 3 {
		dng = knp(dng)
	} else if p == 2 {
		dng = all(dng)
	} else if p == 1 {
		dng = greedy(dng)
	}

	p = set(gb, sb, bb, ga, sa, ba)
	if p == 3 {
		dng = knp(dng)
	} else if p == 2 {
		dng = all(dng)
	} else if p == 1 {
		dng = greedy(dng)
	}

	fmt.Println(dng)
}


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

int main(){
    int n;
    cin >> n;
    int a[2][110] = {};
    for(int i=0; i<2; i++){
        for(int j=0; j<n; j++){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for(int i=0; i<n; i++){
        int tmp = 0;
        for(int j=0; j<=i; j++){
            tmp += a[0][j];
        }
        for(int j=i; j<n; j++){
            tmp += a[1][j];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define ll long long 
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define skorost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 

using namespace std ;
 
ll z , o , ans ;

ll N = 1e9 + 7 ;

int code(  ){

	int n , k ;

	cin >> n >> k ;

	int a[n] ;

	int sum = 0 ;

	for( int i = 0 ; i < n ; i ++ ){

		cin >> a[i] ;

	}

	sort( a , a + n ) ;

	for( int i = 0 ; i < k ; i ++ ){

		sum += a[i] ;

	}

	cout << sum << endl ;

	return 0 ;

}

int main(){ skorost ;

	int tjk = 1 ;

	// cin >> tjk ;

	while( tjk -- ){

		code( ) ;

	}

}

Measured memory_bytes: 3652
import java.util.*;

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

  Scanner sc;
  int n;
  int[] a;
  String ans;

  public Main(Scanner sc) {
    this.sc = sc;
    n = sc.nextInt();
  }
  
  public void show() {
    System.out.println(solve());
  }
  
  private String solve() {
    for (int i = 1; i < 10; i++) {
      for (int j = 1; j < 10; j++) {
        if (i*j==n) return "Yes";
      }
    }
    return "No";
  }
  
  private int[] vi(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = sc.nextInt();
    return a;
  }
}




Measured memory_bytes: 35792
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static int AB = 26;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		char[] s = sc.next().toCharArray();
		sc.close();
		int[] cnt = new int[AB];
		for(i=0;i<s.length;i++) {
			cnt[s[i]-'a']++;
		}
		boolean f=false;
		for(i=0;i<AB;i++) {
			if(cnt[i]==0) {
				f=true;
				break;
			}
		}
		out.println(f?(char)('a'+i):"None");
	}
}


Measured memory_bytes: 25716
/*
 * main.c
 *
 *  Created on: 2020/03/28
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a > b ? b : a)
typedef long long int ll;
typedef unsigned long long int ull;

int sort_inc(const void *a, const void *b) { return (*(int*)a - *(int*)b);}
int sort_dec(const void* a, const void* b) { return (*(int*)b - *(int*)a);}
int sort_dec_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = -1; }
    else if (da == db) { val = 0; }
    else { val = 1; }
    return val;
}
int sort_inc_ll(const void *a, const void *b) {
    ll da = *(ll*)a, db = *(ll*)b;    int val = 0;
    if(da > db) { val = 1; }
    else if (da == db) { val = 0; }
    else { val = -1; }
    return val;
}
int sort_dic(const void *a, const void *b) {
    char *pa = (char *)a;    char *pb = (char *)b;    int i = 0, val = 0, N = 10;
    for (i = 0; i < N; i++) {
    	char da = pa[i], db = pb[i];
    	if (da == db) continue;
  		if (da > db) val = 1; else val = -1;
        break;
    }
    return val;
}

void yesno(int ans) {
	if (ans == 1) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	return;
}

int main()
{
	int A = 0, B = 0, C = 0, D = 0, ans = 0;
	scanf("%d %d %d %d", &A, &B, &C, &D);

	while (1) {
		if ((C - B) <= 0) {
			ans = 1;
			break;
		} else {
			C -= B;
		}
		if ((A - D) <= 0) {
			ans = 0;
			break;
		} else {
			A -= D;
		}
	}
	yesno(ans);
	return 0;
}


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

int main()
{
    ll int a, b, c, d;
    cin>>a>>b>>c>>d;
    ll int arr[4];
  	arr[0]=a*c;
  	arr[1]=a*d;
  	arr[2]=b*c;
  	arr[3]=b*d;
  	cout<<(*max_element(arr, arr+4));
    return 0;
}

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

int main() {
  string s;
  cin>>s;
  int n = s.length();
  int i=0;
  while (s[i]!='A') i++;
  int j=n-1;
  while (s[j]!='Z') j--;
  cout<<j-i+1<<endl;
  return 0;
}

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

#define ll long long
#define endl "\n"
#define vi vector<int>
#define pb push_back
#define F first
#define S second

ll N, W;
pair<ll, ll> arr[1000];

void solve() {
	cin >> N >> W;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i].F >> arr[i].S;
	}
	ll dp[N + 1][W + 1];

	for (int i = 0; i <= W; i++) {
		dp[1][i] = 0;
	}

	dp[1][arr[1].F] = arr[1].S;

	for (int i = 2; i <= N; i++) {
		for (int weight = 0; weight <= W; weight++) {

			dp[i][weight] = dp[i - 1][weight];
			if (arr[i].F <= weight)
				dp[i][weight] = max(dp[i][weight], arr[i].S + dp[i - 1][weight - arr[i].F]);
		}
	}

	cout << *max_element(dp[N], dp[N] + W + 1);


}

int main() {
#ifndef ONLINE_JUDGE
	freopen("manish.txt", "r", stdin);
	//freopen("ps.txt", "w", stdout);
#endif
	int t; t = 1;

	while (t--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 81688
def d_multiple_of_2019():
    from collections import Counter
    S = [int(ch) for ch in input()]

    s = S[::-1]
    n = len(S)
    u = [0] * n

    # u[0] = s[0]
    # power = 1
    # for i in range(1,n):
    #     power *= 10
    #     u[i] = u[i-1] + power * s[i]

    p = 2019
    u[0] = s[0] % p
    power = 1
    for i in range(1, n):
        power *= 10
        power %= p
        u[i] = u[i - 1] + power * s[i]
        u[i] %= p
    count = Counter(u)
    ans = 0
    for k, v in count.items():
        ans += v * (v - 1) // 2
    return ans + count[0]

print(d_multiple_of_2019())

Measured memory_bytes: 19648
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, a, b;
	cin >> n >> a >> b;
	cout << min(n*a, b) << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<math.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < n; i++)

const ll INF = 1LL << 60;


ll dist[100005];
bool hole[100005];
ll a = 1000000007;

ll step(ll x) {
	if (dist[x] != -1) {
		return dist[x];
	}
	else if (x == 0){
		dist[x] = 0;
		return 0;
	}
	else if (x == 1) {
		if (hole[1]) {
			dist[x] = 0;
			return 0;
		}
		else {
			dist[x] = 1;
			return 1;
		}

	}
	else if (x == 2) {
		if (hole[2]) {
			dist[2] = 0;
			return 0;
		}
		else return dist[2] = step(1) + 1;
	}
	else{
		if (hole[x]) {
			dist[x] = 0;
			return dist[x];
		}

	}
	dist[x] = step(x - 1) + step(x - 2);
	return dist[x] % a;
}

signed main() {

	for (int i = 0; i < 100005; i++) {
		dist[i] = -1;
		hole[i] = false;
	}
	ll n, a;
	cin >> n >> a;

	rep(i, a) {
		ll b;
		cin >> b;
		hole[b] = true;
	}
	ll ans = step(n);
	cout << ans << endl;
}

Measured memory_bytes: 4224
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
INF = float("inf")
import sys,collections,heapq,math

N,K = map(int,sys.stdin.readline().split())
a = list(map(int,sys.stdin.readline().split())) # single line with multi param
a.sort(reverse=True)

ng = 0
ok = a[0]

def isOK(v):
    # within range
    # return key <= a[index]
    k = K
    i = 0
    while k >= 0 and i < N:
        #print("?",v,i,a[i],k,math.ceil(a[i] / v) -1,k - (math.ceil(a[i]/v) - 1))
        k = k - (math.ceil(a[i]/v) - 1)
        i += 1
    return k >= 0

while abs(ng-ok) > 1:
    mid = (ok+ng)//2
    #print(mid,isOK(mid))
    if isOK(mid):#ok condition?
        ok = mid #move ok
    else:
        ng = mid
#294924427
print(math.ceil(ok))

# a = [[-b,b,1] for b in tuple(map(int,sys.stdin.readline().split()))] # single line with multi param
# heapq.heapify(a)# a == [1,2,3]
# for _ in range(K):
#     _,ori,di = heapq.heappop(a)
#     heapq.heappush(a, [-(ori)/(di+1),ori,di+1])
# print(math.ceil(-a[0][0]))


Measured memory_bytes: 32148
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
using ll=long long;

ll n,a,b,c,d;
bool solve(){
  ll lo = a-d*(n-1ll);
  ll hi = a+d*(n-1ll);
  if(b<lo||hi<b) return false;
  int l=0,h=(hi-lo)/(c+d)+1;
  while(l+1<h){
    int m=(l+h)/2;
    if(lo+m*(c+d)<=b)l=m;
    else h=m;
  }
  int p=lo+l*(c+d),q=p+(d-c)*(n-1);
  return p<=b&&b<=q;
}

int main(){ _;
  cin>>n>>a>>b>>c>>d;
  cout<<(solve()?"YES":"NO")<<endl;
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n; cin >> n;
	n %= 1000;
	if (n!=0) n = 1000 - n;
	cout << n << endl;
	return 0;
}

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

using namespace std;
//typedef long long ll;
typedef unsigned long long ll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX;
const ll MINF = LONG_LONG_MIN;
const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<char> &s, int a) { return s.find(a) != s.end(); }


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<ll, vector<ll>, greater<ll>> PQ_ASK;
const int mod = 1000000007;


int main() {
    int n, t;
    cin >> n >> t;

    vector<ll> apples(n);
    rep(i, n) cin >> apples[i];

    ll ans = 0;
    ll max_diff = 0;
    {
        ll min_apple = apples[0];
        for (int i = 1; i < n; i++) {
            ll apple = apples[i];
            cmin(min_apple, apple);

            ll diff = apple - min_apple;
            cmax(max_diff, diff);
        }
    }

    ll min_apple = apples[0];
    for (int i = 1; i < n; i++) {
        ll apple = apples[i];
        cmin(min_apple, apple);

        ll diff = apple - min_apple;
        if (diff == max_diff) ans++;
    }

    cout << ans << endl;
}


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

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

  T = S;
  reverse( T.begin(), T.end() );

  int ans = 0;
  for (int i = 0; i < S.size() / 2; i++) {
    if (S[i] != T[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <math.h>
using namespace std;

#define rep(i, o) for (int i = 2; i <= (o); ++i)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define MAX 1000000 

typedef long long ll;
typedef unsigned long long ull;


ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

int main() {
  ull n;
  cin >> n;
  
  ull move = MAX*MAX + 1;
  rep (i, MAX) {
    if (n%i == 0)
    {
        /* code */
        move = min((ull)(i-1 + (n/i - 1)), move);
        // cout << move << " " << n << endl;
    }
  }
  if (move == MAX*MAX + 1) move = n-1;
  cout << move << endl;
  return 0;
}

Measured memory_bytes: 384
xs = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(xs[K - 1])

Measured memory_bytes: 38256
from bisect import bisect_right


def d():
    n = int(input())
    ls = list(map(int, input().split()))
    ls.sort()
    count = 0
    for i in range(n-1, -1, -1):
        for j in range(i-1, -1, -1):
            k = bisect_right(ls, ls[i]-ls[j])
            if j >= k:
                count += j - k

    print(count)


if __name__ == '__main__':
    d()


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

int main(void)
{
	//freopen("A.in","r",stdin);
	//freopen("A.out","w",stdout);
	string a;
	cin >> a;
	if(a[0]=='9' || a[1]=='9')
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
using namespace std;
ll N,M;
const ll MAX_N=1e5;
vector<ll> G[MAX_N],vs;
bool dfs(ll v,ll p){
	if(v==vs[1]){
		return false;
	}
	if(v==vs[0]){
		return true;
	}
	for(auto e:G[v]){
		if(e!=p){
			return dfs(e,v);
		}
	}
}
bool slv(){
	REP(v,N){
		if(G[v].size()%2){
			return false;
		}
	}
	REP(v,N){
		if(G[v].size()>=6){
			return true;
		}
	}
	REP(v,N){
		if(G[v].size()==4){
			vs.push_back(v);
		}
	}
	if(vs.size()<=1){
		return false;
	}
	if(vs.size()>2){
		return true;
	}
	for(auto e:G[vs[0]]){
		if(dfs(e,vs[0])){
			return true;
		}
	}
	return false;
}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>N>>M;
	REP(i,M){
		ll a,b;
		cin>>a>>b;
		a--;
		b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cout<<(slv()?"Yes":"No")<<endl;
}

Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
using namespace std;
void trans(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp%b;
}
void gcd(int a,int b)
{
    int tmp;
    while(a%b!=0&&b%a!=0)
    {
    if(a>b)
        trans(a,b);
    if(a<b)
        trans(b,a);
    }
    cout<<min(a,b)<<endl;
}
int main()
{
    int a,b;
    cin>>a>>b;
    gcd(a,b);
    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int h,w,n;
    cin >> h >> w >> n;
    int r,c;
    cin >> r >> c;
    string s,t;
    cin >> s >> t;
    reverse(ALL(s));
    reverse(ALL(t));
    int L = 1, R = w, U = 1, D = h;
    for(int i = 0; i < n; i++){
        if(t[i] == 'L' && R < w) R++;
        else if(t[i] == 'R' && L > 1) L--;
        else if(t[i] == 'U' && D < h) D++;
        else if(t[i] == 'D' && U > 1) U--;
        if(s[i] == 'L') L++;
        else if(s[i] == 'R') R--;
        else if(s[i] == 'U') U++;
        else D--;
        if(L > R || U > D){
            cout << "NO" << endl;
            return 0;
        }
    }
    if(U <= r && r <= D && L <= c && c <= R){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 776
N,A,B,C=map(int,input().split())
S=['']*(N+1)
for a in range(N):
    S[a]=input()

ans='Yes'
L_ans=['']*(N+1)
i=0
while i<N:
    if S[i]=='AB':
        if A>B:
            B+=1
            A-=1
            L_ans[i]='B'
        elif A<B:
            A+=1
            B-=1
            L_ans[i]='A'
        elif A==B and S[i+1]=='BC':
            B+=1
            A-=1
            L_ans[i]='B'
        else:
            A+=1
            B-=1
            L_ans[i]='A'
    elif S[i]=='AC':
        if A>C:
            C+=1
            A-=1
            L_ans[i]='C'
        elif A<C:
            A+=1
            C-=1
            L_ans[i]='A'
        elif A==C and S[i+1]=='BC':
            C+=1
            A-=1
            L_ans[i]='C'
        else:
            A+=1
            C-=1
            L_ans[i]='A'
    elif S[i]=='BC':
        if C>B:
            B+=1
            C-=1
            L_ans[i]='B'
        elif C<B:
            C+=1
            B-=1
            L_ans[i]='C'
        elif B==C and S[i+1]=='AB':
            B+=1
            C-=1
            L_ans[i]='B'
        else:
            C+=1
            B-=1
            L_ans[i]='C'
    i+=1
    if any([A<0,B<0,C<0]):
        ans='No'
        break

print(ans)
if ans=='Yes':
    j=0
    while j<N:
        print(L_ans[j])
        j+=1

Measured memory_bytes: 16980
r, c = map(int, input().split())
matrix = [[int(n) for n in input().split()] for row in range(r)]

for i, row in enumerate(matrix):
    matrix[i].append(sum(row))

end = [0 for _ in range(c+1)]
for i in range(c+1):
    for row in matrix:
        end[i] += row[i]

matrix.append(end)

for row in matrix:
    row = map(str, row)
    print(" ".join(row))


Measured memory_bytes: 5684
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 505
#define mod 1000000007


int main(){
    fastio;
    int cnt=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(i%2==0 and x&1)
        cnt++;
    }
    cout<<cnt<<"\n";
    return 0;
}

Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
 
ll Abs(ll x,ll y){
    if(x>=y)return x-y;
    else return y-x;
}

int main(void){
    ll n,k,q;
    cin>>n>>k>>q;
    map<ll,ll>m;
    ll sum = 0;
    for(ll i=0;i<q;i++){
        ll a;
        cin>>a;
        m[a]++;
        sum++;
    }
    for(ll i=0;i<n;i++){
        if(k+m[i+1]-sum>0)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}



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

int main() {
  long long n, k;
  cin >> n >> k;

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

  sort(h, h + n);

  long long num = 0;
  for(int i = 0; i < n - k; i++){
    num += h[i];
  }

  cout << num << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF 1e9
#define dump(x) cerr<<#x<<"="<<x<<endl


using ll = long long;
const ll mod = LLONG_MAX;

vector<int> v;
int used[210];
int d[210][210];
int N,M,R;
int res;
void warshall_floyd(){
  for(int k=0;k<N;k++)
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}


int main(){
  cin>>N>>M>>R;
  rep(i,R){
    int t;cin>>t;t--;
    v.push_back(t);
  }

  for(int i=0;i<N;i++)for(int j=0;j<N;j++){
    if(i!=j)d[i][j]=INF;
  }
  rep(i,M){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    if(d[a][b]>c)d[a][b]=c;d[b][a]=c;
  }

  warshall_floyd();
  res=INF;

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

  do{
    int ret=0;
    for(int i=0;i<R-1;i++)ret+=d[v[i]][v[i+1]];
    res=min(res,ret);
  }while(next_permutation(v.begin(),v.end()));
  cout<<res<<endl;

}


Measured memory_bytes: 384
def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for j in dic[a]:
                    if mark[j]:
                        continue
                    
                    d.appendleft(j)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

Measured memory_bytes: 81100
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <list>
#include <bitset>
#include <numeric>
#include <utility>
#define INF 1e9
#define MOD 1000000007
#define ll long long
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pr;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int f[9]={1,1,2,3,5,8,13,21,34};
    int h,w,k;
    cin>>h>>w>>k;
    vector<vector<int>>dp(h+2,vector<int>(w+2,0));
    dp[0][1]=1;
    for(int i=0;i<h;i++){
        for(int j=1;j<=w;j++){
            if(j>1){
                dp[i+1][j]+=dp[i][j-1]*f[j-2]*f[w-j]%MOD;
            }
            dp[i+1][j]+=dp[i][j]*f[j-1]*f[w-j]%MOD;
            if(j<w){
                dp[i+1][j]+=dp[i][j+1]*f[j-1]*f[w-j-1]%MOD;
            }
        }
    }
    // for(int i=0;i<=h;i++){
    //     for(int j=1;j<=w;j++){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<dp[h][k]%MOD;
    return 0;
}


Measured memory_bytes: 256
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class SegmentTree2:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        [q_left, q_right] (閉区間) の値を集計して返します。
        """

        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,k = get_nums_l()
    A = list(map(int, [input() for _ in range(n)]))


    # ある数字を末尾に取るときの最長列帳
    sg = SegmentTree2(300001, max, 0)

    for i in range(0, n):
        a = A[i]
        l = max(0, a-k)
        r = min(300000, a+k)
        v = sg.query(l, r+1)
        sg.update(a, v+1)

    print(sg.query(0, 300001))

main()


Measured memory_bytes: 113512