akhauriyash/Code-Regression huggingface dataset:
h,w=map(int,input().split())
list1=[]
ans=0
count1=0
count2=0
count3=0
for i in range(h):
    list1.append(list(input()))
for i in range(h):
    count3+=list1[i].count("#")
if count3!=h+w-1:
    ans=1
for i in range(h+w-3):
    if count2!=w-1:
        if list1[count1][count2+1]=="#":
            count2+=1
    if count1!=h-1:
        if list1[count1+1][count2]=="#":
            count1+=1
    if count2!=w-1:
        if count1!=h-1:
            if list1[count1+1][count2]=="." and list1[count1][count2+1]==".":
                ans=1
                break
        else:
            if list1[count1][count2+1]==".":
                ans=1
                break
    elif count1!=h-1:
        if list1[count1+1][count2]==".":
            ans=1
            break
if count1!=h-1 or count2!=w-1:
    ans=1
if h==2 and w==2:
    if list1[0][0]=="#" and list1[1][1]=="#" and count3==3:
        ans=0
if ans==1:
    print("Impossible")
else:
    print("Possible")


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


int main() {
    char c;
    cin >> c;
    if(c == 'A')printf("T\n");
    else if(c == 'T')printf("A\n");
    else if(c == 'G')printf("C\n");
    else printf("G\n");
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)

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

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

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


map<lli,lli> makePrimeList2(lli n){
	map<lli,lli> m;
	lli a = 2;
	while(n>=a*a){
		if(n%a==0){
			m[a]++;
			n /= a;
		}
		else a++;
	}
	if(n!=1)m[n]++;
	return m;
}

