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

public class Main {

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

		boolean end = false;
		int tri = 0;
		int ei = 0;
		int cho = 0;
		int don = 0;
		while(stdIn.hasNext()){
			int a = stdIn.nextInt();
			int b = stdIn.nextInt();
			int c = stdIn.nextInt();
			if(!end){
				// ソート
				if(a>b){
					int tmp = a;
					a = b;
					b = tmp;
				}
				if(a>c){
					int tmp = a;
					a = c;
					c = tmp;
				}
				if(b>c){
					int tmp = b;
					b = c;
					c = tmp;
				}

				// 三角形存在条件
				// |b-c|<a<b+c
				if(Math.abs(b-c)<a&&a<b+c){
					tri++;

					// 鋭角条件
					// a^2+b^2 > c^2
					if(a*a+b*b>c*c){
						ei++;
					}
					// 直角条件
					else if(a*a+b*b==c*c){
						cho++;
					}
					// 鈍角
					else{
						don++;
					}
				}
				else{
					// 入力無視
					end = true;
				}
			}
		}
		System.out.println(tri+" "+cho+" "+ei+" "+don);
	}
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define PLUS 0
#define MINUS 1
#define N 4
#define ANS 7
i64 X[N]; // A, B, C, D
char C[N];

void solve() {
  i64 s;
  string res;
  for (i64 i = 0; i < pow(2, N - 1); i++) {
    res = C[0];
    s = X[0];
    REP(j, N - 1) {
      if (i & (1 << j)) {
        s -= X[j + 1];
        res += '-';
      } else {
        s += X[j + 1];
        res += '+';
      }
      res += C[j + 1];
    }
    if (s == ANS) {
      cout << res << "=7" << endl;
      return;
    }
  }
}

int main() {
  i64 x;
  REP(i, N) {
    cin >> C[i];
    X[i] = C[i] - '0';
  }

  solve();

  return 0;
}

Measured memory_bytes: 256
from collections import deque
N=int(input())
tree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
paths=[]
for i in range(N-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    paths.append([a-1,b-1,i,0])
paths=sorted(paths,key=lambda x:x[1])
paths.sort(key=lambda x:x[0])
#print(paths)
v=0
d=deque()
d.append(v)
seen=[0]*N
col=[-1]*N
path=[]
dirtree = [[] for _ in range(N)]
while len(d)>0:
    v=d.popleft()
    seen[v]=1
    for j in tree[v]:
        if seen[j]==0:
            d.append(j)
            dirtree[v].append(j)
#print(dirtree)
v=0
d.append(v)
col[v]=0
while len(d)>0:
    v=d.popleft()
    seen[v]=0
    c=0
    for j in dirtree[v]:
        if seen[j]==1:
            d.append(j)
            c=c+1
            if c==col[v]:
                c=c+1
                path.append([min(j,v),max(j,v),c])
            else:
                path.append([min(j, v), max(j, v), c])
            col[j]=c
path = sorted(path, key=lambda x: x[1])
path.sort(key=lambda x: x[0])
    #print(path)
    #input()
for i in range(N-1):
    paths[i][3]=path[i][2]
paths.sort(key=lambda x:x[2])
path.sort(key=lambda x:x[2],reverse=True)
print(path[0][2])
for i in range(N-1):
    print(paths[i][3])

Measured memory_bytes: 126128
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; }

void say(bool val, string yes = "Yes", string no = "No") { say<string>(val, yes, no); }

template <class T> void chmin(T &a, T b) {
  if (a > b)
    a = b;
}

template <class T> void chmax(T &a, T b) {
  if (a < b)
    a = b;
}

// C++ 17に完全移行したら消す
// 最大公約数を求める
template <class T> T gcd(T n, T m) { return n ? gcd(m % n, n) : m; }

// 最小公倍数を求める
template <class T> T lcm(T n, T m) {
  int g = gcd(n, m);
  return n * m / g;
}

// 重複を消す。計算量はO(NlogN)
template <class T> void unique(std::vector<T> &v) {
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
}


#line 2 "abc170_b.cpp"

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

  int x, y;
  cin >> x >> y;
  REP(i, x + 1) {
    if (2 * i + 4 * (x - i) == y) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;
}


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

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimize("Ofast")
//1.0 * clock() / CLOCKS_PER_SEC

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const ll NN = 1e10 + 7;
const int N = 5e5 + 7;
const int M = 11;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;

void solve1()
{
    int a,b,c;
    cin >> a >> b >> c;
    swap( a , b );
    swap( a , c );
    cout << a << " " << b << " " << c;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); srand(time(0));
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int cghf = 1;//cin >> cghf;
    while( cghf-- ){
        solve1();
    }
}


Measured memory_bytes: 256
import sys
from collections import deque
from itertools import product
sys.setrecursionlimit(10**9)

H,W=map(int,input().split())
G=[[""]*W for _ in range(H)]
road=0

# print("W,H",W,H)
for y in range(H):
    s=input()
    for x in range(W):
        G[y][x]=s[x]
        if s[x]==".":
            road+=1

# print("road",road)
def bfs(pos):
    todo=[pos]
    index=1
    dx,dy=[-1,1,0,0],[0,0,-1,1]
    depth=[[0]*W for _ in range(H)]
    while True:
        x,y=pos

        # print(pos)
        if pos==(W-1,H-1):
            # print(todo)
            return depth[y][x]

        for i in range(4):
            npos=(x+dx[i],y+dy[i])
            if 0<=npos[0]<W and 0<=npos[1]<H:
                if G[npos[1]][npos[0]]=="." and not npos in todo:
                    depth[npos[1]][npos[0]]=depth[y][x]+1
                    todo.append(npos)

        if index<len(todo):
            pos=todo[index]
            index+=1
        else:
            print(-1)
            exit()
            return


