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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 N, M;
	cin >> N >> M;
	vector<int64> X(M);
	REP(i, M) cin >> X[i];
	sort(all(X));
	vector<int64> D(M-1);
	int64 sum = 0;
	REP(i, M-1) D[i] = X[i+1]-X[i];
	REP(i, M-1) sum += D[i];
	sort(all(D), greater<int64>());
	REP(i, min(N-1, M-1)) sum -= D[i];
	cout << sum << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll          long long
#define vl          vector<ll>
#define vi          vector<int>
#define pi          pair<int,int>
#define pl          pair<ll,ll>
#define all(a)      a.begin(),a.end()
#define mem(a,x)    memset(a,x,sizeof(a))
#define pb          push_back
#define mp          make_pair
#define F           first
#define S           second
#define trace(x)    cerr<<#x<<" : "<<x<<endl;
#define trace2(x,y) cerr<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl;
#define trace3(x,y,z) cerr<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl;
#define fast_io 	std::ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;


int main()
{
	fast_io;
	int x;
	cin>>x;
	vi a;
	for(int i=1;i<=1000;i++)
	{
		for(int j=2;j<=1000;j++)
		{
			int temp=pow(i,j);
			if(temp>x)break;
			if(temp<=x)a.pb(temp);
		}
	}
	int ans=*max_element(all(a));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 640
import java.io.IOException;
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {
    private static final StringBuilder builder = new StringBuilder();
    public static void main(String[] args) {
        int k = readInt();
        int n = 7;
        for (int i = 0; i < k; i++) {
            if (n % k == 0) {
                System.out.print(i + 1);
                return;
            }
            
            n = (n % k) * 10 + 7;
        }

        System.out.print(-1);

    }

    private static void read() {
        builder.setLength(0);
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) {
                    break;
                } else {
                    builder.appendCodePoint(b);
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static int readInt() {
        read();
        return Integer.parseInt(builder.toString());
    }

    private static int readInt(int radix) {
        read();
        return Integer.parseInt(builder.toString(), radix);
    }

    private static long readLong() {
        read();
        return Long.parseLong(builder.toString());
    }

    private static long readLong(int radix) {
        read();
        return Long.parseLong(builder.toString(), radix);
    }

    private static BigInteger readBigInteger() {
        read();
        return new BigInteger(builder.toString());
    }

    private static BigInteger readBigInteger(int radix) {
        read();
        return new BigInteger(builder.toString(), radix);
    }

    private static double readDouble() {
        read();
        return Double.parseDouble(builder.toString());
    }

    private static BigDecimal readBigDecimal() {
        read();
        return new BigDecimal(builder.toString());
    }

    private static float readFloat() {
        read();
        return Float.parseFloat(builder.toString());
    }

    private static void skipLine() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == '\n' || b == -1) {
                    break;
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static void skip() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) break;
            } catch (IOException e) {
                break;
            }
        }
    }

}


Measured memory_bytes: 32340
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long a[n+1];
    for(int i=1;i<=n;i++)
    cin>>a[i];
    long long dp[n+1];
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for(int i=3;i<=n;i++){
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
from math import isinf

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

m = [None, 2, 5, 5, 4, 5, 6, 3, 7, 6]

# 最大何桁作れるか

# dp[i] := ちょうど i 本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
# dp[i + 1] = max(dp[i - m[j]] + 1) for all j in A

dp = [float('-inf') for _ in range(N + 1)]
dp[0] = 0

for i in range(1, N + 1):
    for num in A:
        if i - m[num] >= 0:
            dp[i] = max(dp[i], dp[i - m[num]] + 1)

matches = N
ans = ''
for _ in range(dp[N]):
    for a in A:
        if matches - m[a] < 0:
            continue
        if dp[matches - m[a]] == dp[matches] - 1:
            matches -= m[a]
            ans += str(a)
            break

print(ans)


Measured memory_bytes: 3316
# Modified from https://atcoder.jp/contests/abc179/submissions/16893796

import sys

input = sys.stdin.buffer.readline

n, q = map(int, input().split())


class SegmentTree:
    ele = 10 ** 10
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, x)
        yoko.update(temp, now)
        ans += max(0, temp - 1)
    else:
        temp = yoko.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, x)
        tate.update(temp, now)
        ans += max(0, temp - 1)
    # print("a", i, temp - 1)
print((n - 2) ** 2 - ans)


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

using ll = long long int;

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

string s;
string t;

int main(void) {
  // Here your code !
  cin >> s;
  cin >> t;

  int ans = 0;

  for (int i = 0; i < s.size(); ++i) {
    ans += (s[i] == t[i]) ? 1 : 0;
  }

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

  return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	od, ev := 0, 0
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a)
		if a%2 == 0 {
			ev++
		} else {
			od++
		}
	}
	ev += od / 2
	od %= 2
	if ev > 1 {
		ev = 1
	}
	if ev == 0 {
		fmt.Println("YES")
		return
	}
	if od == 0 && ev == 1 {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
string s;
int ans=0;
int tot=0;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='S')
		{
			ans=max(tot,ans);
			tot=0;
		}
		else
		{
			tot++;
		}
	}
	ans = max(ans, tot);
	printf("%d",ans);
}

