akhauriyash/Code-Regression huggingface dataset:
n, m = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(m)]

for x in range(1000):
    keta = 1
    nx = x//10
    d = [x%10]

    while nx:
        keta += 1
        d.append(nx%10)
        nx //= 10

    if keta != n: continue

    flg = True
    d.reverse()
    for s, c in SC:
        if d[s-1] != c:
            flg = False
    if flg:
        print(x)
        exit()

print(-1)

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

ll dp[110][100010];
int weight[110],value[110];

int main()
{

    int n,w; cin>>n>>w;

    for(int i=1;i<=n;i++)
        cin>>weight[i]>>value[i];

    for(int i=0;i<=w;i++)
        dp[0][i]=0;
    for(int i=0;i<=n;i++)
        dp[i][0]=0;

    for(int i=1;i<=n;i++)

    {
        for(int j=1;j<=w;j++)
        {
            dp[i][j]=dp[i-1][j];
            if(weight[i]<=j)
                dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    cout<<dp[n][w];
    return 0;
}



Measured memory_bytes: 80128
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]

    ans = 0
    for y in range(H):
        for x in range(W):
            if board[y][x] == ".":
                ans += 1

    q = deque()
    q.append((0, 0, 0))
    check[0][0] = True
    while len(q) > 0:
        cost, x, y = q.popleft()
        if x == W-1 and y == H-1:
            print(ans - 1 - cost)
            return
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if board[ny][nx] == "." and not check[ny][nx]:
                    q.append((cost+1, nx, ny))
                    check[ny][nx] = True
    print(-1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    string num;
    cin >> num;
    if((num[0] == num[1] && num[1] == num[2]) || (num[1] == num[2] && num[2] == num[3])){
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    
    cout << endl;    
}


Measured memory_bytes: 256
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)

def main():
    N, M, K = LI()
    A = LI()
    B = LI()

    a = [0]+list(accumulate(A))
    b = [0]+list(accumulate(B))

    ans = 0

    for i in range(N + 1):
        if a[i] > K:
            continue
        rest = K - a[i]
        j = bisect.bisect_right(b, rest)
        ans = max(ans, i + j - 1)

    print(ans)

main()


Measured memory_bytes: 131520
#include<bits/stdc++.h>
#define maxn 234567

using namespace std;
typedef long long ll;
ll a,b,c,d,q,r;

int main(){
    cin >> q;
    while (q--){
        cin >> a >> b >> c >> d;
        r=__gcd(b,d);
        if (a>=b&&b<=d&&c>=b-r+a%r) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 256
package main
import (
	"fmt"
)
func main(){
	var k int
	var N[5]int
	fmt.Scan(&N[0], &N[1], &N[2], &N[3], &N[4], &k)
	if N[4]-N[0] > k {
		fmt.Println(":(")
	} else {
		fmt.Println("Yay!")
	}
}

Measured memory_bytes: 512
//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <cmath>
#include <vector>
#include <queue> 
#define LL long long
#define db double 
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
//#define int LL
using namespace std;
const int N   = 233;
//const int mod = ;
const int INF =numeric_limits<int >::max();

#define rep(i,x,y) for (int i=x;i<=y;++i)
void read(int &x)
{
	x=0;
	char ch=getchar();
	int f=1;
	while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
	while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	x*=f;
}
int n,x[N],y[N];
db st[N];
int tp ;
const double pi=acos(-1.);
signed main()
{
	read(n);
	rep(i,1,n) read(x[i]),read(y[i]);
	rep(i,1,n)
	{
		tp=0;
		rep(j,1,n) if (i^j) st[++tp]=atan2(x[j]-x[i],y[j]-y[i]);
		sort(st+1,st+1+tp);
		st[0]=st[tp]-2.*pi;
		db ans=0;
		rep(i,1,n) ans=max(ans,st[i]-st[i-1]-pi);
		printf("%.18f\n",ans/2./pi);
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;

class Factorial {
    vector<mint> facts, factinv;
public:
    explicit Factorial(int n) : facts(n+1), factinv(n+1) {
        facts[0] = 1;
        for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1] * mint(i);
        factinv[n] = facts[n].inv();
        for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * mint(i+1);
    }
    mint fact(int k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }
    mint operator[](const int &k) const {
        if(k >= 0) return facts[k]; else return factinv[-k];
    }
    mint C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[q] * factinv[p-q];
    }
    mint P(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return facts[p] * factinv[p-q];
    }
    mint H(int p, int q) const {
        if(p < 0 || q < 0) return 0;
        return q == 0 ? 1 : C(p+q-1, q);
    }
};

int main() {
    int k; string s;
    cin >> k >> s;
    int N = k+s.size();
    mint ans = 0;
    vector<mint> pow25(N+1, 1), pow26(N+1, 1);
    for (int i = 0; i < N; ++i) {
        pow25[i+1] = pow25[i]*25;
        pow26[i+1] = pow26[i]*26;
    }
    Factorial f(N);
    for (int i = 0; i <= k; ++i) {
        ans += pow25[i]*pow26[k-i]*f.C(i+s.size()-1, i);
    }
    printf("%d\n", ans.val);
    return 0;
}

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

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

  string a, b, c;
  cin >> a >> b >> c;

  string ans;
  ans += a[0] - 32;
  ans += b[0] - 32;
  ans += c[0] - 32;
  
  cout << ans << '\n';

  return (0);
}


Measured memory_bytes: 3648
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    _ = int(input())
    A = [int(i) for i in input().split()]
    rgb = [0, 0, 0]
    ans = modint(1)
    for a in A:
        if rgb[0] == a:
            if rgb[0] == rgb[1] and rgb[0] == rgb[2]:
                ans *= 3
            elif rgb[0] == rgb[1]:
                ans *= 2
            rgb[0] += 1
        elif rgb[1] == a:
            if rgb[1] == rgb[2]:
                ans *= 2
            rgb[1] += 1
        elif rgb[2] == a:
            rgb[2] += 1
        else:
            return print(0)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 54632
#include<iostream>

using namespace std;
using ll=long long;

int main(){
    ll K;
    cin>>K;
    ll x=7%K;
    ll y=x;
    if(x==0){
        cout<<1<<endl;
        return 0;
    }
    for(int i=2;i<=K;i++){
        y=10*y+x;
        y%=K;
        if(y==0){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,c,x,cnt=0;
    cin>>n>>m>>c;
    vector<int> b(m);
    for(int i=0;i<m;i++) cin>>b.at(i);
    for(int i=0;i<n;i++) {
        int s=0;
        for(int j=0;j<m;j++) {
            cin>>x;
            s+=x*b.at(j);
        }
        s+=c;
        if(s>0) cnt++;
    }
    cout<<cnt<<"\n";
}

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

int main(){
    int N,L;cin >> N >> L;
    vector<string> S(N);

    for (int i = 0;i < N;i++){
        cin >> S.at(i);
    }

    sort(S.begin(),S.end());
    string ans;
    for (int i = 0;i < N;i++){
        ans+=S.at(i);
    }
    
    cout << ans << endl;

}

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

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

    string a, b;
    cin >> a >> b;

    if(a.length() > b.length()){
        puts("GREATER");
        return 0;
    }
    else if(a.length() < b.length()) {
        puts("LESS");
        return 0;
    }
    else{
        for (int i = 0; i < a.length(); ++i){
            if(a[i] == b[i]) continue;

            if(a[i] > b[i]){
                puts("GREATER");
                return 0;
            }
            else{
                puts("LESS");
                return 0;
            }
        }
    }
    puts("EQUAL");
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
const long long WHMAX = 401;

bool used[WHMAX][WHMAX] = {};
char m[WHMAX][WHMAX] = {};
long long H, W;
long long black, white;
long long dx[4] = {0, 1, 0, -1};
long long dy[4] = {1, 0, -1, 0};

void dfs(long long y, long long x){
    if(used[y][x]) return;
    used[y][x] = true;
    if(m[y][x] == '#') black++;
    else white++;

    for(long long i = 0; i < 4; ++i){
        long long nx = x + dx[i];
        long long ny = y + dy[i];
        if(0 <= nx && nx < W && 0 <= ny && ny < H && m[y][x] != m[ny][nx] && !used[ny][nx]){
            dfs(ny, nx);
        }
    }
}

int main(){
    cin >> H >> W;
        
    for(long long i = 0; i < H; ++i){
        for(long long j = 0; j < W; ++j){
            cin >> m[i][j];
        }
    }

    long long ans = 0;

    for(long long i = 0; i < H; ++i){
        for(long long j = 0; j < W; ++j){
            black = white = 0;
            if(!used[i][j]){
                dfs(i, j);
                ans += black * white;
            }
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
//G:Longest Path(in DAG)	

using namespace::std;

vector<int> top_sort(vector<int> Adlist[],int GE[],int N){
	vector<int> ret;
	for(int i = 1;i <= N;i++){
		if(GE[i] == 0){
			ret.push_back(i);
		}
	}

	for(int i = 0;i < ret.size();i++){
		int nodo = ret[i];
		for(int newnodo : Adlist[nodo]){
			GE[newnodo]--;
			if(GE[newnodo] == 0)
				ret.push_back(newnodo);
		}
	}

	return ret;
}

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

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

	int GE[N + 1];
	fill(GE,GE + N + 1,0);
	vector<int> Adlist[N + 1];
	
	for(int i = 1;i <= M;i++){
		int a,b;
		cin >> a >> b;

		GE[b]++;
		Adlist[a].push_back(b);
	}

	vector<int> TS = top_sort(Adlist,GE,N);

	vector<int> sol(N + 1,0);
	for(int i = 0;i < N;i++){
		int nodo = TS[i];
//		cerr << nodo << '\n';
		for(int newnodo : Adlist[nodo])
			sol[newnodo] = max(sol[newnodo],sol[nodo] + 1);
	}

	cout << *max_element(sol.begin(),sol.end()) << '\n';

	return 0;
}


Measured memory_bytes: 7032
A = []
A.append(list(map(int, input().split())))
A.append(list(map(int, input().split())))
A.append(list(map(int, input().split())))
N = int(input())
B = [int(input()) for _ in range(N)]

for i in range(N):
    if B[i] in A[0]:
        A[0][A[0].index(B[i])] = True
    elif B[i] in A[1]:
        A[1][A[1].index(B[i])] = True
    elif B[i] in A[2]:
        A[2][A[2].index(B[i])] = True

bingo_flag = False
for i in range(3):
    if A[i][0] == A[i][1] == A[i][2] == True:
        bingo_flag = True
    elif A[0][i] == A[1][i] == A[2][i] == True:
        bingo_flag = True

if A[0][0] == A[1][1] == A[2][2] == True:
    bingo_flag = True
if A[0][2] == A[1][1] == A[2][0] == True:
    bingo_flag = True

if bingo_flag:
    print('Yes')
else:
    print('No')
    

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
using namespace std;
int A,B;
int main()
{
  cin >> A >> B;
  if((A+B)%2==0){
    cout << (A+B)/2 << "\n";
  }
  else{
    cout << "IMPOSSIBLE" << "\n";
  }
  return 0;
}


Measured memory_bytes: 256
import itertools
N, K = map(int, input().split())
p = list(map(int, input().split()))

pos = [(p[i]+1)/2 for i in range(N)]

pos_acum = list(itertools.accumulate(pos))

ans = pos_acum[K-1]
for i in range(N-K):
    ans = max(ans, pos_acum[K+i]-pos_acum[i])
print(ans)

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

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi >
ll a[100010];
int main()
{
  ios::sync_with_stdio(0), cin.tie(0);
    int n,s=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
      cin>>a[i];
      s+=a[i];
    }
    bitset<4000010>b;
    b[0]=1;
    for(int i=1;i<=n;i++)
      b|=(b<<a[i]);
    for(int i=(s+1)/2;i<=s;i++)
    {
      if(b[i]==1)
      {
        cout<<i;
        return 0;
      }
    }

  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
//<<setprecision(30)
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;
using Graph = vector<vector<int>>;

int main(){
  int N; cin>>N;
  vector<int> res(N+1,0);
  for(int i = 2; i <= N; i++){
    int a; cin>>a;
    res.at(a)++;
  }
  for(int i = 1; i <= N; i++)cout<<res.at(i)<<endl;
}

Measured memory_bytes: 3952
if __name__ == "__main__":
    A, B, C = map(int, input().split())
    K = int(input())

    for i in range(K):
        if B <= A:
            B *= 2
        elif C <= A:
            C *= 2
        elif C <= B:
            C *= 2

    if A < B < C:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 9104
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define MOD 100000007


#define MAXN 2000
long long inv[MAXN+1];//MODを法とする乗法の逆元
long long fact[MAXN+1];//階乗
long long ifact[MAXN+1];//階乗の逆元
void init(){
	inv[1] = 1;
    for(int i=2;i<=MAXN;i++) inv[i] = inv[MOD%i] * (MOD - MOD/i) % MOD;
	fact[0]=ifact[0]=1;
	for(int i=1;i<=MAXN;i++){
		fact[i]=i*fact[i-1]%MOD;
		ifact[i]=ifact[i-1]*inv[i]%MOD;
	}
}
long long C(int n, int r){
	if(n < 0 || r < 0 || r > n)return 0;
	if(r > n / 2)r = n - r;
	return fact[n]*ifact[n-r]%MOD*ifact[r]%MOD;
}

int main(){
	int r,c,a1,a2,b1,b2;
	cin>>r>>c>>a1>>a2>>b1>>b2;
	int x,y;
	x = min(abs(a1-b1) , min(a1,b1)+r-max(a1,b1));
	y = min(abs(a2-b2) , min(a2,b2)+c-max(a2,b2));
	init();
	int ans=C(x+y,x);
	if(abs(a1-b1) == min(a1,b1)+r-max(a1,b1))ans=(ans*2)%MOD;
	if(abs(a2-b2) == min(a2,b2)+c-max(a2,b2))ans=(ans*2)%MOD;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string a;
    cin >> a;

    if (a[0] == '7' || a[1]== '7' || a[2]=='7')
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

    
}




Measured memory_bytes: 3648
a,b = map(int,input().split())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A = set(prime_factorize(a))
B = set(prime_factorize(b))

cnt = 0
for i in A:
    if i in B:
        cnt += 1
print(cnt+1)

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

using namespace std;

#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define INF (int)1e9
typedef long long int int64;

void print() {
    cout << endl;
}

void print(const char* s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(string s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int64 s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int s, bool endline = true) {
    cout << s;
    if (endline) print();
}

template <typename T, typename T2>
void print(pair<T, T2>& p, bool endline = true) {
    cout << "(";
    print(p.first, false);
    cout << ", ";
    print(p.second, false);
    cout << ")";

    if (endline) print();
}

template <typename T>
void print(T& t, bool endline = true) {
    cout << "[";
    for (auto it = t.begin(); it != t.end(); ++it) {
        if (it != t.begin()) cout << ", ";
        print(*it, false);
    }
    cout << "]";

    if(endline) print();
}

template <typename T>
vector<T> operator+(const vector<T> &a, const vector<T> &b)
{
    vector<T> ret;
    ret.reserve( a.size() + b.size() );                // preallocate memory
    ret.insert( ret.end(), a.begin(), a.end() );        // add A;
    ret.insert( ret.end(), b.begin(), b.end() );        // add B;

    return ret;
}

template <typename T>
vector<T> &operator+=(vector<T> &a, const vector<T> &b)
{
    a.reserve( a.size() + b.size() );                // preallocate memory without erase original data
    a.insert( a.end(), b.begin(), b.end() );         // add B;
    return a;
}

int main() {
    // g++ -Wall -Wextra -O2 -std=c++17 helloworld.cpp

    int64 n, x;
    cin >> n >> x;

    vector<int64> arr(n);

    for(int64 i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int64 ret = 0;

    for(int64 i = 0; i < n; ++i) {
        if(arr[i] > x) {
            ret += arr[i] - x;
            arr[i] = x;
        }

        if(i != 0) {
            if(arr[i] + arr[i-1] > x) {
                ret += arr[i] + arr[i - 1] - x;
                arr[i] -= arr[i] + arr[i - 1] - x;
            }
        }
    }

    print(ret);

    return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#define N 8
#define FREE 0
#define NOT_FREE 1

int Board[N][N];
int row[N], col[N], dpos[15], dneg[15];

void putQueen(int i) {
  int j, k, m;
  if(i == N) {
    for(k = 0; k < N; k++) {
      for (m = 0; m < N; m++) {
        if(Board[k][m] == FREE) printf(".");
        else printf("Q");
      }
      printf("\n");
    }
    return;
  }
  if(row[i] == NOT_FREE) putQueen(i+1);
  else {
    for(j = 0; j < N; j++) {
      if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE) continue;
      col[j] = dpos[i+j] = dneg[i-j+N-1] = Board[i][j] = NOT_FREE;
      putQueen(i+1);
      col[j] = dpos[i+j] = dneg[i-j+N-1] = Board[i][j] = FREE;
    }
  }
}

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

  for(i = 0; i < N; i++) {
    for(j = 0; j < N; j++) {
      Board[i][j] = FREE;
    }
    row[i] = col[i] = FREE;
  }
  for(i = 0; i < 15; i++) {
    dpos[i] = dneg[i] = FREE;
  }

  scanf("%d", &n);
  for(k = 0; k < n; k++) {
    scanf("%d", &i);
    scanf("%d", &j);
    Board[i][j] = row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
  }
  putQueen(0);

  return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  double l;
  cin >> l;
  double ans = (l/3.0) * (l/3.0) * (l/3.0);
  printf("%.16f\n", ans);
  return 0;
}


Measured memory_bytes: 888
s = list(input())
ans = [0]*len(s)

i = 0
while i != len(s):
    cnt1 = 0
    cnt2 = 0
    while s[i + cnt1] == "R":
        cnt1 += 1
    ans[i + cnt1] += cnt1//2
    ans[i + cnt1 - 1] += cnt1//2 + cnt1%2
    while s[i + cnt1 + cnt2] == "L":
        cnt2 += 1
        if i + cnt1 + cnt2 == len(s):
            break
    ans[i + cnt1] += cnt2//2 + cnt2%2
    ans[i + cnt1 - 1] += cnt2//2
    i += cnt1 + cnt2

an = [str(i) for i in ans]
print(" ".join(an))

Measured memory_bytes: 80544
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999

int main(){
    int n,m;
    cin>>n>>m;
    vi player(m);
    rep(i,m){
        cin>>player[i];
        player[i]--;
    }

    vi score(n,0);
    rep(i,m){
        int sum=0;
        rep(j,n){
            int a;
            cin>>a;
            a--;
            if(a!=player[i])sum++;
            else score[j]++;
        }
        score[player[i]] += sum;
    }
    
    rep(i,n)cout<<score[i]<<endl;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long LL;
LL read()
{
    char c=getchar();LL f=1,sum=0;
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){sum=sum*10+c-'0';c=getchar();}
    return sum*f;
}
LL n;
struct node{
	LL id,dis;
}a[maxn];
LL siz[maxn],fa[maxn],d[maxn],dep[maxn];
vector<LL> edge[maxn];
LL ans;
bool cmp(node l,node r){return l.dis<r.dis;}
void dfs(LL u,LL fa)
{
	dep[u]=dep[fa]+1;
	for(int i=0;i<edge[u].size();i++) if(edge[u][i]!=fa) dfs(edge[u][i],u);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i].dis=read(),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) d[i]=a[i].dis;
	for(int i=n;i>=2;i--)
	{
		siz[a[i].id]++;
		LL tmp=d[i]-(n-2*siz[a[i].id]);
		LL pos=lower_bound(d+1,d+i,tmp)-d;
		if(pos>=i||d[pos]!=tmp) return puts("-1"),0;
		siz[a[pos].id]+=siz[a[i].id];
		fa[a[i].id]=a[pos].id;
	}
	for(int i=1;i<=n;i++)
	if(fa[i]) edge[fa[i]].push_back(i);
	dep[0]=-1;
	dfs(a[1].id,0);
	for(int i=1;i<=n;i++) ans+=dep[i];
	if(ans!=d[1]) return puts("-1"),0; 
	for(int i=1;i<=n;i++) if(fa[i]) printf("%lld %lld\n",i,fa[i]);
} 

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int main(){
  int n,q;
  cin>>n>>q;
  string res = "kogakubu10gokan";
  REP(_,n){
    int y;
    string s;
    cin>>y>>s;
    if(q>=y) res = s;
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 1208
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    let ans = if n % 2 == 0 {
        n / 2
    } else {
        n / 2 + 1
    };

    return format!("{}", ans);
}


Measured memory_bytes: 4352
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	boolean[] p = new boolean[1000000];
	setP(p);
	while(kbd.hasNext()){
	    int n = kbd.nextInt();
	    solve(n, p);
	}
    }

    static void solve(int n, boolean[] p){
	int i=n-1, j=n+1;
	while(!p[i]) i--;
	while(!p[j]) j++;
	System.out.println(i+" "+j);
    }

    static void setP(boolean[] p){
	Arrays.fill(p, true);
	int i, j;
	p[0] = false;
	p[1] = false;
	for(i=2; i<p.length; i++){
	    for(j=i+i; j<p.length; j+=i){
		if(p[i]) p[j] = false;
	    }
	}
    }
}

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

using namespace std;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;



int main () {
	SpeedForce;
	cin >> n >> m >> k;
	if (m < n) swap(m, n);
	cout << (k + m - 1) / m;
   	return Accepted;
}

// B...a

Measured memory_bytes: 18688
#include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
	int A, B, i;
	char S[9], T[9], U[9];

	scanf("%s %s", S, T);
	scanf("%d %d", &A, &B);

	scanf("%s", U);

	i = sizeof(S);

	if (S[0] == U[0] && S[i]==U[i]) {
		A--;
	}
	else {
		B--;
	}

	cout << A << " " << B << endl;

	return 0;
}

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

int num[105], k, n;
string s;

int f(int p, int k)
{
	if (k < 0)	return 0;
	if (k == 0) return 1;
	if (p <= 0)	return 0;
	return f(p-1, k) + 9*f(p-1,k-1);
}

int solve()
{
	int sum = 0;
	int kk = k;
	for (int i = n - 1; i; i--)
	{
		if (num[i] != 0)
		{
			sum += f(i, kk) + (num[i] - 1) * f(i, kk-1);
			kk--;
		}
	}
	if (kk == 0)	sum++;
	if (kk == 1)	sum += num[0];
	return sum;
}

int main()
{
	cin >> s >> k;
	n = s.size();
	for (int i = 0; i < n; i++)
		num[n - 1 - i] = s[i] - '0';
	cout << solve();
	return 0;
}

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

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};


void solve(long long N, vector<long long> x, vector<long long> y){
    vector< pair<ll,int> > X,Y;
    for(int i = 0 ; i < x.size() ; i++){
        X.push_back({x[i],i});
    }
    for(int i = 0 ; i < y.size() ; i++){
        Y.push_back({y[i],i});
    }
    UnionFind uf(N);
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());

    vector<pair<ll,pair<int,int>>> es;
    auto func = [&](vector< pair<ll,int> > X ){
        for(int i = 0 ; i + 1 < X.size() ; i++){
            int id1 = X[i].second;
            int id2 = X[i+1].second;
            es.push_back({min(abs(x[id1]-x[id2]),abs(y[id1]-y[id2])),{id1,id2}});
        }
    };
    func(X);
    func(Y);
    sort(es.begin(),es.end());
    ll ans = 0;
    for( auto e : es ){
        if( uf.unionSet(e.second.first,e.second.second)){
            ans += e.first;
        }
    }
    cout << ans << endl;

}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> y(N-1+1);
	vector<long long> x(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&x[i]);
		scanf("%lld",&y[i]);
	}
	solve(N, x, y);
	return 0;
}



