akhauriyash/Code-Regression huggingface dataset:
import heapq
def A():
    H, W = map(int, input().split())
    maze = []
    for i in range(H):
        maze.append(input())
    # if maze[0][0] == '.':
    #     q = [[0, (0, 0)]]
    # else:
    #     q = [[1, (0, 0)]]
    # heapq.heapify(q)
    # while q:
    #     #print(q)
    #     cost, cur = heapq.heappop(q)
    #     if cur[0] == H-1 and cur[1] == W-1:
    #         print(cost)
    #         return
    #     for direction in [(0, 1), (1, 0)]:
    #         new_r, new_c = cur[0]+direction[0], cur[1]+direction[1]
    #         if new_r >= 0 and new_c >= 0 and new_r < H and new_c < W:
    #             if maze[new_r][new_c]=='.':
    #                 heapq.heappush(q, [cost, (new_r, new_c)])
    #             else:
    #                 heapq.heappush(q, [cost+1, (new_r, new_c)])
    memo = [[float('inf') for i in range(W)] for j in range(H)]
    # if maze[H-1][W-1] == '.':
    #     memo[H-1][W-1] = 0
    # else:
    #     memo[H-1][W-1] = 1
    # def dfs(r, c, prev_flipped):
    #     if memo[r][c] < float('inf'):
    #         return memo[r][c]
    #     cur_flipped = False
    #     if maze[r][c] == '.':
    #         cur_cost = 0
    #     else:
    #         if prev_flipped:
    #             cur_cost = 0
    #         else:
    #             cur_cost = 1
    #         cur_flipped = True
    #     minimum_next = float('inf')
    #     if r+1 < H:
    #         minimum_next = dfs(r+1, c, cur_flipped)
    #     if c+1 < W:
    #         minimum_next = min(minimum_next, dfs(r, c+1, cur_flipped))
    #     res = cur_cost+minimum_next
    #     memo[r][c] = res
    #     return res
    # print(dfs(0, 0, False))
    if maze[0][0] == '.':
        memo[0][0] = 0
    else:
        memo[0][0] = 1
    for i in range(H):
        for j in range(W):
            for r, c in [(i+1, j), (i, j+1)]:
                if r<H and c<W:
                    if maze[i][j] == '.' and maze[r][c] == '#':
                        temp = 1
                    else:
                        temp = 0
                    memo[r][c] = min(memo[r][c], memo[i][j]+temp)
    print(memo[-1][-1])

A()

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

int main()
{

    //  #ifndef oj
    //freopen("in", "r", stdin);
    //freopen("out.txt","w",stdout);
    //#endif
    // system("cls");
    //getchar();

    int n;
    cin>>n;
    string s1,s2;
    cin>>s1>>s2;
    for(int i=0;i<n;i++)
    {
        cout<<s1[i]<<s2[i];
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define INF 2100000000
#define INVALID -1
using namespace std;
int absint(int a)
{
	return max(a , - a);
}
int main()
{
	int n, p[110], a, b;
	int i, j, k,an=0,bn=0,cn=0;
	cin >> n >> a >> b;
	for (i = 1; i <= n; i++)
	{
		cin >> p[i];
		if (p[i] <= a) an++;
		else if (a + 1 <= p[i] && p[i] <= b) bn++;
		else cn++;
	}
	cout << min(an, min(bn, cn)) << endl;
}

Measured memory_bytes: 256
n,q = map(int,input().split())
c = tuple(map(int,input().split()))
qs = [[] for _ in range(n)]
for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  qs[l].append((r,i))

class BIT:
    def __init__(self,n):
        self.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n+1)]
for i in range(n):
  l = pi[c[i]]
  if l != -1:
    ps[l] = i
  pi[c[i]] = i
    
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n-1,-1,-1):
  if ps[x] != -1:
    d.add(ps[x],1)
  for r,i in qs[x]:
    ans[i] = (r-x+1)-d.sum(r)

for i in range(q):
  print(ans[i])


Measured memory_bytes: 223224
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;  
#define ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 998244353
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i));}
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
ll power(ll a,ll n)
{
    ll p;
    if(n==0)
    {
        return 1;
    }
    p=power(a,n/2);
    p=(p%mod*p%mod)%mod;
    if(n%2==1)
    {
        p=(p%mod*a%mod)%mod;
    }
    return p;
}
int main()
{
    fastIO;
    ll n;
    cin>>n;
    vector<ll>v(n);
    map<ll,ll>m;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        m[v[i]]++;
    }
    ll ans=0,x,y,val,val1;
    for(auto itr=m.begin();itr!=m.end();itr++)
    {
        x=itr->se;
        val=(x*(x-1))/2;
        ans+=val;
    }
    for(int i=0;i<n;i++)
    {
        x=v[i];
        y=m[x];
        val=(y*(y-1))/2;
        y--;
        if(y<=0)
        {
            val1=0;
        }
        else
        {
            val1=((y-1)*y)/2;
        }
        cout<<ans-val+val1<<endl;
    }
    
}

