akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
void debug(vector<vector<ll>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
void debug(vector<ll>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}
//m.emplace(x,0).fi->se++;

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<ll>h(n);
  rep(i,0,n)cin>>h[i];
  h[0]--;
  rep(i,1,n){
    if(h[i-1]<h[i])h[i]--;
    if(h[i-1]>h[i]){
      judge=false;
      break;
    }
  }
  ans1(judge);
  return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>

char s[1000003];

int main() {
    scanf("%s", &s[1]);
    int n = strlen(&s[1]), ans = 0;
    for (int i = n; i > 0; i--) {
        if (s[i] > '5' || (s[i] == '5' && s[i - 1] >= '5')) {
            s[i - 1]++;
            ans += ':' - s[i];
        }
        else ans += s[i] - '0';
    }
    ans += s[0];
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1152
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int64_t X, Y;
  cin >> X >> Y;
  
  if (X % Y == 0) {
    cout << -1 << '\n';
    return 0;
  }
  
  cout << X << '\n';

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char a[2333][2333];
int main()
{
	int n,m;scanf("%d%d\n",&n,&m);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) a[i][j]=getchar();
		scanf("\n");
	}
	
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) putchar((((i==1)||(j&1)||(a[i][j]=='#'))&&(i!=n))?'#':'.');
		putchar('\n');
	}
	putchar('\n');
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++) putchar((((i==n)||(!(j&1))||(a[i][j]=='#'))&&(i!=1))?'#':'.');
		putchar('\n');
	}
}

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

const int mn=1e5+7;
int dis[mn],fa[mn];
vector<int> to[mn];
queue<int> q; 

