akhauriyash/Code-Regression huggingface dataset:
while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break

    count = 0

    for i in range(1, n+1):
        for j in range(i+1, n+1):
            k = x - i - j

            if not (j < k <= n):
                continue

            count += 1

    print(count)



Measured memory_bytes: 5592
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define oo 0x3f3f3f3f

const int N = 300005;
int seg[4*N];

void Add(int c, int l, int r, int pos, int val)
{
    if(l==r)
    {
        seg[c]+=val;
        return;
    }
    int m = (l+r)/2;
    if(pos <= m)Add(2*c,l,m,pos,val);
    else Add(2*c+1,m+1,r,pos,val);

    seg[c] = max(seg[2*c], seg[2*c+1]);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int h,w,m;
    cin>>h>>w>>m;
    vector<array<int,2>>A(m);
    vector<vector<array<int,2>>>W(h+1);
    vector<int>H(h+1);

    for(auto&a:A)
        {
            cin>>a[0]>>a[1];
            Add(1,0,w,a[1],1);
            W[a[0]].push_back(a);
            H[a[0]]++;
        }

    int res = 0;

    for(int i=0; i<=h; i++)
    {
        for(auto&a : W[i])
            Add(1,0,w,a[1],-1);

        res = max(res, H[i] + seg[1]);

        for(auto&a : W[i])
            Add(1,0,w,a[1],1);
    }

    cout<<res;
}


Measured memory_bytes: 27200
#include <stdio.h>
#include<stdlib.h>
#define NIL NULL

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;
Node root;
Node* tree;

void insert(int);
void inorder(Node);
void preorder(Node);
Node treeSearch(Node, int);
void delete(Node);
Node minimum( Node);
Node Successor(Node);

int main(){

  int m,i,a,x;
  char str[20];

  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%s",str);
    if ( str[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if(t!=NIL){
	printf("yes\n");
      }
      else {
	printf("no\n");
      }
    }
    if(str[0]=='i'){
      scanf("%d",&a);
      insert(a);
    }
    else if(str[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(str[0] == 'd'){
      scanf("%d", &x);
      delete(treeSearch(root, x));
    }
  }
  
  return 0;
  
}

void inorder(Node x){
  if(x!=NIL){
    inorder(x->left);
    printf(" %d",x->key);
    inorder(x->right);
  }
}

void preorder(Node x){
  if(x!=NIL){
    printf(" %d",x->key);
    preorder(x->left);
    preorder(x->right);
  }
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
  if(y==NIL){
    root=z;
  }
  else if(z->key<y->key){
    y->left=z;
      }
  else{
    y->right=z;
  }
}

Node treeSearch(Node u, int k){
  while(u != NIL && u->key != k){
    if( u->key > k){
      u = u->left;
    }
    else{
      u = u->right;
    }
  }
  return u;
}

Node successor(Node T){
  Node x;
  if(T->right != NULL){
    return minimum(T->right);
  }
  x = T->parent;
  
  while(x != NULL && T == x->right){
    T = x;
    x = x->parent;
  }
  return x;
}
  
void delete(Node T){
  
  Node x;
  Node y;
  
  if(T->left == NULL || T->right == NULL){ 
    x = T;
  }else{
    x = successor(T);
  }
  if(x->left != NULL){
    y = x->left;
  }else{
    y = x->right;
  }
  
  if(y != NULL){
    y->parent = x->parent;
  }
  
  if(x->parent == NULL){
    root = y;
  }else if(x == x->parent->left){
    x->parent->left = y;
  }else{
    x->parent->right = y;
  }
  if(x != T){
    T->key = x->key;
  }
}
  
Node minimum(Node T){
  while(T->left != NULL){
    T = T->left;
  }
  return T;
}

Measured memory_bytes: 19364
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define LL long long
#define mp make_pair
#define fr first
#define sc second
#define pb push_back
#define lc (x<<1)
#define rc ((x<<1)|1)
const int N=100005;
const LL mod=1000000007;
LL a[N];
LL jc(LL n) {LL ans=1;for (LL i=1;i<=n;i++) ans=ans*i%mod;return ans;}
int main(){
  //  freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    int i,n,t;LL j,ans=1,die=0;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (j=1;j<=n;){
        while (j<=n&&2*(j-die)-1<=a[j]) j++;
        if (j>n) break; 
        ans=ans*(j-die)%mod;die++;
    }
    ans=ans*jc(n-die)%mod;
    cout<<ans<<endl;
  //  system("pause");
    return 0;
}


Measured memory_bytes: 1024
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Clue = Tuple!(long, "x", long, "y", long, "h");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

long cnt;

void main()
{
    long x, y, a, b, c;
    scan(x, y, a, b, c);
    auto p = aryread();
    auto q = aryread();
    auto r = aryread();
    p.sort();
    q.sort();
    r.sort();
    p ~= INF;
    q ~= INF;
    long a_iter = a - x, b_iter = b - y, c_iter = c;
    while (c_iter > 0 && min(p[a_iter], q[b_iter]) < r[c_iter - 1])
    {
        if (p[a_iter] < q[b_iter])
            a_iter++;
        else
            b_iter++;

        c_iter--;
    }
    // a_iter.writeln();
    // b_iter.writeln();
    // c_iter.writeln();
    writeln(p[a_iter .. $ - 1].sum() + q[b_iter .. $ - 1].sum() + r[max(c_iter, 0) .. $].sum());
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 12872
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>

int main() {

   int A, B, C, X, Y;
   std::cin >> A >> B >> C >> X >> Y;
   double coe = C - A / 2 - B / 2;
  
   int ans = A * X + B * Y;
   int max = X;
   if (max < Y) max = Y;
   int Nc = 2 * max;
   for (int i = 1; i <= Nc; i++) {
      int Na = std::max(0, X - i / 2);
      int Nb = std::max(0, Y - i / 2);
      int tmp = Na * A + Nb * B + i * C;
      if (ans > tmp) ans = tmp;
   }
   
   std::cout << ans<< std::endl;
   return 0;
}


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

int main()
{
    int n;cin>>n;
    int a[n],c=0,d=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]%2==0)
        {
            c++;
            if(a[i]%3==0 || a[i]%5==0)
            {
                d++;
            }
        }
    }
    if(c==d)cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = []
