akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for(int i = 0; i < n; ++i)  cin >> h[i];
    sort(h.begin(), h.end());
    int ans = INF;
    for(int i = 0; i + k <= n; ++i) chmin(ans, h[i + k - 1] - h[i]);
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef pair<l_l,ll> lll;
typedef vector<string> vs;
const ll dx[4]={1,-1,0,0};
const ll dy[4]={0,0,1,-1};
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
//グリッド：（典型）dp,dfs,bfs,最短経路,その他
const int mod = 1000000007;
struct mint {
ll x;
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 {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
ll n;
vl g[110000];
mint dp[110000][2];
void dfs(ll now,ll last=-1){
    dp[now][0]=1;
    dp[now][1]=1;
    for(auto next:g[now]){
        if(last==next)continue;
        dfs(next,now);
        dp[now][0]=dp[now][0]*(dp[next][0]+dp[next][1]);
        dp[now][1]=dp[now][1]*dp[next][0];
    }
    return;
}
int main(){
    cin>>n;
    rep(i,n-1){
        ll u,v;cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    mint ans=dp[1][0]+dp[1][1];
    cout<<ans.x<<endl;
    return 0;
}

Measured memory_bytes: 17820
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

s = ns()

stack = []
ans = 0

for si in s:
    if len(stack) == 0 or si == stack[-1]:
        stack.append(si)
    else:
        stack.pop()
        ans += 2
        
print(ans)

Measured memory_bytes: 3964
N = int(input())
X = input()

popcnt = X.count('1')

if popcnt == 0:
    for _ in range(N):
        print(1)
    exit()

pop1 = popcnt + 1
pop2 = popcnt - 1

x_int = int(X, base = 2)
x_mod_pop1 = x_int % pop1
if pop2 != 0:
    x_mod_pop2 = x_int % pop2

for i, c in enumerate(X):
    if c == '1':
        if popcnt == 1:
            print(0)
        else:
            mod = x_mod_pop2 - pow(2, N-i-1, pop2) 
            mod %= pop2
            c = 1
            while mod:
                mod %= format(mod, 'b').count('1')
                c += 1
            print(c)
    else:
        mod = x_mod_pop1 + pow(2, N-i-1, pop1) 
        mod %= pop1
        c = 1
        while mod:
            mod %= format(mod, 'b').count('1')
            c += 1
        print(c)


Measured memory_bytes: 79820
#include<stdio.h>
int  main(){

int N,M;
int n[1001]={};

while(1)
{
int s=0;
scanf("%d %d",&N,&M);
if(N==0&&M==0)break;

for(int i=1;i<=N;i++)
scanf("%d",&n[i]);

for(int i=1;i<=N;i++)
for(int j=N;j>i;j--)
if(n[j]>n[j-1]){int t=n[j-1];n[j-1]=n[j];n[j]=t;}

for(int i=1;i<=N;i++)
{if(i%M!=0)s+=n[i];}

printf("%d\n",s);
}

return 0;
}

Measured memory_bytes: 1028
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B, C = get_ints

set = Set.new
set.add(A)
set.add(B)
set.add(C)

if set.length == 2
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 14228
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace ARC093C
{
    public class Program
    {
        void Solve(StreamScanner ss, StreamWriter sw)
        {
            //---------------------------------
            var N = ss.Next(int.Parse);
            var A = ss.Next(long.Parse, N);

            var plan = new[] {0L}.Concat(A).Concat(new[] {0L}).ToArray();

            var cost = 0L;
            for (var i = 1; i < N + 2; i++)
            {
                cost += Math.Abs(plan[i - 1] - plan[i]);
            }

            for (var i = 1; i <= N; i++)
            {
                var via = Math.Abs(plan[i - 1] - plan[i]) + Math.Abs(plan[i] - plan[i + 1]);
                var through = Math.Abs(plan[i - 1] - plan[i + 1]);
                sw.WriteLine(cost - via + through);
            }
            //---------------------------------
        }

        static void Main()
        {
            var ss = new StreamScanner(new StreamReader(Console.OpenStandardInput()));
            var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            new Program().Solve(ss, sw);
            sw.Flush();
        }

        static readonly Func<string, string> String = s => s;
    }

    public class StreamScanner
    {
        static readonly char[] Sep = {' '};
        readonly Queue<string> buffer = new Queue<string>();
        readonly TextReader textReader;

        public StreamScanner(TextReader textReader)
        {
            this.textReader = textReader;
        }

        public T Next<T>(Func<string, T> parser)
        {
            if (buffer.Count != 0) return parser(buffer.Dequeue());
            var nextStrings = textReader.ReadLine().Split(Sep, StringSplitOptions.RemoveEmptyEntries);
            foreach (var nextString in nextStrings) buffer.Enqueue(nextString);
            return Next(parser);
        }

        public T[] Next<T>(Func<string, T> parser, int x)
        {
            var ret = new T[x];
            for (var i = 0; i < x; ++i) ret[i] = Next(parser);
            return ret;
        }

        public T[][] Next<T>(Func<string, T> parser, int x, int y)
        {
            var ret = new T[y][];
            for (var i = 0; i < y; ++i) ret[i] = Next(parser, x);
            return ret;
        }
    }
}

Measured memory_bytes: 31068
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S: str, T: str):
    print( YES if T in [ S[i:]+S[:i] for i,s in enumerate(S) ] else NO )

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int dx[] = {-1, 0,+1, 0};
int dy[] = { 0,+1, 0,-1};

int node[32][32],v[32][32];

int main()
{
	int w,h,c;
	while(cin >> w >> h, (w||h))
	{
		memset(v,0,sizeof(v));
		memset(node,0,sizeof(node));

		for(int l=0; l<2*h-1; l++)
		{
			int y=l/2;

			if(l%2)
			{
				for(int x=0; x<w; x++)
				{
					cin >> c;
					if(c==0)
					{
						node[x][y]   |= 1<<1;
						node[x][y+1] |= 1<<3;
					}
				}
			}
			else
			{
				for(int x=0; x<w-1; x++)
				{
					cin >> c;
					if(c==0)
					{
						node[x]  [y] |= 1<<2;
						node[x+1][y] |= 1<<0;
					}
				}
			}
		}

		queue<int> q; q.push(0); q.push(0);

		int ans=0,tim=0;
		while(!q.empty())
		{
			tim++;

			int qlen = q.size()/2;
			for(int j=0; j<qlen; j++)
			{
				int px = q.front(); q.pop();
				int py = q.front(); q.pop();
				if(px==w-1 && py==h-1)
				{
					ans=tim; break;
				}
				v[px][py] = 1;

				for(int i=0; i<4; i++)
				{
					if(node[px][py] & (1<<i))
					{
						int nx = px+dx[i];
						int ny = py+dy[i];

						if(!v[nx][ny])
						{
							q.push(nx);
							q.push(ny);
							v[nx][ny] = 1;
						}
					}
				}
			}

			if(ans) break;
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 920
#include<iostream>
#include<algorithm>
using namespace std;
string N;
int K,D[10];

int find_least(char n){
	char i=n;
	while(i <= '9' && D[i-'0'] > 0) i++;
	return D[i-'0'] > 0 ? -1 : i;
}

int main(){
	cin >> N >> K;
	for(int i=0; i<K; i++){
		int d;
		cin >> d;
		D[d] = 1;
	}

	string ans;

	char l = find_least('0');
	char m = find_least('1');
	if(find_least(N[0]) < 0){
		ans += m;
		for(int j=0; j<N.size(); j++) ans += l;
		cout << ans << endl;
		return 0;
	}
	int i=0;
	while(i < N.size() && D[N[i]-'0'] == 0){
		ans += N[i];
		i++;
	}
	if(D[N[i]-'0'] == 0) {
		cout << ans << endl;
		return 0;
	}
	while(i > 0 && find_least(N[i]+1) < 0) {
		i--;
		ans.erase(i,1);
	}
	if(i == 0 && find_least(N[0]+1) < 0){
		ans += m;
		for(int j=0; j<N.size(); j++) ans += l;
		cout << ans << endl;
		return 0;
	}
	ans += find_least(N[i++]+1);
	while(i < N.size()) {
		ans += l;
		i++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int a, b, c, m;
    int array [3];
    cin >> a >> b>>c;
    if (a<= b && a <= c){
        m = a;
        if (b<=c){
            m+=b;
        }
        else {
            m+=c;
        }
    }
    if (b<=a&&b<=c){
        m = b;
        if (a<=c){
            m+=a;
        }
        else {
            m+=c;
        }
    }
    if (c<=a&&c<=b){
        m =c;
        if (a<= b){
            m+=a;
        }
        else {
            m+=b;
        }
    }
    cout << m;
    
    
    return 0;
}

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

string t1, t2, s;
int r1, r2 = 1;

int solve(string t){
	int res = 0;
	for (int i = 0; i < s.size(); i++)
		if(s[i] != t[i])
			res++;
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> s;
	for (int i = 0; i < s.size(); i++){
		t1 += (char)('0' + r1);
		t2 += (char)('0' + r2);
		r1 = 1 - r1;
		r2 = 1 - r2;
	}
	
	cout << min(solve(t1), solve(t2));
}

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

using ll = long long;

#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    string res = "";
    REP(i, 0, sz(s)) {
    	if(s[i] == 'g') s[i] = 'r';
    	res += 'p';
    }
    int p = 0, r = 0;
    vector<int> v[2];
    REP(i, 0, sz(s)) {
    	if(s[i] == 'r') {
    		v[0].pb(i);
    	} else {
    		v[1].pb(i);
    	}
    	++p;
    	if(p > r) {
    		while(p > r && !v[1].empty()) {
    			res[v[1].back()] = 'r';
    			v[1].pop_back();
    			--p;
    			++r;
    		}
    		while(p > r && !v[0].empty()) {
    			res[v[0].back()] = 'r';
    			v[0].pop_back();
    			--p;
    			++r;
    		}
    	}
    }
    int bad = 0, good = 0;
    REP(i, 0, sz(s)) {
    	if(s[i] == 'p' && res[i] == 'r') ++bad; 
    	if(s[i] == 'r' && res[i] == 'p') ++good;
    }
    cout << good - bad << "\n";
    return 0;
}


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

using namespace std;

void insertionSort(vector<double> &a, int g, long &cnt)
{
	int j;
	double v;
	for (int i = g; i < a.size(); i++)
	{
		v = a[i];
		j = i - g;
		while (j >= 0 && a[j] > v)
		{
			a[j + g] = a[j];
			j = j - g;
			cnt++;
			if (cnt > (int)pow(a.size(), 1.5))
			{
				return;
			}
		}
		a[j + g] = v;
	}
}

int shellSort(vector<double> &a, vector<int> &g)
{
	long cnt = 0;
	for (int i = 0; i < g.size(); i++)
	{
		insertionSort(a, g[i], cnt);
		if (cnt > (int)pow(a.size(), 1.5))
		{
			break;
		}
	}
	return cnt;
}

int main()
{
	int n;
	long cnt;
	cin >> n;
	vector<double> a(n, 0);
	vector<double> org(a);
	vector<int> g;
	for (int i = 0; i < n; i++)
	{
		cin >> org[i];
	}
	for (int m = 100; m >= 1; m--)
	{
		a = org;
		g.resize(m, 1);
		for (int i = 0; i < m; i++)
		{
			g[i] = (pow(3, m - i) - 1) / 2;
		}
		if (g[0] < 0 || n < g[0])
		{
			continue;
		}
		else
		{
			cnt = shellSort(a, g);
			if (cnt <= pow(n, 1.5))
			{
				break;
			}
		}
	}
	cout << setprecision(10) << g.size() << endl;
	for (int i = 0; i < g.size(); i++)
	{
		cout << g[i];
		if (i == g.size() - 1)
		{
			cout << endl;
		}
		else
		{
			cout << " ";
		}
	}
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
}


Measured memory_bytes: 18384
#include <bits/stdc++.h>
using namespace std;
int round(int n, int m){
	if (n%m==0) return n/m;
	else return int(n/m+1);
}
int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (d==0){
		cout << "Yes" << endl;
		return 0;
	}
	if (b==0){
		cout << "No" << endl;
		return 0;
	}
	int x=round(c, b), y=round(a, d);
	if (x<=y){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

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

typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define ALL(obj) (obj).begin(), (obj).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int dy[]={0, 0, 1, -1, 1, -1, -1, 1};
int dx[]={1, -1, 0, 0, 1, 1, -1, -1};


int main() {
    cout<<fixed<<setprecision(10);

    ll x; cin>>x;
    ll y = 2000 - x;
    ll ans = 1 + y/200 - (ll)(y%200==0);
    cout<<ans<<endl;

    return 0;

}

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

typedef long long ll;

int main(void){
  int n,m;
  cin >> n >> m;
  priority_queue<int> q;

  for(int i = 0; i < n ; ++i){
    int a;
    cin >> a;
    q.push(a);
  }

  for(int i = 0; i < m ; ++i){
    int a = q.top();
    q.pop();
    q.push(a/2);
  }

  ll ans = 0;
  for(int i = 0; i < n ; ++i){
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 892
#include<cstdio>
using namespace std;
int main(void)
{
	int h,w,i,j,cnt;
	scanf("%d %d",&h,&w);
	while(!(h==0 && w==0)){
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
		scanf("%d %d",&h,&w);
	}
	return 0;
}
	

Measured memory_bytes: 1000
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1LL << 60
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const long long MOD=1000000007;

// vector<p> cut(M); vector<vector<ll> > v(4);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
// for(int i=0; i<N;i++){
// }
// sort(cut.begin(),cut.end()), sort(v.rbegin(), v.rend()); //sort
// char '' str ""
int main(void)
{
    int N; cin>>N; int ans;
    for(int i=1;i<100000;i++){
      if(i*i > N){
        ans = (i-1)*(i-1);

            cout<<ans<<endl;
        return 0;
      }
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100005
#define NIL -1

struct Node{ int p, l, r;};
struct Node T[MAX];
int n, H, D[MAX];

int getDepth(int u){
  int d = 0;

  while(T[u].p >= 0){
    u = T[u].p; 
    d++;
  }

  return d;
}

void print(int u){
  if(T[u].p == NIL)
    printf("node %d: parent = %d, depth = %d, root, ",u,T[u].p,D[u]);
  
  else if(T[u].l == NIL)
    printf("node %d: parent = %d, depth = %d, leaf, ",u,T[u].p,D[u]);
  
  
  else printf("node %d: parent = %d, depth = %d, internal node, ",u,T[u].p,D[u]);
  
  
  printf("[");
  int t; 
  t = u;
  if(T[t].l  != NIL){
    printf("%d",T[t].l);
    if(T[T[t].l].r == NIL)
      printf("]\n");
    else printf(",");
    t =T[t].l;
    while(T[t].r != NIL){
      printf(" %d",T[t].r);

      if(T[T[t].r].r == NIL)
	printf("]\n");
      else printf(",");
      t =T[t].r;
    }
  }
  else  printf("]\n");
}

main(){
  int i, j, d, v, c,l,r;
  
  scanf("%d",&n);
  
  for ( i = 0; i < n; i++ ) {
    T[i].p = T[i].l = T[i].r = NIL;
  }
  
   for ( i = 0; i < n; i++ ){
    scanf("%d %d", &v, &d);
    for ( j = 0; j < d; j++ ){
      scanf("%d", &c);
      //make tree
      T[c].p = v;
      
      if(j == 0) T[v].l = c;
      
      else if (j >= 1)
	T[r].r = c;
      r = c;
      }
    }
  

  for ( i = 0; i < n; i++ ){
    D[i] = getDepth(i);
  }

  for ( i = 0; i < n; i++ ) print(i);
  return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main(){
        map<int,long> mp;
        int n,a;
        cin>>n>>a;
        for(int i=0;i<n;i++){
                int t;
                cin>>t;
                map<int,long> temp;
                for(auto x:mp){
                        int tag=x.first+t-a;
                        if(mp.find(tag)==end(mp))
                                temp[tag]=x.second;
                        else
                                temp[tag]=mp[tag]+x.second;
                }
                for(auto x:temp)
                        mp[x.first]=x.second;
                if(mp.find(t-a)==end(mp))
                        mp[t-a]=1;
                else
                        mp[t-a]++;
        }
        cout<<mp[0];
}

Measured memory_bytes: 384
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or d < dst[nh][nw]:
            dq.appendleft((nh, nw, d))
            dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        if dst[nh][nw] == -1 or d + 1 < dst[nh][nw]:
            dq.append((nh, nw, d + 1))
            dst[nh][nw] = d + 1

print(dst[eh][ew])


Measured memory_bytes: 94996
def calc(pp,x,y):
    p = 0
    for i in range(1,1000):
        if i*(100+x)/100 == pp:
            p = i
            break
    return p*(100+y)/100

while True:
    max = 0
    x,y,s = map(int,raw_input().split())
    if x == 0 and y == 0 and s == 0:
        break
    for i in range(1,s):
        for j in range(i,s):
            if i + j != s:
                continue
            if max < calc(i,x,y)+calc(j,x,y):
                max = calc(i,x,y)+calc(j,x,y)
    print max

Measured memory_bytes: 4296
#include <iostream>
#include <queue>
#include <vector>

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

using namespace std;

const int INF = 1000000000;

typedef int Weight;
struct Edge{
  int src, dest; Weight weight;
  //bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

// Dijkstra (Verified: AOJ2005)
// dの要素数は頂点数と等しくあるべき．
void dijkstra(Graph &g, Array &d, int s) {
  fill(d.begin(), d.end(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}


int main()
{
  while(1){
    int n,m,l;
    cin>>n>>m>>l;
    if(!n)break;
    Graph g((n+1)*(l+2));
    REP(i,m){
      int a,b,d,e;
      cin>>a>>b>>d>>e;
      --a;--b;
      REP(j,l+1){
        int s=a*(l+1)+j;
        int t=b*(l+1)+j;
        g[s].push_back({s,t,e});
        g[t].push_back({t,s,e});
        if(j+d<=l){
          g[s].push_back({s,t+d,0});
          g[t].push_back({t,s+d,0});
        }
      }
    }
    Array a((n+1)*(l+2));
    dijkstra(g, a, 0);
    int minn = 1000000000;
    REP(i,l+1){
      minn=min(minn,a[(n-1)*(l+1)+i]);
    }
    cout<<minn<<endl;
  }
  return 0;
}

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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

using ll = long long;
using ull = unsigned long long;

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);

// ================ Main Loop ================
int main() {
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;

    m1 += h1 * 60;
    m2 += h2 * 60;
    cout << abs(m1 - m2) - k << endl;
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <regex>
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pl4 = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using vvs = vector<vs>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpl4 = vector<pl4>;
using vvpl4 = vector<vpl4>;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) sort((a).rbegin(),(a).rend())
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define PREVP(a) prev_permutation((a).begin(),(a).end())
#define NEXTP(a) next_permutation((a).begin(),(a).end())
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Say(a) cout <<(a);
#define Sal(a) cout <<(a)<<endl;
#define dbg(a) cout <<(#a)<<": "<<(a)<<endl;
#define a2l(a) ((ll)(a-97))
#define A2l(a) ((ll)(a-65))
#define l2a(a) ((char)(a+97))
#define l2A(a) ((char)(a+65))

#define int ll

const ll MOD = 1e9+7;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll min(ll a, ll b){if(a>=b) return b;if(a<b) return a;}
ll max(ll a, ll b){if(a>=b) return a;if(a<b) return b;}

ll isP(ll n){
    if(n<=1) return 0;
    FOR(i,2,(ll)sqrt(n)){
        if(n%i==0) return 0;
    }
    return 1;
}

ll BinS(vll a,ll b){
    ll min=0,max=a.size()-1,mid=0;;
    while(1){
        mid=(min+max)/2;
        if(a[min]==b) return min;
        if(a[mid]==b) return mid;
        if(a[max]==b) return max;
        if(max-min<=2) return -1;
        if(a[mid]<b) min=mid;
        if(a[mid]>b) max=mid;
    }
}

//seiki
//#include <regex>
/*bubun*/
//regex_search("u32", regex("[0-9]"));      // true
/*kanzen*/
//regex_match("u32", regex("(i|u)\\d+"));   // true

signed main() {
    
    ll cnt=0;
    string S;
    cin >>S;
    FOR(i,0,3){
        if(S[i]=='+') cnt++;
        if(S[i]=='-') cnt--;
    }
    Sal(cnt);
    
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn];
int mx=-1;
int flag=0,ans;
int cnt=0;

int cmp(int x,int y)
{
	return x>y;
}

int main()
{
	int n,h;
	int sum=0;
	scanf("%d%d",&n,&h);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		if(a[i]>mx) mx=a[i];
	}
	sort(b,b+n,cmp);
	for(int i=0;i<n;i++)
	{
		if(b[i]>mx)
		{
			sum+=b[i];
			cnt++;
		}
		if(sum>=h)
		{
			printf("%d\n",cnt);
			flag=1;
			break;
		}
	}
	if(flag==0)
	{
		ans=(h-sum)/mx;
		if(ans*mx==h-sum) printf("%d\n",ans+cnt);
		else printf("%d\n",ans+cnt+1);
	}
	return 0;
}

Measured memory_bytes: 896
#include<stdio.h>

int main(void)
{
    int a,b,c,d;
    scanf("%d %d %d",&a,&b,&c);
    if(b<c){
        d=b;
        b=c;
        c=d;
    }
    if (a<b){
        d=a;
        a=b;
        b=d;
    }
    if(b<c){
        d=b;
        b=c;
        c=d;
    }
    printf("%d",a-c);
    
}

Measured memory_bytes: 128
N = int(input())
t = list(range(N+1))
for i in range(2, N+1):
    x = t[i-1] + 1
    p6, p9 = 6, 9
    while i-p6 >= 0:
        x = min(x, t[i-p6] + 1)
        p6 *= 6
    while i-p9 >= 0:
        x = min(x, t[i-p9] + 1)
        p9 *= 9
    t[i] = x
print(t[N])


Measured memory_bytes: 6900
#include<stdio.h>
#include<iostream>
#include<math.h> 
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,k,q,b;
ll a[100000+100];
int main()
{
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++)
	{
		a[i]=k;
	}
	for(int i=1;i<=q;i++)
	{
		cin>>b;
		a[b]++;
	}
	if(q<k)
	{
		for(int i=1;i<=n;i++)
		printf("Yes\n");
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(a[i]-q<=0)
			printf("No\n");
			else
			printf("Yes\n");
		}	
	}
	return 0;
}


Measured memory_bytes: 1408
#!/usr/bin/env python3


# import numpy as np

N, A, B, C = list(map(int, input().split()))
L = [int(input()) for _ in range(N)]


inf = 10**9


def dfs(cur, a, b, c):
    if cur == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else inf

    ret0 = dfs(cur + 1, a, b, c)
    ret1 = dfs(cur + 1, a + L[cur], b, c) + 10
    ret2 = dfs(cur + 1, a, b + L[cur], c) + 10
    ret3 = dfs(cur + 1, a, b, c + L[cur]) + 10

    return min(ret0, ret1, ret2, ret3)


print(dfs(0, 0, 0, 0))
# ans = 1000
# for i in itertools.product([0, 1, 2, 3], repeat=n):

#     ans_tmp = 0
#     counter = collections.Counter(i)
#     print(counter)
#     if not((1 in counter) and (2 in counter) and (3 in counter)):
#         continue

#     length = [a, b, c]

#     for index, opt in enumerate(i):
#         if opt != 0:
#             length[opt-1] += L[index]

#     print(length)
#     ans_tmp += (counter[1]-1)*10
#     ans_tmp += (counter[2]-1)*10
#     ans_tmp += (counter[3]-1)*10

#     ans_tmp += abs(a - length[0])
#     ans_tmp += abs(b - length[1])
#     ans_tmp += abs(c - length[2])

#     ans = min(ans, ans_tmp)

# print(ans)


Measured memory_bytes: 3064
#include<algorithm>
#include<cstdio>
#include<functional>
#include<iostream>
#include<cfloat>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<time.h>
#include<vector>
using namespace std;
int n,h;
int a[100100];
int b[100100];
int main(){
  cin >> n >> h;
  int maxa=-1;
  for (int i=1;i<=n;i++){
    cin >> a[i] >> b[i];
    maxa=max(maxa,a[i]);
  }
  sort(b+1,b+n+1);
  int c=n;
  int t=0;
  while(h>0){
    if (c && b[c]>maxa){
      h-=b[c--];
      t++;
    }else{
      t+=h/maxa;
      if (h%maxa) t++;
      break;
    }
  }
  cout << t << endl;
  system ("pause");
  return 0;
}

Measured memory_bytes: 1272
#if 0

#endif
#include <iostream>
#include <memory>
#include <vector>
#include <string>
#include <algorithm>
#include <assert.h>
#include <complex>
#include <queue>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
using ll = long long;
ll ll_max = numeric_limits<ll>::max();
ll ll_min = numeric_limits<ll>::min();
int int_max = numeric_limits<int>::max();
int int_min = numeric_limits<int>::min();
ll N;
ll a[100];
ll total = 0;
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(n, N) {
        cin >> a[n];
        total += a[n];
    }
    double ave = total / (double)N;
    double min_ab = numeric_limits<double>::max();
    ll ret = 0;
    rep(n, N) {
        if (min_ab > fabs(ave - a[n])) {
            min_ab = fabs(ave - a[n]);
            ret = n;
        }
    }
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
struct data{
	int x,y,dir,t;
	data(){}
	data(int xx,int yy,int dd,int tt){
		x=xx;
		y=yy;
		dir=dd;
		t=tt;
	}
};

int res=6;
int fie[6][4][4];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void bubble(int c){
	queue<data> que;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(fie[c][i][j]>=5){
				fie[c][i][j]=0;
				for(int k=0;k<4;k++){
					que.push(data(j,i,k,0));
				}
			}
		}
	}
	int prev=0;
	while(que.size()){
		data q=que.front();
		if(prev!=q.t){
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					if(fie[c][i][j]>=5){
						fie[c][i][j]=0;
						for(int k=0;k<4;k++){
							que.push(data(j,i,k,q.t+1));
						}
					}
				}
			}
		}
		prev=q.t;
		que.pop();
		int nx=q.x+dx[q.dir],ny=q.y+dy[q.dir];
		if(nx<0 || nx>=4 || ny<0 || ny>=4)continue;
		if(fie[c][ny][nx]>0){
			fie[c][ny][nx]++;
			if(fie[c][ny][nx]>=5)que.push(data(-5,-5,0,q.t+1));
		}else que.push(data(nx,ny,q.dir,q.t+1));
	}
}

void dfs(int cnt){
	if(res<=cnt)return;
	bool flag=true;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(fie[cnt][i][j]>0)flag=false;
		}
	}
	if(flag){
		res=cnt;
		return;
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			fie[cnt][i][j]++;
			for(int k=0;k<4;k++){
				for(int l=0;l<4;l++){
					fie[cnt+1][k][l]=fie[cnt][k][l];
				}
			}
			bubble(cnt+1);
			dfs(cnt+1);
			fie[cnt][i][j]--;
		}
	}
}

int main(void){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			scanf("%d",&fie[0][i][j]);
		}
	}
	dfs(0);
	printf("%d\n",res==6?-1:res);
	return 0;
}

Measured memory_bytes: 1036
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; ++i)
#define ll long long int
#define vi vector<int>