Measured memory_bytes: 3688
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        int count = 0;
        int[] m = new int[N+1];
        for(int i=0;i<N; i++){
            a[i] = sc.nextInt();
            if(a[i]>N) count++;
            else{
                m[a[i]]++;
            }
        }
        for(int i=1;i<=N;i++){
            if(m[i]==0) continue;
            if(m[i]<i) count += m[i];
            else count += m[i]-i;
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 51136
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int N;
  double sum = 0;
  cin >> N;
  vector <string> x(N);
  vector <double> u(N);
  rep(i, N)
    cin >> u[i] >> x[i];

  rep(i, N)
  {
    if(x[i] == "BTC")
        u[i] *= 380000.0;
    sum += u[i];
  }
  cout << setprecision(10) << sum << endl;

  return 0;  

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int main() {
  double eps = 0.001;
  ll A;
  double B;
  cin >> A >> B;
  cout << A*(ll)(100*B+eps)/100 << endl;
}

Measured memory_bytes: 3700
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N_MAX 100000

int main(void)
{
    char s[N_MAX];
    int l=0;

    scanf("%s",s);
    l = strlen(s);

    if (s[0] == s[l-1] && l%2) {
        printf("Second");
    } else if (s[0] == s[l-1] && !(l%2)) {
        printf("First");
    } else if (s[0] != s[l-1] && l%2) {
        printf("First");
    } else {
        printf("Second");
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			int p = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			if(n == 0) break;

			ArrayList<Double> t = new ArrayList<Double>();
			for(int i=0;i<n;i++){
				t.add(sc.nextDouble());
			}
			Collections.sort(t);

			double[][] map = new double[m+1][m+1];
			for(int i=0;i<p;i++){
				int from = sc.nextInt();
				int to = sc.nextInt();
				double cost = sc.nextDouble();
				map[from][to] = map[to][from] = cost;
			}

			PriorityQueue<State> open = new PriorityQueue<State>();
			HashSet<State> closed = new HashSet<State>();
			State ans = null;
			open.add(new State(a,0,t));

			while(!open.isEmpty()){
				State st = open.poll();
				if(closed.contains(st)) continue;
				closed.add(st);

				if(st.n == b){
					ans = st;
					break;
				}

				open.addAll(st.nexts(map));
			}

			System.out.println(ans==null ? "Impossible" : ans.cost);
		}
	}
}

class State implements Comparable<State>{
	int n;
	double cost;
	ArrayList<Double> t;

	State(int n,double cost,ArrayList<Double> t){
		this.n = n;
		this.cost = cost;
		this.t = t;
	}

	List<State> nexts(double[][] map){
		int m = map.length;
		List<State> sts = new ArrayList<State>();

		for(int i=1;i<m;i++){
			if(map[n][i] > 0){
				for(int j=0;j<t.size();j++){
					ArrayList<Double> copy = new ArrayList<Double>(t);
					double v = copy.remove(j);
					sts.add(new State(i,cost+map[n][i]/v,copy));
				}
			}
		}

		return sts;
	}

	public int compareTo(State st){
		if(cost < st.cost) return -1;
		if(cost > st.cost) return 1;
		return 0;
	}

	public boolean equals(Object o){
		State st = (State)o;
		return n == st.n && t.equals(st.t);
	}

	public int hashCode(){
		return n + t.hashCode();
	}
}

Measured memory_bytes: 25000
N = int(input())
S = list(input())

rightWhite = []
leftBlack = []

cntB = 0
cntW = 0

for i in range(N):
    rightWhite.append(cntW)
    leftBlack.append(cntB)
    if (S[i] == "#"):
        cntB += 1

    if (S[-i-1] == "."):
        cntW += 1

rightWhite = list(reversed(rightWhite))

ans = N

for i in range(N):
    ans = min(rightWhite[i] + leftBlack[i], ans)

print(ans)


Measured memory_bytes: 15720
#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()
{
  int x, n;
  cin >> x >> n;
  set<int> p;
  rep(i, n)
  {
    int a;
    cin >> a;
    p.insert(a);
  }
  int ans = x;
  int mindif = 1e9;
  rep(i, 150)
  {
    if (n == 0)
      break;
    int dif = abs(x - i);
    if (p.count(i) == 0 && dif < mindif)
    {
      ans = i;
      mindif = dif;
    }
  }
  cout << ans << endl;
  return 0;
}

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

