akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
    static int[] height;
    static int[] dp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        height = new int[n+1];
        dp = new int[n+1];
        for(int x = 1; x<=n; x++){
            height[x] = sc.nextInt();
        }
        Arrays.fill(dp, Integer.MAX_VALUE);
        System.out.println(frog(n));
        //System.out.println(Arrays.toString(dp));


    }

    public static int frog(int i){
        if(dp[i] != Integer.MAX_VALUE)
            return dp[i];
        if(i == 2){
            return dp[i] = Math.abs(height[2] - height[1]);
        }
        if(i == 1)
            return dp[i] = 0;
        return dp[i] = Math.min(frog(i-1) + Math.abs(height[i] - height[i-1]), frog(i-2)+ Math.abs(height[i] - height[i-2]));

    }
}


Measured memory_bytes: 74792
#include <cstdio>
#include <vector>
using namespace std;

void maxHeapify(int i, int heap[], int size)
{
  int left = i * 2;
  int right = i * 2 + 1;
  int largest;

  if (left <= size && heap[left] > heap[i])
    largest = left;
  else
    largest = i;
  if (right <= size && heap[right] > heap[largest])
    largest = right;

  if (largest != i)
  {
    swap(heap[i], heap[largest]);
    maxHeapify(largest, heap, size);
  }
}

void buildMaxHeap(int heap[], int size)
{
  for (int i = size / 2; i > 0; i--)
    maxHeapify(i, heap, size);
}

void print(int heap[], int size)
{
  for (int i = 1; i <= size; i++)
    printf(" %d", heap[i]);
  printf("\n");
}

int main()
{
  int size;
  scanf("%d", &size);

  int heap[size + 1];
  for (int i = 1; i <= size; i++)
    scanf("%d", &heap[i]);

  buildMaxHeap(heap, size);
  print(heap, size);

  return 0;
}

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

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

ll n,m;
string s;
//Write From this Line

const int mod = 1e9+7;
int main()
{
	int a , b , c;
	cin >> a>>b>>c;

	if(a+b+c>=22){
		cout <<"bust"<<endl;
	}else{
		cout <<"win"<<endl;
	}

}



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

int main(){
    int a, b, x;
    std::cin >> a >> b >> x;
    
    double half = (double)a * (double)a * (double)b / 2.0;
    
    double ans;
    if(half <= (double)x){
        double x_half = (double)x - half;
        double h = x_half / (double)a / (double)a * 2;
        double ans = atan( ((double)b - h) / (double)a) * 180 / M_PI;
        std::cout << std::fixed << std::setprecision(12) << ans << std::endl;
    }else{
        double h = (double)x / (double)a / (double)b * 2;
        double ans = 90 - atan(h / (double)b) * 180 / M_PI;
        std::cout << std::fixed << std::setprecision(12) << ans << std::endl;
    }
    
    return 0;
}



Measured memory_bytes: 384
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100;
const LL inf=9223372036854775807;
LL x[maxn], y[maxn];
int n, k;

int check(LL px1, LL py1, LL px2, LL py2){
    int cnt=0;
    for(int i=0;i<n;i++){
        bool bx=1, by=1;
        if((x[i]>px1&&x[i]>px2)||(x[i]<px1&&x[i]<px2))bx=0;
        if((y[i]>py1&&y[i]>py2)||(y[i]<py1&&y[i]<py2))by=0;
        if(bx&&by)cnt++;
    }
    return cnt;
}


