akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)
#define pb push_back

using namespace std;

const int N = 200010;

inline void chkmax(int& x, int y){
	x = x > y ? x : y;
}

inline void chkmin(int &x, int y){
	x = x < y ? x : y;
}

struct Info{
	int Mx, x;

	Info(){
		Mx = x = 0;
	}

	void update(int v){
		if(v > Mx) x = Mx, Mx = v;
		else if(v > x) x = v;
	}

	int query(int v){
		return v == Mx ? x : Mx;
	}
};

Info Maxd[N];
int dep[N], cnt[N];
vector<int> G[N];
char S[N];
int n;

int Maxv[N], high[N], low[N];

void DFS_init(int o, int f){
	cnt[o] = S[o] == '1';
	low[o] = n;
	for(int v : G[o]){
		if(v == f) continue;
		DFS_init(v, o);
		cnt[o] += cnt[v];
		Maxd[o].update(dep[v] + 1);
	}
	dep[o] = Maxd[o].Mx;
}

long long ans = 1;

void DFS_work(int o, int f){
	high[o] = min(Maxd[o].Mx - 1, Maxd[o].x + 1);
	chkmin(low[o], S[o] == '1' ? 0 : high[o] + 1);
	for(int v : G[o]){
		if(v == f) continue;
		int x = Maxd[o].query(dep[v] + 1), y = dep[v];
		if(cnt[1] - cnt[v]) chkmin(low[v], x + 1);
		if(cnt[v]) chkmin(low[o], y + 1);
		Maxd[v].update(x + 1);
		DFS_work(v, o);
	}
	ans += high[o] - low[o] + 1;
}

int main(){
	scanf("%d", &n);
	For(i, 2, n){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), G[v].pb(u);
	}
	scanf("%s", S + 1);
	DFS_init(1, 0);
	DFS_work(1, 0);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 25856
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main(int , char **)
{
	int A,B,C;
	cin >> A >> B >> C;
	for(int i=1;i<=B;i++){
		ll z = (A*i)%B - C;
		if (z==0){printf("YES\n");return 0;}
	}
	printf("NO\n");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

    int n, x , y;
    cin >> n >> x >> y;
    --x,--y;
    vi ans(n);
    rep(sv,n){
        vi dist(n,INF);
        queue<int> q;

        auto push = [&](int v, int d){
            if(dist[v] != INF) return;
            dist[v] = d;
            q.push(v);
        };
        push(sv, 0);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            int d = dist[v];
            if(v-1>=0) push(v-1,d+1);
            if(v+1< n) push(v+1,d+1);
            if(v == x) push(y,d+1);
            if(v == y) push(x,d+1);
        }
        rep(i,n) ans[dist[i]]++;
    }
    rep(i,n) ans[i] /= 2;
    rep1(i,n) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <string>
