akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;
 
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
 
template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}
 
// ------------------------------------------------------------------------------------------

map<vector<int>, int> mp;

void init() {
   vector<int> v(8);
   iota(all(v), 0);
   mp[v] = 0;
   queue<vector<int>> que;
   que.push(v);

   while (que.size()) {
      vector<int> cur = que.front(); que.pop();
      int idx = find(all(cur), 0) - cur.begin();
      int y = idx / 4, x = idx % 4;
      rep (i, 4) {
         int ny = y + dy[i], nx = x + dx[i];
         if (ny < 0 || ny >= 2 || nx < 0 || nx >= 4) continue;
         int nc = ny * 4 + nx;
         vector<int> next = cur;
         swap(next[idx], next[nc]);
         if (mp.count(next)) continue;
         mp[next] = mp[cur] + 1;
         que.push(next);
      }
   }
}

int main() {
   init();
   vector<int> vs(8);
   while (cin >> vs[0]) {
      repp (i, 1, 8) cin >> vs[i];
      cout << mp[vs] << endl;
   }

   return 0;
}


Measured memory_bytes: 5632
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <climits>

constexpr int SINT_MAX = std::numeric_limits<int>::max();
constexpr int SINT_MIN = std::numeric_limits<int>::min();

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

template<class T>
T choose(bool b, T t, T f)
{
    if (b) return t;
    else return f;    
}

const char *YesNo(bool b)
{
    return choose(b, "Yes", "No");
}

const char *YESNO(bool b)
{
    return choose(b, "YES", "NO");
}

template<template<class...> class ContT, class ValueT, size_t Dim>
struct vec_type
{
    using type = ContT<typename vec_type<ContT, ValueT, Dim-1>::type>;
};

template<template<class...> class ContT, class ValueT>
struct vec_type<ContT, ValueT, 0>
{
    using type = ValueT;
};

template<class ValueT, size_t Dim = 1>
using vec_t = typename vec_type<std::vector, ValueT, Dim>::type;


template<class ValueT, size_t Dim, class = typename std::enable_if<Dim == 0>::type>
auto make_vec(ValueT value = ValueT()) -> ValueT
{
    return value;
}

template<class ValueT, size_t Dim, class... Rest>
auto make_vec(size_t size0, Rest... rest)
{
    auto vec = make_vec<ValueT, Dim-1>(rest...);
    return std::vector(size0, vec);
}

int diffabs(int l, int r)
{
    if (l < r) return r-l;
    else return l-r;    
}


///////////////////////////////////////////////////

int main()
{
    vector<string> days = {"SUN","MON","TUE","WED","THU","FRI","SAT"};

    string S;
    cin >> S;
    auto it = find(begin(days), end(days), S);
    int ans = distance(it, end(days));
    cout << ans << endl;
}

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

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


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

