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

public class Main {

    private static FastReader in = new FastReader(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final long MOD = (long) 1e9 + 7;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int k = in.nextInt();
        int q = in.nextInt();
        int[] a = in.nextIntArray(q);
        int[] pts = new int[n];

        for (int i=0; i < a.length; i++) {
            pts[a[i] - 1]++;
        }

        for (int i=0; i < pts.length; i++) {
            pts[i] += k-q;
        }

        // out.println(Arrays.toString(pts));
        for (int i : pts) {
            out.println(i > 0 ? "Yes" : "No");
        }
    }

    // https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(InputStream inputStream) {
            br = new BufferedReader(new
                    InputStreamReader(inputStream));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        // https://qiita.com/masakinpo/items/5f77f2a879578a85a0bb
        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

}


Measured memory_bytes: 34624
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    for(int i=0; A*C >=0; i++){
        C -= B;
        if(C<=0){
            cout << "Yes" << endl;
            return 0;
        }
        A -= D;
        if(A<=0){
            cout << "No" << endl;
            return 0;
        }
        
    }
}

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

using namespace std;

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define outl(x) cout<< (x) << '\n'
#define pb(a) push_back(a)
#define fi first
#define se second
#define MOD 1000000007

template<typename Tn> Tn gcd(Tn a, Tn b)
{
  return (b ? gcd(b, a % b) : a);
}

template<typename Tn> Tn lcm(Tn a, Tn b)
{
  return a / gcd(a, b) * b;
}

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

int main()
{
  int n, t, a;
  int h;

  int ans = 0;
  double temp = 1 << 30;
  
  ci >> n >> t >> a;
  for(int i = 0; i < n; i++) {
    ci >> h;
    if(abs(temp - a) > abs(t - h * 0.006 - a)) {
      ans = i + 1;
      temp = t - h * 0.006;
    }
  }

  co << ans << en;
  
  return 0;
}


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

using namespace std;

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

    if(R < 1200){
	cout << "ABC" << endl;
    }else if(R < 2800){
	cout << "ARC" << endl;
    }else{
	cout << "AGC" << endl;
    }
    
}


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


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N,A,B;
  cin>>N>>A>>B;
  if(N*A<=B)cout<<N*A;
  else cout<<B;
  
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back

// g++ -std=c++17 -Wshadow -Wall -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -o 
vector<pair<int,int>>directions={{1,0},{-1,0},{0,-1},{0,1}};
int h,w;
bool isValid(int i, int j){
 return i>=0 && j>=0 && i<h && j<w;
}
const int inf=1e9+5;
int main(){
 cin>>h>>w;
 int ch,cw,dh,dw;
 cin>>ch>>cw>>dh>>dw;
 ch--;cw--;dh--;dw--;
 string grid[h];
 for(int i=0;i<h;i++){
  cin>>grid[i];
 }
 int dist[h][w];
 for(int i=0;i<h;i++){
  for(int j=0;j<w;j++){
   dist[i][j]=inf;
  }
 }
 deque<pair<int,int>>q;
 dist[ch][cw]=0;
 q.push_front({ch,cw});
 while(!q.empty()){
  pair<int,int>k=q.front();
//   cout<<k.first<<" "<<k.second<<"\n";
  q.pop_front();
  for(auto dir:directions){
   int x=k.first+dir.first;
   int y=k.second+dir.second;
   if(!isValid(x,y))continue;
   if(grid[x][y]=='#')continue;
   if(dist[x][y]>dist[k.first][k.second]){
    dist[x][y]=dist[k.first][k.second];
    q.push_front({x,y});
   }
  }
  for(int i=k.first-2;i<=k.first+2;i++){
   for(int j=k.second-2;j<=k.second+2;j++){
    if(!isValid(i,j))continue;
    if(grid[i][j]=='#')continue;
    if(dist[i][j]>dist[k.first][k.second]+1){
     dist[i][j]=dist[k.first][k.second]+1;
     q.push_back({i,j});
    }
   }
  }
 }
 if(dist[dh][dw]==inf)cout<<"-1\n";
 else cout<<dist[dh][dw]<<"\n";
 return 0;
}


Measured memory_bytes: 9508
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * Created by Seiya on 2016/10/16.
 */
public class Main {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);

        int N;
        String s, t;
        N = scanner.nextInt();
        int ans = N;
        scanner.nextLine();
        s = scanner.nextLine();
        t = scanner.nextLine();
        
        for(int i  = 0; i < N; i++){
            int ok = 1;
            for(int j = i; j < N; j++){
                if(s.charAt(j) != t.charAt(j - i))ok++;

            }

            if(ok == 1){
                ans = i;
                break;
            }

        }

        System.out.println(ans + N);

    }


}


Measured memory_bytes: 9808
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int mod = 1e9 + 7;
 
inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}
 
inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}
 
int64 fact[202020], rfact[202020];
int N, A, B, C, D;
int64 dp[1001][1001];
 
