akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
	
	class Heap{
		Heap left, right;
		int value;
		
		Heap(int v){
			value = v;
			left = right = null;
		}
		
		int top(){
			return value;
		}
		
		Heap push(int v){
			return meld(new Heap(v), this);
		}
		
		Heap pop(){
			return meld(left, right);
		}
	}
	
	Heap meld(Heap a, Heap b){
		if(a == null){
			return b;
		}
		if(b == null){
			return a;
		}
		if(a.value < b.value){
			Heap t = a; a = b; b = t;
		}
		a.right = meld(a.right, b);
		Heap t = a.left; a.left = a.right; a.right = t;
		
		return a;
	}
	
	class Vert extends ArrayList<Integer>{
		int markedTime;
		int parent;
		int degree;
		Heap hp;
		ArrayList<Integer> askedTime;
	}
	
	/*
	Heap rec(Vert vs[], int vid){
		Vert v = vs[vid];
		Heap h = null;
		for(Integer t : v.askedTime){
			h = meld(h, new Heap(t));
		}
		for(Integer u : v){
			h = meld(h, rec(vs, u));
		}
		
		for(;h!=null && h.top() > v.markedTime ;h = h.pop()){
			ans += vid;
		}
		return h;
	}
	*/
	
	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			int N = in.nextInt(), Q = in.nextInt();
			if(N == 0){
				return ;
			}
			Vert[] vs = new Vert[N + 1];
			for(int i=0; i<vs.length; i++){
				vs[i] = new Vert();
				vs[i].markedTime = Integer.MAX_VALUE;
				vs[i].askedTime = new ArrayList<Integer>();
			}
			
			for(int i=2; i<=N; i++){
				int p = in.nextInt();
				vs[p].degree++;
				vs[i].parent = p;
				vs[p].add(i);
			}
			
			vs[1].markedTime = 0;
			for(int t=1; t<=Q; t++){
				String cmd = in.next();
				int v = in.nextInt();
				if(cmd.equals("M")){
					if(vs[v].markedTime == Integer.MAX_VALUE){
						vs[v].markedTime = t;
					}
				}
				else{
					vs[v].askedTime.add(t);
				}
			}
			
			long ans = 0;
			ArrayList<Integer> stack = new ArrayList<Integer>();
			for(int i=1; i<=N; i++){
				if(vs[i].degree == 0){
					stack.add(i);
				}
			}
			
			for(;!stack.isEmpty();){
				int vid = stack.get(stack.size()-1);
				stack.remove(stack.size()-1);
				Vert v = vs[vid];
				Heap h = null;
				for(Integer t : v.askedTime){
					h = meld(h, new Heap(t));
				}
				for(Integer u : v){
					h = meld(h, vs[u].hp);
				}
				
				for(;h!=null && h.top() > v.markedTime ;h = h.pop()){
					ans += vid;
				}
				v.hp = h;
				if(--vs[v.parent].degree == 0){
					stack.add(v.parent);
				}
			}
			
			System.out.println(ans);
		}
	}
	
	public static void main(String args[]){
		new Main().run();
	}
}

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

typedef long long ll;

int main()
{
	ll a,v,b,w,t;
	cin>>a>>v>>b>>w>>t;
	ll sum=t*(v-w);
	if(sum>=(max(a,b)-min(a,b))){
		cout<<"YES"<<endl;
	}
	else {
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,pi,xi,sum=0,dif;
    int ara[111];
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&ara[i]);
        sum+=ara[i];
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&pi,&xi);
        dif = (sum - ara[pi-1])+xi;
        printf("%d\n",dif);
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define vi vector
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define mod 1000000007
#define pb push_back
#define ll long long 
#define db double
#define all(v) v.begin(),v.end()

using namespace std;

/*

ll expo(ll n){
    ll t;
    if(n==0)return 1;
    else if(n==1) return 2;
    t=expo(n/2);
    if(n%2){
        return t*t*2;
    }
    else return t*t;
}

//ffrom geek for geek
ll exponentMod(ll A, ll B, ll C)  
{  
    if (A == 0)  
        return 0;  
    if (B == 0)  
        return 1;  
    ll y;  
    if (B % 2 == 0) {  
        y = exponentMod(A, B / 2, C);  
        y = (y * y) % C;  
    }  
    else {  
        y = A % C;  
        y = (y * exponentMod(A, B - 1, C) % C) % C;  
    }  
  
    return (ll)((y + C) % C);  
}

*/
/*
class dsu{
public:    
vi<ll> v;


void init(ll n){
    v.assign(n+1,-1);
}

 
ll dsufind(ll x){
    if(v[x]<0){
        return x;
    }
    v[x]=dsufind(v[x]);
    return v[x];
}
 
void dsujoin(ll x,ll y){
    x=dsufind(x);
    y=dsufind(y);
    
    if(x==y)
    return;
    if(v[x]>v[y])swap(x,y);
    v[y]+=v[x];
    v[x]=y;
}

};
*/

vi<ll> v[100005];
vi<ll> dp(100005,-1);
ll dfs(ll x){
    if(dp[x]>=0)
    return dp[x];
    ll tmp=0;
    FOR(i,v[x].size()){
        tmp=max(tmp,dfs(v[x][i])+1);
    }

    return dp[x]=tmp;
}