for i in range(n):
    s.append(input())

d = {}
for i in range(n):
    if i==0:
        for j in range(len(s[i])):
            if s[i][j] in d:
                d[s[i][j]] += 1
            else:
                d[s[i][j]] = 1
    else:
        for k in d.keys():
            if d[k] > 0:
                d[k] = min(d[k],s[i].count(k))
ans = ""
for k in d.keys():
    ans += k*d[k]
print("".join(sorted(ans)))



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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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

const ll INF=(ll)1e19;
//const int INF=(1<<30);

int main(){
  int x,y;
  cin >>x >> y;
  cout << x+y/2 << endl;
}



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

public class P
{
	public string s { get; set; }
	public int x { get; set; }
	public int y { get; set; }
	public int step { get; set; }
}

public class hello
{
	public static void Main()
	{
		var map = new int[3, 3];
		var sx = 0;  var sy = 0;
		for (int i = 0; i < 3; i++)
		{
			string[] line = Console.ReadLine().Trim().Split(' ');
			for (int j = 0; j < 3; j++)
			{
				map[i, j] = int.Parse(line[j]);
				if (map[i,j] == 0) { sx = i; sy = j; };
			}
		}
		var ans = goBfs(map, sx, sy);
		Console.WriteLine(ans);
	}
	static int goBfs (int [,] map, int sx , int sy)
	{
		var hs = new HashSet<string>();
		var dx = new int[] { 0, 1, 0, -1 };
		var dy = new int[] { 1, 0, -1, 0 };
		var q = new Queue<P>();
		var t = MapToString(map);
		q.Enqueue(new P { s = t, x = sx,y = sy,step = 0});
		hs.Add(t);
		while (q.Count() > 0)
		{
			var w = q.Dequeue();
			if (w.s == "123456780") return w.step;
			var tmap = StringToMap(w.s);
			for (int i = 0; i < 4; i++)
			{
				var nx = w.x + dx[i];
				var ny = w.y + dy[i];
				if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
				{
					tmap[w.x, w.y] = tmap[nx, ny];
					tmap[nx, ny] = 0;
					var tt= MapToString(tmap);
					if (hs.Add(tt)) q.Enqueue(new P { s = tt, x = nx, y = ny, step = w.step + 1 });
					tmap[nx, ny] = tmap[w.x, w.y];
					tmap[w.x, w.y] = 0;
				}
			}
		}
		return 0;
	}
	static string MapToString (int [,] map)
	{
		var s = "";
		foreach (var x in map) s += x;
		return s;
	}
	static int[,] StringToMap (string s)
	{
		var map = new int[3, 3];
		var p = 0;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				map[i, j] = s[p++] - '0';
		return map;
	}
}



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

using namespace std;

typedef long long ll;

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

  int n, k; cin >> n >> k;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }

  sort(p.begin(), p.end());
  int tot = 0;
  for (int i = 0; i < k; ++i) {
    tot += p[i];
  }

  cout << tot << endl;
  
  return 0;
}