using namespace std;

bool cmp(int a, int b)
{
    int s = a%10;
    if(s == 0) s = 11;
    int t = b%10;
    if(t == 0) t == 11;
    return s < t;
}

int main()
{
    vi a(5,0);
    for(int i = 0; i < 5; i++)
    {
        cin >> a.at(i);
    }
    sort(a.begin(), a.end(), cmp);
    int sum = 0;
    for(int i = 4; i > 0; i--)
    {
        sum += a.at(i);
        if(sum %10)
        {
            sum = ((sum/10)+1)*10;
        }
    }
    cout << sum+a.at(0);

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef unsigned long long int   ull;
typedef long long int            ll;
#define pi                 acos(-1);
int main()
{
    string a;
    cin>>a;
    if(a=="ABC")
        cout<<"ARC"<<endl;
    else if(a=="ARC")
        cout<<"ABC"<<endl;
    return 0;
}


Measured memory_bytes: 3628
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
		if len(os.Args) > 2 {
			wfp, _ = os.Create(os.Args[2])
		}
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)

	if n%2 == 0 {
		fmt.Fprintln(writer, (n-2)*n/2)
		for i := 1; i < n; i++ {
			for j := i + 1; j < n+1; j++ {
				if i+j == n+1 {
					continue
				}
				fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, j))
			}
		}
	} else {
		fmt.Fprintln(writer, ((n-2)*n+1)/2)
		for i := 1; i < n; i++ {
			for j := i + 1; j < n+1; j++ {
				if i+j == n {
					continue
				}
				fmt.Fprintln(writer, fmt.Sprintf("%d %d", i, j))
			}
		}
	}

	writer.Flush()
}


