akhauriyash/Code-Regression huggingface dataset:
class RemovableHeap:
    def __init__(self, is_max_heap: bool=False, data :list=None):
        self.data = [] if data is None else data
        self.erased = []
        self.sign = -1 if is_max_heap else 1
    
    def normalize(self):
        while len(self.erased) > 0 and self.data[0] == self.erased[0]:
            heappop(self.data)
            heappop(self.erased)
    
    def pop(self):
        ret = self.sign * heappop(self.data)
        self.normalize()
        return ret

    def push(self, x):
        heappush(self.data, self.sign * x)
        self.normalize()
    
    def remove(self, x):
        heappush(self.erased, self.sign * x)
        self.normalize()
    
    def __len__(self):
        return max(len(self.data) - len(self.erased), 0)
    
    def get(self):
        return self.sign * self.data[0]


def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    from heapq import heapify, heappop, heappush
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    def f(x):
        if x == 0:
            return False
        count = 0
        for a in A:
            count += ceil(a/x) -1
        return count <= K
    
    ng = 0
    ok = 10**9+1
    while ok - ng > 1:
        dbg(ng,ok)
        m = (ng+ok)//2
        if f(m):
            ok = m
        else:
            ng = m
    print(ok)

    
main()

Measured memory_bytes: 91052
import Data.List
main :: IO ()
main = do
    _ <- getLine 
    h0:hs <- fmap (map read . words) getLine
    let (_, c_end, _, _) = foldl' step s0 hs 
        step (h1, c1, h2, c2) h = (h, c, h1, c1)
            where c = min (c1 + abs (h1 - h)) (c2 + abs (h2-h))
        s0 = (h0, 0, h0, 0)
    print (c_end :: Int)
        

    



