akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,tr[maxn][3],tag[maxn],N,cnt=1,id[maxn],tot,r[maxn];
char s[maxn];

void ins(int v) {
    int x=1,p=v;
    for(int i=1;i<=n;i++) {
        int t=v%3;v/=3;
        if(!tr[x][t]) tr[x][t]=++cnt;
        x=tr[x][t];
    }id[x]=p;
}

void push(int x) {tag[x]^=1,swap(tr[x][1],tr[x][2]);}

void pushdown(int x) {
    if(tag[x]) {
        for(int i=0;i<3;i++) push(tr[x][i]);
        tag[x]=0;
    }
}

void dfs(int x) {
    if(!tr[x][0]) return ;
    pushdown(x);
    swap(tr[x][0],tr[x][1]),swap(tr[x][0],tr[x][2]);
    dfs(tr[x][0]);
}

void get(int x,int v,int t) {
    if(!tr[x][0]) {
        r[id[x]]=v;
        return ;
    }
    pushdown(x);
    for(int i=0;i<3;i++) get(tr[x][i],v+t*i,t*3);
}

int main() {
    read(n);N=pow(3,n);
    for(int i=0;i<N;i++) ins(i);
    scanf("%s",s+1);int m=strlen(s+1);
    for(int i=1;i<=m;i++)
        if(s[i]=='S') push(1);
        else dfs(1);
    get(1,0,1);
    for(int i=0;i<N;i++) printf("%d ",r[i]);
    return 0;
}


Measured memory_bytes: 22048
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    string str;
    cin>>str;
    int ba=0;
    vector<int>player(n,0);
    for(int i=0;i<str.size();i++){
      switch(str[i]){
      case 'S':
	ba+=player[i%n]+1;
	player[i%n]=0;
	break;
      case 'M':
	player[i%n]++;
	break;
      case 'L':
	player[i%n]+=ba+1;
	ba=0;
	break;
      }
    }
    sort(player.begin(),player.end());
    for(int i=0;i<player.size();i++)
      cout<<player[i]<<" ";
    cout<<ba<<endl;
  }
  return 0;
}

Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define sz(v) (ll)(v).size()
#define int long long
#define mod 1000000007

void solve() {
        int x, y; cin >> x>> y;
        map<int, int> mp;
        lp(i, y) {
                int p; cin >> p;
                mp[p]++;
        }
        int an1= 0, an2= 0;
        for (int i = x; ; i++) {
                if (mp.count(i)) continue;
                else {
                        an1= i;
                        break;
                }
        }
        for (int i = x; ; i--) {
                if (mp.count(i)) continue;
                else {
                        an2= i;
                        break;
                }
        }
        if (x-an2 <= an1- x) cout << an2<< "\n";
        else cout << an1<< "\n";

}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int t = 1;
        //cin >> t;
        lp(i, t) {
                solve();
        }
return 0;
}


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

namespace _0030
{

    struct ID
    {
        internal int ken;
        internal int rank;
    }
    
    class Program
    {
        
        
        static void Main(string[] args)
        {

            string[] str = Console.ReadLine().Split(' ');
            int n = int.Parse(str[0]);
            int m = int.Parse(str[1]);

            var ans = new ID[m + 1];

            var data = new Dictionary<long, int>[n + 1];
            var sortdata = new Dictionary<long, int>[n + 1];

            //インスタンスを作成
            for(int i = 1; i <= n; i++)
            {
                data[i] = new Dictionary<long, int>();
                sortdata[i] = new Dictionary<long, int>();
            }

            int p;
            long y;
            //i市情報からデータを設定
            for(int i = 1; i <= m; i++)
            {
                str = Console.ReadLine().Split(' ');
                p = int.Parse(str[0]);
                y = long.Parse(str[1]);

                data[p][y] = i;

            }

            //各県に対してkey(年数)を基準にソート
            for(int i = 1; i <= n; i++)
            {
                sortdata[i] = data[i].OrderBy((x) => x.Key).ToDictionary(x => x.Key, x => x.Value);                
            }

            
            int cnt = 0;
            for(int i = 1; i <= n; i++)
            {
                cnt = 1;
                foreach(var s in sortdata[i])
                {
                    //Console.WriteLine($"i = {i} {s.Key} {s.Value}");
                    ans[s.Value].ken = i;
                    ans[s.Value].rank = cnt;
                    cnt++;
                }
            }

            for(int i = 1; i <= m; i++)
            {
                Console.WriteLine(string.Format("{0:d6}{1:d6}", ans[i].ken, ans[i].rank));
            }

        }
    }
}

Measured memory_bytes: 72348
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const int N = 105;
int cnt[N];

void res(bool t){
    if(t)
        cout << "Possible\n";
    else
        cout << "Impossible\n";
    exit(0);
}

int main(){
    fastIO;
    int n;
    cin >> n;
    if(n == 2)
        res(true);
    int a;
    int mn = n;
    int mx = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> a;
        mn = min(mn, a);
        mx = max(mx, a);
        cnt[a] ++ ;
    }
    if(cnt[mn] > 2)
        res(false);
    int p = mn + 1;
    int z = mn;
    if(cnt[mn]==2) z--;
    for(int i = 0 ; i < z; i ++ ){
        if(cnt[p] < 2)
            res(false);
        p ++ ;
    }
    while(p < N){
        if(cnt[p] > 0)
            res(false);
        p ++ ;
    }
    res(true);
    return 0;
}

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

