akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main(){
	int n, i, j;
	int cards[4][13]={0};
	char suit;
	int num;
	
	cin >> n;
	
	for(i = 0; i < n; i++){
		cin >> suit >> num;
		
		if(suit == 'S'){
			cards[0][num - 1]++;
		}else if(suit == 'H'){
			cards[1][num - 1]++;
		}else if(suit == 'C'){
			cards[2][num - 1]++;
		}else{
			cards[3][num - 1]++;
		}
	}
	
	for(i = 0; i < 4; i++){
		for(j = 0; j < 13; j++){
			if(cards[i][j] == 0){
				if(i == 0){
					cout << 'S' << " " << j + 1 << endl;
				}else if(i == 1){
					cout << 'H' << " " << j + 1 << endl;
				}else if(i == 2){
					cout << 'C' << " " << j + 1 << endl;
				}else{
					cout << 'D' << " " << j + 1 << endl;
				}
			}
		}
	}
	
	return 0;	
}

Measured memory_bytes: 3096
import math

a, b, C = map(float, input().split())
C = math.radians(C)

c = (a ** 2 + b ** 2 - 2 * a * b * math.cos(C)) ** 0.5
h = b * math.sin(C)
S = 0.5 * a * h

print("{:.5f}".format(S))
print("{:.5f}".format(a + b + c))
print("{:.5f}".format(h))



Measured memory_bytes: 5704
#include<stdio.h>
#include<limits.h>
#define ll long long
ll a[20],cost=0,ans=LLONG_MAX,k,n,i;
ll min1(ll a,ll b){
	if(a<b)
		return a;
	else
		return b;
}
void match(ll b,ll s,ll e){
	if(b==n){
		if(s>=k){
			ans=min1(ans,cost);
		}
		return ;
	}
	if(a[b]>e){
		match(b+1,s+1,a[b]);
	}
	else{
		match(b+1,s,e);
		cost+=(e+1-a[b]);
		match(b+1,s+1,e+1);
		cost-=(e+1-a[b]);
	}
}
int main(){
	scanf("%lld%lld",&n,&k);
	for(i=0;i<n;i++)
		scanf("%lld",&a[i]);
	match(1,1,a[0]);
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int K = scan.nextInt();
		int X = scan.nextInt();
		scan.close();

		int range = K - 1;
		int sum = X - range;
		for (int i = 0; i < (K - 1) * 2 + 1; i++) {

			System.out.println(sum);
			sum++;
		}
	}
}

Measured memory_bytes: 22868
#include <cstdio>
#define REP(i,n) for (int i=0;i<(n);i++)
int main(){
int W,a,b;
scanf("%d %d %d",&W,&a,&b);
if(a<=b){
if(b-a-W<=0){
printf("0\n");
}else{
printf("%d\n",b-a-W);
}
}else{
if(a-b-W<=0){
printf("0\n");
}else{
printf("%d\n",a-b-W);
}
}
return 0;
}

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

int N;
int x[10], y[10];

