akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<char,LL> P;
const LL mod=998244353;
const LL LINF=1LL<<62;
const int INF=1<<30;


int main(){
    int n;cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> ca(n+1,0),cb(n+1,0);
    for (int i = 0; i < n; i++) {
        ca[i+1] = __gcd(ca[i],a[i]);
    }
    for (int i = n; i >= 1; i--) {
        cb[i-1] = __gcd(cb[i],a[i-1]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans,__gcd(ca[i],cb[i+1]));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
from sys import stdin
from itertools import chain
head = [[8,1,2,4],[1,2,4,8],[2,4,8,1],[4,8,1,2]]

while(True):
    W,H = map(int, stdin.readline().split())
    m = [[0]*W for _ in range(H)]
    ps = []
    if not (W or H): break
    flag = True
    for h in range(H):
        s = stdin.readline()
        if "X" in s: flag = False
        for w in range(W):
            if s[w] in [".", "X", "E", "N", "W", "S"]:
                m[h][max(0,w-1)] |= 1
                m[min(H-1,h+1)][w] |= 2
                m[h][min(W-1,w+1)] |= 4
                m[max(0,h-1)][w] |= 8
            if s[w] in ["E", "N", "W", "S"]:
                ps.append([h,w,["E", "N", "W", "S"].index(s[w])])
            if s[w] == "X":
                m[h][w] |= 16
    # if flag:
    #     print("NA")
    #     continue
    if W <= 2 or H <= 2:
        print(1)
        continue
    # print(ps)
    # for n in m:
    #     print(n)
    ttt = 0
    while(True):
        ttt += 1
        if ttt > 180: print("NA"); break
        # import time
        # time.sleep(1)
        mt = [[0]*W for _ in range(H)]
        for p in ps:
            mt[p[0]][p[1]] |= 1
        dest = []
        # for mmm in mt:
        #     print(mmm)
        # print()
        # print([a[:2] for a in ps])
        for pi,p in enumerate(ps):
            for i in range(4):
                if head[p[2]][i] & m[p[0]][p[1]]:
                    d = head[p[2]][i]
                    if   d == 1 and not [p[0],p[1]+1] in [a[:2] for a in ps]: p[2] = 0; dest.append([pi,2,p[0],p[1]+1]); break
                    elif d == 2 and not [p[0]-1,p[1]] in [a[:2] for a in ps]: p[2] = 1; dest.append([pi,3,p[0]-1,p[1]]); break
                    elif d == 4 and not [p[0],p[1]-1] in [a[:2] for a in ps]: p[2] = 2; dest.append([pi,0,p[0],p[1]-1]); break
                    elif d == 8 and not [p[0]+1,p[1]] in [a[:2] for a in ps]: p[2] = 3; dest.append([pi,1,p[0]+1,p[1]]); break
            else:
                dest.append([pi,(p[2]+2)&3,p[0],p[1]])
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # print(dest)
        # for mmm in mt:
        #     print(mmm)
        # print("ps = ",ps,dest)
        dellist = []
        for pi,d,dy,dx in dest:
            # print(W,H,dy,dx,mt)
            if not mt[dy][dx]:
                # print("move",W,H,ps[pi][:2],dy,dx)
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[ps[pi][0]][ps[pi][1]] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        # print(dellist)
        for idx in sorted(dellist)[::-1]:
            del ps[idx]
        if not len(ps):
            print(ttt)
            break

    # ms = [stdin.readline() for _ in range(H)]
    # print(m)
    # from pprint import pprint
    # print(ps)
    # for n in m:
    #     print(n)
    # print()



Measured memory_bytes: 5744
import java.io.{BufferedReader, IOException, InputStream, InputStreamReader}
import java.util.{Scanner, StringTokenizer}

import scala.util.Sorting

object Main {
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val H = sc.nextInt()
    val W = sc.nextInt()
    val D = sc.nextInt()
    val N = H * W
    val A = Array.ofDim[(Int, Int)](N + 1)
    
    for {
      h <- 1 to H
      w <- 1 to W
    } {
      val x = sc.nextInt()
      A(x) = (h, w)
    }

    def move(s: (Int, Int), t: (Int, Int)) = math.abs(s._1 - t._1) + math.abs(s._2 - t._2)

    // (1 to D-1) から xまでのコスト
    val cost = Array.ofDim[Int](N + 1)
    (1 to D) foreach { d =>  // 最初の地点dから
      var j = 1
      while(j * D + d <= N) {
//      (0 until (N / D) + (if(d <= N % D) 1 else 0)) foreach { j =>  // j回移動する
//        if (j == 0) cost(d) = 0
//        else {
          val next = d + D * j
          val prev = d + D * (j - 1)
          cost(next) = cost(prev) + move(A(prev), A(next))
//        }
        j += 1
      }
    }

    val Q = sc.nextInt()
    (0 until Q) foreach { _ =>
      val L = sc.nextInt()
      val R = sc.nextInt()
      println(cost(R) - cost(L))
    }
  }

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

  class InputReader(val stream: InputStream) {
    val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
  }
}


Measured memory_bytes: 51208
#include <algorithm>
#include <iomanip>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
// Powered by caide (code generator, tester, and library code inliner)
const int INF = 1e9 + 5;

class Solution {
public:
    void solve(std::istream& in, std::ostream& out) {
        int n,k;
        in >> n >> k;
        vector<int> height(n);
        for (auto &x : height)
            in >> x;
    	
		
        vector<int> dp(n, INF);
        dp[0] = 0;
    	for(int i=0; i<n; i++) {
            for (int j = i + 1; j <=i+k;j++) {
    			if(j<n) {
                    dp[j] = min(dp[j], abs(height[i] - height[j]) + dp[i]);
    			}
    		}
    	}
        out << dp[n - 1] << endl;
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}


#include <fstream>
#include <iostream>


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


    istream& in = cin;


    ostream& out = cout;

    solve(in, out);
    return 0;
}




Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	int n, a, b, i, point1, point2;
	while(1)
	{	
		point1 = 0;
		point2 = 0;
		scanf("%d", &n);
		if ( n == 0 ) break;		
		for ( i = 0; i < n; i++)
		{
			scanf("%d %d", &a, &b);
			if ( a > b )point1 = point1 + a + b;
			else if ( a < b )point2 = point2 + a + b;
			else if ( a == b )
		 	{
				point1 = point1 + a;
				point2 = point2 + b;
			}
		}
		printf("%d %d\n", point1, point2);
	}
return 0;
}

