akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cassert>

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

std::vector<int> edges[505];
int dist[505][505];
bool visit[505];
int c[505];
void color(int on) {
	visit[on] = true;
	for(auto to : edges[on]) {
		if(!visit[to]) {
			c[to] = 1 ^ c[on];
			color(to);
		} else if(c[to] == c[on]) {
			std::cout << "-1\n";
			exit(0);
		}
	}
}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n;
	std::cin >> n;
	const int INF = 1e9;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			char ch;
			std::cin >> ch;
			if(ch == '1') {
				edges[i].push_back(j);
				dist[i][j] = 1;
			} else {
				dist[i][j] = INF;
			}
		}
		dist[i][i] = 0;
	}
	color(0);
	for(int i = 0; i < n; i++) {
		assert(visit[i]);
	}
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			//if(dist[i][j] % 2 == 0) continue;
			ans = std::max(ans, dist[i][j] + 1);
		}
	}
	assert(ans <= n);
	//std::cout << "YES\n" << ans << '\n';
	std::cout << ans << '\n';
}

Measured memory_bytes: 896
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // int n = sc.nextInt();
        String str = sc.next();
        if(str.equals("ABC")) {
            System.out.println("ARC");
        } else {
            System.out.println("ABC");
        }
    }
}

Measured memory_bytes: 35620
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.ArrayDeque

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
//    幅優先
//    e * e
    val (n, x, y) = readIntegerList()

    /** graph[fromNodeIndex]: edges to other node */
    val edges = Array(n) { mutableListOf<Edge>() }
    repeat(n - 1) {
        edges[it].add(Edge(it, it + 1, 1))
        edges[it + 1].add(Edge(it + 1, it, 1))
    }
    edges[x - 1].add(Edge(x - 1, y - 1, 1))
    edges[y - 1].add(Edge(y - 1, x - 1, 1))

    var ans = LongArray(n - 1)
    for (i in 0 until n) {
        val costArray = IntArray(edges.size)
        val isUnchecked = BooleanArray(edges.size) { true }
        val nodeQueue = ArrayDeque<Int>()
        nodeQueue.addLast(i)
        isUnchecked[i] = false
        while (nodeQueue.isNotEmpty()) {
            val node = nodeQueue.removeFirst()
            for (edge in edges[node]) {
                if (isUnchecked[edge.to]) {
                    costArray[edge.to] = costArray[node] + 1
                    ans[costArray[edge.to] - 1]++
                    isUnchecked[edge.to] = false
                    nodeQueue.addLast(edge.to)
                }
            }
        }
    }
    out.println(ans.map{ it / 2}.joinToString("\n"))
}

/** edge info */
data class Edge(val from: Int, val to: Int, val cost: Long)

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 56548
import * as fs from 'fs';

namespace AtCoder {
    export interface Paramable {
        readonly args: string[][];
    }

    export interface Task {
        main(this: Task): void;
    }
}

namespace AtCoder.abc001 {
    export class TaskA implements AtCoder.Task, AtCoder.Paramable {
        public constructor(public readonly args: string[][]) {
        }

        public main(this: TaskA): void {
            const nn: string = this.args[0][0];

            const n: number = +nn.slice(-1);
            if (n === 2 || n === 4 || n === 5 || n === 7 || n === 9) {
                console.log('hon');
            } else if (n === 0 || n === 1 || n === 6 || n === 8) {
                console.log('pon');
            } else if (n === 3) {
                console.log('bon');
            }

        }
    }

    const args: string[][] = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n').map(r => r.split(' '));
    const task: AtCoder.Task = new TaskA(args);
    task.main();
}



Measured memory_bytes: 29628
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>
#include <cassert>

using namespace std;
typedef long long ll;

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

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll N,K;
  cin>>N>>K;
  vector<ll>A(N);
  REP(i,N){
    cin>>A[i];
    A[i]--;
  }
  vector<ll>last(N,-1);
  last[0]=0;
  ll now=0;
  ll nokori=K;
  ll cnt=0;
  while(true){
    nokori--;cnt++;
    ll next=A[now];
    if(last[next]==-1){
      last[next]=cnt;
      now=next;
    }else{
      ll loop=cnt-last[next];
      now=next;
      nokori%=loop;
      break;
    }
    if(nokori==0)break;
  }
  REP(i,nokori){
    ll next=A[now];
    now=next;
  }

  cout<<now+1<<endl;
}


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

#define MOD 1000000007

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

  if (k >= n) {
    cout << 0 << endl;
    return 0;
  }

  vi h(n);
  rep(i, n) {
    cin >> h[i];
  }

  sort(h.begin(), h.end(), greater<int>());

  ll remain_h = 0;
  rep_s(i, k, n) {
    remain_h += h[i];
  }

  cout << remain_h << endl;
}


