akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void func(ll beg, ll end, vector<ll> &v,ll sta, ll fin, ll &val, ll ind)
{
	if(beg==sta && end==fin)
	{
		val=max(val, v[ind]);return;
	}
	ll mid=(beg+end)/2;
	if(fin<=mid)
	{
		func(beg,mid,v,sta,fin, val, 2*ind);
		return ;
	}
	if(beg>mid)
	{
		func(mid+1, end, v, sta, fin, val, 2*ind +1);
		return ;
	}
		
		func(beg, mid, v, sta, mid, val, 2*ind);
		func(mid+1, end, v, mid+1, fin, val, 2*ind+1);
}

void func1(ll beg, ll end, vector<ll> &v, ll hei, ll &val, ll ind)
{
	if(beg==end)
	{
		if(hei!=beg)
		return; 
		v[ind]=max(v[ind],val);
		return ;
	}
	ll mid=(beg + end)/2;
	if(hei>=beg && hei<=end)
	{
		v[ind]=max(val, v[ind]);
		func1(beg, mid, v, hei, val, 2*ind);
		func1(mid+1, end, v, hei, val, 2*ind + 1);
	}
	else return ;
}
int main()
{
	int n;
	cin>>n;
	vector<ll> a(n),h(n);
	ll ma=0;
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
		ma=max(ma,h[i]);
	}
	for(int i=0;i<n;i++)
	cin>>a[i];
	
	vector<ll> v(4*ma + 2,0);
	//cout<<ma;
	for(int i=0;i<n;i++)
	{
		ll val=0;
		func(0,ma, v, 0, h[i]-1, val, 1);
		//for(int i=0;i<v.size();i++)
		//cout<<v[i]<<" ";
		//cout<<"*";
		//cout<<val<<" ";
		//for(int i=0;i<v.size();i++)
	//cout<<v[i]<<" ";
	//cout<<endl;
		
		val=val+a[i];
		func1(0,ma, v, h[i], val,1);
	}
	cout<<v[1];
	return 0;
}


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

using namespace std;

#define ll long long
#define ld long double
#define pll pair <ll , ll>

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair

#define X first
#define Y second

#define LB(x) ((x) & -(x))
#define BIT(a , b) (((a)>>(b)) & 1)

const ll maxn = 2e3 + 10;

vector <ll> vertex[maxn];

ll dfs(ll v , ll k , ll p)
{
    if (k < 0) return 0;
    if (k == 0) return 1;

    ll sum = 1;
    for (ll i = 0; i < vertex[v].size(); i++)
    {
        if (vertex[v][i] != p)
        {
            sum += dfs(vertex[v][i] , k - 1 , v);
        }
    }

    return sum;
}

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

	ll n , k , ans = 0;
	cin >> n >> k;

	for (ll i = 0; i < (n - 1); i++)
    {
        ll v , u;
        cin >> v >> u;

        vertex[v].pb(u);
        vertex[u].pb(v);
    }

	for (ll i = 1; i <= n; i++)
    {
        ll res = 1 , w = 0;
        for (ll j = 0; j < vertex[i].size(); j++)
        {
            ll x = dfs(vertex[i][j] , (k / 2) - 1 , i);
            if (k & 1) w = max(w , dfs(vertex[i][j] , (k / 2) , i) - x);
            res += x;
        }
        res += w;
        ans = max(ans , res);
    }

    cout << n - ans;
}

/*
10 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
*/