double dist(int i, int j) {
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

void solve() {
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> x[i] >> y[i];
    double ans = 0.0;
    for(int i = 1; i <= N; i++) {
        for(int j = i + 1; j <= N; j++) ans += dist(i, j) * 2 / N;
    }
    cout << fixed << setprecision(10) << ans << endl;
    return;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>
#include <cmath>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int N, M;
std::vector<int> k;
std::vector<std::vector<int>> s;
std::vector<int> p;

bool isOK(std::vector<int> &bit) {
  for (int i = 0; i < M; ++i) {
    int tmp = 0;
    for (int j = 0; j < k[i]; ++j) {
      if (bit[s[i][j]])
        tmp++;
    }
    if (tmp % 2 != p[i])
      return false;
  }
  return true;
}

int main() {
  // Input
  std::cin >> N >> M;

  k.resize(M);
  s.resize(M);
  for (int i = 0; i < M; ++i) {
    std::cin >> k[i];
    s[i].resize(k[i]);
    for (int j = 0; j < k[i]; ++j) {
      std::cin >> s[i][j];
      s[i][j]--;
    }
  }
  p.resize(M);
  for (int i = 0; i < M; ++i)
    std::cin >> p[i];

  // std::cout << s << std::endl;
  // std::cout << std::endl;
  // std::cout << p << std::endl;

  // Main
  int res = 0;
  for (int n = 0; n < std::pow(2, N); ++n) {
    // Make bit
    std::vector<int> bit(N, 0);
    int tmp = n;
    int b = N;
    while (tmp > 0) {
      bit[--b] = tmp % 2;
      tmp = tmp / 2;
    }

    if (isOK(bit))
      res++;
  }

  // Output
  std::cout << res << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<functional>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<deque>
#include<stack>
#include<map>
using namespace std;

#define mod 10007

#define ll long long
#define ull unsigned long long


int main() {
	int n, temp, cnt = 0;
	map<int, int> m;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		m[temp]++;
	}
	temp = 0;
	for (auto it : m) {
		if (it.second % 2 == 0) {
			it.second = 2;
			temp++;
		}
		else it.second = 1;
		cnt++;
	}
	printf("%d", (temp % 2 == 0) ? cnt : cnt - 1);
}

Measured memory_bytes: 4864
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <deque>

#define mp make_pair
#define x first
#define y second
#define pb push_back
using namespace std;

const int N = 1e5+5;
int n, k, m, d[N];

int main()
{
    cin >> n >> k >> m;
    for(int i=1; i<=m; ++i) {
        int a; scanf("%d",&a);
        d[a] += 1;
    }
    for(int i=1; i<=n; ++i)
        if (k-m+d[i] > 0) puts("Yes"); else puts("No");
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

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

const int MAXN=100005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N; cin >> N;
	cout << (1000 - (N%1000)) %1000;
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int l, a, b, c, d;

int main(){
	cin >> l >> a >> b >> c >> d;
	int e, f;
	a%c == 0 ? e = a / c : e = a / c + 1;
	b%d == 0 ? f = b / d : f = b / d + 1;
	cout << l - max(e, f) << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    string s;
    cin >> s;
    int n = s.size();
    reverse(ALL(s));
    ll cnt[2019] = {};
    cnt[0] = 1;
    ll ans = 0;
    int now = 0;
    int d = 1;
    for (int i = 0; i < n; i++) {
        int t = s[i] - '0';
        now = (d * t + now) % 2019;
        ans += cnt[now];
        cnt[now]++;
        d *= 10;
        d %= 2019;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3764
#!/usr/bin/env python3

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

mod = 10 ** 9 + 7
ans = 0

for i in range(K, N+2):
    sum_min = i * (i - 1) / 2
    sum_max = i * (2*N - i + 1) / 2
    ans += sum_max - sum_min + 1

print(int(ans % mod))

Measured memory_bytes: 9112
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string S,T;
    cin>>S;
    cin>>T;
    int a=0;
    int length=T.size();
    for(int i=0; i<length-1; i++)
    {
        if(S[i]==T[i])
            a++;
        else
            break;
    }
    if(a==S.size())
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;

}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

int main(){
    string l; cin >> l;
    int n = l.size();
    lint dp[n+1][2];
    rep(i, n+1)rep(j, 2) dp[i][j] = 0;
    dp[0][0] = 1;
    lint mod = 1e9 + 7;
    rep(i, n)rep(j, 2)if(dp[i][j] > 0){
        if(j == 0){
            if(l[i] == '0') dp[i+1][0] = (dp[i+1][0] + dp[i][0]) % mod;
            else{
                dp[i+1][0] = (dp[i+1][0] + 2*dp[i][0]) % mod;
                dp[i+1][1] = (dp[i+1][1] + dp[i][0]) % mod;
            }
        }
        else dp[i+1][1] = (dp[i+1][1] + 3*dp[i][1]) % mod;
    }
    cout << (dp[n][0]+dp[n][1]) % mod << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-9;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int n, m;
  cin>>n>>m;
  cout<<n*(n-1)/2+m*(m-1)/2<<'\n';
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<stack>/*** LIFO *** stack<type> var;
push(), top():to get data, pop():to remove, size(), empty() ***/
using namespace std;

#define Fp(I, STAT, END) for(int I = STAT; I < END; I++)
#define Fm(I, STAT, END) for(int I = STAT; I > END; I--)

int main(){
    int H, A;
    cin >> H >> A;
    if ((H % A) == 0) cout << H / A << endl;
    else cout << (int)(H / A) + 1 << endl; 
}


Measured memory_bytes: 256
#  Areas on the Cross-Section Diagram

class depth_Char:
    ch = ""
    depth = 0

    def __init__(self,char,depth):
        self.ch = char
        self.depth = depth

    def __str__(self):

        return f"{self.ch}:{self.depth}"


string = input()

depth = 0
d_list = []
for ch in string:
    if ch == "\\":
        depth -= 1
        d_list.append(depth_Char(ch,depth))

    elif ch == "_":
        d_list.append(depth_Char(ch,depth))

    elif ch == "/":
        d_list.append(depth_Char(ch,depth))
        depth += 1

# print(*d_list)

lake_list = []  #池のリストを作る
bslash_dict = dict()
for i,d_ch in enumerate(d_list):

    if d_ch.ch == "\\":
        bslash_dict[d_ch.depth] = i
    elif d_ch.ch == "/" and d_ch.depth in bslash_dict:
        j = bslash_dict[d_ch.depth]

        is_need_append = True
        # print(f"search:{[j,i]}")
        remove_list = []  # foreachループの中では削除せず、最後にまとめて削除する

        for lake in lake_list:
            if is_need_append and lake[0] < j and i < lake[1]:
                is_need_append = False

            if j < lake[0] and lake[1] < i:
                # print(f"remove:{lake}")
                remove_list.append(lake)
        
        for rem in remove_list:
            lake_list.remove(rem)

        if is_need_append:
            lake_list.append([j,i])
        

lake_area_list = []
for i,j in lake_list:
    lake = string[i:j+1]
    t_depth = 0
    area = 0
    for ch in lake:
        if ch == "\\":
            t_depth += 1
            area += t_depth
        elif ch == "_":
            area += t_depth
        elif ch == "/":
            t_depth -= 1
            area += t_depth
    
    lake_area_list.append(area)

print(sum(lake_area_list))
print(len(lake_area_list),*lake_area_list)





Measured memory_bytes: 11012
#include <iostream>
#define ll long long int

using namespace std;

int main(){
    ll N, K, X, Y;
    cin >> N >> K >> X >> Y;

    ll ans=0;

    if(N <= K){
        ans = N*X;
    }else{
        ans = K*X + (N-K)*Y;
    }

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
    int n,m,f;
    cin>>n>>m;
    long long int sum=0;
    for(int i=0;i<m;i++)
    {
        cin>>f;
        sum+=f;
    }
    if(sum>n)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<n-sum<<endl;
    }

    return 0;
}


Measured memory_bytes: 3624
num = str(input())
op = ['+', '-']

for i in range(2**3):
    ans = int(num[0])
    t_op = []
    for j in range(3):
        if (i >> j)&1:
            ans -= int(num[j+1])
            t_op.append('-')
        else:
            ans += int(num[j+1])
            t_op.append('+')
    if ans == 7:
        ans_l = [num[0], t_op[0], num[1], t_op[1], num[2], t_op[2], num[3], '=7']
        print(*ans_l,sep='')
        break

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

#define INF (1<<15)

using namespace std;

struct edge{
	int to;
	int cap;
	int rev_id;
};

class FordFulkerson
{
private:
	vector<vector<edge> > adj;
	int v;
	int e;
	vector<bool> visited;
public:
	FordFulkerson() {
		cin >> v;
		cin >> e;
		adj.resize(v);
		for (int i = 0; i < e; ++i)
		{
			int u;
			int v;
			int c;
			cin >> u >> v >> c;
			adj[u].push_back((edge){v, c, adj[v].size()});
			adj[v].push_back((edge){u, 0, adj[u].size() - 1});
		}
	}


	int dfs(int from, int goal, int flow) {
		if(from == goal) return flow;
		visited[from] = true;
		for (int i = 0; i < adj[from].size(); ++i)
		{
			edge &e = adj[from][i];
			if(!visited[e.to] && e.cap > 0) {
				int d = dfs(e.to, goal, min(e.cap, flow));
				if(d > 0) {
					adj[from][i].cap -= d;
					adj[e.to][e.rev_id].cap += d;
					return d;
				}
			}
		}
		return 0;
	}

	void exec() {
		int flow_sum = 0;
		while(true) {
			visited = vector<bool>(v, false);
			int flow = dfs(0, v - 1, INF);
			if(flow == 0) {
				cout << flow_sum << endl;
				return;
			}
			flow_sum += flow;
		}
	}
};

int main() {
	FordFulkerson ff = FordFulkerson();
	ff.exec();
}





Measured memory_bytes: 3192
#include <iostream>
#include <assert.h>
//#include <vector>
//#include <algorithm>
//#include <functional>
#include <cmath>

int main(){
    double N, D;
    std::cin >> N >> D;
    int32_t res = int32_t(std::ceil(N / (2*D + 1)));

    std::cout << res;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
using namespace std;

typedef long long ll;

int main()
{
	int n, m;
	cin >> n;
	string s[100], t[100];
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> t[i];
	}
	int u[100] = {};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (s[i] == s[j]) u[i]++;
		}
		for (int j = 0; j < m; j++) {
			if (s[i] == t[j]) u[i]--;
		}
	}
	sort(u, u + 100);
	reverse(u, u + 100);
	if (u[0] > 0) {
		cout << u[0] << endl;
	}
	else {
		cout << 0 << endl;
	}
	return 0;
}

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

int main(){
  string S; cin >> S;
  int N = S.size();
  bool umb = false;
  int beg = -1, end = -1;
  
  for(int i = 1; i < N; i++){
    if(S[i] == S[i-1]) {
      umb = true;
      beg = i, end = i+1;
      break;
    }
  }
  if(!umb) {
    for(int i = 2; i < N; i++){
      if(S[i] == S[i-2]) {
        umb = true;
        beg = i-1, end = i+1;
        break;
      }
    }
  }
  
  cout << beg << ' ' << end << endl;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int count =0;
		//String As = String.valueOf(A);
		//String Bs = String.valueOf(B);
		for(int i =A;i <= B;i++){
			String ia = String.valueOf(i);
			char[] ic = ia.toCharArray();
			if(ic[0] == ic[4]&&ic[1]==ic[3]){
				count++;
			}
		}
		
		System.out.println(count);
		sc.close();
	}
}


Measured memory_bytes: 30548
import java.util.Scanner;

public class Main {

	static int[] v1 = {0,0, 1, 0, -1};
	static int[] v2 = {0,1, 0, -1, 0};
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(true){
			int n = cin.nextInt();
			if(n==0){
				break;
			}
			int[][][] field = new int[n*2+2][n*2+2][2];
			int midx = n/2+1, midy=n/2+1;
			for(int i = 0; i < n;i++){
				int t = cin.nextInt();
				int f = cin.nextInt();
				int x =midx, y = midy;
				Dice a = new Dice(t, f);
				while(true){
					int max=0, dir=0;
					for(int j = 1; j < 5;j++){
						if(max < a.dice[j]){
							if(field[x][y][0] > field[x+v1[j]][y+v2[j]][0]){
								max = a.dice[j];
								dir = j;
							}
						}
					}
					if(max >= 4){
						a.dice = a.roll(dir);
						x = x+v1[dir];
						y = y+v2[dir];
					}
					else{
						break;
					}
				}
				field[x][y][0]++;
				field[x][y][1]= a.dice[0];
			}
			int[] count = new int[7];
			for(int i = 0; i < field[0].length;i++){
				for(int j = 0; j < field[0].length;j++){
					count[field[i][j][1]]++;
				}
			}
			System.out.print(count[1]);
			for(int i = 2; i < 7;i++){
				System.out.print(" " + count[i]);
			}
			System.out.println();
		}

	}

}
class Dice {
	static int[] dice;
	static int[][] dice_table=
	{   {  0, 0, 0, 0, 0, 0, 0},
		{  0, 0, 3, 5, 2, 4, 0},
		{  0, 4, 0, 1, 6, 0, 3},
		{  0, 2, 6, 0, 0, 1, 5},
		{  0, 5, 1, 0, 0, 6, 2},
		{  0, 3, 0, 6, 1, 0, 4},
		{  0, 0, 4, 2, 5, 3, 0}

	};

