akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
typedef pair<int, int> range;
typedef pair<bool, range> ret;
vector<int> T[100000];
bool setv[100000];
int val[100000];
range valr[100000];
ret check(int v, int p) {
	int l = -(1 << 30), r = 1 << 30;
	for (int to : T[v]) {
		if (to == p) continue;
		ret retv = check(to, v);
		if (!retv.first) return ret(false, range(-1, -1));
		l = max(l, retv.second.first);
		r = min(r, retv.second.second);
	}
	if (l > r) return ret(false, range(-1, -1));
	if (setv[v]) {
		if (l <= val[v] && val[v] <= r) {
			valr[v] = range(val[v], val[v]);
			return ret(true, range(val[v] - 1, val[v] + 1));
		}
		return ret(false, range(-1, -1));
	}
	valr[v] = range(l, r);
	return ret(true, range(l - 1, r + 1));
}
void assign(int v, int p) {
	if (!setv[v]) {
		int X = val[p] + 1;
		int Y = val[p] - 1;
		if (valr[v].first <= X && X <= valr[v].second) val[v] = val[p] + 1;
		else if (valr[v].first <= Y && Y <= valr[v].second) val[v] = val[p] - 1;
		else {
			cout << "No" << endl;
			exit(0);
		}
	}
	for (int to : T[v]) {
		if (to == p) continue;
		assign(to, v);
	}
}
int main() {
	int N;
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int A, B;
		cin >> A >> B;
		A--; B--;
		T[A].push_back(B);
		T[B].push_back(A);
	}
	int K;
	cin >> K;
	int root = -1;
	for (int i = 0; i < K; i++) {
		int V, P;
		cin >> V >> P;
		V--;
		setv[V] = 1;
		val[V] = P;
		root = V;
	}
	ret retv = check(root, -1);
	if (!retv.first) {
		cout << "No" << endl;
		return 0;
	}
	assign(root, -1);
	cout << "Yes" << endl;
	for (int i = 0; i < N; i++) {
		cout << val[i] << endl;
	}
}

