akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int N;
int A[18], B[18];
unsigned char dp[1 << 18][36];
int keisan(int b, bool n, int k) {
	if (dp[b][k] != 255) return dp[b][k];
	if (b == (1 << N) - 1) return 0;

	int saishou = 254;
	int num2 = 0;
	rep(i, N) {
		if (!(b >> i & 1)) {
			if (A[i] < k && B[i] < k) return dp[b][k] = 254;
			if ((n + i) & 1) {
				if (B[i] >= k) {
					chmin(saishou, keisan(b + (1 << i), !n, B[i]) + num2);
				}
			}
			else {
				if (A[i] >= k) {
					chmin(saishou, keisan(b + (1 << i), !n, A[i]) + num2);
				}
			}
			num2++;
		}
	}
	return dp[b][k] = saishou;
}

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


	cin >> N;
	rep(i, N) cin >> A[i];
	rep(i, N) cin >> B[i];

	pair<int, int> kari[36];
	rep(i, N) kari[i] = mp(A[i], i);
	rep(i, N) kari[i + N] = mp(B[i], i + N);
	sort(kari, kari + N * 2);
	int k = 0;
	int mae = kari[0].first;
	rep(i, N * 2) {
		if (mae != kari[i].first) k++;
		mae = kari[i].first;
		if (kari[i].second < N) A[kari[i].second] = k;
		else B[kari[i].second - N] = k;
	}

	rep(i, 1 << N) rep(j, k + 1) dp[i][j] = 255;

	int kotae = keisan(0, 0, 0);
	if (kotae == 254) co(-1);
	else co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 9472
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
 
using namespace std;
int MOD = 1000000007;
signed main(){
    int n,m;
    cin >> n >> m;
    int ans = 0;
    int r[10][10] = {0};
    rep(i,m){
        int a,b;
        cin >> a >> b;
        r[a-1][b-1] = 1;
        r[b-1][a-1] = 1;
    }
    vector<int> s(n);
    rep(i,n)s[i] = i;
    do {
        int c = 1;
        //debug_vec(s);
        rep(i,n-1){
            if(r[s[i]][s[i+1]] == 0)c = 0;
        }
        if(c == 1)ans++;
    } while (next_permutation(s.begin()+1,s.end()));
    cout << ans << endl;


    

    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://abc054.contest.atcoder.jp/tasks/abc054_c
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c

Measured memory_bytes: 256
num_A = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A.reverse()

INF = 10 ** 6
dp = [-INF for i in range(N + 1)]    # get the max digit size using i matches
dp[0] = 0
for i in range(1, N + 1):
    next_num = [Ai for Ai in A if num_A[Ai] <= i]
    if next_num != []:
        dpi_candidate = [dp[i - num_A[next_numi]] + 1
                         for next_numi in next_num]
        dp[i] = max(dpi_candidate)

remain_match = N
ans = ""
while remain_match > 0:
    for Ai in A:
        if remain_match >= num_A[Ai] and dp[remain_match - num_A[Ai]] == dp[remain_match] - 1:
            ans += str(Ai)
            remain_match -= num_A[Ai]
            break

print(int(ans))


Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <math.h> 
#include <algorithm>
using namespace std;

int main() {
  int N;
  string S, T;
  cin >> N >> S >> T ;
  
  for (int i = 0; i < N; i++) {
    cout << S[i] << T[i];
  }
  
  cout << endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int dfs(int d, int n, int s) {
  if (n == 0 && s == 0) return 1;
  if (d == 10) return 0;
  return dfs(d + 1, n, s) + dfs(d + 1, n - 1, s - d);
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n, s;
  while (cin >> n >> s, n) {
    cout << dfs(0, n, s) << endl;
  }

  return 0;
}


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

/* 大文字を小文字に変換 */
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"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    int n; cin >> n;
    double p[n];
    rep(i,n) cin >> p[i];

    double dp[n][n+1];
    rep(i,n) rep(j,n+1) dp[i][j] = 0.0;
    dp[0][0]  = (1.0-p[0]);
    dp[0][1] = p[0];

    for(int i=1; i<n; i++){
        rep(j,n+1){
            if(j == 0) dp[i][j] = dp[i-1][j]*(1.0-p[i]);
            else dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1.0-p[i]);
        }
    }

    double res = 0.0;
    rep(i,n+1){
        if(i>n/2) res += dp[n-1][i];
    }
    printf("%2.10f\n", res);
    // cout << res << endl;
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

vector <int> a;
vector <int> b;

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0 ; i<n ; i++) {
		int x;
		scanf("%d", &x);
		a.pb(x);
	}
	for (int i=0 ; i<n ; i++) {
		int x;
		scanf("%d", &x);
		b.pb(x);
	}
	if (a>b) swap(a, b);
	int cnt = 0;
	while (a != b) {
		cnt++;
		next_permutation(a.begin(), a.end());
	}
	printf("%d\n", cnt);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class D
{
	static void Main()
	{
		var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
		int h = a[0], w = a[1];
		var s = new int[h].Select(_ => Console.ReadLine().Select(x => x == '#' ? -1 : 0).ToArray()).ToArray();

		for (int i = 0; i < h; i++)
		{
			for (int t = 0, j = 0; j < w; j++)
				if (s[i][j] == -1) t = 0;
				else s[i][j] += t++;
			for (int t = 0, j = w - 1; j >= 0; j--)
				if (s[i][j] == -1) t = 0;
				else s[i][j] += t++;
		}
		for (int j = 0; j < w; j++)
		{
			for (int t = 0, i = 0; i < h; i++)
				if (s[i][j] == -1) t = 0;
				else s[i][j] += t++;
			for (int t = 0, i = h - 1; i >= 0; i--)
				if (s[i][j] == -1) t = 0;
				else s[i][j] += t++;
		}
		Console.WriteLine(s.SelectMany(x => x).Max() + 1);
	}
}