int Find(int n) {
  int sum = 0;
  while(n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main() {
  int N;
  cin >> N;
  int min = 0;
  int num;
  min = N;
  for (int a = 1; a < N; a++) {
      int b = N - a;
      num = Find(a) + Find(b);
      if (num < min) {
        min = num;
      }
  }
  cout << min << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
typedef long long int ll;
int main() {
	ll N, C, s, t, c, ma = 0;
	bool f[31][100010] = {};
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> s >> t >> c;
		ma = max(ma, t);
		for (int j = s; j <= t; j++)f[c][j] = 1;
	}
	ll ans = 0, cnt = 0;
	for (int i = 1; i <= ma; i++) {
		for (int j = 1; j <= C; j++) if (f[j][i])cnt++;
		ans = max(ans, cnt);
		cnt = 0;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3328
fn main() {
    let scan = std::io::stdin();
    let mut line = String::new();
    let _ = scan.read_line(&mut line);
    let vec: Vec<&str> = line.split_whitespace().collect();
    let n: i32 = vec[0].parse().unwrap();
    let total: i32 = vec[1].parse().unwrap();

    let mut num_of_10000: i32 = -1;
    let mut num_of_5000: i32 = -1;
    let mut num_of_1000: i32 = -1;

    for x in 0..n+1{
        for y in 0..n-x+1{
            if 10000 * x + 5000 * y + 1000 * (n-x-y) == total{
                num_of_10000 = x;
                num_of_5000 = y;
                num_of_1000 = n-x-y;
            }
        }
    }

    print!("{} ",num_of_10000);
    print!("{} ",num_of_5000);
    println!("{}",num_of_1000);

    // if y > 10000 * num_of_10000 {
    //     num_of_10000 = -1;
    //     num_of_5000 = -1;
    //     num_of_1000 = -1;
    // }else{
    //     while y < 10000 * num_of_10000{
    //         num_of_10000 = num_of_10000 - 1;
    //     }
    //     total = 10000 * num_of_10000;
    //     if y != total {
    //         num_of_5000 = n - num_of_10000;
    //         total = num_of_10000 * 10000 + num_of_5000 * 5000;
    //         while y < total{
    //             num_of_5000 = num_of_5000 - 1;
    //             total = total - 5000;
    //         }
    //
    //         if y != total {
    //             num_of_1000 = n - num_of_10000 - num_of_5000;
    //             total = num_of_10000 * 10000 + num_of_5000 * 5000 + num_of_1000 * 1000;
    //             while y < total{
    //                 num_of_1000 = num_of_1000 - 1;
    //                 total = total - 1000;
    //             }
    //         }
    //
    //     }
    //
    //     if y != total{
    //         num_of_10000 = -1;
    //         num_of_5000 = -1;
    //         num_of_1000 = -1;
    //     }
    // }

}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define forin(x,y) for(ll i=x;i<y;i++)
#define vii vector<ll>
#define pii  pair<ll,ll>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define inf 1e17
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vii seg;
ll upd_tree(ll ind,ll tl ,ll tr,ll pos,ll val)
{
    if(pos<tl || pos> tr)   return -1;
    if(tl == tr && pos == tl)
    {
        seg[ind] = val;
        return seg[ind];
    }
    ll tm = (tl+tr)/2;
    if(pos<= tm )
    {
        upd_tree(2*ind,tl,tm,pos,val);
    }
    else if(pos>tm)
    {
        upd_tree(2*ind+1,tm+1,tr,pos,val);
    }
    seg[ind] =  max(seg[2*ind], seg[2*ind+1]);
    return seg[ind];
}
ll ret_tree(ll ind,ll tl,ll tr,ll l ,ll r)
{
    if(l>r || tl>tr)    return 0;
    if(tl == l && tr == r)
    {   
        return seg[ind];
    }
    else
    {
        ll tm = (tl+tr)/2;
        return max(ret_tree(2*ind,tl,tm,l,min(tm,r)),ret_tree(2*ind+1,tm+1,tr,max(tm+1,l),r));
    }
}

int main()
{
    ios::sync_with_stdio(false);    cin.tie(0);     cout.tie(0);
    ll n;   cin>>n;
    vii h(n),a(n),dp(n+1,0);
    forin(0,n)
    {
        cin>>h[i];
    }
    forin(0,n)
    {
        cin>>a[i];
    }
    ll base = 1;
    while(base<n)
    {
        base *=2;
    }
    seg.resize(2*base+1,0);
    for(ll flower=0;flower<n;flower++)
    {
        dp[h[flower]]  = ret_tree(1,0,n-1,0,h[flower]-1) + a[flower];
        upd_tree(1,0,n-1,h[flower]-1,dp[h[flower]]);
    }
    ll ans=0;
    
    for(auto i:dp)
    {
        ans = max(ans,i);
    }
    cout<<ans<<endl;
}


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

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

    int num_ver = 0;

    for (auto i = 0; i < 21; i++)
    {
        if(pow(2,i) > l){
            num_ver = i ;
            break;
        }
    }

    int num_edge = (num_ver-1)*2;
    vector<int> edge(num_ver, -1);

    for (auto i = num_ver-1; i >= 0; i--)
    {
        if(l-pow(2, i) >= pow(2, num_ver-1)){
            edge[i] = l - pow(2, i);
            l -= pow(2, i);
        }
    }

    for (auto i = 0; i < edge.size(); i++)
    {
        if(edge[i] != -1){
            num_edge += 1;
        }
    }

    cout << num_ver << " " << num_edge << endl;
    for (auto i = 1; i < num_ver; i++)
    {
        cout << i << " " <<  i + 1 << " " << " " << 0 << endl;
        cout << i << " " <<  i + 1 << " " << " " << pow(2, i-1) << endl;
    }
    for (auto i = 0; i < edge.size(); i++)
    {
        if(edge[i] != -1){
            cout << i + 1 << " " << num_ver << " " << edge[i] << endl;
        }
    }
}

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

using static Input;
using static Util;
class Program
{
    static int A,B,C,K;

    static void INPUT()
    {
        A = NextInt();
        B = NextInt();
        C = NextInt();
        K = NextInt();
    }

    static void OUT()
    {   
        var a = Math.Min(A, K);
        K -= a;
        var b = Math.Min(B, K);
        K -= b;
        var c = Math.Min(C, K);

        Console.WriteLine(a - c);
    }
    static void Main(string[] args)
    {
#if DEBUG  
        //TESTINPUT();
        INPUT();

#else
        INPUT();
#endif
        OUT();
    }

    static void TESTINPUT()
    {
    }

}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

class Util
{

}




Measured memory_bytes: 17928
from bisect import bisect_left


def run():
    n = int(input())
    a = [int(x) for x in input().split()]
    assert(n == len(a))

    q = int(input())
    for _ in range(q):
        k = int(input())
        i = bisect_left(a, k)
        print(i)


if __name__ == '__main__':
    run()



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

int main(){
  string s; cin >>s;
  ll ans = 0;
  int cnt = 0;
  int n = s.size();
  rep(i,n){
    if(s[i]=='B') cnt++;
    else ans += cnt;
  }
  cout << ans << endl;
  return 0; 
}

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

minimum = min(X)
maximum = max(X)

def shohi(zahyo, shukai):
  return pow(zahyo - shukai, 2)

saisho = None
for i in range(minimum, maximum + 1):
  ret = sum(map(lambda zahyo: shohi(zahyo, i), X))
  saisho = ret if saisho is None or ret < saisho else saisho

print(saisho)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define outl(x) cout<< (x) << '\n'
#define outl2(x,y) cout<< (x) << ' ' << (y) << '\n'
using pii = pair<int,int>;
using ll = long long;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
static constexpr int INF = 0x3f3f3f3f;


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

    int N, T;
    int ans = INF;
    cin >> N >> T;
    rep(i, N) {
        int c, t;
        cin >> c >> t;
        if (t <= T) {
            chmin(ans, c);
        }
    }

    if (ans < INF)
        outl(ans);
    else outl("TLE");

    return 0;
}



Measured memory_bytes: 256
import itertools

N = int(input())

tbl = [0]*N

for x in range(1,N):
    for y in range(1,N):
        for z in range(1,N):
            p = x*x + y*y + z*z + x*y + y*z + z*x
            if p > N:
                break
            tbl[p-1] += 1

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


Measured memory_bytes: 73924
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fast()    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

ll knapsack(ll wt[],ll val[],ll w,ll n)
{
	ll K[n+1][w+1];
	
	 for (int i = 0; i <= n; i++) 
   { 
       for (int j = 0; j <= w; j++) 
       { 
           if (i==0 || j==0) 
               K[i][j] = 0; 
           else if (wt[i-1] <= j) 
                 K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j]); 
           else
                 K[i][j] = K[i-1][j]; 
       } 
   } 
  
   return K[n][w]; 
} 

 
 int main()
 {
 	ll n,w;
 	cin>>n>>w;
 	ll wt[n],val[n];
 	for(int i=0;i<n;i++)
 	cin>>wt[i]>>val[i];
 	
 	cout<<knapsack(wt,val,w,n);
 	
	 }