int main(){
    while(~scanf("%d%d", &n, &k)){
        LL maxx=-inf,maxy=-inf,minx=inf,miny=inf;
        for(int i=0;i<n;i++){
            scanf("%lld%lld", &x[i], &y[i]);
        }
        LL ans=inf;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                LL upx=x[i], lowx=x[i], upy=y[i], lowy=y[i];
                upx=max(upx, x[j]),lowx=min(lowx,x[j]);
                upy=max(upy, y[j]),lowy=min(lowy,y[j]);
                if(check(upx, upy, lowx, lowy)>=k){
                    ans=min(ans, (upx-lowx)*(upy-lowy));
                }
                for(int a=j+1;a<n;a++){
                    LL upx=x[i], lowx=x[i], upy=y[i], lowy=y[i];
                    upx=max(upx, x[j]),lowx=min(lowx,x[j]);
                    upy=max(upy, y[j]),lowy=min(lowy,y[j]);
                    upx=max(upx, x[a]),lowx=min(lowx,x[a]);
                    upy=max(upy, y[a]),lowy=min(lowy,y[a]);
                    if(check(upx, upy, lowx, lowy)>=k){
                        ans=min(ans, (upx-lowx)*(upy-lowy));
                    }
                    for(int b=a+1;b<n;b++){
                        LL upx=x[i], lowx=x[i], upy=y[i], lowy=y[i];
                        upx=max(upx, x[j]),lowx=min(lowx,x[j]);
                        upy=max(upy, y[j]),lowy=min(lowy,y[j]);
                        upx=max(upx, x[a]),lowx=min(lowx,x[a]);
                        upy=max(upy, y[a]),lowy=min(lowy,y[a]);
                        upx=max(upx, x[b]),lowx=min(lowx,x[b]);
                        upy=max(upy, y[b]),lowy=min(lowy,y[b]);
                        if(check(upx, upy, lowx, lowy)>=k){
                            ans=min(ans, (upx-lowx)*(upy-lowy));
                        }
                    }
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

int Q;
string s;

string conv(string s){
  string res;
  for(int i=0;i<8;i++){
    int num=0;
    if(s[i]>='0'&&s[i]<='9'){
      num=s[i]-'0';
    }
    else if(s[i]>='a'){
      num=s[i]-'a'+10;
    }
    string a;
    while(1){
      if(num%2==0)a+='0';
      else a+='1';
      if(a.size()==4)break;
      num/=2;
    }
    reverse(a.begin(),a.end());
    res+=a;
  }
  return res;
}

int main(){
  cin>>Q;
  for(int i=0;i<Q;i++){
    cin>>s;
    s=conv(s);
    //cout<<s<<endl;
    double res=0;
    string is=s.substr(1,24);
    int a=0;
    for(int j=0;j<(int)is.size();j++){
      a=a*2+(is[j]-'0');
    }
    double b=0;
    string fs=s.substr(25,7);
    int fst=-1;
    for(int j=(int)fs.size()-1;j>=0;j--){
      b=(b+(fs[j]-'0'))*0.5;
      if(fst==-1&&fs[j]=='1'){
        fst=j;
      }
      //cout<<b<<endl;
    }
    fst++;
    if(s[0]=='1')cout<<'-';
    cout<<a;
    cout<<".";
    if(fst==0)cout<<"0"<<endl;
    else{
      // stringstream ss;
      // ss<<b;
      //string tmp=ss.str();
      //cout<<tmp<<endl;
      string tmp;
      for(int i=0;i<fst;i++){
        b*=10;
        tmp+=('0'+(int)b);
        b-=(int)b;
      }
      for(int i=0;i<fst;i++)
        cout<<tmp[i];
      cout<<endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1216
import java.util.*;

public class Main {
	  public static void main(String args[]){
      	Scanner scan = new Scanner(System.in);
          
        int n = scan.nextInt();
        int A[] = new int[n];
        int B[] = new int[n];
        long A_plus_B[] = new long[n];
        
        boolean isAturn = true;
        
        long A_sum = 0;
        long B_sum = 0;
        long cnt = 0;
        
        for(int i = 0 ; i < n ; i++){
          A[i] = scan.nextInt();
          B[i] = scan.nextInt();
          B_sum += (long)B[i];
          
          A_plus_B[i] = (long)A[i] + (long)B[i];
        }
        
        Arrays.sort(A_plus_B);
        
        for(int i = n-1 ; i >= 0 ; i-=2){
          A_sum += A_plus_B[i];
        }
        cnt = A_sum - B_sum;
            
        System.out.println(cnt);
	  }
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

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

    if(H == W) {
        cout << (N - W + 1) * (N - H + 1) << endl;
    } else if(H != W) {
        cout << (N - W + 1) * (N - H + 1) << endl;
    }
}

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


a_L = list(map(int,input().split()))

d = {}

for val in range(n):
    d[val] = a_L[val]

#print(d)
ans = sorted(d.items(),key=lambda x:x[1])
#print(ans)

ans_L = []

for val in ans:
    ans_L.append(str(val[0]+1))

print(" ".join(ans_L))


Measured memory_bytes: 75176
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

void integerFactorization(int n, vector<int>& base, vector<int>& expo)
{
    base.clear();
    expo.clear();
    int a = 2;
    while(a * a <= n){
        int b = 0;
        while(n % a == 0){
            ++ b;
            n /= a;
        }
        if(b > 0){
            base.push_back(a);
            expo.push_back(b);
        }
        ++ a;
    }
    if(n > 1 || base.size() == 0){
        base.push_back(n);
        expo.push_back(1);
    }
}

int keyNumber(int a)
{
    vector<int> base, expo;
    integerFactorization(a, base, expo);

    int ret = base[base.size()-1];
    for(unsigned i=0; i<base.size()-1; ++i)
        ret -= base[i];
    return ret;
}

int main()
{
    for(;;){
        int a, b;
        cin >> a >> b;
        if(a == 0)
            return 0;

        if(keyNumber(a) > keyNumber(b))
            cout << 'a' << endl;
        else
            cout << 'b' << endl;
    }
}

Measured memory_bytes: 1208
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ST_MAX 100

void push(int);
int pop(void);

int stack[ST_MAX];
int top = 0;

int main(void){
  int x,temp1,temp2;
  char S[ST_MAX];
  while( scanf("%s", S) != EOF ){
    if ( S[0] == '+'){
      temp1 = pop();
      temp2 = pop();
      x = temp1 + temp2;
      //printf("%d",x);
      push(x);

    } else if ( S[0] == '-' ){
      temp1 = pop();
      temp2 = pop();
      x = temp2 - temp1;
      //printf("%d",x);
      push(x);

    } else if ( S[0] == '*' ){
      temp1 = pop();
      temp2 = pop();
      x = temp1 * temp2;
      /* printf("%d",x); */
      push(x);

    } else {
      x = atoi(S);
      push(x);
    }
  }

  printf("%d\n",pop());
  
  return 0;
}

void push(int x){
  top++;
  stack[top] = x;
}

int pop(void){
  top--;
  return stack[top + 1];
}



Measured memory_bytes: 2048
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;


int main() {
    int n, q; cin >> n >> q;
    vector<tuple<int, int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int s, t, x; cin >> s >> t >> x;
        a[i] = make_tuple(x, s - x, t - x);
    }
    sort(a.begin(), a.end());
    set<pair<int, int>> st;
    for (int i = 0; i < q; i++) {
        int d; cin >> d;
        st.insert({d,i});
    }
    vector<int> ans(q, -1);
    for (int i = 0; i < n; i++) {
        int s = get<1>(a[i]);
        auto t = st.lower_bound({s,-1});
        while (t != st.end()) {
            if (t->first < get<2>(a[i])) {
                ans[t->second] = get<0>(a[i]);
                st.erase(t++);
            }
            else {
                break;
            }
        }
    }
    for (int k : ans) {
        cout << k << endl;
    }
    return 0;
}

Measured memory_bytes: 14336
#include<stdio.h>
#define MAX 2000000
int H,A[MAX+1];
void swap(int i,int j,int n,int n2){
    A[n]=j;
    A[n2]=i;
}
void maxHeapify(int i){
    int l,r,largest;
    l=2*i;
    r=2*i+1;
    
    if(l<=H && A[l]>A[i])largest=l;
    else largest=i;
    if(l<=H && A[r]>A[largest])largest=r;
    
    if(largest!=i){
        swap(A[i],A[largest],i,largest);
        maxHeapify(largest);
    }
}
int main(){
    int i,j;
    scanf("%d",&H);
    for(i=1;i<=H;i++){
        scanf("%d",&A[i]);
    }
    for(i=H/2;i>=1;i--){
        maxHeapify(i);
    }
    for(i=1;i<=H;i++){
        printf(" %d",A[i]);
    }
    printf("\n");
    return 0;
}



Measured memory_bytes: 3692
#include <iostream>
#include <string>

using namespace std;

int main(){
  int n, i, j, minj;
  bool flag = true, ns = false;
  string in1[36], in2[36], tmp;

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

  //babble
  while(flag){
    flag = false;
    for(i = n - 1;i >= 1;--i){
      if(in1[i][1] < in1[i-1][1]){
	tmp = in1[i];
	in1[i] = in1[i-1];
	in1[i-1] = tmp;
	flag = true;
      }
    }
  }
  for(i = 0;i < n;++i){
    cout << in1[i];
    if(i != n-1)cout << " ";
  }
  cout << "\n";
  cout << "Stable" << endl;

  //select
  for(i = 0;i < n;++i){
    minj = i;
    for(j = i;j < n;++j){
      if(in2[j][1] < in2[minj][1])
	minj = j;
    }
    if(i != minj){
      tmp = in2[i];
      in2[i] = in2[minj];
      in2[minj] = tmp;
    }
  }
  for(i = 0;i < n;++i){
    cout << in2[i];
    if(i != n-1)cout << " ";
  }
  cout << "\n";
  for(i = 0; i < n;++i)
    if(in1[i] != in2[i])ns = true;
  if(ns)cout << "Not stable" << endl;
  else cout << "Stable" << endl;
  
  return 0;
}



Measured memory_bytes: 3200
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace MyProgram
{
    public class Program
    {	
        public static void Main(string[] args)
        {
           int n = int.Parse(Console.ReadLine());
           string[] input = Console.ReadLine().Split(' ');
           
           bool four = false;
           for(int i = 0 ; i < n ; i++)
           {
               if(input[i] == "Y") four = true;
           }
           
           if(four) Console.WriteLine("Four");
           else Console.WriteLine("Three");
        }
    }
}

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

int K;

int S(ll N) {
  if(N < 10) return N;
  return (N % 10) + S(N/10);
}

ll f(ll N) {
  vector<pair<double,ll>> res;
  for(ll m = 1; m <= N*10; m *= 10) {
    ll k = m*(N/m + 1) - 1;
    res.push_back(pair<double,ll>((double)k/S(k), k));
  }
  sort(res.begin(), res.end());
  return res[0].second;
}

int main () {
  cin >> K;

  ll N = 1;
  rep(i,K) {
    printf("%lld\n", N);
    N = f(N+1);
  }
  return 0;
}


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

#define loop(i,first,end) for(int i=(first);i<(end);i++)
#define uint unsigned int
#define ull unsigned long long
#define ll long long
#define vint vector<int>
#define vuint vector<unsigned int>
#define vull vector<ull>
#define vll vector<ll>
#define init(type,var) type var;cin>>var;
#define vinit(vtype,var,n) vtype var(n);loop(i,0,n)cin>>var[i];

const ull MOD = 1000000007ULL;
const ull INF = (ull)(-1LL);

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

	uint d;
	uint count = 0;
	for (d = 1; d*10 <= n; d *= 100){
		count += d * 9;
	}
	if (d <= n)count += n - d + 1;

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define _USE_MATH_DEFINES
#include<math.h>
#include <cmath>
#include <string>
using namespace std;


int main(void)
{
    int K;
    string S;
    cin >> K;
    cin >> S;
    for (int i = 0; i < K; i++){
        if (S[i] == '\0'){
            break;
        }
        cout << S[i];
        if (i+1 >= K && S[i+1] != '\0'){
            cout << "...";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int n, k;
vector<int> G[100010];
int col[100010];

void solve(int now, int pre)
{
    int num = k - 2;
    if (now == 0)
        num = k - 1;
    for (int i = 0; i < G[now].size(); i++)
    {
        if (G[now][i] == pre)
            continue;
        col[G[now][i]] = max(0LL, num);
        num--;
        solve(G[now][i], now);
    }
}

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

    cin >> n >> k;
    rep(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    col[0] = k;
    solve(0, -1);
    int ans = 1;
    rep(i, n) ans = (ans * col[i]) % mod;
    cout << ans << endl;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
const int MAXN = 105;
const int MAXV = 2 * MAXN * MAXN;
const LL INF = (LL)1e9 + 5;
const LL MOD = 1000000007;

struct Flow {
    struct Edge{
        int to,cap,rev;
        Edge(int a,int b,int c) {
        	to = a; cap = b; rev = c;
		}
    };
	// IMPORETANT, MAXV != MAXN
    vector<Edge> G[MAXV];
    int V, flow[MAXV];
    void init(int _V){
        V = _V;
        for(int i=0; i<=V; i++) G[i].clear();
    }

    void add_edge(int f,int t,int c, bool directed){
    	int s1 = G[f].size(), s2 = G[t].size();
        G[f].push_back(Edge(t,c,s2));
		G[t].push_back(Edge(f,c*!directed,s1));
    }

    int dfs(int v, int t) {
        if(v == t) return flow[t];
        for(Edge &e : G[v]){
            if(e.cap==0||flow[e.to]!=-1) continue;
            flow[e.to] = min(flow[v], e.cap);
            int f = dfs(e.to, t);
            if (f!=0) {
                e.cap -= f;
                G[e.to][e.rev].cap += f;
                return f;
            }
        }
        return 0;
    }

    int max_flow(int s,int t){
        int ans = 0, add = 0;
        do {
        	fill(flow,flow+V+1,-1);
        	flow[s] = INF;
        	add = dfs(s, t);
        	ans += add;
		} while (add != 0);
        return ans;
    }
};

int R, C, sr, sc, tr, tc;
char mp[MAXN][MAXN];
Flow mf;

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

	cin >> R >> C;
	
	mf.init(2 * R * C + 5);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			int vin = i * C + j, vout = vin + R * C;
			char ch;
			cin >> ch;
			mp[i][j] = ch;
			if (ch == 'o') {
				mf.add_edge(vin, vout, 1, true);
			}
			else if (ch == 'S') {
				mf.add_edge(vin, vout, INF, true);
				sr = i;
				sc = j;
			}
			else if (ch == 'T') {
				mf.add_edge(vin, vout, INF, true);
				tr = i;
				tc = j;
			}
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			int vout = i * C + j + R * C;
			for (int ii = 0; ii < R; ii++) {
				if (ii == i || mp[ii][j] == '.') continue;
				int uin = ii * C + j;
				mf.add_edge(vout, uin, INF, true);
			}
			for (int jj = 0; jj < C; jj++) {
				if (jj == j || mp[i][jj] == '.') continue;
				int uin = i * C + jj;
				mf.add_edge(vout, uin, INF, true);
			}
		}
	}
	
	if (sr == tr || sc == tc) {
		cout << "-1\n";
		return 0;
	}
	
	int ans = mf.max_flow(sr * C + sc, tr * C + tc);
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 63104
#ifdef Prateek
  #include "C:\Prateek.h"
#else
  #include <bits/stdc++.h>
  using namespace std;
  #define debug(...) 42
#endif
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   string s = "ACL";
   int n;
   cin >> n;
   for(int i = 0; i < n; ++i) {
      cout << s;
   }
   return 0;
} 

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

int main(){
	int dp[11], ndp[11];
	string s;
	while(cin >> s){
		if(s == "0") break;
		int ans = 0;
		memset(dp, 0, sizeof(dp));
		if(s[0]!='0') dp[s[0]-'0']++;
		for(int i=1;i<s.size();i++){
			memset(ndp, 0, sizeof(ndp));
			if(s[i]!='0') ndp[s[i]-'0'] = 1;
			for(int j=0;j<11;j++)
				ndp[(10*j+s[i]-'0')%11] += dp[j];
			memcpy(dp, ndp, sizeof(dp));
			ans += dp[0];
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1120
#include <bits/stdc++.h>
#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 sp(n) cout << fixed << setprecision(n)
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; }
typedef long long ll;
using namespace std;
int main(void){
    string s,z;cin>>s>>z;
    int sz=s.size(),zz=z.size();
    ll res=zz;
    rep(i,sz-zz+1){
        ll buf=0;
        rep(j,zz){
            if(s[i+j]!=z[j])buf++;
        }
        chmin(res,buf);
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3564
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		for(int i=0;i<t;i++) {
			long a = in.nextLong();
			long b = in.nextLong();
			long c = in.nextLong();
			long d = in.nextLong();
			judge(a, b, c, d);
		}
	}
	
	public static void judge(long a,long b,long c,long d) {
		if(a<b || d<b) System.out.println("No");
		else {
			long g = gcd(b,d);
			long max = b - g + a%g;
			if(max>c) System.out.println("No");
			else System.out.println("Yes");
		}
	}
	
	public static long gcd(long p,long q) {
		while(q>0) {
			long t = p%q;
			p = q;
			q = t;
		}
		return p;
	}

}

Measured memory_bytes: 23632
import java.util.Scanner;

public class Main
{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		int x=-1000;
		for (int i=0; i<N; i++){
			int temp = sc.nextInt();
			x = Math.max(x, temp);
		}
		x = Math.max(x, X+1);
		
		int y=1000;
		for (int i=0; i<M; i++){
			int temp = sc.nextInt();
			y = Math.min(y, temp);
		}
		y = Math.min(y, Y);
		
		if (x<y)
			System.out.println("No War");
		else 
			System.out.println("War");

		sc.close();
	}

}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

long long int n=1,cnt=0,ans=0,a=0,b,c,cmp,data,m,h,x,y,xcmp=0,ycmp=0,sum=0;

string s,w;

vector<int> z;

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

        
       cin >> n >> s >> w;
      rep(i,n){
          if(s[i]==w[0]){
              for(int j=i;j<n;j++){
                  if(s[j]==w[a]){
                      cnt++;
                       a++;
                  }
                  else{
                      break;
                  }
                  //Cout(cnt);
                   if(j==n-1){
                       Cout(2*n-cnt);
                       return 0;
                   }  
              }
          }
           a=0;
           cnt=0;
      }
     Cout(2*n);
    
return 0;
}


Measured memory_bytes: 256
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <stdio.h>
#include <random>
#include <ctime>
#include <fstream>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}

using namespace std;


const int D = 365;
const int si = 26;
vector<int> c(si);
vector<vector<int>> s(D, vector<int>(si));

struct cand {
    int score;
    int hist[D];
    int cc;
    vector<int> last;
    cand(int _cc) {
        score = 1000000;
        cc = _cc;
        last = vector<int>(si);
    }
};

bool operator<(const cand &left, const cand &right) {
	return left.score < right.score;
}

random_device r;
MaxHeap<cand> ans_heap;
int cc = 0;
const int width = 150, branch = 26, reading = 1;
int times = 1;
cand example(0);

void input() {
    int n; cin >> n;
    rip(i,si,0) {
        cin >> c[i];
        cc += c[i];
    }
    rip(i,D,0) rip(j,si,0) cin >> s[i][j];
}

cand gen_next(cand now, int day, int aa) {
    int a = aa%26;
    now.hist[day] = a;
    now.score += s[day][a];
    now.cc += cc-c[a]*(day-now.last[a]);
    now.last[a] = day;
    now.score -= now.cc;
	return now;
}

void beem(int day) {
	MaxHeap<cand> cand_heap;
	rip(i, width, 0) {
		cand now = ans_heap.top();
		ans_heap.pop();
		rip(j, branch, 0) {
			cand next = gen_next(now, day, i);
			cand_heap.push(next);
		}
    }
    swap(ans_heap, cand_heap);
}

void output(cand ans) {
    rip(i, D, 0) printf("%d\n", ans.hist[i]+1);
}

int main() {
    input();
	rip(i, width, 0) {
		ans_heap.push(example);
	}
	rip(i, D/reading, 0) {
		beem(i*reading);
		times++;
	}
	output(ans_heap.top());
	// cout << ans_heap.top().score << endl;
}

Measured memory_bytes: 30712
const main = (input) => {
  var inputs = input[0].split("");
  var ans1 = calc(inputs);
  inputs = inputs.reverse();
  var ans2 = calc(inputs);
  console.log(Math.max(ans1, ans2));
}

function calc(inputs){
  var N = inputs.length;
  var arr = [inputs[0]];
  for(var i=1;i<N;i++){
    var w = inputs[i];
    if(arr[arr.length-1] != w){
      arr.push(w);
    }else{
      if(inputs[i+1]){
        arr.push(w + inputs[i+1]);
      }
      i++;
    }
  }
  if(N>1){
    var arr2 = [inputs[0] + inputs[1]];
    for(var i=2;i<N;i++){
      var w = inputs[i];
      if(arr2[arr2.length-1] != w){
        arr2.push(w);
      }else{
        if(inputs[i+1]){
          arr2.push(w + inputs[i+1]);
        }
        i++;
      }
    }
  }else{
    arr2 = [];
  }
  return Math.max(arr.length, arr2.length);
}

main(require('fs').readFileSync('/dev/stdin', 'UTF-8').trim().split("\n"));


Measured memory_bytes: 36044
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MAX_N 40
#define INF 1000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll a, b, c, n;
ll ans;
set<tuple<ll,ll,ll>> s;

ll dx[6] = {1,-1,0,0,0,0};
ll dy[6] = {0,0,1,-1,0,0};
ll dz[6] = {0,0,0,0,1,-1};

int main(){
    cin >> a >> b >> c >> n;
    ans = 2*a*b+2*b*c+2*c*a;
    rep(i,n){
        ll x, y, z;
        cin >> x >> y >> z;
        ll add = 6;
        rep(j,6){
            ll nx = x+dx[j], ny = y+dy[j], nz = z+dz[j];
            if(0>nx||nx>=a||0>ny||ny>=b||0>nz||nz>=c){
                add -= 2;
            } else if(s.count(make_tuple(nx,ny,nz))){
                add -= 2;
            }
        }
        ans += add;
        s.insert(make_tuple(x,y,z));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3148
# -*- coding: utf-8 -*-

from fractions import gcd
from math import ceil,floor
import collections

# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# list = list(map(int, input().split()))


N,A,B=map(int, input().split())

print(min(N*A,B))

Measured memory_bytes: 5560
#include <iostream>

using namespace std;

int com(int n, int k)
{
	if (n == k || k == 0)
		return 1;

	if (n < k)
		return 0;

	if (k > n - k)
		k = n - k;

	long long aux=1;
	for (int i = n - k + 1; i <= n; i++)
		aux *= i;

	for (int i = 2; i <= k; i++)
		aux /= i;

	return aux;
}

int main()
{
	int n, m;
	cin >> n >> m;
	cout << com(n, 2) + com(m, 2);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define rep(i, n) for (int i = 0; (i) < (int)(n); i++)
using namespace std;

int main() {
	int K, A, B;
	cin >> K >> A >> B;
	for (int i = 0; i * K <= B; i++) {
		if (A <= i * K) {
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3596
/*input
11
*/

#include <iostream>

using namespace std;

int main(){

	int X;
	cin >> X;

	long v = 0;
	long c = 1;
	while(1){
		v += c;
		if(v>=X) break;
		c++;
	}
	cout << c << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int sx,sy,tx,ty;cin >> sx >> sy >> tx >> ty;
	int x = tx - sx, y = ty - sy;
	rep(i,x) cout << 'R';
	rep(i,y) cout << 'U';
	rep(i,x) cout << 'L';
	rep(i,y) cout << 'D';
	cout << 'D';
	rep(i,x + 1) cout << 'R';
	rep(i,y + 1) cout << 'U';
	cout << 'L' << 'U';
	rep(i,x + 1) cout << 'L';
	rep(i,y + 1) cout << 'D';
	cout << 'R' << endl;
}


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

using Hash=__int128;
using ll=long long;
const Hash MOD=1e18+9;
const Hash A=1e9+7;
const Hash B=1e7+1;
const Hash C=1e9+9;

int main(){
    map<char,Hash> dict;
    dict['a']=Hash(102432324)%MOD;
    
    for(char x='a';x<'z';x++){
        dict[x+1]=((dict[x]*B)%MOD+C)%MOD;
    }
    dict['A']=((dict['z']*B)%MOD+C)%MOD;
    for(char x='A';x<'Z';x++){
        dict[x+1]=((dict[x]*B)%MOD+C)%MOD;
    }
    string s;
    cin>>s;
    string t;
    cin>>t;
    map<Hash,ll> cnt;

    Hash h=0;
    Hash powA=1;
    for(int i=0;i<t.size();i++){
        h*=A;
        h%=MOD;
        h+=dict[s[i]];
        h%=MOD;
        if(i+1==t.size()) break;
        powA*=A;
        powA%=MOD;
    }
    cnt[h]++;
    
    for(int i=t.size();i<s.size();i++){
        h-=powA*dict[s[i-t.size()]];
        h=(h%MOD+MOD)%MOD;
        h*=A;
        h%=MOD;
        h+=dict[s[i]];
        h%=MOD;      
        cnt[h]++;
    }
    h=0;
    for(int i=0;i<t.size();i++){
        h*=A;
        h%=MOD;
        h+=dict[t[i]];
        h%=MOD;
    }
    
    ll res=0;
    powA=1;
    for(int i=t.size()-1;i>=0;i--){
        Hash tarh=h-(powA*dict[t[i]])%MOD;
        tarh=(tarh%MOD+MOD)%MOD;
        for(int j=0;j<='z'-'a';j++){
            char tar='a'+j;
            if(tar==t[i]) continue;
            Hash x=tarh+(powA*dict[tar])%MOD;
            x%=MOD;          
            if(cnt.count(x)){
                res+=cnt[x];
            }
        }
        for(int j=0;j<='z'-'a';j++){
            char tar='A'+j;
            if(tar==t[i]) continue;
            Hash x=tarh+(powA*dict[tar])%MOD;
            x%=MOD;          
            if(cnt.count(x)){
                res+=cnt[x];
            }
        }
        powA*=A;
        powA%=MOD;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 25636
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        String[] board = new String[H];
        for (int i = 0; i < H; i++) {
            board[i] = sc.next();
            // System.out.println(board[i]);
        }
        long[][] dp = new long[H][W];
        int MOD = 1_000_000_007;
        dp[0][0] = 1;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (board[i].charAt(j) == '#') continue;
                if (i > 0) {
                    dp[i][j] += dp[i-1][j];
                    dp[i][j] %= MOD;
                }
                if (j > 0) {
                    dp[i][j] += dp[i][j-1];
                    dp[i][j] %= MOD;
                }
            }
        }
        long ans = dp[H-1][W-1];
        System.out.println(ans);
    }
}

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

int main() {

  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  string s, t;
  cin >> s >> t;

  map<string, int> m;
  cin >> m[s] >> m[t];

  string tmp;
  cin >> tmp;

  m[tmp]--;
  cout << m[s] << " " << m[t] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
const int MOD = 1000000007;
ll cnt =0;

int main (){
    ll n ;  
  string s; cin >> s;
  s.push_back('a');
  n = s.size();
  ll max = 0;
  for(int i=0;i<n;i++){
      if(s.at(i) == 'A' || s.at(i) == 'C' || s.at(i) == 'G' || s.at(i) == 'T' ){
          cnt++;
      }else{
          if(max < cnt){
              max = cnt ;
          }

          cnt = 0;
          
      }
    
  }
  cout << max << endl;



}

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

using namespace std;

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

struct Edge {
    int to, wt;
    Edge(int to_, int wt_) : to(to_), wt(wt_) {}
};

pair<int, int> dfs(vector<vector<Edge> >& G, int p, int v) {
    pair<int, int> retval(0, v);
    for (auto e: G[v]) {
        if (G[e.to].size() == 1 || e.to == p) continue;
        pair<int, int> t = dfs(G, v, e.to);
        t.first += e.wt;
        if (retval.first < t.first) retval = t;
    }
    return retval;
}

int diameter(vector<vector<Edge>>& G, int s){
    return dfs(G, -1, dfs(G, -1, s).second).first;
}

int solve(vector<int>& p, vector<int>& d, int n) {
    int retval = 0;
    vector<vector<Edge>> G(n);
    for (int i = 1; i < n; ++i) {
        G[i].emplace_back(p[i], d[i]);
        G[p[i]].emplace_back(i, d[i]);
        retval += d[i];
    }
    int s = -1;
    rep(i, n) {
        if (G[i].size() == 1) continue;
        for (auto e: G[i]) {
            if(G[e.to].size() == 1) continue;
            retval += e.wt;
        }
        s = i;
    }
    if (0 <= s) retval -= diameter(G, s);
    return retval;
}

int main(){
    for (int n; cin >> n, n;) {
        vector<int> p(n), d(n);
        for (int i = 1; i < n; ++i) cin >> p[i], p[i]--;
        for (int i = 1; i < n; ++i) cin >> d[i];
        cout << solve(p, d, n) << endl;
    }
    return 0;
}

Measured memory_bytes: 1328
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String str;
		int num,count;
		while (null != (str = in.readLine())) {
			count = 0;
			num = Integer.parseInt(str);
			for (int i = 0; i <= 9; i++) {
				for (int j = 0; j <= 9; j++) {
					for (int k = 0; k <= 9; k++) {
						for (int l = 0; l <= 9; l++)
							count += (i + j + k + l == num) ? 1 : 0;
					}
				}
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 18512
/*------------------------- Bism Allah Alruhmin Alrahim -------------------------------*/
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i > -1; i--)
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define vc vector
#define f first
#define s second
#define pb(i) push_back(i)
#define mx(ar, n) (*max_element(ar, ar + n))
#define mn(ar, n) (*min_element(ar, ar + n))

using namespace std;

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

ll LCM(ll x , ll y){
	return (x*y) / __gcd(x,y) ;
}

ll NumOfDiv(ll a , ll b , ll k){
	return b/k - a/k + (a%k == 0) ;
}
void start(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int res(int a , int b , int c){
	int x[3] = {a,b,c} ;
	sort(x,x+3);
	return x[1] ;
}

int main()
{
	start();
	int x , y ; 
    cin >> x ; 
    bool b = false ;
    for (int i = 0; i <= 9; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            if(i*j == x){
                b = true ;
            }
        }
    }
    cout << ((b) ? "Yes" : "No") << endl ;
    
	return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
double a, b, x;
double A;
void solve() {
    double ans;
    A = a * a;
    if (x >= A * b / 2.0) {
        ans = atan2((A * b - x) * 2.0 / A, a);
    } else {
        ans = atan2(b, x * 2.0 / b / a);
    }
    //cout << ans << endl;
    ans *= 180.0 / PI;
    std::cout << std::fixed;
    std::cout << std::setprecision(10) << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> a >> b >> x;
    solve();
    return 0;
}


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

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i, a, b) for (int i=a;i>=b;--i)

const int MX_N = 2e5+5;
const int MOD = 1e9+7;

int N;
struct Ninja { int X, V, L, R; } ninja[MX_N];
int val[MX_N];
int dp[MX_N];

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

    cin >> N;
    FOR(i,1,N){
        int X, V; cin >> X >> V;
        ninja[i] = {X,V,-1,-1};
        val[i] = V;
    }
    sort(val+1,val+1+N);
    FOR(i,1,N){ ninja[i].V = lower_bound(val+1,val+1+N,ninja[i].V)-val; }

    sort(ninja+1,ninja+1+N,[](Ninja a, Ninja b){ return a.X < b.X; });
    ninja[1].R = ninja[1].V;
    FOR(i,2,N){
        ninja[i].R = max(ninja[i-1].R,ninja[i].V);
    }
    ninja[N].L = ninja[N].V;
    RFOR(i,N-1,1){
        ninja[i].L = min(ninja[i+1].L,ninja[i].V);
    }
    
    sort(ninja+1,ninja+1+N,[](Ninja a, Ninja b){ return a.L == b.L ? a.R < b.R : a.L < b.L; });
    ninja[0] = {-1,-1,0,0};
    dp[0] = 1;
    int s = 0, cur = dp[0], ans = 0;
    FOR(i,1,N){
        while (s < i && ninja[s].R+1 < ninja[i].L) {
            cur -= dp[s++];
            if (cur < 0) cur += MOD;
        }
        dp[i] = cur;
        cur += dp[i];
        if (cur >= MOD) cur -= MOD;

        if (ninja[i].R == N) {
            ans += dp[i];
            if (ans >= MOD) ans -= MOD;
        }
        //cout << cur << " :: " << ninja[i].L << ' ' << ninja[i].R << " dp i " << i << " :: " << dp[i] << endl;
    }
    cout << ans;
}



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

// Begin {{{
using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (i64 i = 0; i < (n); ++i)
#define reps(i, s, n) for (i64 i = (s); i <= (n); ++i)
#define VAR(Type, ...) Type __VA_ARGS__; IN(__VA_ARGS__)

#ifdef DEBUG
#define dump(...) _dump(#__VA_ARGS__, __VA_ARGS__);
#else
#define dump(...)
#endif

using i64 = int_fast64_t;
using pii = pair<i64, i64>;

template <class A, class B>
inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B>
inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

// IN
void IN() {}
template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
  cin >> head;
  IN(forward<Tail>(tail)...);
}

// OUTS
void OUTS() {}
template <class Head, class... Tail>
void OUTS(Head&& head, Tail&&... tail) {
  cout << head << " \n"[sizeof...(tail)==0];
  OUTS(forward<Tail>(tail)...);
}

template <class T>
void OUTS(vector<T> &vec) { for (auto &e : vec) cout << e << " \n"[&e==&vec.back()]; }

template <class T>
void OUTS(vector<vector<T>> &df) { for (auto &vec : df) OUTS(vec); }

// OUTL
void OUTL() {}
template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
  cout << head << "\n";
  OUTL(forward<Tail>(tail)...);
}

template <class T>
void OUTL(vector<T> &vec) { for (auto &e : vec) cout << e << "\n"; }

// OUTN
void OUTN() {}
template <class Head, class... Tail>
void OUTN(Head&& head, Tail&&... tail) {
  cout << head;
  OUTN(forward<Tail>(tail)...);
}

template <class T>
void OUTN(vector<T> &vec) { for (auto &e : vec) cout << e; }

// DEGUG
template <class T>
void _dump(const char *s, T&& x) {
  clog << '{';
  while(*s != '\0') clog << *(s++);
  clog << ": " << x << '}' << "\n";
}

template <class Head, class... Tail>
void _dump(const char *s, Head&& head, Tail&&... tail) {
  clog << '{';
  while(*s != ',') clog << *(s++);
  clog << ": " << head << "}, ";
  for (++s; !isgraph(*s); ++s);
  _dump(s, forward<Tail>(tail)...);
}
// }}} End

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

  VAR(int, N);

  vector<i64> x(N);
  vector<i64> sorted(N);
  rep(i, N) {
    IN(x[i]);
    sorted[i] = x[i];
  }

  sort(all(sorted));

  int mid = (N - 1) / 2;
  rep(i, N) {
    if (x[i] == sorted[mid]) OUTL(sorted[mid+1]);
    else if (x[i] < sorted[mid]) OUTL(sorted[mid+1]);
    else OUTL(sorted[mid]);
  }

  return 0;
}


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

using namespace std;

int main()
{
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a+3);
     ((a[0]==a[1] && a[1]!=a[2]) || (a[0]!=a[1] && a[1]==a[2])) ? cout << "Yes" : cout << "No";


}
//1 -5 6


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){

  vector <string> a,b; 
  string tmp;
  int n,i;

  cin>>n;
  for(i=0;i<n;i++){
    cin>>tmp;
    a.push_back(tmp);
  }
  b.assign(a.begin(),a.end());
  for(i=0;i<n-1;i++) for(int j=n-2;j!=i-1;j--) if(a[j][1]>a[j+1][1]) swap(a[j],a[j+1]);
  for(i=0;i<n-1;i++) cout<<a[i]<<" ";
  cout<<a[n-1]<<endl<<"Stable"<<endl;

  for(i=0;i<n-1;i++){
    int now,minnum=101;
    for(int j=i;j<n;j++) if(minnum>b[j].at(1)-'0'){
	now=j;
	minnum=b[j].at(1)-'0';
      }
    if(i!=now)  swap(b[i],b[now]);
  }

  for(i=0;i<n-1;i++) cout<<b[i]<<" ";
  cout<<b[n-1]<<endl;
  if(a==b) cout<<"Stable"<<endl;
  else cout<<"Not stable"<<endl;
  
  return 0;
  
}



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

int main(){
    // 引数の受け取り
    int A,B,C,D,E,ans;
    scanf("%d %d", &A,&B );
    C = B%10; //1のくらい
    D = B-C; //  10のくらいだけの数字
    E = D/10;// 10のくらい

    ans = 0;
    for(int i=1;i <= A;i++){
        for(int j=2;j <= E;j++){
            if(i%j==0 && i>j && (i/j+(j*10)) <= B && i/j <10){
                int K = j * 10  + i/j;
 //               printf("%d月 %d日\n", i,K);
                if(j*(i/j)!=i || K > B){
                    printf("dame");
                }

                ans++;
            }
        } 
    }

    printf("%d", ans);

    // ----------------------
    //  メイン処理
    // ----------------------
    //
    return 0;
}


Measured memory_bytes: 256
// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.
import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	final long MOD = (long) 1e9 + 7;
	ArrayList<Integer>[] g;
	int N;
	int[] sz;
	long[] dp;
	long[] dp2;// 黒を含まない可能性

	long pow(long a, long n) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % MOD) {
			if (n % 2 == 1) {
				ret = ret * a % MOD;
			}
		}
		return ret;
	}

	long inv(long a) {
		return pow(a, MOD - 2);
	}

	long expected_edges = 0;

	void dfs(int cur, int par) {
		sz[cur] = 1;
		for (int dst : g[cur]) {
			if (dst == par)
				continue;
			dfs(dst, cur);
			sz[cur] += sz[dst];
		}
		if (par != -1) {
			expected_edges += (1 - pow(inv(2), sz[cur])) * (1 - pow(inv(2), N - sz[cur])) % MOD;
			expected_edges %= MOD;
		}
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		g = new ArrayList[N];
		for (int i = 0; i < N; ++i)
			g[i] = new ArrayList<>();
		sz = new int[N];
		dp = new long[N];
		dp2 = new long[N];
		for (int i = 0; i < N - 1; ++i) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			--a;
			--b;
			g[a].add(b);
			g[b].add(a);
		}
		dfs(0, -1);
		long p0 = pow(inv(2), N);// bb,bw,wb,ww (1/4+{1-(1/2)^2})-1
		long p1 = N * pow(inv(2), N) % MOD;
		long ans = ((expected_edges + 1-p0) - N * inv(2) % MOD + MOD) % MOD;
		ans = (ans + MOD) % MOD;
		System.out.println(ans);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase

Measured memory_bytes: 175420