Measured memory_bytes: 49720
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 10000000;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<P, int> PP;
typedef pair<int, PP> PPP;
struct edge { int to; int to2; int cost; };

int used[2000];

signed main(){
	int n, k; cin >> n >> k;
	if ((n + 1) / 2 >= k)puts("YES");
	else puts("NO");
	}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<numeric>
#include<cassert>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define rep(i,s,n) for(int i=(s); i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x)

using namespace std;

typedef unsigned int uint;
typedef long long ll;

const int _dx[] = {0,1,0,-1};
const int _dy[] = {-1,0,1,0};

int getInt(){
  int ret = 0,c;
  c = getchar();
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)){
    ret *= 10;
    ret += c - '0';
    c = getchar();
  }
  return ret;
}

#define MAX 100001
long double ans[MAX];
long double *memo,*prev;
long double buff[2][110];
long double pp[110];

int main(){
  memo = buff[0];
  prev = buff[1];

  prev[1] = 1.0;
  ans[1] = 1.0;
  REP(i,110) pp[i] = pow(1.0/2.0, i);
  rep(i,2,MAX){
    //printf("%d\n",i);
    if(i > 3000){
      ans[i] = ans[i-1] + 0.621446217;
    }else{
      ans[i] = ans[i-1];
      memo[0] = 0.0;
      rep(j,1,110){
        double tmp = prev[j-1] * pp[j-1];
        memo[j]  = tmp;
        memo[0] += prev[j-1] - tmp;
        ans[i] += tmp;
      }
      swap(prev, memo);
    }
    /*
    if(i < 5){
      REP(j,4) printf("%.3f ",(double)memo[j]);
      puts("");
    }
    */
  }

  int n;
  while(n = getInt()) printf("%.8f\n",(double)ans[n]);
  return 0;
}

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

