akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;

typedef long long ll;
ll n, t, Q, sz, st, l, r, md, ans, a[N], b[N], s[N], g1[N], g2[N];
int main()
{
	ll i, x;
	cin >> n >> Q;
	for (i = 1; i<= n; i++) {
		scanf ("%lld", &a[i]);
	}
	st = (n + 2) / 2;
	sz = n - st;
	for (i = st; i < n; i++) {
		l = a[1];
		r = a[i] + 1;
		while (l < r) {
			md = (l + r) / 2;
			t = lower_bound(a + 1, a + n + 1, md - (a[i] - md)) - a;
			if (i - t + 1 < n - i + 1) {
				b[i - st] = md;
				r = md;
			} else {
				l= md + 1;
			}
		}
	}
//	for (i = 1; i <=n; i++) printf("%")
	for (i = 1; i <= n; i++) {
		s[i] = s[i - 1] + a[i];
		g1[i] = g1[i - 1];
		g2[i] = g2[i - 1];
		if (i % 2 == 0) g2[i] += a[i];
		else g1[i] += a[i];
	}
	ll h;
	while (Q--) {
		scanf ("%lld", &x);
		t = upper_bound(b, b + sz, x) - b;
		t--;
		t += st;
		ans = s[n] - s[t];
		h = t - (n - t);
		if (h % 2 == 1) ans += g1[h];
		else ans += g2[h];
		printf("%lld\n", ans);
	}
    return 0;
}


Measured memory_bytes: 5248
def main():
    s = input()

    i = 1
    for l in s:
        if l == "a":
            i *= 2
        elif l == "b":
            i *= 3
        elif l == "c":
            i *= 5

    if i == 30:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include<stdio.h>
int main()
{
    int n,m[1002],mo,s=0,a,r,sm,i;
    scanf("%d%d",&n,&mo);
    for(i=0;i<n;i++)
    scanf("%d",&m[i]);
    for(i=0;i<n;i++)
    {
        s=s+m[i];
    }
    a=mo-s;
    sm=m[0];
    for(i=0;i<n;i++)
    {
        if(m[i]<sm)
        sm=m[i];
    }
    r=a/sm;
    printf("%d",r+n);
    return 0;
    
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>

using namespace std;

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

	int N{};
	int T{};
	int A{};
	constexpr int ratio{ 6 };
	cin >> N;
	cin >> T >> A;
	vector<int> H;
	for( int i = 0; i < N; i++ )
	{
		int Hi{};
		cin >> Hi;
		H.push_back( Hi );
	}

	int point{ -1 };
	int min_ = numeric_limits<int>::max();
	for( int i = 0; i < N; i++ )
	{
		int a{ T * 1000 - (H[i] * ratio) };
		int prev = min_;
		min_ = min( abs( A * 1000 - a ), min_ );
		if( min_ != prev )
		{
			point = i;
		}
	}
	cout << point + 1 << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String args[]){
    //入力
    Scanner scanner = new Scanner(System.in);
    String S = scanner.next();
    
    //初期値
    String[] arrayS = S.split("");
    int N = S.length();
	int[] nums = new int[N];
    for(int num: nums){
      num = 0;
    }
    
    int[] RLs = new int[N];
    RLs[0] = 0;
    int countRL = 1;
    
    int[] LRs = new int[N];
    LRs[0] = 0;
    int countLR = 1;
    
    //処理
    for(int i = 0; i < N - 1; i++){
      if("R".equals(arrayS[i]) &&  "L".equals(arrayS[i + 1])){
        //RLの場所
        RLs[countRL] = i;
        countRL++;
      }
      
      if("L".equals(arrayS[i]) && "R".equals(arrayS[i + 1])){
        //LRの場所
        LRs[countLR] = i;
        countLR++;
      }
    }
    
    LRs[countLR] = N - 1;
    
    for(int i = 1; i < N; i++){
      if(RLs[i] == 0 && i > 1){
        break;
      }
      //Lの個数
      int amountL = LRs[i] - RLs[i];
      
      if(amountL % 2 == 0){
        //Lの個数が偶数の場合の集まり方
        nums[RLs[i] + 1] += amountL / 2;
        nums[RLs[i]] += amountL / 2;
      } else {
        //Lの個数が奇数の場合の集まり方
        nums[RLs[i] + 1] += (amountL + 1) / 2;
        nums[RLs[i]] += (amountL - 1) / 2;
      }
      
      if(LRs[i] == 0){
        break;
      }
      
      //Rの個数
      int amountR = RLs[i] - LRs[i - 1];
      if(LRs[i - 1] == 0){
        amountR = RLs[i] - LRs[i - 1] + 1;
      }
      
      if(amountR % 2 == 0){
        //Rの個数が偶数の場合の集まり方
        nums[RLs[i]] += amountR / 2;
        nums[RLs[i] + 1] += amountR / 2;
      } else {
        //Rの個数が奇数の場合の集まり方
        nums[RLs[i]] += (amountR + 1) / 2;
        nums[RLs[i] + 1] += (amountR - 1) / 2;
      }
    }
    
    for(int num: nums){
      System.out.print(num);
      System.out.print(" ");
    }
  }
}


