akhauriyash/Code-Regression huggingface dataset:
N = int(input())

if N<0:
  negative = True
elif N==0:
  print(0)
  exit()
else:
  negative = False

N = abs(N)

a = bin(N)
a = a[2:]
a = [int(i) for i in a]
a.reverse()

if len(a)%2 == 0 and a[-1]==1:
  a.append(0)
for i,num in enumerate(a[-2::-1]):
  digit = len(a)-2-i
  if digit % 2:
    a[digit+1] += num
  #print('digit: ', digit, 'num: ', num,  '\t', a)


a.append(0)
if negative:
  for i,num in enumerate(a[-2::-1]):
    digit = len(a)-2-i
    a[digit+1] += num


for i,num in enumerate(a):
  while a[i]>1:
    if i < len(a)-1:
      a.append(0)
      a.append(0)
    a[i] -= 2
    if a[i+1] > 0:
      a[i+1] -= 1
    else:
      a[i+1] += 1
      a[i+2] += 1

flag = 0
for i in a[::-1]:
  if i == 1:
    flag = i
  if flag:
    print(i,end='')


Measured memory_bytes: 3192
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <math.h>
#include <string>
#include <time.h>
#include <random>
#include <memory.h>
#include <bitset>
using namespace std;

#define FILE0
#define MAGIC0
mt19937 rnd(time(0)); //rnd()

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mii map<int, int>
#define mll map<ll, ll>
#define msl map<string, ll>
#define mls map<ll, string>
#define MOD (1000000007ll)
#define MOD2 (1000000009ll)
#define BIGMOD (1000000000000000007ll)
#define RMOD int(5e8 + rnd() % (int) 5e8)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef FILE1
ifstream in("input.txt");
ofstream out("output.txt");
#endif
#ifdef MAGIC1
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

bool isPrime(ll a)
{
	ll i;
	for (i = 2; i*i <= a; i++)
	{
		if (a%i == 0)
		{
			return 0;
		}
	}
	return (a != 1);
}

bool isPalindrom(const string &s, int l, int r)
{
	for (int i = 0; i < (r - l + 1) / 2; i++)
	{
		if (s[l + i] != s[r - i])
		{
			return 0;
		}
	}
	return 1;
}

template <class type1> type1 gcd(type1 a, type1 b)
{
	type1 t;
	while (b)
	{
		t = b;
		b = a%b;
		a = t;
	}
	return a;
}

ll positiveMod(ll v, ll md)
{
	v = v%md;
	if (v < 0)
	{
		v += md;
	}
	return v;
}

//-----------------------------------------------------end--------------------------------------//

vector <pair<pair<double, double>, double> > dat;
vector <vector <pair<int, double> > > g;

const double INF = 1.0e15;

int main()
{
	fast;

	int n, i, j;
	double x1, y1, xn2, yn2, x, y ,r, dd;

	cin >> x1 >> y1 >> xn2 >> yn2;
	dat.push_back({ {x1, y1,}, 0 });
	cin >> n;
	for (i = 0; i < n; i++)
	{
		cin >> x >> y >> r;

		dat.push_back({ {x,y}, r });
	}
	dat.push_back({ {xn2,yn2}, 0 });

	n = n + 2;
	g.resize(n);

	for (i = 0; i < n; i++)
	{
		for (j = i + 1; j < n; j++)
		{
			dd = sqrt((dat[i].first.first - dat[j].first.first) * (dat[i].first.first - dat[j].first.first) + (dat[i].first.second - dat[j].first.second) * (dat[i].first.second - dat[j].first.second));
			dd = max(dd - dat[i].second - dat[j].second, 0.0);

			g[i].push_back({ j, dd });
			g[j].push_back({ i, dd });
		}
	}

	int s = 0;

	vector<int> p(n);
	vector <double> d(n, INF);
	d[s] = 0;
	vector<char> u(n);
	for (int i = 0; i<n; ++i) {
		int v = -1;
		for (int j = 0; j<n; ++j)
			if (!u[j] && (v == -1 || d[j] < d[v]))
				v = j;
		if (d[v] == INF)
			break;
		u[v] = true;

		for (size_t j = 0; j<g[v].size(); ++j) {
			int to = g[v][j].first;
			double len = g[v][j].second;
			if (d[v] + len < d[to]) {
				d[to] = d[v] + len;
				p[to] = v;
			}
		}
	}

	cout.precision(11);
	cout << fixed << d[n - 1];

	return 0;
}

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

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


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int p[10]={0,2,5,5,4,5,6,3,7,6},a[10],n,m,tmp,dp[10002],v[10];
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>a[i];
		v[a[i]]=1;
	}
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for (int i=1;i<=m;i++)
		for (int j=p[a[i]];j<=n;j++)
			dp[j]=max(dp[j],dp[j-p[a[i]]]+1);
	tmp=dp[n];
	for (int i=1;i<=tmp;i++)
		for (int j=9;j>=1;j--)
			if (v[j]==1&&p[j]<=n&&dp[n-p[j]]==dp[n]-1){
				cout<<j;
				n-=p[j];
				break;
			}
	return 0;
}

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

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

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

    int x = a + b;
    int y = b + c;
    int z = c + a;
    if(x == c or y == a or z == b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3584
from math import log2
def solve():
  N, K = map(int, input().split())
  ans = 0
  for i in range(1,N+1):
    if i>=K:
      ans += 1/N
    else:
      a = -(-log2(K/i)//1)
      ans += 1/((pow(2,a))*N)
  return ans
print(solve())

Measured memory_bytes: 65176
#include <iostream>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
    long long n,k,s=0; cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr,arr+n);
    for(int i=0;i<n-k;i++)
        s+=arr[i];
    cout<<s;
}


