akhauriyash/Code-Regression huggingface dataset:
#bfs 
#0#000  1#100 1#120 1#123
#00000  01010 21212 21212
#000#0  001#1 021#1 321#1
#000#0  001#1 021#1 321#1

from collections import deque

h,w = map(int,input().split())
lis = [input() for x in range(h)]

vy = [0,0,1,-1]
vx = [1,-1,0,0]

reached = [[-1]*w for x in range(h)]
def bfs(bk_lis):
    q = deque()
    for i in bk_lis:
        q.append(i)
        reached[i[0]][i[1]]=0
    while q:
        y,x = q.popleft()
        for dy,dx in zip(vy,vx):
            ny,nx = y+dy,x+dx
#                print(ny,nx)
            if not(0<=ny<h and 0<=nx<w):
                continue#範囲の確認
            if  reached[ny][nx]==-1 or reached[ny][nx]>reached[y][x]+1:
                reached[ny][nx] = reached[y][x]+1
                q.append([ny,nx])
#        print(reached)
bk_lis = []
ans=0
for y in range(h):
    for x in range(w):
        if lis[y][x] == '#':
            bk_lis.append([y,x])
#print(bk_lis)
bfs(bk_lis)
for y in reached:
    ans = max(max(y),ans)
#for x in reached:
#    print(x)
print(ans)


Measured memory_bytes: 155276
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
constexpr double pi=3.14159265358979;

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;
}
using namespace std;

vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}


void solve(){
    int n;
    cin>>n;
    int sum=0;
    vector<int>l(2*n);
    rep(i,2*n)cin>>l[i];
    sort(begin(l),end(l));
    for(int i=0;i<2*n;i+=2){
      sum+=l[i];
    }
    cout<<sum<<"\n";
    return;
}

signed main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
#include <queue>
#include <string>
#define pb push_back
#define mod 1000000007
#define all(x) x.begin(),x.end()
#define inf (int)(1e9)
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;

int main(void){
  string s;
  cin>>s;
  if(s.size()==2){
    if(s[0]==s[1]) cout<<"1 2"<<endl;
    else cout<<"-1 -1"<<endl;
    return 0;
  }
  for(int i=0;i<s.size()-2;i++){
    if(s[i]==s[i+1]||s[i+1]==s[i+2]||s[i]==s[i+2]){
      cout<<i+1<<" "<<i+3<<endl;
      return 0;
    }
  }
  cout<<"-1 -1"<<endl;
  return 0;
}


Measured memory_bytes: 512
def count_digits(n)
  Math.log10(n.abs).to_i + 1
end

N = gets.to_i
X = count_digits(N)

if X == 6
  puts 90909
elsif X == 5
  puts 909 + (N - 9999)
elsif X == 4
  puts 909
elsif X == 3
  puts 9 + (N - 99)
elsif X == 2
  puts 9
else
  puts N
end


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

int64_t lucas(int n, vector<int64_t> &memo_array){
    
    int64_t ans;

    if (n == 0) {
        return 2;
    } else if (n == 1) {
        return 1;
    }

    if(memo_array.at(n) != 0) {
        return memo_array.at(n);
    }

    ans = (int64_t)lucas(n - 1 , memo_array) + lucas(n - 2, memo_array);

    memo_array.at(n) = ans;

    return ans;
}

int main() {
    //変数定義
    int N;

    //入力処理
    cin >> N;

    vector<int64_t> memo_array(N+1,0);
    //処理

    //出力処理
    cout << lucas(N, memo_array) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	
	int s;
	scanf("%d",&s);
	int m = s / 60;
	s = s % 60;
	int h = m / 60;
	m = m % 60;
	printf("%d:%d:%d\n",h,m,s);
	
	return 0;
}


Measured memory_bytes: 592
let rec loop u =
  let line = read_line () in
  if line = "-" then ()
  else
    let m = read_int () in
    let rec read s i = match i with
        0 -> print_endline s
      | i -> (let h =read_int () in
              read ((String.sub s h ((String.length s)-h))^(String.sub s 0 h)) (i-1))
    in read line m;loop u;;

let () = loop ();;

Measured memory_bytes: 2104
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, n) for (size_t i = 0; i < (n); i++)
#define REP(n) FOR(i, n)
#define cinv(v, n) REP(n) {cin>>(v)[i];}
#define nvec(T, v, n) vector<T> v(n); cinv(v, n)
#define npairs(T1, T2, v, n) vector<pair<T1, T2>> v(n); REP(n){cin>>v[i].first>>v[i].second;}
#define ntuples(T1, T2, T3, v, n) vector<tuple<T1, T2, T3>> v(n); REP(n){cin>>get<0>(v[i])>>get<1>(v[i])>>get<2>(v[i]);}
 
#define min_index(v) size_t( min_element(all(v)) - (v).begin() )
#define max_index(v) size_t( max_element(all(v)) - (v).begin() )
#define min_e(v) *min_element(ALL(v))
#define max_e(v) *max_element(ALL(v))
 
#define count_le(v, a) size_t( upper_bound(ALL(v), a) - (v).begin() )
#define count_lt(v, a) size_t( lower_bound(ALL(v), a) - (v).begin() )
#define count_ge(v, a) size_t( (v).end() - lower_bound(ALL(v), a) )
#define count_gt(v, a) size_t( (v).end() - upper_bound(ALL(v), a) )
 
#define order(neq_sl) [](const auto s, const auto l){return neq_sl;}
#define make_lr(v,type,l,r) vector<type> l(n+1),r(n+1);FOR(i,n){l[i+1]=l[i]+v[i];r[i+1]=r[i]+v[n-1-i];}
 
