akhauriyash/Code-Regression huggingface dataset:
N = int(input())
A = [int(_) for _ in input().split()]

def solve(N, A):
    if N <= 2:
        return 1
    s = 0
    result = 1
    i = 0
    while i < N-1:
        r = A[i+1] - A[i]
        if (r > 0 and s < 0) or (r < 0 and s > 0):
            result += 1
            s = 0
        elif r != 0:
            s = r
        i += 1
    return result

print(solve(N, A))


Measured memory_bytes: 14224
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 500000001000000000
#define MOD 1000000007
typedef long long  ll;

using namespace std;

ll ans;

// a^n mod を計算する
ll modpow(ll a, ll n) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % 2019;
		a = a * a % 2019;
		n >>= 1;
	}
	return res;
}

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

	string s;
	cin >> s;

	ll n = s.size();

	vector<ll> num(n);
	rep(i,n) {
		num[i] = s[i] - '0';
	}
	
	vector<ll> snum(n);
	snum[n-1] = num[n-1];
	

	repk(i, 1, n) {
		snum[n - i - 1] = (snum[n - i] + num[(n - 1) - i] * modpow(10, i)) % 2019;
	}

	map<int, int> t;
	t[0]++;
	rep(i, n) {
		t[snum[i]]++;
	}

	for (auto p : t) {
		ans += p.second * (p.second - 1) / 2;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6796
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner scan=new Scanner(System.in);
    String in1=scan.next();
    String in2=scan.next();
    String[] sp1=in1.split("");
    String[] sp2=in2.split("");
    int Ans=0;
    for(int x=0; x<3; x++){
      if(sp1[x].equals(sp2[x])){
        Ans++;
      }
    }
    System.out.println(Ans);
  }
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E17;

#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////////////////

bool comp(l_l a,l_l b){
    return a.second<b.second;
}

int main(){fastio
    ll n;cin>>n;
    l_l a[n];rep(i,0,n-1)cin>>a[i].first>>a[i].second;
    sort(a,a+n,comp);
    ll time=0;
    rep(i,0,n-1){
        time+=a[i].first;
        if(time>a[i].second){
            cout<<"No"<<endl;return 0;
        }
    }
    cout<<"Yes"<<endl;
    
    return 0;
}

Measured memory_bytes: 3328
// C - Strange Bank
#include <bits/stdc++.h>
using namespace std;

int f(int yen, int coin, int cnt=0){
	while(yen > 0){ cnt += yen % coin; yen /= coin; }
	return cnt;
}

int main(){
	int n; cin>>n;
	int ans = n;
	for(int yen6=0; yen6<=n; ++yen6)
		ans = min(ans, f(n-yen6, 9, f(yen6, 6)));
	cout<< ans <<endl;
}


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 f(int n){
    if(n%2==0) return n/2;
    else return 3*n+1;
}

int main(){
    int s;
    //cin>>s;
    scanf("%d",&s);
    vector<int> num(1000005,0);
    
    bool exist=true;
    int i=1;
    num[s]++;
    while(exist){
        s=f(s);
        num[s]++;
        if(num[s]>1) exist=false;
        i++;
    }
    
    printf("%d\n",i);
    return 0;
}

Measured memory_bytes: 7172
N = int(input())
X = list(map(int, input().split()))

a = sum(X) // N
b = sum(X) // N + 1

ans = float("inf")

for p in [a, b]:
	res = 0
	for x in X:
		res += (x - p) ** 2
	ans = min(ans, res)
	
print(ans)

Measured memory_bytes: 38256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back

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

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

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

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const long double PI = 3.14159265358979323846;


// ****************************************CODE***************************************//










int main(){



   int n;
   cin >> n;

   int ans;
   cin >> ans;

   for(int i = 0; i < n-1; i++){
       int a;
       cin >> a;
       ans ^= a;
   }

   if(ans == 0){
       cout << "Yes" << endl;
   }
   else{
       cout << "No" << endl;
   }








}





























Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a[n];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(i%2!=0 && a[i]%2!=0){
            cnt++;
        }
    }
    cout<<cnt;
}

Measured memory_bytes: 3580
import bisect

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

ans = 0
for j in range(n):
    i = bisect.bisect_left(a, b[j])
    k = n - bisect.bisect_right(c, b[j])
    ans += i * k
print(ans)

Measured memory_bytes: 22452
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;
const string nyan("(=^・ω・^=)");

int N, c, H, MAX;

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> H;
		if (MAX <= H) {
			++c;
			MAX = H;
		}
	}
	cout << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n, m; cin >> n >> m;
  long long ans = 0, tk;
  tk = min(n, m / 2);
  ans += tk;
  n -= tk;
  m -= 2 * tk;
  ans += m / 4;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import sys


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


def input():
    return sys.stdin.readline().strip()