Measured memory_bytes: 896
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC122C
{
    class Program
    {
        static void Main(string[] args)
        {
            var nq = Console.ReadLine().Split(' ');
            var n = int.Parse(nq[0]);
            var q = int.Parse(nq[1]);
            var s = Console.ReadLine();

            var c = new int[n];

            for (int i = 0; i < n - 1; i++)
            {
                c[i + 1] = c[i];
                if(s[i] == 'A' && s[i + 1] == 'C')
                {
                    c[i + 1]++;
                }
            }
            

            foreach(var i in Enumerable.Range(0, q))
            {
                var lr = Console.ReadLine().Split(' ');
                var l = int.Parse(lr[0]);
                var r = int.Parse(lr[1]);

                Console.WriteLine(c[r - 1] - c[l - 1]);

            }
        }
    }
}


Measured memory_bytes: 16456
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

X, K, D = getNM()
X = abs(X)
time = X // D

if K < time:
    print(abs(X - (D * K)))
    exit()
elif (K - time) % 2 == 0:
    print(abs(X - (D * time)))
    exit()
else:
    print(abs((D * (time + 1)) - X))
    exit()

Measured memory_bytes: 78096
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

int main(void){
    ll n, k;
    cin >> n >> k;

    ll sum = 0;
    rep(i, 1, n + 1){
        if(i <= k){
            continue;
        }else{
            sum += (n / i - 1) * (i - k);
            if(k != 0){
                if(n % i - k + 1 > 0){
                    sum += n % i - k + 1;
                }
            }else{
                if(n % i - k > 0){
                    sum += n % i - k;
                }
            }
            sum += i - k;
        }
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"strings"
	"bufio"
	"os"
)

func main(){
	var s, char string
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	s = sc.Text()
	alphabet := "abcdefghijklmnopqrstuvwxyz"
	for _, i := range s{
		char = string(i)
		if strings.Contains(alphabet, char){
			char = strings.ToUpper(char)
		} else {
			char = strings.ToLower(char)
		}
		fmt.Print(char)
	}
	fmt.Print("\n")
}


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


const int MOD=1e9+7;

typedef long long ll;

int main()
{
    int n,m;
    cin>>n>>m;
    if(n<m)swap(n,m);
    if(abs(n-m)>=2){
        cout<<0;
        return 0;
    }
    ll ans=1;

        for(int i=1;i<=n;i++){
            ans*=i;
            ans%=MOD;
        }
        for(int i=1;i<=m;i++){
            ans*=i;
            ans%=MOD;
        }
        if(n==m){
            ans*=2;
            ans%=MOD;
        }
        cout<<ans;

}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define RREP(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;


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

    int sum = 0;
    for (int t = 1; ; t++){
        sum += t;
        if (sum >= x){
            cout << t << endl;
            return 0;
        }
    }
}

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

#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	int n, s = 0, base = 0;
	cin >> n;
	--n;
	int foo, bar;
	cin >> foo >> bar;
	base = foo - bar;
	n -= 2;
	vector<int> a(n), suf_sum(n + 1, 0);
	vector<vector<pair<int, int> > > all(n);
	for (int i = 0; i < n; ++i) cin >> a[i], s += a[i];
	vector<int> rem(s);
	for (int t = 0, i = n - 1; ~i; --i) {
		suf_sum[i] = suf_sum[i + 1] + a[i];
		for (int j = 0; j < a[i]; ++j) rem[t + j] = i;
		t += a[i];
	}
	int m;
	cin >> m;
	vector<int> q(m), ans(m);
	for (int i = 0; i < m; ++i) {
		cin >> q[i];
		if(q[i] >= s) ans[i] = q[i] - s + base;
		else all[rem[q[i]]].push_back(make_pair(i, q[i] - suf_sum[rem[q[i]] + 1]));
	}
	deque<int> dp;
	for (int i = 0; i < n; ++i) {
		while(dp.size() <= a[i]) dp.push_back(dp.size() == 0 ? 0 : dp.back() + 1);
		for (int j = dp.size() - 1, end_j = j - a[i]; j > end_j; --j) dp.push_front(dp[dp.size() - j]);
		for (auto t: all[i]) ans[t.first] = dp[t.second] + base;
	}
	copy(ans.begin(), ans.end(), ostream_iterator<int>(cout, "\n"));
	return 0;
}