Measured memory_bytes: 3784
#include<cstdio>
char c1,c2,c;
int l=0;
int main()
{
	while(~scanf("%c",&c))
	{
		l++;
		if(c1==c)
		{
			printf("%d %d",l-1,l);
			return 0;
		}
		if(c2==c)
		{
			printf("%d %d",l-2,l);
			return 0;
		}
		c2=c1; c1=c;
	}
	puts("-1 -1");
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define at(x,i) get<i>(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n,x,y;cin >> n >> x >>y;x--;y--;
    vvl g(n);
    rep(i,n-1){
        g[i].pb(i+1);
        g[i+1].pb(i);
    }
    g[x].pb(y);
    g[y].pb(x);
    vl ans(n-1,0);
    rep(i,n){
        queue<ll> que;
        que.push(i);
        vl dist(n,-1);
        dist[i]=0;
        while(!que.empty()){
            ll v=que.front();
            que.pop();
            for(auto nv:g[v]){
                if(dist[nv]!=-1)continue;
                dist[nv]=dist[v]+1;
                ans[dist[nv]-1]++;
                que.push(nv);
            }
        }
    }
    rep(i,n-1){
        cout <<ans[i]/2 <<endl;
    }
}

Measured memory_bytes: 384
list=input().split(" ")
x=int(list[0])
y=int(list[1])

sum=0

if x>y:
    sum+=x
    x-=1
else:
    sum+=y
    y-=1

if x>y:
    sum+=x
    x-=1
else:
    sum+=y
    y-=1

print(sum)

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int f[n+1]={}, b[n+1]={};
  for(int i=1; i<=n; i++){
    if(s[i-1]=='W') f[i] = f[i-1] + 1;
    else f[i] = f[i-1];
    
    if(s[n-i]=='E') b[n-i] = b[n-i+1] + 1;
    else b[n-i] = b[n-i+1];
  }
  int ans = n;
  for(int i=0; i<n; i++){
    ans = min(ans, f[i]+b[i+1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int main() {

 int a,b,c;
 cin >> a >> b >> c;
 
 if (a < b && b< c && a != b && b !=c) {
 cout << "Yes" << endl;
 }

 else {
 cout << "No" << endl;
 }
}

 
 



Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  //ios::sync_with_stdio(false);
  while(1){
    int n;
    cin>>n;
    if(n==0) break;
    queue<pair<pair<int,int>,int > > a,b;
    priority_queue<pair<pair<int,int>,int > > c;
    queue<pair<pair<int,int>,int > > d;
    pair<int,int> p[n];
    pair<pair<int,int>,int > pr;
    int ans=0;
    rep(i,n) cin>>p[i].fst>>p[i].scd;
    sort(p,p+n);
    rep(i,n) a.push(make_pair(p[i],p[i].fst));
    while(!a.empty() || !b.empty() ){
      /* rep(i,a.size() ){
	pr=a.front();
	cout<<pr.fst<<" ";
	a.pop();
	a.push(pr);
      }
      cout<<endl;*/
      pair<pair<int,int>,int >at,bt;
      at=bt=make_pair(make_pair(0,0),INF);
      if(!a.empty() ) at=a.front();
      if(!b.empty() ) bt=b.front();
      if(at.scd<=bt.scd){
	while(!a.empty() && a.front().scd<=at.scd){
	  pr=a.front();
	  a.pop();
	  
	  pr.scd=(pr.fst.fst+at.scd);
	  pr.fst.fst*=(-1);
	  c.push(pr);
	  
	}
	while(!c.empty() ){
	  pr=c.top();
	  pr.fst.fst*=(-1);
	  b.push(pr );
	  c.pop();
	}

      }else{
	while(!b.empty() && b.front().scd<=bt.scd){
	  pr=b.front();
	  b.pop();
	  
	  pr.fst.scd--;
	  if(pr.fst.scd!=0){
	    pr.scd=(pr.fst.fst+bt.scd);
	    pr.fst.fst*=(-1);
	    c.push(pr);
	  }else{
	    ans=max(ans,bt.scd);
	  }
	  
	}
	while(!c.empty() ){
	  pr=c.top();
	  pr.fst.fst*=(-1);
	  a.push(pr );
	  c.pop();
	}

      }
    }
    cout<<ans<<endl;
  }
 

  return 0;
}



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

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, int> pli;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 1010;
int N;
int X[MN], Y[MN];

int main() {
	cin >> N;
	int st = -1;
	bool ok = 1;

	rep(i, N) {
		cin >> X[i] >> Y[i];
		int t = abs(X[i] + Y[i]) % 2;
		if (st == -1) {
			st = t;
		} else {
			if (st != t) {
				ok = 0;
			}
		}
	}

	if (!ok) {
		puts("-1");
		return 0;
	}

	vector<ll> vec;

	rep(i, 31) vec.eb(1LL << i);
	if (!st) vec.eb(1);

	vector<string> ans(N);

	rep(i, N) {
		if (!st) {
			++X[i];
			ans[i].pb('L');
		}

		ll p = X[i] + Y[i], q = X[i] - Y[i];

		for (int j = 30; j >= 0; --j) {
			int dec = (1 << j);
			if (p >= 0 && q >= 0) {
				p -= dec; q -= dec; ans[i].pb('R');
			} else if (p >= 0 && q < 0) {
				p -= dec; q += dec; ans[i].pb('U');
			} else if (p < 0 && q > 0) {
				p += dec; q -= dec; ans[i].pb('D');
			} else {
				p += dec; q += dec; ans[i].pb('L');
			}
		} 

		reverse(ALL(ans[i]));
	}

	int sz = vec.size();
	cout << sz << endl;
	rep(i, sz) {
		cout << vec[i] << (i == sz - 1 ? '\n' : ' ');
	}

	rep(i, N) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
	int main()
{
	int a=0,b,c,n,i,j;
	char s[200000],d[5];
	scanf("%s",s);
	for(b=0;s[b]!='\0';b++);
	for(i=0;i<b;i++){
		d[0]=s[i];
		c=atoi(d);
		a+=c;
	}
	if(a%9==0){
		printf("Yes");
	}
	else{
		printf("No");
	}
	return 0;
}

Measured memory_bytes: 1932
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main(){
    int a, b, c, d, k;
    cin >> a >> b >> c >> d >> k;
    if(a<=c&&b<=d){
        cout << ((c-a)*60+(d-b))-k << endl;
    }
    else if(a<=c&&b>d){
        cout << (c-a-1)*60+60-(b-d)-k << endl;
    }
    return 0;
}

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

int main(){
    int A,B;
    string S;
    cin >> A >> B >> S;
    for(int i = 0; i < A+B+1; i++) {
        if(i != A) {
            if(S[i] != '-') {
                continue;
            }
            else {
                cout << "No" << endl;
                return 0;
            }
        } 
        else {
            if(S[i] != '-') {
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    unsigned int n;
    cin>>n;
    unsigned int array[n];
    for(int i=0;i<n;++i){
        cin>>array[i];
    }
    cout<<array[n-1];
    for(int i=1;i<n;++i){
        cout<<" "<<array[n-i-1];
    }
    cout<<endl;
}



Measured memory_bytes: 3100
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    
    System.out.println(n%1000 == 0?0:1000-n%1000);
  }
}


Measured memory_bytes: 27060
#include <iostream>
using namespace std;
int main(){
  
  char c[2][3];
  for(int i=0;i<2;i++)
    for(int k=0;k<3;k++)
    cin >> c[i][k];
  
  for(int i=0;i<2;i++){
    for(int k=0;k<3;k++){
      if(c[i][k]!=c[1-i][2-k]){
        cout << "NO" <<endl;
        return 0;
      }
    }
  }
  cout << "YES" <<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define Maxn 400007
#define eps 1e-7
using namespace std;
int n;
int p[Maxn],fa[Maxn];
int cnt[2][Maxn];
struct node
{
	int cnt0,cnt1,id;
	bool operator < (const node &a) const
	{
		return 1LL*cnt0*a.cnt1<1LL*cnt1*a.cnt0;
	}
};
priority_queue<node> que;
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		scanf("%d",&p[i]);
	for (int i=1;i<=n;i++)
	{
		int val;
		scanf("%d",&val);
		++cnt[val][i];
		fa[i]=i;
	}
	long long ans=0;
	for (int i=2;i<=n;i++)
		que.push((node){cnt[0][i],cnt[1][i],i});
	while (!que.empty())
	{
		node now=que.top();
		que.pop();
		int pos=now.id;
		if (cnt[0][pos]==now.cnt0&&cnt[1][pos]==now.cnt1)
		{
			int new_pos=fa[pos]=find(p[pos]);
			ans+=1LL*cnt[0][pos]*cnt[1][new_pos];
			cnt[0][new_pos]+=cnt[0][pos];
			cnt[1][new_pos]+=cnt[1][pos];
			if (new_pos!=1) que.push((node){cnt[0][new_pos],cnt[1][new_pos],new_pos});
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 10356
use std::vec::Vec;

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()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    assert_eq!(v.len(), 2);
    (v[0], v[1])
}

fn main() {
    let (n, m) = read_touple::<usize>();
    let mut a = vec![];
    let mut b = vec![];
    for _ in 0..n {
        let t: Vec<char> = read::<String>().chars().collect();
        a.push(t);
    }

    for _ in 0..m {
        let t: Vec<char> = read::<String>().chars().collect();
        b.push(t);
    }

    for i in 0..n - m + 1 {
        for j in 0..n - m + 1 {
            if check(&a, &b, i, j) {
                println!("Yes");
                return;
            }
        }
    }

    println!("No");
}

fn check(a: &Vec<Vec<char>>, b: &Vec<Vec<char>>, i: usize, j: usize) -> bool {
    let m = b.len();

    for k in 0..m {
        for l in 0..m {
            if a[i + k][j + l] != b[k][l] {
                return false;
            }
        }
    }

    true
}


Measured memory_bytes: 4352
#include<stdio.h>
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a>b){
        printf("a > b\n");
    }else if(a<b){
        printf("a < b\n");
    }else{
        printf("a == b\n");
    }
    return 0;
}

Measured memory_bytes: 580
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		int p;
		p = r - l + 1;
		count += p;
	}
	cout << count<< endl;
	

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define FILL(a, b) memset(a, b, sizeof(a))

void dout() { cerr << endl; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int ans = 0;
    FOR(i, 1, n)
    {
        for (int j = i; j < n; j += i)
        {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int H,W;
  cin >> H >> W;
  char a[H][W];
  bool s[H];
  bool t[W];
  for (int i = 0; i < H; i++) s[i] = true;
  for (int j = 0; j < W; j++) t[j] = true;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> a[i][j];
      if (a[i][j] == '#') {
        s[i] = false;
        t[j] = false;
      }
    }
  }
  for (int i = 0; i < H; i++) {
    if (s[i]) {
      continue;
    }
    for (int j = 0; j < W; j++) {
      if (!t[j]) {
        cout << a[i][j];
      }
    }
    cout << endl;
  } 
  return 0;
}

Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const long long INF = (long long)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    ll A, B, Q;
    cin >> A >> B >> Q;
    vector<ll> s(A), t(B);
    rep(i, A) cin >> s[i];
    rep(i, B) cin >> t[i];
    s.push_back(INF); s.push_back(-INF); sort(s.begin(), s.end());
    t.push_back(INF); t.push_back(-INF); sort(t.begin(), t.end());

    rep(k, Q){
        ll x;
        cin >> x;
        ll res = INF;

        rep(i, 2){
            ll first;
            if(i == 0) first = s[upper_bound(all(s), x) - s.begin() - 1];
            else first = s[lower_bound(all(s), x) - s.begin()];

            rep(j, 2){
                ll second;
                if(j == 0) second = t[upper_bound(all(t), x) - t.begin() - 1];
                else second = t[lower_bound(all(t), x) - t.begin()];
                res = min(res, abs(x-first) + abs(first-second));
            }
        }
        rep(i, 2){
            ll first;
            if(i == 0) first = t[upper_bound(all(t), x) - t.begin() - 1];
            else first = t[lower_bound(all(t), x) - t.begin()];

            rep(j, 2){
                ll second;
                if(j == 0) second = s[upper_bound(all(s), x) - s.begin() - 1];
                else second = s[lower_bound(all(s), x) - s.begin()];
                res = min(res, abs(x-first) + abs(first-second));
            }
        }
        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 2912
/*  ex4-3
    Rikuta  */

#include <stdio.h>

//プロトタイプ宣言
int snow_height(int west_remain_height,int east_remain_height){
    //snow_heightの計算
    int snow_height=(east_remain_height-west_remain_height-1)*(east_remain_height-west_remain_height)/2-west_remain_height;

    //snow_heightを返す
    return snow_height;
}

int main(void){

    int west_remain_height,east_remain_height;

    //入力受け取り
    scanf("%d %d",&west_remain_height,&east_remain_height);

    //snow_height関数に入れて計算
    int ans =snow_height(west_remain_height,east_remain_height);

    //答えの出力
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 128
/*
Task:
Author: John_05
State: Unknown
Lang: C++
Solution:
*/
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9+10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair

int read() {
	int xx=0,ww=1;
	char ch=getchar();
	while(ch>'9'||ch<'0') {
		if(ch=='-') ww=-ww;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		xx=10*xx+ch-48;
		ch=getchar();
	}
	return xx*ww;
}

string str;
int s;

int main() {
	cin>>str;
	for(int i=0; i<str.length(); i++) {
		int cnt=0;
		for(int j=i; j<str.length(); j++)
			if(str[j]=='A'||str[j]=='T'||str[j]=='G'||str[j]=='C') cnt++;
			else break;
		s=max(s,cnt);
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
/*input

*/


//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define pb          push_back
#define pii         pair<ll int,ll int>
#define vpii        vector< pii >
#define vi          vector<ll int>
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define repr(i,a,b) for(ll int i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 305;
ll n,m,l;
vector< vpii > adj(N,vpii ());
vvi ansf(N,vi (N));


vi dikstra(ll s)
{
	vpii dist(n,mp(inf,inf));
	vi vis(n,0);

	dist[s] = mp(0,0);
	priority_queue< pair< pii,ll > ,vector< pair< pii,ll > >,greater< pair< pii,ll > > > q;
	q.push(mp(dist[s],s));
	while(!q.empty())
	{
		ll u = q.top().S;
		q.pop();


		if(vis[u]==1) continue;

		vis[u]=1;
		ll used = dist[u].S;
		rep(i,0,sz(adj[u]))
		{
			if(vis[adj[u][i].F]==1) continue;

			ll v = adj[u][i].F;
			ll d = adj[u][i].S;

			
			ll req_chan = dist[u].F;
			ll total = used+d;
			if(total>l) req_chan++,total = d; 
			pii cur = mp(req_chan,total);
			if(cur<dist[v])
			{
				dist[v]=cur;	
				q.push(mp(dist[v],v));
			}
		}
	}

	vi ans(n);
	rep(i,0,n) ans[i]=(dist[i].F==inf?-1:dist[i].F);
	return ans;
}

int solve()
{
	cin>>n>>m>>l;
	rep(i,0,m)
	{
		ll x,y,d;
		cin>>x>>y>>d;
		if(d<=l)
		{
			x--,y--;
			adj[x].pb(mp(y,d));
			adj[y].pb(mp(x,d));

		}
	}

	rep(i,0,n) ansf[i] = dikstra(i);
	// ansf[0] = dikstra(0);

	ll q;cin>>q;
	while(q--)
	{
		ll x,y;cin>>x>>y;
		x--,y--;
		cout<<ansf[x][y]<<"\n";
	}
	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	//cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 4976
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

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

  int r;
  cin >> r;

  cout << (3 * (r * r)) << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

bc = sorted(bc, key=lambda x: x[1], reverse=True)
# print(bc)

heapq.heapify(a)
for b, c in bc:
    for i in range(b):
        num = heapq.heappop(a)
        if num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, num)
            break
# print(a)
print(sum(a))


Measured memory_bytes: 33744
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N, M;
    cin >> N >> M;
    priority_queue<int> _Items;
    FOR(i, 0, N) {
        int item;
        cin >> item;
        _Items.push(item);
    }

    while (M-- && !_Items.empty()) {
        int biggest = _Items.top();
        _Items.pop();

        if (biggest == 0)
            break;
        _Items.push(biggest / 2);
    }

    lint ret = 0;
    FOR(i, 0, N) {
        ret += _Items.top();
        _Items.pop();
    }

    cout << ret << endl;
    return 0;
};


Measured memory_bytes: 892
def doc_string():
	"""
	I can fly.
	"""

encode = {
        "A":"00000",
        "B":"00001",
        "C":"00010",
        "D":"00011",
        "E":"00100",
        "F":"00101",
        "G":"00110",
        "H":"00111",
        "I":"01000",
        "J":"01001",
        "K":"01010",
        "L":"01011",
        "M":"01100",
        "N":"01101",
        "O":"01110",
        "P":"01111",
        "Q":"10000",
        "R":"10001",
        "S":"10010",
        "T":"10011",
        "U":"10100",
        "V":"10101",
        "W":"10110",
        "X":"10111", 
        "Y":"11000",
        "Z":"11001",
        " ":"11010",
        ".":"11011",
        ",":"11100",
        "-":"11101",
        "'":"11110",
        "?":"11111"}
decode = {
        "101":" ",
        "000000":"'",
        "000011":",",
        "10010001":"-",
        "010001":".",
        "000001":"?",
        "100101":"A",
        "10011010":"B",
        "0101":"C",
        "0001":"D",
        "110":"E",
        "01001":"F",
        "10011011":"G",
        "010000":"H",
        "0111":"I",
        "10011000":"J",
        "0110":"K",
        "00100":"L",
        "10011001":"M",
        "10011110":"N",
        "00101":"O",
        "111":"P",
        "10011111":"Q",
        "1000":"R",
        "00110":"S",
        "00111":"T",
        "10011100":"U",
        "10011101":"V",
        "000010":"W",
        "10010010":"X",
        "10010011":"Y",
        "10010000":"Z"}

while True:
	try:
		code = raw_input()
	except EOFError:
		break
	code0 = ""
	for var in code:
		code0 += encode[var]

	code = ""
	temp = ""
	for var in code0:
		temp += var
		if temp in decode:
			code += decode[temp]
			temp = ""
		
	print code
	

Measured memory_bytes: 6280
#include<bits/stdc++.h>
#define ll long long int
#define inf 1000000000000
#define MOD 1000000007
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define for0(i, n) for (int i = 0; i < n; i++)
#define tc(t) int t; cin >> t; while (t--)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ps(x,y)         fixed<<setprecision(y)<<x
using namespace std;
int main()
{
	IOS
/*#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif*/
	int n;
	cin >> n;
	ll arr[n];
	ll dp[n][n];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int l = n - 1; l >= 0; l--)
	{
		for (int r = l; r < n; r++)
		{
			if (r == l)
				dp[l][r] = arr[l];
			else
				dp[l][r] = max(arr[l] - dp[l + 1][r], arr[r] - dp[l][r - 1]);
		}
	}
	cout << dp[0][n - 1] << endl;
}

Measured memory_bytes: 70144
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include<iostream>
#include<cmath>

int main() {
	while(true){
		int n, q; std::cin >> n >> q; if (n == 0 && q == 0) break;
		std::vector<std::vector<int>> children(n);
		std::vector<int> parent(n, -1), marked_ancestor(n, 0);
		for (auto i = 1; i < n; ++i) {
			int a; std::cin >> a;
			parent[i] = marked_ancestor[i] = --a;
			children[a].push_back(i);
		}
		std::vector<std::pair<bool, int>> queries;
		for (auto i = 0; i < q; ++i) {
			int node;
			std::string str; std::cin >> str >> node; --node;
			if (str == "M") {
				if (marked_ancestor[node] != node && node != 0) {
					marked_ancestor[node] = node;
					queries.emplace_back(false, node);
				}
			}
			else {
				queries.emplace_back(true, node);
			}
		}
		std::reverse(queries.begin(), queries.end());
		long long int result = 0;
		for (const auto p : queries) {
			if (p.first) {
				int current = p.second;
				while (marked_ancestor[current] != current) {
					current = marked_ancestor[current];
				}
				const auto root = current;
				current = p.second;
				while (current != root) {
					auto temp = current;
					current = marked_ancestor[current];
					marked_ancestor[temp] = root;
				}
				result += root + 1;
			}
			else {
				marked_ancestor[p.second] = parent[p.second];
			}
		}
		std::cout << result << '\n';
	}
}


Measured memory_bytes: 10840
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,d;
    cin >> n >> d;
    int ans = 0;
    while(n--){
        double a,b;
        cin >> a >> b;
        double res = sqrt((a*a)+(b*b));
        if(res<=d){
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3832
#include "bits/stdc++.h"

#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)        cerr<<#a<<" : "<<a<<endl
#else
#define tr(a)    
#endif
#define int         long long
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)    for(int i=a;i<b;i++)
using namespace std;

bool vis[100005];
ll pos[100005];
ll maxa,mina;
vector<pair<int,ll>>adj[100005];
bool good=1;
void dfs(int u,int curpos){
    if(vis[u]){
        if(curpos!=pos[u])good=0;
        return;
    }
    maxa=max(maxa,curpos);
    mina=min(mina,curpos);
    vis[u]=1;
    pos[u]=curpos;
    for(auto i:adj[u]){
        dfs(i.F,i.S+curpos);
    }
}
void solve(){
    memset(pos,1,sizeof pos);
    int N,M;
    cin>>N>>M;
    rep(i,0,M){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,-c});
    }
    rep(i,1,N+1){
        if(vis[i])continue;
        maxa=LLONG_MIN;
        mina=LLONG_MAX;
        dfs(i,0);
        if(maxa-mina>1000000000 or !good){
            cout<<"No";
            return;
        }
    }
    cout<<"Yes";
}

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

Measured memory_bytes: 15616
// eddy1021
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

vector<string> v;
int main()
{
string s;
int k;
cin>>s>>k;

for(int i=0; i<s.size(); i++)
for(int j=1; j<=5; j++)
    v.push_back(s.substr(i, j));

sort(v.begin(), v.end());
unique(v.begin(), v.end())-v.begin();
cout<<v[k-1]<<endl;

system("pause");
return 0;
}

Measured memory_bytes: 1908
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int m;
    cin >> m;
    vector<int> D(m);
    vector<long long> C(m);
    for (int i = 0; i < m; ++i) {
        cin >> D[i] >> C[i];
    }


    long long res = 0;
    long long sum = 0;
    for (auto x : C) {
        res += x;
    }
    --res;
    for (int i = 0; i < m; ++i) {
        sum += D[i] * C[i];
    }
    res += (sum - 9 + 8) / 9;
    
    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 2560
#include<iostream>
using namespace std;
int main() {
    
    int n,m,l;
    
    cin >> n >> m >> l;
    
    int A[100][100] = {{0}};
    int B[100][100] = {{0}};
    long long C[100][100] = {{0}};
    
    for (int i = 0; i < n; i ++) {
        
        for (int j = 0; j < m; j ++) {
            
            cin >> A[i][j];
            
        }
    }
    
    for (int i = 0; i < m; i ++) {
        
        for (int j = 0; j < l; j ++) {
            
            cin >> B[i][j];
            
        }
    }
    
    for (int i = 0; i < n; i ++) {
        
        for (int j = 0; j < m; j ++) {
            
            for (int k = 0; k < l; k ++) {
                
                C[i][k] += A[i][j] * B[j][k];
                
                
            }
            
        }
    }
    
    for (int i = 0; i < n; i ++) {
        
        for (int j = 0; j < l; j ++) {
            
            if (j == l-1) {
                
                cout << C[i][j] << endl;
                
            } else {
                
                cout << C[i][j] << ' ';
            
            }
            
            
        }
    }
    
    
    
    return 0;
    
    
}


Measured memory_bytes: 3260
// {{{
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <complex>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); i++)
#define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); i--)
#define REP(i, n) for(ll i = 0ll; i < static_cast<ll>(n); i++)
#define REPR(i, n) for(ll i = static_cast<ll>(n); i >= 0ll; i--)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> IP;
typedef pair<ll, LP> LLP;

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

constexpr int INF = 100000000;
constexpr ll LINF = 10000000000000000ll;
constexpr int MOD = static_cast<int>(1e9 + 7);
constexpr double EPS = 1e-9;

static inline ll mod(ll x, ll m)
{
    ll y = x % m;
    return (y >= 0 ? y : y+m);
}

// }}}

int N, K;
int r, s, p;
string t;
ll dp[100010];
bool lose[100010];

void solve()
{
    map<char, int> m = { {'s', r}, {'p', s}, {'r', p} };
    dp[0] = 0;
    REP (i, N) {
        dp[i+1] = dp[i];
        if (i < K || t[i] != t[i-K] || lose[i-K]) {
            dp[i+1] += m[t[i]];
        } else {
            lose[i] = true;
        }
    }
    cout << dp[N] << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K >> r >> s >> p;
    cin >> t;
    solve();
    return 0;
}

// vim:set foldmethod=marker:


Measured memory_bytes: 1360
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
using namespace std;
#include <vector>
#define rep(i,n) for (int i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define ll long long
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

/*
#include <math.h>
int standerd = int(pow(10.0,9.0)) + 7;
*/
string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

ll A[2000000];
ll B[2000000]={};
ll C;
ll N;
ll M;
ll K;

int main(){

    cin >> N;
    cin >> K;

    rep(ni,N){
        cin >> A[ni];
        A[ni]--;

    }
    ll cnt=0;

    ll now = 0;
    ll flag = 0;
    while(cnt<K){
        ll next = A[now];
        if(flag==0){
            if(B[next]==0){
                cnt++;
                B[next]=cnt;
            }else{
                cnt++;
                ll base =cnt - B[next];
                //cout << base << endl;

                cnt = (K-B[next])/base * base;
                cnt += B[next];
                while(cnt>K) cnt-=base;
                flag=1;
            }
        }else{
            cnt++;
        }
        //cout << cnt << endl;
        now=next;
    }
    cout << now+1 << endl;

}

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

int main(){
  vector<int> a(9);
  for(int i=0;i<9;i++){
    cin >> a.at(i);
  }
  int n;
  cin >> n;
  vector<int> b(n);
  for(int i=0;i<n;i++){
    cin >> b.at(i);
  }
  vector<bool> c(9,false);
  for(int i=0;i<n;i++){
    for(int j=0;j<9;j++){
      if(b.at(i)==a.at(j)){
        c.at(j)=true;
      }
    }
  }
  if((c.at(0)==true&&c.at(1)==true&&c.at(2)==true)||
     (c.at(3)==true&&c.at(4)==true&&c.at(5)==true)||
     (c.at(6)==true&&c.at(7)==true&&c.at(8)==true)||
     (c.at(0)==true&&c.at(3)==true&&c.at(6)==true)||
     (c.at(1)==true&&c.at(4)==true&&c.at(7)==true)||
     (c.at(2)==true&&c.at(5)==true&&c.at(8)==true)||
     (c.at(0)==true&&c.at(4)==true&&c.at(8)==true)||
     (c.at(2)==true&&c.at(4)==true&&c.at(6)==true)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
const int maxn=0x7f7f7f7f;
 
int main()
{
 int n,i,m,sum,a;
 scanf("%d",&n);
 sum=0;m=-maxn;
 for (i=1;i<=n;i++){
  scanf("%d",&a);
  if (a>m) m=a;
  sum+=a;
 }
 printf("%d\n",sum-m/2);
 return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <iostream>

using namespace std;

const int N_MAX = 1e5 + 5;

int tot[N_MAX];
bool prime[N_MAX];

int main() {
    int Q;

    cin >> Q;

    tot[0] = 0;
    for (int i = 1; i < N_MAX; i++) {
        bool p = true;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                p = false;
            }
        }

        if (p) prime[i] = true;

        tot[i] = tot[i - 1];
        if (i > 2 && prime[i] && prime[(i + 1) / 2]) {
            tot[i]++;
        }
    }

    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;

        // cout << "r: " << tot[r] << ", l: " << tot[l] << endl;
        cout << tot[r] - tot[l - 1] << endl;
    }
}

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

/* define const */

/* finish defineing const */

long x;

vector<long> v;

long make_t(long x)
{
    long i = 1;
    long tmp = 0;
    do
    {
        tmp += i;
        i++;
        v.push_back(tmp);
    } while (tmp < x);

    return --i;
}

int main()
{
    cin >> x;

    long f = make_t(x);
    long i;

    /*
    if (v[i] == x)
    {
        cout << i << endl;
        exit(0);
    }

    long sub = v[f] - x;

    for (int i = 0; i < f; i++)
    {
        if (v[i] == sub)
        {
            cout << f << endl;
        }
    }
    */
    cout << f << endl;
}


Measured memory_bytes: 892
import sys
readline = sys.stdin.readline
N, M = map(int, input().split())
ab = [tuple(map(int, readline().split())) for _ in range(M)]
class UnionFind:
    def __init__(self, size):
        self.rank = [-1] * (size + 1)
        self.number = [1] * (size + 1)
    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
uf = UnionFind(N)
p = N * (N - 1) // 2
ans = [p]
for x, y in reversed(ab[1:]):
    px = uf.find(x)
    py = uf.find(y)
    if px != py:
        p -= uf.number[px] * uf.number[py]
        uf.union(px, py)
    ans.append(p)
print(*ans[::-1], sep="\n")


Measured memory_bytes: 25460
#include <cassert>
#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <cstdint>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
 
#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;
  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0))return 0;
  long long x = 1;
  while (b > 0) {
    if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a;
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

const long long MOD = 998244353;
// const long long MOD = 1e9 + 7;

using ll = long long;
using P=std::pair<long long,long long>;

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

  ll a,p;
  std::cin>>a>>p;

  std::cout<<(3*a+p)/2<<"\n";

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
      	int[] t = new int[n];
      	for (int i = 0; i < n; i++) {
        	t[i] = Integer.parseInt(sc.next());
        }
      	int m = Integer.parseInt(sc.next());
		for (int i = 0; i < m; i++) {
          	int cnt = 0;
        	int p = Integer.parseInt(sc.next());
          	int x = Integer.parseInt(sc.next());
			for (int j = 0; j < n; j++) {
            	if (p == j + 1) {
                	cnt += x;
                } else {
                	cnt += t[j];
                }
            }
          	System.out.println(cnt);
        }
    }
}


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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const long long INF = 2e18;
const long long MOD = 1e9+7;

#define sx(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i < n; i++)
#define ALL(a) begin(a),end(a)

int main(void) {
    ll N,M;
    cin >> N >> M;
    ll ans = 0;
    ans = (N-2) * (M-2);
    if (N==1 && M==1) ans = 1;
    else if (min(N, M) == 1) {
        ans = max(N, M) -2;
    }
    cout  << ans << endl;
    return 0;
}

Measured memory_bytes: 384
/* Just_Do_It ___________ICARUS__________________*/
                     
    #include <bits/stdc++.h>
    using namespace std;
           
    typedef long long ll;
    #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #define rep(i,a,n) for(ll i=a;i<n;i++)
    #define per(i,n,a) for (ll i=n;i>a;i--)
    #define te ll t; std::cin >> t; while(t--)
    #define SZ 100001
    //# define M_PIl  3.141592653589793238462643383279502884L 
    /*   Proceed with CAUTION   */
   
    int main(){
        fastio;
        ll n,k,cnt=0;
        cin>>n>>k;
        ll a[n];
        rep(i,0,n) cin>>a[i];
        sort(a,a+n);
        rep(i,0,n){
        	if(k>=a[i]) {
        		k-=a[i];
        		if(i!=n-1) cnt++;
        		if(i==n-1 && k==0) cnt++;
        	}
        	else break;
        }cout<<cnt<<endl;
        }


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

#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(),(x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ll n;
    cin >> n;
    
    vector<ll> v(n);
    
    for (ll i = 0; i < n; i++) {
    	cin >> v[i];
    }
    
    sort(v.begin(), v.end(), greater<>());
    
    ll before = v[0];
    ll one, two = 0;
    
    for (ll i = 1; i < n; i++) {
    	if (v[i] == before) {
    		if (one == 0) {
    			one = v[i];
    			before = 0;
    		} else {
    			two = v[i];
    			break;
    		}
    	} else {
    		before = v[i];
    	}
    }
    
    cout << one * two << endl;
    
    return 0;
}