int main()
{
  fact[0] = rfact[0] = 1;
  for(int i = 1; i < 102020; i++) {
    fact[i] = fact[i - 1] * i % mod;
    rfact[i] = modInv(fact[i]);
  }
 
  cin >> N >> A >> B >> C >> D;
 
  dp[A - 1][0] = fact[N];
  for(int j = A; j <= B; j++) { // j 人の組
    int64 bat = 1;
    for(int k = 0; k < C - 1; k++) (bat *= rfact[j]) %= mod;
    for(int k = C; k <= D; k++) { // k 個
      (bat *= rfact[j]) %= mod;
      for(int i = 0; i < N; i++) {
        int sum = i + j * k;
        if(sum > N) break;
        (dp[j][sum] += 1LL * dp[j - 1][i] * bat % mod * rfact[k] % mod) %= mod;
      }
    }
    for(int k = N; k >= 0; k--) (dp[j][k] += dp[j - 1][k]) %= mod;
  }
  cout << dp[B][N] << endl;
}

Measured memory_bytes: 9600
import java.util.Scanner;
public class Main {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int MAX = 123456;
		int[] sosu = new int[MAX*2+1];
		for(int i = 0;i<=MAX*2;i++ ){
			sosu[i]=1;
		}
		int j=0;
		for(int i=2; i<= MAX; i++){
			 if(sosu[i] == 0) continue;

			 j = i+i;
			 while(j <= 2*MAX){
				 sosu[j] = 0;
				 j += i;
			 }
		}
		while(true){
			int n=0,p=0;
			n = scan.nextInt();
			if(n==0)
				break;

			for(int i = n+1;i <= n*2;i++){
				p+=sosu[i];
			}
			System.out.println(p);
		}
	}
}



Measured memory_bytes: 27844
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		long x = Long.parseLong(str);
		long a = x / 11;
		long b = x % 11;

		if(b>6){
			System.out.println(a*2 + 2);
		}else if(b>0){
			System.out.println(a*2 + 1);
		}else{
			System.out.println(a*2);
		}
	}

}


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

#define int long long
#define ld long double
#define pii pair<int,int>
#define pb push_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define x first
#define y second

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

	int a;
	cin>>a;
	cout<<a+a*a+a*a*a<<endl;
	return 0;
}

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


//Node
struct node{
  int key;
  struct node *next;
  struct node *prev;
};

//NodePointer
typedef struct node * NodePointer;

//function
NodePointer make1node(int);
//find item
NodePointer finditem(int);
//insert data
void insert(int);
//delete data
void delete(int);
//delete last data
void deleteLast(void);
//delete first data
void deleteFirst(void);

//print
void listprint(void);
//nil
NodePointer nil;

int main(){
 
  nil=make1node(0);
  int n,i;
  long num;
  char a[15];
  //load number of command
  scanf("%d",&n);
  //execute
  for(i=0;i<n;i++){
    //load command
    scanf("%s",a);

    //if insert,load data
    if(strcmp(a,"insert")==0){
      scanf("%ld",&num);
      insert(num);
    }
    //if delete load data

    else if(strcmp(a,"delete")==0){
      scanf("%ld",&num);
      delete(num);
    }


    else if(strcmp(a,"deleteFirst")==0) deleteFirst();
    else if(strcmp(a,"deleteLast")==0) deleteLast();
  }
  //print
  listprint();

  return 0;
}


NodePointer make1node(int keydata){
  NodePointer n;
  n=malloc(sizeof(struct node));
  n->key=keydata;
  n->next=n;
  n->prev=n;

  return n;
}

void insert(int value){
  NodePointer newnode;

  newnode=make1node(value);

  newnode->next=nil->next;

  newnode->next->prev=newnode;
 
  nil->next=newnode;

  newnode->prev=nil;



}

NodePointer finditem(int value){
  NodePointer n;

  n=nil->next;
  while(n!=nil &&n->key!=value){
    n=n->next;
  }
  if(n!=nil) return n;
  else return NULL;


}



void delete(int value){
  NodePointer n;
  if((n=finditem(value))!=NULL){

    n->prev->next=n->next;
    n->next->prev=n->prev;

    free(n);
  }
}

void listprint(void){
  NodePointer n;
  for(n=nil->next;n!=nil;n=n->next){
    if(n==nil->next){
    printf("%d",n->key);
    }
    else printf(" %d",n->key);
  }
  printf("\n");
}

void deleteFirst(void){
  NodePointer n;
  n=nil->next;
  
  n->prev->next=n->next;
  n->next->prev=n->prev;

  free(n);
}

void deleteLast(void){
  NodePointer n;
 
  n=nil->prev;
  
  n->prev->next=n->next;
  n->next->prev=n->prev;

  free(n);


}