Measured memory_bytes: 47644
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define int long long
#define ll long long
#define eps LDBL_EPSILON
#define mod 1000000007
#define int long long
#define double long double
#define INF LLONG_MAX/10
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, s[10010], q, t[510];
signed main() {
	cin >> n;
	rep(i, n)cin >> s[i];
	cin >> q;
	rep(i, q)cin >> t[i];
	int ans = 0;
	rep(i, q) {
		bool f = false;
		rep(j, n)if (s[j] == t[i])f = true;
		if (f)ans++;
	}
	cout << ans << endl;
	return 0;
}


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


using namespace std;


using ll = long long;


void max_heapify(vector<ll> &A, ll i)
{
    ll li, ri, max_i;
    li = i * 2;
    ri = i * 2 + 1;
    max_i = i;

    if (li <= A.size() - 1 && A[i] < A[li]) {
        max_i = li;
    }

    if (ri <= A.size() - 1 && A[max_i] < A[ri]) {
        max_i = ri;
    }

    if (i != max_i) {
        ll t = A[max_i];
        A[max_i] = A[i];
        A[i] = t;

        max_heapify(A, max_i);
    }
}


void build_max_heap(vector<ll> &A)
{
    for (ll i = (A.size() - 1) / 2; i >= 1; i--) {
        max_heapify(A, i);
    }
}


void insert(vector<ll> &A, ll key)
{
    A.push_back(key);
    ll i = A.size() - 1;
    while (i > 1 && A[i] > A[i / 2]) {
        ll tmp = A[i];
        A[i] = A[i / 2];
        A[i / 2] = tmp;
        i /= 2;
    }
}


ll extract(vector<ll> &A)
{
    ll ret = A[1];
    A[1] = A.back();
    A.pop_back();

    max_heapify(A, 1);
    return ret;
}


int main()
{
    vector<ll> A(1);
    string cmd;

    while (true) {
        cin >> cmd;
        if (cmd == "end") {
            break;
        } else if (cmd == "insert") {
            ll tmp;
            cin >> tmp;
            insert(A, tmp);
        } else if (cmd == "extract") {
            cout << extract(A) << endl;
        }
    }
}



Measured memory_bytes: 11172
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,p[300000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>p[i];
    }
    int m=9999999;
    int ans=0;
    for(int i=0;i<n;i++){
        if(m>=p[i]) ans++;
        m=min(m,p[i]);
    }
    cout<<ans;
}


Measured memory_bytes: 1024
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int n = stdIn.nextInt();
        int m = stdIn.nextInt();
        int L[] = new int [m];
        int R[] = new int [m];
        int maxL = 1; int minR = n;
        for(int i = 0; i < m; i++){
            L[i] = stdIn.nextInt();
            R[i] = stdIn.nextInt();
            if(maxL < L[i]) maxL = L[i];
            if(minR > R[i]) minR = R[i];
        }

        System.out.println(minR-maxL+1 >= 0 ? minR-maxL+1 : 0 );
    }
}

Measured memory_bytes: 76008
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new java.util.Scanner(System.in);
        double a = scan.nextDouble(); // ??????
        double b = scan.nextDouble(); // ???
        double C = scan.nextDouble(); // ab???????§?
        double S = a * (b * Math.sin(Math.toRadians(C))) / 2;
        double L = a + b + Math.sqrt(a * a + b * b - 2 * a * b * Math.cos(Math.toRadians(C)));
        double h = (S / a) * 2;
        System.out.println(S);
        System.out.println(L);
        System.out.println(h);
    }
}

Measured memory_bytes: 27808
#include<iostream>
#include<string>
#include<queue>
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;
priority_queue<ll> que;

