akhauriyash/Code-Regression huggingface dataset:
n,k = map(int, input().split())
a = list(map(int, input().split()))
ans = float('inf')

for i in range(2**n):
    height = a[0]
    count = 1
    cost = 0
    for j in range(1,n):
        if (i>>j)&1:
            cost += max(0,(height-a[j]+1))
            height = max(height+1, a[j])
            count +=1
        else:
            if a[j] > height:
                count +=1
                height = a[j]
    if count >= k:
        ans = min(ans, cost)
print(ans)

Measured memory_bytes: 44140
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int N = 100010, P = 1000000007;

int n, m, cnt;
int x[N], y[N], dx[N];
pair<int, int> a[N];
int fw[N];

void add(int& x, int y) {
  if ((x += y) >= P)
    x -= P;
}

int norm(int x) { return x >= P ? (x - P) : x; }

int lowBit(int k) { return k & -k; }

void ch(int k, int x) {
  for (; k <= cnt; k += lowBit(k))
    add(fw[k], x);
}

int qry(int k) {
  int ret = 0;
  while (k) {
    add(ret, fw[k]);
    k &= k - 1;
  }
  return ret;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    cin >> x[i];
  for (int i = 1; i <= m; ++i)
    cin >> y[i];
  for (int i = 1; i <= n; ++i) {
    if (x[i] < y[1] || x[i] > y[m])
      continue;
    int id = lower_bound(y + 1, y + m + 1, x[i]) - y;
    a[++cnt] = make_pair(x[i] - y[id - 1], y[id] - x[i]);
    dx[cnt] = a[cnt].second;
  }
  int ans = 1;
  sort(dx + 1, dx + cnt + 1);
  sort(a + 1, a + cnt + 1, [](const auto& lhs, const auto& rhs) { return lhs.first == rhs.first ? (lhs.second > rhs.second) : (lhs.first < rhs.first); });
  for (int i = 1; i <= cnt; ++i) {
    if (a[i] == a[i - 1]) continue;
    int pos = lower_bound(dx + 1, dx + cnt + 1, a[i].second) - dx;
    int cur = norm(qry(pos - 1) + 1);
    add(ans, cur);
    ch(pos, cur);
  }
  cout << ans << '\n';

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 2560
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

M,K = map(int,input().split())
ans = False
if M == 0:
    if K == 0:
        ans = [0,0]
    else:
        print(-1)

elif M == 1:
    if K == 0:
        ans = [0,0,1,1]
    else:
        print(-1)

else:
    if K < 2**M:
        b = [int(i) for i in range(2**M)]
        b.remove(K)
        ans = []
        ans += b
        ans += [K]
        b.reverse()
        ans += b
        ans += [K]

    else:
        print(-1)
if ans == False:pass
else:
    for i in range(len(ans)):
        print(str(ans[i])+" ",end="")
    print("")


Measured memory_bytes: 14636
process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(string => {
        return string.trim();
    });
    
    atA();
});

function readline() {
    return inputString[currentLine++];
}

function pi(a) {
    return parseInt(a);
}

function probA(){
    let t = parseInt(readline());
    while(t > 0){
        t--;
        let [n,k] = readline().split(' ');
        n = pi(n);
        k = pi(k);

        if(n < k)
            console.log(k-n);
        else{
            if((n+k) % 2 === 0){
                console.log(0);
            }else{
                console.log(1);
            }
        }
    }
}

function probB(){
    let t = pi(readline());

    while(t > 0){
        t--;
        let a = readline().split(' ');
        let b = readline().split(' ');

        a[0] = pi(a[0]);
        a[1] = pi(a[1]);
        a[2] = pi(a[2]);

        b[0] = pi(b[0]);
        b[1] = pi(b[1]);
        b[2] = pi(b[2]);

        let maxSum = 0;
        if(b[2] - (a[0] + a[2]) > 0){
            b[2] = b[2] - (a[0]+a[2]);
            a[0] = 0;
            a[2] = 0;
        }else if(b[2] - a[0] > 0){
            a[2] = a[2] - (b[2] - a[0]);
            b[2] = 0;
            a[0] = 0;
        }else{
            a[0] -= b[2];
            b[2] = 0;
        }

        if(a[2] > b[1])
            console.log((b[1] - b[2]) * 2)
        else
            console.log((a[2]-b[2]) * 2);

    }
}

function probC(){
    let t = pi(readline());
    while(t > 0){
        t--;
        let n = pi(readline());
        let a = readline().split(' ');
        let x = JSON.parse(JSON.stringify(a));

        x.sort((a,b) => pi(a) - pi(b));
        let res = true;
        for(let i = 0; i < n; i++){
            if(x[i] !== a[i]){
                if(pi(a[i]) % pi(x[0]) !== 0){
                    res = false;
                    break;
                }
            }
        }

        if(res)
            console.log('yes');
        else
            console.log('no');
    }
}

function atA(){
    let [n,x,t] = readline().split(' ');
    n = pi(n);
    x = pi(x);
    t = pi(t);

    if(n < x)
        console.log(t);
    else{
        if(n % x === 0){
            console.log((n/x) * t);
        }else{
            console.log(Math.ceil(n/x) * t);
        }
    }
}

Measured memory_bytes: 29988
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int main()
{
    string o, e;
    cin >> o >> e;
    string s = "";
    for (int i = 0; i < int(o.size() + e.size()); i++) {
        if (i % 2 == 0) {
            s += o[i / 2];
        } else {
            s += e[i / 2];
        }
    }
    cout << s << endl;
}


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