#define acm accumulate
#define pub push_back
#define pof pop_front
#define SUM(v) accumulate(ALL(v), 0l)
#define SORT(v) sort(ALL(v))
 
#define GCD(v) gcd(ALL(v), 0l)
 
template <typename T>
T gcd(T a, T b) {
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b%a, a);
}
template <typename InputItr, typename T>
T gcd(InputItr first, InputItr last, T init) {
    for (; first != last; ++first) init = gcd(init, *first);
    return init;
}
 
 
 
int main(){
  long n;
  cin>>n;
  cout<<n*(n+1)/2-3*(n/3)*(n/3+1)/2-5*(n/5)*(n/5+1)/2+15*(n/15)*(n/15+1)/2;
}
 
 
 
 
 
 
/* きょむ〜 */

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

string s;
int it, n;
int vals;

int formula() {
	int res;
	if (s[it] == '-') {
		it++;
		res = 2 - formula();
	}
	else if ('0' <= s[it] && s[it] <= '2') {
		res = s[it] - '0';
		it++;
	}
	else if (s[it] == 'P') {
		it++;
		res = vals % 3;
	}
	else if (s[it] == 'Q') {
		it++;
		res = vals / 3 % 3;
	}
	else if (s[it] == 'R') {
		it++;
		res = vals / 9;
	}
	else {
		assert(s[it++] == '(');
		res = formula();
		if (s[it] == '*') {
			it++;
			res = min(res, formula());
		}
		else {
			assert(s[it++] == '+');
			res = max(res, formula());
		}
		assert(s[it++] == ')');
	}
	return res;
}

int main()
{
	while (cin >> s, s != ".") {
		n = s.size();
		int res = 0;
		for (vals = 0; vals < 27; vals++) {
			it = 0;
			if (formula() == 2) res++;
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dump(...)
#endif
#define endl "\n"
#define ll long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (int i = ((int)(x)); i > 0; i--)
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define vi vector<int>
#define vvi vector<vector<int>>
#define pi pair<int, int>
#define ALL(a) (a).begin(), (a).end()
#define BIT(n) (1LL << (n))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてからつかうこと
constexpr ll MOD = 1e9 + 7;
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec)
        is >> x;
    return is;
}

signed main() {
    cin >> N;
    vector<ll> t(N);
    REP(i, N)
    cin >> t[i];
    ans = 1;
    REP(i, N)
    ans = lcm(t[i], ans);
    cout << ans << endl;
}

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

int num[233333];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
    }
    sort(num + 1, num + n + 1);
    int sum = 0;
    for (int i = 1; i <= k; i++)
        sum += num[i];
    cout << sum;
    return 0;
}

Measured memory_bytes: 3736
/************************************
	Name: 荆国浩 
	E-mail: 1839714778@qq.com 
************************************/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stdio.h>
#include <fstream>
#include <stack>
#define rep(N) for(int i=0;i<N;i++)
#define pii pair<int,int>
#define For(I,N) for(int I=0;I<N;I++)
typedef unsigned long long ull;
using namespace std;

ull f(ull a,ull b)
{
	ull ta=a,tb=b,tc;
	if(ta<tb) swap(ta,tb);
	do
	{
//		cout<<tc<<ta<<tb<<endl;
		tc=ta%tb;
		ta=tb;
		tb=tc;	
	}while(tc);
//	cout<<tb<<' '<<a<<' '<<b<<endl;
	return a/ta*b;
}

int main()
{
//	freopen("input.txt","r",stdin);
	ull n;
	cin>>n;
	ull a[n],s=1LL;
	rep(n)
	{
		cin>>a[i];
		s=f(s,a[i]);
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 256
A, B = map(int, input().split())
S = list(str(input()))
flg = 1
digit = ['1','2','3','4','5','6','7','8','9','0']
if len(S) != A+B+1:
  flg = 0
elif S[A] != '-':
  flg = 0
else:
  for i in range(0, A):
    if S[i] not in digit:
      flg = 0
      break
  for i in range(A+1,A+B+1):
    if S[i] not in digit:
      flg = 0
      break
if flg:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
fun main(args: Array<String>){
    var (n, m) = readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val ab = Array(n){ readLine()!!.split(" ").map { it.toLong() }.let { Pair(it[0], it[1]) }}
    ab.sortBy { it.first }
    var money = 0L
    for(i in 0 until n){
        if(m >= ab[i].second){
            money += ab[i].first*ab[i].second
            m -= ab[i].second.toInt()
        }else{
            money += ab[i].first*m
            break
        }
    }
    println(money)
}

Measured memory_bytes: 82880
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int mod=1000000007 ;

void solve(){
	
	int n ;
	cin>>n ;

	vector<int> v(n) ;

	for(int i=0;i<n;i++){
		cin>>v[i] ;
	}

	for(int i=0;i<n;i++){
		if(v[i]%2==0){
			if(v[i]%3!=0 && v[i]%5!=0)
			{
				cout<<"DENIED" ;
				return ;
			}
		}
	}

	cout<<"APPROVED" ;

}



int main(){
	
	int y ;

	y=1 ;
	//cin>>y ;

	while(y--)
	{	
		solve() ;
	}

}

Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n;
int ans;
int ma;

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		ans += a;
		ma = max(ma, a);
	}
	cout << ans - ma + ma / 2 << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder {
    class Program {
        static void Main() {
            long[] input = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long n = input[0];
            long p = input[1];
            if(n == 1) { Console.WriteLine(p); return; }
            long pow = 0, pro = 1;
            for(long prime = 2; pow < p; prime++) {
                pow = Pow(prime, n);
                if(pow == -1) break;
                while(p % pow == 0) {
                    p /= pow;
                    pro *= prime;
                }
            }
            Console.WriteLine(pro);
        }
        static long Pow(long a, long n) {
            if(n == 0) return 1;
            if(n == 1) return a;
            long b = Pow(a, n / 2);
            if(b == -1 || b > 1000000) return -1;
            return b * b * Pow(a, n % 2);
        }
    }
}

Measured memory_bytes: 13396
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, A);
    IN(ll, B);
    IN(ll, C);
    IN(ll, D);
    YES((C + B - 1) / B <= (A + D - 1) / D);
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define LINF 1e18
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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; }


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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin>>N>>M;
    vector<ll> A(N);
    vector<LP> CB(M);
    ll ans=0;
    REP(i,N){
        cin>>A[i];
        ans+=A[i];
    }
    VSORT(A);
    REP(i,M){
        cin>>CB[i].second>>CB[i].first;
    }
    VRSORT(CB);
    int j=0;
    REP(i,N){
        if(A[i]>CB[j].first) break;
        else{
            ans+=CB[j].first-A[i];
            CB[j].second--;
            if(CB[j].second<=0) j++;
        }
    }
    cout<<ans<<endl;
}


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