d=bfs((0,0))+1

print(road-d)


Measured memory_bytes: 3564
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define INFTY 10000000000
void merge(int*,int,int,int);
void mergesort(int*,int,int);
int count=0;
int main(){

  int i,n,left,right;

  scanf("%d",&n);
  int A[n];
  left = 0;
  right = n;
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  mergesort(A,left,right);

  for(i=0;i<n;i++){
    if(i==n-1){
      printf("%d\n",A[i]);
    }
    else{
      printf("%d ",A[i]);
    }
  }

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

void merge(int *A,int left,int mid,int right){
  int n1,n2,i,j,k;
  n1 = mid - left;
  n2 = right - mid;
  int L[n1];
  int R[n2];
  for(i=0;i<=n1-1;i++){
    L[i] = A[left+i];
  }
  for(i=0;i<=n2-1;i++){
    R[i] = A[mid+i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
    if(L[i]<= R[j]){
      A[k] = L[i];
      i=i+1;
      count++;
    }
    else{
      A[k]=R[j];
      j=j+1;
      count++;
    }
  }
}
void mergesort(int *A,int left,int right){
  int mid;
  if (left+1 < right){
    mid = (left + right)/2;
    mergesort(A, left, mid);
    mergesort(A, mid, right);
    merge(A, left, mid, right);
  }
}

  



Measured memory_bytes: 5588
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
long long dp[22][1<<21];
int matrix[22][22];
int n;

long long solution(int man , int women){  
    if(man==n){
        return (women==((1<<n)-1)) ? 1 : 0;
    }
    if(dp[man][women] != -1){
        return dp[man][women];
    }
    
    long long ret = 0;

    for(int i=0 ; i<n ; i++){
        // cout<<"result "<<i<<" "<<man<<" "<<women<<endl;
        if(matrix[man][i]==1 && (women&(1<<i))==0){
            ret = (ret + solution(man+1 , women|(1<<i)))%mod;
        }
    }

    return dp[man][women] = ret;
}

int main(){
    
    cin>>n;

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


    memset(dp , -1 , sizeof(dp));
    cout<<solution(0 , 0)<<endl;

}

Measured memory_bytes: 360704
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <map>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> data(N);
  int max_num;
  int counter = 1;
  for(int i =0;i < N;i++){
    cin >> data[i];
  }

  max_num = data[0];

  for(int i = 1;i < N;i++){
    if(data[i] >= max_num)counter++;
    max_num = max(max_num,data[i]);
  }

  cout << counter << endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
ans = [0 for _ in range(N)]
for i in range(K):
    d = int(input())
    A = list(map(int, input().split()))
    for num in A:
        ans[num-1] += 1

count = 0
for num in ans:
    if num == 0:
        count+=1

print(count)

Measured memory_bytes: 9128
#include <iostream>
#include <vector>
#include<math.h>
using namespace std;
int main()
{
    int n;
    vector<int> stork;
    cin >> n;
    stork.resize(n + 1);
    stork[0] = 0;
    for (int e = 1; e < n+1; e++)
        cin >> stork[e];

    int answer=0;
    int e=3;
    int run[n+1];
    run[2] = abs(stork[2]-stork[1]);
    while(e<=n){
            run[e] = min(run[e-2]+abs(stork[e]-stork[e-2]),run[e-1]+abs(stork[e]-stork[e-1]));
            e++;
        }
    cout<< run[n]<<endl;
}

Measured memory_bytes: 3968
#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <set>
#include <cstdio>
#include <climits>
#include <cmath>
#include <array>
#include <functional>
#include <sstream>
#include <list>
#include <set>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const double eps=1e-9;
const int inf=1e9;
typedef pair<int,int> P;
typedef pair<double,int> Pdi;

int ipow(int a,int b)
{
  int ans=1;
  for(int i=0;i<b;i++)
    {
      ans=ans*a;
    }
  return ans;
}
int main(int argc,char const* argv[])
{
  int xi[6]={};
  string s;
  cin >> s;
  int k=0;
  char mi='+';
  int ind=0;
  while(s.length()>0)
    {
      k=0;
      if(s[0]=='x')k=1;
      else while(s[0]!='x'&&!s.empty())
	     {
	       k=k*10+s[0]-'0';
	       s.erase(s.begin());
	     }
      if(!s.empty()&&(s[1]=='+' ||s[1]=='-')){s.insert(s.begin()+1,'1');s.insert(s.begin()+1,'^');}
      if(!s.empty())s.erase(s.begin(),s.begin()+2);
      if(s.empty())
	{
	  ind=0;
	  if(mi=='-')k=k*-1;
	}
      else
	{
	  ind=s[0]-'0';
	  if(mi=='-')k=k*-1;
	  mi=s[1];
	  s.erase(s.begin());
	}
      if(!s.empty())s.erase(s.begin());
      xi[ind]=k;
    }
  int mxi;
  for(int i=0;i<6;i++)
    {
      if(xi[i]!=0)mxi=i;
    }
  vector<int> ans;
  for(int i=1;i<=2000;i++)
    {
      ll t=0;
      for(int j=0;j<6;j++)
	{
	  t+=xi[j]*ipow(i,j);
	}
      if(t==0)ans.push_back(-i);
      if(ans.size()>=mxi)break;
      t=0;
      for(int j=0;j<6;j++)
	{
	  t+=xi[j]*ipow(-i,j);
	}
      if(t==0)ans.push_back(i);
      if(ans.size()>=mxi)break;
    }
  sort(ans.begin(),ans.end());
  for(int i=0;i<ans.size();i++)
    {
      char a=ans[i]>0 ? '+':'-';
      ans[i]=abs(ans[i]);
      cout << "(x" << a << ans[i] << ")";
    }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3212
#include<bits/stdc++.h>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main()
{
    string  s;
    cin>>s;
    int len=s.size();
    for(int i=0;i<len;i++)
        cout<<"x";
    cout<<endl;


    return 0;
}
/*
int main()
{
    string s,t,u;
    int a,b;
    cin>>s>>t>>a>>b>>u;
    if(u==s)
        a--;
    else
        b--;
    cout<<a<<" "<<b<<endl;
    return 0;
}*/


Measured memory_bytes: 256
x = str(input())

s_count = 0
st = 0

for i in range(len(x)):
    if(x[i]=='S'):
        s_count+=1
    else:   # x[i]=='T'
        if(s_count>0):
            st+=1
            s_count-=1

print(len(x) - 2*st)

Measured memory_bytes: 3500
#include <bits/stdc++.h>
    #define ll  long long int
    #define N 100000
    #define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
    #define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
    #define po pop_back
    #define pb push_back
    #define lb lower_bound
    #define fi first
    #define se second
    #define debug(x) cout << #x << " = " << x << endl
    #define ub upper_bound
    #define ibs ios_base::sync_with_stdio(false)
    #define cti cin.tie(0)
    #define all(x) x.begin(),x.end()
    #define PI 3.14159265
    #define cot cout.tie(0)
    using namespace std;
      /**
        * @author :: Sawlani
        *
        */

        ll w[101],v[101];
        ll n,W;
        ll dp[101][100001];
        ll rec(ll i,ll wei)
        {
            ll ans=0;
            if(i>n)
                return 0;
            if(dp[i][wei]!=-1)
                return dp[i][wei];
            if(wei+w[i]<=W)
             ans=max(v[i]+rec(i+1,wei+w[i]),rec(i+1,wei));
            else
                ans=rec(i+1,wei);

            return dp[i][wei]=ans;

        }
        int main()
        {
          //  freopen("input.txt","r",stdin);

           memset(dp,-1,sizeof(dp));
            cin >> n >> W;

            f(i,1,n)
            {
                 cin >>  w[i] >> v[i];
            }

            cout <<  rec(1,0);
        }


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

struct Data
{
    char s;
    int a;
};

void swap(Data *p,Data *q)
{
   Data temp;
   temp=*p;
   *p=*q;
   *q=temp;
}

void ButtleSort(int n,Data *p)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=n-1;j>i;j--)
        {
            if((p+j)->a<(p+j-1)->a)
            {
                swap((p+j),(p+j-1));
            }
        }
    }
}

