akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using vec = vector<ll>;
using vect = vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i, n) for (ll i = 0; i < n; i++)
#define Loop(i, m, n) for (ll i = m; i < n; i++)
#define pool(i, n) for (ll i = n; i >= 0; i--)
#define Pool(i, m, n) for (ll i = n; i >= m; i--)
#define mod 1000000007ll
//#define mod 998244353ll
#define flagcount __builtin_popcount
#define flag(x) (1ll << x)
#define flagadd(bit, x) bit |= flag(x)
#define flagpop(bit, x) bit &= ~flag(x)
#define flagon(bit, i) bit &flag(i)
#define flagoff(bit, i) !(bit & (1ll << i))
#define all(v) v.begin(), v.end()
#define low2way(v, x) lower_bound(all(v), x)
#define high2way(v, x) upper_bound(all(v), x)
#define idx_lower(v, x) (distance(v.begin(), low2way(v, x)))  //配列vでx未満の要素数を返す
#define idx_upper(v, x) (distance(v.begin(), high2way(v, x))) //配列vでx以下の要素数を返す
#define idx_lower2(v, x) (v.size() - idx_lower(v, x))         //配列vでx以上の要素数を返す
#define idx_upper2(v, x) (v.size() - idx_upper(v, x))         //配列vでxより大きい要素の数を返す
#define putout(a) cout << a << endl
#define Sum(v) accumulate(all(v), 0ll)
#define gcd(x, y) __gcd(x, y)
ll ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return -1;
}
template <typename T>
T lcm(T x, T y)
{
    T z = gcd(x, y);
    return x * y / z;
}
template <typename T>
bool primejudge(T n)
{
    if (n < 2)
        return false;
    else if (n == 2)
        return true;
    else if (n % 2 == 0)
        return false;
    double sqrtn = sqrt(n);
    for (T i = 3; i < sqrtn + 1; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
        i++;
    }
    return true;
}
template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b; // aをbで更新
        return true;
    }
    return false;
}
template <typename T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b; // aをbで更新
        return true;
    }
    return false;
}
//場合によって使い分ける
//const ll dx[4]={1,0,-1,0};
//const ll dy[4]={0,1,0,-1};
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//2次元配列の宣言
//vector<vector<ll>> field(h, vector<ll>(w));