Measured memory_bytes: 3656
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 100000
#define pb push_back
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
int first[MAXN+5], c[MAXN+5], tot, flag, n, m, cnt1, cnt2;
struct Edge{int to,nex; Edge(){} Edge(int _to, int _nex):to(_to),nex(_nex){}}e[(MAXN<<1)+5];
inline void Add(int a, int b){e[tot] = Edge(b,first[a]), first[a] = tot++, e[tot] = Edge(a,first[b]), first[b] = tot++;}
void DFS(int p, int d)
{
	c[p] = d; d>0 ? ++cnt1 : ++cnt2;
	for(rint u = first[p], v; ~u; u = e[u].nex)
		if(!c[v=e[u].to]) DFS(v,-d);
		else if(c[v]==c[p]){flag = false; return;}
}
int main()
{
	n = read(), m = read(), flag = true, memset(first+1,-1,n<<2);
	for(rint i = 1; i <= m; Add(read(),read()), i++); DFS(1,1);
	printf("%lld\n",(flag ? 1ll*cnt1*cnt2 : 1ll*n*~-n>>1)-m); return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int n,k;
	cin>>n>>k;
	cin>>s;
	for(int i=0;i<n;i++){
		if(i==(k-1)){
			s[i]=s[i]+'a'-'A';
		}
		cout<<s[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define N 100
#define f(i, a, b) for (ll i = (ll)a; i <= (ll)b; i++)
#define rf(i, a, b) for (ll i = (ll)a; i >= (ll)b; i--)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define debug(x) cout << #x << " = " << x << endl
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define all(x) x.begin(), x.end()
#define PI 3.141592653
#define cot cout.tie(0)
#define endl "\n"
using namespace std;
/**
        * @author :: Sawlani
        *
        */

 

int main()
{
         
        double r;
        cin >> r;
        cout << fixed <<  setprecision(10) ;
         double ans = 2.0*PI*r;

         cout << ans;
}


Measured memory_bytes: 3764
N = int(input())

if N == 0:
    print(0)
    exit()

a = ''
b = -2

while N != 1:
    if N % b == 0:
        a += '0'
        N = N // b
    else:
        a += '1'
        if N > 0:
            N = N // b + 1
        else:
            N = N // b + 1
if N == 1:
    a += '1'
print(a[::-1])


Measured memory_bytes: 3060
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import heapq

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M = LI()
ab = []
for i in range(N):
    ab.append(LI())

ab.sort()
candidates = []

ans = 0
s = 0
for i in range(1, M+ 1):
    for j in range(s, N):
        a,b = ab[j]
        if a <= i:
            heapq.heappush(candidates, -b)
        else:
            s = j
            break
    else:
        s = j + 1
    if len(candidates) > 0:
        # print(candidates)
        ans += -1 * heapq.heappop(candidates)

print(ans)
"""
4 3 2

3 2 3 1
2 3 1


"""


Measured memory_bytes: 96616
/**
 	Template created by Danel Batyrbek
 	All rights are reserved 2017 (lol)
*/

#include <bits/stdc++.h>

#define speed_up ios_base :: sync_with_stdio(0);cin.tie(0)
#define fr first
#define sc second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << x << '\n';
#define YES "YES"
#define NO "NO"
#define skip continue
#define left(x) x << 1
#define rght(x) x << 1 | 1
#define forn(x, y, z) for(int x = y; x <= z; ++ x)
#define for1(x, y, z) for(int x = y; x >= z; -- x)
#define fname ""
using namespace std;

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

const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int N3 = 1e3 + 10;
const int INF = 2e9 + 10;
const ll LINF = 2e18;

int n, m;
char a[20][20];

bool u[20][20];

bool check(){
	forn(i, 1, n){
		forn(j, 1, m){
			if(a[i][j] == '#' && u[i][j]) skip;
			if(a[i][j] == '.' && !u[i][j]) skip;
			return 0;
		}
	}
	return 1;
}

bool dfs(int x, int y){
	if(a[x][y] == '.') return 0;
	u[x][y] = 1;
	if(x == n && y == m) return 1;
	if(a[x + 1][y] == a[x][y + 1]) return 0;
	if(a[x + 1][y] == '#') return dfs(x + 1, y);
	if(a[x][y + 1] == '#') return dfs(x, y + 1);
	return 0;
}

int main(){
#ifndef DEBUG
	if(fname != ""){
	freopen(fname".in", "r", stdin);
	freopen(fname".out", "w", stdout);
	}
#endif	
	cin >> n >> m;
	forn(i, 1, n + 1){
		forn(j, 1, m + 1){
			a[i][j] == '.';
		}
	}
	forn(i, 1, n){
		forn(j, 1, m){
        	cin >> a[i][j];
        }
	}
	if(dfs(1, 1) && check()){
		cout << "Possible";
	} else {
		cout << "Impossible";
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k;
int d[100100];
vector<int> a,qjh;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		scanf("%1d",&d[i]);
	if(d[1]==0)
		a.push_back(0);
	int val=0;
	for(int i=1;i<=n;i++)
	{
		if(i!=1&&d[i]!=d[i-1])
		{
			a.push_back(val);
			val=0;
		}
		val++;
	}
	a.push_back(val);
	qjh.resize(a.size()+1);
	qjh[0]=0;
	for(int i=0;i<a.size();i++)
		qjh[i+1]=(qjh[i]+a[i]);
	int res=0;
	for(int i=0;i<qjh.size();i+=1){
		int sc=qjh[min((int)a.size(),k*2+i+1-(i%2))]-qjh[i];
		res=max(res,sc);
	}
	cout<<res<<endl;
	return 0;
}


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

#define in(v) cin>>v;
#define out(v) cout<<v<<"\n"

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int K, A, B;
  cin >> K >> A >> B;

  if (B - A <= 1)
    out(K+1);
  else {
    // A-1回叩く-> A枚を交換 -> B枚に増える-> A枚を交換->B枚増える
    long long k = K-(A-1), ans = A;
    ans += (B-A) * (k/2);
    if (k % 2 == 1)
      ++ans;
    out(ans);
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

// #define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9+5;
const int mod = 1e9+7;
using ll = long long;
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;
 }
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;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
vector<mint> fac(MX);
vector<mint> ifac(MX);
mint comp(ll a, ll b) {
    return fac[a]/fac[b]/fac[a-b];
}
signed main(){
    int n;
    cin >> n;
    mint ten = 1;
    mint nin = 1;
    mint ei = 1;
    rep(i,n) {
        ten *=10;
        nin *=9;
        ei *= 8;
    }
    cout << ten-nin-nin+ei << endl;

    return 0;

}


Measured memory_bytes: 18620
#include<cstdio>
using namespace std;
int n;
int p[20010],a[20010],b[20010];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&p[i]);
	for (int i=1;i<=n;i++)
		a[i]=1,b[i]=-1;
	for (int i=1;i<=n;i++)
		a[p[i]]+=i,b[p[i]+1]-=i;
	for (int i=1;i<=n;i++)
		a[i]+=a[i-1],b[i]+=b[i-1];
	for (int i=1;i<=n;i++)
		printf("%d%c",a[i]+500000000," \n"[i==n]);
	for (int i=1;i<=n;i++)
		printf("%d%c",b[i]+500000000," \n"[i==n]);
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
 
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << ", " << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define f first
#define s second
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    double a, b, m;
    int h;
    cin >> a >> b >> h >> m;
    h = h % 12;
    double H = (h * 30) + (m / 2), M = m * 6;
    double diff = abs(min(H - M, 360 - (H - M))) * M_PI / 180;
    double ans = sqrt((a * a) + (b * b) - (2 * a * b * cos(diff)));
    //cout << H << " " << M << endl;
    printf("%.11f\n", ans);
}



Measured memory_bytes: 4244
#include <stdio.h>
#define len 10001
#define MAX 2000001

int A[MAX];
int B[MAX];
int C[len];

int main(){

  int i,n;
  for(i=0;i<len;i++){
    C[i]=0;
  }
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
  }
  for(i=1;i<=n;i++){
    C[A[i]]++;
  }

  for(i=1;i<=len;i++){
    C[i]=C[i]+C[i-1];
  } 
  for(i=n;i>=1;i--){
    B[C[A[i]]]=A[i];
    C[A[i]]--;
  }

  for(i=1;i<=n;i++){
    if(i>1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  return 0;
}


    
  

Measured memory_bytes: 16268
#include<stdio.h>
int main(void)
{
	int a, b, c;
	int num = 0;
	int max = 0;
	int i;
	scanf("%d %d %d", &a, &b, &c);
	max = a;
	if (max < b) max = b;
	if (max < c) max = c;

	if (a % 2 == b % 2 && a % 2 != c % 2)
	{
		if (max == a || max == b) max++;
		a++;
		b++;
		num++;
	
		for (i = 0; a < max; i++)
		{
			a = a + 2;
			num++;
	}
		for (i = 0; b < max; i++)
		{
			b = b + 2;
			num++;
		}
		for (i = 0; c < max; i++)
		{
			c = c + 2;
			num++;
		}
	}
	else if (a % 2 == c % 2 && a % 2 != b % 2)
	{
		if (max == a || max == c) max++;
		a++;
		c++;
		num++;

		for (i = 0; a < max; i++)
		{
			a = a + 2;
			num++;
		}
		for (i = 0; c < max; i++)
		{
			c = c + 2;
			num++;
		}
		for (i = 0; b < max; i++)
		{
			b = b + 2;
			num++;
		}
	}
	else if (c % 2 == b % 2 && b % 2 != a % 2)
	{
		if (max == c || max == b) max++;
		c++;
		b++;
		num++;

		for (i = 0; c < max; i++)
		{
			c = c + 2;
			num++;
		}
		for (i = 0; b < max; i++)
		{
			b = b + 2;
			num++;
		}
		for (i = 0; a < max; i++)
		{
			a = a + 2;
			num++;
		}
	}
	else if (a % 2 == b % 2 && a % 2 == c % 2)
	{
		for (i = 0; c < max; i++)
		{
			c = c + 2;
			num++;
		}
		for (i = 0; b < max; i++)
		{
			b = b + 2;
			num++;
		}
		for (i = 0; a < max; i++)
		{
			a = a + 2;
			num++;
		}
	}
	printf("%d\n", num);
	return 0;
}

Measured memory_bytes: 128
from sys import stdin
from sys import setrecursionlimit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))

li = [0]*n

for i in a:
    li[i-1] += 1

for i in li:
    print(i)

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

#define int long long

template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  }
  T query(int a,int b){
    T vl=ti,vr=ti;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,dat[k]);
      return check(acc)?k-n:-1;
    }
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }
  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, K;
  cin >> N >> K;

  auto f=[](int a,int b){return min(a,b);};
  SegmentTree<int> rmq1(f,INT_MAX);
  rmq1.init(N);
  auto g=[](int a,int b){return max(a,b);};
  SegmentTree<int> rmq2(g,-1);
  rmq2.init(N);

  vector<int> P(N);
  for ( int i = 0; i < N; i++ ) {
    cin >> P[i];
    rmq1.set_val(i, P[i]);
    rmq2.set_val(i, P[i]);
  }

  vector<int> cum(N, 0);
  for ( int i = 1; i < N; i++ ) {
    if ( P[i] < P[i-1] ) cum[i] = 1;
    cum[i] += cum[i-1];    
  }

  bool add = false;  
  int ans = 0;
  int pre = 0;  
  for ( int i = 1; i < N; i++ ) {
    if ( i+K-2 >= N ) break;    
    if ( cum[i+K-2] - cum[i-1] > 0 ) {
      if ( i == 1 ) {
	ans++;
	pre = 1;
      }
      else {
	ans++;
	// cout << rmq1.query(i-2, i+K-2) << " " << rmq2.query(i-1, i+K-1) << endl;
	if ( rmq1.query(i-2, i+K-2) == P[i-2] && rmq2.query(i-1, i+K-1) == P[i+K-2] && pre == 1 ) {
	  ans--;
	  // cout << i << endl;
	}
	else pre = 1;
      }
    } else {
      add = true;
      pre = 0;
    }
  }
  // cout << add << endl;
  cout << ans+add << endl;  
  
  return 0;
}


