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

int Path[26][200010];
int From[200010];
string A;
void dp(){
    for(int i=0;i<200010;i++)From[i] = -1;
    A = "#" + A;
    int L = A.size();
    for(int i=0;i<26;i++){
        Path[i][L-1] = 200005;
        for(int j = L-1;j>0;j--){
            if(A[j]-'a'==i)Path[i][j-1] = j;
            else Path[i][j-1] = Path[i][j];
        }
    }
}
int main(){
    cin>>A;
    dp();
    queue<int>fromQ, toQ;
    fromQ.push(0);
    toQ.push(0);
    while(true){
        int from = fromQ.front(); fromQ.pop();
        int to = toQ.front(); toQ.pop();
        if(From[to]!=-1)continue;
        From[to] = from;
        if(to == 200005)break;
        for(int i=0;i<26;i++){
            if(From[Path[i][to]]!=-1)continue;
            fromQ.push(to);
            toQ.push(Path[i][to]);
        }
    }
    string ans = "";
    for(int i=200005;i;i = From[i]){
        for(int j=0;j<26;j++){
            if(Path[j][From[i]]==i){
                ans += string(1, 'a'+j);
                break;
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 21824
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int N, K;
    std::cin >> N >> K;

    std::vector<long long> x(N);
    for (int i = 0; i < N; i++) {
        std::cin >> x[i];
    }

    long long ans = 1000000000;
    for (int i = 0; i <= N-K; i++) {
        long long time = 0;
        if (x[i+K-1] < 0) {
            time = -x[i];
        }
        else if (x[i] > 0) {
            time = x[i+K-1];
        }
        else if (x[i+K-1] + x[i] > 0) {
            time = (-x[i]*2);
            time += x[i+K-1];
        }
        else {
            time = (x[i+K-1]*2);
            time -= x[i];
        }
        ans = std::min(ans, time);
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scn=new Scanner(System.in);
		int n=scn.nextInt();
		while(n>0){
	     int val = n%10;
	     if(val==7){
	    	 System.out.println("Yes");
	    	 return;
	     }
	     n/=10;
		}
System.out.println("No");
	}

}

Measured memory_bytes: 35724
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0 ,1};

void dfs(pair<int, int> curr, set<pair<int, int> > &block){
    if(block.find(curr) == block.end()) return;
    block.erase(curr);
    for(int i=0; i<8; i++){
        dfs(make_pair(curr.first +dx[i], curr.second +dy[i]), block);
    }
}

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

    set<pair<int, int> > block; 
    for(int i=0; i<n; i++){
        double x,y;
        cin >> x >> y;
        int xi = (x +1e6)/r;
        int yi = (y +1e6)/r;
        block.insert(make_pair(xi, yi));
    }

    int ans = 0;
    while(!block.empty()){
        ans++;
        pair<int, int> curr = *(block.begin());
        dfs(curr, block);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+5;
const int maxm=5e2+5;
const int maxq=55;
const int INF=0x3f3f3f3f;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int mn=1e9+5;int mx=0;int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            mx=max(mx,x);
            mn=min(mn,x);
        }
        printf("%d\n",mx-mn);
    }
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main()
{
    vector<string> c(3);
    rep(i, 3) cin >> c[i];

    rep(i, 3)
    {
        cout << c[i][i];
    }
    cout << endl;
    return (0);
}


Measured memory_bytes: 3576
package main

import "fmt"

const MAX_NUM  = 2000

func main(){
	var N, Y int
	fmt.Scan(&N)
	fmt.Scan(&Y)

	for ten:= 0; 10000 * ten <= Y; ten++{
		for five :=0; 10000 * ten + 5000 * five <= Y; five++{

			one := N - (ten + five)

			if ten < 0{
				break
			}

			if 10000 * ten + 5000 * five + 1000 * one == Y{
				fmt.Println(ten, five, one)
				return
			}
		}
	}

	fmt.Println(-1, -1, -1)
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

int n;
int a[N],b[N],c[N];
int dp[N];

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n=read();

	for(int i=1;i<=n;++i){
		a[i]=read();
		b[i]=read();
		c[i]=read();
	}

	for(int i=1;i<=n;++i){
		int cnt1=dp[1],cnt2=dp[2],cnt3=dp[3];
		dp[1]=a[i]+max(cnt2,cnt3);
		dp[2]=b[i]+max(cnt1,cnt3);
		dp[3]=c[i]+max(cnt1,cnt2);
		//printf("%d %d %d\n",dp[1],dp[2],dp[3]);
	}

	printf("%d\n",max({dp[1],dp[2],dp[3]}));

    return 0;
}

Measured memory_bytes: 4824
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
typedef vector<string> vstring;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
#define stp(x)  setprecision(x)
const long double PI=3.14159265358979323846264338327950;
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,q;
  cin>>n>>q;
  vector<priority_queue<long long> > vq(n);
  rep(i,q){
    int tmp,t,x;
    cin>>tmp;
    if(tmp==0){
      cin>>t>>x;
      vq[t].push(x);
    }
    else if(tmp==1){
      cin>>t;
      if(vq[t].empty()){
        continue;
      }
      cout<<vq[t].top()<<'\n';
    }
    else{
      cin>>t;
      if(vq[t].empty()){
        continue;
      }
      vq[t].pop();
    }
  }

  return(0);
}
  


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