Measured memory_bytes: 20224
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")
//*********************************************DO IT NOW****************************************************************
#include<bits/stdc++.h> 
#include<random>
#define int long long   
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define pi 3.14159265359
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
#define yes cout<< "YES"<<endl
#define no  cout<< "NO"<<endl
#define all(v) (v).begin(),(v).end()
#define s(v)   sort(v,v+n)
#define  mt mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define read(a,n) for(int i=0;i<n;i++)cin>>a[i]
#define print(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
#define for1(i,a,n)  for(int i=0;i<n;i++)
#define rep(i, c) for(int i = 0; i < (int)c; i++)
#define set(x) cout<<fixed<<setprecision(x);
using namespace std;
//**********************************************DO IT NO****************************************************************
void fastio()
{  
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
int dp[101][1001],ans1=1e9,dp1[1000001];
int num[10];
int a[1000000];
signed main()
{   
    fastio();
    int t=1;
   // cin>>t;
    while(t--)
    {  
        int n;
        cin>>n;
        int a[n+2]={0};
        for(int i=1;i<=n;i++)
        cin>>a[i];
        int c=0;
        for(int i=1;i<=n;i++)
        {
            if(i%2!=0 &&a[i]%2!=0)
            {
               // if(a[i]%2)
                c++;
            }
        }
        cout<<c;
       
        
    }
}
// 🍪 🍪 🍪


Measured memory_bytes: 3600
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define mod 1000000007
#define N 4050
#define m 2001
#define M 200050
typedef long long ll;
int f[N][N],n;
struct A {
	int x,y;
}a[M];
ll fac[M],inv[M];
const ll inv2=(mod+1)/2;
ll qp(ll x,ll y) {
	ll re=1;
	for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod; return re;
}
ll C(int x,int y) {
	if(x<y) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main() {
	scanf("%d",&n);
	int i,j;
	for(fac[0]=i=1;i<M;i++) fac[i]=fac[i-1]*i%mod;
	inv[M-1]=qp(fac[M-1],mod-2);
	for(i=M-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	for(i=1;i<=n;i++) {
		scanf("%d%d",&a[i].x,&a[i].y);
		f[m-a[i].x][m-a[i].y]++;
	}
	ll ans=0;
	int lim=m<<1;
	for(i=1;i<=lim;i++) {
		for(j=1;j<=lim;j++) {
			f[i][j]=(ll(f[i][j])+f[i-1][j]+f[i][j-1])%mod;
		}
	}
	for(i=1;i<=n;i++) {
		ans=(ans+f[m+a[i].x][m+a[i].y])%mod;
		ans=(ans-C(a[i].x*2+a[i].y*2,a[i].x*2))%mod;
	}
	ans=ans*inv2%mod;
	printf("%lld\n",(ans%mod+mod)%mod);
}


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

#define SWAP(a,b) ((a != b)? (a += b,b = a - b,a -= b) : 0 ) //数値のみ
#define SWAPs(type,a,b) { type temp = a; a = b; b = temp; } //型指定する ポインタ, 構造体等
#define rng(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed

int main() {
  int h, w, k, ans = 0, hp, wp, b = 0;
  cin >> h >> w >> k;
  hp = 1<<h;
  wp = 1<<w;
  vector<vector<char>> c(h, vector<char>(w));
  rep(i, h) rep(j, w) cin >> c.at(i).at(j);
  
  rep(i, hp){
    rep(j, wp){
      b = 0;
      rep(x, h) {
        rep(y, w) if(i&(1<<x) && j&(1<<y)) b += (c.at(x).at(y) == '#');
      }
      if(k == b) ans++;
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int cnt=0;
    string s;
    cin>>s;
    cnt=s.length()-2;
    cout<<s[0]<<cnt<<s[s.length()-1]<<endl;

    return 0;
}


Measured memory_bytes: 3588
import math

DEN=10**9+7
def ret_val(n):
    return n%DEN

N,K=map(int,input().split())

sum=0
for i in range(K,N+2):
    min_val=(i*(i-1))//2
    max_val=i*N-min_val
    sum+=max_val-min_val+1

print(ret_val(sum))

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

#define N 100000
#define NIL -1

typedef struct {
  int pare, left, right;
}Node;

int Depth(int);
void Childprint(int);

Node node[N];

int main () {
  int i, j, n = 0, m = 0, k = 0, child = 0, sib = 0;

  

  scanf("%d",&n);


  for(i = 0 ; i < n ; i++) {
    node[i].pare = NIL;
    node[i].left = NIL;
    node[i].right = NIL;
  }

  for(i = 0 ; i < n ; i++) {

    scanf("%d",&m);
    
    scanf("%d",&k);

    sib = NIL;
    for(j = 0 ; j < k ; j++) {
      scanf("%d",&child);
      node[child].pare = m;
      if(j == 0) node[m].left = child;
      else node[sib].right = child;
      sib = child;
 
    }  
  }

  for(i = 0 ; i < n ; i++) {
    printf("node %d: parent = %d, depth = %d, ", i, node[i].pare ,Depth(i));
    
    if(node[i].pare == NIL) {
      printf("root, ");
      Childprint(i);
    }

    else if(node[i].left == NIL) {
      printf("leaf, []\n");
    }

    else {
      printf("internal node, ");
      Childprint(i);
    }
  }

  return 0;
}


void Childprint(int x) {

  int c = 0;

  printf("[");

  for(c = node[x].left ; c != NIL ; c = node[c].right) {

    if(node[c].right == NIL) printf("%d",c);
    else printf("%d, ",c);
    
  }

  printf("]\n");
}


int Depth(int x) {

  if(node[x].pare == NIL) return 0;

  else return Depth(node[x].pare) + 1;
}




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

int main(){
	int ball[3]={1,0,0};
	string str;
	while(cin >> str){
		swap(ball[str[0]-'A'],ball[str[2]-'A']);
	}
	for(int i=0;i<3;i++){
		if(ball[i])cout << (char)('A'+i) << endl;
	}
}

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

long long f(long long x){
	if( x == 0 ) return 1;
	return 1ll<<f(x-1);
}

int isp(int n){
	if( n < 2 ) return 0;
	for(int i = 2 ; i*i <= n ; i++)
		if( n % i == 0 ) return 0;
	return 1;
}
int main(){
	int N;
	cin >> N;
	if( N < 4 ){
		long long A = f(N);
		int l = f(N)+1;
		while(!isp(l))l++;
		long long ans = 0;
		for(int j = 0 ; j < l-1 ; j++){
			ans = (ans * 10 + 1) % l;
		}
		cout << ans << endl;
	}else{
		cout << 0 << endl;
	}
}

Measured memory_bytes: 1164
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<ll, ll> PL;
typedef vector<PL> vpl;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e17;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define RFOR(i, a, b) for(ll i = (a); i > b; i--)
#define rep(i, n) for(ll i = 0; i < n; i++)
#define rrep(i, n) for(ll i = n-1; i > -1; i--)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back
#define epb emplace_back
#define ALL(X) (X).begin(),(X).end()

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

inline ll popcnt(ll x){return __builtin_popcountll((unsigned long long)x);};
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N; cin >> N;
    vl A(N); rep(i, N) cin >> A[i];
    vl AA = A;
    sort(ALL(AA), greater<ll>());
    rep(i, N){
        if(A[i] == AA[0]) cout << AA[1];
        else cout << AA[0];
        cout << endstr;
    }
    return 0;
}


Measured memory_bytes: 4736
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    ABC = LI()
    K = I()
    ABC.sort()

    ans = sum(ABC[:2]) + ABC[2] * 2 ** K
    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9868
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define vl vector<ll>
#define pll pair<ll,ll>
#define mll map<ll, ll> 
#define rep(i,a)  for(ll i= 0;i < a;i++)
#define rep1(i,a) for(ll i= 1;i < a;i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define pb push_back
#define sz(v) v.size()
#define all(a) a.begin(), a.end()
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000005
#define MOD 1000000007
#define el "\n"
const ll INF = 2e9+5;
  
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll isPrime(ll n){if(n<=3) return 1;if(n%2==0||n%3==0) return 0;
for(ll j=5;j*j<=n;j+=6){if(n%j == 0||n%(j+2) == 0) return 0;}return 1;}
 
using namespace std;
void solve(){
   ll n,w;
   cin>>n>>w;
   vl wt(n),v(n);
   rep(i,n)cin>>wt[i]>>v[i];
   ll sum=0;
   rep(i,n)sum+=v[i];
   vl dp(sum+1,INF);
   dp[0] = 0;
   rep(i,n){
      for(ll j=sum-v[i];j>=0;j--)
         dp[v[i]+j] = min(dp[v[i]+j],wt[i]+dp[j]);
   }
   for(ll i =sum;i>=0;i--){
      if(dp[i]<=w){cout<<i<<el;return;}
   }
}
 
int main() {
   #ifndef ONLINE_JUDGE
      freopen("input.txt", "r" , stdin);
      freopen("output.txt", "w" , stdout);
   #endif
   ios::sync_with_stdio(0); 
   cin.tie(0); cout.tie(0);   
   ll t;
   // cin>>t;
   t = 1;
   ll tc=0;
   while(tc++<t){
      // cout<<"Case #"<<tc<<": ";
      solve();
   }
   cerr<<"Time taken : "<<(double)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
   return 0;
}

Measured memory_bytes: 3908
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;

int main()
{
	int n, k; cin >> n >> k;
	vector<int> l(n);
	for (int i = 0; i < n; i++) cin >> l[i];
	sort(l.begin(), l.end(), greater<int>());
	int sum = 0;
	for (int i = 0; i < k; i++) sum += l[i];
	cout << sum << endl;
}

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


class Program
{
    static void Main(string[] args)
    {
        string Sstr = Console.ReadLine();
        int N = Sstr.Length;
        bool answer;

        char[] S = new char[N];
        for(int i=0; i<N; i++){
            S[i] = Sstr[i];
        }

        answer = palindrome(S, N);

        if(!answer){
            Console.WriteLine("No");
        }else{
            List<char> SList = new List<char>();
            SList.AddRange(S);
            SList = SList.GetRange(0, (N-1)/2);
            answer = palindrome(SList.ToArray(), (N-1)/2);
            if(answer){
                Console.WriteLine("Yes");
            }else{
                Console.WriteLine("No");
            }
        }
    }

    static bool palindrome(char[] S, int N){
        bool pal = true;
        if(N % 2 == 1){
            for(int i=0; i<(N-1)/2; i++){
                if(S[i] != S[N-i-1]) pal = false;
            }
        }else{
            for(int i=0; i<N/2; i++){
                if(S[i] != S[N-i-1]) pal = false;
            }
        }
        return pal;
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ll = long long int;
using vec = vector<int>;
using P = pair<int,int>;
const int INF = 1e9+7;

int main() {
  int n,m,k; cin >> n >> m >> k;
  vec a(n), b(m);
  ll sum = 0;
  int cnt = 0;
  int a_max = -1;
  bool f = true;
  rep(i,n) {
    cin >> a[i];
    if (sum + a[i] <= k && f) {
      sum += a[i];
      cnt++;
      a_max = i;
    }
    else if (f) {
      f = false;
    }
  }

  f = true;
  int j = 0;
  rep(i,m) {
    cin >> b[i];
    if (sum + b[i] <= k && f) {
      sum += b[i];
      cnt++;
      j = i+1;
    } else if (f) {
      f = false;
    }
  }

  int ma = cnt;
  for (int i = a_max; i >= 0; i--) {
    sum -= a[i];
    cnt--;
    while (j < m && sum + b[j] <= k) {
      sum += b[j];
      j++;
      cnt++;
    }
    ma = max(ma, cnt);
  }

  cout << ma << endl;
}


Measured memory_bytes: 4840
//agc026_a.cpp
//Sat Nov 10 17:28:22 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int samecol = 0;
	int prevcol = 0;
	int ans = 0;
	for (int i=0;i<n;i++){
		int temp;
		cin >> temp;
		if (temp == prevcol){
			samecol++;
		}else {
			ans += int(samecol/2);
			samecol = 1;
			prevcol = temp;
		}
	}
	ans += int(samecol/2);

	cout << ans << endl;
}

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

int main()
{
	int n;
	cin >> n;
	vector<string> s(n);
	for (auto& item : s) cin >> item;
	set<string> have;
	int kind = 0;
	for (auto item : s) {
		if (have.count(item)) continue;
		else {
			have.insert(item);
			kind++;
		}
	}
	cout << kind << endl;
}


Measured memory_bytes: 25088
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using tii = tuple<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	ll n = s.size();
	ll ans = 0; ll cnt = 0;
	vl v;
	rep(i, n) {
		if (s[i] == 'W') {
			cnt++;
			v.push_back(i);
		}
	}
	rep(i, v.size()) {
		ans += v[i] - i;
	}
	cout << ans << endl;
}



Measured memory_bytes: 2700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  string s;
  cin >> s;
  if (s == "AAA" || s == "BBB") No();
  else Yes();
}

Measured memory_bytes: 764
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
using namespace std;

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

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

	string s,t;
	cin >> s >> t;
	
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	reverse(t.begin(), t.end());
	cout << (s<t?"Yes":"No") << endl;
	return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
 
template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}
 
//~ ifstream f(".in");
//~ ofstream g(".out");
 
const int MOD = 1e9 + 7;

int add(int a, int b) {
  return (a + b) % MOD;
}

int mul(int a, int b) {
  return (1LL * a * b) % MOD;
}
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen(".in", "r", stdin);
#endif
 
  int n;
  cin >> n;
  vector<vector<int>> adj(n + 2);
  for (int i = 1; i <= n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  
  vector<vector<int>> dp(2, vector<int>(n + 2));
  
  function<void(int, int)> dfs = [&](int node, int parent) {
    dp[0][node] = dp[1][node] = 1;
    for (int &x : adj[node]) {
      if (x == parent) {
        continue;
      }
      
      dfs(x, node);
      dp[1][node] = mul(dp[1][node], dp[0][x]);
      dp[0][node] = mul(dp[0][node], add(dp[0][x], dp[1][x]));
    }
  };
  
  dfs(1, 0);
  
  cout << add(dp[0][1], dp[1][1]) << '\n';
 
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}


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

using namespace std;

int main()
{
	double m;
	double max, min;
	max = 0.0;
	min = 100000.0;
	int i = 0;
	while (cin >> m){
		if (max < m){
			max = m;
		}
		else if (min > m){
			min = m;
		}
	}
	cout << max - min << endl;
	
}

Measured memory_bytes: 1280
N,Ma,Mb=list(map(int, input().strip().split()))
abc=[list(map(int, input().strip().split())) for i in range(N)]
maxW=N*10
dp=[{} for __ in range(N+1)]
dp[0][(0,0)]=0
for i in range(N):
    a,b,c=abc[i]
    for k,v in dp[i].items():
        dp[i+1][k]=min(dp[i][k], dp[i+1][k]if k in dp[i+1] else float("inf"))
        dp[i+1][k[0]+a,k[1]+b]=min(dp[i][k]+c, dp[i+1][k[0]+a,k[1]+b] if (k[0]+a,k[1]+b)in dp[i+1] else float("inf"))

cost=float("inf")
Mad=Ma
Mbd=Mb
while Ma<=maxW and Mb <=maxW:
    if (Ma,Mb) in dp[-1]:
        cost=min(dp[-1][Ma,Mb],cost)
    Ma+=Mad
    Mb+=Mbd
print(-1 if cost==float("inf") else cost)

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

    char s[110000];
int a[110000];


int main()
{
    int q,n;
    scanf("%d%d%s",&n,&q,s+1);

    int ct=0;
    for(int i=2;i<=n;i++)
    {
        if(s[i]=='C'&&s[i-1]=='A')
        ct++;
        a[i]=ct;
    }
    int ff,t;
    while(q--)
    {
        scanf("%d%d",&ff,&t);
        printf("%d\n",a[t]-a[ff]);
    }
    return 0;
}



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

#define int long long
const int MOD = 1e9 + 7;

vector<vector<int>> constructIden(int n)
{
	vector<vector<int>> ret(n, vector<int>(n));
	for (int i = 0; i < n; i++)
		ret[i][i] = 1;
	return ret;
}

vector<vector<int>> mul(vector<vector<int>> &a, vector<vector<int>> &b)
{
	vector<vector<int>> ret(a.size(), vector<int>(b.size()));
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			for (int k = 0; k < b[0].size(); k++)
			{
				ret[i][k] += (a[i][j] * b[j][k]) % MOD;
				ret[i][k] %= MOD;
			}
		}
	}
	return ret;
}