void SelectSort(int n,Data *p)
{
    int mini,num=1;
    for(int i=0;i<n-1;i++)
    {
        mini=i;
        for(int j=i+1;j<n;j++)
        {
            if((p+j)->a<(p+mini)->a)
            {
               mini=j;
            }
            
        }
        if(mini!=i)
        {
            if((p+mini)->a==(p+i)->a)
            {
                num=0;
                swap((p+mini),p+i);
            }
            else
                swap((p+mini),p+i);
        }
    }
}


int main(int argc, char const *argv[])
{
    int n,num=1;  cin>>n;
    Data *p,*q;
    p=new Data[n];
    for(int i=0;i<n;i++)
    {
        cin>>(p+i)->s>>(p+i)->a;
    }
    q=new Data[n];
    for(int i=0;i<n;i++)
    {
        (q+i)->a=(p+i)->a;
        (q+i)->s=(p+i)->s;
    }

    ButtleSort(n,p);
    for(int i=0;i<n-1;i++)  cout<<(p+i)->s<<(p+i)->a<<" ";
    cout<<(p+n-1)->s<<(p+n-1)->a<<endl;
    cout<<"Stable"<<endl;

    SelectSort(n,q);
    for(int i=0;i<n-1;i++)  cout<<(q+i)->s<<(p+i)->a<<" ";
    cout<<(q+n-1)->s<<(q+n-1)->a<<endl;
    for(int i=0;i<n;i++)
    {
        if((q+i)->s!=(p+i)->s)
            num=0;
    }
    if(num)
        cout<<"Stable"<<endl;
    else    
        cout<<"Not stable"<<endl;

    delete []p;
    delete []q;
    p=q=NULL;
    //system("pause");
    return 0;
}



Measured memory_bytes: 3072
#include <stdio.h>
#include <ctype.h>
#include <string.h>


