akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

void print_setprecision(int i, long double rsl) {
  cout << fixed << setprecision(i) << rsl << endl;
}

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

  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int rsl = 0;
  int tmp = k;
  rsl += min(k, a);
  tmp -= min(k, a);
  if(tmp <= 0) {
    cout << rsl << endl;
    return 0;
  }
  tmp -= min(tmp, b);
  if(tmp <= 0) {
    cout << rsl << endl;
    return 0;
  }
  rsl -= tmp;
  cout << rsl << endl;
}


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

int main(){
    int a[9];
    int n;
    int b[10];
    bool apr_flg[9];

    for(int i = 0; i < 9; i++){
        cin >> a[i];
    }
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    for(int i = 0; i < 9; i++){
        apr_flg[i] = false;
	for(int j = 0; j < n; j++){
	    if(a[i] == b[j]){
	        apr_flg[i] = true;
	    }
	}
    }

    string ans = "No";
    for(int i = 0; i < 3; i++){
        if(apr_flg[i] && apr_flg[i+3] && apr_flg[i+6]){
	    ans = "Yes";
	}
	if(apr_flg[i*3] && apr_flg[i*3+1] && apr_flg[i*3+2]){
		ans = "Yes";
	}	    
    }
    if(apr_flg[0] && apr_flg[4] && apr_flg[8]){
	ans = "Yes";
    }
    if(apr_flg[2] && apr_flg[4] && apr_flg[6]){
        ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    double w;
    while(cin >> w){
        if(w<=48.00){
            cout << "light fly\n";
            continue;
        }
        if(w<=51.00){
            cout << "fly\n";
            continue;
        }
        if(w<=54.00){
            cout << "bantam\n";
            continue;
        }
        if(w<=57.00){
            cout << "feather\n";
            continue;
        }
        if(w<=60.00){
            cout << "light\n";
            continue;
        }
        if(w<=64.00){
            cout << "light welter\n";
            continue;
        }
        if(w<=69.00){
            cout << "welter\n";
            continue;
        }
        if(w<=75.00){
            cout << "light middle\n";
            continue;
        }
        if(w<=81.00){
            cout << "middle\n";
            continue;
        }
        if(w<=91.00){
            cout << "light heavy\n";
            continue;
        }
        cout << "heavy\n";
    }
}

Measured memory_bytes: 1192
#include <iostream>
#include <vector>
#include <map>
#include <cmath>

int main(void) {
    long x;

    std::cin >> x;

    int n = 0;

    long div = x / 11;
    long mod = x % 11;

    if (mod == 0) {
        div = div*2;
    } else if (mod <= 6) {
        div = div*2+1;
    } else {
        div = div*2+2;
    }

    std::cout << div << std::endl;
}


Measured memory_bytes: 256
N,M = map(int, input().split())
H = [-1] + list(map(int, input().split()))

remain = [0] + [1]*N
for i in range(M):
    a,b = map(int, input().split())
    if H[a] > H[b]:
        remain[b] = 0
    elif H[a] < H[b]:
        remain[a] = 0
    else:
        remain[a],remain[b] = 0,0
print(sum(remain))

Measured memory_bytes: 19976
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

longs = []
edges = {}
def graph_DP(node_to, long):
    global longs
    if longs[node_to] != -1:
        return longs[node_to]
    else:
        nodes_next = edges[node_to]
        if not nodes_next:
            longs[node_to] = 0
            return 0
        else:
            long_max_t = 0
            for node_next in nodes_next:
                if longs[node_next] != -1:
                    long_max_t = max(long_max_t, longs[node_next] + 1)
                else:
                    long_max_t = max(long_max_t, graph_DP(node_next, 0) + 1)
            longs[node_to] = long_max_t
            return long_max_t

def main():
    global longs, edges
    n, m = map(int, input().split())
    edges = {e:set() for e in range(1, n + 1)}
    for _ in range(m):
        s, g = map(int, input().split())
        edges[s].add(g)
    longs = [-1] * (n + 1)

    for i1 in range(1, n + 1):
        if longs[i1] == -1:
            graph_DP(i1, 0)
    print(max(longs))

if __name__ == '__main__':
    main()


Measured memory_bytes: 134800
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		long[] height = new long[n];
		for(int i = 0; i < n; i++) {
			height[i] = s.nextLong();
		}
		s.close();
		String judge = "Yes";
		for(int i = n - 1; i > 0 ; i--) {
			if(height[i-1] > height[i]) {
				if(height[i-1] -1  > height[i]) {
				judge = "No";
				break;
				}else {
					height[i - 1]--;
				}
			}
		}
		System.out.println(judge);
	}

}


Measured memory_bytes: 52788
n=int(input())
a = list(map(int,input().split()))
i=0
b=0
while i<=n:
    b+=a[i]
    i+=1
i=0
x=1
ans=0
while i<=n:
    if a[i] <=x:
        if x<=b:
            ans+=x
            x=(x-a[i])*2
        else:
            ans+=b
            x = b
        b-=a[i]
    else:
        ans=-1
        break
    i+=1
print(ans)


Measured memory_bytes: 83432
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;

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