Measured memory_bytes: 15000
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;

    pair<int , int> p[N]; // (右端, 左端)
    for(int i=0;i<N;i++){
        int X, L, left, right;
        cin >> X >> L;
        left = X - L;
        right = X + L;
        p[i] = make_pair(right, left);
    }
    
    // 昇順ソート（第一要素）
    sort(p, p + N);
    int left = p[0].second, right = p[0].first, ans = 1;
    for(int i=1;i<N;i++){
        int l = max(0, p[i].second), r = p[i].first;
        if(right <= l){
            right = r;
            ans++;
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 1024
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}

#define MOD 1000000007

vector<int> fwt(1e6);
int sum(int r) {
	int result = 0;
	for (; r >= 0; r = (r & (r + 1)) - 1)
		result += fwt[r];
	return result;
}

void inc(int i, int delta) {
	for (; i < 1e6; i = (i | (i + 1)))
		fwt[i] += delta;
}


int main() {

#if defined(_DEBUG) 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	long long k;
	cin >> n >> k;
	vector<long long > vec(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];

	vector<long long> tmp;
	tmp.push_back(0);
	
	long long acc = 0;
	for (int i = 0; i < n; i++)
	{
		acc += vec[i];
		tmp.push_back(acc - k * (i + 1));
	}

	vector<long long> vals = tmp;
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	
	long long ans = 0;
	for (auto x : tmp)
	{
		int i = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
		ans += sum(i);
		inc(i, 1);
	}

	cout << ans;

	return 0;
}


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

int main() {
int N,K;
  cin >> N >> K;
  int a;
  int count = 0;
  for(int i = 0; i < N; i++){
  	cin >> a;
    if(a >= K){
    	count++;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<time.h>
#include<limits.h>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
#include <iomanip>
using namespace std;
#define inf LLONG_MAX
const int N = 1e7 + 1;
#define int long long

void solve() {
    int l,r,d;cin>>l>>r>>d;
    int c = 0;
    for (int i = l; i <= r; i ++) {
        if (i % d == 0) c++;
    }
    cout << c;
}

int32_t main() {
        solve();
}


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

const int N = 105;

int n, a[2][N], r;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++) cin >> a[i][j];
	partial_sum(a[0] + 1, a[0] + n + 1, a[0] + 1);
	reverse(a[1] + 1, a[1] + n + 1);
	partial_sum(a[1] + 1, a[1] + n + 1, a[1] + 1);
	reverse(a[1] + 1, a[1] + n + 1);
	for(int i = 1; i <= n; i++) r = max(r, a[0][i] + a[1][i]);
	cout << r << endl;
}

Measured memory_bytes: 256
import java.io.*;

class Main{
	public static void main(String[] args){
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			Dice d = new Dice(br.readLine());
			int q = Integer.parseInt(br.readLine());
			for(int i=0; i<q; i++){
				d.sim(br.readLine());
				System.out.println(d.getRight());
			}
		} catch(IOException e){
			System.out.println("Exception :" + e);
		}
	}
}
class Dice{
	private int top;
	private int forth;
	private int right;
	private int left;
	private int back;
	private int bottom;
	Dice(String label){
		String lab[] = label.split(" ", 0);
		top    = Integer.parseInt(lab[0]);
		forth  = Integer.parseInt(lab[1]);
		right  = Integer.parseInt(lab[2]);
		left   = Integer.parseInt(lab[3]);
		back   = Integer.parseInt(lab[4]);
		bottom = Integer.parseInt(lab[5]);
	}
	public void sim(String order){
		String ord[] = order.split(" ", 0);
		int ordTop   = Integer.parseInt(ord[0]);
		int ordForth = Integer.parseInt(ord[1]);
		int work;

		if(ordTop==forth){
			work   = top;
			top    = forth;
			forth  = bottom;
			bottom = back;
			back   = work;
		} else if(ordTop==right){
			work   = top;
			top    = right;
			right  = bottom;
			bottom = left;
			left   = work;
		} else if(ordTop==left){
			work   = top;
			top    = left;
			left   = bottom;
			bottom = right;
			right  = work;
		} else if(ordTop==back){
			work   = top;
			top    = back;
			back   = bottom;
			bottom = forth;
			forth  = work;
		} else if(ordTop==bottom){
			work   = top;
			top    = forth;
			forth  = bottom;
			bottom = back;
			back   = work;
			work   = top;
			top    = forth;
			forth  = bottom;
			bottom = back;
			back   = work;
		}

		if(ordForth==right){
			work   = forth;
			forth  = right;
			right  = back;
			back   = left;
			left   = work;
		} else if(ordForth==left){
			work   = forth;
			forth  = left;
			left   = back;
			back   = right;
			right  = work;
		} else if(ordForth==back){
			work   = forth;
			forth  = right;
			right  = back;
			back   = left;
			left   = work;
			work   = forth;
			forth  = right;
			right  = back;
			back   = left;
			left   = work;
		}
	}
	public int getTop(){
		return top;
	}
	public int getRight(){
		return right;
	}
}

Measured memory_bytes: 17040
#include<stdio.h>
#define  NIL -1
#define N 100000
 
int getDepth(int);
 


struct Node{
  int p;
  int l;
  int r;
  int s;
  int h;
   
}Node;
 
 struct Node T[N];
 
int getDepth(int u){
  int d=0;
    
   
 for(;T[u].p != NIL; d++) u=T[u].p;
   
  return d;
}
void setHeight(int n){
  int d,i,j;
  for(i=0;i<n;i++){
    
    if(T[i].r == NIL && T[i].l == NIL){
      T[i].h == 0;
      for(j = i,d = 1;j != NIL; d++){
    j = T[j].p;
    if(T[j].h < d) T[j].h = d;
     
      }
    }
  }
  
}
 
int main(){
  int i;
  int j;
  int n = 0;
  int v  =0;
  int d = 0;
  int c = 0;
  int l = 0;
  scanf("%d",&n);
  
 for(i=0;i<n;i++) {
    
    T[i].p=NIL;
    T[i].l=NIL;
    T[i].r=NIL;
    T[i].s=NIL;
  }
   
 for(i=0;i<n;i++){
   scanf("%d %d %d",&v,&d,&c);
   if( d!= NIL && c ==NIL){
     T[v].l = d;
     T[d].p = v;
   }
   if(c != NIL && d == NIL){
    T[v].r = c;
    T[c].p = v;
   }
   if(d != NIL && c != NIL){
     T[v].l = d;
     T[d].p = v;
     T[v].r = c;
     T[c].p = v;
     T[d].s = c;
     T[c].s = d;
   }
 }
  
  
  
    
 for(i=0;i<n;i++){
   
   printf("node %d: parent = %d, sibling = %d, ",i,T[i].p,T[i].s);
   if(T[i].r == NIL && T[i].l == NIL) printf("degree = 0, ");
    
else if(T[i].r == NIL || T[i].l == NIL) printf("degree = 1, ");
   
   else printf("degree = 2, ");
   setHeight(n);
   printf("depth = %d, height = %d,",getDepth(i),T[i].h);
 
   if(T[i].p == NIL) printf(" root\n");
 
   else if(T[i].l == NIL && T[i].r == NIL) printf(" leaf\n");
 
   else printf(" internal node\n");
    
   
 }
return 0;
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
vector<int> v;
ll int pos[200001],tin[200001];
ll int timer =0,timer_start,length;
void dfs(vector<ll int> adj[],ll int u,ll int visited[])
{
    visited[u]=1;
    tin[u]=timer;
    pos[timer]=u;
    timer++;
    for(ll int i : adj[u])
    {
            if(visited[i]!=1)
                dfs(adj,i,visited);
            else
            {
                timer_start=tin[i];
                length=tin[u]-tin[i]+1;
            }
   }
}
int main()
{
        ll int n,k;
        cin>>n>>k;
        vector<ll int> adj[n+1];
        for(int i=1;i<=n;i++)
        {
            ll int x;
            cin>>x;
            adj[i].push_back(x);
        }
        ll int visited[n+1]={0};
        dfs(adj,1,visited);
        if(k<=timer_start)
            cout<<pos[k];
        else
        {
            ll int ans=timer_start+(k-timer_start)%length;
            cout<<pos[ans];
        }
     cout<<"\n";
    }


Measured memory_bytes: 31312
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main(){
    int N,K;
    cin >> N >> K;
    vector<int>V(N);
    for(int i = 0; i < N; i++) {
        cin >> V[i];
    }
    int ans = 0;
    for(int i = 0; i <= min(N,K); i++) {
        for(int j = 0; j <= min(N-i,K-i); j++) {
            vector<int>cnt = {};
            int sum = 0;
            for(int k = 0; k < i; k++) {
                sum += V[k];
                if(0 > V[k]) cnt.push_back(V[k]);
            }
            for(int k = 0; k < j; k++) {
                sum += V[N-k-1];
                if(0 > V[N-k-1]) cnt.push_back(V[N-k-1]);
            }
            sort(cnt.begin(),cnt.end());
            for(int k = 0; k < min((int)cnt.size(),K-i-j); k++) {
                sum += -cnt[k];
            }
            ans = max(ans,sum);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,K=MI()
    P=LI()
    Q=[(1+p)*p/2/p for p in P]
    now = sum(Q[:K])
    ans = now
    for i in range(N-K):
        now -= Q[i]
        now += Q[i+K]
        ans = max(ans, now)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 26744
X = input()
ans = []
for i in range(len(X)):
    if X[i] == "S":
        ans.append("S")
    if len(ans) == 0:
        if X[i] == "T":
            ans.append("T")
    else:
        if X[i] == "T" and ans[len(ans)-1] == "T":
            ans.append("T")
        if X[i] == "T" and ans[len(ans)-1] == "S":
            ans.pop()
print(len(ans))

Measured memory_bytes: 5096
#include <bits/stdc++.h>
using namespace std;
 
int main(){

int N, K;
  cin >> N >> K;
string S;
  cin >> S;

  for(int i = 0;i < S.size();i++){
  if(i == K - 1){
    S.at(i) = S.at(i) + 0x20;
    cout << S.at(i);
  }
    else cout << S.at(i);
  }

  return 0;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
using namespace std;
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;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;




int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
	
	
    
    int n,i;
    cin>>n;
    int a,b,maxnum=0,maxval=0;
    rep(i,n){
    	cin>>a>>b;
    	if(a>maxnum){
    		maxnum=a;
    		maxval=b;
		}
	}
	cout<<maxnum+maxval<<endl;
	
	
	
	
	
	
	
	
//////////////////////////////////////////////////////
	return 0;
}








Measured memory_bytes: 256
a = str(input())
b =len(a)
c = (b-1)/2
d = (b+3)/2
E = list(a)
R = list(reversed(E))
F = "".join(R)
A = list(a[0:int(c)])
X = list(reversed(A))
S = "".join(X)
B = list(a[int(d-1):int(b+1)])
Y = list(reversed(B))
Q = "".join(Y)
if a[0:int(c)] == S and a[int(d-1):int(b+1)] == Q and a == F :
    print('Yes')
else:
    print('No')

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

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define FOR(i,l,r) for(long long i=l; i<r; i++)
#define FOR_REV(i,r,l) for(long long i=r; i>=l; i--)
#define pb push_back
#define mp make_pair

const long long INF = 1e9;

vector <int> spell;
vector <int> cost;

int main()
{
    FAST_IO;
	int h,n;
    cin>>h>>n;

    int a,b;
    FOR(i,0,n)
    {
        cin>>a>>b;
        spell.pb(a);
        cost.pb(b);
    }

    int dp[10004];
    for(int i = 0; i <= 10001; i++){
        dp[i] = INF;
    }

    dp[h] = 0;

    for (int i=h; i>=0; i--)
    {
        for (int j=0; j<n; j++)
        {
            int x = max(0, i - spell[j]);
            // cout<<" x "<<x;
            dp[x] = min(dp[x], dp[i]+ cost[j]);
            // cout<<"val "<<dp[x];
        }
        // cout<<endl;
    }

    cout<<dp[0]<<endl;

}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        var S = ReadLine();
        var K = int.Parse(ReadLine());

        int N = S.Length;
        var list = new List<string>();
        var find = 'a';
        while (list.Count < K)
        {
            for (int i = 0; i < N; i++)
            {
                if (S[i] == find)
                {
                    for (int j = 0; j < 5; j++)
                    {
                        if (i + j >= N) break;
                        var s = S.Substring(i, j + 1);
                        if (!list.Contains(s))
                        {
                            list.Add(s);
                        }
                    }
                }
            }
            find = (char)(find + 1);
        }
        list.Sort();
        WriteLine(list[K-1]);
    }
}


Measured memory_bytes: 28472
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
a.reverse()
mod=10**9+7
fact = [1]*100005
inv = [1]*100005
for i in range(2,100003):
	fact[i] = (fact[i-1]*i)%mod
for i in range(1,100003):
	inv[i] = pow(fact[i],mod-2,mod)

#n!//k!(n-k)!
def nCk(n,k):
	return fact[n]*inv[k]%mod*inv[n-k]%mod

ans = 0

for i in range(n-k+1):
	ans += (a[i]-a[n-1-i])*nCk(n-1-i,k-1)
	ans%=mod
print(ans)

Measured memory_bytes: 63472
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;

int main(void){
    // Your code here!
    int n,m;
    cin >> n >> m;
    if (n ==m ) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

"""
バケットソート
・累積和
"""

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

def CountingSort(A, k):
    C = [0] * (k+1)
    B = [0] * N
    # C[i] に i の出現数を記録する
    for i in range(N):
        C[A[i]] += 1
    # C[i] に i 以下の数の出現数を記録する
    for i in range(1, k+1):
        C[i] += C[i-1]

    for i in range(N-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        # C[A[i]]の値は1つ場所を確定させたので、1減らしておく
        C[A[i]] -= 1
    return B

B = CountingSort(A, max(A))
print(*B)



Measured memory_bytes: 224384
def count_cuts(a, unit):
    return (a + unit - 1) // unit - 1


def is_good(mid, key):
    return sum(count_cuts(a, mid) for a in A) <= key


def binary_search(key):
    bad, good = 0, 1_000_000_000
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


N, K, *A = map(int, open(0).read().split())
print(binary_search(K))


Measured memory_bytes: 31496
#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 (ll i=(ll)from; i<(ll)to; i++)
#define all(vec) vec.begin(), vec.end()
#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;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N; cin >> N;
  ll a[N]; rep(i,N) cin >> a[i];
  ll result = 0; rep(i,N) result += i%2==0 && a[i]%2==1;
  cout << result << endl;
  return 0;
}

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

using namespace std;

int n;
string s[100005];

int main () {
  cin >> n;
  for (int i = 1;i <= n;i ++) {
    cin >> s[i];
    sort (s[i].begin (), s[i].end ());
  }
  sort (s + 1, s + n + 1);
  long long len = 0, ans = 0;
  
  for (int i = 1;i <= n;i ++) {
    if (s[i] != s[i - 1]) {
      ans += len * (len - 1) / 2;
      len = 0;
    }
    len ++;
  }
  ans += len * (len - 1) / 2;
  cout << ans;
  return 0;
}

Measured memory_bytes: 7296
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	int64 nn, kk, ans = 1;
	cin >> nn >> kk;
	ans = nn - kk + 1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3520
#define ONLINE_JUDGE
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <iterator>
#include <map>
#include <set>
#ifndef ONLINE_JUDGE
#include <prettyprint/prettyprint.hpp>
#endif

#define FOR(i, n) for(int i = 0; i < n; ++i)
#define TEST int T; std::cin >> T; while(T--)
#define ALL(v) v.begin(), v.end()

using ll = long long;
using ull = unsigned long long;
using vi = std::vector<int>;
using vll = std::vector<ll>;
using vull = std::vector<ull>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
#ifndef ONLINE_JUDGE
	ifstream fin("in.txt");
	ofstream fout("out.txt");
	auto cinbuf = cin.rdbuf(fin.rdbuf());    // save and redirect
	auto coutbuf = cout.rdbuf(fout.rdbuf()); // save and redirect
#endif	
	int N, W;
	cin >> N >> W;
	vector<int[2]> objects(N);

	int val_sum = 0;
	for(int i = 0; i < N; ++i) {
		cin >> objects[i][0] >> objects[i][1];
		val_sum += objects[i][1];
	}

	ull dp[N + 1][val_sum + 1];
	// dp[i][j] = minimum weight taking objects 1..i with total value j
	for(int i = 0; i <= val_sum; ++i) {
		dp[0][i] = W + 1;
	}
	for(int i = 0; i <= N; ++i) {
		dp[i][0] = 0;
	}

	for(int i = 1; i <= N; ++i) {
		for(int j = 1; j <= val_sum; ++j) {
			int v = objects[i - 1][1];
			int w = objects[i - 1][0];
			dp[i][j] = dp[i - 1][j];
			if(dp[i - 1][j - v] <= W) {
				dp[i][j] = min(dp[i][j], dp[i - 1][j - v] + w);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= val_sum; ++i) {
		if(dp[N][i] <= W) {
			ans = i;
		}
	}
	cout << ans << endl;
#ifndef ONLINE_JUDGE
	cin.rdbuf(cinbuf);    // restore
	cout.rdbuf(coutbuf); // restore
#endif	
}


Measured memory_bytes: 79232
#include<stdio.h>
int M[12][12];
int main() {
	int n, m, i, j; scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++) {
		char x; scanf(" %c", &x);
		M[i][j] = x == '#';
	}
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (M[i][j] && M[i + 1][j] && M[i][j + 1]) { printf("Impossible"); return 0; }
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (M[i][j] && M[i - 1][j] && M[i][j - 1]) { printf("Impossible"); return 0; }
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (M[i][j] && M[i + 1][j] && M[i - 1][j] && M[i][j - 1]) { printf("Impossible"); return 0; }
	for (i = 1; i <= n; i++)for (j = 1; j <= m; j++)if (M[i][j] && M[i][j + 1] && M[i][j - 1] && M[i - 1][j]) { printf("Impossible"); return 0; }
	printf("Possible");
	return 0;
}

Measured memory_bytes: 128
import math

#n=list(map(int,input().split()))
#x=int(input())
n=int(input())
s=input()
k=int(input())
s2=""
ch=s[k-1]
for a in range(len(s)):
    if ch==s[a]:
        s2+=s[a]
    else:
        s2+="*"
print(s2)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <bitset>
#include <cmath>
#include <stack>
#include <iomanip>
#include <map>
#include <math.h>
typedef long long ll;
using namespace std;
const int MOD = 1000000007;

ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++)
    {
        ll num;
        cin >> num;
        num -= i;
        A[i] = num;
    }
    sort(A.begin(),A.end());
    int mid = A[N/2];
    ll ans = 0;
    for(int i = 0; i < N; i++)
    {
        ans += abs(A[i] - mid);
    }
    cout << ans << endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   

typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> isPair;
using vvll = vector< vector<ll> >;
using vll = vector<ll> ;
#define Pll pair<ll,ll>
#define vpll vector<pll>
#define sll set<ll>
#define mll map<ll,ll>

const ll inf=1e18;
const ll maxs = 100005;
const ll mod = 1e9+7;

#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define LB lower_bound
#define UB upper_bound
#define line cout<<endl;
#define fr(i,a,b) for(int i=a;i<=b;++i)
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fastio(); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mst(x,a) memset(x,a,sizeof(x))

ll a[maxs];
ll dp[maxs];
ll n,k;

void solve()
{
    for(ll i=0;i<n;i++)
        cin>>a[i];
    
    for(ll i=1;i<=k;i++)
        for(ll j=0;j<n;j++)
            if(i>=a[j])
                dp[i] = max(dp[i],1ll*!dp[i-a[j]]);
    if(dp[k])
        cout<<"First";
    else    
        cout<<"Second";
        
}

int main(){
    cin>>n>>k;
	solve();
	return 0;
}


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

long long calc(long long A) {

	if (A <= 0) return 0;

	//4の時に、0,1,2,3,4までになるので、これは5つの整数まで
	//なので帳尻合わせで１足してあげる。
	//A++;
	//10^3 <= 2^10
	//1000 <= 1024
	//10^12 <= 2^40
	//10^12 <= 2進数 40桁くらい

	long long ans = 0;
	//i桁目の偶奇を調べる
	for (int i = 0; i < 50; i++)
	{
		//0桁目 → 周期2
		//1				4
		//2				8
		long long loop = (1LL << (i + 1));
		long long cnt = (A / loop) * (loop / 2);
		//00000.....0011111.....11
		cnt += max(0LL, (A % loop) - (loop / 2) + 1);

		//その桁の1の数が奇数だったら足し算
		if (cnt % 2 == 1) {
			ans += 1LL << i;
		}
	}

	return ans;
}

int main() {
	long long A, B;
	cin >> A >> B;
	long long ans = calc(B) ^ calc(A - 1);
	cout << ans << endl;
}



Measured memory_bytes: 256
def egcd(a, b, x0 = 1, x1 = 0, y0 = 0, y1 = 1)
  if b == 0
    return [x0, y0]
  else
    return egcd(b, a % b, x1, x0 - a / b * x1, y1, y0 - a / b * y1)
  end
end

a, b = gets.split.map(&:to_i)
puts egcd(a, b).join(" ")

Measured memory_bytes: 8640
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include<queue>
#include <sstream>
#include <set>
typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
using namespace std;
int main(){
    int N; cin >> N;
    int ans = 0;

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

    a[0] = 0;
    a[1] = abs(vec[0]-vec[1]);

    for(int i = 2;i<N;i++){
        int x = abs(vec[i-2]-vec[i]);
        int tmp1 = a[i-2] + x;

        int y = abs(vec[i-1]-vec[i]);
        int tmp2 = a[i-1] + y;

        a[i] = min(tmp1,tmp2);
    }

    
    cout << a[N-1] <<endl;
}

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

int main(void){
    int N,i,B=0,C=0;
    cin >> N;
    int a[N],b[N]={0},c[N]={0};
    for (i = 0; i < N; i++){
        cin >> a[i];
    }

    sort(a,a+N);
    reverse(a,a+N);
    for(i = 0; i < N; i++){
        if(i%2==0){
            b[i] = a[i];
        }else{
            c[i] = a[i];
        }
    }

    for(i = 0; i < N; i++){
        B += b[i];
        C += c[i];
    }

    cout << B - C << endl;
    return 0;
}

Measured memory_bytes: 256
object Main extends App {
    val in = io.Source.stdin.getLines
    val n = in.next.toInt
    val es = in.take(n).flatMap(e => {
        val Array(r, _, t@_*) = e.split(" ").map(_.toInt)
        t.map((r, _))
    }).toList
    in.next
    for (Array(s, d, v) <- in.map(_.split(" ").map(_.toInt))) {
        val g = Array.fill(n+1)(Int.MaxValue-100)
        g(s) = 1
        var flag = true
        while(flag) {
            flag = false
            for ((r, t) <- es)
                if (g(r) + 1 < g(t)) {
                    g(t) = g(r) + 1
                    flag = true
                }
        }
        println(if (v >= g(d)) g(d) else "NA")
    }
}

Measured memory_bytes: 49324
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define mp make_pair
using namespace std;
using ll=long long;
using P=pair<int,int>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-5;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct UnionFind{
    vector<int> par,siz;
    UnionFind(int n){
        par.resize(n);
        siz.resize(n,1);
        for(int i=0;i<n;i++)par[i]=i;
    }
    int find(int x){
        return (par[x]==x?x:(par[x]=find(par[x])));
    }
    void unite(int u,int v){
        u=find(u);v=find(v);
        if(u==v)return;
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v];
        par[v]=u;
    }
    bool same(int u,int v){
        return find(u)==find(v);
    }
};
int main(){
    int n,q;cin>>n>>q;
    UnionFind uf(n);
    while(q--){
        int t,u,v;cin>>t>>u>>v;
        if(t==0){
            uf.unite(u,v);
        }else{
            cout<<uf.same(u,v)<<endl;
        }
    }
}



Measured memory_bytes: 3188
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
#include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int op(int a, int b) {
    return max(a, b);
}

int e() {
    return 0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    V<int> a(n), ca(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ca[i] = a[i];
    }
    sort(ALL(ca));
    
    map<int, int> acnt;
    atcoder::segtree<int, op, e> st(n);
    for (int i = 0; i < n; i++) {
        int left = lower_bound(ALL(ca), a[i] - k) - ca.begin();
        int right = upper_bound(ALL(ca), a[i] + k) - ca.begin() - 1;
        int tmp = st.prod(left, right + 1) + 1;
        st.set(lower_bound(ALL(ca), a[i]) - ca.begin() + acnt[a[i]], tmp);
        acnt[a[i]]++;
    }

    cout << st.all_prod() << '\n';
    return 0;
}


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

namespace HelloWorld
{
    class Program
    {
        static void Main(string[] args)
        {
            List<List<int>> trump = new List<List<int>>();

            for (int k = 0; k < 4; k++)
            {
                List<int> card = new List<int>();
                for (int l = 0; l < 13; l++)
                {
                    card.Add(l + 1);
                }
                trump.Add(card);
            }
            //読み取り
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                List<string> data = Console.ReadLine().Split(' ').ToList();
                int mark;
                int number = int.Parse(data[1]);
                switch (data[0])
                {
                    case "S": mark = 0; break;
                    case "H": mark = 1; break;
                    case "C": mark = 2; break;
                    default: mark = 3; break;
                }
                trump[mark].Remove(number);
            }


            for (int i = 0; i < trump.Count; i++)
            {
                string mark1;
                switch (i)
                {
                    case 0: mark1 = "S"; break;
                    case 1: mark1 = "H"; break;
                    case 2: mark1 = "C"; break;
                    default: mark1 = "D"; break;
                }

                for (int j = 0; j < trump[i].Count; j++)
                {
                    Console.WriteLine(mark1 + " " + trump[i][j]);
                }               
            }
        }
    }
}


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

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* na, Arg1&& arg1, Args&&... args) {
  const char* c = strchr(na + 1, ',');
  cerr.write(na, c - na) << " : " << arg1 << " , ";
  __f(c + 1, args...);
}
#define endl "\n"
typedef long long LL;
const int mod = 1e9 + 7;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 2e5 + 5;

