akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cstring>

//isprimeðìÁÄ­êéÖ
int* prime(int num){
	std::vector<int> v;
	int* res = new int[num+1];
	memset(res, 0, sizeof(res));
	res[2] = 1;
	v.push_back(2);

	bool f;
	for(int i=3;i<=num;i+=2){
		f = true;
		for(int j=0;v[j]*v[j]<=i;j++){
			if(i % v[j] == 0){f=false;break;}
		}
		if(f){v.push_back(i),res[i] = 1;}
	}

	return res;
}

int main(){
	int* isprime = prime(50000);

	int n, res = 0;
	while(std::cin >> n, n){
		res = 0;
		for(int i=2;i<=n/2;i++){
			if(isprime[i] && isprime[n-i])res++;
		}
		std::cout << res << std::endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
function Main(input) {
	const n = input.split("\n")[0]
	const ar = input.split("\n")[1].split(" ")
	ar2 = ar.filter((num, i)=> {
        return num % 2 === 0 ? false : (i + 1) % 2 === 0 ? false : true;
    })
    console.log(ar2.length);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29668
#include<stdio.h>
int main(){
  	int a,b;
	scanf("%d %d",&a,&b);
  	if(a*b==15){
      	printf("*");
    }else if(a+b==15){
      	printf("+");
    }else{
      	printf("x");
    }
  	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(void) {
  int n, ans=0, d=1;
  scanf("%d", &n);
  for (int i=0; i<3; i++) {
    if (n%10 == 1) {
      ans += 9*d;
    }else {
      ans += d;
    }
    d *= 10;
    n /= 10;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e4+23;

int hd[maxn],e[maxn],nxt[maxn],v[maxn],d[1000];

int n,m,cnt;
bool vis[1000];

void add(int x,int y,int z)
{
    v[++cnt]=z,e[cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt;
}
void dijkstra(int s)
{
    priority_queue<pair<int,int>> q;
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    q.push({0,s});d[s]=0;
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=hd[x];i;i=nxt[i]){
            int y=e[i],z=v[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push({-d[y],y});
            }
        }
    }
}

char s[30][30];

int cal(int i,int j)
{
    return i*m+j;
}

int main()
{
    for(int i=0;i<30;i++){
        for(int j=0;j<30;j++) s[i][j]='#';
    }
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1),s[i][m+1]='#';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#') continue;
            if(s[i][j+1]!='#') add(cal(i,j),cal(i,j+1),1);
            if(s[i][j-1]!='#') add(cal(i,j),cal(i,j-1),1);
            if(s[i+1][j]!='#') add(cal(i,j),cal(i+1,j),1);
            if(s[i-1][j]!='#') add(cal(i,j),cal(i-1,j),1);
        }
    }
    int mx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dijkstra(cal(i,j));
            for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++) if(d[cal(i,j)]<1e9)mx=max(mx,d[cal(i,j)]);
            }
        }
    }
    cout<<mx;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <limits>
#include <cmath>
#include <cassert>

using namespace std;
using ll = long long;

const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n, n)
    {
        int table[21][21] = {};
        for(int i = 0; i < n; i++)
        {
            int x, y; cin >> x >> y;
            table[y][x] = 1;
        }
        int m; cin >> m;
        int nx = 10, ny = 10;
        int cnt = 0;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        int k = -1;
        for(int i = 0; i < m; i++)
        {
            char dir; int num; cin >> dir >> num;
            if(dir == 'N') k = 0;
            if(dir == 'E') k = 1;
            if(dir == 'S') k = 2;
            if(dir == 'W') k = 3;
            while(num--)
            {
                ny += dy[k];
                nx += dx[k];
                if(table[ny][nx])
                {
                    cnt++;
                    table[ny][nx] = 0;
                }
            }
        }
        if(cnt == n) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}




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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    ll t = stol(s);
    vector<int> v(n);
    rep(i,n){
        v[i] = t%10;
        t /= 10;
    }
    reverse(v.begin(),v.end());
    int ans = 1000,num = 0;
    rep(i,n-2){
        num = v[i]*100 + v[i+1]*10 + v[i+2];
        ans = min(ans,abs(num-753));
    }
    cout << ans << endl;
}

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

main(){
  int n,m,v;
  while(scanf("%d%d",&n,&m),n+m){
    int a[110]={0},h=0,w=0;
    while(n--){
      scanf("%d",&v);
      h = max(h,++a[v/m]);
      w = max(w,v/m);
    }
    double res = 0.01;n=w;
    while(w--)res+=(double)a[w]/h*(double)(n-w)/n;
    printf("%.9lf\n",res);
  }
}

Measured memory_bytes: 1068
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<cmath>

using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::make_pair;
using std::vector;
using std::queue;
using std::deque;
using std::priority_queue;
using std::next_permutation;
//using std::iota;
using std::sort;
using std::greater;
using std::max;
using std::min;
using std::log;

using lli = long long int;
using ulli = unsigned long long int;

#define INF 999999999;
#define MOD 1000000007;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

string S;
int K, N;
char s[3] = {'a', 'b', 'c'};

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

	cin >> N >> K;
	cin >> S;
	S[K-1] = s[S[K-1]-'A'];

	cout << S;

	return 0;
}

