akhauriyash/Code-Regression huggingface dataset:
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//while adding and subs check if mod becomes -ve
//while using an integer directly in a builtin function add ll
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Dont keep array name as size or any other key word

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 1000000007 //998244353
#define lld long double
#define mii map<int, int>
#define mci map<char, int>
#define msi map<string, int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const long long N=200005, INF=2000000000000000000;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
    int g=__gcd(a, b);
    return a/g*b;
}
int power(int a, int b, int p)
    {
        if(a==0)
        return 0;
        int res=1;
        a%=p;
        while(b>0)
        {
            if(b&1)
            res=(res*a)%p;
            b>>=1;
            a=(a*a)%p;
        }
        return res;
    }

int32_t main()
{
    IOS;
    int n,m,k;
    cin>>n>>m>>k;
    vi a, b;
    a.pb(0);
    b.pb(0);
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.pb(x);
    }
    for(int i=0;i<m;i++)
    {
        int x;
        cin>>x;
        b.pb(x);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    a[i]+=a[i-1];
    for(int i=1;i<=m;i++)
    b[i]+=b[i-1];
    for(int i=0;i<=n;i++)
    {
        if(a[i]>k)
        break;
        int rem=k-a[i];
        auto it=upper_bound(all(b), rem);
        int pos=(it-b.begin());
        ans=max(ans, pos+i-1);
    }
    cout<<ans;
}

Measured memory_bytes: 7960
#include<stdio.h>
#include<string.h>

int head,tail;
int Q[1000001]={0};