int main(){
	int N,a,b,c;
	cin>>N;
	for(int i = 0 ; i < N ; i++){
		cin>>a>>b>>c;
	if(a * a == b * b + c * c || b * b == a * a + c * c || c * c == a * a + b * b){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
	}
	return 0;
}


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

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

ll lcm(ll a, ll b){
  return a/gcd(a,b) * b;
}
ll func2(ll n){
  ll res = 0;
  while(n%2 == 0){
    n /= 2;
    res++;
  }
  return res;
}

ll zyou(ll a,ll b){//a＾b
  ll res = 1;
  for(int i = 1;i<=b;i++){
    res *= a;
  }
  return res;
}
struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t),weight(w){ }
};

typedef pair<int,int> P;
using Graph = vector<vector<int>>;

ll calc(ll a, ll b, ll p){//aのb乗をpで割った余り
  if(b == 0) return 1;

  else if(b%2 == 0){
    ll d = calc(a,b/2,p);
    return (d*d)%p;
  }
  else if(b%2 == 1){
    return (a * calc(a,b-1,p))%p;
  }
}


bool is_prime(int n){//nが素数であるかどうか判定 iで割り切れると素数でない
    if(n == 1) return false;//1は例外
    for(int i = 2;i*i <= n;i++){
        if(n%i == 0) return false;
    }
    
    return true;
}

bool palin(string S){//回文判定
  int n = S.size();
  bool flag = true;
  if(n%2 == 0){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  else if(n%2 == 1){
    for(int i = 0;i<=n/2-1;i++){
      if(S[i] != S[n-i-1]){
        flag = false;
        break;
      }
    }
  }
  return flag;
}
/*vector<int> d(N+1,-1);

//頂点xとの各点との最短距離を求める
void bfs(int x,Graph &G){
  d[x] = 0;
  queue<<int> que;
  que.push(x);

  // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }
}*/

int main(){
  string S;
  cin >> S;
  string S2;
  S.push_back('$');

  rep(i,S.size()){
    if(S[i] != S[i+1]) S2.push_back(S[i]);
  }
  S2.pop_back();
  int n = S2.size();
  cout << n-1 << endl;
  
 }


Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(void){

  int N;
  
  cin >> N;
  
  int A[N], B[N], C[N-1];
  
  int beforeEat = -1, sum = 0;
  
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  for(int i = 0; i < N; i++){
    cin >> B[i];
  }
  for(int i = 0; i < N - 1; i++){
    cin >> C[i];
  }
  
  for(int i = 0; i < N; i++){
    sum += B[ A[i] - 1 ];
    if(beforeEat == A[i] - 1 - 1){
      sum += C[beforeEat];
    }
    beforeEat = A[i] - 1;
  }
  
  cout << sum << endl;

  return 0;
}


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

int dp[100010][3];

int main(){
  int n;
  cin>>n;
  vector<int> a(n), b(n), c(n);
  for(int i = 0; i < n; i++)
    cin>>a[i]>>b[i]>>c[i];
  dp[0][0]=a[0], dp[0][1]=b[0], dp[0][2]=c[0];
  for(int i = 1; i < n; i++){
    dp[i][0] = a[i]+max( dp[i-1][1], dp[i-1][2] );
    dp[i][1] = b[i]+max( dp[i-1][0], dp[i-1][2] );
    dp[i][2] = c[i]+max( dp[i-1][0], dp[i-1][1] );
  }
  cout<<max({dp[n-1][0], dp[n-1][1], dp[n-1][2]})<<"\n";
  return 0;
}


Measured memory_bytes: 2560
from math import factorial

number = input().split(" ")
N = int(number[0])
M = int(number[1])

if N > 1:
    a = factorial(N) / factorial(2) / factorial(N - 2)
else:
    a = 0
if M > 1:
    b = factorial(M) / factorial(2) / factorial(M - 2)
else:
    b = 0

print(int(a+b))

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    bool s, e, n, w;
    s=e=n=w=false;
    string str;
    cin >> str;
    for (char ch : str) {
        if (ch == 'E') e=true;
        else if (ch == 'S') s=true;
        else if (ch == 'N') n=true;
        else w=true;
    }
    if (s==n and e==w) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}


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

int main(){
	int a, b, k, count = 0;
	cin >> a >> b >> k;
	// 100 50
	for(int i = min(a, b); i >= 1; i--){
		if(a % i == 0 && b % i == 0)
			count++; 	
		if(count == k)
			return cout << i << '\n', 0;
	}
}

Measured memory_bytes: 256
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static final PrintStream out = System.out;
	static final Scanner sc = new Scanner(System.in);
	static final long Mod = 1000_000_007L;
	static final long INF = 10_000_000_001L;
	int N,HP;

	public static void main(String[] args) {
		Main main = new Main();
		main.solve();
		System.exit(0);
	}

	void solve() {
		HP =  nextInt();
		N = nextInt();

		int []A = new int[N];
		int []B = new int[N];
		for(int i=0;i<N;i++) {
			A[i] = nextInt();
			B[i] = nextInt();
		}

		long []dp = new long [HP+1];
		Arrays.fill(dp, INF);
		dp[0] = 0;
		for (int i = 0; i < N; i++) {
			for (int w = 0; w < HP; w++) {
				int nw = Math.min(w + A[i],HP);
				dp[nw] = Math.min(dp[nw], dp[w]+B[i]);
			}
		}

		out.println(dp[HP]);
	}

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)a[i] = nextInt();
		return a;
	}
	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)a[i] = nextLong();
		return a;
	}
	public int nextInt() {
		return Integer.parseInt(next());
	}
	public long nextLong() {
		return Long.parseLong(next());
	}
	public String next() {
		return sc.next();
	}

}

