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

typedef long long ll;
const int amax = 1e5+1;

int main(){
  ll n, k; cin >> n >> k;

  ll aBucket[amax];
  memset(aBucket, 0, sizeof(aBucket));
  ll a, b;
  for(int i=0; i<n; i++){
    cin >> a >> b;
    aBucket[a] += b;
  }

  ll sum=0;
  int ans;
  for(int i=0; i<amax && sum <= k; i++){
    if(sum<k && aBucket[i]) {
      ans = i;
      sum += aBucket[i];
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  ll ans = 0;
  rep(i, n){
    ans += (ll)(i+1) * (n-i);
  }
  rep(i, n-1){
    int v, u;
    cin >> v >> u;
    if(v > u) swap(v, u);
    ans -= (ll)v * (n-u+1);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3548
import java.util.Scanner;
public class Main{
	
	public void solve(){
		Scanner sc=new Scanner(System.in);
		int x=sc.nextInt();
		System.out.println(x*x*x);
		
	}
	public static void main(String[] args){
		Main obj=new Main();
		obj.solve();
	}
}

Measured memory_bytes: 17156
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.next());
        int y = Integer.parseInt(sc.next());
        int z = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        int result = (x - z) / (y + z);

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main() {
 long int H,A,count,o=0;
  cin>>H>>A;
	vector<long int>HP(H);
  for(int i=0;i<H;i++){
    cin>>HP.at(i);
  }
  sort(HP.begin(), HP.end());
    for(int i=0;i<H-A;i++){
    o+=HP.at(i);
  }
  cout<<o;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define ios ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0)
#define so sizeof
#define pb push_back
#define cl clear() ;
#define vl vector<ll>
#define sz size()
#define len length()
#define el endl;cout.flush()
#define be begin()
#define fi first
#define se second
#define br break
#define en end()
#define ro return 0
#define br break
#define eb emplace_back
#define con continue
#define ms(x) memset(x , 0, so x)
#define all(x) (x).be , (x).en
#define acc(x) accumulate((x).be , (x).en , 0ll)
#define forn(i,a,b) for(ll i=a;i<=b;++i)
#define rng_58 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define plll pair<ll,pair<ll,ll>>
#define plvl pair<pair<ll,ll> ,ll>
#define mp make_pair
#define trace3(a,b,c) cerr <<"a is " << a << " b is " << b << " c is " << c << el;
#define trace4(a,b,c,d) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << el ;
#define trace5(a,b,c,d,e) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << el;
#define trace6(a,b,c,d,e,f) cerr <<"a is " << a << " b is " << b << " c is " << c <<" d is " << d << " e is " << e << " f is " << f << el ;

int main()
{
    ios;
    ll p , q ,r ;
    cin >> p >> q >> r;
    vl v ;
    v.pb(p) ;
    v.pb(q) ;
    v.pb(r) ;
    sort(all(v));
    cout << v[0] + v[1] << el ;

}































Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int):
    tot = 1
    for i in range(1, N+1):
        tot *= i
        tot %= MOD
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int n, m;
	cin >> n >> m;
	cout << n*(n-1)/2+m*(m-1)/2;
}

Measured memory_bytes: 256
import java.util.*;

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

    int n = sc.nextInt();
    int ans = 0;

    for(int i = 1; i <= n; i += 2){
      int buf = 0;
      for(int j = 1; j <= n; j++){
        if(i % j == 0){
          buf += 1;
        }
      }
      if(buf == 8){
        ans += 1;
      }
    }

    System.out.println(ans);
  }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main{

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

		int k = Integer.parseInt(scanner.next());
		int s = Integer.parseInt(scanner.next());

		int res = 0;

		for(int x = 0; x <=k; x++){
			for(int y = 0; y<= k; y++){
				int z = s - (x + y);
				if(0 <= z && z <= k)
					res++;
			}
		}

		System.out.println(res);
	}
}


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

int main()
{
  int64_t N, i, tmp, answer;
  cin >> N;
  answer=N-1;
  for(i=1;i<N;i++)
  {
    if(N%i==0)
    {
      tmp=i+N/i-2;
      answer=min(tmp,N-1);
    }
    if(i>N/i)
      break;
  }    
  cout << answer << endl;
}

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

int main()
{
  int k;
  cin>>k;
  string s;
  cin>>s;
  int n=s.length();

  if(n<=k)
    cout<<s;
  else
  {
    string a=s.substr(0,k);
    a=a+"...";
    cout<<a;
  }
  return 0;
}


Measured memory_bytes: 3640
// https://atcoder.jp/contests/abc120/tasks/abc120_d

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <regex>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

#define EPS (1e-7)
#define INF (1e9)
#define MOD (1000000007)
#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 >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

// long gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// long lcm(long a, long b) { return a * b / gcd(a, b); }
struct UnionFind {
    vector<int> par; // 親の番号
    UnionFind(int size) : par(size, -1) {}
    // xとyの木を併合
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (par[y] < par[x])
                swap(x, y);
            par[x] += par[y];
            par[y] = x;
            return true;
        } else {
            return false;
        }
    }
    // 2つのデータx, yが属する木が同じならtrueを返す
    bool same(int x, int y) { return root(x) == root(y); }
    // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
    // 頂点 v が属するグループと同じグループに属する頂点数を得る
    int size(int x) { return -par[root(x)]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m, t1, t2;
    cin >> n >> m;
    vector<ll> ans, a, b;

    for (int i = 0; i < m; i++) {
        cin >> t1 >> t2;
        a.push_back(--t1);
        b.push_back(--t2);
    }
    reverse(ALL(a));
    reverse(ALL(b));
    UnionFind tree(n);

    ll cur = n * (n - 1) / 2;
    for (int i = 0; i < m; i++) {
        ans.push_back(cur);
        t1 = tree.size(a[i]);
        t2 = tree.size(b[i]);
        if (tree.unite(a[i], b[i])) {
            cur -= t1 * t2;
        }
    }
    reverse(ALL(ans));
    for (auto x : ans) {
        cout << x << '\n';
    }

    return 0;
}


