akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int


int main(){
    int n;
    cin>>n;
    int arr[n+1][3];
    int dp[n+1][3];

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

    dp[1][0]=arr[1][0];
    dp[1][1]=arr[1][1];
    dp[1][2]=arr[1][2];
    int ans=INT_MAX;
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+arr[i][0];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+arr[i][1];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+arr[i][2];
    }
    ans= max(dp[n][0],max(dp[n][1],dp[n][2]));
    cout<<ans<<endl;
    return 0;
}



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

int main(){
    int a;
    
    int b;
    
    int c;
    
    cin >> a >> b >> c;
    
    if (a>b){
        if (b>c){
            cout << c << " " << b << " " << a << endl;
        } else if (a>c){
            cout << b << " " << c << " " << a << endl;
        } else {
            cout << b << " " << a << " " << c << endl;
        }
    } else {
        if (b<c){
            cout << a << " " << b << " " << c << endl;
        } else if (a>c){
            cout << c << " " << a << " " << b << endl;
        } else {
            cout << a << " " << c << " " << b << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
int main()
{
    fastio;
    ll n,m,i,j,ans=0;
    cin>>n>>m;
    vector<pair<ll,ll> >v(n);
    priority_queue<ll>pq;
    for(i=0;i<n;i++)
    {
        cin>>v[i].first>>v[i].second;
    }
    sort(v.begin(),v.end());
    for(i=1,j=0;i<=m;i++)
    {
        for(;v[j].first==i;j++)
        {
            pq.push(v[j].second);
        }
        if(pq.size()!=0)
        {
           ans+=pq.top();
           pq.pop();
        }
    }
    cout<<ans;
}


Measured memory_bytes: 2936
# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    
    l = int(lines[0])

    return (l, )


def solve(l, ):

    result = (l / 3) ** 3

    return  result


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Measured memory_bytes: 3188
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
var L=Arr.shift();
var obj={};
for(var i=0;i<L;i++){
   var arr=Arr[i].split(" ");
   if(arr[0]=="insert")obj[arr[1]]=true;
   else console.log(obj.hasOwnProperty(arr[1]) ? "yes":"no");
}

Measured memory_bytes: 183896
#include<bits/stdc++.h> 
using namespace std;
int main()
{
	char s[200],t[200];
	scanf("%s%s",s,t);
	int len=strlen(s);
	int tt=0;
	while(++tt<=len)
	{
		char p[200];
		for(int i=0;i<len-1;i++)
			p[i+1]=s[i];
		p[0]=s[len-1];
		bool flag=true;
		for(int i=0;i<len;i++)s[i]=p[i];
		for(int i=0;i<len;i++)
			if(s[i]!=t[i])flag=false;
		if(flag){puts("Yes");return 0;}
	}
	puts("No");
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  # エラトステネス　O(N loglog N)
        self.n = n
        self.table = list(range(n+1))       # 最小素因数のリスト
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):  # 素数判定　O(1)
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             # 素因数分解 O(logN)  (試し割りだとO(sqrt(N)))
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             # 素因数分解（個数のリスト） O(logN)
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X, mod=None):        # n個の最大公約数　X:n個のリスト  (O((logN)^2))
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

    def prime_lcm(self, X, mod=None):       # n個の最小公倍数　X:n個のリスト  (O((logN)^2))
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod


#####################################################################################################


int(input())
N = 10**6 + 1
table = PrimeFactor(N)
A = list(map(int, input().split()))
MOD = 10**9+7
temp = table.prime_lcm(A,MOD)
res = 0
for a in A:
    res += temp*pow(a,MOD-2,MOD)
print(res%MOD)






Measured memory_bytes: 80944
n,k=map(int,input().split())
l=[0]+[i%k-1 for i in list(map(int,input().split()))]
from itertools import accumulate
l=list(accumulate(l))
import collections
d=collections.defaultdict(int)
d[0]+=1
ans=0
for i in range(1,n+1):
    if i>=k:
        d[l[i-k]%k]-=1
    ans+=d[l[i]%k]
    d[l[i]%k]+=1
print(ans)

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

const int N = 3000;

int a,b,c,d,e,f,ans,total;
int dp[N+10][N+10];

void dfs(int sugar,int water){
    if (dp[sugar][water]!=-1) return;
    dp[sugar][water] = 1;
    if (sugar*100>e*water) return;
    if (sugar+water>f) return;
    if (total==0 || sugar*total>ans*(sugar+water)){
        if (water>0){
            ans = sugar;
            total = sugar + water;
        }
    }
    dfs(sugar,water+100*a);
    dfs(sugar,water+100*b);
    dfs(sugar+c,water);
    dfs(sugar+d,water);
}

int main(){
    //freopen("F:\\rush.txt","r",stdin);
    memset(dp,255,sizeof dp);
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> a >> b >> c >> d >> e >> f;
    dfs(0,0);
    cout << total << ' '<< ans << endl;
    return 0;
}


Measured memory_bytes: 35712
#include<bits/stdc++.h>
using namespace std;
long long a=0;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //cout.setf(ios_base::fixed,ios_base::floatfield);
    int n,m;
    cin>>n>>m;
    cout<<max({n+m,n-m,n*m})<<'\n';
}

Measured memory_bytes: 3556
module ABC085C
	sub Main(ByVal args() as String)
		dim n,y,i,j,k as integer
		dim arr(2) as string
		arr=Split(Console.ReadLine())
		n=arr(0):y=arr(1)
		for i=0 to n
			for j=0 to n-i
				k=n-i-j
				if i*1000+j*5000+k*10000=y
					Console.WriteLine("{0} {1} {2}",k,j,i)
					return
				end if
			next
		next
		Console.WriteLine("-1 -1 -1")
	end sub
end module


Measured memory_bytes: 13532
#include<stdio.h>
#include<math.h>

int main(void){
    double a,b,C,S,L,h;

    scanf("%lf %lf %lf",&a,&b,&C);
    S = 0.5 * a * b * sin(2.0 * M_PI * C / 360.0);

    L = a + b + sqrt(a * a  + b * b - 2.0 * a * b * cos(2.0 * M_PI * C / 360.0));

    h = 2.0 * S / a;

   printf("%lf\n%lf\n%lf\n",S,L,h);
   return 0;
}

Measured memory_bytes: 648
N,M = list(map(int,input().split(' ')))
 
abp = []
 
for i in range(M):
	a,b = list(map(int,input().split(' ')))
	abp.append([a,b])
 
abp.sort(key=lambda x:x[1])
 
ep = 0
ans = 0 
for a,b in abp:
	if a >= ep:
		ep = b
		ans = ans + 1

print(ans)


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

using namespace std;

int main() {

    int A, B, T;
    cin >> A >> B >> T;
    int currentTime = A;
    int ans = 0;
    while (currentTime <= T) {
        ans += B;
        currentTime += A;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define DELNL        cin.ignore(numeric_limits<streamsize>::max(),'\n')
#define VV(T,h,w)    vector<vector<T>>(h,vector<T>(w))
#define VVI(T,h,w,i) vector<vector<T>>(h,vector<T>(w,i))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
    ll n = in();
    vector<ll>p(n);
    REP(i, n)p[i] = in();
    ll ans = 0;
    REP1(i, n - 2)
        if (
            p[i - 1] < p[i] && p[i] < p[i + 1] ||
            p[i - 1] > p[i] && p[i] > p[i + 1])
            ++ans;
    cout << ans << endl;
}

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

using namespace std;

typedef pair<int,int> ii;
#define X first
#define Y second

const int N=1e5+10;

string s;
int f[N];

int main(){
        cin>>s;
        int n=s.length();
        f[n-1]=n;
        for(int i=n-2;i>=0;i--) if (s[i]==s[i+1]) f[i]=f[i+1];
        else f[i]=i+1;
        for(int i=n;i>=n/2;i--){
                int L=n-i,R=i;
                if (f[L]>=R){
                        cout<<i;
                        return 0;
                }
        }
}


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

using namespace std;

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

	scanf("%d %d %d %d",&a,&b,&c,&k);
	
	long long int maximo = max(max(a,b),c);
	long long int mm = maximo;

	if(mm==a){
		maximo = maximo << k;
		maximo += b +c;
	}
	else if(mm==b){
		maximo = maximo << k;
		maximo += a + c;
	}
	else{
		maximo = maximo << k;
		maximo += a + b;
	}

	printf("%lld\n",maximo);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
int mpow(int base, int exp); 
void ipgraph(int m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vi g[N];
int a[N];

void solve(){
	int i,n,start,end,times;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	ll money=1000,shares;
	for(i=0;i<n-1;i++){
		if(a[i]>=a[i+1])continue;
		shares=money/a[i];
		money+=shares*(a[i+1]-a[i]);
	}
	cout<<money<<endl;

}

int main() {
	ios_base::sync_with_stdio(0);
	int i,t=1;
	//cin>>t;
	for(i=1;i<=t;i++){
		solve();
	}
	return 0;
}

int mpow(int base, int exp) {
	base %= mod;
	int result = 1;
	while (exp > 0) {
		if (exp & 1) result = ((ll)result * base) % mod;
		base = ((ll)base * base) % mod;
		exp >>= 1;
	}
	return result;
}

void ipgraph(int n, int m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}




Measured memory_bytes: 10680
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

void solve(int n){
  int a,b;
  vector<int> imos(100005,0);
  for(int i=0;i<n;i++){
    cin>>a>>b;
    imos[a-1]++;
    imos[b]--;
  }

  int ans=0;
  for(int i=1;i<=n;i++){
    imos[i]+=imos[i-1];
    if(i<=imos[i])ans=max(ans,i);
  }

  cout<<ans<<endl;
}

int main(){
  int n;
  while(cin>>n){
    solve(n);
  }
  return 0;
}



Measured memory_bytes: 3096
#include <cstdio>
#include <algorithm>

const int INF = 1001001001;

int M, N;
int P[10000], C[500], E[500];
int dp[500][10001];

int main(){
    scanf("%d %d", &M, &N);

    for(int i=0;i<M;i++){
        scanf("%d", P+i);
    }
    std::sort(P, P+M);
    std::reverse(P, P+M);

    for(int i=1;i<M;i++){
        P[i] += P[i-1];
    }
    
    for(int i=0;i<N;i++){
        scanf("%d %d", C+i, E+i);
    }

    for(int i=0;i<=M;i++){
        if(i == 0){dp[0][i] = 0;}
        else if(i <= C[0]){dp[0][i] = E[0];}
        else{dp[0][i] = INF;}
    }

    for(int i=1;i<N;i++){
        for(int j=M;j>=0;j--){
            dp[i][j] = dp[i-1][j];
            if(j == M && C[i] > M){
                dp[i][j] = std::min(dp[i][j], E[i]);
            }
            if(j < M){dp[i][j] = std::min(dp[i][j], dp[i][j+1]);}
            if(j - C[i] >= 0){
                dp[i][j] = std::min(dp[i][j], dp[i-1][j-C[i]] + E[i]);
            }
        }
    }

    // for(int i=0;i<N;i++){
    //     for(int j=0;j<=M;j++){
    //         printf("%d ", dp[i][j]);
    //     }
    //     puts("");
    // }

    int res = 0;
    for(int i=0;i<=M;i++){
        // printf("%d: %d, %d\n", i, i>0?P[i-1]:0, dp[N-1][i]);
        res = std::max(res, (i>0?P[i-1]:0) - dp[N-1][i]);
    }

    printf("%d\n", res);
}

Measured memory_bytes: 20600
import java.util.Arrays;
import java.util.Scanner;
 //区間スケジューリング
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		final int n = sc.nextInt();
 
		int robots[][] = new int[n][2];
 
		int x, l;
		for (int i = 0; i < n; i++) {
			x = sc.nextInt();
			l = sc.nextInt();
			robots[i][0] = x - l;
			robots[i][1] = x + l;
		}
		//X+Lが小さい順に並べる
		Arrays.sort(robots, (a, b) -> Long.compare(a[1], b[1])); 
		/*
		for(int i = 0;i<n-1;i++) {
			for(int j = i+1;j<n;j++) {
				if(robots[i][1]>robots[j][1]) {
					int temp_a = robots[i][1];
					robots[i][1] = robots[j][1];
					robots[j][1] = temp_a;
					int temp_b = robots[i][0];
					robots[i][0] = robots[j][0];
					robots[j][0] = temp_b;
					
					}
			}
		}
		*/
        //ロボットの腕が既に残すと決めたロボットの腕と重ならなければロボットを残す。
		int filled = Integer.MIN_VALUE;
		int count = 0;
 
		for (int i = 0;i<n;i++) {
			if (filled <= robots[i][0]) {
				count++;
				filled = robots[i][1];
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 95128
N = int(input())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

dp = [[0] * (N + 1),[0] * (N + 1),[0] * (N + 1)]

for i in range(N):
    dp[0][i + 1] = max(dp[1][i],dp[2][i]) + a[i]
    dp[1][i + 1] = max(dp[2][i],dp[0][i]) + b[i]
    dp[2][i + 1] = max(dp[0][i],dp[1][i]) + c[i]
    
print(max(dp[0][N],dp[1][N],dp[2][N]))



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

int main(){
  
  int n,n4,n3,n2,n1,count = 0;
  cin >> n;
  n4 = n / 1000;
  n3 = n % 1000 / 100;
  n2 = n % 100 / 10;
  n1 = n % 10;
  
  if((n1 == n2 && n1 == n3) || (n2 == n3 && n2 == n4)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}
  
  

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)
n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(lambda x:int(x)-1,input().split())
  t[a].append(b)
  t[b].append(a)
  ab.append((min(a,b),max(a,b)))
k = max(map(len,t))
d = {}
def dfs(pre,cur,col):
  cn = 1 if col != 1 else 2
  for i in t[cur]:
    if i == pre:
      continue
    d[(min(i,cur),max(i,cur))] = cn
    dfs(cur,i,cn)
    cn += 1
    if col == cn:
      cn += 1
dfs(0,0,0)
print(k)
for i in ab:
  print(d[i])

Measured memory_bytes: 80968
n = gets.chomp.to_i
t, h = [0, 0]
n.times do 
  c = gets.split /\s/
  case c[0] <=> c[1]
  when 1
    t += 3
  when -1
    h += 3
  else
    t += 1
    h += 1
  end
end
puts "#{t} #{h}"



Measured memory_bytes: 6996
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#if __cplusplus >= 201103L
#include <chrono>
using namespace std::chrono;
#endif
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
#ifdef LOCAL
#define prl puts("\n------------------\n")
#define prln(x) (cout << #x << ' ' << x << endl)
#define pr(x) (cout << #x << ' ' << x << ' ' )
#define prv(x) (cout << x << ' ')
#else
#define prl 
#define prln(x) 
#define pr(x)
#define prv(x)
#endif
#define clr(x) memset((x), 0, sizeof((x)))
#define clr1(x) memset((x), -1, sizeof((x)))
#define endl "\n"
#define pi acos(-1)
#define rep(i, st, ed) for (int i = (st); i <= (ed); ++i)
#define rep0(i, st, ed) for (int i = (st); i < (ed); ++i)
#define per(i, st, ed) for (int i = (st); i >= ed; --i)
template<class T> void _sf(T &x) {cin >> x;}
void _sf(int &x) {scanf("%d", &x);}
void _sf(ll &x) {scanf("%lld", &x);}
void _sf(double &x) {scanf("%lf", &x);}
void _sf(char &x) {scanf(" %c", &x);}
void _sf(char *x) {scanf("%s", x);}
void sf() {}
template <class T, class...U> void sf(T & head, U&... tail) { _sf(head); sf(tail...);}
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const int maxn = 1e5 + 5;
int a[maxn], b[maxn], c[maxn];
int dp[maxn][4];

int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        #if __cplusplus >= 201103L
        auto start = steady_clock::now();
        #endif
    #endif
    int n = read();
    rep(i, 1, n) {
        sf(a[i], b[i], c[i]);
    }
    rep(i, 1, n) {
        dp[i][1] = max(dp[i - 1][2] + a[i], dp[i - 1][3] + a[i]);
        dp[i][2] = max(dp[i - 1][1] + b[i], dp[i - 1][3] + b[i]);
        dp[i][3] = max(dp[i - 1][1] + c[i], dp[i - 1][2] + c[i]);
    }
    cout << max(dp[n][1], max(dp[n][2], dp[n][3])) << endl;
    #ifdef LOCAL
        #if __cplusplus >= 201103L
        auto end = steady_clock::now();
        duration<double> time_span = duration_cast<duration<double>>(end - start);;
        printf("Total time: %.6fs\n", time_span.count());
        #endif
    #endif
    return 0;
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }

struct UF{
  vi sz, p;
  int comps;

  UF(int s) : comps(s) {
    sz.resize(comps + 1);
    p.resize(comps + 1);
    init();
  }

  void init(){
    for(int i = 0; i <= comps; i++){
      sz[i] = 1;
      p[i] = i;
    }
  }

  int fset(int u){
    return u == p[u] ? u : p[u] = fset(p[u]);
  }

  bool connect(int u, int v){
    u = fset(u);
    v = fset(v);
    if(u != v){
      if(sz[v] > sz[u]){
        swap(u, v);
      }
      sz[u] += sz[v];
      p[v] = u;
      comps--;
      return true;
    }
    return false;
  }
};

map<ii, int> cnt;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n, k, l;
  cin >> n >> k >> l;
  UF a(n), b(n);
  for(int i = 0; i < k; i++) {
    int u, v;
    cin >> u >> v;
    a.connect(u, v);
  }
  for(int i = 0; i < l; i++) {
    int u, v;
    cin >> u >> v;
    b.connect(u, v);
  }
  for(int i = 1; i <= n; i++) {
    cnt[{a.fset(i), b.fset(i)}]++;
  }
  for(int i = 1; i <= n; i++) {
    cout << cnt[{a.fset(i), b.fset(i)}] << " ";
  }
}

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

int main() {
  int n;
  
  while( cin >> n, n ) {
    map<char, char> mp;
    for( int i=0; i<n; i++ ) {
      char a, b;
      cin >> a >> b;
      mp[a] = b;
    }
    
    string res = "";
    int m;
    cin >> m;
    for( int i=0; i<m; i++ ) {
      char a;
      cin >> a;
      if( mp.count(a) ) a = mp[a];
      res += a;
    }

    cout << res << endl;
  }
  
  return 0;
}

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

int main()
{
  int64_t X, n = 100;
  cin >> X;
  for (int y = 1; y <= 4000; y++)
  {
    n += n / 100;
    if (n >= X)
    {
      cout << y << endl;
      break;
    }
  }
}


Measured memory_bytes: 3624
#include <cstdio>
#include <cstdlib>
using namespace std;
int main(void){
    int n, max=-101, min = 101;
    scanf("%d",&n);
    int a[101], c=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(i!=0 && a[i-1] == a[i]){
            c++;
        }
        if(max < a[i]) max = a[i];
        if(min > a[i]) min = a[i];
    }
    if(c==n-1) {
        printf("0\n");
        return 0;
    }
    long long int cost, ans, t;
    for(int i=min;i<=max;i++){
    	cost = 0;
    	for(int k=0;k<n;k++){
    		t = abs(i-a[k]); 
    		cost += t*t;
    	}
    	if(i==min) ans = cost;
    	if(ans > cost) ans = cost;
    }
    
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main() {
	string S;
	cin >> S;
	long long n = 0, r = 0;
	for (char c : S) {
		if (c == 'W') {
			r += n;
		} else {
			n += 1;
		}
	}
	cout << r << endl;
}


Measured memory_bytes: 640
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
D = []
d = 0
for b, c in BC:
    D += [c]*b
    d += b
    if d >= N:
        break
for i in range(N):
    if i < d and A[i] < D[i]:
        A[i] = D[i]
    else:
        break
print (sum(A))

Measured memory_bytes: 34120
#include <atcoder/dsu>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

vector<int> solve(ll N, vector<int>& X, vector<int>& Y) {
    vector<pii> P(N);
    for ( int i = 0; i < N; i++ ) {
        P[i] = pii(X[i],Y[i]);
    }
    sort(P.begin(), P.end());
    vector<int> yr(N);
    int ym = N;
    for ( int i = 0; i < N; i++ ) {
        int y = P[i].second;
        ym = min(ym, y);
        yr[ym] = max(yr[ym], y);
    }
    for ( int i = 1; i < N; i++ ) {
        yr[i] = max(yr[i],yr[i-1]);
    }
    atcoder::dsu uy(N);
    for ( int i = 0; i < N; i++ ) {
        uy.merge(i,yr[i]);
    }
    vector<int> ans(N);
    for ( int i = 0; i < N; i++ ) {
        ans[i] = uy.size(Y[i]);
    }

    return ans;
}

vector<int> solve_small_1(ll N, vector<int>& X, vector<int>& Y) {
    atcoder::dsu uf(N);
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < N; j++ ) {
            if ( X[i] < X[j] && Y[i] < Y[j] ) {
                uf.merge(i,j);
            }
        }
    }
    vector<int> ans(N);
    for ( int i = 0; i < N; i++ ) {
        ans[i] = uf.size(i);
    }
    return ans;
}
struct Data {
    int id;
    ll N;
    vector<int> X;
    vector<int> Y;
};
void test() {
    mt19937 mt(0);
    //uniform_int_distribution<ll> rnd_v(0, n-1);

    int n = 100;
    int id = 0;
    vector<Data> ts;
    for ( int i = 0; i < 100; i++ ) {
        vector<int> X(n), Y(n);
        for ( int i = 0; i < n; i++ ) {
            X[i] = i;
            Y[i] = i;
        }
        shuffle(X.begin(), X.end(), mt);
        shuffle(Y.begin(), Y.end(), mt);
        ts.push_back({++id,n,X,Y});
    }
    
    for ( Data& t : ts ) {
        auto ans0 = solve(t.N,t.X,t.Y);
        auto ans1 = solve_small_1(t.N,t.X,t.Y);
        for ( int i = 0; i < t.N; i++ ) {
            if ( ans0[i] != ans1[i] ) {
                cout << t.id << " " << ans0[i] << " " << ans1[i] << "\n";
            }
        }
    }
    cout << "end" << "\n";
}

int main() {
    //test();
    ll N;
    cin >> N;
    vector<int> X(N), Y(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> X[i] >> Y[i];
        X[i]--, Y[i]--;
    }
    auto ans = solve(N,X,Y);
    for ( int i = 0; i < N; i++ ) {
        cout << ans[i] << "\n";
    }    
    return 0;
}

Measured memory_bytes: 8724
#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define ls (k << 1)
#define rs (k << 1 | 1)
#define N 100005
int n, m, a, b, c, ans;
int main ()
{
    scanf("%d %d %d", &a, &b, &c);
    ans = b + c;
    if (a + b < c)
        ans -= c - a - b - 1;
    printf("%d\n", ans);
    return 0;
}

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

int main() {
    int n,k;
    cin >> n >> k;
    vector<double> p(n);
    
    double y;
    cin >> y;
    p[0] = (y+1)/2;

    for(int i = 1; i < n; i++) {
        double x;
        cin >> x;
        p[i] = p[i-1] + (x+1)/2;
    }

    vector<double> a(n-k+1);
    a[0] = p[k-1];
    for(int i = k; i < n; i++){
        a[i-k+1] = p[i]-p[i-k];
    }

    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    cout << fixed << setprecision(10);
    cout << a[0] << endl;

    return 0;
}

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

int main(){
    int n;
    cin>>n;
    long long a[3*n];
    priority_queue<long long,vector<long long>,greater<long long>> pq;
    long long A[n+1]={};
    for(int i=0;i<3*n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        pq.push(a[i]);
        A[0]+=a[i];
    }
    for(int i=n;i<2*n;i++){
        pq.push(a[i]);
        A[i-n+1]=A[i-n]+a[i]-pq.top();
        pq.pop();
    }

    priority_queue<long long,vector<long long>> pql;

    long long b[n+1]={};
    for(int i=0;i<n;i++){
        pql.push(a[i+2*n]);
        b[0]+=a[i+2*n];
    }
    //cerr<<b[0]<<endl;
    for(int i=0;i<n;i++){
        pql.push(a[n*2-1-i]);
        b[i+1]=b[i]+a[2*n-1-i]-pql.top();
        pql.pop();
        //cerr<<b[i+1]<<endl;
    }

    long long ans=-1e18;

    for(int i=0;i<=n;i++){
        ans=max(A[i]-b[n-i],ans);
        //cerr<<A[i]<<" "<<b[n-i]<<endl;
    }

    cout<<ans<<endl;

         
}

Measured memory_bytes: 6516
ulong[] A;

ulong cost(ulong i, ulong j) {
	switch(j) {
		case 0, 4: // never visit there
			return A[i];
		case 1, 3: // even(x > 0)
			return A[i] == 0 ? 2 : A[i] % 2;
		case 2: // odd
			return (A[i] + 1) % 2;
		default: return 0;
	}
}

// dp[i][j]
// i: point
// j: current mode(details on editorial)

// allowed to move any times
// just need to take care of the parity of A[i]

void main() {
	auto L = ri;
	A = L.iota.map!(i => readAs!ulong).array;
	auto dp = new ulong[][](L+1, 5);
	foreach(ref v; dp) v[] = INF;
	dp[0][0] = 0;
	foreach(i; 0..L) foreach(j; 0..5) foreach(k; j..5) {
		dp[i+1][k] = min(dp[i+1][k], dp[i][j] + cost(i, k));
	}
	dp[L].reduce!min.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

const long INF = 1UL << 60;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 23036
def score(x):
  sc = 0
  th = 1
  for _ in [0]*10:
    a = 2
    b = 3
    if x[th]==10: a=1
    elif x[th]+x[th+1]!=10: b=2
    sc += sum(x[th:th+b])
    th += a
  return x[0], sc

while 1:
  n = input()
  if n==0: break
  A = sorted([score(map(int, raw_input().split())) for _ in [0]*n])
  for a, b in sorted(A, key=lambda x: -x[1]): print a,b

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


using namespace std;


#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()


ll sum(int n);


void go(){
	int H,W;cin>>H>>W;
	char ch;
	int num;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			string wor;cin>>wor;
			if(wor=="snuke"){
				num=i+1;
				ch=65+j;
			}
		}
	}
	cout << ch << num;
}
int main(){
   
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   go();

   return 0;
}