Measured memory_bytes: 11648
#include<bits/stdc++.h>
using namespace std;
int read() {
	int x; scanf("%d", &x); return x;	
}
const int maxn = 3e5 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
using namespace std;
int n, d;
char s[maxn];
int main() {
	#ifdef LOCAL
		freopen("1.in", "r", stdin);
	#endif
	n = read();
	scanf("%s", s + 1);
	int W = 0, S = 0;
	int L = 1, R = n;
	while (s[L] == 'R' && L <= n) L++;
	while (s[R] == 'W' && R >= 1) R--;
	vector<int>l, r;
	for (int i = L; i <= R; ++i) {
		if (s[i] == 'R') l.push_back(i);
		else r.push_back(i);
	}
	sort(l.begin(), l.end(), greater<int>()); sort(r.begin(), r.end());
	int lp = 0, rp = 0;
	int ans = 0;
	while (lp < l.size() && rp < r.size()) {
		if (l[lp] < r[rp]) break;
		swap(s[l[lp]], s[r[rp]]);
		lp++, rp++; ans++;
	}
	cout << ans << endl;
	return 0;	
}
 	

Measured memory_bytes: 4812
# atcoder : python3 (3.4.3)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9+7

# main
N = int(input())

from math import ceil
if ceil(N/1.08) < (N+1)/1.08:
    print(ceil(N/1.08))