def main():
    X = int(input())
    money = 100
    cnt = 0
    while money < X:
        cnt += 1
        money *= 1.01
        money = int(money)

    print(cnt)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
int n,s;
int cnt = 0;

void dfs(int i,int sum,int sumnum){
	if ((sum == s) and (sumnum == n)){
		cnt++;
		return;
	}

	if (i == 10) return;
	if (sum > s) return;

	dfs(i+1,sum,sumnum);
	dfs(i+1,sum+i,sumnum+1);
}

int main(){
	while(true){
		SCD2(n,s);
		if ((n==0) and (s==0)) break;
		cnt = 0;
		dfs(0,0,0);
		PRINTD(cnt);

	}
	return 0;
}


Measured memory_bytes: 3188
/**
 * Martin Leshko (leshko.martin@gmail.com)
 */

#include <bits/stdc++.h>

using namespace std;

#define psb push_back

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define for1n(i, n) for (int i = 1; i <= (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pii;
#define what_is(x) cerr << #x << " is " << x << endl;
#define remplir(a, z) memset(a, z, sizeof(a))
#define all(x) (x).begin(), (x).end()

void faststdio()
{
#ifndef abacaba
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif
}

vector<string> p = {"Sunny", "Cloudy", "Rainy", "Sunny", "Cloudy", "Rainy"};

int main()
{
	faststdio();
	string s;
	cin >> s;	
	forn(i, s.size())
		if (s[i] == 'L' && (i + 1) % 2)
			cout << "No", exit(0);
		else if (s[i] == 'R' && (i + 1) % 2 == 0)
			cout << "No", exit(0);
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
def read():
    N = int(input().strip())
    L = map(int, input().strip().split())
    return N, L


def solve(N, L):
    L = sorted(L)
    return "Yes" if L[-1] < sum(L[:-1]) else "No"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Measured memory_bytes: 2940
//Why 860?
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz(v) ((int)v.size())
#define fill(x, v) memset(x, v, sizeof(x))
#define trace(x) cout << #x << " = " << x << endl
#define FER(i,x,y) for(int (i)=(x);(i)<(y); (i) ++)
#define IFR(i,x,y) for(int (i)=(x);(i)>=(y); (i) --)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#define N 101
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef ll T;

int main(){
	fastio;
	int n; cin >> n;
	int a, b; cin >> a >> b;
	int c1 = 0, c2 = 0, c3 = 0;
	FER(i, 0, n){
		int x; cin >> x;
		if(x <= a) c1 ++;
		else if(x > a && x <= b) c2 ++;
		else c3 ++;
	}
	cout << min(c1, min(c2, c3)) << endl;
	return 0;
}

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

typedef long long ll;

int main() {
     
     int t = 1;
     //cin>>t;

     while(t--){
        string s;

        cin>>s;
        int flag1 = 0, flag2 = 0;
        string te = s;
        reverse(te.begin(), te.end());
        if(te == s){
            flag1 = 1;
        }   
        string a = s.substr(0, (s.size()-1)/2);
        string b = a;
        reverse(b.begin(), b.end());
        if(a == b){
            flag2 = 1;
        }
        if(flag1 && flag2){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }

     }
    return 0;
}


Measured memory_bytes: 256
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#pragma warning(disable:4786)
#pragma warning(disable:4996)

#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int mod=1e9+7;
const int M=500005;
const int N=500005;
const int BLOCK=760;
int answer;
struct query
{
    int l,r,ind;
}Q[M];
int ses[M];
int a[N];
int cnt[M];

void add(int index)
{
    cnt[a[index]]++;
    if(cnt[a[index]]==1) answer++;
}

void remove(int index)
{
    cnt[a[index]]--;
    if(cnt[a[index]]==0) answer--;
}

bool cmp(query f,query s)
{
    if((f.l/BLOCK)!=(s.l/BLOCK))
        return (f.l/BLOCK)<(s.l/BLOCK);
    else
        return f.r<s.r;
}
 main()

{
    int n,q;
    scanf("%d%d",&n,&q);
    f(i,0,n-1)scanf("%d",&a[i]);
    f(i,0,q-1)
    {
        int lft,rgt;
        scanf("%d%d",&lft,&rgt);
        Q[i].ind=i;
        Q[i].l=lft-1;
        Q[i].r=rgt-1;
    }
    sort(Q,Q+q,cmp);
    int cl=0,cr=0;
    for(int i=0;i<q;i++)
    {
        int left=Q[i].l,right=Q[i].r;
        while(cl<left)
            remove(cl),cl++;
        while(cl>left)
            add(cl-1),cl--;
        while(cr<=right)
            add(cr),cr++;
        while(cr>(right+1))
            remove(cr-1),cr--;
        ses[Q[i].ind]=answer;
    }
    f(i,0,q-1)
        printf("%d\n",ses[i]);
    return 0;

}





































Measured memory_bytes: 15476
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
const int MOD = 1000000007;
map<ll, char> mm;
int main(){
	ll n, m;
	string s, t;
	cin >> n >> m;
	cin >> s >> t;
	ll len = n * m / __gcd(n, m);
	for (int i = 0; i < n; ++i) {
		mm[i * len / n] = s[i];
	}
	for (int i = 0; i < m; ++i) {
		auto it = mm.find(i * len / m);
		if (it != mm.end()) {
		  	if (it->second != t[i]) {
		    	cout << -1 << endl;
		    	return 0;
		  	}
		}
	}
	cout << len << endl;
	return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
#define MAX (ll)(2e5 + 1)
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e18)
#define PI (double)(3.14159265)
#define IO ios_base :: sync_with_stdio (false), cine.tie (nullptr);

using namespace std;
using ll = long long;
using ld = long double;

int main () {
 ll n, k, z = 0;
 cin >> n >> k;
 vector<int> p, ne;
 for (int i = 0; i < n; i++) {
  int val;
  cin >> val;
  if (val == 0) {
   z++;
  }
  else if (val > 0) {
   p.push_back (val);
  }
  else {
   ne.push_back (-val);
  }
 }
 ll l = -INF, h = INF;
 ll ans;
 sort (ne.begin (), ne.end ());
 sort (p.begin (), p.end ());
 while (l <= h) {
  ll mid = (l + h) >> 1, gt = 0;
  if (mid < 0) {
   for (int x : ne) {
    ll v = -mid / x;
    if (-mid % x) {
     v++;
    }
    gt += p.end () -  lower_bound (p.begin (), p.end (), v);
   }
  }
  else if (mid > 0) {
   for (int x : p) {
    ll v = mid / x;
    gt += upper_bound (p.begin (), p.end (), v) - p.begin ();
    gt -= (x <= v);
   }
   for (int x : ne) {
    ll v = mid / x;
    gt += upper_bound (ne.begin (), ne.end (), v) - ne.begin ();
    gt -= (x <= v);
   }
   gt /= 2;
  }
  if (mid >= 0) {
   gt += ne.size () * 1LL * p.size () + z * 1LL * (p.size () + ne.size ()) + (z * 1LL *  (z - 1)) / 2;
  }
  if (gt >= k) {
   ans = mid;
   h = mid - 1;
  }
  else {
   l = mid + 1;
  }
 }
 cout << ans << "\n";
}
 


Measured memory_bytes: 1400
/*
      author : nishi5451
      created: 10.08.2020 23:50:35
*/

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


int main(){
    int a,b,h;
    cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,string> tp;
//typedef vector<tp> vt;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e9;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n,h=0;
	while(cin>>n,n){
		if(h++)cout<<endl;
		vi cost{10,50,100,500};
		vi in(4);
		int mi=inf,ans[4];
		rep(i,4)cin>>in[i];
		rep(i,in[0]+1)rep(j,in[1]+1)rep(k,in[2]+1)rep(l,in[3]+1){
			int sum=i*10+j*50+k*100+l*500;
			int out=in[0]-i+in[1]-j+in[2]-k+in[3]-l;
			sum-=n;
			if(sum<0)continue;
			for(int q=3;q>=0;q--){
				out+=sum/cost[q];
				sum%=cost[q];
			}
			if(out<mi){
				mi=out;
				ans[0]=i;ans[1]=j;ans[2]=k;ans[3]=l;
			}
		}
		rep(i,4)if(ans[i])cout<<cost[i]<<" "<<ans[i]<<endl;
	}
}

Measured memory_bytes: 2948
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    string s; cin >> s;
    bool ok = true;
    for(int i=0; i<(int)s.size(); i+=2) {
        ok &= (s[i] == 'h');
        ok &= (s[i+1] == 'i');
    }
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
	let n = read::<usize>();
	let arr = read_vector::<usize>();
	let mut ans = vec![0; n];
	if calculate(0, &arr, &mut ans) == arr[arr.len() / 2] {
		print(&ans);
		return;
	}
	if calculate(2000000000, &arr, &mut ans) == arr[arr.len() / 2] {
		print(&ans);
		return;
	}
	let (mut l, mut r) = (0, 2000000000);
	while r - l > 2 {
		let mut mid = (l + r) / 2;
		if mid % 2 == 1 {
			mid += 1;
		}
		if calculate(mid, &arr, &mut ans) > arr[arr.len() / 2] {
			if (arr.len() - 1) % 4 == 0 {
				r = mid;
			} else {
				l = mid;
			}
		} else {
			if (arr.len() - 1) % 4 == 0 {
				l = mid;
			} else {
				r = mid;
			}
		}
	}
	if (arr.len() - 1) % 4 == 0 {
		let _ = calculate(l, &arr, &mut ans);
	} else {
		let _ = calculate(r, &arr, &mut ans);
	}
	print(&ans);
}

fn calculate(x: usize, arr: &[usize], ans: &mut Vec<usize>) -> usize {
	ans[0] = x;
	let mut r = 1;
	let mut l = arr.len() - 1;
	for i in 0..(arr.len() / 2) {
		if ans[r - 1] / 2 > arr[r - 1] || ans[(l + 1) % arr.len()] / 2 > arr[l]{
			if i % 2 == 0 {
				if (arr.len() - 1) % 4 == 0 {
					return std::usize::MAX;
				} else {
					return 0;
				}
			} else {
				if (arr.len() - 1) % 4 == 0 {
					return 0;
				} else {
					return std::usize::MAX;
				}
			}
		}
		ans[r] = (arr[r - 1] - ans[r - 1] / 2) * 2;
		ans[l] = (arr[l] - ans[(l + 1) % arr.len()] / 2) * 2;
		r += 1;
		l -= 1;
	}
	ans[r] / 2 + ans[l] / 2
}

fn print(ans: &[usize]) {
	for i in 0..ans.len() {
		if i < ans.len() - 1 {
			print!("{} ", ans[i]);
		} else {
			println!("{}", ans[i]);
		}
	}
}

#[allow(dead_code)]
fn read<T>() -> T where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .trim()
        .parse()
        .unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    use std::io::prelude::*;
    let stdin = stdin();
    return stdin
        .lock()
        .lines()
        .map(|line| line
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().unwrap())
            .collect())
        .collect();
}

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

