akhauriyash/Code-Regression huggingface dataset:
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
#include<set>
using namespace std;
#define INF 1100000000000000000
#define MAX 110000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,bool> P;
//typedef pair< pair<int,int>,pair<int,int> > p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

int par[420000],es[420000]; //親

// n要素を初期化
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=-1;
  }
}

//木の根を求める
int find(int x){
  if(par[x]<0){
    return x;
  }else{
    return par[x]=find(par[x]);
  }
}

int usize(int x){
  return -par[find(x)];
}

int esize(int x){
    return es[find(x)];
}


//xとyの属する集合を併合
void unite(int x,int y){
  x=find(x);
  y=find(y);
  es[x]++;
  if(x==y) return;

  if(usize(x)<usize(y)) swap(x,y);
  par[x]+=par[y];
  es[x]+=es[y];
  par[y]=x;
}


//xとyが同じ集合に属するか否か
bool same(int x,int y){
  return find(x)==find(y);
}

vector<int> V[110000];

int main(){
    int N,M;
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int K; cin>>K;
        for(int j=0;j<K;j++){
            int l; cin>>l;
            V[l].push_back(i);
        }
    }
    init(N);
    for(int i=1;i<=M;i++){
        for(int j=0;j<(int)V[i].size()-1;j++){
            unite(V[i][j],V[i][j+1]);
        }
    }
    if(usize(0)==N) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 6272
tailrec fun gcd(a: Int, b: Int = 0): Int = if(b == 0) { a } else { gcd(b, a % b) }
fun main(args: Array<String>) {
    val K = readLine()!!.toInt()

    var result = 0L
    for(a in 1..K) {
        for(b in 1..K) {
            for(c in 1..K) {
                result += gcd(gcd(a,b), c)
            }
        }
    }
    println(result)
}

Measured memory_bytes: 34524
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    s=readline()
    if (s[1]=='H' && s[3]=='H') || (s[1]=='D' && s[3]=='D')
        println('H')
    else
        println('D')
    end
end
main()

Measured memory_bytes: 106672
n = int(input())
A = list(map(int,input().split()))

T = [0, 0, 0]

for i in range(n):
    if A[i] % 4 == 0:
        T[0] += 1
    elif A[i] % 2 == 0:
        T[1] += 1
    else:
        T[2] += 1

if (T[1] == 0 and T[0] >= T[2] - 1) or (T[1] > 0 and T[0] >= T[2]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 62576
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MOD=1000000007;
const ll MAX=9187201950435737471;
const int N=100005;
const ll INF=1e14;

int a[1003][1003];
int dp[1003][1003];
int n,m;

void solve(){
    dp[n-1][m-1]=1;
    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            if(a[i][j+1]!=0)dp[i][j]+=dp[i][j+1];
            if(a[i+1][j]!=0)dp[i][j]+=dp[i+1][j];
            dp[i][j]%=MOD;
        }
    }
}
int main() {
    fastio

    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            if(c=='.')a[i][j]++;
        }
    }
    solve();
    cout<<dp[0][0];
	return 0;
}


Measured memory_bytes: 8064
#include <stdio.h>
#include <math.h>