int N, C;
int tm[31][200001];
int main()
{
	cin >> N >> C;
	REP(i, 0, 31) REP(j, 0, 200001) tm[i][j] = 0;
	
	REP(i, 0, N) {
		int s, t, c;
		cin >> s >> t >> c;
		c--;
		tm[c][2 * s - 1]++;
		tm[c][2 * t]--;
	}
	REP(i, 0, C) {
		REP(j, 1, 200001) {
			tm[i][j] += tm[i][j - 1];
			if (tm[i][j] > 0) {
				tm[30][j]++;
			}
		}
	}
	int ans = 0;
	REP(j, 1, 200001) {
		ans = max(ans, tm[30][j]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 24448
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin>>N;
  long a[N];
  for (int i=0;i<N;i++){
    cin>>a[i];
  }
  long s=0;
  for (int i=0;i<N;i++){
    s+=a[i]%2;
  }
  if (s==0){
    cout<<"second";
  }
  else{
    cout<<"first";
  }
  return 0;
}


Measured memory_bytes: 1024
//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=4e2+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);

ll dp[(1<<16)];
ll dt[(1<<16)];
ll d[MAXn][MAXn];

int main()
{
    IOS();
    ll n;
    cin>>n;
    REP(i,n)REP(j,n)cin>>d[i][j];
    REP(I, (1<<n))
    {
        vector<ll> v;
        REP(i,n)if((1<<i) & I)v.pb(i);
        ll tt = 0;
        REP(j,SZ(v))REP(k, j)tt += d[v[j]][v[k]];
        dt[I] = tt;
    }
    dp[0] = 0;
    REP1(I, (1<<n)-1)
    {
        vector<ll> v;
        REP(i,n)if((1<<i) & I)v.pb(i);
        ll m = SZ(v);
        dp[I] = - INF;
        REP(J, (1<<m))
        {
            ll K = 0;
            REP(i, m)if((1<<i) & J) K += (1<<v[i]);
            dp[I] = max(dp[I], dp[I - K] + dt[K]);
        }
    }
    cout<<dp[(1<<n) - 1]<<endl;
}


Measured memory_bytes: 1280
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string.h>
using namespace std;
int main()
{
	long long int h, k;
	cin >> h >> k;
	long long end = 0;
	if (k == 1||h==1)
	{
		cout << "1" << endl;
		return 0;
	}
	if (h % 2 == 0)
	{
		end = (h / 2) * k;
		cout << end<<endl;
		return 0;
	}
	else
	{
		end = (h / 2) * k;
		if (k % 2 == 0)
		{
			end += (k / 2);
			cout << end << endl;
			return 0;
		}
		else
		{ 
		end += (k / 2) + 1;
		cout << end << endl;
		return 0;
		}
	}

}

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

using namespace std;

struct object
{
    int weight, value;

    object(){};

    int operator<(const object &O)
    {
        if (value == O.value)
        {
            return (weight < O.weight);
        }

        return (value > O.value);
    }
};

const int MAX_N = 1e3 + 5, MAX_VALUE = 55, oo = 1e9;
int minimum_weight[MAX_N][MAX_VALUE];

int main()
{
    int no_of_objects, capacity;
    cin >> no_of_objects >> capacity;

    vector<object> O(no_of_objects + 1);
    for (int i = 1; i <= no_of_objects; i++)
    {
        cin >> O[i].weight >> O[i].value;
    }

    long long total_value = 0;
    for (int i = 1; i <= no_of_objects; i++)
    {
        total_value += O[i].value;
    }

    int answer = 0;
    vector<long long> minimum_weight(total_value + 1, -1);
    total_value = 0;
    minimum_weight[0] = 0;

    for (int i = 1; i <= no_of_objects; i++)
    {
        total_value += O[i].value;

        for (int v = total_value; v >= O[i].value; v--)
        {
            if (minimum_weight[v - O[i].value] != -1)
            {
                long long weight_required = minimum_weight[v - O[i].value] + O[i].weight;

                if (weight_required <= capacity)
                {
                    answer = max(answer, v);
                }

                if (minimum_weight[v] == -1 || minimum_weight[v] > weight_required)
                {
                    minimum_weight[v] = weight_required;
                }
            }
        }
    }

    cout << answer;

    return 0;
}

Measured memory_bytes: 1024
#C
N, M = map(int, input().split())
Hlist = list(map(int, input().split()))
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
#print(A)
a=["0"]*N
for i in range(M):
    if Hlist[A[i]-1]<Hlist[B[i]-1]:
        a[A[i]-1]="-1"
        if not a[B[i]-1]=="-1":
            a[B[i]-1]="+1"
    if Hlist[A[i]-1]>Hlist[B[i]-1]:
        if not a[A[i]-1]=="-1":
            a[A[i]-1]="+1"
        a[B[i]-1]="-1"
    if Hlist[A[i]-1]==Hlist[B[i]-1]:
        a[A[i]-1]="-1"
        a[B[i]-1]="-1"
num=a.count("+1")+a.count("0")
print(num)

Measured memory_bytes: 21724
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define int long long
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, n) for (int i = 1; i <= (n); ++i)
#define repd(i, n) for (int i = (n)-1; i >= 0; --i)
#define repds(i, n) for (int i = (n); i > 0; --i)
#define loop(i, x, n) for (int i = (x); i < (n); ++i)
#define loops(i, x, n) for (int i = (x); i <= (n); ++i)
#define loopd(i, x, n) for (int i = (x); i > (n); --i)
#define loopds(i, x, n) for (int i = (x); i >= (n); --i)
#define itrep(i, a) for (auto i = begin(a); i != end(a); ++i)
#define itrepd(i, a) for (auto i = rbegin(a); i != rend(a); ++i)
#define each(i, x) for (auto &i : x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using priority_queuel = priority_queue<T, vector<T>, greater<T>>;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
constexpr double eps = 1e-9;
ll mod = static_cast<ll>(1e9 + 7);
template <class T>
constexpr int sz(const T &a) { return (int)a.size(); }
template <class T>
constexpr T pow2(const T a) { return a * a; }
template <class T, class... Args>
constexpr void mins(T &a, Args... args) { a = min<T>({a, args...}); }
template <class T, class... Args>
constexpr void maxs(T &a, Args... args) { a = max<T>({a, args...}); }
template <class A, int N, class T>
void fillArray(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

template <typename F>
class FixPoint : private F {
public:
    explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)) {}
    template <typename... Args>
    constexpr decltype(auto)
    operator()(Args &&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <typename F>
static inline constexpr decltype(auto)
make_func(F &&f) noexcept {
    return FixPoint<F>{std::forward<F>(f)};
}

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    map<ll, int> mp;
    rep(i, n) {
        ++mp[i + 1 - a[i]];
    }

    ll ans = 0;
    rep(i, n) {
        --mp[i + 1 - a[i]];
        ans += mp[i + 1 + a[i]];
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout.flush();
    return 0;
}


Measured memory_bytes: 27388
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;


int B = 320;
// バケット i は [i*B, (i+1)*B) の記録を持つ
// lazy[i] :=  バケットi の遅延を記録する
// 遅延が-1 ... 制約よりそんなことは発生しないことを利用して, これを遅延の単位元とできる
// i.e. lazy[i] == -1 def 消化時に何も伝播させないという遅延を与えるとみなす
vector<int> lazy(B, -1), a(100000, (1LL << 31) - 1);
 
// a_s, ..., a_t を x に変更する
void update(int s, int t, int x)
{
    // s の属するバケット, t の属するバケット
    int st = s / B, gt = t / B;

    // st や gt に遅延が存在するとき更新前に消化しておく
    // 遅延はパケットごとに考えるから, 遅延が存在⇔パケット内は全て等しい値で更新されている
    // 区間に被覆されるパケットについてはこのあと新しい値へ更新されるので消化しなくてOK
    if (lazy[st] != -1){
        for (int i = st * B; i < (st + 1) * B; i++) a[i] = lazy[st];
        lazy[st] = -1;
    }
    if (lazy[gt] != -1){
        for (int i = gt * B; i < (gt + 1) * B; i++) a[i] = lazy[gt];
        lazy[gt] = -1;
    }
    //... || ... s ... t ... || ...
    //更新が同一パケット内で済むなら直接更新しても間に合う
    if (st == gt){
        for (int i = s; i <= t; i++) a[i] = x;
    }

    //... s ... || (被覆されるパケット) || ... t ...
    else{
        //端が属するパケット内は直接更新
        for (int i = s; i < (st + 1) * B; i++) a[i] = x;
        for (int i = gt * B; i <= t; i++) a[i] = x;

        //区間に被覆されるパケットについては更新を遅延に残す
        for (int i = st + 1; i < gt; i++){
            lazy[i] = x;
        }
    }
}
 
// a_i を返す
int find(int s){
    int st = s / B;
    //遅延を処理する
    if (lazy[st] != -1){
        for (int i = st * B; i < (st + 1) * B; i++) a[i] = lazy[st];
        lazy[st] = -1;
    }
    return a[s];
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    REP(i, q){
        int type;
        cin >> type;
        if(type == 0){
            int s, t, x;
            cin >> s >> t >> x;
            update(s, t, x);
        }
        else{
            int s;
            cin >> s;
            cout << find(s) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3252
n, a, b = map(int, input().split())
count = 0

for i in range(n):
  sum = 0
  check = i + 1
  while (check > 0):
    sum = sum + check % 10
    check = check // 10
  
  if sum >= a:
    if sum <= b:
      count += (i+1)
      
print(count)

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

int main(){
	int a, b, c, d=0,temp[100],i;
	cin >> a >> b >> c;
	for(i=0;i<100;i++){
		temp[i]=0;
	}
	temp[a-1]=1;
	temp[b-1]=1;
	temp[c-1]=1;

	for(i=0;i<100;i++){
		d += temp[i];
	}
	cout << d;
	
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100001
#define NIL -1

struct node{
  int parent;
  int left;
  int right;
};

struct node T[MAX];
int Dpt[MAX];

void setDepth(int, int);
void printch(int);

int main(){
  int n;
  int id, k;
  int ch, l;
  int root;
  int i, j;

  scanf("%d", &n);

  for(i=0; i<n; i++)
    T[i].parent = T[i].left = T[i].right = NIL;

  for(i=0; i<n; i++){
    scanf("%d%d", &id, &k);

    for(j=0; j<k; j++){
      scanf("%d", &ch);
      T[ch].parent = id;

      if(j==0)
	T[id].left = ch;

      else
	T[l].right = ch;

      l = ch;
    }
  }

  for(i=0; i<n; i++){
    if(T[i].parent == NIL){
      root = i;
      break;
    }
  }

  setDepth(root, 0);

  for(i=0; i<n; i++){
    printf("node %d: parent = %d, depth = %d, ", i, T[i].parent, Dpt[i]);

    if(T[i].parent == NIL)
      printf("root, ");

    else if(T[i].left == NIL)
      printf("leaf, ");

    else
      printf("internal node, ");

    printf("[");
    printch(i);
    printf("]\n");
  }
  
  return 0;
}

void setDepth(int u, int par){
  Dpt[u] = par;
  if(T[u].right != NIL)
    setDepth(T[u].right, par);

  if(T[u].left != NIL)
    setDepth(T[u].left, par+1);
}

void printch(int u){
  int c;
  int num=0;

  c = T[u].left;

  while(c != NIL){
    if(num == 0)
      printf("%d",c);

    else
      printf(", %d",c);

    num++;
    c = T[c].right;
  }
}



Measured memory_bytes: 6412
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;

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

  string s;
  cin>>s;
  bool flag = true;
  if(s[0] != 'A') flag = false;
  int cnt = 0;
  FOR(i, 2, s.size() - 1) {
    if(s[i] == 'C') cnt++;
  }
  if(cnt != 1) flag = false;
  rep(i,s.size()) {
    if(s[i] != 'A' && s[i] != 'C') {
      bool flag2 = false;
      for(char j = 'a'; j <= 'z'; j++)
      {
        if(s[i] == j) flag2 = true;
      }
      if(!flag2) flag = false;
    }
  }
  if(flag) {
    cout << "AC" << endl;
  } else {
    cout << "WA" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    h = list(map(int, input().rstrip('\n').split()))
    h[0] -= 1
    for i in range(1, n):
        if h[i] > h[i-1]:
            h[i] -= 1
        if h[i] < h[i-1]:
            print("No")
            exit()
    print("Yes")


if __name__ == '__main__':
    main()


Measured memory_bytes: 63856
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	var c string
	fmt.Fscan(r, &n, &c)

	wc := make([]int, n)
	for i := 0; i < n; i++ {
		if c[i] == 'W' {
			wc[i] = 1
		}
	}
	for i := 1; i < n; i++ {
		wc[i] += wc[i-1]
	}

	red := n - wc[n-1]
	if wc[n-1] == n || red == n {
		fmt.Println(0)
	} else {
		ans := wc[red-1]
		if ans > red {
			ans = red
		}
		fmt.Println(ans)
	}
}


Measured memory_bytes: 4832
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i,n) for(ll i=n-1; i>=0; --i)
#define rrep1(i,n) for(ll i=n; i>0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define coutl cout<<fixed<<setprecision(10)
template<class T>bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if (b<a){a=b;return 1;}return 0;}
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
// clang-format on

void solve(long long N, std::string S) {
  int n = N % 26;
  rep(i, S.size()) {
    S[i] += n;
    if (S[i] > 'Z') {
      S[i] -= 26;
    }
  }
  cout << S << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::string S;
  std::cin >> S;
  solve(N, S);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
const int N=705;
int n,m,a[N][N],s[2],c[N],ans=1e9;
bool v[N],flg;
bitset<N>b;
int read()
{
	int r=0,f=1;
	char p=getchar();
	while(p>'9'||p<'0')
	{
		if(p=='-')
			f=-1;
		p=getchar();
	}
	while(p>='0'&&p<='9')
	{
		r=r*10+p-48;
		p=getchar();
	}
	return r*f;
}
void dfs(int u,int col)
{
	c[u]=col;
	v[u]=1;
	s[col]++;
	for(int i=1;i<=n;i++)
		if(i!=u&&!a[u][i])
		{
			if(!v[i])
				dfs(i,col^1);
			else if(c[i]!=col^1)
				flg=1;
		}
}
int main()
{
	n=read(),m=read();b[0]=1;
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		a[x][y]=a[y][x]=1;
	}
	for(int i=1;i<=n;i++)
		if(!v[i])
		{
			s[0]=s[1]=0;
			dfs(i,0);
			b=(b<<s[0])|(b<<s[1]);
		}
	if(flg==1)
	{
		puts("-1");
		return 0;
	}
	for(int i=0;i<=n;i++)
		if(b[i])
			ans=min(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

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

    int a, b;
    cin >> a >> b;

    if (a<=0 and b>=0) cout << "Zero\n";
    else if ((a>0 and b>0) or (b-a)%2 != 0) cout << "Positive\n";
    else cout << "Negative\n";
}

Measured memory_bytes: 256
n=int(input())
x=[-1]*n
y=[-1]*n
h=[-1]*n
for i in range(n):
  x[i],y[i],h[i]=map(int,input().split())

mh=max(h)
for cx in range(0,101):
  for cy in range(0,101):
    for H in range(mh,mh+216):
      if all(h[j]==max(H-abs(cx-x[j])-abs(cy-y[j]),0) for j in range(n)):
        print(cx,cy,H)
        exit()


Measured memory_bytes: 9224
N,M,K = list(map(int,input().split()))

e_list = [[] for i in range(N)]

b_list = [[] for i in range(N)]

edge1 = []
edge2 = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge1.append((a,b))
    e_list[a].append(b)
    e_list[b].append(a)

for i in range(K):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    edge2.append((a,b))
    b_list[a].append(b)
    b_list[b].append(a)

color = [-1]*N

from collections import deque

def BFS(vi,c):
    Q = deque([vi])
    color[vi]=c
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color[v1]==-1:
                color[v1]=c
                Q.appendleft(v1)

c=0

for i in range(N):
    if color[i]==-1:
        BFS(i,c)
        c+=1

member = [0]*(max(color)+1)

for i in range(N):
    member[color[i]]+=1
#rint(member)
ans = []
for i in range(N):
    a = member[color[i]] -1 - len(e_list[i]) 
    for j in range(len(b_list[i])):
        if color[i]==color[b_list[i][j]]:
            a-=1

    ans.append(a)

print(*ans)

"""
good = [0]*(max(color)+1)
bad = [0]*(max(color)+1)
for i in range(M):
    good[color[edge1[i][0]]]+=1

for i in range(K):
    bad[color[edge2[i][0]]]+=1

ans = 0
for i in range(len(member)):
    ans += (member[i]*(member[i]-1))//2 - good[i] - bad[i]

print(ans)
"""

Measured memory_bytes: 109744
def solve(n, s):
    l, r = 0, n // 2 + 1
    while l < r:
        m = (l + r + 1) // 2
        if search(m, s):
            l = m
        else:
            r = m - 1
    return l


def search(w, s):
    w2 = w * 2
    appeared = [hash(s[i - w:i]) for i in range(w, w2)]
    comparing = set()

    for i in range(w2, n + 1):
        t = hash(s[i - w:i])
        comparing.add(appeared[i - w2])
        if t in comparing:
            return True
        appeared.append(t)

    return False


n = int(input())
s = input()
print(solve(n, s))


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((a+b+c == max({a,b,c})*2) ? "Yes" : "No") << endl;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;


ll odd(ll a){
  return (a+1)/2%2;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  n--,m--;
  cout<<n*m<<endl;
}


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

int main()
{
    int q;
    cin >> q;
    while (q > 0)
    {
        int dp[1010][1010] = {0};

        string X, Y;
        cin >> X >> Y;

        for (int i = 0; i <= X.size(); i++)
        {
            for (int j = 0; j <= Y.size(); j++)
            {
                if (X[i] == Y[j])
                {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j] + 1);
                }
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
            }
        }

        cout << dp[X.size()][Y.size()] << endl;
        q--;
    }
    return 0;
}



Measured memory_bytes: 7156
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
minans = inf ;ans = 0 ;count = 0 ;pro = 1

a=int(input())
b=int(input())
ans=[1,2,3]
for ai in ans:
    if ai!=b and ai!=a:
        print(ai)

Measured memory_bytes: 38256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    long long x = min(b - 1, n);
    long long y = (a * x) / b - a * (x / b);
    cout << y << endl;

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
//F6編譯，右上三角形執行，ctrl+c強制停止執行  F5開啟exe
#define ll long long
#define maxn 200005
#define mod 998244353
using namespace std;

typedef pair<int, int> P;

int n, m, q;
int a[maxn], b[maxn], c[maxn], d[maxn];
int A[maxn];
int ans = 0;

void dfs(int now)
{
    if (now == n + 1)
    {
        int tot = 0;
        for (int i = 0; i < q; i++)
        {
            if (A[b[i]] - A[a[i]] == c[i])
                tot += d[i];
        }
        ans = max(ans, tot);
        return;
    }
    for (int i = A[now - 1]; i <= m; i++)
    {
        A[now] = i;
        dfs(now + 1);
    }
}

int main()
{
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++)
        scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
    A[0] = 1;
    dfs(1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3704
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

int main()
{
   int N,D;
   int X[10][10];
   std::cin >> N >> D;
   for(int i=0; i<N; i++){
       for(int j=0; j<D; j++){
           std::cin >> X[i][j];
       }
   }

   int count=0;
   double distance=0;
   for(int i=1; i<N; i++){
       for(int j=0; j<i;j++){
           for(int k=0; k<D; k++){
               distance+=std::pow((X[i][k]-X[j][k]),2);
           }
           distance=std::sqrt(distance);
           if(distance==std::floor(distance)){
               count++;
           }
           distance=0;
       }
   }
   std::cout << count << std::endl;
    return 0;
}

Measured memory_bytes: 256
S = gets.chomp.codepoints
T = gets.chomp.codepoints
s_size = S.size
t_size = T.size

dp = Array.new(S.size + 1) { Array.new(T.size + 1, 0) }

def max a,b
  a > b ? a : b
end

S.size.times do |s0|
  s1 = s0 + 1
  cdp = dp[s0]
  ndp = dp[s1]

  t_size.times do |t0|
    t1 = t0 + 1
    if S[s0] == T[t0]
      ndp[t1] = cdp[t0] + 1
    else
      ndp[t1] = max(ndp[t0], cdp[t1])
    end
  end
end

i = dp[S.size][T.size]
s = S.size
t = T.size
a = []

while i > 0
  if dp[s-1][t] == i
    s -= 1
  elsif dp[s][t-1] == i
    t -= 1
  else
    a.unshift(S[s - 1])
    i -= 1
    s -= 1
    t -= 1
  end
end

print a.pack('U*')

Measured memory_bytes: 73468
#include <iostream>
using namespace std;
int main() {
    int a[5];
    for(int i=0;i<5;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<5;i++)
    {
        if(a[i]==0)
        {
            cout<<i+1<<"\n";
            break;
        }
    }

}


Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
#include <limits.h>

int main(void){
    int x1,y1,x2,y2,x3,y3,x4,y4;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    if (y1==y2){
        printf("%d %d %d %d\n",x2,y2+(x2-x1),x1,y2+(x2-x1));
        return 0;
    } else if (x1==x2){
        printf("%d %d %d %d\n",x1+(y1-y2),y2,x1+(y1-y2),y1);
        return 0;
    } else if (x1<x2 && y1>y2){
        x3=x2+(y1-y2);
        y3=y2+(x2-x1);
        x4=x3-(x2-x1);
        y4=y3+(y1-y2);
    } else if (x1<x2 && y1<y2){
        x3=x2-(y2-y1);
        y3=y2+(x2-x1);
        x4=x3-(x2-x1);
        y4=y3-(y2-y1);
    } else if (x1>x2 && y1<y2){
        x3=x2-(y2-y1);
        y3=y2-(x1-x2);
        x4=x3+(x1-x2);
        y4=y3-(y2-y1);
    } else {
        x3=x2+(y1-y2);
        y3=y2-(x1-x2);
        x4=x3+(x1-x2);
        y4=y3+(y1-y2);
    }
    printf("%d %d %d %d\n",x3,y3,x4,y4);
	return 0 ;
}

Measured memory_bytes: 128
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int[] height = new int[10];
		for (int i = 0; i < 10; i++) {
			height[i] = scanner.nextInt();
		}
		Arrays.sort(height);
		System.out.println(height[9]);
		System.out.println(height[8]);
		System.out.println(height[7]);
	}
}

Measured memory_bytes: 26140
#include <iostream>
#include <map>

int main(void)
{
    std::map<const char, int> typeToIndex = { {'S', 0}, {'H', 1}, {'C', 2}, {'D', 3} };
    std::map<const int, char> indexToType = { {0, 'S'}, {1, 'H'}, {2, 'C'}, {3, 'D'} };
    bool card[4][13] = {false};
    int n;
    std::cin >> n;
    char type;
    int num;
    for(int i = 0; i < n; i++) {
        std::cin >> type >> num;
        card[typeToIndex[type]][num-1] = true;
    }

    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 13; j++) {
            if(card[i][j] == false) {
                std::cout << indexToType[i] << " " << j+1 << std::endl;
            }
        }
    }
}