signed main(){

	lli n,m;
	cin>>n>>m;

	map<lli,lli> primeList = makePrimeList2(m);

	/*素因数分解したものをn個の箱に振り分ける*/
	COMinit();

	lli ans=1;
	lli cnt=0;

	for(auto e:primeList){
		ans *= COM(e.second+n-1,n-1);
		ans %= MOD;
		cnt++;
	}
	//if(cnt==1)cout<<1<<endl;
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 12160
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
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;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

vecl a(200010,1),b(200010,1);
vecl popcount(200010,0);

ll f(ll N) {
    ll ans = 0;
    while(N > 0) {
        ans++;
        N %= popcount[N];
    }
    return ans;
}

int main() {
    int N; cin >> N;
    string X; cin >> X;
    int cnt = 0;
    REP(i,N) cnt += X[i] == '1';
    REP(i,200010) {
        ll n = i;
        while(n > 0) {
            popcount[i] += (n%2==1);
            n /= 2;
        }
        a[i+1] = a[i]*2;
        b[i+1] = b[i]*2;
        a[i+1] %= cnt+1;
        if(cnt-1 != 0) b[i+1] %= cnt-1;
    }

    ll s = 0, v = 0;
    
    REP(i,N) {
        s += a[N-i-1]*(X[i]-'0');
        v += b[N-i-1]*(X[i]-'0');
    }

    REP(i,N) {
        if(X[i] == '0') {
            cout << f((s+a[N-i-1])%(cnt+1))+1 << endl;
        } else {
            if(cnt-1 != 0) cout << f((v-b[N-i-1])%(cnt-1))+1 << endl;
            else cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 8288
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    x,k,d = get_all_int()
    x = abs(x)

    if k*d < x:
        print(x - k*d)
        return
    
    y = (x+d-1) // d

    if k%2 == y%2:
        print(abs(x - y*d))
    else:
        print(abs(x - y*d + d))

main()

Measured memory_bytes: 67400
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

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

	string s;
	cin >> s;
	cout << s.substr(0, 3) << "\n";

	return 0;
}

Measured memory_bytes: 3640
s = input()

if 1 <= int(s[2:4]) <= 12:
    ans = "YYMM"
    if 1 <= int(s[:2]) <= 12:
        ans = "AMBIGUOUS"
elif 1 <= int(s[:2]) <= 12:
    ans = "MMYY"
    if 1 <= int(s[2:4]) <= 12:
        ans = "AMBIGUOUS"
else:
    ans = "NA"

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include"atcoder/all"

using namespace std;
using namespace atcoder;

int main() {
    int n, q;
    cin >> n >> q;
    dsu d(n);
    for (int i = 0; i < q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            d.merge(u, v);
        } else {
            if (d.same(u, v)) {
                cout << 1 << endl;
            } else {
                cout << 0 << endl;
            }
        }
    }

    return 0;
}


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

int main(){
  int n, k;
  cin >> n >> k;
  int cnt=0;
  int tmp;
  rep(i,n) {
    cin >> tmp;
    if(tmp>=k) cnt++;
  }
  cout << cnt << endl;
  
}

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

int main() {
    int N; std::cin >> N;
    std::vector<int> L(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> L[i];
    }
    int c = 0;
    std::sort(L.begin(), L.end());
    for (int i = 0; i < N - 2; ++i) {
        for (int j = i+1; j < N-1; ++j) {
            for (int k = j+1; k < N; ++k) {
                if (L[k] < L[i]+L[j] && L[i]!=L[j] && L[j]!= L[k]) c++;
            }
        }
    }
    std::cout << c << '\n';
}

Measured memory_bytes: 3628
h,w,m=map(int,input().split())
a=[0]*h
b=[0]*w
hw=[]
for _ in range(m):
    hh,ww=map(int,input().split())
    hw+=((hh-1,ww-1)),
    a[hh-1]+=1
    b[ww-1]+=1
    
ma=max(a)
mb=max(b)

# x_ind=[i for i,j in enumerate(a) if j==ma]
# y_ind=[i for i,j in enumerate(b) if j==mb]



cnt=0
# sonzai suru

for i,j in hw:
    if a[i]==ma and b[j]==mb:cnt+=1

if cnt==a.count(ma)*b.count(mb):
    print(ma+mb-1)
else:
    print(ma+mb)

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

using namespace std;

int main()
{

    string s;
    cin>>s;
    if(s[s.size()-1] == 's')
    {
        s.push_back('e');
        s.push_back('s');
    }
    else
    {
        s.push_back('s');
    }

    cout<<s<<"\n";
    return 0;
}

Measured memory_bytes: 3628
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

def sigma(func, frm, to):
    result = 0
    for i in range(frm, to+1):
        result += func(i)
    #print(result)

def f(x):
    return x

K = int(input())

#print(sigma(f,1,K))

#print(gcd(sigma(f,1,K),sigma(f,1,K),sigma(f,1,K)))

#sigma(sigma(sigma(gcd(), 1, K)))

#print(gcd(sigma(gcd,1,K),sigma(f(K),1,K),sigma(f(K),1,K)))

x = 0

#print()

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            x += gcd(a, b, c)
            """print("a:",end="")
            print(a)
            print("b:",end="")
            print(b)
            print("c:",end="")
            print(c)"""

print(x)

#print(gcd(27,18,9))

Measured memory_bytes: 69644
#include<cstdio>

int main(){
	int a,b,c;
	int sum=0;
	scanf("%d %d %d",&a,&b,&c);
	sum+=a+b+c;
	int mx=a;
	if(mx<b){
		mx=b;
	}
	if(mx<c){
		mx=c;
	}
	
	printf("%d",sum-mx);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007

using namespace std;

typedef long long ll;

int n;
pair<int, int> p[100002];

bool viz[100002];
ll tryy(int md)
{
    memset(viz, 0, sizeof(viz));
    set<pair<int, int> >sL, sR;
    for(int i = 1; i <= n; ++i)
    {
        sL.insert({p[i].fi, i});
        sR.insert({p[i].se, i});
    }
    ll ans = 0;
    int pos = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(i % 2 == md)
        {
            pair<int, int> current;
            current = *sL.rbegin();
            sL.erase(current);
            int tg = current.se;
            if (pos <= p[tg].se)
            {
                ans += max(p[tg].fi - pos, 0);
                if (pos < p[tg].fi)
                    pos = p[tg].fi;
            }
            else
            {
                ans += max(pos - p[tg].se, 0);
                pos = p[tg].se;
            }
            sR.erase(sR.find({p[tg].se, tg}));
        }
        else
        {
            pair<int, int> current;
            current = *sR.begin();
            sR.erase(current);
            int tg = current.se;
            if (pos >= p[tg].fi)
            {
                ans += max(pos - p[tg].se, 0);
                if (pos > p[tg].se)
                    pos = p[tg].se;
            }
            else
            {
                ans += max(p[tg].fi - pos, 0);
                pos = p[tg].fi;
            }
            sL.erase(sL.find({p[tg].fi, tg}));
        }
    }
    return ans + abs(pos);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> p[i].fi >> p[i].se;
    cout << max(tryy(1), tryy(0)) << '\n';
    return 0;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll N;
ll X[10],Y[10];
ll i, j, k;
ll mk[10];
double zntn(ll ii,ll p,double a){
    if(ii==N){
        return a;
    }
    ll i = 0;
    double ans = 0;
    fornum(i,0,N){
        if(mk[i]==0){
            mk[i] = 1;
            ans += zntn(ii + 1, i, a + sqrt(pow(X[p] - X[i], 2) + pow(Y[p] - Y[i], 2)));
            mk[i] = 0;
        }
    }
    return ans;
}

int main(){
    scanf("%lld", &N);
    fornum(i,0,N){
        scanf("%lld%lld", &X[i], &Y[i]);
    }
    double ans = 0;
    fornum(i,0,N){
        mk[i] = 1;
        ans += zntn(1, i, 0);
        mk[i] = 0;
        
    }
    fornum(i,0,N){
        ans /= (i + 1);
    }
    printf("%.12lf", ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
	int a,b;
	cin>>a>>b;
	double x=(a+b)/2.0;
	if (x==(int)x){
		cout<<(int)x<<endl;
	}else{
		cout<<(int)(x+1)<<endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  int a;
  set<int> s;
  rep(i, n){
    cin >> a;
    s.insert(a);
  }
  if(s.size()==n){
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 9600
n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
B=[int(input())for i in range(m)]


for i in range(n):
  kotae=0
  for j in range(m):
    kotae+=A[i][j]*B[j]
  print(kotae)


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

#define int long long
#define F first
#define S second
#define vi vector<int>


void mymain(){
    int a,b;
    cin >> a >> b;
    cout << 6-(a+b) << endl;



}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--){
        mymain();
    }
}


Measured memory_bytes: 256
using System;
class ITP1_10_B
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split(' ');
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);
        double rad = int.Parse(input[2]) * Math.PI / 180;
        double S=a * b * Math.Sin(rad) / 2;
        Console.WriteLine(S);
        Console.WriteLine(a + b + Math.Sqrt(a * a + b * b -2* a * b * Math.Cos(rad)));
        Console.WriteLine(S / a * 2);
    }
}

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

#define int long long

using namespace std;

const int maxn = 1e5 + 10, maxl = 1e6 + 10, mod = 1e9 + 7;
int a[maxn], L[maxl], n;

int pw(int base, int power)
{
    int res = 1;
    while (power)
    {
        if (power & 1)
            (res *= base) %= mod;
        (base *= base) %= mod;
        power >>= 1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;

    int s = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        (s += pw(a[i], mod - 2)) %= mod;
        for (int d = 2; d * d <= a[i]; d++)
        {
            int cnt = 0;
            while (a[i] % d == 0)
                a[i] /= d, ++cnt;
            L[d] = max(L[d], cnt);
        }
        if (a[i] > 1)
            L[a[i]] = max(L[a[i]], 1ll);
    }

    int lcm = 1;
    for (int i = 2; i < maxl; i++)
        (lcm *= pw(i, L[i])) %= mod;

    cout << lcm * s % mod;

    return 0;
}


Measured memory_bytes: 8192
//
// Created by moono on 2018/10/27.
//

#include <iostream>
#include <string>
#include <cmath>
using namespace std;


int main() {
    int N, M, X;
    cin >> N >> M >> X;

    //
    int cost_zero = 0, cost_n = 0, m;
    for (int i = 0; i < M; ++i) {
        cin >> m;
        if( X - m > 0){
            cost_zero++;
        } else if( N > m && m > X){
            cost_n++;
        };
    }


    //
    if(cost_zero < cost_n)
        cout << cost_zero << endl;
    else
        cout << cost_n << endl;
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
now=1
arr=[0]*(n+1)
for i in range(1,10**6):
  now=a[now-1]
  if i==k:
    print(now)
    quit()
  if arr[now]!=0:
    first=arr[now]
    break
  arr[now]=i
# print(arr)
cycle=max(arr)-first+1
# print(cycle)
mod=(k-first)%cycle
# print(mod)
ans=arr.index(first+mod)
print(ans)

Measured memory_bytes: 32376
#include <iostream>
#include <string>
#include <algorithm>
#include<vector>
#include<math.h>
#include<string>
#include<iomanip>
using namespace std;
int main()
{
    long long A,B,C,K;    cin>>A>>B>>C>>K;
    if(K%2==0){
        cout<<A-B<<endl;
        return 0;
    }
    cout<<B-A<<endl;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>

using namespace std;

#define MAX 1000000

int main(void){

  int n,count = 0,num = 0;

  while(cin >> n){

    vector<int>array(MAX,0);

    if(n == 1){
      count = 0;
      cout << count << endl;
    }

    if(n == 2){
      count = 1;
      cout << count << endl;
    }

    if(n == 3){
      count = 2;
      cout << count << endl;
    }

    if(n > 3){
      count = 2;
      num = 0;
      array[num++] = 2; 
      array[num++] = 3; 


      for(int i = 5; i <= n ; i+=2){
        int flag = 0;
        for(int j = 0; array[j] * array[j] <= i;j++){
          if(i % array[j] == 0){
            flag = 1;
            break;
          }
        }
        if(!flag){
          array[num++] = i;
          count++;
        }
      }
      cout << count << endl;
      count = 0;
      num = 0;
    }
  }

  return 0;
}

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

int main() {
    int W, H, x, y;
    cin >> W >> H >> x >> y;
    double ans = ((double)H * (double)W) / 2.0;
    cout << ans;
    if (2 * x == W && 2 * y == H) {
        cout << " 1\n";
    } else {
        cout << " 0\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int i,n,flag=0;

  scanf("%d",&n);
  char s[n+1];
  for(i=0;i<n;i++){
    scanf(" %c",&s[i]);
    if(s[i]=='Y') flag=1;
  }
  if(flag){
    printf("Four");
    return 0;
  }
  printf("Three");
  return 0;
}


Measured memory_bytes: 128
def gcd(a,b)
      return a if b == 0
      gcd(b,a%b)
end
def lcm(a,b)
      return a * b / gcd(a,b)
end
while line = gets
      a,b = line.split.map(&:to_i)
      print gcd(a,b)," ",lcm(a,b),"\n"
end

Measured memory_bytes: 8564
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll t=1; /*cin>>t;*/ while(t--)
typedef long long int ll;
int main() {
    FIO;
    test{
        // Knapsack Problem
        ll n,w,i,j;
        cin>>n>>w;
        //Taking input
        ll a[n][2];
        for(i=0;i<n;i++){
            cin>>a[i][0]>>a[i][1];
        }
        ll dp[n+1][w];
        memset(dp,0,sizeof(dp));
        dp[1][w-a[0][0]]=a[0][1];
        //Initializing the dp
        for(i=2;i<=n;i++){
            for(j=0;j<w;j++){
                if(j+a[i-1][0]<w){
                    dp[i][j]=max(dp[i][j],a[i-1][1]+dp[i-1][j+a[i-1][0]]);
                }
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
        }
        ll x=0;
        for(i=0;i<w;i++){
            x=max(x,dp[n][i]);
        }
        cout<<x<<endl;
    }
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 3e6;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);

#define pb(x) push_back(x);
#define endl '\n'
#define dokme(x) cout << x ;  return(0);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ms(x , y) memset(x , y , sizeof x);
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

ll n;
ll prt[5000][3];
string s;
ll ans;

int main(){
    migmig
    cin >> n;
    cin >> s;
    for(ll i = 0 ; i < n; i ++){
        if(i){
            prt[i][0] = prt[i-1][0];
            prt[i][1] = prt[i-1][1];
            prt[i][2] = prt[i-1][2];
        }
        if(s[i] == 'R'){
            prt[i][0]++;
        }
        if(s[i] == 'G'){
            prt[i][1]++;
        }
        if(s[i] == 'B'){
            prt[i][2]++;
        }
    }
    for(ll i = 0 ; i < s.size() ; i ++){
        for(ll j = i+2 ; j < s.size() ; j ++){
            if(s[i] != s[j]){
                if(s[i] != 'R' and s[j] != 'R'){
                    ans+=prt[j][0] - prt[i][0];
                }
                if(s[i] != 'G' and s[j] != 'G'){
                    ans+=prt[j][1] - prt[i][1];
                }
                if(s[i] != 'B' and s[j] != 'B'){
                    ans+=prt[j][2] - prt[i][2];
                }
                if((i + j)%2 == 0){
                    if(s[(i + j)/2] != s[i] and s[(i + j)/2]!=s[j]){
                        ans--;
                    }
                }
            }
        }
    }
    cout << ans;


    return(0);
}

//When we hit our lowest point, we are open to the greatest change.
//If I try, I fail. If I don't try, I'm NEVER GOING TO GET IT.
//Sometimes, life is like this dark tunnel. You can't always see the light at the end of the tunnel. But if you just keep moving... you will come to a better place.
//It is important to draw wisdom from diffrent places. If you take it from only one place it becomes rigid and stale.
//kuxtal jach uts chuchul u u páajtal máak jach táaj meyajilo'ob le castigadas tumen ch'aik descansos.


Measured memory_bytes: 3688
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100;
int N;
int A[2][MAX_N], nums[2 + 1][MAX_N + 1];


void solve() {
    REP(i, 2) {
        REP(j, N) {
            if (i == 0) {
                nums[0][j + 1] = nums[0][j] + A[i][j];
            } else {
                nums[1][j + 1] = max(nums[0][j + 1] + A[i][j], nums[1][j] + A[i][j]);
            }
        }
    }
    cout << nums[1][N] << endl;
}

int main() {
    cin >> N;
    REP(i, 2) REP(j, N) {
            cin >> A[i][j];
        }
    solve();
    return 0;
}

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

using namespace std;

void solve1()
{
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> dp(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		dp[i] = 1;
	}
	int res = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (a[j] < a[i])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		res = max(res, dp[i]);
	}
	cout << dp[n - 1] << endl;
}

void solve2()
{
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> dp(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
		dp[i] = 2e9;
	}
	for (int i = 0; i < n; ++i)
	{
		*lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
	}
	cout << lower_bound(dp.begin(), dp.end(), 2e9) - dp.begin() << endl;
}

int main()
{
	//solve1();
	solve2();
	return(0);
}

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

int main(void){
  double a,b,c,d,e,f;
  double x,y;
  while(cin >> a >> b >> c >> d >> e >> f){
    double det = a * e -b * d;
    x = (c * e - b * f) / det;
    y = (a * f - c * d) / det;
    if(x == -0){
      x = 0;
    }
    if(y == -0){
      y = 0;
    }
    printf("%.3f %.3f\n",x,y);
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main { 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] num = new int[100001];
    long total =0;
    for (int i =0; i<N; i++) {
      int a = sc.nextInt();
      total += a;
      num[a]++;
    }
    int Q = sc.nextInt();
    int[] B = new int[Q];
    int[] C = new int[Q];
    for (int i =0; i<Q; i++) {
      B[i] = sc.nextInt();
      C[i] = sc.nextInt();
    }
    for (int i =0; i<Q; i++) {
      total += (long)(C[i] - B[i]) * num[B[i]]; 
      num[C[i]] += num[B[i]];
      num[B[i]] =0;
      System.out.println(total);
    }
  }
}    

Measured memory_bytes: 61596
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
int main(){
  vector<int64_t> a(3);
  cin>>a[0]>>a[1]>>a[2];
  if(a[0]%2==0 || a[1]%2==0 || a[2]%2==0){
    cout<<0<<endl;
  }
  else{
    sort(a.begin(),a.end());
    cout<<a[0]*a[1]<<endl;
  }
}

Measured memory_bytes: 256
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <math.h>
#include <iomanip>
#define int long long
#define ll long long
//#define double long double
using namespace std;
//#pragma endregion

signed main()
{
	//int x;

	int h1, h2, m1, m2, k;
	int box, box1,box2;

	//int N;
	//int n;
	//int m;
	//int k;
	//string s;
	//string t;
	//int m1, m2;
	//int a, b, c, k;

	//long double aaa;

	//int k, d;
	//int all = 0;
	//double all;
	//double a, b;
	//double h, m;
	//int a[30000] = { 0 };
	//double c, d, e;

	//double mbox, hbox;
	//double box, box2;

	//int b = 0;

	//int box[10000] = { 0 };

	//bool flag = true;

	//string str;

	cin >> h1 >> m1 >> h2 >> m2 >> k;
	//cin >> s;

	box = (h1 * 60) + m1;
	box1 = (h2 * 60) + m2;

	box2 = box1 - box;

	box2 -= k;

	/*if (k >= b)
	{
		cout << s << "\n";
	}
	else
	{
		for (int i = 0; i < k; i++)
		{
			cout << s[i];
		}
		cout << "...\n";
	}*/
	
	//cout << b << "\n";

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	cout << box2 << "\n";

	//cout << fixed << setprecision(111) << all;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
string alp="abcdefghijklmnopqrstuvwxyz";
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);



int main(){fastio
    string s,t;cin>>s>>t;
    ll dp[s.size()+1][t.size()+1];
    ll ss=(ll)s.size();
    ll tt=(ll)t.size();
    s='0'+s;
    t='0'+t;
    rep(i,0,ss){
        dp[i][0]=0;
    }
    rep(i,0,tt){
        dp[0][i]=0;
    }
    rep(i,1,ss){
        rep(j,1,tt){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(s[i]==t[j]){
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
            }
        }
    }
    string ans="";
    ll ns=ss;
    ll nt=tt;
    ll now=dp[ss][tt];
    while(now>0){
        if(dp[ns][nt]==dp[ns-1][nt]){
            ns--;
            continue;
        }else if(dp[ns][nt]==dp[ns][nt-1]){
            nt--;
            continue;
        }else{
            ans=s[ns]+ans;
            ns--;
            nt--;
            now--;
            continue;
        }
    }
    cout<<ans<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 70656
#include <cstdio>
#include <iostream>
using namespace std;
int prime[1000005];
bool is_prime[1000005];
int seve(int n)
{
    int p=0;
    for(int i=0;i<=n;i++)
        is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prime[p++]=i;
            for(int j=2*i;j<=n;j+=i)
                is_prime[j]=false;
        }
    }
    return p;
}
int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",seve(n));
    }
    return 0;
}



Measured memory_bytes: 4424
/*
 Abu Jafor Mohammad Saleh
 ios_base :: sync_with_stdio(false);
 cin.tie(NULL);
 */

#include<cstdio>
#include<iomanip>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include <algorithm>
#include <unordered_map>
#define f first
#define s second
#define MOD 1000000007
#define ll long long
#define INF (int)1e9
#define PI 3.1415926535897932384626433832795
#define BOUNDARY(i, j) ((i >= 0 && i < rows) && (j >= 0 && j < columns))
#define mx 6e5 + 100;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//#include<bits/stdc++.h>
const int maxn = 20005;
using namespace std;
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
int rows,coloums;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    fast;
   // cout<<"DFGHJ"<<endl;
    int k,m;
    cin>>k>>m;
    k = k*500;
    if(k>=m)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


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

using namespace std;

int main() {
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> a(m);
    for (int i=0; i<m; i++) cin >> a[i];

    auto it = upper_bound(a.begin(),a.end(), x);
    cout << min(it - a.begin(), a.end() - it) << endl;
}

Measured memory_bytes: 256
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n, k;
    cin >> n >> k;
    cout << k * (ll)pow(k - 1, n - 1) << endl;
}

Measured memory_bytes: 384
import java.util.Scanner;

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

        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for (int i=0;i<n;i++){
            arr[i] = in.nextInt();
        }

        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1]= Math.abs(arr[1]-arr[0]);

        for(int i=2;i<n;i++){
            int temp = Integer.MAX_VALUE;
            int x = Math.max(0, i-k);
            for(int j=x; j<i;j++){

                int y = Math.abs(arr[i]-arr[j]);
                temp = Math.min(temp,(dp[j]+y));
                //System.out.println(temp+" "+arr[i]+" "+y+" "+arr[j]);
            }
            dp[i] = temp;


        }

