akhauriyash/Code-Regression huggingface dataset:
import sys
import bisect

inf = float('inf')

def solve():
    n = int(input())
    A = [int(input()) for i in range(n)]
    dp = [-1] + [inf] * n
    max_ = 1

    for a in A:
        j = bisect.bisect_left(dp, a, lo=0, hi=max_)
        max_ = max(max_, j + 1)
        dp[j] = a

    # print(dp)
    ans = max_ - 1
    print(ans)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Measured memory_bytes: 13260
#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
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

#define INF (1e+14)
int main(void) {
    int64_t x, y;
    cin >> x >> y;
    int64_t ans = INF;
    if(y-x>=0) ans = min(ans, y-x);
    if(-y-x >= 0) ans = min(ans, (-y-x)+1);
    if(y-(-x)>=0) ans = min(ans, (y-(-x)+1));
    if((-y)-(-x)>=0) ans = min(ans, (-y)-(-x)+2);
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N,A,B,a=0,b=0;
  cin>>N>>A>>B;
  vector<char> S(N);
  rep(i,N){cin>>S[i];}
  rep(i,N){
    if(S[i]=='a'){
      if(a+b<A+B){a++; cout<<"Yes"<<endl;}
      else{cout<<"No"<<endl;}
    }
    else if(S[i]=='b'){
      if((a+b<A+B)&&(b<B)){b++; cout<<"Yes"<<endl;}
      else{cout<<"No"<<endl;}
    }
    else{cout<<"No"<<endl;}
  }
}

Measured memory_bytes: 768
#include <stdio.h>
#include <string.h>

int main(void)
{
  int n,tmp;
  int t[51];
  char s[51][101];
  char x[101];
  scanf("%d",&n);
  for (int i=0; i<n;i++)
  {
    scanf("%s %d",&s[i],&t[i]);
  }
  scanf("%s",&x);
  tmp=0;
  for (int i=n-1; i>=0; i=i-1)
  {
    if(strcmp(s[i],x)==0)
    {
      printf("%d",tmp);
    }else{
      tmp=tmp+t[i];
    }
  }

  return 0;
}


Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		long count = 0;
		int mod =0;
		for (int i = 0; i < n; i++) {
			int a1 = Integer.parseInt(br.readLine());
			if(a1>0){
				a1+=mod;
				count += (a1 / 2);
				mod=a1%2;
			}else {
				mod=0;
			}
		}
		System.out.println(count);
	}
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x, n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair< int, int > P;
typedef pair< int, P > PP;

//-------------------------------------------------



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

	int w;
	cin >> w;
	cout << w * 32 << endl;

    return 0;
}




Measured memory_bytes: 3148
import sys

input = sys.stdin.readline
K = int(input())

array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(array[K-1])


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

using namespace std;

int main()
{
   int x,y;
   cin>>x>>y;
   for(int cr=0;cr<=x;cr++){
    int tu=x-cr;
    int legs=4*tu+2*cr;
    if(legs==y){cout<<"Yes"<<endl;return 0;}
   }
   cout<<"No"<<endl;
}


Measured memory_bytes: 3636
N=gets.to_i
a = 1
b = 0
l = []
while a < (N / 2) + 1 && b < N do
  b = N - a
  m = 0
  n = (a.to_s + b.to_s).split""
  n.each do |k|
    m += k.to_i
  end
  l << m
  a += 1
end
puts l.min


