akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
typedef pair<int,int>   pii;
typedef vector<int>     vi;
typedef long double     ld;
#define MOD         1000000007
#define pb          push_back
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define endl        '\n'
#define PI          3.14159265359d
#define sz(x)       (int)x.size()
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    string s,s2;
    cin>>s;
    s2=s;
    reverse(all(s2));
    if(s==s2)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

bika=[0]
cika=[0]
j=0
k=0

a.sort()
b.sort()
c.sort()

for i in range(n):
  if j<n:
    while a[j]<b[i]:
      bika[i]+=1
      j+=1
      if j>=n:
        break
  if i!=n-1:
    bika.append(bika[i])

for i in range(n):
  if k<n:
    while b[k]<c[i]:
      cika[i]+=bika[k]
      k+=1
      if k>=n:
        break
  if i!=n-1:
    cika.append(cika[i])
print(sum(cika))

Measured memory_bytes: 24372
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
int gcd(int a,int b){
	if (a%b == 0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}

}

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

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}



  








      

 
int main(){
   string s;
    cin >> s;
    int n = s.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n - i; j++){
            string t = s.substr(0, j) + s.substr(j+i, n-1);
            //cout << t << endl;
            if(t == "keyence"){
                cout << "YES\n";
                return 0;
            }
        }
    }
    cout << "NO\n";
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
 
using namespace std;
 
/*-------------------------------*/
#define FOR(i, a, b) for(int i = (a); i < (b); i++) 
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; i--)
#define all(i) (i).begin(),(i).end()
#define pb push_back
#define mp make_pair 
 
typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef vector<long long> llv;
typedef vector<pint> vpint;
/*-------------------------------*/
 
int main(void)
{
  int a[3];
  char b[2];
  int rect = 0, rhom = 0;
  
  while (cin >> a[0] >> b[0] >> a[1] >> b[1] >> a[2]){
    if (a[0] == a[1]) rhom++;
    else if(a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) rect++;
  }
  cout << rect << "\n" << rhom << endl;

  return 0;
}

Measured memory_bytes: 3088
Parent = 0
Lchild = 1
Rsibling = 2
Clist = 3

def depth(n):
    i = node[n][Parent]
    if i == -1:
        return 0
    else:
        return depth(i) + 1

def nt(n):
    if node[n][Parent]== -1:
        return 'root'
    elif node[n][Lchild]== -1:
        return 'leaf'
    else:
        return 'internal node'
    return

n = int(input())
node = [[-1, -1, -1, []] for i in range(n)]
for i in range(n):
    tmp = map(int, raw_input().split())
    j = tmp[0]
    rank = tmp[1]
    if rank > 0:
        childs = tmp[2:]
        node[j][Clist] = childs
        p1 = 0
        c1 = childs[p1]
        node[j][Lchild] = c1
        node[c1][Parent] = j
        for p2 in range(1, rank):
            c2 = childs[p2]
            node[c2][Parent] = j
            node[c1][Rsibling] = c2
            c1 = c2

for i in range(n):
    msg = 'node {0}: parent = {1}, depth = {2}, {3}, {4}'
    print msg.format(i, node[i][Parent], depth(i), nt(i), node[i][Clist])

Measured memory_bytes: 39460
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())

la, ra = a - t * v, a + t * v + 1
lb, rb = b - t * w, b + t * w + 1


l, r = min(la, lb), max(ra, rb)
if l == la and r == ra:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 61612
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>

using namespace std;


