akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	std::vector<int> A(n), B(n); A[0] = a[0];
	for(int i = 1; i < n; i++) A[i] = std::__gcd(A[i - 1], a[i]);
	reverse(begin(a), end(a)); B[0] = a[0];
	for(int i = 1; i < n; i++) B[i] = std::__gcd(B[i - 1], a[i]);
	
	int ans = std::max(B[n - 2], A[n - 2]);
	for(int i = 1; i < n - 1; i++) {
		ans = std::max(ans, std::__gcd(A[i - 1], B[n - i - 2]));
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1408
#pragma GCC target ("avx2")
#pragma GCC optimize "trapv"
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define input(a,n) for(ll i1=0;i1<n;i1++)cin>>a[i1]
#define ll long long
#define pi 2 * acos(0.0)
#define vll vector<ll>
#define mll map<ll,ll>
#define pll pair<ll,ll>
#define ull unordered_map<ll,ll>
#define S second
#define sz size()
#define all(v) v.begin(),v.end()
#define Y cout<< "YES"<< "\n"
#define N cout<< "NO"<< "\n"
#define F first
#define mp make_pair
#define pb push_back
#define ld long double
#define mod 1000000007
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,r=0,w=0,x=0,y=0,z=0;
    cin>>n;
    string s,a="",b="",c="";
    cin>>s;
    for(ll i=0;i<n;i++)
    {
        if(s[i]=='R')
            {
                r++;
                z++;
            }
        else
            {
                w++;
                y++;
            }
        a+='R';
        b+='W';
    }
    for(ll i=0;i<r;i++)
    {
           c+='R';
           if(s[i]=='W')
            x++;
    }
    ll ans=min({x,y,z});
    cout<<ans<< "\n";
    return 0;
}


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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    int N;cin>>N;
    vector<ll> S(N);
    for(int i=0;i<N;i++){
        cin>>S[i];
    }
    sort(all(S));
    for(int i=1;i<N;i++){
        S[i]+=S[i-1];
    }
    int cnt=1;
    for(int i=N-2;i>=0;i--){
        if(S[i]*3>=S[i+1]){
            cnt++;
        }
        else break;
    }
    cout<<cnt<<endl;
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  cout << (n / 500) * 1000 + (n % 500) / 5 * 5 << '\n'; 
  return 0;
}

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

//諸機能
#pragma region MACRO 
#define putans(x)  cerr << "answer: " ; cout << (x) << endl
#define dputans(x) cerr << "answer: "; cout << setprecision(10) << (double)(x) << endl
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define RREP(i,a,n) for(int i=(int)(n-1); i>= a; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) begin((a)),end((a))
#define mp make_pair
#define exist(container, n) ((container).find((n)) != (container).end())
#define substr(s,i,l) string((s), (i), (l))
#define tos(x) (to_string((x)))
#ifdef _DEBUG //ファイルからテストデータを読み込む
std::ifstream ifs("data.txt");
#define input ifs >>
#else //いい感じにやる
#define input cin >>
#endif
#pragma endregion
//デバッグなどの支援
#pragma region CODING_SUPPORT
#define dbg(var0) { std::cerr << ( #var0 ) << "=" << ( var0 ) << endl; }
#define dbg2(var0, var1) { std::cerr << ( #var0 ) << "=" << ( var0 ) << ", "; dbg(var1); }
#define dbg3(var0, var1, var2) { std::cerr << ( #var0 ) << "=" << ( var0 ) << ", "; dbg2(var1, var2); }
#define dbgArray(a,n) {std::cerr << (#a) << "=";  rep(i,n){std::cerr <<(a[i])<<",";} cerr<<endl;} 
#ifndef _DEBUG
#define dbg1 {}
#define dbg2 {}
#define dbg3 {}
#define dbgArray {}
#endif 
#pragma endregion 
//typedef（書き換える、書き足す可能性ある）
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii; typedef pair<string, string> pss; typedef pair<int, string>pis;
typedef vector<string> vs; typedef vector<int> vi;
#pragma endregion
//諸々の定数(書き換える可能性ある)
#pragma region CONST_VAL
#define PI (2*acos(0.0))
#define EPS (1e-9)
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e9)
#pragma endregion


int main() {
	int n; input n;
	int a[100];
	rep(i, n) input a[i];
	ll mn = INF;

	REP(i,-100 ,101) {
		ll tmp = 0;
		rep(j, n) {
			tmp += ( i - a[j] )*( i - a[j] );
		}
		mn = min(tmp, mn);
	}
	putans(mn);
	return 0;
}

//B
//
//string s; input s;
//	int seek = 0;
//	vector<char> ans;
//	rep(i, s.length()) {
//		if(s[i] != 'B'){
//			seek++; 
//			ans.push_back(s[i]);
//		}
//		else {
//			if (seek != 0) {
//				ans.erase(ans.begin() + seek-1);
//				seek--;
//			}
//		}
//	}
//	rep(i, ans.size()) {
//		cout << ans[i];
//	}
//	cout << endl;

