akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
#define int long long
using namespace std;
const int mod = 1000000007;
int a[100006];
class BIT {
	public:
		int bit[100006];
		int N;

	void init(int n) {
		N = n;
		for(int i=0;i< n;i++)bit[i] = 0;
	}
	int sum(int i) {
		int s = 0;
		while (i > 0) {
			s += bit[i];
			i -= i&-i;
		}
		return s;
	}
	void add(int i, int x) {
		while (i <= N) {
			bit[i] += x;
			i += i&-i;
		}
	}
};

BIT bit;

signed main() {
	int n; cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	map<int, int>M1,M2;
	for (int i = 0; i < n; i++)M1[a[i]]++;
	int cnt = 1;
	for (auto itr = M1.begin(); itr != M1.end(); itr++) {
		M2[itr->first] = cnt;
		cnt++;
	}
	for (int i = 0; i < n; i++) {
		a[i] = M2[a[i]];
	}
	bit.init(n);
	int ans = 0;

	for (int i = 0; i < n; i++) {
		int S = bit.sum(a[i]-1);
		if (S == 0) {
			ans++;
			bit.add(a[i], 1);
		}
		else {
			int lb = 0, ub = a[i];
			while (ub - lb > 1) {
				int mi = (ub + lb) / 2;
				if (S == bit.sum(mi)) {
					ub = mi;
				}
				else lb = mi;
			}
//			cout << ub << endl;
			bit.add(ub, -1);
			bit.add(a[i], 1);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 14080
mem = []
for i in range(3):
    mem.append(list(input()))

mem = [[ord(y)-97 for y in x] for x in mem]

idx = 0
while 1:
    if len(mem[idx]) >= 1:
        idx = mem[idx].pop(0)
    else:
        break

print(chr(idx+97).upper())

Measured memory_bytes: 3064
# include <iostream>
# include <set>
# include <string>
# include <vector>


using namespace std;


int main() {
    set<string> substrings;

    string s; cin >> s;
    int    k; cin >> k;

    string substring;
    for (int _k=1; _k<=k; _k++) {
        for (int window_left=0; window_left < s.size()-_k+1; window_left++) {
            substring = s.substr(window_left, _k);
            substrings.insert(substring);
        }
    }

    vector<string> substrings_vector(substrings.begin(), substrings.end());
    sort(substrings_vector.begin(), substrings_vector.end());

    cout << substrings_vector[k-1] << endl;
    return 0;
}



Measured memory_bytes: 1536
N = int(input())
B = [int(i) for i in input().split()]
S = []
i = 0
while i < N:
  for j in range(len(B))[::-1]:
    if B[j] == j+1:
      S.append(j+1)
      B = B[:j] + B[j+1:]
      break
  i += 1
if B:
  print(-1)
else:
  for k in range(N)[::-1]:
    print(S[k])

Measured memory_bytes: 3064
#include <iostream>
#include <stack>
#include <string>

using namespace std;
typedef long long ll;

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

int main(void) {
  string s;
  char brackets[] = {'(', ')', '[', ']'};
  while (getline(cin, s) && s != ".") {
    stack<char> stk;
    bool yes = true;
    rep(i, s.size()) {
      bool is_bracket = false;
      rep(j, 4) if (s[i] == brackets[j]) is_bracket = true;
      if (!is_bracket)
        continue;
      if (stk.empty() || s[i] == '(' || s[i] == '[')
        stk.push(s[i]);
      else if ((stk.top() == '(' && s[i] == ')') ||
               (stk.top() == '[' && s[i] == ']'))
        stk.pop();
      else {
        yes = false;
        break;
      }
    }

    if (yes && stk.empty())
      cout << "yes" << endl;
    else
      cout << "no" << endl;
  }
}

Measured memory_bytes: 3124
import sys
input = sys.stdin.readline
def print_ans(N, ar):
    """Test Case
    >>> print_ans(3, ["apple", "orange", "apple"])
    2
    >>> print_ans(5,["grape" ,"grape" ,"grape" ,"grape" ,"grape"])
    1
    """
    print(len(set(ar)))
    

if __name__ == '__main__':
    N = int(input().rstrip())
    ar = [input().rstrip() for _ in range(N) ]
    print_ans(N, ar)




Measured memory_bytes: 35580
#include <stdio.h>

int main()
{
    // 4種類×13
    int cards[4][13];
    // 最初はすべてない
    for (int s = 0; s < 4; s++)
    {
        for (int r = 0; r < 13; r++)
        {
            cards[s][r] = 0;
        }
    }
    // 持ってるカードの枚数
    int n;
    scanf("%d", &n);
    // 持ってるカードを記録する
    for (int i = 0; i < n; i++)
    {
        char s;
        int r;
        scanf(" %c %d", &s, &r);
        if (s == 'S')
        {
            cards[0][r - 1] = 1;
        }
        if (s == 'H')
        {
            cards[1][r - 1] = 1;
        }
        if (s == 'C')
        {
            cards[2][r - 1] = 1;
        }
        if (s == 'D')
        {
            cards[3][r - 1] = 1;
        }
    }

    // 持ってないカードを出力
    for (int s = 0; s < 4; s++)
    {
        for (int r = 0; r < 13; r++)
        {
            if (cards[s][r] == 0)
            {
                char mark;
                if (s == 0)
                    mark = 'S';
                if (s == 1)
                    mark = 'H';
                if (s == 2)
                    mark = 'C';
                if (s == 3)
                    mark = 'D';
                printf("%c %d\n", mark, r + 1);
            }
        }
    }
    return 0;
}


Measured memory_bytes: 2732
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    ll ans = 0;
    FOR(i, 1, N) {
        ans += i;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> P;
typedef string str;
typedef vector<P> vp;
typedef vector<string> vs;
typedef vector<bool> vb;

const ll mod=1e9+7;
const ll inf=1e18;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define repr(i,m,n) for(ll i=m-1;i>=n;i--)
#define fi first
#define se second
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define eb(x) emplace_back(x)
#define pb(x) pop_back(x)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define sum(x) accumulate(all(x),0)
#define pc(x) __builtin_popcount(x)
#define gll greater<ll>()

void solve(){
 ll n,q;
  str s;
  cin >> n >> q >> s;
  
  vector<char> t(q),d(q);
  rep(i,0,q) cin >> t[i] >> d[i];
  
  
  ll l=0,r=n;
	repr(i,q,0){
		if(d[i] == 'R' && s[r-1] == t[i]) r--;
		if(d[i] == 'R' && s[l] == t[i]) l--;
		if(d[i] == 'L' && s[l+1] == t[i]) l++;
		if(d[i] == 'L' && s[r] == t[i]) r++;
	}
	cout << max(r-l-1,0ll) << endl;
  
  

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

Measured memory_bytes: 3948
s = input()
#a = [int(i) for i in input().split()]
#s = [[int(j) for j in input().split()] for i in range(N)]
tar=['A','C','G','T']
fs = [c in tar for c in s]
res = 0
cnt=0
for f in fs:
    if f:
        cnt+=1
        res=max(res,cnt)
    else:
        cnt=0
print(res)


Measured memory_bytes: 2940
import java.util.Scanner;
 
class Main
{
public static void main(String[] args)
{
Scanner stdIn=new Scanner(System.in);
int a=stdIn.nextInt();
int b=stdIn.nextInt();
int c=a*b;
int d=2*(a+b);
System.out.println(c+" "+d);
}
}

Measured memory_bytes: 25976
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

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

	vector<int> vi;
	map<int, long long> mi[51];

	int tmp1;
	int last = 0;
	for (int i = 0; i < N; i++) {
		dummy = scanf("%d", &tmp1);
		if (tmp1 - A != 0) {
			vi.push_back(tmp1 - A);
		} else {
			last++;
		}
	}

	N -= last;

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

	mi[0][0]++;

	for (int i = 1; i <= N; i++) {
		auto itr = mi[i - 1].begin();
		auto end = mi[i - 1].end();
		for (; itr != end; itr++) {
			mi[i][itr->first] += itr->second;
			if (itr->first + vi[i - 1] <= 0)
				mi[i][itr->first + vi[i - 1]] += itr->second;
		}
	}
	
	long long ans = mi[N][0];

	ans = ans << last;

	printf("%lld\n", ans - 1);
	
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>

int main()
{
  int a, b;

  scanf("%d %d", &a, &b);

  if(a > b)
    printf("a > b\n");

  if(a < b)
    printf("a < b\n");

  if(a == b)
    printf("a == b\n");

  return 0;
}

Measured memory_bytes: 1780
### メモ化による方法
n, w = map(int, input().split())
zaq = [tuple(map(int, input().split())) for _ in range(n)]
memo = [[-1] * n for _ in range(w+1)]

def dfs(i, w):
    if i == n:
        return 0
    elif memo[w][i] >= 0:
        return memo[w][i]
    elif w < zaq[i][1]:
        return dfs(i+1, w)
    else:
        res1 = dfs(i+1, w)
        res2 = dfs(i+1, w - zaq[i][1]) + zaq[i][0]
        res = max(res1, res2)
        memo[w][i] = res
        return res
print(dfs(i=0, w=w))


Measured memory_bytes: 24412
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "No" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int BE(int b,int e){
    int r=1;
    while(e){
        if(e&1){
            r=(r*b)%MOD;
        }
        b=(b*b)%MOD;
        e >>=1;
    }
    return r;
}


signed main(void){
    int N;
    int C[214514];
    cin >> N;
    REP(i,N){
        cin >> C[i];
    }
    sort(C,C+N,greater<>());
    int Ans=0;
    int e=BE(2,N-1);
    int inv2=BE(2,MOD-2);
    REP(i,N){
        int num;
        num = e*(i+2);num%=MOD;
        num*=inv2;num%=MOD;
        num*=C[i];num%=MOD;
        Ans+=num;Ans%=MOD;
        //cout << num << " ";
    }
    Ans*=2*e;Ans%=MOD;
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 1792
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(v):
    print(counter)
    for nv in g[v]:
        if nv in visited:
            continue
        visited.add(nv)
        counter[nv] += counter[v]
        dfs(nv)


def input():
    return sys.stdin.readline().strip()


N, Q = map(int, input().split())
g = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)
counter = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    counter[p] += x

stack = [0]
visited = {0}
while stack:
    v = stack.pop()
    for nv in g[v]:
        if nv in visited:
            continue
        stack.append(nv)
        visited.add(nv)
        counter[nv] += counter[v]
print(" ".join(map(str, counter)))


Measured memory_bytes: 99396
N = int(input())
S = input()

R, G, B = set(), set(), set()
r, g, b = 0, 0, 0

for i, s in enumerate(S):
    if s == "R":
        R.add(i + 1)
        r += 1

    elif s == "G":
        G.add(i + 1)
        g += 1

    else:
        B.add(i + 1)
        b += 1

ans = r * g * b
punish = 0


for rr in R:
    for gg in G:
        if (min(rr, gg) - abs(rr - gg)) in B:
            punish += 1

        if (max(rr, gg) + abs(rr - gg)) in B:
            punish += 1
      
        if (abs(rr - gg) % 2 == 0) and (abs(rr - gg)//2 + min(rr, gg) in B):
            punish += 1
      

print(ans - punish)

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


bool check(string a,string b,int d){
  if(a.size()<b.size())swap(a,b);
  if(a==b) return 1;
  int A = a.size(),B=b.size();
  if(d==0||A-B>d)return 0;


  //erase
  for(int i=0;i<A;i++){
    char ch = a[i];
    a.erase(a.begin()+i);
    if(check(a,b,d-1))return 1;
    a.insert(a.begin()+i,ch);
  }

  if(A!=B) return 0;

  //change
  int cnt=0;
  for(int i=0;i<A;i++) cnt+=a[i]!=b[i];
  if(cnt<=d)return 1;
  if(cnt>4) return 0;
  

  //swap
  for(int i=0;i<A-1;i++){
    if(a[i]==a[i+1]||a[i+1]!=b[i]||a[i]!=b[i+1])continue;
    swap(a[i],a[i+1]);
    if(check(a,b,d-1))return 1;
    swap(a[i],a[i+1]);
  }
  return 0;
}

int main(){
  int n,d;
  while(cin>>n,n){
    cin>>d;
    string str[201];
    for(int i=0;i<n;i++)cin>>str[i];
    sort(str,str+n);

    int cnt=0;    
    for(int i=0;i<n;i++)
      for(int j=i+1;j<n;j++)
	if(check(str[i],str[j],d)) cout<<str[i]<<","<<str[j]<<endl,cnt++;
    cout<<cnt<<endl;
  }
  return 0;
}

Measured memory_bytes: 3204
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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 <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Edge=pair<int,int>;
using Graph=vector<vector<int>>;
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();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll N;
  cin>>N;
  ll A[N],T=0;
  REP(i,N){
    cin>>A[i];
    T^=A[i];
  }
  
  REP(i,N){
    ll P=A[i]^T;
    cout<<P<<" ";
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 5116
N = int(input())
 
def num_divisors_table(n):
    table = [0] * (n + 1)
    
    ans = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            ans += j
    
    return ans

print(num_divisors_table(N))

Measured memory_bytes: 145732
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def lcm(n, m):
    return n * m // gcd(n, m)

L = A[0]
for a in A:
    L = lcm(L, a)

ans = 0
for a in A:
    ans += L // a

print(ans % MOD)


Measured memory_bytes: 4084
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int cnt = 0;
  rep(i,n-2){
    if(s.substr(i,3) == "ABC") cnt++;
  }
  printf("%d\n", cnt);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

int main()
{
	ll a,b;
	scanf("%lld%lld",&a,&b);
	if (a==b+1 || a==b || a==b-1) puts("Brown");
	else puts("Alice");
	return 0;
}


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

int main() {
    int n;

    cin >> n;
    n %= 10;

    if (n == 3) {
        cout << "bon" << endl;
    }
    else if (n == 0 || n == 1 || n == 6 || n == 8) {
        cout << "pon" << endl;
    }
    else {
        cout << "hon" << endl;
    }

    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <math.h>
using namespace std;


int main(){
	int N;
	cin >> N;
	int gusu=0;
	int input;
	for(int i=0;i<N;i++){
		cin >> input;
		if(input % 2 == 0){
			gusu++;
		}
	}
	
	
	cout << pow(3,N) - pow(2,gusu) << endl;
	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000000LL;
#define all(x) (x).begin(),(x).end()

vector<pll> prime_factorize(ll N) {
    vector<pll> res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}
const int MAX = 210000;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
  ll n, m;
  COMinit();
  cin >> n >> m;
  vector<pll> vc = prime_factorize(m);
  ll ans = 1;
  for(int i=0; i<vc.size(); i++){
    ll num = COM(vc[i].second + n - 1, n-1);
    //cout << "num:" << num << " vc[i]:" << vc[i].first << " " << vc[i].second << ln;
    ans = (ans * num)% MOD;
  }
  cout << ans % MOD << ln;
}

Measured memory_bytes: 5120
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const (
	INFTY = 1 << 21
	NIL   = -1
)

const (
	WHITE = iota
	GRAY
	BLACK
)

type Graph [][]int

func (g *Graph) dikstra(n int) string {
	var (
		u, minv = 0, 0
	)

	d := make([]int, n)
	color := make([]int, n)

	for i := 0; i < n; i++ {
		d[i] = INFTY
		color[i] = WHITE
	}
	d[0] = 0
	color[0] = GRAY

	for {
		minv = INFTY
		u = -1
		for i := 0; i < n; i++ {
			if minv > d[i] && color[i] != BLACK {
				u = i
				minv = d[i]
			}
		}

		if u == -1 {
			break
		}

		color[u] = BLACK
		for v := 0; v < n; v++ {
			if color[v] != BLACK && (*g)[u][v] != INFTY {
				if d[v] > d[u]+(*g)[u][v] {
					d[v] = d[u] + (*g)[u][v]
					color[v] = GRAY
				}
			}
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		out.WriteString(fmt.Sprintf("%d ", i))
		if d[i] == INFTY {
			out.WriteString(fmt.Sprintf("%d\n", -1))
			continue
		}
		out.WriteString(fmt.Sprintf("%d\n", d[i]))
	}

	return strings.TrimRight(out.String(), "\n")
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	g := make(Graph, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = INFTY
		}
	}

	for i := 0; i < n; i++ {
		sc.Scan()
		u, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())

		for j := 0; j < k; j++ {
			sc.Scan()
			v, _ := strconv.Atoi(sc.Text())
			sc.Scan()
			c, _ := strconv.Atoi(sc.Text())

			g[u][v] = c
		}
	}

	return g.dikstra(n)
}

func main() {
	fmt.Println(answer(os.Stdin))
}



Measured memory_bytes: 1284
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL = 1LL<<40;
const double PI = atan(1)*4;
//const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

struct UnionFind {
    // UnionFind u(n) 宣言
    // u.unionSet(x,y) 併合
    // u.findSet(x,y) -> {true, false}
    // u.root(x) xのroot. data[x]を参照。併合前はxそのもの、併合後は同一union
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

int main() {
    int n,m;cin>>n>>m;
    vector<int>p(n);cin>>p;
    vector<pii> z(m);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;b--;
        z[i].first = a;
        z[i].second=b;
    }
    
    UnionFind u(n);
    
    for(auto q:z){
        u.unionSet(q.first,q.second);
    }
    
    int c = 0;
    
    rep(i,n){
        c += (u.findSet(i,p[i]-1));
    }
    
    cout<<c<<endl;
    
    
    return 0;
}


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

const int INF = 1e9;

main() {
  string s; cin >> s;

  int opt{}, cur{};
  vector<int> dp(1 << 26, INF);
  dp[0] = 0;
  for (auto&& c : s) {
    cur ^= 1 << (c - 'a');
    opt = dp[cur];
    for (int i = 0; i < 26; i++) opt = min(opt, dp[cur ^ (1 << i)]);
    dp[cur] = min(dp[cur], ++opt);
  }
  cout << opt << endl;
}


Measured memory_bytes: 262660
#include<iostream>
#include<vector>
#include<math.h>
#include<bits/stdc++.h>
#define lli long long int
#define mod 1000000007
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); 
    cout.tie(NULL);
  	int a[32]={1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51},n;
  	cin>>n;
  	cout<<a[n-1];
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define in(x, l, r) (ll)(l) <= (x) && (x) < (ll)(r)

int main() {
    int N;
    cin >> N;
    int maxlen = 0;
    int tmplen = 0;
    rep(i,0,N) {
        int D1, D2;
        cin >> D1 >> D2;
        if (D1 == D2) {
            tmplen++;
            maxlen = max(maxlen, tmplen);
        } else {
            tmplen = 0;
        }
    }
    if (maxlen >= 3) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

void solve(long long N, std::vector<std::string> S, std::vector<long long> P) {
  vector< pair<string, pair<int,int>>> a;
  for(int i = 0 ; i < N ; i++){
    a.push_back({S[i], {-P[i], i}});
  }
  sort(a.begin(), a.end());
  for( auto i : a ){
    cout << i.second.second + 1 << endl;
  }
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<std::string> S(N);
  std::vector<long long> P(N);
  for (int i = 0; i < N; i++) {
    std::cin >> S[i];
    scanf("%lld", &P[i]);
  }
  solve(N, std::move(S), std::move(P));
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p (int)(1e6 + 3)

int MOD(int a){
	a %= p;
	return a >= 0 ? a : a + p;
}

int power(int a, int N){
	if(N == 0){
		return 1;
	}
	else if(N % 2 == 0){
		return power(MOD(a * a), N / 2);
	}
	else{
		return MOD(a * power(a, N - 1));
	}
}

int inverse(int a){
	return power(MOD(a), p - 2);
}

int *fact;

int facto(int n){
	if(n >= p){
		return 0;
	}
	else{
		return fact[n];
	}
}

signed main(){
	int Q, q, i;
	fact = (int *)malloc(sizeof(int) * (p + 1));
	fact[0] = 1;
	for(i = 1; i <= p; i++){
		fact[i] = MOD(i * fact[i - 1]);
	}
	scanf("%lld", &Q);
	for(q = 0; q < Q; q++){
		int x, d, n;
		scanf("%lld%lld%lld", &x, &d, &n);
		if(d == 0){
			printf("%lld\n", power(x, n));
			continue;
		}
		if(x == 0){
			printf("0\n");
			continue;
		}
		if((p - x) % d == 0){
			i = (p - x) / d;
			if(i < n){
				printf("0\n");
				continue;
			}
		}
		i = MOD(x * inverse(d));
		int ans = MOD(facto(i + n - 1) * power(d, i + n - 1));
		ans = MOD(ans * inverse(facto(i - 1) * power(d, i - 1)));
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 8704
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        boolean isPossible = false;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i*m + j*n - 2*i*j == k){
                    isPossible = true;
                    break;
                }
            }
            if (isPossible)break;
        }

        System.out.println(isPossible?"Yes":"No");
    }
}


Measured memory_bytes: 25044
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<long long int>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vvl vector<vector<ll> >
#define vvi vector<vector<int> >
#define pl pair<ll,ll>
#define pb push_back
#define PI 3.14159265
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fri(s,n) for(int i=s;i<n;i++)
#define frj(s,n) for(int j=s;j<n;j++)
#define T(i) int i=1;cin>>i;while(i--)
#define vsi vector<set<int> >
#define pii pair<int,int>
#define inf 1e9
#define vpii vector<pair<int,int> >


ll power(ll a,ll b){
    if(b==0)
        return 1;
    if(b&1)
        return a*power(a,b-1);
    ll temp=power(a,b/2);
    return temp*temp;
    }
ll mycompare(ll a,ll b){
    return a>b;
    }
int n;
double max_prob(int c,int heads,vector<double> &p,vector<vector<double> > &dp){
    if(c==0 && heads<=n/2)
        return 0;
    if(c==0)
        return 1;
    if(dp[c][heads]!=-1)
        return dp[c][heads];
    return dp[c][heads]=p[c]*max_prob(c-1,heads+1,p,dp)+(1-p[c])*max_prob(c-1,heads,p,dp);
    }
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    fast;
    cin>>n;
    vector<double> p(n+1);
    fri(1,n+1)
        cin>>p[i];
    vector<vector<double> > dp(n+1,vector<double>(n+1,-1));
    cout<<setprecision(9)<<max_prob(n,0,p,dp);
    }


Measured memory_bytes: 74040
N = int(input())
S1 = input()
S2 = input()

ans = 3
left = None
j = 0
while j < N:
    if S1[j] == S2[j]:
        if left == 'V':
            ans *= 2

        left = 'V'
        j += 1
    else:
        if left == 'H':
            ans *= 3
        else:
            ans *= 2
        left = 'H'
        j += 2

print(ans % 1000000007)


Measured memory_bytes: 3060
// Course＞Introduction to Programming I ＞ ITP1_1_C:   Rectangle
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_C&lang=jp

// 以下のソースコードには(複数の？)誤りがあるので、このまま提出しても「誤り」と判定されます。
// ソースコード中の誤りを修正し、「正解」（Accepted）を出してください。

// 適宜、paiza.io (https://paiza.io/ja/projects/new) などのC++実行環境を、確認に用いることを推奨します。


#include <iostream>
using namespace std;

int main(){
	int a,b;
	cin >> a >> b;
	cout << (a*b) << " "<< (a+b)*2 << endl;
	return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <functional>
#include <list>
#include <iomanip>
#include <cctype>
#include <math.h>
#include <utility>
#include <numeric>

#define REP(i,first,end) for(int i = first; i < end; i++)
#define rep(i,end) for(int i = 0; i < end; i++)

typedef long long ll;
#define mod =1000000007;

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int n;
    cin >> n;
    
    
    vector<double> v(n);
    
    rep(i,n){
        cin >> v[i];
    }
    
    sort(v.begin(),v.end());
    
    rep(j,n-1){
        v[j+1] = double((v[j]+v[j+1])/2);
    }
    
    cout << (double)v[n-1] << endl;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {
   /* #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif*/
        /* 
        Ofcourse it's Hard.
        It's supposed to be Hard.
        If it's easy everyone would do it.
        HARD IS WHAT MAKES IT GREAT

        YESTERDAY U SAID TOMORROW

        SLOWLY BECOMING THE PERSON I 
        SHOULD HAVE BEEN A LONG TIME AGO

        SAME TASK CAN'T BE FOUND DIFFICULT TWICE

        BTBHWSITW

        SPRH TU KAB P

        CP IS ALL ABOUT THINKING 
        YOU HAVE MUCH MORE POTENTIAL THAN U THINK

        AJIT SHIDDAT 10

        UR DAILY ROUTINE 


        */

fast();
//ll t;cin>>t;while(t--)
{
    ll a,b;
    cin>>a>>b;
    if(a>=13)
        cout<<b<<endl;
    else if(a>=6)
        cout<<(b/2)<<endl;
    else
        cout<<0<<endl;
    
}
return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    void solve(Scanner sc, PrintWriter pw) {
        int N = sc.nextInt();
        long total = 0;
        int currentMax = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            int val = sc.nextInt();
            int nextMax = Math.max(currentMax, val);
            if (i > 0) {
                total += nextMax - val;
            }
            currentMax = nextMax;
        }
        pw.println(total);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        new Main().solve(sc, pw);
        pw.flush();
        pw.close();
        sc.close();
    }
}


Measured memory_bytes: 57788
def compute():
    from sys import stdin
    N, M = map(int, stdin.readline().split())
    ipt = sorted(
            [tuple(map(int, stdin.readline().split())) for _ in range(N)],
            key=lambda x: (-x[0], x[1])
          )

    out = 0
    while (M>0) and (len(ipt)>0):
      a, b = ipt.pop()
      b = min(b,M)
      out += a*b
      M -= b

    print(out)


if __name__ == "__main__":
    compute()


Measured memory_bytes: 60764
#include <iostream>
//#include <iomanip>
#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <bitset>
//#include <math.h>
using namespace std ;
//using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	int a,b,c,d ; a = b = c = d = 0 ;
	for(int i=0;i<6;i++){
		int x ; cin >> x ;
		if(x==1) a++ ;
		else if(x==2) b++ ;
		else if(x==3) c++ ;
		else d++ ;
	}
	cout << YorN(a!=3&&b!=3&&c!=3&&d!=3) << endl ;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int n;
  scanf("%d",&n);
  int v[n];
  int ans=0;
  int min = 200000;
  for(int i=0;i<n;i++){
    scanf("%d",&v[i]);
    if(v[i] <= min){
      ans++;
      min = v[i];
    }
  }
  printf("%d",ans);
}

Measured memory_bytes: 896
import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        long sum = 0;
        for(int i = N - 1; i > 0; i--){
            sum += i;
        }
        
        System.out.println(sum);
    }
}


Measured memory_bytes: 21972
#include<stdio.h>

int convert_plus(int x){
  if(x<0)
    x *= -1;
  return x;
}

int main(void){
  int N,L;
  int i;
  int sum = 0 , taste_sum = 0 , best_close = 0;
  
  scanf("%d %d",&N ,&L);

  int taste[N];

  for(i=1 ; i<=N ; i++){
    taste[i-1] = L+i-1;
    sum += taste[i-1];
  }
  
  for(i=1 ; i<=N ; i++){
    taste_sum = sum-taste[i-1];    
    if(sum-taste_sum < convert_plus(sum-best_close)){
      best_close = taste_sum;
    }
  }
  
  printf("%d\n",best_close);
  
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main()
{
  int n;
  cin>>n;
  string s;
  cin>>s;
  int i=0;
  int count=0;
  while (i<n)
  {
    int k=1,j=i+1;
    while(j<n && s[i]==s[j])
    {
      k++;
      j++;
    }
    i+=k;
    count++;
  }
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) { //Passes samples, but WA
		Scanner input = new Scanner(System.in);
		int N = input.nextInt();
		double[][] dp = new double[N+1][N+1];
		double[] p = new double[N+1];
		double answer = 0.0;
		double bug = 1.0; //keep track of tails' product
		for (int i = 1; i <= N; i++) {
			p[i] = input.nextDouble();
		}
		dp[1][1] = p[1];
		bug=1.0-p[1];
		for (int i = 2; i <= N; i++) { //Filling diagonals of DP table
			dp[i][i] = dp[i-1][i-1]*p[i];
		}
		for (int j = 2; j <= N; j++) { //Filling 1st row of DP table
			dp[1][j] = dp[1][j-1]*(1.0-p[j])+p[j]*(bug);
			bug*=(1.0-p[j]);
		}
		for (int i = 2; i < N; i++) { //dp[N][N] is already filled, last row not necessary
			for (int j = i+1; j <= N; j++) {
				dp[i][j]=dp[i][j-1]*(1.0-p[j])+dp[i-1][j-1]*p[j]; 
			}
		}
		for (int i = N/2+1; i <= N; i++) {
			answer+=dp[i][N];
		}
		System.out.println(answer);
	}
}

Measured memory_bytes: 134784
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll N=2*1e6+100;
#define M 1000000007
ll fac[N+1];
ll fast(ll n,ll a,ll m)
{
    if(n==0)
      return 1;
    else if(n==1)
        return a;
    else
    {
        ll res=fast(n/2,a,m);
        res=((res%m)*(res%m))%m;
        if(n%2==0)
            return res;
        else
            return (((res%m)*(a%m))%m);
    }
}
ll nCr(ll n,ll r)
{
    ll p=fac[n];
    ll u=fast(1e9+5,fac[n-r],1e9+7);
    ll v=fast(1e9+5,fac[r],1e9+7);
    p=((p%M)*(u%M))%M;
    p=((p%M)*(v%M))%M;
    return p;
}
ll func(ll i,ll c1,ll c2)
{
    ll A,B;
    A=nCr(c2+i+2,i+1);
    B=nCr(c1+i+1,i+1);
    A-=B;
    if(A<0)
    {
        A+=M;
        A%=M;
    }
    return A;

}
int main()
{
    ll r1,r2,c1,c2;
    cin>>r1>>c1>>r2>>c2;
    ll i,j;
    fac[0]=1;
    for(i=1;i<=r2+c2+10;i++)
    {
        fac[i]=(fac[i-1]*i)%M;
    }
    ll ans=func(r2,c1,c2)-func(r1-1,c1,c2);
    if(ans<0)
    {
        ans+=M;
        ans%=M;
    }
    cout<<ans;



}



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

typedef long long int int64;
int64 n,m;
int main()
{
	scanf("%lld%lld",&n,&m);
	if(m == 0) {
		printf("%lld\n",n*n);
		return 0;
	}
	int64 ans = 0;
	for(int64 b = m + 1;b <= n;++b) {
		ans += (n + 1) / b * (b - m) + std::max(0LL,(n + 1) % b - m);
	}
	printf("%lld\n",ans);
}


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


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
class A
{
    static Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
    static Dictionary<string, int> edgeColor = new Dictionary<string, int>();
    static bool[] visited;
    static Queue<int> q = new Queue<int>();
    static int[] color;
    static int[] parentColor;
    public static void BFS(int node)
    {
        q.Enqueue(node);
        visited[node] = true;
        color[node] = -1;
        parentColor[node] = -1;
        while (q.Count > 0)
        {
            var poppedUpNode = q.Dequeue();
            if (graph.ContainsKey(poppedUpNode))
            {
                int colorToChild = 1;
                int colorCantbeused = color[poppedUpNode];
                
                foreach (var e in graph[poppedUpNode])
                {
                    
                    if (!visited[e])
                    {
                        if (colorCantbeused == colorToChild)
                            colorToChild++;
                        color[e] = colorToChild++;
                        edgeColor.Add($"{poppedUpNode}-{e}", color[e]);
                        edgeColor.Add($"{e}-{poppedUpNode}", color[e]);
                        q.Enqueue(e);
                        visited[e] = true;
                    }
                }
            }
        }

    }
    public static void Main(string[] args)
    {
        int t = 1;
        while (t > 0)
        {
            int n = int.Parse(Console.ReadLine());
            visited = new bool[n + 1];
            color = new int[n + 1];
            parentColor = new int[n + 1];
            List<string> edges = new List<string>();
            for(int i = 1; i < n; i++)
            {
                var arr = Console.ReadLine().Trim().Split().Select(x => int.Parse(x)).ToArray();
                if (!graph.ContainsKey(arr[0]))
                    graph.Add(arr[0], new List<int>());
                if (!graph.ContainsKey(arr[1]))
                    graph.Add(arr[1], new List<int>());
                graph[arr[0]].Add(arr[1]);
                graph[arr[1]].Add(arr[0]);
                edges.Add($"{arr[0]}-{arr[1]}");
            }
            BFS(1);
            int max = -1;
            for (int i = 2; i <= n; i++)
            {
                max = Math.Max(max,color[i]);
            }
            Console.WriteLine(max);
            foreach(var e in edges)
            {
                Console.WriteLine(edgeColor[e]);
            }
            t--;
        }
    }
   
}

Measured memory_bytes: 60496
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
    bool done_something = false;
    stringstream res;
    res << "[";
    for (; begin_iter != end_iter and counter; ++begin_iter) {
        done_something = true;
        counter--;
        res << *begin_iter << ", ";
    }
    string str = res.str();
    if (done_something) {
        str.pop_back();
        str.pop_back();
    }
    str += "]";
    return str;
}

vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
    vector<int> ord(size);
    for (int i = 0; i < size; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), compare);
    return ord;
}

template <typename T>
bool MinPlace(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool MaxPlace(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <typename Container>
int SZ(const Container& S) { return S.size(); }

template <typename S, typename T>
ostream& operator <<(ostream& out, const pair<S, T>& p) {
    out << "{" << p.first << ", " << p.second << "}";
    return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v) {
    out << "[";
    for (int i = 0; i < (int)v.size(); i++) {
        out << v[i];
        if (i != (int)v.size()-1) out << ", ";
    }
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file

    #define dbg_var(x) clog << #x  << ": " << x << endl;
    #define dbg_array(x, len) clog << #x << ": " << print_iterable(x, x+len, -1) << endl;
#else
    #define dbg_var(x)
    #define dbg_array(x, len)
#endif

///////////////////////////////////////////////////////////////////////////
//////////////////// DO NOT TOUCH BEFORE THIS LINE ////////////////////////
///////////////////////////////////////////////////////////////////////////

const int MAXN = 3000;
int dinX[MAXN], dinY[MAXN], a[MAXN]; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Remove in problems with online queries!

    int N, Z, W;
    cin >> N >> Z >> a[0];
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    N++;
    for (int t = N-2; t >= 0; t--) {
        dinX[t] = abs(a[t]-a[N-1]);
        dinY[t] = abs(a[t]-a[N-1]);
        for (int i = t+1; i < N-1; i++) {
            dinX[t] = max(dinX[t], dinY[i]);
            dinY[t] = min(dinX[t], dinX[i]);
        }
    }
    cout << dinX[0] << "\n";
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ull unchaed long long
#define ll long long
#define il inline
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define rep0(i, n) for(int i = 0; i < (n); i ++)
#define per0(i, n) for(int i = (n) - 1; i >= 0; i --)
#define ept 1e-9
#define INF 0x3f3f3f3f
#define sz(x) (x).size()
#define Axx(x) (x).begin(), (x).cntd()
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
using namespace std;
const int mod = 998244353;
const int N = 3010;

int a, b, c, d, dp[N], ndp[N];


int main()
{
	a = read();
	b = read();
	c = read();
	d = read();
	
	dp[b] = 1;
	rep(i, a, c - 1)
	{
		memset(ndp, 0, sizeof(ndp));
		int sum = 0;
		rep(j, b, d)
		{
			sum = 1ll * sum * i % mod;
			ndp[j] = (1ll * dp[j] * j + sum) % mod;
			sum += dp[j];
			sum %= mod;
		}
		memcpy(dp, ndp, sizeof(dp));
	} 
	
	int ans = 0;
	rep(i, b, d) ans = (1ll * ans * c + dp[i]) % mod;
	cout << ans;
	return 0;
}


Measured memory_bytes: 3636
//ΔAGC033C
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 222222;
int n,d[N];
vector<int> v[N];
void dfs(int u,int fa){
	int i;
	d[u]=d[fa]+1;
	for(i=v[u].size();i--;){
		if(v[u][i]==fa)
			continue;
		dfs(v[u][i],u);
	}
}
int main()
{
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<n;i=i+1){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	x=0;
	for(i=1;i<=n;i=i+1)
		if(d[i]>d[x])
			x=i;
	dfs(x,0);
	x=0;
	for(i=1;i<=n;i=i+1)
		if(d[i]>x)
			x=d[i];
	if(x%3==2)
		cout<<"Second";
	else
		cout<<"First";
	return 0;
}

Measured memory_bytes: 21888
#include <iostream>
#include <cmath>
using namespace std;
//解説参考　Test
inline long long f(long long b, long long n) {
	long long Ans = 0;
	if (n < b) return n;
	else { return f(b, n / b) + n%b; }
}

int main() {
	long long n, s; cin >> n >> s;
	if (n == s) { cout << n + 1 << endl; return 0; }
	long long Sq = sqrt(n);
	for (long long i = 2; i < Sq;i++) {
		if (s == f(i, n)) { cout << i << endl; return 0; }
	}
	long long b;
	for (long long i = Sq; i > 0;i--) {
		b = (n - s) / i + 1;
		if (b >= 2) {
			if (s == f(b, n)) { cout << b << endl; return 0; }
		}
	}
	cout << -1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int cnt;
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='g')cnt++;
	}
	cout<<(cnt-(s.size()-cnt))/2;
	return 0;
}

Measured memory_bytes: 3772
N, M = map(int, input().split())
A = list(map(int, input().split()))

M={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
M={a:M[a] for a in A}

dp=[]
for i in range(N+1):
  if i==0:
    dp.append(0)
  else:
    tmp=[dp[i-m] for m in M.values() if i-m>=0]
    if tmp==[]:
      dp.append(-float('inf'))
    else:
      dp.append(max(tmp)+1)
      
Ml=list(M.keys())
Ml.sort(reverse=True)
tmp=''
while 1:
  for ml in Ml:
    if N-M[ml]>=0 and dp[N-M[ml]]==dp[N]-1:
        tmp+=str(ml)
        N-=M[ml]
        break
  if N==0:
    break
    
print(tmp)

Measured memory_bytes: 3316