int main(void) {

  long n;
  scanf("%ld", &n);
  long answer = 0;
  int generate[9];
  long number;
  int has7,has5,has3;
  for (int digits = 3; digits <= 9; digits++) {
    if (pow(10,digits-1) > n) {
      break;
    }
    for (int i = 0; i < digits; i++) {
      generate[i] = 0;
    }
    for (int i = 0; i < pow(3,digits)-1; i++) {
      number = 0;
      has3 = 0;
      has5 = 0;
      has7 = 0;
      for (int j = 0; j < digits; j++) {
        if (generate[j] == 0) {
          has3 = 1;
          number += 3*pow(10,j);
        }
        if (generate[j] == 1) {
          has5 = 1;
          number += 5*pow(10,j);
        }
        if (generate[j] == 2) {
          has7 = 1;
          number += 7*pow(10,j);
        }
      }
      if (has3 == 1 && has5 == 1 && has7 == 1 && number <= n) {
        answer++;
      }
      generate[0]++;
      for (int j = 1; j < digits; j++) {
        generate[j] += generate[j-1]/3;
        generate[j-1] %= 3;
      }
    }
  }
  printf("%ld\n", answer);

  return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int a[3][3];


int main(void){
	cin >> a[0][0] >> a[1][0] >> a[1][1];
	const int s=3*a[1][1];

	a[2][0]=s-a[0][0]-a[1][0];
	a[2][2]=s-a[0][0]-a[1][1];
	a[2][1]=s-a[2][0]-a[2][2];
	a[1][2]=s-a[1][0]-a[1][1];
	a[0][2]=s-a[2][0]-a[1][1];
	a[0][1]=s-a[0][0]-a[0][2];
	
	rep(i,3){
		rep(j,3) cout << (j?" ":"") << a[j][i];
		cout << endl;
	}
	
	return 0;
}

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

int bubbleSort(int A[], int N){
	int sw = 0;
	bool flag = 1;
	for (int i=0; flag; i++){
		flag = 0;
		for (int j=N-1; j>=i+1; j--){
			if (A[j] < A[j-1]){
				swap(A[j], A[j-1]);
				flag = 1;
				sw++;
			}
		}
	}
	return sw;
}

int main(){
	int A[100], N, sw;
	cin >> N;
	for (int i=0; i<N; i++) cin >> A[i];

	sw = bubbleSort(A, N);

	for (int i=0; i<N; i++){
		if (i) cout << " ";
		cout << A[i];
	}
	cout << endl;
	cout << sw << endl;

	return 0;
}

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

int main(){
    ll N, A, B;
    cin >> N >> A >> B;
    ll ans = 0;
    if(A % 2 == 0 && B % 2 == 0)
    {
        ans = (B - A) / 2;
    }else if(A % 2 != 0 && B % 2 != 0){
        ans = (B - A) / 2;
    }
    else
    {
        ans = min(A - 1, N - B) + 1 + ((B - A - 1) / 2);
    }
    cout << ans << endl;
}

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

int main() {
  int N;
  cin >> N;
  int k = sqrt(2*N);
  if (k*(k+1)/2 < N) k += 1;
  cout << k << endl;
  N -= k;
  
  for(int i = k-1; i > 0; i--) {
    if (i <= N) {
      cout << i << endl;
      N -= i;
      if (N == 0) return 0;
    }
  }
}

Measured memory_bytes: 256
line = gets
input_a, input_b, input_c = line.split(" ")
input_a = input_a.to_i
input_b = input_b.to_i
input_c = input_c.to_i
if input_a < input_b && input_b < input_c then
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 6856
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
N = int(input())
X  = list(map(int,input().split()))

b = 0 
c = 0 
for x in X:
    b = b -2 * x
    c = c + x * x 

u = int (float (-b) / float(2* N) + 0.5 )
# print(u)

s = N * u ** 2 + b * u + c
print(s)


Measured memory_bytes: 3060
def read_data():
    N = int(input())
    As = list(map(int, input().split()))
    return N, As

def solve(N, As):
    x = max(As)
    y = min(As)
    if x - y > 1:
        return False
    if x == y:
        if x == N - 1:
            return True
        if x * 2 <= N:
            return True
        return False
    n_solo = As.count(y)
    if x < n_solo + 1:
        return False
    n_group = x - n_solo
    if n_group * 2 <= N - n_solo:
        return True
    return False

N, As = read_data()
if solve(N, As):
    print('Yes')
else:
    print('No')


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

using namespace std;

#define SZ(x) (int)(x.size())
#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, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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

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

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

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  vi a(n), b(n);
  REP(i, n) {
    cin >> a[i];
  }
  REP(i, n) {
    cin >> b[i];
  }

  int ans = 0;
  RREP(d, 29) {
    int h = 1 << (d+1);
    int l = 1 << d;

    REP(i, n) {
      a[i] %= h;
      b[i] %= h;
    }

    sort(ALL(b));

    ll num = 0;
    REP(i, n) {
      int add = 0;
      if(l - a[i] >= 0) {
        auto it1 = lower_bound(ALL(b), l - a[i]);
        auto it2= lower_bound(ALL(b), h - a[i]);
        int pos1 = distance(b.begin(), it1);
        int pos2 = distance(b.begin(), it2);

        add += pos2 - pos1;
      } else {
        auto it1 = lower_bound(ALL(b), h - a[i]);
        int pos1 = distance(b.begin(), it1);
        add += pos1;
        auto it3 = lower_bound(ALL(b), h);
        auto it2 = lower_bound(ALL(b), h + l - a[i]);
        int pos3 = distance(b.begin(), it3);
        int pos2 = distance(b.begin(), it2);
        add += pos3 - pos2;
      }
      num += add;
    }
    if(num & 1) ans += l;
  }
  cout << ans << endl;

}








Measured memory_bytes: 4756
#include <stdio.h>
//#include <windows.h>

int ans = 0;
int x[4],y[4];
int depth = 0;

int put_map(int m[4][4],int current){
	
	if(depth == 8){
		ans++;
		return 0;
	}

	int i,j,k,a,b,pointer;
	int next1,next2;
	int copy[4][4];

	for(pointer = current; pointer < 15; pointer++){
		i = pointer / 4;
		j = pointer % 4;

		if(m[i][j] == 0){
			for(k = 0; k < 4; k++){
				next1 = i + x[k];
				next2 = j + y[k];
				if(0 <= next1 && next1 <= 3 && 0 <= next2 && next2 <= 3){
					if(m[next1][next2] == 0){
						for(a = 0; a < 4; a++){
							for(b = 0; b < 4; b++){
								copy[a][b] = m[a][b];
							}
						}
						copy[i][j] = 1;
						copy[next1][next2] = 1;
						depth++;
						
					//	for(a = 0; a < 4; a++){
					//		for(b = 0; b < 4; b++){
					//			printf("%d",copy[b][a]);
					//		}
					//		printf("\n");
					//	}

						put_map(copy,pointer);

						depth--;
						copy[i][j] = 0;
						copy[next1][next2] = 0;
					}
				}
				next1 = i - x[k];
				next2 = j - y[k];
				if(0 <= next1 && next1 <= 3 && 0 <= next2 && next2 <= 3){
					if(m[next1][next2] == 0){
						for(a = 0; a < 4; a++){
							for(b = 0; b < 4; b++){
								copy[a][b] = m[a][b];
							}
						}
						copy[i][j] = 1;
						copy[next1][next2] = 1;
						depth++;
						
						// for(a = 0; a < 4; a++){
						// 	for(b = 0; b < 4; b++){
						// 		printf("%d",copy[b][a]);
						// 	}
						// 	printf("\n");
						// }

						put_map(copy,pointer);

						depth--;
						copy[i][j] = 0;
						copy[next1][next2] = 0;
					}
				}
			}
			return 0;
		}
	}
	return 0;
}

