akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll r,d,x;
    cin >> r >> d >> x;
    ll prev = x;
    for (int z=0;z<10;z++){
    	cout << r*prev-d << endl;
    	prev = r*prev-d;
    }
    cin >> r;
}

Measured memory_bytes: 256
def input():
    import sys
    return sys.stdin.readline().rstrip()


def main():
    import math
    import collections
    import itertools

    n = int(input())
    if n > 81:
        print("No")
        exit()

    for i in range(9, 0, -1):
        div, rem = divmod(n, i)
        if rem == 0 and div <= 9:
            print("Yes")
            exit()
    else:
        print("No")




if __name__ == '__main__':
    main()

Measured memory_bytes: 3564
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include<iomanip>

using namespace std;

struct Elem {
	int value;
	int num;

	Elem() : value(0), num(0) {
	}

	bool operator<(const Elem& r) {
		return value < r.value;
	}
	bool operator>(const Elem& r) {
		return value > r.value;
	}
};

int main() {
	
	long long n, k;
	vector<Elem> times;


	int a, b;
	
	cin >> n >> k;
	k--;

	while (cin >> a >> b) {
		Elem e;
		e.value = a;
		e.num = b;
		times.push_back(e);
	}

	sort(times.begin(), times.end());
	
	long long pos = 0;
	for (auto& e : times) {
		if (k < pos + e.num) {
			cout << e.value;
			break;
		} else {
			pos += e.num;
		}
		
	}

	cout << endl;
	

	return 0;

}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
std::string solve(std::string S){
    const int N=S.size();
    if(N<26){
        unsigned u=0;
        for(const auto c: S) u|=1u<<(c-'a');
        return S+static_cast<char>('a'+__builtin_ctz(~u));
    }
    else{
        unsigned u=0;
        for(int i=N-1; i>0; --i){
            const auto c=S[i], d=S[i-1];
            u|=1u<<(c-'a');
            if(d<c) return S.substr(0,i-1)+static_cast<char>('a'+__builtin_ctz(u&~((1u<<(d-'a'))-1)));
        }
    }
    return "-1";
}
int main(){
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(false);
    for(std::string S; std::cin >> S; ){
        std::cout << solve(S) << std::endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll i,j,n,k,m;
    cin>>n>>m;
    for(i=m-n+1;i<=m;i++)
    {
        cout<<i<<" ";
    }
    for(i=m+1;i<=m+n-1;i++)
    {
        cout<<i<<" ";
    }

    cout<<endl;
}


Measured memory_bytes: 384
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

n = ni()
E=0
for i in range(n-1):
    u,v = ma()
    if u>v:u,v=v,u
    E+=u*(n-v+1)
P = 0
for r in range(n):
    P+=r*(r+1)//2 +r+1
print(P-E)


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

int main() {
    int a, b, x;
    cin >> a >> b >> x;

    int div = min(a, 2*b);
    int ans = div*(x/1000);
    if (x%1000 > 500) ans += min(a, 2*b);
    else  if (x%1000 > 0) ans += min(a, b);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3100
#include<cstdio>
struct edge{
	int to,next,w;
}e[210000];
int first[110000],vis[110000];
long long dis[110000];
void dfs(int k,long long x)
{
	vis[k]=1;
	dis[k]=x;
	for(int i=first[k];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!vis[v]) dfs(v,(long long)x+e[i].w);
	}
}
int main()
{
    int num=0,n,a,b,c,q,k;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
    	scanf("%d%d%d",&a,&b,&c);
    	e[++num].w=c;
    	e[num].to=b;
    	e[num].next=first[a];
    	first[a]=num;
    	e[++num].w=c;
    	e[num].to=a;
    	e[num].next=first[b];
    	first[b]=num;
	}
	scanf("%d%d",&q,&k);
	dfs(k,0);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&a,&b);
		printf("%lld\n",dis[a]+dis[b]);
	}
    return 0;
}

Measured memory_bytes: 8832
a,b,c=map(int,input().split())
s1=0+abs(a-b)+abs(b-c)
s2=0+abs(a-c)+abs(b-c)
s3=0+abs(b-a)+abs(c-a)
s4=0+abs(b-c)+abs(c-a)
s5=0+abs(c-b)+abs(a-b)
s6=0+abs(c-a)+abs(a-b)
print(min(s1,s2,s3,s4,s5,s6))

Measured memory_bytes: 3064
from heapq import heappop, heappush
N, M = map(int, input().split())
route_list = [[] for _ in range(N)]
for i in range(M):
    L, R, C = map(int, input().split())
    route_list[L-1].append((R-1, C))
for i in range(N-1):
    route_list[i+1].append((i, 0))

distance = [float("inf")] * N
distance[0] = 0  # 初期のノードの距離は0とする
q = [(0, 0)]

while q:
    _, u = heappop(q)
    for des, cost in route_list[u]:
        if distance[des] > distance[u] + cost:
            distance[des] = distance[u] + cost
            heappush(q, (distance[des], des))

print(distance[-1] if distance[-1] != float("inf") else -1)

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