void solve() {
    int d,g;
    cin >> d >> g;
    VI p(d), c(d);
    REP(i,0,d) cin >> p[i] >> c[i];
    VVI dp(d, VI(d*100+1));
    REP(i,0,p[0]) dp[0][i] = 100 * i;
    dp[0][p[0]] = 100 * p[0] + c[0];
    REP(i,1,d) REP(j,0,d*100+1) {
        REP(k,0,p[i]) if (j - k >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-k] + (i + 1) * 100 * k);
        if (j - p[i] >= 0) dp[i][j] = max(dp[i][j], dp[i-1][j-p[i]] + (i + 1) * 100 * p[i] + c[i]);
    }

    /*
    REP(i,0,d) {
        REP(j,0,10) cerr << dp[i][j] << " ";
        cerr << endl;
    }
    */

    REP(i,1,d*100+1) if (dp[d-1][i] >= g) {
        cout << i << endl;
        return;
    }
}

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define ill long long
using namespace std;

int main() {
int a, b, c;
cin >> a >> b;
if(a > b) {
  cout << "safe";
} else {
  cout << "unsafe";
}
}


Measured memory_bytes: 3620
actions = []
while line = gets
  line.chomp!
  actions << line
end

inig = actions.shift.to_i
scores = []
score = 0
out = 0
rui = 0

while inig > 0
  action = actions.shift

  if action == "HIT"
    rui = rui + 1
  end
  if rui > 3
    score = score + 1
    rui = 3
  end
  if action == "HOMERUN"
    score = score + rui + 1
    rui = 0
  end

  if action == "OUT"
    out = out + 1
  end
  if out > 2
    inig = inig - 1
    out = 0
    scores << score
    score = 0
    rui = 0
  end

  if actions.count <= 0
    break
  end
end

scores.each {|s| puts "#{s}\n"}

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

int up(int a,int b){
	if (a%b==0){
		return a/b;
	}else {
		return a/b+1;
	}
}

int main () {
	int a, b;
	int c,d;
	cin >> a>>b>>c>>d;
	int n1 = up(a, d);
	int n2=  up(c, b);
	if (n1 >=n2){
		cout << "Yes";
	}else {
		cout << "No";
	}
}





Measured memory_bytes: 3636
#include <stdio.h>
#include <string.h>

int main()
{
  char wea[10];
  scanf("%s",wea);

  if(strcmp(wea,"Sunny")==0)
  {
      printf("Cloudy");
  }
  else if(strcmp(wea,"Cloudy")==0)
  {
      printf("Rainy");
  }
  else if(strcmp(wea,"Rainy")==0)
  {
      printf("Sunny");
  }

  return 0;

}

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

using namespace std;

int dp[101][10001];

int main() {
  int N,W;
  vector<int> v, w;
  cin>>N>>W;
  for (int i=0;i<N;++i) {
    int vv, ww;
    cin>>vv>>ww;
    v.push_back(vv);
    w.push_back(ww);
  }

  for (int i=w[0];i<=W;++i) {
    dp[0][i] = v[0];
  }

  for (int i=1;i<N;++i) {
    for (int j=0;j<=W;++j) {
      if (j-w[i] < 0) {
        dp[i][j] = dp[i-1][j];
      }
      else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
      }
    }
  }

  cout<<dp[N-1][W]<<endl;

  return 0;
}


Measured memory_bytes: 7080
/*
 * template.cpp
 *
 *  Created on: 2016/10/30
 *      Author: jin
 */
#define MYDEBUG
#include <iostream>
#include <vector>

#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#define LL long long
#define ULL unsigned long long
#define eps 1e-14
using std::max;
using std::min;
using std::swap;
using std::cout;
using std::cin;
using std::ostream;
using std::vector;
using std::endl;

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

class Main {
public:
  void sample() {
    cout << "-------------this is sample program.----------------" << endl;
  }
  void ABC047_A(){
	  int a,b,c;
	  cin >> a >> b >> c;
	  if(a==(b+c)) printf("Yes");
	  else if(b==(c+a)) printf("Yes");
	  else if(c==(a+b)) printf("Yes");
	  else printf("No");
  }
};


int main() {
	Main m;
	m.ABC047_A();
}


Measured memory_bytes: 256
x, y = map(int, input().split())

group_1 = {1, 3, 5, 7, 8, 10, 12}
group_2 = {4, 6, 9, 11}

if (x in group_1) and (y in group_1):
    print('Yes')
elif (x in group_2) and (y in group_2):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9076
import Control.Monad
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B
import qualified Data.Array.IArray as A
import qualified Data.IntMap.Strict as M

type Bound = (Vertex, Vertex)
type Vertex = Int
type Weight = Int
type Edge = ((Vertex, Vertex), Weight)
type Path = [Vertex]
type Graph = A.Array Vertex (S.Set (Vertex, Weight))

buildG :: Bound -> [Edge] -> Graph
buildG b = A.accumArray (flip S.insert) S.empty b . map (\((s, t), w) -> (s, (t, w)))

from :: Graph -> Vertex -> S.Set (Vertex, Weight)
from = (A.!)

size :: Graph -> Int
size g = let (i,j) = A.bounds g in j - i + 1

readDirectedEdge :: B.ByteString -> [Edge]
readDirectedEdge = map (constructOneWay . map readInt . B.words) . B.lines

constructOneWay :: [Int] -> Edge
constructOneWay [s,t,w] = ((s, t), w)
constructOneWay _ = undefined