Measured memory_bytes: 1028
def main():
    N, K = (int(i)for i in input().split())
    x = [int(i) for i in input().split()]
    ans = 3 * (10**8)
    st_val = min(x,key=abs)
    st_idx = x.index(st_val)
    
    for i in range(K+1):
        dist = 3 * (10**8)
        if 0 <= st_idx-K+1+i and st_idx+1+i <= N:
            if (x[st_idx-K+1+i] < 0 and x[st_idx+i] <= 0):
                dist = abs(x[st_idx-K+1+i])
            elif (x[st_idx-K+1+i] >= 0 and x[st_idx+i] > 0):
                dist = abs(x[st_idx+i])
            else:
                if abs(x[st_idx-K+1+i]) > abs(x[st_idx+i]):
                    dist = abs(x[st_idx-K+1+i]) + abs(x[st_idx+i]) * 2
                else:
                    dist = abs(x[st_idx-K+1+i]) * 2 + abs(x[st_idx+i])
        elif N < st_idx+1+i:
            break
        ans = min(ans,dist)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 62704
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <time.h>
#include <complex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }
template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll N,A[200007],B[200007],T=0;
  cin >> N ;
  rep(i,N){
    cin >> A[i];
  }
  rep(i,N){
    cin >> B[i];
  }
  rep(i,N){
    if(clock()>1900000){
      return 0;
    }
    if(T==0){
      ll K=A[i]^B[0],L=0,P=0;
      if((A[i]^B[0])==(A[(i+1)%N]^B[1])){
        P=1;
      }
      rep(j,N){
        if((A[(i+j)%N]^B[j])!=K){
          L=1;
          break;
        }
      }
      if(L==0){
        cout << i << " " << K << endl;
        T=1;
      }
    }
    else{
      if((A[i]^B[0])==(A[(i+1)%N]^B[1])){
        cout << i << " " << (A[i]^B[0]) << endl;
      }
    }
  }
}

Measured memory_bytes: 6528
from collections import Counter

N = int(input())
X = input()
cnt = X.count('1')
memo = [0]*(N+1)
memo2 = [[0]*(N+1) for _ in range(2)]
memo2[0][1] = memo2[1][1] = 1

if cnt == 0:
  for _ in range(N):
    print(1)
  exit()

for i in range(1,N+1):
  if i == 1:
    if cnt > 1:
      memo2[0][i] = 1 % (cnt-1)
    memo2[1][i] = 1 % (cnt+1)
  else:
    if cnt > 1:
      memo2[0][i] = memo2[0][i-1]*2 % (cnt-1)
    memo2[1][i] = memo2[1][i-1]*2 % (cnt+1)
  t = 0
  a = i
  while a > 0:
    b = bin(a).count('1')
    a %= b
    t += 1
  memo[i] = t
  
X1 = 0
X_1 = 0
for i in range(1,N+1):
  if X[N-i] == '1':
    X1 += memo2[1][i]
    X_1 += memo2[0][i]
    X1 %= cnt+1
    if cnt > 1:
      X_1 %= cnt-1
    
for i in range(N,0,-1):
  Y = 0
  if X[N-i] == '1':
    if cnt == 1:
      print(0)
      continue
    Y = X_1 - memo2[0][i]
    if Y < 0:
      Y += cnt - 1
    print(memo[Y]+1)
  else:
    Y = X1 + memo2[1][i]
    Y %= cnt + 1
    print(memo[Y]+1)
  

Measured memory_bytes: 84368
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long int ll;

int main(){

    int n;
    cin >> n;
    ll tmp1 = 0,tmp2 = 0;
    ll ans = 1000000000000000000LL;
    
    vector<ll> a(n);

    for(int i = 0;i < n;i++){
        cin >> a[i];
        tmp1+=a[i];
    }


    for(ll i = 0;i < n-1;i++){
        tmp2+=a[i];
        ans = min(ans,abs(tmp1-2*tmp2));
    }
    cout << ans << endl;        

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree < pairs ,  null_type , greater<pairs>,  rb_tree_tag ,  tree_order_statistics_node_update > 
#define ll long long
#define lld long double
#define vc vector<ll>
const ll MOD=(1e9 +7);
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
    return res;}