int n, k;
LL a[ N ];
double val[ N ];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    //freopen("input.txt", "r", stdin);
  #endif // LOCAL
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    val[i] = a[i] * (a[i] + 1)/2;
    val[i] /= a[i];
    val[i] += val[i - 1];
  }
  double mx = 0.0;
  for (int i = 1; i + k - 1 <= n; i++) {
    mx = max(mx, val[i + k - 1] - val[i - 1]);
  }
  cout << setprecision(10) << fixed << mx << endl;
  return 0;
}



Measured memory_bytes: 3328
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int n,temp,sum,box[]={1,5,3,3,3,3,3,4,3,4};
	char s[1030];
	char tab[20][10]={" ",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	cin>>n;
	while(n--){
		cin>>s;
		sum=0;
		for(int i=0;i<(int)strlen(s);i++){
			if(s[i]=='0'){
				if(sum!=0){
					cout<<tab[temp][(sum-1)%box[temp]];
				}
				sum=0;
			}
			else{
				temp=s[i]-'0';
				sum++;
			}
		}
		cout<<endl;
	}
	return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  for(int i=0;i<W+2;i++) cout << "#" ;
  cout << endl;
  string s;
  for(int i=0;i<H;i++) {
    cin >> s;
    cout << '#' + s + '#' << endl;
  }
  for(int i=0;i<W+2;i++) cout << "#";
  cout << endl;
}


