akhauriyash/Code-Regression huggingface dataset:
import itertools
import math


N = int(input())
XY_list = []
for i in range(N):
    x, y = input().split()
    XY_list.append([int(x), int(y)])

p = list(itertools.permutations(XY_list))
length_sum = 0
for p_list in p:
    length = 0
    for i in range(len(p_list) - 1):
        length += math.sqrt((p_list[i + 1][0] - p_list[i][0])
                            ** 2 + (p_list[i + 1][1] - p_list[i][1]) ** 2)

    length_sum += length
print(length_sum / len(p))

Measured memory_bytes: 7972
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
#define REP(i,n) for(int i=0;i<(int)n;++i)
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

ll Euclid(ll A, ll B){
    if(A<B) swap(A, B);
    ll C = B;
    while(C != 0){
        C = A%B;
        A = B;
        B = C;
    }
    return A;
}

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

    ll N, K;
    cin >> N >> K;

    ll M = N - (N/K)*K;

    cout << min(M, K-M) << endl;

    return 0;
}

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

using namespace std;

int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  int ret = 0;
  for(int i = 1; i <= N; i++) {
    auto s = to_string(i);
    int x = 0;
    for(auto &p : s) x += p - '0';
    if(A <= x && x <= B) ret += i;
  }

  cout << ret << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <bits/stdc++.h>
#include <queue>
#include <math.h>
#define ll long long
#define INF 100000000000
#define N 10000000
using namespace std;

int main(){
    int h,w,k;
    cin>>h>>w>>k;
    char data[h][w];
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin>>data[i][j];
        }
    }
    
    int ans=0;
    
    for(int bit=0; bit<(1<<h); bit++){
        vector<int> S;
        for(int i=0; i<h; i++){
            if(bit & (1<<i)) S.push_back(1);
            else S.push_back(0);
        }
        for(int bit2=0; bit2<(1<<w); bit2++){
            vector<int> T;
            for(int i=0; i<w; i++){
                if(bit2 & (1<<i)) T.push_back(1);
                else T.push_back(0);
            }
            
            char num[h][w];
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    num[i][j]=data[i][j];
                }
            }
            
            for(int i=0; i<h; i++){
                if(S[i]==1){
                    for(int a=0; a<w; a++) num[i][a]='?';
                }
                for(int j=0; j<w; j++){
                    if(T[j]==1){
                        for(int b=0; b<h; b++) num[b][j]='?';
                    }
                }
            }
            
            int count=0;
            for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){
                    if(num[i][j]=='#') count++;
                }
            }
            
            if(count==k) ans++;
        }
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 3580
import time
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]

num = [0] * 100010
for i in A:
    num[i] += 1
s = sum(A)

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    s += (n - p) * num[p]
    num[n] += num[p]
    num[p] = 0
    print(s)

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

public class Main {
	
	public static void main(String[] args) {
		new Main().solve();
	}
	
	void solve() {
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		if(s.length()<4)System.out.println("No");
		else if(s.substring(0,4).equals("YAKI"))System.out.println("Yes");
		else System.out.println("No");
	}
}


Measured memory_bytes: 21844
import bisect

n, m = map(int, input().split())
a_array = sorted([int(x) for x in input().split()])
bc_array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x: x[1], reverse=True)

# 何枚入れ替えられるか
candidate_replace_cnt = n
for b, c in bc_array:
    if a_array[0] >= c or candidate_replace_cnt < 0:
        break
    for i in range(b):
        a_array.append(c)
    candidate_replace_cnt -= b
a_array.sort(reverse=True)
print(sum(a_array[:n]))


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

typedef long long ll;
int s[3]; 
bool flag[100001];

int score(char c){
    if(c=='r') return s[2];
    else if(c=='s') return s[0];
    else if(c=='p') return s[1];
}


