akhauriyash/Code-Regression huggingface dataset:
//#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<ctype.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dy[4]={0,1,0,-1};
//----------program from here----------

int ctoi(int x){
  return int(x-48);
}

int main(){
  int r=0,g=0,b=0,num=0;
  cin >> r >> g >> b;
  num = ctoi(r)*100 + ctoi(g)*10 + ctoi(b);
  cout << (num%4?"NO":"YES") << endl;

  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace abc162_c
{
  class Program
  {
    static void Main(string[] args)
    {
      var K = CIn.ReadInt();

      var ans = 0L;

      for (int i = 1; i <= K; i++)
      {
        for (int j = 1; j <= K; j++)
        {
          for (int k = 1; k <= K; k++)
          {
            ans += MathTools.Gcd(MathTools.Gcd(i, j), k);
          }
        }
      }

      Console.WriteLine(ans);
    }
  }


  static class MathTools
  {
    public static long Gcd(long a, long b)
    {
      while (b != 0)
      {
        var mod = a % b;
        a = b;
        b = mod;
      }
      return a;
    }

    public static long Lcm(long a, long b)
    {
      return a * b / Gcd(a, b);
    }

    public static List<long> PrimeNumbers(long n)
    {
      var list = new List<long>();
      var sieve = new bool[n + 1];

      for (var i = 2; i <= n; i++)
      {
        if (!sieve[i])
        {
          list.Add(i);
          for (var j = i * 2; j <= n; j += i)
          {
            sieve[j] = true;
          }
        }
      }
      return list;
    }

    public static List<long> PrimeFactors(long n)
    {
      var list = new List<long>();
      var primeNumbers = PrimeNumbers((long)Math.Sqrt(n));

      foreach (var p in primeNumbers)
      {
        if (n == 1)
        {
          break;
        }
        while (n % p == 0)
        {
          n /= p;
          list.Add(p);
        }
      }
      if (n > 1)
      {
        list.Add(n);
      }
      return list;
    }
  }

  static class CIn
  {
    private static readonly Queue<string> fieldBuffer = new Queue<string>();

    public static string Read()
    {
      if (fieldBuffer.Count == 0)
      {
        foreach (var field in Console.ReadLine().Split())
        {
          fieldBuffer.Enqueue(field);
        }
      }
      return fieldBuffer.Dequeue();
    }

    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());

    public static string[] ReadStringArray(int n)
    {
      var array = new string[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = Read();
      }
      return array;
    }

    public static int[] ReadIntArray(int n)
    {
      var array = new int[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadInt();
      }
      return array;
    }

    public static long[] ReadLongArray(int n)
    {
      var array = new long[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadLong();
      }
      return array;
    }

    public static double[] ReadDoubleArray(int n)
    {
      var array = new double[n];
      for (var i = 0; i < n; i++)
      {
        array[i] = ReadDouble();
      }
      return array;
    }

    public static char[,] ReadCharMatrix(int h, int w)
    {
      var array = new char[h, w];
      for (var i = 0; i < h; i++)
      {
        var l = Console.ReadLine().ToCharArray();
        for (var j = 0; j < w; j++)
        {
          array[i, j] = l[j];
        }
      }
      return array;
    }
  }
}


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

