akhauriyash/Code-Regression huggingface dataset:
H,W = [int(i) for i in input().split()]
maze = ['0'] * H
for i in range(H):
    maze[i] = list(input())
dx = [1,0,-1,0]
dy = [0,1,0,-1]
import collections
from collections import deque
que = deque()
dic = [[-1] * (W) for _ in range(H)]
dic[0][0] = 0
que.append([0,0])
while (len(que) != 0):
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= H or ny < 0 or ny >= W:
            continue
        if maze[nx][ny] == "#" :
            continue
        if dic[nx][ny] == -1:
            que.append([nx,ny])
            dic[nx][ny] = dic[x][y] +1
ml = dic[H-1][W-1]
count = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            count+=1
if ml == -1:
    print(-1)
else :
    print(count - ml - 1)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int Random(int mi,int ma){
    random_device rnd;
    mt19937 mt(rnd());//32bit
    //[mi,ma]
    uniform_int_distribution<int>engine(mi,ma);
    return engine(mt);
}
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<int>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
int comb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
int n,a[100010];
signed main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>n;
    rep(i,n)cin>>a[i];
    sort(a,a+n,greater<int>());
    if(a[n-1]==0){
        cout<<0<<endl;
        return 0;
    }
    int ans=1;
    rep(i,n){
        if(a[i]>1000000000000000000/ans){
            cout<<-1<<endl;
            return 0;
        }
        ans*=a[i];
    }
    if(ans>1000000000000000000)cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}

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

using namespace std;

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

	int n;
	cin >> n;
	long long ans = 0;
	map<vector<int>, int> mapchik;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		vector<int> cnt(26);
		for (char c : s) {
			++cnt[c - 'a'];
		}
		ans += mapchik[cnt]++;
	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 19072
V,E,r = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(E)]
dp = [float("INF")]*(V)
dp[r] = 0
cnt = 0
while True:
    cnt += 1
    if cnt > V:
        print("NEGATIVE CYCLE")
        exit()
    flag = False
    for s,t,d in edges:
        if dp[t] > dp[s]+d:
            dp[t] = dp[s]+d
            flag = True
    if not flag:
        break
