akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
  int input;
  int temp=0;

  while(1){
    int count=0;
    cin>>input;
    
    if(input==0)
      break;

    for(int i=1;i<input;i++){
      temp=i;
      for(int j=i+1;j<input;j++){
        temp+=j;
        if(temp>input)
          break;
        
        if(temp==input){
          count++;
          break;
        }
      }
    }
    
    cout<<count<<endl;
  }
}



Measured memory_bytes: 2996
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <cstdlib>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) { 
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int f(int n) {
  if(n == 1) return 300000;
  if(n == 2) return 200000;
  if(n == 3) return 100000;
  return 0;
}


int main() {
  int ans = 0;
  int X, Y; cin>>X>>Y;
  ans += f(X) + f(Y);
  if(X == 1 && Y == 1) ans += 400000;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
n,m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)



def dfs(x, y, l):
    if y == n - 1:
        return 1
    else:
        ans = 0
        for i in range(len(g[x])):
            if not g[x][i] in l:
                l2 = l + [g[x][i]]
                ans += dfs(g[x][i], y + 1, l2)
        return ans

print(dfs(0, 0, [0]))

Measured memory_bytes: 42076
def main():
    H, W = map(int, input().split())
    g = [str(input()) for _ in range(H)]
    LW = [[0] * W for _ in range(H)]
    LH = [[0] * W for _ in range(H)]
    for h in range(H):
        cnt = 0
        for w in range(W):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LW[h][w-i] = cnt
                LW[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LW[h][w-i] = cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if g[h][w] == '.':
                cnt += 1
            else:
                for i in range(1, cnt+1):
                    LH[h-i][w] = cnt
                LH[h][w] = 0
                cnt = 0
        else:
            for i in range(cnt):
                LH[h-i][w] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            if g[h][w] != '#':
                ans = max(ans, LH[h][w] + LW[h][w] - 1)
    print(ans)
main()

Measured memory_bytes: 126808
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007
const long long INF = LLONG_MAX / 2 - 1;

using namespace std;

long long R, C, N;
long long r[100005];
long long c[100005];
long long a[100005];
long long w[200005];

vector<pair<long long, long long> > tree[200005];

long long xmin;
long long ymin;

bool dfs(int node){
	if(node < R){
		xmin = min(xmin, w[node]);
	}else{
		ymin = min(ymin, w[node]);
	}
	for(int i = 0; i < tree[node].size(); i++){
		long long next = tree[node][i].first;
		long long wei = tree[node][i].second;
		if(w[next] == INF){
			w[next] = wei - w[node];
			if(dfs(next) == false){
				return false;
			}
		}else{
			if(w[next] + w[node] != wei){
				return false;
			}
		}
	}
	return true;
}

int main(){
	cin >> R >> C >> N;
	for(int i = 0; i < N; i++){
		cin >> r[i] >> c[i] >> a[i];
		r[i]--;c[i]--;
		tree[r[i]].push_back(make_pair(R + c[i], a[i]));
		tree[R + c[i]].push_back(make_pair(r[i], a[i]));
	}

	for(int i = 0; i < R + C; i++){
		w[i] = INF;
	}
	
	for(int i = 0; i < R + C; i++){
		xmin = INF;
		ymin = INF;
		if(w[i] != INF){
			continue;
		}
		w[i] = 0;
		if(dfs(i) == false){
			cout << "No" << endl;
			return 0;
		}
		if(xmin + ymin < 0){
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
}


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

#define int long long int
#define main signed main()
#define bye return 0
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define each(p, v) for (auto p = (v).begin(); p != (v).end(); p++)
#define all(v) (v).begin(), (v).end()
#define prec(n) fixed << setprecision(n)
#define dump(x) cerr << "(L" << __LINE__ << ") " << #x << " = " << (x) << endl
#define clr(x, a) memset(x, a, sizeof(x))

#define sum(v) accumulate(all(v), 0)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define odd(n) ((n) % 2)
#define even(n) (!odd(n))

#define INF 1000000000
#define MOD 1000000007

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>

using namespace std;

main {
  int n;
  cin>>n;
  int a[n],b[n],c[n],x[n];
  clr(x, 0);
  rep(i,n) cin>>a[i]>>b[i]>>c[i];
  int t[101];
  clr(t, 0);
  rep(j,n) t[a[j]]++;
  rep(j,n) {
    if (t[a[j]]<=1) x[j]+=a[j];
  }
  clr(t, 0);
  rep(j,n) t[b[j]]++;
  rep(j,n) {
    if (t[b[j]]<=1) x[j]+=b[j];
  }
  clr(t, 0);
  rep(j,n) t[c[j]]++;
  rep(j,n) {
    if (t[c[j]]<=1) x[j]+=c[j];
  }
  rep(i,n) cout<<x[i]<<endl;
  bye;
}

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

int main() {
  long long A,B,N;
  cin>>A>>B>>N;
  long long x=B-1;
  if(B-1>=N) {cout<<(A*N)/B-(N/B)*A<<endl; return 0;}
	cout<<(A*x)/B-(x/B)*A<<endl;
}
     

Measured memory_bytes: 3632
#include<iostream>
using namespace std;
int main() {
	int r, g, b, ans;

	cin >> r >> g >> b;
	ans = r * 100 + g * 10 + b;

	if (ans % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

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

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = (int)1e9 + 7;

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

    int h, w, k;
    cin >> h >> w >> k;

    vector<vector<LL>> dp(h+1, vector<LL>(w));
    dp[0][0] = 1;
    REP(i, h){
        for(int mask = 0; mask < (1 << (w-1)); mask++){
            bool isRinsetsu = false;
            REP(j, w-1){
                if(mask & (1 << j) && mask & (2 << j)) isRinsetsu = true;
            }
            if(isRinsetsu) continue;
            
            REP(j, w){
                if(j < w-1 && mask & (1 << j)) (dp[i+1][j+1] += dp[i][j]) %= MOD;
                else if(j > 0 && mask & (1 << (j-1))) (dp[i+1][j-1] += dp[i][j]) %= MOD;
                else (dp[i+1][j] += dp[i][j]) %= MOD;
            }
        }
    }
    cout << dp[h][k-1] << endl;
}

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

using namespace std;

int N;

int dfs(const vector<int>* edges, vector<int> S, int node){
    if(S.size() == N) return 1;
    bool flag;
    int count = 0;
    for(int p : edges[node]){
        flag = false;
        for(int s : S){
            if(p == s){
                flag=true;
                break;
            }
        }
        // すでに辿ってきた
        if(flag) continue;
        else{
            S.push_back(p);
            count += dfs(edges, S, p);
            S.pop_back();
        }
    }
    return count;
}

int main()
{
    int M;
    cin >> N >> M;
    vector<int> edges[N];
    int a, b;
    for(int i=0;i<M;++i){
        cin >> a >> b;
        --a;
        --b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    int ans = dfs(edges, vector<int>(1), 0);

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 21
#define INF 9999999

int grapha[MAX][MAX],v[MAX],mini,minnum,n;
bool visited[MAX];

int dijkstra(int x1, int x2){
  for(int i = 0 ; i < MAX ; i++){
    v[i] = INF;
    visited[i] = false;
  }

  v[x1] = 0;

  while(true){
    mini = INF;
    for(int i = 1 ; i <= n ; i++){
      if(v[i] < mini && !visited[i]){
	mini = v[i];
	minnum = i;
      }
    } 
    if(mini == INF) break;
    visited[minnum] = true;
    for(int j = 1 ; j <= n ; j++){
      if(grapha[minnum][j]+v[minnum] < v[j] && grapha[minnum][j]!=INF){
	v[j] = v[minnum] + grapha[minnum][j];
      }
    }
  }
  return v[x2];
}

int main(){
  int m,a,b,c,d,x1,x2,y1,y2,v[MAX];

  for(int i = 0 ; i < MAX ; i++){
    for(int j = 0 ; j < MAX ; j++){
      grapha[i][j] = INF;
    }
    visited[i] = false;
    v[i] = INF;
  }

  cin >> n >> m;
  for(int i = 0 ; i < m ; i++){
    scanf("%d,%d,%d,%d" ,&a ,&b ,&c ,&d);
    grapha[a][b] = c;
    grapha[b][a] = d; 
  }

  scanf("%d,%d,%d,%d" ,&x1, &x2 ,&y1 ,&y2);
  cout << y1-y2-(dijkstra(x1,x2)+dijkstra(x2,x1)) << endl;

  return 0;
}

Measured memory_bytes: 1244
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<queue>
#include<functional>
#include<cmath>
#include<map>
#include<tuple>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
#define rrep(i,n)for(int i=n-1;i>=0;i--)
#define REP(i,n) for (int i = 1; i <= (int)n; i++)//i=1からi=nまで
#define RREP(i,n)for(int i=n;i>=1;i--) 
using namespace std;
using ll = long long;
using P = pair<int, int>;
using graph = vector<vector<int>>;
const ll mod = pow(10, 9) + 7;
const int INF = 1e9;
const ll LINF = 1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	int n;
	cin >> n;
	n=n %10;
	if (n == 3) {
		cout << "bon" << endl;
	}
	else if(n == 0 || n == 1 | n == 6 || n == 8){
		cout << "pon" << endl;
	}
	else {
		cout << "hon" << endl;
	}

}

	








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

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define ABS(x, y) ((x) > (y) ? ((x) - (y)) : ((y) - (x)))

#define MOD(x, y) ((x) % (y))
#define DIVCEIL(x, y) (((x) + ((y) - 1)) / (y))
#define DIVFLOOR(x, y) (((x) + ((y) / 2)) / (y))
#define DIVROUND(x, y) ((x) - MOD(x, y) >= MOD(x, y) ? DIVCEIL(x, y) : DIVFLOOR(x, y))

inline int num(char c) {
  return c & 0xF;
}

int main() {
  string s;
  cin >> s;
  size_t n = s.length();

  long sum{};
  for (size_t i{0}; i < (1 << (n - 1)); ++i) {
    long calc{num(s[0])};
    for (size_t j{0}; j < (n - 1); ++j) {
      if (i & (1 << j)) {
        sum += calc;
        calc = 0;
      }
      calc *= 10;
      calc += num(s[j+1]);
    }
    sum += calc;
  }

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


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

d = [0 for _ in range(1, 55)]
for _ in range(0, m):
    a, b = map(int, input().split())

    d[a] += 1
    d[b] += 1

for i in range(1, n + 1):
    print(d[i])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << ele << endl
#define print10(ele) cout << fixed << setprecision(10) << ele << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int n;
  cin >> n;
  ivec a(n + 2);
  REP(i, n) cin >> a[i + 1];

  int d = 0;
  REP(i, n + 1) { d += abs(a[i] - a[i + 1]); }
  FOR(i, 1, n + 1) {
    int ans = d - abs(a[i - 1] - a[i]) - abs(a[i] - a[i + 1]) +
              abs(a[i - 1] - a[i + 1]);
    print(ans);
  }
  return 0;
}

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

int n,k;
bool vis[11];

bool cek(int x){
	while(x>0){
		int tmp = x%10;
		x/=10;
		if(vis[tmp]) return 0;
	}
	return 1;
}

int main(){
	cin >> n >> k;
	for(int i=0;i<k;i++){
		int x;
		cin >> x;
		vis[x] = 1;
	}
	for(int i=n;;i++){
		if(cek(i)){
			printf("%d\n",i);
			return 0;
		}
	}
	return 0;
}

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



int main(){
	string s;
	bool ok=false;
	cin >> s;
	
	for(int i=0;i<s.size();i++){
		if(s[i]=='C'){
			for(int j=i+1;j<s.size();j++){
				if(s[j]=='F') ok=true;
			}
		}
	}
	
	if(ok) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())

a = list(int(_) for _ in input().split()) 
b = list(int(_) for _ in input().split()) 

cnt = min(a[0],b[0])
if b[0] > a[0]:
	tmp = b[0] - a[0]
else:
	tmp = 0

for i in range(1,n):

	if tmp >= a[i]:
		tmp =  b[i]
		cnt += a[i]
	elif b[i]+tmp >= a[i]:
		tmp = b[i]+tmp - a[i]
		cnt += a[i]
	else:
		cnt += b[i]
		cnt += tmp
		tmp = 0

if tmp > 0:
	cnt += min(a[n],tmp)

print(cnt)

Measured memory_bytes: 18476
fun main(args: Array<String>) {
    var N = readLine()!!.toList().map(Char::toString).map(String::toLong)
    var sum = 0L
    N.map{n->
        sum += n
    }
    
    if((N.joinToString("")).toLong()%sum == 0L) println("Yes")
    else println("No")
    
}


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

using namespace std;

#define dump(n) cerr<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a)
{
	os<<'[';
	rep(i,a.size())
		os<<(i?" ":"")<<a[i];
	return os<<']';
}

ostream& operator<<(ostream& os,const pii& a)
{
	return os<<'('<<a.first<<','<<a.second<<')';
}

int getdist(pii a,pii b)
{
	return abs(a.first-b.first)+abs(a.second-b.second);
}

int main()
{
	for(int w,h;cin>>w>>h,w|h;){
		vs grid(h);
		rep(i,h) cin>>grid[i];
		
		pii start,goal;
		vector<vector<pii> > ps(5);
		rep(i,h) rep(j,w){
			if(grid[i][j]=='S')
				start=pii(i,j);
			if(grid[i][j]=='G')
				goal=pii(i,j);
			if(isdigit(grid[i][j]))
				ps[grid[i][j]-'1'].emplace_back(i,j);
		}
		
		vvi dp(5);
		rep(i,5)
			dp[i].resize(ps[i].size());
		
		pii res(INFTY,-1);
		rep(f,5){
			rep(i,5)
				fill(all(dp[i]),INFTY);
			rep(i,dp[(f+1)%5].size())
				dp[(f+1)%5][i]=getdist(start,ps[(f+1)%5][i]);
			repi(i,2,5){
				vector<pii> &ps0=ps[(f+i-1)%5],&ps1=ps[(f+i)%5];
				vi &dp0=dp[(f+i-1)%5],&dp1=dp[(f+i)%5];
				rep(j,dp0.size()) rep(k,dp1.size())
					dp1[k]=min(dp1[k],dp0[j]+getdist(ps0[j],ps1[k]));
			}
			int tmp=INFTY;
			rep(i,dp[(f+4)%5].size())
				tmp=min(tmp,dp[(f+4)%5][i]+getdist(ps[(f+4)%5][i],goal));
			res=min(res,pii(tmp,f));
		}
		if(res.second==-1)
			cout<<"NA"<<endl;
		else
			cout<<res.second+1<<' '<<res.first<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 2120
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define COUT(a) cout << (a);
#define ENDL cout << "\n";
int main() {
    long long k,a,b;
    scanf("%lld %lld %lld\n",&k,&a,&b);
    if(b-a <= 2) {COUT(k+1);return 0;}
    long long ans = a;
    if((k-a+1)%2 == 0) {
        for(int i=0; i<(k-a+1);i++) {
            if(i%2==0) ans-=a;
            else ans += b;
        }
    }else {
        for(int i=0; i<(k-a);i++) {
            if(i%2==0) ans-=a;
            else ans += b;
        }
        ans++;
    }
    COUT(ans)
}




Measured memory_bytes: 888
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int v=sc.nextInt();
			int e=sc.nextInt();
			int r=sc.nextInt();
			int INF=100000000;
			int[] s=new int[e];
			int[] t=new int[e];
			int[] cost=new int[e];
			for(int i=0; i<e; i++) {
				s[i]=sc.nextInt();
				t[i]=sc.nextInt();
				cost[i]=sc.nextInt();
			}
			int[] d=new int[v];
			for(int i=0; i<v; i++) {
				d[i]=INF;
			}
			d[r]=0;
			int count=0;
			int end=1;
			for(int k=0; k<v; k++) {
				count++;
				//System.out.println("k="+k);
				boolean update=false;
				for(int i=0; i<e; i++) {
					if(d[s[i]]<INF && d[t[i]]>d[s[i]]+cost[i]) {
						if(count==v) {
							end=0;
							break;
						}
						d[t[i]]=d[s[i]]+cost[i];
						update=true;
					}
					//System.out.println("d["+t[i]+"]="+d[t[i]]);
				}
				if(! update) {
					break;
				}
				if(end==0) {
					break;
				}
			}
			if(end==0) {
				System.out.println("NEGATIVE CYCLE");
			}
			else {
				for(int i=0; i<v; i++) {
					if(d[i]==INF) System.out.println("INF");
					else System.out.println(d[i]);
				}
			}
			
		}
	}
}


Measured memory_bytes: 36924
import sys
import heapq
N, M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append([v-1 + N, 1])
    G[u-1 + N].append([v-1 + 2*N, 1])
    G[u-1 + 2*N].append([v-1, 1])

S, T = map(int, input().split())

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[S-1] = 0
heapq.heappush(que, [0, S-1])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]
    
    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

if d[T-1] == INF:
    print(-1)
else:
    print(d[T-1]//3)

Measured memory_bytes: 122020
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
int main(void){
    int a,b,c;
    cin >> a >> b >> c;
    if(a*c < b){
        cout << c << endl;
    }else{
        cout << b/a << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  string s;
  cin>>s;
  int n = sz(s);

  int odd = 0, even = 0;
  vi ans(n,0);
  rep(i,n){
    if(s[i] == 'R'){
      if((i+1)%2) odd++;
      else even ++;
    }
    else{
      if((i+1)%2){
        ans[i] += odd;
        ans[i-1] += even;
      }
      else{
        ans[i]+= even;
        ans[i-1]+=odd;
      }
      even = odd = 0;
    }
  }

  drep(i,n){
    if(s[i] == 'L'){
      if((i+1)%2) odd++;
      else even ++;
    }
    else{
      if((i+1)%2){
        ans[i] += odd;
        ans[i+1] += even;
      }
      else{
        ans[i]+= even;
        ans[i+1]+=odd;
      }
      even = odd = 0;
    }
  }
  rep(i,n)cout<<ans[i]<<" ";
  cout<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(){
	int n;
	while(1){
		
		scanf("%d",&n);
		if(n==0)break;
		int i,j,cnt1=0,cnt2=1;
		for(i=0;i<n-2;i++){
			for(j=cnt2;j<n;j++){
				
				if((j*(j+1)-i*(i+1))==n*2){
					cnt1++;
					cnt2++;
					break;
					
				}
				if((j*(j+1)-i*(i+1))>n*2){
					cnt2++;
					break;
				}
			}
		}
		printf("%d\n",cnt1);
	}
	return 0;
}

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

inline int gcd(int a,int b){
    while(b!=0){
        a=a%b;
        swap(a,b);
    }
    return a;
}

int n,ans;
int cnt[205];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cnt[gcd(i,j)]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans+=cnt[j]*gcd(i,j);
        }
    }
    cout<<ans<<endl;

    return 0;
}

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

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

#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define sqrep(i,cc,n) for(long long i=cc;i*i<=n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>
 
using ll = long long;

const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const ll inf = 1001001001;
const ll e9  = 1000000000;
const ll mod = 1000000007;


int main() {
    ll a,b,v,w,t;
    cin >> a >> v >> b >> w >> t;
    if(v<=w){
        cout << "NO" << endl;
        return 0;
    }
    ll time = abs(a-b)/(v-w);
    if(abs(a-b)%(v-w)!=0)time++;
    if(time <= t){
        cout << "YES" << endl;
        return 0;
    }else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,ans=0,i;
    cin>>n;
    ll a;
    map<ll,int> f;
    for (i=0;i<n;i++)
    {
        cin>>a;
        f[a]++;
        ans+=f[a]&1?1:-1;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 6528
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>

using namespace std;
#define int long
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main() 
{
	int A, B;
	cin >> A >> B;
	cout << lcm(A, B);
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int r, g, b;
    cin >> r >> g >> b;
    
    if((g * 10 + b) % 4 == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define inf 1e9
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,c,d[35][35],co[505][505];
int cnt[5][35];
int ans=inf;
signed main(){
	cin>>n>>c;
	rep(i,c)rep(j,c)cin>>d[i][j];
	rep(i,n)rep(j,n){
		cin>>co[i][j];
		co[i][j]--;
		cnt[(i+j)%3][co[i][j]]++;
	}
	rep(i,c){
		rep(j,c){
			if(i==j)continue;
			rep(k,c){
				int memo=0;
				if(i==k||j==k)continue;
				rep(l,c){
					memo+=cnt[0][l]*d[l][i];
				}
				rep(l,c){
					memo+=cnt[1][l]*d[l][j];
				}
				rep(l,c){
					memo+=cnt[2][l]*d[l][k];
				}
				ans=min(ans,memo);
			}
		}
	}
	cout<<ans<<endl;
}



Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int m, f, r;
    while(cin >> m >> f >> r){
        if(m == -1 && f == -1 && r == -1){
            break;
        }else{
        if(m + f >= 80){
            cout << "A" << endl;
            continue;
        }else if(m + f >= 65 && m + f < 80){
            cout << "B" << endl;
            continue;
        }else if(m + f < 30 || m == -1 || f == -1){
            cout << "F" << endl;
            continue;
        }else if((m + f >= 50 && m + f < 65) || r >= 50){
            cout << "C" << endl;
            continue;
        }else if(m + f >= 30 && m + f < 50){
            cout << "D" << endl;
            continue;
        }
        }
    }
return 0;
}
    

Measured memory_bytes: 3080
#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    # f = set(factrial(e))
    # #print(p,f)
    # if p & f != set():
    #     pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    # p = p | f
for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 203784
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define MAX 10000000
#define n_MAX 101
#define c_MAX 11

typedef pair<int, pair<int, int> > edge;

inline int get_cost(edge e){
  return e.first;
}

inline int get_tickets(edge e){
  return -(e.second.first);
}

inline int get_station(edge e){
  return e.second.second;
}

inline edge make_edge(int cost, int tickets, int station){
  return make_pair(cost, make_pair(-tickets, station));
}

int main() {
 
  while( true ) {
    
    long long int c, n, m, s, d;
    cin >> c >> n >> m >> s >> d;
    if ( n == 0 ) break;
    
    long long int l[n_MAX][n_MAX] = {0};
    
    for ( long long int i = 0; i < m; i++ ) {
      long long int a, b, f;
      cin >> a >> b >> f;
      l[a][b] = l[b][a] = f;
    }
 
    long long int t[c_MAX][n_MAX];
    for ( long long int j = 0; j <= c; j++ ) {
      for ( long long int i = 1; i <= n; i++ ) {
	t[j][i] = MAX;
      }
    }
    
    priority_queue<edge, vector<edge>, less<edge> > queue;
    queue.push(make_edge(0, c, s));
    t[c][s] = 0;

    int ans = MAX;
    while(!queue.empty()){
      edge e = queue.top(); queue.pop();

      const int cost = get_cost(e);
      const int tickets = get_tickets(e);
      const int station = get_station(e);
      if(t[tickets][station] > cost){
	continue;
      }else if(station == d){
	ans = min(ans, cost);
      }
      

      for(long long int next = 1; next <= n; next++){
	if(l[station][next] == 0){
	  continue;
	}
	
	const int next_non_use_cost = cost + l[station][next];
	const int next_use_cost = cost + l[station][next] / 2;
 
	if(tickets > 0 && t[tickets - 1][next] > next_use_cost){
	  t[tickets - 1][next] = next_use_cost;
	  queue.push(make_edge(next_use_cost, tickets - 1, next));
	}
	
	if(t[tickets][next] > next_non_use_cost){
	  t[tickets][next] = next_non_use_cost;
	  queue.push(make_edge(next_non_use_cost, tickets, next));
	}
      }
    }
 
    cout << ans << endl;
  }
 
  return 0;
 
}

Measured memory_bytes: 1304
M,D=map(int,input().split())
count=0
for m in range(M):
    month=m+1
    for d in range(D):
        day=d+1
        if day//10>0:
            a,b=map(int,list(str(day)))
            if month==a*b and a>1 and b>1:
                count+=1
print(count)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

int main()
{

    int A;
    int B;
    scanf("%d",&A);
    scanf("%d",&B);
    if(A<=2*B)
    {
        printf("%d",0);
    }
    else
    {
        printf("%d",A-2*B);
    }
    return 0;
}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef vector<int> vi;
typedef vector<vi> vvi;

const int INF=123456;

vvi rotate(const vvi &v)
{
    int m=v.size();
    vvi ret(m,vi(m));

    rep(i,m)rep(j,m) ret[j][m-1-i]=v[i][j];

    return ret;
}

int main()
{
    int n,m;
    while(scanf(" %d %d",&n,&m),n)
    {
        vvi w(n,vi(n)), p(m,vi(m));
        rep(i,n)rep(j,n) scanf(" %d", &w[i][j]);
        rep(i,m)rep(j,m) scanf(" %d", &p[i][j]);

        int ax=INF, ay=INF;
        rep(rotates,4)
        {
            rep(i,n-m+1)rep(j,n-m+1)
            {
                bool ok=true;
                rep(y,m)rep(x,m)
                {
                    if(p[y][x]==-1) continue;
                    if(p[y][x]!=w[i+y][j+x]) ok=false;
                }

                if(!ok) continue;

                rep(y,m)rep(x,m)
                {
                    if(p[y][x]!=-1)
                    {
                        if(i+y<ay || (i+y==ay && j+x<ax))
                        {
                            ay=i+y;
                            ax=j+x;
                        }
                        break;
                    }
                }
            }

            p=rotate(p);
        }

        if(ax==INF) printf("NA\n");
        else printf("%d %d\n", ax+1,ay+1);
    }
    return 0;
}

Measured memory_bytes: 3268
H, W, K = map(int, input().split())
C = []
for _ in range(H):
    C.append([c for c in input()])

ans = 0
for maskH in range(1 << H):
    for maskW in range(1 << W):
        cnt = 0
        for h in range(H):
            for w in range(W):
                if (maskH >> h) & 1 == 1:
                    continue
                if (maskW >> w) & 1 == 1:
                    continue
                if C[h][w] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1

print(ans)


Measured memory_bytes: 73904
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

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

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

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

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

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

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[allow(unused_macros)]
macro_rules! ifv {
    ($cond:expr, $a:expr, $b:expr) => {
        if $cond {
            $a
        } else {
            $b
        }
    }
}

fn main() {
    input! {
        n: usize,
        p: [f64; n]
    };


    let mut dp = vec![vec![0.0; n+1]; 2];
    dp[0][0] = 1.0;
    for i in 0..n {
        let fr = i % 2;
        let to = 1 - fr;
        for j in 0..n+1 {
            let mut prob = 0.0;
            prob += dp[fr][j] * (1.0 - p[i]);
            if j >= 1 {
                prob += dp[fr][j-1] * p[i];
            }
            dp[to][j] = prob;
        }
    }

    let mut ans = 0.0;
    for i in (n/2+1)..n+1 {
        ans += dp[n%2][i];
    }
    println!("{}", ans);
}

Measured memory_bytes: 4352
N = int(input())
A = [int(a) for a in input().split()]

S = [0]
for a in A:
  S.append(S[-1]+a)

Min = 10**20
for i in range(1,N):
  Min = min(Min,abs((S[i]-S[0])-(S[N]-S[i])))
print(Min)


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

int main() {
  int K;
  cin>>K;
  int64_t Z=0;
  map<string,vector<int64_t>> m;
  vector<int64_t> em(26);
  m["#"]=em;
  vector<pair<int,string>> p(K);
  for(int i=0;i<K;i++){
    string S;
    cin>>S;
    int N=S.size();
    p[i]=make_pair(N,S);
  }
  sort(p.begin(),p.end());
  for(int i=0;i<K;i++){
    int N;
    string S;
    tie(N,S)=p[i];
    if(N==1){
      char a=S[0];
      m["#"][a-'a']++;
    }
    else{
      reverse(S.begin(),S.end());
      string T="";
      vector<int> q(26);
      for(int j=0;j<N;j++){
        int b=S[j]-'a';
        q[b]++;
      }
      if(m.count("#")){
        vector<int64_t> vec=m["#"];
        for(int l=0;l<26;l++){
          if(q[l]!=0){
            Z+=vec[l];
          }
        }
      }
      for(int j=0;j<N-2;j++){
        T+=S[j];
        q[S[j]-'a']--;
        if(m.count(T)){
          vector<int64_t> vec=m[T];
        for(int l=0;l<26;l++){
          if(q[l]!=0){
            Z+=vec[l];
          }
        }
        }
      }
      T+=S[N-2];
      if(!m.count(T)){
        m[T]=em;
      }
      m[T][S[N-1]-'a']++;
    }
  }
  cout<<Z<<endl; 
}

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

using ll = long long;

int main() {
    int n, s;
    while(cin >> n >> s, n) {
        vector<vector<ll>> dp(n+1, vector<ll>(s+1, 0));
        dp[0][0] = 1;
        for(int i=0; i<=100; ++i) {
            for(int j=n-1; j>=0; --j) {
                for(int k=0; k+i<=s; ++k) {
                    dp[j+1][k+i] += dp[j][k];
                }
            }
        }
        cout << dp[n][s] << endl;
    }
}


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

int main(){
  int N,M;
  cin >> N >> M;
  vector <int> A(N);
  int S=0;
  
  for(int i=0;i<N;i++){
    cin >> A.at(i);
    S += A.at(i);
  }
  
  sort(A.begin(),A.end(),greater<int>());
  if(A[M-1]>=S/4.0/M){
    cout << "Yes" << endl;
  } else cout << "No" << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
  typedef long long ll;
#define pii  pair<int,int>
#define vpii vector<pii>
#define vll  vector<ll>
#define vi  vector<int>
#define pb push_back
#define f  first
#define s  second
#define all v.begin(),v.end()
#define fio ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
typedef unsigned long long ulll;
 
using namespace std ;
int main () {

  int a,b,c;
  cin>>a>>b>>c;
  
  if(a*b>c)
  cout<<c;
  
  else
  cout<<a*b;
  
   
  return 0;
}

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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
//gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1 << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define unique(x) (x).erase(unique(x).begin(),(x).end()),(x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) ((n) * ((n) + 1)) / 2
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).push_front(a)
#define eb(x, a) (x).emplace_back(a)
#define F first
#define S second
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T> //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <class T>
bool chmax(T &a, const T &b) //最大値更新 返り値はbool
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) //最小値更新 返り値はbool
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, m, a, b, cnt = 0;
    cin >> n >> m;

    vector<int> h(n);

    rep(i, 0, n) cin >> h[i];
    vector<bool> y;
    y.resize(n, false);

    rep(i, 0, m)
    {
        cin >> a >> b;
        --a, --b;
        if (h[a] > h[b])
            y[b] = true;
        else if (h[a] < h[b])
            y[a] = true;
        else
            y[a] = y[b] = true;
    }

    rep(i, 0, n)
    {
        if (y[i] == false)
            ++cnt;
    }

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

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

using namespace std;

int main() {
    int x=10;
    int y=25;
    long long z=x+y;
    cin>>x>>y;
    vector<long long> v(x);
    z=0;
    for(int i=0;i<x;i++)
   { cin>>v[i];
    
   }
   sort(v.begin(),v.end());
   reverse(v.begin(),v.end());
   for(int i=y;i<x;i++)
 z+=v[i];

    cout<<z;
}

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

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

int main() {
    int N, K;
    cin >> N >> K;
    vector<double> Ain(N);
    REP(i, N){
        cin >> Ain[i];
    }

    long ok = 1e9+1;
    long ng = 0;
    vector<double> A(N);
    while(abs(ok - ng) > 1){

        REP(i, N){
            A[i] = Ain[i];
        }  

        long mid = (ok + ng) / 2;
        bool flag = true;
        long count = 0;
        REP(i, N){
            if(A[i]>mid){
                count += floor(A[i] / mid);
                A[i] /= ceil(A[i] / mid);
            }
            if(count > K){
                flag = false;
                break;
            }
        }
        if(flag)ok = mid;
        else ng = mid;
    }
    cout << ok << "\n";
    return 0;
}

Measured memory_bytes: 6488
#include <stdio.h>
#define NIL -1
#define MAX 10000

void print(int);


typedef struct{
  int left,right,parent;
}node;

node T[MAX];
int n,D[MAX];
int H[MAX];

int main(){
  int i,j;
  int a,l,r;
  int root;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].parent = NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d %d %d",&a,&l,&r);
    T[a].left = l;
    T[a].right = r;
    if( l != NIL) T[l].parent = a;
    if( r != NIL) T[r].parent = a;
  }
  for(i = 0; i <n; i++){
    if(T[i].parent == NIL) root = i;
  }
  setDepth(root,0);
  setHeight(root);

  for(i = 0; i <n; i++) print(i);
  
}

int setDepth(int u,int d){
  if(u == NIL) return NIL;
  D[u] = d;
  setDepth(T[u].left,d + 1);
  setDepth(T[u].right, d + 1);
}

int setHeight(int u){
  int h1=0;
  int h2=0;
  if(T[u].left != NIL) h1 = setHeight(T[u].left) +1;
  if(T[u].right != NIL) h2 = setHeight(T[u].right) +1;
  if(h1>h2){
    H[u] = h1;
  }
  else{
    H[u] = h2;
  }
    return H[u];
}

int getSibling(int u){
  if(T[u].parent == NIL) return NIL;
  if(T[T[u].parent].right != u && T[T[u].parent].right !=NIL)
    return T[T[u].parent].right;
  if(T[T[u].parent].left != u &&T[T[u].parent].left !=NIL )
    return  T[T[u].parent].left;
  return NIL;
}

void print(int u){
  int i,c;
  int deg=0;
  printf("node %d: parent = %d, ",u,T[u].parent);
  if(T[u].right != NIL) deg++;
  if(T[u].left != NIL) deg++;
  printf("sibling = %d, degree = %d, ",getSibling(u),deg);
  printf("depth = %d, height = %d, ",D[u],H[u]);
  
  if(T[u].parent==NIL) printf("root");
  else if(T[u].left == NIL && T[u].right == NIL) printf("leaf");
  else printf("internal node");
  printf("\n");
}




Measured memory_bytes: 2048
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
	string s, t;  cin >> s >> t;

  	if(s.size() < t.size()){
		cout << "UNRESTORABLE" << endl;
      	return 0;
    }
	int ins_point = -1;
	for(int i = 0 ; i <= s.size() - t.size() ; i++){
			
			bool flag = true;
			for(int j = 0 ; j < t.size() ; j++){
					if(s[i + j] != '?' && s[i + j] != t[j]){
							flag = false;
							break;
					}
			}

			if(flag)  ins_point = i;
	}

	if(ins_point == -1)  cout << "UNRESTORABLE" << endl;
	else{
			for(int i = 0 ; i < s.size() ; i++){
					if(i == ins_point){
							for(int j = 0 ; j < t.size() ; j++)	cout << t[j];
							i += t.size() - 1;
							continue;
					}
					if(s[i] != '?')   cout << s[i];
					else              cout << 'a';
			}
			cout << endl;
	}

	return 0;
}


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

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	int H, W, K;
	cin >> H >> W >> K;
	vector<string> board(H);
	rep(i,0,H) cin >> board[i];
	int si = -1, sj = -1;
	rep(i,0,H) rep(j,0,W) if (board[i][j] == 'S') si = i, sj = j;
	queue<pii> q;
	q.push(pii(si, sj));
	vector<vi> dists(H, vi(W, -1));
	dists[si][sj] = 0;
 
	vector<pii> onestep;
 
	while (!q.empty()) {
		pii pa = q.front();
		q.pop();
		int di = dists[pa.first][pa.second];
		if (di <= K) onestep.push_back(pa);
		rep(d,0,4) {
			pii pa2 = pa;
			if (d == 0) pa2.first++;
			if (d == 1) pa2.second++;
			if (d == 2) pa2.first--;
			if (d == 3) pa2.second--;
			if (pa2.first < 0 || pa2.second < 0 || pa2.first >= H || pa2.second >= W) continue;
			if (board[pa2.first][pa2.second] == '#') continue;
			if (dists[pa2.first][pa2.second] != -1) continue;
			dists[pa2.first][pa2.second] = di+1;
			q.push(pa2);
		}
	}
 
	dists.assign(H, vi(W, -1));
	trav(pa, onestep) {
		q.push(pa);
		dists[pa.first][pa.second] = 0;
	}
 
	while (!q.empty()) {
		pii pa = q.front();
		q.pop();
		int di = dists[pa.first][pa.second];
		if (di <= K) onestep.push_back(pa);
		rep(d,0,4) {
			pii pa2 = pa;
			if (d == 0) pa2.first++;
			if (d == 1) pa2.second++;
			if (d == 2) pa2.first--;
			if (d == 3) pa2.second--;
			if (pa2.first < 0 || pa2.second < 0 || pa2.first >= H || pa2.second >= W) continue;
			// if (board[pa2.first][pa2.second] == '#') continue;
			if (dists[pa2.first][pa2.second] != -1) continue;
			dists[pa2.first][pa2.second] = di+1;
			q.push(pa2);
		}
	}
 
	int res = INT_MAX;
	rep(i,0,H) rep(j,0,W) {
		if (i == 0 || j == 0 || i == H-1 || j == W-1) {
			res = min(res, dists[i][j]);
		}
	}
 
	cout << (res + K-1) / K + 1 << endl;
 
	exit(0);
}

Measured memory_bytes: 26992
import java.util.*;
import java.io.*;
import java.math.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		for(int sss = 0; sss < m; sss++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int n = sc.nextInt();
			int max = 0;
			for(int ss = 0; ss < n; ss++) {
				int type = sc.nextInt();
				double c = sc.nextDouble();
				int d = sc.nextInt();
				if(type == 0) {
					//tanri
					int A = a;
					int B = 0;
					for(int i = 0; i < b; i++) {
						B += A * c;
						A -= d;
					}
					max = Math.max(A + B,max);
				}
				else {
					int A = a;
					for(int i = 0; i < b; i++) {
						A += A*c;
						A -= d;
					}
					max = Math.max(A, max);
				}
			}
			System.out.println(max);
		}
	}
}

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