int main() {
	int A, B, K;
	scanf("%d", &K);
	scanf("%d %d", &A, &B);
	for (A; A <= B; A++) {
		if(A%K==0)
		{
			printf("OK\n");
			break;
		}
		if (A == B && B % K == 0) {
			printf("OK\n");
			break;
		}
		if(A==B&&B%K!=0) {
			printf("NG");
			break;
		}
	}
	return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  string s;
  cin>>s;
  string ans=s.substr(0,3);
  cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
ll n, c, g, a, we, le, ac, L[7], p[7], k, dp[500][500];
signed main()
{
    cin >> n >> c, c *= n, k = (1 << (n - 1));
    forn(i, n) cin >> L[i], L[i] *= n;
    sort(L, L + n);
    iota(p, p + n - 1, 0);
    do {
        memset(dp, 0, sizeof(dp));
        dp[L[n - 1]][0] = 1;
        forn(i, c) if (i % n)
        {
            we = p[i % n - 1];
            forn(mask, k) if (!((1 << we) & mask))
                for (ac = i; ac <= c; ac++)
                    dp[max(ac, min(c, L[we] + i))][mask + (1 << we)] += dp[ac][mask];
        }
        g += dp[c][k - 1], a++;
    } while (next_permutation(p, p + n - 1));
    printf("%.15f", g / pow(c / n, n - 1) / a);
}


Measured memory_bytes: 2176
#include<stdio.h>
#include<iostream>
#include<vector>
#include <fstream>
#include<math.h>
#include <numeric>
#include<algorithm>
#include <stdlib.h>
# include <map>

using namespace std;

int main(){
    int n,t ,c, tmp ,ans;
    cin >> n >> t;
    vector<int> v(n , 3000);
    for (int i = 0 ;i < n ; i++){
        cin >> c >> tmp;
        if (tmp <= t){
            v.at(i) = c;
        
        }
    }
    ans =  *min_element(v.begin() , v.end());
    if (ans != 3000){
        cout <<ans << endl;
    }
    else{
        cout << "TLE" << endl;
    }
}


Measured memory_bytes: 256
<?php
list($n) = ints();
for ($i = 0; $i < $n; ++$i) list($a[]) = ints();
// 同じ色で塗れるマスをグループ分けした時のグループごとの末尾の値を格納
// この数より大きい数字であればこのグループに入れられる
$ends = [$a[0]];
for ($i = 1; $i < $n; ++$i) {
    // 二分探索で入れられるグループのうち末尾の値が最大のものを探す
    // endsは常にソート済（降順）
    $l = count($ends);
    $ok = $l;
    $ng = -1;
    while (abs($ok - $ng) > 1) {
        $mid = intdiv($ok + $ng, 2);
        if ($ends[$mid] < $a[$i]) $ok = $mid;
        else $ng = $mid;
    }
    // 見つからない場合はok=lなので要素が追加される
    $ends[$ok] = $a[$i];
}
echo count($ends);
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 24092
#include <stdio.h>

int main()
{
  char lf;
  char a[9];
  for(int i = 0; i < 3; i++) {
    scanf("%c%c%c%c", &a[3*i], &a[3*i+1], &a[3*i+2], &lf);
  }
  printf("%c%c%c\n", a[0], a[4], a[8]);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
 
#define mo 1000000007
#define inf 1e18
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rrep(i,s,n) for(ll i=s;i>=n;i--)
#define adiii \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);  \
  cout.tie(NULL);									
 
ll mod(ll n) { return (n % (ll)mo + (ll)mo)%(ll)mo;}
ll gcd(ll a,ll b) {if (b == 0) return a;return gcd(b, a % b);}
 
ll binpow(ll a, ll b) {ll res = 1;while (b > 0) {if (b & 1) res = res * a;a = a * a;b >>= 1;}return res;}

int main(){
	ll n;cin>>n;
	vector <ll> a(n);
	rep(i,0,n) cin>>a[i];
	vector<vector<ll>> dp(n,vector<ll>(n));
	
	rrep(l,n-1,0){
		rep(r,l,n){
			if(l==r) dp[l][r] = a[l];
			else{
				dp[l][r] = max(a[l]-dp[l+1][r],a[r]-dp[l][r-1]);
			}
		}
	}
	cout<<dp[0][n-1];
}


Measured memory_bytes: 70656
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const long long MAX = 100005;

int main(void){
  long long N;
  cin >> N;
  vector<long long> bucket(MAX);
  long long  sum=0;
  for(int i=0; i<N; i++) {
    long long tmp;
    cin >> tmp;
    sum += tmp;
    bucket[tmp]++;
  }
  
  long long Q;
  cin >> Q;
  
  long long  B, C;
  for(int i=0; i<Q; i++){
    cin >> B >> C;
    long long  diff = C-B;
    sum += bucket[B] * diff;
    bucket[C] += bucket[B];
    bucket[B] = 0;  
    cout << sum << "\n";
  }//for

}//main


Measured memory_bytes: 3964
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let mut s: Vec<i32> = (0..n).map(|_| read()).collect();

    s.sort();
    let sum: i32 = s.iter().sum();

    println!(
        "{}",
        if sum % 10 == 0 {
            match s.iter().find(|&&x| x % 10 != 0) {
                Some(x) => sum - x,
                None => 0,
            }
        } else {
            sum
        }
    );
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main{

	int N;
	int[] ts;
	int[] cs;

	class Swimmer{
		int speed, res, endLap, curLap;
		Swimmer(int s, int r, int e, int c){
			this.speed = s;
			this.res= r;
			this.endLap= e;
			this.curLap= c;
		}
	}

	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			N = in.nextInt();
			if(N==0) return ;
			ts = new int[N];
			cs = new int[N];
			for(int i=0; i<N; i++){
				ts[i] = in.nextInt();
				cs[i] = in.nextInt();
			}
			System.out.println(solve());
		}
	}

	int solve(){
		Swimmer[] ss = new Swimmer[N];
		for(int i=0; i<N; i++){
			ss[i] = new Swimmer(ts[i], ts[i], cs[i], 0);
		}
		Arrays.sort(ss, new Comparator<Swimmer>(){
			public int compare(Swimmer a, Swimmer b){
				return a.speed > b.speed?1:a.speed == b.speed?0:-1;
			}
		});
		ArrayList<Swimmer> Q1 = new ArrayList<Swimmer>(), Q2 = new ArrayList<Swimmer>();
		for(int i=0; i<N; i++){
			Q1.add(ss[i]);
		}
		int t = 0;
		for(;;){
			ArrayList<Swimmer> t1 = new ArrayList<Swimmer>(), t2 = new ArrayList<Swimmer>();
			ArrayList<Swimmer> s1 = new ArrayList<Swimmer>(), s2 = new ArrayList<Swimmer>();
			int proc = Q1.isEmpty()?Q2.get(0).res:Q2.isEmpty()?Q1.get(0).res:Math.min(Q1.get(0).res, Q2.get(0).res);
			t += proc;
			for(int i=0; i<Q1.size(); i++){
				Q1.get(i).res -= proc;
			}
			for(int i=0; i<Q2.size(); i++){
				Q2.get(i).res -= proc;
			}
			boolean flag = true;
			for(int i=0; i<Q1.size(); i++){
				Swimmer s = Q1.get(i);
				if(s.res > 0) flag = false;
				if(flag){
					s.res = s.speed;
					s2.add(s);
				}
				else{
					t1.add(s);
				}
			}
			flag = true;
			for(int i=0; i<Q2.size(); i++){
				Swimmer s = Q2.get(i);
				if(s.res > 0) flag = false;
				if(flag){
					if(++s.curLap < s.endLap){
						s.res = s.speed;
						s1.add(s);
					}
				}
				else{
					t2.add(s);
				}
			}
			Collections.sort(s1, new Comparator<Swimmer>(){
				public int compare(Swimmer a, Swimmer b){
					return a.speed > b.speed?1:a.speed == b.speed?0:-1;
				}
			});
			Collections.sort(s2, new Comparator<Swimmer>(){
				public int compare(Swimmer a, Swimmer b){
					return a.speed > b.speed?1:a.speed == b.speed?0:-1;
				}
			});
			for(int i=0; i<s1.size(); i++){
				t1.add(s1.get(i));
			}
			for(int i=0; i<s2.size(); i++){
				t2.add(s2.get(i));
			}
			if(t1.isEmpty() && t2.isEmpty()) break;
			Q1.clear();
			Q2.clear();
			for(int i=0; i<t1.size(); i++){
				Q1.add(t1.get(i));
			}
			for(int i=0; i<t2.size(); i++){
				Q2.add(t2.get(i));
			}
		}
		return t;
	}

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

Measured memory_bytes: 13000
#include <stdio.h>
int n,i,j,x,a[10][10],list[1000][3],size;

void push(int x,int y,int s){list[size][0]=i;list[size][1]=j;list[size][2]=s;size++;}

int check(int x,int y,int s){
	int d;
	if(s<3 && (x<1 || x>9 || y<1 || y>9)) return 0;
	if(s==3 && (x<2 || x>8 || y<2 || y>8)) return 0;
	d=a[x][y];
	if(a[x-1][y]<d)d=a[x-1][y];
	if(a[x+1][y]<d)d=a[x+1][y];
	if(a[x][y-1]<d)d=a[x][y-1];
	if(a[x][y+1]<d)d=a[x][y+1];
	if(s==1 || d==0)return d;
	if(a[x-1][y-1]<d)d=a[x-1][y-1];
	if(a[x+1][y+1]<d)d=a[x+1][y+1];
	if(a[x+1][y-1]<d)d=a[x+1][y-1];
	if(a[x-1][y+1]<d)d=a[x-1][y+1];
	if(s==2 || d==0)return d;
	if(a[x-2][y]<d)d=a[x-2][y];
	if(a[x+2][y]<d)d=a[x+2][y];
	if(a[x][y-2]<d)d=a[x][y-2];
	if(a[x][y+2]<d)d=a[x][y+2];
	return d;
}

void draw(int x,int y,int s,int d){
	if(size==3 && (x<2 || x>8 || y<2 || y>8)) return;
	a[x][y]+=d;
	a[x-1][y]+=d;
	a[x+1][y]+=d;
	a[x][y-1]+=d;
	a[x][y+1]+=d;
	if(s==1)return;
	a[x-1][y-1]+=d;
	a[x+1][y+1]+=d;
	a[x+1][y-1]+=d;
	a[x-1][y+1]+=d;
	if(s==2)return;
	a[x-2][y]+=d;
	a[x+2][y]+=d;
	a[x][y-2]+=d;
	a[x][y+2]+=d;
}

int search(int nn,int from){
	int i,x,y,s;
	for(i=from;i>=0;i--){
		x=list[i][0];y=list[i][1];s=list[i][2];
		if(y==8 && s<1 && a[x+1][y+1])return 0;
		if(a[x][y]==0 && a[x+1][y]>0)return 0;
		if(s<3 && x<8 && a[x+2][y]>0)return 0;
		if(check(x,y,s)>0){
			draw(x,y,s,-1);
			if(s==1 && a[x+1][y+1]>0 && check(x-1,y+1,3)==0){draw(x,y,s,+1);return 0;}
			if(nn>1){
				if(search(nn-1,i-1)>0){printf("%d %d %d\n",y,x,s);return 1;}
			}else{
				int p,q;
				for(p=0;p<10;p++)for(q=0;q<10;q++){{if(a[p][q]!=0)goto miss;}}
				printf("%d %d %d\n",y,x,s);return 1;miss:;
			}
			draw(x,y,s,+1);
		}
	}
	return 0;
}

int main(void){
	scanf("%d",&n);size=0;
	for(i=0;i<10;i++){for(j=0;j<10;j++){scanf("%d",&a[i][j]);}}
	for(i=1;i<9;i++){
		for(j=1;j<9;j++){
			x=check(i,j,1); if(x==0)continue; else for(;x>0;x--)push(i,j,1);
			x=check(i,j,2); if(x==0)continue; else for(;x>0;x--)push(i,j,2);
			x=check(i,j,3); if(x==0)continue; else for(;x>0;x--)push(i,j,3);
		}
	}
	//for(i=0;i<size;i++)printf("%d %d %d\n",list[i][0],list[i][1],list[i][2]);
	search(n,size-1);
	return 0;
}

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

int main() {
    long long x,y;
    cin >> x >> y;
    long long cnt = 0;
    if(x == 0){
        if(y > 0){
            cout << y << endl;
            return 0;
        }else if(y < 0){
            cout << abs(y)+1 << endl;
            return 0;
        }
    }

    if(y == 0){
        if(x > 0){
            cout << x+1 << endl;
            return 0;
        }else{
            cout << abs(x) << endl;
            return 0;
        }
    }

    if(abs(x) < abs(y)){
        cnt += abs(y)-abs(x);
        if(x * y < 0){
            cnt += 1;
        }else if(x < 0 && y < 0){
            cnt += 2;
        }
    }else if(abs(x) > abs(y)){
        cnt += abs(x) - abs(y);
        if(x > 0 && y > 0){
            cnt += 2;
        }else if(x * y < 0){
            cnt += 1;
        }
    }else{
        cnt = 1;
    }
    cout << cnt << endl; 
    return 0;
}

Measured memory_bytes: 3612
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
int maxn=1<<30;
int n;
int color[10005];
int d[10005];
vector<pair<int, int> > bian[10005];
int f()
{
    priority_queue<pair<int ,int > > pq;
    for(int i=0;i<n;i++)
    {
        d[i]=maxn;
    }
    d[0]=0;
    pq.push(make_pair(0,0));
    while(!pq.empty())
    {
        pair<int ,int > x=pq.top();
        pq.pop();
        int u=x.second;
        color[u]=1;
        if(d[u]<x.first *(-1)) continue;
        for(int i=0;i<bian[u].size();i++)
        {
            int v=bian[u][i].first;
            if(color[v]==1) continue;
            if(d[v]>(d[u]+bian[u][i].second))
            {
                d[v]=d[u]+bian[u][i].second;
                pq.push(make_pair(d[v]*(-1),v));
                color[v]=0;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        printf("%d ",i);
        printf("%d\n",(d[i]==maxn)?-1:d[i]);
    }
}
int main()
{
    int k,u,c,g;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&k,&u);
        for(int j=0;j<u;j++)
        {
            scanf("%d%d",&c,&g);
            bian[k].push_back(make_pair(c,g));
        }
    }
    f();
    return 0;
}

Measured memory_bytes: 7568
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Util{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		string S = rs();

        int ans = 0;
        int cnt = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if(S[i] == 'R') cnt++;
            else {
                ans = Math.Max(cnt, ans);
                cnt = 0;
            }
        }
        ans = Math.Max(cnt, ans);

		Console.WriteLine(ans);
		Console.ReadLine();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
    static int[] generateNums(int num, int N){return Enumerable.Repeat(num, N).ToArray();}
    static int[] generateSuretsu(int N){return Enumerable.Range(0, N).ToArray();}
}