//        for(int i=0;i<n;i++){
//            System.out.print(dp[i]+" ");
//        }
//        System.out.println();

        System.out.println(dp[n-1]);
    }
}


Measured memory_bytes: 50660
def main():
    N = int(input())
    A = list(map(int, input().split()))
    selectionSort(A, N)


def selectionSort(A, N):
    count = 0
    for i in range(N):
        minj  = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j
    
        if i != minj:
            A[i], A[minj] = A[minj], A[i]
            count += 1

    print(*A)
    print(count)


main()


Measured memory_bytes: 5604
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>
#include<numeric>

using namespace std;
typedef long long ll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
const ll INF = 1e18+1;

int H, W;
int a[501][501];

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> h1, h2, w1, w2;

    for (int i = 0; i < H; i++) {
        if (i % 2 == 0) {
            for (int j = 0; j < W; j++) {
                if (j == W - 1) {
                    if (a[i][j] % 2 == 1) {
                        if (i == H-1) break;
                        a[i+1][j]++;
                        h1.push_back(i+1); h2.push_back(i+2); 
                        w1.push_back(j+1); w2.push_back(j+1);
                    }
                    break;
                }
                if (a[i][j] % 2 == 1) {
                    a[i][j+1]++;
                    h1.push_back(i+1); h2.push_back(i+1); 
                    w1.push_back(j+1); w2.push_back(j+2);
                }
            }
        } else {
            for (int j = W-1; j >= 0; j--) {
                if (j == 0) {
                    if (a[i][j] % 2 == 1) {
                        if (i == H-1) break;
                        a[i+1][j]++;
                        h1.push_back(i+1); h2.push_back(i+2); 
                        w1.push_back(j+1); w2.push_back(j+1);
                    }
                    break;
                }
                if (a[i][j] % 2 == 1) {
                    a[i][j-1]++;
                    h1.push_back(i+1); h2.push_back(i+1); 
                    w1.push_back(j+1); w2.push_back(j);
                }
            }
        }
    }

    cout << h1.size() << endl;
    for (int i = 0; i < h1.size(); i++) {
        cout << h1[i] << " " << w1[i] << " "
             << h2[i] << " " << w2[i] << endl;
    }



}

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