int main(){
    int N, M, zero_vector, count=0;
    cin >> N >> M;
    vector<int> g[100007];
    int indegree[N], dist[N];
    queue<int> q;
    
    memset(indegree, 0, sizeof(indegree));
    memset(dist, 0, sizeof(dist));

    for(int i=1;i<M+1;i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        indegree[y-1] += 1;
    }

    for(int i=0;i<N;i++){
        if (indegree[i] == 0)
            q.push(i);
    }

    while(!q.empty()){
        zero_vector = q.front();
        q.pop();
       
        for(int j=0;j<g[zero_vector+1].size();j++){
            indegree[g[zero_vector+1][j]-1] = indegree[g[zero_vector+1][j]-1] - 1;
            dist[g[zero_vector+1][j]-1] = max(dist[g[zero_vector+1][j]-1], 1+dist[zero_vector]);
            count = max(count, dist[g[zero_vector+1][j]-1]);
            if(indegree[g[zero_vector+1][j]-1] == 0)
                q.push(g[zero_vector+1][j]-1);
        }
        indegree[zero_vector] = -1; 
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    for (int i = 0; i < n; ++i) {
        cin >> l[i];
    }
    lint curr = 0;
    int ret   = 1;
    for (int i = 0; i < n; ++i) {
        curr += l[i];
        if (curr <= x) {
            ret++;
        } else {
            break;
        }
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 256
//#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	int H,W,K;
	scan(H>>W>>K);
	char c[7][7];
	rep(i,H){
		scan(c[i]);
	}
	int Hall=(1<<H),Wall=(1<<W);
	int ans=0;
	rep(Hbit,Hall){
		rep(Wbit,Wall){
			int kuro=0;
			rep(i,H){
				rep(j,W){
					if(c[i][j]=='#'&&((Hbit>>i)&1)==0&&((Wbit>>j)&1)==0) kuro++;
				}
			}
			debug(Hbit,Wbit,kuro);
			if(kuro==K) ans++;
		}
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main(){
  ll n,x=1,y=1,z=1,i,mod=1e9+7;
  cin>>n;
  for(i=0;i<n;i++){
    x=x*10%mod;
    y=y*9%mod;
    z=z*8%mod;
  }
  cout<<(x-2*y+z+2*mod)%mod<<endl;
}

Measured memory_bytes: 3596
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define pi 3.141592653589
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long
#define MOD (int)(1e9+7)
#define pii pair<int,int>
using namespace std;


int main() {

	int n;
	string s;

	cin >> n;
	s = to_string(n);
	int sum = 0;
	rep(i, 0, s.size()) {
		sum += s[i] - '0';
	}
	if (n%sum == 0)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 


int main()
{
    string S, T;
    cin >> S >> T;

    LL ans = 0;

    for (int i = 0; i < 3; ++i) {
        if (S[i] == T[i]) {
            ++ans;
        }
    }


    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long int ll;


int main()
{
	ll H,n;
	cin>>H>>n;
	ll sum = 0;
	rep(i,n){
		ll num;
		cin>>num;
		sum += num;
	}
	if( sum >= H){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3136
#include <inttypes.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b)
{
    if (*(intmax_t *)a < *(intmax_t *)b)
        return -1;
    if (*(intmax_t *)a > *(intmax_t *)b)
        return 1;
    return 0;
}

int main(void)
{
    intmax_t K, N, A[(int)2e5];
    intmax_t d[(int)2e5], ans = 0;

    scanf("%jd%jd", &K, &N);
    for (size_t i = 0; i < N; i++) {
        scanf("%jd", &A[i]);
    }

    qsort(A, N, sizeof(A[0]), compare);

    d[0] = (K - A[N - 1]) + A[0];
    for (size_t i = 1; i < N; i++) {
        d[i] = A[i] - A[i - 1];
    }

    for (size_t i = 0; i < N; i++) {
        if (d[i] > ans)
            ans = d[i];
    }

    printf("%jd\n", K - ans);

    return 0;
}


Measured memory_bytes: 3964
#include<iostream>
using namespace std;
using ll = long long;

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

	if (s == 1 || s == 2) {
		cout << 4 << endl;
		return 0;
	}


	int ans = 1;

	while (s != 4) {
		if (s % 2)s = s * 3 + 1;
		else s /= 2;

		ans++;
	}

	cout << ans + 3 << endl;
	
}

Measured memory_bytes: 3584
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int h = sc.nextInt();
        int w = sc.nextInt();
        System.out.println((n - h +1) * ( n - w + 1));

    }
}

Measured memory_bytes: 23636
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let s = read::<String>().chars().collect::<Vec<_>>();
    let t = read::<String>().chars().collect::<Vec<_>>();

    if s.len() > t.len() {
        println!("GREATER");
        return;
    } else if s.len() < t.len() {
        println!("LESS");
        return;
    }

    for i in 0..s.len() {
        if s[i].to_digit(10) > t[i].to_digit(10) {
            println!("GREATER");
            return;
        } else if s[i].to_digit(10) < t[i].to_digit(10) {
            println!("LESS");
            return;
        }
    }
    println!("EQUAL");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
// Ver19.02
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

ll calc_diff_fromA(ll, ll, ll);

int main()
{
  ll n, t, a;
  ll h[1001];
  ll min_diff = INF;
  ll ans;
  scanf("%lld%lld%lld", &n, &t, &a);
  for (int i = 0; i < n; i++)
  {
    scanf("%lld", &h[i]);
    ll maybe = calc_diff_fromA(t, h[i], a);
    if (maybe < min_diff)
    {
      min_diff = maybe;
      ans = i;
    }
  }
  printf("%lld\n", ans + 1);

  return 0;
}

ll calc_diff_fromA(ll t, ll x, ll a)
{
  return llabs(a * 1000 - (t * 1000 - x * 6));
}

Measured memory_bytes: 128
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

using ll = long long;
using ld = long double;

#define mp make_pair

typedef tree<
        pair<int, int>,
        null_type,
        less<pair<int, int>>,
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;


const int p = 1e9 + 7;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}


mt19937 rnd(time(0));

struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};

/*
const int N = 1200000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    if (n<k) return 0;
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
*/




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

    int n, m;
    cin>>n>>m;

    int N = m;
    vector<int> dp(N+1); //dp[len]

    for (int i = 1; i<=N; i++) dp[i] = 1;

    for (int i = 0; i<n; i++)
    {
        vector<int> dp1(N+1);

        int cur = 0;

        for (int j = 1; j<=N; j++)
        {
            dp1[j] = mul(j+1, dp[j]);
            cur = mul(cur, 2);
            if (j>=2)
            {
                cur = add(cur, mul(dp[j-1], j-1));
            }
            dp1[j] = add(dp1[j], cur);
            /*for (int seg = 2; seg<=j; seg++)
            {
                dp1[j] = add(dp1[j], mul(mul(j - seg + 1, po(2, seg-2)), dp[j-seg+1]));
            }*/
        }
        dp = dp1;
    }

    cout<<dp[m];




}



Measured memory_bytes: 3696
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;

const int maxn=3e6+5;

int fi[maxn],ne[maxn*2],dui[maxn*2],dui1[maxn*2],qc[maxn];
int a[105][105],de[20005],h[maxn];
char s[105];
int i,j,k,l,m,n,x,y,now,p,be,ed,ans;
bool bq;

void add(int x,int y,int z){
	if (fi[x]==0) fi[x]=++now; else ne[qc[x]]=++now;
	dui[now]=y; dui1[now]=z; qc[x]=now;
}
bool bfs(){
	memset(de,255,sizeof(de));
	de[be]=0;
	h[1]=be; i=1; j=0;
	while (i>j){
		x=h[++j];
		for(int k=fi[x];k;k=ne[k]){
			if (de[dui[k]]!=-1 || dui1[k]==0) continue;
			de[dui[k]]=de[x]+1;
			h[++i]=dui[k];
		}
	}
	if (de[ed]==-1) return false; else return true;
}
int dinic(int x,int w){
	int i=fi[x],now=0,p;
	if (x==ed) return w;
	for(;i;i=ne[i]){
		if (dui1[i]==0 || de[dui[i]]!=de[x]+1) continue;
		p=dinic(dui[i],min(w-now,dui1[i]));
		if (p){
			dui1[i]-=p; dui1[i xor 1]+=p; now+=p;
		}
	}
	return now;
}
int main(){
//	freopen("074f.in","r",stdin);
	scanf("%d%d",&n,&m);
	fo(i,1,n){
		scanf("%s",&s);
		fo(j,0,m-1){
			if (s[j]=='.') continue;
			a[i][j+1]=++p;
			if (s[j]=='S') be=p;
			if (s[j]=='T') ed=p;
		}
	}
	now=1;
	fo(i,1,n)
		fo(j,1,m) if (a[i][j]>0 && a[i][j]!=ed){
			fo(k,1,m) if (a[i][k]>0 && a[i][k]!=a[i][j] && a[i][k]!=be){
				add(a[i][j]+p,a[i][k],1234567);
				if (a[i][j]==be && a[i][k]==ed){
					printf("-1\n"); return 0;
				}
			}
			fo(k,1,n) if (a[k][j]>0 && a[k][j]!=a[i][j] && a[k][j]!=be){
				add(a[i][j]+p,a[k][j],1234567);
				if (a[i][j]==be && a[k][j]==ed){
					printf("-1\n"); return 0;
				}
			}
		}
	fo(i,1,p){
		if (i==be || i==ed) add(i,i+p,1234567); else add(i,i+p,1);
		add(i+p,i,0);
	}
	ed=ed+p;
	while (bfs()) 
		ans=ans+dinic(be,1234567);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 35200
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
typedef pair<double, double> P;

int n;
pair<double ,double> p[100000];

int main() {
	int i, j;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
	
	//random rotate
	double rad = 0.364364334 * 3.14159265358979;
	for (i = 0; i < n; i++) {
		double x = p[i].first * cos(rad) - p[i].second * sin(rad);
		double y = p[i].first * sin(rad) + p[i].second * cos(rad);
		p[i].first = x;
		p[i].second = y;
	}
	
	sort(p, p + n);
	
	double minDist2 = 1145141919;
	
	for (i = 0; i < n; i++) {
		for (j = i - 1; j >= 0; j--) {
			double dx = p[i].first - p[j].first;
			double dy = p[i].second - p[j].second;
			double dist = dx * dx + dy * dy;
			
			if (dx * dx >= minDist2) break;
			
			minDist2 = min(minDist2, dist);
		}
	}
	
	printf("%.14f\n", sqrt(minDist2));
	return 0;
}

Measured memory_bytes: 4848
import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
		
		Scanner keyboard = new Scanner(System.in); 
		
		long L  = keyboard.nextLong();
		long R  = keyboard.nextLong();
		long x = 2019;
		
		if(R-L>=2018) {
			System.out.print(0);
		}else{
			for(long i = L; i <=R; i++) {
				for(long j = i+1; j <=R; j++) {
					Long amari = (i*j) % 2019;
					x = (amari<=x)? amari:x ;
				}
			}
			System.out.print(x);
		}
		keyboard.close();	
	}
}


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

using namespace std;

int main(){
    int n;
    cin >> n;
    int64_t q, a, b;
    int64_t S_l = 0, S_r = 0, S_b = 0;
    multiset<int64_t> S;

    cin >> q >> a >> b;
    S.insert(a);
    auto medi = S.begin();
    S_b += b;

    for (int i = 1; i < n; i++){
        cin >> q;
        if (q == 1){
            cin >> a >> b;
            S.insert(a);
            S_b += b;
            if (S.size() % 2 == 1){
                if (*medi <= a){
                    S_r += a;
                    S_l += *medi;
                    medi++;
                    S_r -= *medi;
                }else{
                    S_l += a;
                }
            }else{
                if (a < *medi){
                    S_l += a;
                    S_r += *medi;
                    medi--;
                    S_l -= *medi;
                } else {
                    S_r += a;
                }
            }
        }
        else if (q == 2){
            int64_t t = (int64_t(S.size()) - 1) / 2 * (*medi);
            int64_t u = (int64_t(S.size()) / 2) * (*medi);
            cout << *medi << " " << t - S_l + S_r - u + S_b << endl;
        }
    }

}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, a[101010];
int d[101010];
void solve(){
	cin >> n;
	int cnt = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		if(a[i] > n) cnt++;
		else d[a[i]]++;
	}
	
	for(int i = 1; i <= n; i++){
		if(d[i] >= i) cnt += d[i]-i;
		else cnt += d[i];
	}
	cout << cnt << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
using namespace std;
int main(int argc, char const *argv[]) {
  int n;
  cin>>n;
  int l,r;
  long long int num=0;
  for(int i=0;i<n;i++){
    cin>>l>>r;
    num+=r-l+1;
  }
  cout<<num<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define DIM 200005
using namespace std;
int n, i, x, y, nod, m;
int d[DIM], viz[DIM], s[DIM];
vector<int> v[DIM];
void dfs(int nod){
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            d[vecin] = 1 + d[nod];
            dfs(vecin);
        }
    }
}
int main(){
    cin>> n;
    for(i = 1; i < n; i++){
        cin>> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    s[1] = 1;
    for(i = 3; i <= n; i++){
        if(s[i - 1] == 0 || s[i - 2] == 0){
            s[i] = 1;
        }
    }
    dfs(1);
    for(i = 1; i <= n; i++){
        if(d[i] > d[nod]){
            nod = i;
        }
    }
    for(i = 1; i <= n; i++){
        d[i] = viz[i] = 0;
    }
    dfs(nod);
    for(i = 1; i <= n; i++){
        m = max(m, d[i]);
    }
    if(s[m + 1] == 1){
        cout<<"First";
    }
    else{
        cout<<"Second";
    }
}


Measured memory_bytes: 22912
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15) //15桁まで表示
#define str string
typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui,ui> puu;
typedef pair<int, int> P;
typedef vector<int> vi;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int floor(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
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;};