Measured memory_bytes: 44796
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int K = sc.nextInt();
		char[][] arr = new char[h][w];
		for(int i=0;i<h;i++){
			String s = sc.next();
			for(int j=0;j<s.length();j++){
				arr[i][j]=s.charAt(j);
			}
		}
		int ans=0;
		for(int i=0;i<(1<<h);i++){
			for(int j=0;j<(1<<w);j++){
				int black=0;
				for(int k=0;k<h;k++) {
					for(int l=0;l<w;l++) {
						if(((i>>k)&1)==0 && ((j>>l)&1)==0 && arr[k][l]=='#') {
							black++;
						}
					}
				}
				if(black==K){
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 35732
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
 
const int inf = 1e9, maxn = 1e6 + 48, mod = 1e9 + 7, N = 5e4 + 24;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;


double a, b, h, m;

main () {
	cin >> a >> b >> h >> m;
	double A = (h*30 + m / 2), B = m*6;
	double C = A - B;
//	cout << A << ' ' << B << endl;
	cout << fixed << setprecision(11);
	cout << sqrt(a*a + b*b - 2*a*b*cos((pi*C + 0.0) / 180)) << endl;
}	

Measured memory_bytes: 4192
import java.util.*;
public class Main{
    public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
   long n = sc.nextInt();
   long d = sc.nextInt();
   long res=0;
    while(n-->0) {
    long x = sc.nextInt();
    long y = sc.nextInt();
    //int res =0;
    double dis =  Math.sqrt(x*x+y*y);
    
   int dis1 = (int)Math.ceil(dis);
    if(d>=dis)
    res += 1;
     }
    System.out.println(res);
   
      //  System.out.println("Hello World");
}
}


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

int main(){
    int n;
    scanf(" %d",&n);
    int posi = 1;
    for(int i = 0; i < n;++i){
        int va;scanf(" %d",&va);
        if(va%3 && va%5 && (va%2 == 0)) posi = 0;
    }
    if(posi)
        puts("APPROVED");
    else
        puts("DENIED");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

const int M = 13;

string s;
ll t = 1, ans;
ll dp[2][13];
int ho = 0, ge = 1;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> s;
    dp[ho][0] = 1;
    for (int i = (int)s.size()-1; i >= 0; i--) {
        rep(j,M) dp[ge][j] = 0;
        if (s[i] != '?') {
            int x = t*(s[i]-'0')%M;
            rep(j,M) {
                if (x == M) x -= M;
                dp[ge][x++] = dp[ho][j];
            }
        } else {
            int x = 0;
            rep(j,10) {
                int y = x;
                rep(k,M) {
                    if (y == M) y -= M;
                    dp[ge][y++] += dp[ho][k];
                }
                x += t;
                if (x >= M) x -= M;
            }
        }
        if (i%3 == 0) rep(j,M) dp[ge][j] %= MOD;
        t = t * 10 % M;
        swap(ho,ge);
    }
    cout << dp[ho][5]%MOD << endl;
}


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

using namespace std;

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n;
   cin >> n;
   long double sum = 0;
   for (int i = 1; i <= n; i++) {
      double x;
      cin >> x;
      sum += (1.0 / x);
   }
   cout << fixed << setprecision(6) << (1.0 / sum) << '\n';
   return 0;
}


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

int main(void) {
    int N;
    int K;
    std::cin >> N >> K;
    std::vector<int> heights;
    for (int i = 0; i < N; i++) {
        int temp = 0;
        std::cin >> temp;
        heights.push_back(temp);
    }
    int count = 0;
    for (auto height : heights) {
        if (height >= K) {
            count++;
        }
    }
    std::cout << count;
    return 0;
}

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

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

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

using namespace std;

int main()
{
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	int train = min(A, B);
	int bus = min(C, D);

	cout << train + bus << endl;

}






Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<sstream>
#include<algorithm>
#include<stack>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define rep(i,n) for(int i=0;(i)<(n);i++)
#define rep1(i,n) for(int i=1;(i)<=(n);i++)
#define mst(a,b) memset(a,b,sizeof(a))
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define dbg(a) cout<<"* "<< #a <<" : "<<a<<endl
#define fr first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ls x<<1
#define rs x<<1|1
#define lowbit(x) x&(-x)
#define ac cout<<ans<<endl
//#define DEBUG 0
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-6;
const ull hashp=1e7+19;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn=2e5+100;
double x[10],y[10];
double ans=0;
int vis[10];
void dfs(int now,int n,double sum,double nowx,double nowy){
	if(now==n){
		ans+=sum;
		return ;
	}
	rep1(i,n)if(!vis[i]){
		vis[i]=1;
		if(now==0)dfs(now+1,n,0,x[i],y[i]);
		else dfs(now+1,n,sum+sqrt((y[i]-nowy)*(y[i]-nowy)+(x[i]-nowx)*(x[i]-nowx)),x[i],y[i]);
		vis[i]=0;
	}
}
void solve()
{
	int n;cin>>n;
	rep1(i,n){
		cin>>x[i];
		cin>>y[i];
	}
	dfs(0,n,0,0,0);
	int ave=1;
	rep1(i,n)ave*=i;
	ans/=(double)ave;
	printf("%.10f\n",ans);
}
int main(){
    //IOS;
    //freopen("D://data.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)

odd = []
even = []
(0..(n-1)).each do |i|
  if i.even?
    even.push(a[i])
  else
    odd.push(a[i])
  end
end

odd = odd.group_by{ |e| e }
even = even.group_by{ |e| e }

odd1 = odd2 = oddv1 = oddv2 = even1 = even2 = evenv1 = evenv2 = 0
odd.each do | key, v |
  if oddv1 < v.size
    odd2 = odd1
    oddv2 = oddv1
    odd1 = key
    oddv1 = v.size
  elsif oddv2 < v.size
    odd2 = key
    oddv2 = v.size
  end
end

even.each do | key, v |
  if evenv1 < v.size
    even2 = even1
    evenv2 = evenv1
    even1 = key
    evenv1 = v.size
  elsif evenv2 < v.size
    even2 = key
    evenv2 = v.size
  end
end

if even1 == odd1
  max =  [evenv1 + oddv2, evenv2 + oddv1].max
else
  max =  evenv1 + oddv1
end

puts n - max




Measured memory_bytes: 19468
# -*- coding: utf-8 -*-
s = input()
first = int(s[0:2])
last = int(s[2:4])
if 0 < first <= 12:
    if 0 < last <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
else:
    if 0 < last <= 12:
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 2940
n = int(input())
a = list(map(int, input().split()))

a4, a4n, a2 = 0, 0, 0
for ai in a:
  if ai % 4 == 0:
    a4 += 1
  elif ai % 2 == 0:
    a2 += 1
  else:
    a4n += 1

if a2 != 0:
  print("Yes" if a4 + 1 >= a4n+1 else "No")

else:
  print("Yes" if a4 + 1 >= a4n else "No")




Measured memory_bytes: 14252
#include <iostream>
#include <string>
#include <algorithm>
#define MOD 1000000007
#define int long long
using namespace std;
int s;
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int ans = 0;
	int N;
	cin >> N;
	while (N--)
	{
		int a;
		cin >> a;
		ans += a * s;
		ans %= MOD;
		s = (s + a) % MOD;
	}
	cout << ans;
}

Measured memory_bytes: 3612
inp = list(map(int, input().split()))
N, T = inp[0], inp[1]

ans_cost = 100000
exists = False

for i in range(N):
    inp = list(map(int, input().split()))
    c, t = inp[0], inp[1]
    if t > T or c > ans_cost:
        continue
    ans_cost = c
    exists = True

if exists:
    print(ans_cost)
else:
    print('TLE')

Measured memory_bytes: 3064
def search_number(key,S):
    left = 0
    right = len(S)
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        if S[mid] > key:
            right = mid
        elif S[mid] < key:
            left = mid + 1
    return False

n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
for i in range(q):
    if search_number(T[i],S):
        ans += 1
print(ans)


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

int main(){
    int w, h, x, y;
    double a;
    cin >> w >> h >> x >> y;
    a = (double)w * h / 2.0;
    cout << a << " ";
    if(x * 2 == w && y * 2 == h){
        cout << 1 << endl;
    }
    else{
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
//AUTHOR:BlackBox Inc.//
#include<bits/stdc++.h>
#include<unordered_map>
#include<tr1/unordered_map>
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vlli vector<long long int>
#define vvi vector<vector<int>>
#define endl "\n"
#define vpii vector<pair<int,int>>
#define vs vector<string>
#define lin1(x) ll int x; x = scan();
#define lin2(x,y) ll int x, y; x = scan(), y = scan();
#define lin3(x,y,z) ll int x, y, z; x = scan(), y = scan(), z = scan();
#define pb(x) push_back(x)
#define makep(x,y) make_pair(x,y)
#define mx(a,b) (a)>(b)?(a):(b)
#define mn(a,b) (a)<(b)?(a):(b)
#define fori(s,e) for(i=s;i<=e;i++)
#define forj(s,e) for(j=s;j<=e;j++)
#define fork(s,e) for(k=s;k<=e;k++)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x));
#define bits1(x) __builtin_popcount(x)
#define pi 3.14159265358979323846264338327950
#define MOD7 1000000007
#define MOD9 1000000009
#define cn cin>>
#define co cout<<
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace std::tr1;

int main()
{


long long a,b,c,d,e,f,g,h;
cin>>a>>b>>c;

if (a*b<=c)
{
	/* code */
	cout<<a*b<<endl;
}
else
cout<<c<<endl;

return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll long long
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e4+10;
const int MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
vector<int>adj[MAX];

int p ,n;
int val[MAX];

int vis[(1<<16)][16][16];
int  mx;
ll arr[MAX];
int prime[10]={2, 3, 5, 7, 11, 13, 17, 19};
int coun(int x){
	return __builtin_popcount(x);
}

int main() 
{ 
	//ios_base::sync_with_stdio(false);
  //  cin.tie(NULL);	
//	#ifndef ONLINE_JUDGE
//	freopen("inp.txt" ,"r", stdin );
//	freopen("out.txt", "w", stdout);
//	#endif
	
	cin>>n;
	long long sum=0;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=n;j++)
			for(long long k=1;k<=n;k++)
				sum=sum+__gcd(i , __gcd(j , k));
	}
	cout<<sum;

}

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

#define sz(x) int(x.size())
#define Task "abc"
#define For(i, a, b) for(int i = (a), _b = (b); i <= b; ++i)
#define All(x) (x).begin(), (x).end()
#define mp make_pair

typedef long long ll;

const int maxn = 31632;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n, k;
ll f[110][1010], dp[110][2 * maxn], g[110][2 * maxn];

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//  freopen(Task".inp", "r", stdin);  freopen(Task".out", "w", stdout);
  cin >> n >> k;
  if (n <= 1000){
    for (int i = 1; i <= n; ++i) f[1][i] = 1;

    for (int i = 2; i <= k; ++i){
      for (int x = 1; x <= n; ++x) for (int y = 1; x * y <= n; ++y){
        f[i][x] = (f[i][x] + f[i-1][y]) % mod;
      }
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i){
      ans = (ans + f[k][i]) % mod;
    }
    cout << ans;
    return 0;
  }

  int bk = sqrt(n);
  vector<pair<int, int> > vec;
  for (int v = 1; v <= bk; ++v) vec.push_back(mp(v, v));

  for (int v = bk; v >= 1; --v){
    int l = (n / (v+1)) + 1, r = n / v;
    l = max(l, bk + 1);
    if (l > r) continue;
    vec.push_back(mp(l, r));
  }
  int len = vec.size();
  for (int id = 0; id < len; ++id){
    int l = vec[id].first, r = vec[id].second;
    dp[1][id + 1] = r - l + 1;
  }

  for (int v = 1; v <= len; ++v){
    g[1][v] = (g[1][v-1] + dp[1][v]) % mod;
  }

  for (int i = 2; i <= k; ++i){
    for (int v = len; v >= 1; --v){
      int l = vec[v-1].first, r = vec[v-1].second;
      dp[i][v] = (g[i - 1][len - v + 1] * (r - l + 1)) % mod;
    }
    for (int v = 1; v <= len; ++v){
      g[i][v] = (g[i][v-1] + dp[i][v]) % mod;
    }
  }
  cout << g[k][len];

}




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

int main() {
  int n, m;
  cin >> n >> m;
  int ans = 0;
  vector<int> a(n, 1);
  vector<bool> red(n, false);
  red[0] = true;
  rep(i,m){
    int x, y;
    cin >> x >> y;
    x--; y--;
    if(red[x]){
      red[y] = true;
      if(a[x] == 1) red[x] = false;
    }
    a[x]--;
    a[y]++;
  }
  rep(i,n){
    if(red[i] && a[i] > 0)ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>

char A[200010];
int AL;
int nxt[200010][26];
int pos[200010];
int posL;
char res[200010];
int resL;
int n = 26;

void solve()
{
	int i, j;
	int xt[26];
	for(i=0; i<n; i++)
		xt[i] = -1;
	AL = strlen(A);
	for(i=AL-1; i>=0; i--){
		for(j=0; j<n; j++){
			nxt[i][j] = xt[j];
			//xt[A[i]-'a'] = i;//wrong
		}
		xt[A[i]-'a'] = i;
	}
	
	int cnt[26];
	for(i=0; i<n; i++)
		cnt[i] = 0;
	posL = 0;
	for(i=AL-1; i>=0; i--){
		cnt[A[i]-'a'] ++;
		for(j=0; j<n; j++){
			if(cnt[j] == 0)
				break;
		}
		if(j == n){
			pos[posL] = i;
			posL ++;
			for(j=0; j<n; j++)
				cnt[j] = 0;
		}
	}
	
	resL = posL+1;
	for(i=0; i<n; i++)
		cnt[i] = 0;
	for(i=pos[posL-1]-1; i>=0; i--){
		cnt[A[i]-'a'] ++;
	}
	for(i=0; i<n; i++){
		if(cnt[i] == 0){
			res[0] = 'a' + i;
			break;
		}
	}
	int p1, p2;
	if(resL > 1){
		if(A[0]==res[0])
			p1 = 0;
		else
			p1=nxt[0][res[0]-'a'];
		for(i=1; i<resL-1; i++){
			for(j=0; j<n; j++){
				p2 = nxt[p1][j];
				if(p2 >= pos[posL-1-i])
					break;
			}
			res[i] = 'a' + j;
			p1 = p2;
		}
	}
	else{
		p1 = -1;
	}
	for(i=0; i<n; i++){
		cnt[i] = 0;
	}
	for(i=p1+1; i<AL; i++){
		cnt[A[i]-'a'] ++;
	}
	for(i=0; i<n; i++){
		if(cnt[i] == 0)
			break;	
	}
	res[resL-1] = 'a' + i;
	res[resL] = 0;
	printf("%s\n", res);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	scanf("%s", A);
	solve();
	return 0;
}
/*
abdeeaecbadceee
*/

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


def main():
    s = input()
    n = len(s)
    t = input()
    m = len(t)
    ans = float('inf')

    for i in range(n - m + 1):
        u = s[i:i + m]

        count = 0

        for ui, ti in zip(u, t):
            if ui != ti:
                count += 1

        ans = min(ans, count)

    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
    int n,m,k; cin >> n >> m >> k;
    bool ans = false;
    rep(i,n+1) {
        //cout << endl;
        rep(j,m+1) {
            //cout << i*m + j*n - 2*(i*j) << endl;
            //cout << "  " << i*j << endl;
            if (i*m + j*n - 2*(i*j) == k) ans = true;
        }
    }
    auto o = ans ? "Yes" : "No";
    cout << o << endl;
}
//###..
//###..
//###..

//.####
//#....
//#....

Measured memory_bytes: 3628
import java.util.*;

public class Main{
	void solve(){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		int[] h = new int[n];
		for(int i = 0; i < n; i++) h[i] = scan.nextInt();
		int[] dp = new int[n];
		for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
		dp[0] = 0;
		dp[1] = Math.abs(h[1] - h[0]);
		for(int i = 0; i < n; i++) {
			for(int j = 1; j <= k; j++) {
				if(i - j >= 0) dp[i] = Math.min(dp[i], dp[i - j] + Math.abs(h[i - j] - h[i]));
			}
		}
		System.out.println(dp[n - 1]);
		scan.close();
	}

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

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

int main() {
  string s;
  cin >> s;
  int sum = 0,n = stoi(s);
  for(int i = 0;i < s.size();i++) sum += s[i]-'0';
  if(n%sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl a,b,c,d;
    cin >> a >> b;
    fp(!(a%3)||!(b%3)||!((a+b)%3),"Possible","Impossible");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int>T;
int main(){
    int h,w;
    cin>>h>>w;
    h+=4,w+=4;
    int sx,sy,gx,gy;
    cin>>sx>>sy>>gx>>gy;
    sx++,sy++,gx++,gy++;
    vector<vector<char>>s(h,vector<char>(w,'#'));
    for(int i=2;i<h-2;i++)for(int j=2;j<w-2;j++)cin>>s[i][j];
    deque<T>q;
    q.push_front(T(sx,sy,0));
    int dx[5]={-2,-1,0,1,2},dy[5]={-2,-1,0,1,2};
    while(q.size()){
        T t=q.front();
        q.pop_front();
        int x=get<0>(t),y=get<1>(t),d=get<2>(t);
        if(s[x][y]=='#')continue;
        s[x][y]='#';
        if(x==gx && y==gy){
            cout<<d<<endl;
            return 0;
        }
        if(s[x+1][y]=='.')q.push_front(T(x+1,y,d));
        if(s[x-1][y]=='.')q.push_front(T(x-1,y,d));
        if(s[x][y+1]=='.')q.push_front(T(x,y+1,d));
        if(s[x][y-1]=='.')q.push_front(T(x,y-1,d));
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(s[x+dx[i]][y+dy[j]]=='.')q.push_back(T(x+dx[i],y+dy[j],d+1));
            }
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

Measured memory_bytes: 5124
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define IDX(vec, element_iter) distance((vec).begin(), element_iter)
#define pb push_back
#define mp make_pair
#define INF9 1000000000 //10^9
#define MOD 1000000007 //10^9+7
#define fi first
#define sc second
using ll=long long;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
using vstr=vector<string>;

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);

    ll X; cin >> X;
    // vll a(n);
    // rep(i,n) cin >> a[n];
    // string s;cin >> s;
    ll price = 100;
    ll cnt = 0;
    while(price<X){
        cnt++;
        price *= 1.01;
    }
    
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3648
N, M = map(int,input().split())
gate = [list(map(int,input().split())) for i in range(M)]

small = []
large = []

for i in range(M):
    small.append(gate[i][0])
    large.append(gate[i][1])

small.sort(reverse=True)
large.sort()

if small[0] <= large[0]:
    ans = large[0] - small[0] + 1
else:
    ans = 0
print(ans)
    

Measured memory_bytes: 29408
#include <iostream>
#include <stdio.h>

using namespace  std;

int a[200010];
int b[200010];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;++i)
        scanf("%d",&a[i]);
    if (k>=100) k=100;
    int len=n;
    while(k--){
        for (int i=0;i<len;++i){
            int tmp1 = i-a[i];
            int tmp2 = i+a[i]+1;
            if (tmp1<0) tmp1 = 0;
            if (tmp2>=len) tmp2 = len;
            b[tmp1]+=1;b[tmp2]-=1;
        }
        int tot=0;
        for (int i=0;i<len;++i){
            tot+=b[i];a[i]=tot;
            b[i]=0;
        }
    }
    for (int i=0;i<n;++i)
        printf("%d ",a[i]);
}



Measured memory_bytes: 5348
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class UnionFindTree
{
    int n;
    vector<int> parent; // 親ノード
    vector<int> num;    // グループの要素数
public:
    UnionFindTree(int n0){ // コンストラクタ
        n = n0;
        parent.resize(n);
        for(int i=0; i<n; ++i)
            parent[i] = i;
        num.assign(n, 1);
    }
    void unite(int x, int y){ // xとyのグループを併合
        if((x = find(x)) != (y = find(y))){
            parent[y] = x;
            num[x] += num[y];
            -- n;
        }
    }
    int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
};

int main()
{
    for(;;){
        int n, q;
        cin >> n >> q;
        if(n == 0)
            return 0;

        vector<int> parent(n+1, -1);
        for(int i=2; i<=n; ++i)
            cin >> parent[i];

        vector<char> ope(q);
        vector<int> v(q);
        vector<int> cnt(n+1, 0);
        for(int i=0; i<q; ++i){
            cin >> ope[i] >> v[i];
            if(ope[i] == 'M')
                ++ cnt[v[i]];
        }

        UnionFindTree uft(n+1);
        for(int i=2; i<=n; ++i){
            if(cnt[i] == 0)
                uft.unite(parent[i], i);
        }

        long long ret = 0;
        for(int i=q-1; i>=0; --i){
            if(ope[i] == 'Q'){
                ret += uft.find(v[i]);
            }else if(-- cnt[v[i]] == 0 && v[i] != 1){
                uft.unite(parent[v[i]], v[i]);
            }
        }
        cout << ret << endl;
    }
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int n,k;
	string s;
	cin>>n>>k>>s;
	int ok = 0, ng = n+1;
	while( ng - ok > 1 ){
		int mid = ( ng + ok ) / 2;
		int clu = 0;
		bool fl = false;
		for(int i=0;i<mid;i++){
			if( s[i] == '0' && ( i == 0 || s[i-1] == '1' ) ){
				clu++;
			}
		}
		if( clu <= k ) fl = true;
		for(int i=mid;i<n;i++){
			if( s[i] == '0' && ( i == 0 || s[i-1] == '1' ) ){
				clu++;
			}
			if( s[i-mid] == '0' && ( s[i-mid+1] == '1' ) ){
				clu--;
			}
			if( clu <= k ) fl = true;
		}
		if( fl ) ok = mid; else ng = mid;
	}
	cout<<ok<<endl;
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<vector<int>> Graph;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353

int main() {
	string c; cin >> c;
	set<string> s;
	s.insert("a"); s.insert("i"); s.insert("u"); s.insert("e"); s.insert("o");
	if(s.count(c)) cout << "vowel" << endl;
	else cout << "consonant" << endl;
	return 0;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int eat(int a){
    if(a%2){a--;}
    a/=2;
    return a;}
int get(int a,int b){
    b+=a/2;
    return b;}
int main(){
    int a,b,k;
    cin>>a>>b>>k;
    for(int i=0;i<k;i++){
        if(i%2==0){int x=eat(a);
                   b=get(a,b);
                   a=x;}
        else{int y=eat(b);
             a=get(b,a);
             b=y;}}
    cout<<a<<" "<<b<<" "<<endl;
    return 0;}

Measured memory_bytes: 256
#include<stdio.h>

int main(){

	int n;
	int i,j,k,l;
	int count=0;
	
	while(scanf("%d",&n)!=EOF){
	
		for(i=0;i<10;i++){
			for(j=0;j<10;j++){		
				for(k=0;k<10;k++){
					for(l=0;l<10;l++){
						if(i+j+k+l == n){
							count++;
						}
					}
				}
			}
		}
		printf("%d\n",count);
		count=0;
	}

	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> void pr_vec(vector<T> &v, char ep=' '){int n=v.size();REP(ni,n){cout<<v[ni];if(ni!=n-1)cout<<ep;}cout<<endl;};
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int L,R,d;
    cin >> L >> R >> d;
    int ans = 0;
    Rep(i, L, R+1){
        if((i%d)==0) ans++;
    }
    pr(ans);
}

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

map<pair<int,string>,int>mp;

int main()
{
    int n,m,i,a;
    cin>>n>>m;
    int  cor=0;
    int pel=0;
    for(i=1; i<=m; i++)
    {
        cin>>a;
        string s;
        cin>>s;
        mp[{a,s}]++;
        if(s=="AC")
        {
            if(mp[{a,s}]==1)
                {
                    cor++;
                    pel=pel+mp[{a,"WA"}]++;
                }
        }
    }
    cout<<cor<<" "<<pel<<endl;
}


Measured memory_bytes: 22144
import sys

N,H=map(int,input().split())
A=[0]*N
B=[0]*N

for i in range(N):
    a,b=map(int,input().split())
    A[i],B[i]=a,b

max_A=max(A)
B.sort(reverse=True)

K=0
for b in B:
    if H>0 and b>=max_A:
        K+=1
        H-=b

if H>0:
    K+=(H+max_A-1)//max_A

print(K)

Measured memory_bytes: 77792
#include<iostream>
#include<iomanip>
#include<memory>
#include<array>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<algorithm>
#include<cmath>

using namespace std;

int main()
{
  array<double,3> x;
  array<double,3> y;
  array<double,3> gs;
  double xp, yp;

  while ( cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> xp >> yp )
    {
      for ( int i = 0; i < x.size(); i++ )
        {
          x[i] -= xp;
          y[i] -= yp;
        }

      for ( int i = 0; i < gs.size(); i++ )
        {
          gs[i] = x[i] * y[(i+1)%3] - y[i] * x[(i+1)%3];
        }
      
      if (( gs[0] > 0 && gs[1] > 0 && gs[2] > 0 ) || ( gs[0] < 0 && gs[1] < 0 && gs[2] < 0 ))
        cout << "YES" << endl;
      else
        cout << "NO" << endl;
    }
  
  return 0;
}

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

using namespace std;

int main() {
    int N = 0, oturi = 0;
    cin >> N;
    if (N % 1000 != 0) {
        oturi = 1000 - (N % 1000);
    } else {
        oturi = 0;
    }

    cout << oturi << endl;
}

Measured memory_bytes: 3640
#include <stdio.h>
#define N 102
#define W 1000000003
#define V 1005

typedef long long int lli;
lli dp[N][V*N+1];
lli v[N];
lli w[N];
lli min(lli a, lli b){
  if(b>a)return a;
  else return b;
}
lli max(lli a, lli b){
  if(a>b)return a;
  else return b;
}

int main(){
  lli i, j ,k, n, we;
  scanf("%lld %lld", &n,&we);
  for(i=0;i<n;i++)scanf("%lld %lld", &w[i], &v[i]);
  //dp[i][j]:品物iまで見た時の価値jの時の重さ

  for(j=0;j<N*V+3;j++)dp[0][j]=W;
  dp[0][0]=0;
  for(i=0;i<n;i++){
    for(j=0;j<=V*N;j++){
      if(v[i]>j)dp[i+1][j]=dp[i][j];
      else dp[i+1][j]=min(dp[i][j], dp[i][j-v[i]]+w[i]);
    }
  }

  lli res=0;
  for(i=0;i<=N*V;i++)if(dp[n][i]<=we)res = i;

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


  return 0;
}


Measured memory_bytes: 81024
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e18
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

map<string, int> mp;
signed main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        mp[s[i]]++;
    }
    vector<string> v;
    vector<pair<string, int>> p;
    int maxn = 0;
    for (auto itr = mp.begin(); itr != mp.end(); ++itr)
    {
        if(itr->second >maxn){
            maxn = itr->second;
        }
    }
    for (auto itr = mp.begin(); itr != mp.end(); ++itr){
        if(itr->second ==maxn){
            v.push_back(itr->first);
        }
    }
    sort(ALL(v));
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 28404
#include <iostream>
using namespace std;
int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int a = x2 - x1, b = y2 - y1;
	cout << x2 - b << " " << y2 + a << " " << x1 - b << " " << y1 + a << endl;
	return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => { trace!(($($args),*)) }
}

#[allow(unused_macros)]
macro_rules! put {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stdout(), "{}", $var);
    };
    ($var:expr, $($args:expr),*) => {
        let _ = write!(&mut std::io::stdout(), "{} ", $var);
        put!($($args),*);
    };
}

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr, $y:expr) => (max($x, $y));
    ($x:expr, $( $xs:expr ),*) => (max($x, max!($( $xs ),*)))
}

