akhauriyash/Code-Regression huggingface dataset:
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

ld Calc_Dist (ld X1, ld Y1, ld X2, ld Y2){
  ld ans = (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2);
  ans = sqrtl(ans);
  return ans;
}

pair <ld, ld> Calc_P (ld X1, ld Y1, ld R1, ld R2){
  ld A = (X1 * X1 + Y1 * Y1 + R1 * R1 - R2 * R2) / 2;

  ld X = A * X1 + Y1 * sqrtl((X1 * X1 + Y1 * Y1) * R1 * R1 - A * A);
  X /= X1 * X1 + Y1 * Y1;

  ld Y = A * Y1 - X1 * sqrtl((X1 * X1 + Y1 * Y1) * R1 * R1 - A * A);
  Y /= X1 * X1 + Y1 * Y1;

  return make_pair(X, Y);
}

pair <ld, ld> Calc_Q (ld X1, ld Y1, ld R1, ld R2){
  ld A = (X1 * X1 + Y1 * Y1 + R1 * R1 - R2 * R2) / 2;

  ld X = A * X1 - Y1 * sqrtl((X1 * X1 + Y1 * Y1) * R1 * R1 - A * A);
  X /= X1 * X1 + Y1 * Y1;

  ld Y = A * Y1 + X1 * sqrtl((X1 * X1 + Y1 * Y1) * R1 * R1 - A * A);
  Y /= X1 * X1 + Y1 * Y1;

  return make_pair(X, Y);
}

int main(){
  const ld EPS = 1e-8;
  int N, K; cin >> N >> K;

  ld X[N], Y[N], C[N];
  for (int i = 0; i < N; i++){
    cin >> X[i] >> Y[i] >> C[i];
  }

  ld L = 0, R = 1e10;
  while (R - L > EPS){
    ld now = (L + R) / 2;

    vector <pair<ld, ld>> Cand;


    for (int i = 0; i < N; i++){
      Cand.push_back(make_pair(X[i], Y[i]));
      for (int j = i + 1; j < N; j++){
        ld Ri = now / C[i], Rj = now / C[j];
        ld Dist = Calc_Dist(X[i], Y[i], X[j], Y[j]);

        if (Dist < abs(Ri - Rj) - EPS) continue;
        if (Dist > Ri + Rj + EPS) continue;

        double theta = atan((Y[j] - Y[i]) / (X[j] - X[i]));
        
        if (X[j] - X[i] <= 0) theta += PI;
        else if (Y[j] - Y[i] <= 0) theta += 2 * PI;

        double phi = acos((Ri * Ri + Dist * Dist - Rj * Rj) / (2 * Ri * Dist));

        double Xnow = X[i] + Ri * cos(theta + phi);
        double Ynow = Y[i] + Ri * sin(theta + phi);
        Cand.push_back(make_pair(Xnow, Ynow));

        Xnow = X[i] + Ri * cos(theta - phi);
        Ynow = Y[i] + Ri * sin(theta - phi);
        Cand.push_back(make_pair(Xnow, Ynow));
      }
    }
    
    bool flag = false;
    for (int i = 0; i < Cand.size(); i++){
      int cnt = 0;
      ld X_now = Cand[i].first, Y_now = Cand[i].second;

      for (int j = 0; j < N; j++){
        ld Dist = Calc_Dist(X_now, Y_now, X[j], Y[j]);
        if (Dist <= now / C[j] + EPS) cnt++;
      }
      if (cnt >= K) flag = true;
    }
    
    if (flag == true) R = now;
    else L = now;
  }
  cout << setprecision(16) << (L + R) / 2 << endl;

  return 0;
}


Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int to, cost; };
struct gNode { int from, to, cost; };
struct tNode { int value; int parent; vector<int> child; };

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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n/2);
	if(n & 1) res = res * x % MOD;
	return res;
}

int main(void){
	int n, m; cin >> n >> m;
	vector<int> a(n);
	multiset<int> s;
	rep(i, n){
		cin >> a[i];
		s.insert(-a[i]);
	}

	rep(_, m){
		int hoge = *s.begin();
		s.erase(s.begin());
		hoge /= 2;
		s.insert(hoge);
	}

	ll ans = 0;
	for(auto x: s){
		ans += (ll)x;
	}
	cout << -ans << endl;
	return 0;
}

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

int main(void);

int main(void){
    int a, b, c, tmp;
    scanf("%d %d %d", &a, &b, &c);
    tmp = b;
    b = a;
    a = tmp;
    tmp = c;
    c = a;
    a = tmp;
    printf("%d %d %d", a, b, c);

    return 0;
}


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

int main() {
    int n, a;
    int bitsum = 0;
    int count = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        bitsum |= a;
    }
    while (bitsum % 2 == 0)
    {
        count++;
        bitsum >>= 1;
    }
    cout << count << endl;
}

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

