akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)
#define repa(i,n) for (auto& i: n)

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}

#ifdef DEBUG
template <class T, class N> void verr(const T& a, const N& n) { rep(i, n) cerr << a[i] << " "; cerr << "\n" << flush; }
ll dbgt = 1; void err() { cerr << "passed " << dbgt++ << "\n" << flush; }
template<class H, class... T> void err(H&& h,T&&... t){ cerr<< h << (sizeof...(t)?" ":"\n") << flush; if(sizeof...(t)>0) err(forward<T>(t)...); }
#endif

const ll INF = 4e18;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
//--------------------------------------------------------------------------------//

int main() {
    init();
    string s, t;
    cin >> s >> t;
    ll ans = 0;
    rep(i, s.size()) if (s[i] != t[i]) ans++;
    cout << ans << endl;
}

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

int main(){
  int a,b;
  cin>>a>>b;
  if(a<b){
    cout<<"a < b"<<endl;
  }else if(a>b){
    cout<<"a > b"<<endl;
  }else if(a==b){
    cout<<"a == b"<<endl;
  }
  return 0;
}



Measured memory_bytes: 3048
N = int(input())
B = list(map(int,input().split()))
A = [0 for _ in range(N)]
ans = B[0]
for i in range(N-2):
    if B[i] < B[i+1]:
        A[i+1]= B[i]
    elif B[i] > B[i+1]:
        A[i+1]=B[i+1]
    else:
        A[i+1]= B[i]
ans += sum(A)
ans += B[N-2]
print(ans)

Measured memory_bytes: 3064
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int n) { return n & 1; }
constexpr bool even(const int n) { return ~n & 1; }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

int gcd(int a, int b) {
  while (b) a %= b, std::swap(a, b);
  return a;
}

main {
  while (true) {
    string s;
    cin >> s;
    if (s == "#") break;
    reverse(all(s));
    bool f = true;
    pair<int, int> p(0, 1);
    for (auto &c : s) {
      if (c == 'n') {
        p.first = p.first * 2 - 90;
        p.second *= 2;
        if (f) p = {0, 1}, f = false;
      }
      if (c == 'w') {
        p.first = p.first * 2 + 90;
        p.second *= 2;
        if (f) p = {90, 1}, f = false;
      }
    }
    int g = gcd(p.first, p.second);
    p.first /= g;
    p.second /= g;
    cout << p.first;
    if (p.second > 1) cout << '/' << p.second;
    cout << endl;
  }
}



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

using namespace std;

void Minimization()
{
  int n;
  int k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }

  int ans = 1;
  int r = n - k;
  while (r > 0)
  {
    ans++;
    r = r - (k - 1);
  }
  
  cout << ans << endl;
  return;
}

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

Measured memory_bytes: 640
N, Q = [int(v) for v in input().split()]
S = input()

cnt_list = [0] * len(S)
i = 0
for i in range(1, len(S)):

    cnt_list[i] = cnt_list[i - 1]
    if S[i - 1] == 'A' and S[i] == 'C':
        cnt_list[i] += 1

# print(cnt_list)
for i in range(Q):
    l, r = [int(v) for v in input().split()]
    print(cnt_list[r-1] - cnt_list[l-1])


Measured memory_bytes: 6188
#include <bits/stdc++.h>
#define REP(i, n) for (long long i = 0; i < (long long)n; i++)
//#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Vl = vector<ll>;
using vi = vector<int>;
using Graph = vector<vi>;

#define EPS 1e-3

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(15);  //"for float-base
  // problem"
  ll A;
  long double B;
  cin >> A >> B;

  B = B * 100;
  B += EPS;
  int b = (int)B;
  ll C = A * b;
  C = C / 100;

  cout << C << endl;
}

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