/*
int N, K, t=1;
double a=1.0;
double c = 2.0;

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

	cin >> N >> K;
	const double kk = log((double)K);

	double z;
	double r = modf(kk/log(2), &z);
	if(r != 0)z++;
	a -= (1-pow(0.5, z))/N;
	dbug(a)dbugln;
	for(double i = min((double)K-1.0, (double)N); i > 1.0; i-=1.0){
		double cm = kk / log(i);
		if(cm <= c)t++;
		else{
			a -= (1 - pow(0.5, c))*t/(double)N;
			dbug(a)dbug(c)dbug(t)dbugln;
			t=1;
			c+=1.0;
		}
	}
	if(t > 1)a -= (1 - pow(0.5, c))*t/(double)N;
	cout << a;
	return 0;
}
*/


Measured memory_bytes: 256
#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    for start in range(N):
        # ループを探索
        now = start
        cycle = []
        total = 0
        for _ in [0] * N:  # while Trueでもおｋ
            now = P[now]
            cycle.append(C[now])
            total += C[now]
            if now == start:
                break
        # 最大スコアを探索
        length = len(cycle)
        score = 0
        for move in range(length):
            score += cycle[move]
            # 移動回数 >= Kなら，ループ途中でも探索終了
            if move >= K:
                break
            # ループを周回するので，それを利用して探索を省略
            res = score
            if total > 0:
                laps = (K - (move + 1)) // length
                res += total * laps
            ans = max(ans, res)

    print(ans)


if __name__ == '__main__':
    main()


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

int n,s[5][105],x,ans;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=2;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&x);
            s[i][j]=s[i][j-1]+x;
        }          
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,s[1][i]+s[2][n]-s[2][i-1]);
    }
    printf("%d\n",ans);
    return 0;
}

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

#define _rep4(i,p,n,k) for(int i=(p),_rep##_bound=(n),_rep##_inc=(k);i<_rep##_bound;i+=_rep##_inc)
#define _rep3(i,p,n,_a) _rep4(i,p,n,1)
#define _rep2(i,n,_a,_b) _rep4(i,0,n,1)
#define _repcall(a,b,c,d,name,...) name(a,b,c,d)
#define rep(...) _repcall(__VA_ARGS__,_rep4,_rep3,_rep2)

int work(std::istream &in) {
    int A, B, C, X, Y;
    in >> A >> B >> C >> X >> Y;
    int ret = INT_MAX;
    rep(c, std::max(X, Y) + 1) {
        int a = X - c;
        int b = Y - c;
        a = std::max(0, a);
        b = std::max(0, b);
        int cost = a * A + b * B + 2 * c * C;
        ret = std::min(ret, cost);
    }
    return ret;
}

int runTest() {
    int ret = 0;

    struct testcase {
        const char *input;
        int expected;
    };

    struct testcase testdata[] = {
        { "1500 2000 1600 3 2", 7900 },
        { "1500 2000 1900 3 2", 8500 },
        { "1500 2000 500 90000 100000", 100000000 },
    };

    for (const auto &t : testdata) {
        auto in = std::stringstream(t.input);
        int actual = work(in);
        if (actual != t.expected) {
            fprintf(stderr, "expected %d, but actual %d\n", t.expected, actual);
            ret = 1;
        }
    }

    return ret;
}

int main(int argc, char *argv[]) {
    if (argc == 2 && strcmp("--test", argv[1]) == 0) {
        return runTest();
    }
    printf("%d\n", work(std::cin));
    return 0;
}


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

int main(){
    ll n;
    cin >> n;

    ll max1 = 0;
    ll cur1 = 0;
    REP(i, n){
        ll a;
        cin >> a;
        if(a == 0){
            cur1 = 0;
        }else{
            cur1++;
        }
        max1 = max(max1, cur1);
    }

    cout << max1 + 1 << endl;
    return 0;
}



Measured memory_bytes: 3124
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int n;
  vector<int> f;
  cin >> n;
  int a = n;
  for (int i = 2; i * i <= n; i++)
    while (a % i == 0) {
      f.push_back(i);
      a /= i;
    }
  if (a != 1) f.push_back(a);
  cout << n << ':';
  for (int& e: f)
    cout << ' ' << e;
  cout << endl;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
  int n,m;  
  cin >> n >> m;
  for(int i = 0;i<m;i++)
  {
      int a;
      cin >> a;
      n-=a;
  }
  if(n>=0) cout << n << endl;
  else cout << -1<<endl;
  return 0;
}



Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <sstream>
using namespace std;

int n, m;
string cand[22];
vector<string> words;

vector<int> match[82];
int matchBit[82];

vector<char> ansKey;
int ansFlg;

bool matches(string a, string b){
  if(a.size() != b.size()) return false;
  char trans[128];
  memset(trans, -1, sizeof(trans));
  for(int i = 0; i < a.size(); i++){
    if(trans[a[i]] != -1 && b[i] != trans[a[i]]) return false;
    if(trans[b[i]] != -1 && a[i] != trans[b[i]]) return false;
    trans[a[i]] = b[i];
    trans[b[i]] = a[i];
  }
  return true;
}

bool mycmp(const string &a, const string &b){
  set<char> st1;
  for(int i = 0; i < a.size(); i++) st1.insert(a[i]);
  set<char> st2;
  for(int i = 0; i < b.size(); i++) st2.insert(b[i]);

  return st1.size() > st2.size();
}

