akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n ;
    bool haziku = false;
    vector<int> paper(n);
    for(int i=0; i<n; i++)
    cin >> paper.at(i);
    
    for(int i=0; i<n; i++){
        if(paper.at(i)%2 ==0){
            if(paper.at(i) %3 != 0 && paper.at(i) %5 != 0){
                haziku = true;}
            }
        if (haziku) break;
    }
    if(haziku){
        cout << "DENIED" << endl;
    }
    else{
        cout << "APPROVED" << endl;
    }
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool isUpper(char c)
{
   return (c>=65 && c<97);
}
int main()
{
  string s;
  getline(cin,s);
  int len = s.length();
  if(isUpper(s[0]))
   cout<<s[0];
  for(int i =1 ;i<len;++i)
  {
 
    if(isUpper(s[i])&& s[i-1]==' ')
              cout<<s[i];
 
  }
 
}

Measured memory_bytes: 256
n = gets.to_i
hs = gets.to_s.split(' ').map(&:to_i)
dp = Array.new(n, 0)
dp[1] = (hs[1] - hs[0]).abs

(2...n).each do |i|
  dp[i] = [
    dp[i - 1] + (hs[i] - hs[i - 1]).abs,
    dp[i - 2] + (hs[i] - hs[i - 2]).abs
  ].min
end

p dp[n - 1]


Measured memory_bytes: 11396
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) begin(x), end(x)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair <int,int> P;

ll sums[100005],when[100005];

int main(){
  ll n,x,m;
  cin>>n>>x>>m;
  ll now,cnt=0,sum=0;
  while(cnt<n){
    if(cnt==0) now=x;
    else{
      now=now*now;
      now%=m;
    }
    sum+=now;
    cnt++;
    if(when[now]!=0){
      ll shuuki=cnt-when[now];
      ll r=(n-cnt)/shuuki;
      bool f=((n-cnt)%shuuki!=0);
      sum+=r*(sum-sums[when[now]]);
      cnt+=shuuki*r;
      break;
    }
    when[now]=cnt;
    sums[cnt]=sum;
  }
  while(cnt<n){
    now=now*now;
    now%=m;
    sum+=now;
    cnt++;
  }
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 4632
N,Q = list(map(int,input().split()))
S = input()
L = []
R = []
for i in range(Q):
  l,r=list(map(int,input().split()))
  L.append(l)
  R.append(r)

dp = [0]*N
for j in range(N-1):
  if S[j]=='A' and S[j+1]=='C':
    dp[j+1] = dp[j]+1
  else:
    dp[j+1] = dp[j]

for k in range(Q):
  print(dp[R[k]-1]-dp[L[k]-1])

Measured memory_bytes: 88532
import heapq

N = int(input())
a = list(map(int,input().split()))
heapq.heapify(a)
while(True):
    if len(a)==1:
        print(a[0])
        break
    s1 = heapq.heappop(a)
    s2 = heapq.heappop(a)
    heapq.heappush(a,(s1+s2)/2)


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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string ans = "Christmas";
    int D;
    cin >> D;
    for (int i = 0; i < 25-D; ++i) ans += " Eve";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
X,N = map(int,input().split())
def seek(X):
    r=map(int,input().split())
    s= set()
    
    for it in r:
        s.add(it)
    for d in range(0,N+1):
        if not X-d in s:
            print(X-d)
            break
        if not X+d in s:
            print(X+d)
            break
if(N>0):
    seek(X)
else:
    print(X)


Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,k;
vector<int> ans[maxn];
int main() {
	scanf("%d",&n);
	k = -1;
	for(int i=1;i<=n*2;i++) if((long long)i*(i-1)==n*2) k = i;
	if(k==-1) return !printf("No");
	printf("Yes\n");
	int x = 1, y = 2;
	for(int i=1;i<=n;i++) {
		ans[x].push_back(i);
		ans[y].push_back(i);
		y++;
		if(y==k+1) {
			x = x+1;
			y = x+1;
		}
	}
	printf("%d\n",k);
	for(int i=1;i<=k;i++) {
		printf("%d ",ans[i].size());
		for(auto t : ans[i]) printf("%d ",t);
		printf("\n");
	}
}


Measured memory_bytes: 4608
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<chrono>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,x,n) for(int i=x; i<(n); i++)
#define vint(a,n) vint a(n); rep(i, n) cin >> a[i];
#define vll(a,n) vll a(n); rep(i, n) cin >> a[i];
#define ALL(n) begin(n),end(n)
#define RALL(n) rbegin(n),rend(n)
#define MOD (1000000007)
// #define MOD (998244353)
#define INF (2e9)
#define INFL (2e18)

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using vint=vector<int>;
using vll=vector<ll>;
using vbool=vector<bool>;
template<class T>using arr=vector<vector<T>>;
template<class T>int popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;}
template<class T>void pr(T x){cout << x << endl;}
template<class T>void prvec(vector<T>& a){rep(i, a.size()-1){cout << a[i] << " ";} pr(a[a.size()-1]);}
template<class T>void prarr(arr<T>& a){rep(i, a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main()
{
    int n; cin >> n;
    vint a(n+1);
    a[0] = 0;
    rep(i, n) cin >> a[i+1];
    a.push_back(0);
    vint dist(n+1);
    rep(i, n+1){
        dist[i] = abs(a[i+1] - a[i]);
    }
    ll sum = 0;
    rep(i, n+1) sum += dist[i];
    // prvec(dist);

    FOR(i, 1, n+1){
        if(a[i-1] <= a[i] && a[i] <= a[i+1]) pr(sum);
        else if(a[i-1] >= a[i] && a[i] >= a[i+1]) pr(sum);
        else {
            // pr("");
            // pr(dist[i]);
            // pr(dist[i+1]);
            // pr(sum);
            pr(sum - dist[i-1] - dist[i] + abs(a[i-1] - a[i+1]));
            // pr(abs(a[i-1] - a[i+1]));
        }
    }
    return 0;}

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

int n, a[1001001], sosu[1001001], chk[1001001];

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

	for(int i=2;i*i<=1000000;i++){
		if(sosu[i]) continue;
		for(int j=i;j<=1000000;j+=i) sosu[j] = i;
	}
	
	for(int i=2;i<=1000000;i++) if(!sosu[i]) sosu[i] = i;

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

	int fl = 0;
	for(int i=1;i<=n && !fl;i++){
		int k = a[i];
		while(k > 1){
			if(chk[sosu[k]] && chk[sosu[k]] != i){
				fl = 1;
				break;
			}
			chk[sosu[k]] = i;
			k /= sosu[k];
		}
	}

	if(!fl){
		cout << "pairwise coprime";
		return 0;
	}

	for(int i=2;i<=n;i++) a[1] = __gcd(a[1], a[i]);

	cout << (a[1] == 1 ? "setwise coprime" : "not coprime");
}

Measured memory_bytes: 11760
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	list1 := getStdinIntArr()
	p := getStdinIntArr()
	X := list1[0]
	N := list1[1]

	sort.Ints(p)

	find := true
	index := 0
	for idx, val := range p {
		if val == X {
			find = false
			index = idx
			break
		}
	}
	if find {
		fmt.Printf("%d\n", X)
		return
	}

	prev := 0
	min1 := -math.MaxInt16
	min2 := math.MaxInt16

	prev = p[index]
	find = false
	for i := index - 1; i >= 0; i-- {
		if prev-1 != p[i] {
			min1 = prev - 1
			find = true
			break
		}
		prev = p[i]
	}
	if !find {
		min1 = p[0] - 1
	}

	prev = p[index]
	find = false
	for i := index + 1; i < N; i++ {
		if prev+1 != p[i] {
			min2 = prev + 1
			find = true
			break
		}
		prev = p[i]
	}
	if !find {
		min2 = p[N-1] + 1
	}

	if min1 == -math.MinInt16 {
		fmt.Printf("%d\n", min2)
		return
	}
	if min2 == math.MinInt16 {
		fmt.Printf("%d\n", min1)
		return
	}

	min1abs := X - min1
	min2abs := min2 - X
	if min1 < 0 {
		min1abs = -min1
	}
	if min2 < 0 {
		min2abs = -min2
	}

	if min1abs == min2abs {
		fmt.Printf("%d\n", min1)
	} else if min1abs < min2abs {
		fmt.Printf("%d\n", min1)
	} else {
		fmt.Printf("%d\n", min2)
	}
}