int main()
{
	string s,t;
	cin>>s>>t;
	char ar[2*(s.length())];
	for(int i=0;i<2*(s.length());i++)
	{
	    ar[i]=s[i%(s.length())];
	}
	for(int i=0;i<s.length();i++)
	{
	    int fl=0;
	    for(int j=i;j<i+s.length();j++)
	    {
	        if(ar[j]!=t[j-i]){fl=1;break;}
	        
	    }
	    if(fl==0){cout<<"Yes\n";return 0;}
	}
	cout<<"No\n";
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using bint = boost::multiprecision::cpp_int;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    string S;
    cin >> S;
    int N = S.length();
    bool ret = true;
    rep(i,N) {
        if (S[i] != S[N-1-i]) {
            ret = false;
            break;
        }
    }
    rep(i,(N-1)/2) {
        if (S[i] != S[(N-1)/2 - 1 -i]) {
            ret = false;
            break;
        }
    }
    rep(i,(N-1)/2) {
        if (S[i+(N+1)/2] != S[N-1-i]) {
            ret = false;
            break;
        }
    }
    cout << ((ret)? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std ;
template< class T > inl T read() {
	T x = 0 ; int f = 1 ; char k = getchar() ;
	for( ; k > '9' || k < '0'; k = getchar() ) if( k == '-' ) f = -1 ;
	for( ; k >= '0' && k <= '9'; k = getchar() ) x = x * 10 + k - '0' ;
	return x * f ;
}
template< class T > inl T read( T &x ) { return x = read<T>() ; }
int _num, _buf[20];
template< class T > il print( T x ) {
   	if( x == 0 ) return putchar( '0' ) ,void() ;
	if( x < 0 ) putchar( '-' ), x = -x ;
	while( x ) _buf[++_num] = x % 10, x /= 10 ;
	while( _num ) putchar( _buf[_num--] + '0' ) ;
}
ll mul( ll a, ll b, ll mod ) { long double c = 1. ; return ( a * b - (ll)( c * a * b / mod ) * mod ) % mod ; }
it qpow( int x, int m, int mod ) {
	int res = 1, bas = x ;
	while(m) {
		if( m & 1 ) res = ( 1ll * res * bas ) % mod ;
		bas = ( 1ll * bas * bas ) % mod, m >>= 1 ;
	}
	return res ;
}
int n;
int main() {
//	freopen( ".in", "r", stdin ) ;
//	freopen( ".out", "w", stdout ) ;
	n = read<int>() ;
	if( n >= 30 )
		puts( "Yes" ) ;
	else
		puts( "No" ) ;
	cerr << 1. * clock() / CLOCKS_PER_SEC << "\n" ;
	return 0;
}

Measured memory_bytes: 3728
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main() {
    int n, m; scan(n, m);

    auto uf = new UnionFind(n);
    for (int i = 0; i < m; i++) {
        int x, y, z; scan(x, y, z);
        uf.unite(x, y);
    }

    bool[int] set;
    for (int i = 1; i <= n; i++) {
        set[uf.root(i)] = true;
    }
    auto ans = set.keys.length;
    writeln(ans);
}

class UnionFind {
    private int[] _data;
    private int[] _nexts; // 次の要素。なければ -1
    private int[] _tails; // 末尾の要素

    this(int n) {
        _data  = new int[](n + 1);
        _nexts = new int[](n + 1);
        _tails = new int[](n + 1);

        _data[] = -1;
        _nexts[] = -1;
        for (int i = 0; i < _tails.length; i++)
            _tails[i] = i;
    }

    int root(int a) {
        if (_data[a] < 0) return a;
        return _data[a] = root(_data[a]);
    }

    bool unite(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra != rb) {
            if (_data[rb] < _data[ra]) swap(ra, rb);
            _data[ra] += _data[rb]; // ra に rb を繋げる
            _data[rb] = ra;
            // ra の末尾の後ろに rb を繋げる
            _nexts[_tails[ra]] = rb;
            // ra の末尾が rb の末尾になる
            _tails[ra] = _tails[rb];
        }
        return ra != rb;
    }

    bool isSame(int a, int b) {
        return root(a) == root(b);
    }

    /// a が属する集合のサイズ
    int groupSize(int a) {
        return -_data[root(a)];
    }

    /// a が属する集合の要素全て
    void doEach(int a, void delegate(int) fn) {
        auto node = root(a);
        while (node != -1) {
            fn(node);
            node = _nexts[node];
        }
    }
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


Measured memory_bytes: 7932
import scala.io.StdIn

object Main {

  def main(args: Array[String]): Unit = {

    val n = StdIn.readLine().toInt
    val ans = (1 to n).foldLeft(false)((acc, _) => {
      val a = StdIn.readLine().toInt
      acc || (a % 2 == 1)
    })
    println(if(ans) "first" else "second")

  }

}


Measured memory_bytes: 36008
import math

h, w = map(int, input().split())

if h == 1 or w == 1:
    ans = 1
elif (h * w) % 2 == 0:
    ans = (h * w) // 2
else:
    ans = (h // 2) * w + math.ceil(w / 2)

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/
int main(){
    int n; cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    ll count = 0;
    ll sum = 0;
    ll abs_sum = 0;
    rep(i, n){
        cin >> a[i];
        sum += a[i];
        b[i] = abs(a[i]);
        abs_sum += b[i];
        if(a[i] < 0) count++;
    }
    if(*min_element(a.begin(), a.end()) >= 0){
        cout << sum << endl;
        return 0;
    }
    ll abs_min = *min_element(b.begin(), b.end());
    if(count % 2 == 0 or (count % 2 == 1 and abs_min == 0)){
        cout << abs_sum << endl;
        return 0;
    }
    if(count % 2 == 1 and abs_min > 0){
        cout << abs_sum - abs_min * 2 << endl;
        return 0;
    }
}


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

ABs = []

for i in range(N):
    a,b = map(int,input().split())
    ABs.append((a,b))

sorted_ABs = sorted(ABs,key=lambda ab: ab[1])

times = 0
before_line = 0
for ab in sorted_ABs:
    times += (ab[1] - before_line)
    before_line = ab[1]
    tmp = times - ab[0]
    if tmp < 0:
        print("No")
        exit()

    times -= ab[0]

print("Yes")


Measured memory_bytes: 33400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextInt(); // 縦
		long b = sc.nextInt(); // 横
		long c = 0; // 結果
		long d = 2; // 除算

		if (a == 1 || b == 1) {
			c = 1;
		} else if (b % d == 0) {
			long e = b / d;
			c = a * e;
		} else {
			long e = (b / d);
			c = a % d == 0 ? ((a / d) * (e + 1)) + ((a / d) * e) : ((a / d + 1) * (e + 1)) + ((a / d) * e);
		}
		System.out.println(c);
	}
}

Measured memory_bytes: 21844
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        String slimes = sc.next();
        String[] slimesArray = slimes.split("");
        int ans = 1;

        for (int i = 1; i < slimesArray.length; i++) {
            if (!slimesArray[i].equals(slimesArray[i - 1])) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 31584
#include<stdio.h>
#include<string.h>
int main(){
  int n,i,j,a[101][101],m,l,stack[100],stamp[101][2],now,time=1,flag,start;
  scanf("%d",&n);
  for(i=1;i<=n;i++) for(j=1;j<=n;j++){
      a[i][j]=0;
      stack[j]=-1;
      stamp[j][0]=-1;
      stamp[j][1]=-1;
    }
  for(i=1;i<=n;i++){
    scanf("%d %d",&j,&m);

    for(j=1;j<=m;j++){
      scanf("%d",&l);
      a[i][l]=1;
    }
  }
  start=1;
  now=1;
  j=0;
  while(1){
    if(stamp[start][1] != -1){
      flag=0;
      for(i=2;i<=n;i++){
	if(stamp[i][0] == -1){
	  start=i;
	  now=i;
	  flag=1;
	  break;
	}
      }
      if(flag==0) break; 
    }
    flag=0;
    if(stamp[now][0] == -1){
      stamp[now][0]=time;
      time++;
    }
    
    if(stamp[now][1] == -1){
      stack[j]=now;
      j++;
    }
    /*
    printf("now=%d[%d] time=%d stacks =",now,stamp[now][0],time);
    for(i=0;i<j;i++) printf(" %d",stack[i]);
    printf("\n");
    */
    for(i=1;i<=n;i++){
      if(a[now][i]==1 && stamp[i][0] == -1){
	now=i;
	flag=1;
	break;
      }
    }
    if(flag==1) continue;
    stamp[now][1]=time;
    time++;
    j--;
    if(stack[j] == now) j--;
    now=stack[j];

  }
  for(i=1;i<=n;i++){
    printf("%d %d %d\n",i,stamp[i][0],stamp[i][1]);
  }
}



Measured memory_bytes: 2068
using System;
using System.Linq;
namespace algo
{
    class Program
    {
        static void Main(string[] args)
        {
            var input1 = Console.ReadLine().Split(' ');
            int N = int.Parse(input1[0]);
            int M = int.Parse(input1[1]);

            var input2 = Console.ReadLine().Split(' ');
            int[] A = input2.Select(x => int.Parse(x)).ToArray();
            int sum =0;
            for(int i = 0; i < A.Length; i++){
                sum += A[i];
            }
            float limit = (float)sum / (4 * M);
            int count = 0;
            for(int j =0; j< A.Length; ++j){
                if(A[j] < limit) continue;
                count++;
            }

            if(count >= M) Console.WriteLine("Yes");
            else Console.WriteLine("No");

        }
    }
}


Measured memory_bytes: 13396
n, d = gets.split.map(&:to_i)
x = []
for i in 0...n do
  x[i] = gets.split.map(&:to_i)
end
count = 0
for i in 0...(n-1) do
  for j in (i+1)...n do
    dist2 = 0
    for dim in 0...d do
      diff = x[i][dim] - x[j][dim]
      dist2 += diff * diff
    end
    dist = Math.sqrt(dist2).to_i
    count += 1 if dist * dist == dist2
  end
end
puts count


Measured memory_bytes: 1788
while True:
  n = int(input())
  if n == 0:
    break
  dic = {}
  for _ in range(n):
    ss = input().split()
    for s in ss:
      if s[0] in dic:
        dic[s[0]].append(s)
      else:
        dic[s[0]] = [s]
  k = input()
  if k not  in dic:
    print("NA")
    continue
  lst = dic[k]
  k_dic = {}
  for s in lst:
    if s in k_dic:
      k_dic[s] += 1
    else:
      k_dic[s] = 1
  ans = list(k_dic.items())
  ans.sort()
  ans.sort(key=lambda t:-t[1])
  print(*[k for k, v, in ans][:5])



Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
#define INFTY 10000000000
typedef long long int ll;
const int MOD=1000000007;
using Graph = vector<vector<int>>;
using ipair = pair<ll,ll>;
bool operator< (const ipair a, const ipair b){return a.first < b.first;};
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){

  int n,m;cin>>n>>m;
  vector<vector<pair<ll,int>>> p(100005);
  string num[100002];
  rep(i,m){
    int x;ll y;
    cin>>x>>y;

    p[x].emplace_back(make_pair(y,i+1));
  }

  for (int i = 1; i <= n; i++)
  {
    if(p[i].empty())continue;
    sort(p[i].begin(),p[i].end());
    rep(j,p[i].size()){
      string pn,xn;
      pn = to_string(i);
      xn = to_string(j+1);
      int n0f,n0b;
      n0f = 6-pn.length();n0b = 6-xn.length();
      rep(k,n0f)num[p[i][j].second] += '0';
      num[p[i][j].second] += pn;
      rep(k,n0b)num[p[i][j].second] += '0';
      num[p[i][j].second] += xn;
    }
  }

  for (int i = 1; i <= m; i++){
    cout<<num[i]<<endl;
  }
  return 0;
}

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

int main () {
  int H , W ;
  cin >> H >> W ;
  int nul[H][W] = {} ;
  int B[W] = {} ;
  for(int i = 0 ; i < H ; i++ ){
    for(int j = 0 ; j < W ; j++ ){
      cin >> nul[i][j] ;
    }
  }
  for(int i = 0 ; i < W ; i++) {
    cin >> B[i] ;
  }
  for(int i = 0 ; i < H ; i++) {
    int pre = 0 ;
    for(int j = 0 ; j < W ; j++ ){
      pre += nul[i][j] * B[j] ;
    }
    cout << pre << endl ; 
  }
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define R(i,n) for(int i=n-1;i>=0;i--)
using namespace std;
typedef pair<int,int> P;
int n,a[51],b[51],c[51][51],c1,c2,pre=0,a1[51],b1[51],c3,c4;
void bl(){cout<<"NO"<<endl;exit(0);}
main(){
  cin>>n;
  r(i,n+1)cin>>a[i],c1+=a[i],c3+=a[i]*i;
  r(i,n+1)cin>>b[i],c2+=b[i],c4+=b[i]*i;
  if(c1!=n||c2!=n||c3!=c4)bl();
  else{
    c1=c2=0;
    r(i,n+1)while(a[i])a1[c1++]=i,a[i]--;
    R(i,n+1)while(b[i])b1[c2++]=i,b[i]--;
    r(i,n){
      priority_queue<P>q;
      r(j,n)q.push(P(a1[j],j));
      r(j,b1[i]){
    P p=q.top();q.pop();
    a1[p.second]--;
    if(c[i][p.second])bl();
    c[i][p.second]=1;
      }
    }
    cout<<"YES"<<endl;
    r(i,n){
      r(j,n){
    if(j)cout<<' ';
    cout<<c[i][j];
      }
      cout<<endl;
    }
  }
}

Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  vector<long long> C(N);
  for(int i = 0; i < N; ++i){
    cin >> S[i] >> C[i];
  }
  map<string,long long> L, R;
  const long long INF = 1e18;
  L[""] = INF;
  R[""] = INF;
  for(string s = "a"; s <= "z"; ++s[0]){
    L[s] = INF;
    R[s] = INF;
  }
  long long ans = INF;

  priority_queue<tuple<long long,bool,string>,vector<tuple<long long,bool,string>>,greater<>> pq;
  for(int i = 0; i < N; ++i){
    L[S[i]] = C[i];
    pq.emplace(C[i],true,S[i]);
    string s_(S[i].rbegin(), S[i].rend());
    
    if(S[i] == s_)
      ans = min(ans,C[i]);
    
  }

  auto match = [](const string& s, const string& t){
    int l = t.length();
    for(size_t i = 0; i < s.length(); ++i){
      if(i >= t.length()) return true;
      if(s[i] != t[l-1-i]) return false;
    }
    return true;
  };


  while(pq.size()){
    auto [c, f, s] = pq.top();
    // cerr << c << " " << f << " " << s << endl;
    pq.pop();

    if(f and L[s] < c) continue;
    if(!f and R[s] < c) continue;

    if(f){
      for(int i = 0; i < N; ++i){
        const string& t = S[i];
        long long c_ = c + C[i];
        if(c_ >= ans) continue;
        if(!match(s,t)) continue;

        if(s.length() >= t.length()){
          string s_ = s.substr(t.length());
          if((L.find(s_) == L.end()) or L[s_] > c_){
            L[s_] = c_;
            string r(s_.rbegin(), s_.rend());
            if(r == s_) ans = min(ans,c_);
            pq.emplace(c_,true,s_);
          }
        }else{
          string s_ = t.substr(0,t.length()-s.length());
          if(R.find(s_) == R.end() or R[s_] > c_){
            R[s_] = c_;
            string r(s_.rbegin(), s_.rend());
            if(r == s_) ans = min(ans,c_);
            pq.emplace(c_,false,s_);
          }
        }
      }
    }else{
      for(int i = 0; i < N; ++i){
        const string& t = S[i];
        long long c_ = c + C[i];
        if(c_ >= ans) continue;
        if(!match(t,s)) continue;
        if(s.length() >= t.length()){
          string s_ = s.substr(0,s.length()-t.length());
          if(R.find(s_) == R.end() or R[s_] > c_){
            R[s_] = c_;
            string r(s_.rbegin(), s_.rend());
            if(r == s_) ans = min(ans,c_);
            pq.emplace(c_,false,s_);
          }
        }else{
          string s_ = t.substr(s.length());
          if(L.find(s_) == L.end() or L[s_] > c_){
            L[s_] = c_;
            string r(s_.rbegin(), s_.rend());
            if(r == s_) ans = min(ans,c_);
            pq.emplace(c_,true,s_);
          }
        }
      }
    }
  }
  
  if(ans >= INF) ans = -1;
  cout << ans << '\n';
}


Measured memory_bytes: 3664
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp44 {
    class Program {
        static void Main(string[] args) {
            var X = Console.ReadLine().Split(' ').Select(p => long.Parse(p)).ToArray();
            long A = X[0];
            long B = X[1];
            long K = X[2];

            if (A >= K) {
                Console.Write((A - K) + " " + B);
            } else if (A + B >= K) {
                Console.Write(0 + " " + (A + B - K));
            } else {
                Console.Write("0 0");
            }

        }
    }
}


Measured memory_bytes: 13268
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <fstream>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

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

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	string s; cin >> s;
	rep(i, s.size() - 1)if (s.substr(i, 2) == "AC")
	{
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
}

Measured memory_bytes: 3616
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        Console.ReadLine();
        int[] input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        int result = 0;
        for (int 段 = 1; ; 段++)
        {
            int count = 0;
            bool flag = false;
            bool exist = false;
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] >= 段)
                {
                    flag = true;
                    exist = true;
                }
                else if (flag)
                {
                    ++count;
                    flag = false;
                }
            }
            if (flag)
            {
                ++count;
            }
            if (!exist)
            {
                break;
            }
            result += count;
        }

        Console.WriteLine(result);
        Console.ReadKey();
    }
}


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

