akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e16
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<ll,ll>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない
//UnionFind

const int maxn=100000;

int main(){
    ll n,m;
    vector<ll> a;
    ll ans=0;
    vector<P> v;
    
    cin >> n>>m;
    
    rep(i,n){
        ll t;
        cin >> t;
        a.push_back(t);
    }
    
    rep(i,m){
        P p;
        cin >> p.second>>p.first;
        v.push_back(p);
    }
    
    sort(all(a));
    
    sort(all(v));
    reverse(all(v));
    
    int ite=0;
    bool key=false;
    
    rep(i,m){
        rep(j,v[i].second){
            if(ite<n&&a[ite]<v[i].first){
                ans+=v[i].first;
            }else{
                key=true;
                break;
            }
            ite++;
        }
        if(key||i==m-1){
            for(int k=ite;k<n;k++){
                ans+=a[k];
            }
            break;
        }
    }
    
    cout << ans<<endl;
    
    return 0;
}


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

int main() {

int X,A,B;
  cin >>X>>A>>B;
  if(A>=B){
    cout <<"delicious";
  }
  else if((B-A)<=X){
    cout <<"safe";
  }
  else  {
    cout <<"dangerous";
  }
}
 

Measured memory_bytes: 256
def myfunc(op):
    if op == 1:
        return "+"
    else:
        return "-"


a, b, c, d = [int(i) for i in list(input())]

for k in [0, 1]:
    for j in [0, 1]:
        for i in [0, 1]:
            op = [-1, -1, -1]
            if k == 0:
                op[0] = 1
            if j == 0:
                op[1] = 1
            if i == 0:
                op[2] = 1
            if a + b * op[0] + c * op[1] + d * op[2] == 7:
                x = myfunc(op[0])
                y = myfunc(op[1])
                z = myfunc(op[2])
                print(f"{a}{x}{b}{y}{c}{z}{d}=7")
                exit()