Measured memory_bytes: 11136
#include "bits/stdc++.h"
using namespace std;
int main()
{
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.length(); ++i)
    {
        s = s[s.length() - 1] + s;
        s.pop_back();
        if (s == t)
        {
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int sum = (h2*60+m2)-(h1*60+m1);
    cout << sum-k << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> cnt(M, 0);
  for (int i = 0; i < N; ++i)
  {
    int K;
    cin >> K;
    for (int j = 0; j < K; ++j)
    {
      int A;
      cin >> A;
      --A;
      ++cnt[A];
    }
  }
  int ans = 0;
  for (int i = 0; i < M; ++i)
  {
    if (cnt[i] == N)
    {
      ++ans;
    }
  }
  cout << ans << endl;
}


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

using namespace std;
typedef long long ll;




int main()
{
    int A,B;
    cin >> A >> B;
    if(A <= 9 && B <= 9) cout << A*B << endl;
    else cout << -1 << endl;
    
    
    
    
    return 0;
}


Measured memory_bytes: 256
import Data.List

split' :: [Int]	-> [[Int]]
split' (x:xs)
  | x == 0 = []
  | otherwise =	take x xs : split' (drop x xs)

solve :: [Int] -> String
solve = show . maximum . map (maximum . scanl1 (+)) . init . tails

main = getContents >>= putStr . unlines . map solve . split' . map read . lines

Measured memory_bytes: 5968
/* ex3_4
        fmuacshai */
 
#include<stdio.h>
 
int main(void){
    //整数number、割る数div_number、商quotient
    int number,div_number,quotient;
    //numberの入力
    scanf("%d",&number);
    //div_numberの初期設定
    div_number=9;
    //余りが出なくなるまで計算
    while(number%div_number>0){
        div_number=div_number-1;
    }
    //quotientの計算
    quotient=number/div_number;
    //quotientが10未満ならYes、10以上ならNoと出力
    if(quotient<10){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<pair<int,int> > arr;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		arr.push_back({x,i+1});
	}
	sort(arr.begin(),arr.end());
	for(int i=0;i<n;i++)
	{
		cout<<arr[i].second<<" ";
	}
	cout<<endl;
}

Measured memory_bytes: 1780
class Unionfind():  # Unionfind
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

    def find(self, x):  # グループの根
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # グループの併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def groups(self):  # 全てのグループごとの要素
        members_dict = {i: set() for i, x in enumerate(self.parents) if x < 0}
        for i in range(self.N):
            members_dict[self.find(i)].add(i)
        return members_dict


n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.groups().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)


Measured memory_bytes: 121644
using System;

namespace _042b
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] NL = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            string[] S = new string[NL[0]];
            for(int i = 0; i < S.Length; i ++){
                S[i] = Console.ReadLine();
            }
            Array.Sort(S);
            var str = string.Join("",S);
            Console.WriteLine(str);
        }
    }
}

Measured memory_bytes: 13408
import queue
INF = 10**8

def bfs():
    q = queue.Queue()
    q.put((sx, sy))
    d[sx][sy] = 0

    while q.empty() == False:
        now = q.get()
        if now[0] == gx and now[1] == gy:
            break

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and d[nx][ny] == INF:
                q.put((nx, ny))
                d[nx][ny] = d[now[0]][now[1]] + 1

h, w = map(int, input().split())
count = 0
s = [[] for i in range(h)]
for i in range(h):
    s[i] = list(input())
    for j in range(w):
        if s[i][j] == "#":
            count += 1

sx, sy = 0, 0
gx, gy = h - 1, w - 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
d = [[INF]*w for i in range(h)]

bfs()
if d[gx][gy] == INF:
    print(-1)
else:
    ans = h * w - (d[gx][gy] + 1 + count)
    print(ans)


Measured memory_bytes: 44776
import java.util.Scanner

import scala.collection.mutable.{ArrayBuffer, Map => MMap, Queue => MQueue}

object Main extends App
{
	val sc = new Scanner(System.in)
	val n,m = sc.nextInt()
	
	val adj = ArrayBuffer.fill(n)(List.empty[Int])
	(1 to m).foreach { _ =>
		val from, to = sc.nextInt()
		adj(from - 1) ::= to - 1
		adj(to - 1) ::= from - 1
	}
	
	val resultPreMap = calc()
	println("Yes")
	(1 until n).foreach(node => println(resultPreMap(node) + 1))
	
	private def calc(queue: MQueue[Int] = MQueue(0), preMap: MMap[Int, Int] = MMap(0 -> 0)): MMap[Int, Int] =
	{
		while (queue.nonEmpty) {
			val node = queue.dequeue()
			for (nextNode <- adj(node) if !preMap.contains(nextNode)) {
				queue += nextNode
				preMap += Tuple2(nextNode, node)
			}
		}
		preMap
	}
}

Measured memory_bytes: 93448
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = 9e18;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

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

	ll w, h, x, y;
	cin>>w>>h>>x>>y;
	if(h == 2*y && w== 2*x){
		double ui = h*w;
		cout<<(ui/2.0)<<" 1";
		return 0;
	}
	
	double ui = h*w;
		cout<<(ui/2.0)<<" 0";
		return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <math.h>