int main() {
  // ここにプログラムを追記
  int N , A ;
  cin >> N >> A ;
  if (N % 500  <= A ) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
//#include<array>
#include<algorithm>
#include<deque>
#include<vector>
//#include<utility>
//#include<set>
#include<map>
//#include<list>

using namespace std;
using LLI = long long int;

//vector<int>dir_x = { 0,0,1,1,1,-1,-1,-1 };
//vector<int>dir_y = { 1,-1,1,0,-1,1,0,-1 };
//vector<int>dir_x2 = { 0,0,1,-1 };
//vector<int>dir_y2 = { 1,-1,0,0 };
//vector<char>alp = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };

//class UnionFind {
//public:
//	vector<int>data;
//	UnionFind(int size) :data(size, -1) {};
//	bool unionset(int x, int y) {
//		x = root(x), y = root(y);
//		if (x != y) {
//			if (data[y] < data[x]) {
//				swap(x, y);
//			}
//			data[x] += data[y];
//			data[y] = x;
//		}
//		return x != y;
//	}
//	bool findset(int x, int y) {
//		return root(x) == root(y);
//	}
//	int root(int x) {
//		return data[x] < 0 ? x : data[x] = root(data[x]);
//	}
//	int size(int x) {
//		return -data[root(x)];
//	}
//};

//LLI gcd(LLI x, LLI y) {
//	LLI tmp, r;
//	if (x < y) {
//		tmp = x;
//		x = y;
//		y = tmp;
//	}
//	r = x % y;
//	while (r != 0) {
//		x = y;
//		y = r;
//		r = x % y;
//	}
//	return y;
//}
//LLI lcm(LLI x,LLI y) {
//	return x / gcd(x,y) * y;
//}

//long nCr(int n,int r) {
//	long ans = 1;
//	for (int i = n; i > n - r;i--) {
//		ans = ans * i;
//	}
//	for (int i = 1; i < r + 1;i++) {
//		ans = ans / i;
//	}
//	return ans;
//}

//const int n_max = 8;
//array<array<bool, n_max>, n_max>graph;
//int dfs(int v,int N,array<bool,n_max>visited) {
//	int ret = 0;
//	bool all_visited = true;
//	for (int i = 0; i < N;i++) {
//		if (visited[i] == false) {
//			all_visited = false;
//		}
//	}	
//	if (all_visited) {
//		return 1;
//	}
//	for (int i = 0; i < N;i++) {
//		if (graph[v][i] == false) {
//			continue;
//		}
//		if (visited[i] == true) {
//			continue;
//		}
//		visited[i] = true;
//		ret += dfs(i,N,visited);
//		visited[i] = false;
//	}
//	return ret;
//}

//vector<vector<int>>sub;
//int dfs(int id) {
//	if (sub[id].size() == 0) {
//		return 1;
//	}
//	int minP = (int)1e9;
//	int maxP = 0;
//	for (int i : sub[id]) {
//		int P = dfs(i);
//		minP = min(minP, P);
//		maxP = max(maxP, P);
//	}
//	return minP + maxP + 1;
//}

int main(void) {
	string S, T;
	int place = 0;
	bool res = false;
	cin >> S >> T;
	for (int i = 0; i < S.size() - T.size() + 1; i++) {
		for (int j = 0; j < T.size(); j++) {
			if (S[i + j] == T[j] || S[i + j] == '?') {
				/*
				
				
				もうだめだ
				RE
				はぁ
				
				
				
				*/
			}
			else {
				break;
			}
			if (j == T.size() - 1) {
				place = i;
				res = true;
			}
		}
	}
	if (res) {
		for (int i = 0; i < T.size(); i++) {
			S[i + place] = T[i];
		}
		for (int i = 0; i < S.size(); i++) {
			if (S[i] == '?') {
				S[i] = 'a';
			}
		}
		cout << S << endl;
	}
	else {
		cout << "UNRESTORABLE" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
/**
 * File    : A.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-4-28 20:51:18
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
ll A[200010];
ll sum[200010];
map<ll, ll> M;

int main()
{
  cin >> N;
  for (auto i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  sum[0] = A[0];
  for (auto i = 1; i < N; i++)
  {
    sum[i] = sum[i - 1] + A[i];
  }
  M[0] = 1;
  for (auto i = 0; i < N; i++)
  {
    if (M.find(sum[i]) == M.end())
    {
      M[sum[i]] = 1;
    }
    else
    {
      M[sum[i]]++;
    }
  }
  ll ans = 0;
  for (auto x : M)
  {
    ll c = x.second;
    ans += c * (c - 1) / 2;
  }
  cout << ans << endl;
}

Measured memory_bytes: 15872
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <set>
#include <queue>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define pb(x) push_back(x)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1e9+7;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int N=100+5;
struct Node
{
    int to,next;
    //Node(int a,int b):to(a),next(b) {}
} e[N*N];
int first[N],cnt;
void insert(int u,int v)
{
    ++cnt;
    e[cnt].to=v;
    e[cnt].next=first[u];
    /*e[++cnt]=(node)
    {
        v,first[u]
    };*/
    first[u]=cnt;
    ++cnt;
    e[cnt].to=u;
    e[cnt].next=first[v];
    /*e[++cnt]=(node)
    {
        u,first[v]
    };*/
    first[v]=cnt;
}
int dfn[N],low[N];
int sum;
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++cnt;
    for(int k=first[x]; k; k=e[k].next)
    {
        if(!dfn[e[k].to])
        {
            tarjan(e[k].to,x),low[x]=min(low[x],low[e[k].to]);
            if(low[e[k].to]>dfn[x])
                sum++;
        }
        else if(e[k].to!=fa)
            low[x]=min(low[x],dfn[e[k].to]);
    }
}
int main()
{
    int n,m,u,v;
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d",&u,&v);
            insert(u,v);
        }
        cnt=0;
        for(int i=1; i<=n; i++)
            if(!dfn[i])
                tarjan(i,-1);
        printf("%d\n",sum);
    }
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int N, A;
    cin >> N;

    long res = 0;
    for (int n = 0; n < N; n++) {
        cin >> A;
        while (A % 2 == 0) {
            A /= 2;
            res++;
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
t = int(input())
i = 0
def Right_Tri(m,n,o):
    a = (n**2+o**2)**(0.5)
    if m == a:
        return True

while(i<t):
    m,n,o = map(int, input().split())
    if (Right_Tri(m,n,o) or Right_Tri(n,o,m) or Right_Tri(o,m,n) == True):
        print("YES")
    else:
        print("NO")
    i += 1





Measured memory_bytes: 5652
n, m = map(int, input().split())
l = set()
for i in range(m):
  l.add(int(input()))

ans = [0]*(n+1)
for j in range(n+1):
  if j in l:
    ans[j] = 0
  else:
    if j == 0:
      ans[j] = 1
    elif j == 1:
      ans[j] = ans[j-1]
    else:
      ans[j] = ans[j-1] + ans[j-2]
print(ans[-1]%1000000007)

Measured memory_bytes: 460020
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main(void) {
  int n;
  cin >> n;
  ll cnt[10][10];
  rep(i, 10) rep(j, 10) {
    cnt[i][j] = 0;
  }
  rep(i, n + 1) {
    if(i == 0)
      continue;
    if(i < 10) {
      ++cnt[i][i];
      continue;
    }
    if(!(i % 10))
      continue;
    int k = 10;
    int p = 1;
    while(i / k >= 10) {
      ++p;
      k *= 10;
    }
    int rd = i % 10;
    int ld = i / k;
    ++cnt[rd][ld];
  }
  ll ans = 0;
  rep(i, 10) rep(j, 10) ans += cnt[i][j] * cnt[j][i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

int main(){
  int n;
  cin >> n;
  vector<int> h(n);
  rep(i,n){
    cin >> h[i];
  }
  vector<int> a(n);
  a[0] = 0;
  
  for(int i = 1; i < n; i++){
    if(h[i] > h[i-1]){
      a[i] = 0;
    }else{
      a[i] = a[i-1] + 1;
    }
  }
  
  sort(a.begin(),a.end(),greater<int>());
  
  cout << a[0];
  return 0;
}

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

int main() {
  int h,w,a;
  cin>>h>>w;
  std::vector<string> v(h);
  for(int i=0;i<h;i++)cin>>v[i];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(v[i][j]=='#')cout<<"#";
      else{
        a=0;
        for(int k=max(0,i-1);k<min(h,i+2);k++){
          for(int l=max(0,j-1);l<min(w,j+2);l++){
            if(v[k][l]=='#')a++;
          }
        }
        cout<<a;
    }
  }
  cout<<endl;
}
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

const long long MOD = 1e9 + 7;

class Combination {
    //a^p%mod
    ll powmod(ll a, ll p) {
        ll ans = 1LL;
        ll mul = a;
        // p >>=1 <-> p=(p >> 1)
        for (; p > 0; p >>= 1, mul = (mul * mul) % mod) {
            if ((p & 1) == 1) ans = (ans * mul) % mod;
        }

        return ans;
    }
public:
    int N;
    ll mod;
    vector<ll> fact;
    vector<ll> revFact;

    Combination(int n, ll m) : N(n), mod(m), fact(n+1), revFact(n+1) {
        fact[0] = 1;
        for (int i = 1; i <= N; i++) {
            fact[i] = fact[i-1] * i;
            fact[i] %= mod;
        }

        // Fermat's little theorem
        revFact[N] = powmod(fact[N], mod - 2);

        for (int i = N-1; i >= 0; i--) {
            revFact[i] = revFact[i+1] * (i+1);
            revFact[i] %= mod;
        }
    }

    ll get(int a, int b) {
        if (a < 0 || b < 0) return 0;
        if (b > a) return 0;
        return (((fact[a] * revFact[b]) % mod) * revFact[a-b]) % mod;
    }
};


int main(){
    int N, K;
    cin >> N >> K;
    ll a[N];
    for(int i = 0; i < N; i++) cin >> a[i];

    sort(a, a + N);

    Combination cm = Combination(N, MOD);

    ll ans = 0;

    //iが最大としてつかわれる
    for(int i = 0; i < N; i++){
        ll cnt = cm.get(i, K - 1);
        ans += (cnt * a[i]) % MOD;
        ans %= MOD;
    }

    //iが最小
    for(int i = 0; i < N; i++){
        ll cnt = cm.get(N - i - 1, K - 1);
        ans -= (cnt * a[i]) % MOD;
        ans += MOD;
        ans %= MOD;
    }

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


Measured memory_bytes: 2560
#include <iostream>
using namespace std;
int dp[100000];
bool ok[100000];
int main(void){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        dp[i]=1;
        ok[i]=false;
    }
    ok[0]=true;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--,b--;
        dp[a]--,dp[b]++;
        if(ok[a])ok[b]=true;
        if(!dp[a])ok[a]=false;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        //cout<<dp[i]<<ok[i]<<endl;
        if(dp[i]&&ok[i])ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
//#define Fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define sz(a) (int)(a).size()
const int mod=2e9;
signed main(){
	int n;
	sl(n);
	int arr[n+1],dp[n+5];
	for(int i=1;i<=n+4;i++){
		dp[i]=mod;
	}
	dp[1]=0;
	for(int i=1;i<=n;i++)sl(arr[i]);
	
	for(int i=1;i<=n;i++){
		if(i+1<=n)
		dp[i+1]=min(dp[i+1],dp[i]+abs(arr[i+1]-arr[i]));
		if(i+2<=n)
		dp[i+2]=min(dp[i+2],dp[i]+abs(arr[i+2]-arr[i]));
	}
	
	//for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
	
	cout<<dp[n]<<endl;
	
	
}




Measured memory_bytes: 1792
// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;
using std::queue;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n = input<int>();

    vector<string> gr(n);
    input_seq(ALL(gr));
    
    int ans = -1;
    for (int v = 0; v < n; ++v) {
        vector<int> dist(n, -1);
        dist[v] = 1;

        queue<int> q;
        q.push(v);

        while (not q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int w = 0; w < n; ++w)
                if (gr[u][w] == '1' and dist[w] == -1) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
        }

        bool ok = true;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (gr[i][j] == '1' and dist[i] == dist[j]) {
                    ok = false;
                }

        if (ok)
            ans = max(ans, *std::max_element(ALL(dist)));
        else
            break;
    }

    cout << ans << "\n";

    return 0;
}


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

int main(){ 
  
  int N,Q; cin >> N >> Q;
  
  string s; cin >> s;
  
  vector<char> t(Q),d(Q);
  
  for(int i = 0; i < Q; i++){ cin >> t[i] >> d[i];}
  
  int Lmost,Rmost;
  // 落ちる区間の最左端と最右端を求める
  
  int left = -1; int right = N; //まずはLmostから求める
  
  while( right-left > 1){
    
    int mid = (left+right)/2; //この位置のゴーレムがQ回の操作で左端まで到達するかを判定
    
    int pos = mid; //現在地
    
    for(int i = 0; i < Q; i++){ 
      if( t[i] != s[pos]){ continue;}
      
      if( d[i] == 'L'){ pos--;}
      else{ pos++;}
      
      if( pos < 0 || pos >= N){ break;}
    }
    
    if(pos < 0){ //もうちょいleftを大きくできる
      left = mid;}
    
    else{
      right = mid;}
  }
  
  Lmost = left;
  
  left = -1; right = N;
  
  while( right-left > 1){
    
    int mid = (left+right)/2;
    
    int pos = mid;
    
    for(int i = 0; i < Q; i++){
      
      if( t[i] != s[pos]){ continue;}
      
      if( d[i] == 'L'){ pos--;}
      else{ pos++;}
      
      if(pos < 0 || pos >= N){ break;}
    }
    
    
    if( pos >= N ){ right = mid;} //もうちょいrightを小さくしたい
    else{ left = mid;}
  }
  
  Rmost = right;
  
  // Lmost,Rmostがそれぞれ条件を満たすか判定
  
  int ans = N;
  
  int pos = Lmost;
  
  for(int i = 0; i < Q; i++){
    
    if(t[i] != s[pos]){ continue;}
    
    if( d[i] == 'L'){ pos--;}
    else{ pos++;}
 
    if( pos < 0 || pos >= N){ break;}
  }
  
  if( !(pos < 0)){ //ここを含まない
    Lmost--;
  }
    
  pos = Rmost;
  
  for(int i = 0; i < Q; i++){
    
    if(t[i] != s[pos]){ continue;}
    
    if( d[i] == 'L'){ pos--;}
    else{ pos++;}
    
    if( pos < 0 || pos >= N){ break;}
    
  }
  
  if( !(pos >= N)){ //ここを含まない
    Rmost++;
  }
  
  ans -= (Lmost-Rmost+N+1);
  
  cout << ans << endl;
  
  return 0;
} 

Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll  n,x,t;
    cin>>n>>x>>t;
    cout<<t*((n+x-1)/x);
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

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

    int n; cin >> n;
    string s; cin >> s;
    vector<int> vec;
    rep(i, n) {
        vec.push_back(s[i]-'0');
    }

    int ans = 0;
    FOR(i, 0, 1000) {
        vector<int> tmp;
        int num = i;
        while(num) {
            tmp.push_back(num%10);
            num /= 10;
        }
        while(tmp.size()<3) {
            tmp.push_back(0);
        }
        reverse(all(tmp));

        int cur = 0;
        rep(j, n) {
            if (tmp[cur]==vec[j]) cur++;
            if (cur==3) break;
        }
        if (cur==3) ans++;
    }

    cout << ans << endl;
}

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

int main() {

int n,k;
cin >> n >> k;
//int *num=new int[3];

//int num[]={300000,200000,100000,0};
//string *name=new string[N+1];
int res=0;
for(int i=1;i<=n;i++){
if(i%2==1)res++;
}

if(res>=k)
cout << "YES" << endl;
else
cout << "NO" << endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a, b, c, d;
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    long long ans = max(a*c, max(a*d, max(b*c, b*d)));
    printf("%lld\n", ans);
}

Measured memory_bytes: 3840
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string a="";
	char c;
	cin>>c;
	a += c;
	cin>>c;
	a += c;
	cin>>c;
	a += c;
	int y = stoi(a);
	if(y%4==0)
		cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 1; i < n+1; i++)