using namespace std;
const int maxn = 15 + 10;
int n,a[maxn][maxn],b[maxn][maxn],cnt[maxn],c[maxn],Ans;
inline void dfs(int now) {
	if (now == n+1) {
		bool flag = true;
		int ans = 0;
		for (int i = 1;i <= n;i++) {
			ans += c[i];
			for (int j = 1;j <= cnt[i];j++)
				if (c[i] == 1) if (b[i][j] != c[a[i][j]]) { flag = false; break; }
		}
		if (flag) Ans = max(Ans,ans);
		return;
	}
	c[now] = 1;
	dfs(now+1);
	c[now] = 0;
	dfs(now+1);
}
int main() {
	scanf("%d",&n);
	for (int i = 1;i <= n;i++) {
		scanf("%d",&cnt[i]);
		for (int j = 1;j <= cnt[i];j++)
			scanf("%d%d",&a[i][j],&b[i][j]);
	}
	dfs(1);
	printf("%d",Ans);
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
l = list(map(int,input().split(" ")))
N = l[0]
X = l[1]
T = l[2]

if N % X == 0:
  print(int(T * (N / X)))
else:
  print(int(T * (int(N / X) + 1)))
  

Measured memory_bytes: 9172
// By Shreehari Bodas

#include <bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;

int search(int b[], int m, int s){
	int start=0,end=m-1;
	bool flag=false;
	while(start<=end){
		int mid=(start+end)/2;
		if(b[mid]==s){
			flag=true;
			return mid;
		}
		else if(b[mid]>s) end=mid-1;
		else if(b[mid]<s) start=mid+1;
	}
	if(flag==false) return m;
}

long long int pow(long long int a, long long int b){
	if(b==0) return 1;
	long long int res=pow(a,b/2);
	if(b%2 ==1) return res*res*a;
	else if(b%2 ==0) return res*res;
}

int main(){

	long long int x; cin>>x;
	long long int a=100;

	long long int i=0;
	while(a<x){
		a=a*1.01;
		i++;
	}

	cout<<i<<endl;

	return 0;
} 

Measured memory_bytes: 3588
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

void a_k_city(void) {
	int n, m;
	cin >> n >> m;

	cout << (n - 1) * (m - 1) << endl;
}

int main()
{
    a_k_city();
    return 0;
}

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

using namespace std;

long long n;
set <long long> ans;

vector <long long> divisor(long long x)
{
    vector <long long> answer;
    answer.push_back(1);
    int limit = sqrt(x) + 1;
    for (int i = 2; i <= limit; ++i)

        if (x % i == 0)
        {
            int S = (int)answer.size();
            long long t = 1;
            while (x % i == 0)
            {
                t = t * i;
                x /= i;
                for (int j = 0; j < S; ++j)
                    answer.push_back(answer[j] * t);
            }
        }

    if (x > 1)
    {
        int S = (int)answer.size();
        for (int i = 0; i < S; ++i)
            answer.push_back(answer[i] * x);
    }
    return answer;
}

bool check(long long n, long long k)
{
    if (n % k == 0) return check(n / k, k);
    if (n % k == 1) return 1;
    return 0;
}

int main()
{
    cin >> n;
    vector <long long> v = divisor(n - 1);
    for (long long x : v)
        if (x > 1 && check(n, x)) ans.insert(x);

    v = divisor(n);
    for (long long x : v)
        if (x > 1 && check(n, x)) ans.insert(x);
    cout << (int)ans.size();
    return 0;
}


Measured memory_bytes: 384
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int ans = 0;
	sort(a.begin(), a.end());
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (a[i] == a[j]) continue;
			for (int k = j + 1; k < n; ++k) {
				if (a[j] == a[k]) continue;
				ans += a[i] + a[j] >  a[k];
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
N = int(input())
vs = list(map(int, input().split()))
vs0 = vs[0::2]
vs1 = vs[1::2]
M0 = {}
for v in vs0:
  if not(v in M0):
    M0[v] = 0
  M0[v] += 1
M1 = {}
for v in vs1:
  if not(v in M1):
    M1[v] = 0
  M1[v] += 1
L0 = []
for v in M0:
  n = M0[v]
  L0.append((n, v))
L0.sort(reverse=True)
L0.append((0, -1))
L1 = []
for v in M1:
  n = M1[v]
  L1.append((n, v))
L1.sort(reverse=True)
L1.append((0, -1))
#print(L0)
#print(L1)
if L0[0][1] == L1[0][1]:
  r = min(N-L0[1][0]-L1[0][0], N-L0[0][0]-L1[1][0])
else:
  r = N-L0[0][0]-L1[0][0]
print(r)


Measured memory_bytes: 20988
#include <stdio.h>

int main()
{
	int i, max;
	int a, b;
	int c[3];

	scanf("%d%d", &a, &b);
	c[0] = a + b;
	c[1] = a - b;
	c[2] = a * b;

	for (i = 1, max = c[0]; i < 3; i++) {
		if (c[i] > max) {
			max = c[i];
		}
	}

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

	return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;
	std::vector<LL>p(N);
	rep(i, N) in >> p[i];

	LL sum = 0, maxN = 0;
	rep(i, N)
	{
		sum += p[i];
		maxN = std::max(maxN, p[i]);
	}

	out << sum - maxN / 2 << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
main(){
  int a,b,sum=0;
  int n;
  cin>>n;
  cin>>a>>b;
  r(i,n-1){
    int c,d;
    cin>>c>>d;
    int x=max(a/c,b/d);
    if(!x)x++;
    c=c*x;
    d=d*x;
    if(a>c||b>d){
      c=c/x;
      d=d/x;
      x++;
      c=c*x;
      d=d*x;
    }
    a=c;
    b=d;
  }
  cout<<a+b<<endl;
}

Measured memory_bytes: 256
a, b , h, m = map(int,input().split())

h = h * 60 + m

h_angle = h / 2
m_angle = m * 6
C = abs(h_angle - m_angle)
if C > 180 :
  C = 360 - C

import math
x = a**2 + b**2 - 2*a*b*math.cos(math.radians(C))
print(x**(1/2))

Measured memory_bytes: 9596
#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int sum = max(a, b);
    if (max(a, b) - min(a, b) >= 2) {
        sum += max(a,b) - 1;
    }
    else {
        sum += min(a,b);
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int w,h,x,y,r;
scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);
if(x-r<0||x+r>w||y-r<0||y+r>h)printf("No\n");
else printf("Yes\n");
return 0;
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

signed main() {
  int n,d;cin>>n>>d;
  vector<int> v[10];
  rep(i,n){
    v[i].resize(d);
    rep(j,d)cin>>v[i][j];
  }
  int ans = 0;
  rep(i,n){
    repd(j,i+1,n){
      double dd = 0;
      rep(k,d){
        dd += double((v[i][k] - v[j][k]) * (v[i][k] - v[j][k]));
      }
      dd = sqrt(dd);
      if(floor(dd) == dd)ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000],h[1000000];
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);   
    long long a,b,n,m,i,j,k;
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
    	cin>>h[i];
	}
	for (i=0;i<m;i++)
	{
		cin>>a>>b;
		if (h[a]>=h[b] && arr[b]!=-1)
		{
			arr[b]=-1;
		}
		if (h[a]<=h[b] && arr[a]!=-1)
		{
			arr[a]=-1;
		}		
	}
	k=0;
	for (i=1;i<=n;i++)
	{
		if (arr[i]!=-1)
		{
			k++;
		}
	}
	cout<<k<<endl;
}

Measured memory_bytes: 5180
def main():
    A, B, C, X, Y = map(int, input().split())
    if 2 * C < A + B:
        print(min(
            2 * C * max(X, Y),
            2 * C * min(X, Y) + A * (X - min(X, Y)) + B * (Y - min(X, Y))
        ))
    else:
        print(A * X + B * Y)
    return


main()


Measured memory_bytes: 3060
#include <stdio.h>

int main()
{
    int a, b;
    
    scanf("%d %d", &a, &b);
    
    if (a + b == 0) {
        printf("0\n");
    } else if (a + b < 0) {
        printf("-1\n");
    } else if (a + b > 0) {
        printf("1\n");
    }
    
    return 0;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

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

	int64 n, m;
	vector<int64> r1, r2;
	cin >> n >> m;
	map<int64, int64> mp;
	REP(i, n) {
		int64 a;
		cin >> a;
		mp[a]++;
	}
	REP(i, m) {
		int64 a;
		cin >> a;
		if (mp[a]) r1.push_back(a);
	}
	for (auto x : mp) {
		r2.push_back(x.fs);
	}
	cout << r1.size() << " " << r2.size() << endl;
	REP(i, r1.size()) cout << r1[i] << endl;
	REP(i, r2.size()) cout << r2[i] << endl;
}



Measured memory_bytes: 18608
#include <iostream>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;

int main(){
    int x,y;	cin >> x >> y;
    int g[3] = {0};
    switch(x){
	case 1:
	    g[0]++; 
	break;
	case 2:
	    g[2]++; 
	break;
	case 3:
	    g[0]++; 
	break;
	case 4:
	    g[1]++; 
	break;
	case 5:
	    g[0]++; 
	break;
	case 6:
	    g[1]++; 
	break;
	case 7:
	    g[0]++; 
	break;
	case 8:
	    g[0]++; 
	break;
	case 9:
	    g[1]++; 
	break;
	case 10:
	    g[0]++; 
	break;
	case 11:
	    g[1]++; 
	break;
	case 12:
	    g[0]++; 
	break;
    }
    switch(y){
	case 1:
	    g[0]++; 
	break;
	case 2:
	    g[2]++; 
	break;
	case 3:
	    g[0]++; 
	break;
	case 4:
	    g[1]++; 
	break;
	case 5:
	    g[0]++; 
	break;
	case 6:
	    g[1]++; 
	break;
	case 7:
	    g[0]++; 
	break;
	case 8:
	    g[0]++; 
	break;
	case 9:
	    g[1]++; 
	break;
	case 10:
	    g[0]++; 
	break;
	case 11:
	    g[1]++; 
	break;
	case 12:
	    g[0]++; 
	break;
    }
    if(g[0] == 2 || g[1] == 2 || g[2] == 2){
	cout << "Yes" << endl;
    }else{
	cout << "No" << endl;
    }
}


Measured memory_bytes: 256
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = Console.ReadLine().Split(' ');
            int N = int.Parse(array[0]);
            int M = int.Parse(array[1]);
            if (N == M)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

ll n,m,d[110][110],a[1001],b[1001],c[1001],ans;

int main(void){
	cin>>n>>m;
	reg(i,1,n)reg(j,1,n)d[i][j]=1e18;
	reg(i,1,n)d[i][i]=0;
	rep(i,m){
		cin>>a[i]>>b[i]>>c[i];
		d[a[i]][b[i]]=min(c[i],d[a[i]][b[i]]);
		d[b[i]][a[i]]=min(c[i],d[b[i]][a[i]]);
	}
	reg(k,1,n){
		reg(i,1,n){
			reg(j,1,n){
				d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	ans=m;
	rep(i,m){
		if(c[i] == d[a[i]][b[i]])ans--;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#define GROUP_1_MAX 7

typedef struct {
	int iNum;						//番号
	int aiGroup[GROUP_1_MAX];       //整数のグループ

}GROUP_t;

static int judge(int aXY, const GROUP_t* pstGroup);

int main(void) {
	int x, y;
	int GroupNoX, GroupNoY;
	int n;
	int YesNo = 0;

	//x,yを入力
	scanf("%d %d", &x, &y);

	//構造体変数の定義 (空きには-1が入っている)
	const GROUP_t m_Group[3] = {
		{0,{1, 3, 5, 7, 8,10,12}},
		{1,{4, 6, 9,11,-1,-1,-1}},
		{2,{2,-1,-1,-1,-1,-1,-1}}
	};

	//x yの属するグループの比較を行う	
	for (n = 0;n < 3;n++) {
		GroupNoX = judge(x, &m_Group[n]);
		GroupNoY = judge(y, &m_Group[n]);

		if ((GroupNoX == GroupNoY) && (GroupNoX != -1) && (GroupNoY != -1)) {
			YesNo = 1;
			break;
		}
		else {}
	}
	//同じグループに属していた場合Yesを表示
	if (YesNo == 1) {
		printf("Yes\n");
	}//異なるグループに所属していた場合Noを表示
	else if (YesNo == 0) {
		printf("No\n");
	}
	else {}

	return 0;
}
/******
*x,yの値がどの整数のグループに属するかを調べる関数
*[in]aXY			入力値であるxまたはyを入れる
*[in]* pstGroup		x,yと比較したい整数のグループの所属する構造体を入れる
*
*/
int judge(int aXY, const GROUP_t* pstGroup) {
	int i = 0;
	int groupno = -1;
	/*グループ内の数と比較して一致するものがあればグループに割り当てた番号を返す
	そうでないときは一致無し(-1)を返す*/
	for (i = 0; i < GROUP_1_MAX; i++) {
		if (aXY == pstGroup->aiGroup[i]) {
			groupno = pstGroup->iNum;
			break;
		}
		else if (pstGroup->aiGroup[i] == -1)
		{
			break;
		}
		else {
			;
		}
	}
	return(groupno);
}

Measured memory_bytes: 2072
#include<bits/stdc++.h>
#define sf1(n) scanf("%d",&n)
#define sf2(n,q) scanf("%d %d",&n,&q)
#define f first
#define ss second
#define pb push_back
#define lli long long
#define mem(ar,false) memset(ar,false,sizeof(ar))
#define mpr make_pair
#define endl "\n"
#define mod 1000000007
#define inf 9000000000000000000LL
using namespace std;

int ar[200005][5];
int n,k;
int dp[100005][5];
int func(int i,int j)
{

    if(i==n+1)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    int ret = INT_MIN;

    for(int k=1;k<=3;k++)
    {
        if(k==j)
            continue;
       ret = max(ret,ar[i][k]+func(i+1,k));
    }
    return dp[i][j] = ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    mem(dp,-1);
    cin >> n ;
    for(int i=1; i<=n; i++)
        cin >> ar[i][1] >> ar[i][2] >> ar[i][3];

     int ans = func(1,0);
   /* for(int i=1; i<n; i++)
    {
        int ret = INT_MAX;
        for(int j=1;j<=k;j++)
        {
            if(i-j>=0)
                ret = min(ret,dp[i-j]+abs(ar[i]-ar[i-j]));
        }
        dp[i] = ret;
    }*/

    cout << ans << endl;
    return 0;

}


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

const int INF = 1e9+7;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	vector<int> c(n);
	rep(i, n) cin >> v.at(i);
	rep(i, n) cin >> c.at(i);

	int ans = 0;
	rep(i, n){
		int get = v.at(i)-c.at(i);
		if(get>0) ans += get;
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
#include<iostream>

int main(){
int a[4],b[4],i,j,H,B;
	while(std::cin>>a[0]){
		for(i=1;i<4;i++){
			std::cin>>a[i];
		}
		for(j=0;j<4;j++){
			std::cin>>b[j];
		}
		H=0;
		B=0;
		for(i=0;i<4;i++){
			for(j=0;j<4;j++){
				if(a[i]==b[j]){
					if(i==j){
						H++;
					}
					else{
						B++;
					}
				}
			}
		}
		std::cout<< H << " " << B <<std::endl;
	}
return 0;
}

Measured memory_bytes: 1156
function pint(s)   { return parseInt(s);   }
function pfloat(s) { return parseFloat(s); }
Array.prototype.sortNumAsc  = function ()  { return this.sort((a, b) => (a - b)); }
Array.prototype.sortNumDesc = function ()  { return this.sort((a, b) => (b - a)); }
Array.prototype.sortStrAsc  = function ()  { return this.sort();                  }
Array.prototype.sortStrDesc = function ()  { return this.sort().reverse();        }
Array.prototype.without     = function (x) { return this.filter(e => e !== x);    }
function main(lines) {
  var arr = lines[0].split(' ').map(pint);
  var N = arr[0];
  var W = arr[1];
  lines = lines.slice(1).map(l => l.split(' ').map(pint));
  var ttbl = { 0: 0 };
  for (var i = 0; i < N; i++) {
    var w = lines[i][0];
    var v = lines[i][1];
    var tbl = {};
    for (var k in ttbl) {
      var tw = pint(k);
      var tv = ttbl[k];
      if (!(tbl[k] && tv < tbl[k])) tbl[k] = tv;
      if ((tw + w <= W) && (!(tbl[tw+w] && (tv + v) < tbl[tw+w])))
        tbl[tw+w] = tv + v;
    }
    ttbl = tbl;
  }
  var ans = 0;
  for (var n in ttbl)
    ans = Math.max(ans, ttbl[n]);
  console.log(ans);
}
main(require("fs").readFileSync("/dev/stdin", "utf8").split('\n').map(l => l.trim()));

Measured memory_bytes: 20936
import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l)):
    for j in range(i + 1, len(l)):
        ans += max(bisect.bisect_left(l, l[i] + l[j])-j-1, 0)
print(ans)

Measured memory_bytes: 3316
N,M = map(int,input().split())
Alist = list(map(int, input().strip().split()))
r = [0]*N
r[0] = Alist[0]
for i in range(1,len(Alist)):
    r[i] = r[i-1] + Alist[i]
for i in range(len(r)):
    r[i] = r[i]%M
r.sort()
p = []
m = 0
for i in range(len(r)-1):
    m = m+1
    if r[i] != r[i+1]:
        p.append(m)
        m = 0
    if i == len(r)-2:
        p.append(m+1)
x = 0
for i  in range(len(r)):
    if r[i] == 0:
        x = x +1
def combi(n):
    if n == 0:
        return 0
    if n == 1:
        return 0
    else:
        return (n*(n-1))/2
s = 0
for i in range(len(p)):
    s = s + combi(p[i])
s = s + x
print(int(s))

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

int main() {
  string S;
  cin >> S;
  int len = S.size();
  int64_t sum = 0;
  
  for (int tmp = 0; tmp < (1 << (len-1)); tmp++) {
    bitset<20> s(tmp);
    string num_str = ""s + S.at(len-1);
    
    for (int i=0; i<len-1; i++){
      if (s.test(i)) {
        sum += stoll(num_str);
        num_str = ""s + S.at(len-2-i);
      }
      else {
        num_str = S.at(len-2-i) + num_str;
      }
    }
    sum += stoll(num_str);
    
  }
  
  cout << sum << endl; 
  
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, a, b = LI()
    print(min(n*a,b))
    return

#B
def B():
    a = S()
    print(a.count("1"))
    return

#C
def C():
    n = II()
    a = list(str(n))
    if not n % sum(a):
        print("Yes")
    else:
        print("No")
    return

#D
def D():
    n = II()
    a = LI()
    ans = 0
    for a_ in a:
        while not a_ % 2:
            ans += 1
            a_ /= 2
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()


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

int main(void) {
  int N; cin >> N;
  vector<int> b(N); for (int i = 0; i < N; i++) cin >> b.at(i);

  char flag = 1;
  for (int i = 1; i <= N; i++) {
    if (i < b.at(i-1)) {
      flag = 0;
      break;
    }
  }

  if (flag) {
    vector<int> ans;
    while (!b.empty()) {
      for (int i = b.size(); 1 <= i; i--) {
        if (b.at(i-1) == i) {
          ans.push_back(i);
          b.erase(b.begin()+i-1);
          break;
        }
      }
    }

    for (int i = N-1; 0 <= i; i--) {
      cout << ans.at(i) << endl;
    }
  } else cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
 
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

int main(){
    string S;
    cin >> S;
    ll N = S.size();
    vector<vector<mint>> dp(N+1,vector<mint>(13));
    dp[0][0] = 1;
    rep(i,N){
        if(S[i] != '?'){
            ll c = S[i] - '0';
            rep(j,13){
                dp[i+1][(j*10+c)%13] += dp[i][j];
            }
        }else{
            rep(c,10){
                rep(j,13){
                    dp[i+1][(j*10+c)%13] += dp[i][j];
                }
            }
        }
    }
    cout << dp[N][5] << endl;
}

Measured memory_bytes: 16672
using System;

class Practice
{
    public static void Main()
    {
        while (true)
        {
            string[] str = Console.ReadLine().Split(' ');
            int h = int.Parse(str[0]);
            int w = int.Parse(str[1]);
            if (h == 0 && w == 0) break;
            for (int i = 0; i < h; ++i)
            {
                for (int j = 0; j < w; ++j)
                {
                    Console.Write(i != 0 && i != h - 1 && j != 0 && j != w - 1 ? '.' : '#');
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
}


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

#define mp       make_pair
#define mt	 make_tuple
#define pb       push_back
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    pair<int,int>      pii;
typedef    pair<long,long>    pll;

const int INF=1<<29;
const double EPS=1e-9;
const int MOD = 100000007;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int x,y,s;
int main(){
  while (cin >> x >> y >> s){
    if (x == 0 && y == 0 && s == 0)break;
    int ans = 0;
    for (int i = 1; i < 1000; i++){
      for (int j = 1; j < 1000; j++){
	int px = i * (100 + x) / 100;
	int py = j * (100 + x) / 100;
	if (px + py == s){
	
	  int ppx = i * (100 + y) / 100;
	  int ppy = j * (100 + y) / 100;
	  ans = max(ans, ppx + ppy);
	}
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1160
//g++ -std=c++14 test.cpp -o test.out
//問題URL
//https://atcoder.jp/contests/arc098/tasks/arc098_c

//ポイント：
//Yを決めうちした上でループを回す
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N,K,Q;
LL A[2000];

LL ans = INF;

void solve(){
    //A[i]=Yと決め打ちする
    for(int i=0;i<N;i++){
        LL Y = A[i];
        typedef priority_queue<LL,vector<LL>,greater<LL>> pri_queue;
        vector<pri_queue> part;
        part.push_back(pri_queue());
        for(int j=0;j<N;j++){
            if(A[j]<Y){
                part.push_back(pri_queue());
                continue;
            }
            part[part.size()-1].push(A[j]);
        }

        vector<LL> cand;
        for(int j=0;j<part.size();j++){
            while(part[j].size()>=K){
                cand.push_back(part[j].top());
                part[j].pop();
            }
        }
        sort(cand.begin(),cand.end());
        if(cand.size()<Q) continue;
        LL X = cand[Q-1];
        ans = min(ans,X-Y);
    }
}
 
int main(){
	cin >> N >> K >> Q;
    for(int i=0;i<N;i++) cin >> A[i];
 
    solve();

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

Measured memory_bytes: 3380
#include "bits/stdc++.h"
using namespace std;

//諸機能
#pragma region MACRO 
#define putans(x)  std::cerr << "answer: " ; cout << (x) << endl
#define dputans(x) std::cerr << "answer: "; cout << setprecision(10) << (double)(x) << endl
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define RREP(i,a,n) for(int i=(int)(n-1); i>= a; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) begin((a)),end((a))
#define mp make_pair
#define exist(container, n) ((container).find((n)) != (container).end())
#define substr(s,i,l) string((s), (i), (l))
#define tos(x) (to_string((x)))
#ifdef _DEBUG //ファイルからテストデータを読み込む
std::ifstream ifs("data.txt");
#define put ifs >>
#else //いい感じにやる
#define put cin >>
#endif
#pragma endregion
//デバッグなどの支援
#pragma region CODING_SUPPORT
#define dbg(var0) { std::cerr << ( #var0 ) << "=" << ( var0 ) << endl; }
#define dbg2(var0, var1) { std::cerr << ( #var0 ) << "=" << ( var0 ) << ", "; dbg(var1); }
#define dbg3(var0, var1, var2) { std::cerr << ( #var0 ) << "=" << ( var0 ) << ", "; dbg2(var1, var2); }
#define dbgArray(a,n) {std::cerr << (#a) << "=";  rep(i,n){std::cerr <<(a[i])<<",";} cerr<<endl;} 
#ifndef _DEBUG
#define dbg1 {}
#define dbg2 {}
#define dbg3 {}
#define dbgArray {}
#endif 
#pragma endregion 
//typedef（書き換える、書き足す可能性ある）
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii; typedef pair<string, string> pss; typedef pair<int, string>pis;
typedef vector<string> vs; typedef vector<int> vi;
#pragma endregion
//諸々の定数(書き換える可能性ある)
#pragma region CONST_VAL
#define PI (2*acos(0.0))
#define EPS (1e-9)
#define MOD (ll)(1e9 + 7)
#define INF (ll)(1e9)
#pragma endregion


int main() {
	string s; put s;
	string s1, s2;
	s1 = substr(s, 0, 4);
	s2 = substr(s, 4, 8);
END:
	putans(s1 + " "  + s2);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main(void){
	string x,y,z;
	cin >> x >> y;

	z = x + x;
	if(z.find(y) != -1
		){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 3184
from math import sqrt


def dfs(remains, elapsed, hx, hy, prev):
    global crystals, dc

    if not remains:
        return True

    remains_c = set()
    for i in remains:
        cx, cy, dfd = crystals[i]
        new_elapsed = elapsed + dc[prev][i]
        if dfd <= new_elapsed:
            return False
        remains_c.add((i, cx, cy, new_elapsed))

    for i, cx, cy, new_elapsed in remains_c:
        remains.remove(i)
        if dfs(remains, new_elapsed, cx, cy, i):
            return True
        remains.add(i)

    return False


while True:
    n, hx, hy, dx, dy = map(int, input().split())
    if n == 0: break

    crystals_in = [tuple(map(int, input().split())) for _ in range(n)]
    crystals = [(cx, cy, sqrt((cx - dx) ** 2 + (cy - dy) ** 2)) for cx, cy in crystals_in]
    crystals_in += [(hx, hy)]
    dc = [[sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) for x2, y2 in crystals_in] for x1, y1 in crystals_in]

    print('YES' if dfs(set(range(n)), 0, hx, hy, n) else 'NO')

Measured memory_bytes: 7844
#include <stdio.h>
#include <string.h>

#define N 100

int main(){
  char str[10] = {""};
  int stac[N];
  int top = 0, num1, num2, i, j;
  
  i = 0;
  while((str[i] = getchar())!= EOF){
    if(str[i] != ' '){
      i++;
    }
    else{
      i = 0;
      num1 = atoi(str);
      if(num1 != 0){
	top++;
	stac[top] = num1;
      }
      else{
	
	if(str[0] == '+'){
	  //printf("calc +\n");
	  stac[top-1] = stac[top-1] + stac[top];
	  top--;
	}
	if(str[0] == '-'){
	  //printf("calc -\n");
	  stac[top-1] = stac[top-1] - stac[top];
	  top--;
	}
	if(str[0] == '*'){
	  //printf("calc *\n");
	  stac[top-1] = stac[top-1] * stac[top];
	  top--;
	}
      }
      
      strcpy(str ,"");
      /*
      for(j = 1; j < top+1; j++){
	printf("%d ", stac[j]);
	}
      */
    }
  }
  
  if(str[0] == '+'){
    //printf("calc +\n");
    stac[top-1] = stac[top-1] + stac[top];
    top--;
  }
  if(str[0] == '-'){
    //printf("calc -\n");
    stac[top-1] = stac[top-1] - stac[top];
    top--;
  }
  if(str[0] == '*'){
    //printf("calc *\n");
    stac[top-1] = stac[top-1] * stac[top];
    top--;
  }

    printf("%d\n", stac[top]);
    
  return 0;
}



Measured memory_bytes: 2128
import java.util.*;
import java.lang.*;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int count1 = 0;
		int count2 = 0;
		int count3 = 0;
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			if (tmp <= a) {
				count1++;
			} else if (tmp <= b) {
				count2++;
			} else {
				count3++;
			}
		}
		System.out.println(Math.min(count1, Math.min(count2, count3)));
	}
}

Measured memory_bytes: 23124
#define _CRT_SECURE_NO_DEPRECATE
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds; 
using namespace std;
#define int long long int
#define SYNC std::ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii>   vii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, 
//             tree_order_statistics_node_update> 
//    data_set;
#define rep(i,l,r)   for(int i=(l);i<(r);i++)
#define deb(x)     cout << (#x) << " is " << (x) << endl
#define dbg(x)     cout << x << ' '
#define here cout << " Hey baitch!!\n";
#define  pb push_back
#define  F  first
#define  S  second
#define all(v) (v).begin(),(v).end()
#define sz(a) (int)((a).size())
#define sq(x) ((x)*(x))
const int MOD = 1e9+7;
const int MOD1 = 998244353;
const int N = 2e5+5;
const int INF = 1000111000111000111LL;
const ld PI = 3.1415926535898;
vi g[N];
int dp[N][2];
vi vis;
void solve(int node) 
{
	vis[node] = 1;
	dp[node][0] = 1;
	dp[node][1] = 1;
	for(auto to : g[node]) {
		if(!vis[to]) {
			vis[to] = 1;
			solve(to);
			dp[node][0] *= (dp[to][0] + dp[to][1]);
			dp[node][0] %= MOD;
			dp[node][1] *= (dp[to][0]);
			dp[node][1] %= MOD;
		}
	}
	dp[node][0] %= MOD;
	dp[node][1] %= MOD;
}
int32_t main()
{
	SYNC
	int n;
	cin >> n;
	memset(dp,0,sizeof dp);
	vis.resize(N,0);
	rep(i,0,n-1) {
		int u,v; cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	solve(1);
	// for(int i = 1; i <= n; i++) {
	// 	cout << dp[i][0] << ' ' << dp[i][1] << endl;
	// }
	cout << (dp[1][0] + dp[1][1]) % MOD;
    return 0;
}

Measured memory_bytes: 15872
from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
X=deque()
Y=deque()
V=[[0]*(w+2) for i in range(h+2)]
V[0]=[0]*(w+2)
for i in range(1,h+1):
  V[i]=[0]+[10**7]*w+[0]
V[h+1]=[0]*(w+2)
for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i][j]=="#":
      X.append(i)
      Y.append(j)
      V[i][j]=0
XX=[-1,0,0,1]
YY=[0,-1,1,0]
while len(X)!=0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  for i in range(4):
    if V[x+XX[i]][y+YY[i]]==10**7:
      V[x+XX[i]][y+YY[i]]=V[x][y]+1
      X.append(x+XX[i])
      Y.append(y+YY[i])
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]>ans:
      ans=V[i][j]
print(ans)

Measured memory_bytes: 140892
N = int(input())

if N % 2 == 1:  # 奇数なら0
    print(0)
else:
    ans = 0
    pow50 = 50
    while pow50 <= N:
        ans += N//pow50
        pow50 *= 5
    gozyu_baisuu = N//50
    zyuu_baisuu = N//10
    # gohyaku_baisuu = N //200
    print(ans + zyuu_baisuu)
# 1000000000000000000
# 124999999999999995

# 120000000000000000


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  deque<int> b;
  for(int i = 0; i < n; i++){
    if(i%2 == 0)b.push_back(a.at(i));
    else b.push_front(a.at(i));
  }
  if(n%2 == 1){
    reverse(b.begin(),b.end());
  }
  int size = b.size();
  for(int i = 0; i < size - 1; i++){
    cout << b.at(i) << " ";
  }
  cout << b.at(size-1) << endl;
}

Measured memory_bytes: 4724
unittest
{
	assert( [ "2 1 1 3" ].parse.expand.solve == 2 );
	assert( [ "1 2 3 4" ].parse.expand.solve == 0 );
	assert( [ "2000000000 0 0 2000000000" ].parse.expand.solve == 2000000000 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto abck = input.front.split.to!( long[] );
	return tuple( abck[ 0 ], abck[ 1 ], abck[ 2 ], abck[ 3 ] );
}

auto solve( long a, long b, long c, long k )
{
	if(      k <= a     ) return k;
	else if( k <= a + b ) return a;
	else                  return a - ( k - a - b );
}


Measured memory_bytes: 2780
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <cctype>

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i,l,n) for(int (i)=(int)(l);(i)<(int)(n);(i)++)
#define d_arr(arr, h, w) rep(i,(h) ){ cout << "["; rep(j,(w) ) { cout << (arr)[i][j] << ", "; } cout << "]" << endl;}
#define IN(x,s,g) ((x) >= (s) && (x) < (g))
#define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h)))
#define print(x) printf("%d\n",x);
#define pb push_back
#define priv(v) rep(i,v.size()){ cout << v << ", "; } puts("");

typedef pair<int ,int> P;

void vpri(vector<int> v){
    rep(i,v.size()){
        cout<<v[i]<<",";
    }
    puts("fin");
}
int main()
{
    while( true ){
        int x,y,z;
        cin >> x >> y >>z;
        if ( x==0 && y==0 && z==0 ){ break; }
        vector<int> jump;
        jump.clear();
        int tmp;
        rep(i,x){ cin >> tmp; jump.pb(tmp); }
        vector<int> n,e,a;
        n.clear(); e.clear(); a.clear();
        n.resize(y+1,0);e.resize(y+1,0);a.resize(y+1,0);
        double dp[51][5001];
        rep(i,51) rep(j,5001) dp[i][j] = 0.0;


        rep(i,z){
            int n;
            int t_e,t_a;
            cin >> n;
            cin >> t_e;
            e[n] = t_e;
            cin >> t_a;
            a[n] = t_a;
        }
        
        //cout << "input finish" << endl;
        //cout<< "e:"<<endl;
        //vpri(e);
        //cout<< "a:"<<endl;
        //vpri(a);

        //配るDPなので配った先でお金は計算する:
        dp[0][0] = 1.0;
        rep(i,y){
            rep(j,5001){
                if (dp[i][j] == 0.0 ) continue;
                //cout << "start distributing from dp: " << i<<","<<j <<" pro: "<<dp[i][j]<<endl;
                rep(k,x){
                    //k is index of jump
                    int skip,gain,money;
                    int next=min(i+jump[k],y);
                    money = j;
                    if(e[next] == 1) { 
                        //cout<<"Jump!"<<endl;
                        next = min( y, next+a[next] );
                    } else {
                        gain=0;
                        if(e[next] == 2)      { gain =  a[next]; }
                        else if(e[next] == 3) { gain = -a[next]; }
                        money = max(0,j+gain);
                    }
                    //cout << "to dp: " << next<<","<<money<<" add pro:"<<1.0/double(x)<<endl;
                    dp[next][money] += dp[i][j] / double(x); 
                }
            }
        }
        double ev=0.0;
        rep(j,5001){ ev += double(j) * dp[y][j]; }
        cout << int(ev) << endl;
    }
}

Measured memory_bytes: 3208
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
const double EPS = 1e-9;

void init() {
}

char strbuf[100];
vector<string> S;
void solve(int n) {
    S.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%s", strbuf);
        S[i] = strbuf;
    }
    for (int i = 0; i < n; i++) {
        int dot = 0;
        while (dot < S[i].length() && S[i][dot] == '.') ++dot;
        if (dot) {
            if (dot > 1) S[i] = string(dot - 1, ' ') + "+" + S[i].substr(dot);
            else S[i] = "+" + S[i].substr(dot);
        }
    }
    //for (string s : S) cout<<s<<endl;cout<<endl;
    for (int i = 0; i < n; i++) {
        int plus = 0;
        while (plus < S[i].length() && S[i][plus] != '+') ++plus;
        if (plus == S[i].length()) continue;
        for (int j = i - 1; j >= 0; j--) {
            if (S[j][plus] != ' ') {
                break;
            }
            S[j][plus] = '|';
        }
    }
    for (string s : S) {
        printf("%s\n", s.c_str());
    }
    S.clear();
}

signed main(void) {
    LL n, m, p, a, b, c, x, y, z, q;
    string s;
    bool f = false;
    init();
    while (cin >> n, n) {
        solve(n);
    }
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; cin >> N;
    int A[N]; ll S = 0; FOR(i,0,N-1) { cin >> A[i]; S += A[i]; }

    ll T = (ll)N*(N+1)/2;
    if (S % T != 0) { cout << "NO"; return 0; }
    S /= T;
    ll X = 0;
    FOR(i,0,N-1) {
        ll y = A[(i+1)%N]-A[i] - S;
        if (y > 0 || y%N != 0) { cout << "NO"; return 0; }
        y /= -N;
        X += y;
    }
    cout << (X == S ? "YES" : "NO");
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
int main()
{
    int n, d, x;
    cin >> n >> d >> x;
    int a[100];
    rep(i, n){
        cin >> a[i];
    }

    int ans = x;
    int count;
    int tmp;
    rep(i, n){
        count = 1;
        tmp = a[i] + 1;
        while(tmp <= d){
            tmp += a[i];
            count++;
        }
        ans += count;
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string exchange(string a)
{
    reverse(begin(a),end(a));
    return a;
}
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    string t1=exchange(s);
    string s2=s.substr(0,(n-1)/2);
    string t2=exchange(s2);
    string s3=s.substr((n+1)/2);
    string t3=exchange(s3);
    if(s==t1&&s2==t2&&s3==t3)cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int main() {
    int N,A,B,C,D;
    char S[200001];
    cin >> N >>A >>B >> C >>D;
    A--;B--;C--;D--;
    cin >> S;

    int i=B;
    while (i < D) {
        if (i+2 <= D && S[i+2] == '.') {
            i = i+2;
        } else if (i+1 <= D && S[i+1] == '.') {
            i = i+1;
        } else {
            cout << "No"<< endl;
            return 0;
        }
    }
    i = A;
    while (i < C) {
        if (i+2 <= C && S[i+2] == '.') {
            i += 2;
        } else if (i+1 <= C && S[i+1] == '.') {
            i++;
        } else {
            cout << "No" << endl;
            return 0;
        }
    }
    if (C < D) {
        cout << "Yes" << endl;
    } else {
        // A < B < D < C
        // oikoshi
        i = B;
        int found = 0;
        while (i < D) {
            if (S[i-1] == '.' && S[i+1] == '.') found = 1;
            if (i+1 <= D && S[i+1] == '.') i++;
            else i += 2;
        }
        if (S[D-1] == '.' && S[D+1] == '.') found = 1;
        if (found == 1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
        
    return 0;
}



Measured memory_bytes: 384
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

int N,K;
int A[110];
int DP[2][100010];

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

	cin>>N>>K;
	rep(i,0,N)
	{
		cin>>A[i];
	}

	DP[0][0]=1,DP[0][1]=(-1+MOD)%MOD;

	int tar=1;
	rep(i,0,N)
	{
		fill(DP[tar],DP[tar]+100010,0);
		rep(j,0,K+1)
		{
			if(j>0)DP[tar^1][j]=(DP[tar^1][j]+DP[tar^1][j-1]+MOD)%MOD;
			int l=j,r=min(j+A[i]+1,100005LL);
			DP[tar][l]=(DP[tar][l]+DP[tar^1][j])%MOD;
			DP[tar][r]=(DP[tar][r]-DP[tar^1][j]+MOD)%MOD;
		}
		tar^=1;
	}
	tar^=1;

	rep(i,0,K+1)
	{
		if(i>0)DP[tar][i]=(DP[tar][i]+DP[tar][i-1]+MOD)%MOD;
	}

	cout<<DP[tar][K]<<endl;

	return 0;
}

Measured memory_bytes: 1792