vector<vector<int>> exp(vector<vector<int>> &graph, int k)
{
	vector<vector<int>> res = constructIden(graph.size());

	while (k)
	{
		if (k & 1)
		{
			res = mul(res, graph);
		}
		graph = mul(graph, graph);
		k /= 2;
	}
	return res;
}

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

	int n, k;
	cin >> n >> k;

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

	auto res = exp(graph, k);
	int ans = 0;
	for (auto i : res)
	{
		for (auto j : i)
		{
			ans += j;
			ans %= MOD;
		}
	}
	cout << ans << "\n";
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define vi               vector<int>
#define pb(x)            push_back(x)
#define all(x)           x.begin(), x.end()
#define sortall(x)       sort(all(x))
#define debug(x)         cout << '>' << #x << ':' << x << endl;
// #define int               long long
#define int               long double
#define endl "\n";
#define lb lower_bound
#define ub upper_bound
const int mod = 1000000007;
using namespace std;
// const int N = 1e5 + 5; 
// int n;
// int a[N];

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int x,y;
cin >>x >>y;

for(int i = 1; i <=x; i++){
	// debug(i);
	if(2*i + 4*(x-i) == y){
		cout << "Yes" << endl;
		return 0;
	}
}
for(int i = 1; i <=x; i++){
	// debug(i);
	if(2*(x-i) + 4*i == y){
		cout << "Yes" << endl;
		return 0;
	}
}
cout << "No" << endl;


