akhauriyash/Code-Regression huggingface dataset:
import math
A, B, H, M = list(map(int, input().split()))


timePassed = 60 * H + M #min

omega_a = 2*math.pi/(12*60) #rad/min
omega_b = 2*math.pi/(60) #rad/min

theta = omega_a * timePassed - omega_b*timePassed

if theta > math.pi:
    theta = 2 * math.pi - theta

c = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(theta))

print(f"{c:10}")


Measured memory_bytes: 62528
#include<bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using Lint=long long;

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

    string s[8]={"","SAT","FRI","THU","WED","TUE","MON","SUN"};
    string t; cin>>t;
    for(int i=1;i<8;i++) if(s[i]==t){
        cout<<i<<endl;
        return 0;
    }
}

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

#define ull unsigned long long
#define ll long long
#define null NULL
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int dp[3][100000] ;

int rec(vector <int>a,vector <int>b,vector <int>c,int n){
	dp[0][0] = a[0] ;
	dp[1][0] = b[0] ;
	dp[2][0] = c[0] ;
	for(int i = 1;i<n;i++){
		dp[0][i] = max(dp[1][i-1] ,dp[2][i-1]) + a[i] ;
		dp[1][i] = max(dp[0][i-1] ,dp[2][i-1]) + b[i] ;
		dp[2][i] = max(dp[1][i-1] ,dp[0][i-1]) + c[i] ;
	}
	return max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1])) ;
}

int main (){
	IOS
	int n ;
	cin >> n ;
	vector <int> a(n) ;
	vector <int> b(n) ;
	vector <int> c(n) ;
	for(int i = 0;i<n;i++) cin >> a[i] >> b[i] >> c[i] ;
	memset(dp,-1,sizeof(dp)) ;
	int ans = rec(a,b,c,n) ;
	cout << ans ;
	return 0 ;
}
		

Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
  }
  int a=1;
  for(int i=0;i<n;i++){
    if(vec.at(i)==a){
      a++;
    }
  }
  if(a==1){
    cout << -1 << endl;
  }else{
  cout << n+1-a << endl;
  }
}


Measured memory_bytes: 1024
#include<stdio.h>
main(){
  int a[3][8][2],i,j,tmp,l,tmp2,b[6][2];
  double k;
  for(i=0;i<3;i++){
    for(j=0;j<8;j++){
      scanf("%d %lf",&a[i][j][0],&k);
      a[i][j][1]=(int)(k*1000);
    }
  }

  for(i=0;i<7;i++){
    for(j=7;j>i;j--){
      for(l=0;l<3;l++){
	if(a[l][j][1]<a[l][j-1][1]){
	  tmp=a[l][j][1];
	  tmp2=a[l][j][0];
	  a[l][j][1]=a[l][j-1][1];
	  a[l][j][0]=a[l][j-1][0];
	  a[l][j-1][1]=tmp;
	  a[l][j-1][0]=tmp2;
	}
      }
    }
  }

  for(i=0;i<3;i++){
    for(j=0;j<2;j++){
      printf("%d %.2f\n",a[i][j][0],(double)(a[i][j][1])/1000);
    }
  }

    b[0][0]=a[0][2][0];
    b[0][1]=a[0][2][1];
    b[1][0]=a[0][3][0];
    b[1][1]=a[0][3][1];
    b[2][0]=a[1][2][0];
    b[2][1]=a[1][2][1];
    b[3][0]=a[1][3][0];
    b[3][1]=a[1][3][1];
    b[4][0]=a[2][2][0];
    b[4][1]=a[2][2][1];
    b[5][0]=a[2][3][0];
    b[5][1]=a[2][3][1];

  for(i=0;i<5;i++){
    for(j=5;j>i;j--){
      if(b[j][1]<b[j-1][1]){
	tmp=b[j][1],tmp2=b[j][0];
	b[j][1]=b[j-1][1],b[j][0]=b[j-1][0];
	b[j-1][1]=tmp,b[j-1][0]=tmp2;
      }
    }
  }

  for(i=0;i<2;i++)printf("%d %.2f\n",b[i][0],(double)(b[i][1])/1000);
  return 0;
}

Measured memory_bytes: 652
A,B,K = map(int, input().split())
if (A-K) < 0:
  K = (K-A)
  A = 0
else:
  A = A - K
  K = 0
if (B-K) < 0:
  B = 0
else:
  B = B - K
print(A, B)
  

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define fi first
#define se second
#define ld long double
#define ri register int
#define rep(i,a,b) for(ri i=(a);i<=(b);++i)
#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))
#define REP(i,a,b) for(ri i=(a);i>=(b);--i)
#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))
using namespace std;

inline ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

ll t[5],a[5],b[5],c,d;