Measured memory_bytes: 2428
//============================================================================
// Name        : AOJ.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string>
using namespace std;
string s;
int main() {

	cin>>s;
	int ans=0;
	int a0,a1,a2,a3;

	for(a0=0;a0<s.size();a0=a3){
		for(a1=a0;s[a1]=='J';a1++);
		for(a2=a1;s[a2]=='O';a2++);
		for(a3=a2;s[a3]=='I';a3++);
		if(a1-a0>=a2-a1&&a2-a1<=a3-a2)ans=max(ans,a2-a1);

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

Measured memory_bytes: 3992
#include"iostream"
#include"stdio.h"
using namespace std;
int main()
{
	#ifdef whlzy
	freopen("text.in","r",stdin);
	#endif
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=n;i++)
	for(int j=0;j<=m;j++)
	{
		int x=i*m+j*n-2*i*j;
		if(x==k){printf("Yes");return 0;}
	}
	printf("No");
	return 0;
}

Measured memory_bytes: 256
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <iostream>
#include <cstdlib>
#include <typeinfo>

using namespace std;
int main() {
	pair<int, int> p[100010];
	long long int n, k, a = 0;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> p[i].first >> p[i].second;
	}
	sort(p, p + n);
	for (int i = 0; i < n; i++) {
		a += p[i].second;
		if (a >= k) {
			cout << p[i].first << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<complex>
#include<cassert>
#include<array>
#define ll long long
#define endl "\n"
#define pb push_back
#define READ(FILE) freopen(FILE,"r",stdin)
#define WRITE(FILE) freopen(FILE,"w",stdout)
#define loop(i,s,e) for(int i=s;i<e;i++)
#define mego fast();
#define cp(a,b) (conj(a)*b).imag()
using namespace std;
void fast()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
ll lcm(ll x, ll y)
{
    return (x*y)/__gcd(x,y);
}
int main()
{
mego
int a,b;
cin>>a>>b;
cout<<(a+b)%24;
return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
string a, v;
int ans=0;

int main(){
	IOS
	cin >> a >> v;
	int l=a.length();
	for(int i=0;i<l;i++){
		if(a[i]!=v[i]) ans++;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 3764
X,K,D=map(int,input().split())
c=0
if X>0:
    c,x=divmod(X,D)
    if c>K:
        print(X-D*K)
        exit()
elif X<0:
    c,x=divmod(-X,D)
    if c>K:
        print(abs(X+D*K))
        exit()
else:
    if K%2==0:
        print(0)
    else:
        print(D)
    exit()
if (K-c)%2==0:
    print(x)
else:
    print(abs(x-D))



        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














Measured memory_bytes: 9144
import java.util.Scanner;

public class Main {

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

        final int H = sc.nextInt();
        final int N = sc.nextInt();

        int total = 0;
        for (int i = 0; i < N; i++) {
            total += sc.nextInt();
        }

        if (total >= H) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


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

int main(void){
   int x;
   int c = 1;
   while(true) {
       cin >> x;
       if(x == 0) {
           break;
       }
       cout << "Case " << c << ": " << x << endl;
       c = c + 1;  // cを増やす
   }
}



Measured memory_bytes: 3080
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int MAXN = 100005;

int n;
int a[3 * MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < 3 * n; ++i) {
        scanf("%d", a + i);
    }
    sort(a, a + 3 * n);

    long long ans = 0LL;
    for (int i = n; i < 3 * n; i += 2) {
        ans += a[i];
    }

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 1280
import java.util.Scanner;
public class Main{
    public static void  main(String args[]){

        Scanner sc = new Scanner(System.in);
        int R = sc.nextInt();
        int G = sc.nextInt();
        int B = sc.nextInt();
        int N = sc.nextInt();
        int sum = 0;

        for(int r = 0;R * r <= N ; r++){
            for(int g = 0;G * g <= (N - R * r); g++){
                if(((N - (R * r + G * g)) % B == 0)){
                    sum ++;
                    }

            }
        }

        System.out.println(sum);
    }
}


Measured memory_bytes: 23892
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(m)]

for x1, y1 in ab:
    l = 10**10
    index = 0
    for i, (x2, y2) in enumerate(cd):
        if l > abs(x1-x2)+abs(y1-y2):
            l = abs(x1-x2)+abs(y1-y2)
            index = i + 1
    print(index)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;
using i8t = std::int64_t;
using vi8t = std::vector<i8t>;
using vvi8t = std::vector<std::vector<i8t>>;
static const i8t i8t_max=numeric_limits<i8t>::max();
static const i8t i8t_min=numeric_limits<i8t>::min();
using u8t = std::uint64_t;
using vu8t = std::vector<u8t>;
#define F3(I,A,B) for(i8t I=A,I##_N=B;I<I##_N;I++)
#define F(I,N) F3(I,0,N)
#define FR(I,N) for(i8t I=N;I--;)
#define R(V) i8t V;std::cin>>V;
#define RV(V,N) std::vector<i8t> V;F(_i,N){R(_x)V.push_back(_x);}
#define RL1(line) std::getline(std::cin,line);
#define RL(line) std::string line;RL1(line)
#define RM(V,L,C) std::vector<char> V;F(_i,L){RL(_l)F(_j,C)V.push_back(_l[_j]);}
#define P(X) std::cout<<(X)<<std::endl;
template<typename T> T umax(T& ans,T const& value) {if(value>ans)ans=value;return ans;}
template<typename T> T umin(T& ans,T const& value) {if(value<ans)ans=value;return ans;}

int main() {
  R(N)R(M)RV(A,N);
  i8t sum=0;
  for(auto x:A)sum+=x;

  i8t count=0;
  for(auto a:A){
    if(a*4*M < sum)continue;
    count++;
  }
  P(count>=M?"Yes":"No");
  return 0;
}


Measured memory_bytes: 384
from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


def check(min_, max_, x):
  if max_ <= x:
    return 10**max(0, len(str(min_))-2)
  elif min_ <= x:
    ret = max(1, int(str(x)[1:-1]) if len(str(x)) > 2 else 1)
    if int(str(min_)[-1]) <= int(str(x)[-1]):
      ret += 1
    return ret
  else:
    return 0


def main():
  N = int(input())

  if len(str(N)) == 1:
    print(N)
    return
  sum_ = 0
  for l in range(1, 10):
    for r in range(l, 10):
      temp = sum_
      min_ = int(str(l) + '0'*(len(str(N))-2) + str(r))
      max_ = int(str(l) + '9'*(len(str(N))-2) + str(r))
      A = check(min_, max_, N)
      # max_ = int(str(l) + '9'*(len(str(N))-3) + str(r))
      for gap in range(len(str(N))-2):
        A += (10**gap)

      min_ = int(str(r) + '0'*(len(str(N))-2) + str(l))
      max_ = int(str(r) + '9'*(len(str(N))-2) + str(l))
      B = check(min_, max_, N)
      for gap in range(len(str(N))-2):
        B += (10**gap)

      if l == r:
        A += 1
        B += 1
        sum_ += A*B
      else:
        sum_ += 2*A*B
      # print(l, r, sum_ - temp)

  print(sum_)


if(__name__ == '__main__'):
  main()


Measured memory_bytes: 65752
#include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
using namespace std;

int main(){
	double w;
	string s;
	while(cin>>w){
		if(w<=48) s="light fly";
		else if(48<w && w<=51) s="fly";
		else if(51<w && w<=54) s="bantam";
		else if(54<w && w<=57) s="feather";
		else if(57<w && w<=60) s="light";
		else if(60<w && w<=64) s="light welter";
		else if(64<w && w<=69) s="welter";
		else if(69<w && w<=75) s="light middle";
		else if(75<w && w<=81) s="middle";
		else if(81<w && w<=91) s="light heavy";
		else if(91<w) s="heavy";
		cout<<s<<endl;
	}
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
int n;
pair<int, int>p[100005];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i].first;
		p[i].second = i;
	}
	sort(p + 1, p + n + 1);
	for (int i = 1; i < n; i++)
	{
		cout << p[i].second << " ";
	}
	cout << p[n].second << endl;
	return 0;
}

Measured memory_bytes: 1664
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
char s[MAXN];
int dp[1<<26];
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%s",s);
    for(int i=1;i<(1<<26);i++)
		dp[i]=INF;
    int n=strlen(s),mask=0;
    for(int i=0;i<n;i++){
		mask^=(1<<(s[i]-'a'));
		int ans=dp[mask];
		if(!ans)
			ans++;
		for(int j=0;j<26;j++)	
			umin(ans,dp[mask^(1<<j)]+1);
		if(i==n-1)
			printf("%d\n",ans);
		umin(dp[mask],ans);	
	}
	return 0;
}


Measured memory_bytes: 262528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000010;
constexpr ll INF= 1000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}

ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}

ll RS(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P < 0) {
        return 0;
    }
    if(P%2==0){
        ll t = RS(N, P/2, M);
        return t*t % M;
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    ll N;
    cin >> N;
    ll ret = 0;
    for(ll i = 1;i <= N;i++) {
        for(ll j = i;j <= N;j += i) {
            ret += j;
        }
    }
    cout << ret << endl;
}

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

#define pb push_back
#define ll long long
#define maxn 300005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define bg begin()
#define ed end()
#define pii pair<int,int>

int main(){
	int n , m;
	while(cin >> n >> m){
		string s;
		//cin >> n >> m;
		cin >> s;
		int cont[n+5] = {};
		int op[m+5][2] = {};
		for(int i=1;i<=n;i++){
			cont[i] = s[i-1]-'A';
		}
		f(m){
			char a,b;
			cin >> a >> b;
			op[i][0] = a-'A';
			op[i][1] = (b=='R') - (b=='L');
		}
		int rb=0;
		for(int i=1<<20;i;i>>=1){
			int now=rb+i;
			if(now>n)continue;
			int pos=now;
			for(int j=0;j<m;j++){
				if(cont[pos]==op[j][0]){
					pos+=op[j][1];
				}
				//cout << pos << endl;
				if(pos>n){
					rb -= i;
					break;
				}
			}

			rb += i;
		}
		int lb=0;
		for(int i=1<<20;i;i>>=1){
			int now=lb+i;
			if(now>n)continue;
			int pos=n-now;
			for(int j=0;j<m;j++){
				if(cont[pos]==op[j][0]){
					pos+=op[j][1];
				}
				if(pos<1){
					lb -= i;
					break;
				}
			}
			lb += i;
		}
		if(!lb||!rb){
			cout<<0<<endl;
			exit(0);
		}
		lb = n-lb;
		//cout<<rb<<' '<<lb<<endl;
		cout<<max(0,rb-lb+1)<<endl;
	}
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;


int main(){
  vector<vector<int>> data(15,vector<int>(15));
  int n;
  cin >> n;
  n++;
  rep(i,1,n){
    
    int b = i%10;
    int c = i;
    while(c>=10){
        c /=10;
        //if(i<10) break;
    }
    
    int a = c;
    //cout << a << endl;
    data.at(a).at(b) ++;
  }
  int sum = 0;
  rep(i,0,10){
      rep(j,0,10){
          sum += data.at(i).at(j)*data.at(j).at(i);
      }
  }
  cout << sum << endl;



  return 0;
}

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

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

    //freopen("input.txt","r",stdin);

    string s;
    cin>>s;
    int c=0;
    if(s == "SRR" || s == "RRS")c=2;
    else if(s == "RRR")c=3;
    else if(s == "SSR" || s == "SRS" || s == "RSS" || s == "RSR" )c=1;
    else c=0;
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <random>
#include <cassert>
#include <numeric>
#define ll long long int
#define LL unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;



int main() {
    string s; cin >> s;
    int n = s.size(), ans = 0;

    string pre = "", cur = "";
    for(int i = 0; i < n; i++){
        cur += s[i];
        if(cur != pre){
            pre = cur;
            cur = "";
            ans++;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

const string buff = "ATGC";
const int mod = 1e9 + 7;

vector< pair< int, int > > toto[50];
vector< int > order;

int dp2[52][52][52];
int dp3[52][52][52];

void dfs(int idx)
{
  for(auto &to : toto[idx]) {
    if(to.first) dfs(to.second);
    else order.push_back(to.second);
  }
}

int main()
{
  int Na, Nt, Ng, Nc, M;
  string s[50];

  cin >> Na >> Nt >> Ng >> Nc;
  int sum = Na + Nt + Ng + Nc;
  cin >> M;
  cin.ignore();
  for(int i = 0; i < M; i++) getline(cin, s[i]);

  map< string, int > convert;
  for(int i = M - 1; i >= 0; i--) {
    convert[s[i].substr(0, s[i].find(':'))] = i;
  }

  int dp[50] = {};
  for(int i = M - 1; i >= 0; i--) {
    string ss = s[i].substr(s[i].find(':') + 2);
    vector< string > splits;
    string curr;
    for(int j = 0; j <= ss.size(); j++) {
      if(j == ss.size() || ss[j] == ' ') splits.push_back(curr), curr = "";
      else curr += ss[j];
    }
    for(auto &t : splits) {
      if(t[0] == '[') {
        int mask = 0;
        for(int j = 0; j < buff.size(); j++) {
          if(t.find(buff[j]) != string::npos) {
            mask |= 1 << j;
          }
        }
        toto[i].emplace_back(0, mask);
        dp[i] = min(sum + 1, dp[i] + 1);
      } else {
        toto[i].emplace_back(1, convert[t]);
        dp[i] = min(sum + 1, dp[i] + dp[convert[t]]);
      }
    }
  }

  if(dp[0] != sum) {
    cout << 0 << endl;
  } else {
    dfs(0);

    dp2[0][0][0] = 1;
    for(int bit : order) {
      memset(dp3, 0, sizeof(dp3));
      for(int i = 0; i <= 50; i++) {
        for(int j = 0; j <= 50; j++) {
          for(int k = 0; k <= 50; k++) {
            if((bit >> 0) & 1) (dp3[i + 1][j][k] += dp2[i][j][k]) %= mod;
            if((bit >> 1) & 1) (dp3[i][j + 1][k] += dp2[i][j][k]) %= mod;
            if((bit >> 2) & 1) (dp3[i][j][k + 1] += dp2[i][j][k]) %= mod;
            if((bit >> 3) & 1) (dp3[i][j][k] += dp2[i][j][k]) %= mod;
          }
        }
      }
      swap(dp2, dp3);
    }
    cout << dp2[Na][Nt][Ng] << endl;
  }

}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define DBG(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define DBG(...)
#endif

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, n) for (auto i : (n))
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

int N;
int A[100];

int main() {
  cin >> N;
  REP(i, N) cin >> A[i];

  bool ok = true;
  REP(i, N) if (A[i] % 2 == 0 && (A[i] % 3 != 0 && A[i] % 5 != 0)) {
    DBG(A[i]);
    ok = false;
  }

  if (ok) {
    cout << "APPROVED" << endl;
  } else {
    cout << "DENIED" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
        #define ll long long int
        using namespace std;
        #define mod 1000000007
        #define pb push_back
        #define fi first
        #define si second
        #define mp make_pair
        #define f(n) for(ll i=0;i<n;i++)
        #define ff(m) for(ll j=0;j<m;j++)
        #define fr(i,p,n) for(ll i=p;i<n;i++)
        #define in insert
        ll exp(ll a,ll b,ll m);
        #define vl vector<ll> 
        #define pll pair <ll,ll>

    
        void solve(){

        	int n;
        	cin>>n;
        	int h[n];
        	f(n)
        	cin>>h[i];

        	int dp[n+1];
        	dp[0]=0;
        	dp[1]=abs(h[1]-h[0]);
        	fr(i,2,n){
        		dp[i]=min(dp[i-2]+abs(h[i]-h[i-2]),dp[i-1]+abs(h[i]-h[i-1]));
        	}
        	cout<<dp[n-1]<<endl;




        }
 
       int main(){
          
 
            int t=1;
 			//cin>>t;
            while(t--)
               solve();
    
    		return 0;
		}
 
		ll exp(ll a,ll b,ll m)
		{
			if(b==0)
			{
				return 1;
			}
			ll temp =exp(a,b/2,m);
			temp=(temp*temp)%m;
			if(b&1)
			{
				return (temp*(a%m))%m;
			}
			return temp;
		}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n, k;
  string s;
  cin >> n >> s >> k;
  
  char c=s[k-1];
  rep(i, n) if(s[i]!=c) s[i]='*';
  cout << s << newl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  
    string n;
    int d;
    cin>>n;
    d = n[n.size()-1] - '0';
    
    if(d==2||d==4||d==5||d==7||d==9)
      cout<<"hon";
    else if(d==0||d==1||d==6||d==8)
      cout<<"pon";
    else
      cout<<"bon";
    
    
  
  return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

struct Pair {
  ll l, r;
  ll Min() const { return min(l, r); }
  bool operator<(const Pair& p) const { return Min() < p.Min(); }
};

int main() {
  in(ll, n);
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(all(a), greater());

  ll ans = a[0];
  priority_queue<Pair> que;
  que.push({a[0], a[1]});
  que.push({a[1], a[0]});
  for (int i = 2; i < n; ++i) {
    Pair p = que.top();
    dbg(i, ans, p.l, p.r, p.Min());
    que.pop();
    ans += p.Min();
    que.push({p.l, a[i]});
    que.push({a[i], p.r});
  }
  out(ans);
}


Measured memory_bytes: 9020
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VII;
typedef pair<int, int> PII;
typedef long long ll;

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back;
#define MP make_pair
#define SIZE(a) int((a).size())
#define SORT(c) sort((c).begin(), (c).end())

const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 3;

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

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

int main(void){
  string in;
  cin >> in;
  for(int i = 0; i < in.size(); i++){
    cout << (char)((in[i] - 'A' + 23) % 26 + 'A');
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1176
N   = gets.to_i
MAX = 3500

1.upto(MAX) do |h|
  1.upto(MAX) do |n|
    a = (N*h*n).to_f
    b = (4*h*n - N*n - N*h).to_f
    if b != 0.0
      w = a / b
      if w.to_i == w and w > 0
        puts "#{h.to_i} #{n.to_i} #{w.to_i}"
        exit
      end
    end
  end
end


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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int N; scanf("%d", &N);
  vector<int> T(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &T[i]);
    T[i] *= 2;
    T[i] += T[i - 1];
  }

  vector<int> V(N + 2, 0);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &V[i]);
  }
  vector<double> maxV(T[N] + 1, 0);
  double limv = 0.0;
  // fprintf(stderr, "DEBUG: forward\n");
  for (int t = 1, limpos = 0; t <= T[N]; ++t) {
    if (t > T[limpos]) { limv = V[++limpos]; }
    maxV[t] = min(maxV[t - 1] + 0.5, limv);
    // fprintf(stderr, "DEBUG: t=%d, limpos=%d, V[limpos]=%d, maxV[t]=%f\n", t, limpos, V[limpos], maxV[t]);
  }

  // fprintf(stderr, "DEBUG: backward\n");
  maxV[T[N]] = 0;
  for (int t = T[N] - 1, limpos = N + 1; t >= 0; --t) {
    if (t < T[limpos - 1]) { limv = V[--limpos]; }
    maxV[t] = min(maxV[t], min(maxV[t + 1] + 0.5, limv));
    // fprintf(stderr, "DEBUG: t=%d, limpos=%d, V[limpos]=%d, maxV[t]=%f\n", t, limpos, V[limpos], maxV[t]);
  }

  // fprintf(stderr, "DEBUG: maxV=\n");
  // copy(maxV.begin(), maxV.end(), ostream_iterator<double>(cerr, "\n"));
  double ans = 0.0;
  for (int t = 1; t <= T[N]; ++t) {
    ans += (maxV[t - 1] + maxV[t]) * 0.5 * 0.5;
  }

  printf("%f\n", ans);
  return 0;
}


Measured memory_bytes: 512
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx") 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x)  ((int)x.size ())
#define all(x) (x).begin(), (x).end()
#define re return
#define mp make_pair
#define sqrt(x) sqrt (abs(x))
#define y0 y3451
#define y1 y4562
#define j0 j25624
#define j1 j45624
#define makeunique(x) sort(all(x)), (x).resize (unique(all(x)) - (x).begin())

typedef pair <int, int> ii;
typedef long long ll;
typedef unsigned long long ull;
typedef double D;
typedef long double ld;
typedef unsigned int uint;
typedef vector <string> vs;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <vi> vvi;
typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> _tree;

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

const ld pi = 2 * asinl((ld)1.0);

int n;
int m;

#define filename ""

int main ()        
{
//    freopen (filename".in", "r", stdin);
//    freopen (filename".out", "w", stdout);
    cin >> n >> m;
    vi a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int k = 0; k < m; k++) {
        vi add(n + 1);
        for (int i = 0; i < n; i++) {
            int l = max(0, i - a[i]), r = min(n, i + a[i] + 1);
            add[l]++; add[r]--;
        }
        for (int i = 0; i < n; i++) add[i + 1] += add[i];
        assert(add[n] == 0);
        a = add;
        
        /*cout << k << " | ";
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;*/
        
        bool ok = true;
        for (int i = 0; i < n; i++) ok &= (a[i] == n);
        if (ok) {
            break;
        }
    }    
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}


Measured memory_bytes: 5636
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;
int main() {
	int i, j;
	int A, B, C, K;
	int maxnum=0;
	int ans = 0;
	cin >> A >> B >> C;
	cin >> K;

	maxnum = max({A,B,C});
	for (i = 0; i < K; ++i) {
		maxnum *= 2;
	}
	
	ans = A + B + C - max({A,B,C}) + maxnum;
	cout << ans << endl;




}

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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

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

    if (x >= a)
        cout << 10 ;

    else
        cout << 0 ;



    return 0;

}



Measured memory_bytes: 256
#!/usr/bin/env python3
def main():
    import numpy as np

    N, W = map(int, input().split())
    lst = [list(map(int, input().split())) for _ in range(N)]
    v_max = 10 ** 3 * 100 * 10
    w_max = 10 ** 9 * v_max

    # i以上の価値を持つときの最小重量
    dp = np.full(v_max, w_max, dtype=np.int64)
    # initialize
    dp[0] = 0

    for w, v in lst:
        dp[v:] = np.minimum(dp[v:], dp[:-v] + w)

    print(np.asarray(dp <= W).nonzero()[0].max())


if __name__ == '__main__':
    main()


Measured memory_bytes: 50172
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] l = new long[n];
		for(int i = 0 ; i < n ; i++) {
			l[i] = sc.nextLong();
		}
		long count = 0;
		for(int a = 0 ;  a < n ; a++) {
			for(int b = a + 1 ; b < n ; b++) {
				for(int c = b + 1 ; c < n ; c++) {
					long l1 = l[a];
					long l2 = l[b];
					long l3 = l[c];
					if(l1 + l2 > l3 && l2 + l3 > l1 && l3 + l1 > l2 && l1 != l2 && l1 != l3 && l3 != l2)
						count++;

				}
			}

		}

		sc.close();
		System.out.println(count);

	}
}



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