int main(){
  int N;cin >> N;
  vector<ll> A(N,0);
  for(int i=0;i<N;i++){
    cin >> A[i];
  }
  for(int i=N-1;i>=0;i -= 2){
    cout << A[i] << " ";
  }
  for(int i=N%2;i<N;i+=2){
    cout << A[i] << " ";
  }
  cout << endl;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int N, K;
vector<int> u, v;
template <typename T>
void print(vector<T> vec)
{
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << (i == n - 1 ? "\n" : " ");
    }
}

stack<int> st;
string s;
int a, b;

int main()
{
    while (cin >> s)
    {
        if (s == "+")
        {
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            st.push(a + b);
        }
        else if (s == "-")
        {
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            st.push(b - a);
        }
        else if (s == "*")
        {

            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            st.push(a * b);
        }
        else
        {
            a = stoi(s);
            st.push(a);
        }
    }
    cout << st.top() << endl;
}


Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;
int main(){
  int x,y; cin >> x >> y;
  bool ans = false;
  for(int i=0;i<x+1;i++){
    if(i*4+(x-i)*2==y) ans = true;
  }
  if(ans) puts("Yes");
  else puts("No");
}


Measured memory_bytes: 3640
s = gets.chomp!.to_i
x = Math.sqrt(s).to_i + 1

x2 = x
y3 = x
diff = (x2 * y3) - s
if x > 10 ** 9
    x2 = 10 ** 9
    y3 = 10 ** 9
    diff = (x2 * y3) - s
end

if x2 * y3 == s
    puts "0 0 #{x2} 0 0 #{y3}"
else
    puts "0 0 #{x2} 1 #{diff} #{y3}"
end




Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int col[100010];
vector<int>v[100010];
int n,m;
bool f=false;
int s;
void dfs(int x,int c)
{
	col[x]=c;
	if(c==1)s++;
	for(int i=0;i<v[x].size();i++)
	{
		int y=v[x][i];
		if(col[y]==c)
		{
			f=true;
			return;
		}
		if(col[y]==0)dfs(y,-c);
		if(f)return;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,1);
	if(!f)printf("%lld",1LL*s*(n-s)-m);else printf("%lld",1LL*n*(n-1)/2-m);
	return 0;
}

Measured memory_bytes: 6528
#075_B
h,w=map(int,input().split())
s=['.'*(w+2)]+[list('.'+input()+'.') for _ in range(h)]+['.'*(w+2)]

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=='.':
            s[i][j]=sum([s[i+_i][j+_j]=='#' for _i in range(-1,2) for _j in range(-1,2)])
    print(*s[i][1:w+1],sep='')

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

using int64 = long long;
using uint64 = unsigned long long;

using namespace std;

constexpr int MAX_N = 100000;
constexpr int INF = 1 << 28;

vector<int> graph[MAX_N];

int n;
int dist_t[MAX_N], dist_a[MAX_N];

void BFS(int dist[], int s) {
    fill(dist, dist + n, INF);
    queue<int> queue;
    queue.push(s);
    dist[s] = 0;
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();

        for (int to : graph[u]) {
            if (dist[to] > dist[u] + 1) {
                dist[to] = dist[u] + 1;
                queue.push(to);
            }
        }
    }
}

bool check(int move_a, int move_t) {
    for (int u = 0; u < n; u++) {
        if (dist_t[u] <= move_t && dist_a[u] > move_a) {
            return false;
        }
    }
    return true;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int u, v;
    cin >> n >> u >> v;
    u--;
    v--;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    BFS(dist_t, u);
    BFS(dist_a, v);

    int lb = -1,
        ub = n;
    while (ub - lb > 1) {
        int mid = (lb + ub) / 2;
        if (check(mid, mid + (dist_t[v] % 2))) {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    cout << ub - 1 << endl;

    return 0;
}



Measured memory_bytes: 6656
# input
W, H, N = map(int, input().split())
x, y, a = [0]*N, [0]*N, [0]*N
for i in range(N):
    tmp_x, tmp_y, tmp_a = map(int, input().split())
    x[i], y[i], a[i] = tmp_x, tmp_y, tmp_a
xya = zip(x,y,a)

W_L, W_R, W_H0, W_H1 = 0, W, 0, H
for x_i, y_i, a_i in xya:
    if a_i == 1:
        W_L = max(W_L,x_i)
    if a_i == 2:
        W_R = min(W_R,x_i)
    if a_i == 3:
        W_H0 = max(W_H0,y_i)
    if a_i == 4:
        W_H1 = min(W_H1,y_i)

if W_R-W_L <= 0 or W_H1-W_H0 <= 0:
    print(0)
else:
    print(abs(W_R-W_L)*abs(W_H1-W_H0))

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

#define ll long long

int main()
{
    int k;
    cin >> k;
    
    ll ans = 0;
    
    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= k; j++)
        {
            for(int c = 1; c <= k; c++)
            {
                ans += __gcd(__gcd(i, j), c);
            }
        }
    }
    
    cout << ans;

    return 0;
}


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

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int z = 0;
		ArrayList<Integer> d1 = new ArrayList<>();
		ArrayList<Integer> d2 = new ArrayList<>();

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

			d1.add(sc.nextInt());
			d2.add(sc.nextInt());

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

			if(d1.get(i)==d2.get(i)) {
				z++;
			}else {
				z=0;
			}

			if(z==3) {
				break;
			}

		}

		if(z==3) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}


	}

}

