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

using namespace std;

const int MOD = (int)1e9 + 7;

int dp[101010][2];

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

  string s;
  cin >> s;
  int n = s.size();
  dp[0][0] = 1;
  for (int i = 0; i < n; i++) {
    // a + b = 0
    if (s[i] == '0') {
      dp[i + 1][0] = dp[i][0];
      dp[i + 1][1] = dp[i][1];
    } else {
      dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD;
    }

    // a + b = 1
    if (s[i] == '0') {
      dp[i + 1][1] += dp[i][1] * 2 % MOD, dp[i + 1][1] %= MOD;
    } else {
      dp[i + 1][0] += dp[i][0] * 2 % MOD, dp[i + 1][0] %= MOD;
      dp[i + 1][1] += dp[i][1] * 2 % MOD, dp[i + 1][1] %= MOD;
    }
  }

  int ans = (dp[n][0] + dp[n][1]) % MOD;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1232
using System;

namespace Project
{
	class Dice
	{
		public int face;
		public int N;
		public int E;
		public int S;
		public int W;
		public int back;

/*		public Dice(int a1, int a2, int a3, int a4, int a5, int a6)
		{
			face = a1;
			N = a5;
			E = a3;
			S = a2;
			W = a4;
			back = a6;
		}
*/		
		public void roll(char D)
		{
			int pface = face;
			int pN = N;
			int pE = E;
			int pW = W;
			int pS = S;
			int pback = back;
			switch (D)
			{
				case 'N':
					face = pS;
					N = pface;
					S = pback;
					back = pN;
					break;
				case 'E':
					face = pW;
					E = pface;
					W = pback;
					back = pE;
					break;
				case 'W':
					face = pE;
					E = pback;
					W = pface;
					back = pW;
					break;
				case 'S':
					face = pN;
					N = pback;
					S = pface;
					back = pS;
					break;
			}
		}
	}

	class MainClass
	{
		public static void Main(string[] args)
		{
			int n = int.Parse(Console.ReadLine());
			Dice[] dice = new Dice[n];
			for (int i = 0; i < n; i++)
			{
				string[] s = Console.ReadLine().Split(' ');
				int[] a = new int[6];
				for (int j = 0; j < 6; j++)
				{
					a[j] = int.Parse(s[j]);
				}
				dice[i] = new Dice();
				dice[i].face = a[0];
				dice[i].N = a[4];
				dice[i].E = a[2];
				dice[i].S = a[1];
				dice[i].W = a[3];
				dice[i].back = a[5];
			}
			int[,] count = new int[n, n];

			for (int i = 0; i < n - 1; i++)
			{
				for (int j = i + 1; j < n; j++)
				{
					count[i, j] = 0;
					while (count[i, j] < 10)
					{
						if (checkdice(dice[i], dice[j])) break;
						dice[i].roll('N');
						if (checkdice(dice[i], dice[j])) break;
						dice[i].roll('N');
						if (checkdice(dice[i], dice[j])) break;
						dice[i].roll('N');
						if (checkdice(dice[i], dice[j])) break;
						dice[i].roll('N');
						if (count[i, j] == 4) dice[i].roll('N');
						dice[i].roll('W');
						count[i, j]++;
					}
				}
			}
			bool b = true;
			bool c;
			foreach (var x in count)
			{
				if (x == 0) continue;
				c = b && x == 10;
//				Console.WriteLine(x);
//				Console.WriteLine(c);
				b = c;
			}

			if(b) Console.WriteLine("Yes");
			else Console.WriteLine("No");


		}

		public static bool checkdice(Dice dice1, Dice dice2)
		{
			if (dice1.face == dice2.face && dice1.N == dice2.N && dice1.E == dice2.E && dice1.S == dice2.S && dice1.W == dice2.W && dice1.back == dice2.back) return true;
			else return false;
		}

	}
}

Measured memory_bytes: 9052
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <map>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

int main(void) {
  ll n;
  vector<pair<ll, ll>> v;
  map<pair<ll, ll>, ll> m;
  cin>>n;
  for(ll i=0; i<n; i++) {
    ll x, y;
    cin>>x>>y;
    v.push_back(make_pair(x, y));
  }

  for(ll i=0; i<n; i++) {
    for(ll j=i+1; j<n; j++) {
      m[make_pair(v[i].first-v[j].first, v[i].second-v[j].second)]++;
      m[make_pair(v[j].first-v[i].first, v[j].second-v[i].second)]++;
    }
  }
  ll ans=0;
  for(auto &p: m) {
    ans = max(ans, p.second);
  }
  std::cout << n-ans << std::endl;
  return 0;
}



Measured memory_bytes: 384
(* O(|s|) *)
let s = read_line () in
for i = int_of_char 'a' to int_of_char 'z' do
  let c = char_of_int i in
  try String.index s c |> ignore with
  | _ -> Printf.printf "%c\n" c; exit 0
done;
print_endline "None"

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