Measured memory_bytes: 23412
#include <stdio.h>
#include <stdlib.h>
 
#define DEBUG 0
 
typedef struct {
	int input;
 	int place;
  	long year;
  	long id;
} Town;

int compareInput(const void *a,const void *b)
{
	return ((Town *)a)->input - ((Town *)b)->input;
}

int compareYear(const void *a,const void *b)
{
	return ((Town *)a)->year - ((Town *)b)->year;
}
 
int main(void)
{
	int n,m,*p;
 	long i,j,k,min;
  	Town *town;
  	scanf("%d %d",&n,&m);
  	town = (Town *)malloc(sizeof(Town) * m);
  	if (town==NULL) {
    		perror("town malloc");
    	  	exit(1);
   	 }
  	for (i=0;i<m;i++) {
		scanf("%d %ld",&town[i].place,&town[i].year);
		town[i].input = i;
	}
	p = (int *)malloc(sizeof(int) * n);
	for (i=0;i<n;i++) p[i]=1;
	qsort(town,m,sizeof(Town),compareYear);
	
	for (i=0;i<m;i++) {
		town[i].id = town[i].place * 1E6 + p[town[i].place-1];
		p[town[i].place-1]++;
	}

	qsort(town,m,sizeof(Town),compareInput);
  	for (i=0;i<m;i++) printf("%012ld\n",town[i].id);
	
  	free(town);
	free(p);
  	return 0;
}


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

