akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void){
    int H,W;
    int i = 0;
    char sh = '#';
    char dot ='.';
for (; i < 10000; i++){
    scanf("%d %d", &H, &W);
    if( H == 0 && W == 0){
        break;
    }
    int j = 1;
    for(; j <= H;j++){
        int k = 1;
        for(; k <= W; k++){
            if(j %2 == 1 && k %2 ==1){
                printf("%c",sh);
            }else if (j %2 == 0 && k % 2 ==0){
                printf("%c",sh);
            }else{
                printf("%c",dot);
            }
        }
        printf("\n");
    }
     printf("\n");
    
}
    
    return 0;
}


Measured memory_bytes: 2080
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+5;
int a[N],cnt[N];
int vis[N];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	for(int i=1;i<=1000000;i++){
		if(cnt[i]){
			if(cnt[i]>=2)
			vis[i]=1;
			for(int j=i+i;j<=1000000;j+=i){
				vis[j]=1;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!vis[a[i]])
		ans++;
	}
	printf("%d",ans);
}


Measured memory_bytes: 12296
#include<bits/stdc++.h>
using namespace std;
long long n,k,l;//bilibili
int main()
{
  cin>>n;
  for(long long i=1;i<=3500;i++)
  {
    for(long long j=1;j<=3500;j++)
    {
      k=4*i*j-n*j-n*i;
      l=i*j*n;
      if(k>0&&l%k==0)
      {
        cout<<i<<" "<<j<<" "<<l/k<<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> LP;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

struct UnionFind{ // paste zamurai
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i=0;i<v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

struct edge{
  int a,b,c;
};
bool operator<(const edge& a,const edge& b){
  return a.c<b.c;
}

int n,m;
edge es[200*200];
bool use[222];

int main(){
	cin.sync_with_stdio(false);
  while(1){
    cin>>n>>m;
    if(n==0)break;
    vector<P> h;
    rep(i,n){
      int hh;
      cin>>hh;
      h.pb(P(hh,i));
    }
    sort(all(h));
    reverse(all(h));
    h.pb(P(-1,-1));
    rep(i,m){
      int a,b,c;
      cin>>a>>b>>c;
      a--; b--;
      es[i]=(edge){a,b,c};
    }
    sort(es,es+m);
    UnionFind uf(n);
    int res=0;
    int cnt=0;
    memset(use,0,sizeof(use));
    rep(i,n){
      use[h[i].se]=true;
      while(h[i].fi==h[i+1].fi){
        use[h[++i].se]=true;
      }
      rep(j,m){
        if(use[es[j].a]&&use[es[j].b]&&!uf.same(es[j].a,es[j].b)){
          res+=es[j].c;
          uf.unite(es[j].a,es[j].b);
          cnt++;
        }
      }
      if(cnt!=i){
        uf.init();
        res=0; cnt=0;
      }
    }
    cout<<res<<endl;
  }
	return 0;
}

Measured memory_bytes: 3444
import java.util.*;

public class Main{

    int gx,gy,p;
    int[][][][] m;
    int[][] cnt;

    void solve(){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        while(n-->0){
            gx = sc.nextInt();
            gy = sc.nextInt();
            p = sc.nextInt();
            m = new int[gy+1][gx+1][gy+1][gx+1];
            for(int i=0; i<p; i++){
                int x1 = sc.nextInt();
                int y1 = sc.nextInt();
                int x2 = sc.nextInt();
                int y2 = sc.nextInt();
                m[y1][x1][y2][x2] = 1;
                m[y2][x2][y1][x1] = 1;
            }

            cnt = new int[gy+1][gx+1];
            cnt[0][0] = 1;
            for(int j=0; j<=gx; j++){
                for(int i=0; i<=gy; i++){
                    if(j-1>=0 && m[i][j][i][j-1]==0) cnt[i][j] += cnt[i][j-1];
                    if(i-1>=0 && m[i][j][i-1][j]==0) cnt[i][j] += cnt[i-1][j];
                }
            }

            if(cnt[gy][gx]==0) System.out.println("Miserable Hokusai!");
            else System.out.println(cnt[gy][gx]);
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 14000
#include<iostream>
using namespace std;
const int  N=2e5+7;
const int  mod=1e9+7;
long long  arr[N];
long long  num[N];
int  main(){
	long long  n;
	cin>>n;
	for(int  i=1;i<=n;i++){
		cin>>num[i];
	}
	for(int  i=n;i>=1;i--){
		arr[i]=(arr[i+1]+num[i])%mod;
	}
	long long  ans=0;
	for(int  i=1;i<=n;i++){
		ans=(ans+num[i]*arr[i+1])%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6232
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if(s.charAt(0) == s.charAt(1) && s.charAt(1)== s.charAt(2) || s.charAt(1) == s.charAt(2) && s.charAt(2)== s.charAt(3)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 24020
#include<iostream>

using namespace std;

const int MAX_N=1e5;
const long long mod=1e9+7;
int cnt[MAX_N];

long long pow(long long x,int y){
	long long re=1;
	while(y>0){
		if(y&1)re=(re*x)%mod;
		y/=2;
		x=(x*x)%mod;
	}
	return re;
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		cnt[x]++;
	}
	if(n%2==1)cnt[0]++;
	bool ans=true;
	for(int i=n-1;i>=0;i-=2){
		if(cnt[i]!=2)ans=false;
	}
	if(ans)cout<<pow(2,(n/2))<<endl;
	else cout<<0<<endl;
}


Measured memory_bytes: 640
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = sc.nextInt();
    int t = sc.nextInt();

    int kaisu = n/x;

    if(n%x==0){
      System.out.println(t*kaisu);
    }else{
      System.out.println(t*(kaisu+1));
    }
  }
}


Measured memory_bytes: 35704
import java.util.Scanner;

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

		int H = sc.nextInt();
		int W = sc.nextInt();
		int h = sc.nextInt();
		int w = sc.nextInt();

		System.out.println(H * W - (W * h + H * w - h * w));
	}

}


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

int main() {
  int A, B, p, q, r, s, t, x;
  cin >> A >> B;
  for (; A <= B; A++) {
    p = A / 10000;
    q = (A - p * 10000) / 1000;
    r = (A - p * 10000 - q * 1000) / 100;
    s = (A - p * 10000 - q * 1000 - r * 100) / 10;
    t = A - p * 10000 - q * 1000 - r * 100 - s * 10;
    if (p == t && q == s) {
      x++;
    }
  }
  cout << x;
}

Measured memory_bytes: 256
n, k, c = gets.split.map(&:to_i)
s = gets.chomp.split(//)
rs = s.reverse
lcnt, rcnt = 0, 0
left = Array.new(n){|i| i = 0}
right = Array.new(n){|i| i = 0}
llimit, rlimit = -1, -1

n.times do |i|
  if s[i] == "o" && llimit < i
    lcnt += 1
    left[i] = lcnt
    llimit = i + c
  end 
  if rs[i] == "o" && rlimit < i
    rcnt += 1
    right[-(i + 1)] = k + 1 -rcnt
    rlimit = i + c
  end
end

ans = []
n.times do |i|
  if left[i] == right[i] && left[i] > 0
    ans << i + 1
  end
end

unless ans.empty?
  ans.each do |i|
    puts i
  end
end

Measured memory_bytes: 36992
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s; 
    cin>>s;
    int l=s.size(); 
    for(int i=0;i<=l;i++)
    {
        if(s[i]=='C') 
        {
            for(int j=i;j<=l;j++)
            {
                if(s[j]=='F')
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
from decimal import Decimal, ROUND_DOWN

A,B=input().split()
A=Decimal(A).quantize(Decimal('0'), rounding=ROUND_DOWN)
B=Decimal(B).quantize(Decimal('0.01'), rounding=ROUND_DOWN)
C=A*B
C=Decimal(str(C)).quantize(Decimal('0'), rounding=ROUND_DOWN)
print(C)

Measured memory_bytes: 9944
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	void solve() throws IOException {
		long n = nl();
		for (int i = 0; i <= n/4; i++) {
			long j = (n-i*4)/7;
			if (n == i*4+j*7) {
				out.println("Yes");
				return;
			}
		}
		out.println("No");
	}

	private int getP(long n) {
		if (n < 0)
			n = -n;
		int p = 0;
		while (n > 0) {
			n >>= 1;
			p++;
		}
		return p;
	}

	String ns() throws IOException {
		while (!tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine(), " ");
		}
		return tok.nextToken();
	}

	int ni() throws IOException {
		return Integer.parseInt(ns());
	}

	long nl() throws IOException {
		return Long.parseLong(ns());
	}

	double nd() throws IOException {
		return Double.parseDouble(ns());
	}

	String[] nsa(int n) throws IOException {
		String[] res = new String[n];
		for (int i = 0; i < n; i++) {
			res[i] = ns();
		}
		return res;
	}

	int[] nia(int n) throws IOException {
		int[] res = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = ni();
		}
		return res;
	}

	int[][] nia(int n, int m) throws IOException {
		int[][] res = new int[n][];
		for (int i = 0; i < n; i++) {
			res[i] = nia(m);
		}
		return res;
	}

	long[] nla(int n) throws IOException {
		long[] res = new long[n];
		for (int i = 0; i < n; i++) {
			res[i] = nl();
		}
		return res;
	}

	public static void main(String[] args) throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		tok = new StringTokenizer("");
		Main main = new Main();
		main.solve();
		out.close();
	}
}

Measured memory_bytes: 22864
import java.util.*;

 
class Main {
 
    private static Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
        String s[] =new String[5];
        for(int i=0;i<5;i++){
            s[i]=sc.next();
        }
        int k=Integer.parseInt(sc.next());
        int antn[] =new int[5];
        for(int i=0;i<5;i++){
            antn[i]=Integer.parseInt(s[i]);
        }
        for(int r=0;r<5;r++){
            for(int t=0;t<4;t++){
                if(Math.abs(antn[r]-antn[t])>k){
                    System.out.println(":(");
                    return;
                }
            }
        }
        System.out.println("Yay!");
    }
}

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

int main(){
    char b;
    cin >> b;
    char ans;
    if(b == 'A') ans = 'T';
    if(b == 'C') ans = 'G';
    if(b == 'G') ans = 'C';
    if(b == 'T') ans = 'A';
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
p=list(int(i)-1 for i  in input().split())
s=[list(int(i)-1 for i  in input().split()) for _ in range(m)]

a={i:i for i in range(n)}

def find(x):
    if a[x]==x:
        return x
    else:
        a[x]=find(a[x])
        return a[x]

for x,y in s:
    a[find(x)] = find(y)

ans=0

for i in range(n):
    if find(i)==find(p[i]):
        ans+=1


print(ans)

Measured memory_bytes: 138856
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    k=K
    p=[(a+1)*0.5 for a in A]
    cur=sum(p[:k])
    ans=cur
    for i in range(1,N-K+1):
        cur=cur-p[i-1]+p[i+k-1]
        ans=max(cur,ans)
    print(ans)




if __name__ == "__main__":
    main()

Measured memory_bytes: 101892
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<deque>
#include<tuple>
#include<queue>
#include<map>
#include <cstdint>
#include <boost/multiprecision/cpp_int.hpp>


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define Endl endl
#define F first
#define S second

namespace mp = boost::multiprecision;

using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

int ans = 0;
void dfs(int n,  int count, vector<int>path,
	vector<vector<int>>map) {
	if (count == path.size()) {
		ans++;
	}
	else {
		for (int i = 1; i < path.size(); i++) {
			if (map[n][i] == 1 && path[i] == 0) {
				path[i]++;
				count++;
				dfs(i,count, path, map);				
				path[i] = 0;
				count--;
			}
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>>map(n, vector<int>(n,0));
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		map[a][b]++;
		map[b][a]++;
	}
	vector<int>path(n,0);
	path[0] = 1;
	dfs(0, 1, path, map);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int main(){
	int y, m, d;
	scanf("%d/%d/%d", &y, &m, &d);
	if(m<=4) printf("Heisei\n");
	else printf("TBD\n");
}


Measured memory_bytes: 256
// B - Uneven Numbers
#include <stdio.h>

int main(void){
    int n, i;
    int sum=0;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        if(0<i && i<10){
            sum++;
        }else if(99<i && i<1000){
            sum++;
        }else if(9999<i && i<100000){
            sum++;
        }
    }
    printf("%d\n", sum);
    return 0;
}

Measured memory_bytes: 128
void throwdice_N(int x[6]){
    int tmp;
    tmp = x[0];
    x[0] = x[1];
    x[1] = x[5];
    x[5] = x[4];
    x[4] = tmp;
}
void throwdice_E(int x[6]){
    int tmp;
    tmp = x[0];
    x[0] = x[3];
    x[3] = x[5];
    x[5] = x[2];
    x[2] = tmp;
}
void throwdice_S(int x[6]){
    int tmp;
    tmp = x[0];
    x[0] = x[4];
    x[4] = x[5];
    x[5] = x[1];
    x[1] = tmp;
}
void throwdice_W(int x[6]){
    int tmp;
    tmp = x[0];
    x[0] = x[2];
    x[2] = x[5];
    x[5] = x[3];
    x[3] = tmp;
}

#include <stdio.h>
int main(int argc, const char * argv[]) {
    int i, top, front, left, right, back, bottom, count=0;
    int top2, front2, left2, right2, back2, bottom2;
    int x[6], x2[6];
    for(i=0; i<6; i++) {
        scanf("%d",&x[i]);
    }
    back = x[4];
    top = x[0];
    right = x[2];
    left = x[3];
    bottom = x[5];
    front =x[1];
    
    for(i=0; i<6; i++) {
        scanf("%d",&x2[i]);
    }
    back2 = x2[4];
    top2 = x2[0];
    right2 = x2[2];
    left2 = x2[3];
    bottom2 = x2[5];
    front2 =x2[1];
    
    while (x2[1] != front) {
        
        if((x2[1] != back) &&
           (x2[1] != top) &&
           (x2[1] != right) &&
           (x2[1] != left) &&
           (x2[1] != bottom) &&
           (x2[1] != front) ){
            count++;
            break;
        }
        
        if (x2[2] == front || x2[3] == front) {
            //printf("be:%d\n", x[1]);
            throwdice_E(x2);
            //printf("af:%d\n", x[1]);
        }
        throwdice_N(x2);
        //printf("%d\n", x[1]);
    }
    while(x2[5] != bottom){
        if(0 < count) break;
        throwdice_E(x2);
    }
    while (x2[0] != top) {
        if(0 < count) break;
        throwdice_E(x2);
    }
    
    back2 = x2[4];
    top2 = x2[0];
    right2 = x2[2];
    left2 = x2[3];
    bottom2 = x2[5];
    front2 =x2[1];
    
    if(back == back2 &&
       top == top2 &&
       right == right2 &&
       left == left2 &&
       bottom == bottom2 &&
       front == front2){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    
    return 0;
}

Measured memory_bytes: 580
/*  ex2_3
    pptenshi  */

#include<stdio.h>

int main(void) {
    int N;  // マス目
    int A;  // 白色のマス
    int B;  // 黒色のマス


    // input
    scanf("%d", &N);
    scanf("%d", &A);

    B = N * N - A;

    // output
    printf("%d\n", B);

    return 0;
}

Measured memory_bytes: 128
N,M=map(int,input().strip().split())
k=[]
s=[]
for m in range(M):
    ks=list(map(int,input().strip().split()))
    k.append(ks[0])
    s.append(ks[1:])
p=list(map(int,input().strip().split()))

def judge(k,s,p,l):
    ON=True
    for m in range(M):
        num=0
        for i in range(k[m]):
            if l[s[m][i]-1]==1:
                num+=1
        if num%2!=p[m]:
            ON=False
            break
    return ON             
                
cnt=0
def dfs(l,N,M):
    global cnt
    if len(l)==N:
        if judge(k,s,p,l):
            cnt+=1            
        return
    else:
        for n in range(2):
            l.append(n)
            dfs(l,N,M)
            l.pop()

dfs([],N,M)
print(cnt)

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

int main() {
    string s;
    cin >> s;
    bool flag = false;
    for(int i=0;i<s.size();i++){
        if(s[i+1]=='C'&&s[i]=='A'){
            flag = true;
            break;
        }
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

#define show(x) cerr << #x << " = " << x << endl ;
#define input_from_file freopen("input.txt","r",stdin)
#define output_to_file freopen("output.txt" , "w",stdout)
#define fastio ios_base::sync_with_stdio(0)
#define endl '\n'

const int N = 50;
int arr[N];

int main()
{
	 #ifdef LOCAL
        input_from_file;
        output_to_file;
    #endif
	fastio;cin.tie(0);cout.tie(0);
	int n ; string str ; 
	cin >> n >>  str;
	int i = 0 , ans = 0;
	while(i < n)
	{
		int j = i ;
		while(j < n && str[j] == str[i]) ++j;
		++ans , i = j;
	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 512
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

m = {}
m2 = {}

def check(S):
    return ord('0') <= ord(S) and ord(S) <= ord('9')

while True:
    S = raw_input()
    if S == 'END_OF_FIRST_PART':
        break
    atom, w = S.split()
    if len(atom) >= 2:
        m2[atom] = w
    else:
        m[atom] = w

while True:
    S = raw_input()
    if S == '0':
        break
    SS = ''
    for i in range(len(S) - 1):
        SS += S[i]
        if not check(S[i]) and check(S[i + 1]):
            SS += '*'
        if check(S[i]) and not check(S[i + 1]):
            SS += '+'
    SS += S[-1]
    S = '(' + SS + ')'
    for atom in m2:
        S = S.replace(atom, m2[atom] + '+')
    for atom in m:
        S = S.replace(atom, m[atom] + '+')
    S = S.replace('+*', '*')
    S = S.replace('+)', ')')
    try:
        ret = eval(S)
    except:
        ret = "UNKNOWN"
    print ret


Measured memory_bytes: 5036
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>

typedef long long LL;
using namespace std;

const LL N=1000;
int n,m;
int p[N+5];
int c[N+5];
int d[1<<16];

int main()
{
	memset(d,0x3f,sizeof d);
	
	scanf("%d %d",&n,&m);
	
	for(register int i=1;i<=m;i++)
	{
		scanf("%d",&p[i]);
		int k,v;
		scanf("%d",&k);
		for(register int j=1;j<=k;j++)
		{
			scanf("%d",&v);
			c[i] |= 1<<(v-1);
		}
	}
	
	int Max=d[1];
	d[0]=0;
	for(register int s=0;s<(1<<n);s++)
		for(register int i=1;i<=m;i++)
			if(d[s]!=Max)
				d[s|c[i]]=min(d[s|c[i]],d[s]+p[i]);
	if(d[(1<<n)-1]!=Max)
		printf("%d\n",d[(1<<n)-1]);
	else
		printf("-1\n");
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int main() {
	int n; cin >> n;
	int ans = 0;
	if(n < 3000 && n >= 2000) ans ++;
	if(n % 1000 >= 200 && n % 1000 < 300 ) ans ++;
	if(n % 100 >= 20 && n % 100 < 30) ans ++;
	if(n % 10 >= 2 && n % 10 < 3) ans ++;
	cout << ans  << endl;
	return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
import bisect

s = input()
t = input()
s_set = set(list(s))
t_set = set(list(t))

# print(s_set)
# print(t_set)

if t_set <= s_set:
    str_dict = defaultdict(list)
    for i, cha in enumerate(s):
        str_dict[cha].append(i)
    # print(str_dict)

    times = 0
    now = 0

    for i, c in enumerate(t):
        target_char = str_dict[c]
        if target_char[-1] < now:  # 次の週の最初の文字を使用
            times += 1
            now = target_char[0]+1
        else:
            now = target_char[bisect.bisect_left(target_char, now)]+1
        # print((times, now))
    print(len(s) * times + now)

else:
    print(-1)


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

int main()
{
    int n , a , b , c ;
    cin>>n>>a>>b;
    
    c = abs( a - b );
    
    if ( c % 2 == 0 )
    {
        cout<<"Alice"<<endl;
    }
    else
    {
        cout<<"Borys"<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

template<typename T>
void say(vector<T> s, char r) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << r << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("yes");
	else say("no");
}

void Yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

void YN(bool b) {
	if (b)say("YES");
	else say("NO");
}

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

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

void exact_say(double x) {
	cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
}

template<class T> void getVector(vector<T>& v) {
	for (int i = 0; i < v.size(); ++i)
		cin >> v[i];
}

std::string revString(std::string s) {
	string ret;
	auto it = s.rend();
	while (it != s.rbegin()) {
		ret.push_back(*it);
		++it;
	}
	return ret;
}

int suitnum(string s) {
	if (s == "S")return 0;
	else if (s == "H")return 13;
	else if (s == "C")return 26;
	else if (s == "D")return 39;
	else throw;
}

signed main() {
	const string suit = "SHCD";
	vector<bool> exist;
	rep(52)exist.push_back(true);
	makei(n);
	rep(n) {
		makes(s);
		makei(t);
		exist[suitnum(s) + t - 1] = false;
	}
	rep(52) {
		if (exist[i]) {
			cout << suit[i / 13] << " " << i % 13 + 1 << endl;
		}
	}
}


Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define N 200010
int n,a[N],b[N];
int main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n)cin>>b[i];
    int j=0,bef=-1;
    rep(i,n){
	if(bef!=a[i])j=0;
	if(a[i]==b[i]){
	    for(;j<n;j++){
		if(a[j]!=a[i]&&b[j]!=a[i]){
		    swap(b[i],b[j]);
		    break;
		}
	    }
	    if(a[i]==b[i]){
		cout<<"No\n";
		return 0;
	    }
	}
	bef=a[i];
    }
    cout<<"Yes\n";
    rep(i,n){
	if(i)cout<<" ";
	cout<<b[i];
    }
    cout<<"\n";
}

Measured memory_bytes: 5188
#!/usr/bin/env python3
h, w, m = map(int, input().split())
r = [0] * (h + 1)
c = [0] * (w + 1)
s = []
for _ in range(m):
    x, y = map(int, input().split())
    r[x] += 1
    c[y] += 1
    s.append([x, y])
R = max(r)
nr = {i for i, x in enumerate(r) if x == R}
C = max(c)
nc = {i for i, x in enumerate(c) if x == C}
count = 0
for x, y in s:
    count += x in nr and y in nc
print(R + C - (len(nr) * len(nc) == count))


Measured memory_bytes: 216432
N=int(input())
A=list(map(int,input().split()))

dp=[0]*(N)
dp[0]=1000
for i in range(1,N):
    for j in range(i+1):
        stock=dp[i-j]//A[i-j]
        money=stock*A[i]+dp[i-j]-stock*A[i-j]
        dp[i]=max(dp[i],dp[i-j],money)
print(dp[N-1])

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

int main(){
    int N,K;
    string S;

    cin >> N >>K >> S;

    // S.at(N-1) = char(S.at(N-1)+32);
    S.at(K-1) = char(S.at(K-1)+32);
    
    cout << S <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int analysis(char* str){
  int i,answer=0,coefficient=1;

    for(i=0;str[i];i++){
      if('0'<=str[i] && str[i]<='9')
	coefficient=str[i]-'0';
      else{
	switch(str[i]){
	case 'm': 
	  answer=answer+coefficient*1000;
	  break;
	case 'c':
	  answer=answer+coefficient*100;
	  break;
	case 'x':
	  answer=answer+coefficient*10;
	  break;
	case 'i':
	  answer=answer+coefficient;
	  break;
	}
	coefficient=1;
      }
    }
    
    return answer;
}

int main(void){
  int n,i;
  int a,b,c,d,e,f;
  int int_answer;
  char str_a[1024],str_b[1024];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s %s",str_a,str_b);
    int_answer=analysis(str_a)+analysis(str_b);
    a=int_answer/1000;
    b=int_answer%1000;
    c=b/100;
    d=b%100;
    e=d/10;
    f=d%10;
    if(2<=a && a<=9)
      printf("%dm",a);
    else if(a==1)
      printf("m");
    if(2<=c && c<=9)
      printf("%dc",c);
    else if(c==1)
      printf("c");
    if(2<=e && e<=9)
      printf("%dx",e);
    else if(e==1)
      printf("x");
    if(2<=f && f<=9)
      printf("%di",f);
    else if(f==1)
      printf("i");
    printf("\n");
  }
    
return 0;
}

Measured memory_bytes: 608
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	static class Node {
		int id;
		Set<Integer> childrenIds = new HashSet<>();
		Set<Node> children = new HashSet<>();
		Set<Integer> subtreeInfo = new HashSet<>();
		int counter = 0;

		Node(int id) {
			this.id = id;
		}

		void genSubtreeInfo(int[] addVals, int parentVals) {
			this.counter += parentVals;
			this.counter += addVals[this.id];
			for (Node child : children) {
				child.genSubtreeInfo(addVals, this.counter);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int Q = Integer.parseInt(tokens[1]);

		Node[] tree = new Node[N];
		for (int i = 0; i < N; ++i) {
			tree[i] = new Node(i);
		}
		for (int i = 0; i < N - 1; ++i) {
			tokens = in.readLine().split(" ");
			int a = Integer.parseInt(tokens[0]) - 1;
			int b = Integer.parseInt(tokens[1]) - 1;
			tree[a].children.add(tree[b]);
		}

		int[] addVals = new int[N];
		Arrays.fill(addVals, 0);
		for (int i = 0; i < Q; ++i) {
			tokens = in.readLine().split(" ");
			int p = Integer.parseInt(tokens[0]) - 1;
			int q = Integer.parseInt(tokens[1]);
			addVals[p] += q;
		}

		tree[0].genSubtreeInfo(addVals, 0);

		StringBuilder strBuilder = new StringBuilder();
		strBuilder.append(Integer.toString(tree[0].counter));
		for (int i = 1; i < N; ++i) {
			strBuilder.append(" " + Integer.toString(tree[i].counter));
		}
		System.out.println(strBuilder.toString());
	}
}

Measured memory_bytes: 185484
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define  _CRT_SECURE_NO_DEPRECATE
using namespace std;
#define maxv 100005
#define che 1LL<<32
#define modi 1000000007
int main()
{
    ll n;
    cin>>n;
    ll i,a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    ll c=0;
    for(i=1;i<n-1;i++)
    {
        if((a[i]>a[i-1]&&a[i]<a[i+1])||(a[i]>a[i+1]&&a[i]<a[i-1]))
            c++;
    }
    cout<<c<<endl;
}

Measured memory_bytes: 256
n = int(input())
s = input()
r_list = []
g_list = []
b_set = set()
for i in range(n):
    if s[i] == "R":
        r_list.append(i)
    if s[i] == "G":
        g_list.append(i)
    if s[i] == "B":
        b_set.add(i)
def tousable(p, q):
    res = []
    if p % 2 == q % 2:
        res.append((p+q)//2)
    res.append(2*p-q)
    res.append(2*q-p)
    return res
b_length = len(b_set)
ans = 0
for i in r_list:
    for j in g_list:
        minus = 0
        for k in tousable(i, j):
            if k in b_set:
                minus += 1
        ans += b_length - minus
print(ans)


Measured memory_bytes: 73868
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

int main(){
    int a, b, c; cin >> a >> b >> c;
    int l1, l2;
    if(a*a + b*b == c*c){
        l1 = a; l2 = b;
    }
    if(b*b + c*c == a*a){
        l1 = b; l2 = c;
    }
    if(a*a + c*c == b*b){
        l1 = a; l2 = c;
    }
    cout << l1 * l2 / 2 << endl;
    return 0;
}




Measured memory_bytes: 3612
k,x = map(int,input().split())
if k==1:
  print(x)
else:
  list_ = list(range(max(-1000000,x-(k-1)),min(1000000,x+(k-1))+1))
  list_=[str(i) for i in list_]
  answer = " ".join(list_)
  print(answer)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (c >= a && c <= b)
		cout << "Yes" << "\n";
	else
		cout << "No" << "\n";
}

Measured memory_bytes: 3616
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 09/08/20 03:55:25
// -----------------------------------

#include <bits/stdc++.h>
#include <atcoder/string.hpp>

using namespace std;
using ll = long long;

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

  string s; cin>>s;
  auto sa = atcoder::suffix_array(s);
  auto lcp = atcoder::lcp_array(s, sa);
  int n = s.size();
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    if (sa[i] < n-1) {
      ans += n - sa[i] - lcp[sa[i]];
    } else {
      ans += 1;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 15612
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

typedef long long ll;
const int maxn = 200055;

ll a[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
  ll res = 0;
  ll prev_max = a[0];
  for(int i = 1; i < n; i++) {
    if(a[i] < prev_max) {
      res += prev_max - a[i];
    } else {
      prev_max = a[i];
    }
  }
  printf("%lld", res);
  return 0;
}

Measured memory_bytes: 5272
#include <iostream>
#include <cstdio>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <stdlib.h>
#include <functional>
#include <string>
#include <list>
#include <fstream>
#include <iomanip>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <nmmintrin.h>
#include <chrono>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

struct Edge {
	int from, to;
};

signed main()
{
	int n, m;
	cin >> n >> m;
	vector<int> c(n);
	REP(i, m) {
		int a, b;
		scnaf("%d %d", &a, &b);
		c[a - 1]++;
		c[b - 1]++;
	}

	for (auto itr : c) {
		if (itr % 2) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
const int maxn = 1e5 + 5;
#define INF 1000000000
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int a[maxn];
int cnt[maxn];

 int getSum(int n) 
    {  
    int sum = 0; 
    while (n != 0) 
    { 
     sum = sum + n % 10; 
     n = n/10; 
    }  
 return sum; 
 }

int countDigit(long long n) 
{ 
    int count = 0; 
    while (n != 0) { 
        n = n / 10; 
        ++count; 
    } 
    return count; 
} 
char S[110];
char T[110];

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	fastio
	string s;
	cin >> s;
	int res = 0;
	int n = s.size();
	for(int i=0; i<n; i++){
		if(s[i] != s[n-1-i]) res++;
	}
	cout << res/2 << endl; // here we are divide to overcome the double count
}






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

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

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  auto itr = unique(a.begin(), a.end());
  a.erase(itr, a.end());

  int as = a.size();
  rep(i,as) {
    cout << a[i];
    if (i==as-1) cout << endl;
    else cout << " ";
  }

  return 0;
}



Measured memory_bytes: 3088
import std;

alias P = Tuple!(double, "x", double, "y");

double radians(double deg) {
    return PI * deg / 180.0;
}

P rotate(P p, double degree) {
    auto rad = radians(degree);
    auto x = p.x * cos(rad) - p.y * sin(rad);
    auto y = p.x * sin(rad) + p.y * cos(rad);
    return P(x, y);
}

double calc(double a, double b, double h, double m) {
    auto s = rotate(P(0, a), (360 * h / 12.0) + (360 * m / 12.0 / 60.0));
    auto t = rotate(P(0, b), (360 * m / 60.0));
    return sqrt((s.x - t.x) ^^ 2 + (s.y - t.y) ^^ 2);
}

void main() {
    int a, b, h, m; scan(a, b, h, m);
    writefln("%.20f", calc(a, b, h, m));
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T=string)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readints = reads!int;


Measured memory_bytes: 3932
#include<iostream>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int H = 16;
const int W = 16;

int M[H][W];

struct state{
  int i,j;
  int food;
  int hp;
  int cost;
  state(int i, int j, int food, int hp, int cost):i(i),j(j),food(food),hp(hp),cost(cost){}
  bool operator<(const state &t)const{
    if(i!=t.i)return i<t.i;
    if(j!=t.j)return j<t.j;
    if(food!=t.food)return food<t.food;
    if(hp!=t.hp)return hp<t.hp;
    if(cost!=t.cost)return cost<t.cost;
    return false;
  }
};


const int di[] = {0,-1,0,1,0};
const int dj[] = {0,0,1,0,-1};
const int inf = 1<<22;

bool inside(int i, int j, int h, int w){
  return 0<=i&&i<h&&0<=j&&j<w;
}

int solve(int h, int w){
  int si, sj, gi, gj;
  int fid = 0;
  int ret = inf;
  set<state> vis;
  map<pair<int,int>,int> food_conv;
  map<int,pair<int,int> > food_rev;
  
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if( M[i][j] == 2 ){
        si = i;
        sj = j;
      }else if( M[i][j] == 3 ){
        gi = i;
        gj = j;
      }else if( M[i][j] == 4 ){
        food_conv[make_pair(i,j)] = fid;
        food_rev[fid] = make_pair(i,j);
        ++fid;
      }
    }
  }
  state init(si,sj,0,6,0);

  queue<state> q;
  for(q.push(init); !q.empty(); q.pop()){
    state cur = q.front();

    // if( cur.hp == 0 ) continue;

    if( cur.i == gi && cur.j == gj ){
      ret = min(ret, cur.cost );
    }

    if( vis.find(cur) == vis.end() ) vis.insert(cur);
    else continue;

    for(int k = 0; k < 5; ++k){
      int ni = cur.i + di[k];
      int nj = cur.j + dj[k];
      
      if( inside(ni,nj,h,w) && M[ni][nj] != 0 ){
        int nhp = cur.hp - 1;
        int nfood = cur.food;

        if( nhp > 0 ){

          if( M[ni][nj] == 4 ){
            int fid = food_conv[make_pair(ni,nj)];
            if( !(cur.food & (1<<fid)) ){
              nhp = 6;
              nfood |= 1<<fid;
            }
          }
          int ncost = cur.cost + 1;
          q.push(state(ni,nj,nfood,nhp,ncost));
        }
      }
    }
  }

  
  return ret==inf?-1:ret;
}

int main()
{
  int w,h;
  while( cin >> w >> h ){
    if( w == 0 && h == 0 ) break;
    
    for(int i = 0; i < h; ++i){
      for(int j = 0; j < w; ++j){
        cin >> M[i][j];
      }
    }
    
    cout << solve(h,w) << endl;
  }  
  return 0;
}

Measured memory_bytes: 3628
#include<cstdio>
#include<algorithm>
const int N=1000007;
char s[N],t[N];int n,ans,sum[N];
int main()
{
    scanf("%d%s%s",&n,s+1,t+1);
    if(s[1]^t[1]) return !printf("-1");
    for(int i=n,f=0,k=0,p=n;i;--i)
    {
	f+=sum[i+k];
	if(p>i||t[i]^s[p])
        {
	    for(;p>0&&(p>i||t[i]^s[p]);--p);
	    if(p==i) continue;
	    if(p<=0) return !printf("-1");
	    ++k,++f,sum[i+k-1]=0,--sum[p+k-1];
        }
	ans=std::max(ans,f);
    }
    printf("%d",ans);
}


Measured memory_bytes: 5888
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
  int i,x,n,m[1000],to=0,min;
  scanf("%d %d",&n,&x);
  for(i=0;i<n;i++){
    scanf("%d",&m[i]);
    to+=m[i];
  }
  min=m[0];
  for(i=1;i<n;i++){
    if(min>m[i])
    min=m[i];
  }
  x=x-to;

printf("%d\n",n+x/min );
}


Measured memory_bytes: 128
#! python3
# disjoint_set_union_find_tree.py

class UnionFindTree():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n, q = [int(x) for x in input().split(' ')]
uft = UnionFindTree(n-1)

for i in range(q):
    com, x, y = [int(x) for x in input().split(' ')]
    if com == 0:
        uft.unite(x, y)
    elif com == 1:
        if uft.same_check(x, y):
            print(1)
        else:
            print(0)



Measured memory_bytes: 6048
n = int(input())
t, a = tuple(map(int, input().split()))
h = list(map(int, input().split()))

def temp(x):
    return t - x * 0.006

mine = 100000
mini = 0
for i in range(n):
    if abs(a - temp(h[i])) < mine:
        mine = abs(a - temp(h[i]))
        mini = i

print(mini + 1)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 1e6+5;
string s[66];
int a[66];
void solve(){
	int n; 
	cin>>n; 
	for(int i=1;i<=n;i++)cin>>s[i]>>a[i];
	int ans = 0;
	string tar; 
	cin>>tar; 
	bool can = false;
	for(int i=1;i<=n;i++){
		if(can)ans+=a[i];
		if(s[i]==tar)can = true;
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fi > xed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) {  //最小値更新 返り値はbool
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

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

  int n, x;
  cin >> n >> x;
  stack<int> st;
  int ans = 0;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if (i != 0) {
      int now = st.top();
      if (now + a > x) {
        ans += (now + a) - x;
        a = max(a - (now + a - x), (int)0);
        st.push(a);
      } else
        st.push(a);
    } else
      st.push(a);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 4028
#include <iostream>
#include <algorithm>
#include <map>
#include <utility>

using namespace std;
int n, m, a[100005];
map<int, int> mp;

int main()
{
    cin >> n >> m;
    long long rj = 0, s = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        s = (s + a[i]) % m;
        if (s == 0)
            ++rj;
        if (mp.find(s) != mp.end())
            rj += mp[s];
        ++mp[s];
    }
    cout << rj << endl;
    return 0;
}

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

int main(){
  int H, W;
    
    while(1){
      cin >> H >> W;
      if ( H == 0 && W == 0 ) break;
      
        for ( int i = 0; i < H; i++ ){
            for ( int j = 0; j < W; j++ ){
                if ( (i + j) % 2 == 0 ){
                 cout << "#";
                } else {
            cout << ".";
        }
    }
    cout << "\n";
}
    cout << endl;
   }
     return 0;
}

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

int main() {
  string N;
  cin>>N;
  vector<string> a(7);
  a[0]="SUN";
  a[1]="MON";
  a[2]="TUE";
  a[3]="WED";
  a[4]="THU";
  a[5]="FRI";
  a[6]="SAT";
  for(int i=0; i<7;i++){
    if(N == a[i])
      cout<<7-i<<endl;
  }
}

Measured memory_bytes: 256
S = [0] + list(map(int, list(input())))
N = len(S) - 1

def change(s, c):
  if c == 0:
    return s
  else:
    return 1 - s

def check(k):
  count = [0] * (N+1)
  T = S.copy()
  for i in range(1, N+1):
    c = count[i-1]
    s = change(S[i], c)
    if i < N - k + 2:
      T[i] = 0
      if s == 1:
        count[i] = (c + 1) % 2
      else:
        count[i] = c        
    else:
      T[i] = s
      count[i] = c      
  n = 0
  for t in T[1:]:
    if t == 1:
      break
    n += 1
  return n >= k


left = 1 # True
right = N
while left + 1 < right:
  mid = (left + right) // 2
  if check(mid):
    left = mid
  else:
    right = mid

if right == N and check(N):
  print(N)
else:
  print(left)

Measured memory_bytes: 6232
#include <cstdio>
typedef long long ll;

int n,x[205],y[205],p[205],Ans;
const int P=998244353;

int main()
{
    scanf("%d",&n);
    for(int i=p[0]=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]),p[i]=(p[i-1]<<1)%P;
    Ans=(p[n]-n-1+P)%P;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            int d=0;
            for(int k=j+1;k<=n;++k)
                d+=(y[i]-y[j])*(x[i]-x[k])==(y[i]-y[k])*(x[i]-x[j]);
            Ans=(Ans+P-p[d])%P;
        }
    printf("%d\n",Ans);
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
favo=[0]*m
k=[0]*n
for i in range(n):
  k[i]=[list(map(int,input().split()))]
  #print(k[i][0][0])
  for j in range(1,k[i][0][0]+1):
    favo[k[i][0][j]-1]+=1
    
ans=0
for i in range(m):
  if (favo[i]==n):
    ans+=1
#print(favo)
print(ans)

Measured memory_bytes: 3316