Measured memory_bytes: 25056
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

#define ll long long

ll n,a,b;

ll minn(ll a,ll b){
	if(a >= b) return b;
	return a;
}

int main(){
	scanf("%lld%lld%lld",&n,&a,&b);
	if(a > b){
		ll c;
		c = a;
		a = b;
		b = c;
	}
	if(a == b){		
	cout << 0;
	return 0;
} 
	ll ans = 0x7fffffff;
	if((b - a) % 2 == 0) cout << (b-a) / 2; 
	else cout << minn((b-a)/2+a,(b-a-1)/2+n-b+1);
} 

Measured memory_bytes: 256
class UnionFind:
    #par[x]でxの親のID，xが根ならその木のサイズに―をつけたもの
    def __init__(self, n):
        #全て根として初期化
        self.par = [-1] * n
    
    #xの根を返す
    def root(self, x):
        #xが根なら終了
        if self.par[x] < 0:
            return x
        #そうでないならxの親について調べる
        self.par[x] = self.root(self.par[x])    #xの根が親になるように更新
        return self.par[x]

    #xとyを結合
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        #xとyが同じ根を持つ(＝同じ木に属する)なら終了
        if x == y:
            return
        #サイズの大きい木に小さい木を結合
        if self.par[x] > self.par[y]:   #xが大きくなるよう交換
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    
    #xのサイズを返す
    def size(self, x):
        return -1 * self.par[self.root(x)]


#main
n, m = map(int, input().split())
uf = UnionFind(n)
#Union-FInd木を作る
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)      #1からではなく0からに
#サイズが最大のものを探す
ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Measured memory_bytes: 14380
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <set>

using namespace std;
typedef long long ll;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Point {
  ll x;
  ll y;
  int type;
  Point() {;}
  Point(double x, double y, int type) : x(x), y(y), type(type) {;}
  bool operator<(const Point &rhs) const {
    if (fabs(y - rhs.y) > EPS) { return y < rhs.y; }
    if (fabs(x - rhs.x) > EPS) { return x < rhs.x; }
    return false;
  }
};

struct Event {
  int x;
  Point p;
  int in;
  Event() {;}
  Event(int x, Point p, int in) : x(x), p(p), in(in) {;}
  bool operator<(const Event &rhs) const {
    if (x != rhs.x) { return x < rhs.x; }
    return in > rhs.in;
  }
};

inline ll square(ll x) { return x * x; }

inline ll dist2(const Point &a, const Point &b) {
  return square(a.x - b.x) + square(a.y - b.y);
}

int an, bn, n;
ll r;
Event event[500000];

int PlaneSweep() {
  int ans = 0;
  set<Point> open;
  REP(iter, n) {
    Event &e = event[iter];
    Point &p = e.p;
    if (e.in) {
      set<Point>::iterator lower = open.lower_bound(Point(0, p.y - 4.0 * r - 1, 0));
      set<Point>::iterator upper = open.upper_bound(Point(0, p.y + 4.0 * r + 1, 0));
      for (set<Point>::iterator it = lower; it != upper; it++) {
        if (dist2(*it, p) <= 16.0 * r * r) {
          ans += p.type ^ it->type;
        }
      }
      open.insert(p);
    } else {
      open.erase(open.find(p));
    }
  }
  return ans;
}

int main() {
  while (scanf("%d %d %lld", &an, &bn, &r), an|bn) {
    n = (an + bn) * 2;
    REP(i, an) {
      ll x, y;
      scanf("%lld %lld", &x, &y);
      event[2 * i + 0] = Event(x - 4 * r, Point(x, y, 0), 1);
      event[2 * i + 1] = Event(x, Point(x, y, 0), 0);
    }
    REP(i, bn) {
      ll x, y;
      scanf("%lld %lld", &x, &y);
      event[2 * an + 2 * i + 0] = Event(x - 4 * r, Point(x, y, 1), 1);
      event[2 * an + 2 * i + 1] = Event(x, Point(x, y, 1), 0);
    }
    sort(event, event + n);
    int ans = PlaneSweep();
    printf("%d\n", ans);
  }
}

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