int main(){
    int n, m;
    ll a[110000];
    ll tmp;
    ll ans=0;

    cin >> n >> m;
    rep(i,n){
        cin >> tmp;
        que.push(tmp);
    }
    rep(i,m){
        tmp =  que.top()/2;
        que.pop();
        que.push(tmp);
    }
    rep(i,n){
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1400
#include<stdio.h>




int main(){
	int N,K;
	int S[100];
	int B;
	int count;
	int h=1;

	int i,j;

	scanf("%d %d",&N,&K);

	while((N!=0)&&(K!=0)){
		h=1;
		for(i=0;i<K;i++){
			scanf("%d",&S[i]);
		}

		for(i=0;i<N;i++){
			for(j=0;j<K;j++){
				scanf("%d",&B);
				if(h==1){
					S[j]=S[j]-B;
					if(S[j]<0){
						h=0;
						printf("No\n");
					}
				}
			}
		}
		if(h==1){
			printf("Yes\n");
		}


		scanf("%d %d",&N,&K);
	}

	return 0;

}

Measured memory_bytes: 732
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstring>
#include<deque>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<tuple>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << endl

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

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

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

    int n;
    while(cin >> n, n){
        vector< tuple<lint, int, int> > v(5000);
        rep(i, 5000){
            get<1>(v[i]) = n + 1;
            get<2>(v[i]) = i;
        }

        rep(i, n){
            int e;
            lint p, q;
            cin >> e >> p >> q;
            get<0>(v[e]) = max(get<0>(v[e]) - p * q, -1000000LL);
            chmin(get<1>(v[e]), i);
        }

        SORT(v);

        if(get<0>(v[0]) > -1000000LL){
            cout << "NA" << endl;
        }else{
            for(int i = 0 ; i < 4000 && get<0>(v[i]) <= -1000000LL ; ++i){
                cout << get<2>(v[i]) << endl;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 3236
#include <stdio.h>
int main(void){
 int w,a,b;
 scanf("%d%d%d",&w,&a,&b);
 if(b>=a&&b<=a+w||b+w>=a&&b+w<=a+w) puts("0");
 else{
  printf("%d",a<b?b-a-w:a-b-w);
 }
 return 0;
}


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

int main(){
	long long S, c;
	cin >> S >> c;
	long long ans;
	if(S >= c / 2){
		ans = c / 2;
	}else{
		ans = S;
		c -= S * 2;
		ans += c / 4;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import bisect

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans = 0
for i in b:
    ans += bisect.bisect_left(a,i)*(n-bisect.bisect_right(c,i))
print(ans)

Measured memory_bytes: 23232
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

res = 0
for i in range(N):
    res += B[A[i] - 1]
    if i <= N - 2 and A[i + 1] - A[i] == 1:
        res += C[A[i] - 1]

print(res)

Measured memory_bytes: 38256
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    int n;
    cin>>n;
    int ans=inf;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            int a=n/i;
            int b=i;
            {
                int gap=abs(1-a)+abs(1-b);
                ans=min(ans,gap);
            }


        }

    }
    cout<<ans<<endl;

















    return 0;

}














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

using db = double;

struct poi {
	db x, y;
	void r() { cin >> x >> y; }
	poi operator -(poi p) {
		return {x - p.x, y - p.y};
	}
	poi operator /(db d) {
		return {x / d, y / d};
	}
	db cross(poi p) {
		return x * p.y - y * p.x;
	}
	db len2() {
		return x * x + y * y;
	}
};

poi circum(poi a, poi b, poi c) {
	poi ba = b - a, ca = c - a;
	db lb = ba.len2(), lc = ca.len2(), s = ba.cross(ca);
	return a - poi{ba.y * lc - ca.y * lb,
		ca.x * lb - ba.x * lc} / s / 2;
}

int main() {
	cout << fixed << setprecision(3);
	ios :: sync_with_stdio(false);
	int t; cin >> t;
	while(t --) {
		poi a, b, c;
		a.r(); b.r(); c.r();
		poi o = circum(a, b, c);
		cout << o.x << ' ' << o.y << ' ' << sqrt((o - a).len2()) << '\n';
	}
	return 0;
}

Measured memory_bytes: 3256
#include <bits/stdc++.h>
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define REP(i, n) for(int i = 0; i < n; i++)
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    int s;
    int a[m];
    REP(i,m){
        cin>>s;
        a[i] = s;
    }
    unsigned long long dp[100100] = {0};
    int key,tmp = 0;
    dp[0] = 1;
    for(int i = 1; i < n+1; i++){
        if(i == 1 and a[0] != 1){
            dp[1] += 1;
        }
        else{
            key = 0;
            for(int j = tmp; j < m; j++){
                if(i == a[j]){
                    key = 1;
                    tmp = j;
                    break;
                }
            }
            if(key == 0){
                dp[i] += dp[i-1];
                dp[i] += dp[i-2];
                dp[i] %= 1000000007;
            }
        }
    }
    /*
    REP(i, n+1){
        cout<<i<<dp[i]<<endl;
    }
    */
    cout<<dp[n]%1000000007<<endl;
    return 0;
}

Measured memory_bytes: 1408
import sys
l1 = input().split()
l2 = []
for num in l1:
    l2.append(int(num))
value = []
for c in range(0,2*max([l2[3],l2[4]])+1,2):
    a = max([l2[3]-(c/2),0])
    b = max([l2[4]-(c/2),0])                    
    value.append(int((a*l2[0])+(b*l2[1])+(c*l2[2    ])))
print(min(value))


Measured memory_bytes: 7064
import queue

H,W = map(int,input().split())
S = [list(map(str,input())) for _ in range(H)]

ddx = [1,-1,0,0]
ddy = [0,0,1,-1]

INF = 1<<30
ans = 0
for sx in range(W):
    for sy in range(H):       
        if S[sy][sx] == '#': continue
        d = 0
        q = queue.Queue()
        dist = [[INF]*W for _ in range(H)]
        dist[sy][sx] = 0
        q.put([sx,sy])
        while not q.empty():
            x,y = q.get()
            for i in range(4):
                dx = ddx[i]
                dy = ddy[i]
                if y+dy<0 or y+dy>=H or x+dx<0 or x+dx>=W:
                    continue
                if S[y+dy][x+dx] == '.' and dist[y+dy][x+dx] == INF:
                    dist[y+dy][x+dx] = dist[y][x] + 1
                    q.put([x+dx,y+dy])
        
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    d = max(d,dist[i][j])
            
        ans = max(ans,d)
        
print(ans)

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

int main() {
    int num, sub; cin >> num >> sub;
    int wrong = 0, accepted = 0;
    int wrong_answers[105000];
    map<int,bool>mp;
    for(int i = 1; i <= num; i++){
        mp[i] = false;
        wrong_answers[i] = 0;
    }
    
    while(sub--){
        int curr;
        string v;
        cin >> curr >> v;
        if(mp[curr]) continue;
        //has NOT been solved.
        if(v == "WA"){
            wrong_answers[curr]++;
        }
        //has NOT been evaluated.
        if(v == "AC"){
            mp[curr] = true;
            accepted++;
            wrong+=wrong_answers[curr];
        }
    }
    cout << accepted << " " << wrong << endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  bool ans = 1;
for(int i = 0; i < 3; i++){
if(S[i] == '7') ans = 0;

}

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


Measured memory_bytes: 3600
#include <bits/stdc++.h>
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<bool> VB;
typedef vector<double> VD;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//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 SQ(a) ((a)*(a))
#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())
#define LB lower_bound
#define UB upper_bound

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL INF = 1000000000;
const LL MOD = 1000000007;

//other
//-------------------------------------------
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define FI first
#define SE second

int main() {
  int N, x=0;
  cin >> N;
  REP(i,N) {
    int p;
    cin >> p;
    if(p != (i+1)) x++;
  }
  if(x < 3) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
  return 0;
}
  

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

int main(){
    string S;
    cin >> S;
    reverse(S.begin(),S.end());

    vector<string> T = {"dream","dreamer","erase","eraser"};
    for(int i = 0; i < 4; i++){
        reverse(T.at(i).begin(),T.at(i).end());
    }

    bool can =true;
    for(int i = 0; i < S.size();){
        bool can2 = false;
        for(int j = 0; j < 4; j++){
            string d = T.at(j);
            if(S.substr(i,d.size()) == d){
                can2 = true;
                i += d.size();
            }
        }
        if(!can2){
            can = false;
            break;
        }
    }
    if(can)cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 3728
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
string a;
const int inf=1e9+1000;
const int maxn=2050;
int head[maxn],cnt;
struct gg {
    int u,v,next;
}side[maxn*2];
int size[maxn],sum,f[maxn],F[maxn],depth[maxn],dep_sum[maxn];
void insert(int u,int v) {
    side[++cnt]=(gg){u,v,head[u]};head[u]=cnt;
}
int ans=inf;
void init() {
    memset(F,0,sizeof(F));
    memset(size,0,sizeof(size));memset(f,0,sizeof(f));sum=0;
    memset(dep_sum,0,sizeof(dep_sum));
    for(int i=0;i<a.length();i++)size[i+1]=(a[i]=='1');
}
void dfs(int u,int fa,int d) {
    int tot=0,k=0,mx=-1;depth[u]=d;
    for(int i=head[u];i;i=side[i].next) {
        int v=side[i].v;if(v==fa)continue;
        dfs(v,u,d+1);
        dep_sum[u]+=dep_sum[v]+size[v];
        if(dep_sum[v]+size[v]>mx) {
            mx=dep_sum[v]+size[v];k=v;
        }
        size[u]+=size[v];
        tot+=dep_sum[v]+size[v];
    }
    int sum=tot-(dep_sum[k]+size[k]);
    if(mx<=sum)F[u]=tot/2;
    else F[u]=sum+min(mx-sum,2*F[k])/2;
}
int main() {
    ios::sync_with_stdio(0);
    int n;cin>>n>>a;
    for(int i=1,u,v;i<n;i++) {
        cin>>u>>v;
        insert(u,v);insert(v,u);
    }
    for(int i=1;i<=n;i++) {
        init();
        dfs(i,0,0);
        if(F[i]*2==dep_sum[i]) {
            ans=min(ans,dep_sum[i]);
        }
    }
    if(ans>=inf)printf("-1");
    else printf("%d",ans/2);
    return 0;
}

Measured memory_bytes: 512
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main(){
    input!{
        a:usize,
        b:usize,
    }
    let ans = (a * 3 + b)/2;
    println!("{}",ans);
}

Measured memory_bytes: 4352
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int lend=100000;
	for(int i=1;i<=n;i++){
		lend=(lend*1.05-1)/1000;
		lend=(lend+1)*1000;
	}
	cout<<lend<<endl;
}

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

namespace AOJ
{
  class Point
  {
    public double X { get; private set; }
    public double Y { get; private set; }

    public Point(double x, double y)
    {
      X = x;
      Y = y;
    }

    public static Point operator+ (Point p1, Point p2)
    {
      return new Point(p1.X + p2.X, p1.Y + p2.Y);
    }

    public static Point operator- (Point p1, Point p2)
    {
      return new Point(p1.X - p2.X, p1.Y - p2.Y);
    }
  }

  class Program
  {
    public static void Main()
    {
      foreach (var points in ReadPoints())
      {
        if (IsInTriangle(points[0], points[1], points[2], points[3]))
          Console.WriteLine("YES");
        else
          Console.WriteLine("NO");
      }
    }

    static IEnumerable<Point[]> ReadPoints()
    {
      string line;
      while ((line = Console.ReadLine()) != null)
        yield return line.Split(' ').Select((s, i) => new { Index = i, Value = double.Parse(s) })
                                    .GroupBy(x => x.Index / 2)
                                    .Select(x => x.Select(v => v.Value))
                                    .Select(x => new Point(x.First(), x.Skip(1).First()))
                                    .ToArray();
    }

    static bool IsInTriangle(Point a, Point b, Point c, Point p)
    {
      var center = new Point((a.X + b.X + c.X) / 3.0, (a.Y + b.Y + c.Y) / 3.0);
      if (IntersectionLine(a, b, p, center)
          || IntersectionLine(a, c, p, center)
          || IntersectionLine(b, c, p, center)) return false;
      return true;
    }

    static bool IntersectionLine(Point a1, Point a2, Point b1, Point b2)
    {
      return ((a1.X - a2.X) * (b1.Y - a1.Y) + (a1.Y - a2.Y) * (a1.X - b1.X))
        * ((a1.X - a2.X) * (b2.Y - a1.Y) + (a1.Y - a2.Y) * (a1.X - b2.X)) < 0;
    }
  }
}

Measured memory_bytes: 6772
#include <utility>
#include <vector>
#include <iostream>
#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);
    int N;
    cin >> N;
    long names[5] = {};
    REP(i,N){
        string name;    
        cin >> name;
        if (name[0] == 'M'){
            names[0]++;
        }else if (name[0] == 'A'){
            names[1]++;    
        }else if (name[0] == 'R'){
            names[2]++;    
        }else if (name[0] == 'C'){
            names[3]++;    
        }else if (name[0] == 'H'){
            names[4]++;    
        }
    }
    long ans = 0;
    for(int i = 0; i < 3; i++){
        for(int j = i+1; j < 4; j++){
            for(int k = j+1; k < 5; k++){
                if(names[i] > 0 && names[j] > 0 && names[k] >0){
                    ans += names[i]*names[j]*names[k];
                }
            }    
        }
    }
    cout << ans<<endl;
    
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
//----------program from here----------



int main(){
  int a,b;
  cin >> a >> b;
  int ans = max((a+b), (a-b));
  ans = max((a*b), ans);
  cout << ans;
  return 0;
}


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

int main(){
  int a, b;
  bool f=false;
  cin >> a >> b;
  for(int i=1;i<=10000;i++){
    if(i*8/100==a&&i*10/100==b){
      cout << i << endl;
      f=true;
      break;
    }
  }
  if(f==false)cout << "-1" << endl;
  return 0;
}


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

Int s[20][20],idx[20][20],cnt,pru;
Int u[40][4];
Int num[40],ok[40];
vector<vector<vector<Int> > > G;

unordered_map<int, int> dp;
Int dfs(Int z,Int b){
  if(b==0) dp.clear();
  int hs=(b<<5)|z;
  if((z&3)==0) if(dp.count(hs)) return dp[hs];

  Int res=0;
  
  for(Int k=0;k<4;k++){
    for(auto w:G[z][k]){
      if((b>>w)&1) break;
      Int nb=b^(1<<w),flg=1;
      for(Int i=0;i<4;i++){
	if(u[w][i]>=cnt) continue; 
	num[u[w][i]]--;
	if((~nb>>u[w][i])&1)
	  flg&=num[u[w][i]]>=1;
      }
      if(flg){
	if(nb+1==(1<<cnt)) res+=ok[w];
	else if((nb&pru)!=pru) res+=dfs(w,nb);
      }
      for(Int i=0;i<4;i++) num[u[w][i]]++;
    }
  }
  
  if((z&3)==0) dp[hs]=res;
  return res;
};

//INSERT ABOVE HERE
signed main(){
  Int w,h;
  while(cin>>w>>h,w+h){
    for(Int i=0;i<h;i++)
      for(Int j=0;j<w;j++)
	cin>>s[i][j];
    
    cnt=0;
    for(Int i=0;i<h;i++){
      for(Int j=0;j<w;j++){
	idx[i][j]=cnt;
	cnt+=s[i][j]==1;
      }
    }
    
    for(Int i=0;i<h;i++)
      for(Int j=0;j<w;j++)
	if(s[i][j]==2) idx[i][j]=cnt;
    
    Int dy[]={0,0,1,-1};
    Int dx[]={1,-1,0,0};
    auto in=[&](Int y,Int x){return 0<=y&&y<h&&0<=x&&x<w;};    

    G.clear();
    G.resize(cnt+1);
    
    memset(num,0,sizeof(num));    
    memset(ok,0,sizeof(ok));
    
    for(Int y=0;y<h;y++){
      for(Int x=0;x<w;x++){
	if(s[y][x]==0) continue;
	Int z=idx[y][x];
	G[z].resize(4);
	for(Int k=0;k<4;k++){
	  Int ny=y,nx=x;
	  while(1){
	    ny+=dy[k],nx+=dx[k];
	    while(in(ny,nx)&&s[ny][nx]==0)
	      ny+=dy[k],nx+=dx[k];
	    if(!in(ny,nx)) break;	    
	    if(s[ny][nx]==2) ok[z]=1;
	    else G[z][k].emplace_back(idx[ny][nx]);
	  }
	}
	
	for(Int k=0;k<4;k++){
	  u[z][k]=cnt+1;
	  for(auto w:G[z][k]){
	    u[z][k]=w;
	    num[w]++;
	    break;
	  }
	}
	
	if(z==cnt){
	  pru=0;
	  for(Int k=0;k<4;k++){
	    for(auto w:G[z][k]){
	      pru|=(1<<w);
	      break;
	    }
	  }
	}
      }
    }

    cout<<dfs(cnt,0)<<endl;
  }
  return 0;
}



Measured memory_bytes: 120616
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define INF 1e9+7
#define roop(i,m,n) for(int i=m;i<n;i++)
#define mroop(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;

//おまじない



int main() {

	int N;

	cin >> N;

	cout << 800 * N - N / 15 * 200 << endl;

	return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);


    int n, m;
    cin >> n >> m;

    vector<pair<int,int>> P;
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        P.emplace_back(l, r);
    }

    vector<int> X;
    for (auto& p : P) {
        for (auto x : {p.first, p.second}) {
            for (int i = -1; i < 2; ++i) {
                int nx = x + i;
                if (nx >= 0 && nx < m) {
                    X.push_back(nx);
                }
            }
        }
    }

    X.push_back(0);
    X.push_back(m - 1);
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());

    vector<int> indices(m + 1, -1);
    for (int i = 0; i < X.size(); ++i) {
        indices[X[i]] = i;
    }

    set<int> S;
    multiset<int> MS;
    vector<int> dp(m + 2, 0);
    for (auto x : X) {
        dp[x] = 0;
        MS.insert(0);
        S.emplace(x);
    }

    for (int i = 0; i < n; ++i) {
        int l = P[i].first, r = P[i].second;
        auto it = S.lower_bound(l);
        int ans = 1 << 24;
        while (it != S.end()) {
            if (*it > r) {
                break;
            } else {
                int x = *it;
                // cout << i << " " << " remove " << x << endl;
                MS.erase(MS.find(dp[x]));
                it = S.erase(it);
                ans = min(ans, r + 1 - x + dp[x]);
                dp[x] = 1 << 24;
            }
        }
        // cout << "update " << ans << " " << r + 1 <<  endl;
        if (r + 1 < m && ans < dp[r + 1]) {
            if (S.count(r + 1) == 0) {
                S.insert(r + 1);
            } else {
                MS.erase(MS.find(dp[r + 1]));
            }
            dp[r + 1] = ans;
            MS.insert(ans);
        }
        if (S.empty()) {
            cout << -1 << '\n';
        } else {
            cout << *MS.begin() + i + 1 << '\n';
        }
    }

    return 0;
}

Measured memory_bytes: 29704
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#define rep(i,n) for (int i = 0; i < (n);i++)
typedef long long ll;
using namespace std;
/*#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;*/


void Main()
{
    int n; cin >>n;
    vector<int> h(n); rep(i,n) cin>>h.at(i);
    priority_queue<int> que;
    int count = 0;
    rep(i,n-1){
        if(h.at(i) >= h.at(i+1)) count++;
        else {
            que.push(count);
            count = 0;
        } 
    }
    que.push(count);
    cout << que.top() << endl;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

Measured memory_bytes: 1276
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
//string s;
#define rep2(x,from,to) for(long long x=from;x<to;x++)
#define rep(x,to) rep2(x,0,to)
long long n;
long long ans;
long long m;
long long a[100006];
priority_queue<long long> que; 
int main()
{
    cin>>n;
    cin>>m;
    rep(i,n)
    {
        cin>>a[i];
        que.push(a[i]);
    }
    rep(i,m)
    {
        long long t=que.top();
        que.pop();
        que.push((long long)(t/2));
    }
    while(!que.empty())
    {
        ans+=que.top();
        que.pop();
    }
    cout<<ans<<endl;
    return 0;
}

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



int wa(int c){ //各位の和
    int cnt = 0;
    while(true){
        if(c / 10 == 0){
            cnt += c % 10;
            break;
        }
        cnt += c % 10;
        c /= 10;
    }
    return cnt;
}

int number(int n){
    vector<int> plus(n);
    for(int i=0; i<n; i++){
        int a = (i+1);
        int b = n - a;
        int c = wa(a);
        int d = wa(b);
        plus.at(i) = c + d;
    }

    sort(plus.begin(), plus.end());

    return plus.at(0);
    /*
    a = 1;
    int a_wa = wa(a);
    b = n - 1;
    int b_wa = wa(b);
    return a_wa + b_wa;
    */
}

int main(){ // 各位の和を配列に入れてソートすれば答えが出そう
    int N;
    cin >> N;
    int ans = number(N);
    if(ans == 1) ans *= 10;

    cout << ans << endl;
}

Measured memory_bytes: 3748
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define ALL(a) begin(a),end(a)
#define INF 999999999
#define debug(x) cerr << #x << ":" << x << '\n'
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef unsigned long long ull;
typedef unsigned long ul;
typedef unsigned int  ui;

int main() {
	int N, T;
	cin >> N >> T;
	int c[N], t[N];
	REP(i, N) cin >> c[i] >> t[i];
	
	int c_min = 1001, cost = 0;
	REP(i, N) { 
		if(t[i] <= T) {
			if(c[i] < c_min) c_min = c[i];
		}
	}
	if(c_min == 1001) cout << "TLE" << "\n";
	else cout << c_min << "\n";
}


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

int main()
{
	int n;
    cin >> n;
    bool ans = false;
    int d[n][2];
    for (int i = 0; i < n; i++)
    {
        cin >> d[i][0] >> d[i][1];
    }

    for (int i = 0; i < n - 2; i++)
    {
        if(d[i][0] == d[i][1] && d[i + 1][0] == d[i + 1][1] && d[i + 2][0] == d[i + 2][1])ans = true;
    }
    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3668
//B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n,cnt = 0;
	cin >> n;
	ll now = 100;
	while(now < n){
		cnt++;
		now += (ll)floor(now*0.01);
	}
	cout << cnt;
	return 0;
}


Measured memory_bytes: 3716
n,m=map(int, input().split())

arr=[[] for i in range(n+1)]

gro=[0]*(n+1)

for i in range(m):
    a,b=map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

from collections import deque
deque=deque()

gro_no=0

for i in range(1,n+1):
    if gro[i]==0:
        gro_no+=1
        gro[i]=gro_no
        deque.append(i)

    while deque:
        j=deque.popleft()
        for k in arr[j]:
            if gro[k]==0:
                gro[k]=gro_no
                deque.append(k)

print(gro_no-1)

Measured memory_bytes: 82488
package main

import (
        "fmt"
)

func solution(n int, h []int) int {
        memo := make([]int, n)
        for i := 1; i < n; i++ {
                if h[i-1] >= h[i] {
                        memo[i] = memo[i-1] + 1
                }
        }
        out := -1 << 31
        for i := range memo {
                out = max(out, memo[i])
        }
        return out
}

func max(x, y int) int {
        if x > y {
                return x
        }
        return y
}

func main() {
        var n int
        fmt.Scan(&n)
        h := make([]int, n)
        for i := 0; i < n; i++ {
                a := 0
                fmt.Scan(&a)
                h[i] = a
        }
        fmt.Println(solution(n, h))
}

Measured memory_bytes: 5504
#include<bits/stdc++.h> 
#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vb = vector<bool>;
const int INF = 1e9;
const int MOD = 1e9+7;

int N, K = 0;
vector<P> input;
vector<vi> G;
map<P, int> color;
vb visited;

void dfs(int n, int pc)
{
    K = max(K, (int)G[n].size());
    visited[n] = true;
    int c = 1;
    REP(i, G[n].size())
    {
        if(!visited[G[n][i]])
        {
            if(c == pc) c++;
            color[make_pair(min(n, G[n][i]), max(n, G[n][i]))] = c;
            dfs(G[n][i], c);
            c++;
        }
    }
}

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    cin >> N; G.resize(N); visited.resize(N);
    REP(i, N-1)
    {
        int a, b; cin >> a >> b;
        a--; b--;
        input.push_back(make_pair(a, b));
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(0, -1);
    cout << K << endl;
    REP(i, N-1) cout << color[input[i]] << endl;
}

Measured memory_bytes: 13176
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let m: usize = read();
    let mut cities: Vec<u32> = vec![0;n];

    for _ in 0..m {
        let a: usize = read();
        let b: usize = read();
        cities[a-1] += 1;
        cities[b-1] += 1;
    }

    for i in 0..n {
        println!("{}", cities[i as usize]);
    }
}


Measured memory_bytes: 4352
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int main(void)
{
    ll T,t,x,y,n,k,r,d;
    scanf("%lld %lld %lld",&r,&d,&x);
    for(int i=0;i<10;i++)
    {
        printf("%lld\n",(x*r)-d);
        x=(x*r)-d;
    }
    return 0;
}









Measured memory_bytes: 256
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=100000+19;
const int p=1e9+7;

struct Matrix{
	int s[3][3];
} F,sum,st,A,I;
int dp[N],x[N];
int n,m;

Matrix operator * (int k,Matrix A){
	For(i,0,3) For(j,0,3) A.s[i][j]=1ll*k*A.s[i][j]%p;
	return A;
}
Matrix operator * (const Matrix &A,const Matrix &B){
	static Matrix C;
	For(i,0,3) For(j,0,3){
		C.s[i][j]=0;
		For(k,0,3) C.s[i][j]=(C.s[i][j]+1ll*A.s[i][k]*B.s[k][j])%p;
	}
	return C;
}
Matrix Pow(Matrix A,int b){
	Matrix res=A;
	for (--b;b;b>>=1,A=A*A) if (b&1) res=res*A;
	return res;
}
Matrix operator + (Matrix A,Matrix B){
	For(i,0,3) For(j,0,3) A.s[i][j]=(A.s[i][j]+B.s[i][j])%p;
	return A;
}
Matrix operator - (Matrix A,Matrix B){
	For(i,0,3) For(j,0,3) A.s[i][j]=(A.s[i][j]-B.s[i][j]+p)%p;
	return A;
}
int cal(int m){
	return (st*Pow(A,m)).s[0][0];
}

int main(){
	m=IN(),n=IN();
	For(i,1,n+1) x[i]=IN();
	x[++n]=m;
	st.s[0][0]=0;
	st.s[0][1]=1;
	st.s[0][2]=5;
	A.s[0][2]=1;
	A.s[1][0]=1;
	A.s[1][2]=p-2;
	A.s[2][1]=1;
	A.s[2][2]=4;
	I.s[0][0]=2;
	I.s[0][1]=1;
	I.s[1][0]=p-4;
	I.s[1][2]=1;
	I.s[2][0]=1;
	/*
	For(i,1,n+1){
		dp[i]=cal(x[i]);
		For(j,1,i) dp[i]=(dp[i]-1ll*dp[j]*cal(x[i]-x[j])%p+p)%p;
	}
	*/
	For(i,1,n+1){
		dp[i]=((st*Pow(A,x[i])).s[0][0]-(st*sum*Pow(A,x[i])).s[0][0]+p)%p;
		sum=sum+dp[i]*Pow(I,x[i]);
	}
	printf("%d\n",dp[n]);
}

Measured memory_bytes: 1024
N = int(input())
W_list = list(map(int, input().split()))
diff = []
for i in range(1,N):
  S1 = sum(W_list[:i])
  S2 = sum(W_list[i:])
  if abs(S1-S2) == 0:
    print(0)
    exit()
  else:
    diff.append(abs(S1-S2))
print(min(diff))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <set>
#include <numeric>
#include <vector>

using namespace std;


int main()
{
	int n, k;
	cin >> n >> k;
	
	char s[51];
	cin >> s;

	s[k-1] = tolower(s[k-1]);

	cout << s << endl;

	return 0;
}

Measured memory_bytes: 256
func readArrayInt() -> [Int] {
    readLine()!.split(separator: " ").map({Int($0)!})
}

let line = readArrayInt()
let (A, B, C, K) = (line[0], line[1], line[2], line[3])

if K <= A {
    print(K)
} else if K <= A + B {
    print(A)
} else {
    print(A - (K - A - B))
}


Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int n,a[N];
ll pre[N],suf[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
	}
	for(int i=n;i;i--){
		suf[i]=suf[i+1]+a[i];
	}
	ll ans=2e9;
	for(int i=1;i<n;i++){
		ans=min(ans,abs(pre[i]-suf[i+1]));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 7524
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

vector<int> g[200005];
vector<long long> ans;
void dfs(int v, int p = -1) {
	for (auto next_v : g[v]) {
		if (next_v == p) continue;
		ans[next_v] += ans[v];
		dfs(next_v, v);
		
	}
}

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

	for (int i = 1;i < n;i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	ans.resize(n + 1);
	for (int i = 0;i < q;i++) {
		int p, x;
		cin >> p >> x;
		ans[p] += x;
	}

	dfs(1);
	

	for (int i = 1;i <= n;i++) {
		cout << ans[i] << endl;
	}

	return 0;
}


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

int N;
set<int> S;

int main(void) {
	S.clear();

	cin >> N;
	int a;
	for (int i = 0; i < N; ++i) {
		cin >> a;
		S.insert(a);
	}

	int k = S.size();
	if (k % 2 == 0)
		--k;

	cout << k << '\n';
	return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll k,n;
	cin>>k>>n;
	vector<ll>arr(n);
	for(int i=0; i<n; i++)
	 cin>>arr[i];
	sort(arr.begin(),arr.end());
	ll dimin=0;
	ll mx=0;
	for(int i=0; i<n-1; i++){
	 dimin+=arr[i+1]-arr[i];
	 mx=max(mx,arr[i+1]-arr[i]);
    }
    dimin+=k-arr[n-1]+arr[0];
    mx=max(mx,k-arr[n-1]+arr[0]);
    cout<<dimin-mx;
    return 0;
}

Measured memory_bytes: 4784
def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    if n==1:
        print(2*a[0]%mod)
        return
    a.sort(key=lambda x:-x)
    mod=10**9+7
    ans=0
    for i in range(n):
        ans=(ans+pow(2,n-2,mod)*a[i]*(i+2))%mod
    ans=ans*pow(2,n,mod)%mod
    print(ans)

main()

Measured memory_bytes: 102256
#include <iostream>
using namespace std;
const int M = 1000000007;
const int N_MAX = 100000;

int n, dp[N_MAX+1][26];
string s, t;

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

  dp[0][s[0]-'a'] = 1;

  for ( int i = 1; i < n; i++ ){
    dp[i][s[i]-'a'] = (dp[i][s[i]-'a'] + dp[i-1][t[i]-'a']) % M;
    for ( int j = 0; j < 26; j++ ) dp[i][j] = (dp[i][j] + dp[i-1][j]) % M;
  }

  cout << dp[n-2][t[n-1]-'a'] << endl;

  return 0;
}





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

int main() {
  string s;
  cin >> s;
  sort(s.begin(), s.end());
  string abc = "abc";
  if (s == abc) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main(){
 int n;
 cin >>n;
 vector<int> a(n),b(n);
 int ans =0;
 for(int i=0;i<n;i++){
   cin >> a.at(i) >> b.at(i);
   ans += b.at(i)-a.at(i)+1;
 }
 cout << ans << endl;
}


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

int main() {
	int a[101];
	for(int i = 0; i < 101; i ++) {
		a[i] = 0;
	}

	int x;
	int max = 0;
	while(cin >> x) {
		a[x]++;
		if(a[x] > max) {
			max = a[x];
		}
	}
	
	for(int i = 1; i < 101; i++) {
		if(a[i] == max) {
			cout << i << endl;
		} 
	}

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  string S; cin >> S;
  rep(i, S.length()) if (i==3) S[i]='8';
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

int main(void) {
    int N;
    cin >> N;
    vector<cpp_int> A(N);
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }

    if(count(A.begin(), A.end(), 0)) {
        cout << 0 << endl;
        return 0;
    }

    cpp_int ans = 1LL;
    for(int i=0; i<N; i++) {
        ans *= A[i];
        if(ans > 1'000'000'000'000'000'000LL) {            
            cout << -1 << endl;
            return 0;
        }
    }

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


Measured memory_bytes: 6484
#include<bits/stdc++.h>
using namespace std;
long long a[100002];
int main(){
	long long n,x,ans=0;
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2;i<=n;i++){
		if(a[i]+a[i-1]>x){
			ans+=(a[i-1]+a[i])-x;
			if(a[i-1]>x){
				a[i]=0;
				a[i-1]-=a[i-1]-x;
			}else{
				a[i]-=((a[i-1]+a[i])-x);
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1024