var sc = bufio.NewReaderSize(os.Stdin, 1024*1024*10)

func getStdin() string {
	return readLine()
}
func getStdinIntArr() []int {
	str := getStdin()
	list := strings.Split(str, " ")
	rtn := make([]int, len(list))
	for idx, val := range list {
		rtn[idx], _ = strconv.Atoi(val)
	}
	return rtn
}
func readLine() string {
	buf := make([]byte, 0, 0)
	for {
		l, p, _ := sc.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}


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

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

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


def main():
   L = INT()
   print((L/3) ** 3)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3956
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<iostream>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
int main() {
	deque<int> num;
	int n, t;
	cin >> n;
	rep(i, 0, n) {
		cin >> t;
		if (i % 2 == 0)num.push_back(t);
		else num.push_front(t);
	}
	if (n % 2)reverse(all(num));
	rep(i, 0, n) {
		printf(i == n - 1 ? "%d\n" : "%d ", num[i]);
	}
	return 0;
}


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

const int N=110000;
const int INF=1e9;

int n,k;
int known[N];
int used[N];
int l[N],r[N];
vector<int> g[N];
int par[N];
vector<int> order;
int val[N];
int know_parity[N][2];
int a,b;
bool shit=0;
int ans[N];

inline void dfs(int v)
{
	used[v]=1;
	l[v]=-INF;
	r[v]=INF;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		if(used[to]) continue;
		dfs(to);
		par[to]=v;
		if(know_parity[to][0])
			know_parity[v][1]=1;
		if(know_parity[to][1])
			know_parity[v][0]=1;
		l[v]=max(l[v],l[to]-1);
		r[v]=min(r[v],r[to]+1);
	}
	if(known[v])
	{
		l[v]=max(l[v],val[v]);
		r[v]=min(r[v],val[v]);
		know_parity[v][val[v]%2]=1;
	}
	if(know_parity[v][0]&&know_parity[v][1])
	{
		shit=1;
	}
	if(l[v]>r[v])
	{
		shit=1;
	}
	order.push_back(v);
}