Measured memory_bytes: 256
#include "iostream"
#include "algorithm"
#include "vector"
#include "string"
#include "cmath"

int main(int argc, char const *argv[]) {

  int NN;
  std::cin >> NN;

  int k = NN%10;
  int kk = (NN / 10) % 10;
  int kkk = NN /100;

  // std::cout << kk << '\n';
  // std::cout << kkk << '\n';

  if (NN > kkk * 111) {
    std::cout << (kkk+1) * 111 << '\n';
  }else{
    std::cout << kkk*111 << '\n';
  }

  return 0;
}


Measured memory_bytes: 256
S = list(map(int,input().split()))
N = S[0]
M = S[1]
X = S[2]
Y = S[3]
x = list(map(int,input().split()))
y = list(map(int,input().split()))
x.append(X)
y.append(Y)
x_max = max(x)
y_min = min(y)
if x_max < y_min:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long
#define rep(i, a, b) for(ll i = (ll)a; i < (ll)b; i++)
using namespace std;

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

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, 0, n) cin >> v[i];
  int m = v[0];
  rep(i, 1, n) {
    m = gcd(m, v[i]);
  }
  cout << m << "\n";
}

Measured memory_bytes: 3760
h, n = map(int, input().split())
ab = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [10 ** 20] * 10 ** 4 * 2
dp[0] = 0
for i in range(h):
    for a, b in ab:
        dp[i + a] = min(dp[i + a], dp[i] + b)
