akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for u, v in LIR(m):
    graph[u - 1] += [v - 1]


s, t = LI()
dist = [[INF for _ in range(3)] for _ in range(n)]
dist[s - 1][0] = 0
que = deque([(s - 1, 0)])
while que:
    cur, cost = que.popleft()
    for nxt in graph[cur]:
        if cost + 1 < dist[nxt][(cost + 1) % 3]:
            dist[nxt][(cost + 1) % 3] = cost + 1
            que += [(nxt, cost + 1)]



if dist[t - 1][0] == INF:
    print(-1)
else:
    print(dist[t - 1][0] // 3)

Measured memory_bytes: 95536
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

int main(void)
{
  int N,i,j,d[101],sum=0;

  scanf("%d",&N);
  
  for(i=1;i<=N;i++)
  {
    scanf("%d",&d[i]);
  }

  for(i=1;i<=N;i++)
  {
    for(j=1;j<=N;j++)
    {
      if(i!=j)
      {
        sum+=d[i]*d[j];
        //printf("%d\n",d[i]*d[j]);
      }
    }
  }
  
  
  printf("%d",sum/2);
  
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll,ll>;
using vec = vector<ll>;
using vecp = vector<P>;
using mat = vector<vec>;
using matp = vector<vecp>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define all(v) v.begin(), v.end()

ll op(ll a, ll b) {
    return max(a, b);
}

ll e() {
    return (ll)(-1);
}
ll d;
bool f(ll x){
  return x<d;
}

int main(){
  ll N,Q;
  cin >> N >> Q;
  vec A(N);
  rep(i,N){
    cin >> A.at(i);
  }
  
  segtree<ll, op, e> seg(A);
  rep(i,Q){
    ll a,b,c;
    cin >> a >> b >> c;
    b--;
    if(a==1){
      seg.set(b,c);
    }else if(a==2){
      cout << seg.prod(b,c) << endl;
    }else{
      d=c;
      cout << seg.max_right<f>(b)+1 << endl;
    }
  }
}

Measured memory_bytes: 9068
n = int(input())
l = []
l1 = [0]
for i in range(n):
    l1 = input().split()
    l.append([l1[0],int(l1[1]),i+1])
l_rank = sorted(sorted(l, key=lambda x: x[1], reverse=True),key=lambda x: x[0])
for i in range(n):
    print(l_rank[i][2])

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

int main(){

    std::string s;
    std::cin >> s;

    std::vector<size_t> v(s.size() + 1, 0);

    for(size_t i = 0; i < s.size(); i++){
        if(s[i] == '<'){
            v[i + 1] = std::max(v[i] + 1, v[i + 1]);
        }
    }

    for(size_t i = 0; i < s.size(); i++){
        auto index = s.size() - i - 1;
        if(s[index] == '>'){
            v[index] = std::max(v[index], v[index + 1] + 1);
        }
    }

    std::cout << std::accumulate(v.begin(), v.end(), 0ul) << std::endl;

    return 0;
}


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

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

using ll = long long;
using graph = vector<vector<int>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;
vector<bool> seen;

void f(const graph &g,int s,vector<int> &ans){
  for(auto nx:g[s]){
    if(seen[nx]) continue;
    seen[nx]= true;
    ans.push_back(nx);
    f(g,nx,ans);
    break;
  }
}

int main() {
  int N,M;
  cin>>N>>M;
  graph g(N);
  for(int i = 0; i < M; i++){
    int x,y;
    cin>>x>>y;
    g[x-1].push_back(y-1);
    g[y-1].push_back(x-1);
  }
  seen.assign(N,false);
  vector<int> ansa,ansb;
  seen[0]=true;
  f(g,0,ansa);
  f(g,0,ansb);
  reverse(ansb.begin(),ansb.end());
  cout<<ansa.size()+1+ansb.size()<<endl;
  for(auto x:ansb) cout<<x+1<<" ";
  cout<<1<<" ";
  for(auto x:ansa) cout<<x+1<<" ";
  cout<<endl;
}

Measured memory_bytes: 11000
n = gets.to_i
s = gets.chomp
popcount = s.count("1")
x0 = s.to_i(2) % (popcount + 1)
x1 = 0
if popcount != 1
  x1 = s.to_i(2) % (popcount - 1)
end
for i in 0..n-1
  if s[i] == "0"
    x = x0 + 2.pow(n-1-i,popcount + 1)
    x = x % (popcount + 1)
    count = 1
    while x != 0
      x = x % x.to_s(2).count("1")
      count += 1
    end
    puts count
  else
    if popcount == 1
      puts 0
    else
      x = x1 - 2.pow(n-1-i,popcount - 1)
      x = x % (popcount - 1)
      count = 1
      while x != 0
        x = x % x.to_s(2).count("1")
        count += 1
      end
      puts count
    end
  end
end

Measured memory_bytes: 14708
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A , B;
  cin >> A >> B ;
  int count = 0 ;
  for ( int a=1 ; a<10 ; a++ ) {
    for ( int b=0 ; b<10 ; b++ ){
      for ( int c=0 ; c<10 ; c++ ){
        int x=10000*a+1000*b+100*c+10*b+a; 
        if ( A <= x && x <= B){
        count +=1; 
        }
      }
    }
  }
  cout << count << endl ;
}



Measured memory_bytes: 3648
using System;

namespace abc058_b
{
    class Program
    {
        static void Main(string[] args)
        {
            string a = Console.ReadLine();
            string b = Console.ReadLine();
            for (int i = 0; i < b.Length; i++)
            {
                Console.Write(a[i]);
                Console.Write(b[i]);
            }
            if (a.Length != b.Length)
            {
                Console.WriteLine(a[a.Length - 1]);
            }
            else
            {
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 13140
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new java.util.Scanner(System.in);
        int n = scan.nextInt();
        String s = scan.next();
        char[] c = new char[n];
        int out = 0;
        for(int i = 0; i < n; i++){
            c[i] = s.charAt(i);
        }
        for(int i = 0; i < n - 2; i++){
            if(c[i] == 'A' && c[i + 1] == 'B' && c[i + 2] == 'C'){
                out++;
            } 
        }
        System.out.println(out);
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>

using namespace std;

struct Point{int x,y;};
struct Rect{
  int rx,ry,lx,ly;
  bool operator < (const Rect& r) const {
    if(rx != r.rx) return rx < r.rx;
    if(ry != r.ry) return ry < r.ry;
    if(lx != r.lx) return lx < r.lx;
    return ly < r.ly;    
  }
};

const int MAX = 15;
map<Rect, int> idx;
int order[MAX],N;

void init(){
  idx.clear();
  memset(order,-1,sizeof(order));
}

vector<Rect> input(){

  vector<Rect> res(N);
  for(int i = 0; i < N; i++){
    int x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    res[i].rx = min(x1,x2);
    res[i].ry = min(y1,y2);
    res[i].lx = max(x1,x2);
    res[i].ly = max(y1,y2);
    idx[res[i]] = i;
  }
  return res;
}

bool bump(const Point& l, const Point& r, const vector<Rect>& v){
  
  for(int i = 0; i < (int)v.size(); i++){
    int tx = v[i].rx;
    int ty = v[i].ry;
    int by = v[i].ly;
    if(r.x <= tx && tx <= l.x && ty < l.y && l.y < by) return true;
  }
  return false;
}

bool contain(const Point& l, const Point& r, const Rect& rect){
  if(r.x > rect.rx || l.x < rect.rx) return false;
  if(r.x > rect.lx || l.x < rect.lx) return false;
  if(r.y < rect.ly) return false;
  return true;
}

void solve(const vector<Rect>& v, int& n){
  
  int pos = -1;
  for(int i = 0; i < (int)v.size(); i++){
    if(order[idx[v[i]]] != -1) continue;
    if(pos == -1 || v[pos].rx > v[i].rx ||
       (v[pos].rx == v[i].rx && v[pos].ry > v[i].ry)) pos = i;
  }

  if(pos == -1) return;
  
  order[idx[v[pos]]] = n++;

  Point pr = (Point){v[pos].rx, v[pos].ly};
  Point pl = pr; pl.x++;
  
  while(!bump(pl,pr,v) && pl.x <= 501) pl.x++;

  vector<Rect> L;
  for(int i = 0; i < (int)v.size(); i++){
    if(order[idx[v[i]]] != -1) continue;
    if(contain(pl,pr,v[i])) L.push_back(v[i]);
  }
  solve(L,n);
  solve(v,n);
}

int main(){

  bool isFirst = true;
  while(cin >> N && N){
    if(isFirst) isFirst = false;
    else cout << endl;
    init();
    vector<Rect> v = input();
    int n = 1;
    solve(v,n);
    for(int i = 0; i < N; i++) cout << order[i] << endl;
  }
  return 0;
}

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


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>


ll n, ans, s[11000];
int main() {
	cin >> n;
	REP(i, n)cin >> s[i];
	REP(i, n) {
		FOR(j, i + 1, n) {
			ans += s[i] * s[j];
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cout << pow(n,2) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1e9 + 7
#define INF 1e9
#define SENTINEL 2e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}
template <class T>
inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template <class T>
inline T GCD(T a, T b){if (b == 0) return a; else return GCD(b, a % b);}
template <class T>
inline T LCM(T a, T b) {return (a * b) / GCD(a, b);}

void ans(bool flag){
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

int main(){
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    int f=0;
    int s = 0;
    rep(i,3){
        if(a[i]==5)
            f++;
        else if(a[i]==7)
            s++;
    }
    if(f==2&&s==1){
        cout << "YES" << endl;
    
    }
    else
        cout << "NO" << endl;
}

Measured memory_bytes: 888
program divide_the_problems
  implicit none
  integer :: n, d(100000), m, i
  d = 0
  read(*,*) n
  read(*,*) d(1:n)
  call quick_sort(d(1:n))
  write(*,'(i0)') d(n/2+1)-d(n/2)
  stop
contains
  recursive subroutine quick_sort(a)
    implicit none
    integer, intent(inout) :: a(:)
    integer :: p, c
    integer :: n, l, r
    n = size(a)
    l = 1
    r = n
    p = a((l+r)/2)+a(l)+a(r)-max(a((l+r)/2),a(l),a(r))-min(a((l+r)/2),a(l),a(r))
    do
      do while (a(l).lt.p)
        l = l+1
      end do
      do while (a(r).gt.p)
        r = r-1
      end do
      if (l.ge.r) exit
      c = a(l)
      a(l) = a(r)
      a(r) = c
      l = l+1
      r = r-1
    end do
    if (l.gt.2) call quick_sort(a(1:l-1))
    if (n.gt.r+1) call quick_sort(a(r+1:n))
  end subroutine quick_sort
end program divide_the_problems

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

using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const int inf = 1e9+7;
const int mod = 1e9+7;

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

    if(n%1000==0)cout<<0<<endl;
    else{

    cout<<1000-n%1000<<endl;
    }

}


Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

long long int gcd(long long int x, long long int y) {
	if (x < y){
      return gcd(y, x);
    }
	long long int r;
	while (r = x % y) {
		x = y;
		y = r;
	}
	return y;
}

int main(void){
  long long int n,i,j;
 // cin >> n;
  long long int a[n];
  long long int x,y;

  cin >> x >> y;
  if(x==y) cout << x+y << endl;
  else if (x>y) cout << x+x-1 << endl;
  else cout << y+y-1 << endl;
  return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define EPS 1e-14

#define all(v) v.begin(),v.end()
#define INF 1<<30
#define mp make_pair
#define pb push_back

#define fi first
#define se second

#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

typedef long long ll;

void solve(){
	int n,m;
	int c[21];
	int dp[50000];
	rep(i,50000) dp[i]=-1;
	dp[0] = 0;
	cin >> n >> m;
	rep(i,m){
		cin >> c[i];
	}
	rep(i,n+1){
		int tm = 50001;
		rep(j,m){
			if(i-c[j]>=0 && dp[i-c[j]]!=-1){
				tm = min(dp[i-c[j]]+1,tm);
			}
		}
		if(tm!=50001) dp[i] = tm;
	}
	cout << dp[n] << endl;

}

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

Measured memory_bytes: 3304
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    lli n=s.length(),m=t.length();
  	s=" "+s;
  	t=" "+t;
    lli dp[n+1][m+1],i,j;
    for(i=0;i<=n;i++)
        dp[i][0]=0;
    for(i=0;i<=m;i++)
        dp[0][i]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(s[i]==t[j])
                dp[i][j]=dp[i-1][j-1]+1;
        }
    }
    string ans;
    i=n;j=m;
    while(i>0&&j>0)
    {
        if(s[i]==t[j])
        {
            ans+=s[i];
            i--;
            j--;
        }
        else if(dp[i-1][j]>=dp[i][j-1])
            i--;
        else
            j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 70656
import math

a, b = map(int, input().split())

ans = float('inf')
check = False
for i in range(1251):
    i = float(i)
    A = i * 0.08
    B = i * 0.1

    if math.floor(A) == a and math.floor(B) == b:
        ans = min(ans, i)
        check = True

if check:
    print(int(ans))
else:
    print(-1)





Measured memory_bytes: 3064
n=int(input())
h=map(int,input().split())
ans = [0]*n
pre_h = 0
for i,cur_h in enumerate(h):
    if pre_h>=cur_h:
        ans[i] = ans[i-1] + 1
    else:
        ans[i] = 0
    pre_h = cur_h
print(max(ans))

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

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//s.find(w[i])==string::npos
//findの使い方

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)

long long int n,cnt=0,ans=0,a[100000],b,c,cmp[100000],data[100000],m,h,x,y;

string s,w;

int main(void){
     cin >> n >> b;
     rep(i,n+1){
         rep(j,n+1){
             if((10000*i)+(5000*j)==b-(1000*(n-i-j))){
                 if(n-i-j>=0){
                 cout << i << " " << j << " " << n-i-j << endl;
                 return 0;
                 }
             }
         }
     }
     cout << -1 << " " << -1 << " " << -1 << endl;
return 0;
}


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

int main(){
 //erさんの提出結果をうつしました
  cin.tie(0); //cin高速化
  ios::sync_with_stdio(false); //cin高速化
  
  int a,b;
  cin >> a >> b;
  
  if(a+b==15){
    cout<<'+'<<endl;
  }else if(a*b==15){
    cout<<"*"<<endl;
  }else{
    cout<<'x'<<endl;
  }
  
  return 0;
}
    

Measured memory_bytes: 256
H,W = map(int,input().split())
L = [input() for i in range(H)]
dxy = [(-1,-1),(0,-1),(1,-1),(-1,0),(1,0),(-1,1),(0,1),(1,1)]

ANS = [[] for i in range(H)]
for y in range(H) :
    for x in range(W) :
        if L[y][x] == "#" :
            ANS[y].append("#")
        else :
            mine = 0
            for dx,dy in dxy :
                nx = x + dx
                ny = y + dy
                if (0 <= nx <= W-1) and (0 <= ny <= H-1) :
                    if L[ny][nx] == "#" :
                        mine += 1
            ANS[y].append(str(mine))
for i in range(H) :
    ans = "".join(ANS[i])
    print(ans)
    

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5e3 + 5;

int P[maxn], C[maxn];
ll score[maxn];
int vis[maxn];
int main()
{
    int n;
    ll k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> P[i];
    for (int i = 1; i <= n; ++i) cin >> C[i];
    ll ans = -(1LL << 62);
    for (int i = 1; i <= n; ++i){
        ll now = 0, cur = -(1LL << 62);
        int p = i, tk = k, cnt = 0;
        vis[i] = 1;
        while (tk && vis[p] != 2){
            p = P[p];
            ++vis[p];
            now += C[p];
            score[++cnt] = now;
            cur = max(cur, now);
            --tk;
        }
        memset(vis, 0, sizeof(vis));
        ans = max(ans, cur);
        if (tk == 0) continue;
        if (now > 0){
            ll ci = tk / cnt;
            if (ci > 0) ans = max(ans, now + (ci - 1) * now + cur);
            now += ci * now;
            ans = max(ans, now);
            tk -= ci * cnt;
            ll mx = -(1LL << 62);
            for (int i = 1; i <= tk; ++i) mx = max(mx, score[i]);
            now += mx;
            ans = max(ans, now);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
#define mp(a,b)   make_pair(a,b)
#define ll        long long
#define mp(a,b)   make_pair(a,b)
#define si(n)     scanf("%d",&n)
#define sl(n)     scanf("%lld",&n)
#define pi(n)     printf("%d\n",n)
#define pl(n)     printf("%lld\n",n)
#define           newline cout << endl;
#define           ff first
#define           ss second
using namespace std;

int main(){
  //clock_t tStart = clock();
  int n,m;
  cin >> n >> m;
  char arr[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin >> arr[i][j];
    }
  }
  bool check[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++) check[i][j]=1;
  }
  for(int i=0;i<n;i++){
    bool f = 0;
    for(int j=0;j<m;j++){
      if(arr[i][j]=='#') f=1;
    }
    if(!f){
      for(int j=0;j<m;j++){
        check[i][j]=0;
      }
    }
  }
  for(int j=0;j<m;j++){
    bool f = 0;
    for(int i=0;i<n;i++){
      if(arr[i][j]=='#') f=1;
    }
    if(!f){
      for(int i=0;i<n;i++){
        check[i][j]=0;
      }
    }
  }
  for(int i=0;i<n;i++){
    int cnt =  0;
    for(int j=0;j<m;j++){
      if(check[i][j]) cnt++;
    }
    if(cnt>=1){
      for(int j=0;j<m;j++){
        if(check[i][j]) cout << arr[i][j];
      }
      newline
    }
  } newline
  //printf("Time taken: %.2fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<malloc.h>
#include<math.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N;
int sum[200200];
map<int, int> mp;

signed main(){
    cin >> N;
    int ans = 0;
    mp[0] = 1;
    for(int i = 1; i <= N; i++){
        cin >> sum[i];
        sum[i] += sum[i - 1];
        //printf("%lld %lld\n", i, sum[i]);
        ans += mp[sum[i]];
        mp[sum[i]]++;
    }
    cout << ans << endl;


    return 0;
}

/*

*/

Measured memory_bytes: 14336
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>

using namespace std;

using P = pair<int, int>;
using i64 = int64_t;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;

int main(int argc, char **argv) {
    int k, x;
    cin >> k >> x;

    for (int i = x-k+1; i< x+k; ++i) {
        if (-1000001<i && i < 1000001) {
            cout << i << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 256
program main;
var
    i,j,k:integer;
    req:real;
    sum,n,m:integer;
    arr:array[1..10000] of integer;
begin
    readln(n,m);
    sum:=0;
    for i:=1 to n do begin
        read(arr[i]);
        sum:=sum+arr[i];
    end;
    req:=sum/4/m;
    for i:=1 to n do if (arr[i]>=req) then m:=m-1;
    if (m<=0) then writeln('Yes') else writeln('No');
end.

Measured memory_bytes: 1320
n = int(input())
h = list(map(int, input().split()))

maxcount = 0
nowcount = 0

for i in range(n - 1):
    if h[i + 1] <= h[i]:
        nowcount = nowcount + 1
        if maxcount < nowcount:
            maxcount = nowcount
    else:
        nowcount = 0

print(maxcount)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n; long long k; cin >>n >>k;
  int r1,r2,r3,t; bool shit=0;
  set<int>s; vector<int>v(n); vector<int>r(n);
  for(int i=0; i<n; i++) cin >>v[i];
  for(int i=0; i<n; i++){
    if(i) t=v[t-1];
    else t=v[0];
    s.insert(t);
    if(s.size()==i){r1=i; r2=t; shit=1; break;}
    r[i]=t;
  }
  if(shit) for(int i=0; i<n; i++) if(r[i]==r2) r3=i;
  if(!shit)
  {
    if(k%n) cout <<r[k%n-1];
    else cout <<r[n-1];
    return 0;
  }
  if(k<=r3) cout <<r[k-1];
  else cout <<r[(k-r3-1)%(r1-r3)+r3];
return 0;}

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

int main(){
	int tmp_max[2]={-1,-1};
	int n;	
	cin >> n;

	int* a=new int[n];
	cin >> a[0] >> a[1];
	tmp_max[0] = max(a[0],a[1]);
	tmp_max[1] = min(a[0],a[1]);
	
	for(int i=2; i<n;i++){
		cin >> a[i];
		if(a[i] >= tmp_max[0]){
			tmp_max[1] = tmp_max[0];
			tmp_max[0] = a[i];
		}else if(a[i] >= tmp_max[1]){
			tmp_max[1] = a[i];
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==tmp_max[0]){
			cout << tmp_max[1] << endl;
		}else{
			cout << tmp_max[0] << endl;
		}
	}
	return 0;
}
	


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

typedef long long ll;
typedef int64_t i6;
typedef std::vector<std::vector<int64_t> > Graph;

#define rep(i, n) for (int64_t i = 0; i < n; ++i)
#define rep2(i, n) for (int64_t i = 1; i <= n; ++i)
#define repb(i, l, n) for (int64_t i = l; i < n; ++i)
#define repb2(i, l, n) for (int64_t i = l; i <= n; ++i)
#define repe(a, b) for (auto&(a) : (b))
#define ALL(v) (v).begin(), (v).end()
#define Sort(x) sort(ALL(x))
#define Sort_rev(x) Sort(x);reverse(ALL(x))
#define mp(a, b) make_pair((a), (b))
#define Push_back(a, b) push_back( mp( (a), (b) ) )

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;  } return 0;  }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;  } return 0;  }
template<typename V,typename T> bool find_num(V v, T num) { if ( find(ALL(v), num) == v.end() ) { return false; } return true; }

const int inf = 0x3fffffff;
const int64_t INF = 0x3fffffffffffffff;
const int64_t MOD = 1e9+7;

int main() {
    int64_t n;
    cin >> n;
    cout << !n << endl;
    return 0;
}


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

int main() {
	int a,b,c,n=0;
	
	cin>>a>>b>>c;
	
	for(int i=a;i<=b;++i){
		if(c%i);else++n;
	}
	
	cout<<n<<endl;
	
	return 0;
}

Measured memory_bytes: 1164
def main():
    n = int(input())
    v = [int(i) for i in input().split()]
    c = [int(j) for j in input().split()]
    
    x = 0
    y = 0
    for idx in range(n):
        if v[idx] > c[idx]:
            x += v[idx]
            y += c[idx]
    
    print(x-y)

main()


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline

N = int(input())
b = [list(map(int, input().split())) for _ in range(N)]
b.sort(key = lambda x: (x[0], x[1]))
vis = set()
viss = set()
res = 0
def dfs(n, p, q):
  global vis
  global viss
  res = 0
  vis.add(n)
  viss.add(n)
  for k in range(N):
    if k in vis: continue
    if k in viss: continue
    if (b[k][0] == b[n][0] + p) and (b[k][1] == b[n][1] + q):
      res = max(res, dfs(k, p, q))
  vis.discard(n)
  return res + 1
for i in range(N):
  for j in range(N):
    vis = set()
    viss = set()
    p = b[j][0] - b[i][0]
    q = b[j][1] - b[i][1]
    temp = 0
    for n in range(N):
      if n in viss: continue
      t = dfs(n, p, q)
      if t > 1:
        temp += t - 1
    res = max(temp, res)
    #print(temp, p, q)
print(N - res)

Measured memory_bytes: 51804
#include<bits/stdc++.h>
using namespace std;
int t;
void S(){puts("No");exit(0);}
int main()
{
	cin>>t;
	while(t--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a-=b+c;
		if(a<0)S();
		if(a&1)S();
	}
	puts("Yes");
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn],n,k;
int dp[maxn];		//dp[i]´ú±í´Ó0µ½iËùÐèµÄ²½Êý

int main() {
	cin>>n>>k;
	for(int i = 1 ;i <= n;i++) cin>>a[i];
	
	dp[1] = 0;
	dp[2] = abs(a[1] - a[2]);
	for(int i = 3;i <= n;i++) {
		dp[i] = 1e9+10;
		for(int j = 1;j <= k;j++) {		//Ã¶¾ÙÃ¿Ò»²½ 
			if( i-j >= 1) {		//
				dp[i] = min(dp[i],dp[i-j] + abs(a[i-j] - a[i]));
			} else 
				break;
		}
	}
	cout<<dp[n];
	return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

vector<long long> v;

int main(void)
{
    long long a, b, c;
    long long i, j, o;

    cin >> a >> b;
    c = __gcd(a, b);
    for(i = 1; i * i <= c; i ++)
        if(!(c % i))
        {
            v.push_back(i);
            if(i * i != c)
                v.push_back(c / i);
        }

    sort(v.begin(), v.end());
    for(i = 0, o = v.size(); i < (signed)v.size(); i ++)
    {
        for(j = 0; j < i; j ++)
            if(__gcd(v.at(i), v.at(j)) != 1)
                break;
        o -= j != i;
    }
    cout << o << endl;

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#define N 500000

void merge(int *,int,int,int);
void mergeSort(int *,int,int);

int cnt;

int main()
{
  int n,i,S[N];

  scanf("%d",&n);
  if(n>N) exit(1);
  for(i=0;i<n;i++){
    scanf(" %d",&S[i]);
    if(S[i]<0 || S[i]>1000000000) exit(2);
  }

  mergeSort(&S[0],0,n);
  
  for(i=0;i<n;i++){
    printf("%d",S[i]);
    if(i != n-1) printf(" ");
  }
  printf("\n");

  printf("%d\n",cnt);
  
  return 0;
}
  
void merge(int *S,int l,int m,int r)
{
  int n1,n2,i,L[N],R[N],j=0,k=0;

  n1 = m-l;
  n2 = r-m;

  //printf("確認 n1:%d , n2:%d\n",n1,n2);

  for(i=0;i<n1;i++) L[i] = S[l+i];
  for(i=0;i<n2;i++) R[i] = S[m+i];
  L[n1] = 999999999;
  R[n2] = 999999999;

  for(i=l;i<r;i++){
    cnt++;
    if(L[j]<=R[k]){
      S[i] = L[j];
      j += 1;
    }
    else{
      S[i] = R[k];
      k += 1;
    }
  }
}
void mergeSort(int *S,int l,int r)
{
  int m;
  
  if(l+1 < r){
    m = (l+r)/2;
    mergeSort(S,l,m);
    mergeSort(S,m,r);
    merge(S,l,m,r);
  }
}



Measured memory_bytes: 5632
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

pair<int, Edges> prim(Graph g)
{
	vector<bool> used(g.size());
	Edges res;
	int sum = 0;

	priority_queue<Edge, vector<Edge>, greater<Edge>> que;
	que.push(Edge{ -1, 0, 0 });

	while (!que.empty())
	{
		Edge e = que.top(); que.pop();
		if (used[e.to]) continue;
		if (e.from >= 0) res.push_back(e);
		sum += e.cost;
		used[e.to] = true;
		for (Edge i : g[e.to])
		{
			if (!used[i.to]) que.push(i);
		}
	}
	return make_pair(sum, res);
}

int main()
{
	int n, m;
	while (cin >> n >> m, n)
	{
		Graph g(n);
		REP(i, m)
		{
			int s, t, c; cin >> s >> t >> c;
			s--; t--;
			add_edge(g, s, t, c);
			add_edge(g, t, s, c);
		}
		Edges es = prim(g).second;
		sort(ALL(es));
		cout << es[n / 2 - 1].cost << endl;
	}
	return 0;
}

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

int main(){
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    vector<int> cnt;
    cnt.push_back(0);
    char prev = '1';
    for(int i=0;i<n;++i){
        if(s[i] == prev) ++cnt.back();
        else{
            prev = s[i];
            cnt.push_back(1);
        }
    }
    if(prev == '0') cnt.push_back(0);

    int ans = 0, cur = 0;
    if(cnt.size() <= 2*k+1){
        for(int x: cnt) ans += x;
        cout << ans << endl;
        return 0;
    }
    for(int i=0;i<2*k+1;++i) cur += cnt[i];
    ans = cur;
    for(int j=2;j+2*k<cnt.size();j+=2){
        cur -= cnt[j-1] + cnt[j-2];
        cur += cnt[j+2*k-1] + cnt[j+2*k];
        ans = max(ans, cur);
    }
    cout << ans << endl;

    return 0;
}

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

int main() {
    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    double half = (double) W * H / 2;
    bool can = false;
    if (W % 2 == 0 && H % 2 == 0){
        if (x == W/2 && y == H/2) can = true;
    }

    cout << fixed << setprecision(12);
    if (can) cout << half << " " << 1 << endl;
    else cout << half << " " << 0 << endl;
}

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

int main()
{
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int k;
    bool f = true;
    int mi = 124;
    int ma = 0;
    vector<int> antena(5);
    for(int i = 0; i < 5; i++){
        int a;
        cin >> a;
        if(a < mi) mi = a;
        if(a > ma) ma = a;
    }
    cin >> k;
    f = ma-mi <= k;
    cout << (f ? "Yay!" : ":(") << endl;
    return 0;
}


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

int f[10000010];

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void write(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

inline void writeln(int x){
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
     puts("");
}

signed main(){
    int n=read();
    
    int i,j;    
    int ans=0;
    
    for(i=1;i<=n;i++){
        for(j=1;i*j<=n;j++)
            f[i*j]++;
    }
    
    for(i=1;i<=n;i++)
        ans+=i*f[i];
    
    writeln(ans);
    return 0;
}

Measured memory_bytes: 81736
t,x,y = 0,0,0
gets.to_i.times do
  a,b,c = gets.split.map(&:to_i)
  if (a-t)%2 != (b+c-x-y)%2 || a-t < (b-x).abs+(c-y).abs
    puts "No"
    exit
  end
end
puts "Yes"

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const long long INF = 1e18;
const int num[10] = {
	1000000000, 2, 5, 5, 4, 5, 6, 3, 7, 6
};

int main(){
	int N, M;
	cin >> N >> M;
	int A[M];
	for (int i = 0; i < M; i++){
		cin >> A[i];
	}
	sort(A, A + M, greater<int>());

	long long dp[N + 1] = {0};
	for (int i = 1; i <= N; i++){
		dp[i] = -INF;
		for (int j = 0; j < M; j++){
			if(i-num[A[j]] >= 0){
				dp[i] = max(dp[i], dp[i - num[A[j]]] + 1);
			}
		}
	}

	while (N > 0){
		for (int i = 0; i < M; i++){
			if (dp[N - num[A[i]]] == dp[N] - 1 && N - num[A[i]] >= 0){
				N -= num[A[i]];
				cout << A[i];
				break;
			}
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
using namespace std;

int main(){
    int n,k ;
    cin >> n >> k ;
    int q ;
    vector<double> p(n) ;
    for (size_t i = 0; i < n; i++)
    {
        cin >> q ;
        p.at(i) = (q+1) / 2.0 ;
    }
    double now = 0 ;
    for (size_t i = 0; i < k; i++)
    {
        now += p.at(i) ;
    }
    
    double ans = now ;

    for (size_t i = 0; i < n-k; i++)
    {
        now -= p.at(i) ;
        now += p.at(i+k) ;
        if (now > ans)
        {
            ans = now ;
        }
        
    }
    cout << fixed << setprecision(10) << ans << endl ;
}    

Measured memory_bytes: 1792
N, A, B = map(int, input().split())
ans = 0
for i in range(1, N + 1):
    str_i = str(i)
    digit_sum = 0
    for j in range(len(str_i)):
        digit_sum += int(str_i[j])
    if A <= digit_sum and digit_sum <= B:
        ans += i
print(ans)

Measured memory_bytes: 3064
#include <atcoder/all>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;
using namespace atcoder;

int mx(int a, int b) {
    return max(a, b);
}
int mn(int a, int b) {
    return min(a, b);
}

int INF() {
    return numeric_limits<int>::min();
}
int INF2() {
    return numeric_limits<int>::max();
}

int target;
bool f(int v) {
    return v < target;
}
bool g(int v) {
    return v > target;
}

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

    vector<int> X(N), Y(N), idx_x(N), idx_y(N);
    for(int i=0; i<N; i++) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        X[y] = x;
        Y[x] = y;
        idx_x[x] = i;
        idx_y[y] = i;
    }

    segtree<int, mx, INF> seg_x(Y), seg_y(X);
    segtree<int, mn, INF2> seg_x2(Y), seg_y2(X);
    dsu uf(N);

    for(int i=0; i<N; i++) {
        target = seg_x.get(i);
        // cerr << target << endl;
        int tmp = seg_x.max_right<f>(i+1);
        // cerr << tmp << endl;
        if(tmp == N) continue;
        uf.merge(idx_x[i], idx_x[tmp]);
    }

    for(int i=0; i<N; i++) {
        target = seg_y.get(i);
        // cerr << target << endl;
        int tmp = seg_y.max_right<f>(i+1);
        // cerr << tmp << endl;
        if(tmp == N) continue;
        uf.merge(idx_y[i], idx_y[tmp]);
    }

    for(int i=N-1; i; i--) {
        target = seg_x2.get(i);
        // cerr << target << endl;
        int tmp = seg_x2.min_left<g>(i-1);
        // cerr << tmp << endl;
        if(tmp == 0) continue;
        uf.merge(idx_x[i], idx_x[tmp]);
    }

    for(int i=N-1; i; i--) {
        target = seg_y2.get(i);
        // cerr << target << endl;
        int tmp = seg_y2.min_left<g>(i-1);
        // cerr << tmp << endl;
        if(tmp == 0) continue;
        uf.merge(idx_y[i], idx_y[tmp]);
    }

    // vector< tuple<int,int,int> > v(N);
    // for(int i=0; i<N; i++) {
    //     int x, y;
    //     cin >> x >> y;
    //     --x; --y;
    //     v[i] = make_tuple(i, x, y);
    // }


    // sort(v.begin(), v.end(), [](auto &lhs, auto &rhs) {return get<1>(lhs) < get<1>(rhs);});
    // for(int i=0; i<N-1; i++) {
    //     if(get<2>(v[i]) < get<2>(v[i+1])) {
    //         uf.merge(get<0>(v[i]), get<0>(v[i+1]));
    //     }
    // }

    // sort(v.begin(), v.end(), [](auto &lhs, auto &rhs) {return get<2>(lhs) < get<2>(rhs);});
    // for(int i=0; i<N-1; i++) {
    //     if(get<1>(v[i]) < get<1>(v[i+1])) {
    //         uf.merge(get<0>(v[i]), get<0>(v[i+1]));
    //     }
    // }

    for(int i=0; i<N; i++) {
        cout << uf.size(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 15380
MODE = "stdio"
#require 'matrix'
#include Math
line = Array.new

if(defined? MODE)
  line = STDIN.read.split("\n")
else
  tmp = '12
  11
  1
  4
  5
  5
  7
  8
  3
  2
  8
  3
  2'.split("\n")
  tmp.each{|s|
    line << s.strip
  }
end

n = line[0].to_i
arr=[]
(1..n).each do |num|
  arr << line[num].to_i
end

def insertion_sort(a, n, g)
  cnt = 0
  (g..n-1).each do |i|
    v = a[i]
    j = i - g
    while j >= 0 && a[j] > v
      a[j+g] = a[j]
      j = j - g
      cnt+=1
    end
    a[j+g] = v
  end
  return cnt
end
 
 
g = [1]
cnt = 0
while (i = 2 * g[0] + 1) < n do
 g.unshift(i)
end

g.each do |i|
 cnt += insertion_sort(arr, n, i)
end
 
puts g.size
puts g.join(" ")
puts cnt
puts arr

Measured memory_bytes: 108644
#include<stdio.h>
#include<string.h>
#include<set>
#include<map>
using namespace std;
int main(){
  while(1){
    int n, max = 0;
    int points[3000][2];
    set<pair<int, int> > fields;

    scanf("%d", &n);
    if(n == 0){
      return 0;
    }
    for(int i = 0;i < n;i++){
      int xi, yi;
      scanf("%d%d", &xi, &yi);
      points[i][0] = xi;
      points[i][1] = yi;
      fields.insert(make_pair(xi, yi));
    }
    
    for(int i = 0;i < n;i++){
      for(int j = 0;j < n;j++){
	if(i == j)continue;
	int xdis = points[i][0] - points[j][0];
	int ydis = points[i][1] - points[j][1];
	if(points[j][0] + ydis < 0 || points[j][0] + ydis > 5000)continue;
	if(points[j][1] - xdis < 0 || points[j][1] - xdis > 5000)continue;
	if(points[i][0] + ydis < 0 || points[i][0] + ydis > 5000)continue;
	if(points[i][1] - xdis < 0 || points[i][1] - xdis > 5000)continue;
	if(fields.find(make_pair(points[j][0] + ydis, points[j][1] - xdis)) == fields.end())continue;
	if(fields.find(make_pair(points[i][0] + ydis, points[i][1] - xdis)) == fields.end())continue;
	if(max < xdis * xdis + ydis * ydis){
	  max = xdis * xdis + ydis * ydis;
	}
      }
    }
    printf("%d\n", max);
  }
}

Measured memory_bytes: 1180
use std::collections::BTreeMap;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let s: Vec<char> = read::<String>().chars().collect();
    let t: Vec<char> = read::<String>().chars().collect();

    let mut s_t = BTreeMap::new();
    let mut t_s = BTreeMap::new();
    for (&s_i, &t_i) in s.iter().zip(t.iter()) {
        match s_t.get(&s_i) {
            Some(&v) => {
                if v != t_i {
                    println!("No");
                    return;
                }
            }
            None => (),
        }
        s_t.insert(s_i, t_i);

        match t_s.get(&t_i) {
            Some(&v) => {
                if v != s_i {
                    println!("No");
                    return;
                }
            }
            None => (),
        }
        t_s.insert(t_i, s_i);
    }

    println!("Yes");
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}
ll gcd(ll x,ll y){
  if(x>y)swap(x,y);
  if(y%x==0)return x;
  return gcd(y%x,x);
}


int main() {
  ll n;cin >> n;
  vl a(n);
  ll ans;
  rep(i,n){
    cin >> a[i];
    if(i==0)ans=a[i];
    else ans=gcd(ans,a[i]);
  }
  cout << ans << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

ll n;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n && n){
        vector<ll> l(n);
        vector<ll> mask(n,0);
        vector<vector<ll>> dp(2,vector<ll>(1LL << 16,-1));
        dp[0][0] = 0;
        rep(i,n){
            ll m;
            cin >> m >> l[i];
            rep(j,m){
                ll s,T;
                cin >> s >> T;
                s-=6; T-=6;
                FOR(k,s,T)mask[i] |= (1LL << k);
            }
        }
        rep(i,n){
            rep(j,1LL << 16){
                dp[(i+1)%2][j] = max(dp[i%2][j],dp[(i+1)%2][j]);
                if(mask[i] & j)continue;
                if(dp[i%2][j] == -1)continue;
                ll nxt = j | mask[i];
                dp[(i+1)%2][nxt] = max(dp[i%2][j]+l[i],dp[(i+1)%2][nxt]);
            }
        }
        ll ans = 0;
        rep(i,1LL << 16)ans = max(ans,dp[n%2][i]);
        cout << ans << endl;
    }
}


Measured memory_bytes: 4344
#include <iostream>

using namespace std;

int main() {
	string A, B;

	cin >> A >> B;
	if(A.size() > B.size()) {
		cout << "GREATER" << endl;
	} else if(A.size() < B.size()) {
		cout << "LESS" << endl;
	} else {
		bool flag = false;
		for(int i = 0; i < A.size(); i++) {
			if(A[i] > B[i]) {
				cout << "GREATER" << endl;
				flag = true;
				break;
			} else if(A[i] < B[i]) {
				cout << "LESS" << endl;
				flag = true;
				break;
			}
		}
		if(flag == false) {
			cout << "EQUAL" << endl;
		}
	}


	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(h, n, t)
{
    scanf("%d%d", &h, &n);
    while(n-- && h>0)
    {
        scanf("%d", &t);
        h-=t;
    }

    printf("%s\n", (h<=0)?"Yes":"No");

    return 0;
}

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

string s, t;
int n, m;
const int R = 256;
const int INF = 1e9;
vector<vector<int>> dfa;
vector<int> match;
vector<int> L;

void kmp() {
  dfa.resize(R, vector<int>(m+1));
  dfa[t[0]][0] = 1;
  for(int x = 0, j = 1; j <= m; j++) {
    for(int c = 0; c < R; c++) {
      dfa[c][j] = dfa[c][x];
    }
    dfa[t[j]][j] = (j+1)%(m+1);
    x = dfa[t[j]][x];
  }
}

int pathLength(int s, int i, int d) {
  if(d != 0 && s == i) return INF;
  if(!match[i]) return d;
  if(L[i] != -1) return d + L[i];

  return L[i] = pathLength(s, (i+m)%n, d+1);
}

int main () {
  cin >> s >> t;
  n = s.size(), m = t.size();
  match.resize(n);
  L.resize(n, -1);

  kmp();
  for(int i = 0, j = 0; i < n + m - 1; i++) {
    j = dfa[s[i%n]][j];
    if(j == m) match[i-m+1] = 1;
  }

  int ans = 0;
  rep(i,n) {
    if(match[i]) ans = max(ans, pathLength(i, i, 0));
  }

  cout << (ans == INF ? -1 : ans) << endl;

  return 0;
}


Measured memory_bytes: 513892
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

ll n , a , b;

int main(){
    cin >> n >> a >> b;
    if(a != b && n == 1) cout << 0 << endl;
    else if(a > b) cout << 0 << endl;
    else cout << b * (n - 1) + a - (a * (n - 1) + b) + 1 << endl;
    return 0;
}


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

int main(){
  ll n,y; cin >>n >>y;
  rep(i,n+1){
    rep(j,n-i+1){
      int k = n-i-j;
      if(10000*i+5000*j+1000*k==y){
        cout << i << " " << j << " " << k << endl;
        return 0;
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << endl;
  return 0; 
}

Measured memory_bytes: 3608
#include<iostream>
#include<vector>
using namespace std;
const int MAX = 1000000;
int cnt;
int A[MAX];
vector<int> step;
void InsertionSort(int A[], int n, int step)
{
	for (int i = step; i <= n - 1; i++)
	{
		int key = A[i];
		int j = i - step;
		while (j >= 0 && A[j] > key)
		{
			A[j + step] = A[j];
			j -= step;
			cnt++;
		}
		A[j + step] = key;
	}
}
void shellSort(int A[], int n)
{
	cnt = 0;
	int h = 1;
	while (true)
	{
		if (h > n)
			break;
		step.push_back(h);
		h = 3 * h + 1;
	}
	for (int i = step.size() - 1; i >= 0; i--)
		InsertionSort(A, n, step[i]);
	cout << step.size() << endl;
	for (int i = step.size() - 1; i >= 0; i--)
		if (i != 0)
			cout << step[i] << " ";
		else
			cout << step[i] << endl;
	cout << cnt << endl;
	for (int i = 0; i < n; i++)
		cout << A[i] << endl;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> A[i];
	shellSort(A, n);
}


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

int main() {
     int A,B;
     cin >> A >> B ;
      if(A>=13){
        cout << B << endl;
      }
      else if(A>=6 && A<=12){
        cout << B/2 << endl;
      }
      else{
        cout << 0 << endl;
      }
return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second

int n, m, a[50], b[50];
vector<int> es[50];

bool ved[50];

bool solve(int s, int t, int x, int y) {
	if (s == t) return true;
	if (ved[s]) return false;
	ved[s] = true;
	REP(i, es[s].size()) if ((s != x || es[s][i] != y) && (s != y || es[s][i] != x) && solve(es[s][i], t, x, y)) return true;
	return false;
}
 
int main(int argc, char **argv) {
	cin >> n >> m;
	REP(i, m) {
		cin >> a[i] >> b[i];
		--a[i]; --b[i];
		es[a[i]].push_back(b[i]);
		es[b[i]].push_back(a[i]);
	}
	int res = 0;
	REP(i, m) {
		CLEAR(ved);
		if (!solve(a[i], b[i], a[i], b[i])) ++res;
	}
	cout << res << endl;
	return 0;
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	size_t pos = 0;
	while (pos < s.length()) {
		pos = s.find("ST", pos);
		if (pos == string::npos) break;
		s.erase(pos, 2);
		if (pos > 0) -- pos;
	}
	cout << s.length() << endl;
}


Measured memory_bytes: 640