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

#define ll long long
#define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cps CLOCKS_PER_SEC
#define mod (ll)1000000007
#define f first
#define s second
#define debug1(x) cerr<<x<<"\n"
#define debug2(x,y) cerr<<x<<" "<<y<<"\n"
#define debug3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<"\n"
#define nl cerr<<"\n";
#define pq priority_queue
#define inf 0x3f3f3f3f
#define test cerr<<"abcd\n";
#define pi pair<int,int>
#define pii pair<int,pi>
#define pb push_back
#define mxn 200005
int n;
ll a[405],p[405];
ll dp[405][405];


ll doit(int i,int j){
if(i>=j)return 0;
if(dp[i][j]!=-1)return dp[i][j];
dp[i][j]=LLONG_MAX;
for(int k=i; k<j; ++k)
    dp[i][j]=min(dp[i][j],doit(i,k)+doit(k+1,j)+p[j]-p[i-1]);
return dp[i][j];
}

int main(){
sp;
cin>>n;
    for(int i=1; i<=n; ++i){
        cin>>a[i];
        p[i]=a[i];
        p[i]+=p[i-1];
    }
    for(int i=0; i<=n+1; ++i)
        for(int j=0; j<=n+1; ++j)dp[i][j]=-1;
    cout<<doit(1,n);
return 0;}


Measured memory_bytes: 1536
fun min(a:Int, b:Int):Int{
    return if (a > b) b else a
}
fun main(args:Array<String>):Unit {
    val n = readLine()!!.toInt()
    val nums = readLine()!!.split(' ').map(String::toInt).sorted().toIntArray()
    val biggest = nums.last()
    var maxMin = 0
    for (a in nums){
        if (min(a, biggest - a) > maxMin){
            maxMin = a
        }
    }
    println("$biggest $maxMin")
}

Measured memory_bytes: 54188
//
//  main.cpp
//  CP-C++
//
//  Created by ALOK KUMAR THAKUR on 05/05/20.
//  Copyright © 2020 ALOK KUMAR THAKUR. All rights reserved.
//

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define tc() ll T;cin>>T;while(T--)
#define pb push_back
#define Max3(a,b,c) max(a,max(b,c))
#define Min3(a,b,c) min(a,min(b,c))

struct cmp {
    bool operator() (const ll& a, const ll& b){
        return a < b;
    }
};

const ll N = 1e5+1;

int main() {
    
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    /*-----------------Code Begins Here------------------*/
    
    ll n; cin>>n;
    ll a[n+1], b[n+1], c[n+1], dp[N][3] = {0};
    for(ll i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
    for(ll i=1;i<=n;i++){
        dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
        dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
        dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1]);
    }
    cout<<Max3(dp[n][0], dp[n][1], dp[n][2]);
    
    /*------------------Code Ends Here-------------------*/
    
    return 0;
}


Measured memory_bytes: 8272
H,W=map(int,input().split())
s=[input() for _  in range(H)]
G=[[0 for j in range (W)] for i in range(H)]

if s[0][0]==".":G[0][0]=0
else:G[0][0]=1

for i in range(1,H):
    if s[i][0]==".":
        if s[i-1][0]==".":G[i][0]=G[i-1][0]
        if s[i-1][0]=="#":G[i][0]=G[i-1][0]
    if s[i][0]=="#":
        if s[i-1][0]==".":G[i][0]=G[i-1][0]+1
        if s[i-1][0]=="#":G[i][0]=G[i-1][0]

for i in range(1,W):
    if s[0][i]==".":
        if s[0][i-1]==".":G[0][i]=G[0][i-1]
        if s[0][i-1]=="#":G[0][i]=G[0][i-1]
    if s[0][i]=="#":
        if s[0][i-1]==".":G[0][i]=G[0][i-1]+1
        if s[0][i-1]=="#":G[0][i]=G[0][i-1]

for i in range(1,H):
    for j in range(1,W):
        if s[i][j]==".":
            G[i][j]=min(G[i-1][j],G[i][j-1])
        if s[i][j]=="#":
            if s[i-1][j]=="#" and s[i][j-1]=="#":G[i][j]=min(G[i-1][j],G[i][j-1])
            if s[i-1][j]=="." and s[i][j-1]=="#":G[i][j]=min(G[i-1][j]+1,G[i][j-1])
            if s[i-1][j]=="#" and s[i][j-1]==".":G[i][j]=min(G[i-1][j],G[i][j-1]+1)
            if s[i-1][j]=="." and s[i][j-1]==".":G[i][j]=min(G[i-1][j]+1,G[i][j-1]+1)

print(G[H-1][W-1])

Measured memory_bytes: 42992
#include <stdio.h>

int main(void) {
	int N;
	int V[20];
	int C[20];
	int sum = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &V[i]);
	}

	for (int j = 0; j < N; j++) {
		scanf("%d", &C[j]);
	}
	for (int i = 0; i < N; i++) {
		if (V[i] - C[i] > 0) {
			sum += V[i] - C[i];
		}

	}

	printf("%d", sum);


	return 0;

}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int a[2],b;
	for (int i = 0; i < 2; ++i) {
		a[i] = 0;
		for (int j = 0; j < 4; ++j) {
			cin >> b;
			a[i] += b;
		}
	}
	cout << max(a[0], a[1]) << endl;
	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using P = pair<int, int>;

