akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>

int main(){
	int n, k, i, co=0;
	scanf("%d%d", &n, &k);
	int *h;
	h=(int*)malloc(sizeof(int)*n);
	for(i=0;i<n;i++) scanf("%d", &h[i]);
	for(i=0;i<n;i++){
		if(h[i]>=k) co++;
	}
	printf("%d", co);
	free(h);
	return 0;
}

Measured memory_bytes: 512
from collections import deque,defaultdict,Counter
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from bisect import bisect_left,bisect_right
from math import sqrt,gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float('inf')

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse=False):
    data.sort(key=lambda x:x[col],reverse=revese)
    return data

def mymax(data):
    M = -1*float('inf')
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float('inf')
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def mydictvaluesort(dictionary):
    return sorted( dictionary.items(), key=lambda x:x[1] )

def mydictkeysort(dictionary):
    return sorted( dictionary.items(), key=lambda x:x[0] )

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(' ')
        elif type(ls[0])==str:
            print(' '.join(ls))
        elif type(ls[0])==int:
            print(' '.join(map(str,ls)))
        else:
            print('Output Error')
    else:
        if len(ls)==0:
            print('')
        elif type(ls[0])==str:
            print(''.join(ls))
        elif type(ls[0])==int:
            print(''.join(map(str,ls)))
        else:
            print('Output Error')

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

mod = 10**9 + 7

n = I()