readInt :: B.ByteString -> Int
readInt = maybe undefined fst . B.readInt

main :: IO ()
main = do
  [n,_] <- map read . words <$> getLine
  es <- readDirectedEdge <$> B.getContents
  let g = buildG (1, n) es
  putStrLn $ maybe "inf" show (score n g)

score :: Int -> Graph -> Maybe Weight
score n g = guard (im1 M.! n == im2 M.! n) >> return (im1 M.! n)
  where
    im1 = bellmanFord g 1
    im2 = _bellmanFord g (size g) im1

type Memo = M.IntMap Weight

bellmanFord :: Graph -> Vertex -> Memo
bellmanFord g s = _bellmanFord g n m0
 where
  n = size g
  m0 = M.singleton s 0

_bellmanFord :: Graph -> Int -> Memo -> Memo
_bellmanFord g n m
  | n == 0 = m
  | otherwise = _bellmanFord g (pred n) (M.foldrWithKey (move g) m m)

move :: Graph -> Vertex -> Weight -> Memo -> Memo
move g s aw m = S.foldr update m (from g s)
  where
    update (t, w) acc
      | M.notMember t acc || acc M.! t < aw + w = M.insert t (aw + w) acc
      | otherwise = acc

Measured memory_bytes: 2300
#include <bits/stdc++.h>
using namespace std;
// typedef
using ll  = long long;
using str = string;
using PL  = pair<ll, ll>;
using P   = pair<int, int>;
using VL  = vector<ll>;
using VI  = vector<int>;
using VS  = vector<str>;
using VP  = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using VVI = vector<VI>;

// const num
const ll INF         = 1e18 + 18;
const ll MAX         = 100005;
const ll MOD         = 1000000007;
const long double PI = acosl(-1.0);

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

// YesNo
#define Yes(n) cout << ((n) ? "Yes": "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
// All
#define ALL(v) v.begin(), v.end()
#define deduplicate(v) (v).erase(unique(ALL(d)), (v).end())

int main(void){
    str s;
    cin >> s;
    if(s.back()=='s'){
        cout << s << "es" << endl;
    }
    else{
        cout << s << "s" << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
from heapq import heappush, heappop
from collections import defaultdict

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

N = int(input())
V = list(range(1, N+1))
E = defaultdict(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a][b] = 1
    E[b][a] = 1
fen = dijkstra(V, E, 1)
sun = dijkstra(V, E, N)
black, white = 0, 0
for v in V:
    if fen[v] <= sun[v]: black += 1
    else: white += 1
print('Fennec' if black > white else 'Snuke')

Measured memory_bytes: 71196
#include<stdio.h>
int main()
{
    long long A,B,k;
    scanf("%llu%llu",&A,&B);

     k=((A+B)/2);
     if((A+B)%2==0)
     {
         printf("%llu\n",k);
     }
     else
     {
         printf("IMPOSSIBLE");
     }


    return 0;
}


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

public class Main{
	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		long[] A = new long[N];
		long buf,ave = 0,up = 0,down = 0;
		for(int i = 1; i <= N ;i++) {
			buf = scn.nextLong() - i;
			A[i-1] = buf;
			//ave += buf;
		}
		Arrays.sort(A);
		up = A[N/2];
		down = A[(N-1)/2];
		long ans1 = 0,ans2 = 0;
		for(int i = 0;i < N;i++) {
			ans1 += Math.abs(A[i]-up);
			ans2 += Math.abs(A[i]-down);
		}
		System.out.println(Math.min(ans1, ans2));
		scn.close();
	}
}


Measured memory_bytes: 86536
from collections import deque


N = int(input())
A = list(map(int, input().split()))
A.sort()
queue_plus = deque()
queue_minus = deque()
for A_i in A:
    if A_i < 0:
        queue_minus.append(A_i)
    else:
        queue_plus.append(A_i)

xy = [[] for _ in range(N-1)]
cnt = 0
if len(queue_plus) == 0:
    x = queue_minus.pop()
    y = queue_minus.pop()
    xy[cnt] = [x, y]
    cnt += 1
    queue_plus.append(x - y)
elif len(queue_minus) == 0:
    x = queue_plus.popleft()
    y = queue_plus.popleft()
    xy[cnt] = [x, y]
    cnt += 1
    queue_minus.append(x - y)
while len(queue_plus) > 0 and len(queue_minus) > 1:
    x = queue_plus.pop()
    y = queue_minus.pop()
    xy[cnt] = [x, y]
    cnt += 1
    queue_plus.append(x - y)
while len(queue_plus) > 1 and len(queue_minus) > 0:
    x = queue_minus.pop()
    y = queue_plus.pop()
    xy[cnt] = [x, y]
    cnt += 1
    queue_minus.append(x - y)
if len(queue_plus) + len(queue_minus) == 1:
    if len(queue_plus) > 0:
        print(queue_plus.pop())
    else:
        print(queue_minus.pop())
else:
    x = queue_plus.pop()
    y = queue_minus.pop()
    xy[cnt] = [x, y]
    ans = x - y
    print(ans)
for x_y in xy:
    print(" ".join(map(str, x_y)))


Measured memory_bytes: 71124
#include <bits/stdc++.h>
#define LL long long
#define FASTER ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
map <LL, int> mp;
map <LL, int> :: reverse_iterator rt;
int main()
{
    FASTER;

    LL valu;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> valu;
        mp[valu]++;
    }
    LL x = 0, Max = 0;
    for(rt = mp.rbegin(); rt != mp.rend(); rt++){
        if(mp[rt->first] >= 4){
            Max = max(rt->first * rt->first, Max);
        }
        if(!x && mp[rt->first] >= 2){
            x = rt->first;
        }
        else if(x && mp[rt->first] >= 2){
            Max = max(rt->first * x, Max);
            x = 0;
        }
    }
    cout << Max << "\n";
    return 0;
}