Measured memory_bytes: 1196
s = input().split()
n = int(s[0])
k = int(s[1])

arrays = []
answer = 0
count = 0

for i in range(100001):
    arrays.append(0)

for i in range(n):
    v = input().split()
    p = int(v[0])
    q = int(v[1])
    arrays[p] += q

for i in range(len(arrays)):
    if not arrays[i] == 0:
        count += arrays[i]
        if k <= count:
            answer = i
            break

print(answer)



Measured memory_bytes: 11656
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>

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

using namespace std;
typedef long long int ll;
const ll INF = 1000000000000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

int main()
{
    int x, y;
    cin >> x >> y;
    if (y % 2) {
        cout << "No" << endl;
        return 0;
    }
    int a = -x + (y / 2);
    int b = (2 * x) - (y / 2);
    if (a < 0 || b < 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)
typedef pair<int,int> Paint;
bool b[51][51];
bool gone[51][51];

void debug(int n){
  for(int i = 0; n > i; i++){
    for(int j = 0; n > j; j++){
      cout << (b[i][j] ? "1" : "0");
    }
    cout << endl;
  }
}

void init(int landnm){
  rep(i,landnm){
    rep(j,landnm){
      gone[i][j] = false;
    }
  }
}
bool tansaku(int i,int j,int landnm){
  //cout << "enter_tansaku" << endl;
  if(b[i][j]){
    //cout << "found->" << i << " " << j << endl;
    return true;
  }else{
    for(int k = 0; landnm > k;k++){
      if(i == k || j == k)continue;
      if(b[i][k] && !gone[i][k]){
        //cout << "moreenter->" << i << "->" << k << endl;
        gone[i][k] = true;
        gone[k][i] = true;
        if(tansaku(k,j,landnm))return true;
      }else{
        //cout << "noenter->" << i << " " << k << endl;
      }
    }
    return false;
  }
}
bool allconnect(int islandnm){
  for(int i = 0; islandnm > i; i++){
    for(int j = 0; islandnm > j; j++){
      if(i==j)continue;
      init(islandnm);
      //cout << "init->" <<  i << " " << j << endl;
      if(tansaku(i,j,islandnm)){
        //cout << "next." << endl;
        continue;
      }else{
        //cout << "goodbye." << endl;
        return false;
      } 
    }
  }
  return true;
}

int main(){
  int n,m;cin>>n>>m;
  int kekka = 0;
  vector<Paint> a;
  init(n);
  rep(i,n){
    rep(j,n){
      b[i][j] = false;
      
    }
  }
  
  for(int i = 0; m > i; i++){
    int tm,pp;cin>>tm>>pp;
    tm--;pp--;
    b[tm][pp] = true;
    b[pp][tm] = true;
    a.push_back(make_pair(tm,pp));
  }


  for(int i = 0; m > i; i++){
    b[a[i].first][a[i].second] = false;
    b[a[i].second][a[i].first] = false;
    //debug(n);
    //out << i << endl;
    if(!allconnect(n)){
      kekka++;
      //cout << "cant:" << i << endl;
    }else{
      //cout << "can :" << i << endl;
    }

    b[a[i].first][a[i].second] = true;
    b[a[i].second][a[i].first] = true;
  }
  cout << kekka << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define stpr setprecision
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REP(i,a,b) for(ll i=(a);i<(b);++i)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define endl '\n'
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ld EPS=10e-8;
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

ll A[11];
 
int main() {
    ll N,K,X,T;cin >> N >> K;
    rep(i,K){
        cin >> X;
        A[X]=1;
    }
    for(int i = N;i <= 99999; i++){
        X=i;
        T=0;
        while(X>0){
            if(A[X%10]==1){
                T=1;
            }
            X/=10;
        }
        if(T==0){
            cout <<  i << endl;
            return 0;
        }
    }
}

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

typedef long long ll;

const int Maxn = 200005;

char str[Maxn];
int slen;
bool tk[Maxn];
int len;
ll res;

int main()
{
    scanf("%s", str); slen = strlen(str);
    for (int i = 0; i < slen; i++)
        if (str[i] == '1' || str[i] == '0' && len % 2 == 1) {
            len++;
            res += (len + 1) / 2;
            tk[i] = true;
        }
    int ev = 0, od = 0;
    for (int i = slen - 1; i >= 0; i--)
        if (tk[i]) {
            if (str[i] == '1')
                if (len % 2) od++;
                else ev++;
            len--;
        } else {
            swap(ev, od);
            res += (len + 1) / 2 + od;
        }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 4120
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

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

        final int n = sc.nextInt();
        final int m = sc.nextInt();

        final int[] p = new int[m];
        final String[] s = new String[m];
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            p[i] = sc.nextInt();
            s[i] = sc.next();
            if (!map.containsKey(p[i])) {
                map.put(p[i], new int[2]);
            }
            if ("AC".equals(s[i])) {
                map.put(p[i], new int[]{ ++map.get(p[i])[0], map.get(p[i])[1] });
            }
            if ("WA".equals(s[i]) && map.get(p[i])[0] < 1) {
                map.put(p[i], new int[]{map.get(p[i])[0], ++map.get(p[i])[1]});
            }
        }

        int ok = 0;
        int ng = 0;
        for (Map.Entry<Integer, int[]> entry: map.entrySet()) {
            if (entry.getValue()[0] > 0) {
                ok++;
                ng += entry.getValue()[1];
            }
        }

        System.out.println(ok + " " + ng);
    }
}