using namespace std;

char S[101010];

int main()
{
	cin >> S;

	bool app[26];
	for (int i = 0; i < 26;i++) {
		app[i] = false;
	}
	for (int i = 0; S[i] != '\0';i++) {
		app[S[i] - 'a'] = true;
	}
	for (int i = 0; i < 26;i++) {
		if (!app[i]) {
			printf("%c\n", (char)(i + 'a'));
			return 0;
		}
	}
	puts("None");
	return 0;
}



Measured memory_bytes: 384
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;

int main(){

	mp::cpp_int a, b, c, l, r;

	std::cin>> a >> b >> c;

	l = abs(c - a - b)*(c - a - b);
	r = 4 * a * b;

	l = l - r;

	if (l > 0) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;



}


Measured memory_bytes: 256
a,b,c = map(int, input().split())
k = int(input())
for i in range(k+1):
    for j in range(k+1-i):
        l = k - j - i
        if a * 2**i < b * 2**j and b * 2**j < c * 2**l:
            print('Yes')
            exit()
print('No')


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

int main(){
    int n,m;cin>>n;
    string s;
    map<string,int> dic;
    for(int i=0;i<n;i++){
        cin>>s;
        dic[s]++;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>s;
        dic[s]--;
    }
    int ans=0;
    for(auto p:dic){
        auto v=p.second;
        if(v>ans)ans=v;
    }
    cout<<ans<<endl;
}


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