using namespace std;

#define EPS (1e-6)

double x[300], y[300];

int sign[] = {+1, -1};

int main(void) {
  int n;
  while (cin >> n, n) {
    for (int i=0; i<n; i++) {
      cin >> x[i] >> y[i];
    }

    int ans = 1;
    for (int i=0; i<n; i++) {
      for (int j=i+1; j<n; j++) {
        double d = hypot(x[i]-x[j], y[i]-y[j]);
        if ( d > 2.0 + EPS ) { continue; }

        double mx = (x[i] + x[j]) / 2;
        double my = (y[i] + y[j]) / 2;
        double vx = (x[j] - x[i]) / d;
        double vy = (y[j] - y[i]) / d;
        double e = sqrt(1.0 - d*d/4.0);

        for (int s=0; s<2; s++) {
          double px = mx + sign[s]*e*vy;
          double py = my - sign[s]*e*vx;

          int cnt = 2;
          for (int k=0; k<n; k++) {
            if (k==i || k==j) { continue; }
            if ( (px-x[k])*(px-x[k]) + (py-y[k])*(py-y[k]) < 1.0 + EPS ) { cnt++; }
          }
          if (cnt > ans) { ans = cnt; }
        }
      }
    }

    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1248
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast int fvariable = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e9+7;
const ll inf=1e18;
const ll ms=2e5+5;
fast;
ll sum;
void solve()
{
    ll n,a;cin>>n;
    set<ll>st;map<ll,ll>mp;
    for(ll i=1;i<n;i++)
    {
        cin>>a;
        mp[a]++;
        st.insert(a);
    }
    for(ll i=1;i<=n;i++)
    {
        cout<<mp[i]<<" ";
    }
}
int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    //int t;cin>>t;while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 25456
/*
	Author :- Vipin Kumar
*/
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>

#define int long long
using namespace std;



signed main(){
//	freopen("input.txt","r",stdin);
	int n;
	cin>>n;
	double t,a;
	cin>>t>>a;
	double arr[n];
	double mx = 1000000000;
	int ans;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		double p = t - (arr[i] * .006);
		if(abs(p-a) < mx){
			mx = abs(p-a);
			ans = i;
		}
	}
	cout<<ans+1;	
	return 0;
}

Measured memory_bytes: 256
#coding:utf-8
        
def DFS(i,A,d,f,t):
    if d[i-1]:
        return t
    d[i-1]=t
    t+=1
    for j in A[i-1]:
        t=DFS(j,A,d,f,t)
    f[i-1]=t
    t+=1
    return t

if __name__=="__main__":
    n=int(input())
    A=[]
    for i in range(n):
        A.append(list(map(int,input().split(" ")))[2:])
    d=[0]*n
    f=[0]*n
    t=1
    for i in range(n):
        if d[i]==0:
            t=DFS(i+1,A,d,f,t)
    for i in range(n):
        print("{} {} {}".format(i+1,d[i],f[i]))

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

int main(void) {
	string S;
	cin >> S;
	deque<char> que;
	for (char c : S) que.push_back(c);
	int rev = 0;
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			rev = 1 - rev;
		} else {
			int f;
			cin >> f;
			char c;
			cin >> c;
			f--;
			if (rev^f) {
				que.push_back(c);
			} else {
				que.push_front(c);
			}
		}
	}
	if (rev) reverse(que.begin(), que.end());
	for (auto c : que) cout << c;
	cout << endl;
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace   std;
#define ff        first
#define ss        second
#define ll        long long
#define int       long long
#define inf       ((ll)1e18)
#define double    long double
#define ull       unsigned long long
#define mod       1000000007
#define vi        vector<ll>
#define ppi       pair<ll,pair<ll,ll>>
#define pb        push_back
#define mp        make_pair
#define str       string
#define pi        2*acos(0.0)
#define pr(a,x,n) for(int i=x;i<n;i++){cout<<a[i]<<" ";}
#define p(a)      cout<<a;
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define endl      '\n'
#define all(v)    v.begin(), v.end()
#define test      cout<<"THIS_AND_THIS"<<endl;
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
int count(int A, int B, int M) 
{ 
    // Add 1 explicitly as A is divisible by M 
    if (A % M == 0) 
        return (B / M) - (A / M) + 1; 
  
    // A is not divisible by M 
    return (B / M) - (A / M); 
} 
int32_t main(){
	kehsihba();
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll x=(c*d)/__gcd(c,d);
	ll ans=b-a+1-count(a,b,c)-count(a,b,d)+count(a,b,x);
	cout<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    string s;
    cin>>s;
    rep(i,3) cout<<s[i];
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long int
#define INF 1000000007
// cin.eof() 入力個数の問題
int main() {
   long double a,b,c;
   cin>>a>>b>>c;
   long double esp=1.0E-14;
   if(sqrt(a)+sqrt(b)+esp<sqrt(c)){
     cout<<"Yes"<<endl;
   }else
   {
     cout<<"No"<<endl;
   }
   
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)

    val n = sc.nextInt()
    val testimony = Vector.fill(n) {
      val m = sc.nextInt()
      Vector.fill(m) {
        val a, b = sc.nextInt()
        (a, if (b == 1) true else false)
      }
    }

    val bits = bitSearch(n, Vector(true, false))

    val ans =
      bits
        .filter { bit =>
          bit.zipWithIndex.forall {
            case (b, i) =>
              if (!b) true
              else {
                testimony(i).forall {
                  case (x, y) => bit(x - 1) == y
                }
              }
          }
        }
        .map(_.count(_ == true))
        .max

    println(ans)
  }
  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }

  def printExecTime(process: => Unit): Unit = {
    val start = System.currentTimeMillis
    process
    debug("処理時間： " + (System.currentTimeMillis - start) + " ミリ秒")
  }

  def bitSearch[T](n: Int, choice: Vector[T]): Vector[Vector[T]] = {
    @tailrec
    def bitSearchLogic(n: Int,
                       choice: Vector[T],
                       acc: Vector[Vector[T]]): Vector[Vector[T]] = {
      if (n == 0) acc
      else {
        val newAcc =
          acc.flatMap(vec => {
            choice.map(c => vec :+ c)
          })
        bitSearchLogic(n - 1, choice, newAcc)
      }
    }

    val firstAcc = choice.map(i => Vector(i))
    bitSearchLogic(n - 1, choice, firstAcc)
  }
}