Measured memory_bytes: 75740
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
struct edge { ll s, t, x; };
typedef pair<int, int> P;
typedef pair<ll,P> event;
const ll MAX = 510000;
const ll MOD = 1000000007;
#define INF (ll)1000000000000

int main() {
  int N;
  cin>>N;
  vector<int>A(N);
  vector<P>iti(N);
  ll memo[N][2];
  rep(i,N){memo[i][0]=0ll;memo[i][1]=0ll;}
  rep(i,N){
    cin>>A[i];
    A[i]--;
    iti[i]=P(A[i],i);
  }
  sort(iti.begin(),iti.end());
  set<int>st1;
  set<int>st2;
  st1.insert(1);
  st2.insert(N);
  rep(i,N){
    auto t=*st1.lower_bound(-1*iti[i].second);
    memo[i][0]=t+iti[i].second;
    st1.insert(-1*iti[i].second);
  }
  rep(i,N){
    auto t=*st2.lower_bound(iti[i].second);
    memo[i][1]=t-iti[i].second;
    st2.insert(iti[i].second);
  }
  ll ans=0ll;
  rep(i,N){
    ll x=memo[i][0]*memo[i][1];
    ans+=x*(i+1ll);
  }
  cout<<ans;
  
}


Measured memory_bytes: 27488
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n = s.length();
    if(n%2!=0) {
        cout<<"No\n";
        return 0;
    }
    for(int i =0;i<n;i+=2)
    {
       if(s[i]=='h' && s[i+1]=='i') continue;
       else{
           cout<<"No\n";
           return 0;
       }
    }
    cout<<"Yes\n";
    return 0;
}

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