int main() {
  int n, t;
  cin >> n >> t;
  vector<int> cost(n);
  vector<int> time(n);
  for (int i = 0; i < n; i ++) {
    cin >> cost.at(i) >> time.at(i);
  }

  int ans = 1001;
  for (int i = 0; i < n; i ++) {
    if (ans >= cost.at(i) && t >= time.at(i)) {
      ans = cost.at(i);
    }
  }
  if (ans != 1001) {
    cout << ans << endl;
  } else {
    cout << "TLE" << endl;
  }
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <limits>
#define rep(i,a) for(int i=0;i<(a);++i)

const int INF = std::numeric_limits<int>::max()>>2;

struct edge
{
  int to, cap, rev; // ?????????????????????????????? idx

  edge( int to, int cap, int rev )
  : to(to), cap(cap), rev(rev)
  {}
};

int V, E;
std::vector<std::vector<edge> > G;

void add_edge( int u, int v, int cap )
{
  G[u].push_back( edge( v, cap, G[v].size() ) );
  G[v].push_back( edge( u, 0, G[u].size()-1 ) );

  return;
}

std::vector<bool> used;
int dfs( int v, int t, int f )
{
  used[v] = true;

  if( v == t )
    return f;

  for( auto &e : G[v] )
  {
    if( !used[e.to] && e.cap > 0 )
    {
      int d = dfs( e.to, t, std::min( f, e.cap ) );

      if( d > 0 )
      {
        e.cap -= d;
        G[e.to][e.rev].cap += d;

        return d;
      }
    }
  }

  return 0;
}

int max_flow( int s, int t )
{
  int flow = 0;

  for( ;; )
  {
    std::fill( used.begin(), used.end(), false );

    int f = dfs( s, t, INF );

    if( f == 0 )
      break;

    flow += f;
  }

  return flow;
}

int main()
{
  scanf( "%d%d", &V, &E );
  G.resize( V );
  rep( i, E )
  {
    int u, v, c;
    scanf( "%d%d%d", &u, &v, &c );

    add_edge( u, v, c );
  }

  used.resize( V, false );

  printf( "%d\n", max_flow( 0, V-1 ) );
  
  return 0;
}

Measured memory_bytes: 2780
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long
int n,MAX,sz;
int segmax[800005];
void init(){
    sz = 1; while(sz<MAX) sz*=2;
}
int getMax(int i){
    return segmax[i+=sz];
}
void updateMax(int i,int v){
    i+=sz;
    segmax[i] = v;
    while(i>1){
        i/=2;
        segmax[i] = max(segmax[2*i],segmax[2*i+1]);
    }
}
int queryMax(int l,int r){
    l+=sz; r+=sz;
    int res = 0;
    while(l<r){
        if(l%2) res = max(res,segmax[l++]);
        if(r%2) res = max(res,segmax[--r]);
        l/=2; r/=2;
    }
    return res;
}


vector<int> adj[200005];
vector<int> order[200005];
int dp[200005];
int x[200005];
int cnt = 0;
int m;
map<int,int> compress;
void dfsjump(int curr=0, int par = -1){
    int val = queryMax(0,x[curr]);
    int bef = getMax(x[curr]);
    updateMax(x[curr],val+1);
    dp[curr] = val+1;
    m = max(m,val+1);
    for(int next : adj[curr]){
        if(next!=par){
            dfsjump(next,curr);
        }
    }
    updateMax(x[curr],bef);
}
void dfs(int curr=0, int par=-1){
    if(par!=-1)
        dp[curr] = max(dp[curr],dp[par]);
    for(int next : adj[curr])
        if(next!=par) dfs(next,curr);
}
int main(){
    scanf("%d",&n);
    set<int> r;
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
        r.insert(x[i]);
    }
    int v =0;
    for(auto &it : r)
        compress[it] = v++;
    for(int i=0;i<n;i++){
        x[i] = compress[x[i]];
        MAX = max(MAX,x[i]);
    }
    ++MAX;
    init();
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfsjump();
    dfs();
    for(int i=0;i<n;i++) 
        printf("%d\n",dp[i]);
}


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

int main() {
    /* Input */
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    /* Main Logic */
    while (a > 0 && c > 0) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            break;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
int main(){
int h,w;
  cin >> h >> w;
  while(h!=0){
    int i,j;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	if((i%2==0&&j%2==0)||(i%2==1&&j%2==1))
	  cout << "#";
	else cout << ".";
      }
      cout << endl;
    }
    cout << endl;
    cin >> h >> w;
  }
  return 0;
}