Measured memory_bytes: 1024
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val m = sc.nextInt()
    val a = (0 until m).map { sc.next().toInt() }
    println(problem163b(n, m, a))
}

fun problem163b(n: Int, m: Int, a: List<Int>): Int {
    var sum = 0
    for (i in 0 until m) {
        val ai = a[i]
        sum += ai
    }
    return if (n - sum < 0) -1 else n - sum
}

Measured memory_bytes: 44124
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

bool ok(string S) {
	REP(i,S.size()) if (S[i] < 'a' || S[i] > 'z') return false;
	return true;
}

int main() {

	string S,T; cin >> S >> T;
	vector < string > ans;

	REP(i,S.size() - T.size() + 1) {
		string St = S;
		for (int j = i; j < i + T.size(); j++) {
			if (St[j] == '?') {
				St[j] = T[j - i];
			} else if ( St[j] != T[j - i]) goto nxt;
		}
		REP(j,St.size()) if (St[j] == '?') St[j] = 'a';
		if (ok(St)) ans.push_back(St);
		nxt:;
	}

	if (ans.size() == 0) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}

	sort(ans.begin(), ans.end());
	cout << ans[0] << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long int
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define ff first
#define ss second
#define BASE 1000000000
#define ss second
int main() {
    string s;
    cin>>s;
    ll c=0;
    ll n = s.length();
    REP(i, n/2) {
        if(s[i] != s[n-1-i]) c++;
    }
    cout<<c;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))
dic = {}

for i in range (n):
    dic[i] = l[i] #{生徒番号: 何人いたか}

dic_sorted = sorted(dic.items(),key=lambda x: x[1])

for i in range (n):
    print(dic_sorted[i][0]+1,end=" ")


Measured memory_bytes: 25576
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
const ll MOD=1e9+7;
struct mat{ll _[3][3];ll* operator [](int s){return _[s];}};
mat operator * (mat a,mat b)
{
	mat g;
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
		{
			ll&r=g[i][j]; r=0;
			for(int k=0;k<3;++k) r+=a[i][k]*b[k][j];
			r%=MOD;
		}
	return g;
}
mat I()
{
	mat s;
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			s[i][j]=(i==j);
	return s;
}
int n,m,x[SZ];
mat b,h,d,r=I();
mat qp(mat a,ll b)
{
	mat x=I();
	while(b)
	{
		if(b&1) x=x*a;
		a=a*a; b>>=1;
	}
	return x;
}
int main()
{
	b[0][1]=2; b[1][2]=b[2][2]=
	b[0][0]=b[1][1]=b[0][2]=d[2][0]=1;
	h[0][0]=h[1][1]=h[2][2]=h[2][0]=1;
	h=b*h;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d",x+i);
	for(int i=1;i<=m;++i)
		r=r*qp(h,x[i]-x[i-1]-1)*b;
	r=r*qp(h,n-x[m]);
	printf("%d\n",(int)r[0][2]);
}


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

using ll = long long;

const int MAX_N = 100006;
int N, K;
int H[MAX_N];

void solve()
{
	sort(H, H+N);
	int ans = H[K-1]-H[0];
	for(int b = 1; b + K <= N; ++b) ans = min(ans, H[b+K-1]-H[b]);
	cout <<  ans << '\n';
}