return 0;
}

Measured memory_bytes: 3756
from itertools import accumulate
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
I = P
for i, a in enumerate(A[P:], P+1):
    if a + M >= A[P-1]:
        I = i
    else:
        break
J = K = P + N - V
B = [0] + list(accumulate(A))
# print(I, J)
for i in range(J+1, I+1):
    # print(i, B[i-1], B[P-1] , (i - P), (A[i-1] + M) , (i - J) * M)
    if (i - P) * (A[i-1] + M) - B[i-1] + B[P-1] < (i - J) * M:
        break
    K = i
print(min(I, K))

Measured memory_bytes: 14964
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(ll i=0; i<(n); i++)
#define REP2(i,x,n) for(ll i=x; i<(n); i++)
const long long INF = numeric_limits<long long>::max();
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main()
{
    ll N, K;
    cin >> N >> K;
    vector< ll > vec(N);
    for ( ll i = 0; i < N; ++ i ){
        cin >> vec[i];
    }
    vector<ll> dp(N+K, INF);
    dp[0] = 0;
    for ( ll i = 1; i < N; ++ i ){
        for ( ll j = 1; j <= K; ++ j ){
            if ( i <j )    break;
            chmin(dp[i], dp[i-j] + abs(vec[i-j]-vec[i]));
        }
    }

    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 4804
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N; cin >> N; string S; cin >> S;
  vector<int> DPw(N), DPe(N);
  DPw.at(0) = 0; DPe.at(N - 1) = 0;
  for(int i = 1; i < N; i++) {
    DPw.at(i) = DPw.at(i - 1) + ((S.at(i - 1) == 'W') ? 1 : 0);
    DPe.at(N - 1 - i) = DPe.at(N - i) + ((S.at(N - i) == 'E') ? 1 : 0);
  }
  int x = 1000000;
  for(int i = 0; i < N; i++) {
    x = min(x, (DPw.at(i) + DPe.at(i)));
  }
  cout << x << endl;
}