Measured memory_bytes: 3084
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<ctime>
#include<sstream>
#define rep(i,l,r) for (ll i=l;i<=r;i++)
#define down(i,l,r) for (ll i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 1152921504606846976
#define ll long long
#define maxn 210050
#define eps 1e-5
#define mm 2147483648
#define low(x) (x&(-x))
#define pb(x) push_back(x)
#define vi vector<string>
using namespace std;
ll read(){
    ll x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int a[305][305],sum[305],flag[305],pos[305];
int n,m,ans;
bool jud(int mid){
	clr(sum,0); clr(flag,0);
	rep(i,1,n) pos[i]=1,sum[a[i][1]]++;
	int rm=m;
	while (1){
		int cnt=0;
		rep(i,1,m) {
			if (!flag[i]&&sum[i]>mid) ++cnt,flag[i]=1;
		}
		if (!cnt) return 1;
		rm-=cnt;
		if (rm<=0) return 0;
		rep(i,1,n) {
			int &x=pos[i];
			if (flag[a[i][x]]){
				while (flag[a[i][x]]) x++;
				sum[a[i][x]]++;
			}	 
		} 
	}
	return 0;
}
int main(){
//	freopen("in.txt","r",stdin);
	n=read(); m=read();
	rep(i,1,n) rep(j,1,m) a[i][j]=read();
	int l=1,r=n;
	while (l<=r){
		int mid=(l+r)/2;
		if (jud(mid)) {
			ans=mid; r=mid-1;
		}
		else l=mid+1;
	}	
	printf("%d\n",ans);
//	fclose(stdin); fclose(stdout);
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int partition(int *, int, int);
int n;

int main()
{
  int i, A[100000], for_mark;

  scanf("%d",&n);
  
  for(i = 0 ; i < n ; i++) scanf("%d",&A[i]);

  for_mark = partition(A, 0, n-1);

  for(i = 0 ; i < n-1 ; i++){
    if(i == for_mark) printf("[%d] ",A[i]);
    else printf("%d ",A[i]); }
  printf("%d\n",A[n-1]);

  return 0;
}

int partition(int *A, int p, int r)
{
  int x, i, j, for_change;

  x = A[r];
  i = p - 1;

  for(j = p ; j < r ; j++){
    if(A[j] <= x){
      i++;
      for_change = A[i];
      A[i] = A[j];
      A[j] = for_change; }
  }
  
  for_change = A[i+1];
  A[i+1] = A[r];
  A[r] = for_change;

  return ++i;
}



Measured memory_bytes: 2172
#include<stdio.h>
int main()
{
	int n, m;
	while(scanf("%d %d", &n, &m))
	{
		if(n == 0 && m == n)
		{
			break;
		}
		for(int i=0;i<m;i++)
		{
			printf("#");
		}
		printf("\n");
		for(int i=0;i<n-2;i++)
		{
			printf("#");
			for(int j=0;j<m-2;j++)
			{
				printf(".");
			}
			printf("#");
			printf("\n");
		}
		for(int i=0;i<m;i++)
		{
			printf("#");
		}
		printf("\n");
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2608
count = [0,0,0,0]
while 1:
    s = input()
    s = s.split()
    sum = 0
    sum_2 = 0
    for i in range(3):
        s[i] = int(s[i])
        sum += s[i]
        sum_2 += s[i]**2
    if 2*max(s) >= sum:
        break
    else:
        count[0] += 1
        if 2*max(s)**2 == sum_2:
            count[1] += 1
        elif 2*max(s)**2 < sum_2:
            count[2] += 1
        else:
            count[3] += 1
for i in range(3):
    print(count[i],end = " ")
print(count[3])


Measured memory_bytes: 5604
S = input()
S_list = list(map(int, list(S)))
K = int(input())

S_set_under_K = set(S[:K])

if len(S) == 1:
    print(S)
elif len(S_set_under_K) == 1 and S_list[0] == 1:
    print(1)
else:
    for c in S:
        if c != "1":
            print(c)
            exit()


Measured memory_bytes: 3060
use proconio::input;

#[allow(unused_imports)]
use std::collections::HashSet;

use std::cmp;


fn main() {
    input! {
        n: usize,
        k: usize,
    }
    solve(n, k);
}


fn prepare(m: usize, k: usize, p :u64) -> Vec<Vec<u64>> {
    let mut v : Vec<Vec<u64>> = Vec::<Vec<u64>>::with_capacity(m + 1);
    let v0 : Vec<u64> = vec![1; 1];
    v.push(v0);
    for i in 1..m+1 {
        let jmax = cmp::min(i, k);
        let mut vi : Vec<u64> = vec![0; jmax+1];
        for j in 0..jmax+1 {
            vi[j] = 
            if j == 0 || j == i {
                1
            } else {
                (v[i-1][j-1] + v[i-1][j]) % p
            };
        }
        v.push(vi);
        
    }
    return v;
}

fn solve(n: usize, k: usize) {
    let p : u64 = (10u32.pow(9u32) + 7) as u64;

    // 1. Calculate values of combinations
    let m = cmp::max(k-1, n-k+1);
    let c = prepare(m, k, p);

    // 2. Calculate possible ways
    for i in 1..k+1 {
        let b = c[k-1][i-1];
        let r = if i > n-k+1 { 
            0
        } else {
            c[n-k+1][i]
        };
        let t = b * r % p;
        println!("{}", t);
    }
}


Measured memory_bytes: 17836
from sys import exit

def main():
  N = int(input())
  a = list(map(int,input().split()))
  index = -1
  num = 1
  
  for i in range(index+1, N):
    if a[i] != num:
      continue
    elif a[i] == num:
      index = i
      num += 1
      
  if index != -1:
    print(N-(num-1))
    exit()
      
  #indexに更新がなければ-1のまま
  print(index)
  
  
  
  
main()

Measured memory_bytes: 32376
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <utility>
#include <numeric>

using namespace std;
typedef long long llong;
typedef unsigned long long ullong;

const ullong MOD = 1000000000 + 7;

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

	int cnt = 0;
	for (int x = 0; x <= k; x++)
	{
		if (x > s)
		{
			break;
		}
		for (int y = 0; y <= k; y++)
		{
			if (x + y > s)
			{
				break;
			}
			else if (s - (x + y) <= k)
			{
				cnt++;
			}
		}
	}

	cout << cnt << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)n; i++)
const int MOD = 1000000007;
// long long a;
int main(){
  int a,b,c,d;
  cin >> a>>b>>c>>d;
  cout << max(a*b, c*d) << endl;
}


Measured memory_bytes: 256
N = int(input())

count = {}

for i in range(N):
    s = input()
    if s not in count:
        count[s] = 0
    count[s] += 1

max_count = max(count.values())

ans = []

for k, v in count.items():
    if v == max_count:
        ans.append(k)

ans = sorted(ans)

print('\n'.join(ans))



Measured memory_bytes: 35676
#include <stdio.h>
typedef long long int ll;
constexpr int kMod = int(1E9 + 7);
int a[30][30];
ll dp[30][1 << 21];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) if (a[i][j]) {
			for (int k = 0; k < (1 << n); k++) if ((1 << (j - 1)) & k) {
				dp[i][k] = (dp[i][k] + dp[i - 1][k ^ (1 << (j - 1))]) % kMod;
			}
		}
	
	}
	printf("%lld\n", dp[n][(1 << n) - 1]);
}