Measured memory_bytes: 35976
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<string> w(n);
  int i;
  for(i=0;i<n;i++){
    cin >> w[i] ;
  }
  int j;
  string ans = "Yes";
  int l;
  if(w[0] == w[1]){
          ans = "No";
  }
  for(i=1;i<n;i++){
    l = w[i-1].length() - 1;
    if(w[i][0] != w[i-1][l]){
      ans = "No";
    }
    for(j=0;j<n;j++){
      if(i != j){
        if(w[i] == w[j]){
          ans = "No";
        }
      }
    }
  }
  cout << ans << endl;
}
      

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

constexpr int H_MAX = 1001;
constexpr int W_MAX = 1001;
char s[H_MAX][W_MAX] = {};
int dp[H_MAX][W_MAX] = {};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int UNREACHABLE = 1000000000;

struct Point{
    int x;
    int y;
    int n;
};

int main()
{
    int h, w, ch, cw, dh, dw;
    cin >> h >> w >> ch >> cw >> dh >> dw;
    for(int i=1; i<=h; ++i){
        for(int j=1; j<=w; ++j){
            cin >> s[i][j];
            dp[i][j] = UNREACHABLE;
        }
    }
    auto cmp = [](Point &a, Point &b){return a.n > b.n;};
    priority_queue<Point, vector<Point>, decltype(cmp)> pq(cmp);
    pq.push({ch, cw, 0});
    dp[ch][cw] = 0;
    while(!pq.empty()){
        auto pos = pq.top();
        pq.pop();
        // 歩いて移動
        for(int i=0; i<4; ++i){
            int x = pos.x + dx[i];
            int y = pos.y + dy[i];
            if (x < 1 || x > h || y < 1 || y > w) continue;
            if (s[x][y] == '.' && dp[x][y] > dp[pos.x][pos.y]){
                dp[x][y] = dp[pos.x][pos.y];
                pq.push({x, y, dp[x][y]});
            }
        }
        // ワープ移動
        for(int i=max(1, pos.x - 2); i<=min(h, pos.x + 2); ++i){
            for(int j=max(1, pos.y - 2); j<=min(w, pos.y + 2); ++j){
                if (s[i][j] == '.' && dp[i][j] > dp[pos.x][pos.y] + 1){
                    dp[i][j] = dp[pos.x][pos.y] + 1;
                    pq.push({i, j, dp[i][j]});
                }
            }
        }
    }
    if (dp[dh][dw] == UNREACHABLE){
        cout << -1;
    }else{
        cout << dp[dh][dw];
    }
    return 0;
}


Measured memory_bytes: 8592
N, W = map(int,input().split())
v = [0]*(N+1)
w = [0]*(N+1)
for i in range(1,N+1):
    v[i], w[i] = map(int,input().split())
    
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if j-w[i]>=0:
            dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])


Measured memory_bytes: 41888
import java.util.Scanner;

class Solver {
    public void Solve() {
        long h = sc.nextLong();
        long w = sc.nextLong();
        long ans = ((h * w) + 1) / 2;
        if (h == 1 || w == 1) {
            System.out.println(1);
            return;
        }
        System.out.println(ans);
    }

    Scanner sc;

    Solver(Scanner in) {
        this.sc = in;
    }
}

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


Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N,K;
vector<int>G[100001];
int a[100001];
int ans=0;
int dfs(int x,int d){
	/*if(G[x].size()==0){
		/*if(d>K){
			return 1;
		}else{
			return 0;
		}
		return 1;
	}*/
	int ma=0;
	REP(i,G[x].size()){
		int a=dfs(G[x][i],d+1);
		ma=max(a,ma);
	}
	if(ma==K-1&&d!=1&&d!=0){
		ans++;
		//cout<<x<<endl;
		return 0;
	}
	/*
	if(d>K){
		return ma+1;
	}else{
		return ma;
	}
	*/
	return ma+1;
}

int main(){
	cin>>N>>K;
	REP(i,N){
		cin>>a[i];
		a[i]--;
	}
	if(a[0]!=0){
		ans++;
		a[0]=0;
	}
	
	if(K==1){
		REP(i,N){
			if(a[i]!=0)ans++;
		}
		cout<<ans<<endl;
		return 0;
	}
	
	for(int i=1;i<N;i++){
		G[a[i]].push_back(i);
	}
	int a=dfs(0,0);
	//if(a!=0)ans++;
	cout<<ans<<endl;
	return 0;
}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

// 3乗で通したお詫びにO(NlogN)で通します
// 参考 : https://twitter.com/SayakaAmemiya/status/1249515024541859842