using std::cout;
using std::cin;
using std::endl;

/*  テンプレここから */
typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define INF (1e9)
#define INFL (1e18)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outYes(bool_val) cout << (bool_val ? "Yes" : "No") << endl;
#define outYES(bool_val) cout << (bool_val ? "YES" : "NO") << endl;
#define outPossible(bool_val) cout << (bool_val ? "Possible" : "Impossible") << endl;
#define outPOSSIBLE(bool_val) cout << (bool_val ? "POSSIBLE" : "IMPOSSIBLE") << endl;

template<typename A, size_t N, typename T>
void array_fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

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

    int n;
    cin >> n;
    std::vector<int> nums(n);
    for(int i = 0; i < n; ++ i) cin >> nums[i];

    int ans = 0;
    for(int a = 0; a < n; ++ a)
        for(int b = a+1; b < n; ++ b)
            ans += nums[a]*nums[b];

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
    using namespace std;
        
    int main(){
      string s;
      cin >> s;
      int ans = 0;
      int n = s.length();
      for(int i=0;i<n/2;++i){
      	if(s[i]!=s[n-1-i])
          	ans++;
      }
      cout << ans << endl;
      return 0;
    }

Measured memory_bytes: 256
def norma (list)
  result = Array.new(0,nil)
  for l in list
    if (l['total'] >= 1000000)
      result.push(l)
    end
  end
  return result