Measured memory_bytes: 256
package main

import "fmt"

func f(x int) int {
	switch x {
	case 1, 3, 5, 7, 8, 10, 12:
		return 31
	case 2:
		return 28
	default:
		return 30
	}
}

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	if f(x) == f(y) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

int main(){
    long long ans=0, n, m;
    cin >> n >> m;

    if(n + m == 2){
        cout << 1 << endl;
        return 0;
    }else if((n == 1 && m == 2) || (n == 2 && m == 1)){
        cout << 0 << endl;
    }else if(n == 1 || m == 1){
        cout << (max(n, m) - 2) << endl;    
    }else{
        cout << (n-2)*(m-2) << endl;
    }
}

Measured memory_bytes: 256
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-05-17 23:34:25
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

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

  int n; cin >> n; n %= 10;
  if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) {
    cout << "hon" << endl;
  } else if (n == 3) {
    cout << "bon" << endl;
  } else {
    cout << "pon" << endl;
  }

  return 0;
}

Measured memory_bytes: 3560
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <tuple>
#include <algorithm>
#include <ctime>
#include <map>
#include <fstream>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;


const long long MOD = static_cast<long long>(1e9+7);
const long long INFINITE = static_cast<long long>(1e16);
const bool IS_DEBUG = false;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int H,W;
    cin>>H>>W;

    int Ch, Cw, Dh, Dw;
    cin>>Ch>>Cw>>Dh>>Dw;
    Ch--;
    Cw--;
    Dh--;
    Dw--;

    vector<string> lab(H);
    for(int c=0; c<H; c++) cin>>lab[c];

    priority_queue<tuple<int,int,int> > q;

    q.push(make_tuple(0,Ch,Cw));
    vector<vector<int> > seen(H,vector<int>(W,-1));
    seen[Ch][Cw]=0;
    int dx[4]= {0,0,-1,1};
    int dy[4]= {1,-1,0,0};
    while(q.size())
    {
        int distance = -get<0>(q.top());
        int x = get<1>(q.top());
        int y = get<2>(q.top());
        q.pop();
        if(seen[x][y] < distance) continue;
        seen[x][y]=distance;
        if(x == Dh && y == Dw) {
            cout<<distance;
            return 0;
        }

        for(int d=0; d<4; d++)
        {
            int x2 = dx[d]+x;
            int y2 = dy[d]+y;

            if(x2>=0&&y2>=0&&x2<H&&y2<W&&lab[x2][y2]=='.'&&(seen[x2][y2]==-1||seen[x2][y2] > distance))
            {
                q.push(make_tuple(-distance,x2,y2));
                seen[x2][y2]=distance;
            }
        }

        for(int d1 = -2; d1 <= 2; d1++)
        {
            for(int d2 = -2; d2 <= 2; d2++)
            {
                int x2 = d1+x;
                int y2 = d2+y;

                if(x2>=0&&y2>=0&&x2<H&&y2<W&&lab[x2][y2]=='.'&&(seen[x2][y2]==-1||seen[x2][y2] > distance+1))
                {
                    q.push(make_tuple(-distance-1,x2,y2));
                    seen[x2][y2]=distance+1;
                }
            }
        }
    }
    cout<<-1;
}


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

int main()
{
    int c1,c2,c3;
    while(cin >> c1 >> c2 >> c3)
    {
        int cards[11]={1,1,1,1,1,1,1,1,1,1,1};
        cards[c1]=0;
        cards[c2]=0;
        cards[c3]=0;
        
        int goodcard = 0;
        for(int i=1;i<=10;i++)
        {
            if(cards[i]==1 && ( (c1+c2) + i <=20)) goodcard++;
        }
        if(goodcard>3){cout << "YES"<< endl;continue;}
        else {cout <<"NO"<< endl;continue;}

    }

    return 0;
}

Measured memory_bytes: 0
using System;