int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  int sum_vote = 0;
  rep(i, N) {
    cin >> A[i];
    sum_vote += A[i];
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  
  bool ans = true;
  rep(i, M) {
    if (A[i] * 4 * M < sum_vote) {
      ans =false;
      break;
    }
  }

  if (ans) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
/* بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ */
//codeforces
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define mp make_pair
#define pb push_back
#define sz(v) ((int)v.size())
#define all(v) v.begin(), v.end()
void parseArray(ll* A,ll n){ for ( ll K = 0; K < n; K++){ cin >> A[K]; } }
ll modInverse(ll a, ll b){ return 1<a ? b - modInverse(b%a, a)*b/a : 1; }
ll gcd(ll a, ll b){ return b?gcd(b, a % b):a; }
ll lcm(ll a, ll b){ return (a*b)/gcd(a, b); }
ld dist(ld x, ld y, ld a, ld b){ return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
void debug(ll* a, ll n) { for ( ll k = 0; k < n; k++ ){ cerr << a[k] << " ";} cout << "\n"; }
#define PI 3.14159265358979323846
#define FF first
#define SS second

ll n;
ll a[80];

int main(){
	FASTIO;
	cin >> n; parseArray(a, n);
	ll k = 1;
	ll money = 1000;
	while (k < n) {
		while (k < n && a[k] < a[k - 1]) k++;
		ll buy = money / a[k - 1];
		money -= buy * a[k - 1];
		while (k < n && a[k] >= a[k - 1]) k++;
		ll sell = buy * a[k - 1];
		money += sell;
	}
	cout << money << endl;
	return 0;
}

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

using namespace std;

int main() {
  int w, a, b;
  cin >> w >> a >> b;
  if (abs(a - b) <= w) {
    cout << 0 << '\n';
  } else {
    cout << abs(a - b) - w << '\n';
  }
  return 0;
}

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

typedef long long ll; 
#define sz(a) ((int)(a.size()))

const int mod=1e9+7; 
int mul(int a, int b){
  return (ll)a*b%mod; 
}
void add_self(int &a, int b){
  a+=b; 
  if(a>= mod) a-=mod; 
}
void mul_self(int &a, int b){
  a=(ll)a*b%mod; 
}
void sub_self(int &a, int b){
  a-=b; 
  if(a<0) a+=mod;
}
int exp(int a, int b){
  int ret=1; 
  while(b){
    if(b%2){
      mul_self(ret,a); 
    }
    mul_self(a,a); 
    b/=2; 
  }
  return ret; 
}
//--------------------------------------------------

const int nax=2e5+5; 
vector<int> adj[nax]; 
int cnt[nax];

void dfs(int  u, int p, int acc){
  cnt[u]+=acc; 
  for(int v:adj[u]){
    if(v!=p){
      dfs(v,u,cnt[u]); 
    }
  }
}

void solve(){ 
  int n,q; cin>>n>>q; 
  for(int i=1;i<n;i++){
    int a,b; cin>>a>>b; 
    adj[a].push_back(b); 
    adj[b].push_back(a);  
  }
  for(int i=0;i<q;i++){
    int p,x; cin>>p>>x; 
    cnt[p]+=x; 
  }
  dfs(1,0,0); 
  for(int i=1;i<=n;i++){
    cout<<cnt[i]<<" " ; 
  }
  cout<<endl; 
}

int main(){
  clock_t beg=clock(); 
  solve(); 
  clock_t end=clock(); 
  fprintf(stderr,"%.2lf sec\n",(double)(end-beg)/CLOCKS_PER_SEC); 
}

Measured memory_bytes: 23424
#include<iostream>
using namespace std;
	int a[7][7],b[7][7];
int main(){
	for(int i=1;i<=3;i++)
	{
		for(int k=1;k<=3;k++)
		{
			cin>>a[i][k];
			b[i][k]=1;
		}
	}
	int n,t,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		for(int k=1;k<=3;k++)
		{
			for(int j=1;j<=3;j++)
			{
				if(t==a[k][j])
				{
					if(b[k][j]==1)
					{
						b[k][j]=0;
					}
				}
			}
		}
	}
	for(int i=1;i<=3;i++)
	{
		if(b[i][1]==0)
		{
			if(b[i][2]==b[i][1])
			{
				if(b[i][1]==b[i][3])
				ans++;
			}
		}
	}
	for(int i=1;i<=3;i++)
	{
		if(b[1][i]==0)
		{
			if(b[2][i]==b[1][i])
			{
				if(b[1][i]==b[3][i])
				ans++;
			}
		}
	}

	if(b[1][1]==0)
	{
		if(b[2][2]==b[1][1])
		{
			if(b[3][3]==b[1][1])
			ans++;
		}
	}
	if(b[1][3]==0)
	{
		if(b[2][2]==b[1][3])
		{
			if(b[3][1]==b[1][3])
			ans++;
		}
	}
	if(ans>=1)
	cout<<"Yes";
	else
	cout<<"No";
} 

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

void Print( const std::vector<std::vector<int>>& m ){
    int n = m.size();
    for( int j = n; j > 0; --j ){
        for( int i = 1; i < j; ++i ){
            std::cout << m[i][j] << "\t";
        }
        std::cout << "\n";
    }
}

void MatrixChainOrder( const std::vector<int>& p, std::vector<std::vector<int>>& m ){
    int n = p.size() - 1;
    for( int i = 1; i <= n; ++i ){
        m[i][i] = 0;
    }

    constexpr int INF = 1 << 25;
    int j;
    int q;
    for( int l = 2; l <= n; ++l ){
        for( int i = 1; i <= n-l+1; ++i ){
            j = i + l - 1;  
            m[i][j] = INF;
            for( int k = i; k <= j-1; ++k ){
                q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                m[i][j] = ( m[i][j] < q )? m[i][j] : q;
            }
        }
    }
}

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

    std::vector<int> p( n+1 );
    std::vector<std::vector<int>> m( n+1 );
    for( auto& elem : m ){
        elem = std::vector<int>( n+1 );
    }

    int dump;
    for( int i = 0; i < n; ++i ){
        std::cin >> p[i] >> dump;
    }
    p[n] = dump;

    MatrixChainOrder( p, m );

    std::cout << m[1][n] << std::endl;

    //Print( m );

}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> totori(N);
  for (int i=0;i<N;i++){
  cin>>totori.at(i);
 }