int main(){
    int n,k; cin >> n >> k;
    cin >> s[0] >> s[1] >> s[2];
    string t; cin >> t;
    int ans=0;
    for(int i=0;i<k;i++){
        ans+=score(t[i]);
        flag[i]=true;
    }
    for(int i=k;i<n;i++){
        if(t[i]!=t[i-k]){
            ans+=score(t[i]);
            flag[i]=true;
        }else{
            if(!flag[i-k]){
                ans+=score(t[i]);
                flag[i]=true;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
using namespace std;
signed main(){
	int x,y,ans=0;
	cin >> x >> y;
	while(x <= y){
		ans++;
		x *= 2;
	}
	cout << ans << endl;
    return 0;
}

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

int main(){
	int64 a, b, k;
	cin >> a >> b >> k;
	int64 tmp = min(a, k);
	a -= tmp;
	k -= tmp;
	b = max(0LL, b - k);
	cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>  
#include <stdbool.h>   
#define inf (INT_MAX-1)
#define INF 9223372036854775807;
#define PI 3.14159265358979323846;
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
/*
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r)
*/
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r)
#define TYPE long long
#define ll long long
#define MEMSET(a) memset(a,0,sizeof(a))
#define MEMSET_U(a) memset(a,-1,sizeof(a))
#define bool    _Bool
const int mod = (int)1e09 + 7;

//#define DEBUG1
//#define DEBUG2
//#define DEBUGF
#define DUMMY

int in(void) { int i; scanf("%d", &i); return i; }
long long llin(void) { long long i; scanf("%lld", &i); return i; }
double din(void) { double i; scanf("%lf", &i); return i; }
void chin(char s[]) { scanf("%s", s); }

void print(int a) { printf("%d\n", a); }
void llprint(long long a) { printf("%lld\n", a); }
void dprint(double a) { printf("%.10f\n", a); }
void print2(int a, int b) { printf("%d %d\n", a, b); }
int Max(int a, int b) { if (a > b) { return a; }return b; }
int Min(int a, int b) { if (a < b) { return a; }return b; }
long long llmax(long long a, long long b) { return a > b ? a : b; }
long long llmin(long long a, long long b) { return a < b ? a : b; }
double dmax(double a, double b) { return a > b ? a : b; }
double dmin(double a, double b) { return a < b ? a : b; }
//long long llmax(long long a, long long b) { return a > b ? a : b; }
//long long llmin(long long a, long long b) { return a < b ? a : b; }
//double dmax(double a, double b) { return a > b ? a : b; }
int cmp(const void *a, const void *b) { return *(TYPE *)a - *(TYPE *)b; }
int cmp_r(const void *a, const void *b) { return *(TYPE *)b - *(TYPE *)a; }
int char_cmp(const void *a, const void *b) { return strcmp((char *)a, (char *)b); }
int char_cmp_r(const void *a, const void *b) { return strcmp((char *)b, (char *)a); }
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }


int main() {
	char S[5];
	int A, B, C, D;
	scanf("%s",S);
	A = S[0] - '0';
	B = S[1] - '0';
	C = S[2] - '0';
	D = S[3] - '0';

	if (A + B + C + D == 7) { printf("%d+%d+%d+%d=7", A, B, C, D); }
	else if (A + B + C - D == 7) { printf("%d+%d+%d-%d=7", A, B, C, D); }
	else if (A + B - C + D == 7) { printf("%d+%d-%d+%d=7", A, B, C, D); }
	else if (A + B - C - D == 7) { printf("%d+%d-%d-%d=7", A, B, C, D); }
	else if (A - B + C + D == 7) { printf("%d-%d+%d+%d=7", A, B, C, D); }
	else if (A - B + C - D == 7) { printf("%d-%d+%d-%d=7", A, B, C, D); }
	else if (A - B - C + D == 7) { printf("%d-%d-%d+%d=7", A, B, C, D); }
	else if (A - B - C - D == 7) { printf("%d-%d-%d-%d=7", A, B, C, D); }
	printf("\n");

#ifdef DEBUGF
	getch();
#endif
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define W 0
#define B 1
#define inf 2000000
#define NIL -1
#define N 101
 
int main()
{
  int num,i,j,mcost;
  int u,v,a=0;
  int g[N][N];
  int d[N], p[N],c[N];
  
scanf("%d",&num);
for(i=1;i<=num;i++)
  {
    for(j=1;j<=num;j++)
      {
    scanf("%d",&g[i][j]);
      }
  }
  
for(u=1;u<=num;u++)
  {
    d[u] = inf;
    p[u] = NIL;
    c[u] = W;
  }
 d[1] = 0;
  
 while(1)
   {
     mcost =inf;
     for(i=1;i<=num;i++)
       {
     if(c[i]!=B && d[i]<mcost)
       {
         mcost = d[i];
         u=i;
       }
       }
     if(mcost ==inf)break;
  
     c[u]=B;
  
  
         for(v=1;v<=num;v++)
           {
         if(g[u][v] == -1) continue;
        else if(c[v]!=B && g[u][v]<d[v])
           {
             p[v] =u;
             d[v] = g[u][v];
           }
           }
       }
         
  
 for(i=1;i<=num;i++)
   a+=d[i];
 printf("%d\n",a);
 return 0;
}


Measured memory_bytes: 2052
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var A = cin.nextInt();
            var B = cin.nextInt();
            var K = cin.nextInt();

            var c = 0;
            for (int i = Math.Max(A, B); i > 0; i--)
            {
                if (A % i == 0 && B % i == 0) c++;
                if (c == K)
                {
                    Console.WriteLine(i);
                    break;
                }
            }
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N+ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }   

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 13140
//2019/3/14
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int M = sc.nextInt();

		int[] m = new int[M+1];

		Arrays.fill(m, 0);

		int K = 0;

		int A = 0;

		int ans = 0;

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

			K = sc.nextInt();

			for(int j=0;j<K;j++) {

				A = sc.nextInt();

				m[A]++;
			}
		}

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

			if(m[i]==N) ans++;
		}

		System.out.println(ans);
	}

}


Measured memory_bytes: 23764
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

INF = 10**10

h,n = nm()

dp = [INF] * (h+1)

dp[0] = 0

for i in range(n):
  a,b = nm()

  for j in range(h):
    nj = min(j+a,h) 
    dp[nj]=min(dp[nj],dp[j]+b) # ダメージがj+aの時のコスト

print(dp[h])


Measured memory_bytes: 43996
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = len(n[np.where(n==0)])
mp = n[np.where(n>0)]
M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=mz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
        