using ll = long long;
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define repi(n) for (int i = 0; i < n; i++)
#define repj(n) for (int j = 0; j < n; j++)
#define repk(n) for (int k = 0; j < n; k++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i = a; i < b; i++)
#define repv(itr) for (auto&& v : itr)
#define swap(x, y)    \
  {                   \
    auto ___temp = x; \
    x = y;            \
    y = ___temp;      \
  }

const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, -1, 1, -1, 1};
template <typename T>
T minptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i < *re) re = i;
  }
  return re;
}
template <typename T>
T maxptr(T begin, T end) {
  T re = begin;
  for (T i = begin + 1; i != end; i++) {
    if (*i > *re) re = i;
  }
  return re;
}
int __vmax(int x) {
  return INT_MAX;
}
double __vmax(double x) {
  return 1e+300;
}
ll __vmax(ll x) {
  return LLONG_MAX;
}
int __vmin(int x) {
  return INT_MIN;
}
double __vmin(double x) {
  return -1e+300;
}
ll __vmin(ll x) {
  return LLONG_MIN;
}
template <typename T>
vector<T> lis(T begin, T end, bool allowequal = false, bool lds = false) {
  using V = typename iterator_traits<T>::value_type;
  int n = end - begin;
  vector<V> a(n, lds ? __vmin(*begin) : __vmax(*begin));
  vector<int> id(n);
  if (lds && allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (lower_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (lds) {
    for (int i = 0; i < n; i++) {
      id[i] = n - 1 -
              (upper_bound(a.rbegin(), a.rend(), begin[i]) - 1 - a.rbegin());
      a[id[i]] = begin[i];
    }
  } else if (allowequal) {
    for (int i = 0; i < n; i++) {
      id[i] = upper_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  } else {
    for (int i = 0; i < n; i++) {
      id[i] = lower_bound(a.begin(), a.end(), begin[i]) - a.begin();
      a[id[i]] = begin[i];
    }
  }
  int m = *maxptr(id.begin(), id.end());
  vector<T> re(m + 1);
  for (int i = n - 1; i >= 0; i--) {
    if (id[i] == m) re[m--] = begin + i;
  }
  return re;
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  char b;
  cin >> b;
  char x[256];
  x[x['A'] = 'T'] = 'A';
  x[x['C'] = 'G'] = 'C';
  cout << x[b] << endl;
}


Measured memory_bytes: 256
n=int(input())
kakko=[1 if i == '(' else -1 for i in list(input())]
tmp=0
x=0
y=0
for i in range(n):
    x+=kakko[i]
    if tmp<abs(x) and x<0:
        tmp+=1
kakko=[1]*tmp+kakko

if sum(kakko)>0:
    tmp=sum(kakko)
    kakko=kakko+[-1]*tmp
ans=['(' if i==1 else ')' for i in kakko]
print(''.join(ans))

Measured memory_bytes: 38384
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

/*
using PAIR = pair<string, int>;
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA() cerr << "AAAAA" << endl
#define debug_() cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int>>; // クラスカル法とかで、{cost, {from, to}}的に使う。
const ll INF = 1001001001001001;
const double pi = acos(-1);

int main()
{
    int n;
    cin >> n;
    vector<int> a(n, 0);
    for (int i = 0; i < n - 1; i++)
    {
        int x;
        cin >> x;
        a[x - 1]++;
    }
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3968
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAX_H = 50;
const int MAX_W = 50;

int main ( void )
{
	int H, W;
	int hyo[MAX_H][MAX_W];

	cin >> H >> W;

	for (int y = 0; y < H; ++y)
	{
		for (int x = 0; x < W; ++x)
		{
			char semi;

			cin >> semi;

			if ((y == 0) && (x == 0))
			{
				hyo[y][x] = semi - '0';
			}
			else if (x == 0)
			{
				hyo[y][x] = (semi - '0') + hyo[y-1][x];
			}
			else if (y == 0)
			{
				hyo[y][x] = (semi - '0') + hyo[y][x-1];
			}
			else
			{
				hyo[y][x] = (semi - '0') + min(hyo[y-1][x], hyo[y][x-1]);
			}
		}
	}
	
	cout << hyo[H-1][W-1] << endl;

}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int 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()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll a, b;
    cin >> a >> b;
    ll c;
    if(a + b > a - b) c = a + b;
    else c = a - b;

    if(c > a * b) cout << c << endl;
    else cout << a * b << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.util.*;

class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextInt();
		long M = 0;
		long A = 0;
		long R = 0;
		long C = 0;
		long H = 0;
		for(int i = 0; i < N; i++) {
			String Si = sc.next();
			switch(Si.substring(0, 1)) {
			case "M":
				M++;
				break;
			case "A":
				A++;
				break;
			case "R":
				R++;
				break;
			case "C":
				C++;
				break;
			case "H":
				H++;
				break;
			}
		}
		long x = 0;
		x = M * A * R;
		x += M * A * C;
		x += M * A * H;
		x += M * R * C;
		x += M * R * H;
		x += M * C * H;
		x += A * R * C;
		x += A * R * H;
		x += A * C * H;
		x += R * C * H;
		System.out.println(x);
	}
}

Measured memory_bytes: 48324
N = int(input())
h = list(map(int, input().split()))

INF = float('inf')

DP = [INF] * N

DP[0] = 0
DP[1] = abs(h[1] - h[0])

for i in range(2,N):
    one = abs(h[i] - h[i-1]) + DP[i-1]
    two = abs(h[i] - h[i-2]) + DP[i-2]
    DP[i] = min(one,two)

print(DP[N-1])

Measured memory_bytes: 13980
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.StringWriter

fun solve(c: Case) {
    c.int()
    c.println(c.intList().map {
        var current = it
        var count = 0
        while (current % 2 == 0) {
            current /= 2
            count++
        }
        count
    }.sum().toString())
}

open class Case(
    private val input: BufferedReader = System.`in`.bufferedReader(),
    private val out: BufferedWriter = System.out.bufferedWriter()
) {
    fun exec(fn: (Case) -> Unit) = input.use { out.use { fn(this) } }
    fun println(c: CharSequence?) = out.appendln(c)
    fun int(): Int = input.readLine().toInt()
    fun intList(): List<Int> = input.readLine().split(" ").map { it.toInt() }
}

fun main() = Case().exec(::solve)


Measured memory_bytes: 40044
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  if (abs(a - b) <= t * (v - w)) {
    cout << "YES\n";
  }  
  else {
    cout << "NO\n";
  }
} 

Measured memory_bytes: 3652
from collections import deque

H, W = map(int, input().split())
s = [input() for i in range(H)]
Map = [[0]*W for i in range(H)]
num_b = 0
for i in range(H):
  for j in range(W):
    if s[i][j] == '#':
      num_b += 1
      Map[i][j] = -1

dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
que = deque([[0, 0]])
Map[0][0] = 1
while que:
  x, y = que.popleft()
  for dx, dy in dxy:
    xx, yy = x + dx, y + dy
    if 0<=xx<H and 0<=yy<W and Map[xx][yy] == 0:
      Map[xx][yy] = Map[x][y] + 1
      if (xx, yy) == (H-1, W-1):
        print(H*W - Map[xx][yy] - num_b)
        quit()
      que.append([xx, yy])

print(-1)

Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,c;
int main() {cin>>n>>m>>c;
vector<int>b(m);
for(int i=0;i<m;i++){
    cin>>b[i];
}
int count=0;
for(int u=0;u<n;u++){
    int hj=c;
    for(int i=0;i<m;i++){
        int s;cin>>s;
        hj+=s*b[i];
    }
    count+=hj>0;
}
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
    
    #define ll long long
    #define pb push_back
    #define printV(v) for(int i=0;i<(int)v.size();i++){cout << v[i]<< " ";} cout << endl
    #define printRev(v) for(int i=(int)v.size()-1;i >= 0;i--){cout << v[i] << " ";} cout << endl
    #define sortV(v) sort(v.begin(),v.end())
    #define revV(v) reverse(v.begin(),v.end())
    #define FOR(i,from,n) for(int i=from;i<n;i++)
    #define FOL(i,from,n) for(int i=from;i >= n;i--)

        ll a,b,c,d,e,f,g,n,m,k,t,x,h,w,p,q,y;
        string str = "";
        ll mod = 1e9 + 7;

        ll pow(ll base, ll q, ll mod){
            ll answer = 1;
            while(q > 0){
                if(q & 1LL)
                    answer = (answer * base) % mod;

                q = q >> 1LL;
                base = (base*base) % mod;
            }
            return answer % mod;
        }


        
       
        
        void solve(){
            cin >> a >> b >> n;
            int cnt = 0;
            for(int i=a; i<=b;i++){
                if(i%n==0) cnt++;
            }
            cout << cnt << endl;
        }
            
            
        



            



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

            

          
            int cases = 1;
            //cin >> cases;

            while(cases--) solve();
            return 0;

        }

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<long long int,long long int>m;
    long long int n,x,c=0;
    cin>>n;
    while(n--)
    {
        cin>>x;
        m[x]++;
    }
    vector<long long int>v,u;
    v.push_back(0);
    v.push_back(0);
    u.push_back(0);
    u.push_back(0);
    for( map<long long int,long long int>::iterator it=m.begin();it!=m.end();it++)
    {
        if(it->second>=2)
        {
            v.push_back(it->first);
        }
        if(it->second>=4)
        {
            u.push_back(it->first);
        }
    }
    sort(v.begin(),v.end());
    sort(u.begin(),u.end());
    long long int area1,area2;
    area2=u[u.size()-1]*u[u.size()-1];
    if(v.size()==2 || v.size()==3 ) area1=0;
    else area1=v[v.size()-1]*v[v.size()-2];
    area1=max(area1,area2);
    cout<<area1<<endl;
    return 0;
}


Measured memory_bytes: 6528
N=list(input())
if len(N)==1:
  key=int(N[0])
else:
  key=int(N[-1])
if key==2 or key==4 or key==5 or key==7 or key==9:
  print('hon')
elif key==3:
  print('bon')
else:
  print('pon')

Measured memory_bytes: 9120
import math
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np


x= int(input())
# p = list(map(int, input().split()))

def iss(n):
    a = True
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            a = False

    return a
ans = 0
while 1:
    if iss(x):
        ans = x
        break
    x += 1

print(ans)



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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

#define SEG_LEN (1 << 19)
ll seg[SEG_LEN*2][26];

void add(ll ind1, ll ind2, ll v){
    ind1 += SEG_LEN;
    seg[ind1][ind2] += v;
    while(1){
        ind1 /= 2;
        if(ind1 <= 0) break;
        seg[ind1][ind2] = seg[ind1*2][ind2] + seg[ind1*2+1][ind2];
    }
    return;
}

ll get(ll l, ll r,ll i){
    l += SEG_LEN; r += SEG_LEN;
    ll res = 0;
    while(l < r){
        if(l % 2 == 1){
            res += seg[l][i];
            l++;
        }
        l /= 2;

        if(r % 2 == 1){
            res += seg[r-1][i];
            r--;
        }
        r /= 2;
    }
    return res;
}

int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll q;
    cin >> q;

    rep(i,0,s.size()){
        add(i+1,s[i]-'a',1);
    }


    rep(i,0,q){
        ll com;
        cin >> com;
        if(com == 1){
            ll index;
            char c;
            cin >> index >> c;
            if(s[index-1] != c){
                add(index,s[index-1] - 'a', -1);
                add(index,c - 'a', 1);
                s[index-1] = c;
            }
        }
        else{
            ll x,y;
            cin >> x >> y;
            ll cnt = 0;
            rep(i,0,26){
                if(get(x,y+1,i) > 0) cnt++;
            }
            cout << cnt << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 207036
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

int main() {
    ll x, y;
    cin >> x >> y;
    if (x % y == 0) cout << "-1" << endl;
    else cout << x << endl;
    return 0;
}


Measured memory_bytes: 256
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
X = I[1::2]
L = I[2::2]
coord = [[x - l, x + l] for x, l in zip(X, L)]
x_i = collections.defaultdict(int)
for lr in coord:
    x_i[lr[0]] = x_i[lr[1]] = 0
for i, v in enumerate(sorted(x_i.keys())):
    x_i[v] = i
for i in range(N):
    coord[i][0] = x_i[coord[i][0]]
    coord[i][1] = x_i[coord[i][1]]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


array = [-1] * len(x_i)
#array[r]: 腕が動く範囲が[l, r) となるロボットが存在するlの最大値
for l, r in coord:
    array[r] = max(array[r], l)
now = 0
ans = 0
for i in range(len(array)):
    if array[i] != -1 and array[i] >= now:
        now = i
        ans += 1
print(ans)


Measured memory_bytes: 51148
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(any{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

int a = 0, b = 0;

int dfs(int n, int &c, vector<int> &p, vector<bool> &used, vector<int> &x){
	if(p.size()==n){
		bool eq = true;
		for(int i=0; i<n; i++){
			if(p[i]!=x[i]) eq = false;
		}
		if(eq) return c;
		else -1;
		c++;
	}
	for(int i=0; i<n; i++){
		if(used[i]) continue;
		p.push_back(i);
		used[i] = true;
		int ret = dfs(n, c, p, used, x);
		p.pop_back();
		used[i] = false;
		if(ret >= 0) return ret;
	}
	return -1;
}

int main(){
	int N;
	cin >> N;
	vector<int> P(N), Q(N);
	for(int i=0; i<N; i++){
		cin >> P[i];
		P[i]--;
	}
	for(int i=0; i<N; i++){
		cin >> Q[i];
		Q[i]--;
	}

	int x = 0;
	vector<int> p;
	vector<bool> used(N);
	int a = dfs(N, x, p, used, P);
	x = 0;
	int b = dfs(N, x, p, used, Q);

	cout << abs(a-b) << endl;

	return 0;
}


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

ans = 0
for i in range(0,N-2) :
    for j in range(i+1,N-1) :
        for k in range(j+1,N) :
            a = [L[i],L[j],L[k]]
            a = sorted(a)
            if len(a) == len(set(a)) :
                if a[2] < a[0] + a[1] :
                    ans += 1

print(ans)




Measured memory_bytes: 9188
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <utility>
#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, forall_a, forall_b) for (int i = (forall_a); i < (forall_b); ++i)
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pb push_back

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

typedef pair<int, int> P;

bool ps1(const P &forall_a, const P &forall_b)
{ //first昇順
	return forall_a.first < forall_b.first;
}
bool ps2(const P &forall_a, const P &forall_b)
{ //first降順
	return forall_a.first > forall_b.first;
}
bool ps3(const P &forall_a, const P &forall_b)
{ //second昇順
	return forall_a.second < forall_b.second;
}
bool ps4(const P &forall_a, const P &forall_b)
{ //second降順
	return forall_a.second > forall_b.second;
}
int GCD(int x, int y)
{
	return x ? GCD(y % x, x) : y;
}

int main()
{
	int n;
	cin>>n;
	vector<int>a(n);
	int even=0,odd=0;
	rep(i,n){
		cin>>a[i];
		if(a[i]%2!=0){
			odd++;
		}
	}
	bool ans=true;
	if(odd%2!=0){
		ans=false;
	}
	if(ans){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}

}

Measured memory_bytes: 640
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort(reverse=True)
    return divisors


N = int(input())
D = make_divisors(N)
ans = 10 ** 13
for d in D:
    ans = min(ans, d + N // d - 2)

print(ans)


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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;
const int MOD = 1e9 + 7;

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

    int n;cin>>n;
    vector<int> t(n),x(n),y(n);
    int tl=0,xl=0,yl=0;
    for(int i=0;i<n;i++){
        cin>>t[i]>>x[i]>>y[i];
        int td=abs(t[i]-tl),xd=abs(x[i]-xl),yd=abs(y[i]-yl);
        if(xd+yd<=td && (td%2)==(xd+yd)%2) continue;
        else{
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}


Measured memory_bytes: 1408
#include<cstdio>
#include<map>
#include<set>
#include<iostream>
#define mp(a,b) make_pair(a,b) 
using namespace std;
int fa[100010],n,x,y;
map<pair<int,int>,int>G,vis;
multiset<int> S[100010];
pair<int,int> q[1000010];
int t,h;
void p(int &x,int &y){if (x>y) swap(x,y);} 
int find(int x)
{
	//cout<<x<<endl;
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++) scanf("%d%d",&x,&y),p(x,y),G[mp(x,y)]++,S[x].insert(y),S[y].insert(x);
	for (int i=1;i<n;i++) {scanf("%d%d",&x,&y),p(x,y);S[x].insert(y),S[y].insert(x);if (++G[mp(x,y)]>1) vis[mp(x,y)]=1,q[++t]=mp(x,y);}
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int k=1;k<n;k++)
	{
		int x,y;
		while (1)
		{
			if (h==t) {printf("NO");return 0;}
			x=find(q[++h].first),y=find(q[h].second);
			if (x==y) continue;
			else break;
		}
		if (S[x].size()>S[y].size()) swap(x,y);
		fa[x]=y;
		for (set<int>::iterator i=S[x].begin();i!=S[x].end();i++)
		{
			int nw=find(*i);
			if (nw==y) continue;
			S[y].insert(nw),S[nw].insert(y);
			int xx,yy;
			if (nw>y) xx=y,yy=nw;
			else xx=nw,yy=y;
			if (++G[mp(xx,yy)]>1&&vis[mp(xx,yy)]!=1) vis[mp(xx,yy)]=1,q[++t]=mp(xx,yy);
			if (S[nw].find(x)!=S[nw].end()) S[nw].erase(x);
		}
		S[y].erase(x); 
	}
	printf("YES");
} 

Measured memory_bytes: 53376
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct LCA{
    size_t n,r,m,md;
    vector<vector<int>> e;
    vector<int> pa,d;
    vector<vector<int>> lc;
    explicit LCA(int n_){
        n=n_;
        e.resize(n);
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i,int p=-1,int D=0){
        pa[i]=p;d[i]=D;md=max(md,(size_t)D);++D;
        for(auto j:e[i]) if(j!=p) r_dfs(j,i,D);
    }
    void r_i(int r_){
        pa.resize(n);d.resize(n);r=r_;md=0;
        r_dfs(r);
    }
    void b_lca(int r_){
        r_i(r_);
        m=32-__builtin_clz(md);
        lc.clear();
        lc.resize(m,vector<int>(n,-1));
        fr(i,n) lc[0][i]=pa[i];
        fr(i,m-1) fr(j,n) if(lc[i][j]!=-1) lc[i+1][j]=lc[i][lc[i][j]];
    }
    int lca(int a,int b){
        if(a==b) return a;
        if(d[a]>d[b]) swap(a,b);
        for(int i=m-1;i>=0&&d[a]!=d[b];--i) if(lc[i][b]!=-1&&d[a]<=d[lc[i][b]]) b=lc[i][b];
        if(a==b) return a;
        ifr(i,m) if(lc[i][a]!=lc[i][b]) a=lc[i][a],b=lc[i][b];
        if(a!=b) a=pa[a];
        return a;
    }
};

struct edge{
    int to,c,d;
    edge(int to,int c,int d):to(to),c(c),d(d){}
};

struct que{
    int i,x,y;
    que(int i,int x,int y):i(i),x(x),y(y){}
};

vector<vector<edge>> e;
vector<vector<que>> vq;
int D{};
vector<int> num,sum;
vector<int> ans;

void rec(int i=0,int p=-1){
    for(auto q:vq[i]){
        if(q.i<0) ans[-q.i-1]-=2*(D-sum[q.x]+q.y*num[q.x]);
        else ans[q.i]+=D-sum[q.x]+q.y*num[q.x];
    }
    for(auto a:e[i]){
        if(a.to==p) continue;
        D+=a.d;
        ++num[a.c];
        sum[a.c]+=a.d;
        rec(a.to,i);
        D-=a.d;
        --num[a.c];
        sum[a.c]-=a.d;
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n,q;
    in>>n>>q;
    LCA t(n);
    int a,b,c,d;
    e.resize(n);
    fr(i,n-1){
        in>>a>>b>>c>>d;
        t.add(--a,--b);
        e[a].emplace_back(b,c,d);
        e[b].emplace_back(a,c,d);
    }
    t.b_lca(0);
    int x,y,u,v;
    vq.resize(n);
    fr(i,q){
        in>>x>>y>>u>>v;
        vq[--u].emplace_back(i,x,y);
        vq[--v].emplace_back(i,x,y);
        vq[t.lca(u,v)].emplace_back(-i-1,x,y);
    }
    num.resize(n);
    sum.resize(n);
    ans.resize(q);
    rec();
    fr(i,q) cout<<ans[i]<<endl;
}

Measured memory_bytes: 33016
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	char c=getchar();ll t=0,f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
	return t*f;
}
ll n;
int main(){
	n=read();
	if(n<=2){printf("0\n");return 0;}
	ll sum=0;
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			ll a=i;
			if(a!=1&&n==a*(n%(a-1))){sum+=a-1;} 
			a=n/i;
			if(n==a*(n%(a-1))){sum+=a-1;} 
		}
	}
	printf("%lld\n",sum);
	return 0;
}
/*
n/m==n%m
n==(n%m)*(m+1)
*/

Measured memory_bytes: 256
import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

dp0 = np.zeros((N + 1, s + 1), dtype=np.int64)
dp0[0, 0] = 1
dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int64)
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

# Counts of (R >= s / 2)
c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
# Counts of (R == s / 2 and G == s / 2)
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

Measured memory_bytes: 329152
macro_rules! get {
    (Vec<$t:ty>) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
}

fn bis<F>(ok: i64, ng: i64, p: F) -> i64
    where F : Fn(i64) -> bool {

    let mid = (ok + ng) / 2;
    if (ok - ng).abs() == 1 {
        ok
    } else if p(mid) {
        bis(mid, ng, p)
    } else {
        bis(ok, mid, p)
    }
}

fn main() {
    let N = get!(usize);
    let mut A = get!(Vec<i64>);
    let mut B = get!(Vec<i64>);
    let mut C = get!(Vec<i64>);

    A.push(0);
    A.sort();
    B.sort();
    C.push(10_000_000_000);
    C.sort_by_key(|&c| -c);

    // 二分探索により、上に乗せられるパーツを求める
    let mut acc = 0;
    let ans = B.iter()
        .map(
            |&b|
            {
                bis(0, (N + 1) as i64, |k| { A[k as usize] < b }) *
                bis(0, (N + 1) as i64, |k| { C[k as usize] > b })
            }
        )
        .sum::<i64>();

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


Measured memory_bytes: 13560
#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(),(x).end()


int main(void){
	int n,k;
	scanf("%d%d",&n,&k);
	ll v[n];
	for(int i=0;i<n;i++)scanf("%lld",&v[i]);
	int a,b;
	ll ans=0;
	for(int i=0;i<=min(n,k);i++){//捨てるのも含めてとる個数
		for(a=0;a<=i;a++){
			vector<ll> getted(i,0);
			b=i-a;
			for(int j=0;j<a;j++)getted.push_back(v[j]);
			for(int j=n-1;j>n-1-b;j--)getted.push_back(v[j]);
			
			sort(all(getted));
			
			int d=0;
			while(d<k-i && d<getted.size() && getted[d]<0)getted[d++]=0;
			
			ans = max(ans,accumulate(all(getted),0LL));
			
			
		}
		
	}
	printf("%lld",ans);
	
	
	return 0;
}

Measured memory_bytes: 256
def resolve():
    n = int(input())
    b = list(map(int, input().split()))
    b = b[::-1]
    blist = [0]*n
    blist[0] = b[0]
    blist[n-1] = b[-1]
    for i in range(1,n-1):
        blist[i] = min(b[i-1], b[i])
    print(sum(blist))
resolve()

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string s;cin>>s;
	ll n = s.size();
	ll cnt = 0;
	ll ans = 0;
	ll i = 0;
	while(i < n) {
		if (s[i] == 'A'){
			cnt = 1;
			i++;
			while(i + 1 < n){
				if (s[i] == 'A'){
					cnt++;
					i++;
				}
				else if (s[i] == 'B' && s[i + 1] == 'C') {
					ans += cnt;
					i += 2;
				}
				else{
					break;
				}
			}
		}
		else {
			i++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    int k, s;
    cin >> k >> s;

    Int ans = 0;
    for (int x = 0; x <= k; x++) {
        for (int y = 0; y <= k; y++) {
            int z = s - x - y;
            if (0 <= z && z <= k) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


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

#define pb            push_back
#define mp            make_pair
#define ins           insert
#define endl          '\n'
#define all(x)        x.begin(),x.end()
#define debug(X)      { cerr<<endl<<(#X)<<" = "<<(X)<<endl; }
//#define cerr if(0)cerr

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;


int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,a;
    bool ok=1;

    cin>>n;
    while (n--) {
        cin>>a;
        if (a%2==0 && ((a%3)&&(a%5)))
            ok=0;
    }

    cout<<(ok?"APPROVED":"DENIED")<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include <cstring>
using namespace std;
int dp[100000];
int n,a[100000],k;
 
int ans(int i)
{
	if(i==n-1)
		return 0;
 
	if(dp[i]!=-1)
		return dp[i];
  
	int best=1e9;
	for(int j=1;j<=k;j++)
	{
		if(i+j<n)
			best=min(best,abs(a[i]-a[i+j]) + ans(i+j));
	}
	return dp[i]=best;
}
 
int main()
{
  	ios_base::sync_with_stdio(0);            
	cin.tie(NULL);
	cout.tie(NULL);
	memset(dp,-1,sizeof(dp));
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
 
	cout<<ans(0)<<endl;
 
	return 0;
}

Measured memory_bytes: 12160
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <intrin.h>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a - 1; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 300005
#define inf 2000000000
#define EPS 1e-12
#define MOD 998244353ll
#define __builtin_popcount(x) __popcnt(x)

using namespace std;

typedef long long ll;

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

inline void solve()
{
	int k;
	cin >> k;
	ll otv = 0;
	fore(i, 1, k + 1)
		fore(j, 1, k + 1)
		fore(l, 1, k + 1)
		otv += gcd(gcd(i, j), l);
	cout << otv;
}

int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	while (q--)
	{
		solve();
		cout << '\n';
	}

}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

int N, D;
double X, Y;
int cnt;

int main(){
	cin >> N >> D;
	for (int i = 0; i < N; i++){
		cin >> X >> Y;
		if (sqrt(X*X + Y*Y) <= D)cnt++;
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3696
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')

def main():
  a, b = map(int, readline().split())
  print(max(a+b, a-b, a*b))
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 5076
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

Int a[100005];
vector<string> s;
int main(){
    cin.tie(0);

    int N; cin >> N;
    for (int i = 0; i < N; i++){
        string tmp; cin >> tmp;
        s.push_back(tmp);
    }

    Int ans = 0;
    for (int i = 0; i < N; i++){
        int flag = 1;
        for (int j = 0; j < N; j++){
            for (int k = i; k < i + N; k++){
                if (s[j][k%N] != s[k-i][(i+j)%N]) flag = 0;
            }
        }
        if (flag) ans += N;
    }

    cout << ans << endl;

}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int n,k;
int h[309];
ll memo[309][309][309];

ll dp(int i,int cnt,int idx){
  if(memo[i][cnt][idx]!=-1)return memo[i][cnt][idx];
  if(i==n)return 0;
  ll d=(h[i]>h[idx]?h[i]-h[idx]:0);
  ll rec=dp(i+1,cnt,i)+d;
  if(cnt<k){
    rec=min(rec,dp(i+1,cnt+1,idx));
  }
  return memo[i][cnt][idx]=rec;
}

int main(){
  memset(memo,-1,sizeof(memo));
  cin>>n>>k;
  rep(i,n){
    cin>>h[i];
  }

  cout<<dp(0,0,n)<<endl;

  return(0);
}


Measured memory_bytes: 230912
#include <iostream>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <sstream>
#include <vector>
#include <map>
#include <fstream>
using namespace std;

typedef long long int ll;

const int N = 100;

void dfs(int n, int x, string str);

ll sum = 0;
string S;
bool Visit[N];

int main()
{
	cin >> S;

	int len = S.length();

	dfs(len, 0, S);

	sum += stoll(S);

	printf("%lld\n", sum);

	return 0;
}

void dfs(int n, int x, string str)
{
	string S2 = "";

	if (x > 0) {
		for (int i = 0; i < n; i++) {
			S2 += str[i];
			if (Visit[i]) {
				sum += stoll(S2);
				S2 = "";
			}
		}
		if (S2.length() > 0) {
			sum += stoll(S2);
		}
	}

	if (x >= n) {
		return;
	}
	else {
		for (int i = x; i < n - 1; i++) {
			if (!Visit[i]) {
				Visit[i] = true;
				dfs(n, i + 1, str);
				Visit[i] = false;
			}
		}
	}
}

Measured memory_bytes: 256
main = do
    str <- getLine
    let (n:x:_) = map read $ words str
    if ((n,x) == (0,0)) then
        return ()
    else do
        print $ foldr (\_ x -> x+1) 0 [1 | a <- [1..(n-2)], b <- [(a+1)..(n-1)], c <- [(b+1)..(min (n) (x-a-b))], a+b+c==x]
        main

Measured memory_bytes: 4772
#include<iostream>
#include<string>
using namespace std;
int main(){
    int i,j,n,s1=0,s2=0,mini=1000000;
    cin >> n;
    int w[n],df[n];
    for(i=0;i<n;i++){
        cin >> w[i];
    }
    for(i=0;i<n;i++){
        s1 = 0;
        s2 = 0;
        for(j=0;j<=i;j++){
            s1 = s1+w[j];
        }
        for(j=i+1;j<n;j++){
            s2 = s2+w[j];
        }
        if(s2-s1>=0){
            df[i] = s2-s1;
        }
        else{
            df[i] = s1-s2;
        }
    }
    for(i=0;i<n;i++){
        if(df[i]<mini){
            mini = df[i];
        }
    }
    cout << mini;

}

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

#define pb push_back
#define vi vector < int >
#define ii pair < int, int >
#define vii vector < pair < int, int > >
#define vvi vector < vector < int > >
#define ll long long
#define X first
#define Y second
#define mp make_pair
#define FOR( i, lo, hi ) for( int i = (lo);i < (hi);i++ )
#define DFOR( i, hi, lo ) for( int i = (hi);i >= (lo);i-- )
#define pqueue priority_queue

using namespace std;

const int MAXN = 1e5 + 10;

int n;
ll A[ MAXN ];
ll B[ MAXN ];

int main()
{
	cin >> n;
	FOR( i, 0, n + 1 )	
		cin >> A[ i ];
	
	ll sol = 0;
	FOR( i, 0, n )
	{
		cin >> B[ i ];
		sol += min( B[ i ], A[ i ] );
		if ( B[ i ] > A[ i ] )
		{
			sol += min( ( B[ i ] - A[ i ] ), A[ i + 1 ] );
			A[ i + 1 ] = max( 0LL, A[ i + 1 ] - ( B[ i ] - A[ i ] ) );
		}
	}
	cout << sol << "\n";
	return 0;
}


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

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

  bool flag = true;
  int i = 0;
  int counter = 0;
  while (flag) {
    flag = false;
    for (int j = N - 1; j > i; j--) {
      if (A[j] < A[j - 1]) {
        swap(A[j], A[j - 1]);
        flag = true;
        counter++;
      }
    }
    i++;
  }

  for (int i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << A[i];
  }
  cout << endl;
  cout << counter << endl;
}



Measured memory_bytes: 3116
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

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

static const double eps = 10e-8;

ll nCr(int n,int r){
  return (r==0 || n==r) ? 1 : nCr(n-1,r) + nCr(n-1,r-1);
}

int main(){
  string str;
  while(cin>>str){
    map<char,int> freq;
    for(int i=0;i<str.size();i++){
      freq[str[i]]++;
    }
    
    bool isok = true;
    ll sum=1;
    if(str.size() % 2 == 0){        
      int size = str.size() / 2;
      for(map<char,int>::iterator it = freq.begin(); it != freq.end(); it++){
        if(it->second % 2 != 0){
          isok = false;
          break;
        }
        else{
          sum *= nCr(size,it->second / 2);
          size -= it->second / 2;
        }
      }
    }
    else{
      int size = str.size() / 2;
      int c = 0;
      for(map<char,int>::iterator it = freq.begin(); it != freq.end(); it++){
        if(it->second % 2 != 0){
          c++;
          if(c>=2) isok = false;
          if(it->second > 2){
            sum *= nCr(size,(it->second - 1) / 2);
            size -= (it->second - 1) / 2;
          }
        }
        else{
          sum *= nCr(size,it->second / 2);
          size -= it->second / 2;
        }
      }
    }
    printf("%lld\n",isok ? sum : 0);
  }        
}

Measured memory_bytes: 1188
#include <stdio.h>

int main(void){
	int n,a[100],t,i,l,s;
	while(1){
		s=0;
	scanf("%d",&n);
		if(n==0){
			return 0;
		}
	for(t=0;t<n;t++){
		scanf("%d",&a[t]);
	}
	for(i=0;i<n;i++){
		for(t=1;t<n;t++){
			if(a[t-1]<a[t]){
				l=a[t-1];
				a[t-1]=a[t];
				a[t]=l;
			}
		}
	}
	for(t=1;t<n-1;t++){
		s+=a[t];
	}
	s=s/(n-2);
	printf("%d\n",s);
	}
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int n,a,b,ans=0;
  cin>>n>>a>>b;
  rep(i,n+1){
    int cnt=0,x;
    x=i;
    while (x!=0) {
      cnt+=x%10;
      x/=10;
    }
    if (cnt>=a && cnt<=b) {
      ans+=i;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
n=int(input())
a=[int(i) for i in input().split(" ")]
x=0

for i in range(n):
    mi = i
    for j in range(i, n):
        if a[j] < a[mi]:
            mi = j
    
    if i != mi:
        x += 1
        a[i], a[mi] = a[mi] , a[i]

print(" ".join([str(i) for i in a]))
print(x)

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

int main() {
  int num,kadai;
  long long sum = 0;
  int kekka;
  int tmp;
  cin >> num >> kadai;
  
  for(int i = 0; i < kadai; i++){
    cin >> tmp;
    sum += tmp;
  }
  
  if(sum > num) cout << -1;
  else cout << num - sum;
}


Measured memory_bytes: 3632
sx,sy,tx,ty = gets.split.map(&:to_i)

S = [sx, sy]; SU = [sx, sy+1]; SD = [sx, sy-1]; SL = [sx-1, sy]; SR = [sx+1, sy]
T = [tx, ty]; TU = [tx, ty+1]; TD = [tx, ty-1]; TL = [tx-1, ty]; TR = [tx+1, ty]

moves = [S,SU,TL,T,TD,SR,S,SL,TU,T,TR,SD,S].each_cons(2).map do |s,t|
  dx = t[0] - s[0]; dy = t[1] - s[1]
  ((dy >= 0 ? "U" : "D") * dy.abs + (dx >= 0 ? "R" : "L") * dx.abs)
end

puts moves.join


Measured memory_bytes: 1788