	public static void main(String[] args) {

	}
	Dice(int x, int y){
		dice = new int[6];
		dice[0] = x;
		dice[1] = y;
		dice[2] = dice_table[x][y];
		dice[3] = 7-y;
		dice[4] = dice_table[y][x];
		dice[5] = 7-x;
	}
	// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0502
	static int[] roll(int dir){
		int[] b = new int[6];
		if(dir==1){// South
			b[0]=dice[3];
			b[1]=dice[0];
			b[2]=dice[2];
			b[3]=dice[5];
			b[4]=dice[4];
			b[5]=dice[1];
		}
		else if(dir==2){// East
			b[0]=dice[4];
			b[1]=dice[1];
			b[2]=dice[0];
			b[3]=dice[3];
			b[4]=dice[5];
			b[5]=dice[2];
		}
		else if(dir==3){// North
			b[0]=dice[1];
			b[1]=dice[5];
			b[2]=dice[2];
			b[3]=dice[0];
			b[4]=dice[4];
			b[5]=dice[3];
		}
		else if(dir==4){// West
			b[0]=dice[2];
			b[1]=dice[1];
			b[2]=dice[5];
			b[3]=dice[3];
			b[4]=dice[0];
			b[5]=dice[4];
		}
		else if(dir == 5){// Left
			b[0]=dice[0];
			b[1]=dice[4];
			b[2]=dice[1];
			b[3]=dice[2];
			b[4]=dice[3];
			b[5]=dice[5];
		}
		else{// Right
			b[0]=dice[0];
			b[1]=dice[2];
			b[2]=dice[3];
			b[3]=dice[4];
			b[4]=dice[1];
			b[5]=dice[5];
		}
		return b;
	}
}