public static class Combination {
	//使い方:int[][] Is = Combination.Enumerate(nums, k, withRepetition:false).ToArray();
    public static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k, bool withRepetition) {
        if (k == 1) {
            foreach (var item in items)
                yield return new T[] { item };
            yield break;
        }
        foreach (var item in items) {
            var leftside = new T[] { item };

            // item よりも前のものを除く （順列と組み合わせの違い)
            // 重複を許さないので、unusedから item そのものも取り除く
            var unused = withRepetition ? items : items.SkipWhile(e => !e.Equals(item)).Skip(1).ToList();

            foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
                yield return leftside.Concat(rightside).ToArray();
            }
        }
    }
}


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

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl;
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   " << endl;
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}
 
int main(){
  int D;
  cin >> D;
  vector<int> c(26, 0);
  for(int i=0; i<26; i++) cin >> c[i];
  vector<vector<int>> s(D, vector<int>(26, 0));
  for(int i=0; i<D; i++){
    for(int j=0; j<26; j++){
      cin >> s[i][j];
    }
  }

  vector<int> t(D);
  for(int i=0; i<D; i++){
    cin >> t[i];
    t[i]--;
  }
  // cout << " c: " ; print_vec(c);
  // //cout << " s: " << endl; print_vec2(s);
  // cout << " t: " ; print_vec(t);
  //vector<vector<int>> last(D, vector<int>(26, 0));
  vector<int> last(26, -1);
  ll score = 0;
  for(int d=0; d<D; d++){
    int type = t[d];
    score += s[d][type];
    last[type] = d;
  
    
    for(int i=0; i<26; i++){
      score = score - c[i] * (d - last[i]);
      //cout << " d: " << d << " i: " << i << " c[]: " << c[type] << " score: " << score << endl;
    }
    //cout << " c[3]: " << c[3] << " (d - last[3]): "<< (d - last[3]) << "  c[3] * (d - last[3]): " << c[3] * (d - last[3]) << endl;
    cout << score << endl;
  }

  // int type = 1;
  // int cnt = 0;
  // while(cnt < D){
  //   cout << type << endl;
  //   type = type % 26 + 1;
  //   cnt++;
  // }

    
}