Measured memory_bytes: 345804
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  map<char, int> mp;
  string s;
  cin >> s;
  REP(i,s.size()){
    mp[s[i]]++;
  }
  bool ok = true;
  for(auto x: mp){
    if (x.second % 2 == 1)ok = false;
  }
  if(ok)cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,e,k;
	scanf("%d\n%d\n%d\n%d\n%d\n%d",&a,&b,&c,&d,&e,&k);
	if(e-a>k)
		printf(":(");
	else
		printf("Yay!");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int vertical, horizonal, work;
	
	fscanf(stdin, "%d %d", &vertical, &horizonal);
	while (vertical && horizonal) {
		while (0 < vertical--) {
			work = horizonal;
			while (0 < work--) fputc('#', stdout);
			fputc('\n', stdout);
	}
	fputc('\n', stdout);
	fscanf(stdin, "%d %d", &vertical, &horizonal);
	}


	return 0;
}

Measured memory_bytes: 576
using System;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        ulong a = ulong.Parse(Console.ReadLine());
        ulong[] s = Console.ReadLine().Split().Select(ulong.Parse).ToArray();
        Array.Sort(s);
        ulong ans = 0;
        for (ulong i = a * 3-2; i >=a; i--)
        {
            ans += s[i];
            i--;
        }
        Console.WriteLine(ans);
        Console.ReadLine();
    }
}





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

using namespace std;

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

	map<int,int> m;
	int n;
	cin >> n;
	int a;
	for (int i=0;i<n;i++){
		cin >> a;
		if (m[a] == 1){
			cout << "NO" << endl;
			return 0;
		} else {
			m[a] = 1;
		}
	}
	cout << "YES" << endl;
}


Measured memory_bytes: 9600
<?php

$N = trim(fgets(STDIN));
$N_array = trim(fgets(STDIN));
  
$pieces = explode(" ", $N_array);

$result = $pieces[0];

foreach($pieces as $k => $p) {
  if ($p == 0) {
   	echo 0;
    exit;
  }
}

foreach($pieces as $k => $p) {
  if($k == 0) {
    $result = $p;
  } else {
    if ((strlen($result)+ strlen($p)) > 20) {
     	echo "-1";
        exit;
    }
    $result = $result * $p;
  }
}

if ($result > 1000000000000000000) {
  echo "-1";
  exit;
}

echo $result;

Measured memory_bytes: 25668
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define pb push_back
using namespace std;
int dp[100001];
int n;
int solve(int *a, int s)
{
    if(s==0)
        return 0;
    if(s<0)
        return 1;
    if(dp[s]!=-1)
        return dp[s];
    for(int i=0;i<n;i++)
    {
        if(solve(a,s-a[i])==0)
            return dp[s]=1;
    }
    return dp[s]=0;
}
int32_t main()
{
    int t;
    //cin>>t;
    //while(t--)
    {   
        int k;
        cin>>n>>k;
        memset(dp,-1,sizeof(dp));
        int a[100001];
        for(int i=0;i<n;i++)
            cin>>a[i];
        if(solve(a,k))
            cout<<"First";
        else
            cout<<"Second";
    }
}






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

using namespace std;

int t[100];
int s[100];

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

	for (int i = 0; i < n; i++) cin >> t[i];

	sort(t, t + n, greater<int>());

	s[0] = t[0];
	for (int i = 1; i < n; i++) s[i] = t[i] + s[i - 1];

	int ans = c / a;

	for (int i = 1; i <= n; ++i) {
		ans = max(ans, (c + s[i - 1]) / (a + b * i));
	}

	printf("%d\n", ans);
}

Measured memory_bytes: 1164
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<vector<int> > a(n, vector<int>(n)); REP(i, n) REP(j, n) cin >> a[i][j];
  long long ans = 0;
  REP(i, n) FOR(j, i+1, n) {
    bool same = false;
    REP(k, n) if (k != i && k != j) {
      if (a[i][j] == a[i][k] + a[k][j]) same = true;
      else if (a[i][j] > a[i][k] + a[k][j]) {
        cout << -1 << '\n';
        return 0;
      }
    }
    if (!same) ans += a[i][j];
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int prim(void);
#define MAX 100
#define INFTY (1<<21)

int n;
int black=2,white=0,gray=1;
int A[MAX+1][MAX+1];

int prim(){
  int i,u,v,ans=0;
  int mincost;
  int d[MAX+1],p[MAX+1],color[MAX+1];

  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=white;
  }
  
  d[0]=0;
  
 while(1){ 
    mincost=INFTY;
    u=-1;
   for(i=0;i<n;i++){
      if(color[i]!=black && d[i]<mincost){
		u=i;
		mincost=d[i];
}}

    if(u==-1)break;
    color[u]=black;
    
   for(v=0;v<n;v++){if(color[v]!=black && A[u][v]!=INFTY){
     if(A[u][v]<d[v]){
      d[v]=A[u][v];
      p[v]=u;
      color[v]=gray;
     }
    }
   }}
 
 for(i=0;i<n;i++){
  if(p[i]!=-1)ans+=A[i][p[i]];}
  return ans;
 }

int main(){
  int i,j,e;
  scanf("%d", &n);
  for(i=0;i<n;i++){
  for(j=0;j<n;j++){
    scanf("%d", &e);
    A[i][j]=(e==-1)?INFTY : e;
  }}
  
  printf("%d\n", prim());
  return 0;

}



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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;