ll sum(int n){                
   if(n == 0){
      return n;
   }else{
      return sum(n/10) + n%10;
   }
}


Measured memory_bytes: 256
import math
a,b,x=map(float,input().split())
x=x*math.pi/180
S=a*b*0.5*math.sin(x)
print(S)
print(a+b+math.sqrt(a**2 + b**2 -2*a*b*math.cos(x)))
print(2*S/a)


Measured memory_bytes: 5688
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repp(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;

signed main(){
    int m, Nmin, Nmax;
    while(1){
        cin >> m >> Nmin >> Nmax;
        if(m + Nmin + Nmax == 0) break;
        vector<int> d(m);
        rep(i, 0, m){
            cin >> d[i];
        }
        sort(all(d));
        reverse(all(d));
        int MAX = 0, ans = -1;
        rep(i, Nmin, Nmax + 1){
            int diff = d[i - 1] - d[i];
            if(MAX <= diff){
                MAX = diff;
                ans = i;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1212
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
typedef long long ll;
using namespace std;

int main()
{
	string S;
	cin >> S;
	int ans = 0, num = 0;
	for (int i = 0; i < S.size(); i++)
	{
		if (i % 2 == 0 && S[i] == '0') num++;
		else if (i % 2 == 1 && S[i] == '1') num++;
	}
	ans = num;
	num = 0;
	for (int i = 0; i < S.size(); i++)
	{
		if (i % 2 == 0 && S[i] == '1') num++;
		else if (i % 2 == 1 && S[i] == '0') num++;
	}
	ans = min(ans, num);
	cout << ans;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll t;
double ret = 0;
vl X;
vl Y;
double dist[9][9];

void input() {
  IN(N);
  ll x, y;
  X.pb(-1);
  Y.pb(-1);
  REP(i, N) {
    IN(x);
    IN(y);
    X.pb(x);
    Y.pb(y);
  }
}

void solve() {
  FOR(i, 1, N+1) {
    FOR(j, 1, N+1) {
      double sx = X[i];
      double sy = Y[i];
      double tx = X[j];
      double ty = Y[j];
      dist[i][j] = sqrt((sx-tx)*(sx-tx) + (sy-ty)*(sy-ty));
    }
  }
  vector<ll> index;
  ll factN = 0;
  REP(i, N) {
    index.pb(i+1);
  }
  do {
    factN++;
    REP(i, N-1) {
      ret += dist[index[i]][index[i+1]];
    }
  } while(next_permutation(ALL(index)));
  ret /= (double)factN;
  cout << setprecision(10);
  PRINT(ret);
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
int main(){
    long long N;
    cin >> N;
    long long ans = 0;
    for(long long i = 1; i * i < N; i++){
        if((N - i) % i == 0 && N % ((N - i) / i) != 0) ans += (N - i) / i;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.nextLine());
    String[] S = sc.nextLine().split(" ");
    long ans = 0;
    for(int i = 0; i < N; i++){
      long n = Long.parseLong(S[i]);
      ans += (n-1);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
int main()
{
	// long long int n;
	// cin>>n;
	// cout<<n;
	string s;
	cin>>s;
	int sum=0;
	for (int i = 0; i < s.size(); ++i)
	{
		sum+=(s[i]-'0');
	}
	if(sum%9==0)
		cout<<"Yes";
	else
		cout<<"No";
}

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

const ll maxs = 1e6+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e9;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert

int main(){
    //freopen("input00.txt","r",stdin);
    ll T = 1;
    //cin>>T;
    while(T--){
        string s;
        cin>>s;
        bool res = true;
        for(ll i=0;i<s.size();i++){
            if(i&1){
                if(s[i]!='i')
                    res = false;
            }
            else{
                if(s[i] != 'h')
                    res= false;
            }
        }

        if(s.size()&1)
            res = false;
        
        if(res)
            cout << "Yes";
        else
            cout << "No";
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
#define ll  long long 
  vector<ll>to[1000005];
int main(){
  ll a,b,c,d;cin>>a>>b;
  for(ll i=b/a;i>0;i--){
    if(b%i==0&&b/i>=a){
      cout<<i;
      return 0;
    }
  }
}


Measured memory_bytes: 23680
from operator import itemgetter

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


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))

Measured memory_bytes: 109512
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, x1_, y1_, x2_, y2_;

vector<int> x, y;

int main()
{
	scanf("%d", &n);
	scanf("%d", &m);

	x = vector<int>(n);
	y = vector<int>(n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x[i]);
		scanf("%d", &y[i]);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (x[i] > x[j])
			{
				swap(x[i], x[j]);
				swap(y[i], y[j]);
			}
		}
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &x1_);
		scanf("%d", &y1_);
		scanf("%d", &x2_);
		scanf("%d", &y2_);

		int s = distance(x.begin(), upper_bound(x.begin(), x.end(), x1_ - 1));
		int t = distance(x.begin(), lower_bound(x.begin(), x.end(), x2_ + 1));

		int ret = 0;

		for (int j = s; j < t; j++)
		{
			if (y1_ <= y[j] && y[j] <= y2_)
			{
				ret++;
			}
		}

		printf("%d\n", ret);
	}

	return 0;
}

Measured memory_bytes: 2784
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stdlib.h>

using namespace std;

int main() {
    int c[3][3];
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> c[i][j];
        }
    }
    int a[3],b[3];
    a[0] = 0;
    for(int j = 0; j < 3; j++) {
        b[j] = c[0][j];
    }
    a[1] = c[1][0] - b[0];
    a[2] = c[2][0] - b[0];
    bool flag = true;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(c[i][j] != a[i] + b[j]) {
                flag = false;
            }
        }
    }
    if(flag == false) {
        cout << "No";
    }else {
        cout << "Yes";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {0, 1, 0, -1, 1, -1, -1, 1};
int dy[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
struct PMA{
  int next[0x100];
  bool match;
  PMA() { memset(next, -1, sizeof(next)); match = false;}
};
int SIZE = 0;
PMA P[200];
string URDL = "URDL";
int make_PMA(){
  P[SIZE] = PMA();
  return SIZE++;
}
void build_PMA(vector<string> vs){
  SIZE = 0;
  int root = make_PMA();
  for(int i = 0; i < vs.size(); i++){
    int t = root;
    for(int j = 0; j < vs[i].size(); j++){
      if(P[t].next[vs[i][j]] == -1){ P[t].next[vs[i][j]] = make_PMA(); }
      t = P[t].next[vs[i][j]];
    }
    P[t].match = true;
  }
  queue<int> que;
  for(int i = 0; i < 4; i++){
    char c = URDL[i];
    int next = P[root].next[c];
    if(next != -1){
      P[next].next[0] = root;
      que.push(next);
    }else {
      P[root].next[c] = root;
    }
  }
  while(!que.empty()){
    int t = que.front(); que.pop();
    for(int i = 0; i < 4; i++){
      char c = URDL[i];
      int next = P[t].next[c];
      if(next != -1){
        que.push(next);
        int r = P[t].next[0];
        while(P[r].next[c] == -1) r = P[r].next[0];
        P[next].next[0] = P[r].next[c];
        //need??
        if(P[P[r].next[c]].match) P[next].match = true;
      }
    }
  }
}

int move(int t, char c){
  while(P[t].next[c] == -1) t = P[t].next[0];
  return P[t].next[c];
}

int main(){
  int H, W;
  while(cin>>H>>W && H){
    vector<string> grid(H);
    REP(y, H) cin>>grid[y];
    int PL;
    cin>>PL;
    vector<string> ban(PL);
    REP(i, PL) cin>>ban[i];
    build_PMA(ban);
    int dist[50][50][110] = {};
    memset(dist, -1, sizeof(dist));
    queue<int> qx, qy, qt;
    REP(y, H)REP(x, W)if(grid[y][x] == 'S'){
      qx.push(x);
      qy.push(y);
      qt.push(0);
      dist[y][x][0] = 0;
    }
    int ans = -1;
    while(!qx.empty()){
      int x = qx.front(); qx.pop();
      int y = qy.front(); qy.pop();
      int t = qt.front(); qt.pop();
      int d = dist[y][x][t];
      if(grid[y][x] == 'G'){
        ans = d;
        break;
      }
      REP(r, 4){
        int nx = x + dx[r];
        int ny = y + dy[r];
        int nt = move(t, URDL[r]);
        if(valid(nx, ny, W, H) && grid[ny][nx] != '#' && dist[ny][nx][nt] == -1 && !(P[nt].match)){
          qy.push(ny); qx.push(nx); qt.push(nt);
          dist[ny][nx][nt] = d + 1;
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int INF = 1 << 20;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main()
{
    while(true){
        int n; cin >> n;
        if(n == 0) break;
        int f[21][21];
        int tmpx = 10,tmpy = 10;
        for(int i = 0; i < 21; i++){
            for(int j = 0; j < 21; j++){
                f[i][j] = 0;
            }
        }
        for(int i = 0; i < n; i++){
            int x,y; cin >> x >> y;
            f[y][x] = 1;
        }
        int m; cin >> m;
        for(int i = 0; i < m; i++){
            char dir;
            int l;
            cin >> dir >> l;
            if(dir=='N'){
                for(int j = 0; j < l; j++){
                    tmpy += 1;
                    f[tmpy][tmpx] = 0;
                }
            }else if(dir=='S'){
                for(int j = 0; j < l; j++){
                    tmpy -= 1;
                    f[tmpy][tmpx] = 0;
                }
            }else if(dir=='E'){
                for(int j = 0; j < l; j++){
                    tmpx += 1;
                    f[tmpy][tmpx] = 0;
                }
            }else{
                for(int j = 0; j < l; j++){
                    tmpx -= 1;
                    f[tmpy][tmpx] = 0;
                }
            }
        }
        bool e = false;
        for(int i = 0; i < 21; i++){
            for(int j = 0;j < 21; j++){
                if(f[i][j] == 1){
                    e = true;
                }
            }
        }
        if(e){
            cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }
}


Measured memory_bytes: 3068
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
	static String a;
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int[] list = new int[n];
		for(int i = 0; i < n; i++) {
			list[i] = stdIn.nextInt();
		}
		int max = Integer.MIN_VALUE;
		int pre = Integer.MAX_VALUE;
		for(int i = 0; i < n; i++) {
			if(pre <= list[i]) continue;
			else pre = list[i];
			for(int j = i+1; j < n; j++) {
				if(list[j] - list[i] > max) {
					max = list[j] - list[i];
				}
			}
		}
		System.out.println(max);
	}
}

Measured memory_bytes: 97836
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

int N, A, B, C, X;
int next(int x) {
  return x == -1 ? X : (A * x + B) % C;
}

int main() {
  for (; cin >> N >> A >> B >> C >> X, (N|A|B|C|X) != 0; ) {
    int Y[101];
    rep(i, N) cin >> Y[i];

    int ans = -1;
    int x = -1;
    rep(i, N) {
      for (; ans <= 10000; ) {
        x = next(x);
        ans++;
        if (x == Y[i]) break;
      }
    }
    if (ans == 10001) cout << -1 << endl;
    else cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
# coding: utf-8
# Your code here!

S = list(input())
#print(S)
S_int =list(map(int,S))
#print(S_int)
FIRST = S_int[0]*10+S_int[1]
SECOND = S_int[2]*10+S_int[3]

flag1 = 0
flag2 = 0

if FIRST>0 and  FIRST<=12:
    flag1 = 1
if SECOND>0 and SECOND<=12:
    flag2 = 1

if flag1 == 0 and flag2 == 0:
    print("NA")
    
elif flag1 == 0 and flag2 == 1:
    print("YYMM")
elif flag1 == 1 and flag2 == 0:
    print("MMYY")
elif flag1 == 1 and flag2 == 1:
    print("AMBIGUOUS")

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main() {
	ll X; cin >> X;
	ll now = 100;
	int day = 0;
	while (now < X) {
		now = now * 1.01;
		++day;
	}
	cout << day << endl;
	return 0;
}

Measured memory_bytes: 3644
using System;

namespace Atcoder_program_test_Csharp
{
    using System;
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            string[] str = line.Split(' ');
            int X = int.Parse(str[0]);
            int A = int.Parse(str[1]);
            if (X >= A) Console.Write("10");
            if (X < A) Console.Write("0");            
        }
    }
}

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

int main()
{
	int a, b, x;
	cin >> a >> b >> x;
	if (a <= x)
	{
		if (x - a < b)
		{
			cout << "YES";
		}
		else
		{
			cout << "NO";
		}
	}
	else
	{
		cout << "NO";
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define debug(x) cout << #x << " = " << x << endl;
#define debret(x) debug(x) ; return 0;
#define pb(x) push_back(x)
#define MOD 1000000007

using namespace std;

int main(){

    int W,H,N;

    cin >> W >> H >> N;

    int minX = 0;
    int minY = 0;
    
    int x,y,range;

    REP(i,N){
        cin >> x >> y >> range;
        switch(range){
        case 1 : // Less than x
            if(minX < x)
                minX = x;
            break;
        case 2 : // More than x
            if(W > x)
                W = x;
            break;
        case 3 : // Less than y
            if(minY < y)
                minY = y;
            break;
        case 4 : // More than y
            if(H > y)
                H = y;
            break;
        }
    }
    int w = (W-minX);
    int h = (H-minY);
    if(w < 0 || h < 0){
        cout << 0 << endl;
    }else{
        cout << w*h << endl;
    }
    
    return 0;
}


Measured memory_bytes: 384