using namespace std;

int main(void){
    int P,Q,R;
    cin >> P >> Q >> R;
    int a[3]={};
    a[0] = P+Q;
    a[1] = Q+R;
    a[2] = R+P;
    sort(a,a+3);
    cout << a[0] << endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


class Node:

    def __init__(self):
        self.comparison_list = []
        
        self.height = 0
        
        self.id_list = []


def main():
# 整数の入力
    
    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    h_list = [int(x) for x in input().split(' ')]
    node_list = []
    for h in h_list:
        node = Node()
        
        node.height = h
        node_list.append(node)

    for i in range(m):
        s = [int(x) for x in input().split(' ')]
        a = s[0] - 1
        b = s[1] - 1
        node_list[a].id_list.append(b)
        node_list[b].id_list.append(a)

    for n in node_list:
        if len(n.id_list) == 0:
            n.comparison_list.append(True)
        else:
            n.id_list = list(set(n.id_list))
            # もしまだ調べていなかったら
            if len(n.comparison_list) == 0:
                for id in n.id_list:
                    target = node_list[id]
                    if n.height > target.height:
                        n.comparison_list.append(True)
                        target.comparison_list.append(False)                       
                        
                    else:
                        n.comparison_list.append(False)
    
    print(len([x for x in node_list if all(x.comparison_list)]))

if __name__ == '__main__':
    main()

Measured memory_bytes: 54824
// finish date: 2018/08/07
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;

//dijkstra(開始ノード、ノード数、edge[頂点名][距離、行先の頂点])
vi dijkstra(int s, int V, vector<vector<pii>> edge) {
    vi dist(V, INF); //INFの値がこれでいいか確認するべき
    vb used(V, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, s));
    while (!pq.empty()) {
        int d, t;
        tie(d, t) = pq.top();
        pq.pop();
        if (used[t]) continue;
        used[t] = true;
        dist[t] = d;
        for (pii e:edge[t]) {
            if (dist[e.second] < d + e.first) continue;
            pq.push(pii(d + e.first, e.second));
        }
    }
    return dist;
}

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

    vector<vector<pii>> edge(K);
    rep(i, K) {
        edge[i].push_back(pii(1, (i + 1) % K));
        edge[i].push_back(pii(0, (i * 10) % K));
    }

    cout << dijkstra(1, K, edge)[0] + 1 << endl;

    return 0;
}



Measured memory_bytes: 12288
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

cc  = inputs[0][2]
bbs = inputs[1]
srcs = inputs[2..-1]

# body
if $debugFlag
  p cc
  p bbs
  p srcs
end

cnt = 0
srcs.each do |s_i|
  sum = 0
  bbs.size.times do |j|
    sum += bbs[j]*s_i[j]
  end
  cnt += 1 if sum + cc > 0
end

puts cnt


Measured memory_bytes: 1788
a, v = [int(i) for i in input().split()]
b, w = [int(i) for i in input().split()]
t = int(input())
if a<b:
  print("YES") if a+(v*t) >= b+(w*t) else print("NO")
else:
  print("YES") if a-(v*t) <= b-(w*t) else print("NO")

Measured memory_bytes: 9196
#include<iostream>

using namespace std;

int map[11][10001];
int turn[11];
int r,c,ans;

void serch(int n)
{
	int i,j;
	if(n==r)
	{
		int ss;
		int ssans=0;
		for(i=0;i<c;i++)
		{
			ss=0;
			for(j=0;j<r;j++)
			{
//				cout << map[j][i] << " " ;
				if(turn[j]==0)
				{
					if(map[j][i]==1)
						ss++;
				}
				else if(turn[j]==1)
				{
					if(map[j][i]==0)
						ss++;
				}
			}
//			cout << endl;
			if(ss<=r/2)
			{
//				cout << "ss1:" << r-ss << endl;
				ssans+=r-ss;
			}
			else
			{
//				cout << "ss2:" << ss << endl;
				ssans+=ss;
			}
//			cout << "ssans:" << ssans << endl;
		}
		if(ans<ssans)
			ans=ssans;
		return ;
	}
		turn[n]=0;
		serch(n+1);
		turn[n]=1;
		serch(n+1);
	return ;
}
int main()
{
	int i,j;
	
	for(;;)
	{
		cin >> r >> c ;
		if(r==0 && c==0)
			break;
		
		for(i=0;i<r;i++)
		{
			for(j=0;j<c;j++)
			{
				cin >> map[i][j] ;
			}
		}
		
		ans=0;
		
		serch(0);
		
		cout << ans << endl;
	}
}

Measured memory_bytes: 1260
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
sss = []
for _ in range(n):
    sss.append(input())

m = {}
for s in sss:
    if s in m:
        m[s] += 1
    else:
        m[s] = 1

items = m.items()
items = list(sorted(items, key=lambda i:i[0]))
items = list(sorted(items, key=lambda i: i[1], reverse=True))

max_ = items[0][1]
i = 0
while i<len(items) and items[i][1] == max_:
    print(items[i][0])
    i+=1


Measured memory_bytes: 115152
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

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

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)
 
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