int count = 0;

/*1  insertionSort(A, n, g)
2      for i = g to n-1
3          v = A[i]
4          j = i - g
5          while j >= 0 && A[j] > v
6              A[j+g] = A[j]
7              j = j - g
8              cnt++
9          A[j+g] = v
10
11 shellSort(A, n)
12     cnt = 0
13     m = ?
14     G[] = {?, ?,..., ?}
15     for i = 0 to m-1
16         insertionSort(A, n, G[i])*/

void insertSort(int *A,int n,int g){
  int i,j;
  int key;
  for(i = g; i < n; i++){
    j = i;
    key = A[i];
    while(0 <= j - g){
      if(A[j-g] <= key) break;
      A[j] = A[j-g];
      j -= g;
      count++;
    }
   A[j] = key;
 }
}


int main(){
  int n;
  int i,j;
  int *A;
  int G[20];

  scanf("%d", &n);
  A = malloc(n * sizeof(int));
  for(i = 0; i < n; i++) scanf("%d", &A[i]);

  int m = 0;
  G[0] = 0;
  while(1){
    if(n < 3*G[m]+1) break;
    G[m+1] = 3*G[m] + 1;
    m++;
 }

 for(i = m; i > 0; i--) insertSort(A,n,G[i]);

  printf("%d\n", m);
  for(i = m; i >= 1; i--) printf("%d ", G[i]);
  printf("\n");
  printf("%d\n", count);

  for(i = 0; i < n; i++) printf("%d\n", A[i]);

  return 0;
}