using namespace std;

int main() {
	string S;
	cin >> S;

	int psize = 1 << S.size() - 1;
	long long ans = 0;
	for(int i = 0; i < psize; i++) {
		long long tmp = 0;
		long long sum = 0;
		for(int j = 0; j < S.size(); j++) {
			tmp *= 10;
			tmp += S[j] - '0';
			if((i >> j) & 1) {
				sum += tmp;
				tmp = 0;
			}		}
		ans += sum + tmp;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(name, stop) for (ll(name) = 0; (name) < (stop); (name)++)
using ll = long long;
using vi = vector<ll>;

int main(void) {
    ll N;
    cin >> N;
    ll ans = 0;
    REP(i, N + 1) {
        if ((i % 3) == 0 || (i % 5) == 0) continue;
        ans += i;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include<stdio.h>
int main()
{
    int n,s;
    scanf("%d",&n);
    if(n%2==0&&n>1)
    {
        s=(n/2)-1;
    }
    else if(n%2!=0&&n>1)
    {
        s=n/2;
    }
    else
    {
        s=0;
    }
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 128
#pragma warning (disable:4996)
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#define inf 0X7f7f7f7f
#define MS_I(x) memset(x,-inf,sizeof(x))
#define MS(x) memset(x,0,sizeof(x))
#define MSI(x) memset(x,inf,sizeof(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 5;

int main()
{
	int N;
	double ans = 0;
	scanf("%d", &N);
	if (N % 2 == 1)
		ans = (double)((N - 1) / 2 + 1) / N;
	else
		ans = (double)0.5;
	printf("%.10lf", ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, m;
int main(){
    cin >> n >> m;
    if(n % 2){
        for(int i = 1;i <= m; i++){
            cout << i << " " << n - i + 1 << endl;
        }
    }
    else{
        for(int i = 1; i <= min(m, (n / 4)); i++){
            cout << i << " " << n - i + 1 << endl;
            if(i == m){
                return 0;  
            }
        }
        for(int i  = n / 4 + 1; i <= m; i++){
            cout << i + 1 << " " << n - i + 1 << endl;
        }
    }
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int dp[410][410];

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for(int i=0; i<H; ++i) cin >> S[i];
	for(int i=0; i<H*W; ++i){
		for(int j=0; j<H*W; ++j){
			if(i==j) dp[i][j]=0;
			else if(S[i/W][i%W]=='.' && S[j/W][j%W]=='.'){
				if(i/W==j/W && abs(i%W-j%W)==1) dp[i][j]=1;
				else if(i%W==j%W && abs(i/W-j/W)==1) dp[i][j]=1;
				else dp[i][j]=1000;
			}
			else dp[i][j]=1000;
		}
	}
	for(int k=0; k<H*W; ++k){
		for(int i=0; i<H*W; ++i){
			for(int j=0; j<H*W; ++j){
				dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]);
			}
		}
	}
	int ans=0;
	for(int i=0; i<H*W; ++i){
		for(int j=0; j<H*W; ++j){
			if(dp[i][j]<1000){
				ans=max(ans, dp[i][j]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 896
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

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

const int MAX_N = 182;
int num[MAX_N];
VI odd;

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

  num[0] = 0;
  for(int i=1;i<MAX_N;++i){
	num[i] = i*(i+1)*(i+2)/6;
	if(num[i] % 2 == 1) odd.PB(num[i]); // i % 4 == 1
  }

  VI pr;
  REP(i,MAX_N) REP(j,MAX_N)
	pr.PB(num[i]+num[j]);
  SORT(pr);
  
  VI dp(1000000+1,123456789);
  dp[0] = 0;
  for(int i=1;i<1000000+1;++i){
	for(int j=0;j<SZ(odd);++j){
	  if(i < odd[j]) break;
	  dp[i] = min(dp[i], dp[i - odd[j]] + 1);
	}
  }

  int N;
  while(cin>>N,N){
	int cnt = 0;
	if(*lower_bound(num, num+MAX_N, N) == N) cnt=1;
	else if(*lower_bound(ALL(pr), N) == N) cnt=2;
	else{
	  REP(i,SZ(pr)){
		int x = N - pr[i];
		if(x < 0) break;
		if(*lower_bound(num, num+MAX_N, x) == x){
		  cnt=3; break;
		}
		if(*lower_bound(ALL(pr), x) == x){
		  cnt=4;
		}
	  }
	  if(!cnt) cnt = 5;
	}
	cout << cnt << " " << dp[N] << endl;
  }
  
  return 0;
}

Measured memory_bytes: 5260
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <climits>
using namespace std;

#define MOD1097 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mpair make_pair
#define pm(first, second) pb(mpair(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()
#define reall(X) (X).rbegin(), (X).rend()
#define divcel(a, b) (((a) + ((b) - 1)) / (b))

int main(){

	string S;
	cin >> S;
	cout << S[0] << S[1] << S[2] << endl;

	return 0;
}


Measured memory_bytes: 3548
#include "bits/stdc++.h"
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define display(v) for (auto x : v) cout << x << ", "
#define print(x) cout << (#x) << " = [ ";display(x); cout << "]\n"
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define ceel(x, y) ((x) / (y) + !((x) % (y) == 0))
#define ss second
#define ff first
#define pb push_back
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;

void __print(int x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef INCLUDEWHENOFFLINE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif



int main()
{
    fastio;

    int n;
    cin >> n;
    cout << (!n) << endl;

    return 0;
}

Measured memory_bytes: 3612
#include<cstdio>
#include<vector>
#include<algorithm>
//#include<numeric>
#include<functional>
//#include<string>
//#include<iostream>

using namespace std;
const int one = 1;
const int big = (one<<20);
typedef long long int llint;
//11:10～13:00
int main(void){
	llint N=0,L,Q,h,i,a,gen,to,ans;
	vector<llint> x;
	static llint go[17][100005];
	scanf("%lld",&N);
	for(i=0;i<N;i++){
		scanf("%lld",&a);
		x.push_back(a);
	}
	x.push_back(2000000010);
	scanf("%lld",&L);
	for(i=0;i<N;i++){
		go[0][i]=upper_bound(x.begin(),x.end(),x[i]+L)-x.begin()-1;
	}
	for(h=1;h<17;h++){
		for(i=0;i<N;i++){
			go[h][i]=go[h-1][go[h-1][i]];
		}
	}
	scanf("%lld",&Q);
	for(h=0;h<Q;h++){
		ans=0;
		scanf("%lld %lld",&gen,&to);
		if(gen>to){swap(gen,to);}
		gen--;to--;
		for(i=16;i>=0;i--){//行けなくなる最大日数を二分探索+1
			if(go[i][gen]<to){
				ans+=(1<<i);
				gen=go[i][gen];
			}
		}
		printf("%lld\n",ans+1);
	}
	return 0;
}

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

using namespace std;

int main() {
    int a, b, c, d, e;
    vector<int> vec;

    cin >> a >> b >> c >> d >> e;
    vec.push_back(a);
    vec.push_back(b);
    vec.push_back(c);
    vec.push_back(d);
    vec.push_back(e);

    sort(vec.begin(), vec.end(), greater<>());

    for (int i = 0; i < vec.size(); i++) {
        if (i > 0) cout << ' ';
        cout << vec[i];
    }
    cout << endl;
}


Measured memory_bytes: 3120
import java.util.*;

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

        int r = sc.nextInt();   //行数
        int c = sc.nextInt();   //列数
        int[][] a = new int[r][c];  //r行c列の行列
        int[] sum_r = new int[r];   //行合計
        int[] sum_c = new int[c];   //列合計
        int sum_all = 0;    //合計

        /* 値取得 */
        for(int i = 0;i < r;i++){
            for(int j = 0;j < c;j++){
                a[i][j] = sc.nextInt();
                sum_r[i] += a[i][j];
                sum_c[j] += a[i][j];
                sum_all += a[i][j];
            }

        }

        for(int i = 0;i < r + 1;i++){
            if(i < r){
                for(int j = 0;j < c + 1;j++){
                    if(j != 0)  System.out.print(" ");
                    if(j < c)   System.out.print(a[i][j]);
                    if(j == c)  System.out.print(sum_r[i]);    
                }
                System.out.println();
            }
            if(i == r){
                for(int j = 0;j < c + 1;j++){
                    if(j != 0)  System.out.print(" ");
                    if(j < c)   System.out.print(sum_c[j]);
                    if(j == c)  System.out.print(sum_all);
                }
                System.out.println();
            }
        }
    }
}


Measured memory_bytes: 41920
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>


using namespace std;
using ll = long long int; 

int main(void){

    int a;
    cin>>a;

    if(a%2==0)cout<<a/2<<endl;
    else cout<<a/2 +1<<endl;



    return 0;
}

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

typedef long long ll;

int main(){
  int a,b;
  cin >> a >> b;
  if(a%3==0||b%3==0||(a+b)%3==0){
    cout<<"Possible"<<endl;
  }else{
    cout<<"Impossible"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
long N,H,D,mod=1e9+7;
long dp[1<<20];
main()
{
	cin>>N>>H>>D;
	long s=0,p=1;
	for(int i=1;i<=N;i++)
	{
		p=p*i%mod;
		s=(s+p)%mod;
	}
	long now=0;
	for(int i=1;i<=H;i++)
	{
		dp[i]=(now*s+p*(i<=D))%mod;
		now=(now+dp[i])%mod;
		if(i>=D)now=(now-dp[i-D]+mod)%mod;
	}
	cout<<dp[H]<<endl;
}

Measured memory_bytes: 8448
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <cmath>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
int cou[26];

int main(int argc, char const* argv[])
{
  string w;
  cin >> w;
  for(char c: w){
    cou[c - 'a']++;
  }
  for(int i = 0; i < 26; i++){
    if(cou[i] % 2 == 1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
	return 0;
}


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

int main(){
  double d,e;
  while(1){
    cin>>d>>e;
    if(d+e==0)break;
    double ans=1e9;
    for(int i=0;i<=d;i++)
      for(int j=0;j<=d;j++)
	if(i+j==d) ans=min(ans,abs(sqrt(i*i+j*j)-e));
    printf("%lf\n",ans);
  }
    return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int N, K, T, ans;
  cin >> N >> K;
  T=1;
  ans=0;
  for (int i=0; i<40; i++) {
    if (N>=T) {
      ans=ans+1;
      T=T*K;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t;
		while ((t = in.nextInt()) > 0) {
			int n = in.nextInt();
			while (n-- > 0) {
				t += in.nextInt();
				t -= in.nextInt();
			}
			if (t <= 0) {
				System.out.println("OK");
			} else {
				System.out.println(t);
			}
		}
	}
}

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

int main(){
    ll N,i;
    ll result;
    cin>>N;
    result=N;
    vector<ll> D(N);
    for(i=0;i<N;i++)cin>>D[i];
    sort(D.begin(),D.end());
    for(i=1;i<N;i++){
        if(D[i]==D[i-1])result-=1;
    }
    cout<<result<<endl;
}

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

using std::cout;
using std::cin;
using std::endl;
using std::pow;
using std::vector;
using std::string;

int main(){
    int K,N,c,sum=0;
    cin >> N >> K;
    vector<int> p(N);
    for(int i=0;i<N;i++) cin >> p.at(i);
    std::sort(p.begin(),p.end());
    for(int i=0;i<K;i++) sum += p.at(i);
    cout << sum;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long inf=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)
#define ZERO(a) memset(a,0,sizeof(a))





//3111111111111111111111111111111
	

	void solve(){
		
		
		ini(n);
		int tmp = 0;
		FOR(i,1,n+1){
			ini(x);
			if(x%2 and i%2){
				tmp++;
			}
		}
		out(tmp);
		


		
		


			
			
			


				
		


		
		
		
		

		


		
		
	}



	



















int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	solve();
	


	return 0;
}


Measured memory_bytes: 3640
Scanf.scanf "%d" (fun n ->
    let d = Array.init n (fun _ -> Scanf.scanf " %d %d" (fun a b -> a, b)) in

    let rec loop i =
        let same (a, b) = a = b in
        if i = n then "No" else
            if same d.(i) && same d.(i - 1) && same d.(i - 2) then "Yes" else loop (i + 1)
    in
    loop 2 |> print_endline
)


Measured memory_bytes: 3728
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        if self.find(x) != self.find(y):
            return "?"
        return self.weight[x] - self.weight[y]


n, q = map(int, input().split())

tree = WeightedUnionFind(n)

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 0:
        x, y, z = query[1:4]
        tree.union(x, y, z)
    else:
        x, y = query[1:3]
        ans = tree.diff(x, y)
        print(ans)


Measured memory_bytes: 12092
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin >> S;
  int ans = 0;
  for (int i = 0; i < S.size() / 2; i++) {
    if (S.at(i) != S.at(S.size() - 1 - i)) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,n,s) for(int i=(int)(s);i<(int)(n);++i)
#define RREP(i,n,s) for(int i=(int)(s);i>=(int)(n);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

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

    ll ans = 0;
    vector<ll> sum(n);
    map<ll, ll> m;
    REP(i,n) {
        if(i==0) sum[0] = a[0];
        else sum[i] = sum[i-1]+a[i];
        m[sum[i]]++;

        if(sum[i] == 0) ans++;
        ans += m[sum[i]] -1;
    }

    // sort(ALL(sum));
    //
    // FOR(i,sum) {
    //     auto itr2 = upper_bound(ALL(sum), *i);
    //     int c = itr2 - i;
    //
    //     ans += c * (c-1) / 2;
    //     i = itr2-1;
    // }

    cout << ans << endl;
}


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

int main() {
  int N,A;
  cin >> N >> A;
  
  int rem; //remainder
  rem = N%500;  

  if (rem <= A) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" <<endl;
  }
}

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

using namespace std;
typedef long long ll;

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> sum(n + 1);
  sum[0] = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    sum[i + 1] = sum[i] + a[i];
  }
  ll ans = 1e18;
  ll half = sum[n] / 2;
  for (int i = 1; i < n; ++i) {
    if (sum[i] < half) {
      ll tmp = (sum[n] - sum[i]) - sum[i];
      ans = min(ans, tmp);
    } else {
      ll tmp = sum[i] - (sum[n] - sum[i]);
      ans = min(ans, tmp);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3328
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

#n,m = ips()
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(m)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#a.pop(0)は10^5あるときTLEしやすい!注意!抜くなら逆ソート!
n = ip()
a = iprow()
b =[]
s =0
for i in range(n-2):
    b = a[i:(i+3)]
    if b[1] != min(b) and b[1] != max(b):
        s+=1
print(s)

Measured memory_bytes: 23052
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author ExplodingFreeze
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define f(i,a,b) for(int i=(a);i<(b);i++)
const int MOD=1e9+7;
using pii=std::pair<int,int>;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;

int a,b;
class BComparingStrings {
public:
	void solve(std::istream& in, std::ostream& out) {
		in >> a >> b;
		int mi=min(a,b);
		int ma=max(a,b);
		f(i,0,ma)
			out << mi;
		out << "\n";
	}
};


int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	BComparingStrings solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>

using namespace std;
//Greedy じゃだめ
/*
int main(){
	int n,m,c[100],a,ans=0;
	priority_queue<int> coin;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a;
		coin.push(a);
	}
	for(int i=0;i<m;i++){
		c[i]=coin.top();
		coin.pop();
	}
	for(int i=0;i<m;i++){
		while(n>=c[i]){
			n-=c[i];
			ans++;
		}
	}
	cout<<ans<<endl;
}
*/

int main(){
	int n,m,c[100],coin[50001]={};
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>c[i];
		coin[c[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(coin[i]==0){
		int min=1000000;
			for(int j=1;j<i;j++){
				if(min>coin[j]+coin[i-j]){
					min=coin[j]+coin[i-j];
				}
			}
			coin[i]=min;
		}
	}
	cout<<coin[n]<<endl;
}


Measured memory_bytes: 3296
h, w = gets.split.map(&:to_i)
a = Array.new(h) { gets.chomp.chars }

sk = a.flatten.group_by(&:itself).map { |_, b| b.size }.sort

# type 4
t4 = (h / 2) * (w / 2)
t4.times do
  if sk[-1] - 4 < 0
    puts 'No'
    exit
  end

  sk[-1] -= 4
  sk.sort!
end

# type 2
t2 = (w.odd? ? (h / 2) : 0) + (h.odd? ? (w / 2) : 0)
t2.times do
  if sk[-1] - 2 < 0
    puts 'No'
    exit
  end

  sk[-1] -= 2
  sk.sort!
end

puts 'Yes'


Measured memory_bytes: 4092