int main() {
  int N;
  vector<int> a;
  cin >> N;
  rep(i, N) {
    int temp;
    cin >> temp;
    a.push_back(temp);
  }
  rep(i, N) {
    for(int j = i-1; j >= 0; j--) {
      if(a[j+1] < a[j]) {
        swap(a[j+1], a[j]);
      }
    }
    rep(i, N) {
      cout << a[i];
      if(i != N-1) cout << " ";
      else cout << endl;
    }
  }
  return 0;
}


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

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

  int a, b;
  cin >> a >> b;
  int count = 1, ans = 0;

  while (count < b) {
    count += a - 1;
    ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
k, n = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
kyoris = []
for i in range(len(a)-1):
    kyoris.append(abs(a[i]-a[i+1]))
lastkyori = (k - a[-1]) + a[0]
kyoris.append(lastkyori)
print(k - max(kyoris))


Measured memory_bytes: 26444
#include <iostream>

using namespace std;

int main() {
    int n, k, cnt = 0;
    cin >> n >> k;
    int tmp = 1;

    while (tmp < k && cnt < n) {
        tmp *= 2;
        cnt++;
    } 

    while (cnt < n) {
        tmp += k;
        cnt++;
    }

    cout << tmp << endl;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;

int main(){
  int a,b;
  cin >>a>>b;
  cout<<(a*b)<<endl;
  
 

}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
string alp="abcdefghijklmnopqrstuvwxyz";

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

ll ref(ll x,ll y){
    if (x==0||y==0){
        return 0;
    }
    if (y%x==0){
        return (y/x*3-1)*x;
    }
    if (x>y){
        return x/y*2*y+ref(x%y,y);
    }
    return 2*y+y/x*x+ref(x-y%x,y%x);
}

int main(){
    ll N,X;
    cin >> N >> X;
    ll ans=X+ref(X,N-X);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;

int p[100010];

int gcd(int a, int b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}

int main() {
	int n, x;
	cin >> n >> x;
	int ans;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		if (i == 0)ans = abs(p[i] - x);
		else {
			ans = gcd(ans, abs(p[i] - x));
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector< vector< int > > points(n, vector< int > (3));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) cin >> points[i][j];
    }
    vector< vector< int > > dp(n, vector< int > (3, INT_MIN));
    dp[0][0] = points[0][0], dp[0][1] = points[0][1], dp[0][2] = points[0][2];

    for (int i = 1; i < n; i++) {
        dp[i][0] = max(dp[i][0], max(dp[i - 1][1], dp[i - 1][2]) + points[i][0]);
        dp[i][1] = max(dp[i][1], max(dp[i -1][0], dp[i - 1][2]) + points[i][1]);
        dp[i][2] = max(dp[i][2], max(dp[i - 1][0], dp[i - 1][1]) + points[i][2]);
    }
    cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << "\n";
}

Measured memory_bytes: 14088
package main

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

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	mp := map[int]int{}
	for i := 0; i < n; i++ {
		a := nextInt()
		mp[a]++
	}

	ans := 0
	for k, v := range mp {
		if v < k {
			ans += v
		} else if v > k {
			ans += v - k
		}
	}
	puts(ans)
}


Measured memory_bytes: 8628
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int count = 0;
		int a =0;
		int now =0;
		int beforeK=0;
		while (K>0) {
			count *=2;
			if (N>=K) {
				if (beforeK==0) {
					count +=N-K+1;
				} else {
					count +=beforeK-K;
				}
				beforeK=K;
			}
			if (K>1) {
				K=K/2+K%2;
			} else {
				K/=2;
			}
			a++;
		}
		a--;
		int total = (int) Math.pow(2, a);
		total *=N;
		BigDecimal result = new BigDecimal(count);

		result = result.divide(new BigDecimal(total), 12,RoundingMode.HALF_UP);
		System.out.println(result.toPlainString());
	}
}

Measured memory_bytes: 23380
from functools import lru_cache
t=int(input())
for i in range(t):
  n,a,b,c,d=map(int,input().split())
  @lru_cache(maxsize=None)
  def f(n):
    if n==0:
      return 0
    if n==1:
      return d
    else:
      x=n*d
      
      q,r=divmod(n,2)
      if r==0:
        x=min(x,f(q)+a)
      else:
        x=min(x,f(q)+a+d,f(q+1)+a+d)
      
      q,r=divmod(n,3)
      if r==0:
        x=min(x,f(q)+b)
      elif r==1:
        x=min(x,f(q)+b+d,f(q+1)+b+d*2)
      else:
        x=min(x,f(q)+b+d*2,f(q+1)+b+d)
      
      q,r=divmod(n,5)
      if r==0:
        x=min(x,f(q)+c)
      elif r==1:
        x=min(x,f(q)+c+d,f(q+1)+c+d*4)
      elif r==2:
        x=min(x,f(q)+c+d*2,f(q+1)+c+d*3)
      elif r==3:
        x=min(x,f(q)+c+d*3,f(q+1)+c+d*2)
      else:
        x=min(x,f(q)+c+d*4,f(q+1)+c+d)
      
      return x
  
  print(f(n))

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int h, w, k;
	cin >>h >>w >>k;
	vector<string> s(h);
	rep(i, h) cin >>s[i];
	vector<VI> ba(h, VI(w)), sk(h+1, VI(w+1, 0));
	rep(i,h) rep(j,w) ba[i][j] = s[i][j] -'0';
	rep(i,h) rep(j,w){
		sk[i+1][j+1] = sk[i][j+1] + sk[i+1][j] - sk[i][j] + ba[i][j];
	}
	int res = 1<<28;
	rep(i,1<<(h-1)){
		int tsu = 0;
		vector<int> cv(h); //sh;
		rep(j, h){ cv[j] = tsu; if((i>>j)& 1) tsu++; }
		if(tsu > res) continue;
		vector<int> cdy(tsu+1,0);
		rep(x, w){
			bool addsw=false;
			vector<int> gdy(tsu+1,0);
			rep(y, h){
				gdy[cv[y]] += ba[y][x];
				if(gdy[cv[y]] > k) goto lastloop;
				cdy[cv[y]] += ba[y][x];
				if(cdy[cv[y]] > k) addsw=true;
			}
			if(addsw){
				tsu++;
				fill(all(cdy), 0);
				rep(yy, h) cdy[cv[yy]] +=ba[yy][x];
			}
		}
		res = min(res, tsu);
		lastloop: ;
	}
	cout << res <<"\n";
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define ind(a) scanf("%d", &a)
#define inlld(a) scanf("%lld", &a)
#define ind2(a, b) scanf("%d%d", &a, &b)
#define inlld2(a, b) scanf("%lld%lld", &a, &b)
#define ind3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define inlld3(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