int main()
{
	int map[4][4];
	int i,j;
	scanf("%d",&x[0]);
	while(x[0] < 4){
		scanf("%d",&y[0]);
		for(i = 1; i < 4; i++){
			scanf("%d %d",&x[i],&y[i]); // x,yの読み取り
		}

		ans = 0; // 解の個数を0に戻す
		depth = 0; // 探索中の深さを0に戻す

		for(i = 0; i < 4; i++){
			for(j = 0; j < 4; j++){
				map[i][j] = 0; // マップの初期化
			}
		}
		i = put_map(map,0);
		printf("%d\n",ans); // 解の出力
	
		scanf("%d",&x[0]);
	}
	return 0;
}

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

int main() {
  int N;
  int i = 0;
  int j = 0;
  int k = 0;
  int l = 0;
  
  cin >> N;
  for (int A = 0; A < N && 1 <= N && N <= 100; A++) {
    string S;
    cin >> S;
    
    if (S == "P") {
      i++;
    } else if (S == "W") {
      j++;
    } else if (S == "G") {
      k++;
    } else if (S == "Y") {
      l++;
    }
  }
  if (l == 0) {
    cout << "Three" << endl;
  } else {
    cout << "Four" << endl;
  }
}

Measured memory_bytes: 3600
fun main(args: Array<String>) {
    codefestival2017qualc_b()
}

// 全パターン - すべて奇数になるパターン で求める
fun codefestival2017qualc_b() {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(' ').map { it.toInt() }

    val answer = Math.pow(3.0, n.toDouble()).toLong() -
            aList.map { if (it % 2 == 0) 2 else 1 }.reduce { acc, i -> acc * i }

    println(answer)
}


Measured memory_bytes: 38336
#include <iostream>
#include <algorithm>

using namespace std;

int A[100002][3];
int F[100002][3];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i][1] >> A[i][2] >> A[i][3];
    }
    F[1][1] = A[1][1];
    F[1][2] = A[1][2];
    F[1][3] = A[1][3];
    for (int i = 2; i <= n; ++i) {
        F[i][1] = max(F[i-1][2] + A[i][1], F[i-1][3] + A[i][1]);
        F[i][2] = max(F[i-1][3] + A[i][2], F[i-1][1] + A[i][2]);
        F[i][3] = max(F[i-1][1] + A[i][3], F[i-1][2] + A[i][3]);
    }
    int m = max(F[n][1], F[n][2]);
    m = max(F[n][3], m);
    cout << m;
    return 0;
}

Measured memory_bytes: 2560
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		//??????????????°
		String[] a = new String[10];
		ArrayList<String> b = new ArrayList<String>();
		String retu;
		//ArrayList<Integer> num = new ArrayList<Integer>();


		//????????£?????????!!

		Scanner scan = new Scanner(System.in);

		//????????£??\
		while(scan.hasNext()){

			retu = scan.next();
			a = retu.split("");
			ArrayList<Integer> num = new ArrayList<Integer>();


			for(int i = 0 ; i < a.length ; i++){
				int m =  Integer.parseInt(a[i]);

			num.add(m);

			}
			for(int x = 0 ; x < 9; x++){

				for(int i = 0 ; i < num.size() - 1 ; i++){
					int gg = (num.get(i) + num.get(i + 1)) % 10;
					num.set(i,gg);


				}
				num.remove(num.size() - 1);
			}

			//????????¨???
					System.out.println(num.get(0));


		}

	}

}

Measured memory_bytes: 26032
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <time.h>
#include <stdlib.h>
using namespace std;

int main(){
	while(1){
		int n,m;
		char str[100001],pre[100000],post[100000];
		cin >> n;
		if(n==0) return 0;
		for(int i=0;i<n;i++){
			cin >> pre[i];
			cin >> post[i];
		}
		cin >> m;
		for(int i=0;i<m;i++){
			cin >> str[i];
			for(int j=0;j<m;j++){
				if(str[i] == pre[j]){
					str[i] = post[j];
					break;
				}
			}
		}
		str[m] = '\0';
		
		printf("%s\n",str);
	}
	return 0;
}


Measured memory_bytes: 3012
#include <bits/stdc++.h>
#define pb push_back
#define sz(a) (int)(a.size())

using namespace std;

const int N = (int)1e6 + 123;

int main ()
{
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	#endif
	ios_base::sync_with_stdio(0);
	cout.tie(0), cin.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	cout << (a - b) % c;
}

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

const int MOD = (int)1e9+7;

class Union_Find_size{
public:
	vector<int> Parent;
	
	//コンストラクタ
	Union_Find_size(int N){
		Parent=vector<int>(N,-1);
	}
	
	//木の根を求める
	int root(int x){
		//x（自分）が親ならxを返す
		if(Parent.at(x)<0)	return x;
		//経路圧縮しながら return する
		return Parent.at(x)=root(Parent.at(x));
	}
	
	//xの属する木の要素数を調べる
	int size(int x){
		return -Parent.at(root(x));
	}
	
	//xとyが同じ集合に属するかを判定する
	bool same(int x,int y){
		return root(x)==root(y);
	}
	
	//xとyの属する集合を併合する
	void unite(int x,int y){
		x=root(x);
		y=root(y);
		if(x==y)	return;
		
		if(size(x)<size(y))	swap(x,y);
		Parent.at(x)+=Parent.at(y);
		Parent.at(y)=x;
	}
};