bool setKey(const string &a, const string &b, vector<char> &key){
  for(int i = 0; i < a.size(); i++){
    if(key[a[i]] != -1 && key[a[i]] != b[i] ||
       key[b[i]] != -1 && key[b[i]] != a[i]){
      return false;
    }
    key[a[i]] = b[i];
    key[b[i]] = a[i];
  }
  return true;
}

void dfs(int idx, int used, vector<char> key){
  if(idx == m){
    if(ansFlg == 1){
      ansFlg = -1;
    }
    else{
      ansFlg = 1;
      ansKey = key;
    }
    return;
  }

  for(int i = 0; i < match[idx].size(); i++){
    int j = match[idx][i];
    if(used & (1 << j)) continue;

    vector<char> nextKey = key;
    if(setKey(words[idx], cand[j], nextKey)){
      dfs(idx + 1, used | (1 << j), nextKey);
      if(ansFlg == -1) return;
    }
  }
}

void solve(){
  sort(words.begin(), words.end(), mycmp);

  for(int i = 0; i < m; i++){
    match[i].clear();
    matchBit[i] = 0;

    for(int j = 0; j < n; j++){
      if(matches(words[i], cand[j])){
        match[i].push_back(j);
        matchBit[i] |= (1 << j);
      }
    }
  }

  vector<char> key(128, -1);
  ansFlg = 0;
  dfs(0, 0, key);
}

int main(){
  while(cin >> n, n){
    for(int i = 0; i < n; i++){
      cin >> cand[i];

      for(int j = 0; j < i; j++){
        if(cand[j] == cand[i]){
          i--;
          n--;
          break;
        }
      }
    }

    string s;
    getline(cin, s);
    getline(cin, s);
    for(int i = 0; i < s.size(); i++) if(s[i] == '.') s[i] = ' ';

    vector<string> raw;
    stringstream ss(s);
    words.clear();

    while(ss >> s){
      raw.push_back(s);

      bool pushFlg = true;
      for(int i = 0; i < words.size(); i++){
        if(words[i] == s){
          pushFlg = false;
          break;
        }
      }
      if(pushFlg) words.push_back(s);
    }
    m = words.size();

    solve();

    if(ansFlg == 1){
      for(int i = 0; i < raw.size(); i++){
        if(i != 0) cout << " ";
        for(int j = 0; j < raw[i].size(); j++){
          cout << ansKey[raw[i][j]];
        }
      }
      cout << "." << endl;
    }
    else{
      cout << "-." << endl;
    }
  }
}

Measured memory_bytes: 1272
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    cnt = 0

    for i in range(N):
        if a[i] % 2 == 0 and (a[i] % 3 == 0 or a[i] % 5 == 0):
            cnt += 1
        elif a[i] % 2 == 1:
            cnt += 1

    if cnt == N:
        print('APPROVED')
    else:
        print('DENIED')


if __name__ == '__main__':
    main()