Measured memory_bytes: 79104
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define INF 1e9

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	int n;
	cin >> n;
	vi cou(26, INF);
	rep(i, 0, n) {
		string s;
		cin >> s;
		rep(j, 0, 26) {
			int a = count(all(s), 'a' + j);
			cou[j] = min(cou[j], a);
		}
	}
	string ans;
	rep(i, 0, 26) {
		char x = 'a' + i;
		rep(j, 0, cou[i]) {
			ans += x;
		}
	}
	cout << ans << endl;
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define N_DIGIT 40
i64 A, B;

int main() {
    cin >> A >> B;
    if (A == B) {
        cout << A << endl;
        return 0;
    }

    i64 ans = 0;
    i64 p = 1;
    auto f = [&](i64 x, i64 p, i64 n) {
        x++;
        i64 k = x / p;
        if ((x >> n) & 1) {
            return (k / 2) * p + x % p;
        } else {
            return (k / 2) * p;
        }
    };

    // assert(f(0, 1 << 0, 0) == 0);
    // assert(f(1, 1 << 0, 0) == 1);
    // assert(f(3, 1 << 1, 1) == 2);
    // assert(f(4, 1 << 1, 1) == 2);
    // assert(f(10, 1 << 3, 3) == 3);
    // assert(f(12, 1 << 3, 3) == 5);

    REP(i, N_DIGIT + 1) {
        i64 n_one = f(B, p, i) - (A == 0 ? 0 : f(A - 1, p, i));
        ans += (n_one % 2) * p;
        p *= 2;
    }
    cout << ans << endl;

    return 0;
}

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

