akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
namespace aoj {
	struct Point {
		private int _x;
		private int _y;
		public Point(int x, int y) {
			_x = x;
			_y = y;
		}
		public int x {
			get { return _x; }
		}
		public int y {
			get { return _y; }
		}
	}
	public class Program {
		private static bool InRange(int val) {
			return 0 <= val && val < 12;
		}
		public static void Main() {
			var s = new Stack<Point>();
			var map = new int[12,12];
			var dx = new int[] {-1, 0, 1, 0};
			var dy = new int[] {0, -1, 0, 1};
			string str;
			while((str = Console.ReadLine()) != null) {
				int c = 0;
				for (int i = 0; i < str.Length; i++) map[0, i] = str[i] - '0';
				for (int i = 1; i < map.GetLength(0); i++) {
					str = Console.ReadLine();
					for (int j = 0; j < str.Length; j++) map[i, j] = str[j] - '0';
				}
				for (int i = 0; i < map.GetLength(0); i++) {
					for (int j = 0; j < map.GetLength(1); j++) {
						if (map[i, j] == 1) {
							s.Push(new Point(i, j));
							map[i, j] = 0;
							while (s.Count != 0) {
								var p = s.Pop();
								for(int k = 0; k < dx.Length; k++) {
									if (InRange(p.x + dx[k]) && InRange(p.y + dy[k]) && map[p.x + dx[k], p.y + dy[k]] == 1) {
										map[p.x + dx[k], p.y + dy[k]] = 0;
										s.Push(new Point(p.x + dx[k], p.y + dy[k]));
									}
								}
							}
							c++;
						}
					}
				}
				Console.WriteLine(c);
				Console.ReadLine();
			}
		}
	}
}

Measured memory_bytes: 9836
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  int N;
  string s;

  cin >> N;
  cin >> s;

  if( N >= 3200){
    cout << s << endl;
  }else{
      cout << "red" << endl;
  }
}


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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;

ll n,dp[100034],k;
vector<ll> h;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<=n;i++)
		dp[i]=98765432111;
	for(int i=0;i<n;i++)
	{
		ll a;cin>>a;
		h.push_back(a);		
	}
	dp[0]=0;		
	for(int i=1;i<n;i++)
		for(int j=1;j<=k;j++)
			if(i-j>=0)
				dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 2168
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int K = cin.nextInt();
        int S = cin.nextInt();
        int c = 0;
        for (int x = 0; x <= K; x++) {
            for (int y = 0; y <= K; y++) {
                int z = S - x - y;
                if (z >= 0 && z <= K) {
                    c++;
                }
            }
        }
        System.out.println(c);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main(int argc, char *argv[]){
    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(N);
    for(auto & a: A){
        std::cin >> a;
    }
    std::sort(A.begin(),A.end());
    for(int i=0; i<M; ++i){
        A[N-1] >>= 1;
        auto iter = std::upper_bound(A.begin(),A.end()-1,A[N-1]);
        A.insert(iter,A[N-1]);
        A.pop_back();
    }
    long int money = 0l;
    for(const auto &a : A){
        money += a;
    }
    std::cout << money << std::endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 


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

int A, B, M; cin >> A >> B >> M;
VI a(A), b(B); invec(a); invec(b);
VI x(M), y(M), c(M); rep(i, 0, M) cin >> x[i] >> y[i] >> c[i];

i64 mini = *min_element(ALL(a)) + *min_element(ALL(b));

rep(i, 0, M){
    mini = min(mini, a[x[i]-1] + b[y[i]-1] - c[i]);
}


cout << mini << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

    signed main(){
    int R,G;
    cin>>R>>G;
    cout<<2*G-R<<endl;
    return 0;

}


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

signed main(){
    int n,k;
    cin >> n >> k;
    int v[n];
    rep(i,n) cin >> v[i];
    int mmin=min(n,k);
    int low=0;
    int mmax=-100000000000;
    if(mmin%2==0) low=mmin/2;
    else low=mmin/2+1;
    for(int i=low;i<=mmin;i++){
        for(int j=0;j<=i;j++){
            vector<int> vec;
            int a=j;
            int b=i-j;
            rep(l,a) vec.push_back(v[l]);
            rep(l,b) vec.push_back(v[n-1-l]);
            sort(vec.begin(),vec.end());
            for(int l=0;l<k-(a+b);l++){
                if(vec.empty()) break;
                if(vec[l]>=0) break;
                vec[l]=0;
            }
            int ans=0;
            rep(l,vec.size()) ans+=vec[l];
            mmax=max(ans,mmax);

        }
    }
    if(mmax<0) mmax=0;
    cout << mmax << endl;

}

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

int cmp(const void*,const void*);

int main(){
	int N,max=1;
	scanf("%d",&N);
	
	char name[N][11];
	int vote[N];
	for(int i=0;i<N;i++){
		scanf("%s",name[i]);
		vote[i] = 1;
	}
	
	qsort(name,N,sizeof(name[0]),cmp);
	
	for(int i=1;i<N;i++){
		if( strcmp(name[i],name[i-1])==0 ){
			vote[i] += vote[i-1];
			if( vote[i]>max ) max = vote[i];
		}
	}
	
	for(int i=0;i<N;i++){
		if( vote[i]==max ) printf("%s\n",name[i]);
	}
	
	return 0;
}

int cmp(const void *name1,const void *name2){
	const char *nameA = (const char *)name1;
	const char *nameB = (const char *)name2;
	return strcmp(nameA,nameB);
}


Measured memory_bytes: 5244
import sys
if sys.version_info[0]>=3: raw_input=input
  
def insertionSort(a,g):
    global cnt
    for i in range(g,len(a)):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j - g
            cnt+=1
            a[j+g] = v
  
def shellSort(a):
    global cnt
    cnt = 0
    g = []
    h = 1
    while h <= len(a):
        g.append(h)
        h = 3*h+1
    g.reverse()
    m = len(g)
    print(m)
    print(' '.join(map(str,g)))
    for i in range(m):
        insertionSort(a,g[i])
  
a=[int(raw_input()) for i in range(int(raw_input()))]
shellSort(a)
print(cnt)
for e in a: print(e)



Measured memory_bytes: 45520
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
//#define TASK "z2prefix"
#define pb push_back
#define fi first
#define se second
#define double long double
using namespace std;

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) (void)42
#endif