int main()
{
	cin >> N >> K;
	for(int i=0;i<N;++i)cin>>H[i];
	solve();
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <numeric>
#include <limits>
#include <cmath>
#include <iomanip>
 
#define ALL(a)  (a).begin(),(a).end()
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

// 座標 corrdinate と深さを保持するための構造体
struct Corr {
    ll y;
    ll x;
    ll depth;
};

char vec[20][20];  // 座標
queue<Corr> q;

int N, M;

vector<ll> y_vec = {0, 0, -1, +1};
vector<ll> x_vec = {-1, +1, 0, 0};

ll y, x, depth;
ll d;
bool flag = 0;

void bfs() {
    while (!q.empty()) {
        Corr now = q.front(); q.pop();
        y = now.y, x = now.x, depth = now.depth;

        // 停止条件

        // 上下左右 4 方向を探索．進むことができればキューに格納する．
        for (ll i = 0; i < 4; ++i) {
            Corr next = {y + y_vec[i], x + x_vec[i], depth + 1};
            if (0 <= next.y && next.y <= N-1 && 0 <= next.x && next.x <= M-1 && vec[next.y][next.x] == '.') {
                vec[next.y][next.x] = 'x';  // 同じ場所を探索しないようにする
                q.push(next);
                flag = 1;
            }
        }

        // 終点
        if (!flag) d = depth;
        flag = 0;
    }
    return;
}
 
int main() {
    int ans = 1;
    int a = 0;

    cin >> N >> M;

    char map[20][20];

    for (y = 0; y < N; y++) {
        for (x = 0; x < M; x++) {
            cin >> map[y][x];
        }      
    }

    for (int s_y = 0; s_y < N; ++s_y) {
        for (int s_x = 0; s_x < M; ++s_x) {
            for (y = 0; y < N; y++) {
                for (x = 0; x < M; x++) {
                    vec[y][x] = map[y][x];
                }      
            }
            if (vec[s_y][s_x] == '.') { // スタート位置
                Corr start = {s_y, s_x, 0};  // 初期位置の深さ(depth)は 0
                q.emplace(start);  // 初期位置をキューに格納
                bfs();
                a++;
                if (d > ans) ans = d;
            }
        }
    }

    if (a <= 2) ans -= 1;

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [str(input().strip()) for _ in range(N)]
    B = ''
    for _ in range(M):
        B += str(input().strip())

    for i in range(N-M+1):
        for j in range(N-M+1):
            a = ''
            for k in range(M):
                a += A[i+k][j:j+M]

            if a == B:
                return 'Yes'

    return 'No'


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n, q;
int a[200010];

int cnt[200010];
int nur[200010];
int ans;

void Add(int i){
	++cnt[i];
	if(i-cnt[i]>=0) ans -= !nur[i-cnt[i]]++;
}

void Rem(int i){
	if(i-cnt[i]>=0) ans += !--nur[i-cnt[i]];
	--cnt[i];
}

int main()
{
	read(n, q); ans=n;
	for(int i=1; i<=n; ++i) read(a[i]), Add(a[i]);
	for(;q--;){
		int x, y; read(x, y);
		Rem(a[x]); Add(a[x]=y);
		printf("%d\n", ans);
	}
	return 0;
}


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

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const ll inf = 3e18 + 5;

const int MAXN = 1 << 19;
int N = 400000;
int seg[2 * MAXN], A[MAXN];
typedef vector<vi> vvi;

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

    int a1,a2,a3;
    cin >> a1 >> a2 >> a3;
    set<int> a;
    a.insert(a1);
    a.insert(a2);
    a.insert(a3);
    cout << a.size();
}

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

int main()
{
  int a, b;
  cin >> a >> b;
  if ((a * b) % 2 == 1)
  {
    cout << "Odd\n"
         << endl;
  }
  else
  {
    cout << "Even\n"
         << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
using namespace std;
int n,k,s;
signed main(){
    cin>>n>>k>>s;
    rep(i,k){
        cout<<s<<' ';
    }
    rep(i,n-k){
        if(s==1000000000){
            cout<<1<<' ';
        }else{
            cout<<1000000000<<' ';
        }
    }
}

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

int main() {
	string s;
  	cin >> s;
  
  	vector<char> vec(s.size());
  
  	for(int i = 0; i < vec.size(); i++) {
    	cin >> vec.at(i);
    }
  
  	int num = 0;
  
  	for(int i = 1; i < vec.size() - 1;i++) {
    	num++;
    }
  
  	cout << s.at(0) << num << s.at(vec.size() - 1) << endl;
}

Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
n=int(input())
arr=factorization(n)
#print(arr)
cnt=0

if n == 1:
  cnt=0
else:
  for i in arr:
    #print(i)
    x=i[1]
    inc=0
    if x == 1:
      cnt+=1
    else:
      for ii in range(1,x):
        inc+=ii
        #print("inc", inc)
        if inc > x:
          break
        cnt+=1
        #print(inc, cnt)

print(cnt)

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

using namespace std;

typedef long long ll;

int main() {
    int n; cin>>n;
    vector<ll> h(n);
    for (int i=0;i<n;i++) cin>>h[i];

    vector<ll> dp(n,0);
    ll ans=0;
    for (int i=n-1;i>0;i--) {
        if (h[i-1] >= h[i]) {
            dp[i-1] = dp[i] + 1;
            ans = max(dp[i-1], ans);
        } else {
            dp[i] = 0;
        }

        //cout << dp[i-1] << endl;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[])
{
	int n;
	int x[101];
	scanf("%d", &n);
	int i;
	for(i=0;i<n;i++) {
		scanf("%d", &x[i]);
	}

	int ans = 100*100*100;
	int p;
	for(p=1;p<=100;p++) {
		int t = 0;
		for(i=0;i<n;i++) {
			t+=pow(x[i]-p, 2);
		}
		if (ans>t) {
			ans = t;
		}
	}

	printf("%d", ans);

	return 0;
}

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

using  namespace std;

typedef long long ll;

int iprime[999999];
bool is_prime[1000000];

int prime(int n)
{
	fill(is_prime, is_prime + n + 1, true);
	is_prime[0] = is_prime[1] = false;
	int p = 0;
	for(int i = 2; i <= n; ++i)
	{
		if(is_prime[i])
		{
			iprime[p++] = i;
			for(int j = 2*i; j <= n; j += i)
				is_prime[j] = false;
		}
	}
	return p;
}

int main()
{
	int n;
	while(true)
	{
		if(scanf("%d", &n) == EOF)
			break;
			
		printf("%d\n", prime(n));
	}
} 


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

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; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
  ll N;
  cin>>N;
  vector<ll> T(N),A(N);
  rep(i,N) cin>>T[i];
  rep(i,N) cin>>A[i];
  reverse(A.begin(),A.end());
  vector<ll> hi(N);
  hi[0] = T[0];
  hi[N-1] = A[0];
  vector<bool> ok(N);
  bool can = true;
  ok[0] = ok[N-1] = true;
  if(T[0]>A[N-1]||A[0]>T[N-1]) can = false;
  for(int i = 1; i < N; i++){
    if(T[i-1]!=T[i]){
      ok[i] = true;
      hi[i] = T[i];
      if(T[i]>A[N-i-1]) can = false;
    }
    else hi[i] = T[i];
  }
  for(int i = 1; i < N; i++){
    if(A[i-1]!=A[i]){
      if(ok[N-i-1]&&hi[N-i-1]!=A[i]) can = false;
      if(A[i]>T[N-i-1]) can = false;
      ok[N-i-1] = true;
      hi[N-i-1] = A[i];
    }
    else chmin(hi[N-i-1],A[i]);
  }
  if(!can) cout<<0<<endl;
  else {
    ll ans = 1;
    rep(i,N){
      if(!ok[i]) ans = (ans * hi[i])%mod;
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 5596
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

int main(){
  int n; cin >> n;
  vector<int> a(n); rep(i,n) cin >> a[i];
  deque<int> d;
  rep(i,n) {
    int p = lower_bound(all(d), a[i]) - d.begin();
    if(p == 0) d.push_front(a[i]);
    else d[p-1] = a[i];
  }

  cout << d.size() << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    int n; cin>>n;
    string s[101]; int p[101];
    int ind[101];
    for(int i=0; i<n; i++){
        cin>>s[i]>>p[i];
        ind[i]=i;
    }
    sort(ind, ind+n, [&](int i, int j){return (s[i]!=s[j])?(s[i]<s[j]):(p[i]>p[j]);});
    for(int i=0; i<n; i++){
        cout<<ind[i]+1<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main()
{

    int A;
    int B;
    int C;
    int D;
    cin >> A >> B >> C >> D;
    
    int flag=0;

    while(A>0 && C>0){
        if(flag%2==0){
            C=C-B;
        } else {
            A=A-D;
        }
        flag=flag+1;
    }
    if(A>0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

const int mod = 1000000007;

int a[2010];

int main() {
	int n, k; scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] > a[j]) ans++;
		}
	}
	ans = ans * k % mod;
	for (int i = 0; i < n; i++) {
		long long sum = 0;
		for (int j = 0; j < n; j++) {
			if (a[i] > a[j]) sum++;
		}
		ans = (ans + sum * ((1ll * k * (k - 1) / 2) % mod) % mod) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main() {
  size_t N;

  std::cin >> N;

  std::list<size_t> b;

  for (size_t i=0; i<N; i++) {
    size_t a;
    std::cin >> a;

    if (a > i+1) {
      std::cout << -1 << std::endl;
      return 0;
    }

    auto it = std::next(b.begin(), a-1);
    b.insert(it, a);
  }

  for (auto it = b.begin(); it != b.end(); it++) {
    std::cout << *it << std::endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long LL;
int f[15];

int main(){
    int n;
    cin >> n;
    memset(f, 0, sizeof(f));
    while(n){
        f[n%10]++;
        n /= 10;
    }
    int flag = 0, sum = 0;
    for(int i = 1; i < 10; i++){
        sum += f[i] * i;
        if(i != 1 && f[i]) flag = 1;
    }
    if(flag) printf("%d\n", sum);
    else{
        if(f[1] == 1) printf("10\n");
        else printf("%d\n", sum);
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
		long ans = 0;
		for(int i = 0 ; i < n - 1 ; i++) {
			if(a[i] + a[i + 1] > x) {
				ans += a[i + 1] + a[i] - x;
				if(x - a[i] >= 0) {
					a[i + 1] = x - a[i];
				} else {
					a[i + 1] = 0;
					a[i] = x;
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 51244
#include<bits/stdc++.h>
using namespace std;
const long long M=1e9+7;
int a[2010]; 
long long n, k;
long long ans;
long long js(long long k)
{
	if (k==0) return 0; 
	return ((((1+k)%M)*(k%M))/2)%M;
}
int main()
{	
	while (cin>>n>>k)
	{
		memset(a,0,sizeof(a));
		for (int i=0;i<n;i++)
			cin>>a[i];
		long long  sum=0,sum2=0;
		for (int i=0;i<n;i++)
		{
			for (int j=i+1;j<n;j++)
			{
				if (a[i]>a[j])
				{
					sum++;
				}
				else if (a[j]>a[i])
				{
					sum2++;
				}
									
			}	
		}
		ans=((sum*js(k))%M+(sum2*js(k-1))%M);
		cout<<(ans%M)<<endl;	
	}
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 整数の入力


def main():
    # input
    a, b, c = map(int, input().split())
    print(process(a, b, c))


def process(a, b, c):
    ans = c - (a - b)
    if ans < 0:
        ans = 0
    return ans


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
a,b,k = map(int,input().split())
if a+k-1 >= b-k+1:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)

Measured memory_bytes: 80940
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














ll H;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H;

	ll cnt = 1, ans = 0;
	while (0 < H) {
		ans += cnt;
		H /= 2;
		cnt *= 2;
	}

	cout << ans << endl;
}







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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin>>n;
  int t[n];
  int sum = 0;
  for(int i=0;i<n;i++) cin>>t[i],sum+=t[i];
  int m;
  cin>>m;
  while(m--) {
    int p,x;
    cin>>p>>x;
    cout<<sum-t[p-1]+x<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
K=int(input())
import math
def f(x):
  if x==1:
    return 1
  elif x==2:
    return 9
  else:
    m=0
    for j in range(1,x):
      m+=math.gcd(j,x)*6
    for i in range(1,x-1):
      for k in range(i+1,x):
        m+=math.gcd(x,math.gcd(i,k))*6
    return m+x+f(x-1)
print(f(K))

Measured memory_bytes: 9108
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int getint() {
	char C;
	while (!isdigit(C = getchar()));
	int A = C - '0';
	while (isdigit(C = getchar())) A = A * 10 + C - '0';
	return A;
}

void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		C[keta] = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) putchar(C[i]);
	putchar('\n');
}

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


	int N;
	N = getint();
	int A[200001] = {};

	int mae = 0;
	int kotae = 1;
	int mod = 1e9 + 7;
	rep(i, N) {
		int C;
		C = getint();
		if (mae != C) kotae = (kotae + A[C]) % mod;
		A[C] = kotae;
		mae = C;
	}

	putint(kotae);

	Would you please return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <iomanip>
#include <typeinfo>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <set>
#include <numeric>
using namespace std;

#define sortall(container) (sort(container.begin(), container.end()))
#define yn(cond) ((cond) ? (cout << "Yes" << endl) : (cout << "No" << endl))
#define YN(cond) ((cond) ? (cout << "YES" << endl) : (cout << "NO" << endl))
#define LLONG_MAX numeric_limits<long long>::max()
#define INT_MAX numeric_limits<int>::max()

typedef long long       ll;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<string>  vs;
typedef vector<char>    vc;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
typedef vector<vll>		vvll;
typedef vector<vi>		vvi;
typedef vector<vb>		vvb;
typedef vector<vc>		vvc;

typedef struct edge_ {
	ll to;
	ll cost;
} edge;

constexpr double	PI = 3.14159265358979323846;
constexpr ll		INF = 1 << 15;
constexpr ll		MOD = (ll)1e9 + 7;
constexpr double	EPS = 1e-7;
constexpr int		dy4[4] = { 0, 1, 0, -1 };
constexpr int		dx4[4] = { 1, 0, -1, 0 };
constexpr int		dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
constexpr int		dx8[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

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

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
	for (const T& x : vec) os << x << " ";
	return os;
}

template<typename S, typename T>
istream& operator >> (istream& is, pair<S, T>& p) {
	is >> p.first >> p.second;
	return is;
}

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

template <typename T>
void say(vector<T>& vec, string pad = " ") {
	for (const T& elem : vec)
		cout << elem << pad;
}


/******************************************************************************/
/**********************         Don't make WA !!         **********************/
/******************************************************************************/


int main()
{
	int N, K, X, Y;
	cin >> N >> K >> X >> Y;
	cout << min(K, N) * X + max(N - K, 0) * Y << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=210;
int a[maxn];
int n;

void _init()
{
    memset(a,0,sizeof(a));
    for (int i=1;i<maxn;i+=2)
    {
        int cnt=0;
        for (int j=1;j<=i;j++)
            if (i%j==0)
                cnt++;

        if (cnt==8) a[i]=1;
    }
    for (int i=1;i<maxn;i++)
        a[i]=a[i-1]+a[i];
}

int main()
{
    _init();
    while (scanf("%d",&n)!=EOF)
    {
        printf("%d\n",a[n]);
    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll MOD = 1000000007;
using namespace std;

int main(){
    int n; cin >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];

    sort(a.begin(), a.end());
    int r = a[0]; double mid = a[n-1]/2.0;
    double dif = abs(mid - a[0]);
    REP(i, n-1){
        if(dif > abs(mid - a[i])){
            r = a[i];
            dif = abs(mid - a[i]);
        }
    }
    cout << a[n-1] << " " << r << endl;
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner Input = new Scanner(System.in);
        String S = Input.next();
        S = S.toLowerCase();
        int X = 0;
        for (int I = 97; I <= 97 + 25; I++) {
            char A = (char) I;
            if (S.contains(A + "")) {
                X++;
            } else {
                System.out.print(A);
                break;
            }
        }
        if (X >= 26) {
            System.out.println("None");
        }

    }
}


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

int main(int argc, const char * argv[]) {
    
    int a,b,c;
    cin >> a >> b >> c;
    
    if(a < b && b < c){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
using namespace std; //std::の省略のため
using ll = long long;

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

  int count = 0;

  if (b == a)
    count++;

  if (c == b || c == a)
    count++;

  int ans = 3 - count;
  cout << ans << endl;
}


Measured memory_bytes: 3552
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
using namespace std;
struct UnionFind{
    vector<int> par;
    UnionFind(int N) : par(N){
        for(int i=0;i<N;i++){
            par[i] = i;
        }
    }
    int root(int x){
        if(par[x]==x)return x;
        return par[x] = root(par[x]);
    }
    void unite(int x,int y){
        int rx = root(x);
        int ry = root(y);
        if(rx==ry) return;
        par[rx] = ry;
    }
    bool same(int x,int y){
        int rx = root(x);
        int ry = root(y);
        return rx==ry;
    }
    int parent(int x){
        return root(x);
    }
};
int main(){
    int N,M;
    cin >> N >> M;
    UnionFind tree(N+5);
    int X,Y,Z;
    vector<int> check(N+5,0);
    for(int i=0;i<M;i++){
        cin >> X >> Y >> Z;
        X--; Y--;
        tree.unite(X,Y);
        if(Z%2==0){
            check[X] = 1;
            check[Y] = 1;
        }else{
            check[X] = 2;
            check[Y] = 2;
        }
    }
    int ans = 0;
    for(int i=0;i<N;i++){
        if(check[tree.parent(i)]==1){
            ans += 1;
            check[tree.parent(i)]=3;
        }else if(check[tree.parent(i)]==2){
            ans += 1;
            check[tree.parent(i)]=3;
        }else if(check[tree.parent(i)]==0){
            ans += 1;
            check[tree.parent(i)]=3;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<vector<int>> v(n,vector<int>(3));
    for(int i=0;i<n;i++){
        cin>>v[i][0]>>v[i][1]>>v[i][2];
    }
    for(int i=1;i<n;i++){
      v[i][0]+=max(v[i-1][1],v[i-1][2]);
      v[i][1]+=max(v[i-1][0],v[i-1][2]);
      v[i][2]+=max(v[i-1][0],v[i-1][1]);      
    }
 	cout<<max(v[n-1][0],max(v[n-1][1],v[n-1][2]));
}

Measured memory_bytes: 5760
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;

int N;
int Y;

int main(){
  cin >> N >> Y;
  bool flag = true;
  int ans[3];
  for(int i=0;i<min(Y/10000+1,N+1);i++){
    for(int j=0;j<min(Y/5000+1,N+1);j++){
      if(Y==i*10000+5000*j+1000*(N-i-j)&&N-i-j>=0){
	flag = false;
	ans[0]=i;
	ans[1]=j;
	ans[2]=N-i-j;
      }
    }
  }
  if(flag) cout<<-1<<" "<<-1<<" "<<-1<<endl;
  else 	cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<endl;
}


Measured memory_bytes: 256
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let mut xy = (0..n)
        .map(|_| (sc.read::<f64>(), sc.read::<f64>()))
        .collect::<Vec<_>>();
    xy.sort_by(|&(ax, ay), &(bx, by)| {
        let a = ay.atan2(ax);
        let b = by.atan2(bx);
        a.partial_cmp(&b).unwrap()
    });

    let mut max = 0.0;
    for from in 0..n {
        let (mut x, mut y) = (0.0, 0.0);
        for i in 0..n {
            x += xy[(from + i) % n].0;
            y += xy[(from + i) % n].1;
            let d = x * x + y * y;
            if d > max {
                max = d;
            }
        }
    }
    println!("{}", max.sqrt());
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;
LL dp[101010];
const LL MOD =  1000000007;
int main() {
    int n, m;
    cin >> n >> m;
    vector<bool> v(n + 1, true);
    rep(i, m) {
        int x;
        cin >> x ;
        v[x] = false;
    }

    dp[0] = 1;
    if (v[1] == true) {
        dp[1] = 1;
    } else {
        dp[1] = 0;
    }

    for (int i = 2; i <= n; i++) {
        if (v[i] == false) {
            dp[i] = 0;
            continue;
        }
        LL dist1 = 0, dist2 = 0;
        if (v[i - 1] == false) {
            dist1 = 0;
        } else {
            dist1 = dp[i - 1];
        }
        if (v[i - 2] == false) {
            dist2 = 0;
        } else {
            dist2 = dp[i - 2];
        }
        dp[i] = dist1 % MOD + dist2 % MOD;
    }
    cout << dp[n] % MOD << endl;
    return 0;
}


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

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; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans = max(max(a*c,a*d),max(b*c,b*d));
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
while True:
    data = map(int, raw_input().split())
    if data[0] == 0 and data[1] == 0:
        break
    else:
        for i in range(data[0]):
            if i == 0 or i == data[0]-1:
                print "#" * data[1]
            else:
                print "#" + "." * (data[1]-2) + "#"
        print
        

Measured memory_bytes: 6280
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <utility>

#define INITSCORE -1
using namespace std;

typedef struct maze
{
  char c;
  int score;
  maze():score(INITSCORE),c(0){}
}maze;

void initmat(vector<vector<maze> >&mat)
{
  for(int i = 0; i < mat.size(); ++i)
    for(int j = 0; j < mat[i].size(); ++j)
      mat[i][j].score = INITSCORE;
}
void debugprint(vector<vector<maze> >&mat)
{
  for(int i = 0; i < mat.size(); ++i)
  {
    cout << endl;
    for(int j = 0; j < mat[i].size(); ++j)
      cout << mat[i][j].score << " " ;
  }
    cout << endl;
}

void pushscore(vector<vector<maze> >&mat, list<pair<int, int> >& queue,
              int newscore, int x, int y)
{ 
  mat[y][x].score = newscore;
  queue.push_back(make_pair(y, x));
}
int check(vector<vector<maze> >& mat, int score, int x, int y, list<pair<int, int> >& queue)
{
  const int maxX = mat[y].size();
  const int maxY = mat.size();
  const int lx = x - 1;
  const int rx = x + 1;
  const int uy = y - 1;
  const int dy = y + 1;
  const int newscore = score + 1;
  if(lx >= 0 && mat[y][lx].c == '.' && mat[y][lx].score < 0)
    pushscore(mat, queue, newscore, lx, y);
  if(rx < maxX && mat[y][rx].c == '.' && mat[y][rx].score < 0)
    pushscore(mat, queue, newscore, rx, y);
  if(uy >= 0 && mat[uy][x].c == '.' && mat[uy][x].score < 0)
    pushscore(mat, queue, newscore, x, uy);
  if(dy < maxY && mat[dy][x].c == '.' && mat[dy][x].score < 0)
    pushscore(mat, queue, newscore, x, dy);
  return newscore;
}

int bfs(vector<vector<maze> > &mat, int sy, int sx)
{
  int retscore = 0;

  mat[sy][sx].score = 0;
  list<pair<int, int> > queue;
  queue.push_back(make_pair(sy, sx));
  while(!queue.empty())
  {
    pair<int, int> pt = queue.front();
    queue.pop_front();
    int x = pt.second;
    int y = pt.first;
    retscore = max(retscore, check(mat, mat[y][x].score, x, y, queue));
  }
  
  return retscore - 1;
}

int main()
{
  int h, w;
  cin >> h >> w;
  vector<vector<maze> > mat(h, vector<maze>(w));
  int ans = 0;
  for(int i = 0; i < h; ++i)
  {
    for(int j = 0; j < w; ++j)
    {
      cin >> mat[i][j].c;
    }
  }
  for(int i = 0; i < h; ++i)
    for(int j = 0; j < w; ++j)
    {
      if(mat[i][j].c == '.')
      {
        initmat(mat);
        ans = max(bfs(mat, i, j), ans);
      }
    }

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


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

using namespace std;

const int INF = numeric_limits<int>::max();
const int MAXN = 5000+ 5;
const int MOD = 1e9 + 7;
const double res = 1e-9;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int dp[MAXN][MAXN][2];

signed main() {
#if(DEBUG_LEVEL > 0)
    freopen("../input.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    double ans = 0;
    while(n--) {
        double x;
        cin >> x;
        ans += (1 / x);
    }
    cout << (1 / ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue< long long > a;
    for (int i = 0; i < n; i++) {
        long long A;
        cin >> A;
        a.push(A);
    }
    for (int i = 0; i < m; i++) {
        long long A = a.top();
        a.pop();
        a.push(A / 2);
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a.top();
        a.pop();
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int N,M;
    cin >> N >> M;
    
    set<int> Ai;
	rep(i,M){
        int tmpAi;
		cin >> tmpAi;
        Ai.insert(tmpAi);
	}

    vector<int> Di(N+1);
    Di.at(0) = 1;
    if(Ai.count(1)){
        Di.at(1) = 0; 
    }else{
        Di.at(1) = 1;
    }

    rep2(i,2,N){
        if(Ai.count(i)){
            Di.at(i) = 0; 
        }else{
            Di.at(i) = Di.at(i-1) + Di.at(i-2);
            Di.at(i) %= MOD;
        }
    }

    cout << Di.at(N) << endl;
    return 0;
}


Measured memory_bytes: 5376
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	int calcH(int cx, int cy, int x, int y, int h) {
		return h + Math.abs(cx - x) + Math.abs(cy - y);
	}

	boolean check(int cx, int cy, int ch, int x, int y, int h) {
		if (h > 0) {
			return ch == calcH(cx, cy, x, y, h);
		} else {
			return ch <= calcH(cx, cy, x, y, h);
		}
	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int[][] xyh = new int[N][3];
		for (int i = 0; i < N; i++) {
			xyh[i] = new int[] { sc.nextInt(), sc.nextInt(), sc.nextInt() };
		}
		sc.close();

		//hが0ではないxyを保持する
		int p = -1;
		for (int i = 0; i < N; i++) {
			if (xyh[i][2] > 0) {
				p = i;
				break;
			}
		}

		//すべての(x,y)を調べる
		for (int cx = 0; cx <= 100; cx++) {

			for (int cy = 0; cy <= 100; cy++)
				next_point: {
					// xyh[p] の情報から(cx,cy)が中心だったときのHを求める
					int H = calcH(cx, cy, xyh[p][0], xyh[p][1], xyh[p][2]);

					for (int i = 0; i < N; i++) {
						if (!check(cx, cy, H, xyh[i][0], xyh[i][1], xyh[i][2])) {
							break next_point;
						}
					}
					out.println(cx + " " + cy + " " + H);
					return;

				}
		}

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

}


Measured memory_bytes: 21972
//#define _GLIBCXX_DEBUG

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

int main(){
  string a,b,c;
  cin>>a>>b>>c;
  char x,y,z;
  x=a[0]-0x20;
  y=b[0]-0x20;
  z=c[0]-0x20;
  cout<<x<<y<<z<<endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

#define INF 10000001
vector<int> vis;
int p[205][205];
int n,m,r;

int main(){
  cin>>n>>m>>r;
  for(int i=0;i<r;i++){
    int x;
    cin>>x;
    x--;
    vis.push_back(x);
  }
  sort(vis.begin(), vis.end());
  for(int i=0;i<n;i++)for(int j=0;j<n;j++) p[i][j]=INF;
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--; b--;
    p[a][b]=p[b][a]=c;
  }
  for(int i=0;i<n;i++) p[i][i]=0;
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
      }
    }
  }
  int ans=200000005;
  do{
    int sum=0;
    for(int i=0;i<r-1;i++) sum+=p[vis[i]][vis[i+1]];
    ans=min(ans, sum);
  }while(next_permutation(vis.begin(), vis.end()));
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 384
from collections import defaultdict
N, M = map( int, input().split())
S = list( input())
E = [ list( map( int, input().split())) for _ in range(M)]
V = [ 1 for _ in range(N)]
Edges = [[] for _ in range(N)]
A = [0]*N
B = [0]*N
d = defaultdict(int)
for i in range(M):
    a, b = E[i]
    a, b = a-1, b-1
    a, b = min(a,b), max(a,b)
    Edges[a].append(b)
    Edges[b].append(a)
    if d[(a,b)] == 1:
        continue
    else:
        d[(a,b)] += 1
    if a == b:
        if S[a] == 'A':
            A[a] += 1
        else:
            B[a] += 1
        continue
    if S[a] == 'A':
        A[b] += 1
    else:
        B[b] += 1
    if S[b] == 'B':
        B[a] += 1
    else:
        A[a] += 1
T = set([])

for i in range(N):
    if A[i] == 0 or B[i] == 0:
        T.add(i)
while T:
    n = T.pop()
    V[n] = 0
    for m in set(Edges[n]):
        if V[m] == 1:
            if S[n] == 'A':
                A[m] -= 1
                if A[m] == 0:
                    T.add(m)
            else:
                B[m] -= 1
                if B[m] == 0:
                    T.add(m)
                
if sum(V) == 0:
    print('No')
else:
    print('Yes')

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

struct UnionFind {
    vector<int> data;
    int sz;
    UnionFind(int sz) : data(sz, -1), sz(sz) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) == (y = root(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y]; data[y] = x; sz--;
        return true;
    }
    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 size() { return sz; }
};

int main() {
    int n, m; cin >> n >> m;
    vector<int> p(n);
    for (auto &pi: p) cin >> pi, pi--;
    UnionFind uf(n);
    while (m--) {
        int x, y; cin >> x >> y; x--, y--;
        uf.unionSet(x, y);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) cnt += uf.findSet(i, p[i]);
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 1024