int main()
{
	int n;
	cin>>n;
	vector<ll>a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	ll dp[n];
	dp[0]=0;
	dp[1]=abs(a[1]-a[0]);
	for(int i=2;i<n;i++){
		dp[i]=min((dp[i-1]+abs(a[i]-a[i-1])),(dp[i-2]+abs(a[i]-a[i-2])));
	}
	cout<<dp[n-1]<<endl;
}

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

int main() {
    char str[1024],b,tmp[]="w kstnhmyr";
    int len,i,s;
    
    scanf("%s",str);
    len = strlen(str);
    
    for(i=0;i<len;i+=2){
        s = str[i]-'0';
        b = str[i+1];
        if (s==0 && b =='U') printf("nn");
        else{
            if(s!=1) printf("%c",tmp[s]);
            if(b=='T') printf("a");
            else if(b=='L') printf("i");
            else if(b=='U') printf("u");
            else if(b=='R') printf("e");
            else if(b=='D') printf("o");
        }
    }printf("\n");
    return 0;
}


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

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());



map<string,bool> ima;

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    int res = 0;
    cin >> n;
    while(n -- ){
        string x;
        cin >> x;
        if(ima.find(x) == ima.end()){
            ima[x] = 1;
            res++;
        }
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

//ABC079-Dの問題

const long long inf = 1LL << 62;

void warshall_floyd(int n, vector<vector<long long>> &d) {
	for (int k = 0; k < n; k++) {       // 経由する頂点
		for (int i = 0; i < n; i++) {    // 始点
			if (d[i][k] == inf) { continue; }
			for (int j = 0; j < n; j++) {  // 終点
				if (d[k][j] == inf) { continue; }
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

int main() {

	int v, e; //頂点数、エッジ数
	cin >> v >> e;

	//10までの隣接行列を読み込む
	//この問題では有向きグラフG[始点][終点]
	vector<vector<long long>> G(v, vector<long long>(v, inf));
	int s, t, d;
	for (int i = 0; i < e; i++) {
		cin >> s >> t >> d;
		G[s][t] = d;
	}

	for (int i = 0; i < v; i++) {
		G[i][i] = 0; //自分の場合は0にする（ループしない）
	}

	warshall_floyd(v, G);

	//こっからはこの問題専用。
	for (int i = 0; i < v; i++) {
		if (G[i][i] != 0) {
			cout << "NEGATIVE CYCLE" << endl; //この問題では負の閉路ははじく
			return 0;
		}
	}

	for (int i = 0; i < v; i++) {
		int j;
		for (j = 0; j < v - 1; j++) {
			if (G[i][j] != inf) {
				cout << G[i][j] << " ";
			}
			else { 
				cout << "INF" << " ";
			}
		}
		if (G[i][j] != inf) {
			cout << G[i][j] << endl;
		}
		else {
			cout << "INF" << endl;
		}
	}

	return 0;

}


Measured memory_bytes: 3180
k,n = map(int,input().split())
A = list(map(int, input().split()))
max_L = 0
max_R = 0
left = 0
right = 0
for i in range(n):
  d = {}
  if i-1 < 0:
    d['left'] = k - A[n-1] + A[i]
    d['right'] = A[i + 1] - A[i]
  elif i + 1 > n-1:
    d['left'] = A[i] - A[i-1]
    d['right'] = k - A[i] + A[0]
  else:
    d['left'] = A[i] - A[i-1]
    d['right'] = A[i + 1] - A[i]
    
  if max_L < d['left']:
    max_L = d['left']
  if max_R < d['right']:
    max_R = d['right']

  right += d['right']
  left += d['left']
  
if right - max_R < left - max_L:
  print(right - max_R)
else:
  print(left - max_L)


Measured memory_bytes: 26444
import java.lang.Character.Subset;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);
        int a =scan.nextInt();
        int b = scan.nextInt();
        int a_sum,b_sum;
        a_sum=a;
        b_sum=b;
        int tmp,j;
        for(int i=0;i<b-1;i++){
            a_sum*=10;
            a_sum+=a;
        }
        for(int i=0;i<a-1;i++){
            b_sum*=10;
            b_sum+=b;
        }
        if(a>=b){
            System.out.println(b_sum);
        }
        else System.out.println(a_sum);
    }
}

Measured memory_bytes: 21588
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n;
		String[] name = new String[10000];
		int[] p = new int[10000];
		int[] q = new int[10000];
		int[] r = new int[10000];
		while ((n = in.nextInt()) != 0) {
			for (int i = 0; i < n; i++) {
				name[i] = in.next();
				p[i] = in.nextInt();
				q[i] = in.nextInt();
				r[i] = in.nextInt();
			}
			int P = in.nextInt();
			int Q = in.nextInt();
			int R = in.nextInt();
			int C = in.nextInt();
			boolean isNA = true;
			for (int i = 0; i < n; i++) {
				if (p[i] <= P && q[i] <= Q && r[i] <= R
						&& (p[i] + r[i]) * 4 + q[i] * 9 <= C) {
					System.out.println(name[i]);
					isNA = isNA && false;
				}
			}
			if (isNA) {
				System.out.println("NA");
			}
		}
	}
}