int main(){
  int a,b;
  cin >> a >> b ;
  if(a == 2){
    a = 1;
  }
  else if(a == 4 || a == 6 || a == 9 || a == 11){
    a = 2;
  }
  else{
    a = 3;
  }
  
  if(b == 2){
    b = 1;
  }
  else if(b == 4 || b == 6 || b == 9 || b == 11){
    b = 2;
  }
  else{
    b = 3;
  }
  
  if(a == b){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<set>
#include<map>
const int N=1048580,M=21;
using namespace std;
int n,m,len,ans;
int f[M][N],g[M][N];
char s[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++){
		scanf("%s",s);
		for(int j=0;j<(1<<i);j++)f[i][j]=s[j]-'0';//cout<<f[i][j]<<" ";;puts("");
	}
	for(int i=1;i<=n;i++)for(int j=0;j<(1<<i);j++){
		int b=(j>>(i-1))&1,r=0;
		for(;r<i&&((j>>(i-r-1))&1)==b;r++);
		g[i][j]=r==i?-1:r;
	}
	for(int i=0;i<=n;i++){
		for(int j=1;j<=n-i;j++)
		for(int k=0;k<(1<<(i+j));k++){
			f[i][k>>j]+=f[i+j][k];
			int t=g[j][k&((1<<j)-1)];
			if(t==-1)continue;
			f[i+j-t][((k>>j)<<(j-t))|(k&((1<<(j-t))-1))]+=f[i+j][k];
		}
	//	cout<<i<<endl;
		for(int j=(1<<i)-1;j>=0;j--){
		//	cout<<f[i][j]<<endl;
		//	cout<<i<<" "<<j<<endl;
			if(f[i][j]>=m){
				len=i;ans=j;
			}
		}
	}
	for(int i=len-1;i>=0;i--){
		printf("%d",(ans>>i)&1);
	}
	return 0;
}

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

typedef long long  ll;

ll MOD = 1000000007;
ll INF = 90000000000000000;
int PI = 3.1415926535;

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

ll z = 0;

int main(){
  ll N,M;cin >> N >> M;
  if(N < M)swap(N,M);
  if(M == 1){
    if(N == 1){
      cout << 1 << endl;
      return 0;
    }
    cout << max(z,N - 2) << endl;
  }else if(M == 2){
    cout << 0 << endl;
  }else{
    cout << (N - 2) * (M - 2)  << endl;
  }
}

Measured memory_bytes: 256
#if defined(__GNUC__)
#include <bits/stdc++.h>
#define __int32 __int32_t
// __GNUC__
#else
#include "bits/stdc++.h"
#endif
using namespace std;

#define int long long

#define itn __int32
#define REP(i, n) for(itn (i) = 0; (i) < (n); ++(i))
#define REP2(i, x, n) for(itn (i) = x; (i) < (n); ++(i))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort(ALL(x), greater<decltype(x)::value_type>())
#define RSORT2(x, T) sort(ALL(x), greater<T>())
#define REVERSE(x) reverce(ALL(x))
#define ACM(x, y) accumulate(ALL(x), y)

#define INT_POW(x, y) [](int a, int b) -> int {int c = a; REP(i, b - 1){c *= a;} return c;}(x, y)
#define INT_POWM(x, y, m) [](int a, int b, int m) -> int {int c = a; REP(i, b - 1){c *= a; c %= m;} return c;}(x, y, m)
#define FCT(x) [](int a) -> int {int r = 1; REP(i, a){r *= i;} return r;}(x)

// デバッグ用
#define PUT_LIST(x, y) std::copy(ALL(x), ostream_iterator<decltype(x)::value_type>(cout, y))

const int kMod = 1e9 + 7;

itn main() {
	ios::sync_with_stdio(false);

	vector<vector<int>> a(3);
	vector<vector<bool>> check(3);

	REP(i, 3) {
		a[i].resize(3);
		check[i].resize(3, false);
	}

	REP(i, 9) {
		cin >> a[i / 3][i % 3];
	}

	int n;

	cin >> n;

	vector<int> b(n);

	REP(i, n) {
		cin >> b[i];
	}

	REP(i, n) {
		REP(j, 9) {
			if (b[i] == a[j / 3][j % 3]) {
				check[j / 3][j % 3] = true;
				break;
			}
		}
	}

	REP(i, 3) {
		if (check[i][0] == true && check[i][0] == check[i][1] && check[i][0] == check[i][2]) {
			cout << "Yes";
			return 0;
		}
	}

	REP(i, 3) {
		if (check[0][i] == true && check[0][i] == check[1][i] && check[0][i] == check[2][i]) {
			cout << "Yes";
			return 0;
		}
	}

	if (check[0][0] == true && check[0][0] == check[1][1] && check[0][0] == check[2][2]) {
		cout << "Yes";
		return 0;
	}

	if (check[0][2] == true && check[0][2] == check[1][1] && check[0][2] == check[2][0]) {
		cout << "Yes";
		return 0;
	}

	cout << "No";

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
 	public static void main (String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.next().toCharArray();
		int length = arr.length;
		int[][] dp = new int[13][length];
	    for (int i = 0; i < 10; i++) {
	        if (arr[0] == '?' || arr[0] - '0' == i) {
	            dp[i][0] = 1;
	        }
	    }
	    for (int i = 1; i < length; i++) {
	        for (int j = 0; j < 13; j++) {
	            for (int k = 0; k < 10; k++) {
	                if (arr[i] == '?' || arr[i] - '0' == k) {
	                    dp[(j * 10 + k) % 13][i] += dp[j][i - 1];
	                    dp[(j * 10 + k) % 13][i] %= MOD;
	                }
	            }
	        }
	    }
		System.out.println(dp[5][length - 1]);
	}
}


Measured memory_bytes: 30468
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    ll a2 = a;
    ll b2 = b;
    ll m = 2;
    ll ans = 0;
    a2>>=1;
    b2>>=1;
    while(m<=b){
        m*=2;
        ll am = a%m;
        ll bm = (b-1)%m;
        if(((a2%2)*am+(b2%2)*bm)%2==1){
            ans+=m/2;
        }
        a2>>=1;
        b2>>=1;
    }
    if(a%2==0)a++;
    if(b%2==0)b--;
    if(a<=b){
        ans+=1-((b-a)/2)%2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int a, b;
	std::cin >> a >> b;
	if (a+b == 15)
		std::cout << "+\n";
	else if (a*b == 15)
		std::cout << "*\n";
	else
		std::cout << "x\n";
}


Measured memory_bytes: 512
/*
	##############################
	#  Author: Pratyush Gaurav   #
	#  College: NIT ROURKELA     #
	##############################
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli > plli;
typedef vector<lli> vlli;
typedef vector<plli > vplli;

#define rep(i,a,b) for(i = a ; i < b ; i++)
#define repr(i,a) for(i = a ; i >= 0 ; i--)
#define REP(i,a,b) for(i = a ; i <= b ; i++)
#define REPR(i,a,b) for(i = a ; i >= b ; i--)
#define mem(a,b)memset(a,b,sizeof(a))
#define opt ios_base::sync_with_stdio(false);cin.tie(NULL);
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define sqr(x) (x)*(x)
#define all(a) a.begin(),a.end()

#define endl '\n'

const long long INF = 2000000000000;
const long long MOD = 1000000007;
const long long MAXN = 100005;

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

lli a[200][200];

void solve()
{
    lli n,m,i,j;
    cin>>n>>m;
    
    n--,m--;

    cout << 100 << ' ' << 100 << '\n';

    rep(i,0,100)
    {
        rep(j,0,50)
        {
            a[i][j] = 0;
        }
    }

    rep(i,0,100)
    {
        rep(j,50,100)
        {
            a[i][j] = 1;
        }
    }

    lli row = 0, col = 0;

    while(n--)
    {
        a[row][col] = 1;

        col += 2;

        if(col == 50){
            col = 0;
            row+=2;
        }
    }

    row = 0, col = 51;
    while(m--)
    {
        a[row][col] = 0;

        col += 2;

        if(col == 101){
            col = 51;
            row+=2;
        }
    }

    rep(i,0,100){
        rep(j,0,100){
            if(a[i][j]){
                cout << '.';
            }
            else{
                cout << '#';
            }
        }
        cout << '\n';
    }
}
int main()
{
	opt;
	lli t = 1;
	while(t--)
	    solve();
	return 0;
}










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

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

    int x[N];
    for(int i=0; i<N; i++){
        cin >> x[i];
    }

    int M=0;
    
    for(int j=0; j<N; j++){
        if( (K >= 2*x[j]) == true){
            M += 2 * x[j];
        }
        else if( (K < 2*x[j]) == true){
            M += 2 * (K - x[j]);
        }
        else
        {
            M = M;
        }
        
    }

    cout << M << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

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

  vector<int> a(N);
  rep(i, N) { cin >> a[i]; }
  sort(a.begin(), a.end(), greater<int>());

  a.push_back(0);

  int i = 0;
  while (i + 1 < N && i + 1 < a[i + 1]) {
    i++;
  }

  int j = lower_bound(a.begin(), a.end(), i, greater<int>()) - a.begin();
  cout << ((a[i] - i) % 2 == 1 && (j - i) % 2 == 1 ? "Second" : "First")
       << endl;

  return 0;
}

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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

void swap1(int &x, int &y) {
  x ^= y;
  y ^= x;
  x ^= y;
}

void swap2(int &x, int &y) {
  int tmp = x;
  x = y;
  y = tmp;
}

int main() {
  int D;
  cin >> D;
  D = 25 - D;
  string s = "Christmas";
  for (int i = 0; i < D; i++)
    s += " Eve";
  cout << s << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define rep(i,n)for(int i=0;i<(int)(n);i++)
main(){
char s[101];
scanf("%s",s);
int l=strlen(s),min=200;
rep(i,l){
	int ans=0,t=0;
	rep(j,l+1){
		if(j==l||s[i]==s[j]){if(ans<t)ans=t;t=0;}
		else t++;
	}
	if(ans<min)min=ans;
}
printf("%d\n",min);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff(i,a,b) for(i=a;i<=b;i++)
#define fb(i,a,b) for(i=a;i>=b;i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define m 1000000007
int main()
{
    fast;
    ll k,s,i,j,count=0;
    cin>>k>>s;
    ff(i,0,k)
    {
        ff(j,0,k)
        {
            if(s-(i+j)<=k && s-(i+j)>=0)
                count++;
        }
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.close();

        int sum = 0;

        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                for(int k=1; k<=N; k++){
                    sum = sum + gcd(gcd(i, j),k);
                }
            }
        }


        System.out.println(sum);

        
    }
    static int gcd(int a, int b) {//最大公約数を求める
        if(b == 0) return a;
        return gcd(b, a%b);
    }
}    



Measured memory_bytes: 35780
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
	
	Scanner scan = new Scanner(System.in);
	
	int n = scan.nextInt();
	String[] str1 = new String[n];
	String[] str2 = new String[n];
	
	for(int i = 0; i < n; i++){
	    str1[i] = " "+scan.next();
	    str2[i] = " "+scan.next();
	    System.out.println(lcs(str1[i],str2[i]));
	}
	
    }

    public static int lcs(String str1,String str2){
	char[] chr1 = str1.toCharArray();
	char[] chr2 = str2.toCharArray();
	int c1 = chr1.length;
	int c2 = chr2.length;
	int maxl = 0;
	int[][] c = new int[c1][c2];

	for(int i = 0; i < c1; i++){c[i][0] = 0;}
	for(int i = 0; i < c2; i++){c[0][i] = 0;}

	for(int i = 1; i < c1; i++){
	    for(int j = 1; j < c2; j++){
		if(chr1[i] == chr2[j]){
		    c[i][j] = c[i-1][j-1]+1;
		}else{
		    c[i][j] = Math.max(c[i-1][j],c[i][j-1]);
		}
		maxl = Math.max(maxl,c[i][j]);
	    }
	}
	return maxl;
    }
}

Measured memory_bytes: 64740
#include <iostream>
#include <vector>
#include <map>
#include <sstream>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<pair<int,string>,int>  NODE;

#define cost first.first
#define pos first.second
#define visit second

map<string,vector< pair<string,int> > > nodeInfo;
map<string,int> cakeShop;

int dijkstra(){
	int ret = (1<<25);
	priority_queue<NODE,vector<NODE>,greater<NODE> > Q;

	Q.push(make_pair(make_pair(0,"H"),0));
	map<string,int> memo[1<<10];
	while(Q.size()){
		NODE q = Q.top();Q.pop();
		//cout << q.visit << " " << q.cost << endl;
		
		if(memo[q.visit].find(q.pos) != memo[q.visit].end() ){
			if(memo[q.visit][q.pos] <= q.cost)continue;
		}
		
		memo[q.visit][q.pos] = q.cost;
		
		if(q.pos == "D"){
			ret = min(q.cost,ret);
		}
		
		rep(i,nodeInfo[q.pos].size()){
			NODE next;
			next.visit = q.visit;
			string t = nodeInfo[q.pos][i].first;
			next.cost = q.cost + nodeInfo[q.pos][i].second;
			next.pos = t;
			
			if(t[0] == 'C' && (q.visit & (1<<(t[1]-'1'))) )continue;
			
			if(t[0] == 'C'){
				next.visit |= (1<<(t[1]-'1'));
				next.cost  -= cakeShop[next.pos];
				//cout << next.visit << endl;
			}
			Q.push(next);
		}
	}
	return ret;
}
int main(){
	int m,n,k,d;
	int base;
	while(cin >> m >> n >> k >> d , m ){
		nodeInfo.clear();
		cakeShop.clear();
		rep(i,m){
			int c;
			cin >> c;
			stringstream ss;
			ss << 'C' << i+1;
			//cout << ss.str() << "=" << c << endl;
			cakeShop[ss.str()] = c;
		}
		
		//cout << cakeShop["C1"] << endl;
		rep(i,d){
			string a,b;int c;
			cin >> a >> b >> c;
			nodeInfo[a].push_back( make_pair(b,c*k) );
			nodeInfo[b].push_back( make_pair(a,c*k) );
		}
		cout << dijkstra() << endl;
	}
	
	
}

Measured memory_bytes: 1344
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

namespace {
const vector<int64_t> nums = {0, 0, 1, 2, 2*3, 2*3*4, 2*3*4*5, 2*3*4*5*6, 2*3*4*5*6*7};
}

int main() {
  int N;
  cin >> N;
  vector<int> P(N);
  vector<int> Q(N);
  vector<int> sorted(N);
  
  for (size_t i = 0; i < N; ++i) {
    int n;
    cin >> n;
    P[i] = n;
    sorted[i] = n;
  }
  for (size_t i = 0; i < N; ++i) {
    cin >> Q[i];
  }
  sort(sorted.begin(), sorted.end());
  int64_t p_order = 0;
  int64_t q_order = 0;
  {
    set<int> p_set;
    set<int> q_set;
    for (size_t i = 0; i < N-1; ++i) {
      int p_num = P[i];
      int p_cnt = 0;
      for (int n : sorted) {
        if (p_set.count(n)) continue;
        if (n != p_num) {
          ++p_cnt;
        } else {
          break;
        }
      }
      int q_num = Q[i];
      int q_cnt = 0;
      for (int n : sorted) {
        if (q_set.count(n)) continue;
        if (n != q_num) {
          ++q_cnt;
        } else {
          break;
        }
      }
      p_order += p_cnt * nums[N - i];
      q_order += q_cnt * nums[N - i];
      p_set.insert(p_num);
      q_set.insert(q_num);
    }
  }
  cout << abs(p_order - q_order) << endl;
  
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
	ll p;
	cin >> p;
	ll a[3000];
	rep(i, p) cin >> a[i];

	for(int i = 1; i <= p - 1; i++) {
		a[i] -= a[0];
		if(a[i] < 0) a[i] += p;
	}

	vector<ll> ans;
	for(int i = p - 1; i >= 1; i--) {
		ll sum_a = 0;
		for(int j = 1; j <= p - 1; j++) {
			sum_a += a[j];
		}
		sum_a *= p - 1;
		ans.push_back(sum_a % p);
		for(int j = 1; j <= p - 1; j++) {
			a[j] = (a[j] * j) % p;
		}
	}
	ans.push_back(a[0]);
	reverse(ans.begin(), ans.end());

	for(int i = 0; i < ans.size() - 1; i++) {
		cout << ans[i] << ' ';
	}
	cout << ans[ans.size() - 1] << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ll          long long
#define mp	    make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define MOD        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))
#define rep(i,a,b)  for(int i=a;i<b;i++)
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll multbig(ll a,ll b,ll mod){
    if(a==0 or b==0) return 0;
    if(a==1 or b==1) return (a*b)%mod;
    ll cur=multbig(a,b/2,mod);
    cur=(2*cur)%mod;
    if(b%2) cur=(cur+a)%mod;
    return cur;
}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1LL) {if (k & 1LL) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = MOD){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}


#define N 	 100005
void solve(){
	int n;
	cin>>n;
	int A[n+5] = {0}, can[n+5]= {0};
	rep(i,1,n+1)
		cin>>A[i];
	int tot = 0;
	rep(i,1,n+2){
		tot += abs(A[i]-A[i-1]);
		can[i] = abs(A[i+1]-A[i-1]) -abs(A[i]-A[i-1]) -abs(A[i]-A[i+1]);
	}
	rep(i,1,n+1) cout<<tot+can[i]<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
     t =1;
//     cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 2048
n = int(input())
ans = 0
while (n > 0):
    len_n = len(str(n))
    numbers_on_that_digit = n - 10**(len_n-1)+1
    n -= numbers_on_that_digit
    if len_n % 2 == 1:
        ans+=numbers_on_that_digit

print (ans)

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

using ll = long long;

vector<ll> F(45, 0);
long fibDP(int n) {
	if(n <= 1) return F[n] = 1;
	if(F[n] != 0) return F[n];
	return F[n] = fibDP(n-1) + fibDP(n-2);
}

int main() {
	int n; cin >> n;
	cout << fibDP(n) << endl;
	return 0;
}



Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,s2;
    int i,sz,sum;

    while(cin>>s>>s2)
    {
        sum = 0;
        sz = s.size();
        for(i=0;i<sz;i++)
        {
            if(s[i]!=s2[i])
            {
                sum++;
            }
        }
        printf("%d\n",sum);
    }


   return 0;
}


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

int main(){
    int n;
    cin >> n;
    int a[n];
    int rate[9] = {0,0,0,0,0,0,0,0,0};
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i] < 400){
            rate[0]++;
        }else if(a[i] < 800){
            rate[1]++;
        }else if(a[i] < 1200){
            rate[2]++;
        }else if(a[i] < 1600){
            rate[3]++;
        }else if(a[i] < 2000){
            rate[4]++;
        }else if(a[i] < 2400){
            rate[5]++;
        }else if(a[i] < 2800){
            rate[6]++;
        }else if(a[i] < 3200){
            rate[7]++;
        }else{
            rate[8]++;
        }
    }
    int result = 0;
    for(int i=0;i<8;i++){
        if(rate[i]){
            result++;
        }
    }
    if(result != 0){
        cout << result << " " << result + rate[8] << endl;
    }else if(rate[8] <= 8){
        cout << 1 << " " << rate[8] << endl;
    }else{
        cout << 1 << " " << 8 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
static const int MAX = 200000;

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

	if (a > b){
		if (b != 1) {
			cout << "Alice" << endl;
		}
		else {
			cout << "Bob" << endl;
		}
	}
	else if (a < b) {
		if (a != 1) {
			cout << "Bob" << endl;
		}
		else {
			cout << "Alice" << endl;
		}
	}
	else if (a == b) {
		cout << "Draw" << endl;
	}

    return 0;
}

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

using ll = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;
constexpr int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

constexpr int mod = 1000000007;
struct mint
{
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    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 { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= a; }
};

mint choose2(mint n) {
    return n * (n-1) / 2;
}
istream &operator>>(istream &is, mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout << fixed << setprecision(6);
    mint n;
    cin >> n;

    mint ans = mint(10).pow(n.x) - mint(9).pow(n.x) * mint(2) + mint(8).pow(n.x);

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

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define F first
#define S second
#define endl "\n"
#define nl cout<<endl
#define pb push_back
#define f(i,a,b) for(ll i=a;i<b;i++)
#define Knucklehead ios_base::sync_with_stdio(false);cin.tie(NULL);
#define txti freopen("input.txt", "r", stdin);
#define txto freopen("output.txt", "w", stdout);
//#define mod 100000007

#define mat vector<vector<ll>>
mat cn(ll n, ll m){return vector< vector<ll> >(n, vector<ll>(m));}
bool compare(char &s1,char &s2){return s1 > s2;} 

bool sortmahstyle(const pair<ll,ll> &a,  const pair<ll,ll> &b) 
{ 
    if(a.second > b.second )
        return true;
    if( a.second==b.second && a.first > b.second )
       return true;
 
    return false;
 }
//me
ll const mod = 1e9+7;//998244353;
ll const inf = 2e5+1;

vector<ll> nodes[inf];
ll vis[inf];
ll d=0;
void dfs(ll x)
{
    vis[x]=1;
    d++;
    for(auto ch : nodes[x])
        if(vis[ch]==0)
            dfs(ch);
}
void solve()
{   
    ll n, m; cin >> n >> m;

    while(m--){
        ll u,v; cin >> u >> v;
        nodes[u].pb(v);
        nodes[v].pb(u);
    }
    ll ans = 0;
    for(ll i=1; i<=n; i++){
        if(vis[i]==0){
            dfs(i);
            ans = max(ans , d);
            d=0;
        }
    }
    cout << ans << endl;
} 

int main() {
Knucklehead 
//*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
/**/ 
        
        ll t;
        /**/t=1;
        /*/cin>>t;/**/
        f(testcases,0,t){
            solve();
        }
 
 
    return 0;
}