Measured memory_bytes: 4400
#include<bits/stdc++.h>
#define crap ios_base::sync_with_stdio(0);cin.tie(0)
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define int ll

using namespace std;

const int N = 3005;
int A[N];
int dp[N][N];
int n;



int32_t main()
{
   
    crap;
    memset(dp,0,sizeof(dp));
    cin>>n;
    for(int i=0;i<n;i++) cin>>A[i];

    for(int l=n-1;l>=0;l--){
    	for(int r=l;r<n;r++){
    		if(l==r) dp[l][r]=A[l];
    		else
    			dp[l][r]= max(A[l] - dp[l+1][r], A[r] -  dp[l][r-1]);
    	}
    }
    cout<<dp[0][n-1]<<endl;
}

Measured memory_bytes: 70784
st = $<.gets.chomp
po = 0
result = ""
while po < st.length
  case st[po, 5]
  when "apple"
    result += "peach"
    po += 5
  when "peach"
    result += "apple"
    po += 5
  else
    result += st[po]
    po += 1
  end
end
puts result


Measured memory_bytes: 6896
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    rep(i, n) {
        cin >> a.at(i);
    }

    // 昇順にソート
    sort(a.begin(), a.end());

    // \Sigma_{k=1}^{N-1} A_{N - \lfloor k/2 \rfloor} が答え
    long long ans = 0;
    for (int k = 1; k < n; k++) {
        // 添字
        int index = n - floor(k / 2);
        ans += a.at(index - 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 4844
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  const int ans = max({(A * 10) + B + C, A + (B * 10) + C, A + B + (C * 10)});
  cout << ans << endl;

  return 0;
}


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

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Enumerable.Range(1, int.Parse(Console.ReadLine())).Aggregate(1L, (x, y) => (x * y) % (1000000007)));
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()

int main(){
  int N,L;
  cin>>N>>L;
  vector<string> S(N);
  for(int i=0; i<N; i++){
    cin>>S[i];
  }
  sort(all(S));
  for(int i=0; i<N; i++){
    cout<<S[i];
  }
  cout<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<ll, ll> P;
int main()
{
  int N, Q;
  while(cin>>N>>Q,N||Q) {
    map<P, string> MAP;
    FOR(i,0,N) {
      string s;
      ll a, b;
      cin >> s >> a >> b;
      MAP[P(a, b)] = s;
    }
    FOR(i,0,Q) {
      ll in; cin >> in;
      bool ok = false;
      for(auto m : MAP) {
        ll end = m.first.second;
        ll start = end - m.first.first + 1;
        if(in >= start && in <= end) {
          ok = true;
          cout << m.second << " " << in - start + 1 << endl;
        }
      }
      if(!ok) {
        puts("Unknown");
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3272
using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.Linq;
using System.Reflection;
using System.Runtime.InteropServices;
using System.Runtime.Serialization;
using System.Security.Cryptography.X509Certificates;
using System.Xml;

namespace hello_world
{
	class Program
	{

		static void Main(string[] args)
		{

			string[] s = Console.ReadLine().Split(" ");
			decimal a = decimal.Parse(s[0]);
			decimal b = decimal.Parse(s[1]);
			decimal c = Math.Floor(a * b);


			Console.WriteLine(c);

		}
	}
}



Measured memory_bytes: 27604
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,v[1<<15],res;
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i];
    sort(v,v+n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            // v[k] < v[i]+v[j]
            int k = lower_bound(v,v+n,v[i]+v[j])-v;
            //debug(k), debug()
            res += k-i-1;
        }
    }
    cout << res << '\n';
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    static int n, k;
    static ArrayList<Integer> d;
    static ArrayList<Integer> s;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        d = new ArrayList<>();
        for (int i = 0; i < k; i++) d.add(sc.nextInt());
        s = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            if(!d.contains(i)) s.add(i);
        }
        System.out.println(dfs(0, 1));
        sc.close();
    }
    private static int dfs(int cur, int kurai) {
        int ret = Integer.MAX_VALUE;
        if(kurai == 100000) return ret;
        for(int a: s){
            int num = cur + a * kurai;
            if(num < n) num = dfs(num, kurai * 10);
            ret = Math.min(ret, num);
        }
        return ret;
    }

}


Measured memory_bytes: 23508
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
#include <map>
#include <climits>
#include <bitset>
using namespace std;
#define MATH_PI 3.14159265358979323846
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int x = 0, y = 0;
	int t = 0;
	int a, b, c;
	register int i;
	for (i = 1; i <= n; ++i){
		cin >> c >> a >> b;
		if (abs(x - a) + abs(y - b)>c - t){
			cout << "No\n";
			goto endapp;
		}
		if ((abs(x - a) + abs(y - b)) % 2 == 0 && (c - t) % 2 == 1){
			cout << "No\n";
			goto endapp;
		}
		if ((abs(x - a) + abs(y - b)) % 2 == 1 && (c - t) % 2 == 0){
			cout << "No\n";
			goto endapp;
		}
		x = a;
		y = b;
		t = c;
	}
	cout << "Yes\n";