Measured memory_bytes: 1024
{-# LANGUAGE OverloadedStrings #-}
module Main where

import           Data.List
import           Control.Monad
import           Debug.Trace
import qualified Data.ByteString.Char8         as BC
import           Data.Maybe                     ( fromJust )
import qualified Data.Set                      as S
import qualified Data.IntMap.Strict            as IM
import           Data.Char


readTuple2 :: IO (Int, Int)
readTuple2 = do
    [a, b] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b)

readTuple3 :: IO (Int, Int, Int)
readTuple3 = do
    [a, b, c] <- map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine
    return (a, b, c)

readInt :: IO Int
readInt = fst . fromJust . BC.readInt <$> BC.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

split :: (a -> Bool) -> [a] -> [[a]]
split f [] = []
split f as =
    let (fo, la) = span f as
        las      = case la of
            [] -> []
            xs -> split f $ tail xs
    in  case fo of
            [] -> las
            xs -> xs : las

distance :: Int -> Int -> Int -> Int
distance k from to =
        if from > to then to + k - from
        else to - from

solve :: Int -> Int -> [Int] -> Int
solve n k hs = let
    heightList = IM.fromList $ zip [1..] hs
    ansList = IM.fromList [(1, 0), (2, abs (heightList IM.! 2 - heightList IM.! 1))]
    getPoint to from m = case IM.lookup from m of
        Nothing -> maxBound
        Just p -> p + abs (heightList IM.! from - heightList IM.! to)
    getAns h m = minimum $ fmap (\from -> getPoint h from m) [h - k..h - 1]
    ansList' = foldl' (\b a -> IM.insert a (getAns a b) b) ansList [3..n]
    in
    ansList' IM.! n
    

main = do
    (n, k) <- readTuple2
    hs <- readInts
    print $ solve n k hs





Measured memory_bytes: 23292