print(M)


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

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

    int n;
    cin >> n;
    map<int, long long> mp1, mp2;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        mp1[i - a]++;
        mp2[i + a]++;
    }

    long long ans = 0;
    for(auto x: mp1){
        ans += mp2[x.first] * x.second;
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
    int k;
    cin >> k;
    long long a[k];
    for(int i=0; i<k; i++){
        cin >> a[i];
    }
    long long mini,maxi;
    mini = 2;
    maxi = 2;
    for(int i=k-1; i>=0; i--){
        if(mini%a[i]!=0){
            mini = (mini/a[i]+1)*a[i];
        }
        if(maxi%a[i]!=0){
            maxi = (maxi/a[i])*a[i];
        }
        maxi += a[i]-1;
    }
    if(mini > maxi) cout << -1 << endl;
    else cout << mini << " " << maxi << endl;
    return 0;
}


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

long long n, q;
long long a[100005] = {0};
long long x[100005] = {0};
long long ans[100005] = {0};
vector<long long> memo;

void solve();

int main() {
  cin >> n >> q;
  for(int i = 0; i < n; ++i) cin >> a[i];
  for(int i = 0; i < q; ++i) cin >> x[i];
  solve();
  for(int i = 0; i < q; ++i)
    cout
        << ans[upper_bound(memo.begin(), memo.end(), x[i]) -
               memo.begin() - 1]
        << endl;
  return 0;
}

void solve() {
  memo.push_back(0);
  for(int i = 0; i + n / 2 < n && 2 * i - n % 2 + 1 < n;
      ++i)
    memo.push_back(
        (a[2 * i - n % 2 + 1] + a[n / 2 + i] + 2) / 2);
  for(int i = n / 2; i < n; ++i) ans[0] += a[i];
  for(int i = 1;
      i + n / 2 < n && (n + 1) % 2 + (2 * i) - 2 < n; ++i) {
    long long now = ans[i - 1];
    now -= a[n / 2 + i - 1];
    now += a[(n + 1) % 2 + (2 * i) - 2];
    ans[i] = now;
  }
  memo[memo.size() - 1] = 100000000000;
}

Measured memory_bytes: 4216
N = int(input())
A = input().split()
B = input().split()
C = input().split()

s = 0
k = int(A[0])
for i in range(N):
  n = int(A[i])
  s += int(B[n-1])
  if k+1 == n:
    s += int(C[n-2])
  k = n

print(s)

Measured memory_bytes: 3060
// C - Sugar Water

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

const int MAX = 4000;
bool dp[MAX][MAX]; // dp[a][b]: 水i(g), 砂糖j(g)の組み合わせがあれば1

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

	dp[100*A][0] = 1;

	for (int a=100*A; a<=F; a++) {
		for (int b=0; b<=F; b++) {
			if (dp[a][b] == 0) continue;

			if (a + 100*A + b <= F) {
				dp[a + 100*A][b] = 1;
			}

			if (a + 100*B + b <= F) {
				dp[a + 100*B][b] = 1;
			}

			if ((b + C) * (100 + E) <= E * (a + (b + C)) && a + (b + C) <= F) {
				dp[a][b+C] = 1;
			}

			if ((b + D) * (100 + E) <= E * (a + (b + D)) && a + (b + D) <= F) {
				dp[a][b+D] = 1;
			}
		}
	}

	int w = 100*A, s = 0;
	for (int a=100*A; a<=F; a++) {
		for (int b=0; b<=F; b++) {
			if (dp[a][b] == 0) continue;

			if (b * (w + s) > s * (a + b)) {
				w = a;
				s = b;
			}
		}
	}

	cout << w + s << " " << s << endl;

	return 0;
}

Measured memory_bytes: 10496
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
    ll a;
    double b;
    cin >> a >> b;
    cout << (a * (ll)(b * 100 + 0.1)) / 100LL << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int h, w; cin >> h >> w;
  vector<vector<char>> a(h, vector<char>(w));
  for(int i=0;i<h;++i) {
    for(int j=0;j<w;++j) {
      cin >> a[i][j];
    }
  }
  bool ans = true;
  for(int i=0;i<h;++i) {
    for(int j=0;j<w;++j) {
      int cnt1 = 0, cnt2 = 0;
      if(0 <= i-1) cnt1 += a[i-1][j] == '#';
      if(0 <= j-1) cnt1 += a[i][j-1] == '#';
      if(i+1 < h) cnt2 += a[i+1][j] == '#';
      if(j+1 < w) cnt2 += a[i][j+1] == '#';
      if(cnt1 > 1 || cnt2 > 1) {
        ans = false;
        break;
      }
    }
  }
  cout << (ans ? "Possible" : "Impossible") << endl;
}


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


public class Main {


	public static void main(String[] args) {
		int a=0,b=0;
		String s =null;
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		try{
			s=br.readLine();
			StringTokenizer st= new StringTokenizer(s, " ");
			a=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
		}catch(IOException e){
			e.printStackTrace();
		}
		if(a>b){
			System.out.println("a > b");
		}
		else if(a<b){
			System.out.println("a < b");
		}
		
		else{
			System.out.println("a == b");
		}
	}

}



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

const int D = 60;
const int MAX_N = 200005;
int to[D][MAX_N];


int main() {
    int n;
    ll k;
    cin >> n >> k;
    rep(i,n) {
        cin >> to[0][i];
        to[0][i]--;
    }

    rep(i,D-1)rep(j,n) {
        to[i+1][j] = to[i][to[i][j]];
    }

    int v = 0;
    for (int i = D-1; i >= 0; --i) {
        ll l = 1ll<<i;
        if (l <= k) {
            v = to[i][v];
            k -= l;
        }
    }
    cout << v+1 << endl;
    
    return 0;
}