Measured memory_bytes: 9160
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <cstring>
#include <vector>
#include <time.h>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL maxn=1e5+10;
const long long mod=1e9+7;
LL a[maxn];
LL c[maxn];//差
LL ac;LL sum;
LL all;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    bool p;
    LL n;
    cin>>n;
    for(LL i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(LL i=0;i<n;i++){
        c[i]=a[(i+1)%n]-a[i];
        ac+=c[i];
    }
    LL te=n*(n+1)/2;
    if(sum%te!=0)
    {
        cout<<"NO";return 0;
    }
    else
    {
        LL times=sum/te;
        if(ac){cout<<"NO";return 0;}
        else
        {
            for(LL i=0;i<n;i++)
            {
                LL t=times-c[i];
                if(t<0||t%n)
                {
                    cout<<"NO";return 0;
                }
                all+=t/n;
            }
        }
        if(all!=times)
            cout<<"NO";
        else
            cout<<"YES";
    }
    return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int ll;
const ll INF=1e18+5;
int main() {
    IO;
    int a , b ;
    cin>>a>>b ;
    if(b%2==1){
        cout<<"No"<<endl;
        return 0;
    }
    b/=2;
    if(b<a||b>a*2){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 3612
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}


int main()
{
    ll n=read();
    int ans=0;
    for(ll i=2;i*i<=n;++i){
        if(n%i==0){
            int num=0;
            while(n%i==0) num++,n=n/i;

            int l=1,r=1000,t=0;
            //printf("i:%lld num:%d\n",i,num);

            while(l<=r){
                int mid=l+r>>1;
                int res=mid*(mid+1)/2;
                if(res>num) r=mid-1;
                else t=mid,l=mid+1;
            }
            //printf("t:%d\n",t);
            ans+=t;

        }
    }
    if(n!=1) ans++;

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


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

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

void solve(void) {
  int a, b; cin >> a >> b;

  rep(1001, i) {
    if (floor(i * 0.08) == a && floor(i * 0.10) == b) {
      cout << i << endl;
      return;
    }
  }
  cout << -1 << endl;
  return;
}

int main(void) {
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define DEC(i, a, b) for (int i = (a); i > (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
typedef long long ll;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;
const ll LINF = (int)1e18;
const double EPS = 1e-9;

const int MAX_V = (int)1e5;
struct edge {
  int to, cost;
};
typedef pair<int,int> P;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P>> que;
  fill(d, d + V, INF);
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    REP(i, G[v].size()) {
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

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

  cin >> V;
  REP(i,V) {
    int s;
    cin >> s;
    --s;
    G[i].pb({s,1});
  }
  dijkstra(0);
  
  if (d[1] == INF) cout << -1 << endl;
  else cout << d[1] << endl;
  return 0;
}

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

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

    int cnt=0;
    for(int i=0;i<n;i++){
        int x,y;
        cin >>x>>y;
        if(x==y)cnt++;
        else cnt=0;
        if(cnt>=3){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
}




Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define ii pair <int , int>
#define is pair <int, string>
#define ll long long
#define mx 100000
#define sf scanf
#define sf(n) scanf("%d",&n)
#define pf printf
using namespace std;
vector <int> v;

/*int intConvert(string s){
    int n;
    stringstream geek(s);
    geek >> n;
    return n;
}*/

/*string strConvert(int n){
    string s;
    stringstream ss;
    ss << n;
    s=ss.str();
    return s;
}*/


int main(){
    string s;

    while(1){
        cin>>s;
        if(s=="-") break;

        int n,len=s.size();
        sf(n);
        while(n--){
            int a;
            string s1="",s2="";
            sf(a);

            for(int i=0; i<a; i++) s1+=s[i];
            for(int i=a; i<len; i++) s2+=s[i];
            s="";
            s+=s2;
            s+=s1;
        }
        cout<<s<<endl;
    }

    return 0;
}



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

int main() {
    int A, B;
    cin >> A >> B;
    int num_coins;
    if (A > B) {
        num_coins = A + A - 1;
    } else if (B > A) {
        num_coins = B + B - 1;
    } else {
        num_coins = A + B;
    }
    cout << num_coins << "\n";
}

Measured memory_bytes: 256
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        if(a>b){
            System.out.println("a > b");
        }else if(a<b){
            System.out.println("a < b");
        }else{
            System.out.println("a == b");
        }
    }
}


Measured memory_bytes: 26208
package main

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

const (
	initialBufSize = 1024
	maxBufSize     = 1e6
)

var (
	scanner = bufio.NewScanner(os.Stdin)
)

func main() {
	scanner.Split(bufio.ScanWords)
	s, t := scanText(), scanText()
	fmt.Printf("%v%v", t, s)
}

func scanInt() int {
	i, _ := strconv.Atoi(scanText())
	return i
}

func scanInts(size int) []int {
	ints := make([]int, size)
	for i := 0; i < size; i++ {
		ints[i] = scanInt()
	}
	return ints
}

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

func scanFloat64s(size int) []float64 {
	f := make([]float64, size)
	for i := 0; i < size; i++ {
		f[i] = scanFloat64()
	}
	return f
}

func scanText() string {
	scanner.Scan()
	return scanner.Text()
}

func scanTexts(size int) []string {
	s := make([]string, size)
	for i := 0; i < size; i++ {
		s[i] = scanText()
	}
	return s
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func pow(x, y int) int {
	return int(math.Pow(float64(x), float64(y)))
}

// greatest common divisor(最大公約数)
func gcd(a, b int) int {
	for {
		mod := a % b
		if mod == 0 {
			return b
		}
		a, b = b, mod
	}
}

// latest common multiple(最小公倍数)
func lcm(a, b int) int {
	return (a / gcd(a, b)) * b
}


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

int main(){

  int a[99], b[99];

  for(int i=0;i<10;i++) cin >> a[i];
  for(int i=0;i<10;i++) cin >> b[i];

  sort(a, a+10);
  sort(b, b+10);

  cout << a[7]+a[8]+a[9] << " " << b[7]+b[8]+b[9] << endl;

}

Measured memory_bytes: 1180
#include<iostream>
int main(){
    int A, B, C, D;
    std::cin >> A >> B >> C >> D;
    for(int i = 0;A > 0 && C > 0;i++) {
        if(i%2) A -= D;
        else C -= B;
    }
    std::cout << (A <= 0? "No":"Yes") << "\n";
}

Measured memory_bytes: 3604
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
#include<utility>

using namespace std;

int main() {
  int n;
  set<int> s;
  cin >> n;
  for(int i = 0; i < n; i++) {
    int b;
    cin >> b;
    s.insert(b);
  }
  cout << s.size() << endl;
  return 0;
}


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

int main() {
    int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
    vector<int> p(A), q(B), r(C), synthes(X+Y+C);
    rep(i, A) cin >> p[i];
    rep(i, B) cin >> q[i];
    rep(i, C) cin >> synthes[i];

    sort(p.begin(), p.end(), greater<int>());
    sort(q.begin(), q.end(), greater<int>());
    sort(r.begin(), r.end(), greater<int>());

    rep(i, X) synthes.push_back(p[i]);
    rep(i, Y) synthes.push_back(q[i]);

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

    ll ans = 0;
    rep(i, X + Y) {
        ans += synthes[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define pq priority_queue
#define P pair<int, int>
#define P2 pair<int, P>
#define P3 pair<int, P2>
using namespace std;
typedef long long ll; typedef long double ld;
constexpr long long gcd(long long a, long long b){return b ? gcd(b, a % b) : a;}
constexpr long long lcm(long long a, long long b){return a / gcd(a, b) * b;}
constexpr int INF = 1e9, MOD = INF + 7, around[] = {0, 1, 1, -1, -1, 0, -1, 1, 0, 0};
constexpr int mod_pow(long long x, long long n, const int mod){long long ret=1;while(n){if(n&1)(ret*=x)%=mod;(x*=x)%=mod;n>>=1;}return ret;}
template<int n> struct Prime{bool arr[n+1];constexpr bool operator[](int k){return arr[k];}constexpr Prime():arr(){for(int i=2;i<n;i++){arr[i]=true;for(int j=2;j*j<=i;j++){if(!(i%j))arr[i]=false;}}}};
template<int n> struct Factorial{long long arr[n+1],ary[n+1];constexpr Factorial():arr(),ary(){arr[0]=1;ary[0]=1;for(int i=0;i<n;i++){arr[i+1]=arr[i]*(i+1)%MOD;ary[i+1]=mod_pow(arr[i+1],MOD-2,MOD);}}};
constexpr Factorial<10> fact;
constexpr Prime<10> prime;
constexpr int comb(int a, int b){long long pos = fact.arr[a], pot = fact.ary[a - b], por = fact.ary[b];return pos * pot % MOD * por % MOD;}
constexpr int vx[] = {1, 0, -1, 0}, vy[] = {0, 1, 0, -1};
constexpr int sqrtN = 512, logN = 32;
constexpr ld PI = abs(acos(-1));
constexpr ll LINF=1e18;

int main(){
	int h, w; cin >> h >> w; int li[30] = {};
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			char a; cin >> a;
			li[a - 'a']++;
		}
	}
	
	int a = 0, b = 0, c = 0, d = 0;
	a = (h / 2) * (w / 2);
	b = 0;
	c = h % 2 * (w / 2) + w % 2 * (h / 2);
	d = (h % 2) * (w % 2);
	
	for(int i = 0; i < 30; i++){
		while(li[i] >= 4 and a) li[i] -= 4, a--;
	}
	
	for(int i = 0; i < 30; i++){
		while(li[i] >= 2 and c) li[i] -= 2, c--;
	}
	
	for(int i = 0; i < 30; i++){
		while(li[i] >= 1 and d) li[i] -= 1, d--;
	}
	
	if(a or b or c or d) cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <complex>
#include <iomanip>
//定数
#define MOD 1000000007
//マクロ
#define rep(i,n)    for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

#define vsort(v) sort((v).begin(), (v).end());

typedef unsigned long long int ull;
typedef long long lint;

using namespace std;




int main(){
    int N, num;
    int Ntmp, ans=0;
    //入力
    cin >> N;
    Ntmp=N;
    for(num=1; Ntmp>=10; num++) Ntmp/= 10;
    switch (num){
        case 1: 
            ans += N;
            break;

        case 3:
            ans += N-99;
        case 2:
            ans += 9;
            break;

        case 5:
            ans += N-9999;
        case 4:
            ans += 9 + 900; 
            break;

        case 6:
            ans += 9+900+90000;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sort stable_sort
using namespace std; 
 
int _;

int n,k,p[100050],c[100050],cnt;
long long maxn=1 << 30,Maxn,MMaxn;
bool vis[100050];

inline long long dfs(int x)
{
	if(vis[x])
		return 0;
	cnt++;
	vis[x]=true;
	long long sum=dfs(p[x]);
	vis[x]=false;
	return sum+c[x];
}

inline long long Dfs(int x,int depth)
{ 
	if(depth)	
	{
		long long d=Dfs(p[x],depth-1)+c[x];
		MMaxn=max(MMaxn,d);
		return d;
	} 
	return 0;
}
 
inline void rdfs(int x,long long sum,int depth)
{
	if(vis[x] || depth == 0)
		return;
	vis[x]=true;
	sum += c[x];
	Maxn=max(Maxn,sum);
	rdfs(p[x],sum,depth-1);
	vis[x]=false;
	return;
}
 
int main()
{	
	//for(scanf("%d",&_);_;_--)	
	scanf("%d%d",&n,&k);
	maxn <<= 31;
	maxn -= 2;
	maxn <<= 1;
	maxn *= -1;
	long long m=maxn;
	for(int i=1;i <= n;i++)
		scanf("%d",p+i);
	for(int i=1;i <= n;i++)
		scanf("%d",c+i);
	for(int i=1;i <= n;i++)
	{
		cnt=0;
		Maxn=m,MMaxn=m;
		long long x=dfs(i);
		rdfs(p[i],0,k);
		int t=k%cnt;
		Dfs(p[i],t);
		if(x <= 0)
			maxn=max(Maxn,maxn);
		else
			maxn=max(max(x*(k/cnt)+MMaxn,x*(k/cnt-1)+Maxn),maxn); 
	} 
	printf("%lld\n",maxn); 
	return 0;
}               


Measured memory_bytes: 4012
#include<stdio.h>
int max( int num[ ] , int test)
{
    int m , i , pos = 0 ;
    m= num[0] ;
    for( i =0 ; i < test ; i++)
    {
        if( num[i] > m)
        {
             m = num[i] ;
             pos = i ;
        }
           
    }
    return pos;
}
int main( )
{
    int num[15] , test , i , maximum , result = 0 ;
    scanf("%d" , &test);
    for( i = 0 ; i < test ; i++)
    {
        scanf("%d" , &num[i]);
    }
    
    maximum = max( num , test );
    
    for( i = 0 ; i < test ; i++)
    {
           if( maximum == i)
            result = result + num[i]/2 ;
            else
                result = result + num[i] ;
    }
    printf("%d\n" , result);
    return 0 ;
}


Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
int main(){
 int N , count = 0;
	string S;
	cin >> N >> S;
	for (int i = 0;i < N - 2;i++) {
		if (S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C') {
			count++;
		}
	}
	cout << count; 
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

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

		char[] sChars = s.toCharArray();
		char[] tChars = t.toCharArray();
		long N = s.length();
		long lastIndex = -1;

		// 文字と要素番号をマップに格納
		Map<Character, List<Integer>> map = new HashMap<>();
		List<Integer> tmpL = new ArrayList<>();
		for (int i = 0; i < sChars.length; i++) {
			tmpL = map.get(sChars[i]);
			if (tmpL == null) {
				tmpL = new ArrayList<>();
				map.put(sChars[i], tmpL);
			}
			tmpL.add(i);
		}

		// 文字列ｔの文字が文字列ｓに含まれるかチェック
		for (char c : tChars) {
			if (!map.containsKey(c)) {
				System.out.println(-1);
				return;
			}
		}

		Map<Character, Integer> beforeMap = new HashMap<>();
		long ans = 0;
		boolean exists = false;
		int start = 0;
		for (char c : tChars) {
			tmpL = map.get(c);
			Integer tmpI = beforeMap.get(c);
			if (tmpI != null) {
				start = tmpI + 1;
			}
			beforeMap.clear();

			// 続きから後ろを確認
			for (int i = start; i < tmpL.size(); i++) {
				if (tmpL.get(i) > lastIndex) {
					lastIndex = tmpL.get(i);
					beforeMap.put(c, i);
					exists = true;
					break;
				}
			}
			if (!exists) {
				ans += N;
				lastIndex = tmpL.get(0);
				beforeMap.put(c, 0);
			}
			else {
				exists = false;
			}
			start = 0;
		}
		ans = ans + (long)(lastIndex + 1);
		System.out.println(ans);
	}
}


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

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

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

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

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

// --------------------------------------
int n, k;
int h[200005];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> k;
  REP(i, n) cin >> h[i];

  sort(h, h + n, greater<int>());

  ll ans = 0;
  REP(i, n) {
    if(i >= k) ans += h[i];
  }

  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cassert>
#include <list>
#include <map>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    map<int, int> m; for (int i = 0; i < n; i++) { int a; cin >> a; m[a]++; }
    map<int, int> m2;
    for (auto &x : m) m2[x.second]++;
    int sz = 0;
    for (auto &x : m2) sz += x.second;
    for (int t = 1; t <= n; t++) {
        if (sz < t) { cout << 0 << endl; continue; }
        list<pair<int, int> > tmp(m2.begin(), m2.end());
        int ans = 0, cursz = sz;
        // cerr << "t = " << t  << endl;
        while (cursz >= t) {
            // for (auto &x : tmp) cerr << x.first << ' ' << x.second << endl;
            // cerr << "ans = " << ans << endl;
            auto it = prev(tmp.end());
            int t1 = t;
            for (;;) {
                if (t1 > it->second) t1 -= it->second, it--;
                else {
                    if (it->first == 1) {
                        if (it->second == t1) it = tmp.erase(it);
                        else { it->second -= t1; it++; }
                        cursz -= t1;
                    } else {
                        if (it == tmp.begin() || (prev(it)->first != it->first-1)) {
                            tmp.insert(it, {it->first-1, t1});
                        } else prev(it)->second += t1;
                        it->second -= t1;
                        it++;
                    }
                    while (it != tmp.end()) {
                        assert(it->first != 1);
                        if (it != tmp.begin() && prev(it)->first == it->first-1) {
                            prev(it)->second += it->second;
                            it = tmp.erase(it);
                        } else {
                            it->first--;
                            it++;
                        }
                    }
                    break;
                }
            }
            ans++;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 14336
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
--import Data.Array.Unboxed
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getDouble = readLn :: IO Double
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete

f n m b d = runST $ do
    ref <- newSTRef m
    position <- newSTRef 1
    let field = listArray (1,n) b
    forM_ (zip [1..] d) $ \(i,x) -> do
        p <- readSTRef position
        when (p<n) $ do
            let np = p + x
            when (np>=n) $ modifySTRef ref (min i)
            writeSTRef position np
            when (np<n) $ do
                let dp = field!np
                let nnp = np + dp
                when (nnp>=n) $ modifySTRef ref (min i)
                writeSTRef position nnp
    readSTRef ref

main = do
    [n, m] <- getInts
    when (m/=0 || m/=0) $ do
        board <- replicateM n getInt
        dice <- replicateM m getInt
        print $ f n m board dice
        main

Measured memory_bytes: 4940
n = int(input())
ans = [0 for i in range(4)]
tag = ['AC', 'WA', 'TLE', 'RE']
for i in range(n):
  temp = input()
  if temp == 'AC':
    ans[0] += 1
  elif temp == 'WA':
    ans[1] += 1
  elif temp == 'TLE':
    ans[2] += 1
  else:
    ans[3] += 1
  
for i in range(4):
  print('{} x {}'.format(tag[i], ans[i]))

Measured memory_bytes: 9208
/*
  AUTHOR:SOURABH
  CREATED:26:01:20
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<ll , null_type, less< ll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

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

    //freopen("in.txt","r",stdin);
    //freopen(2 "out.txt","w",stdout);

    ll h,n,i,j;
    cin>>h>>n;
    vll a(n),b(n);
    fn(i,n)
    cin>>a[i]>>b[i];
    vll dp(h+1,1e12);
    dp[0]=0;
    fs(j,1,h+1)
    {
        fn(i,n)
        {
            if(j-a[i]<0)
            dp[j]=min(dp[j],b[i]);
            else
            dp[j]=min(dp[j],dp[j-a[i]]+b[i]);
        }
    }
    cout<<dp[h];
    return 0;
}






Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 1000000000
//#define NCONS 100001
//#define NCONS 1001
//#define NCONS 101
#define MCONS 2001
#define LIMIT 1000000000
#define TRUE 1
#define FALSE 0

using namespace std;

int n, A, B, C;
vector<int> l;
bool visited[9];

int dfs(int cur, int a, int b, int c)
{
    if(cur >= n)
    {
        auto ret =  abs(a - A) + abs(b - B) + abs(c - C);
        return ret;
    }
    
    int ret = INT_MAX;
    
    auto r1 = dfs(cur + 1, a, b, c);
    ret = min(ret, r1);
    
    if(!visited[cur])
    {
        auto r2 = dfs(cur + 1, a + l[cur], b, c) + 10;
        ret = min(ret, r2);
        auto r3 = dfs(cur + 1, a, b + l[cur], c) + 10;
        ret = min(ret, r3);
        auto r4 = dfs(cur + 1, a, b, c + l[cur]) + 10;
        ret = min(ret, r4);
    }
    
    
    return ret;
}

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    cin >> n >>  A >> B >> C;
    for(int i = 0; i < n; i++)
    {
        int tl; cin >> tl; l.push_back(tl);
    }
    
    int ret = INT_MAX;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j) continue;
            for(int k = 0; k < n; k++)
            {
                if(i == k || j == k) continue;
                visited[i] = visited[j] = visited[k] = true;
                ret = min(ret, dfs(0, l[i], l[j], l[k]));
                visited[i] = visited[j] = visited[k] = false;
            }
        }
    }
    
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();
	
	int N; cin >> N;
	int ans = 1;
	while (ans * 2 <= N) {
		ans *= 2;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i > 0; i++)
const int MOD =1e9+7;
using ll=long long;

int main(){
  int x, ans;
  cin >> x;
  for(int n = 1; n<=100000; n++){
    int time = n*(n+1)/2;
    if(x <= time) {
      cout << n<< endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

#define SIZE 100000

int main(){
	int n, q;
	int s[SIZE], t[SIZE];

	cin >> n;
	for(int i=0; i<n; i++) cin >> s[i];

	cin >> q;
	for(int j=0; j<q; j++) cin >> t[j];

	int count = 0;
	for(int i=0; i<q; i++){
		for(int j=0; j<n; j++){
			if(t[i] == s[j]){
				count++;
				break;
			}
		}
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 3104
n,m,x,y=map(int,input().split())
xs=list(map(int,input().split()))
ys=list(map(int,input().split()))
xs2=sorted(xs)
ys2=sorted(ys)
if xs2[n-1]<ys2[0] and xs2[n-1]<y and ys2[0]>x:
  print('No War')
else:
  print('War')

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

int main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int max_diff = 0;
    int running_min = 1e9;
    for (int i = 0; i < n; i++) {
        running_min = min(running_min, a[i]);
        max_diff = max(max_diff, a[i] - running_min);
    }

    // cout << max_diff << endl;
    
    running_min = 1e9;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        running_min = min(running_min, a[i]);
        if (a[i] - running_min == max_diff) ans++;
    }
    cout << ans << endl;
}

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

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

string mp[25];
int h,w;
int dist[25][25];
int ans=0;

void chk(int sy, int sx) {
  if(mp[sy][sx]=='#')return;

  for(int i=0;i<25;i++)
    for(int j=0;j<25;j++)
      dist[i][j]=-1;
  dist[sy][sx]=0;

  queue<pair<int, int> > q;
  q.push({sy, sx});
  while(!q.empty()){
    auto v = q.front();q.pop();
    int y = v.first;
    int x = v.second;
    for(int i=0;i<4;i++){
      int ny = y + dy[i];
      int nx = x + dx[i];
      if(0<=ny&&ny<h&&0<=nx&&nx<w && mp[ny][nx]=='.' && dist[ny][nx]==-1){
        dist[ny][nx] = dist[y][x]+1;
        ans = max(ans, dist[ny][nx]);
        q.push({ny, nx});
      }
    }
  }
}

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

  cin>>h>>w;
  for(int y=0;y<h;y++)cin>>mp[y];

  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      chk(y, x);
    }
  }

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

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

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

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

const int mod = 998244353;
const ll inf = 3e18 + 5;

int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }  

const int n = 1e9;

int main(){
    int n, m;
    cin >> n >> m;
    vi res(n+1);
    for(int i=0; i<m; i++){
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        res[tmp1-1]++;
        res[tmp2]--;
    }
    for(int i=0; i<n; i++){
        if(i>0)
            res[i]+=res[i-1];
    }
    int sol = 0;
    for(int i=0; i<n; i++){
        if(res[i] == m)
            sol++;
    }
    cout << sol;
}

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

using namespace std;

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

int a, dp[100003];

int main()
{
	a = gi();
	for (int i = 100; i <= 105; i+=1) dp[i] = 1;
	for (int i = 106; i <= a; i+=1)
	{
		if (dp[i - 100] || dp[i - 101] || dp[i - 102] || dp[i - 103] || dp[i - 104] || dp[i - 105])
			dp[i] = 1;
	}
	printf("%d\n", dp[a]);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    string S;
    string str[] = {"Sunny", "Cloudy", "Rainy"};
    cin >> S;
    rep(i,0,3){
        if(str[i] == S){
            cout << str[(i+1)%3] << endl;
        }
    }
}

Measured memory_bytes: 256
use proconio::{
   fastout, input,
   marker::{Bytes, Chars, Isize1, Usize1},
};

const INF: usize = 999999999999;

fn main() {
   input! {
      n:usize,mut k:usize,
      a:[Usize1;n]
   }
   let mut flag = vec![false; n];
   let mut r = vec![];
   let mut loop_point;
   flag[0] = true;
   let mut from = 0;
   loop {
      if flag[a[from]] {
         r.push(from);
         loop_point = a[from];
         break;
      }
      flag[from] = true;
      r.push(from);
      from = a[from];
   }
   let mut loop_idx = r.iter().position(|&x| x == loop_point).unwrap();
   if k < r.len() {
      println!("{}", r[k] + 1);
   } else {
      k = k - r.len();
      println!("{}", r[loop_idx + k % (r.len() - loop_idx)] + 1);
   }
}


Measured memory_bytes: 6540
import math


def main():
    a, b, h, m = map(int, input().split())
    short = m*360//60
    long = (h*360//12 + (360//12)*(m/60)) % 360
    angle = min(abs(short-long), 360-(abs(short-long)))
    # print(short, long, angle)
    # print(2*a*b*math.cos(angle*math.pi/360))
    ans = (pow(a, 2) + pow(b, 2) - 2*a*b*math.cos(angle*math.pi/180))**(1/2)
    print("{: .13f}".format(ans))
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 62464
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;



int main()
{
  int n, k ;
  cin >> n >> k ;
  int x = 1 ;
  
  REP(i,n){
    x = min(x*2,x+k) ;
  }
  
  cout << x <<endl ;

  return 0 ;
}




Measured memory_bytes: 256
table=[[[0]*10 for i in range(0,3)] for k in range(0,4)]
N=int( input())

for loop in range(N):
    house_id, floor, room, add=map(int, input().split())
    table[house_id-1][floor-1][room-1]+=add
    
x = 0

for i in range(4):
    if x != 0:
        print("#"*20)
    x += 1

    for a in range(3):
        for b in range(10):
            print(" %d"%(table[i][a][b]), end="")
        print()



Measured memory_bytes: 5624
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
	while(1){
		int n, a[25];
		
		scanf(" %d", &n);
		if(n==0) break;
		for(int i=0; i<n; ++i) scanf(" %d", &a[i]);
		
		int r=32, now=0;
		while(r>0){
			r -= (r-1)%5;
			printf("%d\n", r);
			r -= a[now%n];
			if(r<0) r=0;
			printf("%d\n", r);
			++now;
		}
	}

	return 0;
}

Measured memory_bytes: 1188
long long d[21];
v,i,j;
main(n){
	scanf("%d%d",&n,&v);
	d[v]=1;
	for(i=0;i<n-2;i++){
		long long e[21]={0};
		scanf("%d",&v);
		for(j=0;j<=20;j++){
			if(j-v>=0)
				e[j]+=d[j-v];
			if(j+v<=20)
				e[j]+=d[j+v];
		}
		memcpy(d,e,sizeof(d));
	}
	scanf("%d",&v);
	v=!printf("%lld\n",d[v]);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define ll long long
#define mod pow(10,9)+7

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,l;
	cin>>n>>l;
	string s[n]={""};
	for(int i=0;i<n;i++)
		cin>>s[i];
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			if(s[i]>s[j])
			{
				string t=s[i];
				s[i]=s[j];
				s[j]=t;
			}
	for(int i=0;i<n;i++)
		cout<<s[i];
	cout<<endl;
	return 0;
}


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


long long n, m, ans;
vector<long long> a;

//判定
bool chk(long long x) {
    long long cnt = 0;
    for(int i=0; i<n; i++) {
        long long pos = lower_bound(a.begin(), a.end(), x - a[i]) - a.begin();
        cnt += (n - pos);
    }
    return cnt < m;//X以上の和がM個未満かどうか
}

int main() {
    cin >> n >> m;
    a.resize(n);
    for(int i=0; i<n; i++)cin >> a[i];
    sort(a.begin(), a.end());
    //二分探索
    long long ng = 0, ok = LLONG_MAX;
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        if (chk(mid)) ok = mid;
        else ng = mid;
    }
    //終了時にngにX-1,okにXが入っている。


    vector<long long> wa(n + 1); //Aの累積和
    for(int i=0; i<n; i++) wa[i + 1] = wa[i] + a[i];
    for(int i=0; i<n; i++) {
        long long pos = upper_bound(a.begin(), a.end() , ng - a[i]) - a.begin();
        long long cnt = n - pos;
        ans += cnt * a[i] + (wa[n] - wa[pos]);
        m -= cnt;
    }
    ans += m * ng;
    cout << ans << endl;
}

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

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef priority_queue<int> PQ;
typedef priority_queue<int, V, greater<int>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

ll Q, H, S, D, N;
vector<pair<ll, double>> tea;

int main() {
    cin >> Q >> H >> S >> D >> N;
    cout << (N / 2) * min(8 * Q, min(4 * H, min(2 * S, D))) + (N % 2) * min(4 * Q, min(2 * H, S)) << "\n";
}

Measured memory_bytes: 256
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

struct Weighted_Union_Find_Tree {
	vector<int>Par, Rank,Diff_Weight;
	Weighted_Union_Find_Tree(int n) {
		Par.resize(n);
		Rank.resize(n);
		Diff_Weight.resize(n);
		for (int i = 0; i < n; i++) {
			Par[i] = i;
			Rank[i] = 0;
		}
	}

	int find(int x) {
		if (Par[x] == x) {
			return x;
		}
		else {
			int r = find(Par[x]);
			Diff_Weight[x] += Diff_Weight[Par[x]];//累積和をとる
			return Par[x] = r;
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	int weight(int x) {
		find(x);//経路圧縮
		return Diff_Weight[x];
	}

	int diff(int x, int y) {
		return weight(y) - weight(x);
	}

	// weight(y) - weight(x) = w となるように merge する
	bool merge(int x, int y, int w) {
		// x と y それぞれについて、 root との重み差分を補正
		w += weight(x); w -= weight(y);

		// x と y の root へ (x と y が既につながっていたら false を返すようにした)
		x = find(x); y = find(y);
		if (x == y) return false;

		// Rank[x] >= Rank[y] となるように x と y を swap (それに合わせて w も符号反転します)
		if (Rank[x] < Rank[y]) swap(x, y), w = -w;

		// y (のroot) を x (のroot) の下にくっつける 
		if (Rank[x] == Rank[y]) ++Rank[x];
		Par[y] = x;

		// x が y の親になるので、x と y の差分を diff_weight[y] に記録
		Diff_Weight[y] = w;

		return true;
	}
};

int main() {
	int n, q;
	cin >> n >> q;
	Weighted_Union_Find_Tree uf(n);
	REP(i, q){
		int num;
		cin >> num;
		if (num == 0) {
			int x, y, z;
			cin >> x >> y >> z;
			uf.merge(x, y, z);
		}
		else {
			int x, y;
			cin >> x >> y;
			if (uf.same(x, y)) {
				cout << uf.diff(x, y) << endl;
			}
			else {
				cout << "?" << endl;
			}
		}
	}
}


Measured memory_bytes: 3892
#include<iostream>
using namespace std;

struct Directions
{
	int E[6] = { 2, 1, 5, 0, 4, 3 };
	int W[6] = { 3, 1, 0, 5, 4, 2 };
	int N[6] = { 4, 0, 2, 3, 5, 1 };
	int S[6] = { 1, 5, 2, 3, 0, 4 };
};

class Dice
{
public:
	int num[6];
	char dir_command[105];
	void swap(int*);
	Directions dir_array;
	Dice();
	int condition(int);
	void roll(int);
	void show_num(int);
};

Dice::Dice()
{
	Directions direction;
	for (int i = 0; i < 6; i++)
		cin >> this->num[i];
}

int Dice::condition(int i)
{
	if (dir_command[i] == '\0')
		return 0;
	else
		return 1;
}

void Dice::roll(int i)
{
	switch (this->dir_command[i])
	{
	case 'E':
		this->swap(dir_array.E);
		break;
	case 'W':
		this->swap(dir_array.W);
		break;
	case 'N':
		this->swap(dir_array.N);
		break;
	case 'S':
		this->swap(dir_array.S);
		break;
	}
	return;
}

void Dice::swap(int *dir)
{
	int tmp[6];
	for (int i = 0; i < 6; i++)
		tmp[dir[i]] = num[i];
	for (int i = 0; i < 6; i++)
		num[i] = tmp[i];
	return;
}

void Dice::show_num(int i)
{
	cout << this->num[i] << endl;
	return;
}

int main()
{
	int q, t, f;
	Dice dice;
	int a[6][4] = { {1, 2, 4, 3},
	{0, 3, 5, 2},
	{0, 1, 5, 4},
	{0, 4, 5, 1},
	{0, 2, 5, 3},
	{3, 4, 2, 1} };

	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> t; cin >> f;
		for (int j = 0; j < 6; j++)
			if (t == dice.num[j])
				t = j;
			else if (f == dice.num[j])
				f = j;
		for (int j = 0; j < 4; j++)
			if (a[t][j] == f)
				dice.show_num(a[t][(j + 1) % 4]);
	}

	return 0;
}


Measured memory_bytes: 3072
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

    def root(self, x):
        return self.__root(x)

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, M, A, XY):
    uf = UnionFind()

    for x, y in XY:
        uf.union(x, y)

    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(A[i])

    if len(d) == 1:
        return 0

    ans = 0
    n = []
    for v in d.values():
        m = min(v)
        ans += m
        v.remove(m)
        n.extend(v)

    e = len(d)-2
    if len(n) < e:
        return 'Impossible'

    n.sort()
    ans += sum(n[:e])
    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    XY = [read_int_n() for _ in range(M)]
    print(slv(N, M, A, XY))


if __name__ == '__main__':
    main()


Measured memory_bytes: 51716
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
	int x,a,b,s1,s2;
	cin>>x>>a>>b;
	if(x>=1&&x<=1000&&a>=1&&a<=1000&&b>=1&&b<=1000)
	{
		s1=abs(x-a);
		s2=abs(x-b);
		if(s1>s2)cout<<'B'<<endl;
		else if(s1<s2)cout<<'A'<<endl;
	}
	return 0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    int num;
    int count;

    for(int i = 1; i <= n; ++i){
        num = i;
        count = 0;
        while(num != 0){
            num = num / 10;
            ++ count;
        }

        if(count%2 != 0){
            ++ ans;
        }
    }

    cout << ans << endl;
}

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

vector<ll> S(ll X) {
  vector<ll> res(0);
  for (int i = 1; i <= sqrt(X); i++) {
    if (X % i == 0) {
      res.push_back(i);
      res.push_back(-i);
    }
  }
  return res;
}

int main() {
  ll X;
  cin >> X;
  vector<ll> C = S(X);
  ll Csize = C.size();
  for (int i = 0; i < Csize; i++) {
    ll P = C[i];
    ll Q = X / C[i];
    for (ll B = -8000000; B <= 8000000; B++) {
      ll A = P + B;
      if ( A*A*A*A + A*A*A*B + A*A*B*B + A*B*B*B + B*B*B*B == Q ) {
        cout << A << " " << B << endl;
        return 0;
      }
      A = Q + B;
      if ( A*A*A*A + A*A*A*B + A*A*B*B + A*B*B*B + B*B*B*B == P ) {
        cout << A << " " << B << endl;
        return 0;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define long long long // for codeforces

int main(){
  int h,w;
  cin>>h>>w;
  vector<string> vec(h);
  rep(i,h) cin>>vec[i];

  cout << string(w+2, '#') << endl;
  rep(i,h) cout << "#" << vec[i] << "#" <<endl;
  cout << string(w+2, '#') << endl;

  return 0;
}


Measured memory_bytes: 256
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    w,h,x,y = map(int, input().split())
    print(w*h/2, int(w/2 == x and h/2 == y))
    

if __name__ == "__main__":
    main()

Measured memory_bytes: 5108