using namespace std;

const int N=1e5+5;
const int MOD=1e9+7;

typedef long long ll;
typedef long double ld;

ll n, dp[N], arr[N], k;

int main() 
{
    inlld2(n, k);
    for(ll a=1; a<=n; a++)
        inlld(arr[a]);
    dp[1]=0;
    dp[2]=abs(arr[2]-arr[1]);
    for(ll a=3; a<=n; a++)
    {
        dp[a]=1e18;
        for(ll b=1; b<=k && a-b>=1; b++)
            dp[a]=min(dp[a], dp[a-b]+abs(arr[a-b]-arr[a]));
    }
    printf("%lld\n", dp[n]);
    return 0;
}



Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
 
#define MAX 60
 
using namespace std;
 
int N,ans[MAX],remain[14];
bool found;
 
void rec(int sum,int cnt)
{
 
  if(found)return;
 
  if(cnt >= N){
    for(int i=N-1;i>=0;i--){
      if(i != N-1)cout << " ";
      cout << ans[i];
    }
    cout << endl;
 
    found = true;
 
    return;
  }
 
  for(int i=1;i<=13;i++){
    if( remain[i] <= 0 )continue;
    if( ( sum - i ) % i == 0 ){
 
      remain[i]--;
      ans[cnt] = i;
      rec(sum-i,cnt+1);
      if(found)return;
      remain[i]++;
 
    }
  }
}
 