Measured memory_bytes: 6528
n = int(input())
graph = [dict() for _ in range(n)]

for i in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a - 1][b - 1] = c
    graph[b - 1][a - 1] = c

q, k = map(int, input().split())
xy = []
for i in range(q):
    x, y = map(int, input().split())
    xy.append([x-1, y-1])
depth = [0 for _ in range(n)]
prev = [False for _ in range(n)]
depth[k-1] = 0

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(now, graph, depth, prev):
    if len(graph[now]) == 0 or prev[now]:
        return
    prev[now] = True
    for k, v in graph[now].items():
        if not prev[k]:
            depth[k] += depth[now] + v
            dfs(k, graph, depth, prev)
    return depth


depth = dfs(k-1, graph, depth, prev)
for x, y in xy:
    print(depth[x] + depth[y])


Measured memory_bytes: 163920
n,x=gets.chomp.split(" ").map(&:to_i)
d=gets.chomp.split(" ").map(&:to_i).map{|a|(a-x).abs}.sort
ans=0
max_d=d.min
stop=false
@yaku_arr=[]
def yaku(num)
  n=1
  while n**2<num do
    if num%n==0 then
      @yaku_arr.push(n,num/n)
    end
    n+=1
  end
  return @yaku_arr.sort.reverse
end
a=yaku(max_d)

k=1
while !stop do
  for i in 0..(n-1) do
    stop=true
    if d[i]%max_d!=0 then
      stop=false
      break
    end
  end
  if !stop then
    max_d=a[k]
    k+=1
  end
end
p max_d

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

int main(){
	ll H,N;
	cin >> H >> N;
	vector<int> A(N);
	rep(i,N){
		cin >> A[i];
	}
	sort(A.begin(),A.end());
	reverse(A.begin(),A.end());
	
	bool ok = false;
	
	rep(i,N){
		H -= A[i];
		if(H <= 0){
			ok = true;
		}
	}
	
	if(ok){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	
	
    return 0;
}




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

int main(){
  ll n;
  cin>>n;
  n--;
  stack<char> ans;
  while(n>=0){
    ans.push(n%26+'a');
    n/=26;
    n--;
  }
  while(!ans.empty()){
    char a=ans.top();
    ans.pop();
    cout<<a;
  }
  cout<<endl;
}


Measured memory_bytes: 3632
fn main() {
    let mut s = read::<String>().chars().collect::<Vec<char>>();
    s.sort();
    let s2 = s.into_iter().collect::<String>();
    yn(s2 == "abc");
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int first_bit = s[0] - '0';
    vi nums(n);
    int m = 0;
    s += 'p'; // padding bit
    repeat(i, 1, n + 1) {
        int num = 1;
        while (s[i] == s[i - 1]) {
            num++;
            i++;
        }
        nums[m] = num;

        // debug(m);
        // debug(nums[m]);
        m++;
    }

    vl accum(m + 1, 0);
    accum[0] = nums[0];
    repeat(i, 1, m) {
        accum[i] = accum[i - 1] + nums[i];

        // debug(i);
        // debug(accum[i]);
    }

    ll ans = 0;
    rep(i, m) {
        int bit;
        if (i % 2 == 0) {
            bit = first_bit;
        } else {
            if (first_bit == 0) {
                bit = 1;
            } else {
                bit = 0;
            }
        }
        if (bit) {
            ans = max(ans, accum[min(m - 1, 2 * k + i)] - (i - 1 < 0 ? 0 : accum[i - 1]));
        } else {
            ans = max(ans, accum[min(m - 1, 2 * k - 1 + i)] - (i - 1 < 0 ? 0 : accum[i - 1]));
        }
        // debug(bit);
        // debug(ans);
    }
    out(ans);
    return 0;
}


Measured memory_bytes: 1664
import Control.Applicative
import Control.Monad
import Data.List

f :: Int -> Int -> Int
f a b = (a - b) ^ 2

main :: IO ()
main = do
    n <- readLn :: IO Int
    as <- sort . fmap read . words <$> getLine :: IO [Int]
    let k = length as
    let a1 = sum as `div` k
    let a2 = (sum as + (k - 1)) `div` k
    let ans = min (sum $ fmap (f a1) as) (sum $ fmap (f a2) as)
    print ans

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
#define M (50000)
bool isp[M];
int like[M];
int main(){
  int Q;
  cin>>Q;
  isp[0]=false;
  for(int i=1;i<M;++i)isp[i]=true;
  for(int i=0;i<M;++i){
    int p=i*2+1;
    if(isp[i]){
      for(int q=3*p;q<=2*M;q+=2*p){
        isp[(q-1)/2]=false;
      }
    }
  }
  like[0]=0;
  for(int i=1;i<M;++i){
    like[i]=like[i-1];
    if((i==1)||(isp[i]&&!(i%2)&&isp[i/2]))like[i]++;
  }
  for(int i=0;i<Q;++i){
    int l,r;
    cin>>l>>r;
    l=(l-1)/2,r=(r-1)/2;
    cout<<like[r]-(l?like[l-1]:0)<<endl;
  }
  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define int long long
#define mod 1000000007


double solve1(double* p, vector<vector<double>> &dp, int i, int x) {
	if (dp[i][x] > -0.9)return dp[i][x];
	return dp[i][x] = p[i] * solve1(p, dp, i - 1, x - 1) + (1 - p[i]) * solve1(p, dp, i - 1, x);
}

void solve() {
	int n;
	cin >> n;
	double p[n + 1];
	int i;
	for (i = 1; i <= n; i++)cin >> p[i];
	vector<vector<double>> dp(n + 1, vector<double>(n + 1));
	int j;
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n; j++)dp[i][j] = -1;
	}

	dp[0][0] = 1;
	for (i = 1; i <= n; i++)dp[i][0] = 1;
	for (i = 1; i <= n; i++)dp[0][i] = 0;

	double len = solve1(p, dp, n, (n + 1) / 2);
	cout << fixed << setprecision(10) << len << endl;
	return;
}