fn main() {
    let mut sc = Scanner::new();
    let n = sc.cin();
    let mut x: i64 = 0;
    let mut y = 0;
    let mut z = 0;
    for _ in 0..n {
        let a: i64 = sc.cin();
        let b: i64 = sc.cin();
        let c: i64 = sc.cin();
        let _x = max(y, z) + a;
        let _y = max(x, z) + b;
        let _z = max(x, y) + c;
        x = _x;
        y = _y;
        z = _z;
    }
    put!(max!(x, y, z));
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
}


Measured memory_bytes: 4352
from operator import itemgetter

def main():
    num_prefecture, num_city = map(int, input().rstrip().split())
    
    prefecture_list = [[] for i in range(num_prefecture)]
    
    '''prefecture_list[prefecture_number-1] = [[city index, born year], ...]'''
    for idx_city in range(num_city):
        p_belong, y_born = map(int, input().rstrip().split())
        prefecture_list[p_belong - 1].append([idx_city, y_born]) # convert p_belong so that index starts from 0
    
    # sort in the order of city birth year in an each prefecture
    prefecture_list = [sorted(each_prefecture_list, key = itemgetter(1)) for each_prefecture_list in prefecture_list]
    
    id_list = []
    for idx_p, each_prefecture_list in enumerate(prefecture_list):
        for city_order, [idx_city, y_born] in enumerate(each_prefecture_list):
            id_num = str(idx_p + 1).zfill(6) + str(city_order + 1).zfill(6)
            id_list.append([idx_city, id_num])
    
    # sort in the order of city number
    id_list.sort(key = itemgetter(0))
    
    for id_num in id_list:
        print(id_num[1])
    