Measured memory_bytes: 66824
#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>

const int L = 4001;
const int MOD = 998244353;

using Bitset = std::bitset<L>;

int n, m, len[6], pow[L + 1];
char buf[L + 1];
Bitset x, a[6];

int main()
{
#ifdef LOCAL_JUDGE
    freopen("F.in", "r", stdin);
#endif
    scanf("%d", &n);
    scanf("%s", buf);
    m = strlen(buf);
    for (int j = 0; j < m; ++ j) {
        if (buf[j] == '1') {
            x.set(m - 1 - j);
        }
    }
    for (int i = 0; i < n; ++ i) {
        scanf("%s", buf);
        len[i] = strlen(buf);
        for (int j = 0; j < len[i]; ++ j) {
            if (buf[j] == '1') {
                a[i].set(len[i] - 1 - j);
            }
        }
    }
    int i0 = 0;
    for (int i = 0; i < n; ++ i) {
        if (len[i] < len[i0]) {
            i0 = i;
        }
    }
    while (true) {
        int new_i0 = i0;
        for (int i = 0; i < n; ++ i) {
            while (i != i0 && len[i] >= len[i0]) {
                a[i] ^= a[i0] << (len[i] - len[i0]);
                while (len[i] > 0 && !a[i].test(len[i] - 1)) {
                    len[i] --;
                }
            }
            if (len[i] > 0 && len[i] < len[new_i0]) {
                new_i0 = i;
            }
        }
        if (i0 == new_i0) {
            break;
        }
        i0 = new_i0;
    }
    pow[0] = 1;
    for (int i = 1; i <= L; ++ i) {
        pow[i] = (pow[i - 1] << 1) % MOD;
    }
    auto b = a[i0];
    Bitset s;
    int result = 0;
    for (int i = len[i0] - 1; i < L; ++ i) {
        if (x.test(i)) {
            s ^= b;
            result += pow[i - (len[i0] - 1)];
            if (result >= MOD) {
                result -= MOD;
            }
        }
        b <<= 1;
        if (b.test(len[i0] - 1)) {
            b ^= a[i0];
        }
    }
    bool ok = true;
    for (int i = len[i0] - 2; i >= 0; -- i) {
        if (x.test(i) < s.test(i)) {
            ok = false;
        }
        if (x.test(i) > s.test(i)) {
            break;
        }
    }
    result += ok;
    if (result >= MOD) {
        result -= MOD;
    }
    printf("%d\n", result);
}



Measured memory_bytes: 256
n = gets.to_i
takoyaki_points = gets.chomp.split(' ').map(&:to_i)
ans = 0
(takoyaki_points.size-1).times do |i|
    (i+1).upto(takoyaki_points.size-1) do |j|
        ans += takoyaki_points[i]*takoyaki_points[j]
    end
end
puts ans

Measured memory_bytes: 1788
import sys

test =False
if test:
    N = 1
    items = [9999]
else:
    N = int(raw_input())
    items = raw_input().split()
    items = [int(item) for item in items]
max_count = 0
min_val = min(items)
max_val = max(items)
counts = {}
for i in items:
    counts[i - 1] = counts.get(i - 1, 0) + 1
    counts[i] = counts.get(i, 0) + 1
    counts[i + 1] = counts.get(i + 1, 0) + 1
print max(counts.values())



Measured memory_bytes: 16536
#include <stdio.h>
#include <stdlib.h>

#define getchar getchar_unlocked

#define INIT_CAP 10
#define INF 1000000000