Measured memory_bytes: 39992
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
  vector<int> v;
  int n,k,ans=0;
  
  cin >> n >> k;
  for (int i=0; i<n; i++){
    int t;
    cin >> t;
    v.push_back(t);
    ans+=t;
  }
  sort(v.begin(), v.end());
  for (int i=0; i<n-k; i++){
    ans -= v[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a;
    cin>>a;
    if(int(a.find('C'))!=-1&&int(a.rfind('F'))!=-1&&a.find('C')<a.rfind('F'))//个人码风问题，习惯用and而不是&&
        cout<<"Yes";
    else
        cout<<"No";
        return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define rep(i,n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main(){
	int n;
	string s;
	while(cin>>n&&n){
		int dice[6],cnt=1,t;
		for(int i=0;i<6;i++)dice[i]=i+1;
		while(n--){
			cin>>s;
			if(s=="North"){
				t=dice[0];
				dice[0]=dice[1];
				dice[1]=dice[5];
				dice[5]=dice[4];
				dice[4]=t;
			}else if(s=="East"){
				t=dice[0];
				dice[0]=dice[3];
				dice[3]=dice[5];
				dice[5]=dice[2];
				dice[2]=t;
			}else if(s=="West"){
				t=dice[0];
				dice[0]=dice[2];
				dice[2]=dice[5];
				dice[5]=dice[3];
				dice[3]=t;
			}else if(s=="South"){
				t=dice[0];
				dice[0]=dice[4];
				dice[4]=dice[5];
				dice[5]=dice[1];
				dice[1]=t;
			}else if(s=="Right"){
				t=dice[1];
				dice[1]=dice[2];
				dice[2]=dice[4];
				dice[4]=dice[3];
				dice[3]=t;
			}else{
				t=dice[1];
				dice[1]=dice[3];
				dice[3]=dice[4];
				dice[4]=dice[2];
				dice[2]=t;
			}
			cnt+=dice[0];
		}
		cout<<cnt<<endl;
	}
}

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

using namespace std;

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

void dfs(const vector<string> &S, int H, int W, int i, int j, vector<vector<bool>> &visited, long long &black, long long &white)
{
	if (visited[i][j]) {
		return;
	}
	visited[i][j] = true;

	if (S[i][j] == '#') ++black;
	if (S[i][j] == '.') ++white;
	
	for (int k = 0; k < 4; ++k) {
		int y = i + dy[k];
		int x = j + dx[k];
		if (y < 0 || H <= y || x < 0 || W <= x) {
			continue;
		}
		if ((S[i][j] == '#' && S[y][x] == '.') || (S[i][j] == '.' && S[y][x] == '#')) {
			dfs(S, H, W, y, x, visited, black, white);
		}
	}
}

int main()
{
	int H, W;
	cin >> H >> W;

	vector<string> S(H);
	for (auto &x : S) {
		cin >> x;
	}
	vector<vector<bool>> visited(H, vector<bool>(W, false));
	long long ans = 0;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			if (S[i][j] == '#') {
				long long black = 0;
				long long white = 0;
				dfs(S, H, W, i, j, visited, black, white);
				ans += black * white;
			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 20480
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> numbers = new ArrayList<Integer>();
		int N = sc.nextInt();
		int X = sc.nextInt();
		for(int i = 0;i<N;i++){
			int j = sc.nextInt();
			numbers.add(j);
			X -= j;
		}
		Collections.sort(numbers);
		System.out.println(X/numbers.get(0)+N);
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){

  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,pm[10010],pe[10010],pj[10010];
  int ps[10010];
  
  while(1){
    cin>>n;
    if(n==0) break;
    
    for(int i=0; i<n; i++){
      cin>>pm[i]>>pe[i]>>pj[i];
      ps[i]=pm[i]+pe[i]+pj[i];
      
      if(pm[i]==100 || pe[i]==100 || pj[i]==100){
	cout<<"A"<<'\n';
	
    }else if((pm[i]+pe[i])/2>=90){
	cout<<"A"<<'\n';
	
      }else if(ps[i]/3>=80){
	cout<<"A"<<'\n';
	
      }else if(ps[i]/3>=70){
	cout<<"B"<<'\n';
	
      }else if(ps[i]/3>=50 && pm[i]>=80 || pe[i]>=80){
	cout<<"B"<<'\n';
	
      }else{
	cout<<"C"<<'\n';
      }
    }
  }
  return 0;
}



Measured memory_bytes: 2972
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int main(){
  int n;
  string s;
  cin >> n >> s;

  int max_c = 0;
  for(int i = 0; i < n; i++){
    string a = s.substr(0, i);
    string b = s.substr(i);
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    int tmp_cnt = 0;
    for(char c : a) {
      auto itr = b.find(c);
      if(itr != std::string::npos) {
        tmp_cnt++;
      }
    }
    max_c = max(max_c, tmp_cnt);
  }

  cout << max_c << endl;
  return 0;

}


Measured memory_bytes: 3544
s=input()[::-1]
t=['maerd','remaerd','esare','resare']
i=0
while i<len(s):
  if s[i:i+5]==t[0] or s[i:i+5]==t[2]:
    i+=5
  elif s[i:i+6]==t[3]:
    i+=6
  elif s[i:i+7]==t[1]:
    i+=7
  else:
    print('NO')
    break
else:
  print('YES')

Measured memory_bytes: 3188
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

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

signed main(){
    string s;
    cin >> s;
    int n = s.length();

    if(s[0] == '0' || s[n-1] == '1'){
        cout << -1 << endl;
        return 0;
    }

    vector<bool> len(n, false);
    for(int i = 1; i <= n / 2; i++){
        if(s[i] != s[n-i-2]){
            cout << -1 << endl;
            return 0;
        }
        if(s[i] == '1'){
            len[i+1] = true;
        }
    }

    vector<P> ans;
    int parent = 2;
    ans.emplace_back(1, 2);
    int v = 3;
    for(int i = 2; i <= n / 2; i++){
        ans.emplace_back(parent, v);
        if(not len[i]){
            v++;
            continue;
        }
        parent = v;
        v++;
    }
    for(; v <= n; v++){
        ans.emplace_back(parent, v);
    }

    rep(i, n-1){
        cout << ans[i].first << " " << ans[i].second << endl;
    }

    return 0;
}


Measured memory_bytes: 3312
#include <iostream>
#include <array>

int main()
{
  std::array<int, 5> coordinates;
  int k;
  for(int i = 0; i < 5; ++i){
	std::cin >> coordinates[i];
  }
  std::cin >> k;
  
  for(int i = 0; i < 5; ++i){
    for(int j = i + 1; j < 5; ++j){
		if(coordinates[j] - coordinates[i] > k){
			std::cout << ":(";
          	return 0;
        }
    }
  }
  std::cout << "Yay!";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int ans=1;
    while(ans<=n){
        ans*=2;
    }
    cout << ans/2;
    
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

mi = INF
for i in range(1, 10**6 + 1):
 	if is_integer_num(N/i):
 		if mi > i + N//i:
	 		mi = i + N//i

print(mi - 2)

Measured memory_bytes: 62952
#O(2n)程度を見込む解答
s=input()
k=int(input())
ss=s+s
n=len(s)

ppp=1
for i in range(n-1):
	if s[i]!=s[i+1]:
		ppp=0
		break
		
if ppp==1:
	print(n*k//2)
else:		
	counts=0
	i=0
	while i<n-1:
		if s[i]!=s[i+1]:
			i+=1
		else:
			i+=2
			counts+=1
			
	countss=0
	i=0
	while i<n*2-1:
		if ss[i]!=ss[i+1]:
			i+=1
		else:
			i+=2
			countss+=1
			
	if countss==counts*2:
		print(counts*k)
	else:
		print(counts*k+k-1)

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

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++) cin >> a[i];
    int cnt,m=1e9;
    for(int i=0; i<N; i++){
        cnt=0;
        while(1){
            if(a[i]%2==0){
                cnt++;
                a[i] /= 2;
            }
            else{
                break;
            }
        }
        if(cnt<m) m=cnt;
    }
    cout << m << endl;
}


Measured memory_bytes: 256
#include<stdio.h>

int F[100];

int fibonacci(int n){
  if(n==0 || n==1){
    F[n] = 1;
    return F[n];
  }
  if(F[n] != 0)
    return F[n];
      
  F[n] = fibonacci(n-2) + fibonacci(n-1);
  return F[n];
}
int main(void){
  
  int i,n;
  
  for(i=0;i<100;i++) F[i]=0;
  
  scanf("%d",&n);
  
  printf("%d\n",fibonacci(n));
  
  return 0;
}

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

using namespace std;

#define INF 1000000007
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define maxn 15

signed main()
{
    int N, K;
    cin >> N >> K;
    double ans = 0;
    for (int i = 1; i <= N; i++)
    {
        double x = 0;
        if (i < K)
        {
            x = ceil(log2((double)(K) / (double)i));
        }
        double a = (double)1 / (double)N * (double)pow((double)0.5, (double)x);
        ans += a;
    }
    cout << fixed << setprecision(12) << ans << endl;
}


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

//#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    int amt = min(a, k);
    a -= amt;
    k -= amt;
    int sum = amt;
    amt = min(b, k);
    k -= amt;
    amt = min(c, k);
    sum -= amt;
    cout << sum << '\n';
}
/*

 */

Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

int main(){

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

    ll a, b, c, d; cin >> a >> b >> c >> d;

    while(true){
        // takahashi
        c -= b;
        if(c <= 0){
            cout << "Yes" << endl;
            return 0;
        }

        // aoki
        a -= d;
        if(a <= 0){
            cout << "No" << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctype.h>
#include <map>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <cctype>
#include <queue>
#include <set>
#define PI 3.14159265359
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP1(j,n) for(int j=0;j<(int)n;++j)
#define REPD(i,n) for(int i=n;i>=0;--i)
#define REPD1(j,n) for(int j=n;j=>0;--j)
#define REPS(i,n) for(int i=1;i<=(int)n;++i)
#define REPS1(j,n) for(int j=1;j<=(int)n;++j)
#define rep(i,a,n) for(int i=a;i<=(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

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

int main(void) {
	int a;
	cin >> a;
	cout << a * a * a << endl;
	return 0;
}

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

int main(){
	long long int n;
	cin >> n;
	long long int min=1e18; 
	for(long long i=1;i<=sqrt(n);i++){
		if(n%i==0){
			if(i+n/i-2<min)
			 min = i + n/i -2;
		}
		
	}
   cout <<min;
	
}

Measured memory_bytes: 256
#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	S = list(input())
	Dans = defaultdict(int)
	L = [[0] * 10 for i in range(N)]
	R = [[0] * 10 for i in range(N)]
	#L
	L[0][int(S[0])] = 1
	for i in range(1, N):
		for j in range(10):
			L[i][j] = L[i - 1][j]
		L[i][int(S[i])] = 1
	#R
	R[N - 1][int(S[N - 1])] = 1
	for i in range(1, N):
		for j in range(10):
			R[N - 1 - i][j] = R[N - i][j]
		R[N - 1 - i][int(S[N - 1 - i])] = 1

	for i in range(1, N - 1):
		for j in range(10):
			for k in range(10):
				if L[i - 1][j] == 1 and R[i + 1][k] == 1:
					x = str(j) + S[i] + str(k)
					Dans[x] = 1

	ans = len(Dans)
	print(ans)

if __name__ == '__main__':
	main()

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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

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

const ll MOD = 1e+9 + 7;

int main() {
    ll N;
    cin >> N;
    
    vector<vector<ll>> dp(4,vector<ll>(N,0));
    dp[0][0] = 8;
    dp[1][0] = 1;
    dp[2][0] = 1;
    
    for ( int i = 0; i < N-1; ++i){
        dp[0][i+1] = ( 8 * dp[0][i] ) % MOD;
        dp[1][i+1] = ( dp[0][i] + 9 * dp[1][i] ) % MOD;
        dp[2][i+1] = ( dp[0][i] + 9 * dp[2][i] ) % MOD;
        dp[3][i+1] = ( dp[1][i] + dp[2][i] + 10 * dp[3][i] ) % MOD;
    }
    
    ll ans = dp[3][N-1];
    ans %= MOD;
    if ( ans < 0 ) ans += MOD;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 42100
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int j,a[102],k=0,l=0,cnt=0,x;
    map<int,int>m;
   int n;
   double i;
    cin>>n;
    j=n/2;
    i=(double)j;
    if(n%2==1){

        printf("%.10lf\n",(i+1)/n);
    }
    else{
        printf("%.10lf\n",i/n);
    }


}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	vector<int> h;
	h.resize(n);
	vector<int> pre;
	pre.resize(n);
	int i;
	for(i=0;i<n;i++)
		cin>>h[i];
	pre[n-1]=1;
	int ans = 1;
	for(i=n-2;i>=0;i--)
	{
		if(h[i]>=h[i+1])
			pre[i] = pre[i+1]+1;
		else
			pre[i] = 1;
		ans = max(ans,pre[i]);
	}
	cout<<ans-1<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using M = map<int, int>;
ll INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  int n, m;
  cin >> n >> m;
  int g[n][n] = {};
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a][b] = 1;
    g[b][a] = 1;
  }

  vector<int> v(n);
  rep(i, n) v[i] = i;

  int ans = 0;

  do {
    bool is_ok = true;
    rep(i, n-1) {
      if (g[v[i]][v[i+1]] == 0) {
        is_ok = false;
        break;
      }
    }

    if (is_ok) ans++;

  } while(next_permutation(v.begin() + 1, v.begin() + n));

  cout << ans << endl;



  return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

ll a[100010];
signed main(void)
{
	int n;
	cin >> n;
	REP(i, n) {
		cin >> a[i];
	}

	ll b = 0, ret = 0;
	bool c = true;
	REP(i, n) {
		b += a[i];
		if(c && b > 0) {
			ret += b+1;
			b = -1;
		} else if(!c && b < 0) {
			ret += abs(b)+1;
			b = 1;
		} else if(b == 0) {
			if(c) {b = -1; ret++;}
			else {b = 1; ret++;}
		}
		c = !c;
	}
	//if(b == 0) ret++;

	ll ans = ret;
	ret = 0;
	b = 0;
	c = false;
	REP(i, n) {
		b += a[i];
		if(c && b > 0) {
			ret += b+1;
			b = -1;
		} else if(!c && b < 0) {
			ret += abs(b)+1;
			b = 1;
		} else if(b == 0) {
			if(c) {b = -1; ret++;}
			else {b = 1; ret++;}
		}
		c = !c;
	}
	//cout << ans << " " << ret << endl;
	cout << min(ans, ret) << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>

using namespace std;
#define int long long

signed main(){

   int N, K;
   cin>> N>> K;
   int a[N];
   for(int i=0; i<N; i++) cin>> a[i];

   int s[N+1]={0};
   int t[N+1]={0};
   for(int i=0; i<N; i++){
      s[i+1]+=(s[i]+a[i]);
      t[i+1]+=(t[i]+max<int>(0, a[i]));
   }

   int z=0;
   for(int i=0; i+K<=N; i++){
      int ikd=max<int>(s[i+K]-s[i], 0);
      int kdi=(t[i]-t[0])+(t[N]-t[i+K]);
      z=max(z, ikd+kdi);
   }

   cout<< z<< endl;

   return 0;
}


Measured memory_bytes: 2560
import sys
import itertools
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, X, Y = map(int, input().split())

ans = []

cnt = [0] * (N+1)
for a, b in itertools.combinations(range(1, N + 1), 2):
    d1 = b - a
    d2 = abs(X - a) + abs(Y - b) + 1

    d = min(d1, d2)

    cnt[d] += 1

for i in range(1, N):
    print(cnt[i])


Measured memory_bytes: 3444
#include<iostream>
#include<cmath>
#include<cassert>
using namespace std;
  
int calc(int);
long long cnt;
int X;
void insertionSort(int A[],int n,int g){
  int v,j;
  for(int i=g;i<n;i++){
    v=A[i];
    j=i-g;
    while(j>=0&&A[j]>v){
      A[j+g]=A[j];
      j=j-g;
      cnt++;
    }
    A[j+g]=v;
  }
}
 
int Gt[1000000],gt=0;
int  G[1000000], g=0;
 
void shellSort(int A[],int n){
  
 
  int Z =pow(n,1.5),flg,y;
  X=n;
  cnt=0;
 
  for(int i=n;i>=1;i--){
    if(n%i==0){
      Gt[gt++]=i;
      //cout<<i<<" - "<<endl;
    }else{
      if(i*i<=n&&n<=(i+1)*(i+1))Gt[gt++]=y=i;
    }
  }
   
  for(int i=0;i<gt;i++){
    if(i%2==1||i==y){
    
      G[g++]=Gt[i];
    }
  }
  G[g++]=1;
   
  int ng;
  while(1){
    if(g<100)break;
    ng=0;
    for(int i=0;i<g;i++){
      if(i==y||i%2==1){
    G[ng++]=G[i];
      }
    }
    g=ng;
  }
  for(int i=0;i<g;i++){
    insertionSort(A, n,G[i]);
  }
   
  cout<<g<<endl;
  for(int i=0;i<g;i++){
    if(i)cout<<' ';
    cout<<G[i];
  }
  cout<<endl;
  cout<<cnt<<endl;
   
  assert(g<100);
  assert(cnt<Z);
  //cout<<cnt<<" cnt"<<endl;
  //cout<<Z<<" Z"<<endl;
  //cout<<(int)pow(n,1.5)<<endl;
}
  
  
int main(){
  
  int n;
  int A[1000000];
  
  cin>>n;
  for(int i=0;i<n;i++)cin>>A[i];
    
    
  shellSort(A,n);
  
  for(int i=0;i<n;i++){
    cout<<A[i]<<endl;
  }
  
  return 0;
}
  
int calc(int n){
  for(int i=sqrt(n);i>=0;i--){
    if(n%i==0)return n/i;
  }
}



Measured memory_bytes: 7156
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;

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

template <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };

using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T &data, vector<int> &iter)
{
  cout << data << " ";
}
template <typename T>
void dump(const vector<T> &data, vector<int> &iter)
{
  for (auto elem : data)
    dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>> &data, vector<int> &iter)
{
  for (auto elem : iter)
  {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++)
  {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T> &data, int dummy)
{
  for (int i = 0; i < data.size(); i++)
  {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T &data)
{ // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////

class UnionFind
{
public:
  vector<int> parent;
  vector<LL> cnt;
  UnionFind(int n)
  {
    parent = vector<int>(n);
    cnt = vector<LL>(n, 1);
    for (int i = 0; i < n; i++)
      parent[i] = i;
  }
  int find(int v)
  {
    if (v == parent[v])
      return v;
    return parent[v] = find(parent[v]);
  }

  int uni(int u, int v)
  {
    u = find(u);
    v = find(v);
    if (u == v)
      return false;
    parent[u] = v;
    cnt[v] += cnt[u];
    return true;
  }
};
void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B)
{

  UnionFind uf(N);
  for (int i = 0; i < M; i++)
  {
    int a = A[i];
    int b = B[i];
    a--;
    b--;
    uf.uni(a, b);
  }

  vector<int> cnt(N);

  int maxim = 0;
  for (auto c : uf.cnt)
  {
    chmax(maxim, (int)c);
  }

  cout << maxim << endl;
}

int main()
{
  cout << setprecision(10);
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> A(M);
  std::vector<long long> B(M);
  for (int i = 0; i < M; i++)
  {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
  }
  solve(N, M, std::move(A), std::move(B));
  return 0;
}


Measured memory_bytes: 9616
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	cin >> n;
	int d[n+1];
	d[0] = 0;
	for (int i = 1; i <= n; i++) {
		d[i] = d[i-1]+1;
		int tmp = 1;
		for (int j = 1; j <= 6; j++) {
			tmp *= 6;
			if ((i-tmp) >= 0) {
				d[i] = min(d[i], d[i-tmp]+1);
			}
		}
		tmp = 1;
		for (int j = 1; j <= 5; j++) {
			tmp *= 9;
			if ((i-tmp) >= 0) {
				d[i] = min(d[i], d[i-tmp]+1);
			}
		}
	}
	cout << d[n] << endl;
	return 0;
}

Measured memory_bytes: 3960
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

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

int main()
{
	//for(int w,h;cin>>w>>h,w|h;){
	for(int w,h;scanf("%d%d",&w,&h),w|h;){
		//clock_t begin=clock();
		
		vvi field(h,vi(w));
		rep(i,h) rep(j,w)
			//cin>>field[i][j];
			scanf("%d",&field[i][j]);
		
		vector<pii> homes;
		int counter=0;
		rep(i,h) rep(j,w){
			if(field[i][j]==1){
				field[i][j]=++counter;
				homes.push_back(mp(i,j));
			}
			else if(field[i][j]==2){
				field[i][j]=0;
				homes.insert(homes.begin(),mp(i,j));
			}
			else
				field[i][j]=-1;
		}
		
		map<pair<int,int>,int> m;
		m[mp(1,0)]=1;
		foreach(iter,m){
			m.erase(m.begin(),iter);	// svÉÈÁ½vfðÁ³È¢ÆMLEÉÈé
			
			int state=iter->first.first;
			int prev=iter->first.second;
			if(state==(1<<homes.size())-1)
				break;
			
			const int di[]={-1,1,0,0};
			const int dj[]={0,0,-1,1};
			rep(i,4){
				int pi=homes[prev].first,pj=homes[prev].second;
				for(;;){
					pi+=di[i];
					pj+=dj[i];
					if(pi<0 || h<=pi || pj<0 || w<=pj)
						break;
					int homei=field[pi][pj];
					if(homei>=1 && !(state&(1<<homei))){
						m[mp(state|(1<<homei),homei)]+=iter->second;
						break;
					}
				}
			}
		}
		int res=0;
		foreach(iter,m){
			int prev=iter->first.second;
			int pi=homes[prev].first,pj=homes[prev].second;
			if(pi==homes[0].first || pj==homes[0].second)
				res+=iter->second;
		}
		//cout<<res<<endl;
		printf("%d\n",res);
		
		//printf("time: %ldms\n",clock()-begin);
	}
	
	return 0;
}

Measured memory_bytes: 3576
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int (i)=(a);i<(b);i++)
#define INF 1000000000
#define MAX_N 150005
using namespace std;

int dp[1005][1005];

int main(){
    string a=" ",b=" ",x;
    cin>>x;a+=x;
    cin>>x;b+=x;
    rep(i,0,1005)dp[i][0]=dp[0][i]=i;
    
    for(int i=1;i<a.size();i++){
        for(int j=1;j<b.size();j++){
            int cost (a[i]==b[j]?0:1);
            //cout<<cost<<endl;
            dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+cost));
        }
    }
    cout<<dp[a.size()-1][b.size()-1]<<endl;
       
}

Measured memory_bytes: 7144
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    fast
    ll a,b;
    cin>>a>>b;
    cout<<max((a+b),max(a-b,a*b))<<endl;
}


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