else:
    print(":(")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
    unsigned long long n=100,x;
    cin >> x;
    unsigned long long c =0;
    while(true){
        n = n + n*0.01;
        c++;
        if(n>=x){
            cout << c << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3636
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main(){
    double x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<fixed<<setprecision(4)<<sqrt(pow((x1-x2),2)+pow((y1-y2),2))<<endl;
    
    return 0;
}



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

#define mp make_pair
#define fst first
#define snd second

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

template <typename T>
T id(T b) {return b;};
template <class It>
bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It>
bool any(It f,It l){return std::any_of(f,l,id<bool>);}

const int MAX_N = 100000;
int n,m;
int min_opp[MAX_N];

int main()
{
  cin >> n >> m;
  fill_n(min_opp,n,INT_MAX);
  int a,b;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
    min_opp[a-1] = min(min_opp[a-1], b-1);
  }

  int res = 0;
  int mo = INT_MAX;
  for (int i = 0; i < n; i++) {
    mo = min(mo, min_opp[i]);
    if (mo == i+1) {
      res++;
      mo = INT_MAX;
    }
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 640
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<deque>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<list>
#define For(i,a,b) for(int i=(a); i<=(b) ; i++)
#define _For(i,a,b) for(int i=(a); i>=(b) ; i--)
#define Memset(a,b); memset((a),(b),sizeof((a)));
#define Cout(a,b);  printf("%d",(a));printf(b);
#define Coutc(a,b);  printf("%c",(a));printf(b);
#define Couts(a,b);  printf("%s",(a));printf(b);
using namespace std;
const int INF = 0x3f3f3f3f;
typedef  long long LL;typedef  unsigned long long ULL;typedef  long double LDB;
inline LL CinLL(){LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline int Cin(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;}
LL n,k; 
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	LL ans = 0; 
	For(b,k+1,n)
	{
		LL c = n/b;
		LL d = n%b;
		ans+=c*(b-k);
		if(d>=k)
		{
			if(k == 0) ans+=d;
			else ans+=(d-k+1);
		}
	}
	cout<<ans<<endl;
}



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

int main(){
    string str;
    char tmp;
    int i, num, sum = 0;

    cin >> str;
    num = atoi(&str[0]);

    for(i = 0; i < str.size(); i++){
        tmp = str[i];
        sum += atoi(&tmp);
    }
    if(num%sum == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N, a;
	map<int, int> m;
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> a;
		m[a-1]++;m[a]++;m[a+1]++;
	}
	a = 0;
	for(auto itr = m.begin(); itr!=m.end(); itr++)
		a = max(a, itr->second);
	cout << a << "\n";
	return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>

#define N 100000

int partition(int*,int,int);

int main(){
  int A[N];
  int i,j,n;

  scanf("%d",&n);

  for(i=0; i<n; i++){
    scanf("%d",&A[i]);
  }

  j = partition(A,0,n-1);

  for(i=0;i<n;i++){
    if(i!=0) printf(" ");
    if(i==j) printf("[%d]",A[i]);
    else printf("%d",A[i]);
  }

  printf("\n");
  return 0;
}

int partition(int* A,int p,int r){
  int x,i,j;
  int temp;
  x = A[r];
  i = p-1;

  for(j=p; j<r; j++){
    if(A[j] <= x){
      i++;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;
    }
  }
    temp = A[i+1];
    A[i+1] = A[r];
    A[r] = temp;

  return i+1;

}

Measured memory_bytes: 992
import Data.List.Split
import Data.List
main :: IO ()
main = do
    getLinea :: IO Int
    a <- getLine >>= return . map read . splitOn " " :: IO [Int]
    putStrLn . show $ solve a
    where
        getLinea :: Read a => IO a
        getLinea = getLine >>= (return . read)
        sep2 :: [Int] -> [(Int,Int)]
        sep2 [] = []
        sep2 [x] = [(x,0)]
        sep2 (x:y:xs) = (x,y):sep2 xs
        solve :: [Int] -> Int
        solve = foldr (\(x,y) sum -> sum + (x - y)) 0 . sep2 . reverse . sort

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

const int INF = 1e9 + 7;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    rep(i, N) cin >> h[i];

    sort(h.begin(), h.end());
    int res = INF;
    for (int i = 0; i < N - K + 1; i++) {
        res = min(res, h[K+i-1] - h[i]);
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#define INF 100100100
using namespace std;


int		main(void)
{
	int N, M, X;
	int A[12][12];
	int C[12];
	int ans = INF;

	cin >> N >> M >> X;
	for (int i = 0; i < N; i++)
	{
		cin >> C[i];
		for (int j = 0; j < M; j++)
		{
			cin >> A[i][j];
		}
	}

//最大で000000000000 ~ 11111111111 までループを回す。全ての買い方についてのループ
	for (int i = 0; i < 1<<N; i++)
	{
		int cost = 0;
		vector<int> d(M);
		//M（column）のループ
		for (int j = 0; j < N; j++)
		{
			//if found 1, plus cost and plus each row
			if (i>>j & 1)
			{
				cost += C[j];
				for (int k = 0; k < M; k++)
				{
					d[k] += A[j][k];
				}
			}
		}

		//全ての列がX以上であるかどうか調べる
		bool ok = true;
		for (int l = 0; l < M; l++)
		{
			if (d[l] < X)
			{
				ok = false;
			}
		}
		if (ok)
		{
			ans = min(ans, cost);
		}
	}
	if (ans == INF)
		cout << -1 << endl;
	else
		cout << ans << endl;
	return (0);
}

Measured memory_bytes: 3620
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
 
 
#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 LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000
 
using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;
 
int dy[5] = { 0,0,1,-1,0 };
int dx[5] = { 1,-1,0,0,0 };
 
int main(void){

	while(1){
		string s,t;
		int miss=0;
		int spos=0;
		int tpos=0;
		int ssize,tsize;
		vector<string> ss(101),tt(101);
		int sspos=0;
		int ttpos=0;
		bool flag=false;

		cin>>s;
		if(s=="."){
			break;
		}
		cin>>t;
		ssize=s.size();
		tsize=t.size(); 

		flag=false;
		FOR(i,0,s.size()-1){
			if(s[i]=='"'){
				i++;
				
				while(s[i]!='"'){
					ss[sspos].push_back(s[i]);
					s.erase(s.begin()+i);
				}
				sspos++;
			}
		}

		FOR(i,0,t.size()-1){
			if(t[i]=='"'){
				i++;
				while(t[i]!='"'){
					tt[ttpos].push_back(t[i]);
					t.erase(t.begin()+i);
				}
				ttpos++;
			}
		}

		//cout<<s<<endl<<t<<endl;

		FOR(i,0,min(s.size()-1,t.size()-1)){
			if(s[i]!=t[i]){
				miss+=2;
			}
		}

		if(sspos!=ttpos){
			miss+=2;
		}else{
			FOR(i,0,sspos-1){
				if(ss[i]!=tt[i]){
					miss++;
				}
			}
		}

		if(miss==0){
			cout<<"IDENTICAL"<<endl;
		}else if(miss==1){
			cout<<"CLOSE"<<endl;
		}else{
			cout<<"DIFFERENT"<<endl;
		}

	}

}


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

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	int n, m; cin >> n >> m;
	cout << n - m + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime(int num) {
  if (num < 2){
    return false;
  }else if (num == 2){
    return true;
  }else if (num % 2 == 0){
    return false;
  }
  double sqrtNum = sqrt(num);
  for (int i = 3; i <= sqrtNum; i += 2) {
    if (num % i == 0) {
      return false;
    }
  }
  return true;
}

int main(int argc, const char *argv[]) {
  int x;
  cin >> x;

  while(1){
    if(IsPrime(x)){
      cout << x << endl;
      break;
    }
    x++;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e12;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
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; }

typedef vector<vector<P> > Graph;

vector<ll> cost;
void dfs(const Graph &G, ll v, ll p, ll add) {
    cost[v] = add;
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (next_v.first == p) continue; // next_v が探索済だったらスルー
        dfs(G, next_v.first, v, add + next_v.second); // 再帰的に探索
    }
}



int main() {
    ll n;
    cin >> n;
    Graph G(n);
    rep1(i, n-1){
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, c));
    }
    ll q, k;
    cin >> q >> k;
    k--;
    cost.assign(n, 0);
    dfs(G, k, -1, 0);
    rep1(i, q){
        ll x, y;
        cin >> x >> y;
        x--, y--;
        cout << cost[x]+cost[y] << endl;
    }
    //printf("%.12f", ans);
}

Measured memory_bytes: 17096
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <ctime>

using namespace std;
#define RN cout << "\r\n";
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long int ll;
typedef pair<ll, ll> P;

// combination
const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

void dfs(int &a, vector<vector<bool>> &graph, int &ans, vector<bool> &passed, int current) {
    bool complete = true;
    REP(i, a) {
        if (!passed[i]) {
            complete = false;
        }
    }
    if (complete) {
        ans++;
        return;
    }
    REP(j, a) {
        if (graph[current][j] && !passed[j]) {
            vector<bool> new_passed(passed);
            new_passed[j] = true;
            dfs(a, graph, ans, new_passed, j);
        }
    }
    return;
}

int main() {
    int a, b;
    cin >> a >> b;
    vector<vector<bool>> graph;
    graph = vector<vector<bool>>(a, vector<bool>(a, false));
    REP(i, b) {
        int c, d;
        cin >> c >> d;
        graph[c - 1][d - 1] = true;
        graph[d - 1][c - 1] = true;
    }
    int ans = 0;
    vector<bool> passed(a, false);
    passed[0] = true;
    dfs(a, graph, ans, passed, 0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main() {
 
  int a, b, c, d;
 
  scanf("%d %d %d", &a, &b, &c);
 
  if (c < a) {
    d = c;
    c = a;
    a = d;
  }
  if (c < b) {
    d = c;
    c = b;
    b = d;
  }
  if (a > b) {
    d = a;
    a = b;
    b = d;
  }
     
  printf("%d %d %d\n", a, b, c);
         
}
 

Measured memory_bytes: 1848
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Standard_Deviation
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                if (int.Parse(Console.ReadLine()) == 0) break;
                string line = Console.ReadLine();
                string[] strs = line.Split(' ');

                List<int> points = new List<int>();                
                foreach (string str in strs)
                {
                    points.Add(int.Parse(str));
                }
                StandardDeviation problem = new StandardDeviation(points);

                Console.WriteLine(problem.GetStandardDeviation().ToString("F5"));

            }
        }
    }

    public class StandardDeviation
    {

        List<int> points;

        public StandardDeviation(List<int> points)
        {
            this.points = points;
        }

        public double GetStandardDeviation()
        {
            double average = GetAverage();

            double sum = 0.0;
            foreach (int point in points)
            {
                sum += (point - average) * (point - average);
            }

            double variance = sum / points.Count;

            return Math.Sqrt(variance);
        }

        private double GetAverage()
        {
            double average = 0.0;

            foreach (int point in points)
            {
                average += point;
            }
            average /= points.Count;

            return average;
        }

    }
}

Measured memory_bytes: 5832
import math


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    seq = 1
    for i in range(K-1):
        if P[i] < P[i+1]:
            seq += 1
        else:
            seq = 1
    has_orig = seq == K
    ln = int(math.log(K, 2))
    dp1 = [[0] * N for _ in range(ln+1)]
    dp2 = [[0] * N for _ in range(ln+1)]
    dp1[0] = P
    dp2[0] = P
    for k in range(ln):
        for i in range(N-2**k):
            dp1[k+1][i] = min(dp1[k][i], dp1[k][i+2**k])
            dp2[k+1][i] = max(dp2[k][i], dp2[k][i+2**k])
    rmq = [float("inf")] * (N-K+1)
    rMq = [0] * (N-K+1)
    for i in range(N-K+1):
        idx = i
        for k in range(ln+1)[::-1]:
            if K & (2**k):
                rmq[i] = min(rmq[i], dp1[k][idx])
                rMq[i] = max(rMq[i], dp2[k][idx])
                idx += 2**k
    ans = 1
    for i in range(N-K):
        if P[i+K-1] < P[i+K]:
            seq += 1
        else:
            seq = 1
        if seq >= K:
            if not has_orig:
                has_orig = True
                ans += 1
            continue
        if P[i] != rmq[i] or P[i+K] < rMq[i]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 125536
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); ++i)
#define per(i,a,b) for (int i=(a); i>=(b); --i)
using namespace std;