for c in dp:
    if c == float("INF"):
        print("INF")
    else:
        print(c)



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

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

	vector<int> vec(n, 0);
	bool f = true;
	for (int i = 0; i < m; i++) {
		int s, c;
		cin >> s >> c;

		if (vec.at(s - 1) == 0 || vec.at(s - 1) == c) {
			vec.at(s - 1) = c;
			if (n == 3) {
				if (s == 1 && c == 0) {
					f = false;
				}
			}
			if (n == 2) {
				if (s == 1 && c == 0) {
					f = false;
				}
			}
		}
		else {
			f = false;
			break;
		}
	}

	if (f) {
		if (n == 3 && vec.at(0) == 0) {
			vec.at(0)++;
		}
		if (n == 2 && vec.at(0) == 0) {
			vec.at(0)++;
		}

		for (auto& e : vec) {
			cout << e;
		}
	}
	else
	{
		cout << -1;
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int dp[3][2017][2017], n, m;//I, O, -
string S, T;
int main() {
	cin >> n >> m >> S >> T;
	for (int i = 0; i < 2017; i++) { for (int j = 0; j < 2017; j++) { for (int k = 0; k < 3; k++)dp[k][i][j] = -998244353; } }
	dp[2][0][0] = 0;
	for (int i = 0; i <= S.size(); i++) {
		for (int j = 0; j <= T.size(); j++) {
			if (i != S.size()) {
				if (S[i] == 'I') {
					dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[1][i][j] + 1);
					dp[0][i + 1][j] = max(dp[0][i + 1][j], dp[2][i][j] + 1);
					dp[2][i + 1][j] = max(dp[2][i + 1][j], dp[2][i][j]);
				}
				if (S[i] == 'O') {
					dp[1][i + 1][j] = max(dp[1][i + 1][j], dp[0][i][j] + 1);
					dp[2][i + 1][j] = max(dp[2][i + 1][j], dp[2][i][j]);
				}
			}
			if (j != T.size()) {
				if (T[j] == 'I') {
					dp[0][i][j + 1] = max(dp[0][i][j + 1], dp[1][i][j] + 1);
					dp[0][i][j + 1] = max(dp[0][i][j + 1], dp[2][i][j] + 1);
					dp[2][i][j + 1] = max(dp[2][i][j + 1], dp[2][i][j]);
				}
				if (T[j] == 'O') {
					dp[1][i][j + 1] = max(dp[1][i][j + 1], dp[0][i][j] + 1);
					dp[2][i][j + 1] = max(dp[2][i][j + 1], dp[2][i][j]);
				}
			}
		}
	}
	int maxn = 0;
	for (int i = 0; i <= S.size(); i++) { for (int j = 0; j <= T.size(); j++)maxn = max(maxn, dp[0][i][j]); }
	cout << maxn << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

int popcount(ll x) {x = x&0x5555555555555555ULL+(x&0xAAAAAAAAAAAAAAAAULL>>1);x=x&0x3333333333333333ULL+(x&0xCCCCCCCCCCCCCCCCULL>>2);x=x&0x0F0F0F0F0F0F0F0FULL+(x&0xF0F0F0F0F0F0F0F0ULL>>4);return x*0x0101010101010101ULL>>56;}

ll N, K, L, R;
ll a[40];

auto enumerate(int sidx, int size) {
  vector<pair<ll, ll>> ret;
  for(int i=0; i<1<<size; i++) {
    if(popcount(i) > K) continue;
    int cnt = 0; ll sum = 0;
    for(int j=0; j<size; j++)
      if(i >> j & 1) cnt++, sum += a[sidx + j];
    ret.emplace_back(cnt, sum);
  }
  return ret;
}

ll solve() {
  auto v0 = enumerate(0, N / 2);
  auto v1 = enumerate(N / 2, (N + 1) / 2);
  sort(v0.begin(), v0.end());
  ll ret = 0;
  for(int i=0; i<(int)v1.size(); i++)
    ret +=  upper_bound(v0.begin(), v0.end(), make_pair(K - v1[i].first, R - v1[i].second))
          - lower_bound(v0.begin(), v0.end(), make_pair(K - v1[i].first, L - v1[i].second));
  return ret;
}

int main() {
  cin >> N >> K >> L >> R;
  for(int i=0; i<N; i++) cin >> a[i];
  cout << solve() << endl;
  return 0;
}

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

int w,h, HL,WL;
int area[70][70];

struct P{
  int x,y;
  int t;
  P(){};
  P(int i,int j){x=i;y=j;t=0;}
  P(int i,int j,int nt){x=i;y=j;t=nt;}
};

void pr(){
  for( int i=0;i<HL;i++ ){
    for( int j=0;j<WL;j++ )
      cout << area[i][j] << " ";
    cout << endl;
  }
}

int main(){
  queue<P> q;
  P p;
  while( cin>>w>>h &&(w|h) ){
    // cout << "  h="<<h << " w="<<w<<endl;

    HL=2*h+1;
    WL=2*w+1;
    for( int i=0;i<HL;i++ ){
      for( int j=0;j<WL;j++ ){
	if( i==0 || j==0 || i==HL-1 || j==WL-1 )
	  area[i][j]=1;
	else
	  area[i][j] = 0;
      }
    }

    for( int i=1;i<HL-1;i++ ){
      if( i & 0x01 ){ // odd
	for( int j=1;j<w;j++ )
	  cin >> area[i][2*j];
      }else{
	for( int j=0;j<w;j++ )
	  cin >> area[i][2*j+1];
      }
    }

    while( !q.empty() ) q.pop();
    q.push( P(1,1) );
    int ans=0;
    while( !q.empty() ){
      p=q.front(); q.pop();
      int x=p.x, y=p.y, t=p.t, nt=t+1;

      if( area[x][y]==1 ) continue;

      if( x==2*h-1 && y==2*w-1 ){
	ans=t+1; break;
      }
      area[x][y]=1;
      if( area[x+1][y]==0 ) q.push( P(x+2,y,nt) );
      if( area[x-1][y]==0 ) q.push( P(x-2,y,nt) );
      if( area[x][y+1]==0 ) q.push( P(x,y+2,nt) );
      if( area[x][y-1]==0 ) q.push( P(x,y-2,nt) );
    }
    cout << ans << endl;

  }

  return 0;
}

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

int n, a[20], x[20][20], y[20][20];

int counter(int rep) {
	return rep == 0 ? 0 : counter(rep >> 1) + (rep & 1);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		for (int j = 1; j <= a[i]; j++) {
			cin >> x[i][j] >> y[i][j];
		}
	}
	int ans = 0;
	for (int b = 1; b < (1 << n); b++) {
		bool ok = true;
		for (int i = 1; i <= n; i++) {
			if (!(b & (1 << i - 1)))continue;
			for (int j = 1; j <= a[i]; j++) {
				if ((b >> (x[i][j] - 1) & 1) ^ y[i][j])ok = false;
			}
		}
		if (ok)if (ans < counter(b))ans = counter(b);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	const int MAX_N = 20;
	int n;
	int h[MAX_N];
	int ans = 0;
	int max = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		if (h[i] >= max) {
			max = h[i];
			ans++;
		}
	}

	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N = 103000;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =    1e9+7;
int n;
int fact[N];
int arr[N];
ll ifact[N];
ll po(ll x,ll y)
{
	ll res=1;
	while(y)
	{
		if(y%2)
		res=res*x%mod;
		y/=2;
		x=x*x%mod;
	}
	return res;
}
int ncr(int a,int b)
{
	return 1ll*(((fact[a]*ifact[b])%mod)*ifact[a-b])%mod;
}
int main()
{  fast
  fact[0]=1;
  for(int i=1;i<N;i++)
  fact[i]=1ll*fact[i-1]*i%mod;
  ifact[N-1]=po(fact[N-1],mod-2);
  for(int i=N-2;i>=0;i--)
  	ifact[i]=ifact[i+1]*(i+1)%mod;
  	   cin>>n;
  	   int y;
  for(int i=1;i<=n+1;i++)
  {
  	int x;
  	cin>>x;
  	if(arr[x])
	y=n+1-(i-arr[x]+1);
	else
	arr[x]=i;
  }
  for(int i=1;i<=n+1;i++)
  {
  	int res=ncr(n+1,i);
  	if(y>=i-1)
  	res-=ncr(y,i-1);
  	res=(res+mod)%mod;
  	cout<<res<<endl;
  }
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n,m,fx,fy,tx,ty,dist[1010][1010],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
string s[1010];
deque <pair <int,pii> > q;

bool out(int x,int y)
{
	return x<0||x>=n|y<0||y>=m;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>fx>>fy>>tx>>ty;
	fx--;
	fy--;
	tx--;
	ty--;
	rep(i,n) cin>>s[i];
	rep(i,1005) rep(j,1005) dist[i][j]=1e9;
	dist[fx][fy]=0;
	q.pb(mpr(0,mpr(fx,fy)));
	while(!q.empty())
	{
		pair <int,pii> p=q.front();
		q.pop_front();
		rep(i,4)
		{
			int x=p.se.fi+dx[i],y=p.se.se+dy[i];
			if(out(x,y)||s[x][y]=='#'||dist[x][y]<=p.fi) continue;
			dist[x][y]=p.fi;
			q.push_front(mpr(p.fi,mpr(x,y)));
		}
		for(int i=p.se.fi-2;i<=p.se.fi+2;i++) for(int j=p.se.se-2;j<=p.se.se+2;j++)
		{
			if(out(i,j)||s[i][j]=='#'||dist[i][j]<=p.fi+1) continue;
			dist[i][j]=p.fi+1;
			q.pb(mpr(p.fi+1,mpr(i,j)));
		}
	}
	if(dist[tx][ty]>1e8) cout<<-1<<endl;
	else cout<<dist[tx][ty]<<endl;
	return 0;
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
#define int long long
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define PI (acos(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define MOD 1000000007
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using Complex = complex<double>;


string S;
string T;
char m[30];
char im[30];


int toi(char c){
    return c-'a';
}


bool solve(){
    rep(i, 0, SIZE(S)){
        int s = toi(S[i]);
        int t = toi(T[i]);
        if(!m[s]) m[s] = T[i];
        else if(m[s] != T[i]) return false;
        if(!im[t]) im[t] = S[i];
        else if(im[t] != S[i]) return false;
    }
    return true;
}


signed main(){
    cin >> S;
    cin >> T;

    if(solve()) Yes;
    else No;

    return 0;
}

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

using namespace std;

string to_six_digits(int data){
  char ret[6];
  for(int i = 0; i < 6; i++){
    ret[5 - i] = data % 10 + 48;
    data /= 10;
  }
  string ret_str(ret, 6);
  return ret_str;
}

int main(){
  int n, m; cin >> n >> m;
  vector<pair<pair<int, int>, int>> city(m);
  for(int i = 0; i < m; i++){
    int p, y;
    cin >> p >> y;
    city[i] = make_pair(make_pair(p, y), i);
  }
  
  sort(city.begin(), city.end());
  
  vector<pair<int, string>> result(m);
  int pre_prefecture = city[0].first.first;
  string pre_prefecture_id = to_six_digits(pre_prefecture);
  int x = 1;
  result[0] = make_pair(city[0].second, pre_prefecture_id + to_six_digits(x));
  for(int i = 1; i < m; i++){
    if(city[i].first.first == city[i - 1].first.first){
      x++;
    }else{
      pre_prefecture = city[i].first.first;
      pre_prefecture_id = to_six_digits(pre_prefecture);
      x = 1;
    }
    result[i] = make_pair(city[i].second, pre_prefecture_id + to_six_digits(x));
  }
  
  sort(result.begin(), result.end());
  
  for(int i = 0; i < m; i++){
    cout << result[i].second << endl;
  }
  
  return 0;
}


Measured memory_bytes: 8960
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

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

		while (scan.hasNext()) {
			String str = scan.nextLine();

			for (int i = 0; i < 26; i++) {
				String dec = shift(str, i);
				List<String> words = Arrays.asList(dec.split("[^a-z]"));
				if (words.contains("the") || words.contains("this") || words.contains("that")) {
					System.out.println(dec);
					break;
				}
			}
		}
		scan.close();
	}

	private static String shift(String in, int n) {
		StringBuilder sb = new StringBuilder("");

		for (char c : in.toCharArray()) {
			if ('a' <= c && c <= 'z') {
				c += n;
				if (c > 'z') {
					c -= (char) 26;
				}
			}
			sb.append(c);
		}
		return sb.toString();
	}
}

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

vector<long long> divisors(long long n) {
  vector<long long> res;
  for (int i = 1; i < int(sqrt(n)) + 1; i++) {
    if (n % i == 0) {res.push_back(i); res.push_back(n / i);}
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n; cin >> n;
  auto res = divisors(n);
  int m = res.size();
  cout << res[m-1] + res[m-2] - 2 << '\n';
  return 0;

}

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

template <typename T>
T calc_gcd(T x, T y)
{
    if (x < y)
    {
        swap(x, y);
    }
    T remain = x % y;
    while (remain != 0)
    {
        x = y;
        y = remain;
        remain = x % y;
    }
    return y;
}

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

    long long ans = 0;
    for (long long i = 1; i <= K; i++)
    {
        for (long long j = 1; j <= K; j++)
        {
            for (long long k = 1; k <= K; k++)
            {
                ans += calc_gcd(calc_gcd(i, j), k);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Abc
{
    class B_165_1percent
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            long n = long.Parse(Console.ReadLine());
            long i = 0;
            long result = 100;

            while(result < n)
            {
                i++;
                result += result / 100;
            }


            Console.WriteLine(i);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27488
#include<iostream>

using namespace std;

int main()
{
    long long A,B,K;cin >>A>>B>>K;

    if(A>=K) cout << A-K << " " << B;
    else if(A+B>=K)
    {
        cout << 0 << " "<<B-(K-A)<<endl; 
    }else
    {
         cout << 0 << " " <<0<<endl;
    }
    
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG //エラーを出すためのおまじない
#include <bits/stdc++.h>
//#include <cstdlib>  // abs() for integer
#include <cmath>    // abs() for float, and fabs()
#include <math.h>
using namespace std;
#define coYES cout << "YES" << endl
#define coNO cout << "NO" << endl
#define coYes cout << "Yes" << endl
#define coNo cout << "No" << endl
#define coyes cout << "yes" << endl
#define cono cout << "no" << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int k;
  cin >> k;
  vector<int> a(k+100);
  a.at(0) = 0;
  a.at(1) = 7 % k;
  bool flag = true;
  for (int i = 2; i < k+1; i++) {
    a.at(i) = (a.at(i-1)*10 + 7)%k;
  }
  for (int i = 1; i < k+1; i++) {
    if (a.at(i) == 0) {
      cout << i << endl;
      flag = false;
      break;
    }
  }
  if (flag) {
    cout << -1 << endl;
  }
}
 

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

int main(){

    ll a,b,k;

    cin >> a >>b >>k;

    if(b-a+1<=k*2){
        rep(i,b-a+1){
            cout << i+a << endl;
        }
    }else{
        rep(i,k){
            cout << i+a << endl;
        }
        rep(i,k){
            cout << b-k+i+1 << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
bulbs = []
for _ in range(M):
    b = tuple(map(int, input().split()))
    bulbs.append(b[1:])
P = list(map(int, input().split()))

ans = 0
for switch in range(2**N):
    check = [False] * M
    for i ,bulb in enumerate(bulbs):
        count = 0
        for b in bulb:
            if switch >> (b-1) & 1:
                count += 1
        if count % 2 ==P[i]:
            check[i] = True
        else:
            check[i] = False
    if all(check):
        ans += 1
print(ans)

Measured memory_bytes: 73856
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, a, b, c, d;
  string op;
  cin >> N;
  
  a = N / 1000;
  b = (N - a*1000) / 100;
  c = (N - a*1000 - b*100) / 10;
  d = N - a*1000 - b*100 - c * 10;
  
  if ((a==b && a==c) || (b==c && c==d)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3580
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


N, M, Q = map(int, input().split())
sects = []
for _ in range(M):
    sects.append([0] + list(map(int, input().split())))
for q in range(Q):
    sects.append([1] + list(map(int, input().split())) + [q])

sects.sort(key=lambda x: x[2])
b = Bit(N)
ans = []
for s in sects:
    if s[0] == 0:
        b.add(s[1], 1)
    else:
        ans.append((b.sum(s[2]) - b.sum(s[1] - 1), s[3]))
ans.sort(key=lambda x: x[1])
for x in ans:
    print(x[0])


Measured memory_bytes: 66944
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
    int a,b,c;
    double cr,S,L,H;
    cin >> a >> b >> c;
    cr=(acos(-1.0)*c)/180.0;
    S=0.5*a*b*sin(cr);
    L=a+b+sqrt(a*a+b*b-2*a*b*cos(cr));
    H=b*sin(cr);
    
    printf("%lf\n%lf\n%lf\n",S,L,H);
    
    return 0;
}


Measured memory_bytes: 3596
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end

s = gets.chomp
t = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
t.each.with_index do |ss,i|
  if ss == s
    p 7-i
  end
end


#777


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

using namespace std;

#define show(x) cerr << #x << " = " << x << endl;

int main()
{
  string a, b, c;

  cin>>a>>b>>c;

  bool AB = (a[a.size()-1] == b[0])? true: false;
  bool BC = (b[b.size()-1] == c[0])? true: false;

  if(AB && BC)
  {
    cout<<"YES"<<endl;
  }
  else
  {
    cout<<"NO"<<endl;
  }


  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <cstdio>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map> //pair is also included in this library
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define fst first
#define snd second
#define MP make_pair //incase c++11 or later is not available

using namespace std;

typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//prefer define statement
//for reason that const int ver. of INF will raise a silly warning (unused variable)
#define INF (INT_MAX/3)
#define LIM_INF (INT_MAX)
//const int INF = INT_MAX/3;
#define PI = 3.14159265358979323846
/*------------------------------------------------------------------------------*/

int main(){
  int N;
  cin >> N;
  VI A(pow(10, 5), 0);

  REP(i, 0, N){
    int tmp;
    cin >> tmp;
    A[tmp]++;
  }

  int ans = N;
  int lb = 0, ub = pow(10, 5) - 1;
  while(lb <= ub){
    if(A[lb] < 2){
      lb++;
      continue;
    }
    if(A[ub] < 2){
      ub--;
      continue;
    }    
    A[lb]--;
    A[ub]--;
    ans -= 2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 768
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A_sum=0
for i in range(N):
   if A[i]>B[i]:
      A_sum+=A[i]-B[i]
   elif A[i]<B[i]:
      A_sum-=(B[i]-A[i])//2
if A_sum<=0:
   print("Yes")
else:
   print("No")


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

int main() {
  
  int A, B, t = 0;
  cin >> A >> B;
  
  for (int i = A; i <= B; i++) {
    if (i%10 == i/10000%10 && i/10%10 == i/1000%10) t ++;
  }
  cout << t << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define eb 			emplace_back
#define mp 			make_pair
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          first
#define si          second
#define sz(x)       (ll)x.size()
#define endl        '\n'
#define checkbit(n, b) ((n >> b) & 1)
#define mod        1000000007
#define inf        1000000000000000000
#define puts(n)		cout<<n;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define setbits(x) __builtin_popcount(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
vi dx = {1,-1,0,0};
vi dy = {0,0,1,-1};
ll n,m,k;
bool valid(ll x,ll y){
	if(x>=0 && x<n && y>=0 && y<m) return true;
	return false;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	ll x1,x2,y1,y2;
	cin>>x1>>y1>>x2>>y2;
	x1--;x2--;y1--;y2--;
	string s[n];
	ll dis[n][m]={};
	for(ll i=0;i<n;i++){
		cin>>s[i];
		for(ll j=0;j<m;j++){
			if(s[i][j]=='.') dis[i][j]=inf;
		}
	}
	queue<pii> q;
	q.push({x1,y1});
	dis[x1][y1]=0;
	while(q.size()){
		pii x=q.front();
		q.pop();
		for(ll d=0;d<4;d++){
			for(ll i=1;i<=k;i++){
				ll a=x.first+dx[d]*i,b = x.second+dy[d]*i;
				if(!valid(a,b)) break;
				if(dis[a][b]<=dis[x.first][x.second]) break;
				if(dis[a][b]!=dis[x.first][x.second]+1){
					dis[a][b] = dis[x.first][x.second]+1;
					q.push({a,b});
				}
			}
		}
	}
	if(dis[x2][y2]==inf) cout<<"-1";
	else cout<<dis[x2][y2];
	
	return 0;
}

Measured memory_bytes: 14144
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		boolean[] color = new boolean[8];
		int topcoder = 0;
		int ans = 0;
		for(int i = 0; i < N; i++) {
			int rate = sc.nextInt();
			for(int j = 1; j <= 8; j++) {
				if(rate < j*400) {
					color[j-1] = true;
					break;
				}
			}
			if(rate >= 3200)
				topcoder += 1;
		}
		for(int i = 0; i < 8; i++) {
			if(color[i])
				ans ++;
		}
      	if(ans == 0){
          	System.out.println(1 + " " + topcoder);
              return;
        }
		System.out.println(ans + " " + (ans+topcoder));
	}

}


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

int main(){
    int A,B,C,D,E,F;
    cin >> A >> B >> C >> D >> E >> F;
    double ans=-1;
    int x=0,y=0;
    for(int t=0;100*A*t<=F;t++){
        for(int i=0;100*B*i<=F-100*A*t;i++){
            for(int u=0;u*C<=F-100*(A*t+B*i);u++){
                for(int v=0;v*D<=F-100*(A*t+B*i)-u*C;v++){
                    if(v*D+u*C<=E*(A*t+B*i)){
                        if(ans<(double)100*(u*C+v*D)/(100*(A*t+B*i)+u*C+v*D)){
                            ans=(double)100*(u*C+v*D)/(100*(A*t+B*i)+u*C+v*D);
                            x=u*C+v*D;
                            y=100*(A*t+B*i)+u*C+v*D;
                        }
                    }
                }
            }
        }
    }
    cout << y << " " << x << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
    #pragma comment(linker, "/stack:200000000")
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    #include<bits/stdc++.h>
    #define int long long
    # define mo 1000000007
    using namespace std;
    #define goku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    signed main(){
        goku
     int n,m;
     cin>>n>>m;
     if(n==m)
        cout<<"Yes"<<endl;
     else
        cout<<"No"<<endl;
    }


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
INF = 10**9
MOD = 10**9+7

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
print(len([x for x in h if x >= K]))


Measured memory_bytes: 12272
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

#define _ cin.tie(0);ios::sync_with_stdio(false);
int n;
int main(){ _;
  cin>>n;
  V a(n*3);
  REP(i,3*n) cin>>a[i];
  sort(a.begin(),a.end(),std::greater<int>());
  llong ans=0;
  REP(i,n)
    ans+=a[1+2*i];

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define watch(x) cout<<(#x)<<" is "<<(x)<<endl;
#define mod 1000000007
#define pb push_back
#define endl '\n'

int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cout.tie(0);
	
	
	long long h;
	cin>>h;

	int count =0;
	while(h)
	{
		count++;
		h/=2;

	}

	long long ans = pow(2,count)-1;
	cout<<ans<<endl;



}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#define INF 1000000007
using namespace std;

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


int main() {

	char d[4];
	cin >> d;

	int a = 0, c = 0, b = 0;

	for (int i = 0; i < 4; i++) {
		if (d[i] == 'a') {
			a += 1;
		}
		else if (d[i] == 'b') {
			b += 1;
		}
		else if (d[i] == 'c') {
			c += 1;
		}
	}

	if (a == 1 && b == 1 && c == 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}




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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

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

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t;  cin >> s >> t;
    ll lens = s.size();
    ll lent = t.size();
    if (lens < lent) {
      cout << "LESS" << '\n';
    } else if (lens > lent) {
      cout << "GREATER" << '\n';
    } else {
      if (s < t) {
        cout << "LESS" << '\n';
      } else if (s > t) {
        cout << "GREATER" << '\n';
      } else {
        cout << "EQUAL" << '\n';
      }
    }

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll mod = 998244353LL;

// aのb乗を求める.
ll modpow(ll a, ll b) {
	if (a > mod) a %= mod;
	if (b == 0LL) return 1LL;
	ll tmp = modpow(a, b / 2);
	if (b & 1LL)
		return tmp * tmp % mod * a % mod;
	return tmp * tmp % mod;
}

// aの逆元を求める.
ll inverse(ll a) {
	return modpow(a, mod - 2);
}

// kの階乗を計算する.(sgnを0以外に設定すると逆元を返す)
ll fact(ll k, int sgn = 0) {
	static vector<ll> fac(2, 1LL);
	static vector<ll> inv(2, 1LL);
	static vector<ll> finv(2, 1LL);
	static ll nx = 2LL;
	while (nx <= k) {
		fac.push_back(fac[nx - 1] * nx % mod);
		inv.push_back(mod - inv[mod % nx] * (mod / nx) % mod);
		finv.push_back(finv[nx - 1] * inv[nx] % mod);
		++nx;
	}
	if (sgn == 0)
		return fac[k];
	return finv[k];
}

// aCbを計算する.
ll comb(ll a, ll b) {
	if (b < 0 || b > a) return 0;
	return fact(a) * fact(b, 1) % mod * fact(a - b, 1) % mod;
}

signed main() {
	ll n; cin >> n;
	ll ans = modpow(3, n);
	for (ll i = (n / 2) + 1; i <= n; ++i) {
		ans -= modpow(2, n - i) * comb(n, i) % mod * 2 % mod;
		ans += mod;
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 267792
#include<stdio.h>
int main()
{
  int a,x,y;
  while(1){
    scanf("%d %d",&x,&y);
    if(x==0&&y==0)break;
    if(x>y){
      a=x;
      x=y;
      y=a;
    }
    printf("%d %d\n",x,y);
  }
  return 0;
}

Measured memory_bytes: 600
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

int n;
vector<int> kr[100005];
const long long mod = 1000000007;
long long whites[100005];
long long blacks[100005];

void DFS(int x, int par){
    whites[x] = 1LL;
    blacks[x] = 1LL;
    for(int i = 0; i < kr[x].size(); i++){
        if(kr[x][i] != par){
            DFS(kr[x][i], x);
            whites[x] *= (whites[kr[x][i]] + blacks[kr[x][i]]);
            whites[x] %= mod;
            blacks[x] *= whites[kr[x][i]];
            blacks[x] %= mod;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        kr[a].push_back(b);
        kr[b].push_back(a);
    }
    DFS(1, 0);
    printf("%lld\n", (whites[1] + blacks[1])%mod);
    return 0;
}


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

ll int combination(ll int n) {
  return n * (n - 1) / 2;
}

int main() {
  int n;
  cin >> n;
  vector<int> inputs(n + 10);
  vector<ll int> num(n + 10);
  vector<ll int> answers(n + 10);
  ll int all = 0;
  
  rep(i, n) {
    int a;
    cin >> a;
    ++num[a];
    inputs[i] = a;
  }
  
//  cout << "answers" << endl;
  rep(i, n + 1) {
//    cout << "num:" << num[i] << endl; 
    if(num[i] != 0) {
      answers[i] = combination(num[i]) - combination(num[i] - 1);
      all += combination(num[i]);
//      cout << answers[i] << endl;
    }
  }
  
//  cout << all << endl;
  
  rep(i, n) {
    cout << all - answers[inputs[i]] << endl;
  }
  
  return 0;
}


Measured memory_bytes: 6528
import java.util.Scanner;

public class Main {
	    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        
        String s = in.nextLine();
        s = in.nextLine();
        int counter = 0;
        int overseasCounter = 0;
        
        
        for (int x = 0; x < s.length(); x++){
        	if (s.charAt(x) == 'c'){
        		System.out.println("No");
        	} else {
        		if (s.charAt(x) == 'a' && counter < a + b){
        			System.out.println("Yes");
        			counter++;
        		} else if (s.charAt(x) == 'b' && counter < a + b  && overseasCounter < b){
        			System.out.println("Yes");
        			counter++;
        			overseasCounter++;
        		} else {
        			System.out.println("No");
        		}
        	}
        }        
        in.close();
    }
}


Measured memory_bytes: 23940
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char c = sc.next().charAt(0);
        c++;
        System.out.println(c);
    }
}


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

using namespace std;
//38 000.0 1.0 bc
//x yen    y bc
//x = 38 000.0 * y / 1. 0


int main() {
	int n;
	double x;
	string s;
	double res = 0.0;
	cin >> n;
	while (n--){
		cin >> x >> s;
		if (s == "JPY")
			res += x;
		else
			res += (double) (38000.0 * x) / 0.1;
	}
	cout << res;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

int main(){
    int  a,b;
    cin >> a >> b;
    string A, B;
    for(int i=0; i<b; i++){
        A += to_string(a);
    }
    for(int i=0; i<a; i++){
        B += to_string(b);
    }
    if(A < B){
        cout << A;
    }else{
        cout << B;
    }
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>



int main() {
  long i, j = 0, k, num = 0,  ans = 0, N = 0;
  scanf("%ld", &N);
  num = N;
  for (i = 100; i >= 1; i /= 10) {
    if (num / i == 7) ans++;
    num -= num / i * i;
  }
  if (ans) printf("Yes");
  else     printf("No");
  return 0;
}


Measured memory_bytes: 1728
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

char A[1000001];

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


	int N = getint();

	rep(i, N) {
		int a = getint();
		A[a] += A[a] + 1;
	}

	if (A[1]) {
		if (A[1] == 1) co(1);
		else co(0);
		return 0;
	}
	if (A[2]) {
		int kotae = (A[2] == 1);
		for (int i = 3; i <= 500000; i += 2) {
			if (A[i]) {
				kotae += (A[i] == 1);
				for (int j = i + i; j <= 1000000; j += i) {
					A[j] = 0;
				}
			}
		}
		for (int i = 500001; i <= 1000000; i += 2) kotae += (A[i] == 1);
		co(kotae);
		return 0;
	}

	int kotae = 0;
	for (int i = 2; i <= 500000; i++) {
		if (A[i]) {
			kotae += (A[i] == 1);
			for (int j = i + i; j <= 1000000; j += i) {
				A[j] = 0;
			}
		}
	}
	for (int i = 500001; i <= 1000000; i++) kotae += (A[i] == 1);
	co(kotae);

	Would you please return 0;
}

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

using namespace std;


void solve() {
    int n; cin >> n;
    int odd=0, even=0;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int x,y;
        cin >> x >> y;
        if ((x+y)&1) odd++;
        else even++;
        a[i] = {x,y};
    }
    if (odd && even) {
        cout << -1; return;
    }

    int m = 35;
    vector<int64_t> d(m);
    for (int i = 0; i < m; i++) {
        d[i] = 1ll << i;
    }
    reverse(d.begin(), d.end());
    cout << (even?m+1:m) <<"\n";
    for (auto& x: d) {
        cout << x << ' ';
    }
    cout << (even?"1\n":"\n");
    for (auto& p: a) {
        int64_t x,y;
        tie(x,y) = p;
        if (even) x--;
        string res;
        for (int i = 0; i < m; i++) {
            bool u = y+x>0 , v = y-x>0;
            if (u && v)   res += "U", y -= d[i];
            if (!u && !v) res += "D", y += d[i];
            if (u && !v)  res += "R", x -= d[i];
            if (!u && v)  res += "L", x += d[i];
        }
        assert(x == 0 && y == 0);
        if (even) res += "R";
        cout << res << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = 3;
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = sc.nextInt();
		}
		Arrays.sort(p);
		String ans = p[0] + p[1] == p[2] ? "Yes" : "No";
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 21844
class Node
  attr_accessor :parent, :left, :right, :chlds

  def initialize(p, l, r, *chs)
    @parent = p
    @left   = l
    @right  = r
    @chlds  = chs
  end
end

def getDepth(k, d, node)
  if node[k].parent == -1
      d
  else
     getDepth(node[k].parent, d+1, node)
  end
end

def getKubun(k, nodes)
  if nodes[k].parent == -1
    "root"
  elsif nodes[k].left != nil
    "internal node"
  else
    "leaf"
  end
end

nodes = {}
n = gets.chomp.to_i

n.times {
  key, z, *chs = gets.chomp.split.map(&:to_i)

  if nodes[key] == nil
    nodes[key] = Node.new(-1, chs[0], nil, chs)
  else
      nodes[key].left = chs[0]
      nodes[key].chlds = chs
  end

  #-- 子要素について、parentとrightをセット
  chs.each_with_index { |ch, i|
    #-- parentのセット
    if nodes[ch] == nil
      nodes[ch] = Node.new(key, nil, nil, nil)
    else
      nodes[ch].parent = key
    end

    #-- rightのセット
    if i != chs.length - 1
      nodes[ch].right = chs[i + 1]
    end
  }
}

#-- 表示
[*0...n].each { |i|
  print "node #{i}: parent = #{nodes[i].parent}, depth = #{getDepth(i, 0, nodes)}, #{getKubun(i, nodes)}, "
  p nodes[i].chlds.flatten
}


Measured memory_bytes: 32688
H, W = map(int, input().split())
STAGE = [list(input()) for _ in range(H)]

black, white = [], 0
for y, line in enumerate(STAGE):
	for x, cell in enumerate(line):
		if "#" == cell:
			black += [(y, x)]
		else:
			white += 1

stage = STAGE
ds = ((0, 1), (1, 0), (0, -1), (-1, 0))

def get_next(p, d):
	n = (p[0] + d[0], p[1] + d[1])
	if 0 <= n[0] < H and 0 <= n[1] < W:
		return n
	return None

def set_val(p, v):
	global stage
	stage[p[0]][p[1]] = v

def get_val(p):
	return stage[p[0]][p[1]]

count = 0
while white:
	count += 1
	next_black = []
	for b in black:
		for d in ds:
			n = get_next(b, d)
			if n:
				v = get_val(n)
				if "." == v:
					white -= 1
					set_val(n, "#")
					next_black += [n]
	black = next_black

print(count)


Measured memory_bytes: 125248
#include<iostream>
using namespace std;
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
int main(){
	int am,pm;
	char name[15];
	rep(i,9){
		cin>>name>>am>>pm;
		cout<<name<<" "<<am+pm<<" "<<am*200+pm*300<<endl;
	}
}

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

int n[100001];

void Like2017() {
  for (int i = 2; i * i <= 100000; ++i) {
    if (n[i])
      for (int j = i * i; j <= 100000; j += i)
        n[j] = 0;
  }
  for (int i = 100000; i >= 2; --i)
    if (n[i] == 1 && n[(i + 1) / 2] != 1)
      n[i] = 0;
  for (int i = 3; i <= 100000; ++i)
    n[i] += n[i - 1];
}

int main() {
  int Q;
  cin >> Q;
  vector<int> l(Q), r(Q);
  for (int i = 0; i < Q; ++i)
    cin >> l[i] >> r[i];
  for (int i = 2; i <= 100000; ++i)
    n[i] = 1;
  Like2017();
  for (int i = 0; i < Q; ++i)
    cout << n[r[i]] - n[l[i] - 1] << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
	// your code goes here
	vector<vector<ll> > dp(101, vector<ll>(1e5+1, (ll)INT_MIN));
	dp[0][0]=0;
	ll n, w;
	cin >> n >> w;
	for(ll i=0; i<n; i++){
		ll weight, value;
		cin >> weight >> value;
		for(ll j=0; j<=w; j++){
			if(j+weight<=w)
				dp[i+1][j+weight]=max(dp[i+1][j+weight], dp[i][j]+value);
			dp[i+1][j]=max(dp[i+1][j], dp[i][j]);
		}
	}
	ll ans=(ll)INT_MIN;
	for(ll j=0; j<=w; j++)
		ans=max(ans, dp[n][j]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
constexpr int inf=0xE869120;
struct Point{
	int x,y;
};

bool compx(const Point &a,const Point &b){
	return a.x<b.x;
}
bool compy(const Point &a,const Point &b){
	return a.y<b.y;
}

int H,W,K;
string S[1000000];
vector<vector<int>>G;
Point s,g;

int main(){
	cin>>H>>W>>K;
	G=vector<vector<int>>(H,vector<int>(W,inf));
	cin>>s.x>>s.y>>g.x>>g.y;
	s.x--;
	s.y--;
	g.x--;
	g.y--;
	for(int i=0;i<H;i++)cin>>S[i];
	vector<Point>v;
	v.push_back(s);
	G[s.x][s.y]=0;
	while(!v.empty()){
		vector<Point>w;
		for(Point p:v){
			for(int i=1;i<=K;i++){
				if(p.x-i<0||S[p.x-i][p.y]=='@'||G[p.x-i][p.y]<=G[p.x][p.y])break;
				if(G[p.x-i][p.y]==inf){
					w.push_back({p.x-i,p.y});
					G[p.x-i][p.y]=G[p.x][p.y]+1;
				}
			}
		}
		for(Point p:v){
			for(int i=1;i<=K;i++){
				if(p.x+i>=H||S[p.x+i][p.y]=='@'||G[p.x+i][p.y]<=G[p.x][p.y])break;
				if(G[p.x+i][p.y]==inf){
					w.push_back({p.x+i,p.y});
					G[p.x+i][p.y]=G[p.x][p.y]+1;
				}
			}
		}
		for(Point p:v){
			for(int i=1;i<=K;i++){
				if(p.y-i<0||S[p.x][p.y-i]=='@'||G[p.x][p.y-i]<=G[p.x][p.y])break;
				if(G[p.x][p.y-i]==inf){
					w.push_back({p.x,p.y-i});
					G[p.x][p.y-i]=G[p.x][p.y]+1;
				}
			}
		}
		for(Point p:v){
			for(int i=1;i<=K;i++){
				if(p.y+i>=W||S[p.x][p.y+i]=='@'||G[p.x][p.y+i]<=G[p.x][p.y])break;
				if(G[p.x][p.y+i]==inf){
					w.push_back({p.x,p.y+i});
					G[p.x][p.y+i]=G[p.x][p.y]+1;
				}
			}
		}
		swap(v,w);
	}
	if(G[g.x][g.y]==inf)G[g.x][g.y]=-1;
	cout<<G[g.x][g.y]<<endl;
}


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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

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

    for (int i = N - 1; i >= 1; i--) {
        if (H[i] < H[i - 1]) H[i - 1]--;
    }

    bool flag = true;
    rep(i, N - 1) {
        if (H[i] > H[i + 1]) flag = false;
    }

    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int num[20],now,res;
int main(){
	ios::sync_with_stdio(false);
	long long n;cin>>n;
	long long temp=n;
	while(temp){
		num[++now]=temp%10;
		temp/=10;
	}
	int flag=0;
	for (int i=1;i<now;i++)
	if (num[i]<9) flag=-1;
	cout<<(now-1)*9+num[now]+flag;
	return 0;
}

Measured memory_bytes: 256
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define gcd __gcd
#define lcm(n, m) n * m / gcd(n, m)
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define so(n) sort(n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数

int main() {
  int N;
  ci(N);
  ve<ll> B(N - 1);
  rep(i, N - 1){
    ci(B.at(i));
  }
  ll A = B.at(0) + B.at(N - 2);
  rep(i, N - 2){
    A += min(B.at(i), B.at(i + 1));
  }
  co(A);
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#![allow(unused_imports)]
use proconio::input;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::cmp::max;
use std::cmp::min;


fn main() {
    input! {
        S: String,
        T: String,
    }

    // Tの方が短い
    // Tの0文字目とSのi文字目で一致度を見る
    let mut max_hit = 0;


    for i in 0..S.len() - T.len() + 1 {
        let mut cand = 0;
        for j in 0..T.len() {
            if &S[i + j..i + j + 1] == &T[j..j + 1] {
                cand += 1;
            }
        }

        max_hit = max(max_hit, cand);
    }

    let ans = T.len() - max_hit;
    println!("{}", ans);
}


Measured memory_bytes: 2116