Measured memory_bytes: 50472
#include<iostream>
#include<algorithm>
#include<cstring>
#include<numeric>
#include<vector>
using namespace std;

#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

const int mxsz = 3e3 + 5;
const int mod = 1e9 + 7;

int dp[mxsz][mxsz];

signed main()
{
	ndbg( ios::sync_with_stdio(0); cin.tie(0); );
	int n; cin>>n;
	string v; cin>>v;
	
	for (int i=0;i<n;i++)
	{
		if (!i) dp[i][i] = 1;
		else
		{
			vector<int> prf(n), suf(n);
			for (int k=0;k<n;k++) prf[k] = (!k? 0: prf[k-1]) + dp[i-1][k], prf[k] %= mod;
			for (int k=n-1;k>=0;k--) suf[k] = (k==n-1? 0: suf[k+1]) + dp[i-1][k], suf[k] %= mod;
			
			for (int k=0;k<=i;k++)
			{
				if (v[i-1]=='<') dp[i][k] = (!k? 0: prf[k-1]);
				else dp[i][k] = (k==i? 0: suf[k]);
			}
		}
	}
	
	int sum = 0;
	for (int i=0;i<n;i++) sum += dp[n-1][i], sum %= mod;
	cout<<sum<<'\n';
}

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

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define rer(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int inf = 1000000000;
const int mod = 1000000007;
const double EPS = 1e-9;
const int dx[] = { -1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int main() {
	// cin.tie(0); // tie
	// ios::sync_with_stdio(false); // sync
	int m; cin >> m;
	while (m--) {
		string str; cin >> str;
		set<string> ans;
		REP(i, 1, str.size()) {
			string sub[5];
			sub[0] = sub[4] = str.substr(0, i);
			sub[1] = str.substr(i);
			sub[2] = sub[0];
			reverse(all(sub[2]));
			sub[3] = sub[1];
			reverse(all(sub[3]));

			for (int i = 0; i < 4; ++i) ans.insert(sub[i] + sub[i + 1]);
			for (int i = 4; i > 0; --i) ans.insert(sub[i] + sub[i - 1]);
		}
		cout << ans.size() << endl;
	}
	return 0;
}

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

int main(void) {
  int n, k;
  cin >> n >> k;
  ll ans;
  ans = k * pow((k-1),n-1);
  cout << ans << endl;
}

Measured memory_bytes: 4008
def ABC076D():
    N = int(input())
    t = list(map(int, input().split()))
    a = []
    for i in t:
        a.append(i * 2)
    t = a
    v = list(map(int, input().split()))
    #print(t)
    speed_lim = [0]
    speed_list = [0 for i in range(sum(t) + 1)]
    for i in range(N):
        for j in range(t[i]):
            speed_lim.append(v[i])
    #print(speed_lim, len(speed_list), len(speed_lim))
    for i in range(1, sum(t) + 1):
        speed_list[i] = speed_list[i - 1] + 0.5
        if speed_list[i] > speed_lim[i]:
            speed_list[i] = speed_lim[i]
    #print(speed_list)
    speed_list[-1] = 0
    for i in range(sum(t) - 1, -1, -1):
        speed_list[i] = min(speed_list[i + 1] + 0.5, speed_list[i])
        if speed_list[i] > speed_lim[i + 1]:
            speed_list[i] = speed_lim[i + 1]
    #print(speed_list)
    ans = 0
    for i in speed_list:
        ans += i

    print(ans / 2)
ABC076D()

Measured memory_bytes: 3760
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << '\n';
#define SAY(X) cout << (X) << '\n';
#else
#define DBG(X)
#define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

std::string pad(int num)
{
    char buffer[4];
    std::snprintf(buffer, sizeof(buffer), "%03d", num);
    return buffer;
}

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

int solve()
{
    int N;

    std::cin >> N;

    while (N > 0) {
        if (N % 10 == 7) {
            cout << "Yes" << endl;
            return 0;
        }
        N /= 10;
    }

    cout << "No" << endl;

    return 0;
}

int main()
{
//    std::cout << solve() << std::endl;
    solve();

    return 0;
}

Measured memory_bytes: 3632
// #Sazaの1日1AC
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000000+7;
const long long INF=9e18;
const double PI=3.14159265358979323846;

//マクロ
//型エイリアス
using ll = long long;
using P=pair<long long,long long>;
using vl=vector<long long>;
using vvl=vector<vector<long long>>;
using vP=vector<pair<long long, long long>>;
//ショートカット
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,k,n) for(int i=k;i<n;i++) //半開区間
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
//入力
#define vin(v,N) for(long long i=0;i<N;i++) cin>>v.at(i)
#define lin(n) long long n;cin>>n
#define chin(x) char x;cin>>x;
#define sin(s) string s;cin>>s;
#define vlin(v,N) vector<long long>v(N);for(long long i=0;i<N;i++)cin>>v.at(i)

#define max(a,b) max((ll)a,(ll)b)
#define min(a,b) min((ll)a,(ll)b)

//関数
//最大公約数
long long gcd(long long m, long long n){
  long long a=max(m,n);
  long long b=min(m,n);
  long long r=a%b;
  while(r!=0){
    a=b; b=r; r=a%b;
  }
  return b;
}
// 最小公倍数
long long lcd(long long m, long long n){
  return m*n/gcd(m,n);
}
//xのn乗
long long power(long long x, long long N){
  long long ret=1;
  for(long long i=0;i<N;i++)   
    ret*=x;
  return ret;
}
//繰り返し二乗法
long long repeat_squaring(long long x, long long n){
  if(n==0) return 1;
  else if(n%2==0){
    long long t=repeat_squaring(x,n/2);
    return t*t%mod;
  }
  else
    return x*repeat_squaring(x,n-1);
}
//素因数分解(mapで返す)
map<long long,long long> factor(long long p){
  ll p1=p;
  map<long long,long long>ret;
  for(long long i=2;i*i<=p1;i++){
     while(p%i==0){
      ret[i]++;
      p/=i;
    }
  }
  if(p!=1)
  ret[p]++;
  return ret;
}
//素数判定
bool is_prime(long long N){
  for(long long i=2;i*i<=N;i++){
    if(N%i==0)
      return false;
  }
  return true;
}
//最大値更新
void chmax(long long &a,long long b){
  a=max(a,b);
}
//最小値更新
void chmin(long long &a,long long b){
  a=min(a,b);
}

//構造体
//Union-Find木
struct UnionFind{
  //メンバ変数 
  vector<long long>par; //par[i]:=頂点iの親
  vector<long long>s; //s[i]:=頂点iが属する集合の個数(iが根のとき)
  
  //コンストラクタ
  UnionFind(long long N):par(N),s(N){
    for(long long i=0;i<N;i++){
      par[i]=i; //最初はすべてが根として初期化
      s[i]=1;
    }
  }
  //メンバ関数
  //root(i):=頂点iの根
  long long root(long long i){
    if(par[i]==i) return i;
    par[i]=root(par[i]); //経路圧縮
    return root(par[i]); //再帰
  }
  //size[i]:=iが属する集合の個数
  long long size(long long i){
    return s[root(i)];
  }
  //same(x,y) xとyが同じ根を持つか(同じ集合に含まれるか)
  bool same(long long x, long long y){
    return root(x)==root(y);
  }
  //unite(x,y) xの根をyの根に繋げる(集合を合併)
  void unite(long long x, long long y){
    if(!same(x,y)){
      long long rx=root(x);
      long long ry=root(y);
      par[rx]=par[ry];
      s[ry]=s[rx]+s[ry];
    }
  }
};
//////////////////ここまでライブラリ///////////////////////

//メイン関数
int main(){
  //doubleの桁数
  cout<<fixed<<setprecision(10);
  
  
  lin(a);lin(b);lin(c);
  
  cout << c << " " << a << " " << b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;

int N;
int so[200001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a; cin >> a;
		so[a]++;
	}
	for (int i = 1; i <= N; i++) cout << so[i] << '\n';
	return 0;
}

Measured memory_bytes: 4400
a=list(input())
b=list(input())
c=list(input())
order='a'
while True:
  if order=='a':
    if len(a)==0:
      print('A')
      break
    else:
      order=a[0]
      a=a[1:]
  elif order=='b':
    if len(b)==0:
      print('B')
      break
    else:
      order=b[0]
      b=b[1:]
  elif order=='c':
    if len(c)==0:
      print('C')
      break
    else:
      order=c[0]
      c=c[1:]

Measured memory_bytes: 80436
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()　{
	string S;
  	cin >> S;
  	string divide[4] = {"dream", "dreamer", "erase", "eraser"};
  	
  	reverse(S.begin(), S.end());
  	for(int i = 0; i <4; i++) reverse(divide[i].begin(), divide[i].end());
  
  	bool can = true;
  
  	for(int i = 0; i < S.size();) {
    	bool can2 = false;
      	for (int j = 0; j< 4; j++) {
        	string d = divide[j];
          	if (S.substr(i, d.size()) == d) {
            	can2 = true;
              	i += d.size();
            }
        }
      	
      	if (!can2) {
        	can = false;
          	break;
        }
    }
  
  	if (can) cout << "YES" << endl;
  	else cout << "NO" << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<deque>
#include<set>
#include<map>
#include<bitset>
#include<ctime>
#include<queue>
using namespace std;
#define int long long
#define mn 100005
#define inf 4444444444444444444
#define mod 1000000009
#define FLN "test"
#define pii pair <int, int>
#define XX first
#define YY second

int dsk[5];

signed main()
{
#ifdef lowie
	freopen(FLN".inp", "r", stdin);
	freopen(FLN".out", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
  
  int u, v;
  for (int i=0; i<3; i++)
  {
    cin>>u>>v;
    dsk[u]++, dsk[v]++;
}
  if (dsk[1]==3 || dsk[2]==3 || dsk[3]==3 || dsk[4]==3) cout<<"NO";
  else cout<<"YES";
}
// PLEASE REMOVE "cout" AND "cerr" DEBUG LINES BEFORE SUBMITTING PROBLEMS
// Code by low_
// Contact me via mail: dung.totuan01@gmail.com
// ...or codeforces: www.codeforces.com/profiles/low_
// ...or if you're interested in food: www.instagram.com/lowie_review/


Measured memory_bytes: 256
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int a = sc.nextInt();
  int b = sc.nextInt();
  int ans = 0;
  for(int i =1;i<=n;i++){
    int c = (i/10000) + (i%10000)/1000 + (i%1000)/100 + (i%100)/10 +i%10;
    if(c>=a && c<=b)ans += i;
    if(i == n)System.out.println(ans);
  }
}}


Measured memory_bytes: 21844
use std::io;

fn group(x: i32) -> i32 {
    match x {
        1 | 3 | 5 | 7 | 8 | 10 | 12 => 0,
        4 | 6 | 9 | 11 => 1,
        2 => 2,
        _ => -1
    }
}

fn main() {

    let mut input = String::new();

    io::stdin().read_line(&mut input);
    let mut iter = input.split_whitespace();

    let a = iter.next().unwrap().parse::<i32>().unwrap();
    let b = iter.next().unwrap().parse::<i32>().unwrap();

    let a_group = group(a);
    let b_group = group(b);

    if a_group == b_group {
        println!("Yes");
    }
    else {
        println!("No");
    }
}

Measured memory_bytes: 4352
## coding: UTF-8

#ループ構造を見つけたらやめるところまで実装
#freshを用意して、Falseになったらやめる実装

N, K = map(int,input().split())
A = list(map(int,input().split()))



#log = [1] #訪れた地点を記録するもの
#last  = 1 #最後に訪れた地点を記録するもの（ここから次に行くところを検索する）
fresh = ['a'] + [True] * N #まだついたことのない場所をTrueにしている
fresh[1] = False
turn = ['a'] + [0] * N #なん回目におとづれたか記録する
status = True



def search_loop():
    log = [1] #訪れた地点を記録するもの
    last  = 1 #最後に訪れた地点を記録するもの（ここから次に行くところを検索する）
    counter = 0
    while status:
        next_spot = A[last - 1]
        counter += 1
        #print(next_spot)
        if(fresh[next_spot]):
            #処理を書く
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            turn[next_spot] = counter
        else:
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            #最後の人処理をする
            break
    return log, last, turn, counter
    



if(A[0] == 1):
    #1から1へテレポートするなら、答えは必ず1になる。
    ans = 1
else:
    loop, loop_folder, kiroku, count = search_loop()
    #print('loop:{}, loop_folder(結節点):{}, kiroku(なん回目にどこを訪れた):{}, count(終わらせた歩数):{}'.format(loop, loop_folder, kiroku, count))
    #print('結節点を最初に通ったのはK={}'.format(kiroku[loop_folder]))
    x = kiroku[loop_folder]
    p = count - x #p歩でループする
    #print(p)
    if(K < x):
        ans = loop[K]
    else:
        l = loop[x:count]
        L = K - x
        mod = L % p
        #print(mod)
        #print(l[mod])
        ans = l[mod]
print(ans)





Measured memory_bytes: 101912
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;

int di[8] = {0,0,1,-1,1,1,-1,-1};
int dj[8] = {1,-1,0,0,1,-1,1,-1};

int main(){
    int n;
    while(cin >> n, n){
        set<pair<int,int>> points;
        map<pair<int,int>,pair<int,int>> futon;
        for(int i = 0; i < n; i++){
            int x, y;
            char c;
            cin >> x >> y >> c;
            points.insert({x, y});
            int nx = x, ny = y;
            (c == 'x' ? nx : ny)++;
            points.insert({nx, ny});
            futon[{x,y}] = {nx,ny};
            futon[{nx,ny}] = {x,y};
        }
        map<pair<int,int>,int> color;
        bool valid = true;
        for(pair<int,int> p : points){
            if(!valid)  break;
            if(color.count(p))    continue;
            queue<pair<int,int>> paint;
            paint.push(p);
            color[p] = 1;
            while(!paint.empty()){
                pair<int,int> now = paint.front(); paint.pop();
                for(int k = 0; k < 4; k++){
                    pair<int,int> next = now;
                    next.first += di[k], next.second += dj[k];
                    if(points.count(next) == 0)   continue;
                    int nowcolor = color[now], nextcolor = color[next];
                    if(next == futon[now]){
                        if(nextcolor == 0){
                            color[next] = -nowcolor;
                            paint.push(next);
                        }else if(nextcolor == nowcolor){
                            valid = false;
                            break;
                        }else{
                            // futon[now] has already colored correctly
                        }
                    }else{
                        if(nextcolor){
                            if(nextcolor != nowcolor)   valid = false;
                        }else{
                            color[next] = nowcolor;
                            paint.push(next);
                        }
                    }
                }
            }
        }
        cout << (valid ? "Yes" : "No") << endl;
    }
    return 0;
}


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

vector<string> dic;
string In;
char num[256];

int ind[1000];
int p;

void make() {
  num['a'] = num['b'] = num['c'] = '2';
  num['d'] = num['e'] = num['f'] = '3';
  num['g'] = num['h'] = num['i'] = '4';
  num['j'] = num['k'] = num['l'] = '5';
  num['m'] = num['n'] = num['o'] = '6';
  num['p'] = num['q'] = num['r'] = num['s'] = '7';
  num['t'] = num['u'] = num['v'] = '8';
  num['w'] = num['x'] = num['y'] = num['z'] = '9';
}

bool solve(int pos) {
  if(pos == In.size()) {
    for(int i = 0; i < p; ++i) {
      if(i != 0) cout << " ";
      cout << dic[ind[i]];
    }
    cout << "." << endl;
    return true;
  }
  for(int i = 0; i < dic.size(); ++i) {
    bool flag = true;
    for(int j = 0; j < dic[i].size(); ++j) {
      if(pos+j >= In.size() || num[dic[i][j]] != In[pos+j]) {
	flag = false;
	break;
      }
    }
    if(flag) {
      ind[p++] = i;
      solve(pos+dic[i].size());
      --p;
    }
  }
  return false;
}

int main() {
  make();
  int N;
  while(cin >> N && N) {
    dic.clear();
    for(int i = 0; i < N; ++i) {
      string str;
      cin >> str;
      dic.push_back(str);
    }
    cin >> In;
    p = 0;
    solve(0);
    cout << "--" << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
const int nmax=3e5+3;
int v[nmax],x,k,st,dr,n,sol;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>x;
    v[++k]=x;
    for(int i=2;i<=n;++i)
    {
        cin>>x;
        if(x<=v[k])
        {
            v[++k]=x;
            continue;
        }
        st=1;
        dr=k;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(v[mij]<x)
            {
                sol=mij;
                dr=mij-1;
            }
            else st=mij+1;
        }
        v[sol]=x;
    }
    cout<<k;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
#define REP(i,n) for (int i = 0; i < n; i++)
typedef long long ll;
 
int main() {
 
    ll N,M,R; cin >> N >> M >> R;
    vector<ll> r(R);
    REP(i,R) cin >> r[i];
 
    REP(i,R) r[i]--;
    sort(r.begin(), r.end());
 
    ll dist[300][300];
    REP(i,300)REP(j,300) dist[i][j] = 1e18;
    REP(i,N) dist[i][i] = 0;
 
    REP(i,M) {
        ll A,B,C;
        cin >> A >> B >> C;
        A--, B--;
        dist[A][B] = C;
        dist[B][A] = C;
    }
    
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
 
    ll ans = 1e18;
    do {
        ll d = 0;
        REP(i,r.size() - 1) d += dist[r[i]][r[i+1]];
        ans = min(ans, d);
    } while(next_permutation(r.begin(), r.end()));
 
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    if(b==1){
        cout <<0<<endl;
        return 0;
    }
    int ans=1;
    int num=a;
    a--;
    while(num<b){
        num+=a;
        ans++;
    }

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



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

using namespace std;

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

	vector<int> t(n + 1);
	vector<int> x(n + 1);
	vector<int> y(n + 1);

	t[0] = x[0] = y[0] = 0;

	for (int i = 0; i < n; i++) {
		cin >> t[i+1] >> x[i+1]>> y[i+1];
	}

	int can = 1;
	for (int i = 0; i < n; i++) {
		int dt = t[i + 1] - t[i];
		int dx = x[i + 1] - x[i];
		int dy = y[i + 1] - y[i];
		int dis = abs(dx) + abs(dy);
		
		if (dt < dis) { can = 0; break; };
		if (dt % 2 != dis % 2) { can = 0; break; };
		

	}
	if (can)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 1408
import math
import sys
sys.setrecursionlimit(10**6)
class SegmentTree:
    """
    単位元のメモ書き（各演算に対する単位元の対応）
    f(x,y) := x+y -> 0
    f(x,y) := x-y -> 0
    f(x,y) := x*y -> 1
    f(x,y) := gcd(x, y) -> 0
    """

    def __init__(self, size, func=lambda x,y:x+y, default=0):
        """
        size : 配列のサイズ
        func : queryの内容(e.g. 区間和ならf(x, y)=x+y)
        default : 単位元
        """
        self.size = 2**(size-1).bit_length()
        self.default = default
        self.dat = [default for _ in range(self.size*2-1)]
        self.f = func

    def update(self, i, x):
        """
        i番目の値をxに変更する。0-indexedなので注意
        """
        i = i + self.size - 1 #一番下の層の値
        self.dat[i] = x

        while i > 0:
            i = (i-1)>>1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, a, b, k=0, L=0, R=None):
        """
        区間[a, b]に関するクエリを処理します。
        例えばi=1,2,3に関して処理したいなら外からquery(1, 3+1)と呼ぶ必要があります。
        """
        if R is None:
            R = self.size

        #区間がかぶっていない場合
        if R <= a or b <= L:
            return self.default

        #区間が完全に収まっている場合
        if a <= L and R <= b:
            return self.dat[k]

        else:
            lres = self.query(a, b, 2*k+1, L, (L+R)>>1)
            rres = self.query(a, b, 2*k+2, (L+R)>>1, R)
            return self.f(lres, rres)


N = int(input())
A = list(map(int, input().split()))

segTree = SegmentTree(N, func=lambda x,y:math.gcd(x,y), default=0)
for i in range(N):
    segTree.update(i, A[i])

ans = -1
for i in range(N):
    a = segTree.query(0, i)
    b = segTree.query(i+1, N)
    ans = max(ans, math.gcd(a,b))

print(ans)


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

#define int long long
#define pb push_back
#define mod 1000000007
#define w(x) int x;cin>>x; while(x-->0)

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

}

void mysol()
{
    int n; cin >> n;
    int arr[n][3];
    for (auto &i : arr)
        for (auto &j : i)
            cin >> j;
    int dp[n + 1][3];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 0; k < 3; k++)
            {
                if (k == j)
                    continue;
                dp[i + 1][j] = max(dp[i + 1][j], arr[i][j] + dp[i][k]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 3; i++)
        ans = max(ans, dp[n][i]);
    cout << ans;
}

int32_t main()
{
    fast();
    // w(t)
    {
        mysol();
    }
    return 0;
}



Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define ll long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define testcase ll T; cin >> T; for (ll tc = 1; tc <= T; tc++)
#define M 1000000007
#define MM 2000000000000000000
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
#define r2 1.41421356237
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //testcase {
  int n;
  cin>>n;
  vector<ll>v1,v2;
  for(int i=0;i<n;i++) {
  	ll a,b;
  	cin>>a>>b;
  	v1.pb(a+b);
  	v2.pb(a-b);
  }
  sort(all(v1));
  sort(all(v2));
  ll ans=max(v1[n-1]-v1[0],v2[n-1]-v2[0]);
  cout<<ans;
  //}
  return 0;
}

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