int main(){
    int T;
    cin >> T;
    long sum = 0;
    for(long i=1;i<=T;i++){
        long bai = (long)(T/i);
        long cap = bai * i;
        sum += (cap+i) * (cap/i) / 2;
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3616
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <climits>
#include <ctime>
#include <random>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;

int main() {
	speed;
	int n, x, t;
	cin >> n >> x >> t;
	cout << (n + x - 1) / x * t;
}

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

int main() {
  int N, X , i;
  cin >> N;
  i = N;
  while(i > 0){
    X += i % 10;
    i /= 10;
  }
  
  if(N % X == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> N = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            N.add(Integer.parseInt(sc.next()));
        }
        Collections.sort(N);
        for (int i = 0; i < 3; i++) {
            if (i == 2) {
                System.out.printf("%d\n", N.get(i));
            } else {
                System.out.printf("%d ", N.get(i));
            }
        }
    }
}

Measured memory_bytes: 26280
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<pair<int,int>> VPII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
void chmin(int64_t& a, int64_t b){
    a = min(a, b);
}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head
int q,m,n,k,res,tmp,tmp2,tmp3;
//int a[100001] = {};
//int b[100010] = {};
int a,b,c,d;
deque<PII> que;
string s;
VPII kukan[100002];
int dp[1005][1005];

const int CMAX = 2000000;
long long fact[CMAX] = {};
long long revFact[CMAX] = {};
void setFact(int N)
{
  fact[0] = 1;
  for (int i = 1; i<N; i++)
  {
    fact[i] = fact[i-1]*i;
    fact[i] %= mod;
  }
  revFact[N-1] = powmod(fact[N-1],mod-2);
  for (int i=N-2;i>=0;i--)
  {
    revFact[i] = revFact[i+1]*(i+1);
    revFact[i] %= mod;
  }
}

long long getC(int a, int b)
{
  return (((fact[a] * revFact[b]) % mod) * revFact[a-b]) % mod;
}

signed main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
	std::cin >>n>>a>>b>>c>>d;
    dp[0][0] = 1;
    setFact(n*2);
    rep(i,1,n+1){
        if (a<= i && i <= b){
            int wari = powmod(revFact[i],c-1);
        rep(j,c,d+1){
            if (j*i> n){break;}
            wari *= revFact[i];
            wari %= mod;
            rep(k,0,n+1){
                if(k + j*i <=n){
                    dp[i][k+j*i] += (dp[i-1][k] * getC(n-k,j*i))%mod * fact[j*i]%mod * revFact[j]%mod*wari;
                    dp[i][k+j*i] %= mod;
                }
                else{break;}
            }
        }
        }
        rep(j,0,n+1){
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= mod;
        }
    }
    cout<<dp[n][n]<<endl;
//    rep(i,0,n+1){
 //       rep(j,0,n+1){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<< endl;
//    }
}

Measured memory_bytes: 13056
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;cin>>n;
	int A[n+5];
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
	}
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
         if(i!=A[i])
         {
         	swap(A[i],A[A[i]]);
         	cnt ++;
         }
	}
	if(cnt>1) cout<<"NO\n";
	else cout<<"YES\n";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<algorithm>
#include<functional>
#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int k=0, i;
    for(i=0; i<s.length(); i++)
    {
    	if(s[i]==s[i+1] && i+1>=s.length()-1)
    	{
    		k++;
    		break;
		}
    	else if(s[i]==s[i+1] && i+1<=s.length()-1)
    	{
    		k+=2;
    		i+=2;
		}
		else k++;
	}
    cout<<k<<endl;
    
    return 0;
}

Measured memory_bytes: 720
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main () {
    int R[MAX], n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) cin >> R[i];  //for が 1 から n-1 まで

    int maxv = -2000000000; //十分小さい値を初期値に設定
    int minv = R[0];

    for ( int i = 1; i < n; i++ ) { //ここで毎回 R[i] を読み込めば、配列は不要
      maxv = max(maxv, R[i] - minv);  //最大値を更新
      minv = min(minv, R[i]);         //ここまでの最小値を保持しておく
    }

    cout << maxv << endl;

    return 0;
}


Measured memory_bytes: 3904
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
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 dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


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

char sol(int t,char c){
    int res;
    if('a'<=c&&c<='z')res=c-'a';
    else res=c-'A'+26;
    char ans;
    res=(res-t+52)%52;
    if(0<=res&&res<26)ans='a'+res;
    else ans='A'+(res-26);
    return ans;
}
int main(){
    int n;
    int k[110];
    string s;
    while(true){
        cin>>n;
        if(n==0)break;
        REP(i,n)
            cin>>k[i];
        cin>>s;
        string ans="";
        REP(i,s.size()){
            cout<<sol(k[i%n],s[i]);
        }
        cout<<endl;
    }
    return 0;
}


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

typedef long long ll;

const int N = 20;

int digit[N];

int main(){
	ll n;
	scanf("%lld", &n);
	int cnt = 0;
	for ( ; n; n /= 10){
		digit[cnt ++] = n % 10;
	}
	std::reverse(digit, digit + cnt);
	int max = digit[0] - 1;
	bool flag = true;
	for (int i = 1; i < cnt; ++ i){
		max += 9;
		flag = flag && digit[i] == 9;
	}
	max += flag;
	printf("%d\n", max);
	return 0;
}

Measured memory_bytes: 256
n,h,w=map(int,input().split())
ab = []
for _ in range(n):
  ab.append(input().split())
  ab[-1][0] = int(ab[-1][0])
  ab[-1][1] = int(ab[-1][1])
  if ab[-1][0] < h or ab[-1][1] < w:
    ab.pop()
print(len(ab))

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

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

	long A, B;
	cin >> A >> B;

	if((A+B)%2 != 0) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		cout << (A+B)/2 << endl;
	}

	return 0;
}


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