sort(totori.begin(), totori.end()); 
    reverse(totori.begin(), totori.end());
  
  cout <<totori.at(0) - totori.at(N-1)<<endl;
}


Measured memory_bytes: 256
// best coder in the world do not mess with me!!
#include <bits/stdc++.h>
#include <string>
#include <cmath>
#include <sstream>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
typedef long long int ll;
using namespace std;
ll mod=1000000007;
void generate(int per[],int n)
{
	
	for(int i=n-1;i>0;i--)
	{
		int k=rand()%i;
		swap(per[k],per[i]);
	}
}
int main()
{
    
    	int n;
    	cin>>n;
    	vector<int> a(n);
    	for(int i =0;i<n;i++)
    		cin>>a[i];
    	int count1 = 1;
    	int result = a[0];
    	for(int i =1;i<n;i++)
    	{
    		if(a[i]<result)
    		{
    			count1++;
    			result=a[i];
    		}
    	}
    	cout<<count1<<'\n';
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); \
                      cerr << "\n\n" << "Time elapsed: " << \
                      (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
                      return 0
#define ll long long int
#define ull unsigned long long int
#define db long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound 
#define pii pair<int , int>
#define pdd pair<db , db>
#define pll pair<ll , ll>
#define vpl vector<pll >
#define vll vector<ll >
#define mod 1000000007
#define mod1 998244353 
#define inf 1000000000000000007
#define eps 0.000001
#define stp fixed<<setprecision(20)
#define endl '\n'



int main()
{
    fastio;
    #ifdef APNA_IO
        start_routine();
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);    
    #endif
    
    ll r;cin>>r;
    cout<<3*r*r;


    #ifdef APNA_IO
        end_routine();
    #endif
}


Measured memory_bytes: 256
n, m, l = gets.chomp.split.map(&:to_i)

a = []
n.times { a.push(gets.chomp.split.map(&:to_i)) }

b = []
m.times { b.push(gets.chomp.split.map(&:to_i)) }

(0..(n-1)).each do |i|
  c = []
  (0..(l-1)).each do |j|
    x = 0
    (0..(m-1)).each do |k|
      x += a[i][k] * b[k][j]
    end
    c.push x
  end
  puts c.join(" ")
end



Measured memory_bytes: 7248
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

const int maxn = 150;
int n , freq[maxn] , frq[maxn];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	cin >> n;
	string z;
	cin >> z;
	for(int i=0;i<z.size();i++) freq[z[i]]++;
	for(int i=1;i<n;i++)
	{
		for(int j=97;j<=122;j++) frq[j] = 0;
		cin >> z;
		for(int j=0;j<z.size();j++)
		{
			frq[z[j]]++;
		}
		for(int j=97;j<=122;j++)
		{
			freq[j] = min(freq[j] , frq[j]);
		}
	}
	for(int i=97;i<=122;i++) while(freq[i]){ cout << (char)i; freq[i]--; }
}

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	
	int n; cin >> n;
	vector<int> a(3 * n);
	for(int i = 0; i < 3 * n; i++) cin >> a[i];
	sort(a.begin(), a.end(), greater<int>());
	long long sum = 0;
	for(int i = 1; i < 2 * n; i += 2) sum += a[i];
	cout << sum << endl;
	return 0;	
}
  