using namespace std;

template<typename T>
struct SegmentTree {
private:
	int sz, n;
	vector<T> data;
	function<T(T, T)> f;
	T identity_element;
public:
	/* constructor */
	SegmentTree(
		vector<T> v, // initial data
		T identity_element, // identity element
		function<T(T, T)> f // operation
	) {
		sz = v.size();
		n = 1; while (n < sz) n <<= 1;
		this->f = f;
		this->identity_element = identity_element;
		data.resize(2 * n - 1, identity_element);
		for (int i = 0; i < sz; ++i)
			data[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; --i)
			data[i] = f(data[2 * i + 1], data[2 * i + 2]);
	}
	/* update query */
	void update(int idx, const T val) {
		idx += n - 1;
		data[idx] = val;
		while (idx) {
			idx = (idx - 1) >> 1;
			data[idx] = f(data[2 * idx + 1], data[2 * idx + 2]);
		}
	}
	/* get query */
	T get(int left, int right, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (r <= left || right <= l) return identity_element;
		if (left <= l && r <= right) return data[k];
		T val_l = get(left, right, 2 * k + 1, l, (l + r) / 2);
		T val_r = get(left, right, 2 * k + 2, (l + r) / 2, r);
		return f(val_l, val_r);
	}
};

const int INF = numeric_limits<int>::max();