int main(){
	int N,M;
	cin >> N >> M;
	vector<int> X(M),Y(M),Z(M);
	for(int i=0;i<M;i++){
		cin >> X.at(i) >> Y.at(i) >> Z.at(i);
		X.at(i)--;
		Y.at(i)--;
	}

	Union_Find_size Uni(N);
	for(int i=0;i<M;i++){
		if(!Uni.same(X.at(i),Y.at(i))){
			Uni.unite(X.at(i),Y.at(i));
		}
	}

	int ans=0;
	for(int i=0;i<N;i++){
		if(Uni.Parent.at(i)<0)	ans++;
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const long long LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
	int a, b;
	char c;
	cin >> a >> c >> b;
	cout << (c == '+' ? a + b : a - b) << endl;
	return 0;
}

Measured memory_bytes: 256
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言
int func(int);

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int n, sum = 0;

  for(int i=1; i<=N; ++i) {
    n = func(i);
    if(n >= A && n <= B) {
      sum += i;
    }
  }

  cout << sum << endl;

  return 0;
}

int func(int f) {
  int r = 0;

  while(f != 0) {
    r += f%10;
    f /= 10;
  }

  return r;
}


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

#define INF 1e9
using namespace std;

int main() {

    int n; cin >> n;

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

    int ans = 0;
    for (int i = 1; i < n-1; ++i) {
        if ((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i-1] > p[i] && p[i] > p[i+1])) {
            ++ans;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/numeric/interval.hpp>
#include <boost/numeric/interval/io.hpp>
using namespace::std;
namespace mp = boost::multiprecision;
typedef mp::number<mp::cpp_dec_float<32,int64_t>> cfloat;
typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define cout (cout<<fixed<<setprecision(15))
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define out(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<"\n";}while(0)
#define out2(v) for(auto i:v)output(i);
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define INF (1LL<<60)
#define IINF (1<<30)
#define LINF 9223372036854775807
#define MOD 1000000007
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
int main(){
    input(a,n);
    sort(all(a));
    lint ans=accumulate(all(a),0LL);
    if(ans%10!=0){
        cout<<ans;
        return 0;
    }
    rep(i,n){
        if((ans-a[i])%10!=0){
            cout<<ans-a[i];
            return 0;
        }
    }
    cout<<0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
   
	int array[4][3][10];

	int n, b, f, r, v, i, o, m;


	for (i = 0; i < 4; i++) {
		for (m = 0; m < 4; m++) {
			for (n = 0; n < 10; n++) {
				array[i][m][n] = 0;
			}
		}
	}
	scanf("%d", &n);

	for (i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &b, &f, &r, &v);
		array[b - 1][f - 1][r - 1]+= v;
	}

	for (o = 1; o <= 4; o++) {/*棟*/
		for (i = 1; i<4; i++) {/*回数*/
			for (m = 0; m<10; m++) {
				printf(" %d", array[o - 1][i - 1][m]);
			}
			 { printf("\n"); }
		}
		if (o != 4) { printf("####################\n"); }
	}
    
    return 0;
}


Measured memory_bytes: 2048
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=1e6+5;
typedef long long ll;
int n,a[N];
struct node{
    int u,v,nxt;
}edge[N*2];
int head[N],mcnt;
void add_edge(int u,int v){
    mcnt++;
    edge[mcnt].u=u;
    edge[mcnt].v=v;
    edge[mcnt].nxt=head[u];
    head[u]=mcnt;
}
bool NP(int u,int fa){
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa||a[v]>=a[u])
            continue ;
        if(!NP(v,u))
            return true;
    }
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1;i<=n;i++){
        if(NP(i,0))
            printf("%d ",i);
    }
}


Measured memory_bytes: 4224
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    int solve(int n, int x, int p) {
        if (p == 0) return x == 0 ? 1 : 0;
        if (n == 0) return 0;
        int r;
        if (x >= n) r += solve(n-1, x-n, p-1);
        r += solve(n-1, x, p);
        return r;
    }

    for (;;) {
        auto nx = readln.split.to!(int[]);
        auto n = nx[0];
        auto x = nx[1];
        if (n == 0 && x == 0) return;
        writeln(solve(n, x, 3));
    }
}


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

int main(){
  int n,T,H,L,S;
  int t[110],h[110];

  cin >> n >> T >> H >> L;
  for(int i=0;i<n;i++)cin >> t[i] >> h[i];
  S = 0;

  for(;;){
    for(int i=0;i<n;i++){
      if(t[i]){
	S += 10;
	T++;
	t[i]--;
      }else if(h[i]){
	S += 100;
	H++;
	h[i]--;
      }else{
	cout << i+1 << endl;
	return 0;
      }

      if(T>L){
	cout << i+1 << endl;
	return 0;
      }

      if(S>=90){
	S -= 90;
	while(S){
	  if(S<=T*10){
	    t[i] += S/10;
	    T -= S/10;
	    S = 0;
	  }else if(S>=100){
	    S -= 100;
	    h[i]++;
	    H--;
	  }else{
	    cout << i+1 << endl;
	    return 0;
	  }
	}
      }
    }
  }
}

Measured memory_bytes: 1160
from heapq import heappush, heappop
import math

# 最大のなにか、最小の何かを取り出すときに
n, m = map(int, input().split())
work = [list(map(int, input().split())) for _ in range(n)]
work = sorted(work, key = lambda x:x[0])
hq = []
counter = 0
ans = 0
for i in range(1,m+1):
    while counter < n and work[counter][0] <= i:
        heappush(hq, -1*work[counter][1])
        counter += 1
    try:
        ans -= heappop(hq)
    except:
        continue
print(ans)


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

int main(){
  int n,i;
  cin>>n;
  int L[n],R[n];
  for(i=0;i<n;i++){
    cin>>L[i]>>R[i];
  }
  int sum=0;
  for(i=0;i<n;i++){
    sum+=R[i]-L[i]+1;
  }
  cout<<sum;
}

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

const int INF = 2e9;

