akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int S = scan.nextInt();
        int W = scan.nextInt();

        if (W >= S) {
            System.out.println("unsafe");
        } else {
            System.out.println("safe");
        }
    }
}

Measured memory_bytes: 35768
def main():
    n = int(input())
    a = list((map(int, input().split())))
    a.sort()
    m = 0
    y = 0
    for i in reversed(range(n)):
        if len(a) % 2 == 0:
            if i % 2 != 0:
                m += a[i]
            else:
                y += a[i]
        else:
            if i % 2 == 0:
                m += a[i]
            else:
                y += a[i]
    print(m - y)
main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int N,M;
int Map[55][55];
int visit[55];
int main(){

    cin>>N>>M;
    for(int i = 1;i<=M;i++)
    {
        int a,b;
        cin>>a>>b;
        visit[a]++;
        visit[b]++;
        Map[a][b] = Map[b][a] = 1;
    }
    int sum = 0;
    int xi;
    bool falg = true;
    while(1)
    {
        falg = true;
        for(int i = 1;i<=N;i++)
        {
            if(visit[i]==1)
            {
                sum++;
                xi = i;
                falg = false;
                visit[i]--;
                break;
            }
        }
        if(falg) break;
        for(int i = 1;i<=N;i++)
        {
            if(Map[xi][i]==1)
                visit[i]--;
        }
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int main() {
    int A,B,X;
    cin>>A>>B>>X;
    if(X>=A){
      if(X-A<=B)cout<<"YES"<<endl;
      else cout<<"NO"<<endl;
    }
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]

N, K = inpl()
a = inpl()
b = [i if i>0 else 0 for i in a ]
c = [i if i<0 else 0 for i in a ]
d = [0 for _ in range(N-K+1)]
d[0] = sum(c[:K])
e = [0 for _ in range(N-K+1)]
e[0] = sum(b[:K])
for i in range(N-K):
    d[i+1] = d[i] - c[i] + c[i+K]
    e[i+1] = e[i] - b[i] + b[i+K]
print(max(0, sum(b)+max(d), sum(b)-min(e)))

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

using namespace std;
typedef long long llint;
const int maxn = 1e5+10;
const llint mod = 1e9+7;

int n;
char niz[maxn];
int cnt[300];

int main() {
    scanf("%d%s", &n, niz);

    for (int i = 'a'; i <= 'z'; i++) cnt[i] = 1;
    llint sol = 0;
    for (int i = 0; i < n; i++) {
        llint tren = 1;

        for (char j = 'a'; j <= 'z'; j++) {
            if (niz[i] == j) continue;
            tren *= cnt[j], tren %= mod;
        }
        cnt[niz[i]]++;
        sol += tren, sol %= mod;
    }
    printf("%lld\n", sol);
    return 0;
}


Measured memory_bytes: 384
from collections import defaultdict
import bisect
from itertools import product

n = int(input())
s = input()

# {文字:その文字の出現位置}の辞書を構築
d = defaultdict(list)
for i in range(n):
    d[s[i]].append(i)

def canCreate(x,y,z):
    pos = 0
    for c in map(str, [x,y,z]):
        pos = bisect.bisect_left(d[c], pos)
        if pos == len(d[c]):
            return False
        pos = d[c][pos] + 1
    return True

ans = sum([canCreate(x, y, z) for x,y,z in product(range(10), repeat=3)])

print(ans)  

Measured memory_bytes: 10708
n = int(input())
a = list(map(int, input().split()))
p = 0
q = 0
for x in a:
    q += x
p = max(0, q-n*(n-1))
for y in range(p, q+1):
    z = 0
    for x in a:
        z += (x+y+1)//(n+1)
    if y >= z:
        print(y)
        break


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main(int argc, char *argv[]) { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

  int a[5];
  int mn=10;
  int ans=0;
  for(int i=0;i<5;i++){
    cin>>a[i];
    if(a[i]%10==0){
      ans += a[i];
    }else{
      mn = min(a[i]%10, mn);
      ans += a[i];
      ans += 10-a[i]%10;
    }
  }
  if(mn!=10)ans -= (10-mn);
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<vector<ll>> CSF(N-1, vector<ll>(3));
  rep(i,N-1){
    cin >> CSF[i][0] >> CSF[i][1] >> CSF[i][2];
  }
  for(int i=0;i<N-1;i++){
    ll time = CSF[i][1] + CSF[i][0];
    for(int j=i+1;j<N-1;j++){
      if(time < CSF[j][1]) time = CSF[j][1];
      if(time % CSF[j][2] != 0){
        time += CSF[j][2] - (time % CSF[j][2]);
      }
      time += CSF[j][0];
    }
    cout << time << endl;
  }
  cout << 0 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,e;
    cin>>a>>b>>c;
    d=a-b;
    if(d<c)
    {
       e=c-d;
       cout<<e<<endl;
    }
    else
    {
        cout<<"0"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
#define f first
#define s second
#define pb push_back
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

ll n, ans;

int main() {
	fastio; cin >> n;
	FOR(i, 1, n) {
		if (i % 3 != 0 and i % 5 != 0) ans += i;
	}
	cout << ans;
}


Measured memory_bytes: 3648
/* ex3_4 
　　　　　sachiyan*/

#include <stdio.h>
int main(void){
    int NUM; //入力Nの定義
    int i,j; //while内変数の定義
    scanf("%d", &NUM); //Nの読み取り
    i = 1;
    while(i <= 9){ //二重のループを０－９までで回して九九の解をすべてしらべる
        j = 1;
        while(j <= 9){
            if(i*j == NUM){ //九九を総当たりで探し、Nと等しければ
                printf("Yes"); //Yesを出力しendの行まで飛ぶ
                goto end; //endの行まで飛ぶ
            }
            j++;
        }
        i++;
    }
    if(i == 10 && j == 10){ //九九全てに当てはまらないとき
        printf("No"); //Noを出力
    }
    end:
        printf("\n"); //改行を出力
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000)


def main():
    n, m = map(int, input().split())

    net = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        net[x].append(y)

    def longest(i, memo):
        if memo[i] >= 0:
            return memo[i]
        if len(net[i]) == 0:
            l = 0
        else:
            l = max(longest(j, memo) + 1 for j in net[i])
        memo[i] = l
        return l

    memo = [-1] * n
    l = max(longest(i, memo) for i in range(n))
    print(l)


main()


Measured memory_bytes: 119296
#include <cstdio>
#include <queue>
#define MAXN 3005
#define mod 1000000007
using namespace std;

int n, m, dp[MAXN][MAXN], cnt0[MAXN];
int qr[MAXN], qrMax[MAXN];
char s[MAXN];
bool uz[MAXN][MAXN];

int getCnt0Pos(int pos) {
    return cnt0[qrMax[pos]] - cnt0[pos - 1];
}

int computeDp(int l, int c) {
    if(l == n) return 1;
    if(uz[l][c]) return dp[l][c];

    int r = qrMax[l];

    int nextC = c + cnt0[qrMax[l + 1]] - cnt0[qrMax[l]];
    
    dp[l][c] = 0;
    if(c < r - l + 1)
        dp[l][c] += computeDp(l + 1, nextC);
    if(c > 0)
        dp[l][c] += computeDp(l + 1, nextC - 1);

    while(dp[l][c] >= mod) dp[l][c] -= mod;
    uz[l][c] = 1;

    return dp[l][c];
}

int main() {

    scanf("%d %d\n", &n, &m);
    scanf("%s", s + 1);

    for(int i = 1; i <= n; ++i)
        cnt0[i] = cnt0[i - 1] + (s[i] == '0');

    for(int i = 1; i <= n; ++i)
        qr[i] = i;

    for(int i = 1; i <= m; ++i) {
        int l, r;
        scanf("%d %d", &l, &r);
        qr[l] = max(qr[l], r);
    }

    for(int i = 1; i <= n; ++i)
        qrMax[i] = max(qrMax[i - 1], qr[i]);

    printf("%d\n", computeDp(1, getCnt0Pos(1)));

    return 0;
}

Measured memory_bytes: 21376
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,cnt=0;
  cin>>N;
  vector<bool> as(pow(10,9)+1,false);
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    if(as.at(a)==false){as.at(a)=true;cnt++;}
    else{as.at(a)=false;cnt--;}
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 122368
import sys

sys.setrecursionlimit(10 ** 9)

get_length = []
for i in range(50 + 1):
    get_length.append(1 + 4 * (2 ** i - 1))

get_p = []
t = 0
for i in range(50 + 1):
    t = t * 2 + 1
    get_p.append(t)


def dfs(kk, ss, tt):
    if ss > tt:
        return 0

    if kk == 0:
        return 1

    target_length = get_length[kk]
    m = (1 + target_length) // 2

    if 1 <= ss <= 2 and target_length - 1 <= tt <= target_length:
        return get_p[kk]

    if ss == 1:
        return dfs(kk, 2, tt)

    if tt == target_length:
        return dfs(kk, ss, tt - 1)

    if ss == m:
        return 1 + dfs(kk, ss + 1, tt)

    if tt == m:
        return dfs(kk, ss, tt - 1) + 1

    if ss < m < tt:
        return dfs(kk, ss, m - 1) + 1 + dfs(kk, m + 1, tt)

    if ss < m:
        return dfs(kk - 1, ss - 1, tt - 1)
    else:  # ss > m
        return dfs(kk - 1, ss - m, tt - m)


n, x = map(int, input().split())
ans = 0
if get_length[n] < 2 * x:
    ans = get_p[n] - dfs(n, 1, get_length[n] - x)
else:
    ans = dfs(n, 1, x)
print(ans)


Measured memory_bytes: 3064
s=input()
ans=0
for i in range(len(s)):
    if s[i]=="R":
        if i%2==0:
            ans+=1
    elif s[i]=="L":
        if i%2==1:
            ans+=1
    elif s[i]=="U":
        ans+=1
    elif s[i]=="D":
        ans+=1
if ans==len(s):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
from collections import Counter

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if __name__ == "__main__":
    n = int(input())
    sosuu_list = prime_factorize(n)
    c = Counter(sosuu_list)
    cnt = 0
    for _, v in c.items():
        i = 1
        while(v > 0):
            v -= i
            i += 1
            cnt += 1
        if v < 0:
            cnt -= 1
    print(cnt)

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

ll mod = 1e9 + 7;

int main(){
    ll N, X, D;
    cin >> N >> X >> D;
    if (D == 0) {
        if (X == 0) cout << 1 << endl;
        else cout << (N+1) << endl;
        return 0;
    }
    ll ans = 0;
    ll p = D/gcd(X, D);
    for (ll M = 0; M <= N; M++) {
        //cout << ans << endl;
        if (M < p) {
            ans += ( (N*(N-1)/2 - (N-M)*(N-M-1)) + (N*(N-1)/2 - M*(M-1)) )/2+1;
            continue;
        }
        ll l = -N*(N-1)/2 + M*(M-1);
        ll r = N*(N-1)/2 - (N-M)*(N-M-1);
        ll lp = -N*(N-1)/2 + (M-p)*(M-p-1) - 2*X*p/D;
        ll rp = N*(N-1)/2 - (N-M+p)*(N-M+p-1) - 2*X*p/D;
        if (r < lp || l > rp) ans += (r-l)/2+1;
        else {
            if (l <= rp && rp <= r) ans += (r-rp)/2;
            if (l <= lp && lp <= r) ans += (lp-l)/2;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	char c;
	scanf("%c", &c);
	if(c == 'a' || c == 'e' || c== 'i' || c == 'o' || c == 'u'){
		printf("vowel");
	}else{
		printf("consonant");
	}
	
	putchar('\n');
	return 0;
}

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

int main()
{
	vector<int> vec(3);
	for (int i = 0; i < 3; i++) {
		cin >> vec.at(i);
	}
	sort(vec.begin(), vec.end());
	 
	cout << vec.at(0) << " " << vec.at(1) << " " << vec.at(2) << endl;

}



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

#define ran 1001001

struct Node {
	int pre, det, suf;
	Node() {}
} info[ran];

int n;
char s[ran];

Node analysis() {
	int len = strlen(s);
	
	int h = 0;
	int mi = 0;
	for(int i=0;i<len;i++) {
		if(s[i]=='(') h++;
		else h--;
		mi = min(mi, h);
	}
	
	Node res;
	res.pre = -mi;
	res.det = h;
	res.suf = res.pre + res.det;
	return res;
}

int cmp(const Node &a, const Node &b) {
	bool fa = (a.det>=0), fb = (b.det>=0);
	if(fa!=fb) return fa;
	if(fa) return a.pre<b.pre;
	return a.suf > b.suf;
}

bool chk() {
	int sum = 0;
	for(int i=0;i<n;i++)
		sum += info[i].det;
	if(sum!=0) return false;
	
	sort(info, info+n, cmp);
	
	int cur = 0;
	for(int i=0;i<n;i++) {
		if(cur<info[i].pre) return false;
		cur += info[i].det;
	}
	return true;
}

int main() {
	scanf("%d", &n);
	
	for(int i=0;i<n;i++) {
		scanf("%s", s);
		info[i] = analysis();
	}
	
	puts(chk() ? "Yes" : "No");
	
	return 0;
}

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

int ans[1000000];

char check(int a, int b, int c) {
	if((a == c) ^ b) return 'o';
	return 'x';
}

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

	int N;
	string s;
	cin >> N >> s;

	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < 2; j++) {
			ans[0] = i;
			ans[1] = j;
			for(int l = 1; l < N - 1; l++) {
				if(check(ans[l - 1], ans[l], 0) == s[l]) ans[l + 1] = 0;
				else ans[l + 1] = 1;
			}
			if(check(ans[N - 2], ans[N - 1], ans[0]) == s[N - 1] &&
			   check(ans[N - 1], ans[0], ans[1]) == s[0]) {
				for(int l = 0; l < N; l++) {
					if(ans[l] == 0) cout << 'S';
					else cout << 'W';
				}
				cout << endl;
				return 0;
			}

		}
	}
	cout << -1 << endl;
}

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


public class Hello
{
    public static void Main()
    {
        List<double> input = new List<double>();

        double x = 0;
        double y = 0;
        double theta = Math.PI / (double)2;

        string str;
        while (!((str = Console.ReadLine())=="0,0"))
        {
            input = str.Split(',').Select(double.Parse).ToList();
            x += input[0] * Math.Cos(theta);
            y += input[0] * Math.Sin(theta);
            theta -= input[1] * Math.PI / (double)180;
        }

            Console.WriteLine("{0}\r\n{1}", (int)x, (int)y);
    }

}



Measured memory_bytes: 18416
import math

X = int(input())

#https://qiita.com/neko_the_shadow/items/4ebad619564a48f5a97f
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primenums = primes(100004)

for primenum in primenums:
    if X <= primenum:
        print(primenum)
        break

Measured memory_bytes: 7064
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
long long int dp[20001];
long long findcount(long long S,long long curr){
    if(S==0) return 1;
    if(curr>S) return 0;
    if(dp[S]!=-1) return dp[S];
    long long op1=findcount(S-curr,3);
    long long op2=findcount(S,curr+1);
    return dp[S]=(op1+op2)%1000000007;
}
int main()
{
    long long int n,ans=0;
    memset(dp,-1,sizeof(dp));
    cin>>n;
    ans=findcount(n,3);
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 3944
// Maximize the Formula

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	int num[3];
	for (int i = 0; i < 3; ++i)
		cin >> num[i];

	sort(num, num+3);

	cout << num[2]*10 + num[1] + num[0];

	return 0;
}

Measured memory_bytes: 256
x, k, d = map(int, input().split())
x=abs(x)
if x-d*k > 0:
    print(x-d*k)
else:
    n=x//d
    x-=n*d
    if (k-n)%2==0:
        print(x)
    else:
        print(abs(x-d))

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

int main(){
    ll a; cin >> a;
    double b; cin >> b;
    ll ib = b*100+0.5;
    a *= ib;
    cout << a/100 << endl;
}

Measured memory_bytes: 3752
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

vl g1 = {1, 3, 5, 7, 8, 10, 12};
vl g2 = {4, 6, 9, 11};

int main(){
  ll x, y;
  cin >> x >> y;

  ll gx = 0, gy = 0;

  rep(i, g1.size()){
    if(g1[i] == x) gx = 1;
    if(g1[i] == y) gy = 1;
  }
  rep(i, g2.size()){
    if(g2[i] == x) gx = 2;
    if(g2[i] == y) gy = 2;
  }
  if(x == 2) gx = 3;
  if(y == 2) gy = 3;

  if(gx == gy) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  ll k = a * b;
  if(k < n || a + b - 1 > n) {
    cout << -1 << endl;
    return 0;
  }
  vl v;
  k -= n;
  rep(i, a) {
    ll bb = b;
    if(k >= bb - 1) {
      k -= bb - 1;
      bb = 1;
    } else {
      bb -= k;
      k = 0;
    }
    rep(j, bb) v.push_back((i + 1) * b - j);
  }
  vl sv = v;
  sort(all(sv));
  for(auto u : v) {
    ll in = lower_bound(all(sv), u) - sv.begin() + 1;
    cout << in << ' ';
  }
  cout << endl;
}

Measured memory_bytes: 8088
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <string>
#include <cmath>
#include <set>
#include <functional>
#include <map>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cassert>
#include <unordered_map>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define show(x) cout << #x << " = " << x << endl;
typedef long long ll;
typedef pair<int,int> pii;
void y(){
    cout << "Yes" << endl;
}
void n(){
    cout << "No" << endl;
}
int h,w;
int num[26];
int main(){
    cin >> h >> w;
    rep(i,h){
        string s;
        cin >> s;
        rep(j,w){
            num[s[j]-'a']++;
        }
    }
    int a=0,b=0,c=0;
    int aa=0, bb=0, cc=0;
    rep(i,26){
        if(num[i]!=0){
            if(num[i]%4==0){
                a++;
            }else if(num[i]%2==0){
                b++;
            }else c++;
        }
    }
    //cout << a << " " << b << " "<< c << endl;
    if(h%2==0 && w%2==0){
        if(b==0 && c==0){
            y();
        }else n();
    }else if(h%2==1 && w%2==1){
        if(c>1 || c==0){
            n();
        }else if(c==1){
            if(b<=(h-1)/2+(w-1)/2)y();
            else n();
        }
    }else{
        if(c>=1){
            n();
        }else{
            if(h%2==0){
                if(b<=h/2)y();
                else n();
            }else{
                if(b<=w/2)y();
                else n();
            }
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).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; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<vector<int> > graph(3 * n);
    rep (i, m) {
        int a, b; cin >> a >> b; a--; b--;
        rep (j, 3) graph[3 * a + j].push_back(3 * b + (j + 1) % 3);
    }
    vector<bool> used(3 * n);
    int s, t; cin >> s >> t; s--; t--;
    used[3 * s] = true;
    priority_queue<P> que; que.emplace(0, 3 * s);
    while (!que.empty()) {
        P p = que.top(); que.pop();
        if (p.second == 3 * t) {
            cout << -p.first / 3 << "\n";
            return 0;
        }
        for (auto i : graph[p.second]) {
            if (!used[i]) {
                que.emplace(p.first - 1, i);
                used[i] = true;
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}

Measured memory_bytes: 16768
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define all(x) x.begin(),x.end()
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL);
#define N

int main(){
	FIO;
	ld r; cin >> r;
    cout << fixed << setprecision(6) << 2*acos(-1)*r << endl;
	return 0;
}

Measured memory_bytes: 3772
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

//for debugging 
/*
g++ -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -std=c++14 
*/
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// debugging ends here

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
const int mxn  = 3e3+1;
// const int len = 1e7;
ll dp[mxn][mxn][3];
ll vals[mxn][mxn]; 
int r,c;

ll find(int x, int y, int xl){
	if(x<0 || x >= r ) return 0ll;
	if(y<0 || y>=c) return 0ll;
	ll &ans = dp[x][y][xl];
	if(ans!=-1){
		return ans;
	}
	ans = 0;
	if(vals[x][y]!=0){
		ans = max(ans, vals[x][y] + find(x+1,y,2));
	}
	if(xl && vals[x][y]!=0){
		ans = max(ans,vals[x][y] + find(x,y+1,xl-1));
	}
	ans = max(ans, max(find(x+1,y,2), find(x,y+1,xl)));
	// cout << x << ' ' << y << " " << xl << " " << " " << ans << endl;
	return ans;

}

void solve(){
	int k;
	cin >> r >> c >> k;
	memset(dp,-1,sizeof(dp));
	for(int i =0;i<k;i++){
		int x,y,val;
		cin >> x >> y;
		--x,--y;
		cin >> vals[x][y]; 
	}

	ll ans = find(0,0,2);

	cout << ans << endl;
}

int main(){
	fast;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif

	// int t;cin >> t;while(t--)
		solve();
}


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

int main() {
    // 入力
    int n,m;
    cin >> n>>m;
    int a[n];
    int sum=0;
    rep(i,n){
        scanf("%d",&a[i]);
    }
    rep(i,n){
        sum+=a[i];
    }
    float border=float(sum)/float(4*m);
    int cnt=0;
    rep(i,n){
        if(float(a[i])>=border) cnt++;
    }
    if(cnt>=m) cout <<"Yes";
    else cout <<"No";
    return 0;
}

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

#define int long long
typedef pair <int, int> pii;
typedef pair <pii, bool> ppb;

int ans[2] = {(int)1e5, (int)1e5};
string s;
vector <ppb> vec;

int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	int l = 0, r = 1;
	while (l < s.size()) {
		while (r < s.size() && s[l] == s[r])
			r++;
		vec.push_back({{l, r}, s[l] - '0'});
		l = r;
		r++;
	}
	
	for (int i = 0; i < vec.size(); i++) {
		int l = vec[i].first.first, r = vec[i].first.second;
		ans[vec[i].second] = min(ans[vec[i].second], max((int)s.size() - r, l));
	}
	cout << max(((int)s.size() + 1) / 2, min((int)s.size(), max(ans[0], ans[1]))) << endl;
}

Measured memory_bytes: 1992
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>

using namespace std;

int main(){
  int N, K; cin >> N >> K;
  
  vector <int> H(N);
  for(int i = 0; i < N; i++) cin >> H[i];


  vector <int> DP(N);

  for (int i = 1; i < N; i++){
    DP[i] = DP[i - 1] + abs(H[i - 1] - H[i]);
    for (int j = 0; j <= K && i - j >= 0; j++){
      DP[i] = min(DP[i], DP[i - j] + abs(H[i - j] - H[i]));
    }
  }
  cout << DP[N - 1] << endl;

  return 0;
}


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

using namespace std;

int main()
{
  int N;
  int p[101];

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

  
  for ( int i = N; i >= 0; i-- ) {
    int cnt = 0;
    for ( int j = 0; j < N; j++ ) {
      if ( p[j] >= i ) cnt++;
    }

    if ( cnt >= i ) {
      cout << i << endl;
      return 0;
    }
  }
				  
}

Measured memory_bytes: 3080
#include<stdio.h>
int main(){
  int x,a,b,kai,i;
  scanf("%d",&x);
  scanf("%d",&a);
  scanf("%d",&b);
  
  kai=x;
  kai=kai-a;
  
  while(kai>=b){
    kai=kai-b;
  }
  printf("%d",kai);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int) (n); i++)
#define ll long long
#define scout cout << fixed << setprecision(20)
ll INF = 9e17;
ll mod = 1e9 + 7;

int main() {
	int n; cin >> n;
	vector<pair<string,int>> a(n);
	rep(i,n) cin >> a[i].first >> a[i].second;
	string x; cin >> x;
	int ans = 0;
	bool ok = false;
	rep(i,n) {
		if(a[i].first==x) {
			ok=true; continue;
		}
		if(ok) ans += a[i].second;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

const int mod = 1000000007;

int h, w;
vector<string> a;

vvi dp;


int main() {
    cin >> h >> w;
    a.resize(h);
    rep(i, h) {
        cin >> a[i];
    }

    dp.assign(h, vi(w));
    dp[0][0] = 1;

    queue<pair<int, int> > q;
    q.push(make_pair(0, 0));

    while(!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        if(i<h-1 && a[i+1][j] == '.') {
            if(!dp[i+1][j]) {
                q.push(make_pair(i+1, j));
            }
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= mod;
        }

        if(j<w-1 && a[i][j+1] == '.') {
            if(!dp[i][j+1]) {
                q.push(make_pair(i, j+1));
            }
            dp[i][j+1] += dp[i][j];
            dp[i][j+1] %= mod;
        }
    }

    cout << dp[h-1][w-1] << '\n';
}

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long;
#define REP(i,s,N) for (int i=s; i<N; i++)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if(b-a == c-b) cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 256
def main():
    import sys

    input = sys.stdin.readline

    mod = 10 ** 9 + 7
    n = int(input())
    a = tuple(map(int, input().split()))

    b = [0] * 60

    for j in range(60):
        for x in a:
            if (x >> j) & 1:
                b[j] += 1

    ret = 0
    for j in range(60):
        ret = (ret + b[j] * (n - b[j]) * (1 << j)) % mod

    print(ret)


if __name__ == '__main__':
    main()


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

int n,num[10010];
string a;

int main()
{
    cin>>n>>a;
    for(int i = 1;i <= a.size();i++)
    {
        num[i] = a[i - 1] - 'A';
        num[i] = (num[i] + n) % 26;
        a[i - 1] = num[i] + 'A';
    }
    cout<<a;
    return 0;
}

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

using namespace std;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int n;
	cin >> n;
	map<string, int> m;
	while (n--) {
		string s;
		cin >> s;
		m[s]++;
	}
	cout << "AC x " << m["AC"] << '\n'
		<< "WA x " << m["WA"] << '\n'
		<< "TLE x " << m["TLE"] << '\n'
		<< "RE x " << m["RE"] << '\n';
	return 0;
}


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

int main()
{
  int N, A, count, res = 1000000000;
  cin >> N;
  for(int i = 0; i < N; i++)
  {
    count = 0;
    cin >> A;
    while(A % 2 == 0)
    {
      A /= 2;
      count++;
    }
    res = min(res, count);
    
  }
  cout << res << endl;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  char b;
  cin >> b;
  if(b == 'A') {
    cout << 'T' << endl;
  } else if(b == 'T') {
    cout << 'A' << endl;
  } else if(b == 'G') {
    cout << 'C' << endl;
  } else {
    cout << 'G' << endl;
  }
  return 0;
}

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

public class Main {
	private int[] card = new int[5];

	public static void main(String[] args) {
		new Main().run();
	}
	
	private void run() {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			String[] cd = scan.nextLine().split(",");
			for (int i = 0; i < 5; i++) card[i] = Integer.parseInt(cd[i]);
			
			Arrays.sort(card);
			
			if (fourCard()) {
				System.out.println("four card");
			}else if (fullHouse()) {
				System.out.println("full house");
			}else if (straight()) {
				System.out.println("straight");
			}else if (threeCard()) {
				System.out.println("three card");
			}else if (twoPair()) {
				System.out.println("two pair");
			}else if (onePair()) {
				System.out.println("one pair");
			}else {
				System.out.println("null");
			}
			
		}
	}
	
	private boolean fourCard() {
		int max = 0;
		for (int i = 0; i < 5; i++) {
			max = Math.max(max, continueNum(card[i]));
		}
		return (max > 3);
	}
	
	private boolean fullHouse() {
		int max1 = -1;
		for (int i = 0; i < 5; i++) {
			if (continueNum(card[i]) == 3) max1 = card[i];
		}
		
		if (max1 != -1) {
			int count = 0, max;
			for (int i = 0; i < 5; i++) {
				if (card[i] != max1) {
					for (int j = 0; j < 5; j++) {
						if (card[j] != max1 && i != j && card[i] == card[j]) return true;
					}
				}
			}
			return false;
		}else {
			return false;
		}
	}
	
	private boolean straight() {
		if (card[0] == 1) {
			if (card[1] == 2 && card[2] == 3 && card[3] == 4 && card[4] == 5) return true;
			else if (card[1] == 10 && card[2] == 11 && card[3] == 12 && card[4] == 13) return true;
			else return false;
		}else {
			if (card[1] == card[0] + 1 && card[2] == card[1] + 1 && card[3] == card[2] + 1 && card[4] == card[3] + 1) return true;
			else return false;
		}
	}
	
	private boolean threeCard() {
		for (int i = 0; i < 5; i++) {
			if (continueNum(card[i]) == 3) return true;
		}
		return false;
	}
	
	private boolean twoPair() {
		int pair1 = -1;
		for (int i = 0; i < 5; i++) {
			if (continueNum(card[i]) == 2) {
				pair1 = card[i];
				break;
			}
		}
		
		if (pair1 != -1) {
			for (int i = 0; i < 5; i++) {
				int count = 0;
				if (card[i] != pair1) {
					for (int j = 0; j < 5; j++) {
						if (i != j && card[i] == card[j]) count++;
					}
				}
				if (count == 1) return true;
			}
			return false;
		}else {
			return false;
		}
	}
	
	private boolean onePair() {
		for (int i = 0; i < 5; i++) {
			if (continueNum(card[i]) == 2) return true;
		}
		return false;
	}
	
	private int continueNum(int num) {
		int count = 0;
		for (int i = 0; i < 5; i++) {
			if (num == card[i]) count++;
		}
		return count--;
	}
	
	private void debug() {
		System.out.println();
	}

}

Measured memory_bytes: 17200
#include <stdio.h>

char str[81];
int P, Q, R, ans, p;

int min(int a, int b){ return a > b ? b : a; }
int max(int a, int b){ return a < b ? b : a; }

int formula(){
  int x, res;
  if(str[p] == '('){
    p++;
    x = formula();
    if(str[p++] == '*') res = min(x, formula());
    else res = max(x, formula());
    p++;
  }else if(str[p] == '-'){
    p++;
    res = 2 - formula();
  }else{
    if(str[p] == '0') res = 0;
    if(str[p] == '1') res = 1;
    if(str[p] == '2') res = 2;
    if(str[p] == 'P') res = P;
    if(str[p] == 'Q') res = Q;
    if(str[p] == 'R') res = R;
    p++;
  }
  return res;
}

main(){
  while(1){
    scanf("%s", str);
    if(str[0] == '.') break;
    ans = 0;
    for(P=0;P<3;P++){
      for(Q=0;Q<3;Q++){
        for(R=0;R<3;R++){
          p = 0;
          if(formula() == 2) ans++;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

Measured memory_bytes: 532
import std.stdio; // readln
import std.array; // split
import std.conv; // to
import std.typecons;
import std.range;
import std.algorithm;

void main(){
	string[] s = split(readln());
	int n = to!int(s[0]);

	s = split(readln());
	int[] a = new int[](n);
	for(int i = 0; i < n; i++){
		a[i] = to!int(s[i]);
		a[i]--;
	}

	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(i == a[a[i]]) cnt++;
	}
	writeln(cnt / 2);
}


Measured memory_bytes: 4028
#include <stdio.h>
#include <string.h>


int main()
{
   const char *w[3] = { "Sunny", "Cloudy", "Rainy" };

    char S[128];

    scanf( "%s", S );

    if ( !strcmp( S, w[0]) ) printf( "%s\n", w[1] );
    if ( !strcmp( S, w[1]) ) printf( "%s\n", w[2] );
    if ( !strcmp( S, w[2]) ) printf( "%s\n", w[0] );


    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 998244353
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
ll dp[3005][3005];
void solve(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	dp[a][b]=1;
	for(ll i=a+1;i<=c;i++)dp[i][b]=(i*dp[i][b-1]+(b)*dp[i-1][b]-(i-1)*(b-1)*dp[i-1][b-1]%mod+mod)%mod;
	for(ll j=b+1;j<=d;j++)dp[a][j]=((a)*dp[a][j-1]+(j)*dp[a-1][j]-(a-1)*(j-1)*dp[a-1][j-1]%mod+mod)%mod;
	for(ll i=a+1;i<=c;i++){
		for(ll j=b+1;j<=d;j++){
			dp[i][j]=(i*dp[i][j-1]%mod+j*dp[i-1][j]%mod-(i-1)*(j-1)*dp[i-1][j-1]%mod+mod)%mod;
		}
	}
	cout<<dp[c][d];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

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


int main() {
  ll N; cin >> N;
  ll x = 1;
  while(true){
    if(x*x > N) break;
    x++;
  }
  x--;
  cout << x*x << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
const int MOD = 1000000007;

int N, A[21][21], dp[1<<21];
int dfs(int bit) {
  int i = __builtin_popcount(bit);
  if (i == N) return 1;
  if (dp[bit] != -1) return dp[bit];

  dp[bit] = 0;
  rep(j, N)
    if (A[i][j] && (bit & (1 << j)) == 0)
      (dp[bit] += dfs(bit | (1 << j))) %= MOD;

  return dp[bit];
}
int main() {
  scanf("%d", &N);
  rep(i, 1<<21) dp[i] = -1;
  rep(i, N) rep(j, N) scanf("%d", &A[i][j]);
  printf("%d\n", dfs(0));
  return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  string S,T,ans="Yes";cin>>S>>T;
  ll s=S.size(), t=T.size();
  if(s!=t-1) ans="No";
  for(ll i=0; i<s; i++) if(S[i]!=T[i]) ans="No";
  cout<<ans<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;


ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}


int main(){FIN

    ll n,k; cin>>n>>k;
    ll idx;
    vll a(n); REP(i,n) {
        cin>>a[i];
        if (a[i]==1) idx = i;
    }
    if ((n-1)%(k-1)) idx = 1;
    else idx=0;
    cout<< (n-1) / (k-1) + idx<<endl;
    return 0;
}

Measured memory_bytes: 1024
var y,n,ans:int64;
var i:longint;
var x:array[0..10020] of int64;
begin
  read(n);for i:=1 to n do read(x[i]);
  for i:=1 to n do begin read(y);if x[i]<y then inc(ans,(y-x[i]) div 2)
  else dec(ans,x[i]-y);end;if ans>=0 then writeln('Yes')else writeln('No');
end.


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long int
#define INF INT_MAX
#define mod
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b){return (a.second < b.second);}
ll gcd(ll a, ll b){if(a==0)return b;return gcd(b % a, a);}
int main()
{
	chutiyaap;
	ll n;cin>>n;
	ll a[n+2];for(ll i=0;i<n;i++)cin>>a[i];
	ll res[n];
	res[0]=a[0];
	ll flag=-1;
	for(ll i=1;i<n;i++)
	{
		res[0]+=(flag*a[i]);
		flag*=(-1);
	}
	for(ll i=1;i<n;i++)
    {
        res[i] = 2*(a[i-1]-(res[i-1]/2));
    }
    for(ll i=0;i<n;i++)    cout<<res[i]<<" ";
    return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
struct ceva
{
    int x,y;
}p,p1,p2;
int n,m,j,maxi2,maxi,i,lee[1010][1010];
int dx[]={0 , -1 , 0 , 1 , 0 };
int dy[]={0 , 0 , 1 , 0 , -1 };
char mat[1010][1010];
queue <ceva>q;
int in(ceva a)
{
    return (a.x>=1 && a.x<=n && a.y>=1 && a.y<=m);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            lee[i][j]=9999999;
            cin>>mat[i][j];
            if(mat[i][j]=='#')
                q.push({i,j}) , lee[i][j]=0;
        }
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        maxi=max(maxi,lee[p.x][p.y]);
        for(i=1;i<=4;i++)
        {
            p1.x=p.x+dx[i];
            p1.y=p.y+dy[i];
            if(mat[p1.x][p1.y]=='.')
                if(in(p1))
                    if(lee[p1.x][p1.y]>lee[p.x][p.y]+1)
                    {
                        lee[p1.x][p1.y]=lee[p.x][p.y]+1;
                        q.push(p1);
                    }
        }
    }
    cout<<maxi;
    return 0;
}


Measured memory_bytes: 13328
#include <bits/stdc++.h>
#define int long long
#define all(c) (c).begin(),(c).end()
#define pii pair<long long,long long>
#define endl '\n'

using namespace std;

signed main(){
    std::ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    // if(k>n){
    //     int temp=k;
    //     k=n;
    //     n=k;
    // }
    int v1=n%k;
    //int v2=k%v1;
    int v2=min(k-v1,v1);
    cout << v2;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;


int main(void) {
  int i,j,k;
  int n,ma,mb;
  cin>>n>>ma>>mb;
  ll dp[2][405][405];
  rep(i,2)rep(j,405)rep(k,405)
    dp[i][j][k]=INF;
  dp[0][0][0]=0;

  rep(i,n){
    int a,b,c;
    cin>>a>>b>>c;
    rep(j,405)rep(k,405)
      if(dp[i%2][j][k]<INF){
        dp[(i+1)%2][j][k]=min(dp[(i+1)%2][j][k],dp[i%2][j][k]);
        if(j+a<405 && k+b<405)
          dp[(i+1)%2][j+a][k+b]=min(dp[(i+1)%2][j+a][k+b],dp[i%2][j][k]+c);
        dp[i%2][j][k]=INF;
     }
  }

  ll ans=INF;
  for(i=1;i*max(ma,mb)<405;i++)
    ans=min(ans,dp[n%2][i*ma][i*mb]);
  if(ans<INF)
    cout<<ans<<endl;
  else
    cout<<-1<<endl;
}


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

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

using namespace std;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

int main(){
	int n,m; scanf("%d%d",&n,&m);

	vector<int> Lang[100000];
	rep(i,n){
		int k; scanf("%d",&k);
		rep(_,k){
			int l; scanf("%d",&l); l--;
			Lang[l].emplace_back(i);
		}
	}

	union_find U(n);
	rep(l,m) rep(i,(int)Lang[l].size()-1) U.unite(Lang[l][i],Lang[l][i+1]);
	puts(U.size()==1?"YES":"NO");

	return 0;
}


Measured memory_bytes: 4608
x = int(input())
y = 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
print(y[x-1])

Measured memory_bytes: 3060
import collections
import sys
n = int(input())
d = list(map(int, input().split()))
c = collections.Counter(d)
if d[0] != 0 or c[0] > 1:
    print(0)
    sys.exit()
ans = 1
end = max(c.keys())
for i in range(2, end+1):
    if ans == 0:
        break
    ans *= c[i-1]**c[i]
print(ans % 998244353)



Measured memory_bytes: 19936
N=int(input())
S=input()
nums=[[0]*N for _ in range(3)]
for i in range(N):
  if S[i]=='R':
    nums[0][i]+=1
  elif S[i]=='G':
    nums[1][i]+=1
  else:
    nums[2][i]+=1
    
for i in range(1, N):
  nums[0][i]+=nums[0][i-1]
  nums[1][i]+=nums[1][i-1]
  nums[2][i]+=nums[2][i-1]
  
ans=0
for i in range(N-1, 1, -1):
  if S[i]=='R':
    ans+=nums[1][i-1]*nums[2][i-1]
  elif S[i]=='G':
    ans+=nums[0][i-1]*nums[2][i-1]
  else:
    ans+=nums[0][i-1]*nums[1][i-1]
    
tmp=0
for j in range(1, N-1):
  i=j-1
  k=j+1
  while i>=0 and k<=N-1:
    if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      ans-=1
    i-=1
    k+=1
print(ans-tmp)

Measured memory_bytes: 9228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
const ll INF = 1001001001;
const ll MOD = 1e9 + 7;

ll a[51], p[51];
ll func(ll n,ll x){
  if(n == 0) return x <= 0 ? 0 : 1;
  if(x <= a[n-1] + 1) return func(n-1, x-1);
  return p[n-1] + 1 + func(n-1, x - 2 - a[n-1]);
}

int main(){
  ll n, x;
  cin >> n >> x;
  a[0] = 1; p[0] = 1;
  rep(i, 50){
    a[i+1]= 2*a[i] + 3; p[i+1] = 2*p[i]+1;
  }
  cout << func(n, x) <<endl;
}
  
  

Measured memory_bytes: 3644
#line 1 "main_c.cpp"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <utility>
#include <limits>
#include <list>
#include <type_traits>

/* template start */

using i64=std::int_fast64_t;
using u64=std::uint_fast64_t;
 
#define rep(i, a, b) for (i64 i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  if(sizeof...(t)>0)std::cout<<" :";
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

template<typename Num>
constexpr Num mypow(Num a, u64 b,Num id=1) {
  if(b==0)return id;
  Num x = id;
  while (b > 0) {
    if(b & 1)x*=a;
    a*=a;
    b >>= 1;
  }
  return x;
}

/* template end */

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

  constexpr i64 SIZE=1000001;
  std::vector<i64> cnt(SIZE,0);

  rep(i,1,SIZE){
    for(i64 j=i*i;j<SIZE;j+=i){
      if(j==i*i)cnt[j]++;
      else cnt[j]+=2;
    }
  }

  i64 n;
  std::cin>>n;
  i64 ans=0;

  rep(i,1,n){
    ans+=cnt[n-i];
  }
  

  std::cout<<ans<<"\n";
  return 0;
}


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

int main(){
  long long n,m;
  cin >> n >> m;
  long long mod=1000000000+7;
  long long ans=1;
  if(n==m){
    while(n>=1){
      ans=ans*n;
      ans=ans%mod;
      n--;
    }
    ans=ans*ans%mod;
    ans=ans*2%mod;
  }else if(abs(n-m)==1){
    long long mi=min(n,m);
    long long ma=max(n,m);
    while(mi>=1){
      ans=ans*mi%mod;
      mi--;
    }
    ans=ans*ans%mod;
    ans=ans*ma%mod;
  }else{
    ans=0;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        int len = Math.max(s.length(), t.length());
        int[][] dp = new int[len + 1][len + 1];

        // dp
        for (int i = 0; i < s.length(); i++) {
            char cs = s.charAt(i);
            for (int j = 0; j < t.length(); j++) {
                char ct = t.charAt(j);
                if (cs == ct) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1],
                        Math.max(dp[i + 1][j], dp[i][j + 1]));
            }
        }
        // 復元
        StringBuilder ans = new StringBuilder();
        int i = s.length();
        int j = t.length();
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            } else if (dp[i][j] == dp[i][j - 1]) {
                j--;
            } else {
                ans.insert(0, s.charAt(i - 1));
                i--;
                j--;
            }
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 83020