Measured memory_bytes: 17000
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100
#define infinit 1e+8
int main() {
	int n,p[MAX],m[MAX+1][MAX+1];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i-1] >> p[i];
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == j || i==0 || j==0) m[i][j] = 0;
			else m[i][j] = infinit;
		}
    }
	for (int l = 2; l <= n; l++) {
		for (int i = 0; i <= n - l + 1;i++) {
			int j = i + l - 1;
			for (int k = i; k <= j - 1; k++) {
				m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
			}

		}
	}
	cout << m[1][n] << endl;
	

}



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

const string dirs = "NESW";
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1}; 
int H, W;
ll L;
string c[110];
int dist[110][110][4];

bool contain(int y, int x) {
  return y >= 0 && y < H && x >= 0 && x < W;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> H >> W >> L, H) {
    for (int i = 0; i < H; i++) {
      cin >> c[i];
    }

    int y, x, d;
    fill_n((int*)dist, 110 * 110 * 4, -1);
    using P = tuple<int, int, int>;
    vector<P> ps;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        auto pos = dirs.find(c[i][j]);
        if (pos == string::npos) continue;
        y = i; x = j; d = pos;
        dist[y][x][d] = 0;
        ps.emplace_back(y, x, d);
      }
    }

    while (true) {
      int ny, nx, nd;
      ny = y + dy[d]; nx = x + dx[d]; nd = d;
      if (!contain(ny, nx) || c[ny][nx] == '#') {
        ny = y; nx = x; nd = (d + 1) % 4;
      }
      ps.emplace_back(ny, nx, nd);
      if (dist[ny][nx][nd] < 0) {
        dist[ny][nx][nd] = dist[y][x][d] + (nd == d);
        y = ny; x = nx; d = nd;
      } else {
        break;
      }
    }
    
    int ay = -1, ax = -1, ad = -1;
    for (int i = 0; i < (int)ps.size(); i++) {
      tie(y, x, d) = ps[i];
      if (dist[y][x][d] < L) continue;
      ay = y; ax = x; ad = d;
      break;
    }
    if (!(ay < 0)) {
      cout << ay + 1 << " " << ax + 1 << " " << dirs[ad] << endl;
      continue;
    }
    ps.erase(ps.begin(), find(ps.begin(), ps.end(), *prev(ps.end())));
    int gy, gx, gd;
    tie(gy, gx, gd) = *prev(ps.end());
    auto it = ps.begin();
    while (true) {
      tie(y, x, d) = *it;
      if (y != gy || x != gx) {
        ps.erase(ps.begin(), it);
        break;
      }
      it++;
    }
    vector<P> nps;
    int pos = 0;
    while (pos < (int)ps.size()) {
      tie(y, x, d) = ps[pos];
      nps.emplace_back(ps[pos++]);
      while (pos < (int)ps.size()) {
        int ny, nx, nd;
        tie(ny, nx, nd) = ps[pos];
        if (ny != y || nx != x) break;
        pos++;
      }
    }
    int T = nps.size();
    tie(ay, ax, ad) = nps[(L - dist[gy][gx][gd] + T - 1) % T];
    cout << ay + 1 << " " << ax + 1 << " " << dirs[ad] << endl;
  }

  return 0;
}