using namespace __gnu_pbds;
using namespace std;

// MACROS

#define ll long long
#define ull unsigned long long
#define ld long double

#define vi vector<int>
#define vll vector<ll>
#define vld vector<ld>
#define u_s unordered_set

#define pii pair<int,int>
#define pll pair<ll,ll>

#define FOR(i, n) for (ll i = 0; i < n; i++)
#define FORN(i, a, b) for (ll i = a; i < b; i++)
#define FORE(i, l) for (auto i : l)

#define pb push_back
#define pob pop_back
#define emp emplace
#define fi first
#define se second

#define all(n) n.begin(), n.end()
#define in(n) cin >> (n);
#define debug(n) cout << #n << ": " << n << '\n';

// FUNCTIONS

template< typename T >
inline T gcd(T a, T b) { if (b) return gcd(b, a % b); return a; }

template< typename T >
inline T ext_gcd(T a, T b, T & x, T & y) { if (a == 0) { x = 0; y = 1; return b; } T x1, y1; T g = ext_gcd(b % a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return g; }

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);	
    //cout << setprecision(15);
    ll a, b;
    cin >> a >> b;
    cout << (b - 1 + a - 2) / (a - 1) << '\n'; 
}



Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int n, m, a, count = 0;
    scanf("%d %d", &n, &m);
    for(;m > 0; m--)
    {
    	scanf("%d", &a);
    	count += a;
    }
    if(count > n)
    	printf("-1");
    else
    	printf("%d", n - count);
    return 0;
}

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

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int x = sc.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);

		int ans = 0;
		for (int i = 0; i < a.length; i++) {
			x -= a[i];
			if (x < 0)
				break;
			if (i == a.length - 1 && x > 0)
				break;
			ans++;
		}

		System.out.println(ans);
		sc.close();
	}

}


Measured memory_bytes: 21844
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int const MAXN=1e2+9;
int n;
int t1=1;
int t2=1;
int a[MAXN]={0};
int s1[MAXN]={0};
int s2[MAXN]={0};
bool used[MAXN]={false};

bool check(int *s,int t)
{
	for(int i=1;i<t-1;i++)
		if(!(s[i]<s[i+1]))
			return false;
	return true;
}

bool dfs(int i)
{
	if(i==n)
	{
		t2=1;
		for(int i=1;i<=n;i++)
			if(!used[i])
				s2[t2++]=a[i];
		if(check(s1,t1)&&check(s2,t2))
			return true;
		return false;
	}
	if(dfs(i+1))
		return true;
	if(a[i]>=s1[t1-1])
	{
		used[i]=true;
		s1[t1++]=a[i];
		if(dfs(i+1))
			return true;
		used[i]=false;
		t1--;
	}
	return false;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		n=10;
		t1=1;
		t2=1;
		memset(a,0,sizeof(a));
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		memset(used,false,sizeof(used));
		for(int i=1;i<=n;i++)
			cin>>a[i];
		s1[t1++]=a[1];
		used[1]=true;
		if(dfs(2))
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}


Measured memory_bytes: 3036
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <iomanip>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
typedef long long ll;

int main(){
    ll a,b,x;
    cin>>a>>b>>x;
    long double y;
    if(x>a*a*b/2){
        y=1000000000*2*(a*a*b-x)/(a*a*a);
    }else{
        y=1000000000*(a*b*b)/(2*x);
    }
    cout << fixed << setprecision(7) << atan(y/1000000000)*180/M_PI;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var N, D, X, a int
	fmt.Scan(&N)
	fmt.Scan(&D)
	fmt.Scan(&X)

	var as []int
	for i := 0; i < N; i++ {
		fmt.Scan(&a)
		as = append(as, a)
	}

	sum := X
	for _, num := range as {
		sum += choco(num, D)
	}

	fmt.Println(sum)
}

func choco(interval int, x int) int {
	return 1 + (x - 1) / interval
}

Measured memory_bytes: 512
import os, sys, re, math

n = int(input())
p = ([int(n) for n in input().split()])

count = 0
for i in range(1, n - 1):
    if p[i - 1] < p[i] < p[i + 1] or p[i - 1] > p[i] > p[i + 1]:
        count += 1