Measured memory_bytes: 5764
#from collections import deque
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7

S = str(input())
N = len(S)
ans = [0]*N
k = int(1)
R = []
L = []
rcount = int(1)
lcount = int(0)
lLocate = []
for i in range(1,N):
    if S[i]==S[i-1]:
        if k == 1:
            rcount +=1
        else:
            lcount +=1
    else:
        if k==1:
            R.append(rcount)
            lLocate.append(i-1)
            lcount = int(1)
        else:
            L.append(lcount)
            rcount = int(1)

        k *= (-1)


L.append(lcount)

#print(R)
#print(L)
#print(lLocate)
j = int(0)
#for i in range(N):
#    if i in lLocate:
for i in lLocate:
    r = R[j]
    l = L[j]
    ans[i] = (r+1)//2 + l//2
    ans[i+1] = r//2 + (l+1)//2
    j +=1

print(' '.join(map(str, ans)))


Measured memory_bytes: 52208
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1e9;
const long long INFLL = 1LL<<60;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;  // 階乗と階乗の逆元
  combination(int n):fact(n+1),ifact(n+1) {  // 階乗と階乗の逆元を n まで求める
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

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

  ll n, k;
  cin >> n >> k;

  mint ans;
  combination comb(k);
  for (ll i = 0; i <= k; i++) {
    mint tmp = comb(k, i) * mint(i).pow(n);
    if ((k-i) % 2 == 1) ans -= tmp;
    else ans += tmp;
  }

  cout << ans.x << endl;

  return 0;
}