using namespace std;
using ll = long long;

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

  int x;
  cin >> x;
  if (400 <= x && x < 600) {
    cout << 8 << endl;
  } else if (600 <= x && x < 800) {
    cout << 7 << endl;
  } else if (800 <= x && x < 1000) {
    cout << 6 << endl;
  } else if (1000 <= x && x < 1200) {
    cout << 5 << endl;
  } else if (1200 <= x && x < 1400) {
    cout << 4 << endl;
  } else if (1400 <= x && x < 1600) {
    cout << 3 << endl;
  } else if (1600 <= x && x < 1800) {
    cout << 2 << endl;
  } else if (1800 <= x && x < 2000) {
    cout << 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int main(){
    ll n;
    cin >> n;
    ll total = 0;
    ll minus = 0;
    for(int i = 0; i < n; i++){
        ll in;
        cin >> in;
        total = (total + in) % mod;
        minus = (minus + in * in) % mod;
    }
    ll ans = (total * total - minus + mod) % mod;
    if(ans % 2) cout << (ans + mod) / 2 << "\n";
    else cout << ans / 2 << "\n"; 
}

Measured memory_bytes: 3552
using System;
using System.Linq;
namespace ABC151C
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            string[] inp = Console.ReadLine().Split(' ');
            int n = int.Parse(inp[0]);
            int m = int.Parse(inp[1]);

            int[] ac = new int[n];
            int[] wa = new int[n];
            while (m-->0)
            {
                string[] inp2 = Console.ReadLine().Split(' ');
                int number = int.Parse(inp2[0])-1;
                string res = inp2[1];

                if (ac[number]>0) continue;

                if (res == "AC")
                {
                    ac[number] += 1;
                }
                else
                {
                    wa[number] += 1;
                }
            }
            int acCnt = ac.Sum();
            int waCnt = wa.Where((e,i) => ac[i]>0).Sum();
            
            Console.WriteLine($"{acCnt} {waCnt}");
        }
    }
}