int main(){
    int n, c, ans = 0;
    cin >> n;
    vector<int> v(n);
    REP(i, n) cin >> v[i];
    REP(i, n){
        cin >> c;
        v[i] = v[i] - c;
        if(v[i] > 0) ans += v[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
use proconio::{input, fastout};

#[fastout]
fn main() {
  input!{
    l:i64,
    r:i64,
    d:i64
  }
  let mut ans = 0;
  for i in l..=r {
      if i % d == 0{
        ans += 1;
      }
  }
  println!("{}",ans);
}



Measured memory_bytes: 2152
#include <bits/stdc++.h>
using namespace std;
 
typedef signed long long ll;
const int MX = 1e6 + 5;
int p[MX];
vector<ll> prime;
 
void sieve() {
	int sq = sqrt(MX) + 1;
	for(int i = 3; i <= sq; i+= 2) {
		if(!p[i]) {
			for(int j = i * i; j < MX; j += (i + i)) {
				p[j] = 1;
			}
		}
	}
	
	prime.push_back(2LL);
	for(int i = 3; i < MX; i += 2) {
		if(!p[i]) prime.push_back((ll)i);
	}
}

int solve(ll n) {
	int sz = prime.size(), cnt = 1;
	for(int i = 0; i < sz && (prime[i] * prime[i] <= n); i++) {
		if(n % prime[i] == 0) {
			cnt++;
			for(; n % prime[i] == 0; n /= prime[i]);
		}
	}
	if(n != 1LL) cnt++;
	return cnt;
}
 
int main() {
	ll A, B, C;
	cin >> A >> B;
	C = __gcd(A, B);
	sieve();
	cout << solve(C) << endl;
	return 0;
}

Measured memory_bytes: 5240
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	int r;
	int g;
	int b;
	public void run() {
		Scanner sc = new Scanner(System.in);
		r = sc.nextInt();
		g = sc.nextInt();
		b = sc.nextInt();
		int ans = r*100 + g*10 + b;
		if(ans % 4 == 0)System.out.println("YES");
		else System.out.println("NO");
		sc.close();
	}
}

Measured memory_bytes: 21712
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    swap = 0
    for i in range(N):
        if P[i] == i + 1:
            if i < N - 1: P[i], P[i+1] = P[i+1], P[i]
            swap += 1
    print(swap)
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 13876
def ketawa(x):
    l = list(str(x))
    wa = 0
    for a in l:
        wa += int(a)
    return wa

n = int(input())
lst = list(str(n))
keta = len(str(n))




nine = int("".join([lst[0]] + ["9"]*(keta-1)))

if nine <= n:
    print(ketawa(nine))
else:
    lst_head = str(int(lst[0]) - 1)
    nine = int("".join([lst_head] + ["9"]*(keta-1)))
    print(ketawa(nine))

Measured memory_bytes: 9200
S=input()
#Sに０は含まれない。
N=len(S)
#後続の処理でSを加算することはなく、事前に加算する。
ans=0

plus_place=[]
#S(i)の直後に”＋”を挿入する場合plus_place[i]はTrue

#桁数の関係でS=1のみ例外として処理
if int(S) == 1:
    print(1)
    exit()

for i in range(2**(N-1)):
    tmp_bin=bin(i)[2:]
    while(len(tmp_bin) < N-1):
        tmp_bin = '0' + tmp_bin
    plus_place.append(tmp_bin)
#plusが入りうる全てのパターンを網羅

for s in plus_place:
    tmp = 0
    next_index=0
    for i,b in enumerate(s) :
        #各sごとの計算用のリスト
        if b == "1":
            tmp += int(S[next_index:i+1])
            next_index=i+1
        if i == N-2:
            tmp += int(S[next_index:i+2])
#    print('add',tmp)
#  print('i is',i)
#  print('index is',next_index)
    ans += tmp
                      
    
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
struct edge {
	int u, v, l;
	edge (int U, int V, int L): u(U), v(V), l(L) {}
	friend bool operator< (const edge &a, const edge &b) {
		return a.l > b.l;
	}
};
int n, mat[310][310]; long long nn[310][310];
priority_queue<edge> Q;
int main () {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> mat[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				if (mat[i][k] + mat[k][j] < mat[i][j]) {
					cout << -1 << endl;
					exit(0);
				}
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <=n; j++)
			Q.push(edge(i, j, mat[i][j]));
	long long ans = 0;
	memset(nn, 0x3f, sizeof nn);
	for (int i = 1; i <= n; i++)
		nn[i][i] = 0;
	while (!Q.empty()) {
		edge w = Q.top(); Q.pop();
		if (nn[w.u][w.v] <= w.l) continue;
		ans += w.l;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				nn[i][j] = min(nn[i][j], min(
					nn[i][w.u] + w.l + nn[w.v][j],
					nn[i][w.v] + w.l + nn[w.u][j]
				));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2040
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) obj.begin(),obj.end()
#define pb(obj) push_back(obj)
#define REP(i,N) for(int i=0;i<N;i++)
typedef long long ll;
const ll MOD=1000000007;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    vector<int>height(N+1);
    height[0]=0;
    for(int i=1;i<=N;i++){
        cin>>height[i];
    }
    vector<int>sa(N);
    for(int i=0;i<N;i++){
        sa[i]=height[i+1]-height[i];
    }
    for(int i=0;i<N;i++){
        if(sa[i]<=-2){cout<<"No"<<endl;exit(0);}
        if(sa[i]==-1)if(i!=N-1)sa[i+1]--;
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 1024
#include<iostream>

using namespace std;

int main(){
 int c[3][3];
  for(int i=0;i<3;i++){
   for(int j=0;j<3;j++){
    cin >> c[i][j];
   }
  }
 int a[3],b[3];
 for(int i=0;i<3;i++){
  b[i]=c[0][i];
 }
  bool res1=false,res2=false;
    for(int i=0;i<3;i++){
     a[i]=c[1][i]-b[i];
    }
  if(a[0]==a[1]&&a[1]==a[2]) res1=true;
  
  for(int i=0;i<3;i++){
     a[i]=c[2][i]-b[i];
    }
  if(a[0]==a[1]&&a[1]==a[2]) res2=true;
  
  if(res1&&res2) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}

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

int main()
{
	int n;
	cin >> n;
	int c[n],s[n],f[n];
	for(int i = 0;i<n;i++)
		cin >> c[i] >> s[i] >> f[i];
	for(int i = 0;i<n;i++)
	{
		int t = 0;
		for(int j = i; j < n-1; j++)
		{
			if(t < s[j]) t = s[j];
			else if(t % f[j] == 0);
			else t = t + f[j] - t%f[j];
			t += c[j];
		}

		cout << t << endl;
	}

}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= 2

offset = 0
for i in range(n):
    offset = a[i]-offset
x = offset/2

cur = x
for i in range(n):
    print(int(cur), end=' ')
    cur = a[i]-cur


Measured memory_bytes: 14028
package main

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

var (
	N, K int
	M, m int
)

func main () {
	r := bufio.NewReader(os.Stdin)
	fmt.Fscan(r, &N)
	fmt.Fscan(r, &K)

	mod := 1000000007
	ans := 0
	for k := K; k <= N + 1; k++ {
		M = sumOfNums(N - k + 1, N)
		m = sumOfNums(0, k - 1)
		ans += M - m + 1
		ans %= mod
	}
	fmt.Println(ans)
}

func sumOfNums(l, r int) int {
	return (l + r) * (r - l + 1) / 2
}


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

typedef long long ll;
#define REP(i, n, m) for(int i = n; i < m; i++)
#define REPR(i, n, m) for(int i = n; i >= m; i--)
#define LREP(i, n, m) for(ll i = n; i < m; i++)
#define LREPR(i, n, m) for(ll i = n; i >= m; i--)

#define P pair<int, int >


const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;



//---functions---//
int gcd(int a, int b){
    if(a < b) swap(a, b);
    return b?gcd(b, a%b):a;
}

int s2i(string num){stringstream ss; ss << num << flush; int n; ss >> n; return n;}
string i2s(int n){stringstream ss; ss << n << flush; return ss.str();}

bool firstCompare(const P& firstElof, const P& secondElof){
    return firstElof.first < secondElof.first;
}
bool secondCompare(const P& firstElof, const P& secondElof){
    return firstElof.second < secondElof.second;
}
//---------------//


int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s; 
    cin >> t;
    map<char, vector<ll>> m;
    LREP(i, 0L, s.size()){
        m[s[i]].push_back(i + 1);
    }
    LREP(i, 0L, s.size()){
        m[s[i]].push_back(i + 1 + s.size());
    }
    ll pos = 0L;
    ll loop = 0L;
    LREP(i, 0L, t.size()){
        if(m[t[i]].size() == 0){
            cout << -1 << '\n';
            return 0;
        } 
        vector<ll>::iterator it = upper_bound(m[t[i]].begin(), m[t[i]].end(), pos);
        ll next_pos = *it;
        if(next_pos > s.size()){
            ++loop;
            next_pos -= s.size();
        }
        pos = next_pos;
    }
    cout << loop * s.size() + pos << '\n';
}


Measured memory_bytes: 2756
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main() {
	int N;
	int dp[2][100]={};
	int a[2][100];
	cin >> N;
	for(int j=0;j<2;j++)
	for(int i=0;i<N;i++){
		cin >> a[j][i];
	}
	dp[0][0]=a[0][0];
	for(int j=1;j<N;j++){
		dp[0][j]=dp[0][j-1]+a[0][j];
	}
	dp[1][0]=a[0][0]+a[1][0];
	for(int j=1;j<N;j++){
		dp[1][j]=max(dp[1][j-1],dp[0][j])+a[1][j];
	}
	cout << dp[1][N-1] << endl;


	return 0;
}



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

int main(){
    int n ;
    cin >> n ;
    vector<int64_t> s(n+1) ;
    s.at(0) = 0 ;
    int64_t a ;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a ;
        s.at(i+1) = s.at(i) + a ;
    }
    sort(s.begin(),s.end() ) ;
    int64_t ans = 0 ;
    int64_t now = s.at(0) ;
    int64_t chain = 0 ;
    for (size_t i = 0; i < n+1; i++)
    {
        if (s.at(i) == now)
        {
            chain ++ ;
        }else
        {
            now = s.at(i) ;
            ans += chain*(chain-1)/2 ;
            chain = 1 ;
        }
        
    }
    ans += chain*(chain-1)/2 ;
    cout << ans << endl ;
}


Measured memory_bytes: 1792
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l[] = new int[n];
        int wa = 0;
        for (int i = 0; i < n; i++) {
            l[i] = sc.nextInt();
            wa += l[i];
        }
        Arrays.sort(l);
        wa = wa - l[n - 1];
        if (wa > l[n - 1]) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }     //最小公倍数
using Graph = vector<vector<ll>>;
ll inf=300000000000000000;
const double PI = 3.14159265358979323846;
int main(){
  ll n,m;
  cin >> n >> m;
  ll a[n+1];
  a[0]=0;
  rep(i,n)cin >> a[1+i];
  map<ll,ll> k;
  k[0]++;
  rep(i,n){
    a[i+1]=(a[i+1]+a[i])%m;
    k[a[i+1]]++;
  }
  ll ans=0;
  for(auto p: k){
    ll o=p.second;
    ans+=o*(o-1)/2;
  } 
  cout << ans << endl;
}   


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int main()
{
int a,b,k;
cin>>a>>b>>k;
set<int> st;
for(int i=1;i<=a;i++)
{
if(a%i==0)
{
st.insert(i);
}
}
int ans=0;
for(int i=b;i>=1;i--)
{
if(b%i==0 && st.count(i))
{
k--;
if(k==0)
{
ans=i;
}
}
}
cout<<ans<<endl;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=500010;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n;
    cin>>n;
    ll c=0;
    for(ll i=0;i<n;++i){
        ll x;cin>>x;
        if(x%2==0){
            if(x%3==0||x%5==0){}
            else{c=1;}
        }
    }
    if(c==0){cout<<"APPROVED";}
    else{cout<<"DENIED";}

    return (0);
}


Measured memory_bytes: 256
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    ll w,h,x,y;
    string str;
	cin>>n;
    n++;
    vector<ll> v(n);
    rep(i,n-1) cin>>v[i];
    v[n-1]=0;
    sum+=abs(v[0]);
    sum+=abs(v[n-1]);
    rep(i,n-1) sum+=abs(v[i+1]-v[i]);
    cout<<sum-abs(v[n-1]-v[0])-abs(v[0]-v[1])+abs(v[1]-v[n-1])<<endl;
    rep(i,n-2) cout<<sum-abs(v[i+2]-v[i+1])-abs(v[i+1]-v[i])+abs(v[i+2]-v[i])<<endl;
    //cout<<sum-abs(v[n-2]-v[n-1])-abs(v[0]-v[n-1])+abs(v[n-2]-v[0]);
    return 0;
}



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