Measured memory_bytes: 3540
function main(input) {
  input=input.trim();
  const a = parseInt(input.split(" ")[0], 10);
  const b = parseInt(input.split(" ")[1], 10);
  const k = parseInt(input.split(" ")[2], 10);
  var arr=[]
  for(var i=0; i<k; i++){
    if(a+i<=b){
      arr.push(a+i)
    }
  }
  for(var i=0; i<k; i++){
    if(arr.indexOf(b-i)==-1){
      if(a<=b-i)
      arr.push(b-i)
    }
  }
  arr.sort(function(a,b){
    if( a < b ) return -1;
    if( a > b ) return 1;
    return 0;
  });
  for(var i=0; i<arr.length; i++){
    console.log(arr[i]);
  }
}


main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 9392
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		int[][]A = new int[N][];
		for(var i=0;i<N;i++){
			string[] str = Console.ReadLine().Split();
			A[i] = new int[2]{int.Parse(str[0]),int.Parse(str[1])};
		}
		Array.Sort(A,(x,y)=>y[0]+y[1]-x[0]-x[1]);
		long ans = 0;
		for(var i=0;i<N;i++){
			if(i%2==0){
				ans += A[i][0];
			} else {
				ans -= A[i][1];
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 23744
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))



int mp[92][92];
bool ch[92][92];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};//北,東,南,西