int main(){
    constexpr unsigned long MOD = 1000000007;
    unsigned long N;
    cin >> N;
    unsigned long dp{N};
    vector<unsigned long> sum(N + 3, (N - 1) * N % MOD);
    sum[3] = (N * N - 1) % MOD;
    for(unsigned long i = 4; i != N + 3; ++i)sum[i] = (sum[i - 1] - 1 + ((dp += sum[i - 3]) %= MOD)) % MOD;
    cout << dp << endl;
    return 0;
}

Measured memory_bytes: 8064
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<functional>
#include<queue>
#include<map>
using namespace std;
map<int, int>M; vector<int>X; int n, p, cnt;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> p; M[p]++; X.push_back(p); }
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i = 0; i < X.size(); i++) { if (M[X[i]] % 2 == 1)cnt++; }
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 5368
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        TreeMap<String, Integer> map = new TreeMap<String, Integer>();
        int max = 0;
        for(int i=0;i<n;i++){
            String s = sc.next();
           if(map.containsKey(s)){
               int t = map.get(s) + 1;
               map.put(s, t);
               max = Math.max(t, max);
           } else {
               map.put(s, 1);
               max = Math.max(max,1);
           }
        }

        for(Map.Entry<String, Integer> entry :map.entrySet()){
            if(entry.getValue().equals(max)){
                System.out.println(entry.getKey());

            }
        }
    }
}