int main(){
  string S,T;

  cin >> S >> T;
  for(int i=0;i<S.size();++i){
    if(S.at(i) != T.at(i)){
      cout << "No" << endl;
      return 0;
    }
  }
  if(S.size() < T.size()){
    cout << "Yes" << endl;
  }  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3628
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> b(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int res = 0;
        for (int i = 0; i < m; i++) {
            int a;
            cin >> a;
            res += b[i] * a;
        }
        if (res + c > 0)
            cnt++;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
n,a,b,k=map(int,input().split())
p=998244353
def getinv(n):
  inv=[0]*(n+1)
  for i in range(1,n+1):
    inv[i]=pow(i,p-2,p)
  return inv
def getnCr(n):
  inv=getinv(n)
  nCr=[0]*(n+1)
  nCr[0]=1
  for i in range(1,n+1):
    nCr[i]=(nCr[i-1]*(n-i+1)*inv[i])%p
  return nCr
def solve(n,a,b,k):
  ans=0
  nCr=getnCr(n)
  for i in range(n+1):
    if (k-a*i)<0 or (k-a*i)%b!=0:
      continue
    j=(k-a*i)//b
    if a*i+b*j==k and 0<=j<=n:
      ans+= nCr[i]*nCr[j]
      ans%=p
  return ans
print(solve(n,a,b,k))

Measured memory_bytes: 26788
#include<stdio.h>
#define MAX 100000
int main(){
  int n,i;
  int A[MAX+1];
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d",&A[i]);
  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(i/2>=1)
      printf("parent key = %d, ",A[i/2]);
    if(i*2<=n)
      printf("left key = %d, ",A[i*2]);
    if(i*2+1<=n)
      printf("right key = %d, ",A[i*2+1]);
    printf("\n");
  }
  return 0;
}
  



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

template<typename T> 
map<T,int> factorize(T x){
    map<T,int> mp;
    for (T i = 2; i*i <= x; i++){
        while (x%i == 0) {
            x /= i;
            mp[i]++;
        }
    }
    if (x != 1) mp[x]++;
    return mp;
}

int main(void){
    ll n, p;
    cin >> n >> p;
    auto cnt = factorize(p);
    ll res = 1;
    for (auto itr : cnt) {
        if (itr.second >= n) {
            res *= pow(itr.first, (itr.second / n));
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <stack>
#include <bitset>
#include <sstream>

using namespace std;

#define FSIO  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define DEBUG(a)   cout<<"DEBUG: "<<(a)<<endl;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define MP make_pair
#define X  first
#define Y  second
#define REP(i,st,ed)    for(int i=st;i<=ed;++i)
#define IREP(i,st,ed)   for(int i=st;i>=ed;--i)
#define TCASE(T)    cin>>T;while(T--)

const int MAXN = 5005;
const ll MOD = 1e9+7 ;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 1e9+7;
const double PI = acos(-1.0);
const double EPS = 1e-8;

int _;

using namespace std;


bool cmp(const string& a, const string& b)
{
    if(a.length()!=b.length())   return a.length()<b.length();
    else
    {
        int len = a.length();
        for(int i=0;i<len;++i)
            if(a[i]!=b[i])   return a[i]<b[i];
        return 1;
    }
}

string dp[10005];
int aa[15];

int main()
{
    //freopen("test.in","r+",stdin);
    //freopen("test.out","w+",stdout);
    FSIO;
    int cost[] = {0,2,5,5,4,5,6,3,7,6};
    int N, M;
    cin>>N>>M;
    REP(i,1,M)  cin>>aa[i];
    sort(aa+1,aa+1+M);
    reverse(aa+1,aa+1+M);

    for(int i=0;i<=N;++i)
    {
        if(i&&!dp[i].length())  continue;
        for(int j=1;j<=M;++j)
        {
            if(i+cost[aa[j]]<=N&&cmp(dp[i+cost[aa[j]]],dp[i]+char('0'+aa[j])))
                dp[i+cost[aa[j]]] = dp[i]+char('0'+aa[j]);
        }
    }
    cout<<dp[N]<<endl;
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    int num[] = {1,2,4,8,16,32,64};
    
    for(int i=0;i<n;i++){
        if(n<num[i]){
            cout << num[i-1] << endl;
            break;
        }else if(n==num[i]){
            cout << num[i] << endl;
            break;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3608
global input_n
global input_data
global result

#インプットdata
input_n = int(input())
input_data = list(map(int, input().split()))
result = 0

#バブルソートプログラム
def bubbleSort():
    global result
    for i in range(input_n):
        jude = result
        for j in range(input_n-1, i, -1):
            if input_data[j] < input_data[j-1]:
                input_data[j], input_data[j-1] = input_data[j-1], input_data[j]
                result += 1
        if jude == result: break

#アルゴリズム：ソート
def merge(left, mid, right):
    global result
    
    n1 = mid - left
    n2 = right - mid
    inf = 10**9
    L_list = input_data[left: mid] + [inf]
    R_list = input_data[mid: right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        if L_list[i] <= R_list[j]:
            input_data[k] = L_list[i]
            i += 1
        else:
            input_data[k] = R_list[j]
            j += 1
            result += n1 - i

#アルゴリズム：マージソート
def mergeSort(left, right):
    if (left + 1) < right:
        mid = (left + right) // 2
        mergeSort(left, mid)
        mergeSort(mid, right)
        merge(left, mid, right)

#処理の実行
#bubbleSort()
mergeSort(0, input_n)
print(result)


Measured memory_bytes: 27488
using System;

namespace C_sharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine();
            var rc = line.Split();
            var r = int.Parse(rc[0]);
            var c = int.Parse(rc[1]);

            var total = new int[c+1];
            for (var i = 0; i < r; i++)
            {
                line = Console.ReadLine();
                var row = line.Split(' ');

                var row_sum = 0;
                for (var j = 0; j < c; j++)
                {
                    var n = int.Parse(row[j]);
                    row_sum += n;
                    total[j] += n;
                }
                total[c] += row_sum;

                Console.Write(line);
                Console.WriteLine($" {row_sum}");
            }

            Console.WriteLine(string.Join(" ", total));
        }
    }
}



Measured memory_bytes: 19804
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

ll digit(ll n){ll k=0; while(n!=0){n/=10; k++;} return k;}  

ll my_pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main()
{
  ll N; cin>>N;
  
  if(N<10) {cout<<N<<endl; return 0;}
  
  vector<vector<ll>> table(10,vector<ll>(10,0));
  ll same_count=0;
  
  rep(i,N){
    ll n=i+1;
    table[n/my_pow(10,digit(n)-1)][n%10]++;
    if(n/my_pow(10,digit(n)-1)==n%10) same_count++;
  }
  
  ll ans=0;
  rep(i,10){
    rep(j,10){
      if(i==j) {ans+=table[i][i]*(table[i][i]-1); continue;}
      ans+=table[i][j]*table[j][i];
      //cout<<i<<" "<<j<<" "<<ans<<endl;
    }
  }
  ans+=same_count;
  
  cout<<ans<<endl;
  
  //cout<<same_count<<endl;
  /*
  rep(i,10){
    rep(j,10){
      if(j!=0) cout<<" ";
      cout<<table[i][j];
    }
    cout<<endl;
  }
  */
  return 0;
}

Measured memory_bytes: 3640
import itertools

def main():
    N,x = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    accum_a = list(itertools.accumulate(a))
    ans = 0
    for i in range(N):
        if accum_a[i] > x:
            break
        else:
            ans += 1
    if accum_a[-1] < x:
        ans -= 1
    print(ans)

if __name__ == '__main__':
    main()

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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define int ll

const ll MOD = 1000000007;
const ll INF_LL = (ll)1000000007 * 1000000007;
const int INF_INT = (int)1000000007;
const double PI = 3.14159265358979323846;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define irep(itr, st) for (auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for (auto itr = (st).rbegin(); itr != (st).rend(); ++itr)

#define m0(x) memset((x), 0, sizeof((x)))
#define m1(x) memset((x), -1, sizeof((x)))

// xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define RALL(x) (x).rbegin(), (x).rend()  // sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())     // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))  //最大値を求める
#define MIN(x) *min_element(ALL(x))  //最小値を求める
#define all(x) (x).begin(), (x).end()

//略記
#define pb emplace_back  // vectorヘの挿入
#define mp make_pair     // pairのコンストラクタ
#define F first          // pairの一つ目の要素
#define S second         // pairの二つ目の要素

#define BITCOUNT __builtin_popcount
#define BITCOUNT_LL(x) __builtin_popcountll(x)

#define perm(c)             \
  sort(all(c));             \
  for (bool c##p = 1; c##p; \
       c##p = next_permutation(all(c)))  //順列 123 132 213 231 312 321

#define BIT(n) (1LL << (n))

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ": " << (A) << std::endl;
#else
#define PRINT(A)
#endif

//入力高速化
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

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

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

signed main() {
  int N, A, B;
  cin >> N >> A >> B;
  if (A > B) {
    cout << 0 << endl;
    return 0;
  }
  if (N == 2) {
    cout << 1 << endl;
    return 0;
  }

  if (N == 1 && A == B) {
    cout << 1 << endl;
    return 0;
  }
  if (N == 1 && A != B) {
    cout << 0 << endl;
    return 0;
  }
  cout << (B - A) * (N - 2) + 1 << endl;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
c=list(map(int, input().split()))
cnt=0
for i,v in enumerate(a):
	cnt += b[v-1]
	if i == 0:continue
	if v-1 == a[i-1]:
		#print(c[v-1])
		cnt += c[v-2]
print(cnt)

Measured memory_bytes: 3060
import queue

K = int(input())

q = queue.Queue()

counter = 0
for i in range(1, 10):
    q.put(str(i))
    counter += 1
    if counter == K:
        print(i)
        break

while counter < K:
    n = q.get()
    if n[-1] == '0':
        for add in ['0', '1']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(int(n_add))
                break
    elif n[-1] == '9':
        for add in ['8', '9']:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break
    else:
        for add in [str(int(n[-1])-1), str(int(n[-1])), str(int(n[-1])+1)]:
            n_add = n + add
            q.put(n_add)
            counter += 1
            if counter == K:
                print(n_add)
                break

Measured memory_bytes: 8560
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
  int N;
  cin >> N;

  int card[100];
  for(int i = 0; i < N; i++){
    cin >> card[i];
  }

  sort(card, card + N, greater<int>());
  int result = 0;
  for(int i = 0; i < N; i++)
    result += card[i] * (i & 1 ? -1 : 1);

  cout << result  << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(ll)>
using namespace std;
#define All(v) (v).begin(),(v).end()
typedef long long ll;
const ll mod = 1000000007;
const ll inf = mod*mod;
const ll d5 = 114514;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1.0);
int main(){
    ll n;
    cin>>n;
    ll F[111][15],P[111][15];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<10;j++)cin>>F[i][j];
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<11;j++)cin>>P[i][j];
    }
    ll res = -inf;
    for(ll b=1;b<(1<<10);b++){
        ll tmp=0LL;
        for(ll i=0;i<n;i++){
            ll cnt = 0;
            for(ll j=0;j<10;j++){
                if((b>>j&1)&&F[i][j])cnt++;
            }
            tmp+=P[i][cnt];
        }
        res=max(res,tmp);
    }
    cout<<res<<endl;


}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;

void main() {
	auto input = getStdin!(string[])[0].split(" ");
	int w = input[0].to!(int);
	int h = input[1].to!(int);
	int x = input[2].to!(int);
	int y = input[3].to!(int);
	int r = input[4].to!(int);
	
	if (x - r < 0 || x + r > w || y - r < 0 || y + r > h) {
		"No".writeln;
	}
	else {
		"Yes".writeln;
	}
}

T getStdin(T)() {
    string[] cmd;
    string line;
    while ((line = chomp(stdin.readln())) != "") cmd ~= line;
    return to!(T)(cmd);
}

Measured memory_bytes: 2492
#include <bits/stdc++.h>
 
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

template<class D>
struct Hungarian {
    V<D> le, ri;
    V<int> perm;

    Hungarian(const VV<D> &c) {
        int n = int(c.size()), m = int(c[0].size());
        assert(n <= m);
        le = V<D>(n, D(0)); ri = V<D>(m, D(0));
        perm = V<int>(n);
        V<int> to_r(n, -1), to_l(m, -1);

        for (int l = 0; l < n; l++) {
            V<bool> l_u(n), r_u(m);
            V<int> tr(m, -1), min_l(m, l);
            l_u[l] = true;
            V<D> min_cost(m);
            for (int j = 0; j < m; j++) min_cost[j] = c[l][j] + le[l] + ri[j];
            while (true) {
                int r = -1;
                D d = numeric_limits<D>::max();
                for (int j = 0; j < m; j++) {
                    if (!r_u[j] && min_cost[j] < d) {
                        r = j;
                        d = min_cost[j];
                    }
                }
                for (int i = 0; i < n; i++) if (l_u[i]) le[i] -= d;
                for (int j = 0; j < m; j++) {
                    if (r_u[j]) ri[j] += d;
                    else min_cost[j] -= d;
                }
                tr[r] = min_l[r];
                int l = to_l[r];
                if (l == -1) {
                    while (r != -1) {
                        int nl = tr[r], nr = to_r[nl];
                        to_l[r] = nl; to_r[nl] = r;
                        r = nr;
                    }
                    break;
                }
                l_u[l] = r_u[r] = true;
                for (int j = 0; j < m; j++) {
                    D cost = c[l][j] + le[l] + ri[j];
                    if (cost < min_cost[j]) {
                        min_l[j] = l;
                        min_cost[j] = cost;
                    }
                }
            }
        }
        perm = to_r;
    }    
};

 
using D = double;
const D PI = acos(D(-1)), EPS = 1e-10;
using P = complex<D>;
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << fixed;
 
    D ans = 0;
 
    int n;
    cin >> n;
    V<P> up(n), dw(n);
    D x, y;
    cin >> x >> y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y; up[i] = P(x, y);
        cin >> x >> y; dw[i] = P(x, y);
        ans += abs(up[i]-dw[i]);
    }
 
    int l = int(up.size()), r = int(dw.size());
    VV<D> cost(l, V<D>(r));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < r; j++) {
            cost[i][j] = abs(up[i] - dw[j]);
        }
    }
    auto perm = Hungarian<D>(cost).perm;
    for (int i = 0; i < l; i++) {
        ans += cost[i][perm[i]];
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3892
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <utility>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int d[20][20];//d[u][v]??????e=(u,v)????????????(?????¨???????????´??????INF,??????d[i][i]=0??¨??????)
int V;//????????°

void warshall_floyd(){
	for(int k=0;k<V;k++){
		for(int i=0;i<V;i++){
			for(int j=0;j<V;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}

int main(){
	cin>>V;
	rep(i,0,20){
		rep(j,0,20){
			if(i==j) d[i][j]=0;
			else d[i][j]=1000000000;
		}
	}
	int m;
	cin>>m;
	int a,b,c,d1;
	rep(i,0,m){
		scanf("%d,%d,%d,%d",&a,&b,&c,&d1);
		a--; b--;
		d[a][b]=c;
		d[b][a]=d1;
	}
	int x1,x2,y1,y2,MIN;
	scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
	warshall_floyd();
	int ans=y1-y2-d[x1-1][x2-1]-d[x2-1][x1-1];
	o(ans);
}

Measured memory_bytes: 1240
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

struct Cake {
    long long x;
    long long y;
    long long z;
};

int main() {
    
    int N,M;
    cin >> N >> M;
    vector<Cake> A(N);
    vector<Cake> B(N);
    for ( int i = 0; i < N; i++ ) {
        long long x,y,z;
        cin >> x >> y >> z;
        A[i].x = x;
        A[i].y = y;
        A[i].z = z;
    }

    long long ans = 0;
    for ( int a = 0; a < 1<<3; a++ ) {

        vector<long long> C(N);
        for ( int i = 0; i < N; i++ ) {
            B[i] = A[i];
            if ( a&(1<<0) ) { B[i].x = -B[i].x; }
            if ( a&(1<<1) ) { B[i].y = -B[i].y; }
            if ( a&(1<<2) ) { B[i].z = -B[i].z; }

            C[i] = B[i].x+B[i].y+B[i].z;
        }

        long long sum = 0;
        sort( C.begin(), C.end(),greater<long long>() );
        for ( int i = 0; i < M; i++ ) {
            sum += C[i];
        }
        ans = max( ans, sum );
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import sys

# import bisect
from collections import Counter, deque

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class Edge:

    def __init__(self, index, u, v):
        self.index = index
        self.u = u
        self.v = v

    def __str__(self):
        return "{} {}".format(self.u, self.v)


class Vertex:

    def __init__(self, index):
        self.index = index
        self.connected_edge_index = []
        self.color = -1

    def __str__(self):
        return str(self.index)


class Graph:
    # 1-indexed

    def __init__(self, vertices=0):
        self.vertices = [Vertex(x) for x in range(vertices + 1)]
        self.edges = []
        self._vertex_count = vertices
        self._edges_count = 0

    def edges_count(self):
        return self._edges_count

    def vertices_count(self):
        return self._vertices_count

    def add_edge(self, u, v):
        edge = Edge(self._edges_count, u, v)
        self.vertices[edge.u].connected_edge_index.append(edge.index)
        self.vertices[edge.v].connected_edge_index.append(edge.index)
        self.edges.append(edge)
        self._edges_count += 1

    # 連結している節点を求める
    def neighbors(self, index):
        return [self.edges[e].u if self.edges[e].u != index else self.edges[e].v for e in
                self.vertices[index].connected_edge_index]

    # 連結要素数を求める
    def neighbors_count(self, index):
        return len(self.vertices[index].connected_edge_index)

    def __str__(self):
        desc = ""
        for i in range(self._edges_count):
            desc += str(self.edges[i]) + "\n"
        return desc


def main():
    n, k = list(map(int, readline().split()))
    g = Graph(n)

    for i in range(n-1):
        a, b = list(map(int, readline().split()))
        g.add_edge(a, b)

    que = deque()
    que.append((1, 0, k))

    while que:
        current, parent, c = que.popleft()
        g.vertices[current].color = c
        next_c = k - 1 - parent
        for i in g.neighbors(current):
            if g.vertices[i].color == -1:
                que.append((i, 1, next_c))
                next_c -= 1

    ans = 1

    for i in range(1, n + 1):
        ans *= g.vertices[i].color
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 77004
long d[2][5001];A,x,i,j;main(n){for(scanf("%d%d",&n,&A),d[0][n*=A]=1;~scanf("%d",&x);i=!i)for(x-=A,j=2*n+1;j--;)d[!i][j]=d[i][j]+(j<x|j-x>2*n?0:d[i][j-x]);printf("%ld",d[i][n]-1);}

Measured memory_bytes: 256
import math
N=int(input())
X=list(map(int, input().split()))

num=sum(X)/N
num1=math.floor(num)
num2=math.ceil(num)

R1=[(X[i]-num1)**2 for i in range(N)]
R2=[(X[i]-num2)**2 for i in range(N)]
print(min(sum(R1),sum(R2)))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;

template <typename T> void chmin(T &a,T b){ a = min(a,b);}

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    int sum = 1e9;

        for(int i=0,j=i+k-1; j < n ;i++,j++){
           chmin(sum, x[i+k-1]-x[i]+min(abs(x[i+k-1]),abs(x[i])));
        }

    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var L = double.Parse(Console.ReadLine());
            var answer = L * L * L / 27;
            Console.WriteLine(answer.ToString("f12"));
        }
    }
}


Measured memory_bytes: 13140
/* EDPC N 2019/1/6
 * 区間DP
 *  N: 2~400
 *  a: 1~10^9
 * 2020.3.31 作成
 */
#include<iostream>
#include<vector>
#include<algorithm> // max
//#include<cmath>
using namespace std;

int n;
vector<long> a;
vector<vector<long>> asum;
vector<vector<long>> dp;

void init(){
  cin >> n;
  a.assign(n+1,0);
  for(int i=1; i<n+1; i++){
    cin >> a[i];
  }
  vector<long> t1(n+1, 0);
  dp.assign(n+1, t1);
  asum.assign(n+1, t1);
}

// 漸化式
// dp(L,R) = min{0<=i<=R-L-1}(
//    sum_j=0^i(a[L+j]) +
//    sum_j=0^(R-L+1-i)(a[R-j]) +
//    dp(L,L+i) + dp(L+i+1,R) )
// 全区間のsumは先にやっておくべき
void dodp(){
  // sum_a 計算
  for(int L=1;L<n+1;L++){
    for(int R=L;R<n+1;R++){
      for(int i=L;i<=R;i++){
        asum[L][R] += a[i];
      }
    }
  }
  // dp
  for(int m=2;m<n+1;m++){ // 区間サイズ
    for(int L=1;L+m-1<n+1;L++){ // 左
      long temp = asum[L][L] + asum[L+1][L+m-1] + dp[L][L] + dp[L+1][L+m-1];
      for(int i=1;i<m-1;i++){
        temp = min(temp, asum[L][L+i] + asum[L+i+1][L+m-1] + dp[L][L+i] + dp[L+i+1][L+m-1] );
      }
      dp[L][L+m-1] = temp;
      //cout << "db: (" << L << "," << (L+m-1) << ") " << temp << endl;
    }
  }
  return;
}

int main(){
  init();
  dodp();
  cout << dp[1][n] << endl;
  return 0;
}

/*テストケース
4
10 20 30 40
出力
190
*/


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

int main(){
     ios_base::sync_with_stdio(false);
     string s;
     int a[30];
     
     cin>>s;
     for(int i=0;i<29;i++){
     	a[i] = 0;
     }
     
     for(int i=0;i<s.length();i++){
          a[s[i] - 'a']++;
     }
     
     for(int i=0;i<28;i++){
     	  //cout<<a[i]<<" ";
          if(a[i]%2){
               cout<<"No"<<endl;
               return 0;
          }
     }
     cout<<"Yes"<<endl;
     return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
ll maxVal = 1e18; 
 
int main() {
	std::ios_base::sync_with_stdio(false);
	ll n;
	ll ret = 0ll;
	cin >> n;
	vector<ll> a(n);
	int count0 = 0;
	for (int i= 0; i<n; i++) {
		cin >> a[i];
		count0 += (a[i]==0);
	} 
	if (!count0) {
		ret = 1ll;
		for (int i =0; i<n; i++) {
			if (a[i] <= maxVal/ret) ret *= a[i];
			else {ret = -1; break;}
		}
	}
	cout << ret << '\n';
}


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

int main() {
  char c[100];
  stack<int> s;
  while(scanf("%s",c)!=EOF){
    if(c[0]=='+'){
      int a=s.top();
      s.pop();
      int b=s.top();
      s.pop();
      s.push(a+b);
    }else if(c[0]=='-'){
      int a=s.top();
      s.pop();
      int b=s.top();
      s.pop();
      s.push(b-a);
    }else if(c[0]=='*'){
      int a=s.top();
      s.pop();
      int b=s.top();
      s.pop();
      s.push(a*b);
    }else{
      int x=atoi(c);
      s.push(x);
    }
  }
  cout<< s.top()<<endl;
  return 0;
}
    


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

int main() {
    int n;
    string s,sub1,sub2;
    cin >> n >> s;
    sub1 = s.substr(0,n/2);
    sub2 = s.substr(n/2,n);
    if(sub1 == sub2){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
signed main()
{
int x=0,y=0,z=1000,w=0,n=0,m=0,a=0,b=0;
std::cin >> x;
rep(i,x){
  std::cin >> y;
  if(z>y)z=y;
  if(w<y)w=y;
}
std::cout << w-z << '\n';
return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=200005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f; 
const ld pi=acos(-1.0L);
bool a[maxn],b[maxn];

int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
    int n,m,i,x,y,z;
	scanf("%d%d",&n,&m);
	mem0(a);mem0(b);
	for (i=1;i<=m;i++) {
		scanf("%d%d",&x,&y);
		if (x>y) {
			z=x;x=y;y=z;
		}
		if (x==1) a[y]=1;
		if (y==n) b[x]=1; 
	}
	for (i=2;i<n;i++) {
		if (a[i]&&b[i]) {
			cout << "POSSIBLE\n";
			return 0;
		}
	}
	cout << "IMPOSSIBLE\n";
	return 0;
}


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

using namespace std;
typedef long long unsigned int ll;
int main() {
  ll N;
  cin >> N;
  ll minPass = 1e15 + 3LL;
  for (int i = 0; i < 5; ++i) {
    ll x;
    cin >> x;
    minPass = min(minPass, x);
  }
  if (minPass >= N) {
    cout << 5 << endl;
    return 0;
  }
  ll ans = ceil((double)(N - minPass) / minPass) + 5LL ;
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int MOD = 1000000007;
int INF = numeric_limits<int>::max() / 2;


signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int N;
  string S, T, W = {};
  cin >> N >> S >> T;
  for(int i=0;i<N;i++){
    W += S[i];
    W += T[i];
  }
  cout << W << endl;
}

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

int main(){
  string S,T;
  cin>>S>>T;
  string ans="UNRESTORABLE";
  int n=S.size();
  int m=T.size();
  for(int i=0;i<n-m+1;i++){
    bool flag=true;
    string SS=S;
    for(int j=0;j<m;j++){
      if(SS.at(i+j)=='?'){
        SS.at(i+j)=T.at(j);
        continue;
      }
      if(S.at(i+j)!=T.at(j)){
        flag=false;
        break;
      }
    }
    if(flag){
      for(int i=0;i<n;i++){
        if(SS.at(i)=='?'){
          SS.at(i)='a';
        }
      }
      if(ans=="UNRESTORABLE"){
        ans=SS;
      }else{
        ans=min(ans,SS);
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
static const int MAX=100000;
static const int NIL=-1;
int n;
vector<int>G[MAX]; //頂点数を100000とする
                   //隣接リスト
int color[MAX];
void dfs(int r,int c){
  stack<int>S;
  S.push(r); //始点rをスタックに追加
  color[r]=c;//色を入れる
  while(!S.empty()){ //スタックがからでない間
    int u=S.top();
    S.pop(); //スタックから頂点uを取り出し訪問
    for(int i=0;i<G[u].size();i++){
      //頂点uに隣接する頂点vを探索
      int v=G[u][i];
      if(color[v]==NIL){
	color[v]=c;
	S.push(v); //id(色)は変わらない
      }
    }
  }
}
int main(){
  int m,s,t,q;
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>s>>t;
    G[s].push_back(t); //sからtへ辺
    G[t].push_back(s); //tからsへ辺
  }
  int id=1; //colorに入れる色(情報)
  for(int i=0;i<n;i++){
    color[i]=NIL; //全てにNIL
  }
  for(int u=0;u<n;u++){
    if(color[u]==NIL) dfs(u,id++); //id(色)にかぶりがないように
  }
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>s>>t;
    if(color[s]==color[t]){
      cout<<"yes"<<endl;
    }else{
      cout<<"no"<<endl;
    }
  }
  return(0);
}



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

using namespace std;

#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORD(i, m, n) for (int i = m; i >= n; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REP1(i, n) for (int i = 0; i <= n; ++i)
#define REPR(i, n) for (int i = n; i >= 0; --i)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using ll = long long;
using ull = unsigned long long;
using ld = long double;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n,x,t;
	cin>>n>>x>>t;
	int x2=x;
	int t2=t;
	while (1)
	{
		if(n<=x2){
			cout<<t2<<endl;
			return 0;
		}
		t2+=t;
		x2+=x;
	}
	

	return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
const int   N=1e4+10;
long long w[N],v[N];
int main()
{
	long long n,m;
	cin>>n>>m;
	for(int  i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
long long f[n+1][m+1];
memset(f,0,sizeof f);
	for(int  i=1;i<=n;i++)
	{
		for(int  j=0;j<=m;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>=w[i])
			{
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
			}
		}
	}
	cout<<f[n][m]<<endl;
   return 0;
}

Measured memory_bytes: 82380
N,M,Q=map(int, input().split())
ABCD=[tuple(map(int, input().split())) for _ in range(Q)]

ans=0
A=[1]*(N+1)
while True:
    tmp=0
    for a,b,c,d in ABCD:
        if A[b]-A[a]==c: tmp+=d
    ans = max(ans, tmp)
    up=1
    for i in range(N,0,-1):
        A[i]+=up
        if A[i]>M:
            up=1
            A[i]=M
        else:
            up=0
            for j in range(i+1,N+1):
                A[j]=A[i]
            break
    if up==1: break
print(ans)

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  int N; cin >> N;
  ll a; cin >> a;
  rep(i, N - 1) {
    ll b; cin >> b;
    a = __gcd(a, b);
  }
  cout << a << endl;
}


Measured memory_bytes: 256
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)
 
 
N,K=map(int,input().split())

x = Base_10_to_n(N, K)

print(len(str(x)))

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

using namespace std;

typedef long long LL;

int main(){
    LL Q, H, S, D, N;
    cin >> Q >> H >> S >> D >> N;
    LL one = min(Q*4, min(H*2, S));
    LL d = N / 2;
    LL r = N % 2;
    LL ans = d * min(one*2, D) + r * one;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a-1; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct UnionFind{

    vector<ll> par;
    UnionFind(ll n) : par(n, -1){}
    

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

    bool same(int a, int b){
        return root(a)==root(b);
    }
    void unite(int a, int b){
        int x=root(a), y=root(b);
        if(same(x, y)) return;
        if(y<x) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
    int size(int x){
        return -par[root(x)];
    }

};

int main(){
    ll n, q;    cin >> n >> q;
    vector<ll> v(n);
    rep(i, n) cin >> v[i];
    UnionFind tree = UnionFind(n);
    rep(i, q){
        ll a, b;    cin >> a >> b;
        a--, b--;
        tree.unite(a, b);
    }
    ll res=0;
    rep(i, n){
        if(v[i]-1!=i){
            if(tree.same(i, v[i]-1)) res += 1;
        }else res += 1;
    }
    cout << res << endl;
}


Measured memory_bytes: 4828
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: usize,
    }

    match n % 10 {
        3 => {
            println!("bon");
        },
        0|1|6|8 => {
            println!("pon");
        }
        _ => {
            println!("hon");
        }
    }
}


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


int main(){
	long long N,i,j,a,b;
	cin >> N;
	for(i=1;i<=3500;i++){
		for(j=1;j<=3500;j++){
			a=4*i*j-N*(i+j);
			b=i*j*N;
			
			if(a>0&&b%a==0){
				cout << i << " " << j << " " << b/a << endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ctime>
#include <sstream>
#define weewoo ios::sync_with_stdio(false);cin.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define ll long long
#define se second
#define fi first
#define ctoi(x) (x-'0')
#define pi (acos(-1))
#define llputin(a,n) for(int i=0;i<n;i++){ll x;cin >> x;a.push_back(x);}
#define iputin(a,n) for(int i=0;i<n;i++){int x;cin >> x;a.push_back(x);}

#define MOD ((ll) 1e9 + (ll) 7)
using namespace std;

ll pw(ll x,ll a){
    if(a==0)
        return 1;
    ll t = pw(x,a/2);
    if(a%2==0)
        return(t*t);
    else
        return(t*t*x);
}

bool prime(int x)
{
    if(x < 2) return false;
        for(int i=2; i<= sqrt(x); i++) {
            if ((x%i) == 0) return false;
    }
    return true;
}

bool cmp(const pair<int , int> &a , const pair<int , int> &b){
    return (a.first < b.first);
}

ll lcm(ll a,ll b){
    return ( a*b/__gcd(a,b));
}

vector<int>a;
ll ans;
int n;
void solve(int i,int cur){
    if(i==n){
        ans+=cur;
        return;
    }
    solve(i+1,cur|a[i]);
    solve(i+1,cur);
}

int main()
{
    weewoo;
    ll a,b;
    cin >> a >> b;
    ll ans = a*(a-1)/2;
    ans+=(b*(b-1)/2);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <iostream>
#include <string>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstdint>

using namespace std;

#define ll long long unsigned int
#define ti4 tuple<int,int,int,int>
#define pii pair<ll,ll>

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll dp[50][2500];
ll dp2[50][2500];

int main()
{
    ll a, b, c;
    cin >> a >> b >> c;
    
    ll diff = 9000000000000000000L;
    {
        ll v1 = b/2;
        ll v2 = b-v1;
        if(v1 == v2)
        {
            cout << 0 << endl;
            return 0;
        }
        diff = min(a * c, diff);
    }
    {
        ll v1 = c/2;
        ll v2 = c-v1;
        if(v1 == v2)
        {
            cout << 0 << endl;
            return 0;
        }
        diff = min(a * b, diff);
    }
    {
        ll v1 = a/2;
        ll v2 = a-v1;
        if(v1 == v2)
        {
            cout << 0 << endl;
            return 0;
        }
        diff = min(b * c, diff);
    }
    cout << diff << endl;
    return 0;
}

Measured memory_bytes: 256
n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
    
dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = min([dp[i - c[j]]+1 for j in range(m) if i-c[j]>=0])

print(dp[n])



Measured memory_bytes: 7264
import math
S=int(input())
count = 1
if S>=3:
    i=1
    while S>=3*(i+1):
        count += math.factorial(S-3*(i+1)+i)//(math.factorial(S-3*(i+1))*math.factorial(i))
        i+=1
    print(count%1000000007)
else:
    print(0)

Measured memory_bytes: 9184
import java.util.*;
import java.math.BigDecimal;
import java.math.MathContext;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
	int a = sc.nextInt();
	int b = sc.nextInt();
        int d = a / b;
	int r = a % b;
	double f = (double)a/(double)b;



	System.out.print(d + " " + r + " ");
	System.out.printf("%8f\n",f);
  }
	


}

Measured memory_bytes: 26420
#include <bits/stdc++.h>
#define MAXN 45
#define ull unsigned long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
char s[MAXN];
unordered_map<ull,int>S;
int main(){
	int n=read();
	scanf("%s",s+1);
	for (int i=0;i<(1<<n);++i){
		ull h1=0,h2=0;
		for (int j=1;j<=n;++j){
			if (i&(1<<(j-1))) h1=h1*26ull+(ull)s[j]-'a'+1;
			else h2=h2*26ull+(ull)s[j]-'a'+1;
		}
		++S[h1+(h2<<32)];
	}
	long long ans=0;
	for (int i=0;i<(1<<n);++i){
		ull h1=0,h2=0;
		for (int j=n;j>=1;--j){
			if (i&(1<<(j-1))) h1=h1*26ull+(ull)s[j+n]-'a'+1;
			else h2=h2*26ull+(ull)s[j+n]-'a'+1;
		}
		ans+=S[h1+(h2<<32)];
	}
	printf("%lld\n",ans);
}

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

int main(){
  int n;
  cin >> n;
  int arr[n];
  for(int i=0; i<n ; i++)
    cin >> arr[i];
  for(int j=n-1;j>=0;j--){
    if( j!=0)
      cout <<arr[j]<<' ';
    else
      cout <<arr[j];
  }
  cout << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  vecint v(3);
  REP(i,3) cin>>v[i];
  int cnt = 0;
  while (true) {
    sort(ALL(v));
    if (v[0] == v[2]) {
      cout << cnt << endl;
      return 0;
    }
    if (v[0] == v[1]) {
      ++v[0];
      ++v[1];
      ++cnt;
    } else {
      v[0] += 2;
      ++cnt;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int>P;
typedef pair<ll,ll>pl;

const int MAX_N = 40;

ll N,W;
ll v[MAX_N];
ll w[MAX_N];
vector<pl> x,y;

void func(int si,int ti,vector<pl> &x){
  int size=ti-si;
  rep(i,1<<size){
    pl p=pl(0,0);
    rep(j,size){
      if(i&(1<<j)){
        p.first+=w[si+j];
        p.second+=v[si+j];
      }
    }
    x.push_back(p);
  }
}
  
int main(){
  cin>>N>>W;
  rep(i,N){
  	cin>>v[i]>>w[i];
  }
 
  func(0,N/2,x);
  sort(x.begin(),x.end());
  func(N/2,N,y);
  sort(y.begin(),y.end());
    
  ll target=0,maxm=-(1LL<<60),ans=0;
    
  for(int i=x.size()-1;i>=0;i--){
    while(target<y.size() && x[i].first+y[target].first <=W ){
      maxm=max(maxm,y[target].second);
      target++;
    }
    ans=max(ans,maxm+x[i].second);
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 43672
// g++ -std=gnu++1y -O2 main.cpp

#include <cstdio>
#include <vector>
#include <set>

#include <map>
#include <unordered_map>
#include <string>
#include <utility>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <climits>

using namespace std;

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

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

	if (S[2] == S[3] && S[4] == S[5]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
S = input()
ans='None'
if 1<=int(S[:2]) <=12 and 1<=int(S[2:])<=12:
    ans='AMBIGUOUS'
elif 1<=int(S[:2])<=12:
    ans='MMYY'
elif 1<=int(S[2:])<=12:
    ans='YYMM'
else:
    ans='NA'
print(ans)

Measured memory_bytes: 8976
/*
* Author : Omkar Deshmukh
*/
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define all(v) v.begin(), v.end()
#define intvect vector<int>
#define llvect vector<ll>
#define all(v) v.begin(), v.end()
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
vector<pair<string, int>> qry;
intvect freq;
int k;

int32_t main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int ans = 0;
    if (a >= k)
    {
        ans += k;
        k -= k;
    }
    else
    {
        ans += a;
        k -= a;
    }
    if (k)
    {
        if (b >= k)
        {
            ans += (0);
            k -= k;
        }
        else
        {
            k -= b;
        }
    }
    ans -= k;
    cout << ans;

    return 0;
}

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

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

using namespace std;

int main() {
    string s;
    cin >> s;
    string goal = "";
    if(s[0] == '0'){
        goal += '0';
    }else{
        goal += '1';
    }
    for(int i = 1; i < s.length(); i++){
        if(goal[i - 1] == '0'){
            goal += '1';
        }else{
            goal += '0';
        }
    }
    int cnt = 0;
    rep(i, s.length()){
        if(s[i] != goal[i]){
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 640