int main()
{//ld ttt=1000000000000.12121221;ll xxx=floor(ttt);cout<<xxx<<endl;
	t[1]=read(),t[2]=read();
	a[1]=read(),a[2]=read();
	b[1]=read(),b[2]=read();
	c=a[1]*t[1]+a[2]*t[2];
	d=b[1]*t[1]+b[2]*t[2];
	if(c==d){
		puts("infinity");return 0;
	}
	if(c<d)swap(c,d),swap(a[1],b[1]),swap(a[2],b[2]);
	if(a[1]>b[1]&&a[2]>b[2]){
		puts("0");return 0;
	}
	ll ans=0;
	if(b[1]>a[1]){
	ld x=(ld)(b[1]-a[1])*t[1]/(a[2]-b[2]);//cout<<x<<endl;
	ld y=(ld)(c-d)/(a[2]-b[2]);//cout<<y<<' '<<a[2]-b[2]<<endl;
	ld z=x/y;//cout<<z<<endl;
	if(z==(ld)floor(z))ans+=(ll)floor(z);
	else ans+=(ll)floor(z)+1;
	x=(ld)(c-d)/(b[1]-a[1]);//cout<<x<<endl;
	if(x<=t[1]){
		z=t[1]/x;
		ans+=(ll)floor(z);
	}}cout<<ans;
	return 0; 
}

Measured memory_bytes: 256
a, b, h, m = gets.split.map(&:to_i)

passed_minites = 60 * h + m
a_deg = passed_minites.to_f * Math::PI / 360
b_deg = m.to_f * Math::PI / 30
puts Math.sqrt((a ** 2 + b ** 2 - 2 * a * b * Math.cos(a_deg-b_deg)))


