akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	const double eps=1e-11;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.Ia;
		int p=s[0]+s[1],ans=0;
		ans+=Min(s[0],s[3]);
		if(p<s[3]){
			ans-=s[3]-p;
		}
		Console.WriteLine("{0}",ans);
	}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}

Measured memory_bytes: 27512
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();long[] a = new long[n];
		long k = sc.nextLong();
		for (int i = 0; i < n; i++) a[i] = sc.nextLong();
      
		long x = 0;
		for (int i = 39; i >= 0; i--) {
			int count = 0;
			for (int j=0;j<n;j++) count += (1 & (a[j] >> i));
			if (count <= n / 2) {
				if ((x| 1l << i) <= k)  x = x| 1l << i;
			}
		}
		long sum = 0;
		for(int i=0;i<n;i++) sum+=(x^a[i]);
		System.out.println(sum);
	}
}


Measured memory_bytes: 62708
#include<stdio.h>
int count = 0;
void Traverse(int A[], int N)
{
	for(int i = 0; i < N; i++)
	{
		if(i > 0)
			printf(" ");
		printf("%d", A[i]);
	}
	putchar('\n'); 	
}
void BubbleSort(int A[], int N)
{
	int flag = 1;
	while(flag)
	{
		flag = 0;
		for(int j = N-1; j >= 1; j--)
		{
			if(A[j] < A[j-1])
			{
				int tmp = A[j-1];
				A[j-1] = A[j];
				A[j] = tmp;
				flag = 1;
				count++;
			}
		}
	}
}
int main()
{
	int N;
	int A[100];
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", &A[i]);
	BubbleSort(A, N);
	Traverse(A, N);
	printf("%d\n", count);
}



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

int main()
{
	int N;
	int p[10];
	int highest = 0;
	int sum = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> p[i];
		if (highest < p[i])
		{
			highest = p[i];
		}
		sum += p[i];
	}

	sum -= highest / 2;
	cout << sum;
	return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		boolean[] np = new boolean[100001];
		np[0] = true;
		np[1] = true;
		int[] pc = new int[100001];
		int c = 0;
		for(int i = 2; i <= 100000; i++) {
			if(!np[i]) {;
				if(!np[(i + 1) / 2])
					c++;
				for(int j = 2; i * j <= 100000; j++) {
					np[i * j] = true;
				}
			}
			pc[i] = c;
		}
		int q = Integer.parseInt(sc.next());
		for(int i = 0; i < q; i++) {
			out.println(-pc[Integer.parseInt(sc.next()) - 1] + pc[Integer.parseInt(sc.next())]);
		}
		out.flush();
	}
}

Measured memory_bytes: 49368
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
	long long x,sum=100,i;
	cin >> x;
	i=0;
	while(sum<x){
		sum=(long long)(sum*1.01);
		i++;
	}	
	cout << i << endl;
	return 0;
}

Measured memory_bytes: 3636
A = [list(map(int, input().split())) for i in range(3)]
N = int(input())
b = [int(input()) for i in range(N)]

C = [[False] * 3 for i in range(3)]
for bi in b:
    for j in range(3):
        for i in range(3):
            if A[j][i] == bi:
                C[j][i] = True

ans = False
for j in range(3):
    if C[j][0] == C[j][1] == C[j][2] == True:
        ans = True
for i in range(3):
    if C[0][i] == C[1][i] == C[2][i] == True:
        ans = True
if C[0][0] == C[1][1] == C[2][2] == True:
    ans = True
if C[0][2] == C[1][1] == C[2][0] == True:
    ans = True
print('Yes' if ans else 'No')


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h, w;
  cin >> h >> w;
  for(int i = 0; i < w+2; i++) cout << '#';
  cout << endl;
  for(int i = 0; i < h; i++){
    cout << '#';
    for(int j = 0; j < w; j++){
      char a;
      cin >> a;
      cout << a;
    }
    cout << '#' << endl;
  }
  for(int i = 0; i < w+2; i++) cout << '#';
  cout << endl;
  return 0;
}

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

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}