print(count)

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

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

    vector<long long> A(N + 1);
    for(int i = 0; i < N + 1; i++) {
        cin >> A.at(i);
    }

    vector<long long> B(N);
    for(int i = 0; i < N; i++) {
        cin >> B.at(i);
    }

    long long ans = 0;

    for (int i = 0; i < N; i++) {
        if (A.at(i) >= B.at(i)) {
            ans += B.at(i);
        }
        else {
            if (A.at(i) + A.at(i + 1) >= B.at(i)) {
                ans += B.at(i);
                long long remon = B.at(i) - A.at(i);
                A.at(i + 1) -= remon;
            }
            else {
                ans += A.at(i) + A.at(i + 1);
                A.at(i + 1) = 0;
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int t1 = h1 * 60 + m1;
    int t2 = h2 * 60 + m2;
    cout << t2 - t1 - k << endl;

}

Measured memory_bytes: 3648
import java.util.Scanner;
public class Main {
     
    static char[] k = {'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'};
     
 
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        double x1 = stdIn.nextDouble();
        double y1 = stdIn.nextDouble();
        double x2 = stdIn.nextDouble();
        double y2 = stdIn.nextDouble();
         
        double ans = Math.sqrt((x1 - x2)*(x1 - x2) + (y1 - y2) * (y1 - y2));
         
        System.out.println(ans);
    }
}


Measured memory_bytes: 28008
N,M=map(int,input().split())
venue=[]
if N%2==0:
    l=1
    r=N//2
    while l<r:
        venue.append([l,r])
        l+=1
        r-=1
    l=N//2+1
    r=N-1
    while l<r:
        venue.append([l,r])
        l+=1
        r-=1
else:
    l=1
    r=N//2
    while l<r:
        venue.append([l,r])
        l+=1
        r-=1
    l=N//2+1
    r=N
    while l<r:
        venue.append([l,r])
        l+=1
        r-=1
for a,b in venue:
    M-=1
    print(a,b)
    if M==0:
        break


Measured memory_bytes: 22620
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    xy = LIR(n)
    full = itertools.permutations(range(n), n)
    tmp = 0
    ans = 0
    for fu in full:
        i = 0
        bx, by = 0, 0
        for f in fu:
            if i == 0:
                bx, by = xy[f][0], xy[f][1]
                i = 1
                continue
            x, y = xy[f][0], xy[f][1]
            ans += sqrt((bx - x) ** 2 + (by - y) ** 2)
        tmp += 1
    print(ans/tmp)

    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 42348
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2 - 170;

int main() {
    int n, x;
    vector<int> v;
    cin >> n >> x;
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        v.emplace_back(k);
    }
    sort(v.begin(), v.end());
    ll sum = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        sum += v[i];
        if(sum < x) ans++;
        else {
            cout << (sum == x ? ans+1 : ans) << "\n";
            return 0;
        }
    }
    cout << (sum == x ? ans : ans-1) << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int n, m, i, j, t[2][200], temp;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d", &t[0][i], &t[1][i]);
	}
	scanf("%d", &m);
	for (i = n; i < m+n; i++){
		scanf("%d%d", &t[0][i], &t[1][i]);
	}
	
	for (i = m+n-1; i > 0; i--){
		for (j = 0; j < i; j++){
			if (t[0][j] > t[0][j+1]){
				temp = t[0][j];
				t[0][j] = t[0][j+1];
				t[0][j+1] = temp;
				temp = t[1][j];
				t[1][j] = t[1][j+1];
				t[1][j+1] = temp;
			}else if(t[0][j] == t[0][j+1]){
				if (t[1][j] > t[1][j+1]){
				temp = t[0][j];
				t[0][j] = t[0][j+1];
				t[0][j+1] = temp;
				temp = t[1][j];
				t[1][j] = t[1][j+1];
				t[1][j+1] = temp;
				}
			}
		}
	}

	for (i = 0; i < m+n; i++){
		if (t[0][i] != t[0][i+1] || t[1][i] != t[1][i+1]){
			if (t[1][i] < 10){
				printf("%d:0%d", t[0][i], t[1][i]);
			}else {
				printf("%d:%d", t[0][i], t[1][i]);
			}
			putchar(i == m + n - 1 ? '\n' : ' ');
		}
	}
	return 0;
}

Measured memory_bytes: 608
// ABC 150-D
// 2020.1.11 bal4u

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0; int c;
	c = gc();
//	do c = gc();
//	while (isspace(c));
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

int a[100005];
int N, M;

int cmp(const void *u, const void *v) { return *(int *)v - *(int *)u; }

// 配列 a 、個数 n　、　リターン値はユニーク化した配列の長さ（個数）
int uniq(int *a, int n)
{
	int i, j;
	
//	if (n == 0) return 0;
	for (i = 0, j = 1; j < n; j++) {
		while (j < n && a[j] == a[i]) j++;
		if (j < n) if (++i != j) a[i] = a[j];
	}
	return i+1;
}

int check(int X) {
	int i;
	for (i = 1; i < N; ++i) {
		if ((X-(a[i]>>1)) % a[i]) return 0;
	}
	return 1;
}