Measured memory_bytes: 14548
let print_ary a =
  Array.iteri (fun i e -> Printf.printf (if i = 0 then "%d" else " %d") e) a;
  print_newline ()

let rev_iter f a =
  let rec doit i =
    if i >= 0 then (f (Array.get a i); doit (i - 1))
  in
  doit (Array.length a - 1)

let counting_sort a b k =
  let c = Array.make (k + 1) 0 in
  Array.iter (fun e -> c.(e) <- c.(e) + 1) a;
  Array.iteri (fun i _ -> if i <> 0 then c.(i) <- c.(i) + c.(i - 1)) c;
  rev_iter (fun e -> b.(c.(e) - 1) <- e; c.(e) <- c.(e) - 1) a

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun e -> e)) in
  let k = Array.fold_left max (-1) a in
  let b = Array.make n 0 in
  counting_sort a b k;
  print_ary b

Measured memory_bytes: 36212
fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val b = readLine()!!
  println(weiwei(b)+1)
}

tailrec fun weiwei(list :String, c :Int = 0, s: Int = 0) : Int {
    if (list.length == s+1) {
        return c
    }

    val v = if (list[s] == list[s+1]) { 0 } else { 1 }
    return weiwei(list, c + v, s + 1)
}

Measured memory_bytes: 34404
import java.util.*;
 