const int maxn = 105;
int f[maxn][maxn][maxn], s[maxn][maxn], n, m, sx, sy, ans;
char str[maxn];

inline void upd(int &x, int y) {
	if (y > x) x = y;
}

inline int getr(int x, int l, int r) {
	return s[x][r] - s[x][l-1] - s[x-1][r] + s[x-1][l-1];
}

inline int getc(int y, int u, int d) {
	return s[d][y] - s[u-1][y] - s[d][y-1] + s[u-1][y-1];
}

int main() {
	scanf("%d%d", &n, &m);
	rep (i, 1, n) {
		scanf("%s", str + 1);
		rep (j, 1, m) {
			if (str[j] == 'E') sx = i, sy = j;
			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1];
			if (str[j] == 'o') s[i][j]++;
		}
	}
	memset(f, 0xc0, sizeof f); f[0][0][0] = 0;
	rep (u, 0, sx-1) rep (d, 0, n-sx)
		rep (l, 0, sy-1) rep (r, 0, m-sy) {
			if (sx + d + 1 <= n - u)
				upd(f[d+1][l][r], f[d][l][r] + getr(sx + d + 1, max(r+1, sy-l), min(m-l, sy+r)));
			if (sy - l - 1 >= r + 1)
				upd(f[d][l+1][r], f[d][l][r] + getc(sy - l - 1, max(d+1, sx-u), min(n-u, sx+d)));
			if (sy + r + 1 <= m - l)
				upd(f[d][l][r+1], f[d][l][r] + getc(sy + r + 1, max(d+1, sx-u), min(n-u, sx+d)));
			if (sx - u - 1 >= d + 1)
				upd(f[d][l][r],	  f[d][l][r] + getr(sx - u - 1, max(r+1, sy-l), min(m-l, sy+r)));
			upd(ans, f[d][l][r]);
			// printf("%d %d %d %d  %d\n", u, d, l, r, f[d][l][r]);
		}
	printf("%d\n", ans);
	return 0;
}

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