print(min(dp[h:]))

Measured memory_bytes: 42476
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;
using ll = long long;
//----------------------------------------------
#define rep(i,m,n) for(int i=m;i<(int)(n);i++)
#define putout(x) cout<<x<<endl
//----------------------------------------------



int main()//
{
	string s;
	char next;

	cin >> s;

	rep(i, 0, 3)
	{
		if (s[i] == s[i + 1])
		{
			putout("Bad");
			return 0;
		}
	}

	putout("Good");

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define P pair<int, int>

using namespace std;
const int INF=1e5;

int main(){
  long long n, a[100009];
  cin >> n;
  for(int i=0;i<n;i++)cin >> a[i];
  sort(a, a+n);
  long long ans=a[n-1]-a[0];
  for(int i=1;i<n-1;i++)ans+=abs(a[i]);
  cout << ans << endl;
  for(int i=1;i<n-1;i++){
    if(a[i]>=0){
      cout << a[0] << ' ' << a[i] << endl;
      a[0]-=a[i];
    }
    else{
      cout << a[n-1] << ' ' << a[i] << endl;
      a[n-1]-=a[i];
    }
  }
  cout << a[n-1] << ' ' << a[0] << endl;
}



Measured memory_bytes: 2688
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = 1; i <= (int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

//const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) {
        cin >> a[i];
    }
    int ans = 1000000;
    sort(all(a));
    for(int i = a[0]; i <= a[n-1]; i++) {
        int counter = 0;
        rep(j,n) {
            int dif = abs(a[j] - i);
            dif *= dif;
            counter += dif;
        }
        ans = min(ans,counter);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256