public class Main { 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] A = new int[N];
    int[] B = new int[N];
    int[] C = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    for (int i = 0; i < N; i++) {
      B[i] = sc.nextInt();
    }
    for (int i = 0; i < N; i++) {
      C[i] = sc.nextInt();
    }
    Arrays.sort(A);
    Arrays.sort(B);
    Arrays.sort(C);

    int[] sum = new int[N];
    for (int i = 0; i < N; i++) {
      sum[i] = N - upperBound(C, B[i]);
    }
    // System.out.println(Arrays.toString(sum));

    long ans = 0;
    int j = N - 1;
    long now = 0;
    for (int i = N - 1; 0 <= i; i--) {
      while (0 <= j && A[i] < B[j]) {
        now += sum[j--];
      }
      ans += now;
    }

    System.out.println(ans);
  }

  //指定した値以上の先頭のインデックスを返す
  private static final int lowerBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
      mid = ((high - low) >>> 1) + low;   //(low+high)/2のオーバーフロー対策
      if (arr[mid] < value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
 
  //指定した値より大きい先頭のインデックスを返す
  private static final int upperBound(final int[] arr, final int value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
      mid = ((high - low) >>> 1) + low;   //(low+high)/2のオーバーフロー対策
      if (arr[mid] <= value) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}

Measured memory_bytes: 93912
n = int(input())
A = list(map(int, input().split()))
cnt = 0
res = []
for i in range(n - 1, -1, -1):
    c = i + 1
    if (A[i] % 2 == 1):
        cnt += 1
        res.append(c)
        for k in range(1, int(c ** 0.5) + 1):
            if (c % k == 0):
                if (k != c // k):
                    A[k - 1] -= 1
                    A[c // k - 1] -= 1
                else:
                    A[k - 1] -= 1
print(cnt)
print(*res)

Measured memory_bytes: 69340
#include<stdio.h>
int main(void){
	int outcount = 0;
	int hitcount = 0;
	char str[5000];
	int number;
	int score = 0;
	int i;
	scanf("%d",&number);
	for(i = 0;i < number;i++){
		while(scanf("%s",str)){
			if(str[0] == 'H'){
				if(str[1] == 'I'){
					if(str[2] == 'T'){
						hitcount++;
						if(hitcount > 3){
							score++;
							hitcount--;;
						}
					}
				}
			}
			if(str[0] == 'H'){
				if(str[1] == 'O'){
					if(str[2] == 'M'){
						if(str[3] == 'E'){
							if(str[4] == 'R'){
								if(str[5] == 'U'){
									if(str[6] == 'N'){
										score = score + hitcount + 1;
										hitcount = 0;
									}
								}
							}
						}
					}
				}
			}
			if(str[0] == 'O'){
				if(str[1] == 'U'){
					if(str[2] == 'T'){
						outcount++;
						if(outcount == 3){
							printf("%d\n",score);
							score = 0;
							hitcount = 0;
							outcount = 0;
							break;
						}
					}
				}
			}
		}
	}
	return 0;
}

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

using namespace std;

using ll = long long;
using ii = pair<int,int>;

const ll maxn = 1e12+10;

#define ff first
#define ss second

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,ans=maxn;
	cin >> n;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			ans = min(ans,n/i+i-2);
		}
	}
	cout << ans << '\n';
	return 0;
}

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