namespace ABC167
{
    class Program
    {
        static void Main(string[] args)
        {
            A.Solve();
        }
    }
    public static class A {
        public static void Solve () {
            var s = Console.ReadLine ();
            var t = Console.ReadLine ();
            var res = s == t.Substring(0, s.Length) ? "Yes":"No";
            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 25644
def find_match(S, T):
    for i in range(len(S) - len(T) + 1):
        match = True
        for j in range(len(T)):
            if S[i+j] != "?" and S[i+j] != T[j]:
                match = False
                break
        if match:
            return i
    return -1


def main():
    S = input()[::-1]
    T = input()[::-1]
    idx = find_match(S, T)
    if idx != -1:
        S = S[:idx] + T + S[idx+len(T):]
        S = S[::-1].replace("?", "a")
    else:
        S = "UNRESTORABLE"
    print(S)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    int n;
    int a[109];

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n,greater<int>());
    int ret=0;
    for(int i=0;i<n;i++){
        ret+=a[i] * (i & 1 ? -1 : 1);
    }
    cout<<ret<<endl;

}

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

int main()
{
    string s;
    cin>>s;
    string t=s.substr(0,s.size());
    reverse(t.begin(),t.end());
    if(s.compare(t)==0)
    {
        string m=s.substr(0,s.length()/2);
        string n=m;
        reverse(m.begin(),m.end());
        if(m.compare(n)==0)
        {
            string mm=s.substr(s.length()/2+1,s.length());
            string nn=mm;
            reverse(mm.begin(),mm.end());
            if(mm.compare(nn)==0) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else cout<<"No"<<endl;
    }
    else cout<<"No"<<endl;
}


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

int main(){
  string s;
  std::cin >> s;
  bool ans1 = true;
  bool ans2 = true;
  for(int i = 0; i < s.size(); i+=2){
    if(s.at(i) == 'L'){
      ans1 = false;
      break;
    }
  }
  for(int i = 1; i < s.size(); i+=2){
    if(s.at(i) == 'R'){
      ans2 = false;
      break;
    }
  }
  if(ans1 && ans2){
    std::cout << "Yes" << '\n';
  }
  else{
    std::cout << "No" << '\n';
  }
  return 0;
}

Measured memory_bytes: 256
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

fun main() {
  val a = readLine()!!
  val b = readLine()!!

  val n = a.length
  val m = b.length

  val dp = Array<IntArray>(n+1){IntArray(m+1){0}}
  for (i in 0 until n){
    for(j in 0 until m){
      if(a[i] == b[j]){
        dp[i+1][j+1] = 1 + dp[i][j]
      }else dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    }
  }

  val ans = CharArray(dp[n][m]){'?'}
  var ix = dp[n][m]-1
  var i = n
  var j = m
  while(i > 0 && j > 0){
    if(a[i-1] == b[j-1]){
      ans[ix] = a[i-1]
      i--
      j--
      ix--
      continue
    }

    if(dp[i][j-1] > dp[i-1][j]){
      j--
    }else i--
  }

  println(ans)
}

Measured memory_bytes: 87092
#include<stdio.h>
int fun(long long int a,long long int b)
{
    long long int k;
    if(a>b)
    {
        if(a%b==0)
        {
            return b;
        }
        else
        {
            k=a%b;
            a=b;
            b=k;
            fun(a,b);
        }
    }
    else
    {
        if(b%a==0)
        {
            return a;
        }
        else
        {
            k=b%a;
            b=a;
            a=k;
            fun(a,b);
        }
    }
}
int main()
{
    long long int a,b,c,d;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        c=fun(a,b);
        d=a*b/c;
        printf("%lld %lld\n",c,d);
    }
    return 0;
}

Measured memory_bytes: 1796
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int H,W,N;
    cin >> H >> W >> N;

    int maxNum,ans;
    if(H>W) maxNum = H;
    else maxNum = W;

    if(N%maxNum==0) ans = N/maxNum;
    else ans = N/maxNum + 1;
    cout << ans << endl;
}

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

using std::max; using std::swap; using std::abs; using std::priority_queue; using std::queue; using std::bitset; using std::make_tuple; 
using std::istream; using std::ostream; using std::fixed; using std::greater; using std::tuple; using std::tie; using std::make_pair;
using std::cout; using std::cerr; using std::endl; using std::lower_bound; using std::upper_bound; using std::deque; using std::min; 
using std::map; using std::string; using std::fill; using std::copy; using std::sort; using std::unique; using std::unordered_set; 
using std::multiset; using std::nth_element; using std::min_element; using std::max_element; using std::vector; using std::set; 
using std::unordered_map; using std::pair; using std::next_permutation; using std::reverse; using std::rotate; using std::cin; 
using std::iota; using std::function; using std::shuffle;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

int const INF = 100 + (int) 1e9;
ll const INFL = 100 + (ll) 1e18;
ld const PI = 3.141592653589793238462643L;
std::mt19937 mt19937(960172);

ll rnd(ll x, ll y) { static auto gen = std::bind(std::uniform_int_distribution<ll>(), mt19937); return gen() % (y - x + 1) + x; }
bool is_prime(ll x) { if (x <= 1) return 0; for (ll y = 2; y * y <= x; ++y) if (x % y == 0) return 0; return 1; }
ll sqr(int a) { return (ll) a * a; } ld sqr(ld a) { return a * a; } ll sqr(ll a) { return a * a; }
ll gcd(ll a, ll b) { while (b > 0) { ll t = a % b; a = b; b = t; } return a; }




void solve() {
    
    string a = "CODEFESTIVAL2016";
    string b;
    cin >> b;
    
    int ans = 0;
    for (int i = 0; i < (int)a.size(); ++i) if (a[i] != b[i]) ++ans;
    
    cout << ans << endl;
    
    
}