int main() {
	// your code goes here
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	ll t,n,i,j,k,l,c,f;
	ll w;
	cin>>n>>w;
	vector<pairs> wt(n+1);
	vector<vc>mat(n+1,vc(w+1));
	for(i=1;i<=n;i++)cin>>wt[i].first>>wt[i].second;
	sort(wt.begin(),wt.end());
	//sort(val.begin(),val.end());
	for(i=1;i<=n;i++)
	{
	    if(wt[i].first>w)break;
	    for(j=1;j<=w;j++)
	    {
	        if(j<wt[i].first)
	            mat[i][j]=mat[i-1][j];
	       else
	            mat[i][j]=max(mat[i-1][j],wt[i].second+mat[i-1][j-wt[i].first]);
	    }
	}
	cout<<mat[n][w];
	return 0;
}


Measured memory_bytes: 83048
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {
  cout << (expr ? "Yes" : "No") << "\n";
}  
int D;
vector<int> c(26);
vector<vector<int>> s;
int score(vector<int> t) {
  int ans = 0;
  vector<int> last(26);
  REP(i, D) {
    ans += s[i][t[i]];
    last[t[i]] = i + 1;
    REP(j, 26) ans -= c[j] * (i + 1 - last[j]);
  }
  return ans;
}
double TIME_LIMIT = 1950;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> D;
  vector<int> c(26);
  REP(i, 26) cin >> c[i];
  s = vector<vector<int>>(D, vector<int>(26));
  REP(i, D) REP(j, 26) cin >> s[i][j];

  vector<int> t(D);
  REP(i, D) t[i] = i%26;
  
  clock_t start_time = clock();
  int now = score(t);
  int loop = 0;
  double start_temp = 1000, end_temp = 10;
  int max = 0;
  vector<int> tmax(t);
  while(true) {
    loop++;
    clock_t now_time = clock();
    double time = static_cast<double>(now_time - start_time) / CLOCKS_PER_SEC * 1000.0;
    if(time > TIME_LIMIT) break;
    vector<int> tnew(t);
    int mode = rand() % 10;
    if(mode == 0) {
      int idx = rand() % D;
      int type = rand() % 26;
      tnew[idx] = type;
    } else {
      int idx = rand() % (D-1);
      swap(tnew[idx], tnew[idx+1]);
    }
    int next = score(tnew);
    double temp = start_temp + (end_temp - start_temp) * time / TIME_LIMIT;
    double prob = exp((next-now)/temp);
    if(next > now || prob > (rand()%INF)/(double)INF) {
      t = tnew;
      now = next;
    }
    if(now > max) {
      tmax = t;
      max = now;
    }
    //cout << now << "\n";
    //if(next < now) cout << prob << "\n";
  }
  REP(i, D) cout << (tmax[i]+1) << "\n";
  //cout << max << "\n";
  //cout << loop << "\n";
}

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

int main(){
  cout << fixed << setprecision(12);
  
  double r;
  cin>>r;

  double PI = acos(-1);
  double area = r * r * PI;
  double cir = (r + r) * PI;
  
  printf("%f %f", area, cir);
  
  return 0;
}


Measured memory_bytes: 3196
#include <iostream>
#include <climits>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef std::pair<int,int> P;
const int AMAX = 100000;
ll cnt[AMAX + 1];

int main(void) {
  int N;
  ll K;
  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    int ai, bi; cin >> ai >> bi;
    cnt[ai] += bi;
  }

  for (int ans = 1; ans <= AMAX; ans++) {
    if (K <= cnt[ans]) {
      cout << ans << endl;
      break;
    }
    K -= cnt[ans];
  }
}


Measured memory_bytes: 1024
s = list(input() for _ in range(3))
player = ['a', 'b', 'c']
turn = 0
while True:
  if s[turn] == '':
    print(player[turn].upper())
    break
  tmp = player.index(s[turn][0])
  s[turn] = s[turn][1:]
  turn = tmp


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <iterator>

int main() {
  long long A, B;
  std::set<long long> aset, bset, res;
  scanf("%lld %lld", &A, &B);
  int amin = (int)std::sqrt(A), bmin = std::sqrt(B);
  for (int i = 1; i <= amin; ++i) {
    if (A%i == 0) {
      aset.insert(i);
      aset.insert(A/i);
    }
  }
  for (int i = 1; i <= bmin; ++i) {
    if (B%i == 0) {
      bset.insert(i);
      bset.insert(B/i);
    }
  }
  std::set_intersection(aset.begin(), aset.end(),
                        bset.begin(), bset.end(),
                        std::inserter(res, res.end()));
  std::vector<long long> d(res.begin(), res.end());
  for (int i = 1; i < d.size(); ++i) {
    for (std::vector<long long>::iterator j = d.begin() + i+1; j != d.end(); ++j) {
      if ((*j) % (*(d.begin()+i)) == 0) {
        d.erase(j);
        --j;
      }
    }
  }
  std::cout << d.size() << std::endl;
  return 0;
}


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

using namespace std;

int n, m;
void read()
{
    cin >> n >> m;
}

void solve()
{
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
}

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

    read();
    solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<set>