int main (){
    int N, K;
    cin >> N >> K;
    vector <int> a(N);
    for (int i=0; i<N; ++i) cin >> a[i];
    if(K-N==0){
        cout << 1 << endl;
    }else if((K-N)%(K-1) == 0){
        cout << (N-K)/(K-1)+1 << endl;
    }else{
        cout << (N-K)/(K-1)+2 << endl;
    }
}

Measured memory_bytes: 3708
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    AB = [LIST() for _ in range(N)]
    CD = [LIST() for _ in range(M)]

    for a, b in AB:
        dist = INF

        for i, cd in enumerate(CD):
            if dist > abs(a - cd[0]) + abs(b - cd[1]):
                dist = abs(a - cd[0]) + abs(b - cd[1])
                num = i + 1

        print(num)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9988
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <deque>
#include <map>

using namespace std;

const int CMax = 200002;
const int CInf = 2000000001;
const long long CMod = 1000000007;

long long a, b, c, d, e, n;

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

string baseConverter(int base, int num) {
    string tNum = "";
    while (num > 0) {
        tNum = (char)('0' + num%base) + tNum;
        num /= base;
    }
}

bool isPalindrom(string tS) {
    int sn = (int)tS.length();
    for (int i = 0; i < sn / 2; i++) {
        if (tS[i] != tS[sn - i - 1]) return false;
    }
    return true;
}