m = INF
for i in range(n//2):
    a = i + 1
    b = n - a
    a = str(a)
    b = str(b)
    a = list(a)
    b = list(b)
    a = sum(list(map(int,a)))
    b = sum(list(map(int,b)))
    m = min(m,a+b)
print(m)

Measured memory_bytes: 79040
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll n,k,s;
vector<bool> used;
vector<pair<pll,ll>> A;

vector<ll> Ring;
vector<ll> cnt;
ll ans=-E;

ll cross(ll a,ll b){
    ll x=abs(A[a].F.F-A[b].F.F);
    ll y=abs(A[a].F.S-A[b].F.S);
    ll z=abs(A[a].S-A[b].S);
    if(x>=s || y>=s || z>=s){return 0;}
    if(A[a]==A[b]){return 6*s*s;}
    return ((s-x)*(s-y)+(s-x)*(s-z)+(s-y)*(s-z))*2;
}


void dfs(ll w,ll p=-1){
    Ring.push_back(w);
    used[w]=true;
    for(int i=0;i<n;i++){
        if(i==w || i==p || used[i]){continue;}
        if(cross(i,w)){dfs(i,w);}
    }
}

void solve(ll w){
    Ring.clear();
    dfs(w);
    if(Ring.size()<k){return;}
    if(k==1){ans=0; return;}
    if(cross(Ring[0],Ring.back())){
        if(Ring.size()==k){
            ll ret=0;
            for(int i=1;i<k;i++){ret+=cross(Ring[i],Ring[i-1]);}
            if(k!=2){
                ret+=cross(Ring[0],Ring.back());
            }
            ans=max(ans,ret);
            return;
        }
        else{
            for(int i=0;i<Ring.size();i++){
                ll ret=0;
                for(int t=1;t<k;t++){
                    ret+=cross(Ring[(i+t)%Ring.size()],Ring[(i+t-1)%Ring.size()]);
                }
                ans=max(ans,ret);
            }
            return;
        }
    }
    else{
        for(int i=0;i+k<=Ring.size();i++){
            ll ret=0;
            for(int t=1;t<k;t++){
                ret+=cross(Ring[i+t],Ring[i+t-1]);
            }
            ans=max(ans,ret);
        }
    }
}



int main(){
    while(cin>>n>>k>>s){
        if(n==0){break;}
    used.resize(n);
    for(int i=0;i<n;i++){used[i]=false;}
    A.resize(n);
    cnt.resize(n);
    for(int i=0;i<n;i++){cnt[i]=0;}
    for(auto &I:A){cin>>I.F.F>>I.F.S>>I.S;}
    for(int i=0;i<n;i++){
        for(int t=0;t<n;t++){
            if(i!=t){cnt[i]+=(cross(i,t)?1:0);}
        }
    }
    ans=-E;
    for(int i=0;i<n;i++){
        if(!used[i] && cnt[i]<=1){solve(i);}
    }
    for(int i=0;i<n;i++){
        if(!used[i]){solve(i);}
    }
    if(ans==-E){cout<<-1<<endl;}
    else{cout<<s*s*6*k-ans<<endl;}
    }
    
    return 0;
}



Measured memory_bytes: 3184
#include<cstdio>
#include<cstdlib>
#include<vector>


using namespace std;
using vi=vector<int>;

#define F_SIZE 100


void calc(vi&x, vi&y, vi&h, int&cx, int&cy, int&ch)
{
	int n=x.size();
	int b;

	for(b=0;b<n;b++)
	{
		if(h[b]>0) break;
	}

	for(cx=0;cx<=F_SIZE;cx++)
	{
		for(cy=0;cy<=F_SIZE;cy++)
		{
			int is_ok=1;

			ch=h[b]+abs(cx-x[b])+abs(cy-y[b]);
			for(int i=0;i<n;i++)
			{
				if(max(ch-abs(cx-x[i])-abs(cy-y[i]), 0)!=h[i]) is_ok=0;
			}
			if(is_ok) return;
		}
	}
}


int main(void)
{
	int n;

	while(scanf("%d", &n)==1)
	{
		vi x(n), y(n), h(n);

		for(int i=0;i<n;i++)
		{
			scanf("%d%d%d", &x[i], &y[i], &h[i]);
		}

		int cx=-1, cy=-1, ch=-1;
		calc(x, y, h, cx, cy, ch);

		printf("%d %d %d\n", cx, cy, ch);
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

//INT_MAX	2,147,483,647 = 2*1.0e9

int main(){
  int N;
  cin >> N;

  vector<int> A(N);
  for(int i = 0; i < N; i++) cin >> A[i];

  int max = A[0];
  int sec_max = 0;

  for(int i = 1; i < N; i++){
    if(A[i] >= max){
      sec_max = max;
      max = A[i];
      continue;
    } else if(A[i] > sec_max){
      sec_max = A[i];
    }
  }

  for(int i = 0; i < N; i++){
    if(A[i] == max){
      cout << sec_max << endl;
    } else {
      cout << max << endl;
    }
  }

  return 0;
}



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

#define SIZE 100

void push(int);
int pop();
int top();
int size();
int free_mem();
int empty();
void clear();

int stack[SIZE];
int sp=0;

void push(int x){
	if(sp==SIZE){
		printf("Overflow\n");
		exit(1);
	}
	stack[sp++] = x;
}

int pop(){
	if(sp==0){
		printf("Underflow\n");
		exit(1);
	}
	return stack[--sp];
}

int top(){
	if(sp==0){
		printf("Nodata\n");
		exit(1);
	}
	return stack[sp-1];
}

int size(){
	return sp;
}

int free_mem(){
	return SIZE-sp;
}

int empty(){
	return sp==0;
}

void clear(){
	sp=0;
}

int main(void)
{
	char c;
	int a,b;
	int num;
	while((c=getchar())!='\n'){
		switch (c){
		case '+':
			a=pop();
			b=pop();
			push(a+b);
			break;
			
		case '-':
			a=pop();
			b=pop();
			push(b-a);
			break;
			
		case '*':
			a=pop();
			b=pop();
			push(a*b);
			break;
			
		case ' ':
			break;
			
		default :
			num=c-'0';
			while((c=getchar())!=' '){
				num=num*10+c-'0';
			}
			push(num);
		}
	}
	printf("%d\n",pop());
}

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

signed main(){
  int n; cin >> n;
  n--;
  vector<string> now{"a"};
  while(n--){
    vector<string> next;
    for(auto const &s: now){
      int c = *max_element(s.begin(),s.end()) - 'a';
      for(int i=0; i <= c+1; i++){
        next.push_back(s + (char)(i + (int)'a'));
      }
    }
    now = next;
  }
  
  sort(now.begin(), now.end());
  for(auto const &s: now) cout << s << endl;
  
  return 0;
}


Measured memory_bytes: 9116
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const int mod = 1e9+7;
int sum[30],Ans=1;
char s[100100];
int main(){
    int n,m,i,j,k;
    cin>>n;
    scanf("%s",s);
    for(i=0;i<n;i++)sum[s[i]-'a']++;
    for(i=0;i<26;i++)
      Ans=1ll*Ans*(sum[i]+1)%mod;
    cout<<Ans-1<<endl;
	return 0;
}


Measured memory_bytes: 384
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)



        
def main(): #startline--------------------------------------------
    N,W = map(int,input().split())
    wv = [list(map(int,input().split())) for i in range(N)]
    w = [wv[i][0] for i in range(N)]
    v = [wv[i][1] for i in range(N)]
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(W):
        dp[N][i] = 0
    for i in range(N-1,-1,-1):
        for j in range(W+1):
            if j < w[i]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])
    print(dp[0][W])
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 123784
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<map>
#include<numeric>
//#include <bits/stdc++.h>
#include<cstring>
#include<iostream>
#include<functional>
using namespace std;
int main() {

	int N, A, B;

	cin >> N >> A >> B;
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		int tot = 0;
		int remain = i;
		while (remain != 0) {
			tot += remain % 10;
			remain = remain / 10;
			//cout << i << " " << tot << " " << remain << endl;
		}
		if (tot >= A && tot <= B)
			ans += i;


	}
	cout << ans << endl;
	//cin >> N;


	return 0;
}

Measured memory_bytes: 256
m, n, o = map(int, input().split()) 
y = list(map(int, input().split())) 
z = list(map(int, input().split())) 
a, b = [0], [0]
for i in range(m):
    a.append(a[i] + y[i])
for i in range(n):
    b.append(b[i] + z[i])
ans, j = 0, n
for i in range(m + 1):
    if a[i] > o:
        break
    while b[j] > o - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)


Measured memory_bytes: 47368
N, K = map(int, input().split())

A = [0]*N

for i in range(K):
  d = int(input())
  B = list(map(int, input().split()))
  for j in range(d):
    a = B[j]
    A[a-1] += 1
    
ans = 0
    
for i in range(N):
  if A[i] == 0:
    ans += 1
    
print(ans)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,k;
int a[N];
long long dp[N];

long long f(int idx){
  if (idx==n-1) return 0;
  long long &ret = dp[idx];
  if (ret != -1) return ret;
  ret = 1e18;
  for(int i=idx+1; i<=min(idx+k,n-1); i++){
    ret = min(ret, f(i)+abs(a[idx]-a[i]));
  }
  return ret;
}