#define PRINT_VECTOR_MAX 100
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)min(v.size(),PRINT_VECTOR_MAX); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)min(v.size(),PRINT_VECTOR_MAX); i++) {for (ll j = 0; j < (ll)min(v[i].size(),PRINT_VECTOR_MAX); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}

void Main();
int main(){
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	Main();
	return 0;
}

int mod;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

void Main(){
    ll n;
    ll x,m; cin >> n >> x >> m;
    vector<ll> memo(m, 0);
    vector<ll> ss(m, 0);
    memo[x] = 1;
    ss[x] = 0;
    ll now = x;
    ll cnt = 1;
    unsigned long long ans = x;
    while(1){
        if(cnt == n){
            cout << ans << endl;
            return;
        }
        
        now = (now * now) % m;
        cnt++;

        
        
        
        if(memo[now]){
            ll loop = cnt - memo[now];
            ll nloop = (n - cnt + 1) / loop;

            ans += nloop * (ans - ss[now]);
            cnt += nloop * loop;
            break;
        }
        ss[now] = ans;
        ans += now;
        memo[now] = cnt;
        
    }
    for(; cnt <= n; cnt++){
        ans += now;
        now = (now * now) % m;
        

    }
    cout << ans << endl;
}

Measured memory_bytes: 4796
list=input().split()
for i in list:
    i=int(i)
list.sort()
sumcosts=0
costs=0
first=True
mae=0
for i in list:
    i = int(i)
    if(first):
        first=False
        mae=i
    else:
        sumcosts=sumcosts+abs((i-mae))
        mae=i
print(sumcosts)



Measured memory_bytes: 3060
N = int(input())
S = input()

dp = [[0] * (N+1) for _ in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(N-1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i+1][j+1] + 1

ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j-i)
        ans = max(ans, now)

print(ans)


Measured memory_bytes: 230408
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10000
#define STRLEN 20

int main(void){
    int n;
    scanf("%d", &n);
    while(n > 0){
        n = n - 1000;
    }

    n = -n;

    printf("%d\n", n);
    return 0;
}


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

using namespace std;
priority_queue<int>q;
int main()
{
	long long n,m,a;
	cin >> n >> m;

	for(int i = 0;i < n;i ++){
		cin >> a;
		q.push(a);
	}
	long long sum = 0;
	int t;
	for(int i = 0;i < m;i ++){
		t = q.top()/2;
		q.pop();
		q.push(t);
	}
	while(!q.empty()){
		sum += q.top();
		q.pop();
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1020
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<cmath>
#define DB double
int N;
DB x[110], y[110];
int main() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cin >> N;
	std::cout << std::fixed << std::setprecision(20);
	for (int i = 0; i < N; i++) {
		std::cin >> x[i] >> y[i];
	}
	for (int i = 0; i < N; i++) {
		DB per = 1;
		std::vector<DB> A;
		for (int j = 0; j < N; j++) {
			if (i != j)A.emplace_back(std::atan2(y[j] - y[i], x[j] - x[i]));
		}
		std::sort(A.begin(), A.end());
		A.emplace_back(A[0] + M_PI * 2);
		DB max = 0;
		for (int j = 0; j < N - 1; j++) {
			max = std::max(A[j + 1] - A[j],max);
		}
		DB ans = (max > M_PI ? (max - M_PI) / (2 * M_PI) : 0.0);
		std::cout << ans << std::endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin >> a;
  string S;
  for(int i = 0; i < a; i++){
    cin >> S;
    if(S == "Y"){
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
}
    

Measured memory_bytes: 256
#include<iostream>
using namespace std;
bool vis[27];
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++)
		vis[s[i]-'a']=true;
	if(vis[0]&&vis[1]&&vis[2])
		cout<<"Yes";
	else
		cout<<"No";
}

Measured memory_bytes: 256
use std;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_verical_vec<T: std::str::FromStr>(n: u32) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read::<T>());
    }
    return vec;
}

fn read_matrix<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec::<T>()).collect()
}

fn f_intervals_on_tree() {
    let n = read::<i64>();
    let vs = read_matrix::<i64>((n - 1) as u32);

    let v: i64 = (1..n+1).map(|i| i * (n + 1 - i)).sum();
    let e: i64 = vs.iter().map(|vt| {
        if vt[0] < vt[1] { vt[0] * (n + 1 - vt[1]) } else { vt[1] * (n + 1 - vt[0]) }
    }).sum();
    let ans = v - e;

    println!("{}", ans);
}

fn main() {
    f_intervals_on_tree();
}


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

string to_string(string s) { return '"' + s + '"'; }
string to_string(char c) { string s = "'"; s += c; return s + "'"; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } 
template <typename A>
string to_string(A v) {
    bool first = true; 
    string res = "{";
    for (const auto &x : v) {
        if (!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}"; 
    return res;
}
istream_iterator<string> eos;
void dbg_out(istream_iterator<string> it) { cerr << endl; }
template <typename Head, typename... Tail>
void dbg_out(istream_iterator<string> it, Head H, Tail... T) {
    cerr << *it << " = " << to_string(H);
    if(++it != eos) cerr << ", ";
    dbg_out(it, T...);
}
#ifdef LOCAL
    #define dbg(...) { string _s = #__VA_ARGS__; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); dbg_out(_it, __VA_ARGS__); }
#else
    #define dbg(...)
#endif

#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define MP make_pair
#define sz(v) ((int)(v).size())
#define fr(i, j, k) for(int i = j; i < k; i++)
#define nl "\n"
typedef pair<int, int> pii;
typedef vector <int> vi;

pii dir[8] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1} , {-1, 1}, {1, -1} };

const int inf = (1LL << 60), mod = 998244353, nn = 3003;
int n, s;
int a[nn];
int dp[nn][nn];

int fun(int ind, int sum) {
    if(sum == 0) return n - (ind - 2);    // for this set last element is idx-1, and we can take R from idx-1 to n for this set
    if(ind > n) return 0;
    int &res = dp[ind][sum];
    if(res != -1) return res;

    int can = fun(ind + 1, sum);
    if(sum - a[ind] >= 0) can += fun(ind + 1, sum - a[ind]);
    return res = can % mod;
}

