akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;i++)
int main() {
	int N, M, t, t2;
	ll c = 0;
	scanf("%d%d", &N, &M);
	vector<vector<int>> s(M);
	vector<int> p(M);
	rep(i, 0, M) {
		scanf("%d", &t);
		rep(i2, 0, t) {
			scanf("%d", &t2);
			s[i].push_back(t2 - 1);
		}
	}
	rep(i, 0, M)scanf("%d", &p[i]);
	int len = 1 << N, count, flag;
	rep(i, 0, len) {
		flag = 1;
		rep(i2, 0, M) {
			count = 0;
			for (auto t: s[i2]) {
				if(i & (1 << t))count++;
			}
			if (count % 2 != p[i2]) { flag = 0; break; }
		}
		if (flag)c++;
	}
	printf("%lld", c);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fast ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define pi 3.14159265358979323846264338327950LD
#define modd 1000000000
#define k 100000000

int main()
{
        fast;
        int t=1;
      //  cin>>t;
        while(t--)
        {
                int n;
                cin>>n;
                set<string> s;
                for(int i=0;i<n;i++)
                {
                        string str;
                        cin>>str;
                        s.insert(str);
                }
                cout<<s.size()<<endl;
        }
}

Measured memory_bytes: 19220
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int cnt ( int k ) {
  std::set<int> t;
  for(int i=1; i<=std::sqrt(k); i++) {
    if ( k % i == 0 ) {
      t.insert(i);
      t.insert(k/i);
    }
  }
  return t.size();
}

int main (void) {

  int N; std::cin >> N;

  int ans = 0;
  for(int i=1; i<=N; i++) {
    if ( i % 2 == 0 ) continue;
    if ( cnt(i) == 8 ) ans++; 
  }
  std::cout << ans << std::endl;
  return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

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

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl



int main(){
    int n;
    string s;
    cin>>n>>s;
    int x=0,m=0;
    REP(i,n){
        if(s[i]=='I'){
            chmax(m,++x);
        }else{
            --x;
        }
    }
    cout<<m<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
td=[list(map(int,input().split())) for i in range(n)]
td.sort(key=lambda x: -x[1])

dic={}
minlst=[]
maxlst=[]
ans=0
f=0
ln=0
for i in range(n):
    t,d=td[i]
    if i<k:
        f+=d
        if not t in dic:
            dic[t]=d
        else:
            minlst.append(d)
        ln=len(dic)
    else:
        if not t in dic:
            maxlst.append(-d)
            dic[t]=d
        else:
            pass

# print(td)
# print(minlst)
# print(maxlst)
# print(f)
# print(len(dic))
# ln=len(dic)
ans=max(ans,f+pow(ln,2))
heapq.heapify(minlst)
heapq.heapify(maxlst)
while minlst and maxlst:
    f-=heapq.heappop(minlst)
    f-=heapq.heappop(maxlst)
    ln+=1
    ans=max(ans,f+pow(ln,2))
print(ans)

Measured memory_bytes: 101592
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long 

int main(int argc, char const *argv[]){
	int n,red = 0,blue = 0;
	char str[107];
	scanf("%d",&n);
	scanf(" %s",str);
	for (int i = 0; i < n; ++i)
	{
		if(str[i] == 'R')	++red;
		else	++blue;
	}
	if(red > blue)	printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 128
import itertools

N, M, X = map(int, input().split())
C = []
As = []
for _ in range(N):
    vals = list(map(int, input().split()))
    C.append(vals[0])
    As.append(vals[1:])

ans = 10**10
for num in range(N):
    # num = 2
    comb = list(itertools.combinations(enumerate(C), num + 1))
    for vals in comb:
        # vals = comb[0]
        sum_c = 0
        l = [0 for _ in range(M)]
        for idx, c in vals:
            A = As[idx]
            for j in range(len(A)):
                l[j] += A[j]
            sum_c += c
        if min(l) >= X:
            ans = min(sum_c, ans)

if ans == 10**10:
    print(-1)
else:
    print(ans)


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

int main() {
  string s;
  cin >> s;
  bool okay = true;
  for (int i = 0; i < s.size(); ++i) {
    if (i & 1) {
      if (s[i] == 'R') {
        okay = false;
        break;
      }
    }
    else {
      if (s[i] == 'L') {
        okay = false;
        break;
      }
    }
  }
  if (okay) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

Measured memory_bytes: 256
class UnionFind
    def initialize(size)
        @parent = Array.new(size, -1)
    end

    def root(x)
        if @parent[x] < 0
            x
        else
            @parent[x] = root(@parent[x])
            @parent[x]
        end
    end

    def same_parent?(x, y)
        root(x) == root(y)
    end

    def merge(x, y)
        x_root = root(x)
        y_root = root(y)

        return false if x_root == y_root

        # merge technique
        if @parent[x_root] > @parent[y_root]
            tmp = y_root
            y_root = x_root
            x_root = tmp
        end

        @parent[x_root] += @parent[y_root]
        @parent[y_root] = x_root

        return true
    end

    def size(x)
        return -@parent[root(x)]
    end
end


def solve()
    n, m = gets.strip.split.map(&:to_i)
    abs = m.times.map { gets.strip.split.map(&:to_i) }.reverse

    ans = []
    uf = UnionFind.new(n)

    # 不便さ
    cur = (n * (n - 1)) / 2

    # 逆順にみていく(辺がない状態から辺を足していく)
    abs.each do |ab|
        ans.push(cur)

        a = ab.first - 1
        b = ab.last - 1

        # 同じ連結成分なら不便さは変わらない
        next if uf.same_parent?(a, b)

        # aとbをつなげると、
        # それぞれが属する連結成分の大きさをかけた数だけ行き来できるルートが増えるので
        # そのぶん不便さが減る
        size_a = uf.size(a)
        size_b = uf.size(b)
        cur -= size_a * size_b

        uf.merge(a, b)  # aとbをつなげる
    end

    ans.reverse.each { |a| puts a }
end


solve()


Measured memory_bytes: 13876
#include <iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
using namespace std;
using ll = long long;
ll gcd(ll m,ll n){
  if(n==0)return abs(m);
  return(gcd(n,m%n));
}
int main(){
  ll N;
  cin>>N;
  vector<ll> X(N),Y(N),H(N);
  for(ll i=0;i<N;++i){
    cin>>X[i]>>Y[i]>>H[i];
  }
  ll ansh,ansx,ansy;
  for(int i=0;i<=100;++i){
    for(int j=0;j<=100;++j){
      ll h;
      for(int k=0;k<N;++k){
        if(H[k]!=0){
          h=H[k]+abs(X[k]-i)+abs(Y[k]-j);
          break;
        }
      }
      bool flag=true;
      for(int k=0;k<N;++k){
        if(max(h-abs(X[k]-i)-abs(Y[k]-j),0ll)!=H[k])flag=false;
      }
      if(flag){
        ansh=h;
        ansx=i;
        ansy=j;
        break;
      }
    }
  }
  cout<<ansx<<" "<<ansy<<" "<<ansh<<endl;
  return 0;
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    set<char> st;
    while (k--) {
        char a;
        cin >> a;
        st.insert(a);
    }

    while (true) {
        string ans = to_string(n);
        bool flag = true;
        for (char an : ans) {
            if (st.find(an) != st.end()) {
                flag = false;
                n++;
                break;
            }
        }
        if (flag) {
            cout << ans << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
// Java program For handling Input/Output 
import java.io.*;
import java.util.*;
import java.math.*;
//import java.awt.*;

public class Main {
    BufferedReader br;
    StringTokenizer st;

    int max = -1;

    // actual logic
    void solve() throws IOException {
        long x = ni();
        long temp = 360;

        long i = 2;
        while (temp % x != 0) {
            temp = 360 * i;
            i++;
        }

        pl(temp / x);
    }

    int hcf(int a, int b) {
        if (a == 0)
            return b;

        return hcf(b % a, a);
    }

    // constructor
    Main() {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                System.out.println(e);
            }
        } catch (Exception e) {
            System.out.println(e);
        }
    }

    Main(String s) {
        try {
            br = new BufferedReader(new FileReader(s));
            st = new StringTokenizer(br.readLine());
        } catch (Exception e) {
            System.out.println(e);
        }
    }

    // main metohd
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    // Utility methods

    String ns() {
        if (!st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                System.out.println(e);
            }
        }
        return st.nextToken();

    }

    int ni() {
        return Integer.parseInt(ns());
    }

    long nl() {
        return Long.parseLong(ns());
    }

    double nd() {
        return Double.parseDouble(ns());
    }

    void pl(String s) {
        System.out.println(s);
    }

    void pl(long s) {
        System.out.println(s);
    }
}


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

int main(){
  ll n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  ll f = min(a,min(b,min(c,min(d,e))));
  if( n%f == 0 ){
    cout << n/f + 4 << endl;
  }else{
    cout << n/f + 5 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define pb push_back
#define fst first
#define snd second

typedef long long ll;
typedef pair<int,int> pii;
template<typename T> using min_queue=priority_queue<T,vector<T>,greater<T>>;

const ll MOD=1e9+7;

int N;
ll a[200100];

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

    cin>>N;
    for (int i=0;i<N;i++) cin>>a[i];
    sort(a,a+N,greater<ll>());

    int cnt=0;
    ll res = 0;
    for (int i=0;i<N;i++) {
      int z = i==0 ? 1 : 2;
      z = min(z, N-1-cnt);
      if (z==0) break;
      cnt += z;
      res += z * a[i];
    }
    cout << res << '\n';

    return 0;
}


Measured memory_bytes: 5260
#include "bits/stdc++.h"
#include <unordered_set>

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define INF 1000000000
#define PI 3.14159265358979323846

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

// N, E, S, W
const int dx[4] = { -1, 0,  1,  0 };
const int dy[4] = { 0, 1,  0, -1 };

typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<LL> vll;
//==============================================
int ans = 0;

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

	int n;
	cin >> n;

	vi A(n);
	REP(i, n) cin >> A[i];

	int ret = INF;
	for (int i = -100; i <= 100; i++) {
		int t = 0;
		REP(j, n) {
			t += (A[j] - i) * (A[j] - i);
		}

		ret = min(ret, t);
	}

	cout << ret << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long ll;
int main(){
  ll n,k;cin>> n>>k;
  double p[n],d[n],now,ans=0;
  for(ll i=0;i<n;i++){
    cin >> p[i];
    d[i]=(p[i]+1)/2;
  }
  for(ll i=0;i<k;i++){
    now+=d[i];
  }
  ans=now;
  for(ll i=k;i<n;i++){
    now-=d[i-k];now+=d[i];
    ans=max(ans,now);
  }
  cout <<fixed<<setprecision(10)<<ans<<endl;
}

Measured memory_bytes: 3328
/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second   
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define setval(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define trav(x , a) for(auto &x : a)
#define sz(a) ((int)a.size())
typedef long long ll ; 

#define int ll

using namespace std;

const int N = 3e5 +5 ;
const int mod = 1e9 + 7 ;
const ll inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

typedef pair<int, int> pii; 
typedef pair<int , pii> ipii ;
typedef pair<pii , int> piii ; 
typedef unsigned long long ull ;
typedef long double ld;

ll po(ll x,ll y,ll p = mod) {ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}

void solve()
{
    int n ;
    cin >> n; 
    int k = 2; 
    while(k * (k - 1) < 2LL * n) k++ ;
    if(k * (k - 1) != 2LL * n){
        cout << "No";
        return ;
    }
    int cnt = 0;
    vector<int> ans[k];
    cout << "Yes\n";
    cout << k << '\n' ;
    rep(i , k) repA(j , i + 1 , k - 1){
        ans[i].pb(++cnt);
        ans[j].pb(cnt);
    }
    rep(i , k){
        cout << sz(ans[i]) << ' ';
        trav(x , ans[i]) cout << x << ' ' ;
        cout << '\n';
    }
}   

     
int32_t main(int32_t argc, char *argv[])
{
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        cout << "\n" ;
    }
    return 0;
}

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

int main() {
    int x, h;
    while (cin >> x >> h) {
        if (x == 0 && h == 0) break;
        double _h = sqrt( x*x/4.0 + h*h );
        printf("%.6f\n", x*x + x * _h * 2);
//        cout << x*x + x * _h * 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
long long n,m,k,ans=0,cnt=0,tmp;
int main(){
  cin >> n;
  string s[n];
  map<string,int> mp;
  bool f=true;
  for(int i=0;i<n;i++){
    cin >> s[i];
    mp[s[i]]++;
    if(mp[s[i]]>1){
      f=false;
    }
  }
  if(!f){
    cout << "No" << endl;
    return 0;
  }
  for(int i=1;i<n;i++){
    if(s[i-1][s[i-1].size()-1]!=s[i][0]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<unordered_map>
#include <iomanip>
typedef long long ll;
using namespace std;
#define MOD 998244353
int main(){
    string s,t;cin>>s>>t;
    vector<vector<ll>> alpha(26);
    for(ll i=0;i<s.size();i++){
        alpha[s[i]-'a'].push_back(i);
    }
    ll ind=0;
    ll size=s.size();
    for(int i=0;i<t.size();i++){
        int c=t[i]-'a';
        ll pos=ind%size+(i!=0);
        auto itr=lower_bound(alpha[c].begin(),alpha[c].end(),pos);
        //sの途中で見つかった場合
        if((itr!=alpha[t[i]-'a'].end())){
            ind=ind-(ind%size)+(*itr);
        }
        //sの途中では見つからなかった場合
        else{
            ind=(ind+size)/size*size;//sの次の反復へ
            auto hoge=lower_bound(alpha[c].begin(),alpha[c].end(),0);
            if(hoge==alpha[c].end()){
                cout<<-1<<endl;
                return 0;
            }
            else{
                ind+=*hoge;
            }
        }
    }
    cout<<ind+1<<endl;
}


Measured memory_bytes: 1724
def main():
    N = int(input())
    strings = {}
    for _ in range(N):
        s = input()
        if s in strings.keys():
            strings[s] += 1
        else:
            strings[s] = 1
    strings = sorted(strings.items(), key=lambda x: x[1], reverse=True)
    maximum = strings[0][1]
    answer = []
    for s in strings:
        if s[1] == maximum:
            answer.append(s[0])
    answer.sort()
    for ans in answer:
        print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 43228
#include <iostream>

using namespace std;

const int MAX = 100000;
int seq[MAX];

int partition(int a[], int l, int r) {
    int x = a[r];
    int i = l - 1;
    for (int j = l; j < r; ++j) {
        if (a[j] <= x) {
            ++i;
            swap(a[j], a[i]);
        }
    }
    swap(a[i+1], a[r]);
    return i + 1;
}

int
main(int argc, const char *argv[])
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    int q = partition(seq, 0, n-1);

    for (int i = 0; i < n; ++i) {
        if (i) cout << " ";
        if (i == q) cout << "[";
        cout << seq[i];
        if (i == q) cout << "]";
    }
    cout << endl;

    return 0;
}

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


using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VPP vector<pair<int,pair<int,int>>>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)
typedef pair <int, int> P;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int  INF = 1 << 29;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;



int main() {

	ll n, k;
	cin >> n >> k;

	ll ans = n % k;

	ans = min(ans, k - ans);
	cout << ans << endl;



}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

import Data.Int

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = getLine >> readIntegers >>= print . solve . map fromIntegral

solve as = runST $ do
	let
		n = length as
	dp <- newArray ( ( 0, 0 ), ( n, 1 ) ) ( minBound `div` 2 :: Int64 ) :: ST s ( STUArray s ( Int, Int ) Int64 )
	writeArray dp ( 0, 0 ) 0
	forM_ ( zip [ 0 .. ] as ) $ \( i, a ) -> do
		forM_ [ 0, 1 ] $ \j -> do
			modifyArray dp ( i + 1, 0 ) =<< max . ( + ( if j == 0 then a else -a ) ) <$> readArray dp ( i, j )
			when ( i + 1 < n ) $ do
				modifyArray dp ( i + 1, 1 ) =<< max . ( + ( if j == 0 then -a else a ) ) <$> readArray dp ( i, j ) 
	readArray dp ( n, 0 )

Measured memory_bytes: 19836
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k,memo=0,sum=0,ans;
  char a0='z',a1;
  cin >>n>>k;
  for(int i=0;i<n;i++){
      cin >>a1;
      if(a0!=a1)sum+=1;
    a0=a1;
  }
  if(sum<=k*2){ans=n-1;}
  else{ans=n-(sum-k*2);}
  cout <<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
static const int MAX = 100000;
static const int NIL = -1;

int n;
vector<int> G[MAX];
int color[MAX];

void dfs(int r, int c)  {
  stack<int> S;
  S.push(r);
  color[r] = c;
  while (!S.empty())  {
    int u = S.top(); S.pop();
    for (int i = 0; i < G[u].size(); i++)  {
      int v = G[u][i];
      if (color[v] == NIL)  {
        color[v] = c;
        S.push(v);
      }
    }
  }
}

void assignColor()  {
  int id = 1;
  for (int i = 0; i < n; i++)  
    color[i] = NIL;
  for(int u = 0; u < n; u++)  {
    if (color[u] == NIL)
      dfs(u, id++);
  }
}

int main()  {
  int s, t, m, q;
 
  cin >> n >> m;
  
  for (int i = 0;i < m; i++)  {
    cin >> s >> t;
    G[s].push_back(t);
    G[t].push_back(s);
  }
  
  assignColor();
  
  cin >> q;
  
  for (int i = 0; i < q; i++)  {
    cin >> s >> t;
    if (color[s] == color[t])  {
      cout << "yes" << endl;
    }  else  {
      cout << "no" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 8940
(n, m) = map(int, input().split())
h = tuple(map(int, input().split()))
(a, b) = zip(*[tuple(map(int, input().split())) for _ in range(m)])

isgood = {}
for ni in range(1, n + 1):
    isgood[ni] = True

for mi in range(m):
    if h[a[mi] - 1] <= h[b[mi] - 1]:
        isgood[a[mi]] = False
    if h[b[mi] - 1] <= h[a[mi] - 1]:
        isgood[b[mi]] = False

ans = 0
for tow in isgood.keys():
    if isgood[tow]:
        ans += 1

print(ans)


Measured memory_bytes: 36716
//is there any case of -1 or any special corner cases ?
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define zeros(arr) memset(arr,0,sizeof(arr));
#define precise(num)  cout<<fixed; cout << std::setprecision(num)
#define nl cout<<"\n";
#define test int t;cin>>t;while(t--) 
const int maxx  = 3*1e5 , limit = 9*1e18 , MOD=1e9+7;
#define boost  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n';
int32_t main(){
    string s;
    cin>>s;
    if(s[s.size()-1]=='s'){
        s+="es";
    }else{
        s+='s';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
//#include <boost/lexical_cast.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define mp make_pair
#define endl '\n'
#define PI acos(-1)
#define bitcount(a) __builtin_popcountll(a)
#define P pair<int,int>
typedef tree<int,null_type,less_equal <int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

long mod=1e9+7;
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,d;
	cin>>n>>d;
	int dis[n][d];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<d;j++)
			cin>>dis[i][j];
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			int temp=0;
			for(int k=0;k<d;k++)
			{
				temp+=(dis[i][k]-dis[j][k])*(dis[i][k]-dis[j][k]);
			}
			int root=sqrt(temp);
			if(root*root==temp)
				++ans;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long 
#define endl "\n"
#define all(x) (x).begin(),(x).end()
const int MOD = (int)998244353;
const int mxN = 2e5+3;
const double EPS = 1e-9;

int t[4*mxN];

void build(int v, int tl, int tr){
	if(tl == tr)t[v] = 0;
	else{
		int tm = (tl + tr)/2;
		build(v*2, tl, tm);
		build(v*2 + 1, tm + 1, tr);
		t[v] = t[v*2] + t[v*2 + 1];
	}
}

void point_increment(int v, int tl, int tr, int pos, int add){
	if(tl == tr){
		t[v] = (t[v] + add)%MOD;
	}else{
		int tm = (tl + tr)/2;
		if(pos <= tm)point_increment(v*2, tl, tm, pos, add);
		else point_increment(v*2 + 1, tm + 1, tr, pos, add);
		
		t[v] = (t[v*2] + t[v*2 + 1])%MOD;
	}
}

int range_query(int v, int tl, int tr, int l, int r){
	if(l > r)return 0;
	if(l == tl and r == tr)return t[v]%MOD;
	int tm = (tl + tr)/2;
	return (range_query(v*2, tl, tm, l, min(tm,r))%MOD + range_query(v*2 + 1, tm + 1, tr, max(tm+1, l), r)%MOD) %MOD;
}

void solve(){
	int n,k;
	cin >> n >> k;
	vector<pair<int, int>> v(k);
	for(int i = 0; i < k; ++i)cin >> v[i].first >> v[i].second;
	build(1, 0, n - 1);
	vector<int> dp(n+1,0);
	dp[1] = 1;
	point_increment(1, 0, n - 1, 0, 1);
	for(int i = 2; i <= n; ++i){
		for(int j = 0; j < k; ++j){
			if(i - v[j].first > 0){
				int r = (i - v[j].first) - 1;
				int l = max(0ll, i - v[j].second - 1);
				dp[i] = (range_query(1, 0, n - 1, l, r))%MOD;
				point_increment(1, 0, n - 1, i - 1, dp[i]);
			}
		}
	}
	// doubts about segtree in general 
	// does going back / going front matters at all
	// going back can solve this problem
	int fin = range_query(1, 0, n - 1, n - 1, n - 1);
	cout << fin << endl;
}

int32_t main(){
	IO;
	
	int nT = 1;
	//cin >> nT;
	for(int i = 1; i <= nT; ++i)
		solve();
	return 0;
}


Measured memory_bytes: 9036
S = input()
S1 = S[: len(S) // 2]
S2 = S[(len(S) // 2) + 1 :]

ans = "Yes"

for i in range(len(S) // 2):
    if S[i] != S[-1 - i]:
        ans = "No"
for i in range(len(S1) // 2):
    if S1[i] != S1[-1 - i]:
        ans = "No"
for i in range(len(S2) // 2):
    if S2[i] != S2[-1 - i]:
        ans = "No"

print(ans)


Measured memory_bytes: 3064
from functools import *
MOD=10**9+7
@lru_cache(maxsize=None)
def solve(L,R):
  if L > R: return 0
  if L == 1: return (1 + solve(2, R)) % MOD
  return (solve(L//2,(R-1)//2) + solve((L+1)//2,R//2) + solve((L+1)//2,(R-1)//2)) % MOD
  
print(solve(*map(int,input().split())))

Measured memory_bytes: 38512
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 3648
#include <algorithm>
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define Rep(i,n) for(ll i=1;i<=n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
#define prique priority_queue<ll>
const int mod = 1000000007;
const int mod2 = 998244353;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % mod;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
long nCr(int n, int r) {
	int ans = 1;
	for (ll i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (ll i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
int n,m,a[100010],b[100010],s[100010];
signed main() {
	cin>>n>>m;
	rep(i,m){
		cin>>a[i]>>b[i];
		a[i]--;
		b[i]--;
		s[a[i]]++;
		s[b[i]]++;
	}
	rep(i,n){
		if(s[i]%2){cout<<"NO"<<endl;ggr}
	}
	cout<<"YES"<<endl;ggr
	
}


Measured memory_bytes: 2560
#!/usr/bin/env ruby

N, x = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)

count = 0; total = 0

(0...N-1).each{|i|
    if as[i] + as[i+1]>x
        count = [as[i]+as[i+1]-x, as[i+1]].min
        as[i+1] -= count
        total += count
        if as[i] > x
            count = as[i] - x
            as[i] -= count
            total += count
        end
    end
}
puts total

Measured memory_bytes: 11148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
ll combi(ll n,ll k) {
  if (n==k || k==0) return 1;
  else return combi(n-1,k-1)+combi(n-1,k);
}
int main(){
  ll n,p,count_odd=0;
  cin>>n>>p;
  vll a(n);
  for (ll i=0;i<n;i++) {
    cin>>a[i];
    a[i] %= 2;
    count_odd += a[i];
  }
  ll count_even = n-count_odd, ans=0;
  if (p==0) {
    for (ll i=0;i<=count_odd/2;i++) ans+=combi(count_odd,2*i);
    ans*=pow(2,count_even);
  }
  else {
    if (count_odd>0) {
      for (ll i=0;i<(count_odd+1)/2;i++) ans+=combi(count_odd,2*i+1);
      ans*=pow(2,count_even);
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#include <cstring>
#include <queue>

#define unless(c) if (!(c))
#define each(i, c) for (auto& i: c)

using namespace std;

class State{
public:
  int sec, x, y, bit, cost;

  State() {}
  State(int sec, int x, int y, int bit, int cost) :
    sec(sec), x(x), y(y), bit(bit), cost(cost) {}

  bool operator<(const State &st) const {
    return cost > st.cost;
  }
};

int W, H, N;
int sx, sy;
int L[5], pathX[5][40], pathY[5][40];

bool closed[42][22][22][1<<5];

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

void solve() {
  priority_queue<State> open;
  memset(closed, 0, sizeof(closed));
  open.push(State(0, sx, sy, 0, 0));

  while(!open.empty()) {
    State st = open.top();
    open.pop();

    int nbit = st.bit;
    bool dameFlg = false;

    for (int j = 0; j < N; j++) {
      if ((st.bit & (1 << j)) != 0) continue;
      if (st.sec >= L[j] - 1) {
	dameFlg = true;
	break;
      }
      if (st.x == pathX[j][st.sec] && st.y == pathY[j][st.sec]) {
	nbit |= (1 << j);
      }
    }

    if (dameFlg) continue;

    st.bit = nbit;

    if (closed[st.sec][st.x][st.y][st.bit]) continue;
    closed[st.sec][st.x][st.y][st.bit] = true;

    if (st.bit == (1 << N) - 1) {
      cout << st.cost << endl;
      return;
    }

    for (int i = 0; i < 9; i++) {
      int nx = st.x + dx[i];
      int ny = st.y + dy[i];

      if (nx < 0 || W <= nx || ny < 0 || H <= ny) continue;

      bool seniFlg = true;

      // bakudan check
      for (int j = 0; j < N; j++) {
	int idx = L[j] - 1;
	if (nx == pathX[j][idx] && ny == pathY[j][idx]) {
	  seniFlg = false;
	  break;
	}
      }

      if (!seniFlg) continue;

      open.push(State(st.sec + 1, nx, ny, st.bit, st.cost+1));
    }
  }

  cout << -1 << endl;
}

int main(void)
{
  while (cin >> W >> H >> N) {
    cin >> sx >> sy;
    sx--;
    sy--;

    for (int i = 0; i < N; i++) {
      cin >> L[i];
      for (int j = 0; j < L[i]; j++) {
	cin >> pathX[i][j] >> pathY[i][j];
	pathX[i][j]--;
	pathY[i][j]--;
      }
    }

    solve();
  }
}

Measured memory_bytes: 4396
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
using namespace std;
int main(){
	
	string s[8];
	vector<string> t(8,"        ");
	for(int i=0;i<8;i++){
		cin>>s[i];
	}
	
	for(int i=1;i<=3;i++){
		cout<<90*i<<endl;
		for(int j=0;j<8;j++){
			for(int k=0;k<8;k++){
				t[k][j]=s[7-j][k];
			}
		}
		for(int j=0;j<8;j++){
			cout<<t[j]<<endl;
			s[j]=t[j];
		}
	}
	
	
	
}

Measured memory_bytes: 1196
using Atcoder;
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var first = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var a = first[0] * first[1];
            if (a <= first[2])
            {
                Console.Write(a);
            }
            else
            {
                Console.Write(first[2]);
            }

        }
        //static void Main(string[] args)
        //{
        //    var temp = new Atcoder.ABC130.D();
        //    temp.Run();
        //}

    }
}

Measured memory_bytes: 13396
#include <cstdio>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>


using namespace std;

int main(void)
{
    string str;
    while(getline(cin, str)){
        istringstream sin(str);
        long long a, b;
        sin >> a >> b;
        a += b;
        int digit = 0;
        while(a){
            ++digit;
            a /= 10;
        }
        cout << digit << endl;
    }
    
    return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> p2;
ll res=0;
void bfs(p2 a,vector<string> &v){
    queue<p2> q;
    ll d[25][25],n=v.size(),m=v[0].size();
    for(ll i=0;i<25;i++)
    for(ll j=0;j<25;j++)
    d[i][j]=0;
    q.push(a);
    d[a.first][a.second]=1;
    while(!q.empty()){
        ll i=q.front().first,j=q.front().second;
        q.pop();
        res=max(res,d[i][j]-1);
        if(i>0&&v[i-1][j]=='.'&&d[i-1][j]==0){
            q.push({i-1,j});
            d[i-1][j]=d[i][j]+1;
        }
        if(i<n-1&&v[i+1][j]=='.'&&d[i+1][j]==0){
            q.push({i+1,j});
            d[i+1][j]=d[i][j]+1;
        }
        if(j>0&&v[i][j-1]=='.'&&d[i][j-1]==0){
            q.push({i,j-1});
            d[i][j-1]=d[i][j]+1;
        }
        if(j<m-1&&v[i][j+1]=='.'&&d[i][j+1]==0){
            q.push({i,j+1});
            d[i][j+1]=d[i][j]+1;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll h,w;
    cin>>h>>w;
    vector<string> v(h);
    for(ll i=0;i<h;i++)
    cin>>v[i];
    for(ll x=0;x<h;x++)
    for(ll y=0;y<w;y++)
    if(v[x][y]=='.')
    bfs({x,y},v);
    cout<<res;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int n,k,r,s,p,i,f,u[100000];
  char t[100000];
  scanf("%d %d",&n,&k);
  scanf("%d %d %d",&r,&s,&p);
  scanf("%s",t);
  f=0;
  /*printf("%d %d\n",r,p);*/
  /*printf("%c %c %c\n",t[0],t[1],t[2]);*/
  for(i=0;i<k;i++){
    if(t[i]=='r'){
      f=f+p;
      u[i]=1;
      /*printf("%d p\n",f);*/
    }
    else if(t[i]=='s'){
      f=f+r;
      u[i]=2;
      /*printf("%d r\n",f);*/
    }else{
      f=f+s;
      u[i]=3;
      /*printf("%d s\n",f);*/
    }
    /*printf("%d\n",f);*/
  }
  /*printf("%d\n",f);*/
  for(i=k;i<n;i++){
    /*printf("%d\n",f);*/
    /* if(t[i]!=t[i-k]||(t[i]==t[i-k]&&s[i-k]!=11&&s[i-k]!=12&&s[i-k]!=13)){*/
    if(t[i]=='r'&&u[i-k]!=1){
      f=f+p;
      u[i]=1;
    }
    else if(t[i]=='r'&&u[i-k]==1){
      u[i]=0;
    }
    else if(t[i]=='s'&&u[i-k]!=2){
      f=f+r;
      u[i]=2;
    }
    else if(t[i]=='s'&&u[i-k]==2){
      u[i]=0;
    }
    else if(t[i]=='p'&&u[i-k]!=3){
      f=f+s;
      u[i]=3;
    }
    else{
      u[i]=0;
    }
    /* printf("%d\n",f);*/
  }
  printf("%d\n",f);
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<algorithm>
using namespace std;
int c[30];
int gcd(int a,int b){
	while(a){
		b%=a;int c=a;a=b;b=c;
	}
	return b;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		long long val=0;
		long long sum=0;
		for(int i=0;i<b;i++)scanf("%d",c+i);
		for(int i=0;i<(1<<b);i++){
			long long lcm=1;
			int cnt=__builtin_popcount(i);
			for(int j=0;j<b;j++)if(i&(1<<j)){
				lcm=lcm/gcd(lcm,c[j])*c[j];
				if(a<lcm)break;
			}
			long long n=a/lcm;
			if(n){
				if(i%2){
					val-=n;
					sum-=n*(n+1)/2*lcm;
				}else{
					val+=n;
					sum+=n*(n+1)/2*lcm;
				}
			}
		}
		if(val==0){
			printf("0\n");
			continue;
		}
		printf("%.12f\n",(double)sum/val);
	}
}

Measured memory_bytes: 1056
#include <stdio.h>
int main() {
	int a, b, c, x, ans = 0;
	scanf("%d%d%d%d", &a, &b, &c, &x);
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			for (int k = 0; k <= c; k++) {
				if (500 * i + 100 * j + 50 * k == x) {
					ans++;
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
import math
while True:
    a,b,c=input().split()
    a=int(a)
    c=int(c)
    if b == "+":
        print("{}".format(a+c))
    elif b == "-":
        print("{}".format(a-c))
    elif b == "*":
        print("{}".format(a*c))
    elif b == "/":
        print("{}".format(a//c))
    else:
        break


Measured memory_bytes: 5652
#ABC087-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n=I()
A=IL()
B=IL()
for i in range(n-1):
    A[i+1]+=A[i]
    B[i+1]+=B[i]
A=[0]+A
B=[0]+B
ans=0
for i in range(n):
    ans=max(ans,A[i+1]+B[-1]-B[i])
print(ans)

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n;
vector<P> es;
vector<P> g[100010];
ll s[100010];
ll res[100010];
ll cnt[100010];
ll cnt2[100010];

void dfs(ll v,ll p){
  for(P e : g[v]){
    ll nv=e.fi;
    if(nv==p)continue;
    dfs(nv,v);
    cnt[v]+=cnt[nv];
  }
  cnt[v]++;
}

ll dfs2(ll v,ll p){
  ll r=0;
  for(P e : g[v]){
    ll nv=e.fi;
    if(nv==p)continue;
    r+=dfs2(nv,v);
    cnt2[v]+=cnt2[nv];
    r+=cnt2[nv]*res[e.se];
  }
  cnt2[v]++;
  return r;
}

int main(){
	cin>>n;
  rep(i,n-1){
    ll a,b;
    cin>>a>>b;
    a--; b--;
    es.push_back(P(a,b));
    g[a].push_back(P(b,i));
    g[b].push_back(P(a,i));
  }
  rep(i,n)cin>>s[i];

  dfs(0,-1);

  rep(i,n-1){
    ll v=es[i].fi,u=es[i].se;
    if(cnt[v]<cnt[u])swap(v,u);
    ll szu=cnt[u],szv=n-cnt[u];
    if(szu==szv)continue;
    res[i]=abs(s[u]-s[v])/abs(szu-szv);
  }

  rep(i,n-1){
    if(res[i]==0){
      ll v=es[i].fi,u=es[i].se;
      if(cnt[v]<cnt[u])swap(v,u);
      ll szu=cnt[u],szv=n-cnt[u];
      s[u]-=dfs2(u,v);
      s[u]-=dfs2(v,u);
      res[i]=s[u]/szv;
    }
  }

  rep(i,n-1){
    cout<<res[i]<<endl;
  }
	return 0;
}


Measured memory_bytes: 17264
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {

int a,b;
cin >> a >> b;
cout << a/b << " " << a%b << " ";
double f;
f = (double)a/b;
cout << fixed << setprecision(5) << f << endl;
}



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

const int N = 405;
int n, m, f[N], delta[N];
bool mark[N], ok[N];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> m;
	for (int i = 0; i <= m * 2; ++i) f[i] = i;
	for (int i = 0; i < n; ++i) {
		int a, b, c, d; std::cin >> a >> b >> c >> d;
		int L = (c ?: -a) + m, R = (d ? -d : b) + m;
		mark[L] = mark[R] = 1, f[find(L)] = find(R);
		++delta[L], --delta[R];
	}
	for (int i = 0; i <= m * 2; ++i) if (mark[i])
		if (delta[i] > 0 && i > m || delta[i] < 0 && i < m)
			return std::cout << "NO\n", 0;
	for (int i = 0; i <= m * 2; ++i) ok[find(i)] |= delta[i] != 0;
	for (int i = 0; i <= m * 2; ++i)
		if (mark[i] && i == find(i) && !ok[i])
			return std::cout << "NO\n", 0;
	std::cout << "YES\n";
	return 0;
}

Measured memory_bytes: 256
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 Data.Foldable (foldMap)
import Data.List.Split
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
applyWhen :: (a -> Bool) -> a -> a -> a
applyWhen f subs orig = if f orig then subs else orig
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
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)
-- end of templete

leap x = mod x 400 == 0 || (mod x 100 /= 0 && mod x 4 == 0)

main = intercalate [""] . map (applyWhen (==[]) ["NA"] . map show . filter leap . range . apply2 (,)) . takeWhile (any (/=0)) . map (map readInt . words) . lines <$> getContents>>= mapM_ putStrLn

Measured memory_bytes: 4260
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define vint vector<ll>
#define pb push_back
#define all(v) v.begin(),v.end()
#define ios cin.sync_with_stdio(false),cin.tie(NULL)
#define f_(i,m,n) for(ll i=m;i<n;i++)
#define ff first
#define ss second
const int INF=1e9 +7;
const int MOD=998244353;
ll bs;

void solve(){
	ll n;
	cin>>n;
	vector<pair<ll,pair<ll,ll>>> v;
	f_(i,0,n){
		ll a,b,c;
		cin>>a>>b>>c;
		v.pb(make_pair(a, make_pair(b,c)));
	}

	ll dp[n+1][3];

	dp[0][0]=v[0].ff;
	dp[0][1]=v[0].ss.ff;
	dp[0][2]=v[0].ss.ss;

	f_(i,1,n){
		dp[i][0]=v[i].ff+ max(dp[i-1][1], dp[i-1][2]);
		dp[i][1]=v[i].ss.ff + max(dp[i-1][0] , dp[i-1][2]);
		dp[i][2]=v[i].ss.ss + max(dp[i-1][0], dp[i-1][1]);
	}

	cout<< max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]))<<endl;
	return;
}

int main(){
	ll t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 7988
#include <iostream>
#include <vector>

using namespace std;
int main() {
    int N; cin >> N;
    double sum = 0;
    for (int i = 0;i < N;i++) {
        double a;
        string b;
        cin >> a;
        cin >> b;
        if (b == "BTC") {
            a = a * 380000.0; 
        }
        sum += a;
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cmath>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
using namespace std;

int N;
struct edge{
    vector <int> to;
    vector <int> cost;
};

vector <int> result;
vector <edge> gragh;

void dfs(int now){
    vector <int> next = gragh[now].to;
    vector <int> costs = gragh[now].cost;
    //cout<<"now"<<" "<<now<<" "<<result[now]<<endl;
    //cout<<"next"<<endl;
    //for(int i=0;i<next.size();i++) cout<<next[i]<<" "<<result[next[i]]<<endl;
   // for(int i=1;i<;i++) cout<<cost[i]<<endl;
   // cout<<endl;

    for(int i=0;i<next.size();i++){
        if(result[next[i]] != 1000) continue;
        result[next[i]] = result[now] + costs[i];
      //  cout<<costs[next[i]]<<endl;
        result[next[i]] = result[next[i]] % 2;
       //cout<<'&'<<endl;
        dfs(next[i]);
    }


}



int main(){
    cin>>N;
    result.resize(N+10,1000);
    gragh.resize(N+1);
    result[1] = 1;
    for(int i=1;i<=N-1;i++){
        int u,v,w; cin>>u>>v>>w;
        gragh[u].to.push_back(v);
        gragh[u].cost.push_back(w%2);
        gragh[v].to.push_back(u);
        gragh[v].cost.push_back(w%2);
     //   cout<<'%'<<endl;
    }
   dfs(1);
    
for(int i=1;i<=N;i++){
    cout<<result[i]<<endl;
}

    return 0;
}

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

int main(){
  string s;
  cin >> s;
  int n = s.length();
  vector<int> mp(1<<26,INF);
  vector<int> dp(n+1,INF);
  int v = 0;
  mp[0] = 0;
  rep(i,n) {
    int c = s[i] - 'a';
    v ^= (1<<c);
    rep(j,26) {
      int b = v ^ (1<<j);
      if(mp[b] < INF) dp[i+1] = min(dp[i+1],mp[b]+1);
    }
    mp[v] = min(mp[v],dp[i+1]);
  }
  cout << (v == 0 ? 1 : dp[n]) << endl;
  return 0;
}

Measured memory_bytes: 266540
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define INF 1000000000000000000
#define MOD 1000000007
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing

int main() {
	string s;
	cin >> s;
	int n = (int) s.size();
	vector <string> v({"dream", "dreamer", "erase", "eraser"});
	while (n > 0) {
		bool ok = false;
		for (int i = 0; i < 4; i++) {
			if (n >= (int) v[i].size()) {
				if (s.substr(n - (int) v[i].size(), (int) v[i].size()) == v[i]) {
					n -= (int) v[i].size();
					ok = true;
					break;
				}
			}
		}
		if (!ok) {
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES";
}


Measured memory_bytes: 512
# print('input >>')
A, V = map(int,(input().split()))
B, W = map(int,(input().split()))
T = int(input())


if W >= V:
    print('NO')
elif abs(B-A) / (V-W) <= T:
    print('YES')
else:
    print('NO')

# print('-----output-----')

Measured memory_bytes: 9208