Measured memory_bytes: 1408
n, m = map(int, input().split())
h = [int(_) for _ in input().split()]
a = [0] * m
b = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    a[i], b[i] = aa, bb

ans = [1] * n
for i in range(m):
    if h[a[i]-1] == h[b[i]-1]:
        ans[a[i]-1], ans[b[i]-1] = 0, 0
    elif h[a[i]-1] > h[b[i]-1]:
        ans[b[i]-1] = 0
    else:
        ans[a[i]-1] = 0

print(sum(ans))

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

int main() {
  int a, b, c;

  cin >> a >> b >> c;

  if (a >= b && a >= c)
    cout << a * 10 + b + c;
  else if (b >= a && b >= c)
    cout << b * 10 + a + c;
  else
    cout << c * 10 + a + b;

  return 0;
}

Measured memory_bytes: 256
#include"iostream"
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<list>
#include<map>
#include<string>
#include<algorithm> 
#include <queue> 
#include <sstream>
#include <fstream>
#include<cmath>
#define INF 1000000000
#define LL long long
using namespace std;

vector<LL> v;

long long N, M, ans, A[100000],use[10],B;
string s;



int main() {
	cin >> N;
	cout << "Christmas";
	for (int i = 0; i < 25 - N; i++) {
		cout << " ";
		cout << "Eve";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <time.h>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <array>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ost;

const ll maxN = 1e7;
const ll INF = 1e17;
const ll MOD = 1e9 + 7;

ll xs[] = {-1, 1, 0, 0, -1, 1, 1, -1};
ll ys[] = {0, 0, -1, 1, -1, 1, -1, 1};

ll segtree[maxN << 2];
ll lazy[maxN << 2];
ll A[maxN];

inline ll left(ll x){
	return x << 1;
}

inline ll right(ll x){
	return (x<<1) + 1;
}

void build(ll node, ll start, ll end){
	if(start == end)
		segtree[node] = A[start];
	else{
		ll mid = (start + end)/2;
		build(left(node), start, mid);
		build(right(node), mid+1, end);
		segtree[node] = segtree[left(node)] + segtree[right(node)];
	}
}

void update(ll node, ll start, ll end, ll l, ll r, ll val){
	if(lazy[node] != 0){
		segtree[node] += (end-start+1)*lazy[node];
		if(start != end){
			lazy[left(node)] += lazy[node];
			lazy[right(node)] += lazy[node];
		}
		lazy[node] = 0;
	}
	if(start > end or l > start or r < end)
		return ;
	else if(start >= l and r >= end){
		segtree[node] += val;
		if(start != end){
			lazy[left(node)] += val;
			lazy[right(node)] += val;
		}
	}
	else{
		ll mid=(start + end)/2;
		update(left(node), start, mid, l, r, val);
		update(right(node), mid+1, end, l, r, val);
		segtree[node] = segtree[left(node)] + segtree[right(node)];
	}
}

ll sums(ll node, ll start, ll end, ll l, ll r){
	if(lazy[node] != 0){
		segtree[node] += (end-start+1)*lazy[node];
		if(start != end){
			lazy[left(node)] += lazy[node];
			lazy[right(node)] += lazy[node];
		}
		lazy[node] = 0;
	}
	if(l > end or r < start or start > end)
		return 0;
	if(l <= start and r >= end)
		return segtree[node];
	ll mid = (start+end)/2;
	return sums(left(node), start, mid, l , r) + sums(right(node), mid + 1, end, l , r);
}

int main(){
	cin.sync_with_stdio(false);
	cin.tie(0);
	ll a, b;
	string s;
	cin >> a >> b >> s;
	if(s[a] != '-')
		cout << "No";
	else{
		bool ns =1;
		for(ll i=0; s[i]; i++){
			if(i != a and s[i] >= '0' and s[i] <= '9')
				continue;
			else if(i != a)
				ns = false;
		}
		if(ns)
			cout << "Yes";
		else
			cout << "No";
	}
	return 0;
}

Measured memory_bytes: 3644
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main() {
  int n, sum, count;

  while(cin >> n) {
    count = 0;
    FOR(a, 0, 10) {
      FOR(b, 0, 10) {
	FOR(c, 0, 10) {
	  FOR(d, 0, 10) {
	    sum = a+b+c+d;
	    if(sum == n)count++;
	  }
	}
      }
    }
    cout << count << endl;
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,j,n) for(ll i=(ll)(j);i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(ll)(j);i<=(ll)(n);i++)
#define per(i,j,n) for(ll i=(ll)(j);(ll)(n)<=i;i--)
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key)))
#define pb emplace_back
#define mp std::make_pair
//
#define endl "\n"
//using std::endl;
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi=vector<ll>;
using vii=vector<vi>;
using pii=std::pair<ll,ll>;
//
constexpr ll MOD=1e9+7;
//constexpr ll MOD=998244353;
//constexpr ll MOD=10000000;
//constexpr ll MOD=1e5;
constexpr ll MAX=1e7;
constexpr ll INF=(1ll<<62);
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
const ll N=26;
ll solve(ll D,vii &A,vi &C,vi &S){
    vi last(N,-1);
    ll a=0;
    rep(i,0,D){
        ll memo; memo=S[i];
        last[memo]=i;
        a+=A[i][memo];
        rep(j,0,N) a-=(i-last[j])*C[j];
    }
    return a;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    srand((unsigned)time(NULL));
    ll D; cin>>D;
    vi C(N);
    rep(i,0,N) cin>>C[i];
    vii A(D,vi(N));
    rep(i,0,D){
        rep(j,0,N) cin>>A[i][j];
    }
    vi last(N,-1);
    vi ans(D);
    rep(i,0,D){
        ll max=0,memo=0;
        rep(j,0,N){
            if(max<A[i][j]+(i-last[j])*C[j]){
                max=A[i][j]+(i-last[j])*C[j];
                memo=j;
            }
        }
        last[memo]=i;
        ans[i]=memo;
    }
    ll max=solve(D,A,C,ans);
    rep(_,0,46){
        if(_%3==0){
            rep(i,0,D){
                rep(j,0,N){
                    vi S=ans;
                    S[i]=j;
                    ll X=solve(D,A,C,S);
                    if(max<X){
                        max=X;
                        ans[i]=j;
                    }
                }
            }
        }
        else{
            per(i,D-1,0){
                rep(j,0,N){
                    vi S=ans;
                    S[i]=j;
                    ll X=solve(D,A,C,S);
                    if(max<X){
                        max=X;
                        ans[i]=j;
                    }
                }
            }
        }
    }
    rep(i,0,D) cout<<ans[i]+1<<endl;
}