Measured memory_bytes: 15948
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

class Program
{
    static void Main(string[] args)
    {
        var wrong_answer = new wrong_answer();
        wrong_answer.Solve();
    }
}

public class wrong_answer
{
    const int INF = 1 << 29;
    const long INFL = 1L << 60;
    const int MOD = 1000000007;
    const int MOD2 = 998244353;

    myinout IO = new myinout();






    public void Solve()
    {

        var o = IO.intm;
        var a = o[0];
        var b = o[1];


        if(a==b)
        IO.wri("Yes");
        else IO.wri("No");
    }




}






public static class Math2
{
    public static long pow(long i, long n, long MOD = 1000000007)
    {
        long res = 1;
        while (n > 0)
        {
            if ((n & 1) != 0) res = res * i % MOD;
            i = i * i % MOD;
            n >>= 1;
        }
        return res;
    }

    public static long gcd(long i, long y)
    {
        while (y != 0)
        {
            var r = i % y;
            i = y;
            y = r;
        }
        return i;
    }

    public static long lcm(long i, long y)
    {
        return i * y / gcd(i, y);
    }

    public static Dictionary<long, int> primefactorization(long N)
    {

        var ret = new Dictionary<long, int>();

        for (long i = 2; i * i <= N; ++i)
        {
            int cnt = 0;
            while (N % i == 0)
            {
                cnt++;
                N /= i;
            }
            if (cnt != 0) ret[i] = cnt;

        }
        if (N >= 2) ret[N] = 1;

        return ret;

    }