int main(){
	int n,m;
	cin >> n >> m;
	map<int,int> mp;
	rep(i,3) mp[i] = -1;
	bool exist = true;
	rep(i,m){
		int s,c;
		cin >> s >> c;
		s--;
		if(mp[s] != -1 && mp[s] != c) exist = false;
		mp[s] = c;
	}
	if(!exist){
		cout << -1 << endl;
		return 0;
	}
	rep(i,1000){
		string t = to_string(i);
		if(t.size() != n) continue;
		bool ok = true;
		rep(j,t.size()){
			if(mp[j] != -1 && mp[j] != t[j] - '0') ok = false;
		}
		if(ok){
			cout << i << endl;
			return 0;
		}
	}
	cout << -1 << endl;
    return 0;
}



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

int main() {
  int N, K;
  cin >> N >> K;
  int ret = K;
  for (int i = 0; i < N - 1; i++) {
    ret *= K - 1;
  }
  cout << ret << endl;
}

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

string s,t;
int a,b;
string u;
int main(int argc, char const *argv[]){
	cin >> s >> t;
	cin >> a >> b;
	cin >> u;

	if(!s.compare(u)) a-=1;
	if(!t.compare(u)) b-=1;

	cout << a << ' ' << b << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;

    // dp[i][j] is the total cost such that we did activity j on day i
    int dp[n][3];
    cin >> dp[0][0] >> dp[0][1] >> dp[0][2];
    for (int i = 1; i < n; i++) {
        int c[3];
        for (int j = 0; j < 3; j++) cin >> c[j];
        for (int new_dp[3], j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) new_dp[k] = dp[i - 1][k];
            new_dp[j] = 0;
            dp[i][j] = c[j] + max({new_dp[0], new_dp[1], new_dp[2]});
        }
    }
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;

    return 0;
}


Measured memory_bytes: 4736
N,Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

L = [(s-x-0.5, t-x-0.5,x) for s,t,x in STX] + [(d,) for d in D]
L.sort()

import heapq
hp = [] # xを入れる
memo = {} # x:t-x

for l in L:
  if len(l)==1:
    while hp and l[0] > memo[hp[0]]:
      heapq.heappop(hp)
    if hp:
      print(hp[0])
    else:
      print(-1)
  else:
    heapq.heappush(hp, l[2])
    memo[l[2]]=l[1]

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

#define rep(i,n) for(int i=0;i<n;i++)