#define read(x) scanf("%d",&x)
#define write(x) printf("%d",x)
using namespace std;
int k , n; 
set <int> s;
bool cnt(int x)
{
	while(x > 0)
	{
		bool q = s.count(x % 10);
		if(!q)	return false;
		x /= 10;
	}
	return true;
}
int main()
{
	read(n);read(k);
	for(int i = 0 ; i <= 9 ; i++)
		s.insert(i);
	for(int i = 1 ; i <= k ; i++)
	{
		int x;
		read(x);
		s.erase(x);
	}
	int i;
	for(i = n ; !cnt(i) ; i++);
	printf("%d\n",i);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int 
using namespace std;
vector<ll>a;
vector<ll>dp;
ll rec(ll i)
{
	ll x,y;
	if(i==a.size()-1)
    return 0;
  	ll ans=dp[i];
  	if(ans!=-1)
    return dp[i];
  	if(i+1<a.size())
    x=rec(i+1)+abs(a[i]-a[i+1]);
    if(i+2<a.size())
    y=rec(i+2)+abs(a[i]-a[i+2]);
   	ans=min(x,y);
  	return dp[i]=ans;
}
int main()
{
	ll n,i;
    cin>>n;
  	a.resize(n);
  	dp.resize(n+1,-1);
  	for(i=0;i<n;i++)
    cin>>a[i];
    cout<<rec(0);
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

const int maxn = 400400;
const int root = 1;
int nodes = 2;
int to[maxn][26];
int where[maxn];
int S[maxn];
int uid[maxn];

typedef array<array<int, 26>, 26> Arr;

Arr res[100100];
int up[100100];

Arr arr;
void dfs(int u, int from = -1, int fch = -1, int fup = 0) {
    if (from != -1) {
        forn (i, 26) {
            int v = to[from][i];
            if (v != 0 && v != u)
                arr[fch][i] += S[v];
        }
    }
    fup += uid[u] != -1;
    if (uid[u] != -1) {
        res[uid[u]] = arr, up[uid[u]] = fup;
    }
    forn (i, 26) {
        int v = to[u][i];
        if (v) {
            dfs(v, u, i, fup);
        }
    }
    if (from != -1) {
        forn (i, 26) {
            int v = to[from][i];
            if (v != 0 && v != u)
                arr[fch][i] -= S[v];
        }
    }
}

void dfs1(int u) {
    forn (i, 26) {
        int v = to[u][i];
        if (v) {
            dfs1(v);
            S[u] += S[v];
        }
    }
}

int main() {
    #ifdef LOCAL
    assert(freopen("e.in", "r", stdin));
    #else
    #endif
    int n;
    cin >> n;
    forn (i, maxn)
        uid[i] = -1;
    forn (i, n) {
        string s;
        cin >> s;
        int u = root;
        for (auto ch: s) {
            int c = ch - 'a';
            if (to[u][c] == 0)
                to[u][c] = nodes++;
            u = to[u][c];
        }
        where[i] = u;
        uid[u] = i;
        ++S[u];
    }
    dfs1(root);
    Arr arr;
    forn (i, 26)
        forn (j, 26)
            arr[i][j] = 0;
    dfs(root);
    int q;
    cin >> q;
    forn (ii, q) {
        int k;
        string ord;
        cin >> k >> ord;
        --k;
        int res = up[k];
        //cerr << res << '\n';
        forn (i, 26)
            forn (j, i) {
                int s1 = ord[i] - 'a';
                int s2 = ord[j] - 'a';
                res += ::res[k][s1][s2];
            }
        cout << res << '\n';
    }
}


Measured memory_bytes: 276864
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    vector<long long> a(M), b(M);
    vector<int> c(M);
    for(int i=0; i<M; i++){
        cin >> a[i] >> b[i];
        int x = 0;
        for(int j=0; j<b[i]; j++){
            int tmp;
            cin >> tmp;
            tmp--;
            x |= (1<<tmp);
        }
        c[i] = x;
    }
    vector<vector<long long>> dp(M+1, vector<long long>(1<<N, 1LL<<60));
    dp[0][0] = 0;
    for(int i=0; i<M; i++){
        for(int j=0; j<(1<<N); j++){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);

            int k = j | c[i];
            dp[i+1][k] = min(dp[i+1][k], dp[i][j] + a[i]);
        }
    }
    long long ans = dp[M][(1<<N)-1];
    if(ans == 1LL<<60)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

Measured memory_bytes: 32384
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;


string s1,s2;
string ans;
int n,m;
int f[3005][3005];
int t[3005][3005];

void inp()
{
    cin >> s1;
    cin >> s2;
    n = s1.size();
    m = s2.size();
}


void proc()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int ii = i-1;
            int jj = j-1;
            if (s1[ii] == s2[jj])
            {
                f[i][j] = f[i-1][j-1] + 1;
                t[i][j] = 10;
            }
            else
            {
                if (f[i-1][j] < f[i][j-1])
                {
                    t[i][j] = 2;
                }
                else
                {
                    t[i][j] = 1;
                }
                f[i][j] = max(f[i-1][j],f[i][j-1]);
            }
        }
    }
    int x = n;
    int y = m;
    while (x > 0 && y > 0)
    {
        int i,j;
        if (t[x][y] == 10)
        {
            ans += s1[x-1];
            i = x-1;
            j = y-1;
        }
        else if (t[x][y] == 1)
        {
            i = x-1;
            j = y;
        }
        else if (t[x][y] == 2)
        {
            i = x;
            j = y-1;
        }



        x = i;
        y = j;
    }
    //cout << ans;
}


void putout()
{
    for (int i = ans.size()-1; i >= 0; i--)
    {
        cout << ans[i];
    }
}


int main()
{
    inp();
    proc();
    putout();
    return 0;
}


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

using namespace std;

using ll = long long;