int main() {
    
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    
    cout.precision(15);
    cout << fixed;
    cerr.precision(6);
    cerr << fixed;
    
    solve();
    
#ifdef LOCAL
    cerr << "time: " << (ll) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define BiSearchRangeNum(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y)

int main() {
  int A, B;
  cin >> A >> B;
  if (B * 2 >= A) {
    cout << 0 << endl;
    return 0;
  } else {
    cout << A - (B * 2) << endl;
  }
};


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	long long b, c, d = 0, e = 0;
	int a[123456];
	for (int i = 0; i < 3; i++) {
		cin >> a[i];
	}
	sort(a, a + 3);
	if ((a[2] - a[1]) % 2 == (a[2] - a[0]) % 2) {
		cout << (a[2] - a[1] + a[2] - a[0]) / 2 << endl;
	}
	else {
		cout << (a[2] - a[1] + a[2] - a[0] + 3) / 2 << endl;
	}
	cin >> e;
}

Measured memory_bytes: 256
s = input()
if s[0] == s[1] and s[2] == s[3] and s[0] != s[2]:
    print('Yes')
elif s[0] == s[2] and s[1] == s[3] and s[0] != s[1]:
    print('Yes')
elif s[0] == s[3] and s[1] == s[2] and s[0] != s[1]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9052
x, y= map(int,input().split())
A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
if x in A :
    if y in A :
        print("Yes")
    else :
        print("No")
elif x in B :
    if y in B :
        print("Yes")
    else :
        print("No")
else :
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
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;}

ll lcm(ll a, ll b) { return a*b/__gcd(a,b); }
int main() {
  ll A, B; cin >> A >> B;
  cout << lcm(A,B) << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define F(x) for(int i=1;i<=(x);i++)
#define fer(i,n) for(int i=1;i<=(n);i++)
#define FIN  {freopen("1.in","r",stdin);}
#define FOUT {freopen("1.out","w",stdout);}
#define OUT(x)  {cout<<"#x"<<" : "<<x<<endl;}
#define ERR(x)  {cout<<"#error:"<<x;while(1);}
typedef long long ll;
typedef unsigned long long ull;
#define se second
#define fi first
#define make_pair mkp
#define mid ((l+r)>>1)
const int MaxInt = -1u>>1;
const int Max_ = 0x3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1);
using namespace std;
inline int read()
{
    char ch=getchar();int f=1,g=0;
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) g=g*10+(ch^48);
    return g*f;
}
const int N = 500005;
int n,k;
int p[N],nt[N*2],hea[N*2],to[N*2],cnt=0,e[N*2],q[N*2];
inline void add(int u,int v)
{
    nt[++cnt]=hea[u];
    hea[u]=cnt;
    to[cnt]=v;
    e[v]++;
}
int t[N*4];
#define mid ((l+r)>>1)
inline void build(int x,int l,int r)
{
    t[x]=Max_;
    if(l==r) return;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
}
inline void ins(int x,int l,int r,int O,int v)
{
    if(l==r){
        t[x]=v;return;
    }
    if(mid>=O) ins(x*2,l,mid,O,v);
    else ins(x*2+1,mid+1,r,O,v);
    t[x]=min(t[x*2],t[x*2+1]);
}
inline int query(int x,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)
        return t[x];int a1=Max_,a2=Max_;
    if(mid>=L) a1=min(a1,query(x*2,l,mid,L,R));
    if(mid+1<=R) a2=min(a2,query(x*2+1,mid+1,r,L,R));
    return min(a1,a2);
}
int op[N];
priority_queue< int ,vector<int> ,greater<int> >Q;
void tp()
{
    for(int i=1;i<=n;i++) if(!e[i]) Q.push(i);
    while(!Q.empty())
    {
        int now=Q.top();Q.pop();
        op[now]=++cnt;
        for(int i=hea[now];i;i=nt[i])
        {
            int nod=to[i];
            e[nod]--;
            if(!e[nod]) Q.push(nod);
        }
    }
}
int main()
{
    n=read(),k=read();
    F(n) p[i]=read(),q[p[i]]=i;
    build(1,1,n);
    for(int i=n;i>=1;i--) {
        int now = query(1,1,n,min(n,q[i]+1),min(q[i]+k-1,n));
        if(now!=Max_) add(q[i],q[now]);
        now=query(1,1,n,max(1,q[i]-k+1),max(1,q[i]-1));
        if(now!=Max_) add(q[i],q[now]);
        ins(1,1,n,q[i],i);
    }
    cnt=0,tp();
    for(int i=1;i<=n;i++)
    {
        cout<<op[i]<<" ";
    }
    return 0;
}