int main(){
    IOS;
    ll t;
    t=1;
    //cin>>t;
    while(t--){
        ll n,m,ans=INT_MIN,x,y;
        cin>>n>>m;
        FOR(i,m){
            cin>>x>>y;
            v[x].pb(y);
        }
        FORE(i,1,n){
            
            ans=max(ans,dfs(i));
        }
        cout<<ans;


    }
    return 0;
} 

Measured memory_bytes: 11520
import sys
n=int(input())
s=input().split()
if '0' in s:
  print(0)
  sys.exit()
l=list(map(int,s))
max=10**18
ans=1
while n>0:
  ans *= l[n-1]
  n-=1
  if ans>max:
    print(-1)
    sys.exit()
print(ans)

Measured memory_bytes: 21476
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,ans=0; cin >> N;
  ans = N%10;
  
  if(ans==3) cout << "bon" << endl;
  else if(ans==0 || ans==1 || ans==6 || ans==8) cout << "pon" << endl;
  else cout << "hon" << endl;
}

Measured memory_bytes: 3612
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll L, R;
constexpr ll MAX_BIT = 64;
constexpr ll MOD = 1e9 + 7;
bitset<MAX_BIT> L_B, R_B;
map<tuple<ll, bool, bool, bool>, pair<bool, ll>> memo;

ll solve(ll i, bool X_ge_L, bool Y_le_R, bool appear_LSB) {
    if (i == MAX_BIT) {
        return 1;
    }
    auto curr_tuple = make_tuple(i, X_ge_L, Y_le_R, appear_LSB);
    if (memo[curr_tuple].first) {
        return memo[curr_tuple].second;
    }
    memo[curr_tuple].first = true;

    ll result = 0;
    //(1)x 0, y 0とする
    //   こうすることができるのはすでにx >= Lが確定している場合か、Lの対応位置が0である場合
    if (X_ge_L || !L_B[MAX_BIT - 1 - i]) {
        //Rの対応位置が1だったらy <= Rが確定する
        (result += solve(i + 1, X_ge_L, R_B[MAX_BIT - 1 - i] || Y_le_R, appear_LSB)) %= MOD;
    }

    //(2)x 0, y 1とする
    //   こうすることができるのはすでにx >= Lが確定している場合か、Lの対応位置が0である場合 かつ
    //                     すでにy <= Rが確定している場合か、Rの対応位置が1である場合 かつ
    //                     すでにx 1, y 1となる部分が最左ビットとして現れている
    if ((X_ge_L || !L_B[MAX_BIT - 1 - i]) && (Y_le_R || R_B[MAX_BIT - 1 - i]) && appear_LSB) {
        (result += solve(i + 1, X_ge_L, Y_le_R, appear_LSB)) %= MOD;
    }

    //(3)x 1, y 1とする
    //   こうすることができるのはすでにy <= Rが確定している場合か、Rの対応位置が1である場合
    if (Y_le_R || R_B[MAX_BIT - 1 - i]) {
        //x 1, y 1という部分が現れたとしてappear_LSBを立てる
        (result += solve(i + 1, !L_B[MAX_BIT - 1 - i] || X_ge_L, Y_le_R, true)) %= MOD;
    }

    //制約の関係からx 1, y 0となることはないので以上で全部

    return memo[curr_tuple].second = result;
}

int main() {
    cin >> L >> R;
    L_B = bitset<MAX_BIT>(L);
    R_B = bitset<MAX_BIT>(R);
    cout << solve(0, false, false, false) << endl;
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
for i in range(n+1):
  L=map(int,str(i))
  #print(list(L))
  #print(*L)
'''
0
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
'''
print(sum(i for i in range(n+1) if a<=sum(map(int,str(i)))<=b))

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

long long int dp[110][100010],n,a[110],b[110],i,w,j,ans;

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>w;
	for (i=1;i<n+1;i++) cin>>a[i]>>b[i];
	for (i=0;i<n+1;i++)
	for (j=0;j<100001;j++) dp[i][j]=1000000000000;
	dp[0][0]=0;
	for (i=1;i<n+1;i++)
	for (j=0;j<100001;j++)
	if (j-b[i]>=0) dp[i][j]=min(dp[i-1][j],dp[i-1][j-b[i]]+a[i]);
	else dp[i][j]=dp[i-1][j];
	ans=100000;
	while (dp[n][ans]>w) ans=ans-1;
	cout<<ans;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)