int dist(int i, int j) {
    return  (j < i ? n + j : j) - i;
}

int main()
{
    cin >> n >> a >> b >> c >> d >> e;

    long long sum = 4;

    sum += max(n / a + (int)(n % a > 0), max(n / b + (int)(n % b > 0), max(n / c + (int)(n % c > 0), max(n / d + (int)(n % d > 0), n / e + (int)(n % e > 0)))));

    cout << sum << endl;
    return 0;
}


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

int main() {
  string S;
  cin >> S;
  
  string ans;
  ans = "Yes";
  
  for(int i=0; i<S.size(); i++){
    if (i%2 == 0 && (S.at(i) == 'R' || S.at(i) == 'U' || S.at(i) == 'D')){
      continue;
    }
    else if (i%2 == 1 && (S.at(i) == 'L' || S.at(i) == 'U' || S.at(i) == 'D')){
      continue;
    }
    else{
      ans = "No";
    }
  }
  cout << ans << endl;  
}


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

int main() {
    int n, tmp;
    cin >> n;
    deque<int> a;
    int reverse = -1;
    rep(i,n) {
        cin >> tmp;
        if (reverse == -1) {
            a.push_back(tmp);
        } else {
            a.push_front(tmp);
        }
        reverse *= -1;
    }
    if (reverse == -1) {
        while (!a.empty()) {
            cout << a.front() << " ";
            a.pop_front();
        }
    } else {
        while (!a.empty()) {
            cout << a.back() << " ";
            a.pop_back();
        }
    }
}