    public static List<long> divisorenumrate(long N)
    {
        var ret = new List<long>();

        for (long i = 1; i * i <= N; ++i)
        {

            if (N % i == 0)
            {
                ret.Add(i);
                ret.Add(N / i);
            }

        }

        return ret;

    }

    public static void swap<T>(ref T a, ref T b)
    {
        var i = a;
        a = b;
        b = i;
    }

}

class myinout
{
    //in
    public string str => Console.ReadLine();

    public string[] strm => str.Split(' ');

    public long[] longm => strm.Select(long.Parse).ToArray();
    public int[] intm => strm.Select(int.Parse).ToArray();
    public char[] charm => str.ToArray();
    public double[] doublem => strm.Select(double.Parse).ToArray();
    public long long1 => longm[0];
    public int int1 => intm[0];
    public char char1 => charm[0];
    public double double1 => doublem[0];



    //out
    public void wri<T>(T i)
    {
        Console.WriteLine(i);
    }
    public void wri<T>(T[] i)
    {
        Console.WriteLine(string.Join(" ", i));
    }

    public void yn(bool i)
    {
        if (i) wri("Yes");
        else wri("No");
    }

}


Measured memory_bytes: 13396
X, K, D = map(eval, input().split())

if X < -(K * D) < 0:
    X += K * D
elif 0 < K * D < X:
    X -= K * D
elif 0 < X < K*D:
    K = (K - X // D) % 2
    X %= D
    if X > 0:
        X -= K * D
    else:
        X += K * D
else:
    K = (K - (-X) // D) % 2
    X += ((-X) // D) * D
    if X > 0:
        X -= K * D
    else:
        X += K * D

print(abs(X))

Measured memory_bytes: 9148