// every true-boy doesn't read statement!

typedef long long ll;
typedef unsigned long long ull;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
typedef vector < int > vi;
typedef vector < string > vs;

const int MAXN = 333;

int N;
int D[MAXN][MAXN];
bool Q[MAXN][MAXN];

void printQ() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cerr << Q[i][j] << " ";
		cerr << endl;
	}
}

void solve() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> D[i][j];
			Q[i][j] = 1;
		}
		Q[i][i] = 0;
	}
	//printQ();
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (i == k || j == k || i == j)
					continue;
				if (D[i][j] > D[i][k] + D[k][j]) {
					cout << -1;
					return;
				} else if (D[i][j] == D[i][k] + D[k][j]) {
					Q[i][j] = 0;
				}
			}
		}
	}
	//printQ();
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans += (Q[i][j] * D[i][j]);
		}
	}
	cout << ans / 2;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL
	assert(freopen("xxx.in", "r", stdin));
	assert(freopen("xxx.out", "w", stdout));
#else
	//assert(freopen(TASK".in", "r", stdin));
	//assert(freopen(TASK".out", "w", stdout));
#endif
	solve();
	return 0;
}

Measured memory_bytes: 768
N = int(input())
T,A = [int(i) for i in input().split(' ')]
H = [int(i) for i in input().split(' ')]
minTemp = 600

for i,h in enumerate(H):
    temp = T - h * 0.006
    if abs(temp-A) < minTemp:
        minTemp = abs(temp-A)
        place = i+1
print(place)