Measured memory_bytes: 64272
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int h[110000] = {}, dp[110000] = {};
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; i++)
    {
        dp[i] = (abs(h[i] - h[i - 1]) + dp[i - 1] < abs(h[i] - h[i - 2]) + dp[i - 2] ? abs(h[i] - h[i - 1]) + dp[i - 1] : abs(h[i] - h[i - 2]) + dp[i - 2]);
    }
    cout << dp[n - 1] << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
class Shop{
  public:
    int cost;
    int num;
  Shop(int a, int b){
    cost = a;
    num = b;
  }
  bool operator<(const Shop &another) const
  {
    return cost < another.cost;
  };
};
int main(){
  double N,M,m = 0;
  long long ans = 0;
  cin >> N >> M;
  vector<Shop> shopList;
  int tempA, tempB;
  for(int n=0;n<N;n++){
    cin >> tempA >> tempB;
    shopList.push_back(Shop(tempA, tempB));
  }
  std::sort(shopList.begin(),shopList.end());
  for(int n=0;n<N;n++){
    //cout << shopList[n].cost << " "<<shopList[n].num << endl;
    int buy = shopList[n].num;
    if(m + buy > M){
      buy = M - m;
      ans += buy * (long long)shopList[n].cost;
      break;
    }
    m += buy;
    ans += buy * (long long)shopList[n].cost;
  }

  cout << ans << endl;
}

Measured memory_bytes: 1400
#include "bits/stdc++.h"
using namespace std;

int main(void) {
    int N, K;
    cin >> N >> K;
    int c = 0;
    if (N % 2 == 0) {
        c = N / 2;
    }
    else {
        c = N / 2 + 1;
    }
    if (c >= K) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <map>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 99999999

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef map<int,Edges> Graph;

void shortestPath(Graph &g, int s,
    map<int,Weight> &dist, map<int,int> &prev) {
  int n = g.size();
  for(auto &f:g)dist[f.first]=INF; dist[s] = 0;
  priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
  for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
    Edge e = Q.top(); Q.pop();
    if (prev.find(e.dst) != prev.end()) continue;
    prev[e.dst] = e.src;
    for(auto &f:g[e.dst]) {
      if (dist[f.dst] > e.weight+f.weight) {
        dist[f.dst] = e.weight+f.weight;
        Q.push(Edge(f.src, f.dst, e.weight+f.weight));
      }
    }
  }
}

char buf[101];
int W;
int coor(int x,int y){return (y)*(W*2+2)+x;}
int main(){
	int H,N,X1,Y1,X2,Y2;
	scanf("%d%d%d%d%d%d%d",&W,&H,&N,&X1,&Y1,&X2,&Y2);
	X1=coor(X1*2,Y1*2),X2=coor(X2*2,Y2*2);
	vector<vector<int> >m(H*2+1);
	for(auto &&e:m)e.resize(W*2+1);
	for(int i=0;i<N;i++){
		int x,y,t,l;
		scanf("%d%d%d%s",&x,&y,&t,buf);
		l=strlen(buf);
		x=2*x+1,y=2*y+1;
		for(int j=0;j<t;j++){
			for(int k=0;k<l;k++){
				int c=buf[k];
				if(c=='L'&&1<x)m[y][x-1]++,x-=2;
				if(c=='U'&&1<y)m[y-1][x]++,y-=2;
				if(c=='R'&&x<W*2-1)m[y][x+1]++,x+=2;
				if(c=='D'&&y<H*2-1)m[y+1][x]++,y+=2;
			}
		}
	}
	Graph g;
	for(int h=0;h<=H*2;h+=2)for(int w=0;w<=W*2;w+=2){
		int a=coor(w,h),b;
		if(h<H*2)b=coor(w,h+2),g[a].push_back(Edge(a,b,m[h+1][w])),g[b].push_back(Edge(b,a,m[h+1][w]));
		if(w<W*2)b=coor(w+2,h),g[a].push_back(Edge(a,b,m[h][w+1])),g[b].push_back(Edge(b,a,m[h][w+1]));
	}
	map<int,Weight> dist;
	map<int,int> prev;
	shortestPath(g,X1,dist,prev);
	printf("%d\n",dist[X2]);
}

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

typedef ostringstream OSS; typedef istringstream ISS;
typedef long long LL;
typedef pair<int, int> PII;  typedef pair<LL, LL> PLL;
typedef vector<int>    VI;   typedef vector<VI>   VVI;   typedef vector<VVI>   VVVI;
typedef vector<LL>     VLL;  typedef vector<VLL>  VVLL;  typedef vector<VVLL>  VVVLL;
typedef vector<double> VD;   typedef vector<VD>   VVD;   typedef vector<VVD>   VVVD;
typedef vector<string> VS;   typedef vector<VS>   VVS;   typedef vector<VVS>   VVVS;
typedef vector<bool>   VB;   typedef vector<VB>   VVB;   typedef vector<VVB>   VVVB;
typedef vector<PII>    VPII; typedef vector<VPII> VVPII; typedef vector<VVPII> VVVPII;
typedef vector<PLL>    VPLL; typedef vector<VPLL> VVPLL; typedef vector<VVPLL> VVVPLL;