int main(){ 
    int n;
    cin>>n;
    long long int a=1;
REP(i,n){
    a*=i;
    a=a%1000000007;
}
cout<<a;
    return 0;
}


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

int main(){
	int N, T;
	cin >> N >> T;
	int t[N];
	rep(i,N) cin >> t[i];
	ll ans = 0;
	rep(i,N-1) {
		ans += (ll)min(T, t[i+1]-t[i]);
	}
	ans += (ll)T;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 4420
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a.at(i);
  ll cnt = 0;
  rep(i, n - 1) {
    if (a.at(i) == a.at(i + 1)) {
      ++i;
      ++cnt;
    }

  }
  cout << cnt << endl;

  return 0;
}

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

using namespace std;

vector<int> v;
queue<int> q;

bool myf(int n){
	int arr[3]={0,};
	while(n){
		int x = n%10;
		if(x==3) arr[0]=1;
		if(x==5) arr[1]=1;
		if(x==7) arr[2]=1;
		n/=10;
	}
	return arr[0]*arr[1]*arr[2];
}

int main(void)
{
	int n; scanf("%d",&n);
	q.push(3); q.push(5); q.push(7);
	while(1){
		int x = q.front(); q.pop();
		int arr[3]={3,5,7};
		bool flg = false;
		for(int i=0;i<3;i++){
			int nx = 10*x + arr[i];
			if(nx>=1000000000){
				flg = true;
				break;
			}
			q.push(nx);
			if(myf(nx)) v.push_back(nx);
		}
		if(flg) break;
	}
	vector<int>::iterator low = upper_bound(v.begin(),v.end(),n);
	printf("%d",low-v.begin());
	return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
	int n, ans;
	cin >> n;
	ans = n;
	for(int i = 0; i <= n; i++){
		int t = i, c = 0;
		while(t > 0){
			c += t % 6;
			t /= 6;
		}
		t = n - i;
		while(t > 0){
			c += t % 9;
			t /= 9;
		}
		ans = min(ans, c);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
*A,=map(int,input().split())
ref,count={},0

for i,a in enumerate(A):
  if i-a in ref:
     count += ref[i-a]
  if i+a in ref:
     ref[i+a]+=1
  else:
     ref[i+a]=1

print(count)

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

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

typedef long long ll;

using namespace std;

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

//long long int kaizyo(long long int hh){
  //  cmp=1;
    //while(hh>1){
      //  cmp=(cmp*hh)%MOD;
        //hh--;
    //}
    //return cmp;
//}
//long long int ruizyo(long long int aa, long long int bb){
  //  if(aa==0){
    //    return 1;
    //}
    //else if(aa%2==0){
      //  long long int tt=ruizyo(aa/2,bb);
        //return (tt*tt)%MOD;
    //}
    //else{
      //  return (ruizyo(aa-1,bb)*bb)%MOD;
    //}
//}フェルマ－のア


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

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

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

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

//visited=vector<vector<bool>>(10,vector<bool>(10,false));アを全部falseに


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,q,k,depth[10000000];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
using edge = struct{ll to,cost;};
vector<edge> tree[10000000];

void dfs(int now,int p,ll d){
    //現在の頂点　親　距離
    depth[now]=d;
    for(auto &e : tree[now]){
        if(e.to==p)continue;
        dfs(e.to,now,d+e.cost);
    }
}

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

       cin >> n;
       rep(i,n-1){
           cin>>a>>b>>c;
           a--;
           b--;
           tree[a].push_back({b,c});
           tree[b].push_back({a,c});
       }
      cin>>q>>k;
      k--;
      dfs(k,-1,0);
      rep(i,q){
          cin>>x>>y;
          x--;y--;
          Cout(depth[x]+depth[y]);
      }
       
return 0;
}


Measured memory_bytes: 246656
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  for(int i = 0; i < S.size(); i++){
    char idx = S[i];
    idx += N;
    if(idx > 90){
      idx -= 26;
    }
    S[i] = idx;
  }
  cout << S << endl;
}


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