int main(){
   scanf("%d%d",&n,&k);
   for(int i=0; i<n; i++){
     scanf("%d",a+i);
   }
   memset(dp,-1,sizeof dp);
   cout << f(0) << endl;
}

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

using namespace std;

#define int long long
#define MOD 1000000007

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}

//typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
//#define int long long

int N,M;
vector<int> L,R;

signed main()
{
    cin>>N>>M;
    L.resize(M);
    R.resize(M);

    rep(i,M){
        cin>>L[i]>>R[i];
    }

    sort(all(L));
    sort(all(R));

    int min = R[0];
    int max = L[L.size()-1];

    if(min>=max){
        cout <<min-max+1<<endl;
    }
    else{
        cout<<0<<endl;
    }
    return 0;
}


Measured memory_bytes: 1792
#pragma region include
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <cstdio>
#include <tuple>
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
#define MOD (1e9+7)
#define INF (1e9)
#define LLINF (4e18)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
void input() {}
template<typename... R> void input(int& f, R&... r) { scanf("%d", &f); input(r...); }
template<typename... R> void input(double& f, R&... r) { scanf("%lf", &f); input(r...); }
template<typename... R> void input(ll& f, R&... r) { scanf("%lld", &f); input(r...); }
template<typename... R> void input(char& f, R&... r) { scanf("%c", &f); input(r...); }
template<typename... R> void input(string& f, R&... r) { cin >> f; input(r...); }
template<typename T, typename... R> void input(vector<T>& f, R&... r) { REP(i, f.size())input(f[i]); input(r...); }
#pragma endregion

int main() {
    int N, T; input(N, T);
    vector<int> a(N),m(N,0); input(a);
    m[N - 1] = a[N - 1];
    FOR(i, 1, N) {
        m[N - 1 - i] = max(a[N - 1 - i], m[N - i]);
    }
    int cnt = 0, t = -1;
    REP(i, N) {
        if (t == m[i] - a[i]) {
            cnt++;
        }
        else if (t < m[i] - a[i]){
            cnt = 1;
            t = m[i] - a[i];
        }
    }
    cout << cnt << endl;
    getchar(); getchar();
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;
const ll mod = 1e9 + 7;

int main() {
  vector <int> a(3);
  cin >> a[0] >> a[1] >> a[2];
  sort(all(a));
  if (a[0] != a[2] && (a[0] == a[1] || a[1] == a[2])) {
	  cout << "Yes" << endl;
	} else {
	  cout << "No" << endl;
	}
  return 0;
}


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

public class Hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            var a = new List<int>();
            goDfs(n, n, a);
        }
    }
    public static void goDfs(int rest, int prev, List<int> a)
    {
        if (rest == 0) { print(a); return; }
        var imin = Math.Min(rest, prev);
        for (int i = imin; i >= 1; i--)
        {
            a.Add(i);
            goDfs(rest - i, i, a);
            a.RemoveAt(a.Count() - 1);
        }
    }
    public static void print(List<int> a)
    {
        var aL = a.Count();
        for (int i = 0; i < aL - 1; i++) Console.Write("{0} ", a[i]);
        Console.WriteLine(a[aL - 1]);
    }
}