int main() {
	int n, q; cin >> n >> q;
	SegmentTree<int> seg(vector<int>(n, INF), INF, [](int a, int b) {return min(a, b); });
	while (q--) {
		int com, x, y; cin >> com >> x >> y;
		if (com) cout << seg.get(x, y + 1) << endl;
		else seg.update(x, y);
	}
	return 0;
}


Measured memory_bytes: 4152
//
// Created by yamunaku on 2020/05/03.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    //CFS;
    int n, m;
    cin >> n >> m;
    vi a(n);
    rep(i, n) cin >> a[i];
    vi ok(n, true);
    rep(i, m){
        int u, v;
        cin >> u >> v;
        u--, v--;
        if(a[u] >= a[v]) ok[v] = false;
        if(a[v] >= a[u]) ok[u] = false;
    }
    int ans = 0;
    rep(i, n){
        if(ok[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3976
using System;

class Class2
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        ulong A = ulong.Parse(input[0]);
        string[] input2 = input[1].Split('.');
        ulong B = ulong.Parse(input2[0])*100 + ulong.Parse(input2[1]);


        ulong calc = (A * B) /100;



        Console.WriteLine(calc.ToString());
    }
}

Measured memory_bytes: 27440
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#define int long long

template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
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 (a>b) { a=b; return 1; } return 0; }
template<class T> void printv(vector<T> v){ for (T t : v) {cout << t << " " ;} cout << '\n';}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    int N, M;
    cin >> N >> M;
    vi dp(N+1,0);

    REP(i,M){
        int t;
        cin >> t;
        dp[t] = -1;
    }

    dp[0] = 1;

    REP(i,N+1){
        if (dp[i] < 0) continue;
        else dp[i] %= 1000000007;
        if (dp[i+1] >= 0 and i+1 < N+1) dp[i+1] += dp[i] % 1000000007;
        if (dp[i+2] >= 0 and i+2 < N+1) dp[i+2] += dp[i] % 1000000007;
    }




    cout << dp[N] % 1000000007 << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;