struct UnionFind
{
	vector<int> parent;
	vector<int> rank;

	UnionFind(int N) :parent(N, 0), rank(N, 0)
	{
		rep(i, 0, N)
		{
			parent[i] = i;
		}
	}

	int find(int x)
	{
		if (parent[x] == x)
		{
			return x;
		}
		else
		{
			return parent[x] = find(parent[x]);
		}
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (x == y)
		{
			return;
		}

		if (rank[x] < rank[y])
		{
			parent[x] = y;
		}
		else
		{
			parent[y] = x;
			if (rank[x] == rank[y])
			{
				rank[x]++;
			}
		}
	}

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

bool checked[100010];

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N, M;
	int x, y, z;
	cin >> N >> M;
	UnionFind uf(N);
	rep(i, 0, M)
	{
		cin >> x >> y >> z;
		uf.unite(x - 1, y - 1);
	}

	int ans = 0;
	rep(i, 0, N)
	{
		int p = uf.find(i);
		if (!checked[p])
		{
			checked[p] = true;
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

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

#define rng(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define urng(i, a, b) for(int i = int(b) - 1; i >= int(a); i--)
#define urep(i, b) urng(i, 0, b)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed

int main() {
  int n, a, b, ans = 0;
  string s;
  cin >> s;
  //vector<int> v(n), c(n);
  //if(1) {}
  //((a == b)? "Yes" : "No")
  for(int i = 0; i < s.size(); i++) cout << "x";
  cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>                 // [PRIMES]               1777 ~2^10.80
using namespace std;                     //                       10333 ~2^13.33
using ll = long long;                    // seq 1 128 | factor   100333 ~2^16.61
using vl = vector<ll>;                   //   | grep -v ' .* '  1300111 ~2^20.31
using vvl = vector<vl>;                  //                    10300777 ~2^23.30
using pll = pair<ll,ll>;                 //                   100400999 ~2^26.58
using vb = vector<bool>;                 //                  1300400999 ~2^30.28
const ll oo = 0x3f3f3f3f3f3f3f3fLL;      //                 10200500333 ~2^33.25
const double eps = 1e-9;                 //                100200400777 ~2^36.54
#define sz(c) ll((c).size())             //               1200300700111 ~2^40.13
#define all(c) begin(c),end(c)           //              10200300500777 ~2^43.21
#define mp make_pair                     //             100200300400777 ~2^46.51
#define mt make_tuple                    //            1200300400600999 ~2^50.09
#define pb push_back                     //           10200300400600111 ~2^53.18
#define eb emplace_back                  //          100200300400600333 ~2^56.48
#define xx first                         //         1200300400500800999 ~2^60.06
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (ll i=(a); i<(b); i++)
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)

ll n_flowers;
vl heights, values;
map<ll, ll> sequences;

int main() {
 
    cin >> n_flowers;
    heights.resize(n_flowers);
    values.resize(n_flowers);
    FOR(i, 0, n_flowers){
        cin >> heights[i];
    }
    FOR(i, 0, n_flowers){
        cin >> values[i];
    }

    sequences.emplace(heights[0], values[0]);
    FOR(curr_f, 1, n_flowers){
        ll i = curr_f;
        auto lower = sequences.lower_bound(heights[i]);
        auto next = lower;
        ll value_to_insert;
        if(sequences.begin()->first > heights[i]){
            //sequences.emplace(heights[i], value[i]);
            value_to_insert = values[i];
        }
        else{
            lower--;
            //next++;
            value_to_insert = lower->second + values[i];
            if(lower != sequences.end() && value_to_insert < lower->second ){
                //sequences.erase(lower);
                continue;
            }
        }
        while(next != sequences.end() && value_to_insert > next->second){
            sequences.erase(next);
            next = sequences.lower_bound(heights[i]); 
        }
        sequences.emplace(heights[i], value_to_insert);
    }


    ll maxi = values[0];
    for(auto tmp : sequences){
        maxi = max(maxi, tmp.second);
    }

   cout << maxi << endl;

    return 0;
}



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

int main() {
  int N,K;
  cin >> N >> K;
  int A = 1;
  
  for (int i = 0; i < (N + 1); i++) {
    int B = 1;
    for (int j = 0; j < i; j++) {
      B = 2*B;
    }
    B += (N -i)*K;
    
    if (i == 0)
      A = B;
    if (A > B)
      A = B;
    
    //cout << "A:" << A << "B:" << B << "mpl:"<< mpl << "i:" << i<<endl;
  }
  cout << A << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 1000000009
typedef long long ll;
typedef pair<int,int> P;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define int ll

signed main(void){
    int N;
    string S;
    int A=0,B=0;
    cin >> N >> S;
    REP(i,N){
        if(S[i]=='E'){
            A++;
        }else{
            B++;
        }
    }
    if(S[0]=='E'){A--;}else{B--;}
    int Ans=A;
    REP(i,N){
        if(i==0)continue;
        if(S[i-1]=='E'){A++;}else{B++;}
        if(S[i-1]=='E'){
            A--;B++;
        }else{
            A++;B--;
        }
        if(S[i]=='E'){A--;}else{B--;}
        Ans=min(Ans,A);
    }
    cout << Ans << endl;
  return 0;
}


Measured memory_bytes: 900
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef long double ld;

int main() {
	int N,A,B;
	cin >> N>>A>>B;
	cout << min(N*A,B)<<endl;

	return 0;
}

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

    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n=in.nextInt();
            String[] sList = new String[n];
            for(int i=0;i<n;i++)
                sList[i]=in.next();
            HashMap<String,Long> freqMap = new HashMap<>();
            for(int i=0;i<n;i++){
                char[] cur= sList[i].toCharArray();
                Arrays.sort(cur);
                String temp = new String(cur);
                if(!freqMap.containsKey(temp))
                    freqMap.put(temp,0L);
                freqMap.put(temp,freqMap.get(temp)+1);
            }   
            long ans=0;
            for(String x:freqMap.keySet())
                ans+=(1L*freqMap.get(x)*(freqMap.get(x)-1))/2;
            System.out.println(ans);
        }
    }

Measured memory_bytes: 53724
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int n;
	cin>>n;
	int s=0,m=n;
	while(n){
		s+=n%10;
		n/=10;
	}
	if(m%s==0) cout<<"Yes";
	else cout<<"No";
	return 0;
}


Measured memory_bytes: 256
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int S;
    cin >> S;
    int power = 1;
    for (int i = 0; i < 9; i++) power *= 10;