using namespace std;

int main() {
  int answer = 0;
  string S;
  cin >> S;
  for (char c : S) {
    if (c == '+') {
      answer++;
    } else {
      answer--;
    }
  }
  cout << answer;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
s = list(input())
if s[1] == 'o':
    ans = [['S', 'S', 'S'], ['W', 'S', 'W'], ['S', 'W', 'W'], ['W', 'W', 'S']]
else:
    ans = [['S', 'S', 'W'], ['W', 'S', 'S'], ['S', 'W', 'S'], ['W', 'W', 'W']]

for i in range(4):
    for j in range(2, N-1):
        if s[j] == 'o':
            n0, n1 = 'S', 'W'
        else:
            n0, n1 = 'W', 'S'
        if ans[i][j-1] == 'S':
            if ans[i][j] == 'S':
                ans[i].append(n0)
            else:
                ans[i].append(n1)
        else:
            if ans[i][j] == 'S':
                ans[i].append(n1)
            else:
                ans[i].append(n0)
    
    Realize = True
    for j in [-1, 0]:
        if s[j] == 'o':
            if ans[i][j] == 'S':
                if ans[i][j-1] != ans[i][j+1]:
                    Realize = False
                    break
            else:
                if ans[i][j-1] == ans[i][j+1]:
                    Realize = False
                    break
        else:
            if ans[i][j] == 'S':
                if ans[i][j-1] == ans[i][j+1]:
                    Realize = False
                    break
            else:
                if ans[i][j-1] != ans[i][j+1]:
                    Realize = False
                    break
    if Realize:
        print(''.join(ans[i]))
        exit()
print(-1)

Measured memory_bytes: 7376
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define MAXN 101
int N;
ll T[MAXN];
ll gcd(ll a,ll b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
    cin >> N;
    rep(i,N)cin >> T[i];
    ll ans = T[0];
    for(int i=1;i<N;i++){
        ans *= T[i]/gcd(ans,T[i]);
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 256
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(t) t.begin(), t.end()

bool isPrime(int n) {
	static int lim = 1e5;
	static bool done = false;
	static vector<bool> isp(lim + 1, 1);
	if (!done) {
		isp[0] = isp[1] = false;
		for (int i = 2; i <= lim; i++) {
			if (isp[i]) {
				for (int j = i + i; j <= lim; j += i) {
					isp[j] = false;
				}
			}
		}
		done = true;
	}
	return isp[n];
}

int main() {
	int lim = 1e5;
	vector<int>cumlativeSum(lim + 1, 0);
	for (int i = 1; i <= lim; i++) {
		int isLike = i % 2 == 1 && isPrime(i) && isPrime((i + 1) / 2) ? 1 : 0;
		cumlativeSum[i] = cumlativeSum[i - 1] + isLike;
	}
	int q;
	cin >> q;
	vector<int>l(q), r(q);
	rep(i, q)cin >> l[i] >> r[i];
	rep(i, q)cout << cumlativeSum[r[i]] - cumlativeSum[l[i]-1] << endl;


	return 0;
}





Measured memory_bytes: 1792
n,x = input().split()
n = int(n)
x = int(x)
candies = input().split()
candies = [int(i) for i in candies]
count = 0
for i in range(n-1):
  if candies[i]+candies[i+1] > x:
    k = candies[i+1]-(candies[i]+candies[i+1]-x)
    if k >= 0:
      count += candies[i]+candies[i+1]-x
      candies[i+1] = k
    else:
      count += candies[i+1]
      candies[i+1] = 0
      count += candies[i] - x
      candies[i] = candies[i] - x
    
print(count)

Measured memory_bytes: 14844
// ConsoleApplication1.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>

using namespace std;

int main()
{
    int a, b, c, k;
    int sum = 0;
    cin >> a >> b >> c >> k;
    if (k >= a) {
        sum = a;
        k = k - a;
        if (k >= b) {
            k = k - b;
            if (k > 0) {
                sum -= k;
            }
        }
    }
    else {
        sum = k;
    }
    cout << sum;
    return 0;
}

// プログラムの実行: Ctrl + F5 または [デバッグ] > [デバッグなしで開始] メニュー
// プログラムのデバッグ: F5 または [デバッグ] > [デバッグの開始] メニュー

// 作業を開始するためのヒント: 
//    1. ソリューション エクスプローラー ウィンドウを使用してファイルを追加/管理します 
//   2. チーム エクスプローラー ウィンドウを使用してソース管理に接続します
//   3. 出力ウィンドウを使用して、ビルド出力とその他のメッセージを表示します
//   4. エラー一覧ウィンドウを使用してエラーを表示します
//   5. [プロジェクト] > [新しい項目の追加] と移動して新しいコード ファイルを作成するか、[プロジェクト] > [既存の項目の追加] と移動して既存のコード ファイルをプロジェクトに追加します
//   6. 後ほどこのプロジェクトを再び開く場合、[ファイル] > [開く] > [プロジェクト] と移動して .sln ファイルを選択します

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

int main()
{
    lint n;
    cin >> n;
    lint ans=0, tmp;
    vector<lint> a(n);
    REP(i, n) {
        cin >> a[i];
        if((i%2==0)&&(a[i]%2==1))
            ans++;
        }
    cout << ans <<"\n";

    return 0;
}

Measured memory_bytes: 3624
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

n = int(input())
xs = [int(input()) for _ in range(n)]
d = {}
for i, x in enumerate(sorted(xs)):
    d[x] = i

segtree = SegTree([0]*n, n, 0, max)
r = 0
for x in xs:
    xi = d[x]
    y = segtree.query(xi, n)
    segtree.update(xi, y+1)
    r = max(r, y+1)
print(r)



Measured memory_bytes: 74088
import itertools
import itertools
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
S = [list(sys.stdin.readline().rstrip()) for _ in range(H)]
seen = np.zeros((H, W), dtype=bool)

ans = 0
for h, w in itertools.product(range(H), range(W)):
    if seen[h][w]:
        continue
    que = deque()
    que.append((h, w))
    black = white = 0
    while que:
        h, w = que.popleft()
        if seen[h][w]:
            continue
        seen[h][w] = True
        if S[h][w] == '#':
            black += 1
        else:
            white += 1
        for dh, dw in zip((h + 1, h - 1, h, h), (w, w, w + 1, w - 1)):
            if 0 <= dh < H and 0 <= dw < W and not seen[dh][dw]:
                if S[h][w] != S[dh][dw]:
                    que.append((dh, dw))
    ans += black * white
print(ans)


Measured memory_bytes: 13928
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>
#include <fstream>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

template<typename T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);


    ll A, B, C;
    cin >> A >> B >> C;

    ll ans = (A % 2) * B * C;
    chmin(ans, (B % 2) * A * C);
    chmin(ans, (C % 2) * A * B);

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

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

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    cout<<((n*(n-1))>>1);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int k=0;
	char s[5],a1=' ',a2=' ';
	gets(s);
	a1=s[0];
	for(int i=1;i<4;i++)
	{
		if(s[i]!=a1)
		{
			a2=s[i];
			k=i+1;
			break;
		}
	}
	if(a2==' ')
	{
		printf("No");
		return 0;
	}
	for(int i=k;i<4;i++)
	{
		if(s[i]!=a1&&s[i]!=a2)
		{
			printf("No");
			return 0;
		}
	}
	printf("Yes");
}

Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
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;}