typedef unsigned int  UI;
typedef vector<UI>    VUI;
typedef vector<VUI>   VVUI;

#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x)  (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define RANGEBOX(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define RANGE(x, l, r) ((l) <= (x) && (x) <= (r))
#define rep(i, N)  for (int i = 0; i < (int)(N); i++)
#define rrep(i, N) for (int i = N - 1; i >= 0; i--)
#define REP(i, init, N)  for (int i = (init); i < (int)(N); i++)
#define RREP(i, N, last) for (int i = (init - 1); i >= last; i--)
#define MAXUD(orig, target) orig = max(orig, target)
#define MINUD(orig, target) orig = min(orig, target)
#define DUMP(x) cerr << #x << " = " << (x) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a)   { OSS oss; oss << a; return oss.str(); };

template<typename T=int> inline void dump(vector<T> vs, bool ent=false) { rep(i, vs.size()) cout << vs[i] << (i+1==vs.size() ? '\n' : ' '); if (ent) cout << endl; }
template<typename T = int> inline void dump(vector<vector<T>> vs, bool ent=false) { rep(i, vs.size()) dump<T>(vs[i]); if (ent) cout << endl; }

const int    INF  = 0x3f3f3f3f;
const LL     INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int    DX[] = {1,  0, -1, 0};
const int    DY[] = {0, -1,  0, 1};
const double EPS  = 1e-12;
// const double PI   = acos(-1.0);

template<typename T = int> inline T in() { T x; cin >> x; return x; }
template<typename T = int> inline vector<T> in(int n) { vector<T> xs(n); rep(i, n) cin >> xs[i]; return xs; }
template<typename T = int> inline vector<vector<T>> in(int n, int m) { vector<vector<T>> xs(n, vector<T>(m)); rep(i, n) rep(j, m) cin >> xs[i][j]; return xs; }

int main(void) {
    LL a = 1, b = 1;
    int n = in();
    rep(i, n) {
        LL x, y;
        cin >> x >> y;
        LL p = (a + x - 1) / x;
        LL q = (b + y - 1) / y;
        LL k = max(p, q);
        a = k * x;
        b = k * y;
    }

    cout << a + b << endl;

    return 0;
}



Measured memory_bytes: 256
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
#include <utility>

template <typename E, typename H>
struct DualSegmentTree{
private:
  // using H = std::function<E(E,E)>;
  int n, height;
  H h;
  const E ei;
  std::vector<E> laz;
  void propagate(int k){
    if(laz[k] == ei) return;
    if(k >= n){
      return;
    }
    laz[k<<1|0] = h(laz[k<<1|0],laz[k]);
    laz[k<<1|1] = h(laz[k<<1|1],laz[k]);
    laz[k] = ei;
  }
  void thrust(int k){
    for(int i = height; i >= 0; --i)
      propagate(k>>i);
  }
public:
  DualSegmentTree(H h, E ei) :
    h(h), ei(ei) {}
  void build(int n_){
    n = n_;
    height = 2;
    while(n_ >>= 1) ++height;
    laz.assign(2*n,ei);
  }
  void update(int l_, int r_, E x){
    if(l_ >= r_) return;
    l_ += n, r_ += n;
    thrust(l_);
    thrust(r_-1);
    for(int l = l_, r = r_;l < r; l >>= 1, r >>= 1){
      if(l&1) laz[l] = h(laz[l],x), ++l;
      if(r&1) --r, laz[r] = h(laz[r],x);
    }
  }
  E operator[](int i){
    assert(i >= 0 and i < n);
    i += n;
    E ret = laz[i];
    while(i > 0){
      i /= 2;
      ret = h(ret,laz[i]);
    }
    return ret;
  }
};


#include <iostream>
#include <vector>
using namespace std;

int main(){
  long long N, Q;
  cin >> N >> Q;
  auto g = [](int a, int b){
    return min(a,b);
  };
  
  const int INF = 1e9;
  DualSegmentTree row(g,N-2), col(g,N-2);

  row.build(N-2);
  col.build(N-2);
  long long ans = (N-2)*(N-2);
  int rmin = N-2, cmin = N-2;
  for(int i = 0; i < Q; ++i){
    int t, x;
    cin >> t >> x;
    x -= 2;
    if(t == 1){
      int d = col[x];
      ans -= d;
      if(x < cmin){
        row.update(0,d,x);
        cmin = x;
      }
    }else{
      int d = row[x];
      ans -= d;
      if(x < rmin){
        col.update(0,d,x);
        rmin = x;
      }
    }
    // for(int i = 0; i < N-2; ++i)
    //   cerr << row[i] << " ";
    // cerr << endl;
    // for(int i = 0; i < N-2; ++i)
    //   cerr << col[i] << " ";
    // cerr << endl;
    // cerr << ans << endl;
  }
  cout << ans << endl;
}


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

l = [0]
for i in range(1,len(a)):
    l.append(a[i - 1] * 2 - l[i - 1])