Measured memory_bytes: 3724
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include<string>
#include<cstring>
#include<complex>
#include<cmath>
using namespace std;
#define rep(i, n)   for(int i = 0; i < (int)(n); i++)
#define rrp(i, n)   for(int i = ((int)(n)); i >=0; i--)
#define mpp(i,j,k)  make_pair((int)(i),make_pair((int)(j),(int)(k)))
typedef pair<int,pair<int,int > > ppp;
typedef pair<int,int> pp;
typedef vector<int> vi;
typedef vector<vi>  vvi;
int d[3][30];
int p[30][30],c[500][500];
int n,m;
int main(){
 cin>>n>>m;
 rep(i,3)rep(j,30)d[i][j]=0;
 rep(i,m)rep(j,m)cin>>p[i][j];
 rep(i,n)rep(j,n)cin>>c[i][j],d[(i+j+2)%3][c[i][j]-1]+=1;
long long mm=1000000000;

 rep(x,m)rep(y,m)rep(z,m){if(x!=y && y!=z && x!=z){long long xx=0;rep(j,m){xx+=p[j][x]*d[0][j];xx+=p[j][y]*d[1][j];xx+=p[j][z]*d[2][j];} mm=min(mm,xx);}}
cout<<mm<<endl;
  return 0;}




Measured memory_bytes: 1280
(defun root (l)
  (if (null (cdr l)) l (setf (cdr l)(root (cdr l)))))

(loop with ht = (make-hash-table) and N = (read) repeat (read)
      initially (loop for i from 1 to N 
                      do (setf (gethash i ht) (list i)))
      
      do (setf l1 (root (gethash (read) ht))
               l2 (root (gethash (read) ht)))
      (read)
      if (not (eq l1 l2)) do (rplacd (root l1) (root l2))
      
      ;do (loop for v being each hash-value of ht
      ;         do (princ v) (terpri))
      ;(terpri)
      
      finally (princ (loop for v being each hash-value of ht
                           count (null (cdr v)))))

Measured memory_bytes: 80940
import itertools
N=int(input())
nlist=[i for i  in range(1,N+1)]
newlist=[str(i) for i in nlist]
alllist=[]
p=int("".join(input().split()))
q=int("".join(input().split()))

for i in itertools.permutations(newlist):
    alllist.append(int("".join(i)))
a=alllist.index(p)+1
b=alllist.index(q)+1
c=abs(a-b)

print(c)

Measured memory_bytes: 4760
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N=0;
  cin>>N;
  vector<int>V(N);
  for(int i=0;i<N;i++){
    cin>>V.at(i);
  }
  vector<int>C(N);
  for(int i=0;i<N;i++){
    cin>>C.at(i);
  }
  int ans=0;
  for(int i=0;i<N;i++){
    if(V.at(i)>C.at(i)){
      ans+=V.at(i)-C.at(i);
    }
  }
  cout<<ans<<endl;
}


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

typedef long long ll;
#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)

#define P pair<int, int >


const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;



//---functions---//
int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int s2i(string num){stringstream ss; ss << num << flush; int n; ss >> n; return n;}
string i2s(int n){stringstream ss; ss << n << flush; return ss.str();}

bool firstCompare(const P& firstElof, const P& secondElof){
    return firstElof.first < secondElof.first;
}
bool secondCompare(const P& firstElof, const P& secondElof){
    return firstElof.second < secondElof.second;
}
//---------------//

int N;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    int h[N];
    REP(i, 0, N) cin >> h[i];

    bool flag = true;
    int tmp_min = 0;
    int subt = 0;
    REP(i, 0, N-1){
        if(h[i] == h[i+1] + 1){
            if(tmp_min <= h[i] - 1){
                h[i] -= 1;
            }else{
                flag = false;
                break;
            }
        }else if(h[i] > h[i+1] + 1){
            flag = false;
            break;
        }else if((h[i] < h[i+1] + 1) && subt > 0){
            h[i] -= 1;
        }
        subt = h[i+1] - h[i]; 
        tmp_min = h[i];
    }
    if(flag) cout << "Yes" << '\n';
    else cout << "No" << '\n';

}


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

void cc_env(){
	#ifndef ONLINE_JUDGE
		freopen("input", "r", stdin);
		freopen("output", "w", stdout);
		// 
	#endif
}