Measured memory_bytes: 4424
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
	int N;
	string S;
	cin >> N >> S;
	int cnt=0, ans=0;
	for(int i=0; i<N; ++i){
		if(S[i]=='R') ++cnt;
	}
	for(int i=0; i<cnt; ++i){
		if(S[i]=='W') ++ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3752
#include<stdio.h>
#include<algorithm>
using namespace std;
int m[50][50];
int w[50][50];
char str[50][50];
int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};
int main(){
	int a,b;
	while(scanf("%d%d",&b,&a),a){
		for(int i=0;i<a;i++)scanf("%s",str[i]);
		for(int i=0;i<=180;i++){
			for(int j=0;j<a;j++)
				for(int k=0;k<b;k++)
					m[j][k]=-1;
		}
		int ret=-1;
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++){
				if(str[i][j]=='E')m[i][j]=0;
				if(str[i][j]=='N')m[i][j]=1;
				if(str[i][j]=='W')m[i][j]=2;
				if(str[i][j]=='S')m[i][j]=3;
			}
		for(int i=0;i<180;i++){
			for(int j=0;j<a;j++){
				for(int k=0;k<b;k++){
					w[j][k]=0;
					if(!~m[j][k])continue;
					for(int l=0;l<4;l++){
						int tx=j+dx[(m[j][k]+l+3)%4];
						int ty=k+dy[(m[j][k]+l+3)%4];
						if(0<=tx&&tx<a&&0<=ty&&ty<b&&!~m[tx][ty]&&str[tx][ty]!='#'){
							m[j][k]=(m[j][k]+l+3)%4;
							w[j][k]=1;
							break;
						}
					}
				}
			}
			for(int j=0;j<4;j++){
				for(int k=0;k<a;k++){
					for(int l=0;l<b;l++){
						if(m[k][l]!=(2+j)%4)continue;
						if(w[k][l]){
							int tx=k+dx[m[k][l]];
							int ty=l+dy[m[k][l]];
							if(!~m[tx][ty]){
								m[tx][ty]=m[k][l];
								m[k][l]=-1;
							}
						}
					}
				}
			}
			for(int j=0;j<a;j++)
				for(int k=0;k<b;k++)
					if(str[j][k]=='X')m[j][k]=-1;
			bool ok=true;
			for(int j=0;j<a;j++)
				for(int k=0;k<b;k++)
					if(~m[j][k])ok=false;
		/*	for(int j=0;j<a;j++){
				for(int k=0;k<b;k++){
					if(~m[j][k])printf("%d",m[j][k]);else printf(".");
				}
				printf("\n");
			}
			printf("\n");
		*/	if(ok){ret=i+1;break;}
		}
		if(ret==-1)printf("NA\n");
		else printf("%d\n",ret);
	}
}