Measured memory_bytes: 33524
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN printf("\n")
#define LL long long
inline int read(){
	int x=0,y=1;
	char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
	return x*y;
}
std::string s,t;
int main(){
	std::cin>>s>>t;
	std::cout<<t<<s;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		for (int i = 0; i < k; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			if (a > n / 2)
				a = n - a + 1;
			if (b > n / 2)
				b = n - b + 1;
			int c = Math.min(a, b) % 3;
			System.out.println(c == 0 ? 3 : c);
		}

	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

struct UnionFind{
    vector<int> par;

    UnionFind(int n) : par(n,-1) { }
    void init(int n) { par.assign(n,-1); }

    int root(int x){
        if(par[x]<0) return x;
        else return par[x]=root(par[x]);
    }

    bool issame(int x,int y){
        return root(x)==root(y);
    }

    bool merge(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return false;
        if(par[x]>par[y]) swap(x,y);
        par[x]+=par[y];
        par[y]=x;
        return true;
    }

    int size(int x){
        return -par[root(x)];
    }
};

using Graph=vector<vector<int>>;

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    UnionFind uf(n);

    Graph G(n);

    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--,b--;
        uf.merge(a,b);
        G[a].push_back(b);
		G[b].push_back(a);
    }
    rep(i,k){
        int a,b;
        cin>>a>>b;
        a--,b--;
        if(uf.issame(a,b)){
            G[a].push_back(b);
		    G[b].push_back(a);
        }
    }

    rep(i,n){
        cout<<uf.size(i)-1-G[i].size()<<" ";
    }
    cout<<endl;
}