void self_min(int &a, int b){
	a = min(a, b);
}

int main(){
	// cc_env();
	int n, k;
	cin>>n>>k;
	vector<int> height(n);
	for(int i=0;i<n;i++)
		cin>>height[i];

	vector<int> dp(n, INT_MAX);
	dp[0] = 0;
	for(int i=0;i<n;i++){
		for(int j = i+1; j <= i+k; j++){
			if(j < n)
				self_min(dp[j], dp[i]+abs(height[j] - height[i]));
		}
	}

	cout<<dp[n-1]<<endl;
}


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

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

    bool f[4] = {};
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'P') f[0] = true;
        if (c == 'W') f[1] = true;
        if (c == 'G') f[2] = true;
        if (c == 'Y') f[3] = true;
    }

    int t = f[0] + f[1] + f[2] + f[3];
    cout << (t == 3 ? "Three" : "Four") << endl;

    return 0;
}


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

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }
    
    long long height = 0;
    for (int i = 0; i < N-1; i++) {
        if (A.at(i) > A.at(i+1)) {
            height += A.at(i) - A.at(i+1);
            A.at(i+1) = A.at(i);
        }
    }
    cout << height << endl;
}

Measured memory_bytes: 4048
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

ll N1 = 202020;
ll bit1[202020];
ll N2 = 202020;
ll bit2[202020];
void add1(ll a, ll w) {
	 a++;
	 for (ll x = a; x <= N1; x += x & -x) bit1[x] += w;
}
ll sum1(ll a) {
	 a++;
	 ll ret = 0;
	 for (ll x = a; x > 0; x -= x & -x) ret += bit1[x];
	 return ret;
}
void add2(ll a, ll w) {
	a++;
	for (ll x = a; x <= N2; x += x & -x) bit2[x] += w;
}
ll sum2(ll a) {
	a++;
	ll ret = 0;
	for (ll x = a; x > 0; x -= x & -x) ret += bit2[x];
	return ret;
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	REP(i,202020) bit1[i]=0;
	REP(i,202020) bit2[i]=0;
	string str;
	cin>>str;
	vector<ll> c(26,0);
	vector<set<ll>> s(26);
	REP(i,(ll)str.size()) {
		c[str[i]-'a']++;
		s[str[i]-'a'].insert(i);
	}
	ll cnt=0;
	REP(i,26) if(c[i]%2) cnt++;
	if((ll)str.size()%2) {
		if(cnt!=1) {
			cout<<-1<<endl;
			return 0;
		}
	} else {
		if(cnt!=0) {
			cout<<-1<<endl;
			return 0;
		}
	}
	ll ans=0;
	ll tmp=0;
	while(tmp<(ll)str.size()/2) {
		ll n_buf=INF;
		ll c_buf=-1;
		REP(i,26) {
			if((ll)s[i].size()<=1) continue;
			auto ite=s[i].begin();
			ll l=*ite;
			ite=s[i].end();
			ite--;
			ll r=*ite;
			ll diff1=0;
			ll diff2=0;
			diff1+=sum1((ll)str.size())-sum1(l);
			if(l>0)diff1-=sum2(l-1);
			diff2+=sum1((ll)str.size())-sum1(r);
			if(r>0)diff2-=sum2(r-1);
			l+=diff1;
			r+=diff2;
			ll cost=(l-tmp)+((ll)str.size()-1-tmp-r);
			if(cost<n_buf) {
				n_buf=cost;
				c_buf=i;
			}
		}
		ans+=n_buf;
		auto ite=s[c_buf].begin();
		ll l=*ite;
		add1(l,1);
		s[c_buf].erase(ite);
		ite=s[c_buf].end();
		ite--;
		ll r=*ite;
		add2(r,1);
		s[c_buf].erase(ite);
		tmp++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 12948
#include <bits/stdc++.h>
using namespace std;
vector <bool>  primes(1000000,1) ;
void Eratosthenes(int n){
    for(int i = 2; i <= sqrt(n); i++){
		if(primes[i]){
			for(int j = 0; i * (j + 2) <= n; j++){
				primes[i *(j + 2)] = 0;
			}
		}
	}
	/*for(int i = 0; i <= n; i++){
		if(primes[i]){
			cout << i << endl;
		}
	}*/
	primes[0] = 0; primes[1] = 0;
}
int main(void){
    int n = 100010;
    Eratosthenes(n);
    int q; cin>>q;
    vector <int> c(100010);
    
    for(int i=0;i<n;i++){
        if(primes[i]&&primes[(i+1)/2]) c[i]++;
        //cout<<c[i]<<endl;
    }
    int rui[100011];
    rui[0] = 0;
    for(int i=0;i<n;i++){
        rui[i+1] = rui[i] + c[i];
    }
    for(int i=0;i<q;i++){
        int a,b; cin>>a>>b;
        cout<<rui[b+1] - rui[a-1]<<endl;
    }
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s[N];
int main()
{
    int n,a,b,c,d,m,i,j,k,x,y,z;
    scanf("%d%d%d%d%d%s",&n,&a,&b,&c,&d,s+1);
    if((b<c&&c<d)||(c<b&&b<d))
    {
        int f=1;
        for(i=b+1;i<d-1;i++)if(s[i]=='#'&&s[i+1]=='#'){f=0;break;}
        for(i=a+1;i<c-1;i++)if(s[i]=='#'&&s[i+1]=='#'){f=0;break;}
        printf("%s\n",f?"Yes":"No");
    }
    else if(b<d&&d<c)
    {
        int f=1,p=1,q=1;
        for(i=b;i<=d-1;i++)
        {
            if(s[i]=='.'&&s[i+1]=='.'&&s[i+2]=='.'){b=i+1;break;}
            else if(s[i+1]=='#'&&s[i+2]=='#'){break;}
        }
        s[b]='#';
        for(i=a+1;i<c-1;i++)if(s[i]=='#'&&s[i+1]=='#'){f=0;break;}
        for(i=b+1;i<d-1;i++)if(s[i]=='#'&&s[i+1]=='#'){f=0;break;}
        printf("%s\n",f?"Yes":"No");
    }
}


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

int a, b;

int main (){
	cin >> a >> b;
	if (b == a){
		cout << "Draw";
	}
	else if (a == 1){
		cout << "Alice";
	}
	else if (b == 1){
		cout << "Bob";
	}
	else if (a > b){
		cout << "Alice";
	}
	else if (a < b){
		cout << "Bob";
	}	

	return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
	int n;
	cin >> n;
	ll a[n];
	ll ans = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		if(i){
			ans += min(a[i-1], a[i]);
			a[i] = max((ll)0, a[i]-a[i-1]);
		}
		ans += a[i]/2;
		a[i]%=2;

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

Measured memory_bytes: 1024
N, M = [int(v) for v in input().split()]
lights = []
for _ in range(M):
    lights.append(set([int(v) - 1 for v in input().split()[1:]]))

P = [int(v) for v in input().split()]

def patterns(n):
    limit = pow(2, n)
    for val in range(limit):
        flags = '{0:b}'.format(val).zfill(n)
        yield [int(v) for v in flags]

def judge(pattern, rule, check):
    summary = sum([pattern[i] for i in rule]) % 2
    return summary == check

cnt = 0
for pattern in list(patterns(N)):
  ok = all([judge(pattern, lights[i], P[i]) for i in range(M)])
  if ok:
    cnt += 1

print(cnt)

Measured memory_bytes: 3188
n=int(input())
za=[[0 for _ in range(2*n)] for _ in range(2*n)]

al=[]
for _ in range(n):
  a,b=(map(int,input().split()))
  za[a][b]+=1
  
bl=[]

for _ in range(n):
  b=list(map(int,input().split()))
  bl.append(b)
  
bl.sort()

ans=0

for v in bl:
  x,y=v
  tempy=-1
  for z in range(0,x):
    for u in range(0,y):
      if za[z][u]>=1:
        if u>tempy:
          tempx=z
          tempy=u
  if tempy>=0:
    ans+=1
    za[tempx][tempy]-=1
    
print(ans)
          

Measured memory_bytes: 9404
#include <vector>
#include <iostream>
#include <algorithm>
#pragma warning(disable : 4996)
#define mod 1000000007
using namespace std;
int N, Q, s, t, z[100001], fact[100001]; vector<int> seg[262144];
int query(int a, int b, int x1, int x2, int k, int l, int r) {
	if (r <= a || b <= l) return 0;
	if (a <= l && r <= b) return lower_bound(seg[k].begin(), seg[k].end(), x2) - lower_bound(seg[k].begin(), seg[k].end(), x1);
	int lc = query(a, b, x1, x2, 2 * k, l, (l + r) / 2);
	int rc = query(a, b, x1, x2, 2 * k + 1, (l + r) / 2, r);
	return lc + rc;
}
int main() {
	fact[0] = 1;
	for (int i = 1; i < 100000; i++) fact[i] = 1LL * fact[i - 1] * i % mod;
	while (cin >> N >> Q) {
		for (int i = 0; i < N; i++) z[i] = i;
		for (int i = 0; i < Q; i++) {
			scanf("%d%d", &s, &t);
			swap(z[s - 1], z[t - 1]);
		}
		for (int i = 0; i < 262144; i++) seg[i].clear();
		for (int i = 0; i < N; i++) {
			int u = i + 131072;
			while (u > 0) {
				seg[u].push_back(z[i]);
				u >>= 1;
			}
		}
		for (int i = 0; i < 131072; i++) sort(seg[i].begin(), seg[i].end());
		int ret = 0;
		for (int i = N - 1; i >= 0; i--) ret = (ret + 1LL * query(i + 1, N, 0, z[i], 1, 0, 131072) * fact[N - i - 1]) % mod;
		printf("%d\n", ret);
	}
}

Measured memory_bytes: 21548
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		person p[] = new person[24];
		for(int i=0; i<24; i++){
			p[i] = new person(s.nextInt() , s.nextDouble());
		}
		Arrays.sort(p,0,7);
		System.out.println(p[0] + "\n" + p[1]);
		p[0].time = 100;
		p[1].time = 100;
		
		Arrays.sort(p,8,15);
		System.out.println(p[8] + "\n" + p[9]);
		p[8].time = 100;
		p[9].time = 100;
		
		Arrays.sort(p,16,23);
		System.out.println(p[16] + "\n" + p[17]);
		p[16].time = 100;
		p[17].time = 100;
		
		Arrays.sort(p);
		System.out.println(p[0] + "\n" + p[1]);

	}

}
class person implements Comparable<person>{
	int num;
	double time;
	person(int num, double time){
		this.num = num;
		this.time = time;

	}
	@Override
	public String toString(){
		return  num + " " + time ;

	}
	@Override
	public int compareTo(person o) {
	return new Double(time).compareTo(o.time);
	}
}

Measured memory_bytes: 20068