Measured memory_bytes: 1060
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


char buf[10];

int main(){

	scanf("%s",buf);

	switch(buf[0]){
	case 'S':

		printf("Cloudy\n");
		break;

	case 'C':

		printf("Rainy\n");
		break;

	case 'R':

		printf("Sunny\n");
		break;
	}

	return 0;
}


Measured memory_bytes: 256
W, H, N = map(int, input().split())
X_Y_A = [map(int, input().split()) for _ in range(N)]
oX = 0
oY = 0
for x, y, a in X_Y_A:
    if a == 1:
        oX = max(x, oX)
    elif a == 2:
        W = min(x, W)
    elif a == 3:
        oY = max(y, oY)
    else:
        H = min(y, H)
# print(W, oX, H, oY)
print(max(0, W-oX)*max(0, H-oY))


Measured memory_bytes: 9104
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 510000;
const int MOD = 1000000007;

int main(){
  ll N, Y; cin>>N>>Y;
  Y /= 1000;

  ll c = Y - N;

  //4or9
  rep(i,N+1){
    ll sum = 0;
    rep(j,N-i+1){
      sum = i * 4;
      sum += j * 9;
      if(sum == c){
        cout<<j<<" "<<i<<" "<<N-i-j<<endl;
        return 0;
      }
    }

  }
  cout<<-1<<" "<<-1<<" "<<-1<<endl;

}