Measured memory_bytes: 7936
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5+3;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	int n,k;cin>>n>>k;cout<<(n%k==0?0:1)<<endl;

	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            int iH = int.Parse(sS[0]);
            int iN = int.Parse(sS[1]);
            sS = System.Console.ReadLine().Trim().Split(' ');
            List<int> lstInp = new List<int>();
            for (int i = 0; i < sS.Length; i++) { lstInp.Add(int.Parse(sS[i])); }

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            string sOut = "No";
            if (lstInp.Sum() >= iH) { sOut = "Yes"; }

            // 出力
            System.Console.WriteLine("{0}", sOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 19296
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define endl "\n"
#define int ll
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define pll pair<ll, ll>
#define ull unsigned long long
#define ld long double

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;

#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=n-1; i>=0; i--)
#define repa(i,a,b) for(ll i=(a);i<=(b);i++)
#define all(x) (x).begin(), (x).end()
#define ordered_set tree<int , null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>
/*
 Ordered set docs:
 order_of_key (k) : Number of items strictly smaller than k .
 find_by_order(k) : K-th element in a set (counting from zero).
*/
#define blc boost::lexical_cast<long long>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
const int MOD = 1e9+7;
const ll INF = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll add(ll x, ll y) {ll res=x+y; return(res>=MOD?res-MOD:res);}

ll sub(ll x, ll y) {ll res=x-y; return(res<0?res+MOD:res);}

ll lcm(ll x, ll y) {ll res=(x*y)/__gcd(x,y); return res;}

ll powerLL(ll x, ll n, ll mod) 
{ 
    ll result = 1; 
    while (n) { if (n & 1) result = (result%mod * x%mod) % mod; n = n / 2; x = (x%mod * x%mod) % mod; } return result; 
} 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

const int N = 1e5+5;

struct DSU
{
	int connected;
	vector<int> par, sz;

	void init(int n) 
	{
		par = sz = vector<int> (n + 1, 0);
		for(int i = 1; i <= n; i++)
			par[i] = i, sz[i] = 1;
		connected = n;
	}

	int getPar(int u)
	{
		while(u != par[u])
		{
			par[u] = par[par[u]];
			u = par[u];
		}
		return u;
	}

	int getSize(int u)
	{
		return sz[getPar(u)];
	}

	void unite(int u, int v)
	{
		int par1 = getPar(u), par2 = getPar(v);

		if(par1 == par2)
			return;

		connected--;

		if(sz[par1] > sz[par2])
			swap(par1, par2);

		sz[par2] += sz[par1];
		sz[par1] = 0;
		par[par1] = par[par2];
	}
};

void solve()
{
    ll n, k;
    cin>>n>>k;
    DSU dsu;
    dsu.init(n);
    while(k--)
    {
    	ll a, u, v;
    	cin >> a >> u >> v;
    	u++;
    	v++;
    	if(a == 1)
    	{
    		int val = (dsu.getPar(u) == dsu.getPar(v));
    		cout<< val <<endl;
    	}
    	else
    		dsu.unite(u,v);
    }
}
int32_t main()
{
    fast;
    int t;
    t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0; 
}

Measured memory_bytes: 6340
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
char s[110];
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n>>s;
	if(n&1){
		cout<<"No"<<endl;
		return 0;
	}
	for(int i=0;i<n/2;i++){
		if(s[i]!=s[i+n/2]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())

s1 = input()
s2 = input()

INF = 1000000007

left = None
index = 0
cnt = 0
while index < n:
    # 右側が縦テトリス1つ
    if s1[index] == s2[index]:
        index += 1
        if left is None:
            left = 1
            cnt = 3
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 1
        left = 1

    # 右側が横テトリス2つ
    else:
        index += 2
        if left is None:
            left = 2
            cnt = 6
        # 左側が縦テトリス1つ
        elif left == 1:
            cnt *= 2
        # 左側が横テトリス2つ
        else:
            cnt *= 3
        left = 2
    cnt = cnt % INF
print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
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;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


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

    rep(i,N+1)cin>>A[i];
    rep(i,N)cin>>B[i];

    ll ans = 0; 
    rep(i,N){
        ans += min(A[i],B[i]);
        B[i] -= min(A[i],B[i]);
        ans +=min(A[i+1],B[i]);
        A[i+1] -= min(A[i+1],B[i]);

    }
    cout << ans << endl;


    return 0;
    

}

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

int main(){
  int N;
  cin >> N;
  bool a=false;
  if(N%10==9){
    a=true;
  }
  N/=10;
  if(N%10==9){
    a=true;
  }
  if(a){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
package main
import (
	"fmt"
	"os"
	"bufio"
	"strconv"
)

var stdin = bufio.NewScanner(os.Stdin)

func Input_int() int {
	stdin.Scan()
	out,err := strconv.Atoi(stdin.Text())
	if err != nil{
		panic(err)
	}
	return out
}

func main(){
	stdin.Split(bufio.ScanWords)
	point := [5]int{}
	for i:=0;i<5;i++{
		point[i] = Input_int()
	}
	k := Input_int()
	max,min := 0,124
	for i:=0;i<5;i++{
		if max<point[i]{
			max = point[i]
		}
		if min>point[i]{
			min = point[i]
		}
	}
	if (max-min)>k{
		fmt.Println(":(")
	}else{
		fmt.Println("Yay!")
	}
}

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


int main() {
    int a[10],ans,tmp;
    for(int i=0;i<5;i++) cin>>a[i];
    int m=10;
    for(int i=0;i<5;i++) {
      if(a[i]%10==0) tmp=a[i];
      else {
        tmp=((a[i]/10)+1)*10;
        m=min(m,a[i]%10);
      }
      ans+=tmp;
    }
    cout << ans-10+m << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] seq = new int[n];
    int total = 0;
    if(n ==2){
      total = 2* sc.nextInt();
    }else{
      for(int i = 0; i < n - 1; i++){
   seq[i] = sc.nextInt();
     if(i == 0){
     total += seq[i];
     }else if(i == n-2){
     total += seq[i];
       total += Math.min(seq[i],seq[i-1]);
     }else{
     total += Math.min(seq[i],seq[i-1]);
     }
   }  
    }
    System.out.println(total);
  }

}

Measured memory_bytes: 21716
#include<stdio.h>
long long int mod=1000000007;
long long int solve(int N,int M){
	static long long int dp[3001][3001]={0};
	long long int i,j,ans=0;
	if(N==0){return 0;}
	for(i=0;i<=N;i++){
		dp[0][i]=1;
	}
	for(j=1;j<=M;j++){
		i=0;
		dp[j][i]=dp[j-1][i]+dp[j-1][i+1];dp[j][i]%=mod;
		for(i=1;i<N;i++){
			dp[j][i]=dp[j-1][i-1]+dp[j-1][i]*2+dp[j-1][i+1];dp[j][i]%=mod;
		}
		dp[j][i]=dp[j-1][i-1]+dp[j-1][i];dp[j][i]%=mod;
	}
	for(i=0;i<=N;i++){
		ans+=dp[M][i];ans%=mod;
	}
	return ans;
}
int main(void){
	int N,M,it;
	scanf("%d %d",&N,&M);
	it=solve(N,M)-solve(N-1,M);
	if(it<0){it+=mod;}
	printf("%d\n",it);
	return 0;
}

Measured memory_bytes: 70528
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        List<Long> a = new ArrayList<>();
        IntStream.range(0, N).forEach( b -> a.add(scan.nextLong()));
        ArrayList<Long> retA = new ArrayList<>();
        ArrayList<Long> retB = new ArrayList<>();
        boolean flag = true;
        for (long data : a) {
            if(flag) {
                retA.add(data);
                flag = false;
            }
            else {
                retB.add(data);
                flag = true;
            }
        }
        if(N % 2 == 0) {
            IntStream.range(0, retB.size()).forEach(i -> System.out.print(retB.get(retB.size() - 1 - i) + " "));
            retA.forEach(x -> System.out.print(x + " "));
        }
        else {
            IntStream.range(0, retA.size()).forEach(i -> System.out.print(retA.get(retA.size() - 1 - i) + " "));
            retB.forEach(x -> System.out.print(x + " "));
        }
    }
}


Measured memory_bytes: 103520
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

graph = [[] for _ in range(N+1)]
for a,b in zip(AB,AB):
    graph[a].append(b)
    graph[b].append(a)

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

print(' '.join(map(str,val[1:])))


Measured memory_bytes: 124116
N,T = map(int,input().split())
food = [list(map(int,input().split())) for i in range(N)]

dp1 = [[0 for t in range(T+1)] for i in range(N+1)]

for i in range(1,N+1):
    time,deliciousness = food[i-1]
    for t in range(1,T+1):
        if time <= t:
            dp1[i][t] = max(dp1[i-1][t],dp1[i-1][t-time]+deliciousness)
        else:
            dp1[i][t] = dp1[i-1][t]
            