#define MOD (1000 * 1000 * 1000 + 7)
#define INF (1LL << 60)
#define pb push_back
#define po pop_back
#define fi first
#define se second

typedef long long ll;
typedef long double ld;

#define maxn 3005

ld A[maxn];
int N;

ld dp[maxn][maxn];

ld solution(int n, int h) {
  if (n >= N && h > (int)(N / 2)) {
    return 1;
  } else if(n >= N) {
    return 0;
  }

  if (dp[n][h] != -1.0)
    return dp[n][h];

  dp[n][h] = solution(n + 1, h + 1) * A[n] +
             solution(n + 1, h) * (1.0 - A[n]);

  return dp[n][h];
}

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

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

  for (int i = 0; i < maxn; ++i) {
    for (int j = 0; j < maxn; ++j) {
      dp[i][j] = -1.0;
    }
  }

  cout << setprecision(10) << solution(0, 0) << endl;

  return 0;
}

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


const ll INF = 1e18;



int main() {
  ll n, m;
  cin >> n >> m;
  vector<P> c(m);
  vector<ll> p(15);
  ll now=1;
  rep(i,14){
    p[i]=now;
    now*=2;
  }
  rep(i,m){
    ll a1,b1;
    cin>>a1>>b1;
    ll now=0;
    rep(j,b1){
      ll c1;
      cin>>c1;
      c1--;
      now+=p[c1];
    }
    c[i]=make_pair(a1,now);
  }
  ll N=(2<<n);
//  cout<<N<<"N"<<endl;
//  cout<<(13|14)<<endl;
  ll dp[m+5][N+5];
  rep(i,m+5)rep(j,N+5)dp[i][j]=INF;
  rep(i,m+5) dp[i][0]=0;
  rep(i,m){
    rep(j,N){
      ll cost=c[i].first;
      ll key=c[i].second;
      dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
      dp[i+1][j|key]=min(dp[i+1][j|key], dp[i][j]+cost);
    //  cout<<dp[i][j]+cost<<' '<<i<<'i'<<j<<'j'<<' '<<(j|key)<<endl;
    }
  }
//cout<<endl;
  ll ans=INF;
  rep(i,m+1){
    ans=min(ans,dp[i][(2<<(n-1))-1]);
  //  cout<<((2<<(n-1))-1)<<" "<<ans<<endl;
  }
  if (ans==INF)ans=-1;
  cout<<ans;
}


