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

int A[MAX];
int H;

int left(int i) { return i * 2; }
int right(int i) { return i * 2 + 1; }

void MaxHeapify(int *Arr, int i) {
	int l = left(i);
	int r = right(i);
	int largest;
	if (l <= H && Arr[l] > Arr[i])
		largest = l;
	else
		largest = i;
	if (r <= H && Arr[r] > Arr[largest])
		largest = r;
	if (i != largest) {
		swap(Arr[i], Arr[largest]);
		MaxHeapify(Arr, largest);
	}
}

void buildMaxHeap(int *Arr) {
	int i;
	for (i = H / 2; i >= 1; i--) {
		MaxHeapify(Arr, i);
	}
}

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

	buildMaxHeap(A);

	for (i = 1; i <= H; i++) {
		cout << " " << A[i];
	}
	cout << endl;
}


Measured memory_bytes: 5032
#include <stdio.h>


#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim()
{
  int u,minv,d[MAX],p[MAX],color[MAX],i,v,sum=0;

  for( i=0 ; i<n ; i++ ){
    d[i] = INFTY;
    p[i] = -1;
    color[i] = WHITE;
  }

  d[0] = 0;

  while(1){
    minv = INFTY;
    u = -1;
    for( i=0 ; i<n ; i++ ){
      if( (minv>d[i])&&(color[i]!=BLACK) ){
        u = i;
        minv = d[i];
      }
    }
    
    if( u==-1 )
      break;

    color[u]=BLACK;

    for( v=0 ; v<n ; v++ ){
      if( color[v]!=BLACK&&M[u][v]!=INFTY ){
        if( d[v]>M[u][v] ){
          d[v] = M[u][v];
          p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }

  for( i=0 ; i<n ; i++ ){
    if( p[i]!=-1 )
      sum += M[i][p[i]];
  }

  return sum;

}


int main()
{
  int i,j,a;
  
  scanf("%d",&n);

  for( i=0 ; i<n ; i++ ){
    for( j=0 ; j<n ; j++ ){
      scanf("%d",&a);
      M[i][j] = ( a==-1 ) ? INFTY : a;
    }
  }

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

  return 0;
}

  
    


Measured memory_bytes: 2004
#include <iostream>
#include <algorithm>
using namespace std;
int a[120];
int main() {
	int n;cin >> n;
	for (int i = 0;i < n;i++)cin >> a[i];
	sort(a, a + n);
	cout << a[n - 1] - a[0] << endl;
	return 0;
}


Measured memory_bytes: 256
//幅優先じゃんこれ

#include <stdio.h>
#include <queue>
#include <utility>

using namespace std;

int h,w;
char s[21][21];

int memo[20][20];

queue<pair<int,int>> que;

int bfs(int x,int y)
{
    int vecx[]={0,0,-1,1};
    int vecy[]={-1,1,0,0};
    que.push(make_pair(x,y));
    int last;
    while(!que.empty())
    {
        pair<int,int> now=que.front();
        que.pop();
        // printf("(%d,%d)\n",now.first,now.second);
        for(int i=0;i<4;i++)
        {
            int newx=now.first+vecx[i];
            int newy=now.second+vecy[i];
            // printf("    (%d,%d)\n",newx,newy);
            if(s[newx][newy]=='#')continue;
            if(memo[newx][newy]!=-1)continue;
            if(newx>=h||newx<0||newy>=w||newy<0) continue;
            memo[newx][newy]=memo[now.first][now.second]+1;
            que.push(make_pair(newx,newy));
        }
        last=memo[now.first][now.second];
    }
    return last;
}

int main()
{
    scanf("%d%d",&h,&w);
    for(int i=0;i<h;i++)
    scanf("%s",s[i]);

    int ans=0;
    int tmp=0;
    for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
    {
        if(s[i][j]=='#') continue;
        for(int k=0;k<h;k++)
        for(int l=0;l<w;l++)
        memo[k][l]=-1;
        memo[i][j]=0;
        int res=bfs(i,j);
        if(ans<res)ans=res;
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 3204
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


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


def read_float():
    return float(buff_readline())


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


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


def read_str_n():
    return readline().strip().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


@mt
def slv(N, S, A):
    mod = 998244353
    memo = [0] * (S+1)
    memo[0] = 1
    for a in A:
        nm = [2*memo[s] % mod for s in range(S+1)]
        for s in range(S+1-a):
                nm[s+a] += memo[s]
                nm[s+a] %= mod
        memo = nm

    return memo[S]


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 71808
import itertools
n = int(input())
a = [input() for _ in range(n)]

suits = ['S','H','C','D']
ranks = [1,2,3,4,5,6,7,8,9,10,11,12,13]
cards = ["%s %d" % (suit, rank) for suit, rank in itertools.product(suits, ranks)]
answers = [card for card in cards if card not in a]
for ans in answers:
    print(ans)


Measured memory_bytes: 5648
import sys

N = int(input())
x = []
y = []
for i in range(N):
    xin, yin = map(int,input().split())
    x.append(xin)
    y.append(yin)
relative_co = [[] for i in range(N)]
pattern = []
min_cost = 50

if N == 1:
    print("1")
    sys.exit()

for i in range(N):
    for j in range(N):
        tempx = x[i]-x[j]
        tempy = y[i]-y[j]
        pattern.append((tempx, tempy))
        relative_co[i].append((tempx, tempy))
patterns = len(pattern)
for i in range(patterns):
    if pattern[i] == (0,0):
        continue
    cur_cost = 0
    for j in range(N):
        if not pattern[i] in relative_co[j]:
            cur_cost += 1
    if cur_cost < min_cost:
        min_cost = cur_cost
print(str(min_cost))

Measured memory_bytes: 41580
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define stpr setprecision
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<(b);++i)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ld EPS=10e-8;
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
    for(auto i=begin(v); i != end(v); ++i){
        if(i !=begin(v)) os << ' ';
        os << *i;
    }
    return os;
}

int N;
vector<pair<int,int>> A[10007];
int DKSTR[10007];

void dikstra(){
    int chek[10007];
    rep(i,N){
        chek[i]=0;
    }
    DKSTR[0]=0;
    int key=0;
    priority_queue <pair<int,int>> PQ;
    PQ.push(mp(0,0));
    while(PQ.empty()!=1){
        pair<int,int> f = PQ.top();
        PQ.pop();
        key=f.second;
        chek[key]=1;
        if(DKSTR[key] < f.first*(-1)){
            continue;
        }
        rep(j,A[key].size()){
            int v = A[key][j].first;
            if(chek[v]==0 && DKSTR[v]>DKSTR[key]+A[key][j].second){
                DKSTR[v] = DKSTR[key] + A[key][j].second;
                PQ.push(mp(DKSTR[v]*(-1),v));
            }
        }
    }
}

int main(){
    ll X,Y,a,b;
    cin>>N;
    rep(i,N){
        DKSTR[i]=MOD;
    }
    rep(i,N){
        cin >> X >> Y;
        rep(j,Y){
            cin >> a >> b;
            A[X].pb(mp(a,b));
        }
    }
    dikstra();
    rep(i,N){
        cout << i << " " << DKSTR[i] << endl;
    }
}


Measured memory_bytes: 7996
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
 
#define coutv(v) for (int i = 0; i < (v).size(); ++i) cout << v[i] << ' '; cout << endl;
#define coutvv(v) for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cout << v[i][j] << ' '; cout << endl;}
#define debugv(v) {for (int i = 0; i < (v).size(); ++i) cerr << v[i] << ' '; cerr << endl;}
#define debugvv(v) {for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cerr << v[i][j] << ' '; cerr << endl;}}
#define TC int TESTCASE; cin >> TESTCASE; while (TESTCASE--)
typedef long long ll;


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	ll summ = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			if (i != j) {
				summ += a[i] * a[j];
			}
		}
	}
	cout << summ;
}
 