Measured memory_bytes: 6688
N, M = map(int,input().split())
LRs = [list(map(int,input().split())) for _ in range(M)]

current_L = 1
current_R = N
for L,R in LRs:
    if current_L < L:
        current_L = L
    if current_R > R:
        current_R = R


if current_R < current_L:
    print(0)
else:
	print(current_R-current_L+1)
        


Measured memory_bytes: 27332
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='9')s[i]='1';
        else s[i]='9';
    }
    cout<<s;
system("pause");
return 0;
}

Measured memory_bytes: 504
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  std::vector<ll> v(3);
  rep(i,3) cin>>v[i];
  sort(all(v));
  reverse(all(v));
  cout<<v[0]*10+v[1]+v[2]<<endl;

}

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


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#define INF 2000000000
using namespace std;

int main(){
	int n,k,a[100001];
	while(1){
		a[0] = 0;
		cin >> n >> k;
		if(n == 0 && k == 0) break;
		for(int i = 0;i < n;i++) {
			int t;
			cin >> t;
			a[i + 1] = a[i] + t;
		}
		int ma = -INF;
		for(int i = 0;i <= n - k;i++){
			ma = max(ma,a[i + k] - a[i]);
		}
		cout << ma << endl;
	}
	return 0;	
}

Measured memory_bytes: 3484
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

n = n_in()
A = l_in()

print(sum(A[i]%2 ==1 for i in range(0,n,2)))


Measured memory_bytes: 61720
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
int main()
{
     Fast();
     ll n,t,x,y,i,j,k,mini=LONG_LONG_MAX,maxi=LONG_LONG_MIN,flag =0 ,sum=0,mul=1;
     vector<ll>vi;
     string s,s1="";
    cin>>n;
    map<ll,ll>mp;
    mp[n]=1;
    for(i = 1 ; ;i++)
    {
        //cout<<n<<endl;
        if(n%2==0)
        {
            n/=2;
            if(mp[n]==0)
                mp[n]=1;
            else
                break;
        }
        else
        {
            n=n*3 +1;
            if(mp[n]==0)
                mp[n]=1;
            else break;
        }
    }
    cout<<i+1<<endl;

}


Measured memory_bytes: 256
import itertools
N, M, Q = map(int, input().split())
abcd_lis = []
for i in range(Q):
	abcd_lis.append(list(map(int, input().split())))
lis = [i+1 for i in range(M)]

lis = list(itertools.combinations_with_replacement(lis, N))
maxi = 0
for i in lis:
  count = 0
  for j in range(Q):
    idx1 = abcd_lis[j][0]-1
    idx2 = abcd_lis[j][1]-1
    if i[idx2]-i[idx1] == abcd_lis[j][2]:
      count += abcd_lis[j][3]
  if maxi < count:
    maxi = count
print(maxi)

Measured memory_bytes: 21484
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cstring>

void input_vector(int &x);
void show(int x);