int main() {
    int x,y,z;
    cin >> x>>y>>z;
    cout << (x-z)/(y+z) << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
using namespace std;

const double PI=acos(-1);

int main(){
    string s;
    cin >> s;

    int cnt = 0, max = 0;
    for(int i = 0; i < s.length(); i++){
        if(s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T'){
            max = std::max(max, cnt);
            cnt = 0;
            continue;
        }
        cnt++;
    }
    max = std::max(max, cnt);

    cout << max << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>
#include <random>
#include <chrono>
#include <algorithm>
#include <unordered_map>

int64_t segtree[100][1000 * 100];
int64_t gcd(int64_t a, int64_t b){
	// a > b;
	if(a % b == 0)return b;
	return gcd(b, a % b);
}
int64_t gcd_rem(int idx, int rank){
	int64_t ret = 0;
	for(int i=1;i<=rank;i++){
		if(ret == 0){
			ret = segtree[i-1][idx ^ 1];
		}
		else{
			int64_t a, b;
			a = std::max(ret, segtree[i-1][idx ^ 1]);
			b = std::min(ret, segtree[i-1][idx ^ 1]);
			if(b != 0)ret = gcd(a, b);
		}
		idx = idx / 2;
	}
	return ret;
}
int main(void){
	int n;
	std::cin >> n;
	for(int i=0;i<n;i++){
		std::cin >> segtree[0][i];
	}
	int sz = n;
	int rank = 0;
	while(sz > 1){
		rank++;
		for(int j=0;j<sz;j+=2){
			int64_t a, b;
			a = std::max(segtree[rank-1][j], segtree[rank-1][j+1]);
			b = std::min(segtree[rank-1][j], segtree[rank-1][j+1]);
			if(b == 0)b = a;
			segtree[rank][j/2] = gcd(a, b);
		}
		sz = sz % 2 + sz / 2;
	}
	//
	int64_t ans = 1;
	for(int i=0;i<n;i++){
		ans = std::max(gcd_rem(i, rank), ans);
	}
	std::cout << ans << std::endl;
}

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

int main()
{
   int input;
   cin >> input;
   int A = input /10;
   int B = input/1000;
   B = input - B*1000;

   if ((A%111==0)||(B%111==0)) cout << "Yes" << endl;
   else cout << "No" << endl;
}

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

int main(){
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll now=k,ans=0;
    ans+=min(now,a);
    now-=min(now,a);
    if(now>0) now-=min(now,b);
    if(now>0) ans-=now;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int LIM = 105;
int n, w, ans = 0;
int q[LIM];
int multime[100005];
int v[LIM];


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

    for(int i = 1; i <= n; ++i) {
        cin >> q[i] >> v[i];
    }

    vector <int> s;

    for (int j = 1; j <= n; ++j) {
        vector<pair<int,int>> modificari;

        ans = max(ans, v[j]);

        int lg = s.size();

        if(multime[v[j]] == 0)  //daca volumul lui j nu are greutate
            s.push_back(v[j]);
       // cout << lg << '\n';
        for (int k = 0; k < lg; ++k) {
            /// s[k] = volum , v[j] = volum,  q[j] = greutate
            /// sir[volum] = greutate minima

            //cout << s[k] << " " << multime[s[k]] << '\n';

            if (multime[s[k]] + q[j] <= w){ //daca greutatea se incadreaza in W

                if (multime[s[k] + v[j]] == 0) // daca suma rezultata nu mai a aparut pana acum
                    s.push_back(s[k] + v[j]);

                //cout << s[k] << "+" << v[j] << " " << multime[s[k]] << " " << q[j] << " " << multime[s[k]] + q[j] << '\n';

                modificari.push_back(make_pair(s[k] + v[j], multime[s[k]] + q[j]));

                ans = max(ans, s[k] + v[j]);
            }
            //cout <<"\n";
        }
        if(multime[v[j]] == 0)
            multime[v[j]] = q[j];
        else
            multime[v[j]] = min(multime[v[j]], q[j]);

        for(size_t i = 0; i < modificari.size(); ++i) {
            if(multime[modificari[i].first] == 0)
                multime[modificari[i].first] = modificari[i].second;
            else
                multime[modificari[i].first] = min(multime[modificari[i].first], modificari[i].second);
        }
    }


    cout << ans;

    return 0;
}


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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const int INF = 1e9;

int main(void){

	int L; cin >> L;
	double ans = L/3.0;
	ans = pow(ans, 3);

	cout << setprecision(13) <<  ans << endl;


	return 0;

}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
const int N=2020,P=1000000007;
int i,j,k,n,m,K,ans;
int f[N][N],s[N][N];
void Up(int i,int j,int f) {
	if (j>m) i+=j-m,j=m;
	if (0<=i && i<=n && 0<=j && j<=m) s[i][j]=(s[i][j]+f)%P;
}
int main() {
	scanf("%d%d%d",&n,&m,&K);
	f[0][0]=1;
	if (0%(K-1)==n%(K-1) && 0%(K-1)==(m-1)%(K-1)) ans=P-1;
	for (i=0;i<=n;i++)
		for (j=0;j<=m;j++) {
			if (i) s[i][j]=(s[i][j]+s[i-1][j+1])%P;
			f[i][j]=(f[i][j]+s[i][j])%P;
			Up(i,j+K-1,f[i][j]);
			Up(i+K,j-1,(P-f[i][j])%P);
			if (i%(K-1)==n%(K-1) && j+K-1<=m-1 && j%(K-1)==(m-1)%(K-1)) ans=(ans+P-f[i][j])%P;
			if (i%(K-1)==n%(K-1) && j<=m-1 && j%(K-1)==(m-1)%(K-1)) ans=(ans+f[i][j])%P;
		}
	printf("%d\n",ans); 
}

Measured memory_bytes: 31872
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793
const int INF = 100000000;
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,1,-1,-1,1};

int main(){
    int n;
    cin >> n;
    double x = 0;
    while(n--){
        int a;
        cin >> a;
        x += 1.0 / a;
    }
    printf("%0.5lf\n", 1 / x);
}


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

#define WIN 1
#define LOSE -1

int n, m, x, y, game[10][10];
int ans;

void dfs(int x, int y) {
	if (y < n) {
		y++;
	}
	else if (x < n) {
		y = 1;
		x++;
	}
	else {
		for (int i = 1; i <= n; i++) {
			int t = 0;
			for (int j = 1; j <= n; j++) {
				t += game[i][j];
			}
			if (t != 0) {
				return;
			}
		}
		ans++;
		return;
	}

	if (y == 1 && x > 1) {
		int c = 0;
		for (int i = 1; i <= n; i++) {
			c += game[x - 1][i];
		}
		if (c != 0) {
			return;
		}
	}

	if (game[x][y] == 0 && x != y) {
		game[x][y] = WIN;
		game[y][x] = LOSE;
		dfs(x, y);

		game[x][y] = LOSE;
		game[y][x] = WIN;
		dfs(x, y);

		game[x][y] = 0;
		game[y][x] = 0;
	}
	else {
		dfs(x, y);
	}
}

int main() {
	cin >> n;
	while (n) {
		cin >> m;
		fill(game[0], game[9], 0);
		ans = 0;
		for (int i = 0; i < m; i++) {
			cin >> x >> y;
			game[x][y] = WIN;
			game[y][x] = LOSE;
		}
		dfs(1, 1);
		cout << ans << endl;
		cin >> n;
	}
	return 0;
}


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

int main() {
    ll N;
    cin >> N;
    ll mod = 1e9+7;
    if (N == 1) {
        cout << 1 << endl;
        return 0;
    }
    vector<vector<ll>> dp(N+3, vector<ll>(2, 0));
    dp[N][0] = 1;
    dp[N][1] = N-1;
    dp[N-1][0] = N;
    dp[N-1][1] = (N-1)*N%mod;
    
    ll sum = 0;
    ll sum2 = 0;
    for (int i = N-2; i >= 1; i--) {
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod;
        sum += dp[i+3][1];
        sum %= mod;
        sum2 += sum;
        sum2 %= mod;
        dp[i][1] = (sum2 + (N-1)*N) % mod;
    }
    cout << (dp[1][0] + dp[1][1]) % mod << endl;
    return 0;
}

Measured memory_bytes: 54912