int main()
{
    int n;
    cin>>n;
    int a[n];

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

    int sum=1e9;
    int temp=0;
    for(int i=0;i<100;i++)
    {   
        temp=0;
        for(int j=0;j<n;j++)
        {
             temp+=pow((a[j]-(i+1)),2); 
        }
        sum = min(sum,temp);
    }

    cout<<sum<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define numrep(i,n) for(int i=1;i<=n;i++)
#define ll int64_t
#define all(v) v.begin(), v.end()
#define bitrep(n) for(int bit=0;bit<(1<<n);bit++)


//条件が複数ある場合は段階に分けるのも手
int main() {

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

ll r=0,g=0,b=0;

rep(i,N){
  if(S[i]=='R') r++;
  else if(S[i]=='G') g++;
  else b++;
}

ll ans=r*g*b;//まず組み合わせパターン全てを算出

ll sub=0;

rep(i,N-2){
  for(int j=i+1;j+(j-i)<N;j++){
    if(S[i]!=S[j]&&S[j]!=S[j+(j-i)]&&S[i]!=S[j+(j-i)]){
      sub++;
    }
  }
}

cout << ans-sub << endl;

return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int mx = 1e9;
    for (int i = 0; i < n; i++) {
        int curr, cnt = 0;
        cin >> curr;
        while (curr % 2 == 0) {
            curr /= 2;
            cnt++;
        }
        mx = min(mx, cnt);
    }
    cout << mx;
    return  0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
B=list(map(lambda x:abs(x),A))

A.sort()
for i in range(N):
    if A[i]>0:
        break
hu=A[:i]
sei=A[i:]

l=[]
if sei and hu:
    ans=sei.pop(-1)
    for item in sei:
        l.append([hu[0],item])
        hu[0]-=item
    for item in hu:
        l.append([ans,item])
        ans-=item

elif sei:
    ans=sei.pop(-1)
    for i in range(len(sei)-1):
        l.append([sei[0],sei[i+1]])
        sei[0]-=sei[i+1]
    l.append([ans,sei[0]])
    ans-=sei[0]
elif hu:
    for i in range(len(hu)-1):
        l.append([hu[-1],hu[-i-2]])
        hu[-1]-=hu[-i-2]
    ans=hu[-1]

print(ans)
for item in l:
    print(*item)

Measured memory_bytes: 27228
function main(input) {
    const args = input.split('\n');
    const A = parseInt(args[0], 10),
          B = parseInt(args[1], 10),
          C = parseInt(args[2], 10),
          X = parseInt(args[3], 10);

    var count = 0;

    for (var a = 0; a <= A; ++a) {
        for (var b = 0; b <= B; ++b) {
            for (var c = 0; c <= C; ++c) {
                var sum = (a * 500) + (b * 100) + (c * 50);
                if (sum === X) ++count;
            }
        }
    }
    console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 32384
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<pair<int,int>> a;
  int k,p;
  for(int i=0;i<n;i++){
    cin >> k >> p;
    a.push_back(make_pair(k,p));
  }
  sort(a.begin(),a.end());
  
  long cost = 0;
  while(m>0){
    for(int i=0;i<n;i++){
      long l = min(m, a[i].second);
      m -= l;
      cost += a[i].first * l;
      if (m == 0) break;
    }
  }
  cout << cost << endl;
}

Measured memory_bytes: 1400
#include <math.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <ostream>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef int _lcint;
#define REP(i, n) for (_lcint i = 0; i < n; i++)
#define FOR(i, a, b) for (_lcint i = (_lcint)(a); i < (_lcint)(b); i++)
#define FORREV(i, a, b) for (_lcint i = (_lcint)(b)-1; i >= (_lcint)(a); i--)
#define DEBUG(x) cout << #x << ": " << x << endl;
#define DEBUG_VEC(v)  \
  cout << #v << ": "; \
  REP(i, v.size()) cout << " " << v[i] << endl;

#define ALL(a) (a).begin(), (a).end()
#define CHMIN(a, b) a = min((a), (b))
#define CHMAX(a, b) a = max((a), (b))

// permutation
ll mPn(ll m, ll n) {
  ll a = 1;
  REP(i, n) { a *= m - i; }
  return a;
}

// excrametion
ll exc(ll m) {
  ll a = 1;
  FOR(i, 1, m) { a *= i + 1; }
  return a;
}

// combination
ll mCn(ll m, ll n) {
  ll a = 1, b = 1;
  REP(i, n) {
    a *= m - i;
    b *= n - i;
  }
  return a / b;
}

int main() {
  int A, B;
  int r;
  cin >> A >> B;

  if (A < B) {
    r = B--;
  } else {
    r = A--;
  }

  if (A < B) {
    r += B;
  } else {
    r += A;
  }

  cout << r << endl;

  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict, deque
import math

kMod = 1000000007

N = int(input())
key2count = defaultdict(lambda: [0, 0])

for _ in range(N):
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    if a < 0 or a == 0 and b < 0:
        a, b = -a, -b
    if g > 0:
        a, b = a//g, b//g
    idx = 0
    if b <= 0:
        idx = 1
        a, b = -b, a
    key2count[(a, b)][idx] += 1

ans = 1
for key, val in key2count.items():
    if key == (0, 0):
        continue
    plus, minus = val
    ans *= (pow(2, plus, kMod) + pow(2, minus, kMod)-1)
    ans %= kMod

ans += sum(key2count[(0, 0)])

print((ans + kMod-1) % kMod)

Measured memory_bytes: 60552
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

typedef long long ll;

double xx(double r) {
	return r*r;
}

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

int main() {
	int a[4], b[4];
	while ( scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]) != EOF ) {
		for (int i = 0; i < 4; ++i) scanf("%d", &b[i]);

		map<int, bool> m;
		for (int i = 0; i < 4; ++i) m[a[i]] = true;

		int hit = 0, blow = 0;
		for (int i = 0; i < 4; ++i) {
			if (a[i] == b[i]) ++hit;
			else if (m[b[i]]) ++blow;
		}
		cout << hit << " " << blow << endl;
	}
}

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

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

using namespace std;

int main(){
  int n;cin>>n;
  map<ll, ll> having;
  rep(i,n){
    ll t;cin>>t;
    having[t]++;
  }
  bool f=true;
  int m;cin>>m;
  rep(i,m){
    ll t;cin>>t;
    having[t]--;
    if(having[t]<0){
      f=false;
      break;
    }
  }
  if(f) cout<<"YES";
  else cout<<"NO";

  return 0;
}

Measured memory_bytes: 12800
use std::cmp;
use std::io;

fn calc_gcd(num1: i64, num2: i64) -> i64 {
    let mut big_num = cmp::max(num1, num2);
    let mut min_num = cmp::min(num1, num2);

    let mut rest_num;
    loop {
        rest_num = big_num % min_num;
        if rest_num == 0 {
            return min_num;
        } else {
            big_num = min_num;
            min_num = rest_num;
        }
    }
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let k: i64 = buf.trim().parse().unwrap();

    let mut total: i64 = 0;

    for num1 in 1..k + 1 {
        for num2 in 1..k + 1 {
            let gcd_num1_num2 = calc_gcd(num1, num2);
            for num3 in 1..k + 1 {
                total += calc_gcd(gcd_num1_num2, num3);
            }
        }
    }
    println!("{}", total);
}


Measured memory_bytes: 2112
#include <cstdio>

int main() {
    long long n;
    scanf("%lld", &n);
    long long sum = 0;
    int nn = n;
    while (n > 0) {
        int rem = n % 10;
        sum += rem;
        n /= 10;
    }

    if (nn % sum == 0) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return  0;
}

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

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int A, B;
    cin >> A >> B;
    if ((A + B) % 2 == 1) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << (A + B) / 2 << endl;
    }
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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()
{   
    ll n;
    cin >> n;

    string ans;
    while(n) {
        --n;
        ans += char(n%26)+'a';
        n /= 26;
    }
    reverse(all(ans));
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int n,a[3][105];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2;i++)
	  for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++){
		a[1][i]+=a[1][i-1];
	}
	for(int i=1;i<=n;i++){
		a[2][i]=max(a[2][i-1],a[1][i])+a[2][i];
	}
	printf("%d\n",a[2][n]);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=4e5+5;