int main()
{
	int i, ans;
	
	N = in(), M = in();
	for (i = 0; i < N; ++i) a[i] = in();
	qsort(a, N, sizeof(a[0]), cmp);
	N = uniq(a, N);
//	printf("N=%d, a[0]=%d, a[1]=%d\n", N, a[0], a[1]);
	
	ans = 0;
	for (i = 0; ; i += a[0]) {
		int X = i + (a[0]>>1);
		if (X > M) break;
		if (check(X)) ++ans;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,fa[maxn],indeg[maxn];
struct AS{
    int x,dep;
    bool operator<(const AS B)const{
        return dep>B.dep;
    }
};
priority_queue<AS> Q;
vector<int> s[maxn];
inline int read(){
    int res=0,f_f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f_f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)-'0'+ch,ch=getchar();
    return res*f_f;
}
inline void toposort(){
    for (int i=1;i<=n;i++){
        if(!indeg[i]) Q.push((AS){i,0});
    }
    while(!Q.empty()){
        AS u=Q.top();
        Q.pop();
        if(u.x==1){
            printf("%d\n",u.dep);
            return;
        }
        s[fa[u.x]].push_back(u.dep),indeg[fa[u.x]]--;
        if(!indeg[fa[u.x]]){
            int now=fa[u.x],res=0,dep=s[now].size();
            for (vector<int>::iterator it=s[now].begin();it!=s[now].end();it++){
                res=max(res,*it+dep);
                dep--;
            }
            Q.push((AS){now,res});
        }
    }
}
int main(){
    n=read();
    for (int i=2;i<=n;i++){
        fa[i]=read();
        indeg[fa[i]]++;
    }
    toposort();
    return 0;
}

Measured memory_bytes: 9832
N,M = [int(i) for i in input().split()]
a = []
b = []
c = []

for i in range(N):
    x = [int(i) for i in input().split()]
    a.append(x)

for i in range(M):
    y = int(input())
    b.append(y)

for i in range(N):
    z = 0
    for j in range(M):
        z += a[i][j] * b[j]
    c.append(z)

for i in range(N):
    print(c[i])



Measured memory_bytes: 6012
#include <iostream>
#include <cstdio>
#define re register int
using namespace std;

int n;
const int mod=1000000007;

inline long long f(int x)
{
	if(x==1)
		return 1;
	return ((f(x-1)%mod)*x)%mod;
}

int main()
{
	std::scanf("%d",&n);
	
	std::printf("%lld",f(n));
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <vector>
#include <iomanip>
#include <map>
#include <deque>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SIZE = 1e6 + 10, S2 = 1e7 * 2, MOD = 1e9 + 7, INF = 1e9 * 1e9;

vector<vector<ll>> graph;
ll col[SIZE], dist[SIZE], par[SIZE];
pair<ll, ll> bst[SIZE];
bool used[SIZE];

pair<ll, ll> dfs(int v, int par = -1) {
    used[v] = 1;

    /*if (col[v] != -1) {
        if (abs(col[par] - col[v]) % 2 != abs(dist[par] - dist[v]) % 2) {
            cout << "No";
            exit(0);
        }
    }*/
    pair<ll, ll> pr = { -INF, INF };
    if (col[v] != -1) {
        pr = { col[v], col[v] };
    }
    for (auto to : graph[v]) {
        if (!used[to]) {
            dist[to] = dist[v] + 1;
            if (col[v] == -1) {
                pair<ll, ll> q = dfs(to, par);
                pr.first = max(pr.first, q.first - 1);
                pr.second = min(pr.second, q.second + 1);
            }
            else {
                pair<ll, ll> q = dfs(to, v);
                pr.first = max(pr.first, q.first - 1);
                pr.second = min(pr.second, q.second + 1);
            }
        }
    }

    bst[v] = pr;
    return pr;
}

void ch(int v, int par = -1) {
    used[v] = 1;

    if (col[v] != -1 && !(bst[v].first <= col[v] && bst[v].second >= col[v])) {
        cout << "No";
        exit(0);
    }

    bool flag = true;
    if (col[v] == -1) {
        if (bst[v].first <= col[par] - 1 && bst[v].second >= col[par] - 1) {
            col[v] = col[par] - 1;
            flag = false;
        }
        if (flag && bst[v].first <= col[par] + 1 && bst[v].second >= col[par] + 1) {
            flag = false;
            col[v] = col[par] + 1;
        }
    }
    else {
        flag = false;
    }

    if (flag) {
        cout << "No";
        exit(0);
    }
    for (auto to : graph[v]) {
        if (!used[to]) {
            ch(to, v);
        }
    }
}

int main() {
    fastInp;

    ll n;
    cin >> n;

    graph.resize(n);
    for (int i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    ll q;
    cin >> q;

    for (int i = 0; i < n; i++) col[i] = -1;
    while (q--) {
        ll p, v;
        cin >> v >> p;
        v--;

        col[v] = p;
    }

    
    for (int i = 0; i < n; i++) {
        if (col[i] != -1) {
            dfs(i);
            break;
        }
    }

    for (int i = 0; i < n; i++) used[i] = 0;
    
    for (int i = 0; i < n; i++) {
        if (col[i] != -1) {
            ch(i);
            break;
        }
    }

    cout << "Yes\n";
    for (int i = 0; i < n; i++) cout << col[i] << "\n";
    return 0;
}



Measured memory_bytes: 25600
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    int ans = (x[n-1]-x[0])*2;
    for (int i = 0; i <= n - k; i++)
    {
        int temp = x[i + k - 1] - x[i] + min(abs(x[i]), abs(x[i + k - 1]));
        ans = min(ans,temp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
N = gets.strip.to_i
A = Array.new(N)
B = gets.strip.split(' ').map(&:to_i)
(0..N-2).each do |i|
  B[i-1] < B[i] ? A[i] = B[i-1] : A[i] = B[i]
  A[i] = B[i] if i == 0
  A[i+1] = B[i] if i == N - 2
end
puts A.inject(&:+)

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main(){
    int k;
    string s;
    cin >> s >> k;
    vector<string> vec;
    for(int i=0;i<s.size();i++){
        for(int j=1;j<=k;j++){
            vec.push_back(s.substr(i,j));
        }
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    cout << vec.at(k-1) << endl;
}

Measured memory_bytes: 1660
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{
    int to,nxt;
}sq[200200];
int all=0,head[100100];

int n,m,pre[100100],siz[100100],root=0,maxson[100100],now,tax[2][100100],
    sum=0,nowlen[2][100100],tot1=0,tot0=0,maxsiz,val[100100];
bool vis[100100];
char s[100100];
ll ans=0;
vector<int> sav;

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

void add(int u,int v)
{
    all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}

void findrt(int u,int fu)
{
    int i;siz[u]=1;maxson[u]=0;
    for (i=head[u];i;i=sq[i].nxt)
    {
        int v=sq[i].to;
        if ((v==fu) || (vis[v])) continue;
        findrt(v,u);siz[u]+=siz[v];
        maxson[u]=max(maxson[u],siz[v]);
    }
    maxson[u]=max(maxson[u],now-siz[u]);
    if (maxson[u]<maxsiz) {root=u;maxsiz=maxson[u];}
}

bool insert(int u,int fu,int val)
{
    sum+=val;
    pre[u]=min(pre[fu],val-sum);
    return pre[u]+sum>=0;
}

void getdis(int u,int fu,int op)
{
    int nowv;
    if (op) nowv=val[u];else nowv=-val[u];
    if (insert(u,fu,nowv))
    {
        if (op) nowlen[1][++tot1]=sum;else nowlen[0][++tot0]=sum;
        sav.pb(sum);
    }
    int i;
    for (i=head[u];i;i=sq[i].nxt)
    {
        int v=sq[i].to;
        if ((vis[v]) || (v==fu)) continue;
        getdis(v,u,op);
    }
    sum-=nowv;
}

void calc(int u)
{
    tax[0][0]=tax[1][0]=1;int i;
    for (i=head[u];i;i=sq[i].nxt)
    {
        int v=sq[i].to;
        if (vis[v]) continue;
        tot0=0;tot1=0;
        sum=0;pre[u]=0;getdis(v,u,1);
        sum=0;pre[u]=0;getdis(v,u,0);
        rep(j,1,tot1)
            ans+=tax[0][nowlen[1][j]+val[u]];
        rep(j,1,tot0)
            ans+=tax[1][nowlen[0][j]-val[u]];
        rep(j,1,tot0) tax[0][nowlen[0][j]]++;
        rep(j,1,tot1) tax[1][nowlen[1][j]]++;
    }
    rep(i,0,(int)sav.size()-1) tax[0][sav[i]]=tax[1][sav[i]]=0;sav.clear();
}

void divide(int u)
{
    vis[u]=1;calc(u);int i;
    for (i=head[u];i;i=sq[i].nxt)
    {
        int v=sq[i].to;
        if (vis[v]) continue;
        maxsiz=maxd;now=siz[v];
        findrt(v,u);divide(root);
    }
}

int main()
{
    n=read();scanf("%s",s+1);
    rep(i,1,n)
        if (s[i]=='(') val[i]=1;else val[i]=-1;
    rep(i,1,n-1)
    {
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    maxsiz=maxd;now=n;
    findrt(1,0);divide(root);
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 12112
parseInt(x) = parse(Int,x)

function main()
  (N,M) = map(parseInt, split(readline()))
  L = zeros(Int,M)
  R = zeros(Int,M)
  for i = 1:M
    (L[i],R[i]) = map(parseInt, split(readline()))
  end
  l = maximum(L)
  r = minimum(R)
  println(max(r-l+1,0))
end

main()

Measured memory_bytes: 153044
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

LL grundy(LL a, LL k) {
	if (a < k) {
		return 0;
	}
	if (a % k == 0) {
		return a / k;
	}
	LL root = (a % k) / (a / k + 1);
	//root回まで変化させようとしてよい
	LL lim = (a % k) / (a / k + 1);
	LL tim = min(root, lim);
	if (tim <= 0)tim = 1;
	LL next = a - ((a / k) + 1);
	if (next < k) {
		return 0;
	}
	if (next % k == 0) {
		return next / k;
	}
	return grundy(a - ((a / k) + 1) * tim, k);
}

int main(void)
{
	LL N;
	cin >> N;
	LL ans = 0;
	for (int i = 0; i < N; ++i) {
		LL a, k;
		cin >> a >> k;
		ans ^= grundy(a, k);
	}
	if (ans) {
		cout << "Takahashi\n";
	}
	else {
		cout << "Aoki\n";
	}
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
char h[]="01235789";
main(){
  while(1){
    ll n;
    scanf("%lld",&n);
    if(!n) break;
    ll a=0;
    ll k=1;
    while(n>0){
      a += (k*(n%8));
      k*=10;
      n/=8;
    }
    char r[15]={};
    int i=0;
    while(a>0){
      r[i]=a%10;
      a/=10;
      ++i;
    }
    for(int j=i-1;j>-1;j--) printf("%c",h[r[j]]);
    puts("");
  }
}

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

const ll MOD = (ll)1e9 + 7;

template< typename T >
T mod_pow(T x, T n, const T &p) {
    T ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x) %= p;
        (x *= x) %= p;
        n >>= 1;
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    vector<ll> one(61);
    for (int i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        bitset<61> abit(a);
        for (int j = 0; j < 60; ++j) {
            if (abit[j]) one[j]++;
        }
    }

    ll ans = 0;
    for (int i = 0; i < 61; ++i) {
        ll x = (n - one[i]) * one[i] % MOD;
        ans = (ans + (mod_pow(2ll, (ll)i, MOD) * x) % MOD) % MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int i,k,b,n,m,s[102];
    cin>>n>>m;
    for(i=0;i<n;i++)
        cin>>s[i];
    for(k=1;k<=m;k++){
        b=-1;
        while(++b<n-1)
            if(s[b]%k>s[b+1]%k)
                swap(s[b],s[b+1]);
    }
    for(int i=0;i<n;i++)cout<<s[i]<<endl;
}

Measured memory_bytes: 1160
#!/usr/bin/env python3


def solve(xs: "List[int]"):
    for idx, x in zip(range(1, 6), xs):
        if x == 0:
            return idx


def main():
    x = list(map(int, input().split()))
    answer = solve(x)
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 8984
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  lint k, a, b; cin >> k >> a >> b;
  lint res = 1;
  if (b - a <= 1) res += k;
  else {
    if (res < a) {
      lint c = min(k, a - 1);
      res += c;
      k -= c;
    }
    res += k / 2 * (b - a);
    res += k & 1;
  }
  cout << res << '\n';
}

Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - A?C
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

char s[8];

/* subroutines */

/* main */

int main() {
  scanf("%s", s);

  if (s[1] == 'B') s[1] = 'R';
  else s[1] = 'B';

  puts(s);
  return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    int n;
    cin >> n;
    VL a(n);
    cin >> a;
    FOR(i, 0, n - 1)a[i + 1] += a[i];

    map<ll, ll> map;
    FOR(i, 0, n)map[a[i]]++;
    
    ll ans = map[0];
    for (auto m : map) {
        ll s = m.second;
        ans += s * (s - 1) / 2;
    }
    cout << ans << "\n";
}

Measured memory_bytes: 14336
N = int(input())
A = list(map(int, input().split()))
t = [0]
for i, a in enumerate(A):
    if i % 2 == 0:
        t.append(a)
    else:
        t.append(-a)
for i in range(N):
    t[i+1] += t[i]
ans = []
for i in range(1, N+1):
    if i % 2:
        ans.append(t[N] - t[i-1] - t[i-1])
    else:
        ans.append(-t[N] + t[i-1] + t[i-1])
print(*ans)

Measured memory_bytes: 17632
a=[int(input())]
for i in range(1,1000000):
    if a[i-1]%2==0:
        a.append(a[i-1]/2)
    else:
        a.append(a[i-1]*3+1)
    if a.count(a[i])==2:
        break
print(i+1)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
//size_t f = string::npos
//make pair, tuple

int dist(pair<int, int> p1, pair<int, int> p2){
      return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

int main(){
      int n,m;cin >> n >> m;
      vector<pair<int, int>> vs;
      vector<pair<int, int>> vc;
      for(int i = 0;i < n;i++){
            int x,y;cin >> x >> y;
            vs.push_back(make_pair(x, y));
      }
      for(int i = 0;i < m;i++){
            int x,y;cin >> x >> y;
            vc.push_back(make_pair(x, y));
      }
      for(int i = 0;i < n;i++){
            int currMin = 0;
            for(int j = 1;j < m;j++){
                  if(dist(vs[i], vc[j]) < dist(vs[i], vc[currMin])){
                        currMin = j;
                  }
            }
            cout << currMin + 1 << "\n";
      }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string a,b,c;
int ans1,ans2;
int main()
{
    cin>>a>>b;
    cin>>ans1>>ans2;
    cin>>c;
    if(a==c) cout<<ans1-1<<" "<<ans2;
    else cout<<ans1<<" "<<ans2-1;
    return 0;
}


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

// Function Macros:
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define setpre(n) cout << fixed << setprecision(n)

// Type / Class / Struct Definitions:
using namespace std;

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

// Constants:
const int INF = (1ll << 30) - 1;  // approx 1.07e9
const ll INFLL = 1ll << 60;       // approx 1.15e18
const int MOD = 1e9 + 7;          // 998244353
const long double EPS = 1.0e-14;

// Global Variables:

// Prototype Declarations:
int gcd(int, int);
template <class T>
inline bool chmin(T&, T);
template <class T>
inline bool chmax(T&, T);
ll modAdd(ll, ll, ll);
ll modSub(ll, ll, ll);
ll modTms(ll, ll, ll);
ll modInv(ll, ll);
ll modDiv(ll, ll, ll);
ll modPow(ll, ll, ll);

// ================ Main Loop ================
int main() {
    ll n, k;
    cin >> n >> k;
    ll l = 0, r = 0, ans = 0;
    for(int i = 0; i <= n; i++) {
        l = modAdd(l, i, MOD);
        r = modAdd(r, n - i, MOD);
        if(i >= k - 1) {
            ans = modAdd(ans, modAdd(modSub(r, l, MOD), 1, MOD), MOD);
        }
        // cout << l << " " << r << " " << ans << endl;
    }

    cout << ans << endl;
    return 0;
}
// ===========================================

// Functions:
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

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;
}
ll modAdd(ll a, ll b, ll m) {
    return (a + b) % m;
}

//引き算:a - b O(1)
ll modSub(ll a, ll b, ll m) {
    return (a > b) ? (a - b) % m : (a - b) % m + m;
}

//掛け算:a * b O(1)
ll modTms(ll a, ll b, ll m) {
    return a * b % m;
}

//逆関数
//Extended Euclid Algorithm O(log a)
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;
}

//割り算:a/b O(log b)
ll modDiv(ll a, ll b, ll m) {
    return modTms(a, modInv(b, m), m);
}

//冪乗:a^n O(log n)
ll modPow(ll a, ll n, ll m) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}


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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

int n, m;

vector<int> grids;
vector<int> diffs;

int ans = 0;

int main(void) {
  // Here your code !
  scanf("%d %d", &n, &m);

  if (n >= m) {
    printf("%d\n", 0);
    return 0;
  }

  for (int i = 0; i < m; ++i) {
    int cur;
    scanf("%d", &cur);
    grids.push_back(cur);
  }

  sort(grids.begin(), grids.end());

  for (int i = 1; i < grids.size(); ++i) {
    diffs.push_back(grids[i] - grids[i - 1]);
  }

  sort(diffs.begin(), diffs.end(), greater<int>());

  // n < m
  for (int i = n - 1; i < diffs.size(); ++i) {
    ans += diffs[i];
  }

  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using Graph = vector<vector<int>>;


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() {
    int x1,x2,x3,x4,x5;
    cin >> x1 >> x2 >> x3 >> x4 >> x5;
    int sum = 15;
    cout << 15 - x1 - x2 - x3 - x4 - x5 <<endl;

}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    string S, T;
    cin >> S >> T;
    for(int i = 0; i < S.size(); i++) {
        string one = S.substr(0, i);
        string two = S.substr(i, S.size() - i);
        if(two + one == T) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (10);   小数点以下１０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//string s = to_string(int数);
//int n = stoi(string文字列);

int main() {
  int a,b;
  cin >>a>>b;
  
  int sum = a*b+a*(a-1)/2;
  
  int eat = 10000;
  rep(i,a) {
  eat = min(eat,abs(b+i));
  }
  
  rep(i,a) {
    if(eat==abs(b+i)) eat = b+i;
  }
  
  cout << sum-eat << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<long long>cnt1(n + 3, 0), cnt2(n + 3, 0), cnt3(n + 3, 0);
    if(s[0] == 'B'){
        cnt1[0] = 1;
    }
    else if(s[0] == 'R'){
        cnt2[0] = 1;
    }
    else{
        cnt3[0] = 1;
    }
    for(int i = 1; i < n; i++){
        cnt1[i] = cnt1[i - 1];
        cnt2[i] = cnt2[i - 1];
        cnt3[i] = cnt3[i - 1];
        if(s[i] == 'B'){
            cnt1[i]++;
        }
        else if(s[i] == 'R'){
            cnt2[i]++;;
        }
        else{
            cnt3[i]++;;
        }
    }
    long long ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(s[i] != s[j]){
                if(s[i] == 'R' && s[j] == 'B'){
                    ans = ans + (cnt3[n - 1] - cnt3[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'G'){
                            ans--;
                        }
                    }
                }
                else if(s[i] == 'B' && s[j] == 'R'){
                    ans = ans + (cnt3[n - 1] - cnt3[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'G'){
                            ans--;
                        }
                    }
                }
                else if(s[i] == 'G' && s[j] == 'R'){
                    ans = ans + (cnt1[n - 1] - cnt1[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'B'){
                            ans--;
                        }
                    }
                }
                else if(s[i] == 'R' && s[j] == 'G'){
                    ans = ans + (cnt1[n - 1] - cnt1[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'B'){
                            ans--;
                        }
                    }
                }
                else if(s[i] == 'G' && s[j] == 'B'){
                    ans = ans + (cnt2[n - 1] - cnt2[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'R'){
                            ans--;
                        }
                    }
                }
                else if(s[i] == 'B' && s[j] == 'G'){
                    ans = ans + (cnt2[n - 1] - cnt2[j]);
                    if(2*j - i < n){
                        if(s[2*j - i] == 'R'){
                            ans--;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3684
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    a,b = (int(_) for _ in input().split())  
    print(max(a+b,a-b,a*b))
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(int i = 0;i < n;++i)
#define LONGINF 1000000000000000000
int main() {
	string s;
	cin >> s;
	int n = s.length();
	int ans = s.length();
	vector<int> hoge;
	int cnt = 0;
	char now = 'S';
	for (int i = 0;i < n;++i) {
		if (now != s[i]) {
			now = s[i];
			hoge.push_back(cnt);
			cnt = 1;
		}
		else {
			cnt++;
		}
	}
	if (cnt != 0) hoge.push_back(cnt);
	int now_stock = 0;
	int ppp = hoge.size() / 2;
	ppp *= 2;
	for (int i = 0;i < ppp;i += 2) {
		now_stock += hoge[i];
		if (now_stock >= hoge[i + 1]) {
			ans -= hoge[i+1] * 2;
			now_stock -= hoge[i + 1];
		}
		else {
			ans -= now_stock * 2;
			now_stock = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define inf 1000000000
#define mod 1000000007
#define eps 1e-6
#define PI atan(1) * 4
using namespace std;
int freq[100005];
int main() {
	int a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%d", &a);
	SET(freq, 0);
	for (i = 1; i <= a; i++) {
		scanf("%d", &b);
		freq[b]++;
	}
	c = 0;
	for (i = 1; i <= 100000; i++) {
		c += max(freq[i] - 1, 0);
	}
	c = (c + 1) / 2 * 2;
	printf("%d\n", a - c);
	return 0;
}

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

#include <unistd.h>
 
using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
 
 
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'

signed main() {
  fio();
  int n, k;
  cin >> n >> k;
  int r, s, p;
  cin >> r >> s >> p;
  string t;
  cin >> t;
  string ss(n, '?');
  vector<pair<int, char>> tt(3);
  tt[0] = {r, 's'};
  tt[1] = {s, 'p'};
  tt[2] = {p, 'r'};
  sort(all(tt));
  reverse(all(tt));

  ll ans = 0;
  rep (i, 3) {
    char temp = tt[i].second;
    int score = tt[i].first;
    //DEBUG(temp);
    rep (j, n) {
      if (t[j] == temp) {
        if (j < k or ss[j - k] != temp) {
          ans += score;
          ss[j] = temp;
        }
      }
    }
    //DEBUG(ss);
    //DEBUG(ans);
  }

  cout << ans << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
using namespace std;


int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> x;
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;
        x.push_back(tmp);
    }

    sort(x.begin(), x.end());

    vector<int> diff;
    for (int i = 0; i < m - 1; i++) {
        diff.push_back(x[i + 1] - x[i]);
    }

    sort(diff.rbegin(), diff.rend());

    int region = x.back() - x.front();
    int res = region;
    for (int i = 0; i < n - 1; i++) {
        if (i >= diff.size()) {
            break;
        }
        res -= diff[i];
    }
    cout << res << endl;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#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() {
  string s;
  cin >> s;
  int n = s.size();
  bool ans = n%2==1 ^ s[0]==s[n-1];
  cout << (ans?"First":"Second") << endl;
}

Measured memory_bytes: 3756
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,p,q,t;
    string s,ss;
    vector<ll>v;
    deque<ll>dq;
    cin>>s>>ss;
    t=0;
    for(int i=0;i<3;i++)
    {
        if(s[i]==ss[i]) t++;
    }
    cout<<t<<endl;
}




Measured memory_bytes: 256