Measured memory_bytes: 384
/*
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
*/
#include <bits/stdc++.h>

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

int main()
{
    int n, j=0;
    cin >> n;
    string str;
    vector<string> data;
    vector<pair<int,int>> a(n);
    rep(i,n){
        cin >> str;
        data.push_back(str);
        a[i].first = 0;
    }

    sort(data.begin(), data.end());

    rep(i,n-1){
        a[j].second = i;
        if(data[i] == data[i+1]){
            a[j].first++;
        }else{
            j++;
        }
    }
    a[n-1].second = n-1;

    sort(a.rbegin(), a.rend());

    for(int i=n-1; i>=0; i--){
        if(a[0].first == a[i].first){
            cout << data[a[i].second] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 15856
#include <iostream>
using namespace std;
int main(void){
    int K, X;
    cin >> K >> X;
    
    for (int i = X-(K-1); i <= X + (K-1); i++) {
        if (i != X+(K-1))
            cout << i << " ";
        else
            cout << i << endl;
    }
}

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

int main() {
	long long N;
	while (cin >> N) {
		if (N == 0) return 0;
		long long ANS = 0;
		for (int i = 3; i <= N; i += 2) {
			if (N % i == 0) ANS++;
		}
		cout << ANS << endl;
	}
}


Measured memory_bytes: 3068
n = int(input())
nums = list(map(int, input().split()))
nums_sorted = sorted(nums)
l = nums_sorted[n//2 - 1]
r = nums_sorted[n//2]
for i in range(n):
    num = nums[i]
    if num <= l:
        print(r)
    else:
        print(l)

Measured memory_bytes: 26772