int main()
{
	int n,m,u,v;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		scanf("%d%d",&u,&v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	q.push(1);
	dis[1]=1;
	while(!q.empty()) {
		u=q.front(),q.pop();
		for(int i=0;i<to[u].size();++i) {
			v=to[u][i];
			if(!dis[v]) {fa[v]=u,dis[v]=dis[u]+1;q.push(v);}
		}
	}
	for(int i=1;i<=n;++i) if(!dis[i]) {puts("No");return 0;}
	puts("Yes");
	for(int i=2;i<=n;++i) printf("%d\n",fa[i]);
}

Measured memory_bytes: 10892
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MOD 998244353
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long lli;


int main()
{
    int n, i, j, count=0;
    lli sum=0;
    char s[200000];
    scanf("%s",s);
    n = strlen(s);
    for(i=0; i<n;) {
        if(s[i]=='A') {
            count++;
            i++;
        } else if(strncmp(s+i, "BC", 2)==0) {
            sum += count;
            i += 2;
        } else {
            count = 0;
            i++;
        }
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 384
import sys

input = sys.stdin.readline


def main():
    Q, H, S, D = map(int, input().split())
    N = int(input())

    ans = 0
    price_of_1_L = min(4 * Q, 2 * H, S)
    if D < 2 * price_of_1_L:
        n_D = N // 2
        ans += D * n_D
        N -= 2 * n_D
    ans += N * price_of_1_L

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
N,M,X,Y=list(map(int,input().split()))
x=list(map(int,input().split()))
y=list(map(int,input().split()))
mx=max(x+[X])
my=min(y+[Y])
r=my-mx
if r>=1:
    print('No War')
else:
    print('War')

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

int main() {
  int n, l;
  cin >> n >> l;
  vector<string> a(n);
  for (int i = 0; i < n; i ++) {
    cin >> a.at(i);
  }

  sort(a.begin(), a.end());
  for (int i = 0; i < n; i ++) {
    cout << a.at(i);
  }
  cout << endl;
}


Measured memory_bytes: 256
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int32_t, int32_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

int32_t neighbours[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

  int32_t H, W;
  cin >> H >> W;
  vector<vector<bool>> goal_grid(H, vector<bool>(W, false));
  for (int32_t i = 0; i < H; ++i) {
    string s;
    cin >> s;
    for (int32_t j = 0; j < W; ++j) {
      goal_grid[i][j] = (s.c_str()[j] == '#');
    }
  }
  bool is_okay = true;
  for (int32_t r = 0; r < H; ++r) {
    for (int32_t c = 0; c < W; ++c) {
      if (goal_grid[r][c]) {
        bool found = false;
        for (const auto &neighbour : neighbours) {
          const int32_t next_r = r + neighbour[0];
          const int32_t next_c = c + neighbour[1];
          if (next_r >= 0 && next_r < H && next_c >= 0 && next_c < W) {
            if (goal_grid[next_r][next_c]) {
              found = true;
            }
          }
        }
        if (!found) {
          is_okay = false;
          break;
        }
      }
    }
  }
  if (is_okay) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
var s:string;
    i,z,x:longint;
 begin
  read(s);
  z:=2100000000;
  for i:=1 to length(s) do
   if s[i]='F'then x:=i;
  for i:=length(s) downto 1 do
   if s[i]='C'then z:=i;
  if z<x then writeln('Yes')
         else writeln('No');
 end.


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

using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i <(n);++i)
#define rep2(i,a,n) for(int i=(a);i<(n);++i)
int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n;cin>>n;
  int hoge[n],huga,cnt=0,turn=0;
  rep(i,n){
    cin>>huga;
    hoge[i]=--huga;
  }
  rep(i,n){
    turn=hoge[turn];
    cnt++;
    if(turn==1){
      cout<<cnt<<endl;
      return 0;
    }
  }
  cout<<-1<<endl;
}


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

#define int long long

int32_t main(){
	int n , k ;
	cin >> n >> k;
	int a[n] ;
	for(int i = 0 ; i < n ; i++) cin >> a[i] ;
	int dp[n] = {} ;
	dp[0] = 0 ;
	for(int i = 1 ; i < n ; i++){
		dp[i] = LLONG_MAX ;
		for(int j = i - 1 ; j >= 0 && j >= i - k ; j--){
			dp[i] = min(dp[j] + abs(a[j] - a[i]) , dp[i]) ;
		}
	}
	cout << dp[n-1] ;
	return 0 ;
}



Measured memory_bytes: 5144
#include <stdio.h>
#include <string.h>

int main() {
  char text[101];
  char pattern[101];

  int remaining = 0;

  scanf("%s", &text);
  scanf("%s", &pattern);

  int textLen = strlen(text);

  int i, j, counter;

  for (i = 0; i < textLen; i++) {
    if (text[i] == pattern[0]) {
      //check
      counter = i;
      remaining = textLen - i;
      for (j = 0; j < strlen(pattern); j++) {
        if (counter > textLen - 1)
          counter = 0;
        //printf("Current letter of text: %c\n", text[counter]);
        if (text[counter] != pattern[j])
          break;
        if (j == strlen(pattern) - 1) {
          printf("Yes\n");
          return 0;
        }
        counter++;
      }
    }
  }

  printf("No\n");

  return 0;
}



Measured memory_bytes: 2108
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ORDER 500000
 
struct NODE{
  int key,nil;
  struct NODE *left,*right,*parent;
};
 
typedef struct NODE Node;
 
Node *head;
 
void insert(Node*);
void print1(Node*);
void print2(Node*);
int find(Node*,int);
void delete(Node*);
Node* successor(Node*);
Node* mini(Node*);
Node* search(Node*,int);
 
int main(){
  int i,num;
  Node *n;
  char order[ORDER][10];
  Node tmp;
 
  scanf("%d",&num);
 
  n = (Node *)malloc(sizeof(Node) * num);
 
for(i=0; i<num; i++){
    scanf("%s",order[i]);
    if(strcmp(order[i],"print")!=0)scanf("%d",&n[i].key);
  }
 
  for(i=0; i<num; i++){
    if(strcmp(order[i],"insert")==0) insert(&n[i]);
    if(strcmp(order[i],"print")==0){
      print1(head);
      printf("\n");
      print2(head);
      printf("\n");
    }
    if(strcmp(order[i],"find")==0){
      if(find(head,n[i].key)==1) printf("yes\n");
      else printf("no\n");
    }
    if(strcmp(order[i],"delete")==0)
 delete(search(head,n[i].key));
  }
 
  return 0;
}
 
 
 
 
 
 
void insert(Node *z){
  Node *y,*x;
 
 z->left = NULL;
  z->right = NULL;
  y = NULL;
  x = head;
 
  while(x != NULL){
    y = x;
    if(z->key < x->key)  x = x->left;
    else x = x->right;
  }
  z->parent = y;
 
  if(y == NULL) head = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}
 
 
 
void print1(Node *node){
  if(node == NULL){
    return;
  }
 
  print1(node->left);
  printf(" %d",node->key);
  print1(node->right);
  return ;
}
 
 
 
void print2(Node *node){
  if(node == NULL){
    return;
  }
  printf(" %d",node->key);
  print2(node->left);
  print2(node->right);
  return;
}
 
 
 
int find(Node *node,int num){
  int found=0;
  if(node == NULL){
    return 0;
  }
  if(node->key == num) found=1;
  if(node->key > num) found = find(node->left,num);
  if(node->key < num) found = find(node->right,num);
 
  return found;
}
 
 
 
void delete(Node *node){
  Node *x,*y;
  if(node->left == NULL || node->right == NULL) y = node;
  else y = successor(node);
 
  if(y->left != NULL) x = y->left;
  else x = y->right;
 
  if(x != NULL) x->parent = y->parent;
 
  if(y->parent == NULL) head = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
 
  if(y != node) node->key = y->key;
}
 
 
 
Node* successor(Node *node){
  Node *y,*x;
  if(node->right != NULL) return mini(node->right);
  x = node;
  y = x->parent;
  while(y != NULL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}
 
 
Node* mini(Node *node){
  while(node->left != NULL){
    node = node->left;
  }
  return node;
}
 
 
Node* search(Node *node,int num){
  Node *found;
  if(node == NULL){
    return 0;
  }
  if(node->key == num){
    found = node;
  }
  if(node->key > num) found = search(node->left,num);
  if(node->key < num) found = search(node->right,num);
 
  return found;
}

Measured memory_bytes: 21128
N = int(input())
S = input()
R = [0]*N
G = [0]*N
B = [0]*N
for k in range(N):
    if S[-k-1] == "R":
        R[-k-1] = 1
    elif S[-k-1] == "G":
        G[-k-1] = 1
    else:
        B[-k-1] = 1

for k in range(N-1,0,-1):
    R[k-1] += R[k]
    G[k-1] += G[k]
    B[k-1] += B[k]
R = R + [0]
G = G + [0]
B = B + [0]

ans = 0
for k in range(N):
    if S[k] == "R":
        ans += G[k+1]*B[k+1]
    elif S[k] == "G":
        ans += R[k+1]*B[k+1]
    else:
        ans += R[k+1]*G[k+1]

for k in range(1+N//2):
    l = 0
    while l+2*k < N:
        if S[l] != S[l+k] and S[l+k] != S[l+2*k] and S[l+2*k] != S[l]:
            ans -= 1
        l += 1
print(ans)


Measured memory_bytes: 9408
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2 vector<vec>
#define vecll2 vector<vecll>
#define vec3 vector<vec2d>
#define vecll3 vector<vecll2d>
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(vector<T> v){for(T e:v)cout<<e<<" ";cout<<endl;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}

const int N=1e5+10;
ll a[N<<4];
int sum[11];
main(){
    ios
    int h,w,n;cin>>h>>w>>n;
    h-=2,w-=2;
    int x;int y;
    int cnt=0;
    ll m=(ll)h*w;
    rep(iii,n){
        cin>>x>>y;
        rep(i,3)if( x-i>=1 && x-i<=h){
            rep(j,3)if(y-j>=1 && y-j<=w){
            a[cnt++]=((ll)(x-i)<<32)+(y-j);
            }
        }
    }
    sort(a,a+cnt);
    ll t=1;
    rep(i,cnt){
        if(a[i]==a[i+1])t++;
        else sum[t]++,t=1,m--;
    }
    cout<<m<<" ";
    rep2(i,1,9)cout<<sum[i]<<" ";
}



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

const ll X=1000000007;

int main() {
  int N;
  cin>>N;
  vector<int> A(N);
  rep(i,N){
    cin>>A.at(i);
  }
  vector<int> rbg(3,-1);
  ll ans=1;
  bool checked;
  rep(i,N){
    int count=0;
    checked=false;//i番目がもう足されたかどうか
    rep(j,3){
      if(rbg.at(j)==A.at(i)-1){
        count++;
        if(checked==false){
          rbg.at(j)++;
          checked=true;
        }
      }
    }
    ans*=count;
    ans%=X;
  }
  cout<<ans<<endl;
}



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

int main () {

    int A, B;
    cin >> A >> B;

    int unused = 1;
    for (int i = 0;; i++) {
        if (unused >= B) {
            cout << i << endl;
            break;
        }

        unused = unused - 1 + A;
    }

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;
constexpr LL kMax = 1e9;

int main() {
  LL S; std::cin >> S;

  if (S<kMax) {
    std::cout << "0 0 1 0 0 " << S << std::endl;
  } else {
    LL l;
    while(l*l<S) ++l;

    LL ab = l*l - S;
    for (LL a = 1; a <= kMax; ++a) {
      if (ab%a == 0 && ab/a < kMax) {
        std::cout << "0 0 " << a << " " << l << " " << l << " " << ab/a << std::endl;
        break;
      }
    }
  }
}


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

int main(){
  int N;
  cin >> N;
  vector<long long> A(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  sort(A.begin(),A.end());
  long long ans=0;
  if(N%2==0){
    for(int i=0;i<N;i++){
      if(i<N/2) ans-=2*A.at(i);
      else  ans+=2*A.at(i);
    }
    ans+=A.at(N/2-1);
    ans-=A.at(N/2);
    cout << ans << endl;
    return 0;
  }

  long long tmp=0;
  for(int i=0;i<N;i++){
    if(i==N/2)  continue;
    if(i<N/2) tmp-=2*A.at(i);
    else  tmp+=2*A.at(i);
  }
  ans=max(tmp+(A.at(N/2-1)-A.at(N/2)),tmp+(A.at(N/2)-A.at(N/2+1)));
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<string>
using namespace std;
int main(){
long i,j,k;
string s[9];
for(i=0;i<9;i++)cin>>s[i];
i=j=k=0;
cout<<"R";j++;
for(;;){
     if(k==0&&i>0&&s[i-1][j]=='1'){cout<<"U";i-=2;k=3;}
else if(k==0&&     s[i][j]  =='1'){cout<<"R";j++; k=0;}
else if(k==0&&i<8&&s[i+1][j]=='1'){cout<<"D";i+=2;k=1;}
else if(k==0)                     {cout<<"L";j--; k=2;}
else if(k==1&&     s[i][j]  =='1'){cout<<"R";j++; k=0;}
else if(k==1&&i<8&&s[i+1][j]=='1'){cout<<"D";i+=2;k=1;}
else if(k==1&&j>0&&s[i][j-1]=='1'){cout<<"L";j--; k=2;}
else if(k==1)                     {cout<<"U";i-=2;k=3;}
else if(k==2&&i<8&&s[i+1][j]=='1'){cout<<"D";i+=2;k=1;}
else if(k==2&&j>0&&s[i][j-1]=='1'){cout<<"L";j--; k=2;}
else if(k==2&&i>0&&s[i-1][j]=='1'){cout<<"U";i-=2;k=3;}
else if(k==2)                     {cout<<"R";j++; k=0;}
else if(k==3&&j>0&&s[i][j-1]=='1'){cout<<"L";j--; k=2;}
else if(k==3&&i>0&&s[i-1][j]=='1'){cout<<"U";i-=2;k=3;}
else if(k==3&&     s[i][j]  =='1'){cout<<"R";j++; k=0;}
else if(k==3)                     {cout<<"D";i+=2;k=1;}
if(i==0&&j==0)break;
}
cout<<endl;
return 0;
}

Measured memory_bytes: 1180
#include<stdio.h>
#include<stdlib.h>

#define NIL NULL

struct node{
  struct node *l;
  struct node *r;
  struct node *p;
  int key;
};

typedef struct node * Node;

Node root;

void Preorder(Node t){
  printf(" %d",t->key);
  if(t!=NIL){
    if(t->l!=NIL)Preorder(t->l);
    if(t->r!=NIL)Preorder(t->r);
  }
}

void Inorder(Node t){
  
  if(t!=NIL){
    if(t->l!=NIL){
      Inorder(t->l);
      }
    printf(" %d",t->key);
    
    if(t->r!=NIL){
      Inorder(t->r);
      }
  }
}

void insert(int k){
  Node y=NIL;
  Node x=root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key=k;
  z->l=NIL;
  z->r=NIL;
  
  while(x!=NIL){
    y=x;

    if(z->key<x->key) x=x->l;
    else x=x->r;
  }
  z->p=y;
  
  if(y==NIL) root=z;
  else if(z->key<y->key) y->l=z;
  else y->r=z;
}

Node Search(Node t,int k){
  if(t==NIL || k==t->key) return t;
  if(k<t->key) return Search(t->l,k);
  else return Search(t->r,k);
}

main(){
  int n, i, x;
  char str[20];
  
  scanf("%d",&n);

  for ( i = 0; i < n; i++ ){
    scanf("%s",str);

    if (str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    } 
    else if (str[0]=='p'){
      Inorder(root);
      printf("\n");
      
      Preorder(root);
      printf("\n");
    }
    else if(str[0]=='f'){
      scanf("%d",&x);
      Node s=Search(root,x);
      if (s!= NIL ) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}

Measured memory_bytes: 19364
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1000000000
#define LINF 1000000000000000000
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef pair<int, int> P;
typedef pair<long long, long long> LLP;

int H, W;
string S[20];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

bool check(int x, int y) {
    if (x < 0 || x >= W || y < 0 || y >= H) return false;
    return S[y][x] == '.';
}

int bfs(int x, int y) {
    int maximum = -1;
    queue<pair<P, int>> que;
    int distance[H][W];
    rep(i,H) rep(j,W) distance[i][j] = -1;
    que.push(make_pair(make_pair(x, y), 0));
    distance[y][x] = 0;
    while (!que.empty()) {
        pair<P, int> p = que.front(); que.pop();
        int i = p.first.second;
        int j = p.first.first;
        rep(k,4) {
            if (!check(j + dx[k], i + dy[k])) continue;
            if (distance[i + dy[k]][j + dx[k]] < 0) {
                distance[i + dy[k]][j + dx[k]] = p.second + 1;
                que.push(make_pair(make_pair(j + dx[k], i + dy[k]), distance[i + dy[k]][j + dx[k]]));
                maximum = max(maximum, distance[i + dy[k]][j + dx[k]]);
            }
        }
    }

    return maximum;
}

int main() {
    
    cin >> H >> W;

    rep(i,H) cin >> S[i];

    int maximum = -1;

    rep(y,H) rep(x,W) {
        if (check(x, y)) {
            maximum = max(maximum, bfs(x, y));
        }
    }

    cout << maximum << endl;

    return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;

int main() {
    int n;
    cin >> n;
    vector<int> res(n, 0);
    for (int x = 1; x < 105; ++x) {
        for (int y = 1; y < 105; ++y) {
            for (int z = 1; z < 105; ++z) {
                ll v = x*x + y*y + z*z + x*y + y*z + z*x;
                if (v < 10050) res[v]++;
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << res[i] << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <algorithm>
using namespace std;
struct date{
	int m;
	int t;
};
struct Rule{
	bool operator()(const date& a,const date& b){
		return a.m<b.m;
	}
};
date d[105];
int main()
{
	int N,T,i;
	cin>>N>>T;
	for( i=0;i<N;i++)
		cin>>d[i].m>>d[i].t;
	sort(d,d+N,Rule());

	for(i=0;i<N;i++)
	{
		if(d[i].t<=T)
		{
			cout<<d[i].m;
			break;
		}
			
	}
	if(i==N)
		cout<<"TLE"<<endl;
	return 0;
}

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

int h,w,n,sx,sy,gx,gy,dp[1111][1111][4],nex[10009][4][4];
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
int MIN[4];
string t,s[1009];

void init(){
  int pos=0;
  r(i,4)MIN[i]=1e9;
  r(i,n+1)r(j,4)r(k,4)nex[i][j][k]=1e9;
  for(int i=n;i>=1;i--){
    if(t[i-1]=='R'){
      for(int i=3;i>1;i--)swap(MIN[(i)%4],MIN[(i-1+4)%4]);
    }
    if(t[i-1]=='L'){
      r(i,3)swap(MIN[i],MIN[(i+1)%4]);
    }
    if(t[i-1]=='R')pos=1;
    if(t[i-1]=='L')pos=3;
    pos=(pos+4)%4;
    MIN[pos]=min(MIN[pos],i);
    r(j,4)r(k,4){
      if(j<k)nex[i-1][j][k]=MIN[(k-j+4)%4];
      else nex[i-1][j][k]=MIN[(4-j+k+4)%4];
    }
  }
}

bool dij(){
  r(i,1111)r(j,1111)r(k,4)dp[i][j][k]=1e9;
  priority_queue<P,vector<P>,greater<P> >q;
  while(1){
    q.push(P(0,sx+sy*10000+0*100000000));
    dp[sy--][sx][0]=0;
    if(sy==-1)break;
    if(s[sy][sx]=='#')break;
  }
  while(!q.empty()){
    P p=q.top();q.pop();
    int x=p.second%10000;
    int y=(p.second/10000)%10000;
    int d=p.second/100000000;
    if(dp[y][x][d]<p.first)continue;
    r(i,4){
      if(i==d)continue;
      if(nex[p.first][d][i]==1e9)continue;
      int cost=nex[p.first][d][i];
      int X=x,Y=y;
      while(1){
        X+=dx[i];
        Y+=dy[i];
        if(X<0||Y<0||X>=w||Y>=h)break;
        if(s[Y][X]=='#')break;
        if(dp[Y][X][i]<=cost)continue;
        dp[Y][X][i]=cost;
        q.push(P(cost,X+Y*10000+i*100000000));
      }
    }
  }
  r(i,4)if(dp[gy][gx][i]!=1000000000)return 1;
  return 0;
}

signed main(){
  while(cin>>h>>w>>n,n){
    cin>>t;
    r(i,h)cin>>s[i];
    r(i,h)r(j,w){
      if(s[i][j]=='S')sx=j,sy=i;
      if(s[i][j]=='G')gx=j,gy=i;
    }
    init();
    cout<<(dij()?"Yes":"No")<<endl;
  }
}


Measured memory_bytes: 24432
/******************************************************/
/******************************************************/
/**                                                  **/
/**            BISMILLAHIR RAHMANIR RAHIM            **/
/**         REAZ AHAMMED CHOWDHURY - reaziii         **/
/**  Department of Computer Science and Engineering  **/
/*         INSTITUTE OF SCIENCE AND TECHNOLOGY       **/
/**                                                  **/
/******************************************************/
/******************************************************/



#include<bits/stdc++.h>
#define sc(x)        scanf("%lld",&x)
#define pcase(x)     printf("Case %d: ",x++)
#define pn           printf("\n")
#define fri(f)       for(int i=0;i<f;i++)
#define frj(f)       for(int j=0;j<f;j++)
#define reset(x,e)   memset(x,e,sizeof(x))
#define all(x)       x.begin(),x.end()
#define input        freopen("input.txt","r",stdin);
#define output       freopen("output.txt","w",stdout)
#define infi         INT_MAX
#define m_v          3000000
#define pii          pair<int,int>
#define pch          pair<char,char>
#define pll          pair<ll,ll>
#define mgraph       map<int,vector<int> >
#define mp           make_pair
#define pb           push_back
#define clr(x)       memset(x,0,sizeof(x))
#define frx(x,y)     for(int x=0;x<y;x++)
#define ff           first
#define ss           second
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
bool checkbitt(ll num, int pos);
ll setbitt(ll num, ll pos);
ll resetbitt(ll num, int pos);
void abcd() {
#ifndef ONLINE_JUDGE
	input;
	output;
#endif
#ifdef ONLINE_JUDGE
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#endif
}

void read(int *aa, int sz) {fri(sz) scanf("%d", (aa + i));}
void read(ll *aa, int sz) {fri(sz) scanf("%lld", (aa + i));}
void read(ll *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%lld", (aa + i));}
void read(int *aa, int s, int e) {for (int i = s; i < s + e; i++)scanf("%d", (aa + i));}
const ll mod =       1e9 + 7;
const ll N =     1e6 + 10;

//.................___Start from here___.................//
//.................._____________________................//
int n, k;
ll dp[N];
ll w[N];
ll v[N];



int solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> w[i] >> v[i];
	}


	for (int i = 1; i <= n; i++) {
		for (int j = k; j >= 1; j--) {
			if (j >= w[i]) {
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	}

	cout << dp[k] << endl;


	return 0;
}
int main() {
	// abcd();
	int cs = 1;
	int cn = 1;
	//cin>>cs;
	while (cs--) {
		solve();

	}
}


bool checkbitt(ll num, int pos) {return (num >> pos) & 1;}
ll setbitt(ll num, ll pos) {return (1 << pos) | num;}
ll resetbitt(ll num, int pos) {if (!checkbitt(num, pos)) return num; else return (1 << pos)^num;}




Measured memory_bytes: 4424
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int N, K;
int D[2001];
int E[4001], ne[4001], he[2001];
void dfs(int v, int d) {
	D[v] = d;
	for (int to = he[v]; to; to = ne[to]) {
		if (D[E[to]] < 0) dfs(E[to], d + 1);
	}
}

int dfs2(int v, int prev, int d) {
	if (d > K / 2) return 0;
	int ret = 1;
	for (int to = he[v]; to; to = ne[to]) {
		if (E[to] != prev) ret += dfs2(E[to], v, d + 1);
	}
	return ret;
}

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


	cin >> N >> K;
	int tmp = 1;
	rep(i, N - 1) {
		int a, b;
		cin >> a >> b;
		E[tmp] = b;
		ne[tmp] = he[a];
		he[a] = tmp++;
		E[tmp] = a;
		ne[tmp] = he[b];
		he[b] = tmp++;
	}

	rep1(j, N) D[j] = -1;
	dfs(1, 0);
	int saidai = 0;
	int doko, doko2;
	rep1(i, N) if (saidai < D[i]) {
		saidai = D[i];
		doko = i;
	}
	rep1(j, N) D[j] = -1;
	dfs(doko, 0);
	saidai = 0;
	rep1(i, N) if (saidai < D[i]) {
		saidai = D[i];
		doko2 = i;
	}
	if (saidai <= K) {
		printf("0\n");
		return 0;
	}

	bool muri[2001] = {};
	rep1(i, N) if (D[i] < K / 2) {
		muri[i] = 1;
	}
	rep1(j, N) D[j] = -1;
	dfs(doko2, 0);
	rep1(i, N) if (D[i] < K / 2) {
		muri[i] = 1;
	}

	if (K % 2 == 0) {
		int kotae = N;
		rep1(i, N) {
			if (!muri[i]) {
				int kazu = dfs2(i, -1, 0);
				kotae = min(kotae, N - kazu);
			}
		}
		co(kotae);
	}
	else {
		int kotae = N;
		rep1(i, N) {
			for (int to = he[i]; to; to = ne[to]) {
				int j = E[to];
				if (i < j) {
					if (!muri[i] && !muri[j]) {
						int kazu = dfs2(i, j, 0) + dfs2(j, i, 0);
						kotae = min(kotae, N - kazu);
					}
				}
			}
		}
		co(kotae);
	}

	Would you please return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f,maxn=310;

int n,map[maxn][maxn],f[maxn][maxn];

int abs(int x){return x>0?x:-x;}
int main(){
	n=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)map[i][j]=read(),f[i][j]=map[i][j];
	bool ok=1;
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			for(int k=1;k<=n;k++)if(i!=k&&j!=k){
				if(map[i][j]>map[i][k]+map[k][j])ok=0;
				if(map[i][j]==map[i][k]+map[k][j])f[i][j]=f[j][i]=0;
			}
			//for(int k=1;k<=n;k++)f[i][j]=max(f[i][j],abs(map[i][k]-map[j][k]));
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans+=f[i][j];
    if(ok)printf("%lld",ans/2);else printf("-1");
    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>

int main() {
  int s[10000],t[500],i,j,n,q,ans=0;
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&s[i]);
  scanf("%d",&q);
  for (i = 0; i < q; i++)
    scanf("%d",&t[i]);
  for (i = 0; i < q; i++) {
    for (j = 0; j < n; j++){
      if(t[i]==s[j]){
        ans++;
        break;
   }
   }
}
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 1856
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int x = (c + b - 1) / b;
	int y = (a + d - 1) / d;
	if (x > y) { cout << "No\n"; }
	else { cout << "Yes\n"; }

	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>

// @author: pashka

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);

    long long int n, k;
    cin >> n >> k;
    long long int s = 0;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        s += a[i].second;
        if (s >= k) {
            cout << a[i].first;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 1024
H, W, K = [int(v) for v in input().split()]
G = []
for _ in range(H):
    G.append(input())

ans = 0

for mask_r in range(1 << H):
    for mask_c in range(1 << W):
        black = 0
        for i in range(H):
            for j in range(W):
                if ((mask_r >> i) & 1 == 0) and ((mask_c >> j) & 1 == 0) and G[i][j] == "#":
                    black += 1
        if black == K:
            ans += 1

print(ans)


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

int main(){
  int N;
  cin>>N;
vector<int> data(N);
	for(int i=0;i<N;i++){
      int a;
      cin>>a;
      data[i]=a;
	}
  int count=0;
  sort(data.begin(),data.end());
   data.erase(unique(data.begin(),data.end()),data.end());
   cout<<data.size()<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

int main(){
  int n;
  cin >> n;
  n--;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int ans;
  cin >> ans;
  vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(2,vector<ll>(21)));
  dp[0][0][a[0]]=1;
  rep(i,n-1){
    rep(j,21){
      if(dp[i][0][j]){
        if(j+a[i+1]<=20)
          dp[i+1][0][j+a[i+1]] += dp[i][0][j];
        if(j-a[i+1]>=0)
          dp[i+1][1][j-a[i+1]] += dp[i][0][j];
      }
      if(dp[i][1][j]){
        if(j+a[i+1]<=20)
          dp[i+1][0][j+a[i+1]] += dp[i][1][j];
        if(j-a[i+1]>=0)
          dp[i+1][1][j-a[i+1]] += dp[i][1][j];
      }
    }
  }
  ll res=0;
  res += dp[n-1][0][ans];
  res += dp[n-1][1][ans];
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define rep(i,l,r) for(int i = l;i < r;i++)
#define per(i,l,r) for(int i = r - 1;i >= l;i--)
#define de(x) cout<<#x<<" = "<<x<<endl
#define dd(x) cout<<#x<<" = "<<x<<','
typedef long long ll;
int c[505],s[505],f[505];
int main()
{
	int n;
	cin>>n;
	rep(i,0,n - 1) scanf("%d%d%d",&c[i],&s[i],&f[i]);
	rep(j,0,n - 1){
		int ans = 0;
		rep(i,j,n - 1){
			if(ans < s[i]) ans = s[i];
			else if((ans - s[i]) % f[i] != 0) 
			ans += (f[i] -(ans - s[i]) % f[i]);
			//de(ans);
			ans += c[i];
			/*de(i);
			de(c[i]);
			de(ans);*/
		}
		printf("%d\n",ans);
	}
	cout<<'0';
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i, j;
    for(i=1;i<=9;i++){
        for(j=1;j<=9;j++){
            printf("%dx%d=%d\n",i ,j ,i*j);
        }
    }
    return 0;
}




Measured memory_bytes: 2044
n, m = gets.chomp.split(' ').map(&:to_i)
start = n % 2 == 0 ? n : [n + 1, m].min
final = m % 2 == 1 ? m : [m - 1, n].max
distance = final - start
xor = m
if n != m
  xor = (distance / 2 + 1) % 2 == 1 ? 1 : 0
  xor ^= start == n ? 0 : n
  xor ^= final == m ? 0 : m
end
puts xor

Measured memory_bytes: 3836
n = int(input())
a = [list(map(int, input().split(' '))) for i in range(n)]
for x in range(101):
    for y in range(101):
        for i in range(n):
            if a[i][2] > 0:
                htop = a[i][2] + abs(x-a[i][0]) + abs(y-a[i][1])
                break
        for i in range(n):
            if a[i][2] == 0:
                if htop - (abs(x-a[i][0]) + abs(y-a[i][1])) > 0:
                    break
            if a[i][2] > 0:
                if htop - (abs(x-a[i][0]) + abs(y-a[i][1])) != a[i][2]:
                    break
        else:
            print(x,y,htop)
            exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9+7;
const ll INF= 1e18L+5;
ll dp[1001][1001];
char a[1001][1001];
ll solve(int i, int j){
	if(i==0 && j==0)
		return 1;
	int x = 0, y=0;
	if(i>0&&a[i-1][j]=='.'){
		if(dp[i-1][j]==-1){
			dp[i-1][j] = solve(i-1,j);
		}
		x = dp[i-1][j];
	}
	if(j>0&&a[i][j-1]=='.'){
		if(dp[i][j-1]==-1){
			dp[i][j-1] = solve(i,j-1);
		}
		y = dp[i][j-1];
	}
	return (x+y)%mod;
}

int main() {
	int h,w;
	cin >> h >> w;
	// char a[h][w];
	memset(dp,-1,sizeof(dp));
	for(int i=0; i<h; i++){
		for(int j=0;j<w; j++)
			cin >> a[i][j];
	}
	// dp[h-1][w-1] = solve(h-1,w-1);
	// for(int i=0; i<h; i++){
	// 	for(int j=0; j<w; j++){
	// 		cout<<dp[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	cout<<solve(h-1,w-1)<<endl;
	// int dp[i][j]={0};
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define rep(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define rep_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9)+7;
const ll INF = ll(1e10);
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
  vector< pair<ll, ll> > p;
  for (ll i = 2; i * i <= n; i++) {
    if ((n % i) != 0) continue;
    p.push_back(make_pair(i, 0));
    while ((n % i) == 0) {
      n /= i;
      p[i].second += 1;
    }
    p.push_back(make_pair(n, 0));
  }

  if (n != 1) p.push_back(make_pair(n, 1));
  return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a) {
	ll b = MOD, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0) { u += MOD; }
	return u;
}
// 順列
ll permutation(const ll n, const ll m) {
	ll result = 1;
	for (ll i = n; i > n - m; i--) { result = (result * i) % MOD; }
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x) {
	if (x == 0) return 1;
	ll res = repeat_square(n, x/2);
	res = res * res % MOD;
	if ((x % 2) == 1) res = res * n % MOD;
  return res;
}
// 組み合わせ
ll combination(const ll n, const ll a) {
	ll x = 1, y = 1;
  for(ll i = 0; i < a; i++){
    x = x * (n-i) % MOD;
    y = y * (i+1) % MOD;
  }
  return x * repeat_square(y, MOD-2) % MOD;
}

int main() {
	ll K, A, B;
	cin >> K >> A >> B;

	ll k = K, n = 1 + K;
	ll x = 1, a = 0;
	while (k > 0) {
		if (a > 0 && B > A) {
			x += B;
			a -= 1;
			k -= 1;
			continue;
		}

		if (x >= A && B > A && k != 1) {
			x -= A;
			a += 1;
			k -= 1;
			continue;
		}

		x += 1;
		k -= 1;
	}

	cout << (max({n, x})) << endl;
	return 0;
}


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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define foreach(it, v) for(typeof(v.begin()) it=v.begin(); it!=v.end(); ++it)
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;

//MOD//
const ll MOD = 1000000007;
struct big;
big ex(big a, ll tms);
typedef struct big{
  ll val;
  big():val(0){}
  big(ll val):val((val%MOD+MOD)%MOD){}
  big& operator += (const big& obj){ (val+=obj.val)%=MOD; return *this;}
  big& operator -= (const big& obj){ (val+=MOD-obj.val)%=MOD; return *this;}
  big& operator *= (const big& obj){ (val*=obj.val)%=MOD; return *this;}
  big& operator /= (const big& obj){ (val*=ex(obj,MOD-2).val)%=MOD; return *this;}
  big operator + (const big& obj)const{ return big(*this) += obj;}
  big operator - (const big& obj)const{ return big(*this) -= obj;}
  big operator * (const big& obj)const{ return big(*this) *= obj;}
  big operator / (const big& obj)const{ return big(*this) /= obj;}
  bool operator < (const big& obj)const{ return val < obj.val;}
  bool operator == (const big& obj)const{ return val == obj.val;}
} big;
istream& operator >> (istream& i, big& obj){ i>>obj.val; return i;}
ostream& operator << (ostream& o, const big& obj){ o<<obj.val; return o;}
big ex(big obj, ll tms){
  if(!tms) return 1;
  big ret = ex(obj, tms/2);
  ret *= ret;
  return (tms&1) ? ret*obj : ret;
}
//MOD//

ll pow(ll n, int m){
  if(!m) return 1;
  ll ret = pow(n, m/2);
  ret *= ret;
  return (m&1) ? ret*n : ret;
}

template <class F, class T>
void convert(const F &f, T &t){
  stringstream ss;
  ss << f;
  ss >> t;
}

int  N, X;
int S[205];
big ans;

big dq[205][100005];

void hoge (int i, big rate, int v) {
  if (v==0) return;
  if (i==N-1) {
    ans += big(v%S[i]) * rate;
    return;
  }
  if (v<S[i]) hoge(i+1, rate*(N-i), v);
  else {
    hoge(i+1, rate*(N-i-1), v);
    hoge(i+1, rate, v%S[i]);
  }
}

void fuga() {

  rep (j, X+1) dq[0][j] = j%S[0];

  rrep(i, N-1) {
    rep (j, X+1) {
      dq[i][j] = dq[i-1][(j%S[i])] + dq[i-1][j] * i;
    }
  }
}

int main(){
  scanf("%d%d",&N,&X);
  rep(i,N) scanf("%d",&S[i]);

  sort(&S[0], &S[N]);

  //reverse(&S[0], &S[N]);
  //hoge(0, 1, X);

  fuga();
  ans = dq[N-1][X];

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


Measured memory_bytes: 160384
q=[1.0]+[a=k=0]*n=gets.to_i
g=[]
$<.map{|s|b,c=s.split;(g[b.to_i-1]||=[])<<c.to_i-1}
g.map{|h|h.map{|t|q[t]+=q[k]/h.size};k+=1}
e=[0.0]*n
(h=g[k-=1].map{|x|e[x]}
s=h.inject :+
e[k]=1+s/z=h.size
z>1&&a=[a,q[k]*=(s-h.max)/~-z-s/z].min)while k>0
p e[0]+a

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

int main()
{
  int a, b;
  std::cin >> a >> b;

  if (a > b)
  {
    std::cout << "a > b" << std::endl;
  }
  else if (a == b)
  {
    std::cout << "a == b" << std::endl;
  }
  else
  {
    std::cout << "a < b" << std::endl;
  }

  return 0;
}



Measured memory_bytes: 3116
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	println(abs((x - 2) * (y - 2)));
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;


int main() {
  int N; cin >> N;
  cout << 0 << endl;
  string r0; cin >> r0;
  string rnow;
  int l = 0, r = N-1;
  while(l!=r) {
    int mid = (l+r+1)/2;
    cout << mid << endl;
    cin >> rnow;
    if (rnow=="Vacant") break;
    if (rnow==r0^(mid%2)) l = mid;
    else r = mid-1;
  }
  return 0;
}

Measured memory_bytes: 852
N, W = map(int, input().split())
wv = list(map(int, input().split()))
w1 = wv[0]

wvs = [[] for i in range(4)]
wvs[0].append(wv[1])

for i in range(N - 1):
  w, v = list(map(int, input().split()))
  w -= w1
  wvs[w].append(v)

s = [0] * 4
for i in range(4):
  wvs[i] = sorted(wvs[i], reverse = True)
  s[i] = len(wvs[i])
  if s[i] > 1:
    for j in range(1, s[i]):
      wvs[i][j] += wvs[i][j - 1]
  wvs[i].insert(0, 0)
#print(wvs)

ans = 0
for i in range(s[0] + 1):
  for j in range(s[1] + 1):
    for k in range(s[2] + 1):
      for l in range(s[3] + 1):
        weight = w1 * (i + j + k + l) + (j + 2 * k + 3 * l)
        if weight <= W:
          value = wvs[0][i] + wvs[1][j] + wvs[2][k] + wvs[3][l]
          ans = max(ans, value)
          
print(ans)
        
        


  
  
  

Measured memory_bytes: 73276
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
typedef long long ll;
typedef vector<ll> vl;
#define rp(i, f, t) for (long long int i = f; i < t; i++)
#define pr(i, f, t) for (long long int i = t - 1; i >= f; i--)
#define ca(n, a) rp(ca_i, 0, n) cout << a[ca_i] << ((ca_i == n - 1) ? "\n" : " ")
#define ia(n, a) rp(ia_i, 0, n) cin >> a[ia_i]
#define za(n, a) rp(za_i, 0, n) a[za_i] = 0
#define be(a) a.begin(), a.end()
#define ce(a) cout << (a) << endl
int main()
{
    ll n, k;
    cin >> n >> k;
    ll a[n + 1], c[n + 1];
    rp(i, 0, n) cin >> a[i];

    rp(i, 0, k)
    {
        rp(j, 0, n + 1) c[j] = 0;
        rp(j, 0, n)
        {
            if (a[j] >= 1)
            {
                c[j + 1]++;
                c[min(n - 1, j + a[j]) + 1]--;
                c[max(ll(0), j - a[j])]++;
                c[j]--;
            }
        }
        // ca(n, c);
        rp(j, 1, n) c[j] += c[j - 1];
        rp(j, 0, n) a[j] = 1 + c[j];
        bool sig = true;
        rp(j, 0, n) if (a[j] != n)
        {
            sig = false;
            break;
        }
        if (sig)
            break;
    }
    ca(n, a);
}

Measured memory_bytes: 6712
N, M = map(int, input().split())
mod = 10 ** 9 + 7
dp = [0] * (N+3)
dp[0] = 1
for i in range(M):
    dp[int(input())] = 0.5

for i in range(N):
    if dp[i] % 1 == 0:
        dp[i+1] = (dp[i+1] + dp[i]) % mod
        dp[i+2] = (dp[i+2] + dp[i]) % mod

print(dp[N] % mod)


Measured memory_bytes: 46668
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
using namespace std;

int main(){
    string s,t = "";
    char tmp;
    string ans = "No";
    cin >> s >> t;

    for (int i = 0; i < s.length(); i++)
    {
        if(s == t){
            ans = "Yes";
            break;
        }
        else{
            tmp = s[s.length()-1];
            for (int j = s.length()-2; j > -1; j--)
            {
                s[j+1] = s[j];
            }
            s[0] = tmp;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;class Main{public static void main(String[]z){Scanner s=new Scanner(System.in);for(int n,m,r,i;(n=s.nextInt())>0;System.out.println(r)){m=s.nextInt();int[]a=new int[n];for(i=r=0;i<n;)r+=a[i++]=s.nextInt();Arrays.sort(a);for(i=n-m;i>=0;i-=m)r-=a[i];}}}

Measured memory_bytes: 12000
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int N;
ll A[405], DP[405][405], sum[405];

ll Calc(int L, int R){
  if (DP[L][R] != -1) return DP[L][R];
  if (L == R) return DP[L][R] = 0;

  ll ans = 1e18;
  for (int i = L; i < R; i++){
    ans = min(ans, Calc(L, i) + Calc(i + 1, R) + sum[R] - sum[L - 1]);
  }

  return DP[L][R] = ans;
}

int main(){
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%lld", &A[i]);
  for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + A[i];
  fill((ll*)DP, (ll*)(DP + N), -1);
  printf("%lld\n", Calc(1,N));
  return 0;
}


Measured memory_bytes: 1536
#include <algorithm>
#include <iostream>
#include <queue>
#include <queue>
#include <stdio.h>
#include <string>

using namespace std;

void solve(int A, int B, int K) {
  int ans;
  vector<int> v;
  for (int i = 1; i <= min(A, B); i++) {
    if ((A % i == 0) && (B % i == 0)) {
      v.emplace_back(i);
    }
  }
  ans = v[v.size() - K];
  cout << ans << endl;
}

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  solve(A, B, K);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
    int a,b;
    while(true){
        cin >> a >> b;
        if(a == 0 && b == 0)break;
        if(a > b)cout << b << " " << a << endl;
        else cout << a << " " << b << endl;
    }
}

Measured memory_bytes: 1160
L = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
B = list(int(input()) for _ in range(n))
ans = 'No'
for i in range(3):
  for j in range(3):
    for b in B:
      if L[i][j] == b:
        L[i][j] = 0
        
for i in range(3):
  if L[i][0] == L[i][1] == L[i][2] == 0: ans = 'Yes' #横
  if L[0][i] == L[1][i] == L[2][i] == 0: ans = 'Yes' #縦
if L[0][0] == L[1][1] == L[2][2] == 0: ans = 'Yes'
if L[0][2] == L[1][1] == L[2][0] == 0: ans = 'Yes'
  
print(ans)

Measured memory_bytes: 9100