Measured memory_bytes: 79120
# -*- coding: utf-8 -*-
"""
Created on Sat May 26 21:05:34 2018

@author: maezawa
"""

n = int(input())
s = input()

ans = 0
for i in range(1,n):
    s1 = set(s[:i])
    s2 = set(s[i:])
    #print(s1)
    #print(s2)
    cnt = len(s1.intersection(s2))
    if ans < cnt:
        ans = cnt

print(ans)

    

Measured memory_bytes: 3060
#N=gets.to_i
#S=gets.chomp
#A=(0...N).map{gets.to_i}
#sum=A.inject(&:+)
#B=gets.split.map(&:to_i)


M,K=gets.split.map(&:to_i)
if K>=2**M || (K==1 && M==1)
  puts -1
  exit(0)
end
if K==0
  puts (0..2**M-1).to_a+(0..2**M-1).to_a.reverse
  exit(0)
end
temp=(1..(K-1)).to_a+((K+1)..((2**M)-1)).to_a
puts [0,K,0]+temp+[K]+temp.reverse



Measured memory_bytes: 9084
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a == b)
			System.out.println("Draw");
		else if (a == 1 || (a > b && b != 1))
			System.out.println("Alice");
		else
			System.out.println("Bob");
		sc.close();
	}
}

Measured memory_bytes: 21588