int32_t main() {
	std::ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	solve();
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> cnt(n, 0);
  rep(i, n - 1) {
    int ai;
    cin >> ai;
    cnt[ai - 1]++;
  };

  rep(i, n) cout << cnt[i] << endl;

  return 0;
}

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

#define endl '\n'
#define ll long long
#define int long long
#define re register
#define pb(x) push_back(x)
#define ce(x) cout << x << '\n';

#define db  long double;
#define pll pair < ll, ll >;
#define scan(a, n) 		for(int i = 0; i < n; i++)cin >> a[i];

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
#define infl LLONG_MAX

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 
ll f[200009];

int32_t main() {
	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t, i, x, j, y, 	m, z, k, n;
	cin >>  n;
	ll a[n];
	// scan(a, n);
	rep(i, 0, n - 1, 1)	{
		cin >> a[i];
		a[i]--;
		f[a[i]]++;
	}

	rep(i, 0, n, 1) ce(f[i])

	// if (m < 0)	m = -1;
	// ce(m)
	// cout_p((44 * n) / 7.0, 6);
}


Measured memory_bytes: 6780
// ~zaletaet~

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#define fi first
#define se second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const ll N = 1e5 + 123, MOD = 1e9 + 7, oo = 1e9 + 9, INF = 1e18 + 9;
const double EPS = 1e-9, PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    int h, w;
    cin >> h >> w;

    array<array<int, 510>, 510> a;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        cin >> a[i][j];
    }

    vector<array<int, 4>> ans;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j + 1 < w; j++) {
            if (a[i][j] & 1) {
                a[i][j]--;
                a[i][j + 1]++;
                ans.pb({i, j, i, j + 1});
            }
        }
    }
    for (int i = 0; i + 1 < h; i++) {
        if (a[i][w - 1] & 1) {
            a[i][w - 1]--;
            a[i + 1][w - 1]++;
            ans.pb({i, w - 1, i + 1, w - 1});
        }
    }
    cout << sz(ans) << '\n';
    for (auto i: ans) {
        cout << i[0] + 1 << ' ' << i[1] + 1 << ' ' << i[2] + 1 << ' ' << i[3] + 1 << '\n';
    }

    return 0;
}

/*
  Raise your standard.
*/

Measured memory_bytes: 5232
import sys
readline = sys.stdin.readline

def main():
    A, B = map(int, readline().rstrip().split())
    ans = 0
    for i in range(A, B+1):
        if str(i) == str(i)[::-1]:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

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

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 50;
const int MAX_K = 6;

int N, M;
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], p[MAX_N+1], up[MAX_N+1][MAX_K+1];