// optimized for small mod
template<int mod, int proot> struct NTT {
	int get_mod() { return mod; }
	int pow(int a, int b) {
	int res = 1;
		for (; b; b >>= 1) {
			if (b & 1) res = res * a % mod;
			a = a * a % mod;
		}
		return res;
	}
	int inv(int i) { return pow(i, mod - 2); }
	void ntt(std::vector<int> &a, bool inverse) {
		int n = a.size();
		assert((n & -n) == n);
		int h = pow(proot, (mod - 1) / n);
		if (inverse) h = inv(h);
		
		for (int i = 0, j = 1; j < n - 1; j++) {
			for (int k = n >> 1; k > (i ^= k); k >>= 1);
			if (j < i) std::swap(a[i], a[j]);
		}
		for (int i = 1; i < n; i <<= 1) {
			int base = pow(h, n / i / 2);
			int w = 1;
			
			std::vector<int> ws(i);
			for (int j = 0; j < i; j++) ws[j] = w, w = w * base % mod;
			
			for (int j = 0; j < n; j += i << 1) {
				for (int k = 0; k < i; k++) {
					int u = a[k + j];
					int d = a[k + j + i] * ws[k] % mod;
					a[k + j] = u + d >= mod ? u + d - mod : u + d;
					a[k + j + i] = d > u ? u + mod - d : u - d;
				}
			}
		}
		if (inverse) {
			int ninv = inv(a.size());
			for (auto &i : a) i = i * ninv % mod;
		}
	}
};

int main() {
	int n = ri();
	int back[3] = { 0 };
	int forward[3] = { 0 };
	std::vector<int> a(n);
	{
		char tmp[4096];
		scanf("%s", tmp);
		for (int i = 0; i < n; i++) {
			a[i] = tmp[i] == 'R' ? 0 : tmp[i] == 'G' ? 1 : 2;
			back[a[i]]++;
		}
	}
	
	int64_t res = 0;
	// j - i != k - jを無視したの
	for (int j = 0; j < n; j++) {
		back[a[j]]--;
		res += forward[(a[j] + 1) % 3] * back[(a[j] + 2) % 3];
		res += forward[(a[j] + 2) % 3] * back[(a[j] + 1) % 3];
		forward[a[j]]++;
	}
	// j - i == k - jで相異なるものを引く
	int n2 = 1;
	for (; n2 < n + n - 1; n2 <<= 1);
	NTT<40961, 3> ntt;
	std::vector<int> count[3];
	for (auto &i : count) i.resize(n2);
	for (int i = 0; i < n; i++) count[a[i]][i]++;
	for (auto &i : count) ntt.ntt(i, false);
	
	std::vector<int> conved[3]; // conved count[i], count[(i + 1) % 3]
	for (int i = 0; i < 3; i++) {
		auto &cur = conved[i];
		cur.resize(n2);
		for (int j = 0; j < n2; j++) cur[j] = count[i][j] * count[(i + 1) % 3][j] % 40961;
		ntt.ntt(cur, true);
	}
	for (int j = 0; j < n; j++) res -= conved[(a[j] + 1) % 3][j + j];
	
	printf("%" PRId64 "\n", res);
	
	return 0;
}


Measured memory_bytes: 4000
inp = input().split()

i = 1
x = 0

while i <= pow(10,18):
	if inp[0] == "1" and inp[1] == "1":
		print(-1)
		x = 1
		break
	if i % int(inp[0])  == 0 and i % int(inp[1]) != 0:
		print(i)
		x = 1
		break
	i *= int(inp[0])

if x == 0:
	print(-1)

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

#define ll long long
#define ull long long unsigned
#define vii vector<int>
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define pldld pair<long long double, long long double>
#define ff first
#define ss second
#define pb push_back
#define read freopen("alu.txt","r",stdin);
#define write freopen("vorta.txt","w",stdout);
#define fastio ios::sync_with_stdio(false); cin.tie(NULL);
#define PI 2*acos(0.0)

const int MAX=100005, MOD=1000000007;
const ll inf=1e9;

int arr[MAX];
string s[2];
int n;
ll ans=1;
void solve(int i, bool last){
    if(i>=n) return;
    else if(s[0][i]!=s[1][i]){
        if(last) ans*=3;
        else ans*=2;
        ans%=MOD;
        solve(i+2,true);
    }
    else{
        if(last) ans*=1;
        else ans*=2;
        ans%=MOD;
        solve(i+1,false);
    }
}

int main(){

    fastio;
    cin>>n;
    cin>>s[0]>>s[1];
    if(s[0][0]!=s[1][0]){
        ans*=6;
        solve(2,true);
    }
    else{
        ans*=3;
        solve(1,false);
    }
    cout<<ans<<"\n";


}











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

using namespace std;

#define pii pair<int,int>
#define ll long long
#define s second
#define f first

const int MAX_N=2*10e5+5;
ll n,k,a[MAX_N];
double ex,mx=-1;