int main(void) {
    int x, a, b, ate;
    cin >> x >> a >> b;
    if (b - a <= 0) cout << "delicious" << endl;
    else if (b - a <= x) cout << "safe" << endl;
    else cout << "dangerous" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v) cerr << #v << ":"; rep(i, v.size()) cerr << " " << v[i]; cerr << endl
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; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

template<int mod>
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

const int mod = 998244353;
using Mint = ModInt<mod>;

Mint dp[3030][6060];

int main(){
    int n, s;
    cin >> n >> s;
    dp[0][0] = 1;
    rep(i, n) {
        int a;
        cin >> a;
        rep(j, s + 1) {
            dp[i + 1][j] += dp[i][j] * 2;
            dp[i + 1][j + a] += dp[i][j];
        }
    }
    cout << dp[n][s] << endl;
}


Measured memory_bytes: 75368
n,y = map(int,input().split())

y = y//1000

for a in range(n+1):
	for b in range(0,n+1-a):
		c = n - (a+b)
		if y == 10*a + 5*b + c:
			print(a,b,c)
			exit()


print("-1 -1 -1")

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

int main() 
{
    int n;
    cin >> n;
    int f[n][10], p[n][11];
    for (int i=0; i<n; i++)
        for (int j=0; j<10; j++)
            cin >> f[i][j];
    for (int i=0; i<n; i++)
        for (int j=0; j<11; j++)
            cin >> p[i][j];
    int ans = -INT_MAX;
    for(int b = 1; b < (1<<10); b++)
    {
        vector<int> bin(n,0);
        for(int i=0; i<10; i++) if(b & (1<<i))
        {
            for (int j=0; j<n; j++)
                if (f[j][i] == 1)
                    bin[j]++;
        }
        int act = 0;
        for (int i = 0; i < n; i++) {
            act += p[i][bin[i]];
        }
        ans = max(act, ans);
    }
    cout << ans;
    return 0;
}

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