void dfs(int x){
	up[x][0] = p[x];
	for(int i=1; i<MAX_K; i++){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(int i : gp[x]){
		if(i==p[x])	continue;
		lv[i] = lv[x]+1;
		p[i] = x;
		dfs(i);
	}
}

int lca(int x, int y){
	for(int i=MAX_K-1; i>=0; i--){
		if(lv[up[x][i]]>=lv[y])	x = up[x][i];
		if(lv[up[y][i]]>=lv[x])	y = up[y][i];
	}
	if(x==y)	return x;
	for(int i=MAX_K-1; i>=0; i--){
		if(up[x][i]!=up[y][i]){
			x = up[x][i];
			y = up[y][i];
		}
	}
	return up[x][0];
}

vector<pii> vt;
vector<pii> v;

ll two[MAX_N+1];
ll ans;
int cnt;
int dp[MAX_N+1];

void dfs2(int x){
	for(int j : gp[x]){
		if(j==p[x])	continue;
		dfs2(j);
		dp[x]+=dp[j];
	}
	//cout<<"*"<<x<<" "<<dp[x]<<endl;
	if(x!=1 && dp[x]==0)	cnt++;
}

void calc(int x){
	if(x==vt.size()){
		for(int i=1; i<=N; i++)	dp[i] = 0;
		for(pii p : v){
			int l = lca(p.first, p.second);
			dp[p.first]++;
			dp[p.second]++;
			dp[l]-=2;
		}
		cnt = 0;
		dfs2(1);
		//cout<<cnt<<" "<<v.size()<<endl;
		if(v.size()%2){
			ans-=two[cnt];
		}else{
			ans+=two[cnt];
		}
		return;
	}else{
		v.pb(vt[x]);
		calc(x+1);
		v.pop_back();
		calc(x+1);
	}
}

int main(){
	scanf("%d", &N);
	two[0] = 1;
	for(int i=1; i<=N; i++)	two[i] = two[i-1]*2LL;
	for(int i=1; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	}
	scanf("%d", &M);
	lv[1] = 1; dfs(1);
	for(int i=1; i<=M; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		vt.pb({a, b});
	}
	calc(0);
	cout<<ans;
	return 0; 
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;

typedef long long ll;
ll MOD = 1e9+7;

double dp[3000][3000];//dp[i][j]...コインをi枚投げたときに表がj枚出ている確率
double p[3001];

int main()
{
	int n;
	double ans=0;
	cin>>n;
	for(int i=1;i<n+1;i++)
		cin>>p[i];
	
	fill(dp[0],dp[3000],0.0f);
	dp[1][1]=p[1];
	dp[1][0]=1.0f-p[1];
	//ここからDP
	for(int i=2;i<n+1;i++)
	{
		for(int j=0;j<=i;j++)
		{
			dp[i][j]=dp[i-1][j]*(1.0f-p[i]);
			if(j!=0)
				dp[i][j]+=dp[i-1][j-1]*p[i];
		}
	}
	//ここまでDP

	for(int i=n/2+1;i<=n;i++)
		ans+=dp[n][i];
	cout<<fixed<<setprecision(12)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 70528
#!/usr/bin/env python3
n = int(input())
a = [0]
a += [int(input()) for i in range(n)]

cnt = 0
ps = 1

for _ in range(1, n + 1):
    ps = a[ps]
    cnt += 1

    if ps == 2:
        print(cnt)
        break
else:
    print(-1)


Measured memory_bytes: 13812
#include <stdio.h>
#include <stdlib.h>

bool DP[80][80][(80+80)*80];
int main()
{
	int A1, A2, A3;
	scanf("%d %d %d", &A1, &A2, &A3);
	if(A1 + A2 + A3 >= 22){
		printf("bust\n");
	}else{
		printf("win\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int n;
    cin >> n;
    ll m = 0;
    while(m * (m - 1) / 2 < n) ++m;
    if (m * (m - 1) / 2 != n) {
        cout << "No" << endl;
        return 0;
    }
    vector<vector<int>> ans(m+1);
    int num = 1;
    for (int i = 1; i <= m; ++i) {
        for (int j = i + 1; j <= m; ++j) {
            ans[i].push_back(num);
            ans[j].push_back(num);
            ++num;
        }
    }
    cout << "Yes" << endl;
    cout << m << endl;
    for (int i = 1; i <= m; ++i) {
        cout << (int)(ans[i].size());
        for (int x: ans[i]) {
            cout << " ";
            cout << x;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 4336
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
      	int K = sc.nextInt();
      	int Q = sc.nextInt();
      	int i = 0;
      	int A[] = new int[Q];
      	int Count[] = new int[N + 1];
        Arrays.fill(Count, 0);
      	for(i = 0;i < Q;i++){
          A[i] = sc.nextInt();
          Count[A[i]] += 1 ;
        }
      	for(i = 1;i <= N;i++){
          if(K - Q + Count[i] >= 1){
             System.out.println("Yes");            
          }
          else{
             System.out.println("No");
          }
        }  	
    }
}

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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  int n,k;
  const int max_n = 1e5;
  int a[max_n + 1];
  int pos;
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    if(a[i] == 1) pos = i;
  }
  
  int s = pos - k + 1;
  int e = pos + k - 1;

  int ans = INF;
  int cnt;
  for(int i = s; i <= e; i++){
    int ss = i;
    int ee = ss + k - 1;
    if(ss < 0) continue;;
    if(ee > n-1) continue;
    int left_leng = ss;
    int right_leng = n - 1 - ee;
    int left_cnt = left_leng / (k - 1);
    int right_cnt = right_leng / (k - 1);
    // cout << "ss, ee = " << ss << "," << ee << endl;
    // cout << "l, r = " << left_leng << "," << right_leng << endl;
    if(left_leng % (k-1) != 0) left_cnt ++;
    if(right_leng % (k-1) != 0) right_cnt ++;
    cnt = 1 + left_cnt + right_cnt;
    ans = min(ans, cnt);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4016
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
using namespace std;
int main() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; i++) {
		cout << 'x';
	}
	cout << endl;
	return 0;
}






Measured memory_bytes: 256
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
#include <vector>
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define base10_4 10000      //1e4
#define base10_5 100000     //1e5
#define base10_6 1000000    //1e6
#define base10_7 10000000   //1e7
#define base10_8 100000000  //1e8
#define base10_9 1000000000 //1e9

#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

vll A;
ll B;
ll C;
ll N;
ll M;
ll K;

ll ltmp;
string stmp;
double dtmp;

int main(){

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

    cin >> N;
    rep(ni,N){
        cin >> ltmp;
        A.push_back(ltmp);
    }
    /*
    N=200000;
    rep(ni,N){
        A.push_back(ni/10000);
    }
    */

    ll cnt = 0;
    ll target_index = 1;
    rep(ai,A.size()){
        if(A[ai]==target_index){
            target_index++;
        }else{
            cnt++;
        }
    }
    if(target_index==1) cout << -1 << endl;
    else    cout << cnt << endl;


}

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

int main(void) {
  int n, q;
  string s;
  cin
    >> n >> q
    >> s;
  vector<int> l(q);
  vector<int> r(q);
  vector<int> sum(n + 1);
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> r[i];
  }

  sum[0] = 0;
  sum[1] = 0;
  for (int i = 1; i < n; i++) {
    if (s[i - 1] == 'A' && s[i] == 'C') {
      sum[i + 1] = sum[i] + 1;
    } else {
      sum[i + 1] = sum[i];
    }
  }

  for (int i = 0; i < q; i++) {
    int result = sum[r[i]] - sum[l[i]];
    cout << result << endl;
  }

  return 0;
}

Measured memory_bytes: 4520
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <algorithm>
#include <functional>
#include <utility>
#include <string>
#define typeof(x) __typeof__(x)
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define ceil(x,m) ((x)+(m)-1)/(m)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

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

signed main()
{
   int N; cin >> N;
   vec<int> A(N), B(N);
   rep(i, 0, N) {
      cin >> A[i] >> B[i];
   }

   vec<P> X(2*N);
   rep(i, 0, N) {
      X[i] = MP(A[i], i);
      X[N+i] = MP(B[i], N+i);
   }

   SORT(X);

   int sum = 0;
   vec<bool> used(2*N, false);
   rep(i, 0, N) {
      sum += X[i].first;
      used[X[i].second] = true;
   }

   bool pair_used = false, A_used = false, B_used = false;
   rep(i, 0, N) {
      if (used[i] && used[N+i]) {
         pair_used = true;
      } else if (used[i]) {
         A_used = true;
      } else if (used[N+i]) {
         B_used = true;
      }
   }

   if (pair_used || !(A_used && B_used)) {
      cout << sum << endl;
   } else {
      int min_diff = INF;
      for (int i = 0; i < N; i++) {
         int MAX = max(A[i], B[i]);
         if (i == X[N-1].second % N) {
            min_diff = min(min_diff, MAX - X[N-2].first);
         } else {
            min_diff = min(min_diff, MAX - X[N-1].first);
         }
      }
      cout << sum + min_diff << endl;
   }

   return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define iter(it,a) for(auto it=a.begin();it!=a.end();it++)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define preturn(X) cout<<X<<endl; return 0
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//cout.setf(ios::fixed); cout.precision(18)
 
const int N = 200000+10;
string s;
int n;
int val[N];
map<int,int> x;
int dp[N];
 
int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    cin>>s;
    n = s.size();
    dp[0] = 0;
    x[0] = 0;
    val[0] = 0;
    rep(i,1,n+1){
        val[i] = val[i-1]^(1<<(s[i-1]-'a'));
        dp[i] = dp[i-1]+1;
        if(val[i]==0){
            dp[i] = 1;
        }
        rep(j,0,26){
            int temp = val[i]^(1<<j);
            if(temp==0){
                dp[i] = 1;
            }
            else if(x[temp]!=0){
                dp[i] = min(dp[i],dp[x[temp]]+1);
            }
        }
        x[val[i]] = i; 
    }
    preturn(dp[n]);
}

Measured memory_bytes: 205844
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
 
#define mo 1000000007
#define inf 1e18
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rrep(i,s,n) for(ll i=s;i>=n;i--)

ll mod(ll n) { return (n % (ll)mo + (ll)mo)%(ll)mo;}
vector<ll> adj[200005];
vector<bool> vis(200005,0);
ll cnt;
void dfs(ll u){
	cnt++;
	vis[u] = 1;
	for(auto v : adj[u]){
		if(!vis[v]) dfs(v);
	}
}


int main(){
	ll n,m;
	cin>>n>>m;
	rep(i,0,m){
		ll u,v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	ll ans = -inf;
	rep(i,1,n+1){
		cnt = 0;
		if(!vis[i]){
			dfs(i);
			ans = max(ans,cnt);
		}
	}
	cout<<ans;
	
}

Measured memory_bytes: 20668
#include <iostream>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> L;
	int l;
	
	for (int i = 0; i < n; i++) {
		cin >> l;
		L.push_back(l);
	}
	int a, b, c, cnt = 0;
	for (int i = 0; i < n-2; i++) {
		a = L[i];
		for (int j = i+1; j < n-1; j++) {
			b = L[j];
			if (a == b) continue;
			for (int k = j+1; k < n; k++) {
				c = L[k];
				if (a == c || b == c) continue;
				if ((a + b > c) && (b + c > a) && (c + a > b)) {
					cnt++;
				}
			}
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
#define INF 10000000000000LL
#define DIM 100007
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update> myset;
typedef  pair< long long, pair<long long, long long> > ppll;
ll n,m,c,x,x2,y2,e,h,k,res1,a1,a2,w,a3,y,z,a4,a5,a6,last,LL,timer,start,finish,maxmask,newmax,reslast,tests,police,brothers;
string s,s1;
ll al,ar;
ll mas[100007],dp[100007];
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>mas[i];
    }
    dp[1]=0;
    dp[2]=abs(mas[1]-mas[2]);
    for(int i=3;i<=n;i++){
        dp[i]=min(dp[i-2]+abs(mas[i]-mas[i-2]),dp[i-1]+abs(mas[i]-mas[i-1]));
    }
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read() {
	int x = 0, f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-')  f = -1; ch = getchar();}
	while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x * f;
}
map<int, int> mp;
int cnt, ccnt, ori, xh[100005];
signed main() {
	int n = Read(), x = ori = Read(), m = Read();
	if(n <= m + 1) {
		int ans = 0;
		for(int i = 1; i <= n; i++)
			ans += x, x = x * x % m;
		cout << ans << endl;
		return 0;
	}
	for(int i = 1; ; i++) {
		if(mp[x]) {ccnt = i - 1; cnt = mp[x]; break;}
		mp[x] = i;
		x = x * x % m;
	}
	x = ori; int ans = 0, sum = 0;
	for(int i = 1; i <= ccnt; i++) {
		if(i < cnt)  ans += x;
		else  xh[i - cnt + 1] = x, sum += x;
		x = x * x % m;
	}
	n = n - cnt + 1;
	int div = n / (ccnt - cnt + 1), md = n % (ccnt - cnt + 1);
	ans += div * sum;
	for(int i = 1; i <= md; i++)  ans += xh[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7096
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
const ll M = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int ans = 0;
  rep(i, n) {
    cin >> a[i];
    if ((i+1) % 2 == 1 && a[i] % 2 == 1) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
///Astalavista Code........~CodeSlayer007
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define Br cout<<endl
#define int long long
#define fe first
#define se second
#define double long double
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define PT(x) cout << (x) << endl
#define last(x)  prev(x.end())
#define PTT(x) cout << (#x) << " is " << (x) << endl
#define lets_go ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int M = 1e9 + 7;
const int N = 2e5 + 10;
const int IM = 1e15 + 37;
const double PI = 3.1415926535897932384;
inline void PP(int n) { cout << n << " ";}
void PV(vi v) { for (int i = 0 ; i < v.size() ; i++) cout << v[i] << " " ; cout << endl;}
void PVV(vii v) {for (int i = 0 ; i < v.size() ; i++) cout << v[i].first << " " << v[i].second << endl;}
void PA(int v[], int n, int x = 0) { for (int i = x ; i < n + x; i++)cout << v[i] << ' ' ; cout << endl;}
void IN(int a[], int n, int x = 0) {for (int i = x; i < n + x; i++)cin >> a[i];}
inline void op() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
// <=================================================================================================================================
// <=================================================================================================================================

int n, w;
int a[500], b[500];
int dp[200][N];

signed  main() {
    //op();
    lets_go

    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - a[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i]);
            }
        }
    }
    int ans = dp[n][w];
    PT(ans);




    /**/
    return 0;
}

Measured memory_bytes: 82068
n=int(input())
as_=list(map(int,input().split()))
bs=list(map(int,input().split()))
cs=list(map(int,input().split()))
p=sum(bs)+sum([cs[a-1] for a,a_ in zip(as_,as_[1:]) if a+1==a_])
print(p)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s1,s2;
    cin>>s1>>s2;
    int n1 = s1.length();
    int n2 = s2.length();
    if(s1==s2.substr(0,n1) && n2 == (n1+1)){
           cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3624
/**
 *    author:  tourist
 *    created: 29.09.2018 15:26:49       
**/
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  map<int,int> mp[2];
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    mp[i & 1][x]++;
  }
  vector<pair<int,int>> v[2];
  for (int u = 0; u < 2; u++) {
    for (auto &p : mp[u]) {
      v[u].emplace_back(p.second, p.first);
    }
    if (v[u].size() == 1) {
      v[u].emplace_back(0, -1);
    }
    sort(v[u].rbegin(), v[u].rend());
  }
  int ans = 0;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      if (v[0][i].second != v[1][j].second) {
        ans = max(ans, v[0][i].first + v[1][j].first);
      }
    }
  }
  cout << n - ans << '\n';
  return 0;
}

Measured memory_bytes: 8912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 7;
const double pi = acos(-1);
const int mod = 998244353;
const double eps = 1e-8;

int main(){     	
	int n,m;
	scanf("%d %d",&n,&m);
	cout << n*(n-1)/2+m*(m-1)/2<<endl; 
    return 0;
}


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

#pragma warning(disable: 4996)

#define MAX_N 500000

int v[MAX_N], dp[MAX_N + 7];

int main()
{
	register int N, C = 0;

	scanf("%d", &N);

	dp[N] = 1;

	for (int i = (N + 2) / 2; i > 1; i--)
	{
		dp[i] = dp[2 * i - 1] + 2 * dp[2 * i] + dp[2 * i + 1];
	}

	for (int i = 2; i <= N; i++)
	{
		C += dp[i] * i;
	}

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &v[i]);
	}

	std::sort(v, v + N);

	for (int i = 0; i < N; i++)
	{
		if (i) { printf(" "); }

		printf("%d", v[i]);
	}

	printf("\n");

	printf("%d\n", C);

	return 0;
}

Measured memory_bytes: 5668