int main(){
  cin >> n >> k;
  for(int i=0;i<n;++i){
    cin >> a[i];
  }
  for(int i=0;i<k;++i){
    double p=a[i]+1;
    ex+=p/2;
  }
  for(int i=k;i<n;++i){
    //cout << ex << endl;
    mx=max(mx,ex);
    double p=a[i]+1;
    ex+=p/2;
    p=a[i-k]+1;
    ex-=p/2;
  }
  cout << setprecision(10) << max(mx,ex);
  return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main() {
	cin >> n;
  	int arr[n];
  	int sum = 0;
  	for (int i = 0; i < n; i++) {
    	cin >> arr[i];
      	sum += arr[i];
    }
  	int m1 = sum / n;
  	int m2 = sum / n + 1;
  	int c1 = 0;
  	int c2 = 0;
  	for (int i = 0; i < n; i++) {
    	c1 += (arr[i]-m1) * (arr[i]-m1);
     	c2 += (arr[i]-m2) * (arr[i]-m2);
    }
  	cout << min(c1, c2);
  
  
}

Measured memory_bytes: 3160
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def main():
    n = int(ipt())
    s = input()
    q = int(ipt())
    alp = "abcdefghijklmnopqrstuvwxyz"
    sn = [2**(alp.find(i)) for i in s]

    def segfunc(x,y):
        return x|y

    def popcnt(n):
        return bin(n).count("1")

    ST = SegTree(sn,segfunc,0)
    for i in range(q):
        nm = tuple(input().split())
        if nm[0] == "1":
            ST.update(int(nm[1])-1,2**(alp.find(nm[2])))
        else:
            print(popcnt(ST.query(int(nm[1])-1,int(nm[2]))))


    return None

if __name__ == '__main__':
    main()


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


int main() {
  int N;
  cin >> N;
  vector<string> vec(N);
  rep(i, N) cin >> vec[i];
  
  rep(i, N) {
    rep(j, N) {
      if(vec[i] == vec[j] && i != j) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  
  rep(i, N-1) {
    if(vec[i][vec[i].size()-1] != vec[i+1][0]) {
      cout << "No" << endl;
      return 0;
    }
  }
  
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
import java.util.*;


class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long n = sc.nextInt();
    long k = sc.nextInt();
    
    long ans = 0;
    long mod = 1000000007;
    long min = (1+k)*k/2;
    long max = (n+1)*n/2;
    long p;
    
    for(long i=k;i<=n+1;i++){  
      ans += (((n-i+1)+n)*i/2 - (i-1)*i/2 + 1) % mod;
      ans %= mod;
    }
    System.out.println(ans);
    
    
  }
}

Measured memory_bytes: 35800
// AOJ DSL_3_C The Number of Windows
// 2018.5.6 bal4u@uu

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

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in() {
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

long long ll() {
	long long n = 0;
	int c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

#define MAX_N 100005
long long s[MAX_N];

int main()
{
	int N, Q, i, j;
	long long base, x, ans;

	N = in(), Q = in();
	base = (long long)N*(N+1) >> 1;

	for (i = 1; i <= N; i++) s[i] = s[i-1] + in();
	s[i] = 0x10101010101010LL;
	while (Q--) {
		x = ll();
		j = 1; while (s[j] <= x) j++;
		ans = 0, i = 0;
		while (1) {
			while (s[j]-s[i] > x) i++, ans += N-j+1;
			while (j <= N && s[j]-s[i] <= x) j++;
			if (j > N) break;
		}
		printf("%lld\n", base-ans);
	}
	return 0;
}


Measured memory_bytes: 2480
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;
typedef long double ld;
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int d;
    cin >> d;
    switch(d)
    {
    case 25:
        cout << "Christmas";
        break;
    case 24:
        cout << "Christmas Eve";
        break;
    case 23:
        cout << "Christmas Eve Eve";
        break;
    default:
        cout << "Christmas Eve Eve Eve";
    }

    return 0;
}


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

class Edge
{
public:
	int v,d,c;

	Edge(){}
	Edge(int v, int d, int c)
		:v(v),d(d),c(c)
	{}

	bool operator<(const Edge& e) const 
	{

		if(d!=e.d) return d>e.d;
		return c>e.c;
	}
};

typedef vector<Edge> G;

int main()
{
	int N,M;
	while(cin >> N >> M, (N||M))
	{
		vector<G> edges(10009);
		for(int i=0; i<M; i++)
		{
			int u,v,d,c;
			cin >> u >> v >> d >> c;
			u--; v--;

			edges[u].push_back(Edge(v,d,c));
			edges[v].push_back(Edge(u,d,c));
		}

		priority_queue<Edge> q;
		q.push(Edge(0,0,0));
		bool v[10009]={0};

		int ret=0;

		while(!q.empty())
		{
			Edge s=q.top(); q.pop();
			if(v[s.v]) continue;
			v[s.v]=1;

			ret+=s.c;
			s.c=0;

			for(int i=0; i<edges[s.v].size(); i++)
			{
				Edge e=edges[s.v][i];
				if(v[e.v]) continue;

				q.push(Edge(e.v, e.d+s.d, e.c+s.c));
			}
		}

		cout << ret << endl;
	}
}

Measured memory_bytes: 1744
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
using Graph=vector<vector<int>>;

int main()
{
  int N,M;cin>>N>>M;
  vector<int> H(N+1,0);
  for (int i=1;i<=N;i++)
    cin>>H[i];
  
  Graph G(N+1);
  for (int i=1;i<=M;i++)
  {
    int a,b;cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);	
  }
  
  int count=0;
  for (int i=1;i<=N;i++)
  {
    int flag=1;
    for (auto n: G[i])
    {
      if (H[n]>=H[i]) flag = 0;
    }
    //int c=check(G[i]);
    if (flag==1)
    {
      count++;
      //cout<<"i; "<<i<<endl;
    }
    //count-=c;
  }
  cout<<count<<endl;
}


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

int main()
{
    int n;
    cin >> n;
    
    vector<int> v(n);
    
    for(int i = 0; i < n; i++){
        cin >> v.at(i);
    }
    
    sort(v.begin(),v.end());
    cout << v[n-1] - v[0] << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7


int main() {

	int A, B;
	scanf("%d%d", &A, &B);

	if (A <= 8 && B <= 8)printf("Yay!");
	else printf(":(");











}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define BPhuong "main"
#define maxn 100005
#define maxm
#define fi(i,a,b) for(int i = a; i<= b; i++)
#define fid(i,a,b) for(int i = a; i>= b; i--)
#define se second
#define f first
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define bit(x, i) ((x>>i)&1)
#define oo 1e9
struct data{
    int x, y, z;
};
using namespace std;
int n, m, l[maxn], cl[maxn];
vector <int> a[maxn];
void dfs(int u)
{
    cl[u] = 1;
    l[u] = 0;
    for(int i = 0; i < a[u].size(); i++)
    {
        int v = a[u][i];
        if(cl[v] == 0) dfs(v);
        l[u] = max(l[u], l[v]+1);
    }
    //l[u]++;
}
void nhap(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    //freopen(BPhuong".inp","r",stdin);
    //freopen(BPhuong".out","w",stdout);
    cin >> n >> m;
    fi(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        a[u].pb(v);
    }

}

void xuli(){
    int ans = 0;
    fi(i, 1, n)
    {
        if(!cl[i])
        {
            dfs(i);
        }
        ans = max(ans, l[i]);
    }
    //fi(i, 1, n) cout << l[i] << ' ';cout << '\n';
    cout << ans;
}

int main(){
    nhap();
    xuli();
}


Measured memory_bytes: 12528
#include <stdio.h>

int main(void){
    int a,b,c,d,e,t;
    scanf("%d",&a);scanf("%d",&b);scanf("%d",&c);scanf("%d",&d);scanf("%d",&e);
    t=0;
    if(a<0){
        t=-a*c+d;
        a=0;
    }
    t+=(b-a)*e;
    printf("%d\n",t);
}


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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 4 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

int M[MAX][MAX];

string solve(const vector<int>& xs)
{
    for (auto x : xs)
    { 
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j)
                if (M[i][j] == x)
                    M[i][j] = 0;
    }

    for (int i = 0; i < 3; ++i)
    {
        int sum = 0;

        for (int j = 0; j < 3; ++j)
            sum += M[i][j];

        if (sum == 0)
            return "Yes";
    }

    for (int j = 0; j < 3; ++j)
    {
        int sum = 0;

        for (int i = 0; i < 3; ++i)
            sum += M[i][j];

        if (sum == 0)
            return "Yes";
    }

    int sum = 0;

    for (int i = 0; i < 3; ++i)
        sum += M[i][i];

    if (sum == 0)
        return "Yes";

    sum = 0;

    for (int i = 0; i < 3; ++i)
        sum += M[i][2 - i];

    if (sum == 0)
        return "Yes";

    return "No";
}

int main()
{
    ios::sync_with_stdio(false);

    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> M[i][j];

    int N;
    cin >> N;

    vector<int> xs(N);

    for (int i = 0; i < N; ++i)
        cin >> xs[i];

    auto ans = solve(xs);

    cout << ans << '\n';

    return 0;
}


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

using namespace std;
int main()
{
    string s,t;
    cin >> s >> t;

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

    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    if (s < t)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [0] * (s * 2 + 1)
# dp[s+i] ... count of i = B - R - G
dp[s] = 1
for ai in a:
    ndp = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp[j] != 0:
            ndp[j+ai] += dp[j]
            ndp[j+ai] %= MOD
            ndp[j-ai] += dp[j] * 2
            ndp[j-ai] %= MOD
    dp = ndp
# exclude B >= R + G
# beware cases like B == R and G == 0

# dp2[s+i] ... count of i = B - R, assuming G is always 0
dp2 = [0] * (s * 2 + 1)
dp2[s] = 1
for ai in a:
    ndp2 = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp2[j] != 0:
            ndp2[j+ai] += dp2[j]
            ndp2[j+ai] %= MOD
            ndp2[j-ai] += dp2[j]
            ndp2[j-ai] %= MOD
    dp2 = ndp2
#print(sum(dp[s+1:]), sum(dp2[s+1:]))
ans = (pow(3, n, MOD) - ((sum(dp[s:]) - dp2[s] * 2) * 3 + dp2[s] * 3)) % MOD
print(ans)

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    ll N,K; cin >> N >> K;
    VL H(N+1,0); REP(i,N) cin >> H[i+1];

    if(N == K){
        cout << 0 << en;
        return 0;
    }

    ll dp[N+1][K+1]; REP(i,N+1)REP(j,K+1) dp[i][j] = LINF;
    dp[0][0] = 0;
    REP(i,N)REP(j,K+1){
        REP(k,i+1){
            if(i-k < 0 || j-k < 0) break;
            chmin(dp[i+1][j], dp[i-k][j-k] + max((ll)0, H[i+1]-H[i-k]));
        }
    }

    ll ans = LINF;
    REP(i,K+1) chmin(ans, dp[N-i][K-i]);
    cout << ans << en;
    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#include<math.h>
#define PI 3.14159265

int main(void)
{
	double a, b, c, s, C;
	double S, L, h;

	scanf("%lf %lf %lf", &a, &b, &C);
	/*残りの一片の長さcを求める(余弦定理)*/
	c = sqrt(a*a + b*b - 2 * a*b*cos(C*PI / 180));
	/*周の長さLを求める*/
	L = a + b + c;
	/*面積Sを求める(ヘロンの公式)*/
	s = (a + b + c) / 2;
	S = sqrt(s*(s - a)*(s - b)*(s - c));
	/*高さhを求める*/
	h = 2 * S / a;

	printf("%f\n%f\n%f\n", S, L, h);
	return 0;
}


Measured memory_bytes: 2056
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define SORT(c) sort((c).begin(),(c).end())
#define MOD 1000000007
//S.size()
//配列名.Length()
using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<bool> VB;
typedef unsigned long long ll;


int main(void){
	int N,D; cin>>N>>D;
	int k = N % (D * 2 + 1);
	cout<<(k == 0 ? N / (D * 2 + 1):N/(D*2+1) + 1);
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int n,s=0;
	int p=3;
	cin>>n;
	if(n<=2){
		cout<<0;
		return 0;
	}
	while(n) {
		while(n>=p+3||n==p) {
			s++;
			n-=p;
		}
		p++;
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <map>
#include <bitset>
#include <numeric>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[8]={ 0, 1, 0,-1, 1, 1,-1,-1}; // x軸方向への変位
ll dy[8]={ 1, 0,-1, 0, 1,-1, 1,-1}; // y軸方向への変位

int main(void) {
    ll n;
    cin >> n;
    ll a[n+1];
    for(ll i = 0; i < n; i++)
        cin >> a[i];
    a[n] = -100;
    sort(a, a+n, greater<ll>());
    vector<p> vp;
    ll count = 0;
    ll check = 0;
    for(ll i = 0; i <= n; i++){
        count++;
        if(a[i]!=a[i+1]) {
            if(count >= 2)
            vp.push_back(p(a[i], count));
            count = 0;
        }
    }
    ll b = vp.size();
    if(b==0)
        cout << 0 << endl;
    else if(b<2 && vp[0].second<4)
        cout << 0 << endl;
    else if(vp[0].second>=4)
        cout << vp[0].first*vp[0].first << endl;
    else
        cout << vp[0].first*vp[1].first << endl;
    return 0;
}


Measured memory_bytes: 2168
#include<iostream>
#include<algorithm>
#include<list>

using namespace std;

int main(){
    int n, num, order, d;
    list<int> a, out;
    cin >> n;
    list<int>::iterator it = a.begin();
    for(int i=0;i<n;i++){
        cin >> order;
        switch (order){
        case 0:
            cin >> num;
            it = a.insert(it, num);
            break;
        case 1:
            cin >> num;
            advance(it, num);
            break;
        case 2:
            it = a.erase(it);
            break;
        default:
            break;
        }
    }
    it = a.begin();
    while(it!=a.end()) {
        cout << *it << endl;
        it++;
    }    
}


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

int main(){
    long long S;
    cin >> S;
    long long v = 1000000000;
    long long X = (v-S%v)%v;
    long long Y = (S+X)/v;
    cout << 0 << " " << 0 << " " << 1000000000 << " " << 1 << " " << X << " " << Y <<endl;
}

Measured memory_bytes: 256
from fractions import gcd

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

n = int(input())
a = list(map(int, input().split()))
l=1;ans=0
for i in a:
	l = lcm(l, i)
l-=1
for i in a:
	ans += l%i
print(ans)

Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int> a[1<<20],dis[1<<20],faL[1<<20],faR[1<<20],faU[1<<20],faD[1<<20];
int n,m,k,sx,sy,tx,ty,qx[1<<20],qy[1<<20];
char s[1<<20];
int getF(vector<int>&fa,int x){return fa[x]==x?x:fa[x]=getF(fa,fa[x]);}
int main(){
	scanf("%d%d%d%d%d%d%d",&n,&m,&k,&sx,&sy,&tx,&ty);
	for(int i=1;i<=n;i++){
		a[i].resize(m+1),dis[i].resize(m+1,2e9);
		faL[i].resize(m+2),faR[i].resize(m+2);
		scanf(" %s",s+1);
		for(int j=1;j<=m;j++)a[i][j]=s[j]=='@';
		for(int j=0;j<=m+1;j++)faL[i][j]=faR[i][j]=j;
	}
	for(int i=1;i<=m;i++){
		faU[i].resize(n+2),faD[i].resize(n+2);
		for(int j=0;j<=n+1;j++)faU[i][j]=faD[i][j]=j;
	}
	int l=1,r=1;qx[1]=sx,qy[1]=sy;
	dis[sx][sy]=0;
	while(l<=r){
		int x=qx[l],y=qy[l++],d=dis[x][y];
		if(x==tx && y==ty)printf("%d\n",d),exit(0);
		for(int i=getF(faU[y],x-1);i>=x-k && i && !a[i][y];i=getF(faU[y],i-1)){
			if(dis[i][y]>1e9)dis[i][y]=d+1,qx[++r]=i,qy[r]=y;
			faU[y][i]=i-1;
		}
		for(int i=getF(faD[y],x+1);i<=x+k && i<=n && !a[i][y];i=getF(faD[y],i+1)){
			if(dis[i][y]>1e9)dis[i][y]=d+1,qx[++r]=i,qy[r]=y;
			faD[y][i]=i+1;
		}
		for(int i=getF(faL[x],y-1);i>=y-k && i && !a[x][i];i=getF(faL[x],i-1)){
			if(dis[x][i]>1e9)dis[x][i]=d+1,qx[++r]=x,qy[r]=i;
			faL[x][i]=i-1;
		}
		for(int i=getF(faR[x],y+1);i<=y+k && i<=m && !a[x][i];i=getF(faR[x],i+1)){
			if(dis[x][i]>1e9)dis[x][i]=d+1,qx[++r]=x,qy[r]=i;
			faR[x][i]=i+1;
		}
	}
	puts("-1");
	return 0;
}

Measured memory_bytes: 234428
S = input()

if S[0] == "R" and S[1] == "R" and S[2] == "R":
    print(3)
elif S[0] == "R" and S[1] == "R":
    print(2)
elif S[1] == "R" and S[2] == "R":
    print(2)
elif S[0] == "R" or S[1] == "R" or S[2] == "R":
    print(1)
else:
    print(0)


Measured memory_bytes: 9052
import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        r = L[j] + L[i]
        ans += bisect.bisect_left(L[j+1:], r)
print(ans)

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

int func(long long n) {
	int digits = 0;
	while(n > 0) {
		n /= 10;
		digits++;
	}
	return digits;
}

int main(void) {
	long long i,j;
	long long n;
	cin >> n;
	int ans = 1e9;
	for (i = 1; i*i <= n; i++) {
		if (n % i == 0) {
			j = n /i;
			ans = min(ans, func(j));
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='.')
    s.append(si)

# 左に照らした場合 行ごとに見てゆく
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if s[i][j]:
            if j==0:
                L[i][j]=1
            else:
                L[i][j]=L[i][j-1]+1

# 右に照らした場合 行ごとに見てゆく
R=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in reversed(range(W)):
        if s[i][j]:
            if j==W-1:
                R[i][j]=1
            else:
                R[i][j]=R[i][j+1]+1

# 上に照らした場合 列ごとに見てゆく
U=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in range(H):
        if s[i][j]:
            if i==0:
                U[i][j]=1
            else:
                U[i][j]=U[i-1][j]+1

# 下に照らした場合 列ごとに見てゆく
D=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in reversed(range(H)):
        if s[i][j]:
            if i==H-1:
                D[i][j]=1
            else:
                D[i][j]=D[i+1][j]+1

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)

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

int main()
{
  string s, t, u;
  int a, b;
  cin >> s >> t >> a >> b >> u;
  if (s == u) {
    a--;
  } else {
    b--;
  }
  cout << a << " " << b << endl;
}


Measured memory_bytes: 256
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;




#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define pii                 pair<int,int>
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define N                   200007
#define inf                 100000008
#define mod                 1000000007

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/




int main()
{
    ll n;
    cin>>n;
    if(n)cout<<0<<endl;
    else cout<<1<<endl;
    return 0;
}





















Measured memory_bytes: 3584
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
/*answer*/
    int n;
    int a, b, c, d, count;

    for(;sc.hasNext();){
      n = sc.nextInt();
      count = 0;
      for(a = 0;a < 10;a++){
        for(b = 0;b < 10;b++){
          for(c = 0;c < 10;c++){
            d = n - a - b - c;
            if(d >= 0 && d <= 9)count++;
          }
        }
      }
      System.out.println(count);
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }
}

Measured memory_bytes: 18744
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Miguel Mini
 */

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
vi g[maxn];
int dp[maxn];
int f[maxn], rf[maxn];
int r[maxn];
int sz[maxn];

int add(int a, int b) {
    return a + b < mod ? a + b : a + b - mod;
}

int mul(ll a, ll b) {
    return a * b % mod;
}

int comb(int n, int m) {
    if (m > n) return 0;
    return mul(f[n], mul(rf[m], rf[n - m]));
}

void dfs(int x, int p) {
    dp[x] = sz[x] = 1;
    for (int v : g[x]) {
        if (v == p) continue;
        dfs(v, x);
        sz[x] += sz[v];
    }
    int m = sz[x] - 1;
    for (int v : g[x]) {
        if (v == p) continue;
        dp[x] = mul(dp[x], mul(dp[v], comb(m, sz[v])));
        m -= sz[v];
    }
}

int ex(int a, int b) {
    int r = 1;
    while (b > 0) {
        if (b&1) r = mul(r, a);
        a = mul(a, a);
        b >>= 1;
    }
    return r;
}

void dfs_reroot(int x, int p) {
    if (p != 0) {
        int temp = mul(dp[p], ex(mul(comb(sz[p] - 1, sz[x]), dp[x]), mod - 2));
        dp[x] = mul(dp[x], mul(temp, comb(sz[p] - 1, sz[p] - sz[x])));
        sz[x] = sz[p];
    }
    for (int v : g[x]) {
        if (v == p) continue;
        dfs_reroot(v, x);
    }
}

class FDistributingIntegers {
public:

    void solveOne(istream& in, ostream& out) {
        f[0] = rf[0] = r[1] = 1;
        re(i, 1, maxn) {
            if (i > 1) {
                r[i] = mul(mod / i, mod - r[mod % i]);
            }
            f[i] = mul(i, f[i-1]);
            rf[i] = mul(r[i], rf[i-1]);
        }
        int n;
        in >> n;
        re(i, 1, n+1) {
            g[i].clear();
        }
        re(i, 1, n) {
            int a, b;
            in >> a >> b;
            g[a].eb(b);
            g[b].eb(a);
        }
        dfs(1, 0);
        dfs_reroot(1, 0);
        int ans = 0;
        re(i, 1, n+1) {
            out << dp[i] << endl;
        }
    }

    void solve(istream& in, ostream& out) {
        int testNumber = 1;
        //in >> testNumber;
        re(tc, 1, testNumber+1) {
            //out << "Case #" << tc << ": ";
            solveOne(in, out);
        }
    }
};


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

Measured memory_bytes: 17780