int main(){
    string s, s1;
    cin >> s >> s1;
    for(ll i = 0; i < s.length(); ++i){
        if(s[i] != s1[i]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;

}


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

int main(){

    int N,M;
    cin >> N >> M;

    vector<vector<int>> v;
    for(int i=0;i<M;i++){
        int k;
        cin >> k;
        vector<int> tmp;
        for(int j=0;j<k;j++){
            int s;
            cin >> s;
            s--;
            tmp.emplace_back(s);
        }
        v.push_back(tmp);
    }

    vector<int> p;
    for(int i=0;i<M;i++){
        int t;
        cin >> t;
        p.emplace_back(t);
    }

    int ans=0;

    vector<int> s(N);
    for(int bit =0; bit < (1<<N); bit++){
        vector<int> l;
        bool b=true;
        for(int i=0;i<N;i++){
            if(bit & (1<<i)){
                s[i]=1;
            }else{
                s[i]=0;
            }
        }

        for(int j=0;j<M;j++){
            int sum=0;
            for(auto x:v[j]){
                sum+=s[x];
            }
            if(sum%2!=p[j])b=false;
        }

        if(b)ans++;
    }

    cout << ans << endl;
            

    return 0;
}

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

int w,h;
char fie[72][72];
string str[72][72];

int main(void){
	while(1){
		scanf("%d %d",&w,&h);
		if(w+h==0)break;
		for(int i=0;i<h;i++){
			string in;
			cin >> in;
			for(int j=0;j<w;j++){
				fie[j][i]=in[j];
				str[j][i]="";
			}
		}
		string res="";
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(str[j][i]=="" && fie[j][i]=='0')continue;
				if(fie[j][i]>='0' && fie[j][i]<='9'){
					str[j][i]+=fie[j][i];
				}else continue;
				if(res.size()<str[j][i].size() || (res.size()==str[j][i].size() && res<str[j][i])){
					res=str[j][i];
				}
				if(str[j+1][i].size()<str[j][i].size() || (str[j+1][i].size()==str[j][i].size() && str[j+1][i]<str[j][i])){
					str[j+1][i]=str[j][i];
				}
				if(str[j][i+1].size()<str[j][i].size() || (str[j][i+1].size()==str[j][i].size() && str[j][i+1]<str[j][i])){
					str[j][i+1]=str[j][i];
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 1444
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res=res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}



signed main() {
	int n;
	string s, s2;
	set<string>se;
	cin >> n;
	cin >> s;
	se.insert(s);
	rep(i, n - 1) {
		cin >> s2;
		if (s.back() != s2[0]) {
			cout << "No" << endl;
			return 0;
		}
		if (se.count(s2)) {
			cout << "No" << endl;
			return 0;
		}
		se.insert(s2);
		s = s2;
	}
	cout << "Yes" << endl;
}

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

int main() {
  int A,B,C,D,E ;
  cin >>A>>B>>C>>D>>E ;
  int F;
  F= (A + 9)/10+(B + 9)/10+(C + 9)/10+(D + 9)/10+(E + 9)/10;
  int a,b,c,d,e;
  a = (A%10+9)%10 ;
  b = (B%10+9)%10 ;
  c = (C%10+9)%10 ;
  d = (D%10+9)%10 ;
  e = (E%10+9)%10 ;
  int minimum = min(min(min(min(a, b), c), d), e); // 最小値を計算
   cout << F*10 + minimum - 9 << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define brk system("pause");

const int N = 1e5 + 1;
int a[101], dp[N];

main()
{
	ios::sync_with_stdio(0);
	
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	for(int i = a[1]; i <= k; i++)
		for(int j = 1; j <= n; j++)
			if(i - a[j] >= 0)
				if(dp[i - a[j]] == 0)
					dp[i] = 1;
	
	if(dp[k]) cout << "First" << endl;
	else cout << "Second" << endl;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;
//const int INF=(1<<30);


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

  vector<ll> a(N);
  REP(i,N)cin>>a[i];

  vector<ll> s(N+1);
  s[0]=0;
  REP(i,N)s[i+1]=s[i]+a[i];

  ll ans = INF;
  FOR(i,1,N){
    ans = min(ans, abs(2 * s[i] - s[N]));
  }
  cout << ans << endl;
}



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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair



ll solve(ll l, ll n, vl x) {
  vl sum1(n + 1);
  rep (i, n) {
    sum1[i + 1] = sum1[i] + 2*x[i];
  }
  vl sum2(n + 1);
  rep (i, n) {
    sum2[i + 1] = sum2[i] + 2*(l - x[n - 1 - i]);
  }
  ll res = -INF;
  rep (i, n) {
    if ((n - i) % 2) {
      chmax(res, sum1[(n - i)/2 + 1 + i] - sum1[i] + sum2[(n - i) / 2] - x[(n - i) / 2 + i]);
    }
    else {
      chmax(res, sum1[(n - i)/2 + i] - sum1[i] + sum2[(n - i) / 2] - (l - x[n - (n - i)/2]));
    }
  }
  return res;
}
  
  
  

int main() {
  ll l, n;
  cin >> l >> n;
  vl x(n);
  vl x2(n);
  rep (i, n) {
    cin >> x[i];
    x2[n - 1 - i] = l - x[i];
  }
  ll ans = max(solve(l, n, x), solve(l, n, x2));
  cout << ans << endl;
}


Measured memory_bytes: 9672
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
#define MK make_pair
const ll E=1e18+7;
const ll MOD=1000000007;





int main(){
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> rq;
    for(int i=0;i<m;i++){
        ll l,r;
        cin>>l>>r;
        rq.push_back({r,l});
    }
    sort(rq.begin(),rq.end());
    ll mx=-1;
    ll count=0;
    for(int i=0;i<rq.size();i++){
        if(rq[i][1]<mx){continue;}
        count++;
        mx=rq[i][0];
    }
    cout<<count<<endl;
    
    
    
    return 0;
}


Measured memory_bytes: 6836
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,flag=0;
    cin >> n;
    while(n!=0)
    {
        int rem = n % 10;
        if(rem==7)
        {
            flag=1;
            break;
        }
        n=n/10;
    }
    if(flag==1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


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

int main() {
  int n, k;
  while(cin >> n >> k, n+k) {
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    long long ans = -10000000000;
    for(int i = 0; i < n-k; i++) {
      long long sum = 0;
      for(int j = 0; j < k; j++) {
	sum += a[i+j];
      }
      if(ans < sum) ans = sum;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1524
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 1000000007
#define N 100010
ll n,m,q;
ll a[N],b[N],c[N];
namespace uf{
    ll p[N];
    void init(){
        for(int i=0;i<N;i++){
            p[i]=i;
        }
    }
    ll par(ll x){
        return p[x]=(p[x]==x?x:par(p[x]));
    }
    void unite(ll a,ll b){
        a=par(a),b=par(b);
        if(a==b)return;
        p[b]=a;
    }
    bool same(ll a,ll b){
        a=par(a),b=par(b);
        return a==b;
    }
};

int main(){
  cin>>n>>m>>q;
  uf::init();
  for(int i=0;i<q;i++){
      cin>>a[i]>>b[i]>>c[i];
      if(c[i]==0){
          uf::unite(a[i],b[i]);
      }
  }
  ll cnt=0;
  for(int i=0;i<n;i++){
      if(uf::p[i]==i){
          cnt++;
      }
  }
  bool ok=1,th=0;
  for(int i=0;i<q;i++){
      if(c[i]==1){
          th=1;
          if(uf::same(a[i],b[i])){
              ok=0;
          }
      }
  }
  if(ok==0){
      cout<<"No"<<endl;
      return 0;
  }
  if(n-1==m){
      if(th==0)cout<<"Yes"<<endl;
      else cout<<"No"<<endl;
      return 0;
  }
  if(cnt==1){
      cout<<"No"<<endl;
  }
  if(cnt==2){
      cout<<"No"<<endl;
  }
  if(cnt>=3){
      if((cnt-1)*(cnt-2)/2+n-1>=m){
          cout<<"Yes"<<endl;
      }
      else cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 3328
// Aizu Vol-0 0069: Drawing Lots II
// 2017.8.6

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

char *gets(char *);
char buf[100], *p;

int getInt(void)
{
	int n = 0;
	while (isspace(*p) || *p == ',') p++;
	while (isdigit(*p)) n = 10 * n + (*p++ - '0');
	return n;
}

int a[32][10], N, D;
int s[32][10];

int main()
{
	int i, j, k, n, m;

	while (1) {
		gets(buf); N = atoi(buf); if (!N) break;
		gets(buf); m = atoi(buf);
		gets(buf); n = atoi(buf);
		gets(buf); D = atoi(buf);
		for (i = 1; i <= D; i++) {
			gets(p = buf); while (isspace(*p)) p++;
			for (j = 1; j < N; j++) a[i][j] = (*p++ == '1');
		}
		for (i = 1; i <= D; i++) a[i][0] = a[i][N] = 0;
		for (j = 1; j <= N; j++) s[D+1][j] = j;
		for (i = D; i > 0; i--) {
			for (j = 1; j <= N; j++) s[i][j] = s[i + 1][j];
			for (j = 1; j < N; j++) {
				if (a[i][j]) k = s[i][j], s[i][j] = s[i][j + 1], s[i][j + 1] = k;
			}
		}
		if ((k = s[1][m]) == n) puts("0");
		else {
			for (i = 1; i <= D; i++) {
				for (j = 1; j < N; j++) {
					if (((s[i][j] == k && s[i][j + 1] == n) || (s[i][j] == n && s[i][j + 1] == k))
						&& a[i][j-1] == 0 && a[i][j] == 0 && a[i][j + 1] == 0) {
					printf("%d %d\n", i, j); goto Done; }
				}
			}
			puts("1");
		}
	Done:;
	}
	return 0;
}

Measured memory_bytes: 532
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int n;
    while(cin >> n,n){
        vector<int> cards(2*n+1,0);
        rep(i,n){
            int a;cin >> a;
            cards[a]++;
        }
        vector<int>taro,hana;
        for(int i=1;i<2*n+1;i++){
            if(cards[i])taro.push_back(i);
            else hana.push_back(i);
        }
        int turn = 0,num=0;
        while(!taro.empty()&&!hana.empty()){
            if(!turn){
                auto ite = lower_bound(All(taro),num);
                if(ite==taro.end()){
                    num = 0;
                }else{
                    num = *ite;
                    taro.erase(ite);
                }
            }else{
                auto ite = lower_bound(All(hana),num);
                if(ite==hana.end()){
                    num = 0;
                }else{
                    num = *ite;
                    hana.erase(ite);
                }
            }
            turn = 1 - turn;
        }
        cout << hana.size() << endl;
        cout << taro.size() << endl;
    }

    return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
const ll mod = 998244353;
int main(){
  ll N,K,i,j;scanf("%lld%lld",&N,&K);
  ll dp[N] = {};dp[0] = 1;
  pair<pair<ll,ll>,ll> S[K] = {};
  for(i=0;i<K;i++){
    scanf("%lld%lld",&S[i].first.first,&S[i].first.second);
    if(S[i].first.first == 1) S[i].second++;
  }
  for(i=1;i<N;i++){
    for(j=0;j<K;j++){
      dp[i] = (dp[i]+S[j].second)%mod;
    }
    for(j=0;j<K;j++){
      if(i+1 >= S[j].first.first) S[j].second = (S[j].second+dp[i+1-S[j].first.first])%mod;
      if(i >= S[j].first.second) S[j].second = (S[j].second-dp[i-S[j].first.second]);
      if(S[j].second < 0) S[j].second += mod;
    }
  }
  printf("%lld\n",dp[N-1]);
}

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

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

#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define p(x) cout << (x) << endl
#define FOR(i,r,n) for(ll i=(ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n); i>=r; i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) REP(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pb push_back

const int inf = (int)1e9;
const ll INF = (ll)1e18;

// vectorの中身をcout << vs;で表示
template <class T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
    o << "{";
    for (int i = 0; i < (int)v.size(); i++) o << (i > 0 ? ", " : "") << v[i];
    o << "}";
    return o;
}

ll gcd (ll a, ll b) {
	while (b > 0) {
		ll t = a % b;
		a = b, b = t;
	}
	return a;
}

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

bool is_prime (ll n) {
		if (n < 2) return false;
		else if (n == 2) return true;
		else if (n % 2) return false;
		
		double sqrtn = sqrt(n);
		for (ll i = 3; i < sqrtn; i += 2) {
			if (n % i == 0) return false; 
		}
		return true;
}

ll ctoi(char c) {
	return (ll)(c - 48);
}

ll n, k, cnt=0, ans=0;
string s,t;

// ==================== template ============================

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

	ll a, b; cin >> a >> b;
	n = b - a;
	ll sum = 0;
	REP(i, n) {
		sum += i;
	}
	cout <<  sum - a << endl;

}



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

int main(){
    int N,L;
    cin >> N >> L;
    vector<string> data(N);
    
    for(int i = 0;i<N;i++){
        cin >> data.at(i);
    }
    
    sort(data.begin(),data.end());
    
    string str = "";
    
    for(int i = 0;i<N;i++){
        str += data.at(i);
    }
    cout << str << endl;
}

Measured memory_bytes: 256
'''
def binsearch(x, t):
    low = 0
    high = len(x) - 1
    k = (low + high) // 2
    if x[low] == t:
        return low
    if x[high] == t:
        return high
    while (low <= high):
        if x[k] < t:
            low = k
        elif x[k] > t:
            high = k
        else:
            return k
        k = (low + high) // 2
'''
N=int(input())
X=[int(i) for i in input().split()]
Y=sorted(X)
M=N//2
L=Y[M-1]
R=Y[M]
for i in range(N):
    if X[i]<=L:
        print(R)
    else:
        print(L)



Measured memory_bytes: 25476
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
#include <cctype>
using namespace std;
using ll = long long;
int main(){
  int n,k;
  cin>>n>>k;
  int h[n];
  int ans=0;
  for(int i=0;i<n;i++){
    cin>>h[i];
    if(h[i]>=k)ans++;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define popcnt(a) __builtin_popcount(a)
#define FastIO() ios::sync_with_stdio(false), cin.tie(0);
#define IO() freopen("palindrome.in","rw",stdin)
#define error(args...)                       \
{                                            \
    cerr<<"LINE "<<__LINE__;                 \
    string _s = #args;                       \
    replace(_s.begin(), _s.end(), ',', ' '); \
    stringstream _ss(_s);                    \
    istream_iterator<string> _it(_ss);       \
    err(_it, args);                          \
    cerr<<endl;                              \
}
void err(istream_iterator<string> it)
{
} 
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
  cerr<<' '<< *it << " = " << a ;
  err(++it, args...);
} 
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 1e6+9, M = (1<<31), OO = 0x3f3f3f3f;
int arr[N];
int vis[N];
vector<int> adj[N];
void dfs(int p=1,int sum=arr[1])
{
  if(vis[p]) return ;
  vis[p]=1;
  for(auto ch : adj[p])
  {
    if(!vis[ch])
    {
      arr[ch]+=sum;
      dfs(ch,arr[ch]);
    }
  }
}
int main()
{
  int n,q;
  scanf("%d%d",&n,&q);
  for(int i=0;i<n-1;++i)
  {
    int u,v;
    scanf("%d%d",&u,&v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  while(q--)
  {
    int u,x;
    scanf("%d%d",&u,&x);
    arr[u]+=x;
  }
  dfs();
  for(int i=1;i<=n;++i) printf("%d%c",arr[i]," \n"[i==n]);
  #ifdef _LOCAL_DEFINE
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
  #endif
  return 0; 
}

Measured memory_bytes: 41472
N,X,Y=map(int,input().split())
G=[[0 for i in range(N)] for i in range(N)]
for i in range(0, N):
    for j in range(0, N-i):
        G[i][i+j]=j
G[X-1][Y-1]=1
for i in range(Y-1,N-1):
    G[X-1][i+1]=G[X-1][i]+1
for i in range(0,N):
    if G[X-1][Y-2-i]<G[X-1][Y-1-i]+1:
        break
    else:
        G[X-1][Y-2-i]=G[X-1][Y-1-i]+1
for i in range(0, N):
    #a=G[i][X-1]
    a=abs(i-(X-1))
    for j in range(i,N-1):
        G[i][j+1]=min(G[i][j+1], a+G[X-1][j+1])
ans=[0 for i in range(N)]
for i in range(0,N):
    for j in range(0,N-i):
        ans[G[i][i+j]]+=1
for i in range(N-1):
    print(ans[i+1])

Measured memory_bytes: 79452
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
    if(a>b)
        swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
    char str[100];
    sprintf(str,"%s.in",s);
    freopen(str,"r",stdin);
    sprintf(str,"%s.out",s);
    freopen(str,"w",stdout);
#endif
}
int rd()
{
    int s=0,c;
    while((c=getchar())<'0'||c>'9');
    do
    {
        s=s*10+c-'0';
    }
    while((c=getchar())>='0'&&c<='9');
    return s;
}
int upmin(int &a,int b)
{
    if(b<a)
    {
        a=b;
        return 1;
    }
    return 0;
}
int upmax(int &a,int b)
{
    if(b>a)
    {
        a=b;
        return 1;
    }
    return 0;
}
struct graph
{
    int v[200010];
    int t[200010];
    int h[100010];
    int n;
    graph()
    {
        n=0;
    }
    void add(int x,int y)
    {
        v[++n]=y;
        t[n]=h[x];
        h[x]=n;
    }
};
graph g1,g2,g;
int fa[100010];
int fb[100010];
int a1[100010];
int a2[100010];
int st[100010];
int top;
int b[100010];
int c[100010];
void dfs1(int x)
{
    int i;
    for(i=g1.h[x];i;i=g1.t[i])
        dfs1(g1.v[i]);
    if(a1[x])
        st[++top]=x;
    while(top>=2)
    {
        g.add(st[top],st[top-1]);
        g.add(st[top-1],st[top]);
        top-=2;
    }
}
void dfs2(int x)
{
    int i;
    for(i=g2.h[x];i;i=g2.t[i])
        dfs2(g2.v[i]);
    if(a2[x])
        st[++top]=x;
    while(top>=2)
    {
        g.add(st[top],st[top-1]);
        g.add(st[top-1],st[top]);
        top-=2;
    }
}
void dfs(int x,int v)
{
    c[x]=v;
    b[x]=1;
    int i;
    for(i=g.h[x];i;i=g.t[i])
        if(!b[g.v[i]])
            dfs(g.v[i],-v);
}
int main()
{
//  open("agc018f");
    int n;
    scanf("%d",&n);
    int i;
    int rt1,rt2;
    for(i=1;i<=n;i++)
        a1[i]=a2[i]=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&fa[i]);
        if(fa[i]==-1)
            rt1=i;
        else
        {
            g1.add(fa[i],i);
            a1[fa[i]]^=1;
        }
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&fb[i]);
        if(fb[i]==-1)
            rt2=i;
        else
        {
            g2.add(fb[i],i);
            a2[fb[i]]^=1;
        }
    }
    for(i=1;i<=n;i++)
        if(a1[i]!=a2[i])
        {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    printf("POSSIBLE\n");
    top=0;
    dfs1(rt1);
    top=0;
    dfs2(rt2);
    for(i=1;i<=n;i++)
        if(!b[i])
            dfs(i,1);
    for(i=1;i<=n;i++)
        if(!a1[i])
            printf("0 ");
        else
            printf("%d ",c[i]);
    return 0;
}

Measured memory_bytes: 10752
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
	
	
	public static int dfs(final int p, final int q, final int a, final int cur_a, final int n, final int pre_div){
		//System.out.println(p + " " + q + " " + a + " " + n + " " + pre_div);
		
		if(n == 0){
			return p == 0 ? 1 : 0;
		}else if(p == 0){
			return 1;
		}
		
		int ret = 0;
		for(int div = pre_div; div <= a; div++){
			if(p * div > q * n){
				//System.out.println("! " + p + " " + q + " " + a + " " + n + " " + pre_div);
				break;
			}else if(p * div - q < 0){
				continue;
			}else if(cur_a * div > a){
				continue;
			}
			
			ret += dfs(p * div - q, q * div, a, cur_a * div,  n - 1, div);
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		
		while(true){
			final int p = sc.nextInt();
			final int q = sc.nextInt();
			final int a = sc.nextInt();
			final int n = sc.nextInt();
			
			if(p == 0 && q == 0 && a == 0 && n == 0){
				break;
			}
			
			System.out.println(dfs(p, q, a, 1, n, 1));
		}
		
	}
}

Measured memory_bytes: 21872
tax1, tax2 = map(int,input().split())

def _tax(tax,rate):
  return (100*tax)/rate, (100*(tax+1))/rate

tax1_m, tax1_u = _tax(tax1, 8)
tax2_m, tax2_u = _tax(tax2, 10)

import math
if tax1_m < tax2_u and tax2_m < tax1_u:
  print(math.ceil(max(tax2_m, tax1_m)))
else:
  print(-1)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
 //解説見た
int main() {
  int n,m;
  cin >> n >> m;
  vector<int> f(m);
  for(int i=0;i<n;i++){
    int k;
    cin >> k;
    for(int j=0;j<k;j++){
      int p;
      cin >> p;
      p--;
      f.at(p)++;
    }
  }
  int ans=0;
  for(int i=0;i<m;i++){
    if( f.at(i) == n ){
      ans++;
    }
  }
  cout << ans << endl;
  

  return 0;
  
}

Measured memory_bytes: 256