int main()
{
  string sa,sb,u;
  cin >> sa >> sb;
  int a,b;
  cin >> a >> b;
  cin >> u;
  if(u==sa)cout << a-1 << " " << b << endl;
  else{
    cout << a << " " << b-1 << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>
#include <cstdint>

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

using namespace std;
typedef long long ll;

const ll INF = 1LL << 62;
const int MOD = 1e9 + 7;


int main() {
    int n, W; cin >> n >> W;
    vector<int> w(n), v(n); rep(i, n) cin >> w[i] >> v[i];

    vector<vector<ll>> dp(n+1, vector<ll>(1e5+1, INF));
    dp[0][0] = 0;

    rep(i, n) rep(j, 1e5+1) {
        if (j+v[i] <= 1e5) dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]], dp[i][j] + w[i]);
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
    }


    for (int j = 1e5; j >= 0; j--) {
        if (dp[n][j] <= W) {
            cout << j << endl;
            break;
        }
    }


    return 0;
}

Measured memory_bytes: 80256
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define itr(it,a) for( auto it = (a).begin(); it != (a).end(); ++it )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

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

using ll = long long;

ll N, ans;

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

  repi( i, 1, N+1 )
  {
    if( i%15 == 0 )
    {}
    else if( i % 3 == 0 )
    {}
    else if ( i% 5 == 0 )
    {}
    else
      ans += i;
  }

  std::cout << ans << std::endl;

  return 0;
}