Measured memory_bytes: 9644
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
#include <climits>
using namespace std;
#define _GLIBCXX_DEBUG
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vit vector<lint>::iterator
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define mod 1000000007
#define graph_set(n) struct edge{int to,int cost;} vector<edge> G((n))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define range(x,y) ((x) >= 0 && (x) < h && (y) >= 0 && (y) < w)
#define pyes cout << "Yes" << endl
#define pno cout << "No" << endl
typedef vector<long long> vi;
typedef vector<pair<long long, long long>> vp;
typedef vector<vector<long long>> vvi;
typedef pair<long long, long long> pi;
typedef long long lint;
typedef long long ll;
lint qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
lint qp(int a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
lint gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
long long INF = 1e14;

/********************/
#define MAX_V 105
int main() {
	int n, k; cin >> n >> k;
	if (2*k > (n - 1)*(n - 2)){
		cout << -1 << endl; return 0;
	}
	vp G;
	rep(n - 1) G.pb(pi(n, i + 1));

	int c = (n - 1)*(n - 2) / 2 - k;
	if(c == 0) goto B;
	for (int i = 1; i <= n - 2; i++) {
		for (int j = i + 1; j <= n - 1; j++) {
			G.pb(pi(i, j));
			c--;
			if (c == 0) goto B;
		}
	}
B:;
	cout << G.size() << endl;
	rep(G.size()) {
		cout << G[i].ff << " " << G[i].ss << endl;
	}
	return 0;
}

Measured memory_bytes: 512
def modpow2(n, m)
  if n == 0
    1
  else
    if n % 2 == 1
      ((modpow2(n / 2, m) ** 2) * 2) % m
    else
      (modpow2(n / 2, m) ** 2) % m
    end
  end
end

n = gets.chomp.to_i
x = gets.chomp

count = x.count('1')

modpos = x.chars.map(&:to_i).inject(0) { |acc, i| (acc * 2 + i) % (count + 1) }
modneg = x.chars.map(&:to_i).inject(0) { |acc, i| (acc * 2 + i) % (count - 1) } if count > 1

(1..n).each do |i|
  if x[i - 1] == '1' && count == 1
    puts 0
  else    
    t = if x[i - 1] == '1'
        (modneg - modpow2(n - i, count - 1)) % (count - 1)
      else
        (modpos + modpow2(n - i, count + 1)) % (count + 1)
      end

    answer = 1
    while t > 0
      t = t % (t.to_s(2).count('1'))
      answer += 1
    end
    puts answer
  end
end



Measured memory_bytes: 46212
#include<stdio.h>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#include<string>
#include<string.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

struct edge{int to, flow, cap, rev;};

const int N = 100;
const int MX = 2e4;
const int SINK = MX;
const int SRC = SINK + 1;

vector<edge> lst[MX + 5];

void addEdge(int a, int b, int cap){
	int sa = lst[a].size(), sb = lst[b].size();
	lst[a].pb({b, 0, cap, sb});
	lst[b].pb({a, 0, 0, sa});
}

char grid[N + 5][N + 5];
int id[N + 5][N + 5];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int level[MX + 5];
int lastEdge[MX + 5];
int h, w;

bool bfs(){
	queue<int> q;
	memset(level, -1, sizeof level);

	q.push(SRC);
	level[SRC] = 0;

	while(!q.empty()){
		int cur = q.front(); q.pop();
		for(int i = 0; i < lst[cur].size(); ++i){
			edge &e = lst[cur][i];
			if(level[e.to] != -1)continue;
			if(e.flow < e.cap){
				level[e.to] = level[cur] + 1;
				q.push(e.to);
			}
		}
	}

	return level[SINK] != -1;
}

int dfs(int now, int flow){
	if(now == SINK)return flow;

	int ret = 0;
	for(int &i = lastEdge[now]; i < lst[now].size(); ++i){
		edge &e = lst[now][i];
		if(e.flow == e.cap)continue;
		if(level[e.to] == level[now] + 1){
			int curr = dfs(e.to, min(flow, e.cap - e.flow));
			if(curr > 0){
				e.flow += curr;
				lst[e.to][e.rev].flow -= curr;
				flow -= curr;
				ret += curr;
				if(flow == 0)return ret;
			}
		}
	}

	return ret;
}

int maxFlow(){
	int ret = 0;
	while(bfs()){
		memset(lastEdge, 0, sizeof lastEdge);
		ret += dfs(SRC, N * N * 10);
	}
	return ret;
}

bool inRange(int x, int y){
	return x >= 0 && y >= 0 && x < h && y < w;
}


int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> w;
	int cnt = 0;
	for(int i = 0; i < h; ++i){
		for(int j = 0; j < w; ++j){
			cin >> grid[i][j];
			id[i][j] = cnt++;
		}
	}

	bool sideExist = false;

	for(int i = 0; i < h; ++i){
		for(int j = 0; j < w; ++j){

			if(grid[i][j] == '.')addEdge(id[i][j] + h * w, id[i][j], 1);
			else addEdge(id[i][j] + h * w, id[i][j], MX + 5);

			for(int k = 0; k < 4; ++k){
				int nx = i + dx[k];
				int ny = j + dy[k];
				if(!inRange(nx, ny)) addEdge(id[i][j], SINK, 1);
				else addEdge(id[i][j], id[nx][ny] + h * w, 1);
			}
			if(grid[i][j] == 'X'){
				if(i == 0 || j == 0 || i == h - 1 || j == w - 1)
					sideExist = true;
				addEdge(SRC, id[i][j] + h * w, MX + 5);
			}
		}
	}

	if(sideExist)cout << -1 << endl;
	else cout << maxFlow() << endl;
}

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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>string join(const vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T>ostream& operator<<(ostream& o, const vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, const vector<vector<T> >&vv)
{int l=vv.size();if(l){o<<endl;rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const ll INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    int n; cin >> n;
    vi dp(n+1);
    dp[0] = dp[1] = 1;
    REP(i,2,n+1) dp[i] = dp[i-1] + dp[i-2];
    cout << dp[n] << endl;
    return 0;
}


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

int main(){

	long long N, A, B;

	cin >> N >> A >> B;

	if((B - A)%2 == 0){
		cout << (B-A)/2 << endl;
	}else{
		if((N-A) >= B){
			cout << A + (B - A -1)/2 << endl;
			//cout << B -1 << endl;
		}else{
			cout << (N-B)+1 + (B-A-1)/2 <<endl;
			//cout << (N-A) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
for i in range(N):
	if B[i]<A[i]:
		ans+=B[i]
	else:
		if A[i+1]>B[i]-A[i]:
			ans+=B[i]
			A[i+1]-=B[i]-A[i]
		else:
			ans+=A[i+1]+A[i]
			A[i+1]=0
print(ans)

Measured memory_bytes: 18476
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926535
/*
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
*/
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1
#define LINF 1000000000000000001 // 1e18+1

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
//---------------------------
class UnionFind {
private:
	vector<int> parent;
	vector<int> height;
	vector<int> m_size;

public:
	UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	void init(int size_) {
		parent.resize(size_);
		height.resize(size_, 0);
		m_size.resize(size_, 0);
		for (int i = 0; i < size_; ++i) parent[i] = i;
	}
	int find(int x) {
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		int t = size(x) + size(y);
		m_size[x] = m_size[y] = t;
		if (height[x] < height[y]) parent[x] = y;
		else parent[y] = x;
		if (height[x] == height[y]) ++height[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		if (parent[x] == x) return m_size[x];
		return size(parent[x] = find(parent[x]));
	}
};

int N,K,L;
int p[200000],q[200000],r[200000],s[200000];
int a[300000],b[300000];
map<pair<int, int>, int> mp;
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  cin>>N>>K>>L;
  UnionFind ufk(N);
  UnionFind ufl(N);
  REP(i,K){
   cin>>p[i]>>q[i];
   p[i]--;q[i]--;
   ufk.unite(p[i], q[i]);
  }
  REP(i,L){
    cin>>r[i]>>s[i];
    r[i]--;s[i]--;
    ufl.unite(r[i], s[i]);
  }
  REP(i,N){
    a[i]=ufk.find(i);
    b[i]=ufl.find(i);
    mp[make_pair(a[i], b[i])]++;
  }
  REP(i,N){
    cout<< mp[make_pair(a[i], b[i])] <<" \n"[i==N-1];
  }

  return 0;
}


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

#define ll long long
#define p_q priority_queue
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main(){
    ll a,b,k;
    cin>>a>>b>>k;
    if(a-k<=0){
        cout<<0<<" ";
        if((b+a)-k<=0){
            cout<<0;
        }else{
            cout<<(b+a)-k;
        }
    }else{
        cout<<a-k<<" ";
        cout<<b<<endl;
    }
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N];
int main()
{
	int n; 
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	int l = 1, r = 1, tmp = 0; 
	ll sum = 0;
	while (r <= n)
	{
		while ((a[r] ^ tmp) == (a[r] + tmp) && r <= n)
		{
			tmp ^= a[r];
			r++;
		}
		if (r != n + 1)
			sum += r - l;
		else
			sum += (ll)(r - l) * (ll)(r - l + 1) / (ll)2;
		tmp ^= a[l];
		l++;
	}
	printf("%lld\n", sum);
}

Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
ll n;
string s="";

signed main(){
	cin>>n;
	while(n){
		n--;
		s+=char('a'+n%26);
		n/=26;
	}
	reverse(s.begin(),s.end());
	cout<<s<<endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    int a,b,k;
    cin >> a >> b >> k;
    int min_ab= min(a,b);
    vector<int> gcdlist;
    int tmp=0;
    for (int i=1;i<=min_ab;i++){
        if ((a%i==0) && (b%i==0)) {
            gcdlist.push_back(i);
            tmp += 1;
        }
    }
    cout << gcdlist[tmp-k] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(void)
{
    string s;
    cin>>s;
    ll ans=INT_MAX;
    for(int i=0;i<s.size()-2;i++)
    {
        string ss;
        ss+=s[i];
        ss+=s[i+1];
        ss+=s[i+2];
        ll x=stoi(ss);
        ll ok=abs(753-x);
        ans=min(ans,ok);
    }
    cout<<ans<<endl;
}


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

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

    vector<int> pt;
    pt.push_back(0);
    for(int i=0;i<n;i++){
        int l;
        cin >> l;
        pt.push_back(pt.back()+l);
    }

    int ans = 0;
    for(auto p: pt){
        if(p <= x) ans++;
    }

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

Measured memory_bytes: 256
S = str(input())

if S[0] == "S":
  if S[1] == "S":
    if S[2] == "S":
      print(0)
    else:
      print(1)
  else:
    if S[2] == "S":
      print(1)
    else:
      print(2)
else:
   if S[1] == "S":
    if S[2] == "S":
      print(1)
    else:
      print(1)
   else:
    if S[2] == "S":
      print(2)
    else:
      print(3)

Measured memory_bytes: 9128
#include <stdio.h>

int main () {
    int A;
    int B;

    scanf("%d", &A);
    scanf("%d", &B);

    int ans = 0;
    if (13 <= A)
        ans = B;
    else if (6 <= A && 12 >= A)
        ans = B / 2;
    else
        ans = 0;
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 128
//解説の別解
// 左がxとすると右はsum-xなので
// 最小のabs(sum-2x)をみつける
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
// const ll INF = 1000000000000000000LL;

//最大公約数
ll gcd(ll a,ll b){
    if(a<b) swap(a,b);
    bool have_mod =true;
    while(have_mod){
        ll mod = a % b;
        if(mod == 0 ) have_mod = false;
        a = b;
        b = mod;
    }
    return a;
}

//最小公倍数
ll lcm(ll a,ll b){
	ll g = gcd(a,b);
	return a/g*b; //a>b
}

int main(){
	int n;
	cin >> n;
	vector<ll> t(n);
	rep(i,n) cin >> t[i];
	ll num = t[0];
	for(int i=1;i<n;i++){
		num = lcm(num,t[i]);
	}
	cout << num << endl;
	return 0;
}

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

// 点クラス
struct P{
	int x, y;
	P(int x_, int y_){
		x = x_; y = y_;
	}
};
bool operator<(const P& a, const P& b){
	if( a.x < b.x ) return true;
	else if( a.x > b.x ) return false;
	return a.y < b.y;
}

// x,y := 位置, t := 時刻, cost := お姉さんの指示を無視した回数
struct State{
	int cost, t, x, y;
	State(int cost_, int t_, int x_, int y_){
		cost = cost_; t = t_; x = x_; y = y_;
	}
};
bool operator<(const State& a, const State& b){
	if( a.cost < b.cost ) return false;
	else if( a.cost > b.cost ) return true;
	return a.t > b.t;
}

const int INF = 1e+8;
int lx, ly;
// b[P(x,y)] := 通れないマスかどうか
map<P,bool> b;
// d[y][x][t] := (x,y) に 時刻 t(mod 6) のときの無視した指示の回数
int d[300][300][6];
// 6近傍 + その場にとどまる
int dx[2][7] = {
	{0,1,1,0,-1,-1,0},
	{0,1,1,0,-1,-1,0}
};
int dy[2][7] = {
	{1,0,-1,-1,-1,0,0},
	{1,1, 0,-1, 0,1,0}
};

// ダイクストラ
int solve(int sx, int sy, int gx, int gy){
	// 初期化
	for(int y=0 ; y < 300 ; y++ ){
		for(int x=0 ; x < 300 ; x++ ){
			for(int i=0 ; i < 7 ; i++ ){
				d[y][x][i] = INF;
			}
		}
	}
	// 始点をメモして優先度つきキューに入れる.
	d[sy+100][sx+100][0] = 0;
	priority_queue<State> q;
	q.push( State(0,0,sx,sy) );
	
	int res = INF;
	while( !q.empty() ){
		// キューから取り出す. (コストはお姉さんの指示を無視した回数)
		// お姉さんの指示を無視した回数が小さい方から値が取り出される.
		int t = q.top().t;
		int x = q.top().x;
		int y = q.top().y;
		int cost = q.top().cost;
		q.pop();
		
		// ゴールのとき
		if( x == gx && y == gy ){
			res = cost;
			break;
		}
		// お姉さんの指示する方
		int dir = abs(x*y*t) % 6;
		
		for(int i=0 ; i < 7 ; i++ ){
			int mx = x + dx[abs(x)%2][i];
			int my = y + dy[abs(x)%2][i];
			// 座標の絶対値がlx, ly を超えるときと障害物があるときは移動しない
			if( lx < abs(mx) || ly < abs(my) ) continue;
			if( b[P(mx,my)] ) continue;
			
			// 次のコスト
			int next_cost;
			if( i == dir ){ // 指示を守る
				next_cost = cost;
			}else{ // 指示を守らない
				next_cost = cost + 1;
			}
			
			if( next_cost < d[my+100][mx+100][(t+1)%6] ){
				d[my+100][mx+100][(t+1)%6] = next_cost;
				State next(next_cost, t+1, mx, my );
				q.push( next );
			}
		}
	}
	return res;
}

int main(){
	int sx, sy, gx, gy, n;
	cin >> sx >> sy >> gx >> gy >> n;
	for(int i=0 ; i < n ; i++ ){
		int x, y;
		cin >> x >> y;
		b[P(x,y)] = true;
	}
	cin >> lx >> ly;
	for(int y = -ly ; y <= ly ; y++ ){
		for(int x=0 ; x < lx ; x++ ){
			if( !b.count(P(x,y)) ){
				b[P(x,y)] = false;
			}
		}
	}
	int ans = solve(sx, sy, gx, gy);
	if( ans == INF ) ans = -1;
	cout << ans << endl;
}

Measured memory_bytes: 5832
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
#include <deque>
#include <complex>
#include <bitset>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<long long, long long> pll;
typedef vector<pll> vpll;

typedef long double ld;
typedef vector<ld> vld;

typedef vector<bool> vb;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, n) for (ll i = 1; i <= (n); i++)
#define rrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rreps(i, n) for (ll i = (n); i >= 1; i--)
#define all(v) (v).begin(), (v).end()

template <class T> void chmin(T& a, T b) { a = min(a, b);}
template <class T> void chmax(T& a, T b) { a = max(a, b);}

constexpr int INF = 1 << 30;
constexpr ll INFL = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-12;
ld PI = acos(-1.0);

typedef vector<vb> vvb;

void solve() {
    ll n, k;
    cin >> n >> k;
    vll a;
    rep(i, n) {
        ll _a;
        cin >> _a;
        if(_a >= k) continue;
        a.push_back(_a);
    }
    n = a.size();

    vvb sa(n + 1, vb(k + 1));
    vvi saf(n + 1);
    sa[0][0] = true;
    for(ll i = 0; i < n; i++) {
        for(ll j = 0; j <= k; j++) {
            if(sa[i][j]) {
                sa[i + 1][j] = true;
                if(j + a[i] <= k) sa[i + 1][j + a[i]] = true;
            }
        }
    }
    rep(i, n + 1) rep(j, k + 1) if(sa[i][j]) saf[i].push_back(j);

    sa.assign(n + 1, vb(k + 1, false));
    vvi sab(n + 1);
    sa[n][0] = true;
    for(ll i = n - 1; i >= 0; i--) {
        for(ll j = 0; j <= k; j++) {
            if(sa[i + 1][j]) {
                sa[i][j] = true;
                if(j + a[i] <= k) sa[i][j + a[i]] = true;
            }
        }
    }
    rep(i, n + 1) rep(j, k + 1) if(sa[i][j]) sab[i].push_back(j);

    ll ans = 0;
    for(ll i = 0; i < n; i++) {
        vi& v1 = saf[i];
        vi& v2 = sab[i + 1];
        // v1+v2がk-a[i]~k-1となるのを探す
        bool ok = false;
        for(auto& j : v1) {
            ll l = lower_bound(v2.begin(), v2.end(), k - a[i] - j) - v2.begin();
            ll r = upper_bound(v2.begin(), v2.end(), k - 1 - j) - v2.begin();
            if(r - l > 0) ok = true;
            if(ok) break;
        }
        if(!ok) ++ans;
    }
    cout << ans << endl;
    return;
}

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

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

using namespace std;

typedef long long           ll;
typedef vector<int>         vi;
typedef pair<int,int>       ii;

#define endl                '\n'
#define ff                  first
#define pf                  printf
#define ss                  second
#define MX                  109
#define pb                  push_back
#define DB                  pf("Hi\n")
#define pf1(a)              pf("%d",a)
#define sc1(a)              scanf("%d",&a)
#define all(c)              (c).begin(),(c).end()
#define mem(a,b)            memset(a, b, sizeof(a))
#define RD                  freopen("0iuput.txt","r",stdin)
#define WR                  freopen("0uput.txt","w",stdout)
#define TC                  int _T;scanf("%d",&_T);while(_T--)
#define rep(i,a,b)          for(int i=int(a)-(a>b);i!=(b)-(a>b);i+=1-2*(a>b))

char arr[MX][MX];

int main()
{
    int a,b;

    sc1(a);
    sc1(b);

    getchar();

   rep(i,1,a+1)
   {
       scanf("%s",arr[i]);
   }

   rep(i,0,a+2)
   {
       rep(j,0,b+2)
       {
          if(i==0 || j==0 || i==a+1 || j==b+1)pf("#");
          else pf("%c",arr[i][j-1]);
       }
       puts("");
   }

}



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

int main(){
    string S;
    cin >> S;
    int a = S.size();
    int b = a - 1;
    int c = 0;
    for(int i = 0;i < (a / 2);i++){
        if(S.at(i) != S.at(b - i)){
            c = c + 1;
        }
    }
    cout << c << endl;
}

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

using namespace std;

struct CWW{CWW(){ios::sync_with_stdio(false);cin.tie(0);}}cww;
typedef long long LL;
const LL INF=1e16;
typedef vector<LL> V;
typedef vector<V> VV;
int main(){
    for(int N,M;cin>>N>>M,N+M;){
	VV riku(N,V(N,INF)),umi(N,V(N,INF));
	for(int i=0;i<N;i++)riku[i][i]=umi[i][i]=0;
	while(M--){
	    int a,b;LL t;string s;
	    cin>>a>>b>>t>>s;
	    a--;b--;
	    if(s=="L")riku[a][b]=riku[b][a]=t;
	    else umi[a][b]=umi[b][a]=t;
	}
	for(int k=0;k<N;k++)
	    for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
		    riku[i][j]=min(riku[i][j],riku[i][k]+riku[k][j]);	    
		    umi[i][j]=min(umi[i][j],umi[i][k]+umi[k][j]);
		}
	int R;
	cin>>R;
	vector<int> z(R);
	for(auto &it:z){
	    cin>>it;it--;
	}
	VV dp(R,V(N,INF));
	dp[0][z[0]]=0;
	for(int i=1;i<R;i++){
	    for(int j=0;j<N;j++){
		dp[i][j]=dp[i-1][j]+riku[z[i-1]][z[i]];
		for(int k=0;k<N;k++)
		    dp[i][j]=min(dp[i][j],dp[i-1][k]+riku[z[i-1]][k]+umi[k][j]+riku[j][z[i]]);
	    }
	}
	LL res=INF;
	for(auto &it:dp.back())res=min(res,it);
	cout<<res<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 1000000007
#define exp pow(10,-9)
#define F first
#define S second
#define PB push_back 
#define MP make_pair
#define daman ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define lowercase(str) transform(str.begin(), str.end(), str.begin(), ::tolower);
#define uppercase(str) transform(str.begin(), str.end(), str.begin(), ::toupper);
main(){
    daman
	lli n;
	cin>>n;
	
	lli ans = n + n*n + n*n*n;
	
	cout<<ans<<"\n";
	
	
}

Measured memory_bytes: 3648
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF = 10**18
# R,L,U,D
data = {x:[-INF,INF,-INF,INF]for x in 'RLUD'}

N = int(readline())
XYD = read().split()
X = (int(x) for x in XYD[::3])
Y = (int(x) for x in XYD[1::3])
D = (x.decode('utf-8') for x in XYD[2::3])

for x,y,d in zip(X,Y,D):
    if data[d][0] < x: data[d][0] = x
    if data[d][1] > x: data[d][1] = x
    if data[d][2] < y: data[d][2] = y
    if data[d][3] > y: data[d][3] = y

X = []
Y = []
# a+tb
X += [(data['L'][0],-1), (data['L'][1],-1)]
X += [(data['R'][0],1), (data['R'][1],1)]
X += [(data['U'][0],0), (data['U'][1],0)]
X += [(data['D'][0],0), (data['D'][1],0)]

Y += [(data['L'][2],0), (data['L'][3],0)]
Y += [(data['R'][2],0), (data['R'][3],0)]
Y += [(data['U'][2],1), (data['U'][3],1)]
Y += [(data['D'][2],-1), (data['D'][3],-1)]

X = [(x,dx) for x,dx in X if abs(x) < INF]
Y = [(x,dx) for x,dx in Y if abs(x) < INF]

T = []
for (x,dx),(y,dy) in itertools.combinations(X,2):
    if dx == dy: continue
    # x + tdx = y + tdy
    T.append((x-y)/(dy-dx))
for (x,dx),(y,dy) in itertools.combinations(Y,2):
    if dx == dy: continue
    # x + tdx = y + tdy
    T.append((x-y)/(dy-dx))

T = set([0] + [t for t in T if t > 0])

def F(t):
    xs = [x+t*speed for x,speed in X]
    ys = [x+t*speed for x,speed in Y]
    dx = max(xs) - min(xs)
    dy = max(ys) - min(ys)
    return dx*dy

answer = min(F(t) for t in T)
print(answer)

Measured memory_bytes: 17256
#include<bits/stdc++.h>
using namespace std;
int tot=0;
int nxt[100001];
int to[100001];
int head[100001];
int degree[100001];
int f[100001];
void addedge(int u,int v)
{
	tot++;
	nxt[tot]=head[u];
	to[tot]=v;
	head[u]=tot;
}
int dfs(int ind)
{
	int i,v;
	if(head[ind]==0)
		f[ind]=0;
	if(f[ind]>=0)
		return f[ind];
	for(i=head[ind];i;i=nxt[i])
	{
		v=to[i];
		f[ind]=max(f[ind],dfs(v)+1);
	}
	return f[ind];
}
int main()
{
	memset(f,0xff,sizeof(f));
	int u,v,n,m,i,maxn;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&u,&v);
		addedge(u,v);
		degree[v]++;
	}
	for(i=1;i<=n;i++)
	{
		//if(degree[i]==0)
			dfs(i);
	}
	maxn=0;
	for(i=1;i<=n;i++)
		maxn=max(maxn,f[i]);
	printf("%d",maxn);
	return 0;
}

Measured memory_bytes: 3584
N, M = gets.split.map(&:to_i)
STs = readlines.map{|l| l.split.map(&:to_i)}

fs, ts, ns = Array.new(N + 1){[]}, Array.new(N + 1){[]}, Array.new(N + 1, 0)
STs.each{|s, t| fs[s] << t; ts[t] << s; ns[s] += 1}
ev = Array.new(N + 1, 0.0)
(N - 1).downto(1).each do |i|
  ev[i] = fs[i].inject(0){|s, j| s + ev[j] + 1} / ns[i]
end
wt = Array.new(N + 1, 1.0)
(2 .. N).each do |j|
  wt[j] = ts[j].inject(0){|s, i| s + wt[i] / ns[i]}
end
d = (1 .. N).select{|i| ns[i] > 1}.map do |i|
  k = fs[i].max_by{|j| ev[j]}
  n = ns[i]
  fs[i].inject(0){|s, j| s + ev[j] / (j == k ? n : n*(1 - n))}*wt[i]
end.max || 0
puts ev[1] - d

Measured memory_bytes: 32764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int main(){
    map<int, int> mp;
    for(int i=0; i<3; i++){
        int a; cin >> a;
        mp[a]++;
    }

    if(mp[5] == 2 && mp[7] == 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}

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

int main() {

	int a, b; cin >> a >> b;

	int sumLeft = 0;
	int sumRight = 1;
	for (int i = 1; i < 1000; i++) {
		sumLeft += i;
		sumRight += i + 1;
		for (int j = 1; j <= sumRight; j++) {
			if (sumLeft - j == a && sumRight - j == b) {
				cout << j << endl;
				return 0;
			}
		}
	}

	return 0;
}

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

using namespace std;
typedef pair<int, int> P;

int main() {
  vector< vector<bool> > a(3, vector<bool>(3, false));
  map<int, P> m;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      int tmp;
      cin >> tmp;
      m[tmp] = P(i, j);
    }
  }
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int b;
    cin >> b;
    auto it = m.find(b);
    if (it != m.end()) {
      P pos = m[b];
      a[pos.first][pos.second] = true;
    }
  }

  bool ok = false;
  for (int i = 0; i < 3; ++i) {
    if (a[i][0] && a[i][1] && a[i][2]) ok = true;
    if (a[0][i] && a[1][i] && a[2][i]) ok = true;
  }

  if ((a[0][0] && a[1][1] && a[2][2]) || (a[0][2] && a[1][1] && a[2][0])) ok = true;
  if (ok) puts("Yes");
  else puts("No");
  return 0;
}



Measured memory_bytes: 256
line = gets.chomp.split(" ")
n = line[0].to_i
x = line[2].to_i

line = gets.chomp.split(" ")
gate = []
for i in line
  gate.push(i.to_i)
end

cost_a = 0
for i in x+1...n
  if gate.include?(i)
    cost_a += 1
  end
end

cost_b = 0
for i in 0..x
  if gate.include?(i)
    cost_b += 1
  end
end

puts cost_a < cost_b ? cost_a : cost_b

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back

using namespace std;

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

const int MAXN = 100 + 10;

int n;

struct rest{
	string s;	
	int sc;
	int ind;
} re[MAXN];

int main(){
	ios_base::sync_with_stdio(false), cin.tie(0);
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> re[i].s >> re[i].sc;
		re[i].ind = i+1;
	}

	sort(re, re+n, [](rest a, rest b){
		if(a.s != b.s) return a.s < b.s;
		return a.sc > b.sc;
	});

	for(int i=0; i<n; i++) cout << re[i].ind << endl;
}


Measured memory_bytes: 256
//@formatter:off
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define rrep(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = int(s); i < int(n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vp vector<P>
#define vvp vector<vector<P>>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==int(v.size()-1)?"":","); return os<<']'; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << '\n'; }
void YES(bool b) { cout << (b ? "YES" : "NO") << '\n'; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;
//@formatter:on

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, x, t;
    cin >> n >> x >> t;
    cout << (n + x - 1) / x * t << endl;
}

Measured memory_bytes: 3644