Measured memory_bytes: 3600
using System;
using System.Linq;
using static System.Console;

namespace Contest
{
    class Program
    {
        public static void Main(string[] args)
        {
            var data1 = ReadLine().Split().Select(int.Parse).ToArray();
            var data2 = ReadLine().Split().Select(int.Parse).ToArray();
            var dice = new Dice(data1);
            int top = data2[0], forward = data2[1];
            SearchNumber(dice, top, forward);
            WriteLine(data2.SequenceEqual(dice.Data) ? "Yes" : "No");
        }

        public static void SearchNumber(Dice dice, int top, int forward)
        {
            for (int i = 0; i < 5; i++)
            {
                for (int j = 0; j < 5; j++)
                {
                    if (dice.GetNumber() == top && dice.GetNumber(1) == forward) return;
                    if (dice.GetNumber(1) == forward) break;
                    dice.RollDice('N');
                }
                dice.RollDice('W');
            }
        }
    }

    class Dice
    {
        public int[] Data { get; set; }
        public int X { get; set; } = 0;
        public int Y { get; set; } = 0;
        public Dice(int[] data)
        {
            Data = data;
        }

        public void RollDice(char c)
        {
            // 0: Top
            // 5: Bottom
            // 1: Forward
            // 4: Back
            // 3: Left
            // 2: Right
            int tmp;
            switch (c)
            {
                case 'N': { tmp = Data[0]; Data[0] = Data[1]; Data[1] = Data[5]; Data[5] = Data[4]; Data[4] = tmp; break; }
                case 'S': { tmp = Data[0]; Data[0] = Data[4]; Data[4] = Data[5]; Data[5] = Data[1]; Data[1] = tmp; break; }
                case 'W': { tmp = Data[0]; Data[0] = Data[2]; Data[2] = Data[5]; Data[5] = Data[3]; Data[3] = tmp; break; }
                case 'E': { tmp = Data[0]; Data[0] = Data[3]; Data[3] = Data[5]; Data[5] = Data[2]; Data[2] = tmp; break; }
                default: break;
            }
        }

        public int GetNumber(int number = 0)
        {
            return Data[number];
        }

    }
}


Measured memory_bytes: 18312
n,m = map(int,input().split())
ab = [ list(map(int,input().split())) for i in range(n) ]
# print(ab)
ab.sort()
# print(ab)
import heapq
heap = []
ans = 0
i = 0
for day in reversed(range(m)):
    while i<n and ab[i][0]==(m-day):
        heapq.heappush(heap,-ab[i][1])
        i += 1
    if len(heap) > 0:
        ans += -heapq.heappop(heap)
    # print(day,i,ans,heap)
print(ans)

Measured memory_bytes: 31980
#include <iostream>

int find_ways(int, int);

int main ()
{
  int n, x;
  std::cin >> n >> x;

  while ((n!=0) || (x!=0))
    {
      std::cout << find_ways(n, x) << std::endl;
      std::cin >> n >> x;
    }
}

int find_ways(int n, int x)
{
  int count = 0;
  for (int a=1; a<=x/3; a++)
    {
      for (int b=a+1; b<=(x-a)/2; b++)
        {
          auto c = x - a - b;
          // std::cout << a << " " << b << " " << c << std::endl;
          // std::cout << a + b + c << std::endl;
          if ((c>b) && (c<=n))
            {
              count += 1;
            }
        }
    }
  return count;
}