int insert(int *Q,int x)
{
	Q[head]=x;
	head++;
	return 0;
}
int delete(int *Q,int x)
{
	int i;
	for(i=head;i>=tail;i--)
	{
		if(Q[i]==x){Q[i]=-1;break;}
	}
	if(i==head){head--;}
	if(i==tail){tail++;}
	return 0;
}
int deleteFirst(int *Q)
{
	while(1)
	{
		if(Q[head-1]==-1){head--;}
		else{break;}
	}
	Q[head-1]=-1;
	head--;
	return 0;
}
int deleteLast(int *Q)
{
	while(1)
	{
		if(Q[tail]==-1){tail++;}
		else{break;}
	}
	Q[tail]=-1;
	tail++;
	return 0;
}
int main(void)
{
	int d=0,i,n,q,t;
	char s[16];
	scanf("%d",&n);
	head=tail=0;
	for(i=0;i<n;i++)
	{
		scanf("%s",s);
		if(!strcmp(s,"insert")){scanf("%d",&t);insert(Q,t);}
		else if(!strcmp(s,"delete")){scanf("%d",&t);delete(Q,t);}
		else if(!strcmp(s,"deleteFirst")){deleteFirst(Q);}
		else if(!strcmp(s,"deleteLast")){deleteLast(Q);}
	}
	for(i=head-1;i>=tail;i--)
	{
		if(Q[i]!=-1)
		{
			if(d==1){printf(" ");}
			printf("%d",Q[i]);
			d=1;
		}
	}
	printf("\n");

	return 0;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define BiSearchRangeNum(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y)

static const int MAX = 100000;

vector<int> G[MAX];
int N;
bool visited[MAX];
int prenum[MAX], parent[MAX], lowest[MAX], timer;

void dfs(int current, int prev) {
  prenum[current] = lowest[current] = timer;
  timer++;

  visited[current] = true;

  int next;

  rep(i, 0, G[current].size()) {
    next = G[current][i];

    if (!visited[next]) {
      // ノードcurrentからノードnextへ訪問する直前の処理
      parent[next] = current;
      dfs(next, current);
      // ノードnextの探索が終了した直後の処理
      lowest[current] = min(lowest[current], lowest[next]);
    } else if (next != prev) {
      // エッジcurrent --> nextがback-edgeの場合の処理
      lowest[current] = min(lowest[current], prenum[next]);
    }
  }
};

void art_points() {
  rep(i, 0, N) {
    visited[i] = false;
  }

  timer = 1;
  dfs(0, -1); // 0: root
  set<int> ap;
  int np = 0; // rootの子の数
  rep(i, 1, N)  {
    int p = parent[i];
    if (p == 0) np++;
    else if (prenum[p] <= lowest[i]) {
      ap.insert(p);
    }
  }

  if (np > 1) {
    ap.insert(0);
  }
  for (set<int>::iterator it = ap.begin(); it != ap.end(); it++) {
    cout << *it << endl;
  }
};

int main() {
  int m;
  cin >> N >> m;
  rep(i, 0, m) {
    int s, t;
    cin >> s >> t;
    G[s].push_back(t);
    G[t].push_back(s);
  }

  art_points();
};



Measured memory_bytes: 6956
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
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);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    const int MAX_N = 200000;
    int N, A[MAX_N];
    cin >> N;
    REP(i, N) {
        cin >> A[i];
    }
    ll res = 0;
    int acc = 0;
    for (int s = 0, e = 0; e < N;) {
        while ((acc & A[e]) == 0) {
            acc += A[e];
            e++;
            res += (e - s);
            if (e == N) {
                break;
            }
        }
        while ((acc & A[e]) != 0) {
            acc -= A[s];
            s++;
            if (s == e) {
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=8000;
string s;
int N;
vector<int> vx,vy;
int x,y;

bool C(const vector<int> &vec,int v){
	bitset<MAX_N*2+1> dp;
	dp[MAX_N]=true;
	for(auto i:vec){
		dp=(dp<<i)|(dp>>i);
	}
	if (v<-MAX_N){
		return false;
	}
	return dp[v+MAX_N];
}
int main(){
	cin>>s>>x>>y;
	N=s.size();
	{
		bool f=false;
		REP(i,N){
			int j;
			for(j=i;j<N && s[j]=='F';j++){
			}
			if (!f){
				if (i==0){
					x-=j-i;
				}else{
					vx.push_back(j-i);
				}
			}else{
				vy.push_back(j-i);
			}
			f=!f;			
			i=j;
		}
	}
	cout<<(C(vx,x) && C(vy,y) ? "Yes" : "No")<<endl;
	return 0;
}

Measured memory_bytes: 256
/* ****Ragnar7 _Lawliet_**** */
/* First, solve the problem.Then write the code. */
#include<bits/stdc++.h>
#define ll          long long
#define ld             long double
#define hell        1000000007
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

class convexHull
{
public:
    vector<pair<ll,ll> > lines;

    static bool intersect(pair<ll,ll> p1,pair<ll,ll> p2,pair<ll,ll> p3)
    {
        return (ld)(p1.second - p2.second)/(ld)(p2.first - p1.first) >= (ld)(p1.second - p3.second)/(ld)(p3.first - p1.first);
    }
    
    void addLine(pair<ll,ll> newLine)
    {
        // cout<<newLine.first<<" "<<newLine.second<<endl;
        while(!lines.empty() and lines.back().first==newLine.first and lines.back().second>=newLine.second)
            lines.pop_back();
        while((ll)lines.size()>1LL and intersect(lines[(ll)lines.size()-2LL],lines.back(),newLine))
            lines.pop_back();
        if(lines.empty() or lines.back().first != newLine.first)
        lines.push_back(newLine);

    }

    ll getMin(ll valx)
    {
        ll L =0,R=(ll)lines.size()-1,mid;
        ll maxi = LLONG_MAX;
        while(L<=R)
        {
            mid = (L+R)/2;
            maxi = min(maxi,lines[mid].first*valx+lines[mid].second);
            if(mid+1<=R and lines[mid].first*valx+lines[mid].second < lines[mid+1].first*valx+lines[mid+1].second)
                R = mid;
            else if(mid+1<=R)
                L = mid+1;
            else
                break;
        }
        return maxi;
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen ("input.txt","r",stdin);
    // freopen ("output.txt","w",stdout);
    #endif
    ll t = 1;
    // cin>>t;
    while(t--)
    {
        ll n,c;
        cin>>n>>c;
        vector<ll> heights(n+1,0);
        for(ll i=1;i<=n;i++)
            cin>>heights[i];
        vector<ll> dp(n+5,0);
        convexHull hull ;
        ll tmp;
        hull.addLine({-2*heights[1],heights[1]*heights[1]});
        for(ll i=2;i<=n;i++)
        {
            tmp = hull.getMin(heights[i]);
            dp[i] = tmp + heights[i]*heights[i] + c;
            hull.addLine({-2*heights[i] , dp[i]+heights[i]*heights[i]});
        }

        cout<<dp[n];   
        
        
    }

    
    time
    return 0;
}

Measured memory_bytes: 10564
N, M = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(N)]
D.sort(key=lambda t:t[0])

s = 0
c = 0
for i in range(N):
    s += D[i][1]
    c += D[i][0] * D[i][1]
    if s >= M:
        c -= (s - M) * D[i][0]
        break

print(c)



Measured memory_bytes: 61528
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int jera(int H,int **C)
{
	for(int i=0;i<H;i++){
		if(C[i][0]==C[i][1]){
			if(C[i][1]==C[i][2]){
				if(C[i][2]==C[i][3]){
					if(C[i][3]==C[i][4]){
						C[i][0]
							=C[i][1]
							=C[i][2]
							=C[i][3]
							=C[i][4] =0;
					} else {
						C[i][0]
							=C[i][1]
							=C[i][2]
							=C[i][3] =0;
					}
				} else {
					C[i][0]
						=C[i][1]
						=C[i][2] =0;
				}
			} else {
				if((C[i][2]==C[i][3])&&(C[i][3]==C[i][4])){
					C[i][2] =C[i][3] =C[i][4] =0;
				}
			}
		} else {
			if(C[i][1]==C[i][2]){
				if(C[i][2]==C[i][3]){
					if(C[i][3]==C[i][4]){
						C[i][1]
							=C[i][2]
							=C[i][3]
							=C[i][4] =0;
					} else {
						C[i][1]=C[i][2]=C[i][3]=0;
					}
				}
			} else {
				if((C[i][2]==C[i][3])&&(C[i][3]==C[i][4])){
					C[i][2] =C[i][3] =C[i][4] =0;
				}
			}
		}
	}
	return 0;
}

int jfal(int H,int **C)
{
	int flag=0;
	for(int i=0;i<H;i++){
		for(int j=0;j<5;j++){
			if(C[i][j]==0){
				for(int k=i;k>0;k--){
					if(C[k-1][j]!=0)flag=1;
					C[k][j]=C[k-1][j];
				}
				C[0][j]=0;
			}
		}
	}
	return flag;
}

int main()
{
	while(1){
		int H;
		cin >> H;
		if(H==0)break;
		int **C;
		C=(int**)malloc(sizeof(int*)*H);
		int sum=0;
		for(int i=0;i<H;i++){
			C[i]=(int*)malloc(sizeof(int)*5);
			for(int j=0;j<5;j++){ cin >> C[i][j]; sum+=C[i][j]; }
		}
		do{
			jera(H,C);
		}while(jfal(H,C));

		for(int i=0;i<H;i++){
			for(int j=0;j<5;j++){ sum-=C[i][j]; }
		}
		cout << sum << endl ;
		for(int i=0;i<H;i++){
			free(C[i]);
		} free(C);
	}

	return 0;
}

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

using namespace std;

int main(){

	int n,am;
	cin>>n>>am;
	int a[n];
	int ans=0;

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

	for(int i=0;i<n;i++){
	
		am-=a[i];
		ans++;
		if(am==0){
		
			break;
		}
		if(am<0){
		
			ans--;
			break;
		}
	}
	if(am>0){
	
		ans--;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
constexpr int MOD = 1e9+7;

int main() {
  int N; cin >> N;
  map<string, int> m;
  string ACGT = "ACGT";

  rep(i, 4*4*4) {
    string tmp;
    int two = 1;
    rep(j, 3) {
      tmp += ACGT[(i / two) % 4];
      two *= 4;
    }
    if (tmp == "AGC" || tmp == "ACG" || tmp == "GAC")
      continue;
    ++m[tmp];
  }

  rep(i, N-3) {
    map<string, int> m2;
    for (const auto& e:m) {
      string s = e.first;
      int forbidden = -1;
      if (s[0] == 'A' && s[2] == 'G' || s.substr(0, 2) == "AG" || s.substr(1) == "GA" || s.substr(1) == "AG")
        forbidden = 1;
      else if (s.substr(1) == "AC")
        forbidden = 2;

      rep(j, 4)
        if (j != forbidden)
          (m2[s.substr(1) + ACGT[j]] += e.second) %= MOD;
    }
    swap(m, m2);
  }
  int ans = 0;
  for (const auto& e:m)
    (ans += e.second) %= MOD;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val str = readLine()?.orEmpty()
    var result = "No"
    val sLength = str!!.length

    val strLeft = str.substring(0,((sLength - 1) / 2))
    val strRight = str.substring(((sLength + 1) / 2),sLength)

    if(judgeGram(str) && judgeGram(strLeft) && judgeGram(strRight)){
        result = "Yes"
    }

    
    println(result)
}

fun judgeGram(s:String):Boolean{
    var result = false
    val sLength = s.length

    var sLeft = ""
    var sRight = ""

    if(sLength % 2 == 0){
        sLeft = s.substring(0,sLength  / 2)
        sRight = s.substring(sLength / 2,sLength)

    }else{
        sLeft = s.substring(0,((sLength - 1) / 2))
        sRight = s.substring(((sLength + 1) / 2),sLength)
    }

    val sRR = sRight.reversed()
    if(sLeft == sRR){
        result = true
    }
    return result
}

Measured memory_bytes: 33788
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back

int n,m;
ll dp[90001000];
int main(){
    ll d=0;
    string ans="";
    cin >> n >> m;
    vector<int> v,u;//vは可能なコスト、uは使える数
    map<int,int> c;
    c.insert({1,2});
    c.insert({2,5});
    c.insert({3,5});
    c.insert({4,4});
    c.insert({5,5});
    c.insert({6,6});
    c.insert({7,3});
    c.insert({8,7});
    c.insert({9,6});
    for(int i=1;i < n+1;i++)
    {
        dp[i]=-1;
    }//init これによりあり得ないコストで終わることはない

    for(int i=0;i<m;i++)
    {
        int x;
         cin >> x;
         v.pb(c.at(x));
         u.pb(x);
    }
    sort(v.begin(),v.end());
    sort(u.begin(),u.end(),greater<int>());
    unique(v.begin(),v.end());

    for(int i=2;i < n+1;i++)
    {
        for(int j=0;j < v.size();j++)
        {
            
            if(i-v.at(j)>=0){
                dp[i]=max(dp[i-v.at(j)]+1,dp[i]);
            }
        }
    }//dp[n]桁がつくれる最大桁数

//-----------------------------------------------
    ll cost=n,cnt=0;
    for(int i=0;i<u.size() && cnt<=dp[cost] ;i++)
    {
        if(n-c.at(u.at(i))>=0 && dp[n-c.at(u.at(i))]==dp[n]-1){
            ans+=(char)(u.at(i)+48);
            n-=c.at(u.at(i));
            i--;
            cnt++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
d1 :: [Double] -> [Double] -> Double
d1 v1 v2 = foldl (\s (a,b) -> s + abs(a-b) ) 0 $ zip v1 v2

d2 :: [Double] -> [Double] -> Double
d2 v1 v2 = sqrt $ foldl (\s (a,b) -> s + (a-b)*(a-b) ) 0 $ zip v1 v2

d3 :: [Double] -> [Double] -> Double
d3 v1 v2 = (** (1.0/3.0)) $ foldl (\s (a,b) -> s + (abs(a-b))*(abs(a-b))*(abs(a-b)) ) 0 $ zip v1 v2

di :: [Double] -> [Double] -> Double
di v1 v2 = maximum $ map (\(a,b) -> abs(a-b)) $ zip v1 v2

ans :: [[Double]] -> [Double]
ans (v1:v2:_) = [
  d1 v1 v2,
  d2 v1 v2,
  d3 v1 v2,
  di v1 v2 ]

main = do
  l <- getLine
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Double]]
      o = ans i
  mapM_ print o

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

def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

#高速素因数分解

#エラストテネスのふるい
#sieveが0なら素数、0以外ならその値を割り切る素数
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve
#素因数分解
#dicではkey=素数、value=何乗か
def prime(n,sieve):
  dic={}
  while(1):
    if sieve[n]==0:
      dic[n]=dic.get(n,0)+1
      break
    else:
      p=sieve[n]
      dic[p]=dic.get(p,0)+1
      n=n//p
  return dic

def setwise(a):
  l=a[0]
  for i in range(len(a)):
    l=gcd(l,a[i])
  return l==1


if setwise(a):
  check=set()
  sieve=create_sieve(max(a))
  for num in a:
    if num!=1:
      dic=prime(num,sieve)
      for j in dic:
        if j in check:
          print("setwise coprime")
          exit()
        else:
          check.add(j)
  print("pairwise coprime")
  
else:
  print("not coprime")
  
  
  

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


int main(){
    int a;
    cin >> a ;
    if (a % 2 == 0) {
        cout << (a / 2)*(a / 2) << endl;
    }
    else cout << (a / 2 + 1)*(a / 2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
    string S, T;
    unsigned int A, B;
    string U;
    
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    
    if(S == U){
    	A--;
    }else{
    	B--;
    }
 
    cout << A << " " << B << endl;
}

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

int main(){
    int e;
    while(cin>>e){
        if(e==0) break;
        int m=1e9;
        for(int i=0;i*i*i<=e;i++){
            for(int j=0;j*j<=e-i*i*i;j++){
                int c=i+j+(e-i*i*i-j*j);
                m=min(c,m);
            }
        }
        cout<<m<<endl;

    }
}


Measured memory_bytes: 2992
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>  //sqrt 
#include <iomanip> //setprecision
using namespace std;

int main(){
    int x=0;
    cin>>x;
    if(400<=x&&x<=599){
        cout<<8<<endl;
    }else if(600<=x&&x<=799){
        cout<<7<<endl;
    }else if (800<=x&&x<=999)
    {
        cout<<6<<endl;
    }else if (1000<=x&&x<=1199)
    {
        cout<<5<<endl;
    }else if (1200<=x&&x<=1399)
    {
        cout<<4<<endl;
    }else if (1400<=x&&x<=1599)
    {
        cout<<3<<endl;
    }else if (1600<=x&&x<=1799)
    {
        cout<<2<<endl;
    }else if (1800<=x&&x<=1999)
    {
        cout<<1<<endl;
    }
    
    
    
}

Measured memory_bytes: 3224
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const int M=1e6+5;
const ll mod=1e9+7;
int n,cnt;
bool vis[M]; 
int num[M],used[N];
ll a[N],ans=0,mx[N],p[N],d[N][22];
struct tree{
	int l,r,mid;
	ll mul;
}tr[N*3];
void buildtree(int i,int l,int r){
	tr[i].l=l;tr[i].r=r;
	tr[i].mid=(l+r)>>1; 
	tr[i].mul=1;
	if(l==r){
		if(mx[l])tr[i].mul=p[l];
		return ;
	}
	int mid=(l+r)>>1;
	buildtree(i<<1,l,mid);
	buildtree((i<<1)+1,mid+1,r);
	tr[i].mul=tr[i<<1].mul*tr[(i<<1)+1].mul%mod;
	return ;
}
ll query(int i,int l,int r){
	if(l<=tr[i].l&&r>=tr[i].r)return tr[i].mul;
	int mid=tr[i].mid;
	ll Mul=1;
	if(l<=mid)Mul*=query(i<<1,l,r);
	if(r>mid)Mul*=query((i<<1)+1,l,r);
	return Mul%mod;
}
int main(){
	cnt=0;
	for(int i=2;i<M;i++){
		if(!vis[i]){
			p[++cnt]=i;
			for(int j=2;j*i<M;j++)vis[j*i]=1;
			d[cnt][0]=1;num[i]=cnt;
			for(int j=1;j<=20;j++)d[cnt][j]=d[cnt][j-1]*p[cnt]%mod;
		}
	}
	//cout<<cnt<<endl;
	int qwq=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		int x=a[i],y;
		for(int j=1;p[j]<=1000;j++){
			y=0;
			while(x%p[j]==0){
				x/=p[j];y++;
			}
			mx[j]=max(mx[j],(ll)y);
			qwq=max(qwq,j+1);
		}
		if(x>1)mx[num[x]]=1;
	}
	buildtree(1,1,cnt);
	int used_pri=0;
	ll tmp=0;
	for(int i=1;i<=n;i++){
		ll b=1;
		int x=a[i],y;
		for(int j=1;p[j]<=1000;j++){
			y=0;
			while(x%p[j]==0){
				x/=p[j];y++;
			}
			b=b*d[j][mx[j]-y]%mod;
		} 
		if(x==1)b*=query(1,qwq,cnt);
		else {
			int Num=num[x];
			if(Num>qwq)b*=query(1,qwq,Num-1);
			b%=mod;
			if(Num!=cnt)b*=query(1,Num+1,cnt);
		}
		b%=mod;ans+=b;
	}
	ans%=mod;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 32128
import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)



Measured memory_bytes: 9440
#include<cstdio>

long long a,b,x;
long long s,e;
int main(){
	scanf("%lld%lld%lld",&a,&b,&x);
	if(a%x==0)s=a/x;
	else s=a/x+1;
	e=b/x;
	if(s<=e)printf("%lld",e-s+1);
	else printf("0");
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);

using namespace std;

vector<pair<int,int>> v[100001];
bool vis[100001];
int color[100001];

void dfs(int x)
{
    for(auto i:v[x])
    {
        if(!vis[i.fi])
        {
            vis[i.fi]=true;
            if(i.se%2==0)
            {
                color[i.fi]=color[x];
            }
            else color[i.fi]=color[x]^1;
            dfs(i.fi);
        }
    }
}

int main()
{
    IOS;
    int n;
    cin>>n;
    int x,y,w;
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y>>w;
        v[x].pb({y,w});
        v[y].pb({x,w});
    }
    memset(vis,false,sizeof vis);
    vis[1]=true;
    color[1]=0;
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        cout<<color[i]<<endl;
    }
    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

long long a, b;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> a >> b;
    cout << max(max(a * b, a - b), a + b);

}



Measured memory_bytes: 256
import math

a, b, h, m = map(float, input().split())
hour = 30 * h + 0.5 * m
minute = 6 * m

radian = abs(hour - minute)

if radian < 180:
    dist = a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(radian))
    print(math.sqrt(dist))
elif radian == 180:
    print(a + b)
else:
    radian = 360 - radian
    dist = a ** 2 + b ** 2 - 2 * a * b * math.cos(math.radians(radian))
    print(math.sqrt(dist))


Measured memory_bytes: 9352
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <set>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
#define DEBUG
#ifdef DEBUG
	#define debug printf
#else
	#define debug(...)
#endif
const int maxn = 4;
int deg[maxn];
int main(int argc, char const *argv[])
{
	for(int i = 0;i < 6; ++i)
	{
		int x;
		scanf("%d",&x);
		x--;
		deg[x]++;
	}
	int ans = 0;
	for(int i = 0;i < 4; ++i)
	{
		ans += deg[i] & 1;
	}
	if(ans == 2 || ans == 0)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 256
#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par =  [i for i in range(n)]
    self.rank = [1 for _ in range(n)]

  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      self.rank[x] += self.rank[y]
      self.par[y] = x

  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)
    
n,m = map(int,input().split())
info = [list(map(int,input().split())) for i in range(m)]
uf = UnionFind(n)
okisa = [1]*(n)
ans = [0]*(m)
ans_=0
for i in range(n):
  ans_ = ans_+i
  
ans[m-1]= ans_
for i in range(1,m)[::-1]:
  if uf.is_same(info[i][0]-1,info[i][1]-1):
    ans[i-1] = ans[i] 
  else:
    ans[i-1] = ans[i]-uf.rank[uf.find(info[i][0]-1)]*uf.rank[uf.find(info[i][1]-1)]
    uf.union(info[i][0]-1,info[i][1]-1)
for i in range(m):
  print(ans[i])


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

using namespace std;

int main()
{
  int a, b, t;
  long long int ve = 0, sum = 0;
  scanf("%d", &t);
  scanf("%d %d", &a, &b);
  ve = a + b;
  t--;
  while(t--){
    scanf("%d %d", &a, &b);
    sum = a + b;
    ve = min(ve, sum);
  }
  printf("%lld\n", ve);
  
  return 0;
}

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

#define int long long
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define sq(x) (x)*(x)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define t4i tuple<int,int,int,int>
#define mii map<int,int>

const int INF = 1LL<<60;
const int MOD = 998244353;

template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
string to_string(string s) {return s;}
string to_string(bool b) {return b?"true":"false";}
template <typename A, typename B>
string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) { return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";}
template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}
string bin_string(int x) {
    const int d = 32;
    string result(d, ' ');
    REP(i, 0, d) result[d-1-i] = '0'+(x>>i & 1LL);
    return result;
}

int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

vector<vi> nodes;
vb seen;
void dfs(int u, int p=-1) {
    if (seen[u]) return;
    seen[u] = true;
    for (int v : nodes[u]) if (v!=p) {
        dfs(v, u);
    }
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int BIG = 200000;
    vi sieve(BIG);
    REP(p, 2, BIG) if (!sieve[p]) for (int u=2*p; u<BIG; u+=p) sieve[u] = p;

    int n;
    cin >> n;
    REP(i, n, BIG) if (!sieve[i]) {
        cout << i;
        break;
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define re(n) for (int i = 0; i < (n); ++i)
#define rej(n) for (int j = 0; j < (n); ++j)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <int, int> pii;
typedef vector <pair <int, int>> vii;

const ld PI = acos((ld)-1);

void f(set <ll> &v, ll n) {
    v.insert(1);
    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            v.insert(i);
            n /= i;
        }
    }
    if (n > 1)
        v.insert(n);
}

vector <char> d(1000005, 1);
 
void er(ll n) {
    d[0] = 0;
    for (ll i = 2; i < n + 1; ++i) {
        if (d[i] == 1) {
            for (ll j = i * i; j <= n; j += i)
                d[j] = 0;
        }
    }
}

int main() {
    #ifndef LOCALDEBUG
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #endif  // LOCALDEBUG
    er(1000003);
    ll a, b;
    cin >> a >> b;
    set <ll> aa, bb;
    f(aa, a);
    f(bb, b);
    vector <ll> s;
    for (ll y : aa) {
        if (bb.find(y) != bb.end()) {
            // if ((y < 1000003 && d[y]) || (y >= 1000003)) {
                s.push_back(y);
            // }
        }
    }
    int n = sz(s);
    // re(n) cout << s[i] << " ";
    cout << n;
    // re(50) cout << int(d[i]) << " ";
    
    return 0;
}


Measured memory_bytes: 1280
#include <iostream>

int main(){
    int n;
    std::string s, t;
    std::cin >> n >> s >> t;

    std::string ans = "";
    for(int i = 0; i < n; ++i){
        ans.push_back(s.at(i));
        ans.push_back(t.at(i));
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
print(0 if n%1000==0 else 1000-n%1000)

Measured memory_bytes: 10100
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<climits>
#include<ctime>
#include<cstring>
#include<sstream>
#define REP(i,p,n) for(int i=p;i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep_split(tok,a_str,re) for(char *tok = strtok((char *)a_str.c_str(),re); tok != NULL; tok = strtok(NULL,re))
#define ALL(c) (c).begin(), (c).end()
#define dump(a) cerr << #a << "=" << (a) << endl
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //t=min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //t=max
using namespace std;

int main() {
	string A,B;
	cin >> A >> B;
	bool is_match=false;

	rep(i,A.size()) {
		is_match = true;
		rep(j,B.size()) {
			if (i+j > A.size()) { 
				is_match = false;
				break;
			}
			if (! (A[i+j] == B[j] || B[j] == '_') ) {
				is_match = false;
				break;
			}
		}
		if (is_match) { break; }
	}
	cout << ((is_match) ? "Yes" : "No") << endl;

	return EXIT_SUCCESS;
}


Measured memory_bytes: 1184
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
int main() {
	ios_base::sync_with_stdio(false);
	string t; cin>>t;
	ll n=0,s=0,w=0,e=0;
	for (auto &c:t) {
		if (c=='N') n=1;
		if (c=='S') s=1;
		if (c=='E') e=1;
		if (c=='W') w=1;
	}
	//printf("%d %d %d %d. %lld %lld\n",n,s,e,w,n^s,e^w);
	if ((n^s)||(e^w)) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
//2704 ??????????????± 1_1_D
import java.util.Scanner;
public class Main{
	int S,h,m,s;
	
	public void solve(){
		Scanner sc=new Scanner(System.in);
		S=sc.nextInt();
		
			h=S/3600;
			m=(S-3600*h)/60;
			s=(S-3600*h-60*m);
			
			System.out.println(h+":"+m+":"+s);
			
	}
	public static void main(String[]args){
		Main obj=new Main();
		obj.solve();
	}
}

Measured memory_bytes: 17164
#include <iostream>
#include <utility>
#define P pair<char,int>
using namespace std;

P p[10];
int o[10];

bool dfs( int n ){
  if( n>0 && n % 3 ==0 ){
    int i=n-3;

    if( p[o[i]].first != p[o[i+1]].first ||
	p[o[i+1]].first != p[o[i+2]].first )
      return false;

    /*
    cout << "  n="<< n << endl;
    for( int j=0;j<3;j++ )
      cout << p[o[j+i]].first << "," << p[o[j+i]].second << endl;
    */
    if( ( p[o[i]].second+1 == p[o[i+1]].second &&
	  p[o[i]].second+2 == p[o[i+2]].second ) ||
	( p[o[i]].second == p[o[i+1]].second &&
	  p[o[i+1]].second == p[o[i+2]].second  ) )
      {
	if( n==9 ){
	  /*
	  for( int j=0;j<9;j++ )
	    cout << p[o[j]].first << " ";
	  cout << endl;
  	  for( int j=0;j<9;j++ )
	    cout  << p[o[j]].second << " " ;
	  cout << endl;
	  */
	  return true;
	}
      }else
      return false;
  }

  for( int i=0,j;i<9;i++ ){
    for( j=0;j<n && o[j]!=i ;j++ );
    if( j!=n ) continue;
    o[n]=i;
    if( dfs( n+1 ) ) return true;
  }
  return false;
}

int main(){
  int t;

  cin>>t;
  while( t-- ){
    for( int i=0;i<9;i++ )      cin >> p[i].second;
    for( int i=0;i<9;i++ )      cin >> p[i].first;
    if( dfs(0) )
      cout << "1" << endl;
    else
      cout << "0" << endl;
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
    double a = 0.0;
    double b = 0.0;
    double c = 0.0;
    double angel = 0.0;
    double area = 0.0;
    double cir = 0.0;
    double height = 0.0;
    
    cin >> a >> b >> angel;
    area = (a * b * sin(angel * M_PI / 180)) / 2;
    c = sqrt((a * a) + (b * b) - 2 * a * b * cos(angel * M_PI / 180));
    cir = a + b + c;
    height = 2 * area / a;
    
    cout << setprecision(10) << area << endl;
    cout << setprecision(10) << cir << endl;
    cout << setprecision(10) << height << endl;
    
    return 0;
}



Measured memory_bytes: 3588
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#include <cmath>
#include <string>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define Cout(s) cout<<s<<endl

bool sosuu(const int x)
{
	if (x == 2)return true;
	if (x < 2 || x % 2 == 0)return false;
	for (int i = 3; i * i <= x; i += 2)
		if (x % i == 0)return false;
	return true;
}

typedef long long ll;
using namespace std;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================

int a = 0, b = 0, c, d, n, k = 0;
string s, t;


int main()
{
	cin >> n;
	char x; bool y = true;
	rep(i, n) 
	{
		cin >> x;
		if (x == 'Y')y = false;
	}
	if (y)
		Cout("Three");
	else
		Cout("Four");

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    
    vector<string> vs(3);
    cin >> vs[0];
    cin >> vs[1];
    cin >> vs[2];
    
    bool flag = true;
    int tgt = 0; // 0:A, 1:B, 2:C
    while(flag)
    {
        if(vs[tgt].size() == 0)
        {
            if(tgt == 0)
            {
                cout << "A" << endl;
            }
            else if(tgt == 1)
            {
                cout << "B" << endl;
            }
            else if(tgt == 2)
            {
                cout << "C" << endl;
            }
            else
            {
                cout << "Error" << endl;
                return 1;
            }
            return 0;
        }

        int temp = vs[tgt][0];
        vs[tgt].erase(0, 1);

        if(temp == 97)
        {
            tgt = 0;
        }
        else if(temp == 98)
        {
            tgt = 1;
        }
        else if(temp == 99)
        {
            tgt = 2;
        }
        
        /*
        cout << "A:\t" << vs[0] << endl;
        cout << "B:\t" << vs[1] << endl;
        cout << "C:\t" << vs[2] << endl << endl;
         */
        
    }
    return 0;
}

Measured memory_bytes: 3040
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W; cin >> H >> W;
	vector<vector<char>> v(H, vector<char>(W));
	rep(i, 0, H) rep(j, 0, W) { cin >> v[i][j]; }
	auto inrange = [&](int i, int j) { return i >= 0 && i < H && j >= 0 && j < W; };
	rep(i, 0, H)rep(j, 0, W) {
		if (v[i][j] == '.') {
			int cnt = 0;
			rep(di, -1, 2)rep(dj, -1, 2) {
				int ni = i + di, nj = j + dj;
				dump(ni, nj);
				if (inrange(ni, nj)) {
					if (v[ni][nj] == '#')
						cnt++;
				}
			}
			v[i][j] = cnt + '0';
		}
	}
	rep(i, 0, v.size()) {
		cout << v[i][0];
		rep(j, 1, v[i].size()) { cout  << v[i][j]; }
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int n;
int a[100002];
int kq = 0;
int tong = 0;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[0] = 0;a[n+1] = 0;
    for (int i = 1; i <= n+1; i++) tong = tong + abs(a[i]-a[i-1]);
    for (int i = 1; i <= n; i++)
    {
        kq = tong - abs(a[i]-a[i-1]) - abs(a[i+1]-a[i]) + abs(a[i+1]-a[i-1]);
        cout << kq << endl;
    }
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;  
#define ordered_set tree<ll, null_type , less<ll> , rb_tree_tag , tree_order_statistics_node_update> 
#define ll long long
#define ull unsigned long long
#define pb push_back
#define inf 1e18
#define mk make_pair
#define ld long double
#define mod 1000000007
#define fi first
#define se second
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test ll t; cin>>t; while(t--)
#define setbits __builtin_popcount
#define endl '\n'
#define LOCAL
#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__) << "] "
int main()
{
    fastIO;
    string str;
    cin>>str;
    ll n,x,y;
    n=str.length();
    string str1,str2,str3;
    x=(n-1)/2;
    y=(n+3)/2;
    for(int i=0;i<x;i++)
    {
        str1+=str[i];
    }
    for(int i=y-1;i<n;i++)
    {
        str2+=str[i];
    }
    string str4,str5;
    str3=str;
    str4=str1;
    str5=str2;
    reverse(str3.begin(),str3.end());
    reverse(str4.begin(),str4.end());
    reverse(str5.begin(),str5.end());
    if(str==str3 && str1==str4 && str2==str5)
    {
        cout<<"Yes\n";
    }
    else
    {
        cout<<"No\n";
    }
}  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a[2222],res=0; cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      for(int k=j+1;k<n;k++){
        if(a[i]+a[j]>a[k])res++;
      }
    }
  }
  cout<<res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
template<typename T>
void print(T x) {
    cout << x << endl;
}
int main(void) {
    int a, b; cin >> a >> b;
    if(a<b) swap(a,b);
    int mx = max(2*a-1, a+b);
    cout << mx;
}


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

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var trains = new List<int>();
            string s;
            while ((s = Console.ReadLine()) != null)
            {
                int n = int.Parse(s);
                if (n == 0)
                {
                    Console.WriteLine(trains[trains.Count - 1]);
                    trains.RemoveAt(trains.Count - 1);
                }
                else
                    trains.Add(n);
            }
        }
    }
}

Measured memory_bytes: 5648
class Elm:
    def __init__(self, value, ptr_prev, ptr_next):
        self.value = value
        self.prev = ptr_prev
        self.next = ptr_next
#        self.prev = None
#        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.nil = Elm("NIL", None, None)
        self.nil.prev = self.nil # tail
        self.nil.next = self.nil # head
        
def insertVal(self, value):
    new_elm = Elm(value, self.nil, self.nil.next)
    new_elm.next.prev = new_elm
    self.nil.next = new_elm

def deleteVal(self, value):
    ptr = self.nil.next
    while ptr.value != value:
        if ptr.next == self.nil:
            return
        ptr = ptr.next
#    if ptr.value == value:
#        ptr.prev.next = ptr.next
#        ptr.next.prev = ptr.prev
    ptr.prev.next = ptr.next
    ptr.next.prev = ptr.prev

def deleteFirst(self):
    self.nil.next = self.nil.next.next
    self.nil.next.prev = self.nil

def deleteLast(self):
    self.nil.prev = self.nil.prev.prev
    self.nil.prev.next = self.nil

def show(self):
    ptr = self.nil.next
    while ptr!=self.nil:
#    while True:
        if ptr.next == self.nil:
            print(ptr.value)
            return
        print(ptr.value, end=" ")
        ptr = ptr.next
        
def selectOps(dll, command):
#    ops = command[0]
    if command[0] == "insert":
        insertVal(dll, command[1])
    elif command[0] == "delete":
        deleteVal(dll, command[1])        
    elif command[0] == "deleteFirst":
        deleteFirst(dll)
#    elif ops == "deleteLast":
    else:
        deleteLast(dll)
#    else:
#        print("Error: invalid oparation")

    
import sys

n = int(input())
l = DoublyLinkedList()

for i in range(n):
    command = sys.stdin.readline().split()
#    command = input().split(" ")
#    selectOps(dll=l, command=command)
    if command[0] == "insert":
        insertVal(l, command[1])
    elif command[0] == "delete":
        deleteVal(l, command[1])        
    elif command[0] == "deleteFirst":
        deleteFirst(l)
#    elif ops == "deleteLast":
    else:
        deleteLast(l)
show(l)



Measured memory_bytes: 227800
#include<bits/stdc++.h>
using namespace std;
const long double pi=3.14159265358979323846;
int main(){
  long double A,B;
  long double H = 0, M = 0;
  long double C = 0,x;

  cin >> A >> B >> H >> M;

  x = 11*pi*(60*H+M)/360;
  C = A*A + B*B - 2.0*A*B*cos(x);

  long double c = sqrtl(C);

  printf("%.20Lf\n",c);

}

Measured memory_bytes: 4164
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a;
    int color[8]={};
    int key=0;
    for(int i=0; i<n; i++){
        cin>>a;
             if(1<=a&&a<=399)color[0]=1;
        else if(400<=a&&a<=799)color[1]=1;
        else if(800<=a&&a<=1199)color[2]=1;
        else if(1200<=a&&a<=1599)color[3]=1;
        else if(1600<=a&&a<=1999)color[4]=1;
        else if(2000<=a&&a<=2399)color[5]=1;
        else if(2400<=a&&a<=2799)color[6]=1;
        else if(2800<=a&&a<=3199)color[7]=1;
        else if(3200<=a)key++;
    }
    int ans=0;
    for(int i=0; i<8;i++){
        if(color[i]==1)ans++;
    }
    if(ans==0)cout<<1<<" "<<ans+key<<endl;
    else cout<<ans<<" "<<ans+key<<endl;
    return 0;
}



Measured memory_bytes: 256
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

class Dis{
  public:
  vector<ll> rank,p;
  
  Dis(int s){
    rank.resize(s,0);
    p.resize(s,0);
    rep(i,s) makeSet(i);
  }
  
  void makeSet(int x){
    p[x]=x;
    rank[x]=0;
  }
  
  bool same(int x,int y){
    return findSet(x)==findSet(y);
  }
  
  void unite(int x,int y){
    link(findSet(x),findSet(y));
  }
  
  void link(int x,int y){
    if(rank[x]>rank[y]) p[y]=x;
    else{
      p[x]=y;
      if(rank[x]==rank[y]) rank[y]++;
    }
  }
  
  int findSet(int x){
    if(x != p[x]) p[x]=findSet(p[x]);
    return p[x];
  }
};
  
class Edge{
  public: int source,target;
          double cost;
  Edge(int source=0, int target=0, double cost=0):
  source(source),target(target),cost(cost){}
  bool operator < (const Edge &e) const{
    return cost<e.cost;
  }
};
  
double kruskal(int N,vector<Edge> edges){
  double totalCost=0;
  sort(ALL(edges));
  
  Dis dset=Dis(N+1);
  
  int source,target;
  rep(i,edges.size()){
    Edge e=edges[i];
    if(!dset.same(e.source,e.target)){
      totalCost+=e.cost;
      dset.unite(e.source,e.target);
    }
  }
  return totalCost;
} 

int main() {
  int n;
  while(cin>>n){
    if(n==0) return 0;
    
    vector<double> x(n),y(n),z(n),r(n);
    rep(i,n) cin>>x[i]>>y[i]>>z[i]>>r[i];
  
    vector<Edge> edges;
    rep(i,n){
      rep(j,n){
        if(j<=i) continue;
        edges.push_back(Edge(i,j,max(0.0,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+
                                     (z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j])));
      }
    }
  
    cout<<fixed<<setprecision(3)<<kruskal(n,edges)<<endl;
    
  }
  return 0;
}


Measured memory_bytes: 3320
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}


int main(){
  int Q; cin >> Q;
  auto table = prime_table(100005);
  vector<int> tab(100005,0);
  int cnt = 0;
  rep(i,100005){
    if (table[i] && table[(i+1)/2]) cnt++;
    tab[i] = cnt;
  }

  rep(q,Q){
    int l, r;
    cin >> l >> r;
    cout << tab[r+1]-tab[l-1] << endl;
  }


  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3752
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <list>

#include <random>
using namespace std;

int main(void) {
	int N, t;
	const int BUCKET_MAX = 100000;
	scanf("%d", &N);
	vector<int> a = vector<int>(BUCKET_MAX+1, 0);

	for (int i = 0; i < N; i++) {
		scanf("%d", &t);
		a[t]+=1;
	}

	int max = -1;
	for (int i = 0; i < BUCKET_MAX+1; i++) {
		int sum = 0;
		for (int k = i; k < i + 3; k++) {
			if (k <= BUCKET_MAX) {
				sum += a[k];
			}
		}
		if (sum > max) {
			max = sum;
		}
	}
	printf("%d\n", max);

	return 0;
}

Measured memory_bytes: 640