end

def total (input, staff)
  staff['total'] = staff['total']+(input[1]*input[2])
end

def getS (num,staff)
  for n in staff
    if (n['id'] == num)
      n # => {"total"=>1040000, "id"=>1001}, {"total"=>1040000, "id"=>1001}
      return n
    end
  end
  return nil
end

n = gets.to_i
while n != 0
  list = Array.new(0,nil)
  n.times do |i|
    data_s = gets
    data = data_s.split(nil)
    data = data.map{|d| d.to_i}
    
    if (getS(data[0],list) != nil)
      staff = getS(data[0],list)
      total(data,staff)
    else
      staff = {"id"=>data[0], "total"=>0}
      total(data,staff)
      list.push(staff)
    end
  end
  
  result = norma(list)
  if result.size != 0
    for r in result
      puts r['id']
    end
  else
    puts "NA"
  end
  n = gets.to_i
end

Measured memory_bytes: 2588
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N, K, S = MAP()
if S < 10**9:
	ans = [S]*K + [S+1]*(N-K)
else:
	ans = [S]*K + [S-1]*(N-K)

print(*ans)

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

int main()
{
ll k ;
cin >> k ;
rep(i,k)rep(j,k)rep(l,k){
  ans+=__gcd(i+1,__gcd(j+1,l+1));
}
cout << ans << endl;
return 0;
}