Measured memory_bytes: 22388
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



#if 0
const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}
#endif

#if 0
int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}
#endif

using namespace std;

const int MOD = (int) 1e9 + 7;

int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    vector <int> a(n), bef(n), tot(n);
    for(i = 0; i < n; i++) {
        cin >> a[i];
        for(j = i - 1; j >= 0; j--) {
            if(a[i] < a[j]) {
                bef[i]++;
            }
        }
    }
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            if(a[i] < a[j]) {
                tot[i]++;
            }
        }
    }

    int ans = 0;
    for(i = 0; i < n; i++) {
        ans = (ans + 1LL * k * bef[i]) % MOD;
        ans = (ans + 1LL * ((1LL * k * (k - 1) / 2) % MOD) * tot[i]) % MOD;
    }
    cout << ans;

    return 0;
}




Measured memory_bytes: 256
def quick_sort(list):
    stand=list[0]
    over=[]
    same=[]
    under=[]
    for i in list:
        if(i>stand):
            over.append(i)
        elif(i<stand):
            under.append(i)
        else:
            same.append(i)
    if(len(over)>1):
        over=quick_sort(over)
    else:
        pass
    if(len(under)>1):
        under=quick_sort(under)
    else:
        pass

    return over+same+under

N,K=map(int,input().split())
H=list(map(int,input().split()))
H=quick_sort(H)
if(N<=K):
    print(0)