//#define DEBUG
using namespace std;

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

    vector<string> S(N);

    for(int i = 0; i < N; i++){
        cin >> S.at(i);
    }

    sort(S.begin(), S.end());
    string ans = "";
    for(int i = 0; i < N; i++){    
        ans += S.at(i);
        //cout << S.at(i) << endl;
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
let () =
  let n = read_int () in
  let rec loop = function
      0 -> ()
    | i ->(
      let (xa, ya, ra, xb, yb, rb)
        = Scanf.scanf "%f %f %f %f %f %f\n" (fun xa ya ra xb yb rb->(xa, ya, ra, xb, yb, rb)) in
      let d = sqrt((xa-.xb)**2. +. (ya-.yb)**2.) in
      if d +. rb < ra then print_endline "2"
      else if d +. ra < rb then print_endline "-2"
      else if d > ra +. rb then print_endline "0"
      else print_endline "1"
    );loop (i-1)
  in loop n

Measured memory_bytes: 2324
#include<stdio.h>
#include<iostream>
using namespace std;

#define ll long long

int main(){
  ll N;
  cin >> N;
  string S;
  cin >> S;
  ll ans = 0;
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 10; j++){
      for(int k = 0; k < 10; k++){
        bool ok = false;
        ll current = 1;
        for(int l = 0; l < N; l++){ 
          if((i==S[l]-'0') && (current == 1)){
            current++;
          }else if((j==S[l]-'0') && (current == 2)){
            current++;
          }else if((k==S[l]-'0') && (current == 3)){
            ok = true;
            break;
          }else{
          }
        }
        if(ok) {
          ans++;
          //cout << i << j << k << endl;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

void doSum( int a, int b, int n, int s, int sum, int* count ){
	for ( int i = a; i < b; ++i ){
		int tsum = sum + i;
		if ( !n ){
			if ( tsum == s ) *count += 1;
		}else{
			doSum( i+1, b+1, n-1, s, tsum, count );
		}
	}
}

int main(){
	int n, s, count;

	while ( cin >> n >> s ){
		if ( !n && !s ) break;

		count = 0;
		doSum( 0, 10-n+1, n-1, s, 0, &count );

		cout << count << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int main(){
  int n,s,i;
  while(1){
    s=1;
    scanf("%d",&n);
    if(n==0)break;
    if(n==1)s--;
    for(i=2;i*i<=n;i++){
      if(n%i==0){
	s+=i;
	if(i*i!=n)s+=n/i;
      }
    }

    if(n==s)printf("perfect number\n");
    else if(n>s) printf("deficient number\n");
    else printf("abundant number\n");

  }
  return 0;
}

Measured memory_bytes: 1012
s = input()
n = len(s)

if s == s[::-1]:
  #前半部分の回文チェック
  p = int((n-1)/2)
  f = s[:p]
  if f == f[::-1]:
    #後半部分の回文チェック
    q = int((n+3)/2)
    l = s[q-1:]
    if l == l[::-1]:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")

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

using namespace std;

int pzl[9][9];

bool check(int y, int x)
{
  for(int i = 0; i < 9; i++){
    if(x == i) continue;
    if(pzl[y][x] == pzl[y][i]) return false;
  }
  for(int i = 0; i < 9; i++){
    if(y == i) continue;
    if(pzl[y][x] == pzl[i][x]) return false;
  }
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      if(y == y/3*3+i && x == x/3*3+j) continue;
      if(pzl[y][x] == pzl[y/3*3+i][x/3*3+j]) return false;
    }
  }
  return true;
}

int main()
{
  int n;
  cin >> n;
  for(int l = 0; l < n; l++){
    if(l > 0) cout << endl;
    for(int i = 0; i < 9; i++){
      for(int j = 0; j < 9; j++){
	cin >> pzl[i][j];
      }
    }
    for(int i = 0; i < 9; i++){
      for(int j = 0; j < 9; j++){
	if(check(i, j)) cout << ' '; 
	else cout << '*';
	cout << pzl[i][j];
      }
      cout << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1160
import numpy as np 

n = int(input())
h = list(map(int, input().split()))

ans = np.zeros(n)
ans[1] = abs(h[1] - h[0])

for i in range(2, n):
    from_minus_1 = ans[i-1] + abs(h[i] - h[i-1])
    from_minus_2 = ans[i-2] + abs(h[i] - h[i-2])
    
    if from_minus_1 < from_minus_2:
        ans[i] = from_minus_1
    else:
        ans[i] = from_minus_2

print(int(ans[-1]))

Measured memory_bytes: 22780
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split(' ');
        int A = int.Parse(s[0]);
        int B = int.Parse(s[1]);
        string S = Console.ReadLine();

        for(int i = 0; i < S.Length; i++)
        {
            if (i != A ? 
                (S[i] - '0' < 0 || S[i] - '0' > 9) : 
                S[i] != '-')
            {
                Console.WriteLine("No");
                return;
            }
        }
        Console.WriteLine("Yes");
    }
}


Measured memory_bytes: 13140
#include "bits/stdc++.h"
using namespace std;

void dfs(vector<vector<int>>& con, int num, vector<bool>& seen, vector<int>& ope)
{
	seen.at(num) = true;
	for (int con_ele : con.at(num)) {
		if (seen.at(con_ele) == false) {
			ope.at(con_ele) += ope.at(num);
			dfs(con, con_ele, seen, ope);
		}
	}
};

int main()
{
	int n, q;
	cin >> n >> q;
	vector<vector<int>> points(n);
	for (int i = 0; i < n - 1; i++) {
		int a_in, b_in;
		cin >> a_in >> b_in;
		points.at(a_in - 1).push_back(b_in - 1);
		points.at(b_in - 1).push_back(a_in - 1);
	}
	vector<int> ope(n, 0);
	for (int i = 0; i < q; i++) {
		int p_in, x_in;
		cin >> p_in >> x_in;
		ope.at(p_in - 1) += x_in;
	}

	vector<bool> seen(n, false);
	dfs(points, 0, seen, ope);

	for (int ope_ele : ope) {
		cout << ope_ele << " ";
	}
	cout << endl;
}


Measured memory_bytes: 29824
#!/usr/bin/env python3
import sys
from itertools import chain

# import numpy as np
# from itertools import combinations as comb
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter


def solve(
    N: int, M: int, Q: int, ABCD: "List[(int,int,int,int)]",
):
    def dfs(A, l, r, n):
        if n > 0:
            max_score = 0
            for Ai in range(l, r + 1):
                A.append(Ai)
                score = dfs(A, Ai, r, n - 1)
                if score > max_score:
                    max_score = score
                A.pop()
            return max_score
        else:
            score = 0
            for a, b, c, d in ABCD:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            return score

    return dfs([], 1, M, N)


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    ABCD = []
    for i in range(Q):
        a = int(next(tokens))
        b = int(next(tokens))
        c = int(next(tokens))
        d = int(next(tokens))
        ABCD.append((a, b, c, d))
    answer = solve(N, M, Q, ABCD)
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9292
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N;
    int max=0;
    cin >> N;
    vector<int> A(N),B(N),sa(N+1,0),sb(N+1,0);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        sa.at(i+1) = sa.at(i) + A.at(i);
    } 
    for (int i = 0; i < N; i++) {
        cin >> B.at(i);
        sb.at(i+1) = sb.at(i) + B.at(i);
    }
    for (int i = 0; i < N; i++) {
        int b = sb.at(N) - sb.at(i);
        if(sa.at(i+1) + b > max) max = sa.at(i+1) + b;
    }

    cout << max << endl;
}

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

def popcnt1(n):
    return bin(n).count("1")

k = [0,1,1,2,1,2,1,2,1,2,1,2,1,2,2,3,1,2,1] #18まで

c = 0
for i in range(N):
    if X[i] == "1":
        c += 1

m1 = 0
p1 = 0

for i in range(N):
    if c != 1:
        if X[i] == "1":
            m1 += pow(2,N-1-i,c-1)
            m1 %= c-1
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1
    else:
        if X[i] == "1":
            p1 += pow(2,N-1-i,c+1)
            p1 %= c+1

for i in range(N):
    if c != 1: 
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            B2 = m1 - pow(2,N-1-i,c-1)
            B2 %= c-1
    else:
        if X[i] == "0":
            B2 = p1 + pow(2,N-1-i,c+1)
            B2 %= c+1
        else:
            print(0)
            continue

    S = len(bin(B2))
    c2 = popcnt1(B2)

    if c2 == 0:
        print(1)
    else:
        print(2+k[B2%c2])

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

int a, b, c, d;

int main() {
    scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", std::max(0, std::min(b, d) - std::max(a, c)));
    return 0;
}



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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    t = 1;
    while(t--){
        int n;
        cin >> n;
        vector<long long int> h(n);
        for(int i=0 ; i<n ; i++)
            cin >> h[i];
        vector<long long int> dp(n);
        dp[0] = 0;
        dp[1] = h[0] - h[1];
        if(dp[1]<0) dp[1] *= -1;

        for(int i=2 ; i<n ; i++){
            long long int temp1 = h[i] - h[i-1];
            if(temp1 < 0) temp1 *= -1;
            long long int temp2 = h[i] - h[i-2];
            if(temp2 < 0) temp2 *= -1;

            dp[i] = min(dp[i-1] + temp1, dp[i-2] + temp2);

        }
        cout << dp[n-1] << "\n";
    }
    return 0;
}



Measured memory_bytes: 4764
#include <bits/stdc++.h>
using namespace std;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
using Int = long long;
const Int MOD = 1000000007;
vector<vector<int>> G;
Int cnt[5050], dp[5050][2][5050], tmp0[5050], tmp1[5050], pat[5050];
void recur(int node, int prev) {
    cnt[node] = 1;
    dp[node][0][1] = 1;
    for (int next : G[node]) if (next != prev) {
        recur(next, node);
        int sz = cnt[node] + cnt[next] + 1;
        fill_n(tmp0, sz, 0);
        fill_n(tmp1, sz, 0);
        for (int i = 0; i <= cnt[node]; i++) {
            for (int j = 0; j <= cnt[next]; j++) {
                tmp0[i + j] += dp[node][0][i] * dp[next][0][j] + dp[node][1][i] * dp[next][1][j];
                tmp1[i + j] += dp[node][0][i] * dp[next][1][j] + dp[node][1][i] * dp[next][0][j];
                tmp0[i] += dp[node][0][i] * dp[next][1][j] % MOD * pat[j];
                tmp0[i] += dp[node][1][i] * dp[next][0][j] % MOD * pat[j];
                tmp1[i] += dp[node][0][i] * dp[next][0][j] % MOD * pat[j];
                tmp1[i] += dp[node][1][i] * dp[next][1][j] % MOD * pat[j];
                tmp0[i] %= MOD, tmp1[i] %= MOD, tmp0[i + j] %= MOD, tmp1[i + j] %= MOD;
            }
        }
        copy_n(tmp0, sz, begin(dp[node][0]));
        copy_n(tmp1, sz, begin(dp[node][1]));
        cnt[node] += cnt[next];
    }
}
int main() {
    int N; cin >> N;
    G.resize(N);
    pat[2] = 1;
    for (int i = 4; i <= N; i += 2) {
        pat[i] = (pat[i - 2] * (i - 1)) % MOD;
    }
    for (int i = 0; i < N - 1; i++) {
        int x, y; cin >> x >> y; x--, y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    recur(0, 0);
    Int ans = 0;
    for (int n = 0; n <= N; n++) {
        ans += dp[0][0][n] * pat[n];
        ans -= dp[0][1][n] * pat[n];
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 181284
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;

void solve(int h, int w, vector<string> s) {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == '.') {
                int n = 0;
                for (int a = 0; a < 3; a++) {
                    for (int b = 0; b < 3; b++) {
                        if (a+i-1 < 0 || a+i-1 >= h || b+j-1 < 0 || b+j-1 >= w) {
                            continue;
                        }
                        if (s[a+i-1][b+j-1] == '#') {
                            n++;
                        }
                    }
                }
                s[i][j] = '0' + n;
            }
        }
    }
    for (int i = 0; i < h; i++) {
        std::cout << s[i] << std::endl;
    }
}

int main() {
    struct timeval start,end;
    long long span;
    int h, w;

    gettimeofday(&start,NULL);

    std::cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) {
        std::cin >> s[i];
    }
    solve(h, w, s);

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 256
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>

using namespace std;
typedef long long LL;
typedef pair<LL, LL> LLLL;

vector<LL> v;
vector<LL> w;

const int MAX_W = 100000;
const int THRESHOLD = 1 << 9;

vector<LLLL> calc(int node) {
	int init_node = node;
	vector<LLLL> dp;
	dp.emplace_back(LLLL(0, 0));
	for (LL i = 0; i < 9; ++i) {
		vector<LLLL> next = dp;
		for (auto kv : dp) {
			if (kv.first + w[node] > MAX_W) continue;
			next.emplace_back(LLLL(kv.first + w[node], kv.second + v[node]));
		}
		dp = next;
		node /= 2;
		if (node <= 0 || (init_node >= THRESHOLD && node < THRESHOLD)) {
			break;
		}
	}
	return dp;
}

int main(int argc, char* argv[]) {
	LL n, q, x, y;
	cin >> n;
	v.resize(n + 1);
	w.resize(n + 1);
	for (LL i = 1; i <= n; ++i) {
		cin >> v[i] >> w[i];
	}
	vector<vector<LL>> lower(THRESHOLD);
	if (n >= THRESHOLD) {
		vector<vector<LLLL>> dp(THRESHOLD);
		dp[0].emplace_back(LLLL(0, 0));
		for (int i = 1; i < THRESHOLD; ++i) {
			vector<LLLL> next = dp[i / 2];
			for (auto kv : dp[i / 2]) {
				if (kv.first + w[i] > MAX_W) continue;
				next.emplace_back(LLLL(kv.first + w[i], kv.second + v[i]));
			}
			dp[i] = next;
			if (i >= THRESHOLD / 2) {
				next.emplace_back(LLLL(MAX_W + 1, 0));
				sort(next.begin(), next.end());
				LL mxv = 0, prev = 0;
				lower[i].resize(MAX_W + 1);
				for (auto kv : next) {
					for (LL j = prev; j < kv.first; ++j) {
						lower[i][j] = mxv;
					}
					prev = kv.first;
					mxv = max(mxv, kv.second);
				}
			}
		}
	}
	cin >> q;
	for (LL tt = 0; tt < q; ++tt) {
		cin >> x >> y;
		LL ans = 0;
		vector<LLLL> r = calc(x);
		if (x < THRESHOLD) {
			for (auto kv : r) {
				if (kv.first <= y) {
					ans = max(ans, kv.second);
				}
			}
		} else {
			while (x >= THRESHOLD) {
				x /= 2;
			}
			for (auto kv : r) {
				if (kv.first <= y) {
					ans = max(ans, kv.second + lower[x][y - kv.first]);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


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

int main() {
  int n;cin>>n;
  vector<int> p(n),q(n);
  rep(i,n)cin>>p[i];
  rep(i,n)cin>>q[i];
  vector<int> a(n);
  rep(i,n)a[i]=i+1;
  map<vector<int>,int> mp;//配列に番号を付ける
  do{
    mp[a]=mp.size();
  }while(next_permutation(all(a)));
  int ans=abs(mp[p]-mp[q]);
  cout<<ans<<endl;
}

Measured memory_bytes: 8672
#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define all(c) c.begin(),c.end()
#define pb push_back
using namespace std;
typedef pair<int,string> P;
int main(){
	int n;
	while(cin>>n,n){
		vector<P> ans(n);
		vector<vector<int> > v(n);
		map<int,int> mp;
		int m,x;
		for(int i=0;i<n;i++){
			string s;
			cin>>s>>m;
			ans[i]=P(0,s);
			for(int j=0;j<m;j++){
				cin>>x;
				v[i].pb(x);
				mp[x]++;
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<v[i].size();j++){
				ans[i].first=ans[i].first+n-mp[v[i][j]]+1;
			}
		}
		sort(all(ans));
		cout<<ans[0].first<<" "<<ans[0].second<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
//0276
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,d,e,f,g,h;
        cin>> a>>e>>b>>f>>c>>g>>d>>h;
    if(a==1)
        cout << e*6000 << endl;
    if(a==2)
        cout << e*4000 << endl;
    if(a==3)
        cout << e*3000 << endl;
    if(a==4)
        cout << e*2000 << endl;
    
    if(b==1)
        cout << f*6000 << endl;
    if(b==2)
        cout << f*4000 << endl;
    if(b==3)
        cout << f*3000 << endl;
    if(b==4)
        cout << f*2000 << endl;
    
    if(c==1)
        cout << g*6000 << endl;
    if(c==2)
        cout << g*4000 << endl;
    if(c==3)
        cout << g*3000 << endl;
    if(c==4)
        cout << g*2000 << endl;
    
    if(d==1)
        cout << h*6000 << endl;
    if(d==2)
        cout << h*4000 << endl;
    if(d==3)
        cout << h*3000 << endl;
    if(d==4)
        cout << h*2000 << endl;
    
    
}



Measured memory_bytes: 3116
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int t = sc.nextInt();
        if(x - t <= 0) System.out.println(0);
        else System.out.println(x - t);
    }
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, A, B;
    cin >> N >> A >> B;
    if (A > B || (A != B && N == 1)) {
        cout << 0 << endl;
        return 0;
    }

    ll min = A * (N - 1) + B;
    ll max = A + B * (N - 1);
    cout << max - min + 1LL << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using vi = vector<int>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    ll n,m;cin>>n>>m;
    vector<pair<ll,ll>> p(n);
    rep(i,n){
        cin>>p[i].first>>p[i].second;
    }
    sort(p.begin(),p.end());
    ll ans=0;
    ll cnt=0;
    bool ok = false;
    for(ll i=0;i<n;i++){
        if(cnt + p[i].second<m){
            ans += p[i].first * p[i].second;
            cnt += p[i].second;
        }else{
            ans += p[i].first * (m-cnt);
            break;
        }
        //cout << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

void Search(vector<vector<int>>&edge, vector<int>&flag, int node) {
	for (auto i : edge[node]) {
		Search(edge, flag, i);
		if (flag[i] == -1)flag[node] = 1;
	}
	if (flag[node] == 0)flag[node] = -1;
}

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

	cin >> N;
	vector<int>v(N);
	for (auto &i : v)cin >> i;
	vector<vector<int>>edge(N);
	for (int i = 1; i < N; i++) {
		cin >> L >> R;
		L--;
		R--;
		edge[L].push_back(R);
		edge[R].push_back(L);
	}
	vector<int>flag(N, -1);
	vector<vector<int>>eedge(N);
	vector<int>indir(N);
	for (int i = 0; i < N; i++) {
		for (auto j : edge[i]) {
			if (v[i] > v[j]) {
				flag[i] = 0;
				eedge[i].push_back(j);
				//cout << i << " " << j << endl;
				indir[j]++;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		if (indir[i])continue;
		Search(eedge, flag, i);
	}
	vector<int>ret;
	for (int i = 0; i < N; i++) {
		//cout << i << " " << flag[i] << endl;
		if (flag[i] == 1) {
			ret.push_back(i + 1);
		}
	}
	for (int i = 0; i < ret.size(); i++) {
		if (i)cout << " ";
		cout << ret[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long dp[100005][2];
int main()
{
    char s[100005];
    cin>>s+1;
    dp[0][1]=1;
    dp[0][0]=0;
    int n=strlen(s+1);
    for(int i=1;s[i];i++)
    {
        dp[i][0]=(dp[i-1][0]*3)%mod;
        if(s[i]=='1')
        {
            dp[i][1]=(dp[i-1][1]*2)%mod;
            dp[i][0]+=dp[i-1][1];
            dp[i][0]=(dp[i][0])%mod;
        }
        else
        {
            dp[i][1]=dp[i-1][1];
        }
    }
    printf("%lld\n",(dp[n][1]+dp[n][0])%mod);
}

Measured memory_bytes: 1920
import java.util.*;

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

        if(str.equals("A")){
            ans = "T";
        }else if(str.equals("T")){
            ans = "A";
        }else if(str.equals("C")){
            ans = "G";
        }else if(str.equals("G")){
            ans = "C";
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23380
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <sstream>
#include <limits>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define PI (acos(-1.0))
#define Abs(a) (((a)<0) ? (-(a)) :(a) )
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define Rep(i,n) for(int i=0;i<(n);i++)
#define Rrep(i,n) for(int i=((n)-1);i>=0;i--)
#define rrep(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define Pii pair<int,int>
#define PB push_back
#define Size(x) ((int)(x.size()))
using namespace std;
typedef long long mint;
typedef unsigned long long umint;
string a[55], b[55];
int main()
{
    //freopen("in.txt","r",stdin);
    int n,m;
    cin >> n >> m;
    Rep(i,n)
    {
        cin >> a[i];
    }
    Rep(i,m)
    {
        cin>> b[i];
    }
    Rep(p, n - m + 1)
    {
        Rep(q, n - m + 1)
        {
            bool ok = true;
            Rep(r, m)
            {
                Rep(s, m)
                {
                    if(a[p + r][q + s] != b[r][s])
                    {
                        ok = false;
                        break;
                    }
                }
                if(!ok)
                {
                    break;
                }
            }
            if(ok)
            {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}



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

using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	bool vis[4];
	memset(vis,0,sizeof(vis));
	vis[a]=vis[b]=1;
	for(int i=1;i<=3;i++){
		if(!vis[i]){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
inline ll read() {
	ll kk=0,f=1;
	char cc=getchar();
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
	return kk*f;
}
inline void write(ll xx){
	if(xx < 0){putchar('-');xx=-xx;}
	if(xx > 9)write(xx/10);
	putchar(xx%10+'0');
	return;
}
map<pair<ll,int>,ll> mp;
ll a[200005];
int n;
int main(){
	n = read();
	ll res = 0;
	for(int i = 1;i <= n;i++){
		a[i] = read();
		mp[make_pair(a[i] + i,0)]++;
		mp[make_pair(i -a[i],1)]++;
	}
	for(int i = 1;i <= n;i++){
		if(mp[make_pair(a[i] + i,1)]){
			res += (mp[make_pair(i + a[i],0)] * mp[make_pair(i + a[i],1)]);
			mp[make_pair(a[i] + i,1)] = 0;
			mp[make_pair(a[i] + i,0)] = 0;
		}else if(mp[make_pair(i - a[i],0)]){
			res += (mp[make_pair(i - a[i],0)] * mp[make_pair(i - a[i],1)]);
			mp[make_pair(i - a[i],0)] = 0;
			mp[make_pair(i - a[i],1)] = 0;
		}
	}
	write(res);
	return 0;
}

Measured memory_bytes: 50316
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char ch;
    cin>>ch;
    if(ch=='A')cout<<'T'<<endl;
    else if(ch=='T')cout<<'A'<<endl;
    else if(ch=='G')cout<<'C'<<endl;
    else if(ch=='C')cout<<'G'<<endl;

}


Measured memory_bytes: 256
A,B,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=min(a)+min(b)
for i in range(m):
  x,y,c=map(int,input().split())
  ans=min(ans,a[x-1]+b[y-1]-c)
print(ans)

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

using namespace std;

#define min3(a, b, c)           min((a), min((b), (c)))
#define max3(a, b, c)           max((a), max((b), (c)))
#define lcm(a,b)                (a / __gcd(a,b) ) *b
#define gcd(a,b)                __gcd(a,b)
#define dist(x1,y1,x2,y2)       sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
#define distl(x1,y1,x2,y2)      sqrtl((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
#define sqr(a)                  ((a)*(a))
#define FOR(a, b)               for(int i=a; i<b; i++)
#define fRead(x)                freopen(x,"r",stdin)
#define fWrite(x)               freopen (x,"w",stdout)
#define pb                      push_back
#define mk                      make_pair
#define ff                      first
#define ss                      second
#define lb                      lower_bound
#define ub                      upper_bound
#define all(a)                  a.begin(),a.end()
#define FASTIO                  ios_base::sync_with_stdio(0);cin.tie(NULL);

int main()
{
    FASTIO

    int  n, m;
    cin >> n >> m;

    bool AC[100050];
    memset(AC, false, sizeof AC);

    map<int, int> WA;

    FOR (0, m)
    {
        int submission;
        string verdict;

        cin >> submission;
        cin >> verdict;

        if (verdict == "AC")
            AC[submission] = true;
        if (verdict == "WA")
        {
            if (!AC[submission])
                WA[submission]++;
        }
    }

    int ACCOUNT=0, WACOUNT =0;

    for (auto it: WA)
    {
        if (AC[it.first])
        {
            ACCOUNT++;
            WACOUNT += it.second;
            AC[it.first] = false;
        }
    }

    for (int i=0; i<=n; i++)
        if (AC[i])
            ACCOUNT++;
    cout << ACCOUNT << " " << WACOUNT;

}


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

int main(){
  ll n, a, b; cin >> n >> a >> b;
  vector<ll> x(n);
  for(int i = 0; i < n; i++) cin >> x[i];
  ll ans = 0;
  for(int i = 1; i < n; i++){
    ans += min(a*(x[i] - x[i-1]), b);
  }
  cout << ans << endl;
}
  

Measured memory_bytes: 4044
N, M = gets.split.map(&:to_i)

Q, Ikr, FullBit = [], [100001]*(1<<N), (1<<N)-1
master_key = 0
M.times{
	a, c = gets.to_i, gets.split.map(&:to_i)
	tkrbit = c.inject(0){|bit, tkr|
		bit | (1<<(tkr-1))
	}
	next if Ikr[tkrbit] < a
	master_key |= tkrbit
	Ikr[tkrbit] = a
	Q << ((a<<N)|tkrbit)
}
if master_key != FullBit
	p -1
	exit
end

Q.sort!
q, r = [], []
while lowest = Q.shift
	low_cost, low_tkrbit = lowest>>N, lowest&FullBit
	next if Ikr[low_tkrbit] < low_cost
	break if low_tkrbit == FullBit

	while kg = Q.shift
		cost, tkrbit = kg>>N, kg&FullBit
		next if Ikr[tkrbit] < cost
		cost, tkrbit = low_cost+cost, low_tkrbit|tkrbit
		next if tkrbit == low_tkrbit
		q << kg
		next if Ikr[tkrbit] <= cost
		Ikr[tkrbit] = cost
		r << ((cost<<N)|tkrbit)
	end

	until q.empty?
		unless r.empty?
			l, pv = q[0] < r[0] ? [q, r[0]+FullBit] : [r, q[0]+FullBit]
			Q.concat l.shift(l.bsearch_index{|_| pv <= _ }||l.size)
		else
			Q.concat q
			q.clear
		end
	end
	Q.concat r
	r.clear
end
p Ikr[FullBit]


Measured memory_bytes: 3836
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<numeric>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const ll MOD = 1000000007;
 
using namespace std;

int main(){
    int N, K;   cin >> N >> K;
    vector<int> a(N);
    for(int i=0; i<N; i++)  cin >> a[i];

    int l, r;
    for(int i=0; i<min(K,50); i++){
        vector<int> tmp(N,0);
        for(int j=0; j<N; j++){
            l = max(j - a[j], 0);
            r = min(j + a[j] + 1, N);
            tmp[l]++;
            if(r < N)   tmp[r]--;
        }
        for(int j=1; j<N; j++)  tmp[j] += tmp[j-1];
        a = tmp;
    }
    for(int i=0; i<N; i++)  cout << a[i] << " ";
}

Measured memory_bytes: 4848
#pragma GCC optimize("O2")
/*
Arthor : Ender_zzm
E-mail zzm_ender_wiggin@outlook.com
Blog ender-zzm.enbar.cn
*/
#include <bits/stdc++.h>
using namespace std;

inline int Isdigit(char c) {
	if (c < '0' || c > '9') return 0;
	return 1;
}
inline int readint(){
    register int x = 0, flag = 1;
    register char ch;
    while (!Isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), Isdigit(ch = getchar()));
	return x * flag;
}

inline long long readlong() {
	register long long x = 0, flag = 1;
	register char ch;
	while (!Isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), Isdigit(ch = getchar()));
	return x * flag;
}
template <class T>
inline void write(T x){
    if (x < 0)
        putchar('-'), x = -x;
    if(x >= 10) write(x / 10); 
    putchar(x % 10 + '0');
}

template<class T> inline bool Chkmax(T& x, const T& y) { return x < y ? x = y, true : false; }
template<class T> inline bool Chkmin(T& x, const T& y) { return x > y ? x = y, true : false; }

#define For(i, x, y) for (int i = (x); i <= (y); i++) 
#define Rep(i, x, y) for (int i = (x); i >= (y); i--) 
#define ri readint
#define rl readlong

#define int long long


const int maxn = 201010;
int n;
int a[maxn];
double b[maxn];
int Pow(int x, int y) {
	int ans = 1;
	for (int i = 1; i <= y; i++) ans = ans * x;
	return ans;
}
int t[maxn], cnt, cs[maxn];
int two[maxn], five[maxn];
int pp[1001][1001];
const int MaxL = 100;
int Query(int x, int y, int L, int R) {
	return pp[L][R] - pp[x - 1][R] - pp[L][y - 1] + pp[x - 1][y - 1];
}
char asd[maxn];
signed main() {
	n = ri();
	for (int i = 1; i <= n; i++) {
		scanf("%s", asd + 1);
    	int ll = strlen(asd + 1),flag = false,cnt = 10;
    	for(int j = 1;j <= ll; ++j) {
      		if(asd[j] == '.') {flag = true; continue;}
   		   		t[i] *= 10;
	   	   		t[i] += (asd[j] - '0');
   		   	if(flag) cnt--;
   	 	}
	    for(int j = 1;j <= cnt; ++j) t[i] *= 10;
	}
	sort(t + 1, t + 1 + n);
	for (int i = 1; i <= n; i++) {
		int tmp = t[i];
		while (tmp % 2ll == 0) two[i]++, tmp /= 2;
		tmp = t[i];
		while (tmp % 5ll == 0) five[i]++, tmp /= 5;
	}
	int ans = 0, tmp = 0;
	for (int i = 1; i <= n; i++) {
		//printf("%lld %lld %lld\n",t[i], two[i], five[i]);
		pp[two[i] + 1][five[i] + 1]++;
		if (min(2 * two[i], 2 * five[i]) >= 20) tmp++;
		two[i] ++, five[i]++;
	}
	for (int i = 1; i <= MaxL; i++) {
		for (int j = 1; j <= MaxL; j++) {
			pp[i][j] = pp[i - 1][j] + pp[i][j - 1] + pp[i][j] - pp[i - 1][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		int minn = 22 - two[i], minnf = 22 - five[i];
		ans += Query(max(1ll, minn), max(1ll, minnf), MaxL, MaxL);	
	}
	cout << (ans - tmp) / 2;
	return 0;
}


Measured memory_bytes: 8952
#include <iostream>

using namespace std;
/** Problem0136 : Frequency Distribution of Height **/
int main()
{
	int n, list[6]={0};
	double d;
	
	cin >> n;
	for (int i=0; i<n; i++) {
		cin >> d;
		if (d < 165) list[0]++;
		else if (d<170) list[1]++;
		else if (d<175) list[2]++;
		else if (d<180) list[3]++;
		else if (d<185) list[4]++;
		else			list[5]++;
	}
	
	for (int i=0; i<6; i++) {
		cout << i+1 << ":";
		for (int j=0; j<list[i]; j++)
			cout << "*";
		cout << endl;
	}
	return 0;
}

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

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

    int not1index = S.length();
    char not1;
    for (int i = 0; i < S.length(); i++) {
        if (S[i] != '1') {
            not1 = S[i];
            not1index = i;
            break;
        }
    }
    if ((K - 1) < not1index) {
        cout << 1 << endl;
    } else {
        cout << not1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;

public class Test
{
	static public void Main( )
	{
		string[] abc = Console.ReadLine().Split( ' ' );
		
		var a = int.Parse( abc[0] );
		var b = int.Parse( abc[1] );
		var c = int.Parse( abc[2] );
		
		var cnt = 0;
		for( var i=a; i<=b; i++ ) {
			if( 0 == c%i ) cnt++;
		}
		
		Console.WriteLine( cnt );
	}
}

Measured memory_bytes: 5612
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Coprime
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_P = 1000000;

/* typedef */

/* global variables */

bool primes[MAX_P + 1];
int pnums[MAX_P], cs[MAX_P];

/* subroutines */

int gen_primes(int maxp, int pnums[]) {
  memset(primes, true, sizeof(primes));
  primes[0] = primes[1] = false;

  int p, pn = 0;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums[pn++] = p;
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums[pn++] = p;
  return pn;
}

template <typename T>
T gcd(T m, T n) {  // m > 0, n > 0
  if (m < n) swap(m, n);
  while (n > 0) {
    T r = m % n;
    m = n;
    n = r;
  }
  return m;
}

/* main */

int main() {
  int pn = gen_primes(MAX_P, pnums);
  //printf("pn=%d\n", pn);

  int n;
  scanf("%d", &n);

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

    for (int j = 0; pnums[j] * pnums[j] <= ai; j++)
      if (ai % pnums[j] == 0) {
	cs[j]++;
	ai /= pnums[j];
	while (ai % pnums[j] == 0) ai /= pnums[j];
      }

    if (ai > 1) {
      int k = lower_bound(pnums, pnums + pn, ai) - pnums;
      cs[k]++;
    }
  }

  int maxc = 0;
  for (int i = 0; i < pn; i++)
    if (maxc < cs[i]) maxc = cs[i];

  if (maxc == n) puts("not coprime");
  else if (maxc > 1) puts("setwise coprime");
  else puts("pairwise coprime");

  return 0;
}


Measured memory_bytes: 5272
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main()
{
    int a,b,c,x;
    int ans=0;
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(i*500+j*100+k*50==x)
                    ans++;
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256