Measured memory_bytes: 3208
#include<stdio.h>
int main(void){
    while(1){
        int T,D,L;
        int wave,ans=0,wet=0;
        scanf("%d%d%d",&T,&D,&L);
        if(T+D+L==0)break;
        for(int i=0;i<T;i++){
            scanf("%d",&wave);
            if(wave>=L){
                wet=D;
            }
            if(wet>0){
                ans++;
                wet--;
            }
        }
        printf("%d\n",(ans<1)?0:(ans-1));
    }
}



Measured memory_bytes: 2044
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define MAX_N (200005)
#define INF (1LL<<60)
#define EPS (1e-7)
#define DEBUG(x) cerr << #x <<":"<< x << endl;
#define DEBUGVC(x) cerr << #x <<": "; for(auto p:(x)) cerr << p <<" "; cerr << endl;
#define DEBUGVCP(x) for(auto p:(x)) cerr << #x <<": "<< p.first <<", "<< p.second << endl;
#define DEBUG2(x, y) cerr << #x <<" : "<< x <<", "<< #y <<" : "<< y << endl;
#define DEBUG3(x, y, z) cerr << #x <<" : "<< x <<", "<< #y <<" : "<< y <<", "<< #z <<" : "<< z << endl;
const int MOD = (int)1e9+7;