const int MOD=1e9+7;
ll a[N],sum[N];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
char mp[100][100];
int n,m;
bool check(int x,int y){
    for(int i=0;i<4;i++){
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]=='#')   return true;
    }
    return false;
}


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

    cin >>n>>m;
    for(int i=1;i<=n;i++)   cin >> mp[i]+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='#'&&!check(i,j)){
                cout <<"No"<<"\n";
                return 0;
            }
        }
    }
    cout <<"Yes"<<endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define ALL(x) (x).begin(), (x).end()
constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=1e9+7; constexpr int NIL = -1;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<class T>inline int popcount(T a) {return __builtin_popcount(a);}
//-------------------

struct mint {
	ll x;
	mint(ll x=0):x(x%mod){}

	bool operator==(const mint a)const{return x==a.x;}
	bool operator!=(const mint a)const{return x!=a.x;}
	bool operator>=(const mint a){return (x >= a.x)? 1: 0;}
	bool operator<(const mint a){return !(*this>=a);}
	bool operator>(const mint a){return (x > a.x)? 1:0;}
	bool operator<=(const mint a){return !(*this>a);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
			return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
			return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res*=a;
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res/=a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;  //2 square
		if (t&1) a *= *this; 
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod-2);
	}
};

//here below is Matrix library.
template <class T>
using Matrix = vector< vector<T> >;

template <class T>
void init_mat(Matrix<T> &A, int h, int w){
	A.resize(h, vector<T>(w,0));
}

template <class T>
Matrix<T> dot_mat(Matrix<T> A, Matrix<T> B){
	Matrix<T> C(A.size(), vector<T>(B[0].size()));
	for(int i=0; i<A.size(); i++){
		for(int k=0; k<B.size(); k++){
			for(int j=0; j<B[0].size(); j++){
				C[i][j] = C[i][j] + A[i][k]*B[k][j];
			}
		}
	}
	return C;
}

template <class T>
Matrix<T> pow_mat(Matrix<T> A, ll n){
	Matrix<T> B(A.size(), vector<T>(A.size()));
	for(int i=0; i<A.size(); i++) B[i][i] = 1;
	while(n){
		if(n&1) B = dot_mat(B,A);
		A = dot_mat(A,A);
		n >>= 1;
	}
	return B;
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(15);
    int n; cin >> n;
    ll k; cin >> k;
    Matrix<mint> A;
    init_mat(A, n, n);
    rep(i,n) rep(j,n) {
        ll a; cin >> a;
        A[i][j] = mint(a);
    }

    Matrix<mint> v; 
    init_mat(v, n, 1);
    rep(i,n) v[i][0] = mint(1);

    auto y = dot_mat(pow_mat(A, k), v);

    mint ans(0);
    rep(i,n) ans += y[i][0];
    cout << ans.x << endl; 
    return 0;
}