dam = [sum(a) - sum(l)]

for i in a[:-1]:
    dam.append((i - dam[-1] // 2) * 2)
print(*dam)

Measured memory_bytes: 71652
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//---------------------------------------
string shuffle(string str, int h);
//---------------------------------------

int main(void)
{
	while(true){
		string str;
		cin >> str;  //??¢???????????????????????????
	
		if(str == "-"){  //??\?????????
			break;
		}
		
		int num_shuffle;
		cin >> num_shuffle;  //?????£??????????????°?????????
		
		for(int i = 0; i < num_shuffle; i++){
			int num_h;  //?????????h???????????????????????£?????????
			cin >> num_h;
			str = shuffle(str, num_h); //?????£?????????
		}
		cout << str << endl;  //?????£?????????????????????????????????
	}
}

//---------------------------------------
string shuffle(string str, int h)
{
	string copy_str = str;
	
	for(int i = 0; i < h; i++){  //?????£??????????????????????????????????????£?????????
		copy_str.push_back(str[i]);
	}
	
	for(int i = 0; i < str.size(); i++){  //???????????????
		copy_str[i] = copy_str[h+i];
	}
	for(int i = 0; i < h; i++){
		copy_str.pop_back();   //?????????1???????¶????
	}
	
	return copy_str;
	
}

Measured memory_bytes: 3204
// created by mtnshh
 
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"--------------------------"<<endl; 
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second
 
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"
 
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e18;
#define PI 3.14159265
 
const ll N = 100005;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n;
    cin >> n;
    if(n >= 30){
    	cout << "Yes" << endl;
    }
    else{
    	cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1'000'000'007;
const ll inf=1'000'000'000'000'000'00;
const int INF=1'000'000'000;
const double EPS=1e-10;
const double PI=acos(-1);

int dp[50][500][500];

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	int n,ma,mb;
	cin>>n>>ma>>mb;
	vector<int> a(n),b(n),c(n);
	rep(i,n){
		cin>>a[i]>>b[i]>>c[i];
	}
	rep(i,50)rep(j,500)rep(k,500) dp[i][j][k]=INF;
	dp[0][0][0]=0;
	rep(i,n)rep(j,500)rep(k,500){
		if(dp[i][j][k]==INF) continue;
		chmin(dp[i+1][j][k],dp[i][j][k]);
		chmin(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
	}
	int ans=INF;
	FOR(j,1,500)FOR(k,1,500){
		if(j*mb==k*ma){
			chmin(ans,dp[n][j][k]);
		}
	}
	if(ans==INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

Measured memory_bytes: 52468
#include <iostream>
#include <utility>
#include <algorithm>
#define ll long long
using namespace std;

pair<int, int> point[200010];
ll mod=998244353, pw[200010];
void fill_pw(){
	pw[0]=1;
	for(int i=1; i<200010; ++i){
		pw[i]=(pw[i-1]*2)%mod;
	}
}

int bit[200010];
void bAdd(int a, int k){
	for(int i=k; i<200010; i += (i&(-i))){
		bit[i] += a;
	}
}
int bSum(int k){
	int res=0;
	for(int i=k; i>0; i -= (i&(-i))){
		res += bit[i];
	}
	return res;
}

int main() {
	int N;
	cin >> N;
	for(int i=0; i<N; ++i){
		int x, y;
		cin >> x >> y;
		point[i]=make_pair(y, x);
	}
	fill_pw();
	sort(point, point+N);
	for(int i=0; i<N; ++i){
		point[i].first=i+1;
		swap(point[i].first, point[i].second);
	}
	sort(point, point+N);
	ll ans=0;
	for(int i=0; i<N; ++i){
		int s=point[i].second;
		ll got=(pw[N]+mod-(pw[i]+pw[N-1-i]+pw[s-1]+pw[N-s])%mod)%mod;
		int u=bSum(s);
		got=(got+pw[u]+pw[i-u]+pw[s-1-u]+pw[N-s-i+u]-1)%mod;
		ans=(ans+got)%mod;
		bAdd(1, s);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4096
#include<cstdio>
#include<cstdlib>
using namespace std;

int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if( (a+b)%2==0){
        printf("%d\n",(a+b)/2);
    }
    else{
        printf("%d\n",(a+b)/2+1);
    }
}

Measured memory_bytes: 128
class AtCoder:
    def main(self):
        H, W = map(int, input().split())

        print(min(self.f(H, W), self.f(W, H)))

    def f(self, H: int, W: int) -> int:
        ans = None
        for h in range(1, H):
            Sa = h * W

            half_w = W // 2
            Sb = (H - h) * half_w
            Sc = (H - h) * (W - half_w)
            S1 = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)

            half_h = (H - h) // 2
            Sb = half_h * W
            Sc = (H - h - half_h) * W
            S2 = max(Sa, Sb, Sc) - min(Sa, Sb, Sc)
            S = min(S1, S2)
            if ans is None:
                ans = S
            else:
                ans = min(ans, S)
        return ans


if __name__ == '__main__':
    AtCoder().main()

Measured memory_bytes: 3064