Measured memory_bytes: 3652
// binary search

package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		a := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			a[i], _ = strconv.Atoi(scanner.Text())
		}
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())
		cnt := 0
		low, high := 0, n-1
		for low <= high {
			cnt++
			mid := (low+high)>>1
			if k == a[mid] {
				break
			}
			if k < a[mid] {
				high = mid-1
			} else {
				low = mid+1
			}
		}
		fmt.Println(cnt)
	}
}



Measured memory_bytes: 1092
#include <bits/stdc++.h>
#include <stdio.h>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int gcd( int x, int y ){ return y ? gcd(y, x%y) : x; }
signed main() {
int x=0,y=0,z=0,w=0,n=0,m=0;
int a=0,b=0;
while (true) {
  std::cin >> x;
  if(x==0)break;
std::cin >> y;
rep(i,y){
  std::cin >> z>>w;
  n+=w-z;
}
if(n>=x)std::cout << "OK" << '\n';
else std::cout << x-n << '\n';
n=0;
}
}



Measured memory_bytes: 3104
a, b, c, d= gets.split(" ").map(&:to_i)
takahashi_hp = a
takahashi_attack = b
aoki_hp = c
aoki_attack = d

i = 0
while takahashi_hp > 0 || aoki_hp > 0
  aoki_hp -= takahashi_attack
  i += 1
  break if aoki_hp <= 0
  takahashi_hp -= aoki_attack
  i += 1
  break if takahashi_hp <= 0
end

if i % 2 == 0
  puts "No"
else
  puts "Yes"
end

Measured memory_bytes: 14212
mod = 1000000007
n = int(input())
end_a = [0,0,0,16]
end_g = [0,0,0,15]
end_ag = [0,0,0,4]
end_ac = [0,0,0,3]
end_ga = [0,0,0,4]
end_at = [0,0,0,4]
end_aga = [0,0,0,1]
end_agt = [0,0,0,1]
end_agg = [0,0,0,1]
end_atg = [0,0,0,1]
ans = [0,0,0,61]
for i in range(3, n+1):
    end_a.append(ans[i]%mod)
    end_g.append((ans[i] - end_ac[i])%mod)
    end_ag.append(end_a[i]%mod)
    end_ac.append((end_a[i] - end_ga[i])%mod)
    end_ga.append(end_g[i]%mod)
    end_at.append(end_a[i]%mod)
    end_agt.append(end_ag[i]%mod)
    end_agg.append(end_ag[i]%mod)
    end_atg.append(end_at[i]%mod)
    taboo = (end_ag[i] + end_ac[i] + end_ga[i] + end_agt[i] + end_agg[i] + end_atg[i])%mod
    ans.append((taboo*3 + (ans[i]-taboo)*4)%mod)
print(ans[n]%mod)

Measured memory_bytes: 38632
"use strict";
process.stdin.resume();
process.stdin.setEncoding("utf8");