void solve(){
    cin >> n >> s;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int ans = 0;
    memset(dp, -1, sizeof dp);

    for(int i = 1; i <= n; i++) {
        ans = (ans + fun(i, s)) % mod;         // fix L = i, ignoring all elements previous to i 
    }
    cout << ans << '\n';
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    for(int tc = 1; tc <= T; tc++){
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for(int i = (int)(n); i>=0; --i)
struct fast_ios { fast_ios(){cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast_ios_;

int main()
{
    int K, A, B;
    cin >> K >> A >> B;
    
    for(int i=A;i<=B;++i)
    {
        if(i%K==0)
        {
            cout << "OK" << endl;
            return 0;
        }
    }

    cout << "NG" << endl;
    
    return 0;
}

Measured memory_bytes: 3652
#include<stdio.h>

int n,k,a,b,c,d,e;
int G[101][101];
int cost[101];
int visited[101];
int INF=100000000;

int dijkstra(int start,int goal){
  int i,p,mini;
  for(i=1;i<=n;i++){
    cost[i]=INF;
    visited[i]=0;
  }
  cost[start]=0;
  
  while(1){
    mini=INF;
    for(i=1;i<=n;i++){
      if(visited[i]==0 && mini>cost[i]){
        mini=cost[i];
        p=i;
      }
    }
    if(mini==INF)break;
    visited[p]=1;
    for(i=1;i<=n;i++){
      if(cost[p]+G[p][i] < cost[i]){
        cost[i]=cost[p]+G[p][i];
      }
    }
  }
  if(cost[goal]==INF)return -1;
  else return cost[goal];
}

void init(){
  int i,j;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      G[i][j]=INF;
}

int main(){
  int i,flg;

  while(1){
    scanf("%d %d",&n,&k);
    if(n==0&&k==0)break;
    init();
    for(i=0;i<k;i++){
      scanf("%d",&flg);
      if(flg==0){
        scanf("%d %d",&a,&b);
        printf("%d\n",dijkstra(a,b));
      }else{
        scanf("%d %d %d",&c,&d,&e);
        if(e<G[c][d]){
          G[c][d]=e;
          G[d][c]=e;
        }
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1064
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
using lint = long long;
using P = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define repn(i, a, b) for(int i = (a); i < (b); ++i)
#define rep_inv(i, n) for (int i = (n); i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define cend printf("\n")

//constexpr lint mod = 998'244'353LL;
constexpr lint Mod = 1000'000'007LL;
constexpr lint Inf = 4'500'000'000'000'000'007LL; //4.5e18+7
constexpr double Pi = 3.141592653589793;

template<class T> using prique     = priority_queue<T>;
template<class T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool chmin(T& a, const T& b) {
	if (a > b) {
		a = b; return true;
	}
	return false;
}
template<class T> bool chmax(T& a, const T& b) {
	if (a < b) {
		a = b; return true;
	}
	return false;
}
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }
template<class T, class U>inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "(" << rhs.first << ", " << rhs.second << ")"; }
template<class InputIterator> void arrin(InputIterator first, InputIterator last) { for (; first != last; ++first) cin >> (*first); }
template<class InputIterator> void arrout(InputIterator first, InputIterator last) {
	for (; first != last; ++first) {
		cout << (*first) << ((first + 1) != last ? " " : "\n");
	}
}

template<class T, class U> void print(const T& a, const U& b, bool f) {
	if (f) cout << a << "\n";
	else cout << b << "\n";
}

bool pri(lint x) { 
	for (lint i = 2; i * i <= x; ++i) {
		if (x % i == 0) return false;
	}
	return 1 < x; 
}

lint fact[3000000];
void fact_init(lint n, lint m = Mod) {
	if (3000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1] % m;
	}
}

lint modpow(lint x, lint n, lint m = Mod) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % m;
		x = x * x % m;
		n >>= 1;
	}
	return res;
}

lint intpow(lint x, lint n) {
	lint res = 1;
	while (n > 0) {
		if (n & 1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

lint comb(lint n, lint r, lint m = Mod) {
	if (r == 0 || r == n) return 1;
	lint res = fact[n] * modpow(fact[n - r], m - 2, m) % m * modpow(fact[r], m - 2, m) % m;
	return res < 0 ? res + m : res;
}

map<lint, lint> factring(lint n) {
	map<lint, lint> res;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++res[i];
		}
	}
	if (n != 1) ++res[n];
	return res;
}

int ans = 100000;
string s, t;
int f(const string& x) {
	int res = 0;
	rep(i, t.size()) res += (x[i] != t[i]);
	return res;
}
int main() {
	cin >> s >> t;
	int n = s.size(), m = t.size();

	rep(i, n - m + 1) {
		ans = min(ans, f(s.substr(i, m)));
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

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

// 辺を表す構造体（行き先、容量、コスト、逆辺）
struct edge{ int to, cap, cost, rev; };

const int MAX_V = 2*200*200+2;

int V; 				// 頂点数
vector<edge> G[MAX_V];		// グラフの隣接リスト表現
int dist[MAX_V];			// 最短距離
int prevv[MAX_V], preve[MAX_V]; 	// 直前の頂点と辺

// from から to へ向かう容量 cap の辺をグラフに追加する
void add_edge(int from, int to, int cap, int cost){
	G[from].push_back((edge){to, cap, cost, G[to].size()});
	G[to].push_back((edge){from, 0, -cost, G[from].size() - 1});
}

// s から t への流量 f の最小費用流を求める
// 流せない場合は -1 を返す
int min_cost_flow(int s, int t, int f){
	int res = 0;
	while(f > 0){
		// ベルマンフォード法により、s-t 間の最短路を求める
		fill(dist, dist + V, INF);
		dist[s] = 0;
		bool update = true;
		while(update){
			update = false;
			rep(v, V){
				if (dist[v] == INF) continue;
				rep (i, G[v].size()){
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to] > dist[v] + e.cost){
						dist[e.to] = dist[v] + e.cost;
						prevv[e.to] = v;
						preve[e.to] = i;
						update = true;
					} // end if
				} // end rep
			} // end rep
		} // end while
		
		if (dist[t] == INF){
			// これ以上流せない
			return -1;
		} // end if
	
		// s-t 間最短路を使って目一杯流す
		int d = f;
		for (int v = t; v != s; v = prevv[v]){
			d = min(d, G[prevv[v]][preve[v]].cap);
		} // end for
		f -= d;
		res += d*dist[t];
		for (int v = t; v != s; v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		} // end for
	} // end whle

	return res;
}

int in[200][200];
int out[200][200];

int main()
{
	memset(in, 0, sizeof(in));
	memset(out, 0, sizeof(out));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int H, W; cin >> H >> W;
	vector<vector<int> > a(H, vector<int> (W, 0));
	rep (i, H) rep (j, W) cin >> a[i][j];

	V = 2 * H * W + 2;
	int cnt = 0;
	rep (i, H) rep (j, W) in[i][j] = cnt++;
	rep (i, H) rep (j, W) out[i][j] = cnt++;
	int S = cnt++;
	int T = cnt++;
	
	add_edge(in[0][0], out[0][0], 1, 0);
	add_edge(in[H-1][W-1], out[H-1][W-1], 1, 0);
	rep (i, H){
		rep (j, W){
			add_edge(in[i][j], out[i][j], 1, -a[i][j]);
		} // end rep
	} // end rep
 	rep (i, H){
		rep (j, W){
			if (i + 1 < H){
				add_edge(out[i][j], in[i+1][j], 1, 0);
			} // end if
			if (j + 1 < W){
				add_edge(out[i][j], in[i][j+1], 1, 0);
			} // end if
		} // end rep
	} // end rep

	add_edge(S, in[0][0], 2, 0);
	add_edge(out[H-1][W-1], T, 2, 0);

	int res = -min_cost_flow(S, T, 2);
	cout << res << endl; 

	return 0;
}

Measured memory_bytes: 9856
#include <iostream>

int main(){
    int a,b,c = 0;
    std::cin >> a >> b >> c;
    int n = 0;
    for(int i=a; i<=b; i++){
        n += c%i ? 0 : 1;
    }
    std::cout << n << std::endl;
    return 0;
}



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

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

    int n;
    cin >> n;
    set<string> st;

    rep(i, n) {
        string s;
        cin >> s;
        st.insert(s);
    }

    if (st.size() == n) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 19072
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
#define MAX_N 100000
#define MAX_M 100000
using namespace std;

typedef pair< int, int > pii;

int n, m;
int a[MAX_M], b[MAX_M];
vector< int > graph[MAX_N];

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

  cin >> n >> m;
  for(int i = 0; i < m; i++){
    cin >> a[i] >> b[i];
    --a[i]; --b[i];
  }

  for(int i = 0; i < m; i++){
    graph[a[i]].push_back(b[i]);
    graph[b[i]].push_back(a[i]);
  }

  bool ans = true;
  for(int v = 0; v < n; v++){
    if(graph[v].size() % 2 == 1){
      ans = false;
      break;
    }
  }

  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


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

int main() {
  double pi = 3.141592653589793;
  double a,b,h,m;cin>>a>>b>>h>>m;
  double c2 ;
  double deg1 = h*30 + m*0.5;
  double deg2 = m * 6;
  c2 = a*a + b*b - 2*a*b*cos(pi*2*(deg1-deg2)/360);
  c2 = sqrt(c2);
  printf("%.16f", c2);
}


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

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    int l, r;
    l = a + b;
    r = c + d;

    string m = "";
    if(l > r) m = "Left";
    else if(l == r) m = "Balanced";
    else m = "Right";

    cout << m << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var A, B int
	var S string
	fmt.Scan(&A, &B)
	fmt.Scan(&S)
	if S[A] != '-' {
		fmt.Println("No")
		return
	}
	s := S[0:A]
	for _, v := range s {
		if v < '0' || v > '9' {
			fmt.Println("No")
			return
		}
	}
	s = S[A+1:]
	for _, v := range s {
		if v < '0' || v > '9' {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
using namespace std;
char s[200010];
int n, c[200010], a[200010];
long long ans;
vector < int > p[26];
bool check() {
	int cnt = 0;
	for (int i = 0; i < 26; ++i)
		cnt += p[i].size() & 1;
	return cnt < 2;
}
void add(int p, int x) {
	for (; p <= n; p += lowbit(p)) c[p] += x;
}
int sum(int p) {
	int res = 0;
	for (; p; p -= lowbit(p)) res += c[p];
	return res;
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) p[s[i]-'a'].pb(i);
	if (!check()) return puts("-1"), 0;
	for (int i, sz, x = 0; x < 26; ++x) {
		for (i = 0; i < (sz = p[x].size()); ++i)
			a[p[x][i]] = p[x][sz-1-i];
	}
	for (int i = 1; i <= n; ++i)
		ans += sum(a[i]), add(a[i], 1);
	printf("%lld\n", ans / 2);
	return 0;	
}


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 200100;
ll a[maxn], n, d;
ll f[maxn], g[maxn];

int getf(int l, int r) {
    ll minvalue = LLONG_MAX;
    int ind = 0;
    for(int i=l;i<=r;i++) {
        if(f[i] < minvalue) {
            minvalue = f[i];
            ind = i;
        }
    }
    return ind;
}

int getg(int l, int r) {
    ll minvalue = LLONG_MAX;
    int ind = 0;
    for(int i=l;i<=r;i++) {
        if(g[i] < minvalue) {
            minvalue = g[i];
            ind = i;
        }
    }
    return ind;
}

vector<pair<ll, pair<int,int> > > edges;

void solve(int l, int r) {
    if(l >= r) return;
    else {
        int mid = (l + r) / 2;
        int fi = getf(l, mid);
        int si = getg(mid+1, r);

        for(int i=l;i<=mid;i++) {
            edges.pb(mp(f[i] + g[si], mp(i, si)));
        }
        for(int i=mid+1;i<=r;i++) {
            edges.pb(mp(f[fi] + g[i], mp(fi, i)));
        }

        solve(l, mid);
        solve(mid+1, r);
    }
}
int uparent[maxn];
int usize[maxn];

int ufind(int x) {
    while(uparent[x] != x) {
        x = uparent[x];
    }
    return x;
}

void unite(int x, int y) {
    x = ufind(x);
    y = ufind(y);

    if(x == y) return;

    if(usize[x] > usize[y]) {
        uparent[y] = x;
        usize[x] += usize[y];
    }
    else {
        uparent[x] = y;
        usize[y] += usize[x];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d;
    for(ll i=1LL;i<=n;i++) {
        cin>>a[i];
        f[i] = a[i] - 1LL * i * d;
        g[i] = a[i] + 1LL * i * d;
        uparent[i] = i;
        usize[i] = 1;
    }
    solve(1, n);
    sort(edges.begin(), edges.end());
    ll result = 0LL;
    int br = 0;
    for(auto i:edges) {
        int x = i.second.first;
        int y = i.second.second;
        if(x == y) continue;
        if(ufind(x) != ufind(y)) {
            unite(x, y);
            result += i.first;
            br++;
        }
    }
    cout<<result<<"\n";
    return 0;
}

Measured memory_bytes: 74208
n=gets.to_i
t=gets.split.map{|e|e.to_i*2}
v=gets.split.map{|e|e.to_i*2}
z=[0]*10**5
q=j=s=m=0
n.times{|i|z[j]=[z[j],v[i]].min;(j+1..j=q+=t[i]).each{|k|z[k]=[z[k-1]+1,v[i]].min}}
(j-1).downto(0){|i|s+=m=[m+1,z[i]].min}
p s/4.0

Measured memory_bytes: 2556
#include <iostream>
#include <set>
#include <vector>

using namespace std;

vector<bool> prime(int d) {
  vector<bool> arr(d+1, true);
  arr[0] = arr[1] = false;

  for (int i = 2; i*i <= d; i++) {
    if (!arr[i]) continue;
    for (int j = 2; j*i <= d; j++) {
      if (!arr[j*i]) continue;
      arr[j*i] = false;
    }
  }

  return arr;
}

int main(int argc, char* argv[]) {
  int N; cin >> N;
  
  int m = 0;
  vector<int> input;
  for (int i = 0; i < N; i++) {
    int d; cin >> d;
    input.push_back(d);
    m = max(m, d);
  }

  vector<bool> arr = prime(m);

  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (arr[input[i]]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 13336
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    int maxn = max({a, b, c}), sum = a + b + c;
    if (sum == 2 * maxn)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "ctime"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	cin >> N;
	bool flag = false;
	for (int i = 0; i < N; i++) {
		cin >> M;
		if (M & 1)flag = true;
	}
	if (flag)cout << "first\n";
	else cout << "second\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char c;
  scanf("%c", &c);
  if(c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o')
    printf("vowel\n");
  else
    printf("consonant\n");

}

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

int main() {
  ios::sync_with_stdio(false);
  int N = 13, M = 1e9 + 7;
  vector<int> DP(N);
  DP.at(0) = 1;
  char c;
  while (cin >> c) {
    vector<int> V(N);
    for (int i = 0; i < N; i++) {
      if (c != '?') (V.at((i * 10 + c - '0') % 13) += DP.at(i)) %= M;
      else for (int j = 0; j < 10; j++) {
        (V.at((i * 10 + j) % 13) += DP.at(i)) %= M;
      }
    }
    DP = V;
}

cout << DP.at(5) << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a=0,b=0;
    char *answer; 
    answer= "Yes";
    scanf("%d",&a);
    scanf("%d",&b);
    char s;
    for(int i=0;i<a+b+2;i++){
         char s=getchar();
        if(i==a+1&&s!='-'||i!=a+1&&s=='-'){
          answer="No";
          break;
        }
    }
    printf("%s\n",answer);
    return 0;
}


Measured memory_bytes: 128
// AOJ 0294 Catch a Thief
// 2018.2.14 
// Lengauer-Tarjan algorithm? 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX   100002
#define QSIZE 150000
#define MAGIC 150

int par[MAX], m[MAX];
int parent[MAX], vertex[MAX];
int semi[MAX], idom[MAX], U[MAX];
int **b_to, b_hi[MAX];
int *g_to[MAX], g_hi[MAX], _g_hi[MAX];
int *r_to[MAX], r_hi[MAX], _r_hi[MAX];
int *q, top;

int find(int v) { int r;
	if (par[v] == v) return v;
	r = find(par[v]);
	if (semi[m[v]] > semi[m[par[v]]]) m[v] = m[par[v]];
	return par[v] = r;
}
int eval(int v) { find(v); return m[v]; }
void link(int x, int y) { par[y] = x; }

void tree(int n)
{
	int id, i, j, w, u, v;
	
	for (i = 1; i <= n; i++) par[i] = m[i] = i;

	id = 1, q[0] = 1, top = 1;
	while (top) {
		v = q[--top];
		if (semi[v]) continue;
		semi[v] = id;
		vertex[id++] = v;
		i = g_hi[v]; while (i--) {
			u = g_to[v][i];
			if (!semi[u]) parent[u] = v, q[top++] = u;
		}
	}
	free(q);

	b_to = malloc(n * sizeof(int *));
	b_to[1] = malloc(25000 << 2), b_to[1][0] = 0, u = 25000;
	for (i = 2; i <= n; i++) {
		b_to[i] = malloc(MAGIC << 2);
		b_to[i][0] = u, u += MAGIC;
	}

	for (i = n; i > 1; i--) {
		w = vertex[i];
		for (j = 0; j < r_hi[w]; j++) {
			v = r_to[w][j];
			u = eval(v);
			if (semi[u] < semi[w]) semi[w] = semi[u];
		}
		v = vertex[semi[w]];
		b_to[v][b_hi[v]++] = w;
		u = parent[w], link(u, w);
		for (j = 0; j < b_hi[u]; j++) {
			v = b_to[u][j];
			U[v] = eval(v);
		}
	}
//	free(b_to);

	for (i = 2; i <= n; i++) {
		w = vertex[i];
		u = U[w];
		if (semi[w] == semi[u]) idom[w] = semi[w];
		else idom[w] = idom[u];
	}
	for (i = 2; i <= n; i++) {
		w = vertex[i];
		idom[w] = vertex[idom[w]];
	}
}

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
	int n, m, i, s, t, Q, r;
	
	n = in(), m = in();

	i = m << 2; if (i < QSIZE) i = QSIZE;
	q = malloc(i << 2);
	top = 0; for (i = 0; i < m; i++) {
		s = in(), t = in();
		q[top++] = s, q[top++] = t;
		_g_hi[s]++, _r_hi[t]++;
	}
	for (i = 1; i <= n; i++) {
		g_to[i] = malloc(_g_hi[i] << 2);
		r_to[i] = malloc(_r_hi[i] << 2);
	}
	top = 0; for (i = 0; i < m; i++) {
		s = q[top++], t = q[top++];
		g_to[s][g_hi[s]++] = t;
		r_to[t][r_hi[t]++] = s;
	}

	tree(n);

	Q = in();
	while (Q--) {
		r = in();
		if (idom[r] == 1) printf("%d\n", r);
		else              printf("%d\n", idom[r]);
	}
	return 0;
}


Measured memory_bytes: 74596
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100005
  int N;
vector<int> G[MAX_N];

int solve(int pos,int prev){
  int res=0;
  for(int i=0;i<(int)G[pos].size();i++){
    int to=G[pos][i];
    if(to==prev)continue;
    res^=solve(to,pos);
  }
  return res+1;
}


int main(){
  cin>>N;
  for(int i=0;i<N-1;i++){
    int x,y;
    cin>>x>>y;
    x--,y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  int ans=0;
  for(int i=0;i<(int)G[0].size();i++){
    int x=G[0][i];
    ans^=solve(x,0);
  }
  if(ans>0)cout<<"Alice"<<endl;
  else cout<<"Bob"<<endl;
  return 0;
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
using    namespace std;
#define  ll        long long
#define  pb        push_back
#define  ff        first
#define  ss        second
#define  mk        make_pair
#define  all(v)    v.begin(),v.end()
#define  allr(v)   v.rbegin(),v.rend()
#define  sz        size()
#define  Tanmoy    ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0)

const int MOD=1e9+7;
/*
for(ll i=0; i<n; i++)      **I Want To Be The Best**
for(ll i=n-1; i>=0; i--)
*/

int main()
{
     Tanmoy;

     ll sum=0;
     double n,d,a,b;
     cin>>n>>d;

     for(ll i=0; i<n; i++){
        cin>>a>>b;
        if(sqrt((a*a)+(b*b))<=d)sum++;
     }
     cout<<sum;

  return 0;
}





Measured memory_bytes: 3836
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <bitset>
#include <map>
#include <math.h>
#include <utility>

using namespace std;

const double PI = acos(-1);

int main(){

    string S;
    cin >> S;
    if (S == "ABC") cout << "ARC" << endl;
    if (S == "ARC") cout << "ABC" << endl;

    return 0;
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define rep(begin, end) for (i=begin;i<end;i++)
#define init(arr, val) for (i=0;i<end;i++) arr[i] = val;
#define prlong longlong long(i0, i1) prlong longf("%d %d\n", i0, i1)

using namespace std;
const long long inf = pow(10,13);
const int nil = -1;
int i, j, n, m, k, ans;
int a[200001];
long long dp[200001][3];

int main() {
    scanf(" %d", &n);
    rep(1,n+1) scanf(" %d", &a[i]);
    // even; 0: i/2-1, 1: i/2
    // odd ; 0: (i-1)/2, 1: (i+1)/2
    dp[1][0] = 0;
    dp[1][1] = a[1];
    dp[2][0] = 0;
    dp[2][1] = max(a[1], a[2]);
    rep(3, n+1) {
        if (i%2 == 0) {
            dp[i][0] = max(dp[i-2][0] + a[i], dp[i-1][0]);
            dp[i][1] = max(dp[i-2][1] + a[i], dp[i-1][1]);
        } else {
            dp[i][0] = max(dp[i-2][0] + a[i], dp[i-1][1]);
            dp[i][1] = dp[i-2][1] + a[i];
        }
    }
    if (n%2 == 0) printf("%lld\n", dp[n][1]);
    else printf("%lld\n", dp[n][0]);
}

Measured memory_bytes: 9296
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<utility>
 
using namespace std;
 
int main()
{
    int n,i,low,high,c;
    scanf("%d",&n);
    int p[n];
    for(i=0; i<n; i++)
    {
        scanf("%d",&p[i]);
    }
    low=high=p[0];
    for(i=0; i<n; i++)
    {
        if(low>p[i])
            low=p[i];
        if(high<p[i])
            high=p[i];
    }
    c=high-low;
    printf("%d\n",c);
    return 0;
}

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

using namespace std;

typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

signed main(){

	int N, K;
	vector<P> v;
	vector<int> X, Y;
	cin >> N >> K;
	for (int i = 0; i < N; i++){
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
		X.push_back(a);
		Y.push_back(b);
	}
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	
	int ans = 1LL<<62;
	for (int xl = 0; xl < N; xl++){
		for (int xr = xl + 1; xr < N; xr++){
			for (int yl = 0; yl < N; yl++){
				for (int yr = yl + 1; yr < N; yr++){
					int s = 0;
					for (int i = 0; i < N; i++){
						if (X[xl] <= v[i].first && v[i].first <= X[xr]
							&& Y[yl] <= v[i].second && v[i].second <= Y[yr])
							s++;
					}
					if (s >= K){
						ans = min(ans, (X[xr] - X[xl])*(Y[yr]-Y[yl]));
//						cout << X[xr] << " " << X[xl] << " " << Y[yr] << " " << Y[yl] << " " << (X[xr] - X[xl])*(Y[yr] - Y[yl]) << endl;
					}
				}
			}
		}
	}
	cout << ans << endl;
	

	return 0;
}

Measured memory_bytes: 256
MOD = 10**9+7
def inv_mod(a,p=MOD):
    def inv_mod_sub(a,p):
        if a == 1:
            return 1,0
        else:
            d,r = p//a,p%a
            x,y = inv_mod_sub(r,a)
            return y-d*x,x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n,k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD

def f(a,b):
  return comb_mod(a+b,b)

r1,c1,r2,c2 = map(int,input().split())
f_mod=[1]*(3*10**6)
f_mod_inverse=[1]*(3*10**6)
for i in range(1,3*10**6):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
print((f(r2+1,c2+1)-f(r1,c2+1)-f(r2+1,c1)+f(r1,c1))%MOD)

Measured memory_bytes: 125400
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//const ll mod=998244353;
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;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
V<int> z_algo(const string &s){
    int n=s.size();
    V<int> prefix(n);
    for(int i=1,j=0;i<n;i++){
        if(i+prefix[i-j]<j+prefix[j]){
            //すでに計算済みの場所である
            prefix[i]=prefix[i-j];
        }else{
            // わからないところを愚直に調べる
            int k=max(0,j+prefix[j]-i);
            while(i+k<n&&s[k]==s[i+k])k++;
            prefix[i]=k;
            j=i;
        }
    }
    prefix[0]=n;
    return prefix;
}
V<int> res[5005];
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    for(int i=0;i<n;i++){
        string t=s.substr(i,n-i);
       res[i]=z_algo(t);
    }
    int ans=0;
    for(int i=0;i<n;i++){
    for(int j=1;j<res[i].size();j++){
        //今見ている部分列のj番目より前の文字より長い共通接尾辞は被りがあるので飛ばす
       if(j<res[i][j])continue;
       else chmax(ans,res[i][j]);
    }
    }
    cout<<ans<<"\n";
}

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

int n;
int a[32];

void dfs(int dep,bool h)
{
    if (dep>10) {
        --n;
        if (n==0) {
            int p=0;
            while (a[p]==0) ++p;
            for (int i=p;i<dep;i++) {
                printf("%d",a[i]);
            }
            puts("");
            exit(0);
        }
        return;
    }
    if (h) {
        dfs(dep+1,true);
        for (int i=1;i<=9;i++) {
            a[dep]=i;
            dfs(dep+1,false);
        }
    } else {
        for (int i=max(0,a[dep-1]-1);i<=min(9,a[dep-1]+1);i++) {
            a[dep]=i;
            dfs(dep+1,false);
        }
    }
}

int main()
{
    scanf("%d",&n);
    ++n;
    dfs(1,true);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MAXSTRING 100

int main(int argc,char const* argv[])
{
  string s;
  int n;
  cin >> s;
  n=s.size();
  cout << s[0] << n-2 << s[n-1];
  return 0;
}




Measured memory_bytes: 256
N = int(input())
ans = 0
for i in range(1,min(N,1250000)):
    if(((N-i)/i).is_integer() and N//((N-i)/i) == N%((N-i)/i)):
        # print((N-i)//i,i)
        ans += ((N-i)//i)
        # if(i == 800000):
        #     print(ans)
    # print(i)
print(ans)

Measured memory_bytes: 9240
package main

import (
	"fmt"
  "sort"
)

var N int
var g [8][8]int

// https://play.golang.org/p/ljft9xhOEn
func nextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

func main() {
	var m int
	fmt.Scan(&N, &m)
	var a, b int
	for i := 0; i < m; i++ {
		fmt.Scan(&a, &b)
		g[a-1][b-1] = 1
		g[b-1][a-1] = 1
	}
	v := make([]int, N)
  for i := 0; i < N; i++ {
    v[i] = i
  }

  ans := 0
  for {
    ok := true
    for i := 0; i < N - 1; i++ {
      if g[v[i]][v[i + 1]] != 1 {
        ok = false
        break
      }
    }
    if ok {
      ans++
    }
    if !nextPermutation(sort.IntSlice(v[1:])) {
      break
    }
  }
  fmt.Println(ans)
}


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

int main()
{
    int a,b,c;
    int n;
    scanf("%d%d%d",&a,&b,&c);
    scanf("%d",&n);
    if(a>b){
       if(b>c){
        a=a*pow(2,n);
       }
       else{
        if(a>c){
            a=a*pow(2,n);
        }
        else{
            c=c*pow(2,n);
        }
       }
    }
    else{
        if(a>c){
            b=b*pow(2,n);
        }
        else{
            if(c<b){
                b=b*pow(2,n);
            }
            else{
                c=c*pow(2,n);
            }
        }
    }
    cout<<a+b+c<<endl;
    return 0;
}


Measured memory_bytes: 256
/* BISMILLAHIR RAHMANIR RAHIM */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() 
{
	ios_base :: sync_with_stdio(0);  
	ll n, k;
	cin >> n >> k;
	ll res = k;
	for(ll i = 1; i < n; i++) {
		res *= (k - 1);
	}
	cout << res << "\n";
	return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque

input = sys.stdin.readline


def dfs(G, v, p, counter):
    stack = deque([(v, p)])
    while stack:
        v, p = stack.pop()
        for c in G[v]:
            if c == p:
                continue
            counter[c] += counter[v]
            stack.append((c, v))


def main():
    N, Q = map(int, input().split())

    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    dfs(G, 0, -1, counter)

    print(*counter)


if __name__ == "__main__":
    main()


Measured memory_bytes: 62224
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define N 100001
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
 
typedef long long ll;

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

    int minm1 = INT_MAX;

    int minm2 = INT_MAX;

    int dp1[n],dp2[n];
     
    for(int i=0;i<n;i++){
        dp1[i]=0;
        dp2[i]=0;
    }

    if(s[0]=='W'){
        dp1[0]=1;
    }
    else{
        dp1[0]=0;
    }
    for(int i=1;i<n;i++){
        if(s[i]=='W'){
            dp1[i] = dp1[i-1]+1;
        }
        else{
            dp1[i] = dp1[i-1];
        }
    }

    if(s[n-1]=='R'){
        dp2[n-1]=1;
    }
    else{
        dp2[n-1]=0;
    }

    for(int i=(n-2);i>=0;i--){
        if(s[i]=='R'){
            dp2[i] = dp2[i+1]+1;
        }
        else{
            dp2[i] = dp2[i+1];
        }
    }
    minm1 = min(minm1,min(dp1[n-1],dp2[0]));
    minm2 = min(minm2,max(dp1[n-1],dp2[0]));

    for(int i=0;i<n-1;i++){
        minm1=min(minm1,(dp1[i]+dp2[i+1]));
        minm2=min(minm2,max(dp1[i],dp2[i+1]));
    }

    cout<<min(minm1,minm2);

    return 0;
}

Measured memory_bytes: 5304
#include <stdio.h>
#include <algorithm>

using namespace std;

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

int main() {

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

    int X[N], temp[N];
    REP(i, N) {
        scanf("%d", &X[i]);
        temp[i] = X[i];
    }

    sort(X, X + N);

    int l = X[N / 2 - 1];
    int r = X[N / 2];
    REP(i, N) {
        if (temp[i] <= l) {
            printf("%d\n", r);
        } else {
            printf("%d\n", l);
        }
    }

    return 0;
}


Measured memory_bytes: 3712
N = int(input())
S = input()
c = '0'
ans = 0

for i in range(N):
    if c == S[i]:
        continue

    elif i == N-1:
        ans += 1

    else:
        c = '0'

        if S[i] == S[i+1]:
            c = S[i]
            ans += 1

        else:
            ans += 1

print(ans)

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

int main(){
  int n;
  cin >> n;
  string b;
  vector<int> a(4);
  for(int i=0;i<n;i++){
    cin >> b;
    if(b == "AC") a.at(0)++;
    else if(b == "WA") a.at(1)++;
    else if(b == "TLE") a.at(2)++;
    else a.at(3)++;
  }
  
  cout << "AC x" << ' ' << a.at(0) << endl;
  cout << "WA x" << ' ' << a.at(1) << endl;
  cout << "TLE x" << ' ' << a.at(2) << endl;
  cout << "RE x" << ' ' << a.at(3) << endl;
  
  return 0;
}


Measured memory_bytes: 3600
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
 
long long mg(int A[],int l,int m,int r){
  long long cnt=0;
  int n1=m-l,n2=r-m;
  int L[n1+1],R[n2+1];
  for(int i=0;i<n1;i++)L[i]=A[l+i];
  for(int i=0;i<n2;i++)R[i]=A[m+i];
  L[n1]=1000000001,R[n2]=1000000001;
  int i=0,j=0;
  for(int k=l;k<r;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
      cnt+= (long long)n1- (long long)i;
    }
  }
  return cnt;
}
 
long long mgs(int A[],int l,int r){
  long long cnt=0;
  if(l+1<r){
    int m=(l+r)/2;
    cnt+=mgs(A,l,m);
    cnt+=mgs(A,m,r);
    cnt+=mg(A,l,m,r);
  }
  return cnt;
}
 
int main(){
  int n,A[200000];
  long long cnt;
  cin>>n;
  for(int i=0;i<n;i++)scanf("%d",&A[i]);
  cnt=mgs(A,0,n);
  cout<<cnt<<endl;
  return 0;
}

Measured memory_bytes: 4792