    int X1, X2, X3, Y1, Y2, Y3;
    X1 = 0;
    Y1 = 0;
    X2 = power;
    Y2 = 1;
    Y3 = (int)ceil(1.0 * S / power);
    X3 = power * Y3 - S;

    cout << X1 << " " << Y1 << " " << X2 << " " << Y2 << " " << X3 << " " << Y3 << endl;

    return 0;
}

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

#define ll long long
#define ld long double

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rrep(i, a, b) for(ll i = a; i >= b; --i)

#define pii pair<int, int>
#define pll pair<ll, ll>

#define fi first
#define se second

#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vpll vector<pll>

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

#define endl '\n'
using namespace std;
using namespace atcoder;

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

const ll MOD=10000007;//998244353
const ll INF=1e18;
const int inf=1e9;
const double PI=acos(-1);
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,-1,1,1,-1};
 
const int MAX=3e5+10;


int op(int a,int b){ return max(a,b);}
int e(){return 0;}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  
  segtree <int,op,e> dp(MAX);
  rep(i,n){
    int x = a[i];
    int now = dp.prod(max(x-k,0),min(x+k+1,MAX));
    dp.set(x,now+1);
  }
  int ans = dp.all_prod();
  
  cout << ans << endl;
                       
  return 0;
}


Measured memory_bytes: 9812
import java.util.Scanner;

import static java.lang.Character.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        String input = sc.nextLine();

        char[] output = new char[input.length()];

        for(int i = 0; i < input.length(); i++){
            if(isLowerCase(input.charAt(i)))
                output[i] = toUpperCase(input.charAt(i));
            else if(isUpperCase(input.charAt(i)))
                output[i] = toLowerCase(input.charAt(i));
            else output[i] = input.charAt(i);
        }

        System.out.println(output);

        sc.close();
    }
}



Measured memory_bytes: 25924
package main

import (
	"fmt"
	"sort"
)

type As [][]int

func (a As) Len() int {
	return len(a)
}

func (a As) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
}

func (a As) Less(i, j int) bool {
	return a[i][0] < a[j][0]
}

func main() {
	var n int
	fmt.Scan(&n)
	s := make(As, 0)
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		s = append(s, []int{a, i + 1})
	}
	sort.Sort(s)
	for i := range s {
		if i == len(s)-1 {
			fmt.Println(s[i][1])
		} else {
			fmt.Printf("%d ", s[i][1])
		}
	}
}


Measured memory_bytes: 15416
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include<sstream>
#include<limits.h>
using namespace std;
int main(void){
    int val[100001];
    int n,k;
    int minv = INT_MAX;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        val[tmp]++;
        if(minv > tmp) minv = tmp;
    }
    int ans = (n - val[minv]) / (k - 1);
    if(!((n - val[minv]) % (k - 1) == 0)) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
N,K = map(int,input().split())

list_A = [0]*N
ans = 0
d = []
A = []

for i in range(K):
    d.append(int(input()))
    A.append(list(map(int,input().split())))

list_A = [0]*N

for i in range(len(A)):
    for j in A[i]:
        list_A[j-1] += 1
        
for i in range(N):
    if list_A[i] == 0:
        ans += 1
        
print(ans)

Measured memory_bytes: 9204
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>


int main() {
    long long N, M;
    std::cin >> N >> M;
    std::vector<bool> broken(N + 1);
    for (long long i = 0; i < M; i++) {
        long long a;
        std::cin >> a;
        broken[a] = true;
    }
    std::vector<long long> dp(N + 1);
    dp[0] = 1;
    for (long long i = 1; i <= N; i++) {
        if (broken[i]) {
            dp[i] = 0;
        } else {
            if (i == 1) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] % 1000000007 + dp[i - 2] % 1000000007 ;
            }
        }
    }
    std::cout << dp[N ] % 1000000007 << std::endl;
    return 0;
}


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

const int MOD = 1e9 + 7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> dp(n + 1);
  dp[0] = 1;
  for (int i = 3; i <= n; i++) {
    for (int j = 3; j <= n; j++) {
      if (i - j >= 0) {
        dp[i] += dp[i - j];
        dp[i] %= MOD;
      }
    }
  }
  cout << dp[n] % MOD << '\n';
  return 0;
}

Measured memory_bytes: 3624