const ll INF=1e17;
using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
ll ans1=0;
void recur(vector<pair<char,int>> str,int val,ll sum,int idx){
  if(val<0) return;
  else if(val==0){
    ans1=max(ans1,sum);
    return;
  }
  if(idx>=str.size()) return;
  rep(j,idx,str.size()){
    recur(str,val-str[j].s,sum*10+str[j].f-'0',idx+1);
    recur(str,val-str[j].s,sum*10+str[j].f-'0',idx);
  }
}
void  solve(){
  int n,m2;
  cin>>n>>m2;
  int a[m2];
  rep(i,0,m2) cin>>a[i];
  sort(a,a+m2);
  map<int,int> m,m1;
  m[1]=2;
  m[2]=5;
  m[3]=5;
  m[4]=4;
  m[5]=5;
  m[6]=6;
  m[7]=3;
  m[8]=7;
  m[9]=6;
  rep(i,0,m2){
    m1[m[a[i]]]=a[i];
  }
  int sma= (*m1.begin()).s;
  int rep = max(n/m[sma]-7,0);
  int rem=n%m[sma]+min(n/m[sma],7)*m[sma];

  string ans="";
  ans+=repeat(getString('0'+sma),rep);
  vector<pair<char,int>> str;
  for(auto i:m1){
    str.pb({i.s+'0',i.f});
  }
  ans1=0;
  recur(str,rem,0,0);
  vector<char> res;
  rep(i,0,ans.length()) res.pb(ans[i]);
  // cout<<ans1<<endl;
  while(ans1){
    res.pb(ans1%10+'0');
    ans1/=10;
  }
  sort(all(res),greater<char>());
  rep(i,0,res.size()) cout<<res[i];
  cout<<endl;
  // if(rem==0) cout<<ans<<endl;
  // else{
  //   int mx=-1;
  //   for(auto i:m1){
  //     if(i.f<=rem) mx=max(mx,i.s);
  //   }
  //   cout<<rem<<endl;
  //   if(mx!=-1 && sma>mx) ans+= getString(mx+'0');
  //   else if(mx!=-1 && sma<=mx) ans=getString(mx+'0')+ans;
  //   cout<<ans<<endl;
  // }
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
int n,x,a;
string s;
int main()
{
    cin>>n;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='I'){
            x++;
            a=max(a,x);
        }
        else if(s[i]=='D')
            x--;
    }
    cout<<a;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define optimize ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define INF 2000000020LL
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define POS(n, x) (lower_bound(ALL(n), x) - (n).begin())
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define PB push_back
#define EB emplace_back
#define MOD 1000000007
#define PRIME 101 
#define MAXN 1010
#define MAXL 23
#define endl '\n'

using namespace std;

// (1 + sqrt(5)) / 2
const ld GOLDEN_RATIO = 1.6180339887498949025257388711906969547271728515625;
const ld PI = 2.0 * acos(0.0);
const int BLOCK = 333;

char mapa[MAXN][MAXN];
int dp[MAXN][MAXN];

int solve(int i, int j)
{
	if(i < 0 || j < 0) return 0;
	if(i + j == 0) return 1;
	if(dp[i][j] != -1) return dp[i][j];

	if(mapa[i][j] == '#') return dp[i][j] = 0;

	return dp[i][j] = (solve(i - 1, j) + solve(i, j - 1)) % MOD;
}

int main(int argc, char const *argv[])
{
	optimize;
	
	memset(dp, -1, sizeof dp);

	int N, M;

	cin >> N >> M;

	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			cin >> mapa[i][j];

	cout << solve(N - 1, M - 1) << endl;

	return 0;
}

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

using namespace std;

//container util
#define SORT(c) sort((c).begin(),(c).end())

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


int main(void){

	string S; cin >> S;

	char buffer = S[0];

	int section = 1;
	FOR(i,1,S.length()){
		if(buffer != S[i]){
			section++;
			buffer = S[i];
		}
	}

	int ans = section - 1;
	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    // Your code here!
    int n;
    scanf("%d", &n);
    if(100<=n && n<=111) printf("%d", 111);
    else if(112<=n && n<=222) printf("%d\n", 222);
    else if(223<=n && n<=333) printf("%d\n", 333);
    else if(334<=n && n<=444) printf("%d\n", 444);
    else if(445<=n && n<=555) printf("%d\n", 555);
    else if(556<=n && n<=666) printf("%d\n", 666);
    else if(667<=n && n<=777) printf("%d\n", 777);
    else if(778<=n && n<=888) printf("%d\n", 888);
    else if(889<=n && n<=999) printf("%d\n", 999);
}

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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

// grid
//--------------------------------------------
VL dx = {0, 1, 0, -1};
VL dy = {1, 0, -1, 0};
VL dx2 = {-1, 0, 1, -1, 1, -1, 0, 1};
VL dy2 = {-1, -1, -1, 0, 0, 1, 1, 1};

//debug
//--------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//IO accelerate
//--------------------------------------------
struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

//template
//--------------------------------------------
template<typename T>
istream& operator >>(istream& is, vector<T>& vec) {
  for(T& x: vec) is >> x;
  return is;
}
template<typename T>
ostream& operator <<(ostream& os, const vector<T>& vec) {
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : "\t" );
  }
  return os;
}
template<typename T>
ostream& operator <<(ostream& s, const vector<vector<T>>& vv) {
	for (int i = 0; i < vv.size(); ++i) {
		s << vv[i] << endl;
	}
	return s;
}

// 多重vector
// auto dp=make_v<int>(4,h,w) みたいに使える
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// 多重vectorのためのfill
// fill_v(dp,0) みたいに使える
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//main code

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	string s;
	cin >> s;
	int ans = 1;
	for (int i = 0; i < n-1; i++) {
		if (s[i] != s[i+1]) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


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

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)

Measured memory_bytes: 60340
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n;
string s, t;