inline int get_val(int v,int par)
{
	if(par==0)
	{
		return l[v];
	}
	l[v]=max(l[v],ans[par]-1);
	r[v]=min(r[v],ans[par]+1);
	while(l[v]%2==ans[par]%2)
		l[v]++;
	return l[v];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d %d",&a,&b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	{
		scanf("%d %d",&a,&b);
		val[a]=b;known[a]=1;
	}
	shit=false;
	dfs(1);
	if(shit)
	{
		puts("No");
	}
	else
	{
		reverse(order.begin(),order.end());
		for(int i=0;i<n;i++)
		{
			int v=order[i];
			ans[v]=get_val(v,par[v]);
		}
		puts("Yes");
		for(int i=1;i<=n;i++)
		{
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

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

namespace ABC116
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            List<int> h = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();


            int indexL = 0, counter = 0;
            while (h.Sum() > 0)
            {
                while (h[indexL] == 0) indexL++;

                int indexR = h.FindIndex(indexL, x => x == 0);
                if (indexR < 0) indexR = h.Count;

                for (int i = indexL; i < indexR; i++)
                {
                    h[i]--;
                }
                counter++;
            }
            Console.WriteLine(counter);
        }
    }
}


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

int main(){

  int n;  std::cin >> n;
  std::vector<int> numbers(n, 1);
  for(int i=0; i < numbers.size(); i++) numbers.at(i) += i;
  
  int answer = 1;
  int power = 0;
  for(int i=0; i < numbers.size(); i++){
    int dividend = numbers.at(i);
    int count = 0;
    
    while(dividend % 2 == 0){
      count++;
      dividend /= 2;
    }
    
    if(power < count){
      power = count;
      answer = numbers.at(i);
    }
    
  }
  
  std::cout << answer << std::endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
if n%2==1:
    x=""
    for i in range(m):
        x+=f"{i+1} {n-i}\n"
    print(x)
else:
    x=""
    for i in range(m):
        x+=(f"{i+1} {n-i}\n" if i<m/2 else f"{i+1} {n-i-1}\n")
    print(x)

Measured memory_bytes: 11160
#include <stdio.h>

int main(){
  int A, B, C, D;
  scanf("%d%d%d%d", &A, &B, &C, &D);

  
  if(A > B){
    if(C > D){
     printf("%d\n", B+D);
    }
    else{
     printf("%d\n", B+C);
    }
  }
  else{
    if(C > D){
     printf("%d\n", A+D);
    }
    else{
     printf("%d\n", A+C);
    }
  }

 return 0;
  }


Measured memory_bytes: 2124
#include<bits/stdc++.h>
#define case_no(n) cout<<"Case "<<n<<": ";

using namespace std;

long long monster[100005];
long long soldier[100005];

int main()
{
    long long n,i,count=0;
    cin>>n;
    for(i=0; i<n+1; i++)
    {
        cin>>monster[i];
    }
    for(i=0; i<n; i++)
    {
        cin>>soldier[i];
        if(soldier[i]>=monster[i])
        {
            count=count+monster[i];
            soldier[i]=soldier[i]-monster[i];
         //   cout<<count<<endl;
        }
        else
        {
            count=count+soldier[i];
            soldier[i]=0;
         //    cout<<count<<endl;
        }
        if(soldier[i]!=0)
        {
            if(monster[i+1]>=soldier[i])
            {
                count=count+soldier[i];
                monster[i+1]=monster[i+1]-soldier[i];
            //     cout<<count<<endl;
            }
            else{
                count=count+monster[i+1];
                monster[i+1]=0;
             //    cout<<count<<endl;
            }
        }
    }
    cout<<count;
}


Measured memory_bytes: 1792
N, M = gets.split.map(&:to_i)

dp = [-1] * (N + 1)

M.times do
  dp[gets.to_i] = 0
end

dp[0] = 0

if dp[1] == -1
  dp[1] = 1
end

if dp[2] == -1
  dp[2] = dp[1] + 1
end

3.upto(N) do |i|
  next if dp[i] == 0

  x = dp[i - 2]
  y = dp[i - 1]

  dp[i] = x + y
end

puts dp[N] % 1_000_000_007

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

const int MOD = 1000000007;
const int INF = 1000000000;

//long long
#define ll  long long

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b;
}

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; }


int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  ll ans = 0;
  ll cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for(int i=0;i<n;i++){
        if(s[i]=='R') cnt1++;
        if(s[i]=='G') cnt2++;
        if(s[i]=='B') cnt3++;
    }

ans = cnt1 * cnt2 * cnt3;

for(int i = 1; i <= n; i++){
  for(int j = 0; j< n; j++){
    if(j - i < 0 || j + i >= n) continue;
    if(s[j] != s[j - i] && s[j] != s[j + i] && s[j + i] != s[j - i])
    {
        //cout<<"s[j] : "<<j<<"s[j-i] : "<<j-i<<"s[j+i] : "<<j+i<<endl;
        ans--;
    }
  }
}
  cout << ans << "\n";
  return 0;
}


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