int main(){
	int h,w;
	cin >> h >> w;
	vector<string> s(h);
	REP(i,h) cin >> s[i];
	
	vector<vector<int>> E(h*w); 
	int dotmasu=0;
	REP(i,h){
		REP(j,w){
			if(s[i][j]=='#') continue;
			
			dotmasu++;
			if(i!=h-1 && s[i+1][j]=='.'){
				E[i*w+j].push_back((i+1)*w+j);
				E[(i+1)*w+j].push_back(i*w+j);
			}
			if(j!=w-1 && s[i][j+1]=='.'){
				E[i*w+j].push_back(i*w+(j+1));
				E[i*w+(j+1)].push_back(i*w+j);
			}
		}
	}
	
	queue<pair<int,int>> q;
	vector<int> count(h*w, -1);
	count[0] = 1;
	q.push({0,1});
	while(!q.empty()){
		int now = q.front().first;
		int dist = q.front().second;
		q.pop();
		
		for(auto child: E[now]){
			if(count[child]==-1){
				count[child] = dist+1;
				q.push({child, dist+1});
			}
		}
	}
	
	if(count[h*w-1]==-1){
		cout << -1 << endl;
	}else{
		cout << dotmasu - count[h*w-1] << endl;
	}
	
	return 0;
}

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