Measured memory_bytes: 3192
#if 0

#endif

#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void p(A a){cout << (a) << endl;}
template<class A,class B>void p(A a,B b){cout << a << " "  ;p(b);}
template<class A,class B,class C>void p(A a,B b,C c){cout << a << " " ;p(b,c);}
template<class A,class B,class C,class D>void p(A a,B b,C c,D d){cout << a << " " ;p(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for copy
// for(int i=0;i<N;++i) {

int main(void) {
  int n;cin>>n;
  string s;cin>>s;
  int cnt=0;
  for(int i=0;i<n-2;++i) {
    if(s.substr(i,3)=="ABC") cnt++;
  }
  p(cnt);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <cstring>

using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for (ll i = 0; i < (n); ++i)

int n;
int cnt[4];
string Str[4] = {"AC", "WA", "TLE", "RE"};

int main() {
    cin >> n;
    rep(i,n){
        string s;
        cin >> s;

        switch(s[0]){
            case 'A' : cnt[0]++; break;
            case 'W' : cnt[1]++; break;
            case 'T' : cnt[2]++; break;
            case 'R' : cnt[3]++; break;
        }
    }

    rep(i,4) cout << Str[i] << " x " << cnt[i] << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
int sum[maxn];
void pre()
{
    sum[1]=1;
    for(int i=2;i<maxn;i++)sum[i]=sum[i-1]+i;
}
int judge(int x)
{
    int tmp=0;
    for(int i=1;i<maxn;i++){
        if(sum[i]<x) tmp=i;
        else break;
    }
    return tmp+1;
}
int main()
{
    int x;
    pre();
    scanf("%d",&x);
    printf("%d\n",judge(x));
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
//登録しよう！→ https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define gre greater //sortを降順にする
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
ll N;
vector<vector<tuple<ll,ll>>> A;

bool j(int bit){
   for (int i = 0; i < N; i++) {
     if(!(bit & (1 << i)))continue;
     for (auto xy : A[i]) {
       if(get<1>(xy) == 1 && !(bit & (1 << get<0>(xy))))return false;
       if(get<1>(xy) == 0 && (bit & (1 << get<0>(xy))))return false;
     }
   } 
 return true;
}

int main(){
  cin >> N;
  A.resize(N);
  for (int i = 0; i < N; i++) {
    ll a;
    cin >> a;
    for (int l = 0; l < a; l++) {
      ll x,y;
      cin >> x >> y;
      A[i].pb(make_tuple(x-1,y));
    }
  }
  
  ll ans = 0;
  for (int bit = 0; bit < (1 << N); bit++) {
    if(j(bit)){
      ll c=0;
      for (int i = 0; i < N; i++){if(bit & (1 << i))c++;}
      ans = max(ans,c);
    }
  }
  cout << ans << endl;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N), h(N);
    rep(i, N) cin >> x[i] >> y[i] >> h[i];
    
    for (int Cx = 0; Cx <= 100; ++Cx) {
        for (int Cy = 0; Cy <= 100; ++Cy) {
            int H = -1;
            rep(i, N) {
                if (Cx == x[i] && Cy == y[i]) H = h[i];
            }
            if (H == -1) {
                rep(i, N) {
                    if (h[i] != 0) {
                        H = h[i] + abs(Cx - x[i]) + abs(Cy - y[i]);
                        break;
                    }
                }
            }
            if (H == -1) H = 1;
            
            bool judge = true;
            rep(i, N) {
                if (max(H - abs(Cx - x[i]) - abs(Cy - y[i]), 0) != h[i]) judge = false;
            }
            if (judge) {
                cout << Cx << " " << Cy << " " << H << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <cstdio>

int w, h, c[50][50], count = 0;

void search(int x, int y)
{
    c[y][x] = 0;

    for (int dx = -1; dx <= 1; ++dx)
    {
        for (int dy = -1; dy <= 1; ++dy)
        {
            if (x + dx < 0 || x + dx >= w || y + dy < 0 || y + dy >= h)
            {
                continue;
            }

            if (c[y + dy][x + dx] == 1)
            {
                search(x + dx, y + dy);
            }
        }
    }
}

bool sub_search()
{
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if (c[i][j] == 1)
            {
                search(j, i);
                count++;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    while (true)
    {
        scanf("%d %d", &w, &h);
        if (w == 0 && h == 0)
        {
            break;
        }

        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                scanf("%d", &c[i][j]);
            }
        }

        count = 0;

        while (sub_search())
        {
        }

        printf("%d\n", count);
    }
}


Measured memory_bytes: 2840
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, int>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

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

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

  int cnt = 0;

  if (a%2 != 0 || b%2 != 0 || c%2 != 0) {
    cout << cnt << endl;
    return 0;
  }

  while (a != b || b != c || c != a) {
    if (a%2 != 0 || b%2 != 0 || c%2 != 0) {
      cout << cnt << endl;
      return 0;
    }
    int aa = b/2 + c/2;
    int bb = c/2 + a/2;
    int cc = a/2 + b/2;
    a = aa;
    b = bb;
    c = cc;
    cnt++;
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

void depth(int,int);

int d[100000],k[100000],c[100000][20],g[100000],root,id;

int main()
{
  int i,n,id,j,p[100000],type[100000];

  scanf("%d",&n);

  for(j=0;j<n;j++) d[j]=0;

  for(j=0;j<n;j++){
    scanf("%d",&id);
    scanf("%d",&k[id]);

    for(i=0;i<k[id];i++){
      scanf("%d",&c[id][i]);

      	d[c[id][i]]= d[id] + 1;
  
      p[c[id][i]] = id;
    }

    if(d[id]==0){
 p[id] =-1;
    }
  }

  /*type*/
  for(j=0;j<n;j++){
    if(p[j]==-1) {
type[j] = 0;
 root = j;
    }
    else if(k[j]==0) type[j] = 1;
    else type[j] = 2;
  }

  depth(root,0);

  for(j=0;j<n;j++){
    printf("node %d: parent = %d, depth = %d, ",j,p[j],g[j]);

    if(type[j]==0) printf("root, ");
    else if(type[j]==1) printf("leaf, ");
    else printf("internal node, ");

    printf("[");
    for(i=0;i<k[j];i++){
      printf("%d",c[j][i]);  
      if(i!=k[j]-1) printf(", ");
    }
    printf("]\n");
  }

  return 0;
}

void depth(int v,int dep){
  int i;
  g[root]=0;
  if(k[v]==0) return;
  dep++;
  for(i=0;i<k[v];i++){    
    g[c[v][i]]=dep;
  }

  for(i=0;i<k[v];i++){
    depth(c[v][i],dep);
  }

}

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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int N; scanf("%d", &N);
  vector<int> C(N + 1), S(N + 1), F(N + 1);
  for (int i = 1; i < N; ++i) {
    scanf("%d %d %d", &C[i], &S[i], &F[i]);
  }
  for (int i = 1; i < N; ++i) {
    int t = S[i] + C[i];
    for (int j = i + 1; j < N; ++j) {
      if (t <= S[j]) { t = S[j] + C[j]; }
      else if ((t - S[j]) % F[j] == 0) { t += C[j]; }
      else {
        t += F[j] - (t % F[j]) + C[j];
      }
    }
    printf("%d\n", t);
  }
  printf("0\n");
  return 0;
}


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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

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

    ll ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            ans = max(ans, abs(a[i] - a[j]));
        }
    }
    cout << ans << endl;
    
    return 0;
}

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

#define PI 3.14159265358979323846264338327950288419

using namespace std;

int n, a, b, c, d;
char field[200005];

int main(){
	scanf("%d %d %d %d %d", &n, &a, &b, &c, &d);
	scanf(" %s", field + 1);
	bool overtake = false;
	while(b < d){
		// check this cell
		if(field[b - 1] == '.' && field[b + 1] == '.'){
			overtake = true;
		}
		if(field[b + 1] == '.'){
			b++;
		}else if(b + 2 <= d && field[b + 2] == '.'){
			b += 2;
		}else{
			printf("No\n");
			return 0;
		}
	}
	if(field[b - 1] == '.' && field[b + 1] == '.'){
		overtake = true;
	}
	
	if(c > d && !overtake){
		printf("No\n");
		return 0;
	}
	while(a < c){
		if(field[a + 1] == '.'){
			a++;
		}else if(a + 2 <= c && field[a + 2] == '.'){
			a += 2;
		}else{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 384
n, m = map(int,input().split())
adj = [[0]*(n+1) for i in range(n+1)]
edges = []
for i in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))
    adj[a][b] = 1
    adj[b][a] = 1


visited = [False] * (n+1)
parents = [None] * (n+1)
cycles = set()
count = 0
def dfs(u):
    for v in range(n+1):
        if adj[u][v]:
            if parents[u] == v:
                continue
            #print (u, v)
            #print (parents)
            adj[u][v], adj[v][u] = 0, 0
            if parents[v] is not None:
                #print ("Isn't None", u, v, parents[u])
                cycles.add(u)
                cycles.add(v)
                w = parents[u]
                while w != v:
                    cycles.add(w)
                    w = parents[w]
                
            if parents[v] == None: 
                parents[v] = u
                dfs(v)
parents[1] = 0
dfs(1)
ans = m
#print (parents)
for i in range(m):
    a, b = edges[i]
    if a in cycles and b in cycles:
        ans -= 1
print (ans)

Measured memory_bytes: 9212
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
typedef long long ll;
using namespace std;

struct Dijkstra{
  int n,i,l;
  vector<vector<pair<ll,int> > > edge; //cost,to
  vector<pair<ll,ll> > distance[300];
  vector<bool> visited;

  void init(int v){
    n=v;
    edge.resize(n);
    for(i=0;i<n;i++)distance[i].resize(n);
    visited.resize(n);
  }

  void input(int from,int to,int cost){
    edge[from].push_back({cost,to});
  }

  void calc(int start,int v){
    for(i=0;i<n;i++){
      distance[v][i]={1000000,0};
      visited[i]=0;
    }
    distance[v][start]={0,0};

    priority_queue<pair<pair<ll,ll>,int> > q; //cost,to
    int from,to;
    pair<ll,ll> tmp;
    q.push({{0,0},start});

    while(!q.empty()){
      from=q.top().second;

      if(visited[from]){
        q.pop();
        continue;
      }
      visited[from]=1;
      q.pop();
      for(i=0;i<edge[from].size();i++){
        to=edge[from][i].second;
        tmp=distance[v][from];
        tmp.second+=edge[from][i].first;
        if(tmp.second>l){
          tmp.second=edge[from][i].first;
          tmp.first++;
        }
        if(distance[v][to]>tmp){
          distance[v][to]=tmp;
          tmp.first*=-1;
          tmp.second*=-1;
          q.push({tmp,to}); //greater
        }
      }
    }

  }
};

int main(void){
  int n,m,l,a,b,c,q,i,j;
  static int s[100000],t[100000];
  Dijkstra graph;
  cin>>n>>m>>l;
  graph.init(n);
  graph.l=l;
  for(i=0;i<m;i++){
    cin>>a>>b>>c;
    a--;
    b--;
    if(c>l)continue;
    graph.input(a,b,c);
    graph.input(b,a,c);
  }

  for(i=0;i<n;i++){
    graph.calc(i,i);
  }

  cin>>q;
  for(i=0;i<q;i++){
    cin>>s[i]>>t[i];
    s[i]--;
    t[i]--;
  }

  for(i=0;i<q;i++){
    
    if(graph.distance[s[i]][t[i]].first==1000000){
      cout<<-1<<endl;
    }
    else{
      cout<<graph.distance[s[i]][t[i]].first<<endl;
    }
  }

  return 0;
}


Measured memory_bytes: 5652
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long MOD = 998244353;

void solve(int maxNum, int t, int n, char* s) {
	rep(i, maxNum+2) {
		s[t - 1] = 'a' + i;
		if (t == n) {
			rep(j, n) cout << s[j];
			cout << "\n";
		}
		else {
			solve(max(i, maxNum), t + 1, n, s);
		}
	}
}

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

	int n;
	cin >> n;
	char* s;
	s = new char[n];
	solve(-1, 1, n, s);

	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <string>

using namespace std;

string solve(const string& s){
	const int n = s.size();
	vector<int> step(n+2, 0);
	step[n] = 1;
	vector<vector<int>> next(n, vector<int>(26, n+1));
	for(int i=0;i<n;i++){
		for(int j=i;j>=0;j--){
			if(next[j][s[i]-'a'] < n+1) break;
			next[j][s[i]-'a'] = i+1;
		}
	}
	for(int i=n-1;i>=0;i--){
		step[i] = 100000000;
		for(int j=0;j<26;j++){
			step[i] = min(step[i], step[next[i][j]] + 1);
		}
	}
	string res;
	int pos = 0;
	while(pos < n){
		for(int i=0;i<26;i++){
			if(step[pos] == step[next[pos][i]] + 1){
				res += i+'a';
				pos = next[pos][i];
				break;
			}
		}
	}
	return res;
}

int main(){
	string s;
	while(cin >> s){
		cout << solve(s) << endl;
	}
}


Measured memory_bytes: 27780
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
from fractions import gcd

class SegmentTree:
    def __init__(self, N, func, I):
        self.func = func
        self.I = I
        self.sz = 2**(N-1).bit_length()
        self.seg = [I] * (self.sz * 2)
 
    def assign(self, k, x):
        self.seg[k + self.sz] = x
 
    def build(self):
        for i in range(self.sz - 1, 0, -1):
            self.seg[i] = self.func(self.seg[2 * i], self.seg[2 * i + 1])
 
    def update(self, k, x):
        k += self.sz
        self.seg[k] = x
        while k > 1:
            k >>= 1
            self.seg[k] = self.func(self.seg[2 * k], self.seg[2 * k + 1])

    def query(self, a, b):
        L = self.I
        R = self.I
        a += self.sz
        b += self.sz
        while a < b:
            if a & 1:
                L = self.func(L, self.seg[a])
                a += 1
            if b & 1:
                b -= 1
                R = self.func(self.seg[b], R)
            a >>= 1
            b >>= 1
        return self.func(L, R)

def main():
    N = int(readline())
    m = map(int,read().split())
    seg = SegmentTree(N , gcd , 0)
    for i in range(N):
        seg.assign(i , next(m))
    seg.build()
    ans = 1
    for i in range(N):
        ans = max(ans,gcd(seg.query(0,i) , seg.query(i+1,N)))
    print(ans)

main()


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

using namespace std;

int main (void) {
	int mt[10], t = 10;
	
	for (int i = 0; i < t; i ++) {
		cin >> mt[i];
	}
	
	for (int i = 0; i < t; i ++) {
		for (int j = 0; j < i; j ++) {
			if (mt[i] > mt[j]) {
				swap(mt[i], mt[j]);
			}
		}
	}
	
	for (int i = 0; i < 3; i ++) {
		cout << mt[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
import sys

input = sys.stdin.readline


def get_primes(n):
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i:: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    N = int(input())
    primes = get_primes(55555)
    ans = []
    for p in primes:
        if len(ans) == N:
            break

        if p % 5 == 1:
            ans.append(p)

    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3684
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
#define MOD (long long int)(1e9+7)
#define ll long long int


int main(void){
	int n,m;
	cin>>n>>m;
	int run;
	run=(n-m)*100+m*1900;
	for(int i=0;i<m;i++){
		run=run*2;
	}
	cout<<run<<endl;
	return 0;	
}


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

const int MOD = 1e9+7;
const int MAXN = 200101;

typedef struct def{
	int a,b,c;

	def(){}
	def(int a2, int b2, int c2){
		a = a2; b = b2; c = c2;
	}
	bool operator < (def comp) const{
		if(a!=comp.a) return a < comp.a;
		else return b < comp.b;
	}
} generico;

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

#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define x first
#define y second

int n;
int v[MAXN];
vector<int> g [MAXN];

int main(){
	scanf("%d",&n);
	
	int act[n][3];
	
	for(int i = 0 ; i < n ; i++)
		scanf("%d %d %d",&act[i][0], &act[i][1], & act[i][2]);
	
	int memo[n][3];
	
	memset(memo,-1,sizeof memo);
	
	memo[0][0] = act[0][0];
	memo[0][1] = act[0][1];
	memo[0][2] = act[0][2];
	
	for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < 3 ; j ++)
			for(int k = 0 ; k < 3 ; k ++){
				if(j == k) continue;
				memo[i+1][j] = max(memo[i+1][j] , memo[i][k] + act[i+1][j]);
			}
	
	int ans=0;
	for(int i=0;i<3;i++){
		ans = max(ans,memo[n-1][i]);
	}
	
	printf("%d\n",ans);
	
	return 0;
}

Measured memory_bytes: 7296
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-3;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int a[1 << 17];
ll dp[1 << 17],cop[1<<17];
int main() {
	int n, k; cin >> n >> k;
	rep(i, n) {
		cin >> a[i];
	}
	dp[0] = 1;
	rep(i, n) {
		ll sum = 0;
		rep(j, k + 1) {
			sum += dp[j];
			if (j - a[i] - 1 >= 0)sum -= dp[j - a[i] - 1];
			sum = (sum + mod) % mod;
			cop[j] = sum;
		}
		rep(j, k + 1)dp[j] = cop[j];
	}
	cout << dp[k] << endl;
	//stop
	return 0;
}

Measured memory_bytes: 1792