let lines = []

var reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on("line", line => {
  lines.push(line);
});

reader.on("close", () => {
  let n = parseInt(lines.shift());
  let h = lines.shift().split(/\s/).map(i => parseInt(i));

  let ans = 0;
  while(h.filter(x => x > 0).length != 0) {
    let l = -1, r = -1;
    
    for (let i = 0; i < n; i++) {
      if (l == -1 && h[i] > 0) l = i;
      if (l != -1 && h[i + 1] <= 0 || i == n - 1) {
        r = i;
        break;
      }
      
    }
    
    for (let i = l; i <= r; i++) {
      h[i] -= 1;
    }
    ans++;
  }
  
  console.log(ans);
});


Measured memory_bytes: 21320
#include <stdio.h>
 
int p(int i){ return i / 2;}
int l(int i){ return 2 * i;}
int r(int i){ return 2 * i + 1;}
 
int main(){
  int h[512], size, n, i;
 
  scanf("%d", &size);
  for(i = 1; i <= size; ++i){
    scanf("%d", h + i);
  }
 
  for(i = 1; i <= size; ++i){
    printf("node %d: key = %d, ", i, h[i]);
    if(p(i)) printf("parent key = %d, ", h[p(i)]);
    if(l(i) <= size) printf("left key = %d, ", h[l(i)]);
    if(r(i) <= size) printf("right key = %d, ", h[r(i)]);
    puts("");
  }
  return 0;
}

Measured memory_bytes: 608
#include<iostream>
#include<stdio.h>
#include<cmath>

using namespace std;

int main() {
	double a, b, h, m;
	cin >> a >> b >> h >> m;

	double hx = h * 30.0+0.5*m;
	double mx = m * 6.0;

	double theta = hx - mx;
	if (theta > 180.0) {
		theta = 360.0 -theta;
	}
	double pi = 3.14159265359;

	double x = (a * a) +( b * b) - (2.0 * a * b * cos(theta * (pi/180.0)));
	printf("%.9f", sqrt(x)); 
	return 0;
}

Measured memory_bytes: 4228
#include<iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    //cout << s << endl;
    string str[4] = {"dream", "dreamer", "erase", "eraser"};
    int cnt = 0;
    while (cnt != s.length()) {
        int flg = 0;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < str[i].size(); ++j) {
                if (s[cnt + j] != str[i][j]) {
                    break;
                }
                if (j == str[i].size() - 1) {
                    flg = i + 1;
                }
            }
            //cout << flg << endl;
            if (i == 3 && flg == 0) {
                cout << "NO" << endl;
                return 0;
            }
        }
        //cout << "flg " << flg << endl;
        for (int k = 1; k < 5; ++k) { //sample 2 dreamer eraser
            //cout << "flg " << flg << "  k " << k << endl;
            if (flg == k) {
                int tmp = cnt;
                if (k == 2) {
                    for (int l = cnt + 5; l <= tmp + 9; ++l) { //dream erase
                        //cout << "l " << l << endl;
                        if (s[l] != str[2][l - (cnt + 5)]) {
                            cnt += str[k - 1].size(); //plus dreamer
                            //cout << "cnt1 " << cnt << endl;
                            break;
                        }
                        if (l == cnt + 9) {
                            cnt += 5; //plus dream
                            //cout << "cnt2 " << cnt << endl;
                        }
                    }
                } else {
                    cnt += str[k - 1].size();
                    //cout << "cnt3 " << cnt << endl;
                }
            }
        }
    }
    cout << "YES" << endl;
    return 0;
}


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

#define fi first
#define se second
long long ans[10], h, w, n;
pair<int, int> p[100010];
set<long long> candidate[10];

int main() {
    scanf("%lld%lld%lld", &h, &w, &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld%lld", &p[i].fi, &p[i].se);
        p[i].fi--, p[i].se--;
    }
    sort(p, p + n);
    for(int i = 0; i < n; i++) {
        for(int dx = -2; dx <= 2; dx++) {
            for(int dy = -2; dy <= 2; dy++) {
                int x = p[i].fi + dx, y = p[i].se + dy, z = x + 2, t = y + 2;
                if(x < 0 || y < 0 || z >= h || t >= w) continue;
                int cnt = 0;
                for(int a = 0; a < 3; a++) {
                    for(int b = 0; b < 3; b++) {
                        int c = a + x, d = b + y, f = lower_bound(p, p + n, make_pair(c, d)) - p;
                        if(f < n && p[f].fi == c && p[f].se == d) cnt++;
                    }
                }
                candidate[cnt].insert(x*w + y);
            }
        }
    }
    for(int i = 1; i <= 9; i++) ans[i] = candidate[i].size();
    ans[0] = (h-2) * (w-2);
    for(int i = 1; i <= 9; i++) ans[0] -= ans[i];
    for(int i = 0; i <= 9; i++) printf("%lld\n", ans[i]);
}


Measured memory_bytes: 118272