int main(){
    string a;
    string b;
    bool check=true;

    cin>>a;
    cin>>b;
    
    for (int i=0;i<a.size();i++){
        if(a[i]!=b[i]){
            check=false;
        }
    }

    if(a.size()!=b.size()-1){
        check=false;
    }

    if(check){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3560
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2000005;
const int mod = 1000000007;
int a[maxn];
int main()
{
    int n;
    cin >> n;
    long long ans = 0 , sum  = 0 ;
    for(int i=0;i<n;i++){
        cin >> a[i];
        ans = (ans+sum*a[i])%mod;
        sum = (sum+a[i])%mod;
    }
    cout << ans <<endl;
    return 0;
}


Measured memory_bytes: 4400
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ff first
#define ss second
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vs vector<string>
#define vss vector<vs>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define repr(i, a, n) for (int i = (n); i >= (a); --i)
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);
const int pi = 3.1415926536;
const int MOD = 1000000007;

void Main() {
  int N;
  cin >> N;
  int max = -INF, min = INF;
  rep(i, 0, N) {
    int a;
    cin >> a;
    if (a > max) max = a;
    if (a < min) min = a;
  }
  cout << max - min << endl;
}

int main() {
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  Main();
}

Measured memory_bytes: 256
import numpy as np
def main():
  n, k, q = map(int,input().split())
  a=[int(input()) for i in range(q)]
  a = np.asarray(a)
  list = np.ones(n)*k
  list = list - q
  for i in range(q):
    list[a[i]-1] = list[a[i]-1] + 1
  for i in range(n):
    if 0<list[i]:
      print('Yes')
    else:
      print('No')

if __name__ == '__main__':
  main()

Measured memory_bytes: 17096
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    return res[:-1] if res[-1] == "\n" else res
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
MOD = 1000000007

def main():
    H, N = LI()
    AB = LIR(N)

    dp = [float("inf")] * (H+1)
    dp[0] = 0

    for a, b in AB:
        for i in range(H+1):
            ni = min(H, a + i)
            nv = dp[i] + b
            if nv < dp[ni]:
                dp[ni] = nv

    print(dp[H])


main()


Measured memory_bytes: 74412
#include <bits/stdc++.h>
#define rep(i,n); for(ll i = 0; i < ll(n); i++)
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
int gcd(int a, int b){ //a>=0,b>=0,￢(a=b=0)
  while(min(a,b)>0){if(a<b)swap(a,b);a=a%b;}return max(a,b);
}



int main(){
  ll n,a,b;
  cin>>n>>a>>b;
  ll ans;
  if((b-a)%2==0) ans = (b-a)/2;
  else ans = min(min(a+b-1, 2*n-a-b+1)/2,min(b-1, n-a));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
alp = "qwertyuiopasdfghjklzxcvbnm"
c = [0]*26
for i in range(h):
    s = input()
    for i in range(26):
        c[i] += s.count(alp[i])
for i in range(26):
    c[i] %= 4
c2 = c.count(2)
c2 += c.count(3)
for i in range(26):
    c[i] %= 2
c1 = c.count(1)
a2 = 0
a1 = 0
if h%2 == 1:
    a2 += w//2
if w%2 == 1:
    a2 += h//2
if h%2 == 1 and w%2 == 1:
    a1 = 1
if c2 <= a2 and c1 <= a1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

int  main()
{
	int n, x, y, t;
	int flag = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &t, &x, &y);
		if(t < (x + y))
		{
			flag = 0;
			break;
		}
		if(t%2 == 1 && ((x%2 == 0 && y%2 == 1) || (x%2 == 1 && y%2 == 0)))
		{
			flag = 1;
		}
		else if(t%2 == 0 && ((x%2 == 1 && y%2 == 1) || (x%2 == 0 && y%2 == 0)))
		{
			flag = 1;
		}
		else
		{
			flag = 0;
			break;
		}
	}
	if(flag == 1) printf("Yes\n");
	if(flag == 0) printf("No\n");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vdo=vector<double>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vvdo=vector<vector<double>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using pqin=priority_queue<int>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
int main()
{
    string s;
    cin>>s;
    int a,b,c,d;
    a=s[0]-'0';
    b=s[1]-'0';
    c=s[2]-'0';
    d=s[3]-'0';
    vin x(3);
    bool can=false;
    rep(i,1<<3){
        bitset<3> e(i);
        int sum=0;
        if(e.test(0))sum+=b;
        else sum-=b;
        if(e.test(1))sum+=c;
        else sum-=c;
        if(e.test(2))sum+=d;
        else sum-=d;
        if(sum==7-a){
            can=true;
            x[0]=e[0];
            x[1]=e[1];
            x[2]=e[2];
            break;
        }
    }
    if(can){
        cout<<a;
        if(x[0]==1)cout<<'+';
        else cout<<'-';
        cout<<b;
        if(x[1]==1)cout<<'+';
        else cout<<'-';
        cout<<c;
        if(x[2]==1)cout<<'+';
        else cout<<'-';
        cout<<d<<'='<<7<<endl;
    }
}


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

using namespace std;
using ll = long long;

constexpr static ll MOD = 1000000007ll;
constexpr static int INF = 1 << 28; // for x <= 10^9
constexpr static ll INFL = 1ll << 60; // for x <= 10^19
constexpr static double EPS = 1e-10;

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

    unordered_map<string, ll> numsMap;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        numsMap[s]++;
    }

    ll ans = 0;
    for (const auto& value : numsMap) {
        ans += (value.second * (value.second - 1)) / 2;
    }

    cout << ans << endl;
}