Measured memory_bytes: 3684
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

j = sum(b) - sum(a)
c = [0, 0]
for i in range(n):
    if a[i] > b[i]:
        c[0] += a[i] - b[i]
    if a[i] < b[i]:
        c[1] += -(-(b[i]-a[i])//2)

print("Yes" if max(c) <= j else "No")


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

int main()
{
    int K, N; cin >> K >> N;
    int A[N];
    rep(i, N){
        int Ai; cin >> Ai;
        A[i] = Ai;
    }
    int max_dis = 0;
    rep(i, N){
        int dis;
        if(i != N-1){
            dis = A[i+1] - A[i];
            if(max_dis < dis) max_dis = dis;
        }else{
            dis = (K-A[i]) + A[0];
            if(max_dis < dis) max_dis = dis;
        }
    }
    cout << K - max_dis << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(){
	char s[5];
	scanf("%s",&s);
	getchar();
	
	if (s[0] != s[2]){
		printf("Yes");
}
	else if(s[1] != s[2]){
		printf("Yes");
	}
	else
	{
		printf("No");
	}
	
	return 0;
	
	
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define _abs(x)((x) < 0 ? (x) * -1 : (x))

typedef struct Node {
    long id;
    vector<Node*> connected;

    Node() : id(-1) {}
    Node(long i) : id(i) {}
} Node;

Node* update(Node *node, vector<bool> &lookUpTable) {
    Node *n;

    long i, len = node->connected.size();

    for (i = 0; i < len; i++) {
        n = node->connected[i];

        if (!lookUpTable[n->id - 1]) {
            lookUpTable[n->id - 1] = true;

            return n;
        }
    }

    return node;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //freopen("debug.txt", "w", stderr);

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

    long N, M;
    long A, B;
    vector<long> ans;

    cin >> N >> M;

    vector<Node*> nodes(N);
    Node *node1;
    Node *node2;
    vector<bool> lookUpTable(N);
    long id1, id2;

    long i, len;

    for (i = 0; i < N; i++) {
        nodes[i] = new Node(i + 1);
        lookUpTable[i] = false;
    }

    for (i = 0; i < M; i++) {
        cin >> A >> B;

        A--;
        B--;

        nodes[A]->connected.push_back(nodes[B]);
        nodes[B]->connected.push_back(nodes[A]);
    }

    node1 = nodes[0];
    node2 = nodes[0];
    id1 = 0;
    id2 = 0;
    lookUpTable[0] = true;
    ans.push_back(nodes[0]->id);

    while (node1->id != id1 || node2->id != id2) {
        id1 = node1->id;
        id2 = node2->id;

        node1 = update(node1, lookUpTable);
        node2 = update(node2, lookUpTable);

        if (node1->id != id1) ans.insert(ans.begin(), node1->id);
        if (node2->id != id2) ans.push_back(node2->id);
    }

    len = ans.size() - 1;
    cout << ans.size() << endl;
    for (i = 0; i < len; i++) cout << ans[i] << " ";
    cout << ans[len] << endl;

    len = nodes.size();
    for (i = 0; i < len; i++) delete nodes[i];

    return 0;
}


Measured memory_bytes: 10356
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;r0=x;r1=y;a0=1;a1=0;b0=0;b1=1;
  while(r1>0){q=r0/r1;r2=r0%r1;a2=a0-q*a1;b2=b0-q*b1;r0=r1;r1=r2;a0=a1;a1=a2;b0=b1;b1=b2;}
  *c=r0;*a=a0;*b=b0;
}

ll get_inv(ll n, ll p){
  ll a,b,c;
  extended_euclid(n,p,&c,&a,&b);
  if(a<p) a+=p;
  return a%p;
}

ll fact[2000100],fact_inv[2000100];

void init() {
  fact[0]=1;
  REP(i,1,2000100) fact[i]=fact[i-1]*i%MAX;
  fact_inv[2000050]=get_inv(fact[2000050],MAX);
  rrep(i,2000050)fact_inv[i]=fact_inv[i+1]*(i+1)%MAX;
}

ll nCr(int N,int K){
  if(K<0||K>N)return 0;
  return fact[N]*fact_inv[K]%MAX*fact_inv[N-K]%MAX;
}

void Main() {
  init();
  int n;
  R n;
  n++;
  int a[n],c[n];
  mem(c);
  ll d[n];
  mem(d);
  rep(i,n) {
    R a[i];
    c[a[i]]++;
  }
  vector<int> v;
  rep(i,n) {
    if(c[a[i]]>1) v.pb(i);
  }
  int t=v[1]-v[0];
  rep(i,n) d[i]=nCr(n,i+1);
  rep(i,n-t) d[i]=(d[i]-nCr(n-t-1,i)+MAX)%MAX;
  rep(i,n) pr(d[i]);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}

Measured memory_bytes: 34048
import sys

n = int(input())
s = input()
 
if n%2 == 1:
  print("No")
  sys.exit()
 
slise = (n/2)
a = s[:int(slise)]
b = s[int(slise):]
 
if a==b:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>

using namespace std;
const int INF = 1001001001;
#define rep(i,n) for(int i=0;i<n;i++)
int A,B;
int Ak[5002],Bk[5002];




int main(){
	scanf("%d %d",&A,&B);
	rep(i,A){scanf("%d",&Ak[i]);}
	rep(i,B){scanf("%d",&Bk[i]);}
	int ans=0;
	rep(i,B){
		int count=0;
		rep(j,A){
			if(Bk[i+count]==Ak[j])count++;
		}
		ans=max(count,ans);
	}
	printf("%d\n",ans);
}

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

int main() {
  int a,b,ans=0;
  cin >> a >> b;
  if(a > b){
    ans += a;
    a -= 1;
  }
  else{
    ans += b;
    b -= 1;
  }
  if(a > b){
    ans += a;
  }
  else{
    ans+= b;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output


def chkprint(*args):
    names = {id(v): k for k, v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))

# Binary converter


def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]

# --------------------------------------------


dp = None


def main():
    S = set(input().split()[0])

    if len(S) == 3:
        print("Yes")
    else:
        print("No")


main()


Measured memory_bytes: 4628
#include <bits/stdc++.h>
using namespace std;
#define fr(i,n) for (int i=0;i<n;i++)
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,a,b) for (int i=a;i>=b;i--)
#define all(cont) cont.begin(), cont.end()
#define unique(a)  sort(all(a)) , (a).erase(unique((a).begin(), (a).end()),(a).end())
#define rall(cont) cont.rbegin(), cont.rend()
#define sz(x) (int)(x).size()
#define fastio          ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define PB push_back
#define endl "\n"
#define f first
#define s second
#define mset(m,v) memset(m,v,sizeof(m))
#define mod 1000000007
const int N = 2e5 + 5;
#define PI acos(-1.0)
long double EPS = 1e-9;
typedef long long ll;
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
#define pqll_max priority_queue<ll> // max heap. push(),pop(),top(),size(),empty()
#define pqll_min priority_queue<ll,vector<ll>,greater<ll> >
#define lb(v,val)   lower_bound(v.begin(),v.end(),val) //first equal to or lower than [------------
#define ub(v,val)   upper_bound(v.begin(),v.end(),val) //first greater than ------------)
#define bs(v,x) binary_search(v.begin(),v.end(),x)
inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x; }
inline ll sub(ll a, ll b) { if (a < b)swap(a, b); return (((a%mod) - (b%mod) + mod) % mod); }
inline ll mul(ll x, ll y) { return (x%mod * 1ll * y%mod) % mod; }
inline ll pwr(ll a, ll b) { ll x = 1 % mod; while (b) { if (b & 1) x = mul(x, a); a = mul(a, a); b >>= 1; }return x % mod; }
inline ll inv(ll a) { return pwr(a, mod - 2) % mod; }
ll gcd(ll a, ll b) { if (!a)return b % mod; return gcd(b%a, a) % mod; }
#define debug(x) cout << #x << " = " << x << endl;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#define in(container) for (auto &it : container) cin>>it;
#define out(container) for (auto it : container) cout << it << " "; cout << endl;
void pre() {
}
int arr[N];
void solve() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i <= n; i++) {
		arr[i] = i;
		if(i)
		arr[i] += arr[i - 1];
	}
	int ans = 0;
	for (int i = k; i <= n + 1; i++) {
		if (i == n+1) {
			ans += 1;
			continue;
		}
		//ans += (arr[n] - arr[n - i] - arr[i - 1] + 1);
		ans += arr[n];
		ans %= mod;
		ans -= arr[n - i];
		if (ans < 0)ans+=mod;
		ans %= mod;
		ans -= arr[i - 1];
		if (ans < 0)ans += mod;
		ans %= mod;
		ans += 1;
		if (ans < 0)ans += mod;
		ans %= mod;
	}
	cout<<ans<<endl;
}
signed main()
{
	fastio;
	cout << fixed << setprecision(3);
	//clock_t begin = clock();
	//pre();
	int tc;
	tc = 1;
	//cin >> tc;
	while (tc--) {
		solve();
	}
	//clock_t end = clock();double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;cerr << elapsed_secs;
}