int main(){
	long long n,sum=0;
	cin >> n;
	for(int i=1;i<=n;i++){
		sum+=i;
		if(sum>=n){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
"use strict";
    
const main = arg => {
    const packs = arg.split("\n")[0].split(" ").map(n=>parseInt(n)).sort((a,b)=>b-a);
    
    if(packs[0] === packs[1] + packs[2]) {
        console.log("Yes");
    } else {
        console.log("No");
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 9420
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  string s; cin >> s; bool flag = true;
  ll n = s.size();
  
  s.pop_back();
  
  while(flag){
    bool flag2 = true;
    if(n % 2 == 0){
      for(ll i=0; i < n/2; i++){
        if(s[i] != s[n/2 + i]){
          flag2 = false;
          break;
        }
      }
    }
    else flag2 = false;
    
    if(flag2){
      flag = false;
      break;
    }
    
    s.pop_back();
    n = s.size();
  }
  
  cout << s.size() << endl;
  
  
}

Measured memory_bytes: 3616
def main():
    H,N = map(int, input().split())
    weight = list(); value = list()
    for n in range(N):
        temp = input().split()
        weight.append(int(temp[0]))
        value.append(int(temp[1]))
    
    inf = float("inf")
    dp = [[inf for i in range(H+max(weight)+1)] for j in range(N+1)]
    for i in range(N+1): dp[i][0] = 0
    for i in range(N):
        for h in range(H+max(weight)+1):
            if(weight[i] <= h):
                dp[i+1][h]=min(dp[i][h-weight[i]]+value[i], dp[i+1][h-weight[i]]+value[i], dp[i][h])
            else:
                dp[i+1][h]=dp[i][h]
    res = int(min(dp[N][H:]))
    print(res)



if __name__ == "__main__":
    main()


Measured memory_bytes: 414216