Measured memory_bytes: 7328
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;

int a, b, m;
int as[N], bs[N];

int main() {
    cin >> a >> b >> m;
    int min_a = 1e6;
    int min_b = 1e6;
    for (int i = 0; i < a; i++) {
        int x;
        cin >> x;
        as[i] = x;
        min_a = min(min_a, x);
    }
    for (int i = 0; i < b; i++) {
        int x;
        cin >> x;
        bs[i] = x;
        min_b = min(min_b, x);
    }
    int ans = min_a + min_b;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        ans = min(ans, max(0, as[x - 1] + bs[y - 1] - c));
    }
    cout << ans << '\n';
    return 0;
}



Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		
		char[] s=S.toCharArray();
		
		int n = s.length;
		char[] s2 = new char[n-8];
		
		for(int i=0;i<n-8;i++) {
			s2[i]=s[i];
		}
		
		S=String.valueOf(s2);
		
		System.out.println(S);

	}


}


Measured memory_bytes: 22612
#define ll long long
#define lld long double
#define cn(n)  ll n;cin >> n;
#define tes(t) ll t;cin>>t;while(t--) 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define al(v) v.begin(), v.end()
#define oset(X) tree<X, null_type, less<X>, rb_tree_tag, tree_order_statistics_node_update>
#define roset(X) tree<X, null_type, greater<X>, rb_tree_tag, tree_order_statistics_node_update>
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll INF = 1ll * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 + 7;
const ll MOD2 = 998244353;
const long double PI = 3.141592653589793;
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
ll power(ll x, ll y, ll p){ll res = 1;x %= p;while (y > 0){if (y & 1)res = (res * x) % p;y = y >> 1;x = (x * x) % p;}return res;}
ll po(ll base, ll powerRaised){if (powerRaised != 0)return (base * po(base, powerRaised - 1));else return 1;}
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll lcm(ll a, ll b){return (a * b) / gcd(a, b);}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
// #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
// #endif //*
  ll x,k,d;
  cin>>x>>d>>k;
  x=abs(x);
  ll a=x%k;
  ll b=k-x%k;
  ll steps=x/k;
  if(d<=steps)
  cout<<x-d*k;
  else
  {
    d-=steps;
    if(d%2==0)
    cout<<a;
    else cout<<b;
  }
  
  
}


Measured memory_bytes: 3680
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

int main(){
  int S, W; cin >> S >> W;
  if(W>=S) cout << "unsafe" << endl;
  else cout << "safe" << endl;
  return 0;
}


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

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


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 52 + 9;
const ll MOD = 1000000007;
int main()
{
    int n;
    scanf("%d", &n);
    char s[N];
    scanf("%s", s);
   // cout << s << endl;
    vector<ll> a;
    a.push_back(1);
    for (ll i = 1; i < strlen(s); i++) {
        if (s[i] == s[i-1]) a[a.size() - 1]++; else a.push_back(1);
    }
   // for (ll i = 0; i < a.size(); i++) cout << ' ' << a[i];
    ll dp[N] = {0};
    dp[0] = 3 * a[0];
    for (ll i = 1; i < a.size(); i++) {
        if (a[i-1] == 1) dp[i] = (dp[i-1] * 2) % MOD;
        if (a[i-1] == 2) {
            if (a[i] == 1) dp[i] = dp[i-1];
            else dp[i] = dp[i-1] * 3 % MOD;
        }
    }
    cout << dp[a.size() - 1] << endl;
}

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