signed main() {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    S[K-1] = S[K-1] + 32;
    cout << S << endl;

}

Measured memory_bytes: 256
# ワ―シャルフロイドで解くよ
def main():
    import sys
    input = sys.stdin.readline  # 1行ごとの入力を繰り返し扱う場合の高速化
    N, M, L = map(int, input().split())
    # distanceを格納(未到達は無限遠として初期化)
    d = [[10 ** 12] * N for _ in range(N)]  
    # input-edges
    for i in range(M):
        a, b, c = map(int, input().split())
        if L >= c: # 距離がLより大きいのは無視
            d[a - 1][b - 1] = d[b - 1][a - 1] = c
    for i in range(N):
        d[i][i] = 0  # 自己ループ無
    
    # ワ―シャルフロイド法適用
    # 町間の最短距離を一度求める。
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][k] + d[k][j], d[i][j])
    
    # 先ほど求めた町間の内、最短距離がL以下のものを距離1で結ぶ。
    edge = [[10 ** 12] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if d[i][j] <= L:
                edge[i][j] = 1
    
    # もう一度ワ―シャルフロイド法適用
    for k in range(N):
        for i in range(N):
            for j in range(N):
                edge[i][j] = min(edge[i][k] + edge[k][j], edge[i][j])
    
    # input-query
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        if edge[s - 1][t - 1] >= 10 ** 12:
            print(-1)
        else:
            print(edge[s - 1][t - 1] - 1)  # 最初に燃料Lがある分、マイナス1をする。
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 55516
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

void agc_a_prefix_and_suffix(void) {
	int n;
	string s, t;
	cin >> n >> s >> t;
	

	int match_num = 0;
	for (int i = 1; i <= n; i++){
		string s_sub = s.substr(s.size()-i,i);
		string t_sub = t.substr(0, i);
		if (s_sub == t_sub) {
			match_num = i;
		}
		
	}

	int out_length = s.size() + t.size() - match_num;

	cout << out_length << endl;

}

int main()
{
    agc_a_prefix_and_suffix();
    return 0;
}

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

int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i, n){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    ll ans=0;
    ans += a[0];
    for(int i=1;i<=(n-1)/2;i++){
        ans += a[i]*2;
    }
    if(n%2==1) ans -= a[n/2];
    cout << ans << endl;
}