inline int nextInt(void) {
	int ch;
	int minus, x;

	do {
		ch = getchar();
	} while (ch < '-');

	if (ch == '-') {
		minus = 1;
		ch = getchar();
	} else
		minus = 0;

	x = 0;
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch & 15);
		ch = getchar();
	}

	return minus ? -x : x;
}

typedef struct {
	int *elem, cap, size;
} VecInt;

VecInt adj[100000];
int d[100000];
int cnt[100000];
int queue[100000];
int front, rear;

void init(int n) {
	while (n--)
		adj[n] = (VecInt){malloc(sizeof(int) * INIT_CAP), INIT_CAP, 0};
}

void add(int from, int to) {
	if (adj[from].size == adj[from].cap) {
		adj[from].cap <<= 1;
		adj[from].elem = realloc(adj[from].elem, sizeof(int) * adj[from].cap);
	}
	adj[from].elem[adj[from].size++] = to;
}

int main(void) {
	int i;
	int n, m;

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

	init(n);
	for (i = 0; i < m; i++) {
		int a, b;

		scanf("%d %d", &a, &b);
		a--; b--;

		add(a, b);
		add(b, a);
	}
	for (i = 0; i < n; i++)
		d[i] = INF;

	d[0] = 0;
	queue[rear++] = 0;
	while (front != rear) {
		const int from = queue[front++];
		cnt[d[from]]++;
		for (i = 0; i < adj[from].size; i++) {
			const int to = adj[from].elem[i];
			if (d[to] == INF) {
				d[to] = d[from] + 1;
				queue[rear++] = to;
			} else if (d[to] == d[from]) {
				printf("%lld\n", (long long)n * (n - 1) / 2 - m);
				return 0;
			}
		}
	}

	long long sum[2] = {0};
	for (i = 0; i < 100000; i++)
		sum[i & 1] += cnt[i];

	printf("%lld\n", sum[0] * sum[1] - m);

	return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sz size
#define eps 1e-7
#define fod find_by_order
#define fastio ios::base_sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ofk order_of_key
#define val(x) cout << "Value dari "<< #x << " adalah " << x  << "\n"
#define tr tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

void readf(string x){
	freopen((x+".in").c_str(),"r",stdin);
	freopen((x+".out").c_str(),"w",stdout);
}


int read()
{
	bool min = 0;
	int  result = 0;
	char ch;
	ch = getchar();
	while(1)
	{
		if(ch == '-') break;
		if(ch >='0' && ch <= '9') break;
		ch = getchar();
	}
	if(ch == '-') min = 1;else result = ch-'0';
	while(1)
	{
		ch =getchar();
		if(ch< '0' || ch>'9') break;
		result = result * 10 + (ch-'0');
	}
	if(min) return -result;
	return result;
}

int main(){
	int N;
	cin >> N;
	int x[3*N+5];
	for(int i=1;i<=3*N;i++) cin >> x[i];
	sort(x+1,x+3*N+1);
	ll ans = 0;
	int sum = 0;
	for(int i=3*N-1;i>=1;i-=2){
		ans += x[i];
		sum++;
		if(sum == N) break;
	}
	cout << ans << "\n";
}


Measured memory_bytes: 1408
N=int(input())
a=list(map(int,input().split()))

#ai=a[i-1]とした
A=0
S=0
a.sort(reverse=True)
for i in range(N):
    S+=a[i]
    if i%2==0:
        A+=a[i]
print(abs(S-2*A))


Measured memory_bytes: 38384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;

int main(){
    int n;
    cin>>n;
    vector<int> l(n),r(n);
    rep(i,n){
        int x,y;
        cin>>x>>y;
        l[i]=x-y;
        r[i]=x+y;
    }
    vector<int> ord(n);
    rep(i,n)ord[i]=i;
    sort(ord.begin(),ord.end(),[&](int s,int t){
        return r[s]<r[t];
    });
    int ans = 0, pre = -inf;
    for(auto i:ord){
        if(l[i]<pre)continue;
        ++ans;
        pre=r[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1408
n,m=list(map(int,input().split()))
# 再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

#隣接行列表現
es=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=list(map(int,input().split()))
  es[a-1][b-1]=1
  es[b-1][a-1]=1

  
#深さ優先探索

def dfs(v,visited):
  ans=0
  
  #自分が今いるところは探索済にする
  visited[v-1]=1
 
  #全部探索できたことになる
  if visited==check:
    visited[v-1]=0
    return 1
  
  #vから行けるところを考える
  for i in range(n):
    #道があって未訪問
    if visited[i]==0 and es[v-1][i]==1:
      ans=ans+dfs(i+1,visited)
  #次の探索のため未訪問にしておく
  visited[v-1]=0
   
  return ans





visited=[0 for i in range(n)]
check=[1 for i in range(n)]
print(dfs(1,visited))






      

  

Measured memory_bytes: 9072
#include <bits/stdc++.h>
#define mkp make_pair
#define pb push_back
#define clr(a,b) memset(a, b, sizeof(a))
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;

int gcd(int a, int b){
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

void compute(){
    int n;
    cin>>n;
    vi v(n);
    int mn = INT_MAX;
    for(int i=0; i<n; i++){ cin>>v[i];
        mn = min(mn, v[i]);
    }
    int res = mn;
    for(int i=0; i<n; i++){
        res = gcd(res, v[i]);
    }
    cout<<res<<"\n";
}

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{

  int k,n;
  int h[100005],dp[100005];

  cin >> n >> k;

  for(int i=0; i<n; i++) cin >> h[i];

  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);

  for(int i=2; i<n; i++){
    dp[i] = dp[i-1] + abs(h[i-1] - h[i]);
    for(int j=2; j<=k; j++){
      if(i - j < 0) break;
      dp[i] = min(dp[i] , dp[i-j] + abs(h[i-j] - h[i]));
    }
  }
  
  cout << dp[n-1] << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int n; cin >> n;
    vector<string> name(n);
    vvi g(n);
    REP(i, n) {
        int k; cin >> k; --k;
        cin >> name[i];
        if (k == -1) continue;
        g[k].push_back(i);
    }

    function<void(int,int)> dfs = [&](int v, int d) {
        REP(_, d) cout << '.';
        cout << name[v] << endl;
        for (int u : g[v]) {
            dfs(u, d+1);
        }
    };

    dfs(0, 0);


    return 0;
}



Measured memory_bytes: 3464
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  while (true) {
  	bool ok = true;
    for (int i = 2; i * i <= n; ++i) {
      if (n % i == 0) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cout << n;
      break;
    }
    n++;
  }
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [a, b, c, x, y] <- getIntList
  if (a + b) < 2 * c
    then print $ a * x + b * y
    else do
      let m = minimum [x, y]
      let x' = x - m
      let y' = y - m
      let m' = maximum [x, y]
      print $ minimum [(a * x' + b * y' + c * 2 * m), (c * 2 * m')]


Measured memory_bytes: 3684
//auto 関数名 = [(&:ラムダ外の引数をとる時))](引数の型1 引数名1, 引数の型2, 引数名2, ...) { 関数の処理 }; //inside main() define function. take care of };
// for (int tmp = 0; tmp < (1 << ビット数); tmp++) {
//   bitset<ビット数> s(tmp);
//   // (ビット列sに対する処理)
// }
// sort(配列変数.begin(), 配列変数.end());
// do {
//   // 順列に対する処理
// } while (next_permutation(配列変数.begin(), 配列変数.end()));
//const double PI = acos(-1); M_PI
// cout << fixed << setprecision(10);
#include <bits/stdc++.h>
#include <regex>
using namespace std;
using ll = int64_t;
using P = pair<int,int>;
#define _GLIBCXX_DEBUG 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end() //sort(all(vec)); ,reverse(all(vec));etc
int main(){
  int n,k;
  cin>>n>>k;
  map<int,int> m;
  int a;
  rep(i,n){
    cin>>a;
    m[a]=m[a]+1;
    //cout<<m[a]<<endl;
  }
  vector<int>vec;
  for(auto p:m){
    auto v=p.second;
    vec.push_back(v);
  }
  sort(all(vec));
  int cnt=0;
  int ans=0;
  rep(i,n){
    if((int)(vec.size())-cnt<=k){
      cout<<ans<<endl;
      return 0;
    }else{
      cnt+=1;
      ans+=vec.at(i);
    }
  }
}




Measured memory_bytes: 13628
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    double answer;
    int i, number;
    number = Integer.parseInt(sc.next());
    int[] values = new int[number];
    for(i = 0; i < number; i++) values[i] = Integer.parseInt(sc.next());
    Arrays.sort(values);
    answer = values[0];
    for(i = 1; i < number; i++) {
      answer = (answer + values[i]) / 2.0;
    }
    System.out.println(answer);
  }
}


Measured memory_bytes: 23252
N = int(input())
H = list(map(int, input().split(" ")))

max_count = 0
count = 0
pre = H[0]
for i in H[1:]:
    if pre >= i:
        count += 1
    else:
        count = 0
    
    if count > max_count:
        max_count = count

    pre = i

print(max_count)

Measured memory_bytes: 14252
n,m,x = map(int,input().split())
book = []
import numpy as np
for _ in range(n):
    a = list(map(int,input().split()))
    book.append(a)
ans = float("inf")
for i in range(1,2**n):
    use_book = []
    for j in range(n):
        if (i>>j) &1:
            use_book.append(book[j])
    arr = np.array(use_book)
    arr_sum = np.sum(arr,axis =0)
    true =1
    for i in range(1,m+1):
        if arr_sum[i] < x:
            true = 0
            break
    if true == 1:
        ans = min(ans,arr_sum[0])
if ans == float("inf"):
    ans = -1
print(ans)

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

int main() {
  int N,M,X;
  cin >> N >> M >> X;
  int A;
  int cost=0;
  for(int i=0;i<N;i++){
    cin >> A;
    if(A<X){
      cost++;
    }
  }
  
  cout << min(cost,M-cost) << endl;
}



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

int main(){
    int n; cin>>n;
    char s[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>s[i][j];
        }
    }

    int ans=0;
    // a=0
    for(int b=0; b<n; b++){
        char t[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                t[i][j]=s[i%n][(j+b)%n];

                if(j<i && t[i][j]!=t[j][i]) goto END;
            }
        }
        ans++;
        END:;
    }
    cout << ans*n << endl;
}

Measured memory_bytes: 384
def nCr(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod


mod = 10 ** 9 + 7  # 出力の制限

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

ans = pow(2, n, mod)-1 - nCr(n, a, mod) - nCr(n, b, mod)

print(ans%mod)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <cstdio>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;



#define INF 2000000000
#define MAX_V 10



bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll modpow(ll a,ll n,ll mod1) {
    ll res=1;
    while(n>0){
        if(n&1) res=res*a%mod1;
        a = a*a%mod1;
        n >>= 1;
    }
    return res;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x*=i;
    return x;
}

ll gcd(ll a,ll b) { return b ? gcd(b, a%b) : a; }

ll func(ll a,ll b,ll& ans_x,ll& ans_y){
    if(b == 0){
        ans_x = 1;
        ans_y = 0;
        return a;
    }else{
        ll ret = func(b,(a%b),ans_y,ans_x);
        ans_y -= (a/b)*ans_x;
        return ret;
    }
}

ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}
const ll MAX = 5100000;
const ll MOD = 1000000007;
 
ll fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using graph = vector<vector<ll>>;
pair<pair<ll,ll>,ll> p[100010];

ll dp[50010];



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

    ll n,sum=0;
    cin>>n;
    rrep(i,n){
        ll kou=n/i;
        sum+=(kou)*(kou+1)*i/2;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <cstring>
#include<bits/stdc++.h>
#define MAX_N 1000 + 16

using namespace std;

int N, H, W;
int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N];
int fld[2 * MAX_N][2 * MAX_N], // 填充遍?用，代表坐?(i, j)?是否空白（??后）
dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

// ??坐?，将坐?的??成“?是第几??”，返回一共有几?坐?
int compress(int *x1, int *x2, int w)
{
	vector<int>xs;

	for (int i = 0; i < N; ++i)
	{
		int tx1 = x1[i], tx2 = x2[i];
		if (1 <= tx1 && tx1 < w) xs.push_back(tx1);
		if (1 <= tx2 && tx2 < w) xs.push_back(tx2);
	}
	xs.push_back(0);
	xs.push_back(w);
	sort(xs.begin(), xs.end());
	xs.erase(unique(xs.begin(), xs.end()), xs.end());
	for (int i = 0; i < N; ++i)
	{
		x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
		x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
	}
	return xs.size() - 1;
}

int bfs()
{
	int ans = 0,res=0;
	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < W; ++j)
		{
			if (fld[i][j]) continue;
			++ans;
			queue<pair<int, int> >que;
			que.push(make_pair(j, i));
			while (!que.empty())
			{
				int nx = que.front().first, ny = que.front().second;
				que.pop();
				for (int k = 0; k < 4; ++k)
				{
					int tx = nx + dx[k], ty = ny + dy[k];
					if (tx < 0 || W < tx || ty < 0 || H< ty || fld[ty][tx] > 0) continue;
					que.push(make_pair(tx, ty));
					fld[ty][tx] = 1;
					res++;
				}
			}
		}
	}
	//cout<<res<<endl;
	return ans;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	while (cin >> W >> H, W | H)
	{
		cin >> N;
		for (int i = 0; i < N; ++i)
		{
			cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
		}

		memset(fld, 0, sizeof(fld));

		W = compress(X1, X2, W);
		H = compress(Y1, Y2, H);

		// imos-法
		//printf("%d %d\n",W,H);
		for (int i = 0; i < N; i++)
		{
			fld[Y1[i]][X1[i]]++;
			fld[Y1[i]][X2[i]]--;
			fld[Y2[i]][X1[i]]--;
			fld[Y2[i]][X2[i]]++;
		}
		// 横向累?
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
			    if((!i)&&(!j))continue;
			    if(i&&j)fld[i][j] += fld[i][j - 1]+fld[i-1][j]-fld[i-1][j-1];
			    else if(i==0)fld[i][j] += fld[i][j - 1];
			    else if(j==0)fld[i][j] += fld[i-1][j];
			}
		}
		cout << bfs() << endl;
	}
	return 0;
}