Measured memory_bytes: 67924
//29
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  for(int n;cin>>n,n;){
    int num[7]={};
    while(n--){
      int a;
      cin>>a;
      num[min(a/10,6)]++;
    }
    for(int i=0;i<7;i++){
      cout<<num[i]<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 864
import sys

n= int(sys.stdin.readline())
a = [ int(x) for x in sys.stdin.readline().split() ]

x = 0
for i in range(n):
    if i%2==0: x+= a[i]
    else: x-=a[i]
#
print( x,end="" )
for i in range(n-1):
    x = 2 * a[i] - x
    print( " {}".format( x ),end="" )
print()


Measured memory_bytes: 14584
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        
        int a = stdIn.nextInt();
        int b = stdIn.nextInt();

        if(a > b){
            System.out.println("a > b");
        }

        else if(a < b){
            System.out.println("a < b");
        }

        else{
            System.out.println("a == b");
        }

    }



}


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

int main(){
	ll N;cin>>N;
	ll ret=0;
	ll decl=0;
	ll last=-1;
	for(ll a=0;a<N;++a){
		ll n;cin>>n;
		if(last==-1){
			last=n;
			++ret;
			continue;
		}
		if(last==n){
			continue;
		}
		if(decl==0){
			if(n>last){
				decl=1;
				last=n;
				continue;
			}
			if(n<last){
				decl=2;
				last=n;
				continue;
			}
		}
		if(decl==1){
			if(n>last){
				last=n;
				continue;
			}
			if(n<last){
				decl=0;
				last=n;
				++ret;
				continue;
			}
		}
		if(decl==2){
			if(n>last){
				decl=0;
				last=n;
				++ret;
				continue;
			}
			if(n<last){
				last=n;
				continue;
			}
		}
	}
	cout<<ret<<endl;
}


Measured memory_bytes: 256