else:
    print(sum(H[K:N]))

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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  ll N, A, B;
  cin >> N >> A >> B;
  if(A > B){
    cout << 0 << endl;
    return 0;
  }

  if(N==1 && A != B){
    cout << 0 << endl;
    return 0;
  }
  if(A == B){
    cout << 1 << endl;
    return 0;
  }

  if(N==2){
    cout << 1 << endl;
    return 0;
  }

  cout << (N-2) * (B - A) + 1 << endl;



  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>

#define inf  1000000007
#define ll long long
#define PA pair<int,int>
#define PPAP pair<int,PA>
#define  MP make_pair
#define  PB push_back

using namespace std;

int main(){
	int h,w;
	cin >> h >> w;
	vector<string>s(h);
	for(int i=0;i<h;i++){
		cin >> s[i];
	}
	int x=0,y=0;
	vector<vector<bool> > flag(h,vector<bool>(w));
	flag[x][y] = 1;
	bool pos=0;
	while(1){
		if(y==w-1&&x==h-1){
			flag[x][y] = 1;
			break;	
		}
		if(y==w-1){
			if(s[x+1][y]=='#'){
				x++;
				flag[x][y]=1;
			}else{
				pos = 1;
				break;
			}
		}else if(x==h-1){
			if(s[x][y+1]=='#'){
				y++;
				flag[x][y]=1;
			}else{
				pos = 1;
				break;
			}
		}else{
			if(s[x+1][y]=='#'){
				x++;
				flag[x][y] = 1;
			}else if(s[x][y+1]=='#'){
				y++;
				flag[x][y] = 1;
			}else{
				pos = 1;
				break;
			}
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(flag[i][j]!=1&&s[i][j]=='#'){
				pos = 1;
			}
		}
	}
	if(pos){
		cout << "Impossible" << endl;
	}else{
		cout << "Possible" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N , M = map(int,input().split())
con = 0
like = 0
List = []
for i in range(1,N+1):
  L = list(map(int,input().split()))
  for a in range(L[0]):
    b = L[a + 1]
    List.append(b)
for j in range(1,M + 1):
  con = 0
  for k in List:
    if k == j:
      con += 1
  if con == N:
    like += 1   
print(like)


Measured memory_bytes: 9040
def get_int_array
    gets.strip.split(' ').map(&:to_i)
end

a,b,h,m = get_int_array

dm = 6 * m
dh = 30 * h + 0.5 * m

d = (dm - dh).abs

ans = Math.sqrt(a ** 2 + b ** 2 - 2 * a * b * Math.cos(d * (Math::PI / 180)))

puts ans

Measured memory_bytes: 14660
def solve(s, t="keyence"):
    if s == t:
        return "YES"
    n = len(s)
    for i in range(n):
        for j in range(i+1,n):
            if s[:i] + s[j:] == t:
                return "YES"
    return "NO"

s = input()
print(solve(s))

Measured memory_bytes: 3060
#include <iostream>

#define endl '\n'
#define ll long long

using namespace std;

ll max(ll a, ll b) {

    if(a > b) {
        return a;
    }

    return b;
}

int main() {
    ll a, b, maior, coins;

    cin >> a >> b;

    maior = max(a, b);

    coins = 2 * maior - 1;

    if(coins < (a + b)) {
        coins = a + b;
    }

    cout << coins << endl;

    return 0;
}

Measured memory_bytes: 256
while(True):
    a,op,b = input().split()
    if op == '+':
        print(int(a)+int(b))
    elif op == '-':
        print(int(a)-int(b))
    elif op == '*':
        print(int(a)*int(b))
    elif op == '/':
        print(int(int(a)/int(b)))
    elif op == '?':
        break



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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  ll tmp;
  for(int i = 0; i < N; i++){
    cin >> A[i];
    B[i] = A[i];
  }

  set<ll> Odd, Even;
  sort(B.begin(), B.end());
  for(int i = 0; i < N; i++){
    if(i%2 == 0){
      Even.insert(B[i]);
    }else{
      Odd.insert(B[i]);
    }
  } 

  int cnt = 0;
  for(int i = 0; i < N; i++){
    if(i%2 == 0){
      if(Even.find(A[i]) == Even.end()){
        cnt++;
      }
    }else{
      if(Odd.find(A[i]) == Odd.end()){
        cnt++;
      }
    }
  }

  cout << cnt / 2 << endl;
  
  return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX

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

int main(){
	int H, W;
	cin >> H >> W;
	vector<string> mp(H);
	rep(i, H) cin >> mp[i];

	vector<string> red(mp), blue(mp);

	rep(i, H){
		red[i].resize(W);
		blue[i].resize(W);
		if (i % 2 == 0) REP(j,1, W-1) red[i][j] = '#';
		else REP(j, 1, W - 1) blue[i][j] = '#';
	}

	rep(i, H){
		red[i][0] = '#';
		blue[i][W - 1] = '#';
	}

	rep(i, H)cout << red[i] << endl;
	cout << endl;
	rep(i, H)cout << blue[i] << endl;

	return 0;
}

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000

using namespace std;

int main(){
  int h,w,ch,cw,dh,dw;cin>>h>>w>>ch>>cw>>dh>>dw;
  ch--;cw--;dh--;dw--;
  vector<string> s(h);
  rep(i, h)cin>>s[i];
  vector<vector<int>>score(h, vector<int>(w, INF));

  deque<pair<int, pi>> q;
  q.push_back({0, {ch, cw}});
  while(q.size()){
    auto c = q.front();q.pop_front();
    int cs = c.first;
    int y = c.second.first;
    int x = c.second.second;
//cout<<q.size()<<' '<<cs<<' '<<y<<' '<<x<<endl;

    if(y<0 || y>=h || x<0 || x>=w)continue;
    if(s[y][x]=='#')continue;
    if(score[y][x]<=cs)continue;

    score[y][x] = cs;

    q.push_front( {cs, {y+1, x}});
    q.push_front( {cs, {y-1, x}});
    q.push_front( {cs, {y, x+1}});
    q.push_front( {cs, {y, x-1}});
    for(int i=-2; i<=2; i++)for(int j=-2; j<=2; j++)q.push_back( {cs+1, {y+i, x+j}} );
  }

  int result = score[dh][dw];
  cout << (result==INF ? -1 : result) << endl;

  return 0;
}

Measured memory_bytes: 12516
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
const int MAXN = 1e5  + 10;
long long dp[MAXN];
long long W[120], V[120];

int main() {
	int n, w;
	cin >> n >> w;
	for (int i = 1; i <= n; i++) {
		cin >> W[i] >> V[i];
	}
	
	
	for (int j = 1; j <= n; j++) {
		for (int i = w; i >= 0; i--) {
			if (i - W[j] >= 0) {
				dp[i] = max(dp[i], dp[i - W[j]] + V[j]); 
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i <= w; i++) {
	
		ans = max(ans, dp[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 110;
const ll mod = 1e9 + 7;
ll dp[maxn][5][5][5], n;
// 0 is empty character

bool check_state(int f, int s, int t) {
    string ss = "";
    ss += char(f+'a');
    ss += char(s+'a');
    ss += char(t+'a');
    return (ss != "bcd") && (ss != "cbd") && (ss != "bdc");
}

bool check2(int f, int s, int t) {
    string ss = "";
    ss += char(f+'a');
    ss += char(s+'a');
    ss += char(t+'a');
    return (ss != "bcd");
}

int main() {
    cin>>n;

    dp[0][0][0][0] = 1LL;

    for(int i=0;i<n;i++) {
        for(int f=0;f<5;f++) {
            for(int s=0;s<5;s++) {
                for(int l=0;l<5;l++) {
                    if(dp[i][f][s][l] == 0) continue;
                    for(int d=1;d<=4;d++) {
                        // extend with character D
                        if(check_state(s,l,d) && check2(f,s,d) && check2(f, l, d) && check2(l, s, d)) {
                            dp[i+1][s][l][d] += dp[i][f][s][l];
                            dp[i+1][s][l][d] %= mod;
                        }
                    }
                }
            }
        }
    }

    ll result = 0LL;
    for(int f=1;f<=4;f++) {
        for(int s=1;s<=4;s++) {
            for(int l=1;l<=4;l++) {
                result += dp[n][f][s][l];
                result %= mod;
            }
        }
    }
    cout<<result<<"\n";
    return 0;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define INF LONG_LONG_MAX
#define MOD 1000000007
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;

int n;
set<int> s;
bool f = true;

signed main() {
    cin >> n;
    rep(i,n) {
        int a;
        cin >> a;
        if (s.count(a)) f = false;
        s.insert(a);
    }
    cout << (f ? "YES" : "NO") << endl;
}




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

using namespace std;
typedef long long ll;
const int N=3500;
char s[N],t[N],ans[N];
ll a[N][N],n,m,i,j,cnt=0;
int main(){
	cin>>s>>t;
	n=strlen(s); m=strlen(t);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(s[i-1]==t[j-1]) a[i][j]=a[i-1][j-1]+1;
			else a[i][j]=max(a[i][j-1],a[i-1][j]);
		}
	}
	i=n;j=m;
	if(a[i][j]==0){
		cout<<" ";
		return 0;
	}
	for(;;){
		if(s[i-1]==t[j-1]){
			ans[cnt++]=t[j-1];
			--i;--j;
		}
		else{
			if(a[i][j]==a[i-1][j]) --i;
			else j--;
		}
		if(i==0||j==0) break;
	}
	for(i=cnt-1;i>=0;i--) cout<<ans[i];
}

Measured memory_bytes: 84224
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

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

class Solve {
public:
	Solve() {};
	~Solve() {};

	void solver() {
		std::vector<int> results;
		while (1) {
			int n;
			std::cin >> n;
			if (!n) break;

			std::array<char, 3600 * 24 + 60 * 60 + 60 + 1> times = {0};
			std::string str;
			rep(i, n) {
				int leave, arrive;
				std::cin >> str;
				leave = std::stoi(str.substr(6, 2)) + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(0, 2)) * 3600;
				std::cin >> str;
				arrive = std::stoi(str.substr(6, 2)) + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(0, 2)) * 3600;

				//????????§??°??°+1, ??°?????§-1
				times[leave]++;
				times[arrive]--;
			}
			int max = 0;
			int now = 0;
			for (auto& x : times) {
				now += x;
				if (max < now) max = now;
				if (now < 0) now = 0;
			}
			results.push_back(max);
		}
		for (auto& x : results) {
			std::cout << x << std::endl;
		}
	}
private:
};

int main() {
	Solve solve;
	solve.solver();
	getchar(); getchar();
	return 0;
}

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

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

string in;
int L, temp, N;
const int kInf = 1<<30;
vector<int> v;
double dp[1<<15][15];

double rec(int S, int pv) {
  // printf("%d : %d\n", S, pv);
  if (S == (1<<N)-1) return v[pv];
  double &d= dp[S][pv];
  if (d >= 0) return d;
  
  double ret = kInf;
  for (int i = 0; i < N; ++i) {
    if (!(S >> i & 1)) {
      ret = min(ret, 2 * sqrt(v[pv] * v[i]) + rec(S|1<<i, i));
    }
  }
  return d = ret;
}

int main() {
  while (getline(cin, in)) {
    // input
    istringstream is(in);
    is >> L;
    v.clear();
    while (is >> temp) v.push_back(temp);
    N = v.size();
    double ans = kInf;
    rep(i,N) {
      memset(dp, -1, sizeof dp);
      ans = min(ans, v[i] + rec(1<<i, i));
    }
    // printf("%lf :", ans);
    printf("%s\n", (L >= ans) ? "OK" : "NA" );
    
  }
  return 0;
}

Measured memory_bytes: 0
#import"bits/stdc++.h"
#define r(i,n) for(i=0;i<n;i++)
using namespace std;main(int N){cin>>N;int A[2*N],c[N+1]={},n,t,i;r(i,2*N)cin>>A[i];r(i,2*N)c[A[i]]++;if(*max_element(c,c+N+1)>N)cout<<"No";else{cout<<"Yes ";queue<int> s;r(i,N)if(A[i]==A[N+i])s.push(i);while(!s.empty()){n=s.front(),t=N+rand()%N;s.pop();if(A[n]!=A[t]&A[t-N]!=A[n+N])swap(A[n+N],A[t]);else s.push(n);}r(i,N)cout<<A[i+N]<<" ";}}

Measured memory_bytes: 6800
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", ans);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	ll x, y;
	cin >> x >> y;

	int ans = 0;
	while (x <= y) {
		x *= 2;
		ans++;
	}

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

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int a, b, c, i;
  scanf ("%d %d %d", &a, &b, &c);
  for ( i = 0 ; a <= b ; a++ ){
    if ( c % a == 0 ) i++ ;
  }
  printf ("%d\n", i);
  return 0;
}



Measured memory_bytes: 2100