ll x[110000],y[110000];
main(){
  ll n,m,cut,ans=0;
  cin>>n>>m;
  rep(i,0,m)cin>>x[i];
  sort(x,x+m);
  rep(i,0,m-1){y[i]=x[i+1]-x[i];ans+=x[i+1]-x[i];}
  sort(y,y+m-1,greater<ll>());
  rep(i,0,m-1){
    if(n==1)break;
    ans-=y[i];
    n--;
  }
  cout<<ans;
}

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

int main(){
    ll x;
    ll ans = 0;
    cin >> x;
    ll fiveh = x/500;
    ans += fiveh*1000;
    x -= 500*fiveh;
    ans += (x/5)*5;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<limits.h>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<set>
#include<vector>
#include<queue>
#include<set>
#include<stdlib.h>
#include<time.h>
using namespace std;
typedef long long ll;
#define inf	1000000
typedef pair<int,int>	P;
const int N=100010;
int parent[N];
bool marked[N];
ll sum;
void init(int n){
	for(int i=1;i<=n;i++){
		parent[i]=i;
	}
	memset(marked,false,sizeof(marked));
	marked[1]=true;
}

int find(int x){
	if(marked[x]){
		return x;
	}else{
		return find(parent[x]);
	}
}



int main() {
	int n,q;
	while(scanf("%d%d",&n,&q)!=EOF){
		sum=0;
		if(n==0&&q==0){
			break;
		}
		init(n);
		int x;
		char str[2];
		for(int i=2;i<=n;i++){
			scanf("%d",&parent[i]);
		}
		while(q--){
			scanf("%s",str);
			if(str[0]=='M'){
				scanf("%d",&x);
				marked[x]=true;	
			}else if(str[0]=='Q'){
				scanf("%d",&x);
				sum+=find(x);
			}
		}
		printf("%lld\n",sum);
	}
	return 0;
}


Measured memory_bytes: 3688
#include <iostream>
#include <map>
using namespace std;
map <string,int> mp;
int main(int argc, char** argv) {
	mp["MON"]=6;
	mp["TUE"]=5;
	mp["WED"]=4;
	mp["THU"]=3;
	mp["FRI"]=2;
	mp["SAT"]=1;
	mp["SUN"]=7;
	string a;
	cin >> a;
	cout << mp[a];
	return 0;
}

Measured memory_bytes: 256