Measured memory_bytes: 3060
#include <bits//stdc++.h>
using namespace std;
#define int long long
#define rep(i,n,k) for(int i=n;i<k;i++)
#define P make_pair
#define F first
#define S second
#define M LLONG_MAX
signed main(void){
    int n,m,ans,w,p,q;
    ans=0;
    string s,s1,s2;
    vector<int> v;
   cin>>s;
   if(s[0]=='7'||s[1]=='7'||s[2]=='7')
   cout<<"Yes"<<endl;
   else
   cout<<"No"<<endl;
   
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll getnum(ll A , ll B) {
    int len1 , len2;
    if(A == B) return 1;
    for(len1 = 0 ; ((ll)1 << len1) <= A ; len1++);
    for(len2 = 0 ; ((ll)1 << len2) <= B ; len2++);
    if(len2 < len1) {
        ll t;
        for(t = len1 - 2 ; t >= 0 ; t--)
            if(((ll)1 << t) & A) break;
        if(t == -1) t = 0;
        else t = ((ll)1 << (t + 1)) - 1;
        if(B <= t + 1) return ((ll)1 << len1) - B;
        return (((ll)1 << (len1 - 1) | t) - B + 1) + (((ll)1 << len1) - 1 - (((ll)1 << (len1 - 1)) + B) + 1);
         
    }
    return getnum(A ^ ((ll)1 << (len1 - 1)) , B ^ ((ll)1 << (len2 - 1)));
}
int main() {
    ll A , B;
    cin >> B >> A;
    cout << getnum(A , B) << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    a,b,m = map(int, readline().split())
    A = [int(i) for i in readline().split()]
    B = [int(i) for i in readline().split()]

    t = min(A) + min(B)
    ans = 10**6
    for i in range(m):
        x,y,c = map(int, readline().split())
        tmp = A[x-1] + B[y-1] - c
        ans =min(ans, tmp)
    
    print(min(ans,t))

if __name__ == "__main__":
    main()


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-6;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int main(void){
	int32 N, M;
	set<string> st;
	cin >> N;
	string s;
	REP(i, N){
		cin >> s;
		st.insert(s);
	}
	cin >> M;
	bool closing = 1;
	REP(i, M){
		cin >> s;
		if(st.find(s) != st.end()){
			if(closing) cout << "Opened by " << s << endl;
			else cout << "Closed by " << s << endl;
			closing = !closing;
		}else{
			cout << "Unknown " << s << endl;
		}
	}
}


Measured memory_bytes: 3220
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>
#include <cstdint>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						(int)2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define	BitSetV(Val,Bit)		((Val) |= (Bit))			
#define	BitTstV(Val,Bit)		((Val) & (Bit))				
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef unsigned long long		SQWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
int main()
{
	// 入力
	int N;
	cin >> N;

	int num = N / 100;
	int amari = N % 100;

	int cnt = amari / 5;
	if (amari % 5 != 0) {
		cnt++;
	}

	int ans = 0;
	if (cnt <= num) {
		ans = 1;
	}

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


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i, j, k, n, b;
	int S[13] = { 0 };
	int H[13] = { 0 };
	int C[13] = { 0 };
	int D[13] = { 0 };

	char a;
	scanf("%d", &n);

	for (i = 0; i<n; i++) {
		scanf("%*c%c %d", &a, &b);
		if (a == 'S') { S[b - 1] = b; }
		else if (a == 'H') { H[b - 1] = b; }
		else if (a == 'C') { C[b - 1] = b; }
		else if (a == 'D') { D[b - 1] = b; }
	}

	for (j = 0; j<4; j++) {
		for (k = 0; k<13; k++) {
			if (j == 0) {
				if (S[k] != k + 1) {
					printf("S %d\n", k + 1);
				}
			}if (j == 1) {
				if (H[k] != k + 1) {
					printf("H %d\n", k + 1);
				}
			}if (j == 2) {
				if (C[k] != k + 1) {
					printf("C %d\n", k + 1);
				}
			}if (j == 3) {
				if (D[k] != k + 1) {
					printf("D %d\n", k + 1);
				}
			}
		}
	}
	return 0;
}


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

#define ll long long

void solve()
{
	ll h, n;

	cin >> h >> n;

	vector<ll> a(n);
	bool test = false;

	int sum = 0;

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

		sum += a[i];
	}

	if (sum >= h)
	{
		cout << "Yes";
	}
	else
	{
		cout << "No";
	}
}

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

	solve();

	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
  int n, a[50];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  int ans = 0;
  for(int i=0; i<n-1; i++){
    for(int j=i+1; j<n; j++){
      ans += a[i] * a[j];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

char** table;

void func(int height){

	for(int i = 0; i < height; i++){
		for(int k = 0; k <= 1049; k++)table[i][k] = '#';
	}

	int most_right = 0;

	for(int i = 0; i < height; i++){
		scanf("%s",table[i]);

		for(int k = 0;table[i][k] != '\0';k++){
			if(table[i][k] == '.' && table[i][k+1] != '\0' && table[i][k+1] != '.'){
				table[i][k] = '+';
				most_right = max(most_right,k);
				for(int p = 0; p < k; p++)table[i][p] = ' ';
				break;
			}
		}
	}


	int top,bottom;

	for(int col = 0; col <= most_right; col++){
		top = 0;
		while(true){
			for(;top <= height-1 && table[top][col] != '+';top++);
			if(top == height)break;

			for(bottom = top+1;bottom <=height-1 && table[bottom][col] == ' ';bottom++);
			if(bottom == height)break;

			if(table[bottom][col] == '+'){
				for(int i = top+1; i <= bottom-1; i++)table[i][col] = '|';
			}
			top = bottom;
		}
	}

	for(int i = 0; i < height; i++)printf("%s\n",table[i]);
}

int main(){

	table = new char*[1000];
	for(int i = 0; i < 1000; i++){
		table[i] = new char[1051];
	}

	int height;
	while(true){
		scanf("%d",&height);
		if(height == 0)break;

		func(height);
	}
	return 0;
}

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

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

    int ans = 0;
    for (int i = 0; i < (int)s.size() - 2; ++i) {
        if (s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		for(int j=0;j<s.size();j++)
		{
			string t=s;
			t.erase(i,j);
			if(t=="keyence")
			{
				cout<<"YES";
				return 0;
			}
		}
	}
	cout<<"NO";
}

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

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

int n, a, k;
vi stones;
int dp[100001];

bool calc(int x){
	if(dp[x]!=-1) return dp[x];
	if(x==0) return dp[x]=0;
	bool ans=false;;
	trav(s, stones){
		if(x-s>=0){
			if(!(dp[x-s]=calc(x-s))){
				ans=true; break;
			}
		}
	}
	return dp[x]=ans;
}

int main(){
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);
  cin.sync_with_stdio(0); cin.tie();
  cin.exceptions(cin.failbit);

  cin >> n >> k;
  rep(i, 1, n){
  	cin >> a;
  	stones.pb(a);
  }
  rep(i, 0, k) dp[i]=-1;
  cout << (calc(k)? "First" : "Second");
}

Measured memory_bytes: 8668
#include<bits/stdc++.h>
using namespace std;
string s[101];
int main(){
    int n,l;
    cin>>n>>l;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define a first
#define b second
using namespace std;
typedef pair<ll, ll> line;
const int N = 1e6 + 5;
ll n, c, h[N], dp[N];
line it[4 * N];
ll val(line u, ll x) { return u.a * x + u.b; }
void insert(int k, int l, int r, line u)
{
    if (l == r)
    {
        if (val(it[k], r) > val(u, r))
            it[k] = u;
        return;
    }
    int mid = (l + r) >> 1;
    if (it[k].a < u.a)
        swap(it[k], u);
    if (val(it[k], mid) > val(u, mid))
    {
        swap(it[k], u);
        insert(2 * k, l, mid, u);
    }
    else
        insert(2 * k + 1, mid + 1, r, u);
}

ll query(int k, int l, int r, ll x)
{
    if (l == r)
        return val(it[k], x);
    int mid = (l + r) >> 1;
    if (x < mid)
        return min(val(it[k], x), query(2 * k, l, mid, x));
    else
        return min(val(it[k], x), query(2 * k + 1, mid + 1, r, x));
}

int main()
{
    //freopen("z.inp", "r", stdin);
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    //dp[i] = min(dpj + (hj - hi)^2 + c) = dpj + hj^2 - 2hjhi + hi^2 + c
    //dp[i] = min(-2hj*hi + dpj + hj^2) + hi^2 + c
    dp[1] = 0;
    insert(1, 1, 1e6, {-2 * h[1], h[1] * h[1]});
    for (int i = 2; i <= n; i++)
    {
        dp[i] = query(1, 1, 1e6, h[i]) + h[i] * h[i] + c;
        insert(1, 1, 1e6, {-2 * h[i], dp[i] + h[i] * h[i]});
    }
    cout << dp[n];
    return 0;
}

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

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

using namespace std;

ll s[51], c[51];

ll solve(ll x, int n) {
  if (n == 0 && x >= 1) return 1LL;
  if (x <= 1) return 0LL;
  if (x < s[n-1] + 2LL) return solve(x - 1LL, n-1);
  if (x == s[n-1] + 2LL) return c[n-1] + 1LL;
  if (x < 2LL*s[n-1] + 2LL) return c[n-1] + 1LL + solve(x - (s[n-1] + 2LL), n-1);
  return c[n];
}

int main()
{
  ll n,x;
  cin >> n >> x;
  s[0] = 1;
  c[0] = 1;

  FOR(i,1,n+1) {
    s[i] = 3 + 2*s[i-1];
    c[i] = 1 + 2*c[i-1];
  }

  cout << solve(x, n) << endl;
}


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

using namespace std;

void readData(vector<string>& input_data){
    string buff;
    while(getline(cin, buff))
        input_data.push_back(buff);
}

int perseString(string line) {
    stringstream ss;
    ss << line;

    int a, b;
    ss >> a >> b;

    return a + b;
}

int countDigit(int n){
    int cnt = 1;

    while(n /= 10)
        ++cnt;

    return cnt;
}

void mainRoutine(){
    vector<string> input_data;

    readData(input_data);

    for(int i = 0; i < input_data.size(); ++i){
        auto ret = perseString(input_data[i]);
        cout << countDigit(ret) << endl;
    }
}

int main() {
    mainRoutine();

    return 0;
}



Measured memory_bytes: 3236
x,n=map(int,input().split())
if n!=0:
  p=list(map(int,input().split()))

  for i in range(0,101):
    check=x-i
    if not check in p:
      print(check)
      break
    check=x+i
    if not check in p:
      print(check)
      break

if n==0:
  print(x)

Measured memory_bytes: 9192
#include<stdio.h>
int cell[51][51],w,h;
void visit(int i,int j)
{
  cell[i][j]=0;
  if(j+1<=w)
    {
      if(cell[i][j+1]==1)
	{
	  visit(i,j+1);
	}
    }
  if(j-1>=0)
    {
      if(cell[i][j-1]==1)
	{
	  visit(i,j-1);
	}
    }
  if(i-1>=0)
    {
      if(cell[i-1][j]==1)
	{
	  visit(i-1,j);
	}
    }
  if(i+1<=h)
    {
      if(cell[i+1][j]==1)
	{
	  visit(i+1,j);
	}
    }
  if(i-1>=0 && j-1>=0)
    {
      if(cell[i-1][j-1]==1)
	{
	  visit(i-1,j-1);	
	}
}
  if(i-1>=0 && j+1<=w)
    {
      if(cell[i-1][j+1]==1)
	{
	  visit(i-1,j+1);
	}
    }
  if(i+1<=h && j+1<=w)
    {
      if(cell[i+1][j+1]==1)
	{
	  visit(i+1,j+1);
	}
    }
  if(i+1<=h && j-1>=0)
    {
      if(cell[i+1][j-1]==1)
	{
	  visit(i+1,j-1);
	}
    }
}

int main(void)
{
  int i,j,count=0;
  while(1)
    {
      count=0;
      scanf("%d %d",&w,&h);
      
      if(w==0 && h==0)break;
      
      for(i=0;i<h;i++)
	{
	  for(j=0;j<w;j++)
	    {
	      scanf("%d",&cell[i][j]);
	    }
	}
      for(i=0;i<h;i++)
	{
	  for(j=0;j<w;j++)
	    {
		if(cell[i][j]==1)
		  {
		    count++;
		    visit(i,j);
		  }
	    }
	}
      printf("%d\n",count);
    }
  return 0;
}

Measured memory_bytes: 0
_, k = map(int, input().split())
A = [*map(int, input().split())]
ng, ok = 0, 1<<30
while ok - ng > 1:
    m = (ng + ok) // 2
    if k < sum((a-1)//m for a in A): ng = m
    else: ok = m
print(ok)


Measured memory_bytes: 31000
// ABC 147-D
// 2019.12.23 bal4u

#include <stdio.h>
#include <ctype.h>

typedef long long ll;

#define gc() getchar_unlocked()

ll in() {   // 非負整数の入力
	ll n = 0; int c;
	do c = gc();
	while (isspace(c));
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define M 1000000007
int N;
ll A[300005];

int main()
{
	int i, n, b;
	ll ans, a;
	
	N = (int)in();
	for (i = 0; i < N; ++i) A[i] = in();

	ans = 0;
	b = 61; while (b--) {
		n = 0;
		i = N; while (i--) {
			if ((A[i] >> b) & 1) ++n;
		}
		if (n > 0 && n < N)
			ans = (ans + (1LL << b) % M * ((ll)n*(N-n) % M)) % M;
	}
	printf("%d\n", (int)ans);
	return 0;
}


Measured memory_bytes: 2560
n, a, b = map(int, input().split())
if a + b <= n:
    if a <= b:
        print(a, 0)
    else:
        print(b, 0)
elif a + b > n:
    if a <= b:
        print(str(a) + " " + str(a + b - n))
    else:
        print(str(b) + " " + str(a + b - n))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define REP(i, n) for(int i=0; i<n; i++)
#define RER(i, n) for(int i=n-1; i>=0; i--)
#define ALL(v) v.begin() v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int n;

int gcd(int a, int b){
	if(b==0) return a;
	return gcd(b, a%b);
}

signed main(){
	int a, b;
	cin >> n >> a;
	REP(i, n-1){
		cin >> b;
		b = gcd(a, b);
		a = b;
	}
	cout << a << endl;
    return 0;
}

Measured memory_bytes: 256
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
s = input()
t = input()
if s == t:
    print(0)
    exit()
cnt = 0
for i in range(len(s)):
    if s[i] != t[i]:
        cnt += 1
print(cnt)


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

const ll mod=1e9+7;

ll dp[101][5][5][5];

int main(){
	int n;cin>>n;
	dp[0][3][3][3]=1;
	for(int now=1;now<=n;now++){
        for(int i=1;i<=4;i++){
            for(int j=1;j<=4;j++){
                for(int k=1;k<=4;k++){
                    for(int nxt=1;nxt<=4;nxt++){
                        if(j==1&&k==2&&nxt==3) continue;
                        if(j==2&&k==1&&nxt==3) continue;
                        if(j==1&&k==3&&nxt==2) continue;
                        
                        if(i==1&&j==2&&nxt==3) continue;
                        if(i==1&&k==2&&nxt==3) continue;
                        dp[now][j][k][nxt]+=dp[now-1][i][j][k],dp[now][j][k][nxt]%=mod;
                    }
                }
            }
        }
	}
	ll ans=0;
	for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            for(int k=1;k<=4;k++)
            ans+=dp[n][i][j][k],ans%=mod;
    cout<<ans<<endl;

	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAXN 100005
#define lint long long
#define trace(x) cout<<#x<<" = "<<x<<'\n'
#define trace2(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<'\n'
#define tracea(arr, i) cout<<#arr<<"["<<i<<"]"<<" = "<<arr[i]<<'\n'
#define print(arr, n) for (int iDx = 0; iDx < (n); iDx++) cout << arr[iDx] << " \n"[iDx == (n)-1]
#define sz(x) (int)(x).size()
using namespace std;
struct ii {
	lint a, b;
	bool operator < (ii o) const { return a*o.b > o.a*b; }
};
struct iii {
	int a, b, c;
	bool operator < (iii o) const { return make_tuple(a, b, c) < make_tuple(o.a, o.b, o.c); }
};
int TC, M, K, Q, x, y, z;

lint N, arr[5];
priority_queue<ii> pq;

int main() {
	#ifdef FAIRUZI10
	freopen("/home/fairuzi/Documents/CP/input.in", "r", stdin);
	#endif
	
	scanf("%lld%lld%lld%lld", &arr[0], &arr[1], &arr[2], &arr[3]);
	pq.push({arr[0], 1});
	pq.push({arr[1], 2});
	pq.push({arr[2], 4});
	pq.push({arr[3], 8});
	scanf("%lld", &N);
	N <<= 2;
	lint ans = 0;
	while (N) {
		ii now = pq.top();
		pq.pop();
		lint banyak = N/now.b;
		ans += banyak*now.a;
		N %= now.b;
	}
	printf("%lld\n", ans);
	
	return 0;
}


Measured memory_bytes: 256
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    v = list(map(int, input().split()))
    a = Counter(v[0::2]).most_common()
    b = Counter(v[1::2]).most_common()
    a.append([0, 0])
    b.append([0, 0])

    if a[0][0] != b[0][0]:
        print(n-(a[0][1]+b[0][1]))
    else:
        print(min(n-(a[1][1]+b[0][1]), n-(a[0][1]+b[1][1])))


if __name__ == '__main__':
    main()


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll H, W;
    cin >> H >> W;
    vector<string> A(H+2);
    REP(i,1,H+1) {
        cin >> A[i];
        A[i] = "." + A[i] + ".";
    }
    REP(i,0,W+1) {
        A[0] += ".";
        A[H+1] += ".";
    }

    ll i = 1, j = 1;
    bool f = true;
    ll d = 0;
    while(i < H+1 && j < W+1) {
        if(d == 0 && A[i][j-1] == '#') {
            f = false;
            break;
        }
        else if(d == 1 && A[i-1][j] == '#') {
            f = false;
            break;
        }
        else {
            if(i == H && j == W) break;
            if(A[i+1][j] == '#' && A[i][j+1] == '.') {
                ++i;
                d = 0;
            }
            else if(A[i+1][j] == '.' && A[i][j+1] == '#') {
                ++j;
                d = 1;
            }
            else {
                f = false;
                break;
            }
        }
    }
    if(f) PR("Possible");
    else PR("Impossible");

    return 0;
}

/*

*/

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main() {
  int x, a, b;
  cin >> x >> a >> b;
  if (a - b >= 0) {
    cout << "delicious" << endl;
  } else if (abs(a - b) <= x) {
    cout << "safe" << endl;
  } else {
    cout << "dangerous" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
// from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

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

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

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

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

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

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

#[allow(unused_macros)]
macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } }
// macro_rules! debug { ($x: expr) => () }

#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
    T: Iterator,
    T::Item: std::fmt::Display
{
    let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
    res.pop();
    res
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};

fn main() {
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }
    
    input! {
        a: usize,
        b: usize,
        c: usize,
    }

    println!("{}", max(a*10+b+c, max(a+10*b+c, a+b+c*10)));
}



Measured memory_bytes: 4476
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
int main()
{
    int N, ans = 0;
    cin >> N;
    vint p(N);
    rep(i, N) cin >> p[i];
    for (int i = 0; i < N; i++)
    {
        if (p[i] == i + 1)
        {
            if(i!=N)
            swap(p[i], p[i + 1]);
            else swap(p[i],p[i-1]);
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
    long long N, K,ans;cin >> N >> K;
    if(K%2 == 1){
        long long M = N/K;
        ans = M*M*M;
    }
    else{
        long long M = N/K,L = (N + K/2)/K;
        ans = M*M*M + L*L*L;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <limits.h>
#include <math.h>

int main(void){
	int num, min, a[1000];

	while(1){
		scanf("%d", &num);
		if(!num) break;
		for(int i=0; i<num; i++){
			scanf("%d", &a[i]);
		}

		min=INT_MAX;
		for(int i=0; i<num-1; i++){
			for(int j =i+1; j<num; j++){
				min = fmin(min, abs(a[j]-a[i]));
			}
		}
		printf("%d\n", min);
	}

	return 0;
}


Measured memory_bytes: 2104
#include "bits/stdc++.h"

using namespace std;

int main() {
    vector<int> g1 {1, 3, 5, 7, 8, 10, 12};
    vector<int> g2 {4, 6, 9, 11};
    int x, y;
    cin >> x >> y;

    if (find(g1.begin(), g1.end(), x) != g1.end() && find(g1.begin(), g1.end(), y) != g1.end()) {
        cout << "Yes" << endl;
    } else if (find(g2.begin(), g2.end(), x) != g2.end() && find(g2.begin(), g2.end(), y) != g2.end()) {
        cout << "Yes" << endl;
    } else if (x == 2 && y == 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
struct edge{ll to,cost;};

int main() {
  ll ans=1;
  ll n,k;
  cin >> n >> k;
  vl a(n);
  ll sum=0;
  rep(i,n){
    cin >> a[i];
    sum += a[i];
  }
  ll z=sqrt(sum);
  vl p(100000);
  ll j=0;
  FOR(i,1,z+1){
    if(sum%i==0){
      p[j]=i;
      j++;
    }
  }
  j--;
  ll x;
  if(sum==z*z){
    p.resize(2*j+1);
    FOR(i,j+1,2*j+1){
      p[i]=sum/p[2*j-i];
    }
    x=2*j+1;
  }
  else{
    p.resize(2*j+2);
    FOR(i,j+1,2*j+2){
      p[i]=sum/p[2*j+1-i];
    }
    x=2*j+2;
  }
  vl b(n);
  vl c(n);
  rep(i,x){
    ll MIN=INF;
    rep(j,n){
      b[j]=a[j]%p[i];
    }
    sort(b.begin(),b.end());
    rep(j,n){
      c[j]=(p[i]-b[j])%p[i];
    }
    vl sumb(n);
    vl sumc(n);
    sumb[0]=b[0];
    sumc[n-1]=c[n-1];
    rep(i,n-1){
      sumb[i+1]=sumb[i]+b[i+1];
      sumc[n-2-i]=sumc[n-1-i]+c[n-2-i];
    }
    rep(j,n-1){
      MIN=min(MIN,max(sumb[j],sumc[j+1]));
    }
    if(MIN<=k){
      ans=p[i];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9


int main(){
	while(1){
	int n,m;
	cin>>n>>m;
	if(n==0)break;
	vector<vector<mp> > gt(m);
	vector<vector<mp> > gc(m);
	vector<vector<ll> > dpt(m,vector<ll> (m,inf) );
	vector<vector<ll> > dpc(m,vector<ll> (m,inf) );
	for(int i=0;i<n;i++){
		ll a,b,c,t;
		cin>>a>>b>>c>>t;
		a--,b--;
		dpc[a][b]=dpc[b][a] = c;
		dpt[a][b] = dpt[b][a] = t;
	}
	for(int i=0;i<m;i++)dpc[i][i] = dpt[i][i] = 0;
	for(int k=0;k<m;k++)
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				if(dpc[i][k] != inf && dpc[k][j] != inf){
					dpc[i][j] = min(dpc[i][j],dpc[i][k]+dpc[k][j]);
					dpt[i][j] = min(dpt[i][j],dpt[i][k]+dpt[k][j]);
				}
	int k;
	cin>>k;
	for(int i=0;i<k;i++){
		int p,q,r;
		cin>>p>>q>>r;
		p--,q--;
		if(r==0){
			cout<<dpc[p][q]<<endl;
		}else{
			cout<<dpt[p][q]<<endl;
		}
	}
	}

	return 0;
}



Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	string s;
	cin >> s;
	ll n = s.size();
	
	string dp[26];
	zep(j, 0, 26){dp[j] = j+'a';}
	
	zep(i, 0, n){
		string a = s.substr(i, 1);
		string ms = dp[0]+a;

		zep(j, 1, 26){
			string tmp = dp[j]+a;
			if(tmp.size() < ms.size() || (tmp.size() == ms.size() && tmp < ms)){
				ms = dp[j]+a;
			}
		}
		dp[s[i]-'a'] = ms;
	}
	
	string ans = dp[0];
	zep(j, 1, 26){
		if(dp[j].size() < ans.size() || (dp[j].size() == ans.size() && dp[j] < ans)){
			ans = dp[j];
		}
	}
	print(ans)
	return 0;
}

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

digis_sum = 10 ** 2

def cal_digit(num):
    tmp = 0
    q = num
    while q:
        q, r = divmod(q, 10)
        tmp += r
        if q == 0:
            break
    return tmp

for x in range(1, int(n/2)+1):
    y = n - x
    t = cal_digit(x) + cal_digit(y)
    if t < digis_sum:
        digis_sum = t

print(digis_sum)

Measured memory_bytes: 3064
N, = map(int, input().split())
rs = []
for i in range(N):
    s, a = input().split()
    a = int(a)
    rs.append((i+1, s, -a))
rs.sort(key=lambda x : (x[1], x[2]))
for i, s, a in rs:
    print(i)


Measured memory_bytes: 38384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}

int main(void){
	int a,b,c,d;
	scanf("%1d",&a);
	scanf("%1d",&b);
	scanf("%1d",&c);
	scanf("%1d",&d);
	if(a+b+c+d==7)printf("%d+%d+%d+%d=7\n",a,b,c,d);
	else if(a-b+c+d==7)printf("%d-%d+%d+%d=7\n",a,b,c,d);
	else if(a+b-c+d==7)printf("%d+%d-%d+%d=7\n",a,b,c,d);
	else if(a+b+c-d==7)printf("%d+%d+%d-%d=7\n",a,b,c,d);
	else if(a-b-c+d==7)printf("%d-%d-%d+%d=7\n",a,b,c,d);
	else if(a-b+c-d==7)printf("%d-%d+%d-%d=7\n",a,b,c,d);
	else if(a+b-c-d==7)printf("%d+%d-%d-%d=7\n",a,b,c,d);
	else printf("%d-%d-%d-%d=7\n",a,b,c,d);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#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 F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 998244353;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int>v(n);
    int f = 0;
    for (auto &i : v) {
        cin >> i;
    }
    for (int i = 1 ; i < v.size() ; i++) {
        if (v[i] + v[i-1] >= k) {
            f = i;
            break;
        }
    }
    if (!f) {
        cout << "Impossible\n";
        exit(0);
    }
    cout << "Possible\n";
    f1(f-1){
        cout << i <<'\n';
    }
    for (int i = n - 1 ; i >= f ; i--) {
        cout << i <<'\n';
    }
}
    



Measured memory_bytes: 1280
#include <algorithm>
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define mod (int)1000000007
// Big two primes 
#define X 1011001110001111ll
#define M 26388279066623ll
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define int int
#define ll long long
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define in(x) scanf("%d", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define vi vector<int> 
#define fi first
#define se second
#define endl "\n"
#define pi pair<int, int>
#define vii vector<pi>
const int MAXN = (int)((1e5) + 10);
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;}  
bool isPrime(int N){ for(int i=2;i*i<=N;++i){if(N%i==0) return false;}return true;}

int main()
{
    fio;

    int n,l;
    cin>>n>>l;

    vector<string> a(n);

    for0(i, n) 
     cin>>a[i];

    string str; 

    sort(all(a));

    for0(i, n)
     str += a[i]; 

    cout<<str<<endl; 


    rr;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <stack>
#include <queue>
#include <set>

#define mod 1000000007
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, k;
    ll ans = 1;
    cin >> n >> k;
    vector<ll> a(n+1);
    vector<pair<ll, ll>> b(n+1);
    b[1].first++;
    b[1].second=0;
    for(ll i= 1; i<=n; i++) cin >> a[i];
    for(ll j=1; j<=k; j++){
        ans=a[ans];
        b[ans].first++;
        if(b[ans].first==2){
            j+=(j-b[ans].second)*((k-j)/(j-b[ans].second));
        }
        b[ans].second=j;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 7952
#include<stdio.h>
#include<ctype.h>

int main()
{
	int i;
	i = 0;
	char ch[10000];
	while(1){
		i=i+1;
		scanf("%c", &ch[i]);
		if(ch[i]=='\n'){
			printf("\n");
			break;
		}
		if(isalpha(ch[i])){
			if(isupper(ch[i])){
				printf("%c",tolower(ch[i]));
			}else{
			    printf("%c",toupper(ch[i]));
			}
		}
		else{
			printf("%c",ch[i]);
		}
	}
	return 0;
}

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

using namespace std;
typedef long long ll;
const int N = 400;
ll dis[N][N],w[N][N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n,m,L;
    cin>>n>>m>>L;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dis[i][j]=w[i][j]=(ll)1e18;
        }
    }
    for(int i=0;i<=n;i++) dis[i][i]=w[i][i]=0;
    ll a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        dis[a][b]=dis[b][a]=c;
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(dis[i][j]<=L){
                w[i][j]=w[j][i]=1;
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
            }
        }
    }
    int q;
    cin>>q;
    int s,t;
    while(q--){
        cin>>s>>t;
        if(w[s][t]==(ll)1e18){
             cout<<-1<<endl;
             continue;
        }
        cout<<w[s][t]-1<<endl;
    }
    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  cin>>S;
  if (S == "SUN") {
    cout<<7<<endl;
  }
  else if (S == "MON") {
    cout<<6<<endl;
  }
  else if (S == "TUE") {
    cout<<5<<endl;
  }
  else if (S == "WED") {
    cout<<4<<endl;
  }
  else if (S == "THU") {
    cout<<3<<endl;
  }
  else if (S == "FRI") {
    cout<<2<<endl;
  }
  else {
    cout<<1<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define mod 1000000007
#define ull unsigned lint
#define db long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define gc getchar()
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
inline int inn()
{
	int x,ch;while((ch=gc)<'0'||ch>'9');
	x=ch^'0';while((ch=gc)>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^'0');return x;
}
const int N=200010;
int dp[N],c[N],a[N],s[N];
inline int upd(int &x,int y) { return x+=y,(x>=mod?x-=mod:0); }
int main()
{
	int n=inn();rep(i,1,n) c[i]=inn();int ns=n;n=0;
	rep(i,1,ns) if(c[i]^c[i-1]) a[++n]=c[i];dp[0]=1;
	rep(i,1,n) upd(s[a[i]],dp[i-1]),upd(dp[i],s[a[i]]);
	return !printf("%d\n",dp[n]);
}

Measured memory_bytes: 3328