if __name__ == '__main__':
    main()

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

int main() {
  int fx=0,x,xa,s=100000000;
  cin >> x;
  xa=x;
  for(int i=0;i<9;i++){
    fx+=x/s;
      x=x%s;
      s=s/10;
}
  if (xa%fx==0)
    cout<< "Yes"<< endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#define FNAME ""
 
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <string>
 
#define hash padjf9srpi
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define forn(i, n) for (int i = 0; i < (n); i++)
#define fornr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define forab(i, a, b) for (int i = (a); i < (b); i++)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
 
#ifdef _WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif
 
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;                                                                                                                                                                                      
typedef vector <int> vi;
 
template <class T> T sqr(const T &a) {return a * a;}

const int M = 420;
const int Q = 1e9 + 8;
int dp[42][M][M];

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

    for (int i = 0; i < 42; i++) {
    	for (int j = 0; j < M; j++) {
    		for (int k = 0; k < M;k++) {
    			dp[i][j][k] = Q;
    		}
    	}
    }
    dp[0][0][0] = 0;
    int n, ma, mb;
    cin >> n >> ma >> mb;
    for (int i = 0; i < n; i++) {
    	int ai, bi, ci;
    	cin >> ai >> bi >> ci;
    	for (int j = 0; j < M; j++) {
    		for (int k = 0; k < M; k++) {
    			dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
    			dp[i + 1][j + ai][k + bi] = min(dp[i + 1][j + ai][k + bi], dp[i][j][k] + ci);
    		}
    	}
    }

    int ans = Q;
    for (int i = 0; i < M; i++) {
    	for (int j= 0;j  < M; j++) {
    		if (i * mb == j * ma && i * ma) {
    			ans = min(ans, dp[n][i][j]);
    		}
    	}
    }
    if (ans == Q) 
    	cout << -1;
    else
    	cout << ans;

    
    
    
    return 0;
}