Measured memory_bytes: 4848
s = input()
N = len(s)
dp = [0 for i in range(N+1)]
dp[1] = 1
dp[2] = 2
if s[1]==s[0]:
    dp[2] = 1
for i in range(2,N):
    if s[i] == s[i-1]:
        dp[i+1] = dp[i-2]+2
    else:
        dp[i+1] = dp[i]+1
print(dp[-1])

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

int main(){
  int A, B;
  cin >> A >> B;
  
  if(A > 12){
    cout << B << endl;
  }else if(A > 5){
    cout << B / 2 << endl;
  }else{
    cout << 0 << endl;
  }
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <iomanip>
using namespace std;

int main(){
    long long int n,m=0,sum=0;
    cin>>n;
    vector<int>a(1000000);
    for(int i=0;i<n;i++){
        cin>>a[i];
        
        if(m<a[i]){
            m=a[i];
        }
        sum+=a[i];
    }
    cout<<sum-m/2<<endl;

    return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
int main() {
    ll h, n;
    cin >> h >> n;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    ll M = *max_element(all(a));
    vector<ll> dp(h + 1 + M, 931931324810LL);
    dp[0] = 0;
    for(ll i = 0; i <= h + M; i++) {
        for(ll j = 0; j < n; j++) {
            if(i - a[j] >= 0) {
                dp[i] = min(dp[i], dp[i - a[j]] + b[j]);
            }
        }
    }
    ll ans = LLONG_MAX;
    for(int i = h; i <= h + M; i++) {
        ans = min(ans, dp[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 384
// ???AOJ??§??????????????????ES6??§?¨???°?????????????????\????????????

//???????????¢?´¢
var binarySearch = function(key, n, a) {
  // ??????????????¨????????¢?´¢?????????
  // left???0??????right???????´???°n????????????
  var left = 0;
  var right = n;

  while (left < right) {
    // ??¢?´¢???????????????????????????
    var mid = Math.floor((left + right) / 2);
    if (a[mid] == key) {
      return true;
    } else if (key < a[mid]) {
      // ??¢?´¢??????????????????
      right = mid;
    } else {
      // ??¢?´¢??????????????????
      left = mid + 1;
    }
  }
  return false;
};

(function(stdin) {
  // ?????????????????????
  var arr = (stdin.trim()).split('\n');

  // ???????????¨?????????????????°???????´?????????????
  var s = arr[1].split(" ").map(Number);
  var t = arr[3].split(" ").map(Number);

  var ans = 0;
  for (var i = 0; i < t.length; i++) {
    // ????????¢?´¢
    ans += binarySearch(t[i], s.length, s);
  }
  // ??????
  console.log(ans);
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1000000007;

const ll INF = 1LL << 60;

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


int main() {
  string s;cin >> s;
  if(s[2]==s[3] && s[4] ==s[5])cout << "Yes";
  else cout << "No";
}

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

int main(void){
	int x; scanf("%d",&x);
	int a=x/100,b=x%100;
	if(a>0 && a<=12){
		if(b>0 && b<=12) printf("AMBIGUOUS");
		else printf("MMYY");
	}
	else{
		if(b>0 && b<=12) printf("YYMM");
		else printf("NA");
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define dd double
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep1(i,b) for(ll i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define vi vector<ll>
#define all(v) v.begin(), v.end()

bool isPerfectSquare(long double x) 
{   
  long double sr = sqrt(x); 
   
  return ((sr - floor(sr)) == 0); 
} 

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

	ll n = 0, d = 0;
	cin >> n >> d;
	long double points[n][d];
	for(ll i = 0; i < n; ++i) {
		for(ll j = 0; j < d; ++j) {
			cin >> points[i][j];
		}
	}
	ll ans = 0;
	for(ll i = 0; i < n; ++i) {
		for(ll j = i; j < n; ++j) {
			long double dist = 0;
			if(i != j) {
				for(ll k = 0; k < d; ++k) {
					dist += pow(abs(points[i][k] - points[j][k]), 2.0);	
				}
				if(isPerfectSquare(dist)){
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

lli fn(vector<lli> a)
{
  deque<lli> p, q;
  each (i, a) p.push_back(i);

  int cnt = 0;
  while (1 < p.size()) {
    if (q.empty()) {
      q.push_back(p.front());
      p.pop_front();
    } else {
      lli x, y;
      if (cnt % 2) {
        x = p.back();
        p.pop_back();
        y = p.back();
        p.pop_back();
      } else {
        x = p.front();
        p.pop_front();
        y = p.front();
        p.pop_front();
      }
      q.push_back(x);
      q.push_front(y);
    }
    ++cnt;
  }

  if (p.size()) {
    if (abs(q.front() - p.front()) < abs(q.back() - p.front())) {
      q.push_back(p.front());
      p.pop_front();
    } else {
      q.push_front(p.front());
      p.pop_front();
    }
  }

  vector<lli> b;
  while (q.size()) {
    b.push_back(q.front());
    q.pop_front();
  }

  // cout << b << endl;
  lli sum = 0;
  for (int i = 0; i + 1 < b.size(); ++i) {
    sum += abs(b[i] - b[i + 1]);
  }
  return sum;
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  while (cin >> n) {
    vector<lli> a(n);
    cin >> a;
    sort(a.begin(), a.end());    
    lli x = fn(a);
    reverse(a.begin(), a.end());
    lli y = fn(a);
    cout << max(x, y) << endl;
  }
  
  return 0;
}


Measured memory_bytes: 5864