int main()
{
    cout << fixed << setprecision(30);
    ll N, L;
    cin >> N >> L;
    vec a(N);
    loop(i, N) cin >> a[i];
    string I = "Impossible", P = "Possible";
    ll maxx = 0;
    loop(i, N - 1) maxx = max(maxx, a[i] + a[i + 1]);
    if (maxx < L)
    {
        putout(I);
        return 0;
    }
    putout(P);
    ll x, y;
    loop(i, N - 1)
    {
        ll check = a[i] + a[i + 1];
        if (check == maxx)
        {
            x = i + 1;
            y = i + 2;
            break;
        }
    }
    loop(i, x - 1) putout(1 + i);
    loop(i, N - 2 - (x - 1)) putout(N - 1 - i);
    putout(x);
    return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define mp make_pair
#define INF 1e9

void init(){
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

int main(void){
    init();
    int n,m,x;
    cin>>n>>m>>x;
    vector<pair<int,vector<int>>>data;
    rep(i,n){
        int c;
        cin>>c;
        vector<int>a(m);
        rep(j,m){
            cin>>a[j];
        }
        data.push_back(mp(c,a));
    }

    int ans=INF;
    rep(tmp,(1<<n)){
        bitset<20> bit_d(tmp);
        int C = 0;
        vector<int>A(m);
        rep(i,n){
            if(bit_d.test(i)==true){
                C+=data[i].first;
                rep(j,m){
                    A[j]+=data[i].second[j];
                }
            }
        }
        int flag = 1;
        rep(j,m){
            if(A[j]<x)flag=0;
        }
        if(flag==1&&ans>C){
            ans=C;
        }
    }
    if(ans!=INF){
        cout<<ans<<endl;
    }else{
        cout<<"-1"<<endl;
    }
}


Measured memory_bytes: 3612
import math
import itertools
import statistics
#import collections

n, h = list(map(int, input().split()))
a = [] #降る
b = [] #投げる

for i in range(n):
    x,y = [int(j) for j in input().split()]
    a.append(x)
    b.append(y)


b2 = sorted(b, reverse=True)
total = 0
a_max = max(a)

#投げた方が強いやつを全部投げた
for i in range(n):
    if b2[i] >= a_max:
        total += b2[i]
        if total >= h:
            print(i+1)
            exit()


"""
#全部投げた場合
for i in range(n):
    total += b2[i]
    if total >= h:
        print(i+1)
        exit()
"""


count = 0
remain_hp = h

#振るより投げた方がいいやつを投げる
for i in range(n):
    if b[i] >= a_max:
        remain_hp -= b[i]
        count +=1
#振って一番削れるのでやる
count += math.ceil(remain_hp/a_max)
print(count)





Measured memory_bytes: 14200
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
  long long x;
  cin>>x;
  for(int i=sqrt(x);i;i--)
    if(x%i==0)
    {
      cout<<i+x/i-2<<endl;
      return 0;
    }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <climits>

#define mod 1000000007
#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)

using namespace std;
using ll = long long;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

void solve() {
    ll min = 2, max = 2;
    int k;
    cin >> k;
    ll a[k];
    REP(i, k) cin >> a[i];

    for(int i = k-1; i >= 0; i--){
        min = ((min+a[i]-1)/a[i])*a[i];
        max = (max/a[i])*a[i] + (a[i]-1);
        if(min > max){
            cout << "-1" << endl;
            return;
        }
    }
    cout << min << " " << max << endl;
}

int main(){
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define br cout << "\n";
#define pb push_back
#define ll long long 
#define ff first 
#define ss second
#define all(x) x.begin(),x.end()
#define in(a , idx , n ) for (int i = idx ; i < n ; ++i)cin >>a[i];
using namespace std;
const int MOD = 1000*1000*1000 + 7 ; 
const int MAXN = 1000*100 +10 ;
void solve(){
	int n , k ;
	cin >> n  >> k ;
	vector<int>h(n+1); 
	for(int i =  1 ; i <= n ; ++i  )
		cin >> h[i] ;
	int dp[n + 1 ];
	for (int i = 0 ; i <= n ; ++i )
		dp[i] = INT_MAX;
	dp[1] = 0 ;
	for(int i = 1 ; i <= n ; ++i )
	{
		for(int j =  1 ; j <= k ; ++j )
		{
			if( i-j <= 0 )continue ;
			
			dp[i] = min( dp[ i ], dp[i-j] + abs( h[i-j] - h[i]));  
			 
		}
	}
	cout << dp[n];
	
}
int main (){ 
	int t = 1  ;
	// cin >> t ;
	while (t--){
		solve() ; 
	}
    
return 0 ; 
}


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

const int coin[4] = {10,50,100,500};
int cost,ans,a[4];
int ans_coin[4];

int check(int total){
  int res = 0;

  for(int i = 3 ; i >= 0 ; i--){
    res += total / coin[i];
    total %= coin[i];
  }

  return res;
}

void judge(){
  int ans = 1<<28;
  
  for(int i = 0 ; i <= a[0] ; i++){
    for(int j = 0 ; j <= a[1] ; j++){
      for(int k = 0 ; k <= a[2] ; k++){
	for(int l = 0 ; l <= a[3] ; l++){

	  int sum = coin[0]*i+coin[1]*j+coin[2]*k+coin[3]*l;
	  if(sum < cost) continue;

	  int want = sum - cost;
	  int tmp = check(want) - (i + j + k + l);

	  if(tmp < ans){
	    ans_coin[0] = i; ans_coin[1] = j;
	    ans_coin[2] = k; ans_coin[3] = l;
	    ans = tmp;
	  }

	}
      }
    }
  }

}

int main(){  
  bool flg = false;
  while(cin >> cost ,cost){
    if(flg) cout << endl;
    for(int i = 0 ; i < 4 ; i++) cin >> a[i];
    judge();
    for(int i = 0 ; i < 4 ; i++){
      if(ans_coin[i]){
	cout << coin[i] << " " << ans_coin[i] << endl;
      }
    }
    flg = true;
  }

  return 0;
}

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

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

int main() {
  long long x, k, d;
  cin >> x >> k >> d;

  long long cur = abs(x);
  long long rem = k;
  long long cnt = min(cur / d, k);

  cur -= d * cnt;
  rem -= cnt;

  if (rem > 0) {
    if (rem % 2 == 1) {
      cur = cur - d;
    }
  }

  cout << abs(cur) << endl;

  return 0;
}

Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>

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

using namespace std;

int main(){
    int n,a,b,c; cin >> n >> a >> b >> c;
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    long long min = 1 << 30;
    for(int bit = 0; bit < pow(2,2*n);bit++) {
        int x = bit;
        int aa = 0;
        int bb = 0;
        int cc = 0;
        long long mp = 0;
        for(int i = 0; i < n; i++) {
            if((x & 3) == 1){
                if(aa != 0)
                    mp += 10;
                aa += l[i];
            }
            if((x & 3) == 2){
                if(bb != 0)
                    mp += 10;
                bb += l[i];
            }
            if((x & 3) == 3){
                if(cc != 0)
                    mp += 10;
                cc += l[i];
            }
            x >>= 2;
        }
        if(aa == 0 || bb == 0 || cc == 0)
            continue;
        mp += abs(a-aa) + abs(b-bb) + abs(c-cc);
        // cout << bit << " " << mp << endl;
        if(min > mp)
            min = mp;
    }
    cout << min << endl;
}



Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
int main(void){
    int a,b,c,d,start,end ;
    scanf("%d%d%d%d",&a,&b,&c,&d) ;
    if (a<c) {
        start=c ;
    } else {
        start=a ;
    }
    if (b<d) {
        end=b ;
    } else {
        end=d ;
    }
    if (start<end){
        printf ("%d\n",end-start) ;
    } else {
        printf ("0\n") ;
    }
    return 0 ;    
}

Measured memory_bytes: 128
function Main(input) {
  input=input.split("\n");
  
  const N=input[0]-0;
  const A=input[1].split(' ')[0]-0;
  const B=input[1].split(' ')[1]-0;
  for(var i=A;i<=B;i++){
    if(i%N==0){
      console.log('OK');
      return;
    }
  }
  console.log('NG');
}


//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  
  


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

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

    int ans = 0;

    string str = std::to_string(n);
    for(int i = 0; i < str.length(); i++) {
        ans += (int)(str[i] - '0');
    }

    if(n % ans == 0) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
a_spot = a + (v*t)
b_spot = b + (w*t)
A_spot = a - (v*t)
B_spot = b - (w*t)
if a <= b:
    
    if a_spot >= b_spot:
        print("YES")
    else:
        print("NO")
        
else:
    if  A_spot <= B_spot:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 9200
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define int long long
#define inf 1000000007
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef pair<int,int>  P;
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
signed main(){
    int a,b,c,k;cin>>a>>b>>c>>k;
    int maxi=max({a,b,c});
    int ans=a+b+c-maxi;
    rep(i,0,k)maxi*=2;
    cout<<ans+maxi<<endl;
    return 0;
}


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

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;

const int N = 1e5 + 5;
int fact[N], a[N], n, k;

int mul(const int& a, const int& b) {
  return int(1LL * a * b % (1LL * mod));
}

int add(const int& a, const int& b) {
  return (a % mod + b % mod) % mod;
}

int power(int x, int y) {
  if (y == 0)
    return 1;
  if (y == 1)
    return x;
  int tmp = power(x, y / 2);
  tmp = mul(tmp, tmp);
  if (y & 1)
    tmp = mul(tmp, x);
  return tmp;
}

int inv(int x) {
  return power(x, mod - 2);
}

void init() {
  fact[0] = 1;
  for (int i = 1; i < N; ++i)
    fact[i] = mul(fact[i - 1], i);
}

int nCr(int n, int r) {
  if (r > n)
    return 0;
  return mul(mul(fact[n], inv(fact[r])), inv(fact[n - r]));
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  init();
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  sort(a + 1, a + 1 + n);
  int s1 = 0, s2 = 0;
  for (int i = k, sum = 0, t = k - 2; i <= n; ++i) {
    sum = add(sum, nCr(t, k - 2));
    s1 = add(s1, mul(a[i], sum));
    t++;
  }
  for (int i = n - k + 1, sum = 0, t = k - 2; i >= 1; --i) {
    sum = add(sum, nCr(t, k - 2));
    s2 = add(s2, mul(a[i], sum));
    t++;
  }
  s2 = ((0 - s2) % mod + mod) % mod;
  cout << add(s1, s2);
  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf = 1e18;

int N;
const int MAX=3e4;
int P[MAX];
int a[MAX],b[MAX];
int main(){
    cin>>N;

    REP(i, 1, N+1) cin>>P[i];


    REP(i, 1, N+1){
        a[i]=i*MAX;
        b[i]=(N+1-i)*MAX;
    }
    REP(i, 1, N+1)a[P[i]]+=i;
    REP(i, 1, N+1) cout<<a[i]<<" ";
    cout<<endl;
    REP(i, 1, N+1) cout<<b[i]<<" ";
    cout<<endl;
    return 0;
}

Measured memory_bytes: 896
import math
import numpy as np

# n, m = 4,4
# a_list = np.array([1,9,3,5])

n,m = map(int, input().split())
a_list = np.array(list(map(int, input().split())))

a_list = np.sort(a_list)

a_logs = np.log2(a_list).astype('int64')

max_num = max(a_logs)
num = max_num*1

count_num = 0
flag = True
while(flag):
    count_num_temp = sum(a_logs>=num) + count_num
    if(count_num_temp > m):
        flag = False
        remain = m - count_num
    else:
        count_num = count_num_temp
        num -= 1
        if(num == -1):
            print('0')
            exit()

a_list = a_list // 2**((a_logs > num) * (a_logs - num))

if(remain > 0):
    a_list = np.sort(a_list)
    a_list[(n-remain):] = a_list[(n-remain):] //2

ans = sum(a_list)
print(ans)


Measured memory_bytes: 23132
#include <stdio.h>
#include <string.h>
 
#define MAXLINE 1000
#define CMD_LEN 9
 
void
flip(char *, int, int);
 
void
pri(char *, int);
 
int
main(void)
{
    char str[MAXLINE + 1];
    char rep[MAXLINE + 1];
    char cmd[CMD_LEN];
    int cmdCnt, param1, param2;
    scanf("%s", str);
    for (scanf("%d", &cmdCnt); cmdCnt > 0; cmdCnt--) {
        scanf("%s %d %d", cmd, &param1, &param2);
        if (!strcmp(cmd, "reverse"))
            flip(str, param1, param2);
        else if (!strcmp(cmd, "replace")) {
            scanf("%s", rep);
            strncpy(str + param1, rep, strlen(rep));
        } else if (!strcmp(cmd, "print"))
            pri(str + param1, param2 - param1);
    }
 
    return 0;
}
 
void
flip(char *str, int st, int end)
{
    char tmp;
    for ( ; st < end; st++, end--) {
        tmp = str[st];
        str[st] = str[end];
        str[end] = tmp;
    }
}
 
void
pri(char *str, int l)
{
    int i;
    for (i = 0; i <= l; i++)
        putchar(str[i]);
    putchar('\n');
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

//-----------------------------------------------------


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,a,b;
  cin >> n >> a >> b;
  cout << min(a*n,b) << endl;
  
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(void) {
    unsigned long int coin;
    std::cin >> coin;
    unsigned int yen500;
    unsigned int yen5;

    yen500 = coin/500;
    coin -= yen500*500;
    yen5 = (unsigned int)coin/5;
    std::cout << yen500*1000+yen5*5 << std::endl;

    return 0;
}


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

typedef int SEGNODE_TYPE;

class Segtree
{
    public:
 
    SEGNODE_TYPE monoid;
    int segsize;    // セグ木の大きさ
    vector<SEGNODE_TYPE> value;
 
    // [引数]
    //          int n                   : 大きさ
    //          SEGNODE_TYPE start      : 初期値
    //          SEGNODE_TYPE mnd        : 単位元（モノイド）
    // [動作]
    //          セグ木を作る
    // ※SEGNODE_TYPE の定義を忘れずに
    Segtree() {}
    Segtree(int n, SEGNODE_TYPE start, SEGNODE_TYPE mnd) {    
        segsize = 1;
        while(segsize < n){
            segsize = segsize * 2;
        }
   
        value = vector<SEGNODE_TYPE>(2 * segsize - 1, start);
        monoid = mnd;
    }      
 
    // [引数]
    //          int i           : 変更箇所
    //          SEGNODE_TYPE x  : 変更値
    // [動作]
    //          場所iをxに変更
    void UpDate(int i, SEGNODE_TYPE x) {
        i += segsize - 1;
        value[i] = x;
   
        while(i > 0){
            i = (i-1) / 2;
            value[i] = Requirement(value[i * 2 + 1], value[i * 2 + 2]);
        }
 
        return;
    }
 
    // [引数]
    //          int a   : 区間の左端
    //          int b   : 区間の右端
    // [動作]
    //          区間[a, b)のクエリを処理する（SegQueryへ橋渡し）
    // ※呼び出す際にはSEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y)の中身を確認
    SEGNODE_TYPE Query(int a, int b) {
        return ( SegQuery(a, b+1, 0, 0, segsize) );
    }
 
    // [引数]
    //          int a    : クエリの範囲の左端
    //          int b    : クエリの範囲の右端
    //          int k    : 今いるノードの場所
    //          int l    : 今いるノードの参照範囲の左端
    //          int r    : 今いるノードの参照範囲の右端
    // [動作]
    //          区間[a, b)のクエリを求める
    SEGNODE_TYPE SegQuery(int a, int b, int k, int l, int r) {
        // [a, b)の区間に対するクエリについて、ノードk(区間[l, r)担当)が答える
        if(r <= a || b <= l) {
            return (monoid);
        }
        if(a <= l && r <= b){
            // ノードkの担当クエリ区間[a ,b)に完全に含まれる
            return (value[k]);
        }
        else {
            // 左右の子に尋ねる
            SEGNODE_TYPE c1 = SegQuery(a, b, 2*k+1, l, (l+r)/2);    // 左の子（状況に合わせて型を変える）
            SEGNODE_TYPE c2 = SegQuery(a, b, 2*k+2, (l+r)/2, r);    // 右の子（状況に合わせて型を変える）
     
            return ( Requirement(c1, c2) ); // 左右の子から求めたいものを返す
        }        
    }
 
    // 求めたいもの（最小値ならmin(x, y)、最大値ならmax(x, y)、合計値なら(x + y)など）
    // ※ここのreturn文は用途に合わせて書き換える必要がある
    SEGNODE_TYPE Requirement(SEGNODE_TYPE x, SEGNODE_TYPE y) {
        return ( max(x, y) );
    }
 
    // [引数]
    //          int i   : 場所
    // [動作]
    //          左からi番目の値を変えす
    SEGNODE_TYPE GetReaf(int i) {
        return( value[i + segsize - 1] );
    }
};


int main() {
    SEGNODE_TYPE sum;
    int n, k, a, ans;
    ans = 1;
    
    Segtree tree = Segtree(300001, 0, 0);
    cin >> n >> k;
    for ( int i = 0; i < n; i++ ) {
        cin >> a;   
        
        sum = tree.Query(max(0, a-k), min(300000, a+k));
        ans = max(ans, sum+1);
        
        tree.UpDate(a, sum+1);
    }
    
    cout << ans << endl;
    return (0);
}

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

int main() {
  long long N; cin >> N;
  long long A[N]; for (int i = 0; i < N; i++) cin >> A[i];
  
  if (N % 2 == 0){
    long long dp[N][2]; for (int i = 0; i < N; i++) dp[i][0] = dp[i][1] = -10000000000000000;
    for (long long i = 0; i < N; i++){
      if (i == 0) dp[i][0] = A[i];
      else if (i == 1) {
        if (i == N - 1) dp[i][0] = dp[i - 1][0];
        dp[i][1] = A[i];
      }
      else {
        if (i >= 2) dp[i][0] = dp[i - 2][0] + A[i];
        if (i == N - 1) dp[i][0] = dp[i - 1][0];
        if (i >= 3) dp[i][1] = dp[i - 3][0] + A[i];
        if (i >= 2) dp[i][1] = max(dp[i][1], dp[i - 2][1] + A[i]);
      }
    }
    cout << max(dp[N - 1][0], dp[N - 1][1]) << endl;
  }
  else {
    long long dp[N][3]; 
    for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) dp[i][j] = -10000000000000000;
    for (long long i = 0; i < N; i++){
      if (i == 0) dp[i][0] = A[i];
      else if (i == 1) dp[i][1] = A[i];
      else if (i == 2) {
        dp[i][2] = A[i];
        if (i <= N - 2) dp[i][0] = dp[i - 2][0] + A[i];
        else dp[i][0] = dp[i - 2][0];
        if (i == N - 1) dp[i][1] = dp[i - 1][1];
      }
      else {
        if (i >= 2 && i <= N - 3) dp[i][0] = dp[i - 2][0] + A[i];
        if (i >= N - 2) dp[i][0] = dp[i - 2][0];
        if (i >= 3) dp[i][1] = dp[i - 3][0] + A[i];
        if (i >= 2) dp[i][1] = max(dp[i][1], dp[i - 2][1] + A[i]);
        if (i == N - 1) dp[i][1] = max(dp[i][1], dp[i - 1][1]);
        if (i >= 4) dp[i][2] = dp[i - 4][0] + A[i];
        if (i >= 3) dp[i][2] = max(dp[i][2], dp[i - 3][1] + A[i]);
        if (i >= 2) dp[i][2] = max(dp[i][2], dp[i - 2][2] + A[i]);
      }
    }
    cout << max(max(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]) << endl;
  }
}

Measured memory_bytes: 9880
//from PKU1125
#define M 201
double dist[M][M],d;
next[M][M],x[M],y[M];
main(){
	int a,b,k,n,i,j;
	for(;scanf("%d",&n),n;){
		/*initialize*/
		for(i=1;i<=n;i++)scanf("%d",&a),scanf("%d%d",x+a,y+a);
		for(i=1;i<=n;i++)for(j=1;j<=n;next[i][j]=j,j++)
			dist[i][j]=(d=hypot(x[i]-x[j],y[i]-y[j]))<50.1?d:999;

		{/*warshall-floyd*/
			int k,i,j;
			for(k=1;k<=n;k++)
				for(i=1;i<=n;i++)
					for(j=1;j<=n;j++){
						if(dist[i][j]>dist[i][k]+dist[k][j])
							dist[i][j]=dist[i][k]+dist[k][j],next[i][j]=next[i][k];
					}
		}

		{/*query*/
			for(scanf("%d",&k);k;k--){
				scanf("%d%d",&a,&b);
				if(dist[a][b]>998)puts("NA");
				else{
					for(j=a;j!=b;j=next[j][b])printf("%d ",j);
					printf("%d\n",b);
				}
			}
		}
	}exit(0);
}

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

typedef long long ll;
#define pb push_back

// int gcd(int a, int b) {   if (b == 0) return a; return gcd(b, a % b);  }
// int lcm(int a,int b){return a/gcd(a,b)*b;}

int main(){
    int x;
    cin>>x;
    if(x>=30) cout<<"Yes";
    else cout<<"No";
    return 0;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}


int N,K;
int table[1005][1005];

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> N >> K;
  rep(i,N){
    int x,y;cin >> x >> y;
    char c; cin >> c;
    x%=2*K;
    y%=2*K;
    int black = 1;
    if(c=='W')black^=1;
    if(x>=K)black^=1;
    if(y>=K)black^=1;
    x%=K;
    y%=K;
    table[1][1]+=black;
    if(!black)black=-1;
    table[1][y+2]-=black;
    table[x+2][1]-=black;
    table[x+2][y+2]+=2*black;
  }
  int ans = 0;
  rep(x,K)rep(y,K){
    table[x+1][y+1] += table[x+1][y] + table[x][y+1] - table[x][y];
    ans = max(ans, max(table[x+1][y+1], N-table[x+1][y+1]));
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 4224
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<numeric>
#include<algorithm>
#include<string>
#include<map>
#include<bitset>
#include<set>
#include<cmath>
#define int long long
const int inf=8938103643641919514ll;
const int mod=1000000007ll;
const int dd[]={0,-1,0,1,0};
using namespace std;
class mod_int{
public:
	int x;
	mod_int():x(0){}
	mod_int(int u):x(u){}
	mod_int operator=(int u){
		x=u;
		return *this;
	}
	mod_int operator+=(mod_int y){
		x+=y.x;
		x=x>=mod?x-mod:x;
		return *this;
	}
	mod_int operator-=(mod_int y){
		x-=y.x;
		x=x<0?x+mod:x;
		return *this;
	}
	mod_int operator*=(mod_int y){
		x*=y.x;
		x%=mod;
		return *this;
	}
	mod_int operator/=(mod_int y){
		mod_int z=1;
		for(int u=1;u<=mod-2;u<<=1){
			if((mod-2)&u)
				z*=y;
			y*=y;
		}
		operator*=(z);
		return *this;
	}
};
mod_int operator+(mod_int x,mod_int y){
	return x+=y;
}
mod_int operator-(mod_int x,mod_int y){
	return x-=y;
}
mod_int operator*(mod_int x,mod_int y){
	return x*=y;
}
mod_int operator/(mod_int x,mod_int y){
	return x/=y;
}
ostream& operator<<(ostream &os,mod_int x){
	return os<<x.x;
}
const int aaa=300000;
mod_int ttt[aaa];
static class aaaaaaaaaaaaaaaa{
public:
	aaaaaaaaaaaaaaaa(){
		ttt[0]=1;
		mod_int x=1;
		for(int i=1;i<aaa;i++){
			ttt[i]=x*=i;
		}
	}
} aaaaaaaaaaaaaaaaaaaaaaaaa;
mod_int combi(int u,int v){
	if(u<aaa){
		return ttt[u]/(ttt[v]*ttt[u-v]);
	}
	mod_int x=1,y=1;
	for(int w=0;w<u-v;w++){
		x*=u-w;
		y*=w+1;
	}
	return x/y;
}
mod_int catal(int u){
	if(u==0)
		return 1;
	return combi(u*2,u)-combi(u*2,u-1);
}
struct A{
	int w;
	vector<int> e;
};
using bbb=int;
bbb p[100000];
int saiki(int oya,int u){
}
signed main(){
	int a,b,c,d,e,f,g,n,m;
	int i,j,k;
	cin>>n>>m>>k;
	mod_int ans=0;
	for(i=0;i<=k;i++){
		int x=i,y=k-i;
		auto u=combi(n+m+k*2,n+x*2);
		auto v=combi(n+x*2,x);
		if(x>0)
			v-=combi(n+x*2,x-1);
		u*=v;
		v=combi(m+y*2,y);
		if(y>0)
			v-=combi(m+y*2,y-1);
		u*=v;
		ans+=u;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 5472
n,m = map(int,input().split())



def fun():
    if int(m/2) == m/2:
        ans = n*m/2
    else:
        if int(n/2)==n/2:
            ans = n*m/2
        else:
            ans = (n*m/2)+0.5
    
    print(int(ans))  
    
if n == 1 or m ==1:
    print("1")
else:
    fun()

Measured memory_bytes: 38512
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, k, s; cin >> n >> k >> s;
    ll big = 1e9;
    
    rep(i, k){
        cout << s << " ";
    }
    if(s != big){
        reps(i, k, n){
            cout << big << " ";
        }
    }
    else{
        reps(i, k, n){
            cout << 1 << " ";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1280
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double H = sc.nextDouble();
        double W =sc.nextDouble();
        double N = sc.nextDouble();

        double ans;

        if(H <= W){
           ans = Math.ceil(N/W);
        }else{
            ans = Math.ceil(N/H);
        }

        System.out.println((int)ans);

    }
}



Measured memory_bytes: 23508
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=1000000;
const ll inf=1e9;
const ll mod=998244353;


int a[MX];

int main()
{

    FasterIO;

    int n, m, x;

    cin>>n>>x;
    m=2*n-1;

    if(x==1 || x==m)
    {
        cout<<"No"<<endl; return 0;
    }

    cout<<"Yes"<<endl;

    a[n]=x;
    for(int i=n+1; i<=m; i++) x=x%m+1, a[i]=x;

    for(int i=1; i<n; i++) x=x%m+1, a[i]=x;

    for(int i=1; i<=m; i++) cout<<a[i]<<endl;

    return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

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

  int a, b, m;
  cin >> a >> b >> m;
  vi v(a), vv(b);
  int L = mod, M = mod;
  for(int i = 0; i < a; i++){
    cin >> v[i];
    L = min(L, v[i]);
  }
  for(int i = 0; i < b; i++){
    cin >> vv[i];
    M = min(M, vv[i]);
  }
  int res = L + M;
  for(int i = 0; i < m; i++){
    int x, y, c;
    cin >> x >> y >> c;
    //cout << x - 1 << " " << y - 1 << endl;
    int rez = v[x - 1] + vv[y - 1] - c;
    res = min(res, rez);
  }
  cout << res;
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
const int inf = 1000000001;
const ll INF = 2e18;
const ll MOD = 1000000007;
const ll mod = 1000000009;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

const int N = 100010;
vector<vector<pll> > G(N);
vi treesize(N);
ll ans = 0;
int n;


class CentroidDecomposition {
public:
	int n; //頂点数
	vii G; //グラフの隣接リスト表現
	vector<bool> isused; //その頂点がすでに分割に使われているか
	vi subtreesize; //部分木のサイズ,更新される
	vi parent;
	vi centroid; //重心が後ろに追加されていく
	vector<char> ans;

	CentroidDecomposition(int n) : n(n) {
		G.resize(n); isused.resize(n);
		subtreesize.resize(n); parent.resize(n);
		ans.resize(n);
	}

	void add_edge(int u, int v) {
		G[u].push_back(v); G[v].push_back(u);
	}

	int search_centroid(int now, int par, int size) {
		subtreesize[now] = 1;
		parent[now] = par;
		bool iscentroid = true;
		for (int i = 0; i < G[now].size(); i++) {
			int child = G[now][i];
			if (child == par) continue;
			if (isused[child]) continue;
			int child_size = search_centroid(child, now, size);
			if (child_size > size / 2) iscentroid = false;
			subtreesize[now] += child_size;
		}
		if (size - subtreesize[now] > size / 2) {
			iscentroid = false;
		}
		if (iscentroid) {
			centroid.push_back(now);
		}
		return subtreesize[now];
	}


};

int fillsize(int now, int parent) {
	int cnt = 1;
	rep(i, G[now].size()) {
		if (G[now][i].first == parent) {
			continue;
		}
		cnt += fillsize(G[now][i].first, now);
	}
	treesize[now] = cnt;
	return cnt;
}

void calc(int now, int parent) {
	rep(i, G[now].size()) {
		if (G[now][i].first == parent) {
			continue;
		}
		ans += 2 * min(treesize[G[now][i].first], n - treesize[G[now][i].first]) * G[now][i].second;
		calc(G[now][i].first, now);
	}
}

int main() {
	cin >> n;
	CentroidDecomposition tree(n);
	rep(i, n - 1) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		G[a].push_back(pll(b, c));
		G[b].push_back(pll(a, c));
		tree.add_edge(a, b);
	}
	fillsize(0, -1);
	calc(0, -1);
	tree.search_centroid(0, -1, n);
	if (tree.centroid.size() == 2) {
		int u = tree.centroid[0], v = tree.centroid[1];
		rep(i, G[u].size()) {
			if (G[u][i].first == v) {
				ans -= G[u][i].second;
			}
		}
	}
	else {
		ll mi = INF;
		int u = tree.centroid[0];
		rep(i, G[u].size()) {
			mi = min(mi, G[u][i].second);
		}
		ans -= mi;
	}
	cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define debug(a) cout << #a << ": " << a << endl;

int main() {
  int N;
  cin >> N;
  vector<int> a(N + 1, 0);
  rep(i, N) { cin >> a[i + 1]; }

  vector<int> box(N + 1, 0);
  for (int i = N; i > 0; i--) {
    int cnt = 0;
    for (int j = i; j <= N; j += i) {
      cnt += box[j];
    }
    if ((cnt % 2) != a[i]) {
      box[i] = 1;
    }
  }

  cout << count(box.begin(), box.end(), 1) << endl;
  for (int i = 1; i <= N; i++) {
    if (box[i] == 1) {
      cout << i << " ";
    }
  }
  cout << endl;
}


Measured memory_bytes: 2432
class Dice():
    #0:上面、1:前面、2:側面(見える方)、3:側面(裏側)、4:背面、5:底面
    def __init__(self,numlist):
        self.lst=numlist
    
    def roll(self,direction):
        for x in direction:
            if x=="S" : self.lst=[self.lst[4],self.lst[0],self.lst[2],self.lst[3],self.lst[5],self.lst[1]]
            elif x=="N" : self.lst=[self.lst[1],self.lst[5],self.lst[2],self.lst[3],self.lst[0],self.lst[4]]
            elif x=="W" : self.lst=[self.lst[2],self.lst[1],self.lst[5],self.lst[0],self.lst[4],self.lst[3]]
            elif x=="E" : self.lst=[self.lst[3],self.lst[1],self.lst[0],self.lst[5],self.lst[4],self.lst[2]]        
    
    def dice_set_make(self):
        self.dice_set=[]
        for x in ["","W","WW","WWW","SE","SW"]:
            self.work=Dice(self.lst[:])
            self.work.roll(x)
            self.dice_set.append(self.work.lst)
            for _ in range(3):
                self.work.roll("S")
                self.dice_set.append(self.work.lst)
        

lst=list(map(int,input().split()))
q=int(input())

d1=Dice(lst)
d1.dice_set_make()
dice_set=d1.dice_set

for _ in range(q):
    a,b=map(int,input().split())
    for x in dice_set:
        if x[0]==a and x[1]==b:
            print(x[2])
            break


Measured memory_bytes: 5604
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int n;
int[] a;

int dfs(int depth, bool gu)
{
  if (depth == n) {
    return gu;
  }
  int cnt = 0;
  for (int i = -1; i <= 1; ++i) {
    cnt += dfs(depth + 1, gu || ((a[depth] + i) % 2 == 0));
  }
  return cnt;
}

void main()
{
  n = readln.chomp.to!int;
  a = readln.chomp.split.map!(to!int).array;
  writeln = dfs(0, false);
}


Measured memory_bytes: 256
pub fn read_parameters<T>() -> Result<Vec<T>, String>
where
    T: std::str::FromStr,
{
    let mut line = String::new();
    std::io::stdin()
        .read_line(&mut line)
        .map_err(|err| format!("{:?}", err))?;

    let xs = line.trim().split_whitespace();
    let mut result = Vec::new();

    for x in xs {
        let ans = x.parse::<T>().map_err(|_| format!("{}", "parse error"))?;
        result.push(ans);
    }
    Ok(result)
}

fn main() {
    loop {
        let (h, w) = read_parameters::<usize>().map(|xs| (xs[0], xs[1])).unwrap();
        if h == 0 && w == 0 {
            break;
        }

        let mut top = String::new();
        for _ in 0..w {
            top = top + "#";
        }
        let mut side = "#".to_string();
        for _ in 0..(w - 2) {
            side = side + ".";
        }
        side = side + "#";

        println!("{}", top);
        for _ in 0..(h - 2) {
            println!("{}", side);
        }
        println!("{}\n", top);
    }
}



Measured memory_bytes: 5040
from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
c = list(map(int,input().split()))
c.sort(reverse=True)
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
que = deque([root])
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
while que:
  x = que.popleft()
  order.append(x)
  for y in graph[x]:
    if parent[x] == y:
      continue
    parent[y] = x
    que.append(y)
ans = []
for i in range(n):
  ans.append((order[i],c[i]))
ans.sort()
print(sum(c[1:]))
for i in ans:
  print(i[1],end=" ")

Measured memory_bytes: 53336
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 1000000007
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<complex<double>>  DFT(vector<complex<double>> a) {
	int n = a.size();
	if (n == 1) return a;
	vector<complex<double>> a0(n / 2), a1(n / 2);
	REP(i, n) {
		if (i % 2 == 0) {
			a0[i / 2] = a[i];
		}
		else {
			a1[i / 2] = a[i];
		}
	}
	vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1);
	vector<complex<double>> inversed_a(n);
	for (int i = 0; i < n; ++i) {
		complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n));
		inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)];
	}
	return inversed_a;
}
vector<complex<double>> IDFT(vector<complex<double>> inversed_a) {
	int n = inversed_a.size();
	vector<complex<double>> now = DFT(inversed_a);
	reverse(now.begin(), now.end());
	for (int q = now.size() - 1; q >= 1; --q) {
		swap(now[q], now[q - 1]);
	}
	REP(i, n) {
		now[i] /= complex<double>(n, 0);
	}
	return now;
}
vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) {
	int deg = a.size() + b.size() - 1;
	int n = 1;
	while (n < deg) n <<= 1;
	a.resize(n);
	b.resize(n);
	vector<complex<double>> inversed_a = DFT(a), inversed_b = DFT(b);
	vector<complex<double>> inversed_c(n);
	REP(i, n) {
		inversed_c[i] = inversed_a[i] * inversed_b[i];
	}
	return IDFT(inversed_c);
}
long long powing(long long now, long long hoge) {
	long long ans = 1;
	while (hoge != 0) {
		if (hoge % 2 == 1) {
			ans *= now;
			ans %= MOD;
		}
		hoge /= 2;
		now *= now;
		now %= MOD;
	}
	return ans;
}
long long inv(long long now) {
	return powing(now, MAX_MOD - 2LL);
}
unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned long t = (x^(x << 11));
	x = y; y = z; z = w;
	return (w = (w^(w >> 19))^(t^(t >> 8)));
}
int main() {
	int n;
	cin >> n;
	vector<long long> inputs;
	REP(i, n) {
		long long a;
		cin >> a;
		inputs.push_back(a);
	}
	int cnt = 0;
	REP(i, n) {
		if (i + 1 != inputs[i])cnt++;
	}
	if (cnt <= 2) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#define mod 1000000007
using namespace std;

int main(){
    int h,w;
    cin>>h>>w;
    char grid[h+1][w+1];
    int dp[h+1][w+1];
    for (size_t i = 0 ; i <= h; i++) {
        grid[i][0] = '.';
        dp[i][0] = 0;
    }
    for (size_t i = 0 ; i <= w; i++) {
        grid[0][i] = '.';
        dp[0][i] = 0;
    }
    dp[1][0] = 1;
    for (size_t i = 1 ; i <= h; i++) {
        for (size_t j = 1 ; j <= w; j++) {
            cin>>grid[i][j];
        }
    }
    for (size_t i = 1 ; i <= h; i++) {
        for (size_t j = 1 ; j <= w; j++) {
            if (grid[i][j] == '.') {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
            } else dp[i][j] = 0;
        }
    }
    std::cout << dp[h][w] << endl;
}


Measured memory_bytes: 8536
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
ABC = [LI() for _ in range(N)]


def main():
    dp = [[0] * 3 for _ in range(N + 1)]
    for i in range(1, N + 1):
        a, b, c = ABC[i - 1]
        dp[i][0] = a + max(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = b + max(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = c + max(dp[i - 1][0], dp[i - 1][1])
    ans = max(dp[-1])
    print(ans)



if __name__ == "__main__":
    main()


Measured memory_bytes: 50116
#include <iostream>

using namespace std;

typedef long long int ll;

const unsigned int TWO = 2097153, N = 22, MOD = 1e9 + 7;

unsigned int dp[N][TWO];
int n, compatible[N][N];

unsigned int countWays(int currMan, ll usedWomen, int menCount, int womenCount) {
  if (menCount == n && womenCount == n)
    return 1;
  if (menCount == n || womenCount == n)
    return 0;

  if (dp[currMan][usedWomen] != -1)
    return dp[currMan][usedWomen];

  dp[currMan][usedWomen] = 0;

  for (int i = 0; i < n; i++)
    if (compatible[currMan][i] && !(usedWomen & (1 << i)))
      dp[currMan][usedWomen] += countWays(currMan+1, usedWomen | (1 << i), menCount+1, womenCount+1) % MOD, dp[currMan][usedWomen] %= MOD;

  dp[currMan][usedWomen] %= MOD;
  return dp[currMan][usedWomen];
}

int main() {
  cin >> n;
  
  for (int i = 0; i < N; i++)
    for (int j = 0; j < TWO; j++)
      dp[i][j] = -1;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      cin >> compatible[i][j];

  cout << countWays(0, 0, 0, 0) % MOD << endl;
}


Measured memory_bytes: 183900
//=============================================
// Author   :   NAVPUN31
// Name     :   Naveen Punjabi
//=============================================


#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define ld      long double
#define pii     pair<int ,int>
#define pld     pair<ld ,ld>
#define F       first
#define S       second
#define mod     1000000007
#define pb      push_back
#define mp      make_pair
#define all(x)  x.begin(),x.end()
#define mset(x) memset(x, 0, sizeof(x));
#define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);


void run(){
    int n;
    cin >> n;

    priority_queue< ld, vector<ld>, greater<ld> > pq;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;

        pq.push(x);
    }

    
    while(pq.size() > 1){
        ld x = pq.top();
        pq.pop();
        ld y = pq.top();
        pq.pop();

        pq.push( (x+y) / (ld)2.0 );
    }

    cout << pq.top() << endl;
}


void setup(){
    ios;
    cout << setprecision(20);
}


signed main(){
    setup();
    int tests = 1;
    // cin >> tests;
    for(int i = 1; i <= tests; i++) run();
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
using namespace std;


int main() {
	string S;
	cin >> S;
	if (S.size() >= 4 && S[0] == 'Y'&& S[1] == 'A' && S[2] == 'K' && S[3] == 'I')
		printf("Yes\n");
	else
		printf("No\n");
}

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

ls=set([1])
i=1
while 6**i<=100000:
  ls.add(6**i)
  i+=1
i=1
while 9**i<=100000:
  ls.add(9**i)
  i+=1

dp = [float("inf") for i in range(n+2)]
dp[0] = 0

#円の総合計
for i in range(n+1):
  #額面のコインの種類
  for j in ls:
    if i + j <= n:
      dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])

Measured memory_bytes: 6296
require 'pp'
s = gets.chomp.chars
s = s.map { |e| e == '1' }

len = s.size
ret = len

pos = []
z = s[0]

# pp s
left_len = 0
loop do
  break if left_len == len
  if s[left_len] != z
    ret = [ret, [left_len, len - left_len].max].min
    z = !z
    # (left_len..(len-1)).each do |j|
    #   s[j] = !s[j]
    # end
    # pp s
  else
    left_len += 1
  end
end

puts ret


Measured memory_bytes: 10620
/**
 * @author yuzining
 * @date 2020/08/02 20:00
 */

#ifdef local
#include "D:\vscode\acm\local.hpp"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(...) do { } while(false)
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  Main();
  return 0;
}
#endif

void Main() {
  int n; cin >> n;
  cout << (n >= 30 ? "Yes\n" : "No\n");
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>;
using namespace std;
int c[100005];
int a,n;
int main(){
	cin >> n;
	for (int i = 1; i <=n; i++) 
	{
	cin >> a;
	c[a]++;
	}
	int ans=0;
	for (int i = 0; i <= 100000; i++) 
	ans= max(ans, c[i]+c[i + 1]+c[i + 2]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("abc179/abc179_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v) \
rep(l, v.size()) { cout << v[l] << " "; } \
cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;
  
  vector<int> a(N), b(N);
  rep(i, N) { cin >> a[i] >> b[i]; }

  int cnt = 0;
  rep(i, N) {
    if (a[i] == b[i]) cnt++;
    else
      cnt = 0;
    if (cnt == 3) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 3656