int main(){
    int n;
    cin >> n;
    vector<int> x(n),y(n);
    rep(i,n){
        cin >> x[i];
        y[i] = x[i];
    }
    sort(y.begin(),y.end());
    int a = n/2;
    vector<int> b(2);
    b[0] = y[a-1],b[1] = y[a];
    rep(i,n){
        if(x[i] <= b[0]) cout << b[1] << endl;
        else cout << b[0] << endl;
    }
}

Measured memory_bytes: 3712
#include<stdio.h>

void QSort(int x[ ], int left, int right);
void Swap(int x[ ], int i, int j);
void reverse(int array[], int length);

void QSort(int x[ ], int left, int right)
{
    int i, j;
    int pivot;
    i = left;                      
    j = right;
    pivot = x[(left + right) / 2]; 
    while (1) {                    
        while (x[i] < pivot)       
            i++;

        while (pivot < x[j])       
            j--;                 
        if (i >= j)              
            break;              

        Swap(x, i, j);            
        i++;                       
        j--;
    }
    
    if (left < i - 1)              
        QSort(x, left, i - 1);    
    if (j + 1 <  right)            
        QSort(x, j + 1, right);    
}

void Swap(int x[ ], int i, int j)
{
    int temp;
    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}

void reverse(int array[], int length)
{
    int i, j;
    int temp;
    
    for( i = 0, j = length - 1; i < j; i++, j-- )
    {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

int main (void) {
  int N,K;
  scanf("%d %d",&N,&K);
  int a[5010];
  int i,j;
  for(i=0;i<N;i++){
    scanf("%d",&a[i]);
    if(a[i]>=5000){
      N--;
      i--;
    }
  }

  QSort(a, 0, N-1);
  reverse(a,N);

  int left,right,point;
  int sum;
  int check = 0;
  point = -1;
  for(left=0;left<N;left++){
    sum = 0;
    for(right=left;right<N;right++){
      sum += a[right];
      if(sum>=K){
	point = right;
	sum -= a[right];
      } else {
	if(right==N-1){
	  //check = 1;
	}
      }
    }
    if(check){
      break;
    }
  }
  
  printf("%d\n",N-point-1);

  return 0;
}


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

#define ll long long int
#define INFTY (1<<21)

using namespace std;

int main(void){
    cin.sync_with_stdio(false);
    int a,b,x;
    cin>>a>>b>>x;
    cout<<((a>x||(a+b)<x)?"NO":"YES")<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int n,m,l;

  cin >> n >> m >> l;

  int A[101][101]={{}},B[101][101]={{}};

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

  for(int i=0;i<m;i++){
    for(int j=0;j<l;j++){
      cin >> B[i][j];
    }
  }

  long long C[101][101]={{}};

  for(int i=0;i<n;i++){
    for(int j=0;j<l;j++){
      for(int k=0;k<m;k++){
        C[i][j] += A[i][k]*B[k][j];
      }
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<l;j++){
      cout << C[i][j];
      if(j!=l-1) cout << " ";
      else cout << endl;
    }
  }


  return 0;
}

Measured memory_bytes: 3252
#include<iostream>
#include<functional>
#include<utility>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;
const auto MOD = 1000000007;
const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i,n) for(int i = 0; i < (n);i++)
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef vector<int> VI;
typedef vector<long long> VLL;


int n, m;
string s;

int main() {
	cin >> n;
	VI a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	if (!a[0] && !a[n - 1]) { cout << "Yes" << endl;return 0; }
	if ((n % 3)) { cout << "No" << endl;return 0; }
	int b, c, d;
	b = a[0];c = a[n / 3];d = a[2 * n / 3];
	for (int i = 0; i < n/3; i++)
	{
		if (a[i] != b) { cout << "No" << endl;return 0; }
	}
	for (int i = 0; i < n / 3; i++)
	{
		if (a[i+n/3] != c) { cout << "No" << endl;return 0; }
	}
	for (int i = 0; i < n / 3; i++)
	{
		if (a[i+2*n/3] != d) { cout << "No" << endl;return 0; }
	}
	if(b^c^d) { cout << "No" << endl;return 0; }
	cout << "Yes" << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

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

	vector<int> res;
	while(v.size()>0){
		int idx=-1;
		for(int i=v.size()-1; i>=0; i--){
			if(v[i]==i+1){
				idx=i+1;
				res.push_back(idx);
				v.erase(v.begin()+i);
				break;
			}
		}
		if(idx==-1){
			cout << -1 << endl;
			return 0;
		}
	}
	for(int i=n-1; i>=0; i--){
		cout << res[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
/* Hello darkness my old friend, I've come to visit you again! */

#include<bits/stdc++.h>
#define lli long long int
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORB(i,b,a) for(i=b;i>=a;i--)
#define mod 1000000007
#define PI 2*acos(0.0)
#define gs getline(cin,s)
#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pb push_back
#define eb emplace_back4
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 1000000005
#define INF 1000000000000000005
#define io ios_base::sync_with_stdio(0);
#define ff first
#define ss second
using namespace std;
int a[1000];
int main()
{
    io;
    cin.tie(0);
    cout.tie(0);
    int A,B,n,i;
    cin>>A>>B;
    FOR(i,1,1000)
    a[i]=a[i-1]+i;
    FOR(i,1,1000)
    {
        if(a[i]<=A || a[i+1]<=B)
            continue;
        if(a[i]-A == a[i+1]-B)
        {
            cout<<a[i]-A;
            return 0;
        }
    }
    return 0;
}

/* This is the end, beautiful friend! */


Measured memory_bytes: 256
N=input()
prev_x=0
prev_y=0
prev_t=0
a=[]
for i in range(N):
	t,x,y=map(int,raw_input().split())
	l=abs(x-prev_x)+abs(y-prev_y)
	t_diff=t-prev_t
	a.append( (t_diff,l) )
	prev_x=x
	prev_y=y
	prev_t=t


for i,j in a:
	if i>=j and (i-j)%2==0:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"
	


Measured memory_bytes: 16004
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

#define LL long long

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

int n, t = 0;
bool flg = true;
vector<pair<int, int>>work;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		work.push_back(make_pair(b, a));
	}
	sort(work.begin(), work.end());
	for (int i = 0; i < n; i++) {
		t += work[i].second;
		if (t > work[i].first) {
			flg = false;
			break;
		}
	}
	if (flg)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    double R; cin >> R;
    cout << std::fixed << std::setprecision(3) << 2*M_PI*R << endl;
    return 0;
}


Measured memory_bytes: 3796
#include<bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;

typedef long long ll;
typedef complex<double> P;
#define EPS 1e-5
int n;
int r[17],sx[17],sy[17],gx[17],gy[17];
bool dp[1<<17];

double get(double a,double b){
	return a+b;
}

double dot(P a,P b){
	return (get(a.real()*b.real(),a.imag()*b.imag()));
}

double cross(P a,P b){
	return (get(a.real()*b.imag(),-a.imag()*b.real()));
}


double distance_ls_p(P a,P b,P c){
	if(dot(b-a,c-a)<EPS)return abs(c-a);
	if(dot(a-b,c-b)<EPS)return abs(c-b);
	return abs(cross(b-a,c-a))/abs(b-a);
}


bool C(int bit,int v){
	P fp,tp;
	fp=P(sx[v],sy[v]);
	tp=P(gx[v],gy[v]);
	for(int i=0;i<n;i++){
		if(i==v)continue;
		P pt=P(sx[i],sy[i]);
		if((bit>>i) & 1){
			pt=P(gx[i],gy[i]);
		}
		long double len=distance_ls_p(fp,tp,pt);
		if(get(-r[i]-r[v],len)<0){
			return false;
		}
	}
	return true;
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d%d%d",&r[i],&sx[i],&sy[i],&gx[i],&gy[i]);
	}
	memset(dp,false,sizeof(dp));
	dp[0]=true;
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		if(dp[i]){
			for(int j=0;j<n;j++){
				if(!(i>>j & 1)){
					if(C(i,j)){
						dp[i+(1<<j)]=true;
						ans=max(ans,__builtin_popcount(i+(1<<j)));
					}
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

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

char c[1000000];
int main() {
	int a, b;
	while (scanf("%d", &a), a) {
		scanf("%d%s",&b, c);
		int d = strlen(c);
		int s = 0;
		for (int e = 0; e < d; e++) {
			if (c[e] == 'I') {
				int k = 1;
				for (int f = e + 1; f < d; f++) {
					if (c[f - 1] == c[f]) { e = f - 1; break; }
					k++;
				}
				k++;
				k /= 2;
				if (k > a)s += k - a;
			}
		}
		printf("%d\n", s);
	}
}

Measured memory_bytes: 4128
mod = 10**9+7
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

pi = 1
ni = 0
ans = 1
i = 0
while i < K-1:
  if A[ni]*A[ni+1] > A[-pi]*A[-pi-1]:
    ans = ans*A[ni]*A[ni+1]%mod
    ni += 2
    i += 2
    
  else:
    ans = ans*A[-pi]%mod
    pi += 1
    i += 1
    
if i == K-1:
  ans = ans*A[-pi]%mod
  
if A[-1]<0 and K%2==1:
  ans = 1
  for i in A[N-K:]:
    ans = ans*i%mod

print(ans)


Measured memory_bytes: 30908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD=1e9+7;
ll inv(ll a, ll b = MOD){
    ll x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        const ll q = a / b;
        ll tmp = a % b;
        a = b;
        b = tmp;
        tmp = x0 - q * x1;
        x0 = x1;
        x1 = tmp;
        tmp = y0 - q * y1;
        y0 = y1;
        y1 = tmp;
    }
    return (x0 + MOD) % MOD;
}
ll fact(ll x){
    // 再帰だとスタックオーバーフローするので
    ll ret = 1;
    for(ll a=2; a<=x; ++a){
        ret = (ret * a) % MOD;
    }
    return ret;
}
/*
【解法】
A = [1, 2, ..., n] と固定する（求める場合の数は、固定した場合の数の mPn 倍）。B を長さ n の数列とする

ある集合 S \subset {1, ..., n} の上で値が一致する（そのほかにも一致する値のある可能性がある）ような B の場合の数は g(S) = (m-|S|)P(n-|S|) 通り
（まだ決まっていない n-|S| 箇所の値を、使っていない m-|S| 個の値から重複しないように決める）

ある集合 S \subset {1, ..., n} の上でちょうど値が一致する（ S に属さない点 i ではA[i] != B[i] となる）ような
B の場合の数を f(S) 通りとすると、g(S) = \sum_{S\subset T} f(T) となる。

F(S) = f({1, ..., n} \setminus S), G(S) = g({1, ..., n} \setminus S) とおくと、
G(S) = \sum_{T\subset S} F(S) なので、包除原理から F(S) = \sum_{T\subset S} (-1)^|S\setminus T| G(T) が成り立つ。

求めるのは f(\emptyset)
= F({1, ..., n})
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| G(T)
= \sum_{T\subset {1, ..., n}} (-1)^|{1, ..., n}\setminus T| g({1, ..., n} \setminus T)
= \sum_{T\subset {1, ..., n}} (-1)^|T| g(T)
（ T -> T\setminus {1, ..., n} で置換）
ここで g は size の関数なので g(T) = g(|T|) とおくと、 k 元集合の選び方が nCk 通りなので 
= \sum_{k=0}^n (-1)^k nCk g(k)
= \sum_{k=0}^n (-1)^k n! / (n-k)! / k! * (m-k)! / (m-n)!
となる。

これを高速に計算する。 k == 0 のとき m! / (m-n)! で、

    n! (m-k)!             n! (m-(k-1))!          n-k+1
---------------- == ------------------------ * ---------
(n-k)! k! (m-n)!    (n-(k-1))! (k-1)! (m-n)!   (m-k+1) k

なので、 k がふえるたびに (n-k+1) / (m-k+1) / k 倍すればよい
*/
ll inv_table[500001] = {};
void make_inv_table(int n){
    inv_table[1] = 1;
    for (int i=2; i<=n; ++i){
        // (MOD / i) * i + MOD % i = 0 なので
        // (MOD / i) * i = - (MOD % i)
        // - (MOD / i) * (MOD % i)^(-1) = i^(-1)
        inv_table[i] = inv_table[MOD%i] * (MOD - MOD / i) % MOD;
    }
}

int main()
{
    ll n, m;
    cin >> n >> m;

    const ll mpn = fact(m) * inv(fact(m-n)) % MOD;
    ll tmp = mpn;
    ll sum = tmp;
    const ll sign[2] = {1, MOD-1};
    make_inv_table(m);
    for(int k=1; k<=n; ++k){
        tmp = ((tmp * inv_table[m-k+1]) % MOD * (inv_table[k] * (n-k+1) % MOD)) % MOD;
        sum = (sum + sign[k%2] * tmp) % MOD;
    }
    cout << (sum * mpn) % MOD;
    return 0;
}


Measured memory_bytes: 7552
#include<stdio.h>
#include<string>
using namespace std;
string str[50];
char temp[21];
int in[9];
int v[50];
int w[50];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%s",temp);
			str[i]=temp;
			for(int j=0;j<9;j++)scanf("%d",in+j);
			v[i]=(in[6]*in[7]*in[8]-in[0]);
			w[i]=(in[1]+in[2]+in[3]+in[8]*in[4]+in[8]*in[5]);
			//printf("%f\n",v[i]);
		}
		for(int i=0;i<a;i++){
			int at=0;
			for(int j=0;j<a;j++){
				if(w[j]>=0){at=j;break;}
			}
			for(int j=0;j<a;j++){
				if(w[j]<0)continue;
				if(v[at]*w[j]<v[j]*w[at]){
					at=j;
				}else if(v[at]*w[j]==v[j]*w[at]&&str[at]>str[j]){
					at=j;
				}
			}
			printf("%s\n",str[at].c_str());
			w[at]=-1;
		}
		printf("#\n");
	}
}

Measured memory_bytes: 1060
#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,dp[100005],x,y;
vector<int> bi[100005];
void dfs(int x,int fa)
{
	int i;
	dp[x]=0;
	for (vector<int>::iterator it=bi[x].begin();it!=bi[x].end();it++)
	{
		if (*it==fa) continue;
		dfs(*it,x);
		if (dp[*it]==0) dp[x]++;
		if (dp[*it]>1||dp[x]>1)
		{
			dp[x]=2;
			break;
		}
	}
}
int main()
{
	cin>>n;
	for (i=1;i<n;i++)
	{
		cin>>x>>y;
		bi[x].push_back(y);
		bi[y].push_back(x);
	}
	dfs(1,0);
	if (dp[1]==1) cout<<"Second"; else cout<<"First";
	return 0;
}

Measured memory_bytes: 6144
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  ll a;
  cin >> a;

  cout << a+a*a+a*a*a << endl;

  return 0;
}


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

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

	string a, b, c; cin >> a >> b >> c;
	int turn = 0;
	while(true){
		if(turn == 0){
			if(a.empty()){
				cout << "A" << endl;
				return 0;
			}
			turn = a[0] - 'a';
			a.erase(0,1);
		}
		else if(turn == 1){
			if(b.empty()){
				cout << "B" << endl;
				return 0;
			}
			turn = b[0] - 'a';
			b.erase(0,1);
		}
		else{
			if(c.empty()){
				cout << "C" << endl;
				return 0;
			}
			turn = c[0] - 'a';
			c.erase(0,1);
		}
	}
	return 0;	
}





  

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