Measured memory_bytes: 14748
#include <iostream>
#include <math.h>
using namespace std;
int main() {
	int N, T, A, H[1001];
	int min = 1;

	cin >> N >> T >> A;

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

	for (int i = 2; i <= N; i++)
	{
		/*if ((abs((T - H[min] * 0.006)-A))>abs(((T - H[i] * 0.006)-A))){
			min = i;
		}*/
		double a = (T - H[min] * 0.006) - A;
		if (a < 0) {
			a = -a;
		}
		double b = (T - H[i] * 0.006) - A;
		if (b < 0) {
			b = -b;
		}
		if (a > b) {
			min = i;
		}

	}

	cout << min << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
 
int main() {
    char s;
    cin >> s;
    bool b=false;
    vector<char>a={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    rep(i,26){
        if(s==a.at(i))b=true;
    }
    if(b) cout << 'a' << endl;
    else cout << 'A' << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>

using namespace std;

int main() {
  int N;
  cin >> N;
  bool flag = false;
  // ここにプログラムを追記
  for(int i; i < N ; i++){
    char A;
    cin >> A;
    if(A == 'Y'){
      flag = true;
    }
  }
  if(flag == true)
      cout << "Four" << endl;
  else
      cout << "Three" << endl;
}


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

using namespace std;
int main(int argc, char const *argv[]) {
  string s;
  cin >> s;

  for (int i = 0; i < s.length(); i++) {
    if ((i % 2 == 0 && s[i] == 'L') || (i % 2 == 1 && s[i] == 'R')) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  Int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(Int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  Int find(Int st,C &check,T &acc,Int k,Int l,Int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    Int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    Int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }
  template<typename C>
  Int find(Int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,q;
  cin>>n>>q;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  const Int INF = 1e15;
  using T = tuple<Int,Int,Int,Int,Int>;
  T ti(-INF,-INF,-INF,-INF,-INF);

  auto f=[&](T a,T b){
           if(a==ti) return b;
           if(b==ti) return a;
           Int as,ava,avi,avl,avr;
           tie(as,ava,avi,avl,avr)=a;
           Int bs,bva,bvi,bvl,bvr;
           tie(bs,bva,bvi,bvl,bvr)=b;
           Int cs=as+bs;
           Int cva=ava+bva,cvi=max(avi,bvi),cvl=avl,cvr=bvr;
           cvi=max(cvi,avr+bvl);
           cvl=max(cvl,ava+bvl);
           cvr=max(cvr,avr+bva);
           return T(cs,cva,cvi,cvl,cvr);
         };
  SegmentTree<T> seg(f,ti);

  vector<T> vt;
  for(Int i=0;i<n;i++) vt.emplace_back(as[i],as[i],as[i],as[i],as[i]);
  seg.build(vt);

  auto print=
    [&](){
      auto res=seg.query(0,n);
      Int ans=max({get<0>(res),get<1>(res),get<2>(res),get<3>(res),get<4>(res)});
      chmax(ans,0);
      cout<<ans<<endl;
    };

    print();
  for(Int i=0;i<q;i++){
    Int k,x;
    cin>>k>>x;
    k--;
    seg.set_val(k,T(x,x,x,x,x));
    print();
  }
  return 0;
}



Measured memory_bytes: 17808
n = int(input())
count = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == b:
        count += 1
    else:
        if count >= 3:
            print("Yes")
            exit()
        count = 0
if count >= 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 62360
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b;
  cin >> a >> b;
  if((a+b)/2==0){
    cout<< (a+b)/2 << endl;
  }
  else{
    cout << (a+b+1)/2 <<endl;
  }
}

Measured memory_bytes: 3568
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  string s;cin>>s;
  ll ans=0;
  ll n=s.size();
  ll part=0;
  rep(i,n){
    if(s[i]=='B')part++;
    if(s[i]=='W')ans+=part;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
N, K= map(int, input().split())
R, S, P =map(int, input().split())

T = [c for c in input()]
score = 0

for i in range(N):
    if i >= K and T[i] == T[i-K]:
        T[i] = "a"
        continue
    if T[i] == "r":
        score += P
    elif T[i] == "s":
        score += R
    else:
        score += S

print(score)

Measured memory_bytes: 4212
#include <iostream>
#include <ctype.h>

using namespace std;

int main(){
        int N, K;
        char S[50];
        cin >> N >> K;
        cin >> S;
        //printf("%d,%d\n", N, K);
        S[K-1] =  tolower(S[K-1]);
        printf("%s\n", S);
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created by hwzheng on 2017/3/27.
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader Reader = new BufferedReader (new InputStreamReader(System.in));
        int N = Integer.parseInt(Reader.readLine());
        String A[] = Reader.readLine().split(" ",0);
        int[] arr = new int[N];
        for (int i=0; i < N; i++){
            arr[i] = Integer.parseInt(A[i]);
        }
        bubbleSort(arr,N);
    }

    private static void bubbleSort(int[] arr, int n) {
        boolean flag = true;
        int exCount = 0;
        while (flag){
            flag = false;
            for (int i = n - 1; i > 0; i--){
                if (arr[i] < arr[i-1]){
                    exch(arr,i,i-1);
                    exCount++;
                    flag = true;
                }
            }
        }
        String str = "";
        for (int i = 0; i < arr.length; i++){
            str += arr[i] + " ";
        }
        System.out.println(str.substring(0,str.length()-1));
        System.out.println(exCount);
    }

    private static void exch(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

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

q = int(input())

from collections import Counter

ca = Counter(a)

ans=sum(a)
for _ in range(q):
    b,c = list(map(int, input().split()))
    
    if b in ca:
        cnt = ca.pop(b)
        ca[c] += cnt

        ans -= b * cnt
        ans += c * cnt
    
    print(ans)
    

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

int main(){
        int h, w;
        while(1){
                cin >> h >> w;
                if(h == 0 && w == 0)break;

                for(int i = 0; i < h; i++){
                        for(int j = 0; j < w; j++){ 
                                if(i == 0 || i == h - 1){
                                        cout << '#';
                                }else{
                                        if(j == 0 || j == w - 1){
                                                cout << '#';
                                        }else{
                                                cout << '.';
                                        }
                                }
                        }
                        cout << endl;
                }
                cout << endl;

        }
}

Measured memory_bytes: 3076
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
if sum(A)>sum(B):print("No")
else:
    c,d=0,0
    for i in range(N):
        if A[i]>=B[i]:c+=A[i]-B[i]
        else:d+=(B[i]-A[i])//2
    if c>d:print("No")
    else:print("Yes")

Measured memory_bytes: 4596
n,*abc=map(int,input().split())
ip=[0]*n
dic={0:"A",1:"B",2:"C"}
for i in range(n):
	tmp=input()
	if tmp=="AB":
		ip[i]=[0,1]
	elif tmp=="BC":
		ip[i]=[1,2]
	else:
		ip[i]=[0,2]
ans="Yes"
res=[0]*n
s=sum(abc)
if s==0:
	ans="No"
elif s==1:
	for i in range(n):
		i1=ip[i][0]
		i2=ip[i][1]
		ABC=[abc[i1],abc[i2]]
		if ABC==[0,0]:
			ans="No"
		elif ABC==[0,1]:
			abc[i1]+=1
			abc[i2]-=1
			res[i]=i1
		else:
			abc[i1]-=1
			abc[i2]+=1
			res[i]=i2
else:
	i1=ip[0][0]
	i2=ip[0][1]
	if [abc[i1],abc[i2]]==[0,0]:
		ans="No"
	else:
		for i in range(n):
			i1=ip[i][0]
			i2=ip[i][1]
			if abc[i1]==0:
				abc[i1]+=1
				abc[i2]-=1
				res[i]=i1
			elif abc[i2]==0:
				abc[i1]-=1
				abc[i2]+=1
				res[i]=i2
			elif i+1<n and ip[i+1]!=ip[i]:
				c=list(set(ip[i])&set(ip[i+1]))[0]
				if i1==c:
					abc[i1]+=1
					abc[i2]-=1
					res[i]=i1
				else:
					abc[i1]-=1
					abc[i2]+=1
					res[i]=i2
			else:
				abc[i1]+=1
				abc[i2]-=1
				res[i]=i1
print(ans)
if ans=="Yes":
	for i in range(n):
		print(dic[res[i]])

Measured memory_bytes: 18644
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut ds = vec![0; n];
    for i in 0..n {
        ds[i] = read::<usize>();
    }
    let mut sum = 0;
    for i in 0..n {
        for j in 0..i {
            sum += ds[i] * ds[j];
        }
    }
    println!("{}", sum);
}


Measured memory_bytes: 2112
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<numeric>

#define MOD 1000000007

using namespace std;
typedef long long ll;

int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int field[100][100];
int N, M;

int check(int y, int x) {
	field[y][x] = 0;
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (field[ny][nx])
			cnt = max(cnt, check(ny, nx) + 1);
	}
	field[y][x] = 1;
	return cnt;
}

int main()
{
	while (1) {
		for (int i = 0; i < 100; i++)
			for (int j = 0; j < 100; j++)
				field[i][j] = 0;
		cin >> N >> M;
		if (N == 0 && M == 0)break;

		for (int i = 1; i <= M; i++)
			for (int j = 1; j <= N; j++)
				cin >> field[i][j];

		int ans = 0;
		int mx = 0;
		for (int i = 1; i <= M; i++) {
			for (int j = 1; j <= N; j++) {
				if (field[i][j]) {
					mx = check(i, j) + 1;
					ans = max(mx, ans);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

ll k, m = 0, n;
ll t[1 << 17], d[1 << 17];
vector<ll> u, v;

int main()
{
    cin >> n >> k;
    n++;
    if (n / 2 >= k)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;


int main()
{
int A,B;
cin>>A>>B;
int r ,t ,y;
r=A+B;
t=A-B;
y=A*B;

if(r>=t&&r>=y)
    cout <<r;
else
    if(t>=y&&t>=r)
cout <<t;
else
    if(y>=t&&y>=r)
    cout << y;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,avrg_int;
    double avrg,frac;
    scanf("%d %d",&a,&b);
    avrg=(a+b)/2.0;
    avrg_int=avrg;
    frac=avrg-avrg_int;
    if(avrg==avrg_int)
    {
        printf("%d",avrg_int);
    }
    else
    {
        printf("%d",avrg_int+1);
    }
    return 0;
}




Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        if ("AAA".equals(s) || "BBB".equals(s)) {
            System.out.println("No");
            return;
        }
        System.out.println("Yes");
    }

}


Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;

struct LowestCommonAncestor {
    size_t n;
    size_t size() const { return n; }
    vector<int> color, parent, depth, topDepth, goUp, visited;
    vector<vector<int>> g;
    LowestCommonAncestor(size_t n_) : n(n_), g(n) {}
    void addEdge(int u, int v){
        g[u].push_back(v); g[v].push_back(u);
    }
    void decomp(int root = 0, int B = 500){
        parent.assign(n, -1); depth.assign(n, 0);
        topDepth.assign(n, 0); goUp.assign(n, -1); visited.assign(n, false);
        vector<int> tord;
        vector<int> q(n+1); int l = 0, r = 0;
        q[r++] = root;
        while(l != r){
            int v = q[l++]; visited[v] = true;
            tord.push_back(v);
            for(int c : g[v]){
                if(!visited[c]){ parent[c] = v; depth[c] = depth[v] + 1; q[r++] = c; }
            }
        }
        swap(color, visited); // ?????¢????????±??????
        color.assign(n, -1);
        int c = 0;
        for(int u : tord){
            if(color[u] != -1) continue;
            l = 0, r = 0;
            q[r++] = u;
            for(int i = 0; i < B && l != r; i++){
                int v = q[l++];
                color[v] = c; goUp[v] = parent[u]; topDepth[v] = depth[u];
                for(int c : g[v]) if(color[c] == -1) q[r++] = c;
            }
            c++;
        }
    }
    int solve(int u, int v){
        while(topDepth[u] > topDepth[v]) u = goUp[u];
        while(topDepth[u] < topDepth[v]) v = goUp[v];
        while(depth[u] > depth[v]) u = parent[u];
        while(depth[u] < depth[v]) v = parent[v];
        while(u != v) u = parent[u], v = parent[v];
        return u;
    }
};

#define rep(i,n) for(int i = 0; i < (int)(n); i++)

int main(){
    int n;
    cin >> n;
    LowestCommonAncestor g(n);
    rep(i,n){
        int k;
        cin >> k;
        rep(j,k){
            int c;
            cin >> c;
            g.addEdge(i,c);
        }
    }
    g.decomp(0);
    int q;
    cin >> q;
    rep(i,q){
        int u,v;
        cin >> u >> v;
        cout << g.solve(u,v) << endl;
    }
}

Measured memory_bytes: 10028
n = int(input())
a = [int(input()) for i in range(n)]

ans = 0

for i in range(n-1):
    ans += a[i]//2
    if a[i]%2==1 and a[i+1]>0:
        a[i+1]-=1
        ans += 1

ans += a[n-1]//2

print(ans)

Measured memory_bytes: 49880
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;
int a[maxx];
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> a[i];
	ll sum = 0;
	for(int i = 0; i < n; i ++)
	{
		for(int j = i; j < n; j ++)
		{
			if(i == j) continue;
			else
			{
				sum += a[i] * a[j];
//				cout << sum << "ssss";
			}
		}
		
	}
	cout << sum << '\n'; 

	return 0;
}



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

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


signed main(){
    i64 n, t;
    cin >> n >> t;
    vector<i64> a(n);
    for(auto& x : a)
        cin >> x;

    i64 ans = 0;
    for(int i = 1; i < n; ++i){
        i64 nex = min(t, a[i] - a[i - 1]);
        ans += nex;
    }

    cout << ans + t << endl;
}


Measured memory_bytes: 1792
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N, M, K;
char S[2000011];
char T[2000011];

void show(char *s) {
    int i;
    for (i=2000010; s[i] == 0; i--) ;
    for (; i>=0; i--) putchar(s[i]+'0');
    putchar('\n');
}

void MAIN() {
    scanf("%d%d%d", &N, &M, &K);
    scanf("%s", S);
    scanf("%s", T);
    REP (i, N) S[i] -= '0';
    REP (i, M) T[i] -= '0';

    reverse(S, S+N);
    reverse(T, T+M);

    stack<int> st;

    for (int i=1000011; i--;) {
	VI update;
	if (S[i] == 1 && T[i] == 1) {
	    S[i] = T[i] = 0;
	    int xs = 1, xt = 1;
	    int z = K-1;
	    int j = i+1;
	    while (xs || xt) {
		if (S[j] == 0 && T[j] == 0) {
		    if (xs == 1 && xt == 0) {
			S[j] = 1;
			st.push(j);
			break;
		    } else if (xs == 0 && xt == 1) {
			T[j] = 1;
			st.push(j);
			break;
		    }
		}
		if (st.empty() || st.top() - j > z) {
		    S[j+z] = T[j+z] = 1;
		    break;
		}

		int p = st.top(); st.pop();
		z -= p - j;
		j = p;

		if (S[j] == xs && T[j] == xt) {
		    S[j] = T[j] = 0;
		    j++;
		    continue;
		}

		if (xs == 1 && xt == 1) {
		    xs = S[j];
		    xt = T[j];
		    S[j] ^= 1;
		    T[j] ^= 1;
		    update.push_back(j);
		    j++;
		    continue;
		}

		if (S[j] != xs && T[j] != xt) {
		    if (z == 0) {
			S[j] = T[j] = 1;
			break;
		    } else {
			S[j] = T[j] = 0;
			j++;
			z--;
			xs = xt = 1;
			continue;
		    }
		}

		assert(false);
	    }

	    while (!update.empty()) {
		st.push(update.back());
		update.pop_back();
	    }
	} else if (S[i] || T[i]) {
	    st.push(i);
	}
    }

    show(S);
    show(T);
}

int main() {
    int TC = 1;
    //    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

int main() {
  string N;
  cin >> N;
  int Nnum = N.size();
  vector<int> M(Nnum);
  int sum=0;
  
  for (int i=0; i<Nnum; ++i) {
    M.at(i) = N.at(i) - '0';
  }
  
  for (int i=0; i<Nnum; ++i) {
    sum += M.at(i);
  }
  
  if ( N == "0") {
    cout << "Yes" << endl;
  }
  else if ( sum%9==0 ) {
    cout << "Yes" << endl;
  }
  else if (sum%9 != 0) {
    cout << "No" << endl;
  }

}

Measured memory_bytes: 4240
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string w;
    cin >> w;
    vint cnt(26,0);
    for(char c:w){
        cnt[(int)(c-'a')]++;
    }
    REP(i,26){
        if(cnt[i]%2==1){
            puts("No");
            return 0;
        }
    }
    puts("Yes");

    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 	// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inff (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
#define SPEED ios_base::sync_with_stdio(false) ;cin.tie(NULL) ;cout.tie(NULL) ;
#define fp(i,a,n) for(ll i=n-1; i>a ;i--)
#define deb(x) cout << #x << " ---> " << x << endl;
#define X first
#define Y second
#define pia 3.1415926536
#define mod 1000000007
#define mod2 998244353

#define ml map<ll,ll>
#define mll map<pll,ll>
#define vvl vector<vl>
#define vvi vector<vi>
#define letsh(a,b) a<<b
#define rigsh(a,b) a>>b 
mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count()) ;
		bool sortbysec(const pair<int,int> &a, 
		      const pair<int,int> &b) 
		{ 
		    return (a.second < b.second); 
		} 	   
		
		  ll power(ll a,ll n)
		{
		ll ans=1;
		while(n)
		{
		if(n&1) ans=(ans*a)%mod;
		a=(a*a)%mod ;
		n=n>>1;
		 }
		 return ans;
		}
		ll power2(ll a,ll n)
		{
		ll ans =1 ;
		while(n)
		{
			if(n&1) ans =(ans*a) ;
			n =n>>1 ;
			a = (a*a) ;
		  }
		  return ans ;
		}
		ll lcm(ll a, ll b)
		{
		       return a / __gcd(a, b) * b;
		}
#define N 100050
#define M 400060
         vll dir({{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) ;
	     void solve()
		 {
	      ll n ;cin>>n ;
	     vl a(n) ;f(i,0,n) cin>>a[i] ;
		ll mx =a[0] ;
	     ll ans =0 ;
		 f(i,0,n) mx = max(mx,a[i]) ,ans +=mx-a[i] ;
		 cout<<ans<<endl ; 
	     }    
		  
			  int main() 
	  	{
	    SPEED
	   ll t =1 ;
	    while(t--) solve() ;
	    
	    }

Measured memory_bytes: 4824
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N=1e2+5;
const int mod=1e9+7;
int a,b;
int main()
{
	cin>>a>>b;
	if(a%b)cout<<1;
	else cout<<0;


	return 0;
}


Measured memory_bytes: 384
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	a, b, c := nextInt(), nextInt(), nextInt()
	c++
	fmt.Println((a * b) / 2)
}


Measured memory_bytes: 640
import sys
lst = list(map(int,input().split()))
lst1 = list(set(lst))
ans = False
if len(lst1) == 1:
    print('No')
    sys.exit()
if lst.count(lst1[0]) == 1:
    if lst.count(lst1[1]) == 2:
        ans = True
else:
    if lst.count(lst1[1]) == 1:
        ans = True

if ans == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
# だめだったやつ
""" 
s=list(input())
res=[0]*len(s)
cnt=0
a=0
b=0
for i in range(1,len(s)):
    if s[i]=='L':continue
    else:
        cnt+=1
        if s[i+1]=='L':
            if cnt%2:
                res[i]+=cnt//2
                res[i+1]+=cnt//2+1
            else:
                res[i+1]+=cnt//2+1
                res[i]+=cnt//2
            cnt=0
print(res)           
"""    

# 2019/09/12

s=list(input())
n=len(s)
res=[1]*n


def rle():

    RLE=[]
    l=0
    r=1
    while l<n:
        while r<n:
            if s[l]==s[r]:
                r+=1
            else:
                break
        RLE.append((s[l],r-l))
        l=r
        r+=1
    return RLE

RLE=rle()

ans=[]

for i in range(0,len(RLE),2):
    r=RLE[i][1]
    l=RLE[i+1][1]
    ans+=[0]*(r-1)

    a=r//2+(-(-l//2))   
    b=l//2+(-(-r//2))
    if (r+l)%2:
        a,b=b,a


    ans.append(a)
    ans.append(b)
    ans+=[0]*(l-1)
    

print(*ans)

Measured memory_bytes: 14880
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

string C[3];
int i;
inline void solve(){
  REP(i,3)IN(C[i]);
  REP(i,3)cout<<C[i][i];
  cout<<endl;
}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
// +build ignore
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func gcd(x, y int) int {
	if x%y != 0 {
		return gcd(y, x%y)
	}
	return y
}

const D int = 60
const MAX_N int = 200005

var to [D][MAX_N]int

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	N := sc.nextInt()
	K := sc.nextInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = sc.nextInt() - 1
	}

	for i := 0; i < N; i++ {
		to[0][i] = A[i]
	}

	for i := 1; i < D; i++ {
		for j := 0; j < N; j++ {
			to[i][j] = to[i-1][to[i-1][j]]
		}
	}

	p := 0
	for i := D; i >= 0; i-- {
		if K&(1<<i) != 0 {
			p = to[i][p]
		}
	}

	fmt.Println(p + 1)

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


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

namespace _0087
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string s = Console.ReadLine();
                if (string.IsNullOrEmpty(s)) break;
                string[] x = s.Split();
                Stack<double> stack = new Stack<double>();
                for (int i = 0; i < x.Count(); i++)
                {
                    switch (x[i])
                    {
                        case ("+"):
                        {
                            stack.Push(stack.Pop() + stack.Pop());
                            break;
                        }
                        case ("-"):
                        {
                            double a = stack.Pop();
                            stack.Push(stack.Pop() - a);
                            break;
                        }
                        case ("*"):
                        {
                            stack.Push(stack.Pop() * stack.Pop());
                            break;
                        }
                        case ("/"):
                        {
                            double a = stack.Pop();
                            stack.Push(stack.Pop() / a);
                            break;
                        }
                        default:
                        {
                            stack.Push(double.Parse(x[i]));
                            break;
                        }
                    }
                }
                Console.WriteLine(stack.Pop());
            }
        }
    }
}


Measured memory_bytes: 10628
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <ios>
#include <cstdlib>
#define ll long long
#define rep(i, s, n) for(int i = s; i < n; i++)
using namespace std;

int main() {
    ll h;
    //cout << floor(5/2.0);
    ll count = 1;
    cin >> h;
    while(h > 1) {
        h /= 2;
        count++;
    }
    //cout << -(1-pow(2, count)) << endl;
    //printf("%10ld\n",  -(1-pow(2, count)));
    ll ans = -(1-pow(2, count));
    //cout << -(1-pow(2, count)) << endl;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>

namespace gg
{
	typedef long long ll;
	const int N=100100,M=N*2;
	int begin[N],next[M],to[M];
	int col[N];
	int n,m,e;
	int cnt1,cnt2;
	ll ans;
	void add(int x,int y,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		if(k)add(y,x,0);
	}
	bool dfs(int p,int w)
	{
		if(col[p]==w)return 1;

		if(!col[p])col[p]=w;
		else return 0;

		for(int i=begin[p];i;i=next[i])
		{
			int q=to[i];
			if(!dfs(q,3-w))return 0;
		}
		return 1;
	}
	void initialize()
	{
		scanf("%d%d",&n,&m);
		for(int u,v,i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			add(u,v);
		}
	}
	void work1()
	{
		cnt1=cnt2=0;
		for(int i=1;i<=n;i++)
			if(col[i]==1)cnt1++;
			else cnt2++;

		ans=(ll)cnt1*cnt2;

		printf("%lld\n",ans-m);
	}
	void work2()
	{
		ans=(ll)n*(n-1)/2;
		printf("%lld\n",ans-m);
	}
	void solve()
	{
		initialize();
		if(n<=3)
		{
			printf("0\n");
			return;
		}
		if(dfs(1,1))work1();
		else work2();
	}
}

int main()
{
	gg::solve();
	return 0;
}


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

typedef priority_queue<int> maxHeap;
typedef priority_queue<int, vector<int>, greater<int>> minHeap;
#define endl "\n"
#define int long long
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define max(x, y) ((x > y) ? x : y)
#define min(x, y) ((x < y) ? x : y)
#define mid(s, e) ((s + (e - s) / 2))

bool test_cases;

void init(bool k) {
    test_cases = k;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

struct precompute {
    void compute() {
    }
};

struct test_cases {
    void test_case() {
        int n;
        cin >> n;
        int a[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> a[i][j];
            }
        }

        int dp[n][3];

        dp[0][0] = a[0][0];
        dp[0][1] = a[0][1];
        dp[0][2] = a[0][2];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 2; j++) {
                int mx = INT_MIN;
                int act;
                for (int k = 0; k <= 2; k++) {
                    if (k == j) continue;
                    if (mx <= dp[i - 1][k]) {
                        mx = dp[i - 1][k];
                        act = k;
                    }
                }

                dp[i][j] = mx + a[i][j];
            }
        }
        cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << endl;
    }
};

int32_t main() {
    init(false);
    int tc;
    if (test_cases) {
        cin >> tc;
    } else {
        tc = 1;
    }
    struct precompute l;
    l.compute();
    for (int i = 0; i < tc; i++) {
        struct test_cases o;
        o.test_case();
    }
    return 0;
};

Measured memory_bytes: 8228
#include<iostream>
using namespace std;
int parent[1<<17],myrank[1<<17],weight[1<<17];
int root(int x)
{
	if(parent[x]==x)return x;
	else
	{
		int r=root(parent[x]);
		weight[x]+=weight[parent[x]];
		return parent[x]=r;
	}
}
int get_weight(int x)
{
	root(x);
	return weight[x];
}
bool issame(int x,int y)
{
	return root(x)==root(y);
}
void diff(int x,int y)
{
	if(!issame(x,y))
	{
		cout<<"UNKNOWN"<<endl;
	}
	else cout<<get_weight(y)-get_weight(x)<<endl;
}
void mymerge(int x,int y,int w)
{
	w+=get_weight(x)-get_weight(y);
	x=root(x);y=root(y);
	if(myrank[x]<myrank[y])swap(x,y),w*=-1;
	if(myrank[x]==myrank[y])myrank[x]++;
	parent[y]=x;
	weight[y]=w;
}
main()
{
	int n,m;
	while(cin>>n>>m,n)
	{
		for(int i=0;i++<n;)parent[i]=i,myrank[i]=0,weight[i]=0;
		for(int i=0;i<m;i++)
		{
			char c;cin>>c;
			if(c=='!')
			{
				int a,b,w;cin>>a>>b>>w;
				mymerge(a,b,w);
			}
			else
			{
				int a,b;cin>>a>>b;
				diff(a,b);
			}
		}
	}
}



Measured memory_bytes: 4148
import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    D = int(input().strip())
    C = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
    S = np.empty((D, 26), dtype=np.int32)
    for i in range(D):
        s = np.fromstring(input().strip(), dtype=np.int32, sep=" ")
        S[i, :] = s[:]
    M = 10000
    RD = np.random.randint(D, size=(M, ), dtype=np.int32)
    RQ = np.random.randint(26, size=(M, ), dtype=np.int32)
    DQ = np.stack([RD, RQ]).T
    return D, C, S, M, DQ


@njit
def diff_satisfaction(C, S, d, p, last):
    """d日目にコンテストpを開催するときの、満足度の更新量を求める
    """
    v = 0
    for i in range(26):
        v -= C[i] * (d - last[i])
    v += C[p] * (d - last[p])
    v += S[d, p]
    return v


@njit
def evaluate(D, C, S, d, p, last, k=13):
    """d日目にコンテストpを開催し、その後d+k日目までコンテストが開催されないときの、満足度の更新差分を求める
    """
    v = diff_satisfaction(C, S, d, p, last)
    for e in range(d+1, min(d+k, D)):
        for i in range(26):
            v -= C[i] * (e - last[i])
        v += C[p] * (d - last[p])
    return v


@njit
def greedy_fine(D, C, S):
    T = np.zeros(D, dtype=np.int32)
    last = -np.ones(26, dtype=np.int32)
    cumsat = 0
    for d in range(D):
        
        max_p = 0
        max_e = -999999999

        # select contest greedily
        for p in range(26):
            e = evaluate(D, C, S, d, p, last, k=13)
            
            if e > max_e:
                max_p = p
                max_e = e
        
        # update schedule
        cumsat += diff_satisfaction(C, S, d, max_p, last)
        T[d] = max_p
        last[max_p] = d
    return cumsat, T


@njit
def solve(D, C, S, M, DQ):
    cumsat, T = greedy_fine(D, C, S)
    for t in T:
        print(t+1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


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

typedef long long int Int;

void faster()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}




int main()
{
    faster();
    
    Int n,W;
    cin>>n>>W;
    Int i,j;
    
    Int w[n+1];
    Int v[n+1];
    
    for(i=1; i<=n; i++) { cin>>w[i]>>v[i]; }
    
    w[0] = 0;
    v[0] = 0;
    
    Int val[W+1][n+1];
    
    for(i=0; i<=W; i++)
    {
        for(j=0; j<=n; j++)
        {
            if (i <= 0 || j <= 0) val[i][j] = 0;
            else
            {
                if ( i >= w[j]  )
                {
                    val[i][j] = max( v[j] + val[ i- w[j] ][ j-1 ] , val[i][j-1]  );
                }
                else
                {
                    val[i][j] = val[i][j-1];
                }
                
            }
            
        }
    }
    
    
    cout<<val[W][n];
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 79232
n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
ans = [0] * n
even_a = 0
for i in a[1::2]:
    even_a += i
ans[0] = s - 2 * even_a
for i in range(1, n):
    ans[i] = 2 * a[i-1] - ans[i-1]
print(" ".join(map(str, ans)))

Measured memory_bytes: 84580
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cctype>
#include <string>

using namespace std;

int main(){

  int N;
  cin >> N;
  int ans = 0;

  bool flag = true;

  while (1){
    if(N > 10){
      N = N % 10;
    }else{
      flag = false;
    }
    if(flag == false) break;
  }

  if(N == 2 || N == 4 || N == 5 || N == 7 || N == 9){
    cout << "hon" << endl;
  } else if (N == 0 || N == 1 || N == 6 || N == 8 ){
    cout << "pon" << endl;
  } else {
    cout << "bon" << endl;
  }

  return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;

const ll mod = 1e9+7;
const ll INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

ll x[100000];
ll y[100000];

int main(void){
    ll n, m; cin >> n >> m;
    for(int i = 0;i < n;i++)cin >> x[i];
    for(int i = 0;i < m;i++)cin >> y[i];
    ll xx = 0;
    for(int i = 0;i < n-1;i++){
        xx += (x[i+1] - x[i]) * (i+1) * (n-i-1);
        xx %= mod;
    }
    ll yy = 0;
    for(int i = 0;i < m-1;i++){
        yy += (y[i+1] - y[i]) * (i+1) * (m-i-1);
        yy %= mod;
    }
    cout << (xx * yy) % mod << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 1000000 + 10
using namespace std;
int N;
int len[Maxn];
int result = 0;
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> len[i];
    sort(len,len+N);
    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            int a=len[i];
            int b=len[j];
            int k=lower_bound(len,len+N,a+b)-len;
            result+=k-j-1;
        }
    }
    cout<<result<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < (n);i++)
#define lint long long
const lint mod=1e9+7;
const lint inf=2.19e15+1;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}

signed main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    int l = 0, r = n - 1;
    while (true){
        while (s[l] != 'W' and l < n - 1) l += 1;
        while (s[r] != 'R' and r > 0) r -= 1;
        if (l >= r) break;
        cnt += 1;
        l += 1;
        r -= 1;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3720
n = gets.to_i
p = gets.split.map(&:to_i)
ans = 0
0.upto(n - 1) do |i|
  if p[i] == i + 1
    if i == n - 1
      p[i], p[i - 1] = p[i - 1], p[i]
    else
      p[i], p[i + 1] = p[i + 1], p[i]
    end
    ans += 1
  end
end
puts ans

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

int main() {
  long N, K;
  cin >> N >> K;
  vector<pair<int, int>> AB(N);
  for (auto& ab : AB) cin >> ab.first >> ab.second;
  sort(AB.begin(), AB.end());
  for (auto ab : AB) {
    if (K <= ab.second) {
      cout << ab.first << endl;
      return 0;
    }
    K -= ab.second;
  }
}

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

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.ok","w",stdout);
    int n; int k; int64_t a=0;
    cin >> n >> k;
    int64_t h[n];
    for (int i=0;i<n;i++)
        cin >> h[i];
    sort(h,h+n,greater<int>());
    for (int i=k;i<n;i++)
        a=a+h[i];
    cout << a; 
}

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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int n, m;
    cin >> n >> m;
    vi x(m);
    rep(i, m) cin >> x[i];
    VSORT(x);
    vi b(m-1);
    rep(i, m-1) b[i] = x[i+1] - x[i];
    VSORT(b);
    ll ans = 0;
    rep(i, m-n) ans += b[i];
    cout << ans << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;

ll n,m,k;
ll a[200005];
ll b[200005];

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]=a[i]+a[i-1];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        b[i]=b[i]+b[i-1];
    }
    int j=m;
    int rj=0;
    for(int i=0;i<=n;i++){
        ll t=k-a[i];
        if(t<0)
            break;
        for(j;j>=0;j--)
            if(b[j]<=t)
                break;
        rj=max(rj,i+j);
    }
    cout <<rj<<endl;
}


Measured memory_bytes: 6732