using namespace std;

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair< T, int > dfs(const WeightedGraph< T > &g, int idx, int par) {
  pair< T, int > ret(0, idx);
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto cost = dfs(g, e.to, idx);
    cost.first += e.cost;
    ret = max(ret, cost);
  }
  return ret;
}

template< typename T >
T tree_diameter(const WeightedGraph< T > &g) {
  auto p = dfs(g, 0, -1);
  auto q = dfs(g, p.second, -1);
  return (q.first);
}

int main() {
  int N;
  scanf("%d", &N);
  WeightedGraph< int > g(N);
  for(int i = 1; i < N; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  printf("%d\n", tree_diameter(g));
}


Measured memory_bytes: 16020
n=gets.to_i
a=(2..n).map{gets.split.map &:to_i}
a.each_index{|i|
    t=0
    a[i..n-1].each{|c,s,f|t=c+(t<s ?s:(t%f==0?t:t+f-t%f))}
    p t
}
p 0

Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int mean_i;
  double a,b,mean;
  
  cin >> a;
  cin >> b;
  
  mean_i = (a+b)/2;
  mean = (a+b)/2;
  
  if (mean-mean_i == 0.5){
    mean_i = mean_i+1;
  }
  
  cout << mean_i << endl;
}
    
  
  

Measured memory_bytes: 256
x = []
for i in range(5):
        x.append(int(input()))