Measured memory_bytes: 18972
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    N = int(input())
    A = list(map(int, input().split()))

    arr = A[0]
    ans = 0
    for i in A:
        ans += abs(arr - i) if i <= arr else 0
        arr = max(arr, i)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 31984
# coding:utf-8
 
n = int(input())
s = input()
LetterCount = {i:s.count(i) for i in 'abcdefghijklmnopqrstuvwxyz'}
answer = 1
for i in 'abcdefghijklmnopqrstuvwxyz':
  answer = answer * (LetterCount[i]+1) % (10**9+7)
print(answer-1)

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

int main(){
    ll N;cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }

    ll ans = 0;
    while(1){
        ll tar = -1;   //2で割られる数のインデックス
        rep(i,N){
            if(A[i]%2 == 0){
                if(tar == -1)tar = i;
                else if(A[i]%4 == 0){
                    tar= i;
                    A[i] /= 2;
                    ans++;
                    break;
                }
            }
        }
        if(tar != -1){
            A[tar] /= 2;
            ans++;
        }
        else break;
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;
ll X[505][505]; 
int main(void){
	int N,M,Q;
	cin >> N >> M >> Q;
	vector<int> ans,p(Q),q(Q);
	for(int i=0;i<M;i++){
		int L,R;
		cin >> L >> R;
		X[L][R]++;
	}
	for(int i=0;i<Q;i++){
		cin >> p[i] >> q[i];
	}
	// x[L][R];
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			X[i][j+1] = X[i][j+1] + X[i][j];
		}
	}
	for(int i=0;i<=N;i++){
		for(int j=0;j<=N;j++){
			X[j+1][i] = X[j+1][i] + X[j][i];
		}
	}
	for(int i=0;i<Q;i++){
		int L = p[i];
		int R = q[i];
		int t = X[R][R] + X[L-1][L-1] - X[L-1][R] - X[R][L-1];
		ans.push_back(t);
	}
	for(auto x:ans)cout << x << endl;
}