int main(){
 
  while(cin >> N,N){
 
    for(int i=0;i<14;i++)remain[i] = 0;
 
    int c[N+1],sum = 0;
    for(int i=0;i<N;i++){
      cin >> c[i];
      sum += c[i];
      remain[c[i]]++;
    }
 
    sort(c,c+N);
 
    found = false;
    rec(sum,0);
 
    if(!found){
      cout << "No" << endl;
    }
       
  }
  return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std; 
int main(){
  int n;
  cin >> n;
  int i=1;
  while(1){
    int ans=0;
    ans=i*100+i*10+i;
    if(ans-n>=0){
      cout << ans;
      break;
    }
    i++;
  }
}
    
  


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define INF 1000000
using namespace std;
int main(){
    string s;
    while(cin >> s){
        if(s == "#") break;
        char table[10][10];
        int posy = 0,posx = 0;
        rep(i,s.size()){
            if(s[i] == 'b') {
                table[posy][posx] = 'b';
                posx++;
            }
            else if(s[i] == '/') {
                posy++;
                posx = 0;
            }
            else {
                int tmp = s[i]-'0';
                for(int j=0; j<tmp; j++) {
                    table[posy][posx] = '.';
                    posx++;
                }
            }
        }
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--; posy++;
        swap(table[a][b],table[c][d]);
        vector<char> vec;
        rep(i,posy){
            int cnt = 0;
            bool flag = false;
            rep(j,posx){
                if(table[i][j] == 'b') {
                    if(flag == true) {
                        vec.push_back(cnt+'0');
                        cnt = 0;
                    }
                    vec.push_back('b');
                    flag = false;
                }
                else {
                    cnt++;
                    flag = true;
                }
            }
            if(flag == true) {
                vec.push_back(cnt+'0');
                flag = false;
            }
            if(i != posy-1) vec.push_back('/');
        }
        rep(i,vec.size()) cout << vec[i];
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
using System;
using System.Collections.Generic;
using System.Linq;
using static Scanner;

class Program
{
    static void Main() => new Program().Solve();

    public void Solve()
    {
        int n = ReadInt();
        int[] a = ReadInt(n).ToArray();
        long money = 1000;
        long stock = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (a[i] < a[i + 1])
            {
                long x = money / a[i];
                money -= x * a[i];
                stock += x;
            }
            else if (a[i] > a[i + 1])
            {
                money += stock * a[i];
                stock = 0;
            }
        }
        Console.WriteLine(money + stock * a[^1]);
    }
}

static class Scanner
{
    static Queue<string> que = new Queue<string>();
    public static string Read() { if (!que.Any()) foreach (var s in Console.ReadLine().Split()) que.Enqueue(s); return que.Dequeue(); }
    public static int ReadInt() => int.Parse(Read());
    public static IEnumerable<string> Read(long n) { for (long i = 0; i < n; i++) yield return Read(); }
    public static IEnumerable<int> ReadInt(long n) => Read(n).Select(int.Parse);
}


Measured memory_bytes: 28184
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val h = sc.nextInt()
    val w = sc.nextInt()
    val k = sc.nextInt()
    val c = (0 until h).map { sc.next().toCharArray() }
    println(problem173c(h, w, k, c))
}

fun problem173c(h: Int, w: Int, k: Int, c: List<CharArray>): Int {
    var count = 0
    fun isK(list: Array<CharArray>) = list.sumBy { it.count { it == '#' } } == k

    fun allSearch(current: Int, ignoreY: MutableList<Boolean>, ignoreX: MutableList<Boolean>) {
        if (ignoreY.size + ignoreX.size == h + w) {
            val list = Array(h) { CharArray(w) { '.' } }
            for (i in 0 until h) {
                if (ignoreY[i]) continue
                for (j in 0 until w) {
                    if (ignoreX[j]) continue
                    list[i][j] = c[i][j]
                }
            }
            if (isK(list)) count++
            return
        }

        if (current <h) {
            val tmp1 = ignoreY.toMutableList()
            tmp1.add(true)
            allSearch(current + 1, tmp1, ignoreX)
            val tmp2 = ignoreY.toMutableList()
            tmp2.add(false)
            allSearch(current + 1, tmp2, ignoreX)
        } else {
            val tmp1 = ignoreX.toMutableList()
            tmp1.add(true)
            allSearch(current + 1, ignoreY, tmp1)
            val tmp2 = ignoreX.toMutableList()
            tmp2.add(false)
            allSearch(current + 1, ignoreY, tmp2)
        }
    }
    allSearch(0, mutableListOf(), mutableListOf())
    return count
}

Measured memory_bytes: 42448
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define fo(i,a,n) for (i = a; i <= n; i++)
#define F first
#define S second
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front    
#define PB pop_back
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;

void solve(){
    int n, m, x, ans = LLONG_MAX;
    cin>>n>>m>>x;
    int a[n+3][m+3], c[n+3];
    f(i,n){cin>>c[i];f(j,m)cin>>a[i][j];}
    f(i,1<<n){
        int cnt = 0, now[m+3] = {0}, f = 1;
        f(j,n)if((i>>j) & 1){
            cnt += c[j];
            f(k,m)now[k] += a[j][k];
        }
        f(j,m)if(now[j] < x)f = 0;
        if(f)ans = min(ans,cnt);
    }
    if(ans == LLONG_MAX)cout<<"-1";
    else cout<<ans;
}

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


Measured memory_bytes: 3608
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

fn order(n: i64, lims: &Vec<i64>) -> usize {
    let mut ret: usize = 0;
    if n >= 0 {
        for i in 0..17 {
            if n <= lims[i * 2] {
                ret = i * 2;
                break;
            }
        }
    } else {
        for i in 0..16 {
            if n >= lims[i * 2 + 1] {
                ret = i * 2 + 1;
                break;
            }
        }
    }
    ret
}

fn main() {
    let mut n: i64 = read();

    let mut bits: Vec<i64> = vec![];
    let mut lims: Vec<i64> = vec![];
    let mut r: i64 = 1;
    let mut tmp: i64 = 0;
    for i in 0..33 {
        if i % 2 == 0 {
            bits.push(r);
            tmp += 2 * r - 1;
        } else {
            bits.push(-r);
            tmp += -2 * r + 1;
        }
        lims.push(tmp);
        r *= 2;
    }

    if n == 0 {
        println!("0");
    } else {
        let mut ans: Vec<char> = vec![];
        let mut lastketa: usize = order(n, &lims) + 1;
        while n != 0 {
            let keta = order(n, &lims);
            n -= bits[keta];
            for _ in 0..(lastketa - keta - 1) {
                ans.push('0');
            }
            lastketa = keta;
            ans.push('1');
        }
        for _ in 0..lastketa {
            ans.push('0');
        }
        let s: String = ans.into_iter().collect();
        println!("{}", s);
    }
}


Measured memory_bytes: 4352
/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Max-Min Sums
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;

/* global variables */

int as[MAX_N];
int fs[MAX_N + 1], ifs[MAX_N + 1];

/* subroutines */

int powmod(int a, int n) {  // a^n % MOD
  int pm = 1;
  while (n > 0) {
    if (n & 1) pm = (ll)pm * a % MOD;
    a = (ll)a * a % MOD;
    n >>= 1;
  }
  return pm;
}

inline int invf(int n) {
  if (! ifs[n]) ifs[n] = powmod(fs[n], MOD - 2);
  return ifs[n];
}

inline int nck(int n, int k) {  // nCk % MOD
  if (n < 0 || k < 0 || n < k) return 0;
  return (ll)fs[n] * invf(n - k) % MOD * invf(k) % MOD;
}

/* main */

int main() {
  int n, k;
  scanf("%d%d", &n, &k);

  for (int i = 0; i < n; i++) scanf("%d", as + i);
  sort(as, as + n);

  fs[0] = ifs[0] = 1;
  for (int i = 1; i <= n; i++) fs[i] = (ll)fs[i - 1] * i % MOD;

  int sum = 0;
  for (int i = 0; i < n; i++)
    sum =
      ((sum + 
	(ll)(MOD - as[i]) * nck(n - 1 - i, k - 1) % MOD) % MOD +
       (ll)as[i] * nck(i, k - 1)) % MOD;

  printf("%d\n", sum);
  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PI 3.14159265358979323846264338327950L
#define MOD 1000000007
#define sz 100005
ll inf = 1e16;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
} 
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main()
{
 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  ll n;
  cin>>n;
  ll a[n],sum=0;
  map<ll,ll> m;
  for(ll i=0;i<n;i++)
    {
      cin>>a[i];
      sum+=a[i];
      m[a[i]]++;
    }
  ll q;
  cin>>q;
  while(q--)
  {
    ll c,d;
    cin>>c>>d;
    cout<<sum+m[c]*(d-c)<<'\n';
    sum=sum+m[c]*(d-c);
    if(m.find(d)!=m.end())
      m[d]=m[d]+m[c];
    else
      m.insert({d,m[c]});
    m.erase(c);
  }
  return 0;
}

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

using namespace std;

#define int long long

int32_t main(){

	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n,ans=0;
	cin>>n;

	ans+=n/500 * 1000;
	n%=500;
	ans+=n/5 * 5;

	cout<<ans;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,k;
string s;
int32_t main(){
CODE_START;
cin>>s;
n=s.size();
cin>>k;
for(ll i=0;i<n;i++)
if(s[i]!='1'&&i<k){
    rc(s[i]);
}
cout<<"1";
}



Measured memory_bytes: 256
from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
mark=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  a-=1;b-=1
  g[a].append(b)
  g[b].append(a)
D=deque([0])
visited=[False]*n
visited[0]=True
while D:
  v=D.popleft()
  for i in g[v]:
    if visited[i]:
      continue
    visited[i]=True
    mark[i]=v
    D.append(i)
print("Yes")
for i in range(1,n):
  print(mark[i]+1)

Measured memory_bytes: 35052
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)


int main(){
    int a,b,h;
    cin >> a >> b >> h;
    cout << (a+b)*h/2 << endl;

    return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  int n = (N-1) * (N-2) / 2;
  if(K > n) {
    cout << -1 << endl;
    return 0;
  }
  using P = pair<int, int>;
  vector<P> ans;
  rep(i, 1, N) ans.push_back(P(i, N));
  rep(i, 1, N) rep(j, i+1, N) {
    if(K == n - (ans.size() - (N - 1))) break;
    ans.push_back(P(i, j));
  }
  cout << ans.size() << endl;
  for(P p : ans) cout << p.first << " " << p.second << "\n";
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
using namespace std;
const long long mod = 1e9 + 7 ;


//This is power function which gives us x^y % mod 

long long power(long long x , long long y , long long mod){
 
  // Base Case
  if(y == 0) return 1 ;
  
  long long p = power(x , y/2 , mod)%mod ;
  p = (p * p) % mod ;
  
  if(y & 1){
    p = (x * p) % mod ;
  }
  
  return p ;
}

// This Function give us Inverse of factorial of n .

long long Inversefactorial(long long n ){
  
  // Base case
  if(n <= 0) return 1 ;
  
  long long fact=1;
  
  for(long long i=1 ; i <= n ; i++){
    fact=(fact * i) % mod ;
  }
  
  return power(fact , mod-2 , mod); 
}


//This Function return factorial n % mod 
long long factorial(long long n){
  
  // Base case
  if(n <= 0) return 1 ;
  
  long long fact=1;
  
  for(long long i=1 ; i <= n ; i++){
    fact=(fact * i) % mod ;
  }
  return fact ;
}
long long nck ( long long n , long long k ){
  
 // The value of nCk is n! / (( n- k)! * k!) 
  
  return (((factorial(n) * Inversefactorial(k)) % mod) * Inversefactorial(n - k)) % mod;
}

// Return the total number of ways reach (n , m) from (0 , 0)
long long TotalWays(long long n , long long m){
  
  // Case I : If (n+m)%3!=0 then answer is 0.
  
  if((n + m) % 3 != 0) return 0;
  
  /*Case II : Form the equation x + 2y = n and 2x + y == m , find the value of 
    		x and y and if x < 0 or y < 0 the our answer is zero
  */
  
  long long x = n - (n + m) / 3;
  long long y = m - (n + m) / 3;
  
  if(x < 0 || y < 0)
    return 0;
  
  //Case III : choose y moves from ( x + y ) moves 
  
  return nck (x + y , y) ;
  
}

int main() {
	long long n , m ;
  cin>> n >> m ;
  
  	cout<<TotalWays(n , m)<<endl;
  
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define el '\n'
typedef long long ll;
const int mod = 1e9 +7;
ll dp[105][5][5][5];
// A = 1
// C = 2
// G = 3
// T = 4
bool cek3(int a, int b, int c) {
  return (a==1 && b == 2 && c == 3);
}
bool cek4(int a, int b, int c, int d) {
  if (cek3(a, b, c) || cek3(b, c, d)) return false;
  if (cek3(a, c, b) || cek3(c, b, d)) return false;
  if (cek3(b, a, c) || cek3(a, c, d)) return false;
  if (cek3(a, b, d) || cek3(b, d, c)) return false;
  return true;
}
ll serc(int len, int a, int b, int c) {
  if (len == 0) return 1;
  if (dp[len][a][b][c] != -1) return dp[len][a][b][c];
  ll ret = 0;
  for (int nex = 1; nex <= 4; nex++) {
    if (cek4(a, b, c, nex)) {
      ret += serc(len-1, b, c, nex);
      if (ret >= mod) ret -= mod;
    }
  }
  if (a != 0 && b != 0 && c != 0) dp[len][a][b][c] = ret;
  // if (a == 0 || b == 0 || c == 0) {
  //   cerr << "ANJING ";
  //   cerr << a << " " << b << " " << c << el;
  // }
  return ret;  
}
int main() {
  int n;
  cin >> n;
  memset(dp, -1, sizeof(dp));
  cout << serc(n, 0, 0, 0) << el;
  return 0;
}

Measured memory_bytes: 384
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O2")
// #pragma GCC optimization ("unroll-loops")
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
// #define int ll
#define pb push_back
#define pob pop_back
#define __bp __builtin_popcount
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pdd = pair<ld,ld>;
using vint = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
#define F first
#define S second
const int N = 1e5+5;//(1 << 18) + 5;
//const ll inf = 1e18+7;
const int Inf = 1e9+7;
const ll INF = 1e18+7;
const int Mod = 1e9+7;
const ld eps = 1e-9;
#ifndef M_PI
#define M_PI 3.1415926535
#endif

void io()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cerr.tie(NULL);
//	freopen("sweets.in", "r", stdin);
//	freopen("sweets.out", "w", stdout);
//	cout << setprecision(7) << fixed;
}

int n;

void solve()
{
	ll a, b, c, d;
	cin >> a >> b;
	cin >> c >> d;
	ll x1 = a * c;
	ll x2 = a * d;
	ll x3 = b * c;
	ll x4 = b * d;
	cout << max(x1, max(x2, max(x3, x4)));
}

signed main()
{
	io();
	int tt = 1;
//	cin >> tt;
	while (tt--) {
		// solve();
		solve();
//		cerr << '\n';

	}
}

Measured memory_bytes: 3656
/*
*         ****FOX****
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <limits>
//freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#include <utility>
#include <list>
#include <cstdio>
#include<forward_list>
#include<algorithm>
#include<string>
#define Omar_Hafez ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926536
#define ll long long
#define ull unsigned long long
#define lli long long int
using namespace std;
int main()
{
    Omar_Hafez
   int n; cin >> n;
    vector<int> v(n,0); 
    for (int i = 1; i < 400; i++)
    {
        for (int j = 1; j < 400; j++)
        {
            for (int z = 1; z < 400; z++)
            {
                int res = (i * i) + (j * j) + (z * z) + (i * j) + (j * z) + (i * z);  
                if (res <= n)  v[--res]++;
                else break;
            }
        }
    }
    for (int i = 0; i< v.size(); i++) cout << v[i] << "\n";
    return 0;
}


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

using namespace std;

const int N = 51;
bool was[N];
bool g[N][N];
int a[N], b[N];

void dfs(int v, int &n){
  if(was[v]) return;
  was[v] = true;
  for(int i = 0; i < n; ++i)
    if(g[v][i]) dfs(i, n);
}

int main(){
  int n, m;
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; ++i){
    scanf("%d %d", &a[i], &b[i]);
    g[--a[i]][--b[i]] = true;
    g[b[i]][a[i]] = true;
  }
  int ans = 0;
  for(int i = 0; i < m; ++i){
    g[a[i]][b[i]] = false;
    g[b[i]][a[i]] = false;
    for(int j = 0; j < n; ++j) was[j] = false;
    dfs(0, n);
    bool bridge = false;
    for(int j = 0; j < n; ++j) if(!was[j]) bridge = true;
    if(bridge) ans++;
    g[a[i]][b[i]] = true;
    g[b[i]][a[i]] = true;
  }
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
#define Mod1(x) (x>=mod?x-mod:x)
#define Mod2(x) (x<0?x+mod:x)
#define maxn 1000010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
int p[maxn],mn[maxn],f[maxn];
int a[maxn],sum[maxn];
int n,mx,tot;
void euler(int n)
{
	tot=0; f[1]=1;
	for(int i=2;i<=n;i++){
		if(!mn[i])p[++tot]=i,mn[i]=tot,f[i]=Mod2(1-i);
		for(int j=1;j<=mn[i]&&i*p[j]<=n;j++)
			mn[i*p[j]]=j,f[i*p[j]]=(j==mn[i]?f[i]:(ll)f[i]*f[p[j]]%mod);
	}
//	for(int i=1;i<=n;i++)
//		printf("%d %d %d\n",i,p[mn[i]],f[i]);
}
int main()
{
	n=read();
	mx=0;
	for(int i=1;i<=n;i++){
		int k=read();
		mx=std::max(mx,k);
		++a[k];
	}
	euler(mx);
	for(int i=1;i<=mx;i++){
		sum[i]=0;
		for(int j=i,k=1;j<=mx;j+=i,++k)
			sum[i]=(sum[i]+(ll)k*a[j])%mod;
	}
	ll ans=0;
	for(int i=1;i<=mx;i++){
		ans=(ans+(ll)i*f[i]%mod*sum[i]%mod*sum[i])%mod;
//		printf("%d %lld\n",i,ans);
	}
//	writeln(ans);
	for(int i=1;i<=mx;i++){
		ll cur=(ll)i*a[i]%mod;
		ans=Mod2(ans-cur);
	}
	writeln(ans*((mod+1)>>1)%mod);
	return 0;
}

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

int main(){
  int n; cin>>n;
  vector<int> num(n);
  for(int i=0;i<n;i++){
    cin>>num[i];
  }sort(num.begin(),num.end());
  reverse(num.begin(),num.end());
  cout<<num[0]<<' ';
  long long ans=0;
  for(int i=0;i<n;i++){
    if(abs(num[0]/2-ans)>abs(num[0]/2-num[i]) || abs((num[0]+1)/2-ans)>abs((1+num[0])/2-num[i])){
      ans=num[i];
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 640
Scanf.(Array.(scanf " %d" @@ fun n ->
  let a = make 2000000 false in
  let col n = if n mod 2 = 0 then n/2 else 3*n+1 in
  let rec f i x = if a.(x) then i else
    (a.(x) <- true; f (i+1) (col x))
  in print_int @@ f 1 n))

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,Q;
string S;
int nex[505050][28];
int nexd[505050][20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	FORR(c,S) c-='a';
	N=S.size();
	FOR(i,27) nex[N][i]=nex[N+1][i]=N+1;
	FOR(i,20) nexd[N][i]=nexd[N+1][i]=N+1;
	for(i=N-1;i>=0;i--) {
		nex[i][S[i]]=i+1;
		for(j=S[i]+1;j<=26;j++) nex[i][j]=nex[nex[i][j-1]][j-1];
		for(j=0;j<S[i];j++) nex[i][j]=nex[nex[i][26]][j];
		nexd[i][0]=nex[i][26];
		for(j=0;j<19;j++) nexd[i][j+1]=nexd[nexd[i][j]][j];
	}
	cin>>Q;
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		for(i=19;i>=0;i--) if(nexd[L][i]<=R) L=nexd[L][i];
		if(L==R) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 95516
#include <utility>
#include <vector>
#include <iostream>
#include <cstdlib>
#include<bits/stdc++.h>
#include <limits>
#include <set>
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
using namespace std;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
    const int inf = 100000000;
    int n, m;
    cin >> n >> m;
    int a[1000], b[1000], c[1000], dist[100][100];
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--, b[i]--;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i==j){
                dist[i][j] =0;
            }else{
                dist[i][j] = inf;
            }
        }
    }

    for(int i = 0; i < m; i++){
        dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
        dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
            }
        }
    }
    int ans = m;
    for(int i = 0; i < m; i++){
        bool shortest = false;
        for(int j = 0; j < n; j++){
            if(dist[j][a[i]]+c[i] == dist[j][b[i]]){
                shortest = true;
            }
        }
        if(shortest){
            ans-=1;
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
vector<ll> G[2 * e5];
vector<ll> ans(2 * e5);
unordered_map<ll, ll> pl;
vector<bool> seen(2 * e5);

void dfs(ll now, ll value) {
    seen[now] = true;
    ans[now] = value;
    each(e, G[now]) {
        if (!seen[e]) {
            dfs(e, value + pl[e]);
        }
    }
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        cin.tie(0);
        ios::sync_with_stdio(false);
        
        ll n, q;
        cin >> n >> q;
        rep(i, n - 1) {
            ll a, b;
            cin >> a >> b;
            a--, b--;
            G[a].eb(b);
            G[b].eb(a);
        }

        rep(i, q) {
            ll p, x;
            cin >> p >> x;
            p--;
            pl[p] += x;
        }
        dfs(0, pl[0]);

        rep(i, n) cout << ans[i] << '\n';

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 32584
$N = gets.to_i
$ss, $sst = [], Array.new($N){Array.new($N)}
$N.times do |i|
    $ss[i] = gets.chomp.split('')
end

$sst = $ss.transpose

def check(a)
    (0...$N).each do |i|
        if $ss[i] != $sst[i]
            return false
        end
    end
    true
end

sum = 0
(0...$N).each do |a|
    sum += $N if check(a)
    (0...$N).each { |i| $ss[i].rotate!(1) }
    $sst.rotate!(1)
end
puts sum


Measured memory_bytes: 8060
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
vector<string> uvs;
vector<int> pu;
pair<int,string> solve(void){
  string answer="";
  REP(si,pu.size()){
    string &s=uvs[pu[si]];
    int ol=min(answer.size(),s.size());
    for(;ol>0;--ol){
      bool flag=true;
      REP(i,ol) if(answer[answer.size()-ol+i]!=s[i]){
	flag=false;
	break;
      }
      if(flag) break;
    }	       
    for(auto i=s.begin()+ol;i!=s.end();++i) answer.push_back(*i);
  }
  return make_pair(answer.size(),answer);
}
int main(void)
{
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    vector<pair<int,string> > vs(n);
    uvs.clear();
    REP(i,n){
      string s;
      cin >> s;
      vs[i]=make_pair(-(int)s.size(),s);
    }
    SORT(vs);
    REP(i,n){
      bool flag=true;
      REP(j,i) REP(k,vs[i].first-vs[j].first){
	string tmp=vs[j].second;
	string r(tmp.begin()+k,tmp.begin()+k-vs[i].first);
	if(vs[i].second==r) flag=false;
      }
      if(flag) uvs.push_back(vs[i].second);
    }
    pu.resize(uvs.size());
    REP(i,pu.size()) pu[i]=i;
    pair<int,string> answer(1000,"");
    do{
      answer=min(answer,solve());
    }while(next_permutation(pu.begin(),pu.end()));
    cout << answer.second << endl;
  }
}

Measured memory_bytes: 3156
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>

using ll = long long;
typedef unsigned long long ull;
typedef std::pair<int, int>p;
struct edge { int to, cost; };
std::vector<edge>v[1000];
typedef std::vector<std::vector<int>>ma;
ma d;

ll min(ll a, ll b) {
	if (a >= b)return b;
	else return a;
}
ll max(ll a, ll b) {
	if (a >= b)return a;
	else return b;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const ll Z = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
bool flag = true;
bool fl = true;
bool f = true;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
std::string abc = "abcdefghijklmnopqrstuvwxyz";

void warshall(int v) {
	for (int k = 0;k < v;k++)
		for (int i = 0;i < v;i++)
			for (int j = 0;j < v;j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
	int h, w;
	std::cin >> h >> w;
	d = ma(10, std::vector<int>(10, INF));
	for (int i = 0;i < 10;i++)
		for (int j = 0;j < 10;j++) {
		int c;
		std::cin >> c;
		d[i][j] = c;
	}
	warshall(10);
	int ans = 0;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			int a;
			std::cin >> a;
			if(a!=-1)ans += d[a][1];
		}
	}
	std::cout << ans << std::endl;
	}

Measured memory_bytes: 256
from math import *
from collections import *
from itertools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)


n=int(input())
l=list(map(int,input().split()))
c=Counter(l)
s=sum(l)
for i in range(int(input())):
    a,b=map(int,input().split())
    x=c[a]
    c[a]=0
    if b in c:
        c[b]+=x
    else:c[b]=x    
    s-=a*x
    s+=b*x
    print(s)
    


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

using ll = long long;
using P = pair<int, int>;

bool flag[200010];
vector<ll> v;

int main() {
  ll N, K;
  cin >> N >> K;
  ll a[N+1];
  for (int i = 1; i < N + 1; i++) cin >> a[i];

  ll now = 1;
  flag[now] = true;
  while (1) {
    now = a[now];
    if (flag[now]) break;
    flag[now] = true;
  }

  ll pivot = now;
  v.push_back(pivot);
  while (1) {
    now = a[now];
    if (now == pivot) break;
    v.push_back(now);
  }

  ll ans = -1;
  ll cnt = 1;
  now = 1;
  while (1) {
    if (now == pivot) break;
    now = a[now];
    if (cnt == K) {
      ans = now;
      break;
    }
    cnt++;
  }

  if (ans != -1) {
    cout << ans << endl;
  } else {
    ll tmp = K - (cnt - 1);
    ll sz = v.size();
    cout << v[tmp%sz] << endl;
  }

  return 0;
}

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

int main() {
    int N;
    int t[110000], x[110000], y[110000];
    cin >> N;
    t[0] = x[0] = y[0] = 0;  // 初期状態
    for (int i = 0; i < N; ++i) cin >> t[i+1] >> x[i+1] >> y[i+1];  // 1-index にしておく

    bool can = true;
    for (int i = 0; i < N; ++i) {
        int dt = t[i+1] - t[i];
        int dist = abs(x[i+1] - x[i]) + abs(y[i+1] - y[i]);
        if (dt < dist) can = false;
        if (dist % 2 != dt % 2) can = false;  // dist と dt の偶奇は一致する必要あり！
    }
    
    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>

int main(){
	long long h, w;
	std::cin >> h >> w;
	long long ans = 1;
	if(h>=2 and w>=2){
		if(h%2==1 and w%2==1){
			ans =  (h * w + 1) / 2;
		}else{
			ans =  (h * w) / 2;
		}
	}
	std::cout << ans << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

int main()
{
    fastio;
    ll a;
    long double b;
    cin >> a >> b;
    ll ans = a * b;
    cout << ans;
}

Measured memory_bytes: 3748
S = list(input())

cnt = 0
a = S[0]

for i in range(1,len(S)):
  if S[i] == a:
    cnt += 1
    if S[i] == "1":
      a = "0"
    else:
      a = "1"
  else:
    a = S[i]
    
print(int(cnt))


Measured memory_bytes: 49392
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;
const ll MOD = 1e9 + 7;

ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
const int MAXN = 2100;

vector<tuple<ll, int, int>> ed;

vector<pair<int, ll>> eds[MAXN];
int p[MAXN];
int sz[MAXN];

int get(int a) {
	if (p[a] == a)
		return a;
	return p[a] = get(p[a]);
}

int un(int a, int b) {
	a = get(a);
	b = get(b);
	if (a == b)
		return 0;
	if (sz[a] > sz[b])
		swap(a, b);
	p[a] = b;
	sz[b] += sz[a];
	return 1;
}

int get(int a, int p, int b) {
	if (a == b)
		return 1;
	for (auto e: eds[a]) {
		int u = e.first;
		if (u == p)
			continue;
		ll x = get(u, a, b);
		if (x) {
			x = max(x, e.second);
			return x;
		}
	}
	return 0;
}
ll sum;
int n, m;

ll get(ll x) {
	if (sum >= x)
		return pw(2, m);
	int cnt = 1;
	for (int i = 0; i < m; ++i) {
		int a, b; ll w;
		tie(w, a, b) = ed[i];
		ll go = sum - get(a, -1, b) + w;
		if (go >= x)
			++cnt;
	}
	return pw(2, cnt);
}

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n >> m;
	ll x;
	cin >> x;
	for (int i = 0; i < m; ++i) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		--a, --b;
		ed.emplace_back(w, a, b);
	}
	sort(ed.begin(), ed.end());
	for (int i = 0; i < n; ++i) {
		p[i] = i, sz[i] = 1;
	}
	sum = 0;
	for (int i = 0; i < m; ++i) {
		int a, b;
		ll w;
		tie(w, a, b) = ed[i];
		if (un(a, b)) {
			eds[a].emplace_back(b, w);
			eds[b].emplace_back(a, w);
			sum += w;
		}
	}
	ll ans = (get(x) - get(x + 1) + MOD) % MOD;
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 512
#include <stdio.h>

int main(){
  long input, tmp;
  long zerocount=0;
  long i;

  scanf("%ld", &input);
  while(input!=0){
    zerocount=0;
    for(i=5; i<=input; i=i+5){
      tmp=i;
      while(tmp%5==0){
        zerocount++;
        tmp/=5;
      }
    }
    printf("%ld\n", zerocount);
    scanf("%ld", &input);
  }
  return 0;
}

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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n,c = 1;
    cin >> n;
    int x[8],y[8];
    double ans = 0;
    for (int i = 0;i < n;++i) cin >> x[i] >> y[i];
    for (int i = 1;i < n;++i) c *= i;
    for (int i = 0;i < n;++i) {
        for (int j = 0;j < n;++j) ans += sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))*c;
    }
    cout << fixed << setprecision(12) << ans/c/n << endl;
}

Measured memory_bytes: 256