int main() {
	cin >> n;
	cin >> s >> t;
	
	int i, j;
	int ans = 114514;
	
	for (i = 0; i <= n; i++) {
		string str;
		str += s;
		for (j = i; j < n; j++) {
			str += t[j];
		}
		
		int cor = 0;
		for (j = (int)str.length() - n; j < str.length(); j++) {
			if (str[j] != t[cor]) {
				break;
			}
			cor++;
		}
		if (j == str.length()) {
			ans = min(ans, 2 * n - i);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s1, s2;
		int l1, l2;
		cin >> s1 >> s2;
		l1 = s1.length();
		l2 = s2.length();
		if (l1>80 || l2 > 80)
			cout << "overflow";
		else
		{
			int result[100], r = 0, m = max(l1, l2), t;
			reverse(s1.begin(), s1.end());
			reverse(s2.begin(), s2.end());
			s1.resize(m + 1, '0');
			s2.resize(m + 1, '0');
			for (int j = 0; j < m; j++)
			{
				t = r + s1[j] + s2[j] - 48 * 2;
				result[j] = t % 10;
				r = t / 10;
			}
			if (r == 1)
				result[m++] = 1;
			if (m>80)
				cout << "overflow";
			else
				for (int j = m - 1; j >= 0; j--)
					cout << result[j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define inf 1000000000000000000
using namespace std;
 
typedef struct {
  long long s, t, c;
} edges;
long long n, m, ans;
vector<edges> edge;
long long dis[1005] = {0};
 
void prians(bool answer) {
  if(answer)
    cout << "inf" << endl;
  else
    cout << ans << endl;
}
bool solve();
 
int main() {
  cin >> n >> m;
  for(int i = 0; i < m; ++i) {
    edges e;
    cin >> e.s >> e.t >> e.c;
    --e.s;
    --e.t;
    e.c *= -1;
    edge.push_back(e);
  }
  prians(solve());
  return 0;
}
 
bool solve() {
  for(int i = 0; i < n; ++i) dis[i] = inf;
  dis[0] = 0;
  for(int i = 0; i < n; ++i) {
    bool update = 0, upn = 0;
    for(int j = 0; j < m; ++j) {
      edges now = edge[j];
      if(dis[now.s] != inf &&
         dis[now.s] + now.c < dis[now.t]) {
        update = 1;
        if(now.t == n - 1) upn = 1;
        dis[now.t] = dis[now.s] + now.c;
      }
    }
    if(!update) break;
    if(upn && i == n - 1) return 1;
  }
  ans = -dis[n - 1];
  return 0;
}

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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 10000000000000007ll;

const double eps = 1e-10;

// #include "segtree_push.h"

// del

struct less_key {
    bool operator() (const pair<i64, i64>& p1, const pair<i64, i64>& p2) {
        return p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first);
    }
};

const i64 MAXN = 200005;

i64 n, k;


i64 R = 0;


stringstream ss;
void out(i64 i, i64 j) {
    ss << i << " " << j << endl;
    R++;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n >> k;

    i64 m = (n - 1) * (n - 2) / 2;



    for (i64 i = 1; i <= n - 1; i++) {
        out(n, i);
    }

    for (i64 i = n - 2; i >= 1; i--) {
        if (k == m) {
            break;
        }
        for (i64 j = i + 1; j <= n - 1; j++) {
            if (k == m) {
                break;
            }
            out(i, j);
            m--;
        }
    }

    if (k != m) {
        cout << -1 << endl;
    }
    else {
        cout << R << endl;
        cout << ss.str();
    }

    return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
int main(){
  int x,y,max,sm;
  scanf("%d%d",&x,&y);
  if(x<y){
    sm=x;
    x=y;
    y=sm;
  }
  max=x%y;
  while(max!=0){
    x=y;
    y=max;
    max=x%y;
  }
  printf("%d\n",y);
  return 0;
  
}



Measured memory_bytes: 2732
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

int main() {
  int N;

  std::cin >> N;

  std::vector<int> tmp;
  while (N != 0) {
    int amari = N % 10;
    tmp.push_back(amari);
    N = N / 10;
  }
  std::vector<int> tmp_rev(tmp.size());
  std::copy(tmp.begin(), tmp.end(), tmp_rev.begin());
  std::reverse(tmp_rev.begin(), tmp_rev.end());

  int sum = 0;
  for (int i = 0; i < tmp.size(); i++) {
    sum += std::abs(tmp[i] - tmp_rev[i]);
  }

  if (sum == 0) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
#define INF 1000000007
#define LINF 1000000000000000007
 
typedef long long i64;
typedef pair<i64,i64> P;


int n,m;
vector<int> v[101010];//v_from(to)
bool used[101010];
bool color[101010];

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a,b,c;
		cin >> a >> b >> c;
		c %= 2;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(used[i]) continue;
		cnt++;
		queue<int> q;
		q.push(i);//ばしょ
		while(!q.empty()){
			int p = q.front();
			q.pop();
			used[p] = 1;
			for(int j = 0; j < v[p].size(); j++){
				if(used[v[p][j]]) continue;
				q.push(v[p][j]);
			}
		}
	}
	cout << cnt << endl;
	
	return 0;
}

Measured memory_bytes: 6648
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int x, n, p[100];
int find(int a)
{
  for ( int i=0; i<n; i++ )
    if ( a==p[i] )
      return 1;
  return 0;
}
int main()
{
  scanf("%d %d", &x, &n);
  if ( n<=0 ) {
    printf("%d\n", x);
  } else {
    for ( int i=0; i<n; i++ )
      scanf("%d", &p[i]);
    for ( int i=0; i<100; i++ ) {
      if ( !find(x-i) ) {
        printf("%d\n", x-i);
        break;
      } else if ( !find(x+i) ) {
        printf("%d\n", x+i);
        break;
      }
    }
  }
  return 0;
}

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

int main() {
  int N;
  cin>>N;
  
  vector<int> A(N);
  for(int i=0;i<N;i++)
    cin>>A.at(i);
  
  sort(A.begin(),A.end());
  reverse(A.begin(),A.end());//大きい順に変換
  
  int X=0,Y=0;
  for(int i=0;i<N;i++){
    if(i%2==0)
      X+=A.at(i);
    else
      Y+=A.at(i);
  }
  
  cout<<X-Y<<endl;
}
  
      
  
  


Measured memory_bytes: 256
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dp[410][410] = {};
ll a[410];
ll sum[410] = {};

ll calc(ll lv, ll rv){
    ll &res = dp[lv][rv];
    if(~res) return res;
    if(rv - lv == 1){
        return res = 0;
    }
    res = INF;
    rep(i,lv,rv-1){
        ll val = sum[i+1] - sum[lv] + sum[rv] - sum[i+1] + calc(lv,i+1) + calc(i+1, rv);
        // print(lv,rv,i,val);
        res = min(res, val);
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    rep(i,0,N) cin >> a[i];
    rep(i,0,N+1){
        rep(j,0,N+1){
            dp[i][j] = -1;
        }
    }
    rep(i,0,N) sum[i+1] = sum[i] + a[i];
    ll ans = calc(0, N);
    print(ans);


}

Measured memory_bytes: 1536
from sys import stdin
import math
n = int(stdin.readline())
di = {}
a = map(int,stdin.readline().split())
for i in a:
    di[i] = di.get(i,0)+1
valid = 1

if n%2:
    if di.get(0,0)!=1:
        valid = 0
        
    else:
        for i in di:
            if i==0:
                continue
            if i >=n:
                valid = 0
                break
            if i%2:
                valid = 0
                break
            if di.get(i,0)!=2:
                valid = 0
                break
else:
    for i in di:
        if i>=n:
            break
        if i%2==0:
            valid = 0
            break
        if di.get(i,0)!=2:
            valid = 0
            break
if valid:
    print pow(2,n/2,10**9 + 7)
else:
    print 0

Measured memory_bytes: 11348
// https://atcoder.jp/contests/abc172/tasks/abc172_c

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DEBUG 1
#if DEBUG
  #define _GLIBCXX_DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

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

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

//------------------------------------------------------------------------------
const int N_MAX = 200000;
const int M_MAX = 200000;
const int K_MAX = 1e9;
const int A_I_MAX = 1e9;
const int B_I_MAX = 1e9;

int N, M, K;

vector<int> AB;

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

  AB = vector<int>(N + M + 1);
  REP(i, N) cin >> AB[N - 1 - i];
  REP(i, M) cin >> AB[N + i];
  AB[N + M] = 0;

  // DUMP(AB);

  int ans = 0;
  int s = 0;
  int t = 0;
  int sum = 0;
  while (true) {
    while (t <= M + N && sum <= K) {
      if (s <= N && t >= N) {
        // cout << "[" << s << "," << t << ") : " << sum << endl;
        chmax(ans, t - s);
      }
      sum += AB[t++];
    }
    if (sum <= K) break;
    sum -= AB[s++];
  }

  cout << ans << endl;
}


Measured memory_bytes: 4812
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n){
		cin >> a[i];
		a[i]--;
	}
	vector<ll> v(n);
	rep(i, n) {
		v[a[i]]++;
	}
	ll tot = 0;
	rep(i, n) {
		if(v[a[i]] > 0) tot += (ll) v[i] * (v[i]-1) / 2;
	}
	rep(i, n) {
		ll now = v[a[i]];
		ll dif = now * (now-1) / 2;
		ll add = (now - 1) * (now - 2) / 2;
		ll ans = tot - dif + add;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<algorithm>
using namespace std;
 
 
main(){
	int n,i,j,k;
	int g=0;
	cin>>n;
  	if(n==0)
      return 0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				g+=__gcd(i,__gcd(j,k));
				
	cout<<g;
  	return 0;
}

Measured memory_bytes: 3636
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	for i := 0; i < 3000; i++ {
		x, y := nextInt(), nextInt()
		if x == 0 && y == 0 {
			break
		}
		if x < y {
			fmt.Fprintln(out, x, y)
		} else {
			fmt.Fprintln(out, y, x)
		}
	}
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}



Measured memory_bytes: 1260
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 16;
ll mask_value[1<<maxn];
ll dp[1<<maxn];
ll a[maxn][maxn];
ll n;

void preprocess() {
    for(int mask=0;mask<(1<<n);mask++) {
        ll value = 0LL;
        for(int i=0;i<n;i++) {
            if(mask & (1<<i)) {
                for(int j=i+1;j<n;j++) {
                    if(mask & (1<<j)) {
                        value += a[i][j];
                    }
                }
            }
        }
        mask_value[mask] = value;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            cin>>a[i][j];
        }
    }
    preprocess();

    for(int mask=0;mask<(1<<n);mask++) {
        int b = 0;
        int x = mask;
        do {
            dp[mask] = max(dp[mask^b] + mask_value[b], dp[mask]);
        } while (b=(b-x)&x);
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}


Measured memory_bytes: 1280
n = gets.to_i
a = gets.split("\s").map(&:to_i)
b = gets.split("\s").map(&:to_i)
c = gets.split("\s").map(&:to_i)
result = 0
former = -1

n.times do |i|
  result += b[i]
  if(former + 1 == a[i])
    result += c[a[i] - 2]
  end
  former = a[i]
end

puts result

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <string>
#include <cmath>
#include <map>


using namespace std;
typedef long long ll;

//?????????????

int main(){

    string S, T;
    cin >> S >> T;
    map<char, char > check_s;
    map<char, char > check_t;
    //sort(S.begin(), S.end());
    //sort(T.begin(), T.end());

    for(ll i = 0; i < S.size(); i++){
        if(check_s.count(S[i])){
            if(check_s[S[i]] != T[i]){
                cout << "No" << endl;
                return 0;
            }
        }
        if(check_t.count(T[i])){
            if(check_t[T[i]] != S[i]){
                cout << "No" << endl;
                return 0;
            }
        }
        check_s[S[i]] = T[i];
        check_t[T[i]] = S[i];
    }

    cout << "Yes" << endl;
    
}

Measured memory_bytes: 776
n,x=gets.chomp.split(" ").map{|s| s.to_i}
l=gets.chomp.split(" ").map{|s| s.to_i}
d=0
c=0
for i in 0..n-1
  d+=l[i]
  if d<=x
    c+=1
  end
end

puts c+1

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

int main(){
  int a, b;

  cin >> a >> b;
  
  if ((a + b) % 2 == 0) {
    cout << (a + b) / 2 << endl;
  }
  else{
    cout << (a + b + 1) / 2;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main() {
    int n;
    cin >> n;
    ll sum = 0;
    for(int i=1; i<=n; i++){
        if(i % 3 == 0 && i % 5 == 0){

        }else if(i % 3 == 0){

        }else if(i % 5 == 0){

        }else{
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3632
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = list(readline().rstrip().decode())
k = int(read())
if len(set(s)) == 1:
    print(len(s) * k // 2)
    exit()
ans = 0
memo = 0
flag = True
for i, (bf, af) in enumerate(zip(s, s[1:])):
    if s[0] == af and flag:
        memo += 1
    else:
        flag = False
    if bf == af:
        ans += 1
        s[i + 1] = '?'
ans *= k
if s[-1] == s[0] and memo % 2 == 0:
    ans += k - 1
print(ans)


Measured memory_bytes: 3064
n=int(input())
a,b=map(int,input().split())
for i in range(1,n):
    x,y=map(int,input().split()) 
    if x>=a and y>=b:
        a=x 
        b=y 
        continue 
    mul1=-1 
    mul2=-1 
    if a%x!=0: 
        mul1=a//x  +1 
    else:
        mul1=a//x  
    if b%y==0:
        mul2=b//y 
    else: 
        mul2=b//y+1   
    m=max(mul1,mul2) 
   # print(m,x,y)
    a,b=x*m,y*m   
  #  print(a,b,'gd')
print(a+b)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;
typedef long long ll;
using namespace std;
const ll mod=1000000007,mod9=1000000009;
template <class T>inline T lcm(T a,T b){return (a*b/__gcd(a,b));}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<pair<int ,int> > v;
    int a;
    for(int i=0;i<n;i++){
        cin>>a;
        v.pb(make_pair(a,i));
    }
    sort(be(v));
    int num=0;
    for(int i=0;i<n;i++){
        if((v[i].second-i)%2)num++;
    }
    cout <<num/2<<endl;
    return 0;
}



Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define fi first
#define sc second
typedef pair<int,int> P;
typedef long long ll;
multiset<P>S[100005];
int n,q,num[100005];
vector<int>edge[100005];
int col[100005],id=1;
int dep[100005],up[100005][19];
void dfs(int v,int u){
	num[v] = id++;
	up[v][0] = u; if(u == -1) dep[v] = 0; else dep[v] = dep[u]+1;
	rep(i,edge[v].size()){
		if(edge[v][i]==u) continue;
		dfs(edge[v][i],v);
	}
}
int ans[100005];
int lca(int a,int b){
	if(dep[a] > dep[b]) swap(a,b);
	int D = dep[b]-dep[a];
	rep(i,18) if(((D>>i)&1)) b = up[b][i];
	if(a == b) return a;
	for(int i=17;i>=0;i--) {
		if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
	}
	return up[a][0];
}
int dist(int a,int b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}
void add(int c,int v){
	if(S[c].empty()){
		S[c].insert(P(num[v],v));
		return;
	}
	else if(S[c].size() == 1){
		int x = (*S[c].begin()).sc;
		int D = dist(x,v);
		S[c].insert(P(num[v],v));
		ans[c] += D;
		return;
	}
	else{
		auto it = S[c].lower_bound(P(num[v],v));
		int D;
		if(it == S[c].begin()){
			int a = (*it).sc; auto itt = S[c].end(); itt--; int b = (*itt).sc;
			D = -dist(a,b)+dist(a,v)+dist(b,v); D/=2;
		}
		else if(it == S[c].end()){
			it--;int a = (*it).sc; auto itt = S[c].begin(); int b = (*itt).sc;
			D = -dist(a,b)+dist(a,v)+dist(b,v); D/=2;
		}
		else{
			int a = (*it).sc; it--; int b = (*it).sc;
			D = -dist(a,b)+dist(a,v)+dist(b,v); D/=2;
		}
		S[c].insert(P(num[v],v));
		ans[c] += D;
		return;
	}
}
void rem(int c,int v){
	if(S[c].size() == 1){
		S[c].erase(P(num[v],v));
		return;
	}
	else if(S[c].size() == 2){
		auto it = S[c].begin();
		int x = (*it).sc;
		if(x == v){ it++; x = (*it).sc; }
		
		int D = dist(x,v);
		S[c].erase(P(num[v],v));
		ans[c] -= D;
		return;
	}
	else{
		auto it = S[c].lower_bound(P(num[v],v));
		int D;
		if(it == S[c].begin()){
			it++; int a = (*it).sc; auto itt = S[c].end(); itt--;
			int b = (*itt).sc;
			D = dist(a,b)-dist(a,v)-dist(b,v); D/=2;
		}
		else{
			it++;
			if(it == S[c].end()){
				it--; it--; int a = (*it).sc; auto itt = S[c].begin(); 
				int b = (*itt).sc;
				D = dist(a,b)-dist(a,v)-dist(b,v); D/=2;
			}
			else{
				int a = (*it).sc; it--; it--;int b = (*it).sc;
				D = dist(a,b)-dist(a,v)-dist(b,v); D/=2;
			}
		}
		S[c].erase(P(num[v],v));
		ans[c] += D;
		return;
	}
}
int main(){
	scanf("%d",&n);
	rep(i,n-1){
		int a,b; scanf("%d%d",&a,&b);
		edge[a].pb(b);
		edge[b].pb(a);
	}
	dfs(1,-1);
	rep(j,18) repn(i,n){
		if(up[i][j] == -1) up[i][j+1] = -1;
		else up[i][j+1] = up[up[i][j]][j];
	}
	repn(i,n){
		scanf("%d",&col[i]);
		add(col[i],i);
	}
	scanf("%d",&q);
	rep(i,q){
		char ch; scanf(" %c",&ch);
		if(ch == 'Q'){
			int a; scanf("%d",&a);
			if(S[a].empty()) puts("-1");
			else printf("%d\n",ans[a]);
		}
		else{
			int a,b; scanf("%d%d",&a,&b);
			rem(col[a],a);
			col[a] = b;
			add(col[a],a);
		}
	}
}



Measured memory_bytes: 31300
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = long long;

#define REP(i, a) for (int i = 0; i < (a); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a)-1; i >= (b); --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond, yes, no) \
    { cout << ((cond) ? (yes) : (no)) << endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(), (list).rend())
#define ASSERT(cond, mes) assert(cond&& mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template <typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

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

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())
    is >> v[i];
    return is;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a) n = a;
    if (n > b) n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

template <typename T>
std::vector<T> enum_div(T n) {
    std::vector<T> ret;
    for (T i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) { ret.push_back(n / i); }
        }
    }
    return ret;
}

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

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

struct ToUpper {
    char operator()(char c) {
        return toupper(c);
    }
};

struct ToLower {
    char operator()(char c) {
        return tolower(c);
    }
};

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

    int H, W;
    cin >> H >> W;
    vector<vector<int>> C(10, vector<int>(10));
    cin >> C;
    vector<vector<int>> A(H, vector<int>(W));
    cin >> A;

    REP(k, 10) {
        REP(i, 10) {
            REP(j, 10) {
                C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
            }
        }
    }

    int ans = 0;
    REP(h, H) {
        REP(w, W) {
            if (A[h][w] == -1) continue;
            ans += C[A[h][w]][1];
        }
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main(){
    int n,d,x; cin >> n >> d >> x;
    vector<int> a;

    for(int i = 0; i < n; i++){
        int b; cin >> b;
        a.push_back(b);
    }

    int count = 0;
    for(int i = 0; i < n; i++){
        int num = 1;
        count++;
        while(1){
            num += a[i];
            if(num > d)break;
            count++;
        }
    }
    cout << count + x << endl;
    return 0;
}

Measured memory_bytes: 256
/**
*    created: 03.07.2020 02:00:52
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
const long double pi = acos(-1.0);
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    string s, t;
    cin >> s >> t;

    auto ctoi2 = [&] (char c) {
        if (c >= 'a' && c <= 'z') return c - 'a';
        return -1;
    };

    int ma = -1;
    int mi = INF;

    rep(i,s.size()) {
        int tmp = ctoi2(s[i]);
        chmin(mi,tmp);
    }
    rep(i,t.size()) {
        int tmp = ctoi2(t[i]);
        chmax(ma,tmp);
    }

    bool ok = true;
    if (!(s.size() < t.size())) ok = false;
    else {
        map<char,int> mp;
        rep(i,t.size()) mp[t[i]]++;
        rep(i,s.size()) {
            if (mp[s[i]] == 0) ok = false;
        }
    }


    if (mi < ma || ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3652
# -*- coding: utf-8 -*-
def gcd(a,b):
    a, b = max(a,b), min(a,b)
    d = 1
    while a > b > 0:
        if a&1 == b&1 == 0:
            a >>= 1
            b >>= 1
            d <<= 1
        else:
            a, b = b, a%b
    d *= a
    return d

def solve():
    N, M = map(int,input().split())
    S = input()
    T = input()
    D = gcd(N,M)
    a = N//D
    b = M//D
    for i, j in zip(range(0,N,a), range(0,M,b)):
    	if S[i] != T[j]:
    		return '-1'
    L = N*M//D
    return str(L)

if __name__ == '__main__':
    print(solve())

Measured memory_bytes: 3316
k,n = map(int, input().split())

a= list(map(int,input().split()))
sa=[0]*n
for i in range(n-1):
    sa[i]=a[i+1]-a[i]
    sa[n-1]=a[0]+(k-a[n-1])
#print(sa)
ans=max(sa)
ans=k-ans
print(ans)

Measured memory_bytes: 32148
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
const int MAX=3000;

signed main(){
    int N;cin>>N;
    vector<int>X(N);
    vector<int>C(N);
    REP(i,N)cin>>X[i];
    C=X;
    sort(C.begin(),C.end());
    int ls=C[N/2-1];
    int rs=C[N/2];
    REP(i,N){
        cout<<(X[i]<=ls?rs:ls)<<endl;
    }
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

int main() {

  long long N;
  cin >> N;
  vector<vector<int>> neighbors(N);
  ll colorNum;
  ll color;
  vector<vector<int>> colorlist(N);
  map<pair<int,int>,int> mp;
  vector<int> ans(N-1);
  long long maxcolor;

  for (int i = 1; i < N; i++) {
    int a, b;
    cin >> a >> b;
    neighbors.at(a-1).push_back(b);
    neighbors.at(b-1).push_back(a);
    if ( a > b ){
       swap(a,b);
    }
    mp[make_pair(a,b)] = i-1;
  }
  maxcolor = neighbors[0].size();
  REP(int, i, 1, N){
    if ( maxcolor < neighbors[i].size())
      maxcolor = neighbors[i].size();
  }
  vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
  queue<int> que;

  dist[0] = 0;
  que.push(0); 

  while ( !que.empty() ) {
      int v = que.front(); // キューから先頭頂点を取り出す
      que.pop();
      color = 1;
      for ( int nv : neighbors[v] ) {
        if ( dist[nv-1] != -1 ) continue; // すでに発見済みの頂点は探索しない
        dist[nv-1] = 1;
        que.push(nv-1);
        if ( !colorlist[v].empty() ){
          for ( int nc : colorlist[v] ){
            if ( color == nc ) color++;
          }
        }
        /* */
        int a,b;
        a = v+1; b = nv;
        if ( a > b ) swap(a,b);
        ans[mp[make_pair(a,b)]] = color;
        /* 彩色 */
        colorlist.at(v).push_back(color);
        colorlist.at(nv-1).push_back(color);
        //cout << v + 1 << " " << nv << " " << "color: " << color << endl;
        color++;
      }
  }
  printf("%d\n",maxcolor);
  REP(int,i,0,N-1) printf("%d\n",ans[i]);
}

Measured memory_bytes: 18688
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int count(int N)
{
        int cnt = 0;
        while (N)
        {
                cnt += N % 10;
                N /= 10;
        }
        return cnt;
}

int main()
{
        int N;
        cin >> N;
        map<int, int> mp;
        rep(i, N)
        {
                int a;
                cin >> a;
                mp[a]++;
        }
        cout << mp.size() << endl;
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int, int>;
using pll = pair<int, int>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

bool dfs(const Graph &G, int v, int vdir, pint &num, vector<int> &dir) {
    bool res = true;
    dir[v] = vdir;
    if (vdir == 1) ++num.first;
    else if (vdir == -1) ++num.second;
    for (auto nv : G[v]) {
        if (dir[nv] == 0) {
            if (!dfs(G, nv, -vdir, num, dir)) res = false;
        }
        else if (dir[nv] != -vdir) res = false;
    }
    return res;
}

bool isbipartite(const Graph &G, vector<pint> &nums) {
    bool res = true;
    int N = (int)G.size();
    vector<int> dir(N, 0);
    for (int v = 0; v < N; ++v) {
        if (dir[v] != 0) continue;
        pint num = {0, 0};
        if (!dfs(G, v, 1, num, dir)) res = false;
        nums.push_back(num);
    }
    return res;
}

int main(){
    ll n, m; cin >> n >> m;
    Graph edges(n, vector<int>(n,1));
    for(int i = 0; i < m; ++i){
	    int a, b; cin >> a >> b;
	    --a; --b;
	    edges[a][b] = 0;
	    edges[b][a] = 0;
    }

    Graph G(n);
    for (int i = 0; i < n; ++i) {
		for (int j = i+1; j < n; ++j){
			if (edges[i][j]) {
				G[i].push_back(j);
				G[j].push_back(i);
			}
		}
	}

	// 二部グラフの構成
    vector<pint> nums;
    if (!isbipartite(G, nums)) {
        cout << -1 << endl;
        return 0;
    }

	// 左右の割り振りを適切に選択することで、達成可能な個数を求める
	// 部分和問題
	int num_size = nums.size();
	vector<vector<bool>> dp(num_size + 1, vector<bool>(n + 1, false));
	dp[0][0] = true;
	for (int i = 0; i < num_size; ++i) {
		for (int j = 0; j <= n; ++j) {
			if (j >= nums[i].first)  dp[i + 1][j] = dp[i + 1][j] | dp[i][j - nums[i].first];
			if (j >= nums[i].second) dp[i + 1][j] = dp[i + 1][j] | dp[i][j - nums[i].second];
		}
	}
	/* 配列使いまわし
    vector<bool> dp(N+1, false);
    dp[0] = true;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = N; j >= 0; --j) {
            if (dp[j] == false) continue;
            dp[j] = false;
            dp[j + nums[i].first] = true;
            dp[j + nums[i].second] = true;
        }
    }*/

	// 左右に割り振る個数を可能な限り均等にしたい(N/2に近づけたい)
    long long a = -1;
    long long dist = n;
    for (int i = 0; i <= n; ++i) {
        if (!dp[num_size][i]) continue;
        if (dist > abs(i - n/2)) dist = abs(i - n/2), a = i;
    }
    long long b = n-a;

	// クリークの辺数は N*(N-1)/2
    cout << a*(a-1)/2 + b*(b-1)/2 << endl;
}

Measured memory_bytes: 5120