Measured memory_bytes: 29184
n,m,c=map(int,input().split())
bline=list(map(int,input().split()))
num=0
for i in range(n):
  nm=list(map(int,input().split()))
  inpro=c
  for j in range(m):
    inpro += nm[j] * bline[j]
  if inpro >0:
    num += 1
  else:
    pass
print(num)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }

int main() {
    init();
	int l, r, d;
	cin >> l >> r >> d;
	int ans = 0;
	for (int i = l; i <= r; i++) {
		if (i % d == 0) ans++;
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1012345678;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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

int a[6];
int main(){
  int k;
  rep(i,5){
    cin >> a[i];
  }
  bool flag = true;
  cin >> k;
  
    if(a[4] - a[0] > k) flag = false;
  
  if(!flag) cout << ":(" << endl;
  else cout << "Yay!" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T, class T2> void smin(T& a, T2 val) {if (a > val) a = val;}template<class T, class T2> void smax(T& a, T2 val) {if (a < val) a = val;}
const int N = 50;

void yes(){
   cout<<"Yes"<<endl;
   //exit (0);
}
void no(){
   cout<<"No"<<endl;
   //exit (0);   
}

int n, m, k;
char a[N][N];

int32_t main(){_
   
   cin >> n >> m >> k;

   for (int i = 0; i < n; ++i)
   {
      for (int j = 0; j < m; ++j)
      {
         cin >> a[i][j];
      }
   }
      
   int ans = 0;
   for (int i = 0; i < (1LL << n); ++i)
   {
      for (int j = 0; j < (1LL << m); ++j)
      {
         vector<bool> rows(n, false);
         vector<bool> cols(m, false);
         for (int t = 0; t < n; ++t)
         {
            if (i & (1LL << t)){
               rows[t] = true;
            }
         }

         for (int t = 0; t < m; ++t)
         {
            if (j & (1LL << t)){
               cols[t] = true;
            }
         }

         int bad = 0;
         for (int i = 0; i < n; ++i)
         {
            for (int j = 0; j < m; ++j)
            {
               if (rows[i] or cols[j]){
                    continue;
                 }
                 bad += (a[i][j] == '#');
            }
         }

         if (bad == k){
            ans++;
         }

      }
   }

   cout<<ans;

   return 0;
}

Measured memory_bytes: 3584
#include<stdio.h>

int H[251];

int parent(int i){
  return (int)i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
  return 2*i+1;
}

int main(){
  int i,n,k;
  scanf("%d",&n);
  for(i=1;i<n+1;i++){
    scanf("%d",&H[i]);
  }

  for(i=1;i<n+1;i++){
    printf("node %d: ",i);
    printf("key = %d, ",H[i]);

    k=parent(i-i%2);
    if(k>0)
      printf("parent key = %d, ",H[k]);

    k=left(i);
    if(k<=n)
      printf("left key = %d, ",H[k]);

    k=right(i);
    if(k<=n)
      printf("right key = %d, ",H[k]);
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 600
using System;
class Program
{
    static void Main(string[] args)
    {
        // 整数の入力
        int a = int.Parse(Console.ReadLine());
        int k=1;
        for (int i=1;i<8;i++){
            if (System.Math.Pow(2, i)  <= a){
                k=(int)System.Math.Pow(2, i);
            }
        }
        Console.WriteLine(k);
    }
}

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



int main() {
    ll h, ans = 0;
    cin >> h;
    for(ll i; h; i++) {
        h /= 2;
        ans += pow(2, i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4068
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
if N == 1:
    print(1)
    exit()
xy.sort(key = lambda x:x[0])
d = {}
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        tmp = (xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
        if not tmp in d:
            d[tmp] = 0
        d[tmp] += 1
        #print(xy[i][0] - xy[j][0], xy[i][1] - xy[j][1])
    #print()
d = sorted(d.items(), key = lambda x:-x[1])
print(N - d[0][1])

Measured memory_bytes: 39536