Measured memory_bytes: 4216
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define pdump(p) cout<<" "<<#p<<"=("<<p.fst<<","<<p.snd<<")"
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std; using lint = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<lint, lint>;

int main(void) {
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> b(m);
    repeat (i, m) cin >> b[i];
    int ans = 0;
    rep (n) {
        vector<int> a(m);
        repeat (i, m) cin >> a[i];
        int calc = 0;
        repeat (i, m) calc += a[i] * b[i];
        calc += c;
        if (calc > 0) ++ans;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<typeinfo>

using namespace std;
#define REP(i,m,n) for(int i=m;i<n;++i)
#define REPll(i,m,n) for(ll i=m;i<n;++i)
#define INF 10000000000000000
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define all(v) v.begin(),v.end()

int power(int a, int b) {
	int ans = 1;
	REP(i, 0, b) {
		ans *= a;
	}
	return ans;
}

bool check(int a) {
	int ans = 0;
	while (a != 0) {
		int tmp = a % 10;
		if (tmp == 7) {
			tmp += 2;
		}
		tmp--;
		ans = (ans | tmp);
		a /= 10;
	}
	if (ans == 14) {
		return true;
	}
	else {
		return false;
	}
}

int cal(int a, int b) {
	int ans = 0;
	REP(a0, 0, 3) {
		REP(a1, 0, 3) {
			REP(a2, 0, 3) {
				REP(a3, 0, 3) {
					REP(a4, 0, 3) {
						REP(a5, 0, 3) {
							REP(a6, 0, 3) {
								REP(a7, 0, 3) {
									REP(a8, 0, 3) {
										int tmp = (2 * a0 + 3) + (2 * a1 + 3) * 10 + (2 * a2 + 3) * 100 + (2 * a3 + 3) * 1000 + (2 * a4 + 3) * 10000 + (2 * a5 + 3) * 100000 + (2 * a6 + 3) * 1000000 + (2 * a7 + 3) * 10000000 + (2 * a8 + 3) * 100000000;
										if (tmp%power(10, a) <= b&&check(tmp%power(10, a)) == true) {
											ans++;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	return ans;
}

int main() {
	int n;
	cin >> n;
	int ans = 0;
	int hoge = n, t = 1;
	while (hoge >= 10) {
		ans += power(3, t) - 3 * power(2, t) + 3;
		hoge /= 10;
		t++;
	}
	ans += cal(t, n) / power(3, 9 - t);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long A,B,K;
  cin >> A >> B >> K;
  
  if (B-A < 2*K) {
    for (int i=A;i<=B;i++) {
      cout << i << endl;
    }
  }
  
  else {
    for (int i=0;i<K;i++) {
      cout << A+i << endl;
    }
    for (int i=0;i<K;i++) {
      cout << B-K+i+1 << endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int64_t MAXN = 510;
vector<vector<int64_t>> LR(MAXN, vector<int64_t>(MAXN, 0));

int main()
{
  int64_t N, M, Q, l, r, p, q;
  cin >> N >> M >> Q;
  for (int i = 0; i < M; i++)
  {
    cin >> l >> r;
    for (int j = 1; j <= l; j++)
    {
      LR.at(j).at(r)++;
    }
  }
  for (int i = 1; i <= N; i++)
  {
    for (int j = 1; j <= N; j++)
    {
      LR.at(i).at(j) += LR.at(i).at(j - 1);
    }
  }
  vector<pair<int64_t, int64_t>> qs(Q);
  for (int i = 0; i < Q; i++)
  {
    cin >> p >> q;
    qs.at(i) = make_pair(p, q);
  }
  for (int i = 0; i < Q; i++)
  {
    cout << LR.at(qs.at(i).first).at(qs.at(i).second) << endl;
  }
}


Measured memory_bytes: 4608