Measured memory_bytes: 3784
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var item = Console.ReadLine().Split().Select(elem => double.Parse(elem)).ToArray();
            var H = item[0];
            var W = item[1];
            long answer;
            if (H == 1 || W == 1)
            {
                answer = 1;
            }
            else
            {
                answer = (long)Math.Ceiling(H * W / 2);
            }

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13396
/*
 * main.c
 *
 *  Created on: 2019/07/21
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int x[8] = {0}, y[9] = {0};
double d[8][8] = {0};

double get_value(int i, int j)
{
	double ret = 0.0;
	ret = pow((x[i] - x[j]), 2.0);
	ret += pow((y[i] - y[j]), 2.0);
	ret = sqrt(ret);
	//printf("i=%d j=%d %.09f\n", i, j, ret);
	return ret;
}

int main()
{
	int N = 0, i = 0, j = 0;
	double ans = 0.0; //, base = 1.0;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d %d", &x[i], &y[i]);
	}
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			ans += get_value(i, j);
		}
	}
	//printf("%f\n", base);
	//printf("%.09f\n", ans);
	//printf("%.09f\n", (ans*(double)(N-1)));
	printf("%.09f\n", (ans*(double)(N-1))/(N * (N-1)));

    return 0;
}


Measured memory_bytes: 128
N = int(input())
a = (N - (N % 3) + 3) * (N // 3) // 2
b = (N - (N % 5) + 5) * (N // 5) // 2
c = (N - (N % 15) + 15) * (N // 15) // 2
d = (1 + N) * N // 2
print(d - a - b + c)


Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	int n,ans=99999999;cin>>n;
	for (int i=1;i<=n/2;i++){
		int j=n-i,k=i,t=0;
		while(k){
			t+=(k%10);k/=10;
		}
		while(j){
			t+=(j%10);j/=10;
		}
		ans=min(ans,t);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main()
{
    int N;
    cin >> N;
    int *A = new int[N];
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    int cnt = 0;
    bool fl = true;
    while(fl){
        for (int i = 0; i < N;i++){
            if(A[i]%2 != 0){
                fl = false;
                break;
            }
            A[i] /= 2;
        }
        if(fl)
            cnt++;
    }
    cout << cnt;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; 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; }
const ll MOD = 1e9+7;


bool black[100100];
int main(){
    string S;
    cin >> S;
    int N = S.length();
    REP(i,N){
        if(S[i] == '0')
            black[i] = true;
    }


    int ans = N;

    int num = 0;
    REP(i,N){
        if(i%2 == 0){
            if(black[i]) num++;
        }
        else{
            if(!black[i]) num++;
        }
    }
    chmin(ans, num);

    num = 0;
    REP(i,N){
        if(i%2 == 0){
            if(!black[i]) num++;
        }
        else{
            if(black[i]) num++;
        }
    }
    chmin(ans, num);

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


Measured memory_bytes: 512
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;
use nalgebra::min;

#[fastout]
fn main() {
    input! {
    n: usize,
    s: Chars
    }
    let mut l = vec![vec![0; 2]; n + 2];
    for i in 0..n {
        l[i + 1][0] = l[i][0];
        l[i + 1][1] = l[i][1];
        l[i + 1][if s[i] == 'W' { 0 } else { 1 }] += 1;
    }
    l[n + 1] = l[n].clone();
    let mut ans = std::usize::MAX;
    for i in 0..n {
        ans = min(ans, l[i][0] + l[n + 1][1] - l[i + 1][1]);
    }
    println!("{}", ans);
}


Measured memory_bytes: 19936
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define pp pair<ll,ll>
#define vi vector<pair<pp,pp> >
#define pq_min priority_queue<ll,vector<ll>,greater<ll>>
#define pq_max priority_queue<ll>
#define forx(i,a,b) for(ll i=0;i<a;i++)
#define ld long double
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef pair<pp,pp> ppll;
const ll mod=1e9 + 7;

int main()
{
	fast;
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll ans=0;
    for(ll i=0;i<n;i++)
    {
    	if(i+2<n && s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
    	{
           ans++;
    	}
    }
	cout<<ans<<endl;
}

Measured memory_bytes: 256
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import math

def solve():
    k = II()
    ans = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            g1 = math.gcd(a, b)
            for c in range(1, k+1):
                g2 = math.gcd(g1, c)
                ans = ans + g2

    print(ans)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 9216
//参考：https://qiita.com/DaikiSuyama/items/9dba963ba74396b9b7fd
//インクルード(アルファベット順)
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列
using namespace std;
typedef long long ll;
//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define FIR first    //pairの一つ目の要素
#define SEC second   //pairの二つ目の要素
signed main()
{
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, K;
    cin >> N >> K;

    vector<int> A(N);
    REP(i, N)
    {
        cin >> A[i];
    }

    //参考：https://misteer.hatenablog.com/entry/ARC099#C---Minimization-%E6%9C%80%E5%B0%8F%E5%8C%96
    ll Q = (N - 1) / (K - 1);
    ll R = (N - 1) % (K - 1);

    ll ans = (R == 0 ? Q : Q + 1);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
int h[100001];
int dp[100001];
int main(int argc, char const *argv[]) {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) 
        scanf("%d", &h[i]);
    dp[0] = 0;
    for(int i = 1; i < n; ++i) {
        dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
        if(i > 1)
            dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
    }
    printf("%d\n", dp[n-1]);
    return 0;
}

Measured memory_bytes: 4556
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	m := map[string]int{
		"SUN": 7,
		"MON": 6,
		"TUE": 5,
		"WED": 4,
		"THU": 3,
		"FRI": 2,
		"SAT": 1,
	}

	fmt.Println(m[s])
}


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

float gyaku(float a){
  float b;
  b = 1/a;
  return b;
}

int main() {
  int n;
  cin >> n;
  float a[n];
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  
  float sum = 0;
  for(int i = 0; i < n; i++){
    sum += gyaku(a[i]);
  }
  cout << gyaku(sum) << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i<n; i++){
        cin >> a[i];
    }
    int mai = 0;
    int pura = 0;
    long long acc = 0;
    long long minn = 1'000'000'000;
    for (int i = 0; i<n; i++){
        if (a[i]<0) mai++;
        else pura++;
        acc += abs(a[i]);
        minn = min(minn,abs(a[i]));
    }
    long long ans;
    if (mai%2!=0) ans=acc-minn*2;
    else ans=acc;
    cout << ans << endl;
}



Measured memory_bytes: 1024
n=int(input())
l=list(map(int,input().split()))
 
ans=0
for i in range(0,n):
    for j in range(i+1,n):
        for k in range(j+1,n):
 
            if l[i]!=l[j] and l[j]!=l[k] and l[i]!=l[k]:
                if  l[i]+l[j]>l[k] and l[j]+l[k]>l[i] and l[k]+l[i]>l[j]:
                    ans+=1
 
print(ans) 

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

typedef long long int ll;

int main() {
	ll x; cin >> x;

	ll cnt = 0;
	while(x >= 500) {
		x -= 500;
		cnt++;
	}
	ll cnt2 = 0;
	while (x >= 5) {
		x-=5;
		cnt2++;
	}

	cout << cnt*1000+cnt2*5 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[110000];

// DP テーブル
long long dp[110000];

int main() {
    int N, K; cin >> N >> K;
    for (int i = 0; i < N; ++i) cin >> h[i];

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 110000; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= K; ++j) {
            chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }

    // 答え
    cout << dp[N-1] << endl;
}

Measured memory_bytes: 5184
inf = 1 << 60
m = inf
i = 10 ** 15 - 1
sunuke = []
while i > 0:
    a=sum(map(int,str(i)))
    b=i/a
    if m >= b:
        #print(f'{i} / {a} = {b}')
        m = b
        sunuke.append(i)
    for j in range(15,2,-1):
        if i > 10**j:
            i -= 10**(j-3)
            break
    else:
        i -= 1

K=int(input())
for i in range(K):
    print(sunuke[-i-1])


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

#ifdef local
#define _assert(expr) assert(expr)
#else
#define _assert(expr)
#endif

int Mod = 998244353;

typedef long long ll;

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
int inv(int a, int Mod = ::Mod) {
  int x, y;
  exgcd(a, Mod, x, y);
  return (x < 0) ? (x + Mod) : x;
}

class Z {
  public:
    int v;

    Z() {	}
    Z(int v) : v(v) {
      _assert(v >= 0 && v < Mod);
    }
    Z(ll x) : v(x % Mod) {	}

    friend Z operator + (Z a, Z b) {
      int x;
      return Z((x = a.v + b.v) >= Mod ? x - Mod : x); 
    }
    friend Z operator - (Z a, Z b) {
      int x;
      return Z((x = a.v - b.v) < 0 ? x + Mod : x);
    }
    friend Z operator * (Z a, Z b) {
      return 1ll * a.v * b.v;
    }
    friend Z operator ~ (Z a) {
      _assert(a.v);
      return inv(a.v);
    }
    friend Z operator - (Z a) {
      return Z(0) - a;
    }
    Z& operator += (Z b) {
      return *this = *this + b;
    }
    Z& operator -= (Z b) {
      return *this = *this - b;
    }
    Z& operator *= (Z b) {
      return *this = *this * b;
    }
};

typedef Z Zi;

Zi qpow(Zi a, int p) {
  if (p < 0)
    p += Mod - 1;
  Zi rt = 1;
  for ( ; p; p >>= 1, a *= a) {
    if (p & 1) {
      rt *= a;
    }
  }
  return rt;
}
Zi qpow(Zi a, ll p) {
  return qpow(a, (int) (p % (Mod - 1)));
}

const int N = 405;

int n, K;

vector<Zi> fac, _fac;

void init_fac(int n) {
  fac.resize(n + 1);
  _fac.resize(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i;
  }
  _fac[n] = ~fac[n];
  for (int i = n; i; i--) {
    _fac[i - 1] = _fac[i] * i;
  }
}
Zi comb(int n, int m) {
  return n < m ? 0 : fac[n] * _fac[m] * _fac[n - m];
}

Zi f[205][205];

Zi calc(int n, int m, int bu, int bd) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      f[i][j] = 0;
    }
  }
  for (int j = 0; j < m; j++) {
    f[0][j] = (j <= bu && j >= bd);
  }
  for (int i = 1; i < n; i++) {
    Zi sum = 0;
    for (int j = 0; j < m && j <= bu + i; j++) {
      sum += f[i - 1][j];
      if (j >= bd + i) {
        f[i][j] = sum;
      }
    }
  }
  Zi sum = 0;
  for (int j = max(bd + n - 1, 0); j < m && j < bu + n; j++) {
    sum += f[n - 1][j];
  }
  for (int i = 1; i < n; i++) {
    if (i + bu >= m) {
      sum += f[i][m - 1];
    }
  }
  return sum;
}

int main() {
  scanf("%d%d%d", &n, &K, &Mod);
  init_fac(405);
  K = n - 1 - K;
  Zi ans = !K;
  for (int sl = max(K, 1); sl < n; sl++) {
    for (int sr = max(K, 1); sl + sr < n; sr++) {
      Zi tmp = calc(sr, sl, sl - K, K - sr); 
//      cerr << tmp.v << " ";
      tmp = tmp * ~Zi(sl + sr + 1);
      ans += tmp;
    }
  }
  ans *= fac[n];
  printf("%d\n", ans.v);
  return 0;
}

Measured memory_bytes: 3984
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vec vector
#define psb push_back
#define ppb pop_back
#define mkp make_pair
#define fst first
#define scd second
#define ins insert
#define psf push_front
#define ppf pop_front
using namespace std;
int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll x, i, j;
	bool a[100004];
	memset(a, true, sizeof(a));
	for(i = 2; i*i <= 100004; i++) {
		if(a[i]) {
			for(j = i<<1; j < 100004; j+=i){
				a[j]=false;
			}
		}
	}
	vec<ll> b;
	for(i=2;i<100004;i++)
		if(a[i])
			b.psb(i);
	cin >> x;
	cout << *lower_bound(b.begin(), b.end(), x); //ge
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 5050;
int n,p[N],pos[N],a,b,mx[N][N];
ll f[N][N];
int main() {
	read(n);read(a);read(b);rep(i,1,n)read(p[i]),pos[p[i]]=i;
	rep(i,1,n)rep(j,i,n)mx[i][j]=max(mx[i][j-1],p[j]);
	rep(i,0,n)rep(j,0,n)f[i][j]=1e16;
	f[0][0]=0;
	rep(i,0,n-1)rep(j,0,n)if(f[i][j]<1e16){
		if(pos[i+1]<=j)umin(f[i+1][j],f[i][j]+a);
		else if(i+1==mx[j+1][pos[i+1]])umin(f[i+1][j],f[i][j]);
		else{
			umin(f[i+1][j],f[i][j]+b);
			umin(f[i+1][pos[i+1]],f[i][j]);
		}
	}
	ll res=1e16;rep(i,0,n)umin(res,f[n][i]);
	cout<<res;
	return 0;
}


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

// constexpr int INF = 1000101010;

int main(){
  int n,m;
  cin >> n >> m;
  vector<vector<int>> r(n);
  rep(i,m){
    int a,b;
    scanf("%d%d",&a,&b);
    r[a-1].push_back(b-1);
    r[b-1].push_back(a-1);
  }

  queue<int> q;
  vector<int> c(n,-1);
  vector<int> d(n,-1);

  d[0]=0;
  q.push(0);

  while(!q.empty()){
    int v = q.front();
    q.pop();
    for(int j: r[v]){
      if(d[j]!=-1) continue;
      d[j] = d[v]+1;
      c[j] = v;
      q.push(j);
    }
  }

  // rep(i,n){
  //   for(int j:r[i]){
  //     if(c[j]==-1) c[j]=c[i]+1;
  //   }
  // }
printf("%s\n","Yes");
  for(int i=1;i<n;++i){
    printf("%d\n",c[i]+1);
  }
  return 0;
}

Measured memory_bytes: 10660
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int n,s;
	cin >> n;
	vector<int>arr(50001,0);
	rep(i, 50000)arr[i + 1] += arr[i] + (i+1);
	auto itr = lower_bound(all(arr), n);
	int k = itr - arr.begin();
	s = n;
	for (int i = k; i > 0; i--) {
		if (s - i < 0)continue;
		s -= i;
		cout << i << endl;
	}
	return 0;
}



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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX_N 1000100

using namespace std;

typedef unsigned long long ll;

ll euler[MAX_N];
ll answer[MAX_N];

void euler_phi2(){
  for(ll i=0;i<MAX_N;i++)euler[i] = i;
  for(ll i=2;i<MAX_N;i++){
    if(euler[i] == i){
      for(ll j=i;j<MAX_N;j+=i)euler[j]=euler[j]/i*(i-1);
    }
  }
}

int main(){
  euler_phi2();
  answer[1] = 2;
  REP(i,2,MAX_N)answer[i] = answer[i-1] + euler[i];
  int t,n;
  scanf("%d",&t);
  rep(_,t){
    scanf("%d",&n);
    printf("%lld\n",answer[n]);
  }
  return 0;
}

Measured memory_bytes: 16812