Measured memory_bytes: 3100
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX_N = 100100;
int N;
int dir[MAX_N];
int f[MAX_N]; //[i, i+K-1]を反転させたかどうか

bool calc(int K){
    memset(f, 0, sizeof(f));
    int res = 0;
    int sum = 0;
    for (int i = 0; i + K - 1 <= N - 1; i++) {
        if ((dir[i] + sum) % 2 != 0) {
            res++;
            f[i] = 1;
        } 
        sum += f[i];
        if (i - K + 1 >= 0) {
            sum -= f[i - K + 1];
        } 
    }

    int i = N - K + 1;
    bool flag = true;
    while (i < K) {
        if ((dir[i] + sum)%2 != 0) {
            flag = false;
        } 
        i++;
    }
    return flag;
}

int main () {
    
    string s; cin >> s;
    N = s.length();
    for (int i = 0; i < N; i++) {
        if (s[i] == '0') {
            dir[i] = 0;
        } else {
            dir[i] = 1;
        } 
    }

    vector<int> v(N);
    REP(i, N) v[i] = i+1;
    int ok = -1;
    int ng = v.size();
    while (abs(ok - ng) > 1) {
        int m = (ok+ng)/2;
        if (calc(v[m])) {
            ok = m;
        } else {
            ng = m;
        } 

    }
    cout << v[ok] << endl;
    
    return 0;
}







Measured memory_bytes: 1664
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func solve() {
	var s string
	fmt.Scan(&s)

	n := len(s)

	b := []int{}
	count := 0
	for i := 0; i < n; i++ {
		count++
		if i+1 < n && s[i] != s[i+1] {
			b = append(b, count)
			count = 0
		}
	}
	b = append(b, count)

	ans := make([]int, n)
	k := 0
	for i := 0; i+1 < n; i++ {
		if s[i] == 'R' && s[i+1] == 'L' {
			ans[i] += (b[k] - (b[k] / 2))
			ans[i] += (b[k+1] / 2)
			ans[i+1] += (b[k] / 2)
			ans[i+1] += (b[k+1] - (b[k+1] / 2))
			k += 2
		}
	}

	ansStr := []string{}
	for i := 0; i < n; i++ {
		ansStr = append(ansStr, strconv.Itoa(ans[i]))
	}

	buf := strings.Join(ansStr, " ")

	fmt.Println(buf)
}

func main() {
	solve()
}


Measured memory_bytes: 10752
#include<stdio.h>
#define N 1001
#define INFTY (1<<21)
 
int n, M[N][N];
int color[N], d[N], f[N], tt;
int Q[N*2], head, tail;
 
void init(){
  head = tail = 1;
}
 
void enqueue(int x){
  Q[tail++] = x;
}
 
int empty(){
  return head == tail;
}
 
int dequeue(){
  int x = Q[head++];
  return x;
}
 
void bfs(int s){
  int i, u, v;
  init();
  enqueue(s);
  for ( i = 0; i < n; i++ )d[i] = INFTY;
  d[s] = 0;
  while(!empty()){
    u = dequeue();
    for ( v = 0; v < n; v++ ){
      if ( M[u][v] == 0 ) continue;
      if ( d[v] != INFTY ) continue;
      d[v] = d[u] + 1;
      enqueue(v);
    }
  }
  for ( i = 0; i < n; i++ ){
    printf("%d %d\n", i+1,((d[i]==INFTY)?(-1):d[i]));
  }
}
 
main(){
  int  u, k, v, i, j; 
 
  scanf("%d", &n);
 
  for ( i = 0; i <n; i++ ){
    for ( j = 0; j <n; j++ ) M[i][j] = 0;
  }
   
  for ( i = 0; i < n; i++ ){
    scanf("%d %d", &u, &k);
    u--;
    for ( j = 0; j < k; j++ ){
      scanf("%d", &v);
      v--;
      M[u][v] = 1;
    }
  }
   
  bfs(0);
 
  return 0;
}