Measured memory_bytes: 3076
#include <iostream>

using namespace std;

int main(){
    int n, in1, in2, in3, in4, count[4][3][10]={0};
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> in1 >> in2 >> in3 >> in4;
        count[in1-1][in2-1][in3-1] += in4;
    }
    for(int j1=0;j1<4;j1++){
        for(int j2=0;j2<3;j2++){
            for(int j3=0;j3<10;j3++){
                cout << " " << count[j1][j2][j3];
            }
            cout << endl;
        }
        if(j1!=3){
            cout << "####################" << endl;
        }
    }
}


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


#define debug(x) cerr<< #x << ": "<< x << endl;
#define print(x) cerr<< x << endl;

#define mp make_pair
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define REP(i,x,y) for(int i=x;i<y;i++)
#define REPIT(it,A) for(typeof(A.begin()) it = (A.begin()); it!=A.end();it++)
#define fst first
#define snd second
#define sqr(x) ((x)*(x))

#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#define ones(x) __builtin_popcountll(x)
using namespace std;

typedef pair<int,int> ii ;
typedef long long ll ;
typedef vector<int> vi;
typedef vector<ii> vii;

int a[2][110];
int main(){
   fastio;
	
	int n;
	cin >> n;
	REP(i,0,2) REP(j,0,n) cin >> a[i][j];
	int res = 0;
	REP(i,0,n){
		int c = 0;
		REP(j,0,i+1) c += a[0][j];
		REP(j,i,n) c += a[1][j];
		res = max(res,c);
	}
	cout<<res<<endl;

   return 0;
}



Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    def extgcd1(a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b: t=a//b; a-=t*b; a,b=b,a; u,v=v,u-t*v
        if a!=1: return -1#互いに素じゃない
        return u%b0
    
    maxn=M
    fact=[1]*(maxn+1)#NはnCrの最大のn
    ifact=[1]*(maxn+1)
    x=1
    for i in range(2,maxn+1):
        x=(x*i)%mod
        fact[i]=x; ifact[i]=extgcd1(x,mod)
        
    def comb(n,r): return (fact[n]*ifact[r]%mod)*ifact[n-r]%mod
    def P(n,r): return (fact[n]*ifact[n-r]%mod)
    ans=0
    sin=-1
    for i in range(0,N+1):
        sin*=-1
        ans+=sin*comb(M,i)*P(N,i)%mod*(P(M-i,N-i)**2%mod)
        ans%=mod
        
        #print(ans)
    
    print(ans)




if __name__ == "__main__":
    main()

Measured memory_bytes: 81224
// ###### Sat Mar 28 14:19:29 IST 2020
#include <bits/stdc++.h>  
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(i,a,b)        for( i = a ; i < b  ; i++ )
#define debug(x)           cout << #x << " " << x << " -- \n"
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll                 long long    
#define MOD                998244353
#define pi                 pair<int,int>
#define vi                 vector <int>
#define pb                 push_back
#define vp                 vector <pair<ll,ll>>
#define endl               cout << "\n"  
#define f1                 first 
#define s1                 second    
#define in                 insert
#define all(x)             (x).begin(),(x).end() 
using namespace std ; 
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set ; 
const int N = 2e5+7;
int tests(){ 
  int n,i;
  cin >> n ;
  int ans = 0 ; 
  vector <int> v = {500,100,50,10,5,1};
  ans += (n/500)*1000;
  n %= 500 ; 
  ans += (n/5)*5;
  cout << ans  << '\n' ;
  return 0 ;
} 
int main(){
    I__O ;            
    int cases = 1 ; 
    // cin >> cases ;  
    while(cases--){   
    // cout << "Case #" << cases << ": ";
      tests(); 
    }
    return 0 ; 
}

// -Wall -Wextra -O2
// -pedantic -std=c++11
// -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[100007]={},b[100007]={};
int mod = (int)(1e9+7);
int main(){
    int n,m;
    cin >> n >> m;
    int a[m];
    for(int i=0;i<m;i++){
        cin >> a[i];
        b[a[i]]=1;
    }
    dp[0] = 1;
    if(!b[1]) dp[1] = 1; 
    for(int i=0;i<n-1;i++){
        dp[i+2] = (dp[i]+dp[i+1])%mod;
        if(b[i+2]) dp[i+2] = 0;
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 4648
{-# LANGUAGE BangPatterns #-}
import Control.Arrow
import Data.Int
import Data.List
import qualified Data.Vector.Unboxed as VU
import qualified Data.ByteString.Char8 as B

solve :: Int -> [Int16] -> Int32
solve n hs = fst $ fst dp
 where
  h1 : h2 : h3 = hs

  -- dp[i]: minimal cost of moving from 1st to i-th place
  dp           = foldl'
    (\((!dp1, !dp2), (!x, !y)) (!i, !v) ->
      ( ( min (dp1 + abs (fromIntegral $ v - x))
              (dp2 + abs (fromIntegral $ v - y))
        , dp1
        )
      , (v, x)
      )
    )
    ((fromIntegral $ abs $ h1 - h2, 0), (h2, h1))
    (zip ([2 ..] :: [Int]) h3)

main = do
  let sillyTail b | B.null b  = b
                  | otherwise = B.tail b
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt b
        | B.null b = Nothing
        | otherwise = fmap (first fromIntegral . second sillyTail) $ B.readInt b

  n  <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  hs <- unfoldr readInt <$> B.getLine
  print $ solve n hs


Measured memory_bytes: 1916
N = int(input())
import itertools
cnt = 0
for i in range(1,10):
    Ls = list(itertools.product(["3","5","7"], repeat=i))
    for L in Ls:
        if ("3" in L) and ("5" in L) and ("7" in L):
            S = int("".join(L))
            if S<=N:
                cnt+=1
print(cnt)


Measured memory_bytes: 45548
from sys import stdin
from copy import deepcopy

N = int(stdin.readline().rstrip())
C = [x for x in stdin.readline().rstrip().split()]

def sortBubble(C, N):
    c = deepcopy(C)
    for i in range(N):
        for j in range(N-1, i, -1):
            if c[j][1] < c[j-1][1]:
                c[j], c[j-1] = c[j-1], c[j]

    return c

def sortSelect(C, N):
    c = deepcopy(C)
    for i in range(N):
        minj = i
        for j in range(i, N):
            if c[j][1] < c[minj][1]:
                minj = j

        if i != minj:
            c[i], c[minj] = c[minj], c[i]

    return c

def isStable(Cin, Cout):
    stable = sortBubble(Cin, len(Cin))
    if len(stable) != len(Cout):
        return False
    else:
        for i in range(len(Cin)):
            if Cout[i][0] != stable[i][0]:
                return False
        else:
            return True
            
def output(C, N, *f):
    for fn in f:
        sortedC = fn(C, N)
        print(*sortedC)
        if isStable(C, sortedC):
            print("Stable")
        else:
            print("Not stable")

output(C, N, sortBubble, sortSelect)


Measured memory_bytes: 6348
#include <stdio.h>
#include <algorithm>
using namespace std;
long long a[100020],b[100020],c[100020];
long long bp[100020],ap[100020];
long long bph[100020];
long long n;
int main()
{
	long long ans=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	sort(c+1,c+n+1);
	int j=1;
	for(int i=1;i<=n;i++)
	{
		while(c[j]<=b[i]&&j<=n) j++;
		bp[i]=j;
		//printf("bp[%d]=%d\n",i,j);
	}
	j=1;
	for(int i=1;i<=n;i++)
	{
		while(b[j]<=a[i]&&j<=n) j++;
		ap[i]=j;
		//printf("ap[%d]=%d\n",i,j);
	}
	for(int i=n;i>=1;i--)
	{
		bph[i]=bph[i+1]+(n-bp[i]+1);
		//printf("bph[%d]=%d\n",i,bph[i]);
	}
	for(int i=1;i<=n;i++)
	{
		ans+=bph[ap[i]];
	}
	printf("%lld",ans);
	return 0;
}

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

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

typedef long long LL;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const int MOD = 1e9+7;

LL mpow(LL x, LL n) {
    LL res = 1;
    while (n) {
        if (n & 1) {
            res *= x;
            res %= MOD;
        }
        x *= x;
        x %= MOD;
        n >>= 1;
    }
    return res;
}

int main(void) {
    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    vector<bool> vis(maxn, false);
    vector<int> sp(maxn, 0);
    unordered_map<int, int> m;

    for (int i = 2; i < maxn; i+=2) sp[i] = 2;
    for (LL i = 3; i < maxn; i+=2) {
        if (!vis[i]) {
            sp[i] = i;
            for (LL j = i; (j*i) < maxn; j+=2) {
                if (!vis[j*i]) {
                    vis[j*i] = true;
                    sp[j*i] = i;
                }
            }
        }
    }


    for (auto x : a) {
        unordered_map<int, int> cur_m;
        while (x > 1) {
            ++cur_m[sp[x]];
            x /= sp[x];
        }

        for (const auto& item : cur_m) {
            m[item.first] = max(m[item.first], item.second);
        }
    }

    LL lcm = 1;
    for (const auto& item : m) {
        for (int i = 0; i < item.second; ++i) {
            lcm *= item.first;
            lcm %= MOD;
        }
    }
    debug() << lcm;

    LL ans = 0;
    for (auto x : a) {
        ans += (lcm * mpow(x, MOD-2));
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}



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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

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



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,t; cin>>n>>t;
  vll a(n);
  rep(i,n) cin>>a[i];
  map<ll,ll> m;
  ll r=0;
  rep(l,n){
    while(r<n&&a[l]<=a[r]){
      ll d=a[r]-a[l];
      m[d]++;
      r++;
    }
    if(r==l) r++;
  }
  ll ans=0;
  ll now=0;
  for(auto e: m){
    if(chmax(now,e.first)) ans=e.second;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int K[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int C;

    cin >> C;
    cout << K[C - 1] << endl;
    return 0;
}

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int main() {
  const int T = 6000 + 1;
  int n, t;
  cin >> n >> t;
  vector<int> dp(T, -1);
  dp[0] = 0;

  vector<pii> ab(n);
  rep(i, n) cin >> ab[i].F >> ab[i].S;

  sort(all(ab));

  int ans = 0;
  rep(i, n) {
    int a = ab[i].F;
    int b = ab[i].S;
    for (int j = t - 1; j >= 0; j--) {
      if (dp[j] == -1) continue;
      dp[j + a] = max(dp[j + a], dp[j] + b);
      ans = max(dp[j + a], ans);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long intl;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF = 1e9;
using namespace std;
int main(){
    intl a;
    cin >> a;
    intl b;
    cin >> b;
    intl c;
    cin >> c;
    bool flag = false;
    if(a == b){
        if(a != c)flag = true;
    }
    if(a == c){
        if(a != b)flag = true;
    }
    if(c == b){
        if(b != a)flag = true;
    }
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using Graph = std::vector<std::vector<int>>;
using WGraph = std::vector<std::vector<std::pair<int, long long>>>;
using ll = long long;
using namespace std;
 
int main() {
  long long a = 0, b = 0, k = 0;
  cin >> a >> b >> k;
  int cnt = 0;
  while (cnt < k) {
    b += a/2;
    a /= 2;
    cnt++;
    if (cnt == k) break;
    a += b/2;
    b /= 2;
    cnt++;
  }
  cout << a << " " << b << endl;
  return 0;
}


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

int main() {
  int a, b, c;
  std::cin >> a >> b >> c;
  const auto cost = std::min(std::abs(a - b) + std::abs(c - a), std::min(
    std::abs(b - a) + std::abs(c - b), std::abs(b - c) + std::abs(a - c)));
  std::cout << cost << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<utility>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

int main(){
	int n, c, k;
	cin >> n >> c >> k;
	vector<int> t(n);
	for(int i=0; i<n; i++)
		cin >> t[i];
	sort(t.begin(), t.end());
	int i=0, limit, num=0;
	while(true){
		bool flag = false;
		limit = t[i]+k;
		for(int j=0; j<c; j++){
			if(t[i]<=limit){
				i++;
			}else{
				break;
			}
			if(i==n){
				flag = true;
				break;
			}
		}
		num++;
		if(flag)
			break;
	}
	cout << num << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define PI (acos(-1))

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  vector<vector<int>> g(n);
  rep(i,m){
    int x,y;
    cin>>x>>y;
    x--,y--;
    g[x].push_back(y);
  }
  vector<bool> used(n,false);
  vector<int> dp(n,0);
  function<int(int)> dfs=[&](int v){
    if(used[v]) return dp[v];
    used[v]=true;
    for(auto itr:g[v]){
      chmax(dp[v],dfs(itr)+1);
    }
    return dp[v];
  };
  rep(i,n){
    if(!used[i]) dfs(i);
  }
  cout<<*max_element(begin(dp),end(dp))<<endl;
}

Measured memory_bytes: 8832
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// ここまで

fn run() {
    input! {
        n: usize,
        h: [usize; n],
    }
    let mut h = h;
    for i in (0..(n - 1)).rev() {
        if h[i] > h[i + 1] {
            h[i] -= 1;
        }
        if h[i] > h[i + 1] {
            println!("No");
            return;
        }
    }
    println!("Yes");
}

fn main() {
    run();
}


Measured memory_bytes: 6396
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,a,b) for(int i=a ; i<b ; i++)
const int max_n = 1e5;
const ll mod = 1e9+7;
void send(int a,int b,int c,int d){
  printf("%d %d %d %d\n",a,b,c,d);
}
int main(){
  int n,m;  cin >> n >> m;
  int v[n][m];
  rep(i,0,n)rep(j,0,m){
    cin >> v[i][j];
  }
  int cnt = 0;
  vector<pair<P,P> > p;
  rep(i,0,n)rep(j,0,m-1){
    while(v[i][j]%2 != 0){
      cnt++;
      v[i][j]--;
      v[i][j+1]++;
      p.pb(mp(mp(i,j),mp(i,j+1)));
    }
  }
  rep(i,0,n-1){
    while(v[i][m-1]%2!=0){
      v[i][m-1]--;
      cnt++;
      v[i+1][m-1]++;
      p.pb(mp(mp(i,m-1),mp(i+1,m-1)));
    }
  }
  cout << cnt << endl;
  rep(i,0,p.size()){
    send(p[i].fi.fi+1,p[i].fi.se+1,p[i].se.fi+1,p[i].se.se+1);
  }
  return 0;
}


Measured memory_bytes: 5104
from collections import*
s,_,*q=open(0)
d=deque(s[:-1])
p=1
for q in q:
  try:
    q,f,c=q.split()
    if(f<'2')^p:d+=c,
    else:d.appendleft(c)
  except:p^=1
print(''.join(d)[::p or-1])

Measured memory_bytes: 18548