Measured memory_bytes: 5212
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358979323846

typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 998244353;
const int inf = 9e18;
const int N = 1e6 + 5;

int i,n,m,sum,a[N];

void solve(){
    sum=0;
    cin>>n>>m;
    for(i=0;i<m;++i){
        cin>>a[i];
        sum+=a[i];
    }
    if(n>=sum)
        cout<<n-sum;
    else
        cout<<-1;
}

signed main(){
    fastio;
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
#define ll long long int
const double mx = 2e6 + 5 ;

void solve()
{
	string s;
	cin>>s;
	vector<pair<char, int>> vect;
	int n = s.length();
	vector<int> ans(n+1);
	ll sum = 0;
	for(int i=0; i<n; i++)
	{
		if(s[i]=='<')
			ans[i+1] = max(ans[i]+1, ans[i+1]);
	}
	for(int i=n-1; i>=0; i--)
	{
		if(s[i]=='>')
			ans[i] = max(ans[i], ans[i+1]+1);
	}
	for(auto a: ans)
		sum+=a;
	cout<<sum<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 5816
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    vector<int>dp(3);
    int n,day;
    cin>>n;
    for(day=0;day<n;day++)
    {
        vector<int>c(3),newdp(3,0);
        for(int i=0;i<3;i++)
        {
            cin>>c[i];
        }
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if(i!=j)
                    newdp[j]=max(newdp[j],dp[i]+c[j]);
            }
        }
        dp=newdp;
    }
    cout<<max({dp[0],dp[1],dp[2]})<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int MAX = 1000000000;