Measured memory_bytes: 2148
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int main()
{ios_base::sync_with_stdio(false);
int n;
cin>>n;
if(n%10==9)
{
	ol("Yes");
	return 0;
}
n/=10;
if(n%10==9)
{
	ol("Yes");
	return 0;
}
ol("No");
return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
//For ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MOD 1000000007
#define test int t; cin>>t; while(t--)
#define init(arr,val) memset(arr,val,sizeof(arr))
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopr(i,a,b) for(int i=a;i>=b;i--)
#define loops(i,a,b,step) for(int i=a;i<b;i+=step)
#define looprs(i,a,b,step) for(int i=a;i>=b;i-=step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define PLL pair<long long, long long>
#define PII pair<int, int>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define FILE_READ_IN freopen("input.txt","r",stdin);
#define FILE_READ_OUT fr(eopen("output.txt","w",stdout);
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;
// For ordered_set
using namespace __gnu_pbds;
template <typename T>
using ord_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 1e5;
const ll inf = 1e9;
const double pi = acos(-1);
const int N = 1e5+10;
ll dp[N][3];
ll r,s,p;
int n,k;
string a;

int winner(char a){
    if(a == 'r')return 1;
    if(a == 'p')return 2;
    return 0;
}
ll cost(int a){
    if(a == 0)return r;
    if(a == 1)return p;
    return s;
}
int main(){
    cin >> n >> k;
    cin >> r >> s >> p;
    cin >> a;
    loop(i,0,k){
        if(i >= a.size())break;
        dp[i][winner(a[i])] += cost(winner(a[i]));
    }
    loop(i,k,n){
        dp[i][0] = max(dp[i-k][1],dp[i-k][2]);
        dp[i][1] = max(dp[i-k][0],dp[i-k][2]);
        dp[i][2] = max(dp[i-k][1],dp[i-k][0]);
        dp[i][winner(a[i])]+=cost(winner(a[i]));
    }
    ll ans = 0;
    loop(i,0,k){
        if(i >= a.size())break;
        auto o = dp[n-1-i];
        ans+=max({o[0],o[1],o[2]});
    }
    cout << ans << "\n";
   return 0;
}

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

int a[100010];

signed main(){
    int n, k, q;
    cin >> n >> k >> q;
    for(int i=0;i<q;i++){
        int x;
        cin >> x;
        a[x]++;
    }
    for(int i=1;i<=n;i++){
        if(k-q+a[i] > 0) cout << "Yes\n";
        else cout << "No\n";
    }
}


Measured memory_bytes: 1408
import java.util.*;

public class Main {
	public static void main(String... args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		while (sc.hasNext()) {
			list.add(sc.nextInt());
		}
		Collections.sort(list,Comparator.reverseOrder());
		int cnt = 0;
		for (int i = 0 ; i < n / 2 ; i++) {
			cnt = cnt + list.get(i * 2) - list.get(i * 2 +1);
		}
		System.out.println(n % 2 == 1 ? cnt + list.get(n-1) : cnt);
	}
}


Measured memory_bytes: 23764
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	
	public static int dfs(final int n, int cur, int prev, int[][] adj, boolean do_back){	
		boolean leaf = true;
		int sum_cost = 0;
		
		int[] costs = new int[n];
		for(int next = 0; next < n; next++){
			if(next != prev && adj[cur][next] > 0){
				final int cost = dfs(n, next, cur, adj, true) + adj[cur][next] * 2;
				sum_cost += cost;
				costs[next] = cost;
				
				if(leaf){
					leaf = false;
				}
			}
		}
		
		int min_cost = sum_cost;
		if(!do_back && !leaf){
			for(int next = 0; next < n; next++){
				if(next != prev && adj[cur][next] > 0 && costs[next] > 0){
					min_cost = Math.min(min_cost, (sum_cost - costs[next]) + (adj[cur][next] + dfs(n, next, cur, adj, false)));
				}
			}
		}
		
		//System.out.println((cur + 1) + " " + (prev == -1 ? "-" : (prev + 1) + "") + " " + sum_cost + " " + min_cost);
		
		if(leaf){
			return -2 * adj[prev][cur];
		}else{
			return min_cost;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while (true) {
			final int N = sc.nextInt();
			
			if(N == 0){
				break;
			}
			
			int[][] adj = new int[N][N];
			for(int i = 0; i < N - 1; i++){
				final int from = sc.nextInt() - 1;
				final int to = sc.nextInt() - 1;
				final int cost = sc.nextInt();
				
				adj[from][to] = adj[to][from] = cost;
			}
			
			System.out.println(dfs(N, 0, -1, adj, false));
			
		}
	}

}

Measured memory_bytes: 23828
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

#define int ll

signed main(){
	int n;
	cin>>n;
	vector<int> a(n),b(n);
	rep(i,n)cin>>a[i]>>b[i];
	
	
	reverse(all(a));
	reverse(all(b));
	
	int sum=0;
	rep(i,n){
		int x = a[i]+sum;
		int y = b[i];
		if(x%y==0)continue;
		sum+=y-(x%y);
	}
	
	cout<<sum<<endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
typedef unsigned int ui;
int main(){
	int h, w;
	string s; int alf[26] = {};
	int cap1=0; int cap2=0;
	int i, j;
	cin >> h >> w;
	for (i = 0; i < h; i++) {
		cin >> s;
		for (j = 0; j < w; j++) {
			alf[s[j] - 'a']++;
		}
	}
	if (h % 2 == 1)cap2 += w / 2;
	if (w % 2 == 1)cap2 += h / 2;
	if (h % 2 == 1 && w % 2 == 1)cap1 = 1;
	for (i = 0; i < 26; i++) {
		if (alf[i] % 4 == 2)cap2--;
		else if (alf[i] % 2 == 1)cap1--;
	}
	if (cap1 >= 0 && cap2 >= 0)cout << "Yes" << endl;
	else cout << "No" << endl;
	char nyaa;
	std::cin >> nyaa;
	return 0;
}

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

int main(){
    int n,cnt=0;
    cin >> n;
    int a[n];
    bool flag=1;
    for(int i=0;i<n;i++) cin >> a[i];
    while(flag){
        flag=0;
        for(int i=n-1;0<i;i--){
            if(a[i]<a[i-1]){
                int b=a[i];
                a[i]=a[i-1];
                a[i-1]=b;
                cnt++;
                flag=1;
                }
        }
    }
    for(int i=0;i<n-1;i++) cout << a[i] << " ";
    cout << a[n-1] << endl;
    cout << cnt << endl;
}


Measured memory_bytes: 3096
use whiteread::parse_line;

fn main() {
    let (_n, x): (usize, usize) = parse_line().unwrap();
    let mut a: Vec<usize> = parse_line().unwrap();
    let ans: usize;

    if a.iter().sum::<usize>() == x {
        ans = a.len();
    } else {
        a.sort();
        loop {
            a.pop();
            if a.iter().sum::<usize>() <= x {
                ans = a.len();
                break;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define drep(i, n) for (int i=n; i>=0; --i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    vector<vector<int> > b(10), v(10);
    vector<ll> dp(2000);
    rep(i, n) {
        int c, g; cin >> c >> g; g--;
        b[g].push_back(c);
    }
    rep(i, 10) {
        sort(RALL(b[i]));
        v[i].push_back(0);
    }
    rep(i, 10) rep(j, b[i].size()) v[i].push_back(v[i][j]+b[i][j]+j*2);
    rep(i, 10) drep(j, k) {
        for (int h=max(0, j-(int)v[i].size()+1); h<j; ++h) {
            chmax(dp[j], dp[h]+v[i][j-h]);
        }
    }
    cout << dp[k] << endl;
    return 0;
}


Measured memory_bytes: 3180
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: [u32; 2],
    }
    println!("{}", a[0] * a[1] - a[0] - a[1] + 1);
}


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

typedef long long ll;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

// bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) {
//     return arg1.first > arg2.first;
// }

// template<class T> void chmin(T& a, T b) {
//     if (a > b) {
//         a = b;
//     }
// }

// template<class T> void chmax(T& a, T b) {
//     if (a < b) {
//         a = b;
//     }
// }

int main(void) {
    int d;
    cin >> d;

    if(d==25) cout << "Christmas" << endl;
    else if(d==24) cout << "Christmas Eve" << endl;
    else if(d==23) cout << "Christmas Eve Eve" << endl;
    else cout << "Christmas Eve Eve Eve" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <utility>
#include <set>
#include <climits>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 100005;

int parent[N];
int rk[N];
int ct[N];

void make(int n) {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        rk[i] = 0;
        ct[i] = 1;
    }
}

int find(int u) {
    if (u == parent[u]) {
        return u;
    } else {
        return parent[u] = find(parent[u]);
    }
}

void union_(int u, int v) {
    u = find(u);
    v = find(v);

    if (u == v) {
        return;
    }

    if (rk[u] < rk[v]) {
        parent[u] = v;
        ct[v] = ct[u] + ct[v];
    } else {
        parent[v] = u;
        ct[u] = ct[u] + ct[v];
        if (rk[u] == rk[v]) {
            ++rk[u];
        }
    }
}

int main() {
    int n, m;
    scanf ("%d %d", &n, &m);
    vector<pii> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf ("%d %d", &u, &v);
        edges.push_back(make_pair(u, v));
    }

    make(n);
    vector<ll> result;
    result.push_back(1LL * n * (n - 1) / 2);
    for (int i = m - 1; i >= 0; --i) {
        int u = find(edges[i].first);
        int v = find(edges[i].second);

        ll last = result.back();
        if (u == v) {
            result.push_back(last);
        } else {
            result.push_back(last - 1LL * ct[u] * ct[v]);
            union_(u, v);
        }
    }

    for (int i = m - 1; i >= 0; --i) {
        printf("%lld\n", result[i]);
    }
    return 0;
}



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

typedef long long ll;
typedef unsigned long long ull;
typedef string st;
typedef double db;
typedef vector<long long> vecll;
typedef vector<char> vechar;
ll mod = 1000000007;

int main(){
    ll n;
    cin >> n;
    cout << pow(n, 3) << endl;
}


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

int main() {
  int n;
  cin >> n;
  string s;
  rep(i,n) cin >> s;
  int j = n - 1, tmp = n - 1, ans = 0,end;
  for(int i = 0;i < n - 1;i++) {
    if(s[i] == 'W') {
      end = 0;
      for(j = tmp;j >= 1 + i;j--) {
        if(s[j] == 'R') {
          swap(s[i],s[j]);
          ans++;
          end = 1;
        }
        if(end) break;
      }
    tmp = j;
    }
    if(i + 1 == j) break;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3732
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
	int i, a = 0, b = 0;
	string s;
	cin >> s;
	for (i = 0; i < s.size(); i++) {
		if (s[i] == '0')
			a++;
		else
			b++;
	}
	printf("%d", min(a, b) << 1);
	return 0;
}

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(m);
    vector<int> d(m);
    for (int i = 0;i < n;i++){
        cin >> a.at(i) >> b.at(i);
    }
    for (int i = 0;i < m;i++){
        cin >> c.at(i) >> d.at(i);
    }
    vector<int> ans(n);
    for (int i = 0;i < n;i++){
        int mi = 1e9;
        for (int j = 0;j < m;j++){
            int dis = abs(a.at(i) - c.at(j)) + abs(b.at(i) - d.at(j));
            if (mi > dis){
                mi = dis;
                ans.at(i) = j + 1;
            }
        }
        cout << ans.at(i) << endl; 
    }
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        String[] tarou = new String[n];
        String[] hanako = new String[n];
        int tarou_score = 0;
        int hanako_score = 0;

        for(int i=0;i<n;i++){
            tarou[i] = stdIn.next();
            hanako[i] = stdIn.next();
        }
         
        for(int i=0;i<n;i++){
            if(tarou[i].compareTo(hanako[i])>0){
                tarou_score += 3;
            }
            else if(tarou[i].compareTo(hanako[i])<0){
                hanako_score += 3;
            }
            else{
                tarou_score += 1;
                hanako_score += 1;
            }
        }
         
        System.out.println(tarou_score+" "+hanako_score);
    }
}

Measured memory_bytes: 20824
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 3000100

ll fac[SIZE];
ll fac_in_memo[SIZE];

void factorial_init(int n){
  fac[0] = 1;
  for(int i=1;i<=n;i++) fac[i] = (i * fac[i-1])%mod;
}

ll factorial(int n,int M){
  ll ret=1;
  if(n<=1) return 1;
  return fac[n];
  
  for(int i=1;i<=n;i++){
    ret = (ret*i)%M;
  }
  
  return ret;
}

ll power(int k,int n,int M){
  if(n==0) return 1;
  if(n==1) return (ll)k;
  
  ll ret = power(k,n/2,M);
  
  ret=(ret*ret)%M;
  
  if(n%2==1)
    ret=(ret*k)%M;
  
  return ret;
}

ll fac_in(int k, int n, int M){
  if(fac_in_memo[k]) return fac_in_memo[k];
  return fac_in_memo[k] = power(k,n,M);
}

//nCm nPm nHm (mod M)

/*Combination*/
int C(int n,int m,int M){
  if(n<m) return 0;
  if(m==0 || n==m) return 1;
  
  ll chi = factorial(n,M);
  ll mot = (factorial(m,M) * factorial(n-m,M))%M;
  
  mot = power((int)mot,M-2,M);
  
  ll ret = (chi*mot)%M;
  
  return (int)ret;
}
/*Permutation*/
int P(int n,int m,int M){
  if(n<m) return 0;
  if(m==0) return 1;
  
  ll chi = factorial(n,M);
  ll mot = factorial(n-m,M);
  
  
  mot = power((int)mot, M-2,M);
  
  ll ret = (chi*mot)%M;
  
  return (int)ret;
}
/*Combination with Repetitions*/
int H(int n,int m,int M){
  if(n==0 && m==0) return 1;
  return C(n+m-1,m,M);
}



bool solve(){
  int a,b,c,sx,sy;

  scanf("%d%d%d%d%d",&a,&b,&c,&sx,&sy);

  if(a +b + c == 0) return false;
  
  if(sx < sy){
    swap(sx,sy);
    swap(a,b);
  }

  ll ans_sum = 0;
  
  for(int i=sx-sy;i<=sx;i++){
    int p = i;
    int q = i - (sx-sy);

    if(p < a || q < b || (a==0 && p>0) || (b==0 && q > 0)) continue;

    ll ans = 1;

    ans = (ans * C(p-1,a-1,mod))%mod;
    ans = (ans * C(q-1,b-1,mod))%mod;
    ans = (ans * C(sx-i+(c+b+a-1),c+b+a-1,mod))%mod;
    
    ans_sum = (ans_sum + ans)%mod;
  }
  
  ans_sum = (ans_sum * factorial(a+b+c,mod))%mod;
  ans_sum = (ans_sum * power(factorial(a,mod),mod-2,mod))%mod;
  ans_sum = (ans_sum * power(factorial(b,mod),mod-2,mod))%mod;
  ans_sum = (ans_sum * power(factorial(c,mod),mod-2,mod))%mod;

  printf("%lld\n",ans_sum);

  return true;
}

int main(){

  factorial_init(3000000);
  
  while(solve());
  
  return 0;
}

Measured memory_bytes: 26596
N = int(input())
L = list(map(int, input().split()))
tmp = 10 ** 12
after = sum(L)
before = 0
for i in range(N-1):
    before += L[i]
    after -= L[i]
    if abs(before -after) < tmp:
        tmp = abs(before -after)
print(tmp)

Measured memory_bytes: 23792
from itertools import accumulate
from operator import add

N, K = map(int, input().split())
xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

iXs = list(range(N))
iXs.sort(key=lambda iX: xs[iX])
odrXs = [0]*(N)
for odrX, iX in enumerate(iXs):
    odrXs[iX] = odrX
iYs = list(range(N))
iYs.sort(key=lambda iY: ys[iY])
odrYs = [0]*(N)
for odrY, iY in enumerate(iYs):
    odrYs[iY] = odrY

Ass = [[0]*(N) for _ in range(N)]
for odrX, odrY in zip(odrXs, odrYs):
    Ass[odrX][odrY] = 1

def getAccAss(Ass):
    accAss = [[0] * (len(Ass[0])+1)] + [accumulate([0] + As) for As in Ass]
    for x in range(1, len(accAss)):
        accAss[x] = list(map(add, accAss[x], accAss[x-1]))
    return accAss
def getRangeSum2D(accAss, xFr, xTo, yFr, yTo):
    return accAss[xTo+1][yTo+1] - accAss[xTo+1][yFr] - accAss[xFr][yTo+1] + accAss[xFr][yFr]

accAss = getAccAss(Ass)

ans = 10**20
for xFr in range(N-1):
    for xTo in range(xFr+1, N):
        for yFr in range(N-1):
            for yTo in range(yFr+1, N):
                num = getRangeSum2D(accAss, xFr, xTo, yFr, yTo)
                if num >= K:
                    area = (xs[iXs[xTo]]-xs[iXs[xFr]]) * (ys[iYs[yTo]]-ys[iYs[yFr]])
                    ans = min(ans, area)

print(ans)


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    A *= 100, B *= 100;
    double maxp = 0.0;
    int maxw = 0.0, maxs = 0.0;
    for(int i = 0; A * i <= F; ++i){
        for(int j = 0; A * i + B * j <= F; ++j){
            int W = A * i + B * j;
            if(W == 0)  continue;
            for(int k = 0; W + C * k <= F; ++k){
                if(C * k > W / 100 * E) break;
                for(int l = 0; W + C * k + D * l <= F; ++l){
                    int S = C * k + D * l;
                    if(S > W / 100 * E) break;
                    double P = 100.0 * S / (W + S);
                    if(P >= maxp){
                        maxp = P;
                        maxw = W;
                        maxs = S;
                    }
                }
            }
        }
    }
    cout << maxw + maxs << ' ' << maxs << endl;
}

Measured memory_bytes: 3616
import java.util.*

fun main(args: Array<String>) {
  val sc = Scanner(System.`in`)
  val n = sc.nextInt()
  val d = sc.nextInt()
  val x = sc.nextInt()
  val a = (1..n).map { sc.nextInt() }

  println(abc092b(n, d, x, a))
}

private fun abc092b(n: Int, d: Int, x: Int, a: List<Int>): Int {
  var count = 0

  for (ai in a) {
    var tmp = 0
    while (ai * tmp + 1 <= d) {
      tmp++
      count++
    }
  }

  return count + x
}


Measured memory_bytes: 31632
#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>;
using vv = vector<vector<ll>>;
template <class _t> inline bool chmax (_t& a,_t b){if(a<b){a=b;return true;}return false;} template <class _t> inline bool chmin (_t& a,_t b){if(a>b){a=b;return true;}return false;}

const long long inf = 1ll << 60;
const long long mod = 1000000007;

int dx[4] = {1,0,-1,0};int dy[4] = {0,-1,0,1};
using Graph = vector<vector<int> >;

int main() {
    int n,m;cin >> n >> m;
    Graph G(n+1);
    for(int i=0;i<m;i++){
	int a,b;cin >> a >> b;
	G[a].push_back(b);
	G[b].push_back(a);
    }   
    vector<int> dist(n+1,n+100);
    queue<P> que;
    dist [1] = 0; que.push(make_pair(1,0));
    vector<int> to(n+1,0);
    while(!que.empty()){
	P v = que.front();que.pop();
	for(int i=0;i<G[v.first].size();i++){
	    int nv;
	    nv = G[v.first][i];
	    if(dist[nv] == n+100){
		que.push(make_pair(nv,v.first));
		to[nv] = v.first;
		dist[nv] = dist[v.first]+1;
	    }
	}
    }
    bool ok = true;
    for(int i=1;i<=n;i++){
	if(dist[i] == n+100) ok = false;
    }
    if(ok){ 
	cout << "Yes" << endl;
	for(int i=2;i<=n;i++){
	    cout << to[i] << endl;
	}

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



    return 0;
}


Measured memory_bytes: 10872
let n, a, b = Scanf.scanf "%d %d %d\n" (fun n a b -> n, a, b)
let h = Array.init n (fun _ -> Scanf.scanf " %d" (fun i -> i))

let rec f l r =
  if l = r then r
  else
    let m = (l + r) / 2 in
    let rec g i tot =
      if i = n || tot < 0 then tot
      else
        let c = h.(i) - b * m in
        let tot = tot - if c > 0 then (c - 1) / (a - b) + 1 else 0 in
        g (i + 1) tot in
    let tot = g 0 m in
    if tot < 0 then f (m + 1) r
    else f l m

let () =
  let ans = f 0 1000000000 in
  Printf.printf "%d\n" ans


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

int main() {
  int n; cin >> n;
  int two=0, four=0, other=0;
  for(int i=0; i<n; i++) {
    int a;
    cin >> a;
    if(a%4==0) four++;
    else if(a%2==0) two++;
    else other++;
  }
  if((two==0 && other==four+1) || four>=other) cout << "Yes" << endl;
  else cout << "No" << endl; 
  return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;


int main(){
    ll N; cin >> N;
    vector<vector<int>> V(N);
    map<pair<int, int>, int> C;
    for(int i = 0; i < N-1; i++){
        int u, v, w; cin >> u >> v >> w; u--; v--;
        V[u].push_back(v);
        V[v].push_back(u);
        //C[u][v] = C[v][u] = w;
        C[make_pair(u, v)] = C[make_pair(v, u)] = w;
    }
    bool grid[N];
    memset(grid, false, sizeof(grid));
    vector<ll> D(N);
    grid[0] = true;

    queue<ll> Q; 
    Q.push(0);
    while(!Q.empty()){
        ll x = Q.front(); Q.pop();
        //cout << x << endl;
        for(auto v : V[x]){
            if(!grid[v]){
                grid[v] = true;
                Q.push(v);
                D[v] = D[x] + (ll)C[make_pair(x, v)];
            }
        }
    }
    for(int i = 0; i < N; i++){
        if(i == 0) cout << 1 << endl;
        else{
            if(D[i] % 2 == 0) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
}

Measured memory_bytes: 19328
import math
import collections
#X=int(input())
# N,M,Q=map(int,input().split())
# S=[[]for i in range(Q)]
# for i in range(Q):
#     a=list(map(int,input().split()))
#     S[i]=a
# ans=0
# print()

S=input()
if S=="ABC":
    print("ARC")
else:
    print("ABC")

Measured memory_bytes: 64904
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
bool broken[100001];
#define mod 1000000007
int main () {
    int n, m;
    cin >> n >> m;
    ll x[n + 1];
    memset(x, 0, sizeof(x));
    memset(broken, false, sizeof(broken));
    for (int i = 1; i <= m; i++) {
        int a;
        cin >> a;
        broken[a] = true;
    }
    x[1] = 1;
    x[2] = 2;
    if (broken[1]) {
        x[2] = 1;
    }
    for (int i = 3; i <= n; i++) {
        if ((broken[i - 1]) && (broken[i - 2])) {
            x[i] = 0;
        }
        else if (broken[i - 1]) {
            x[i] = x[i - 2];
        }
        else if (broken[i - 2]) {
            x[i] = x[i - 1];
        }
        else {
            x[i] = (x[i - 1] + x[i - 2]) % mod;
        }
    }
    cout << x[n] << endl;
    return 0;
}

Measured memory_bytes: 4468
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

struct UFTree {
private:
	vector<int> mNode;
	vector<int> mRank;

public:
	UFTree(int n) : mNode(n), mRank(n)
	{
		for (int i = 0; i < n; i++) {
			mNode[i] = i;
		}
	}

	int find(int x)
	{
		if (mNode[x] == x) {
			return x;
		}
		else {
			mNode[x] = find(mNode[x]);
			return mNode[x];
		}
	}

	void unite(int x, int y)
	{
		int idxX = find(x);
		int idxY = find(y);

		if (idxX == idxY) {
			return;
		}

		if (mRank[idxX] > mRank[idxY]) {
			mNode[idxY] = idxX;
		}
		else {
			mNode[idxX] = idxY;
			if (mRank[idxX] == mRank[idxY]) {
				mRank[idxY]++;
			}
		}
	}

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

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

	map<int, vector<int>> m;
	for (auto i = 0; i < N; ++i)
	{
		int K;
		cin >> K;
		for (auto j = 0; j < K; ++j)
		{
			int L;
			cin >> L;
			m[L].push_back(i);
		}
	}

	UFTree t(N);
	for (auto& p : m)
	{
		auto& list = p.second;
		if (list.size() <= 1)
		{
			continue;
		}

		auto x = list[0];
		for (auto i = 1; i < (int)list.size(); ++i)
		{
			t.unite(x, list[i]);
		}
	}

	auto ans = "YES";
	auto root = t.find(0);
	for (auto i = 1; i < N; ++i)
	{
		if (t.find(i) != root)
		{
			ans = "NO";
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7168
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=sum(a)
for i in range(n):
  if a[i]>=b[i]:
    a[i]-=b[i]
  else:
    b[i]-=a[i]
    a[i]=0
    if a[i+1]>=b[i]:
      a[i+1]-=b[i]
    else:
      b[i]-=a[i+1]
      a[i+1]=0
print(s-sum(a))

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

#define sz(x) ((int)x.size())

using namespace std;

const int MAXN = 8000 + 123, LIM = 8000;


struct chip {
	bool a[(MAXN << 1) + 123] = {}, null = false;
	bool& operator [] (int x) {
		if (x < - LIM || x > LIM)
			return null;
		return a[x + MAXN];
	}
} dp[MAXN], bp[MAXN];


string s;
int x, y, p, cnt;
deque<int> t[2];


int main() {
	cin >> s >> x >> y;
	for (auto i : s)
		if (i == 'T')
			t[p].push_back(cnt), cnt = 0, p = 1 - p;
		else
			cnt++;
	t[p].push_back(cnt);
	x -= t[0].front();
	t[0].pop_front();
	bp[0][0] = dp[0][0] = true;
	for (int i = 1; i <= t[0].size(); i++)
		for (int j = -LIM; j <= LIM; j++)
			dp[i][j] = dp[i - 1][j - t[0][i - 1]] || dp[i - 1][j + t[0][i - 1]];
	for (int i = 1; i <= t[1].size(); i++)
		for (int j = -LIM; j <= LIM; j++)
			bp[i][j] = bp[i - 1][j - t[1][i - 1]] || bp[i - 1][j + t[1][i - 1]];
	if (dp[t[0].size()][x] && bp[t[1].size()][y])
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

Measured memory_bytes: 129280
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
  ll n;cin>>n;
  ll a[n];
  for(ll i=0;i<n;++i)
    cin>>a[i];
  ll maxx=0,f=0;
  for(ll i=1;i<n;++i)
  {
     if(a[i-1] >= a[i])
        ++f;
     else
        f=0;
        maxx=max(maxx,f);
  }
        cout<<maxx;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef long long ll;
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = 10e15;
const ll MINF = -10e10;
const int INF = INT_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("~/Downloads/02.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;

int main() {
    ll n, d, a;
    cin >> n >> d >> a;

    vector<P> temp(n);
    rep(i, n) cin >> temp[i].first >> temp[i].second;
    sort(temp.begin(), temp.end());

    vector<ll> hit_points(n);
    vector<ll> positions(n);

    rep(i, n) positions[i] = temp[i].first;
    rep(i, n) hit_points[i] = (temp[i].second + a - 1) / a;

    vector<ll> attack_points(n, 0);

    ll count = 0;
    for (ll i = 0; i < n; i++) {
        if (i > 0)attack_points[i] += attack_points[i - 1];
        ll attack = hit_points[i];
        attack -= attack_points[i];
        if (attack <= 0) continue;
        count += attack;
        attack_points[i] += attack;
        ll start_position = positions[i];
        ll end_position = start_position + (d + d);
        {
            auto it = upper_bound(positions.begin(), positions.end(), end_position);
            if (it == positions.end()) continue;
            int range = it - positions.begin();
            attack_points[range] -= attack;
        }

    }
    cout << count << endl;

}


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

template <typename First, typename Second, typename Third>
struct triple
{
    First first;
    Second second;
    Third third;
};
#define ll long long
using namespace std;

void solve()
{
    ll x, y, z;
    cin >> x;
    vector<ll> v(x);
    for (int i = 0; i < x; i++)
        cin >> v[i];
   sort(v.begin(),v.end());
   ll sum = 0;
   for (int i = 1; i < x; i++)
       sum += (v[i] - v[i - 1]);
   cout << sum;
}
int main()
{

    std::ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 256