signed main() {
    lint N; cin >> N;
    vector<lint> A(N); 
		for(lint i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    lint ans;
    if(N % 2 == 0){
        lint temp=0;
        for(lint i = 0; i < N/2-1; i++) temp -= 2*A[i];
        temp -= A[N/2-1];
        temp += A[N/2];
        for(int i = N/2 + 1; i < N; i++)  temp += 2 * A[i];
        ans = temp;
    }
    else {
        lint temp = 0;
        for(lint i = 0; i < N/2-1; i++) temp -= 2*A[i];
        for(lint i = N/2+2; i < N; i++) temp += 2*A[i];
        ans = max( temp - 2*A[N/2-1] + A[N/2] + A[N/2+1], temp - A[N/2-1] - A[N/2] + 2*A[N/2+1] );
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
n, k = map(int, input().split())
S = str(input())

flag = '0'
ans = []
for i, s in enumerate(S):
    if s == '1':
        if flag == '0':
            tmp = [0]*2
            tmp[0] = i+1
            flag = '1s'
        if flag == '1s' and i == n-1:
            tmp[1] = i+1
            ans.append(tmp)
    else:
        if flag == '1s':
            tmp[1] = i
            ans.append(tmp)
            flag = '0'
if S[0] == '0':
    ans.insert(0, [1, 1])
if S[n-1] == '0':
    ans.append([n, n])
# print(ans)
anser = []
if k >= len(ans):
    print(n)
else:
    for i in range(len(ans)):
        if i+k > len(ans)-1:
            break
        else:
            anser.append(ans[i+k][1]-ans[i][0]+1)
    print(max(anser))


Measured memory_bytes: 13132
def ncr(n, r):
	s = 1
	for i in range(n - r + 1, n + 1):
		s = s * i / (i - (n - r))
	return s

a, b = map(int, raw_input().split())
l = map(int, raw_input().split())

c1 = len([i for i in l if i % 2 == 1])
c2 = len([i for i in l if i % 2 == 0])
s1 = 0
s2 = 0

for i in range(c1 + 1):
	if i % 2 == 0:
		s2 += ncr(c1, i)
	else:
		s1 += ncr(c1, i)

s3 = 2 ** c2

if b == 1:
	print s1 * s3
else:
	print s2 * s3

Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
#define LL long long 
#define LLU long long unsigned
#define rarr(arr, n) for(int aab = 0; aab < n; aab++){cin >> arr[aab];}
#define parr(arr, n) for(int aab = 0; aab < n; aab++){cout << arr[aab] << " ";}
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n";

#define freopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);ios_base::sync_with_stdio(0);cin.tie(0);

int main(){   
    int n;
    cin >> n;
    long long int v1[n], ans = 0;
    for(int i = 0; i < n; i++){
		cin >> v1[i];
    }

    for(int i = 0; i < n; i++){
    	for(int j = i + 1; j < n; j++){
    		for(int k = j + 1; k < n; k++){
    			if(v1[i] != v1[j] && v1[i] != v1[k] && v1[j] != v1[k] && v1[i] + v1[j] > v1[k] && v1[i] + v1[k] > v1[j] && v1[j] + v1[k] > v1[i]){
    				ans++;
    			}
    		}
    	}
    }

    cout << ans;
}

Measured memory_bytes: 3632