int main(){
    ll n;
    cin >> n;
    int score[100000][3];
    for (int i = 0; i < n;i++){
        cin >> score[i][0] >> score[i][1] >> score[i][2];
    }
    ll dp[100000][3];
    for (int i = 0; i < 3;i++){
        dp[0][i] = score[0][i];
    }
    for (int i = 1; i < n;i++){
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + score[i][0];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2] )+ score[i][1];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][0] )+ score[i][2];
    }
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
}

Measured memory_bytes: 3712
var s  :array[1..2010]of array[1..2010]of char;
    u,d,l,r,t  :array[1..2010]of array[1..2010]of integer;
    i,j,k,n,h,w,ans  :integer;
    
begin
  readln(h,w);
  for i:=1 to h do begin
    for j:=1 to w do 
      read(s[i][j]);
      readln;
  end;
  {up}
  for j:=1 to w do begin
    if s[1][j]='.' then u[1][j]:=1 else u[1][j]:=0;
    for i:=2 to h do begin
      if s[i][j]='.' then u[i][j]:=u[i-1][j]+1 else u[i][j]:=0;
    end;
  end;
  {down}
  for j:=1 to w do begin
    if s[h][j]='.' then d[h][j]:=1 else d[h][j]:=0;
    for i:=h-1 downto 1 do begin
      if s[i][j]='.' then d[i][j]:=d[i+1][j]+1 else d[i][j]:=0;
    end;
  end;
  {left}
  for i:=1 to h do begin
    if s[i][1]='.' then l[i][1]:=1 else l[i][1]:=0;
    for j:=2 to w do begin
      if s[i][j]='.' then l[i][j]:=l[i][j-1]+1 else l[i][j]:=0;
    end;
  end;
  {right}
  for i:=1 to h do begin
    if s[i][w]='.' then r[i][w]:=1 else r[i][w]:=0;
    for j:=w-1 downto 1 do begin
      if s[i][j]='.' then r[i][j]:=r[i][j+1]+1 else r[i][j]:=0;
    end;
  end;
  
  ans:=0;
  for i:=1 to h do
    for j:=1 to w do begin
      if ans<(u[i][j]+d[i][j]+l[i][j]+r[i][j]-3)
        then ans:=u[i][j]+d[i][j]+l[i][j]+r[i][j]-3;
    end;
  writeln(ans);
end.

Measured memory_bytes: 67584