dp2 = [[0 for t in range(T+1)] for i in range(N+1)]

for i in range(N):
    time,deliciousness = food[N-i-1]
    for t in range(1,T+1):
        if time <= t:
            dp2[N-i-1][t] = max(dp2[N-i][t],dp2[N-i][t-time]+deliciousness)
        else:
            dp2[N-i-1][t] = dp2[N-i][t]

ans = 0

for t in range(T):
    for i in range(1,N+1):
        ans = max(ans,dp1[i-1][t]+dp2[i][T-1-t]+food[i-1][1])
        
print(ans)

Measured memory_bytes: 195076
n,*a=$<.read.split.map &:to_i
t=1
c=0
b=[0]*n
n.times do |i|
  b[c]+=1
  if t>a[i]
    c+=1
    t-=2
  end
  t+=2
end
ca=1
ta=0
n.times do |i|
  ta+=b[i]
  ca*=ta-i
  ca%=10**9+7
end
p ca

Measured memory_bytes: 11644
#include <iostream>
#include <vector> 
using namespace std;
int n,m;
int num[11]={0};
int cnt=0;
vector <int>s[11]; 
bool p[11];
void dfs(int x)
{
	if(x==n+1)
	{
		for(int i=1;i<=m;i++)
			if(num[i]%2!=p[i])return ;
		cnt++;
		return ;
	}
	dfs(x+1);
	for(int i=0;i<s[x].size();i++)
	{
		num[s[x][i]]++;
	}
	dfs(x+1);
	for(int i=0;i<s[x].size();i++)
	{
		num[s[x][i]]--;
	}
}

int main()
{
	cin >> n >> m;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin >> a;
		for(int j=1;j<=a;j++)
		{
			cin >> b;
			s[b].push_back(i);
		}
	}
	for(int i=1;i<=m;i++)
		cin >> p[i];
	dfs(1);
	cout << cnt;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long a, b;
	cin>>a>>b;
	long long r = a * b;
	if(r % 2 == 0){
		cout<<"Even"<<endl;
	}
	else{
		cout<<"Odd"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    private static int MOD = 1000000007;


    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String str = br.readLine();
        String[] split = str.split(" ");
        int n = Integer.parseInt(split[0]);
        int x = Integer.parseInt(split[1]);
        int y = Integer.parseInt(split[2]);

        Map<Integer, List<ISet>> map = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int dist = j - i; //別経路を通らない場合
                int s = another(i, j, x, y);
                //距離が短いほうを設定
                dist = s < dist ? s : dist;
                List<ISet> iSets = map.get(dist);
                if(iSets == null) {
                    iSets = new ArrayList<>();
                }
                iSets.add(new ISet(j, i));
                map.put(dist, iSets);
            }
        }


        for(int i = 1; i < n ; i++){
            List<ISet> iSets = map.get(i);
            if (iSets == null) {
                System.out.println(0);
                continue;
            }
            System.out.println(iSets.size());
        }
    }

    private static int another(int s, int e, int x, int y) {
        return Math.abs(x - s) + Math.abs(y - e) + 1;
    }


    static class ISet {
        int a;
        int b;

        public ISet(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public boolean contain(int x, int y) {
            return a <= x && y <= b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ISet iSet = (ISet) o;
            return a == iSet.a &&
                    b == iSet.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }

        @Override
        public String toString() {
            return "ISet{" +
                    "a=" + a +
                    ", b=" + b +
                    '}';
        }
    }

}


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

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pi;
typedef long long i64;

i64 sum(i64 num) {
  i64 res = 0;
  while(num) {
    res += num % 10;
    num /= 10;
  }
  return res;
}

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

  int k;
  cin >> k;
  cout << 1 << endl;

  i64 n = 1, d = 1;
  rep(i, 1, k) {
    if(sum(n + d) * (n + 10 * d) < sum(n + 10 * d) * (n + d)) d *= 10;
    n += d;
    cout << n << endl;
  }
}


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

using namespace std;

int main() {
  string s, t;
  cin >> s >> t;

  // dp[i][j] := sのi文字目, tのj文字目まで見たときの最長共通部分列(LCS)
  vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
  for (int i = 0; i < (int)s.size(); i++) {
    for (int j = 0; j < (int)t.size(); j++) {
      if (s[i] == t[j]) {
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]) + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j]);
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1]);
      }
    }
  }

  int i = s.size(), j = t.size();
  string ans = "";
  while (i > 0 && j > 0) {
    // dp[i-1][j] -> dp[i][j] と更新
    if (dp[i][j] == dp[i - 1][j]) {
      i--;
    } else if (dp[i][j] == dp[i][j - 1]) {
      j--;
    } else {
      ans = s[i - 1] + ans;
      i--;
      j--;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 35584
n, m = map(int, input().split())
list_score = set([int(input()) for _ in range(m)])

dp = [0] * (n + 1)
mod = pow(10, 9) + 7

dp[0] = 1
if 1 in list_score:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in list_score:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

print(dp[n])


Measured memory_bytes: 13192
from bisect import bisect_right

N = int(input())
L = list(map(int, input().split()))

L_sorted = sorted(L)

count = 0
for i in range(N):  # longest stick
    for j in range(i):  # second longest stick
        r = bisect_right(L_sorted, L_sorted[i] - L_sorted[j])
        count += max(0, j - r)

print(count)

Measured memory_bytes: 3316
import java.util.Scanner;

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

    long left=0, right=0, diff=0, res=2020202021;
    for(int i=0; i<N; i++) {
      left += A[i];
      right = sum - left;
      diff = Math.abs(left - right);
      if(diff < res) res = diff;
    }
    System.out.println(res);
  }
}


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