int main(int argc,char **argv) {
	int a,b;
	cin>>a>>b;
	int now=1;
	int ans=0;
	while(now<b) {
		ans++;
		now+=a-1;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
module Main where

-- import Utils
import Control.Applicative

getInt :: IO Int
getInt = head <$> getInts

getInts :: IO [Int]
getInts = map read . words <$> getLine 

main :: IO ()
main = do
  { [a, b] <- getInts
  ; putStrLn (unwords (map show [a * b, 2 * (a + b)]))
  }



Measured memory_bytes: 3620
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


int main(){
  int sx, sy, tx, ty;
  cin>>sx>>sy>>tx>>ty;

  REP(i, ty-sy) cout<<'U';
  REP(i, tx-sx) cout<<'R';
  REP(i, ty-sy) cout<<'D';
  REP(i, tx-sx+1) cout<<'L';
  REP(i, ty-sy+1) cout<<'U';
  REP(i, tx-sx+1) cout<<'R';
  cout<<'D'<<'R';
  REP(i, ty-sy+1)cout<<'D';
  REP(i, tx-sx+1)cout<<'L';
  cout<<'U'<<endl;



  return 0;
}


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

int main(){
	

	int n;
	string s;
	cin >> n >> s;
	if(s.size() <= n){
		cout << s;
	}
	else{
		for(int i = 0; i < n; ++i){
			cout << s[i];
		}
		cout << "...";
	}
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include<string>
#include<cmath>
#include<ciso646>
#include<cstring>
#include<iomanip>

using ll = long long;

using namespace std;
int main()
{/*三日目*/
	ll n, a, b; cin >> n >> a >> b;
	ll syou, amari, sum; sum = 0;
	syou = n / (a + b);
	amari = n % (a + b);
	sum += syou * a;
	if (amari >= a)
		sum += a;
	else
		sum += amari;
	cout << sum;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const int MAX_N = 5005;
const ll MOD = 1000000007LL;

vector<int> Centroid(const vector<vector<int>> &edge) {
    int n = edge.size();
    vector<int> centroids;
    vector<int> sz(n);
    function<void(int, int)> dfs = [&](int cur, int par) {
        sz[cur] = 1;
        bool is_centroid = true;
        for (int ch : edge[cur]) {
            if (ch == par) continue;
            dfs(ch, cur);
            sz[cur] += sz[ch];
            if (sz[ch] > n / 2) is_centroid = false;
        }
        if (n - sz[cur] > n / 2) is_centroid = false;
        if (is_centroid) centroids.push_back(cur);
    };
    dfs(0, -1);
    return centroids;
}

ll inv[MAX_N], fac[MAX_N], fiv[MAX_N];

void COMinit() {
    inv[1] = fac[1] = fiv[1] = inv[0] = fac[0] = fiv[0] = 1;
    for (ll i = 2; i < MAX_N; i++) {
        fac[i] = fac[i - 1] * i % MOD; // n!
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD; // n^-1
        fiv[i] = fiv[i - 1] * inv[i] % MOD; // (n!)^-1
    }
}

ll com(ll n, ll k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * fiv[k] % MOD * fiv[n-k] % MOD;
}

vector <int> sz(5005);
int dfs(vector<vector<int>> &edge, int cur, int par) {
    int sum = 1;
    for (int ch : edge[cur]) {
        if (ch == par) continue;
        sum += dfs(edge, ch, cur);
    }
    sz[cur] = sum;
    return sum;
}

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

    ll n;
    cin >> n;

    vector <vector<int>> edge(n);
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;

        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    COMinit();

    vector<int> centroids = Centroid(edge);

    if (centroids.size() == 2) {
        cout << fac[n / 2] * fac[n / 2] % MOD << "\n";
        return 0;
    }

    int center = centroids[0];
    dfs(edge, center, -1);

    vector<int> children(1, 0);
    for (int v : edge[center]) children.push_back(sz[v]);

    sort(children.begin(), children.end());
    int ch = children.size();

    ll dp[ch][n];
    fill(dp[0], dp[ch], 0LL);
    // dp[i][j] : i番目の部分木において、j個が自分の部分木に戻る場合の数

    dp[0][0] = 1;
    int sum = 0;
    for (int i = 1; i < ch; i++) {
        int cur_sz = children[i];

        for (ll j = 0; j <= cur_sz; j++) {
            for (int k = 0; k <= sum; k++) {
                dp[i][k + j] += dp[i - 1][k] * com(cur_sz, j) % MOD * com(cur_sz, j) % MOD * fac[j] % MOD;
                dp[i][k + j] %= MOD;
            }
        }

        sum += cur_sz;
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll sgn = i % 2 == 0 ? 1 : -1;
        ll tmp = fac[n - i] * dp[ch-1][i] % MOD;
        tmp = (sgn * tmp + MOD) % MOD;
        ans = (ans + tmp) % MOD;
    }

    cout << ans << '\n';
    return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<ll> A;
    vector<ll> B;

    for (int i = 0; i < N; i++)
    {
        ll a, b;
        cin >> a >> b;
        A.push_back(a);
        B.push_back(b);
    }

    // ソート
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ll ans;
    if (N % 2 == 0)
    {
        // 偶数
        ll ma = A[N / 2] + A[N / 2 - 1];
        ll mb = B[N / 2] + B[N / 2 - 1];
        ans = mb - ma + 1;
    }
    else
    {
        // 奇数
        ll ma = A[N / 2];
        ll mb = B[N / 2];
        ans = mb - ma + 1;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6592
from collections import deque


def main():
    n = int(input())
    dll = deque()

    def delete(x):
        try:
            dll.remove(x)
        except ValueError:
            pass

    methods = {"insert": dll.appendleft,
               "delete": delete,
               "deleteFirst": dll.popleft,
               "deleteLast": dll.pop}
    for _ in range(n):
        command = input().split()
        if len(command) > 1:
            methods[command[0]](int(command[1]))
        else:
            methods[command[0]]()
        # print(dll)

    print(" ".join(map(str, dll)))


if __name__ == "__main__":
    main()



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

using namespace std;

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

  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i+=2) 
    cout << s[i];
  cout << endl;

  return 0;
}



Measured memory_bytes: 592
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define GYOU_MAX 256
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define s_pri(str) printf("%s\n",str);
#define PRINT(str) printf(#str "\n")
#define v_pri(val) printf("%d\n",val);
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define pi acos(-1.0)
#define sca(x) scanf("%d",&x);

typedef long long int ll;

/*
puts("aa");
//*/


int main(void) {

	int N, M;
	sca(N); sca(M);
	int a[50], b[50], c[50], d[50];
	rep(i, N) {
		sca(a[i]);
		sca(b[i]);
	}
	rep(i, M) {
		sca(c[i]);
		sca(d[i]);
	}

	int kyori;
	int min = 400000000;
	int x;
	rep(i, N) {
		rep(j, M) {
			kyori = abs(c[j] - a[i]) + abs(d[j] - b[i]);
			if (kyori < min) {
				min = kyori;
				x = j;
			}
			if (j == M - 1) {
				min = 400000000;
			}
			//printf("%d %d\n\n", j,min);
			//printf("%d\n", kyori);
		}
		printf("%d\n", x+1);
	}
	
	
	return 0;
}




Measured memory_bytes: 128
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>

const long long INF = __LONG_LONG_MAX__;

using namespace std;

int N, D;

/*bool is_distance_integer(int **x, int i, int j) {
    int distance = 0;
    double d;

    for(int k = 0; k < D; k++) {
        distance += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
    }

    int max = distance;

    cout << distance << endl;

    for (int k = 1; k <= max; k++) {
        if (k*k == distance) {
            return true;
        }
    }
    return false;
}*/



int main() {
    cin >> N;
    cin >> D;

    int X[N][D];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < D; j++) {
            cin >> X[i][j];
        }
    }

    int count = 0;
    int distance;
    int max;

    for(int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            distance = 0;
            for(int k = 0; k < D; k++) {
                distance += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }
            max = distance;
            for (int k = 1; k <= max; k++) {
                if (k*k == distance) {
                    count++;
                }
            }
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<(n);i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main()
{   
    ll N, M; cin >> N >> M;
    vector<pair<int, int>> edge(M);
    ll a, b;
    rep(i, M)
    {
        cin >> a >> b;
        edge[i] = make_pair(a - 1, b - 1);
    }

    UnionFind uf(N);

    ll ans[M];
    ans[M - 1] = N * (N - 1) / 2;

    for (ll i = M - 2; i >= 0; i--)
    {
        if (!uf.issame(edge[i + 1].first, edge[i + 1].second))
        {
            ans[i] = ans[i + 1] - uf.size(edge[i + 1].first) * uf.size(edge[i + 1].second);
            uf.merge(edge[i + 1].first, edge[i + 1].second);
        }
        else ans[i] = ans[i + 1];
    } 
    rep(i, M)
    {
        cout << ans[i] << endl;
    }
}

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

typedef ostringstream OSS;
typedef istringstream ISS;

typedef long long LL;
typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<PII> VPII;

#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x) (x).begin(),(x).end()
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define rep(i, N) for (int i = 0; i < (N); i++)
#define rep2(i, j, N, M) rep(i, N) rep(j, M)
#define rep3(i, j, k, N, M, L) rep(i, N) rep(j, M) rep(k, L)
#define REP(i, init, N) for (int i = (init); i < (N); i++)

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a) { OSS oss; oss << a; return oss.str(); };

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

vector<bool> Prime;
vector<int> PrimeStk;
void initPrime(LL num) {
	Prime = vector<bool>(num + 1, true);
	Prime[1] = Prime[0] = false;
	LL sq_num = sqrt((double)num);
	for (LL i = 2; i <= sq_num; i++) {
		if (Prime[i]) {
			for (LL j = i + i; j <= num; j += i) {
				Prime[j] = false;
			}
		}
	}
}
void initPrimeStk(long begin) {
	PrimeStk.clear();
	for (long i = begin; i < (int)Prime.size(); i++) {
		if (Prime[i]) {
			PrimeStk.push_back(i);
		}
	}
}

int M, A, B;
double AB;

PII solve() {
    PII ans;
    int ans_pq = 0;

    VI ps(ALL(PrimeStk));
    int n = ps.size();

    rep(i, n){
        int p = ps[i];

        if (p > M) break;

        REP(j, i, n) {
            int q = ps[j];

            int m = p * q;
            if (m < 0 || m > M) break;

            double pq = 1. * p / q;
            if (!(AB < pq + 1e-6)) break;

            if (ans_pq < m) {
                ans_pq = m;
                ans = MP(p, q);
            }
        }
    }

    return ans;
}

int main(void) {
    initPrime(100000);
    initPrimeStk(0);

    while (cin >> M >> A >> B, A) {
        AB = 1. * A / B;
        PII ans = solve();
        cout << ans.fst << " " << ans.snd << endl;
    }
    

	return 0;
}

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

int main(){
  int n,l,r,ans=0;cin>>n;
  REP(i,n){
    cin>>l>>r;
    ans+=r-l+1;
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n, a;

    cin >> n >> a;

    int x[60];

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

    long long dp[60][60][2510] = {0};

    for (int j = 0; j <= n; ++j) {
        for (int k = 0; k <= n; ++k) {
            for (int s = 0; s <= n*a; ++s) {
                if (j == 0 && k == 0 && s == 0) {
                    dp[j][k][s] = 1;
                } else if (j >= 1 && s < x[j-1]) {
                    dp[j][k][s] = dp[j-1][k][s];
                } else if (j >= 1 && k >= 1 &&  s >= x[j-1]) {
                    dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]];
                } else {
                    dp[j][k][s] = 0;
                }
            }
        }
    }

    long long result = 0;

    for (int k = 1; k <= n; ++k) {
        result += dp[n][k][k*a];
    }

    cout << result << endl;
}


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

int main(){
    int N;  cin >> N;
    vector<int> A(3*N);
    for(int i=0; i<3*N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    long long ans = 0;
    for(int i=1; i<=N; i++){
        ans += A[3*N-2*i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 1408
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int H[] = new int[N];
    for (int i = 0; i < N; i++) {
      H[i] = sc.nextInt();
    }

    int first = H[0];
    int count = 1;
    for (int i = 1; i < N; i++) {
      if (first <= H[i]) {
        count++;
        first = H[i];
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mxN=1e5+1;
vector<string>op(mxN);

vector<char>ans;

signed main(){
    int x;
    cin>>x;
    int b=100;
    int ans=0;
    while(b<x){
        b+=b/100;
        ans+=1;
    }
    cout<<ans<<endl;
}

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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int N = 505;

int n;
int c[N], s[N], f[N];

int main() {

	FAST;
	
	cin >> n;
	for (int i = 1; i < n; i ++) {
		cin >> c[i] >> s[i] >> f[i];
	}
	for (int i = 1; i < n; i ++) {
		intt t = 0;
		for (int j = i; j < n; j ++) {
			if (t <= s[j]) {
				t = s[j];
			}
			else {
				if (t % f[j]) {
					t = (t / f[j] + 1) * f[j];
				}
			}
			t += c[j];
		}
		cout << t << '\n';
	}
	cout << 0 << '\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define PI 3.14159265;
const int nax=605;
int n;
vector<vector<int>> v(nax);
ld ans=2e18;
void solve(int z){
    ld dp[n];
    dp[n-1]=0;
    for(int i=n-2;i>=0;i--){
        ld s=0;
        ld m=-1;
        ld l=0;
        for(auto x: v[i]){
            s+=dp[x];
            l++;
            m=max(m,dp[x]);
        }
        if(i==z && l>1){
            s-=m;
            s/=(l-1);
        }
        else{
            s/=l;
        }
        dp[i]=s+1;
    }
    ans=min(ans,dp[0]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b; a--; b--;
        v[a].push_back(b);
    }
    for(int i=0;i<n;i++){
        solve(i);
    }
    cout<<fixed<<setprecision(10)<<ans;
}

Measured memory_bytes: 1408
N = map(int, input().split())
A = list(reversed(sorted(list(map(int, input().split())))))
if A[-1] == 0:
    ans = 0
else:
    ans = A[0]
    for a in A[1:]:
        ans *= a
        if ans > 10**18:
            ans = -1
            break
print(ans)

Measured memory_bytes: 21780
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define PI acos(-1)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}

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

   set<int> a;

   rep(i,n){
      int x;
      cin>>x;
      if(a.find(x)!=a.end()){
         a.erase(x);
      }
      else{
         a.insert(x);
      }
   }
   cout<<a.size();

   return 0;
}


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

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

    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    for (int i = 0; i < 1000; ++i) {
        string tmp = to_string(i);
        while (tmp.size() < 3) {
            tmp = '0' + tmp;
        }
        int p1 = -1, p2 = -1, p3 = -1;
        for (int p = 0; p < N; ++p) {
            if (S.at(p) == tmp.at(0)) {
                p1 = p;
                break;
            }
        }
        if (p1 == -1) continue;
        for (int p = p1 + 1; p < N; ++p) {
            if (S.at(p) == tmp.at(1)) {
                p2 = p;
                break;
            }
        }
        if (p2 == -1) continue;
        for (int p = p2 + 1; p < N; ++p) {
            if (S.at(p) == tmp.at(2)) {
                p3 = p;
                break;
            }
        }
        if (p3 != -1) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
# input here
_INPUT = """\
101
"""

def main():
    # -*- coding: utf-8 -*-
    # スペース区切りの整数の入力
    K = int(input())

    t = 7
    for i in range(K):
        if t % K == 0:
            print(i + 1)
            break
        t = (t * 10 + 7) % K
    else:
        print(-1)

if __name__ == '__main__':
    import io
    import sys
    import math

    #sys.stdin = io.StringIO(_INPUT)
    main()

Measured memory_bytes: 9092
n=int(input())
a=[list(map(str,input().split())) for i in range(n)]
# print(a)
# print(len(a[0][0]))
ans=[]
cnt=0
# s=a[1][0]
# s=s.replace("a","b",1)
# print(s)

# print(a[0][0][0])
# print(a[0][0])
for i in range(len(a[0][0])):
    cnt=0
    for k in range(1,n):
        if (a[0][0][i] in a[k][0]):
            a[k][0]=a[k][0].replace(a[0][0][i],'',1)
            # print(a[k][0])
            cnt+=1
            # print(a)
    if cnt==n-1:
        ans.append(a[0][0][i])
ans.sort()
res=''
for x in ans:
    res+=x
print(res)

Measured memory_bytes: 3064