endapp:
	//system("pause > nul");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;

#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPL(i,a,n) for(ll i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define SRTVG(v) sort(v.begin(),v.end(),greater<>())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;
typedef pair<ll,ll> Pi;
typedef map<string,int> si;

template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}
template<class T> void YesNo(T& a) {if(a){cout << "Yes" << ENT;}else{cout << "No" << ENT;}}
template<class T> void YESNO(T& a) {if(a){cout << "YES" << ENT;}else{cout << "NO" << ENT;}}


vector<int> used;
vector<vector<int>> connect;
int n,m;


int dfs(int now, int depth) {
    if (used[now]) return 0;
    if (depth == n) return 1;

    used[now] = 1;
    int ret = 0;

    for (int i = 0; i < n; i++){
        if (connect[now][i]) ret += dfs(i, depth + 1);
    }
    used[now] = 0;

    return ret;
}


int atcoder() {
    cin >> n >> m;
    vector<int> a(m),b(m);
    REP(i,0,m){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    int ans;
    
    used = vector<int>(n,0);
    connect = vector<vector<int>> (n,vector<int>(n,0));
    REP(i,0,m) connect[a[i]][b[i]] = connect[b[i]][a[i]] = 1;
    
    ans = dfs(0,1);
    cout << ans << ENT;
    
    return 0;
}

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


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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) cin >> a.at(i);
  long long ans = 1LL << 60;
  for (int i = -100; i <= 100; i++) {
    long long tmp = 0;
    for (int j = 0; j < N; j++) tmp += pow(a.at(j)-i, 2);
    ans = min(ans, tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N,M = map(int,input().split())

dp = [False]*N
dp[0] = True
cnt = [1]*N

for _ in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    dp[y] = dp[y] or dp[x]
    cnt[y] += 1
    cnt[x] -= 1
    if cnt[x] == 0:
        dp[x] = False

print(sum(dp))


Measured memory_bytes: 10300
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
#define rep(i,n) for (int i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/

void quickSortIndex(int value[ ],int index[], int left_i, int right_i);
void quickSwap(int x[ ], int i, int j);
void quickSortIndex(int value[ ],int index[], int left_i, int right_i)
{
    int li, ri;
    int pivot;
    li = left_i;
    ri = right_i;
    pivot = value[index[(left_i + right_i) / 2]]; /* 基準値を配列の中央付近にとる */
    while (1) {
        while (value[index[li]] < pivot)       /* pivot より大きい値が */
            li++;                   /* 出るまで i を増加させる */
        while (pivot < value[index[ri]])       /* pivot より小さい値が */
            ri--;                   /*  出るまで j を減少させる */
        if (li >= ri)                /* i >= j なら */
            break;                 /* 無限ループから抜ける */
        quickSwap(index, li, ri);
        li++;                       /* 次のデータ */
        ri--;
    }
    if (left_i < li - 1)              /* 基準値の左に 2 以上要素があれば */
        quickSortIndex(value, index, left_i, li - 1);    /* 左の配列を Q ソートする */
    if (ri + 1 <  right_i)            /* 基準値の右に 2 以上要素があれば */
        quickSortIndex(value, index,ri + 1, right_i);    /* 右の配列を Q ソートする */
}
/* 配列の要素を交換する */
void quickSwap(int x[ ], int i, int j)
{
    int temp;
    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}

int R=0;
int G=1;
int K=2;
int X,Y,A,B,C;
int color[1000000];
int index[1000000];
int taste[1000000];

int main(){
    cin >> X >> Y >> A >> B >> C;
    int N = A + B + C;
    int value;
    int cnt=0;
    rep(ni,A){
        index[cnt]=cnt;
        color[cnt]=R;
        cin >> value;
        taste[cnt]=value;
        cnt++;
    }
    rep(ni,B){
        index[cnt]=cnt;
        color[cnt]=G;
        cin >> value;
        taste[cnt]=value;
        cnt++;
    }
    rep(ni,C){
        index[cnt]=cnt;
        color[cnt]=K;
        cin >> value;
        taste[cnt]=value;
        cnt++;
    }
    
    ll ans = 0;
    int cntR = 0;
    int cntG = 0;
    int cntK = 0;
    int cntAll = 0;
    quickSortIndex(taste,index,0,N-1);
    int ni = 0;
    while(cntAll<X+Y){
        int ii =  index[(N-1) -ni];
        if(color[ii]==R){
            if(cntR<X){
                cntR = cntR + 1;
                cntAll = cntAll + 1;
                ans = ans + taste[ii];
            }
        }else if(color[ii]==G){
            if(cntG<Y){
                cntG = cntG + 1;
                cntAll = cntAll + 1;
                ans = ans + taste[ii];
            }
        }else if(color[ii]==K){
            cntAll = cntAll + 1;
            ans = ans + taste[ii];
        }
        ni++;
        //cout << ans << endl;
    }

    cout << ans << endl;

}

Measured memory_bytes: 9600
#pragma region
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define repc(i, m, n) for (int i = m; i < n; i++)
#define reprc(i, m, n) for (int i = m; i > n; i--)
#define all(v) v.begin(), v.end()
#define INF 1e9
#define EPS 1e-10
using namespace std;
typedef long long ll;
#pragma endregion

int main()
{
    double A,B,x,y;
    cin >> A >> B;

    repc(i,1,1001){
        if(floor(i * 0.08) == A && floor(i * 0.1) == B){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 256
#091_C
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
cd = [tuple(map(int, input().split())) for _ in range(n)]

ab.sort(key = lambda x:(-x[1]))
cd.sort(key = lambda x:(x[0]))
flg = [True for _ in range(n)] 
ans = 0

for i in range(n):
    c, d = cd[i]
    for j in range(n):
        if flg[j]:
            a, b = ab[j]
            if a < c and b < d:
                ans += 1
                flg[j] = False
                break
                
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LL long long
#define int long long
inline LL read(){
	char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
	LL k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(LL x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(LL x){write(x);puts("");}
int n,a[1000010],f[1000010],ans;
signed main(){
	n=read();for (int i=1;i<=n;i++){
		a[i]=read();f[a[i]]=f[a[i]-1]+1;ans=max(ans,f[a[i]]);
	}writeln(n-ans);
}


Measured memory_bytes: 5888
def check(b, c, rest)
  if rest.size == 1
    return b.last < rest.first || c.last < rest.first
  end

  if b.last < rest.first
    bb = b.dup
    rr = rest.dup
    bb.push(rr.shift)
    return true if check(bb, c.dup, rr)
  end
  if c.last < rest.first
    cc = c.dup
    rr = rest.dup
    cc.push(rr.shift)
    return true if check(b.dup, cc, rr)
  end
end

n = gets.to_i
n.times do
  rest = gets.strip.split.map(&:to_i)
  b = [0]
  c = [0]
  b.push(rest.shift)
  puts check(b, c, rest) ? 'YES' : 'NO'
end



Measured memory_bytes: 6876
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 2e5 + 5;

int n, k;
int a[maxn];

struct fenwick
{
    int val[maxn];

    void init()
    {
        fill(val + 1, val + n + 1, 0);
    }

    void update(int x, int k)
    {
        for(; x <= n; x += x & -x)
            val[x] += k;
    }

    int get(int x)
    {
        int res = 0;
        for(; x > 0; x -= x & -x)
            res += val[x];
        return res;
    }
} tree;

void read_input()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
}

bool check()
{
    for(int i = 1; i <= n; ++i)
        if(a[i] != n) return true;
    return false;
}

void solve()
{
    while(k > 0 && check())
    {
        --k;
        tree.init();
        for(int i = 1; i <= n; ++i)
        {
            int l = max(i - a[i], 1), r = min(i + a[i], n);
            tree.update(l, 1);
            tree.update(r + 1, -1);
        }
        for(int i = 1; i <= n; ++i)
            a[i] = tree.get(i);
    }
    for(int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
    cout << '\n';
}

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



Measured memory_bytes: 5216
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,K;
  cin >> A >> B >> K;
  
  for (int i = 0; i < K; i++) {
    int C;
    if (i % 2 == 0){
      if (A % 2 == 1){
        A--;
      }
      A = A/2;
      B += A;
    }
    else {
      if (B % 2 == 1){
        B--;
      }
      B = B/2;
      A += B;
    }
  }
  cout << A << ' ' << B << endl;
}

Measured memory_bytes: 3648
#include<vector>
#include<iostream>
#include<algorithm>
#include<chrono>
#include<set>
#include<cstdio>
#include<string>
#include<unordered_map>

using namespace std;


int main()
{
    int n, q;
    long long ans = 0;
    scanf("%d",&n);
    unordered_map<int, int> mp;
    for(int i = 0; i < n; i++){
        int a;
        scanf("%d", &a);
        mp[a]++;
        ans += a;
    }
    scanf("%d",&q);
    for(int i = 0; i < q; i++){
        int b, c;
        scanf("%d%d", &b, &c);
        mp[c] += mp[b];
        ans += (mp[b]*c - mp[b]*b);
        mp[b] = 0;
        cout << ans << endl;
    }
}

Measured memory_bytes: 6856
#include<bits/stdc++.h>
#define  pb push_back
#define  xx first
#define  yy second
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;
int h,n;
int dp[1001];
int v[4000],cost[4000];
int ans = 1e-9;
/*
int go(int i,int sum){

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

       dp[i][sum] =min(val[i]+go(i+1,W-a[i]),go(i+1,W));
       return dp[i][sum];
}
*/
void go(int i,int x, int y ){

     ans = max(ans,x-y);
    if(i>n){
      return ;
    }
    go(i+1,v[i]+x,cost[i]+y);
    go(i+1,x,y);
    return;
}
 int main()
{
   // fast;

  cin >> n;
  memset(dp,-1,sizeof dp);
  for(int i=1; i<=n; i++){
     cin >> v[i];
  }
  for(int i=1; i<=n; i++){
     cin >> cost[i];
  }
  go(1,0,0);
  cout << ans << endl;


   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e5+5;
vector<int>g[maxm];
int L[maxm],R[maxm],idx;
int a[maxm];
int n,q;
void dfs(int x,int fa){
    L[x]=++idx;
    for(int v:g[x]){
        if(v==fa)continue;
        dfs(v,x);
    }
    R[x]=idx;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,1);
    while(q--){
        int x,val;cin>>x>>val;
        a[L[x]]+=val;
        a[R[x]+1]-=val;
    }
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1];
    }
    for(int i=1;i<=n;i++){
        cout<<a[L[i]]<<' ';
    }
    return 0;
}


Measured memory_bytes: 28568
def solve(a):
    n = len(a)
    cost = [[0 for i in range(n)] for j in range(n)]
 
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            k = i+length-1
            def f(i,j,k):
                return cost[i][j-1]+cost[j][k]+M[i][0]*M[j-1][1]*M[k][1]
            cost[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
    return cost[0][n-1]
 
n = input()
M = []
for i in range(n):
    M.append(map(int, raw_input().split()))
print solve(M)

Measured memory_bytes: 6528
import scala.io.StdIn.readLine
import scala.math.{max,min}

object Main extends App {

  var m = readLine.split(" ").map(_.toInt)
  while( m(0) != 0 || m(1) != 0 ){
    val Array(n,x) = m
    println( ( 1 until min(n-1,x/3) ).foldLeft(0) { (sum,i) => sum + (max(i+1,x-i-n) until min(n,(x-i+1)/2)).length })

    m = readLine.split(" ").map(_.toInt)
  }
}

Measured memory_bytes: 44040
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func nextFloat64() (float64, error) {
	return strconv.ParseFloat(nextString(), 64)
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func main() {
	scanner.Split(bufio.ScanWords)

	sizeRing := 400000 * 2
	ring := make([]int, sizeRing)
	iHead := sizeRing - 1
	iTail := 0

	nQueries := nextInt()
	for i := 0; i < nQueries; i++ {
		queryType := nextInt()
		// fmt.Printf("q=%v, iHead=%v, iTail=%v\n", queryType, iHead, iTail)
		if queryType == 0 {
			d := nextInt()
			x := nextInt()
			if d == 0 { // insert to head
				ring[iHead] = x
				iHead = (iHead - 1 + sizeRing) % sizeRing
			} else if d == 1 { // insert tot tail
				ring[iTail] = x
				iTail = (iTail + 1 + sizeRing) % sizeRing
			}
		} else if queryType == 1 {
			p := nextInt()
			t := sizeRing - iHead - 1
			// fmt.Println(p, t, iHead)
			if p < t {
				fmt.Println(ring[iHead+p+1])
			} else {
				fmt.Println(ring[p-t])
			}
		} else if queryType == 2 {
			d := nextInt()
			if d == 0 { // pop from head
				// fmt.Println(ring[iHead])
				iHead = (iHead + 1 + sizeRing) % sizeRing
			} else if d == 1 { // pop from tail
				// fmt.Println(ring[iTail])
				iTail = (iTail - 1 + sizeRing) % sizeRing
			}
		}
		// fmt.Println(ring)
	}
}



Measured memory_bytes: 12264
//	-*- mode: C++ -*-
//	Print Test Cases
//		In an online judge system, a judge file may includes multiple datasets to check whether the submitted program outputs a correct answer for each test case. This task is to practice solving a problem with multiple datasets.
//
//		Write a program which reads an integer x and print it as is. Note that multiple datasets are given for this problem.
//
//	Input
//		The input consists of multiple datasets. Each dataset consists of an integer x in a line.
//
//		The input ends with an integer 0. You program should not process (print) for this terminal symbol.
//
//	Output
//		For each dataset, print x in the following format:
//
//	Case i: x
//		where i is the case number which starts with 1. Put a single space between "Case" and i. Also, put a single space between ':' and x.
//
//	Constraints
//		1 ≤ x ≤ 10000
//		The number of datasets ≤ 10000
//	Sample Input
//		3
//		5
//		11
//		7
//		8
//		19
//		0
//	Sample Output
//		Case 1: 3
//		Case 2: 5
//		Case 3: 11
//		Case 4: 7
//		Case 5: 8
//		Case 6: 19

#include <iostream>
#include <vector>

int	main(int	argc,
		 char*	argv[])
{
	std::vector<int>	xv;

	for(int i = 0; i < 10000; i++){
		int	x	= 0;
		std::cin >> x;

		if(x <= 0){
			break;
		}

		xv.push_back(x);
	}

	int j = 1;
	for(int x : xv){
		std::cout << "Case " << j << ": " << x << '\n';
		++j;
	}
}



Measured memory_bytes: 3232
#include<iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  int A[N];
  int sum=0,cnt=0;
  for(int i=0; i<N; i++) cin >> A[i];
  for(int j=0; ; j++){
    for(int i=0; i<N; i++){
      if(A[i]%2 == 0){
        cnt++;
        A[i] /= 2;
      }
      else break;
    }
    if(cnt == N) sum++;
    else break;
    cnt=0;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

wari = []
for i in range(M):
    t = list(map(int, input().split()))
    wari.append([t[0]-1, t[1]-1, t[2]])

# print(wari)

r = []

for x, y, c in wari:
    p = a[x] + b[y] - c
    r.append(p)
r.append(min(a)+min(b))


# print(r)
print(min(r))

Measured memory_bytes: 35032
n, a, b = map(int, input().split())
cnt = 0
for i in range(1,n+1):
    s = list()
    l = str(i)
    for j in range(len(l)):
        s.append(int(l[j]))
    if a <= sum(s) and sum(s) <= b:
        hoge = map(str, s)
        hoge = ''.join(hoge)
        cnt += int(hoge)

print(cnt)

Measured memory_bytes: 3064
#include <stdio.h>
int main(void) {
  int a,b,d,r;
  double f;
  scanf("%d %d\n",&a,&b);
  d = a/b;
  r = a%b;
  f = (double)a/(double)b;
  printf("%d %d %lf\n",d,r,f); 
}


Measured memory_bytes: 2028
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;

using namespace std;

int main()
{
   FAST/**/
    
   string s, t;
   cin>>s>>t;
   
   ll cnt = 0;
   for(ll i=0;i<3;i++)
        cnt+=(s[i] == t[i]);
  
   cout<<cnt;        
   
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#define rep(i, n) for (int i=0; i < n; i ++)
#define _min(x, y) x = min(x, y)
#define _max(x, y) x = max(x, y)
using namespace std;


int main() {
  long N;
  unordered_map<long, long> dest2time;
  long long cumsum = 0;
  vector<long> keys;
  int flag=0;

  cin >> N;
  rep(i, N) {
    long long A, B;
    cin >> A >> B;
    if (dest2time.find(B) == dest2time.end()) {
      dest2time[B] = 0;
      keys.push_back(B);
    }
    dest2time[B] += A;
  }

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

  for (long i: keys) {
    cumsum += dest2time[i];
    if (cumsum > i) flag = 1;
  }
  cout << (flag == 1 ? "No" : "Yes") << endl;
  return 0;
}


Measured memory_bytes: 10044
#include <iostream>
#define REP(i, a, n) for(int i = (a); i < (n); i++)
using namespace std;

int E;

int main(void) {
  while(cin >> E, E) {
    int ans = 100000000;
    REP(z, 0, 101) {
      int z3 = z * z * z;
      if(z3 > E) break;
      REP(y, 0, 1001) {
        int y2 = y * y;
        int x = E - z3 - y2;
        if(x < 0) continue;
        ans = min(ans, x + y + z);
      }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3088
#include <stdio.h>
int main() {
    int a,b,c,d,RideBack[55];for (a=0;a<=50;RideBack[a++]=0);
    for (a=0;a<10;a++) for (b=0;b<10;b++) for (c=0;c<10;c++) for (d=0;d<10;d++) RideBack[a+b+c+d]++;
    while (scanf("%d",&a)!=EOF) printf("%d\n",RideBack[a]);return 0;
}

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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  int X, Y;
  X = max(max(A, B), C);
  Y = A + B + C - X;
  for (int i = 0; i < K; i++) {
    X *= 2;
  }
  cout << X + Y << endl;
}


Measured memory_bytes: 256
def self.calculate(a)
	i = 0
	a.map do |num|
		result = (num.to_i - i).abs
		i = num.to_i
		result
    end
end

n = gets.to_i
array = gets.chomp.split(' ').map(&:to_i)

array2 = [0] + array + [0]
array3 = self.calculate(array2)
sumation = 0
array3.each do |num|
	sumation += num
end

(1..n).each do |num|
	copied_sum = sumation
	copied_sum -= array3[num] + array3[num + 1]
	puts copied_sum += (array2[num - 1] - array2[num + 1]).abs
end


Measured memory_bytes: 15508
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define rep1(i, a, b) for(int i =a; i >=b; i--)
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple

int r,b,n;
string s;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
cin >> s;
for(int i=0;i<n;i++){
       if(s[i]=='R')r++;
       else b++;
}
if(r>b){
       cout << "Yes" << endl;
}
else {
       cout << "No" << endl;
}

return 0;
}
///....


Measured memory_bytes: 256
<?php
  const DIRS = array('R','D','L','U');
  $p = array(1,0,0);
  $path = 'R';
  $step =  array(array(1,0), array(0,1), array(-1,0), array(0,-1));

  function frontIsClear($p, $l) {
      list($x,$y,$d) = $p;
      return ($d == 0 && ($y>0 ? !$l[2*$y-1][$x] : 1))
             || ($d == 1 && ($x<4 ? !$l[2*$y][$x] : 1))
             || ($d == 2 && ($y<4 ? !$l[2*$y+1][$x] : 1))
             || ($d == 3 && ($x>0 ? !$l[2*$y][$x-1] : 1));
  }

  function canMove($p,$l) {
      list($x,$y,$d) = $p;
      switch($p[2]) {
      case 0:
          return $x!=4 && $l[2*$y][$x];
      case 1:
          return $y!=4 && $l[2*$y+1][$x];
      case 2:
          return $x!=0 && $l[2*$y][$x-1];
      case 3:
          return $y!=0 && $l[2*$y-1][$x];
      }
  }

  function move(&$p,$step) {
      $p[0] = $p[0] + $step[$p[2]][0];
      $p[1] = $p[1] + $step[$p[2]][1];
  }

  for($i=0;$i<9;$i++)
      $l[] = trim(fgets(STDIN));

  while(true) {
       if(!frontIsClear($p,$l)){
          $p[2] = ($p[2]+3) % 4;
       } else {
           while(!canMove($p,$l)) {
              $p[2] = ($p[2]+1) % 4;
           }
       }
       if($p == array(0,0,0))
           break;
       move($p,$step);
       $path .= DIRS[$p[2]];
  }

  echo $path.PHP_EOL;

Measured memory_bytes: 15324
n = int(input())
raw_a = list(map(int, input().split()))
a = sorted(raw_a, reverse=True)
alice = 0
bob = 0
for i in range(0, n, 2):
    alice += a[i]
for i in range(1, n, 2):
    bob += a[i]
print(alice-bob)

Measured memory_bytes: 3064
#coding: utf-8
#ABC043D
import sys

s=raw_input()

for i in xrange(len(s)-1):
 if s[i]==s[i+1]:
  print i+1,i+2
  sys.exit()

for i in xrange(len(s)-2):
 if s[i]==s[i+2]:
  print i+1,i+3
  sys.exit()
  
print -1,-1


Measured memory_bytes: 2692
def solve(inp):
    (N, K) = map(int, inp.readline().strip().split(' '))
    H = list(map(int, inp.readline().strip().split(' ')))

    r = 0
    for h in H:
        if h >= K:
            r += 1

    return str(r)


def test(s):
    from io import StringIO
    print(solve(StringIO(s)))


def main():
    import sys
    result = solve(sys.stdin)
    if result:
        print(result)


if __name__ == '__main__':
    # test('50\n' + '100 ' * 50)
    main()


Measured memory_bytes: 11908
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int, readline().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in readlines()]
X = [0] * H 
Y = [0] * W 
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  
C = [w for w, y in enumerate(Y) if y == maxY] 

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)

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

int main(){
  int n;
  int imap[110][110];
  int mmap[110][2];//0->row 1->column
 
  while(cin >> n && n){
 
    for(int i=0;i<n;i++){
      mmap[i][1] = 1<<30; 
      mmap[i][0] = 0;
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	cin >> imap[i][j];
	mmap[j][0] = max(mmap[j][0],imap[i][j]);
      }
      for(int j=0;j<n;j++)mmap[i][1] = min(mmap[i][1],imap[i][j]);
    }
    bool found = false;
    for(int i=0;i<n;i++){
      
      for(int j=0;j<n;j++){
	if(mmap[i][0] == mmap[j][1]){
	  cout << mmap[i][0] << endl;
	  found = true;
	  break;
	}

      }
   	if(found)break;

    }
    if(!found)cout << "0" << endl;



  }
  return 0;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define vec(x) vector<x>
#define IINF INT_MAX
#define LLINF LLONG_MAX
ll gcd(ll a,ll b){while(b){ll tmp = a % b;a = b;b = tmp;}return a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define out(x) for(auto i : x) cout << i << " "; cout << endl;
#define outln(x) for(auto i : x) cout << i << endl;
#define vec_cpy(to,from) copy(all(to),back_inserter(from))
#define ary_cpy(to,from) memcpy(to, from, sizeof from)
#define MOD 1000000007
#define DEBUG true

int main(){
  int n; cin >>n;
  cout << n * 32 << endl;
  return 0;
}

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

int main(){

    int n;
    int sum=0,ans=0;
    cin>>n;
    vector<int> d(n);
    for(int i=0;i<n;i++){
        cin>>d.at(i);
        sum+=d.at(i);
    }

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

        ans+=d.at(i)*(sum-d.at(i));

    }

    cout<<ans/2<<endl;









    return 0;
}

Measured memory_bytes: 256
S = input()
flag = 1
if S.count("W") == 0 and S.count("E") == 0:
  if S.count("N") == 0 or S.count("S") == 0:
    flag = 0
  else:
    flag = 1
elif S.count("W") == 0 or S.count("E") == 0:
  flag = 0
elif S.count("N") == 0 and S.count("S") == 0:
  flag = 1
elif S.count("N") == 0 or S.count("S") == 0:
  flag = 0
else:
  flag = 1
if flag == 1:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3188
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
int main() {
    int N; cin >> N;
    vector< pair<int, int> > v;
    for(int i=0; i<N; i++) {
        int a, b; cin >> a >> b;
        v.emplace_back(b, a);
    }

    sort(v.begin(), v.end());
    int t = 0;
    for(int i=0; i<N; i++) {
        int a, b; tie(b, a) = v[i];
        t += a;
        if(t > b) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main(){
	long long n,t;
	scanf("%lld",&n);
	t=n/500;
	n=n-t*500;
	n=n/5;
	printf("%lld\n",t*1000+n*5);
	return 0;
}

Measured memory_bytes: 888
#include <iostream>
using namespace std;
#define BIG_NUM 1000000007

long long int perm(long long int num)
{
    long long int res = num;
    for(long long int i = num - 1; i > 1; --i)
    {
        res = (res % BIG_NUM) * (i % BIG_NUM);
    }
    return res;
}

int main()
{
    long long int n, m;
    cin >> n >> m;
    
    long long int n_p = perm(n);
    long long int m_p = perm(m);
    //cout << n_p << endl;
    //cout << m_p << endl;
    long long int res;
    res = (n_p % BIG_NUM) * (m_p % BIG_NUM);

    if (n == m)
    {
        res = (res % BIG_NUM) * 2;
    }

    if(abs(n-m) < 2)
    {
        cout << res % BIG_NUM << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

template <class E>
using Graph = vector<vector<E>>;

template<class D, D INF>
struct Dijkstra {
    vector<D> res; //res[i] = sからiまでの最短距離
    
    template<class E>
    Dijkstra(const Graph<E> &g, int s) {
        int V = (int)g.size();
        res = vector<D>(V, INF);
        
        using P = pair<D, int>;
        priority_queue<P, vector<P>, greater<P>> q;
        q.push(P(0, s));
        res[s] = 0;
        while (!q.empty()) {
            P p = q.top(); q.pop();
            if (res[p.second] < p.first) continue;
            for (E e: g[p.second]) {
                if (p.first+e.dist < res[e.to]) {
                    res[e.to] = p.first+e.dist;
                    q.push(P(res[e.to], e.to));
                }
            }
        }
    }
};

struct Edge {
    int to;
    ll dist;
};

int main() {
    int n;
    cin >> n;
    Graph<Edge> g(n+1);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b; a--; b--;
        g[a].push_back(Edge{b, 1});
        g[b].push_back(Edge{a, 1});
    }
    vector<int> fix(n, -1);
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int v, p;
        cin >> v >> p; v--;
        fix[v] = p;
        g[n].push_back(Edge{v, p});
    }
    Dijkstra<ll, TEN(15)> da(g, n);
    for (int i = 0; i < n; i++) {
        int up = da.res[i];
        if (fix[i] != -1 && fix[i] != up) {
            printf("No\n");
            return 0;
        }
        fix[i] = up;
    }

    for (int i = 0; i < n; i++) {
        for (auto e: g[i]) {
            int j = e.to;
            if (abs(fix[i]-fix[j]) != 1) {
                printf("No\n");
                return 0;
            }
        }
    }

    printf("Yes\n");
    for (int i = 0; i < n; i++) {
        printf("%d\n", fix[i]);
    }
    return 0;
}

Measured memory_bytes: 13556
#include <iostream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <map>
#include <vector>
#include <climits>
#include <cmath>
#include <stdlib.h>

#define max_n 100001

long long mod = 1e9 + 7;

using namespace std;

int main()
{
    int n; cin >> n;
    long long total = 1;
    for (int i = 0; i < n; i++)
    {
        total = (total * 10) % mod;
    }
    long long total09 = 1;
    for (int i = 0; i < n; i++)
    {
        total09 = (total09 * 8) % mod;
    }
    long long total0 = 1;
    for (int i = 0; i < n; i++)
    {
        total0 = (total0 * 9) % mod;
    }
    cout << (total - total0 * 2 + total09 + 2 * mod) % mod << endl;
    return 0;
}

Measured memory_bytes: 3668
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        // 主処理
        String result = s;
        if (s.length() == 3) {
            StringBuilder sb = new StringBuilder(s);
            result = sb.reverse().toString();
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 21716
from operator import add


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c % MOD
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1]) % MOD

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l]) % MOD
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r]) % MOD
            r //= 2
        return self.__dot(vl, vr) % MOD
    

MOD = 998244353
N, K = map(int, input().split())
move = [tuple(map(int, input().split())) for _ in range(K)]
move.sort()

st = SegmentTree([0] * N, add, 0)
st.update(0, 1)
for i in range(1, N):
    cnt = 0
    for l, r in move:
        L = max(0, i - r)
        R = i - l
        if R >= 0:
            cnt += st.get(L, R + 1)
    st.update(i, cnt)

print(st.get(N - 1, N))


Measured memory_bytes: 79260
import java.util.Scanner;

public class Main {
	static char board[][];
	static Scanner sc = new Scanner(System.in);
	static int[] vx = new int[]{0,1,0,-1};
	static int[] vy = new int[]{1,0,-1,0};
	static int maxh, maxw;
	static boolean wflag;
	static boolean bflag;
	static int count;
	static int wcount = 0;
	static int bcount = 0;;
	
	public static void main(String[] args) {
        while (true) {
            maxw = sc.nextInt();
            maxh = sc.nextInt();
            if(maxw == 0) break;
            board = new char[maxh][maxw];
            for (int i = 0; i < maxh; i++) {
            	board[i] = sc.next().toCharArray();
            }
            wcount=0;
            bcount=0;
            solve();
            System.out.println(bcount + " " + wcount);
        }
	}

	private static void solve() {
		for (int i = 0; i < maxh; i++) {
			for (int j = 0; j < maxw; j++) {
				if (board[i][j] == '.') {
					count=0;
					wflag = false;
					bflag = false;
					dfs(i, j);
					if (wflag && !bflag) wcount += count;
					if (!wflag && bflag) bcount += count;
				}
			}
		}		
	}

	private static void dfs(int h, int w) {
		board[h][w] = 'X';
		count++;
		for (int i = 0; i < 4; i++) {
				if (h + vx[i] >= maxh || h + vx[i]  < 0 || w + vy[i] >= maxw || w + vy[i] < 0)
					continue;
				char c = board[h + vx[i]][w + vy[i]];
				if (c == 'X') continue;
				if (c == 'W') {
					wflag = true;
					continue;
				}
				if (c == 'B') {
					bflag = true;
					continue;
				}
				dfs(h + vx[i], w + vy[i]);
		}
	}
}

Measured memory_bytes: 25428