k = int(input())
a = x[0]
n = True
for i in x:
        b = abs(a-i)
        if b > k:
                n = False
        else:
                None
if not n:
        print(":(")
else:
        print("Yay!")

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string sS = Console.ReadLine().Trim();

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            string sOut = "No";
            if (sS.Reverse().SequenceEqual(sS)) { sOut = "Yes"; }

            //出力
            Console.WriteLine("{0}", sOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }
}


Measured memory_bytes: 13396
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;
int a[N];

int main()
{
  int n;
  cin >> n;
  for(int i = 0; i < n; ++i)
    cin >> a[i];
  
  sort(a, a+n, greater<int>());
  
  queue<int> qu;
  LL res = 0;
  qu.push(a[0]);
  
  for(int i = 1; i < n; ++i)
  {
    res += qu.front();
    qu.pop();
    qu.push(a[i]);
    qu.push(a[i]);
  }
  
  cout << res << endl;
  
  return 0;
}

Measured memory_bytes: 5104
import math
import itertools

# 入力
n = int(input())
town = dict()
for i in range(n):
    x, y = map(int, input().split())
    town[i] = [x, y]


def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)


total = 0
for p in itertools.permutations(town, n):
    bef = p[0]
    for i in p[1:]:
        total += distance(town[bef], town[i])
        bef = i

print(total/math.factorial(n))





Measured memory_bytes: 3064