int main(){
  ll N;
  cin >> N;
  ll S,T;
  S=N/10;
  T=N-N/1000*1000;
  if(S%111==0 || T%111==0){
    cout << "Yes" << endl;
    return 0;
  }
  else{
    cout << "No" << endl;
    return 0;
  }
}

Measured memory_bytes: 3572
def resolve():
	s = input()
	if s[0] != 'A':
		print('WA')
		return
	cnt = False
	for i in s[2:-1]:
		if i == 'C':
			cnt += 1
	if cnt != 1:
		print('WA')
		return
	for i in s:
		if i == 'A' or i == 'C':
			continue
		if i.isupper():
			print('WA')
			return
	print('AC')
resolve()

Measured memory_bytes: 38256
A, B, M = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

min_a = min(a)
min_b = min(b)

min_ab = min_a + min_b

min_wari = 10000000

for i in range(M):
    x, y, c = map(int, input().split())
    cur = a[x-1] + b[y-1] - c
    if cur < min_wari:
        min_wari = cur

if min_ab > min_wari:
    print(min_wari)
else:
    print(min_ab)


Measured memory_bytes: 18736
use std::io::Read;

fn main() {
    let mut buff = String::new();
    std::io::stdin().read_to_string(&mut buff).unwrap();
    let mut iter = buff.split_whitespace();

    let n: usize = iter.next().unwrap().parse().unwrap();
    let mut a = Vec::new();

    for _i in 0..n {
        let x: i32 = iter.next().unwrap().parse().unwrap();
        a.push(x);
    }

    a.sort();
    println!("{}", a.last().unwrap() - a.first().unwrap());

    ()
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define MOD 1000000007

int main()
{
    int N; cin >>N;
    vi b(N); cin >> b;
    vi op;


    rep(i, N) {
        for (int j = b.size()-1; j >= 0; j--) {
            if (b[j] == j+1) {
                op.push_back(j+1);
                b.erase(b.begin()+j);
                break;
            }
        }
        if (op.size() != i+1) {
            cout << -1 << endl; return 0;
        }
    }

    reverse(all(op));
    rep(i, N) cout << op[i] << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma warning(disable:4996)
using namespace std;
const int N = 1e5 + 5;
int arr[N];
long long dp[N];
int main() {
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	dp[0] = 0;
	dp[1] = abs(arr[0] - arr[1]);
	for(int i = 2; i < n;i++){
		long long ans = INT_MAX;
		for(int j = 1; j <= k and (i - j) >= 0; j++){
			ans = min(ans, dp[i - j] + abs(arr[i] - arr[i - j]));
		}		
		dp[i] = ans;
	}
	
	cout << dp[n - 1];
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main () {
  string A, B;
  cin >> A >> B;
  A += B;
  if(stoi(A) == pow((int)sqrt(stoi(A)), 2))cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
def solve():
    def num2alpha(num):
        if num <= 26:
            return chr(64 + num)
        elif num % 26 == 0:
            return num2alpha(num // 26 - 1) + chr(90)
        else:
            return num2alpha(num // 26) + chr(64 + num % 26)
    print(num2alpha(N).lower())

if __name__ == "__main__":
    N = int(input())
    solve()

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

int main(){
    int n;
    while(cin>>n){
        if(!n) break;
        int a[n];
        for(int i=0; i<n; i++){
            cin >> a[i];
        }
        int mx=-99999999;
        for(int i=0; i<n; i++){
            int sum=0;
            for(int j=i; j<n; j++){
                if(mx < sum+a[j]) mx = sum+a[j];
                sum += a[j];
            }

        }
        cout << mx << endl;
    }

    return 0;
}

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

int main()
{
  int N;
  cin >> N;
  vector<int> di(N);
  for(int i = 0; i < N; i++)
    cin >> di.at(i);
  sort(di.begin(), di.end(), greater<int>());
  int pre = -1, count = 0;
  for(int i = 0; i < N; i++)
  {
    if(di.at(i) == pre)
      continue;
    pre = di.at(i);
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int k;cin >> k;
	string s;cin >> s;
	int sz = s.size();
	if(sz <= k) cout << s;
	else cout << s.substr(0,k) << "...\n";
}


Measured memory_bytes: 3652