int dfs(int y,int x,int sum){
	ch[y][x]=true;
	int a=sum;//ここまでの探索階層
	REP(i,4){
		if(mp[y+dy[i]][x+dx[i]]==1&&!ch[y+dy[i]][x+dx[i]]){
			a=max(a,dfs(y+dy[i],x+dx[i],sum+1));
		}
	}
	ch[y][x]=false;
	return a;
}
int main(){
	
	int n,m;
	while(cin>>m>>n){
		if(n==0&&m==0)break;
		CLR(mp);
		REP(i,n)REP(j,m)cin>>mp[i+1][j+1];
		int res=0;
		FOR(i,1,n+1){
			FOR(j,1,m+1){
				if(mp[i][j]==1){
					CLR(ch);
					//cout<<dfs(i,j,1)<<" ";
					res=max(res,dfs(i,j,1));
				}
			}
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <queue>

using namespace std;
typedef long long ll;

int main() {
    ll a,b,c;
    cin >> a >> b >> c;
    ll d = c-a-b;
    if(d > 0 && 4*a*b < d*d){
        cout << "Yes";
    } else {
        cout << "No";
    }
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chkmax(T& a,T b){return a<b?a=b,1:0;}
template<class T> inline bool chkmin(T& a,T b){return a>b?a=b,1:0;}
template<typename T> inline T& read(T& x){
    static char c; bool flag=0;
    while(!isdigit(c=getchar())) if(c=='-') flag=1;
    for(x=c-'0';isdigit(c=getchar());(x*=10)+=c-'0');
    if(flag) x=-x;
    return x;
}
char s[55];
int main(){
    scanf("%s",s);
    for(int i=0;i<strlen(s)-8;i++) printf("%c",s[i]);
    return 0;
}


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

using namespace std;
namespace{
    const int DATA_MIN = 1;
    const int DATA_MAX = 10000000000;
}

int main() {
    int n, r_min, rn;
    int max_prof = DATA_MIN - DATA_MAX;
    cin >> n;
    for(unsigned int i = 1; i < n; i++){
        if(i == 1) cin >> r_min;
        cin >> rn;
        max_prof = max(max_prof, rn - r_min);
        r_min = min(r_min, rn);
    }
    cout << max_prof << endl;
    return 0;
}


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

int main() {
  vector<int> a(3);
  cin >> a.at(0) >> a.at(1) >> a.at(2);
  sort (a.begin(), a.end());
  if (a.at(0)+a.at(1)==a.at(2)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
n,l=map(int,input().split())
ans=0
if l<0:
    if n>-l:
        for i in range(n):
            ans+=l+i
    else:
        for i in range(n):
            ans+=l+i
        ans-=l+n-1
else:
    for i in range(n):
        ans+=l+i
    ans-=l
print(ans)

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

int main(){
    int n;
    cin>>n;
    vector<int> ans(n+1,-1);
    for(int i=1;n>0;i++){
      n-=i;
      if(n<0) ans[-1*n]=0;
      ans[i]=i;
    }
    for(int i=1;i<=(int)ans.size();i++){
      if(ans[i]==-1) return 0;
      else if(ans[i])cout<<ans[i]<<endl;
    }
}

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

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

bool same(int x, int y) { return root(x) == root(y); }

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  int N, i;
  cin >> N >> i;
  cout << (N - i + 1) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define inf 0x7fffffff
#define infll 0x7fffffffffffffff
#define clr(c) memset(c,0,sizeof(c))
using namespace std;
int mod=998244353;
const int M=1e6+10;
const int N=3e5+10;
inline ll read(){
    ll b=1,sum=0; char c=getchar();
    while(!isdigit(c)){if(c=='-') b=-1; c=getchar();}
    while(isdigit(c)){sum=sum*10+c-'0'; c=getchar();}
    return b*sum;
}
ll T,n,m;
int ans;
int main()
{
    int i,j,k;
    ll x=read();
    ans=0;
    n=100;
    for(i=1;;i++) {
    	ans++;
    	n+=n/100;
    	if(n>=x) break;
	}
	printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 3760
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<functional>
using  namespace std;
typedef long long ll;
#define sc(x) scanf("%d",&x)
#define pd(x) printf("%d\n",x)
const int INF=1e9+10;
const int MOD=1e9+7;
const double eps=1e-5;
const double pi=acos(-1.0);
const int N=2e5+5;
ll p,a[N],sum[N],s[N];
int n;
int lowbit(int i)
{
    return i&(-i);
}
void update(int i)
{
    while(i<=n)
    {
        sum[i]+=1;
        i+=lowbit(i);
    }
}
ll get_sum(ll i)
{
    ll ans=0;
    while(i)
    {
        ans+=sum[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    while(~scanf("%d%lld",&n,&p))
    {
        memset(sum,0,sizeof(sum));
        memset(s,0,sizeof(s));
        ll ans=0,Ans=0;
        a[0]=0;
        s[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
            a[i]-=p;
            a[i]+=a[i-1];
            s[i]=a[i];
        }
        n++;
        sort(s,s+n);
        int k=unique(s,s+n)-s;
        for(int i=n; i>=1; i--) a[i]=a[i-1];
        for(int i=1; i<=n; i++) a[i]=(lower_bound(s,s+k,a[i])-s)+1;
        for(int i=1; i<=n; i++)
        {
            update(a[i]);
            ll tmp=get_sum(a[i]);
            ans+=tmp-1;//i前面小于等于a[i]的数个数
            Ans=i-tmp;
//        printf("i==%d a[i]==%lld tmp==%lld  ans==%lld\n",i,a[i],tmp,i-tmp);
        }
        printf("%lld\n",ans);
//        printf("%lld\n",Ans);//求逆序数
    }
    return 0;
}

//7 26
//10
//20
//30
//40
//30
//20
//10



Measured memory_bytes: 4992
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	[ n, k ] <- readInts
	printf "%.12f\n" $ ( / fromIntegral n ) $ sum $ map ( solve k ) [ 1 .. n ]

solve :: Int -> Int -> Double
solve k x = ( 0.5 ) ^ rolling x
	where
		rolling x'
			| x' < k = 1 + rolling ( 2 * x' )
			| otherwise = 0

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

#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>

using namespace std;


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


int power(int a,int n)
{
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return a*power(a*a,n/2);
    return power(a*a,n/2);
}
const int md = 998244353;
const int inf = (int) 1e18;

/*int inverse(int x){

    return power(x,mod-2)%mod;//little fermat....
}*/
int lcm(int x,int y){
    return (x*y)/__gcd(x,y);
}

signed main()
{
    showoff;
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int ans = b/c+b/d-b/lcm(c,d);
    a--;
    ans -= a/c+a/d-a/lcm(c,d);
    cout << b-a-ans;
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...   

Measured memory_bytes: 256
n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
c = [list(map(int, input().split())) for _ in range(m)]
for si in s:
    di = 10 ** 10
    ans = 0
    for j, cj in enumerate(c):
        dij = abs(si[0] - cj[0]) + abs(si[1] - cj[1])
        if dij < di:
            di = dij
            ans = j + 1
    print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define REP(i, n) for (LL i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (LL i = m; i n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define int long long
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
signed main() {
 int n;
  cin >> n;
  vector<int> a(n);
  REP(i,n)cin>>a[i];
  SORT(a);
  int s=0;
  REP(i,n-1)s+=a[i];
  if(a[n-1]<s){
  cout << "Yes";
  }else{
  cout << "No";
  }
}


Measured memory_bytes: 3640
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define co(x) cout << (x) << "\n"
#define pb push_back
#define Never
#define To

using namespace std;

int main(){

	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;

	cin >> N;

	int L[N];

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

	sort(L, L+N);

	long long ans = 0;

	for(int i = 0; i < N-2; i++){
		for(int j = i +1; j < N -1; j++){
			for(int k = j + 1; k < N;  k++){
				if(L[i] + L[j] <= L[k]) {
					break;
				} else {
					ans++;
				}
			}
		}
	}

	cout << ans << endl;

	Never To return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>

using namespace std;
int main(){
    int n;
    string s;

    cin >> n; cin >> s;
    s= "_"+s;

    long long int ans = 0;
    for(int j=1;j<=n;j++){
        int sum_lr=0,sum_lg=0,sum_lb=0,sum_rr=0,sum_rg=0,sum_rb=0;
        for(int i=j-1;i>0;i--){
            if(s[i]=='R')sum_lr++;
            else if(s[i]=='G')sum_lg++;
            else if(s[i]=='B')sum_lb++;
        }
        for(int i=j+1;i<=n;i++){
             if(s[i]=='R')sum_rr++;
            else if(s[i]=='G')sum_rg++;
            else if(s[i]=='B')sum_rb++;           
        }
        if(s[j]=='R'){ ans+= sum_lg*sum_rb + sum_lb*sum_rg; }
        if(s[j]=='G'){ ans+= sum_lr*sum_rb + sum_lb*sum_rr; }
        if(s[j]=='B'){ ans+= sum_lr*sum_rg + sum_lg*sum_rr; }
        for(int c=1;;c++){
            int i=j-c,k=j+c;
            if(i<=0||k>n)break;
            if(s[i]!=s[j]&&s[i]!=s[k]&&s[k]!=s[j])ans--;
        }
    }
    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 3632
def erat(M):
    p = [1] * M
    p[0] = p[1] = 0
    for x in range(2, int((M - 1)**.5) + 1):
        if p[x]:
            for y in range(x*x, M, x):
                p[y] = 0
    return p
INF = 10**5 + 1
p = erat(INF)
q = [0] * INF
from itertools import*
for i in range(INF):
    q[i] = i%2 * p[i] * p[-~i//2]
*a, = accumulate([0] + q)
for _ in [None] * int(input()):
    l, r = map(int, input().split())
    print(a[-~r] - a[l])


Measured memory_bytes: 14604
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
const ll mod=1e9+7;
ll powmod(ll a,ll b) {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;}

vector<int>graph[200006];
bool isVisited[200006]={false};

int dp[200006];
map<int,int>m;
void dfs(int start,int val){
    isVisited[start]=true;
    dp[start]+=(val+m[start]);
    for(int i=0;i<graph[start].size();i++){
        if(!isVisited[graph[start][i]]){dfs(graph[start][i],val+m[start]);}
    }
    }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1;i<=q;i++){
        int y,x;
        cin>>y>>x;
        m[y]+=x;
    }
    for(int i=1;i<=n;i++){
        if(!isVisited[i])dfs(i,0);
    }
    for(int i=1;i<=n;i++){
        cout<<dp[i]<<" ";
    }
    return 0;
    }


Measured memory_bytes: 42496
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

using namespace std;

const long long INF = 1e18;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

struct node {
	ll a;
	int length;
	vector<int> children;
};

void solve(node* nodes, ll* lis, int current, int pre, int n) {
	ll t;
	auto p = lower_bound(lis, lis + n, nodes[current].a);
	t = *p;
	*p = nodes[current].a;
	nodes[current].length = lower_bound(lis, lis + n, INF - 1) - lis;

	rep(i, nodes[current].children.size()) {
		if (nodes[current].children[i] == pre) continue;

		solve(nodes, lis, nodes[current].children[i], current, n);
	}

	*p = t;
}

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

	int n;
	cin >> n;
	node* nodes = new node[n];
	rep(i, n) cin >> nodes[i].a;

	int u, v;
	rep(i, n - 1) {
		cin >> u >> v;
		nodes[u - 1].children.push_back(v - 1);
		nodes[v - 1].children.push_back(u - 1);
	}

	ll* lis = new ll[n+1];
	rep(i, n+1) lis[i] = INF;
	solve(nodes, lis, 0, -1, n);

	rep(i, n) {
		cout << nodes[i].length << "\n";
	}

	return 0;
}



Measured memory_bytes: 33528
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	int n;
	cin >> n;

	int div=0, count=0;
	for(int i=1;i<=n;i += 2) {
		div=0;
		for(int j=1;j<=i;j++) {
			if(i%j == 0) div++;
		}
		if(div == 8) count++;
	}

	cout << count << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define db cout<<"db: "
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)
pii mov[4]={{1,0},{-1,0},{0,1},{0,-1}};
int main()
{
    int n,i,j,t;
    boost;

    int r,c,k;
    cin>>r>>c>>k;

    pii s,f;
    cin>>s.F>>s.S>>f.F>>f.S;
    s.F--;s.S--;f.F--;f.S--;

    bool arr[r][c];
    clean(arr);
    rep(i,0,r)
    {
        string s;
        cin>>s;
        rep(j,0,c) if(s[j]=='@') arr[i][j]=1;
    }
    // bool vis[r][c];
    // clean(vis);
    int best[r][c];

    rep(i,0,r)
    {
        rep(j,0,c)best[i][j]=1e9;
    }
    priority_queue<pair<int,pii>> q;
    pair<int,pii> u;
    int x,y;
    q.push({0,s});
    // vis[s.F][s.S]=1;
    best[s.F][s.S]=0;
    

    while(!q.empty())
    {
        u=q.top();
        // cout<<u.F<<' '<<u.S<<'\n';
        q.pop();
        if(-u.F > best[u.S.F][u.S.S]) continue;
        for(auto &z:mov)
        {
            j=k;
            x=u.S.F;y=u.S.S;
            while(j--)
            {
                x+=z.F;y+=z.S;
                if(!(x>=0 and y>=0 and x<r and y<c and !arr[x][y] and best[x][y]>=1-u.F)) break;
                if(best[x][y]==1-u.F)continue;
                best[x][y]=1-u.F;
                q.push({-best[x][y],{x,y}});
            }
        }
    }
    // rep(i,0,r)
    // {
    //     rep(j,0,c)cout<<best[i][j]<<' ';
    //     cout<<'\n';
    // }
    if(best[f.F][f.S]==1e9) best[f.F][f.S]=-1;
    cout<<best[f.F][f.S];

    return 0;
}



Measured memory_bytes: 9728
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin>>n>>s;
    string res = "";
    int a = 0, b = 0;
    for (int i = 0; i < n;i++){
        res += s[i];
        if (s[i] == ')')
        {
            a++;
            if(a>b){
                res = '(' + res;
                b++;
            }
        }else{
            b++;
        }
    }
    for (int i = 0; i < b - a; i++)
    {
        res += ')';
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<vector>
#include<sstream>

using namespace std;

string str;

int main(void){
	string word;
	
	map<string,int> h;
	vector<string> v;
	
	getline(cin, str);
	stringstream ss;
	ss << str;
	while(ss >> word){
		h[word]++;
		v.push_back(word);
	}
	int mh = 0, ml = 0;
	int hi = 0, li = 0;
	for(int i = 0; i < v.size(); i++){
//		cout << h[v[i]] << endl;
		if(h[v[i]] > mh){
			mh = h[v[i]];
			hi = i;
		}
		if(v[i].size() > ml){
			ml = v[i].size();
			li = i;
		}
	}
	
	cout << v[hi] << " " << v[li] << endl;
	
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
int mod=1e9+7;
int min(int a,int b){
    return (a<b)?a:b;
}
int max(int a,int b){
    return (a>b)?a:b;
}
int fp(int a,int b){
    if(b==0) return 1;
    int x=fp(a,b/2);
    x=(x*x)%mod;
    if(b&1) x=(x*a)%mod;
    return x;
}


signed main() {
 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 char ch;
 cin>>ch;
 if('a'<=ch&&ch<='z')
 cout<<'a';
 else
 cout<<'A'; 


}

Measured memory_bytes: 3584
#!/usr/bin/env python3
import sys
import numpy as np
import collections


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    cc = collections.Counter(A)
    ans = sum(A)
    for i in range(1,Q+1):
        cb = cc[B[i-1]]
        cc[B[i-1]] = 0
        cc[C[i-1]] += cb
        ans -= cb * B[i-1]
        ans += cb * C[i-1]
        print(ans)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 47740
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
template<class T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int H,W,Ch,Cw,Dh,Dw;
string grid[1005];
int clr[1005][1006];
int visited[1005][1006];


int main() {
  cin >> H>>W>>Ch>>Cw>>Dh>>Dw;
  Ch--,Cw--,Dh--,Dw--;
  rep(i,H) cin >> grid[i];
  vvi cost(H, vi(W, INF));
  deque<ii> q;
  q.push_back({Ch,Cw});
  cost[Ch][Cw] = 0;
  while(q.size()) {
    auto[i,j] = q.front();
    q.pop_front();
    int dx[] = {0,1,0,-1};
    int dy[] = {1,0,-1,0};
    rep(k,4) {
      int ni = i + dy[k];
      int nj = j + dx[k];
      if (ni < 0 || ni >= H || nj < 0 || nj >= W || grid[ni][nj] == '#') continue;
      if (chmin(cost[ni][nj], cost[i][j])) q.push_front({ni, nj});
    }
    for (int dx = -2; dx<=2; dx++) {
      for (int dy = -2; dy<=2; dy++) {
        int ni = dy + i;
        int nj = dx + j;
        if (ni < 0 || ni >= H || nj < 0 || nj >= W || grid[ni][nj] == '#') continue;
        if (chmin(cost[ni][nj], 1+cost[i][j])) q.push_back({ni, nj});
      }
    }
  }
  int ans = cost[Dh][Dw];
  if (ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9452