int main(){
 string a,b;
 cin>>a>>b;
 vector<vector<ll>> dp(a.length()+1,vector<ll>(b.length()+1));
 for(ll i=1;i<=a.length();i++){
 	for(ll j=1;j<=b.length();j++){
 		if(a[i-1]==b[j-1]){
 			dp[i][j]=1+dp[i-1][j-1];	
		}	
		else{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
 }
 string sol;
 ll I=a.length(),J=b.length();
 while(dp[I][J]){
 	if(a[I-1]==b[J-1]){
 		string chr="";
 		chr.push_back(a[I-1]);
 		sol=chr+sol;
 		I--,J--;
	}
	else{
		if(dp[I-1][J]==dp[I][J]){
			I--;
		}
		else{
			J--;
		}
	}
 }
 cout<<sol<<endl;
 return 0;
}



Measured memory_bytes: 74064
#include<stdio.h>
int main(void)
{
    int i,n,j,suuti[101],A,kaisuu;
    while(1){
            kaisuu=0;
        scanf("%d",&n);
        if(n==0)break;
        for(i=0;i<n;i++){
        scanf("%d",&suuti[i]);
        }
        for(i=0;i<n;i++){
            for(j=0;j<n-1;j++){
                if(suuti[j]>suuti[j+1]){
                        A=suuti[j];
                        suuti[j]=suuti[j+1];
                        suuti[j+1]=A;
                        kaisuu++;
                }
            }
        } printf("%d\n",kaisuu);
    }
    return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  double t,x; 
  cin>>t>>x;
  double ans = t/x;
  printf("%lf\n",ans);


  return 0;
}


Measured memory_bytes: 256
#include <array>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

constexpr unsigned long maxN = 200010;

array<unsigned long, maxN> perm;
    array<unsigned long, maxN> binary;
    array<unsigned long, maxN> coef;
    array<unsigned long, maxN> fenwick_tree;

    unsigned long que(unsigned long i){
        unsigned long s{0}, j{i};
        while (i) { s += fenwick_tree[i]; i -= i & -i; }
        while (j < maxN) { ++fenwick_tree[j]; j += j & -j; }
        return s;
    };


int main() {
    //using namespace std;
   
    unsigned long N;
    scanf("%lu", &N);
   
    {
        array<pair<long, long>, maxN> p;
        for(unsigned long i = 0; i < N; ++i)scanf("%lu%lu", &p[i].first, &p[i].second);
        sort(p.begin(), p.begin() + N);
        for(unsigned long i = 0; i < N; ++i)p[i] = {p[i].second, i + 1};
        sort(p.begin(), p.begin() + N);
        transform(p.cbegin(), p.cbegin() + N, perm.begin(), [](auto i){return i.second;});
    }

    constexpr unsigned long MOD = 998244353;

    unsigned long n = binary[0] = 1;
    generate(binary.begin() + 1, binary.end(), [&n](){if(n >= MOD)n -= MOD;return n <<= 1;});




    coef[N] = N + MOD - 4;
    for(unsigned long i = 0; i != N; ++i){
        auto p = perm[i], q = que(p);
        ++coef[q];
        ++coef[i - q];
        ++coef[p - q - 1];
        ++coef[N - i - p + q];
    }

    printf("%lu", inner_product(binary.begin(), binary.begin() + N + 1, coef.begin(), 4 + MOD - N) % MOD);
    return 0;
}


Measured memory_bytes: 9600
#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main(void){
  long N,T;
  cin>>N>>T;
  long t[N];
  for(int i=0;i<N;i++){
      cin>>t[i];
  }
  long sum=0;
  for(int i=0;i<N-1;i++){
    int gap=t[i+1]-t[i];
    if(gap<=T) sum+=gap;
    else sum+=T;
  }
  cout<<sum+T;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
  
int main(){
    int cost[22][22]={0};
    int n,m,i,j,k,a,b,c,d;
    char cc;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            cost[i][j] = 1<<28;
        }
    }
    for(i=0;i<m;i++){
        cin>>a>>cc>>b>>cc>>c>>cc>>d;
        cost[a][b]=c;cost[b][a]=d;
    }
    for(k=1;k<=n;k++)
      for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
    cin>>a>>cc>>b>>cc>>c>>cc>>d;
    cout << c-d-cost[a][b]-cost[b][a] << endl;
}

Measured memory_bytes: 1160
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using static System.Console;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
//using System.Numerics;
//using static System.Math;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 };
    readonly int mod = 1000000007;
    readonly string alfa = "abcdefghijklmnopqrstuvwxyz";
    readonly string ALFA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    int N;
    void solve()
    {
        var S = cin.next.ToCharArray();
        int K = cin.nextint;
        for (int i = 0; i < S.Length; i++)
        {
            int idx = alfa.IndexOf(S[i]);
            if (i == S.Length - 1)
            {
                S[i] = alfa[(idx + K) % 26];
            }
            else if (S[i] != 'a' && idx + K >= 26)
            {
                S[i] = 'a';
                K -= 26 - idx;
            }

        }
        WriteLine(new string(S));
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13140
loop do
  n,m,p = gets.split.map(&:to_i)
  break if n==0

  x = []
  n.times{x<<gets.to_i}
  sum = x.inject(&:+)
  if x[m-1]==0
    puts 0
  else
    puts sum*(100-p)/x[m-1]
  end
end

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

#pragma warning( disable: 4996 )

using namespace std;

typedef long long ll;

#define INF 1000000000
#define EPS 1e-10

#define MAX_N 1501
#define MAX_M 1501

int N, M;

int h[MAX_N], w[MAX_M];
int sum_h[MAX_N];
int sum_w[MAX_M];

vector<int> ans_list;

int main(){


	while (true){

		cin >> N >> M;
		if (N == 0 && M == 0)
			break;

		for (int i = 0; i < N; i++){
			cin >> h[i];
			sum_h[i + 1] = sum_h[i] + h[i];
		}

		for (int i = 0; i < M; i++){
			cin >> w[i];
			sum_w[i + 1] = sum_w[i] + w[i];
		}

		vector<int> list_h, list_w;

		for (int emp = 0; emp < N; emp++){
			for (int s = 0, e = N - emp; e <= N; s++, e++){
				list_h.push_back(sum_h[e] - sum_h[s]);
			}
		}

		for (int emp = 0; emp < M; emp++){
			for (int s = 0, e = M - emp; e <= M; s++, e++){
				list_w.push_back(sum_w[e] - sum_w[s]);
			}
		}

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

		int ans = 0;

		for (int i = 0; i < list_w.size(); i++){
			ans += upper_bound(list_h.begin(), list_h.end(), list_w[i]) - lower_bound(list_h.begin(), list_h.end(), list_w[i]);
		}

		ans_list.push_back(ans);

	}

	for (int i = 0; i < ans_list.size(); i++){
		cout << ans_list[i] << endl;
	}

	return 0;

}

Measured memory_bytes: 21464