akhauriyash/Code-Regression huggingface dataset:
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int M, K;

int main(){
  scanf("%d%d", &M, &K);
  int all = pow(2, M);

  if (M == 0){
    if (K == 0) printf("0 0\n");
    else printf("-1\n");
    return 0;
  }

  if (M == 1){
    if (K == 0) printf("0 0 1 1\n");
    else printf("-1\n");
    return 0;
  }

  if (K >= all){
    printf("-1\n"); return 0;
  }

  if (K == 0){
    printf("0");
    for (int i = 1; i < all; i++) printf(" %d", i);
    for (int i = all - 1; i >= 0; i--) printf(" %d", i);
    printf("\n");
    return 0;
  }


  printf("0 %d 0", K);
  for (int i = 1; i < all; i++){
    if (i == K) continue;
    printf(" %d", i);
  }
  printf(" %d", K);
  for (int i = all - 1; i >= 1; i--){
    if (i == K) continue;
    printf(" %d", i);
  }
  printf("\n");



  return 0;
}


Measured memory_bytes: 4176
import java.util.ArrayList;
import java.util.Scanner;

public class Main {


	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		ArrayList<String> word = new ArrayList<String>();

		for(int i = 0; i < n; i++) {
			word.add(sc.next());
		}

		for(String wordContain1:  word) {
			int count = 0;
			for(String wordContain2 : word) {
				if(wordContain1.equals(wordContain2)){
					count++;
				}
			}
			if(count > 1) {
				System.out.println("No");
				return;
			}
		}

		for(int i = 0; i < n - 1; i++) {
			String str1 = word.get(i);
			String str2 = word.get(i + 1);

			String str1l = str1.substring(str1.length() - 1);
			String str2f = str2.substring(0,1);

			if(!(str1l.equals(str2f))) {
				System.out.println("No");
				return;
			}
		}

		System.out.println("Yes");


	}
}

Measured memory_bytes: 23764
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n, *ans, tmp;
	scanf("%d", &n);
	ans = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		ans[i] = 0;
	for (int i = 2; i <= n; i++) {
		scanf("%d", &tmp);
		ans[tmp - 1] += ans[i - 1] + 1;
	}

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

	free(ans);
	return 0;
}

Measured memory_bytes: 2248
N=int(input())
INF=10**9+7
"""
lst=[[
]][i-2][i-1][i]0=A,1=G,2=C,3=T
"""
lst1=[]
lst2=[]
for i in range(4):
    lst2.append((i,0,1))
    lst2.append((i,1,0))
    lst1.append((i,0,2))
for i in range(1,4):
    lst2.append((0,i,1))
    lst2.append((0,1,i))
lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
lst[3][3][3]=1
def LST(lst):
    Lst=[[[0 for i in range(4)] for j in range(4)]for k in range(4)]
    for i in range(4):
        for j in range(4):
            for k in range(4):
                if (i,j,k) in lst2:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][2]=0
                elif (i,j,k) in lst1:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
                    Lst[j][k][1]=0
                else:
                    for h in range(4):
                        Lst[j][k][h]+=lst[i][j][k]%INF
    return Lst
for n in range(N):
    lst=LST(lst)
sum=0
for i in range(4):
    for j in range(4):
        for k in range(4):
            sum+=lst[i][j][k]
print(sum%INF)


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

template<typename t>inline t min_(t a,t b){return a<=b?a:b;}
template<typename t>inline t max_(t a,t b){return a>=b?a:b;}
template<typename t>inline void chkmin(t&a,t b){if(a>b)a=b;}
template<typename t>inline void chkmax(t&a,t b){if(a<b)a=b;}

typedef long long ll;
const int maxn=1e5+10;
int n,rt=-1,ans;
vector<int> g[maxn];

bool dfs(int pos,int fa){
	int cnt0=0,cnt1=0;
	for(int i=0,v;i<g[pos].size();++i)
		if((v=g[pos][i])!=fa){
			if(dfs(v,pos))
				++cnt1;
			else
				++cnt0;
		}
	if(cnt0>1){
		ans+=cnt0-1;
		return true;
	}
	else
		return cnt1>0;
}

int main(){
	cin>>n;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=0;i<n;++i)
		if(g[i].size()>2){
			rt=i;
			break;
		}
	if(rt==-1){
		puts("1");
		return 0;
	}
	dfs(rt,-1);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 9984
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<stdio.h>
using namespace std;
 
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<25
 
int main()
{
	string s;
	cin >> s;
	s[3] = '8';
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n,p = map(int,input().split())
    s = input()

    if p == 2 or p == 5:
        ans = 0
        for i in range(n-1,-1,-1):
            if int(s[i]) % p == 0:
                ans += i+1
        print(ans)
        exit()

    l = [0]*p
    l[0] += 1
    s1 = s[::-1]
    ten = 1
    mod = 0
    for i in range(n):
        mod += int(s1[i])*ten%p
        mod %= p
        ten = ten*10%p
        l[mod] += 1
    ans = 0

    for i in l:
        ans += (i-1)*i//2
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 3500
#include <stdio.h>

int main(){
	char S[3];
	scanf("%c%c%c", &S[0], &S[1], &S[2]);
	if(S[0] != S[1] || S[1] != S[2] || S[0] != S[2]){
		printf("Yes\n");
	}else {
		printf("No\n");
	}
}

Measured memory_bytes: 1596
#include <bits/stdc++.h>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()




using namespace std;

int main(){
  string S; cin>>S;

  REP(i,S.size()){
    if(S[i] == '?') cout<<"D";
    else cout<<S[i];
  }
  cout<<endl;

  return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<long long>csum(200100);
    int a;
    for(int i=0;i<N;i++){
        cin >> a;
        if(i==0) csum[i]=a;
        else csum[i]=csum[i-1]+a;
    }
    long long mi=1e10,dif;
    for(int i=0;i<N-1;i++){
        dif=abs(csum[i]-(csum[N-1]-csum[i]));
        mi=min(mi,dif);
    }
    cout << mi << endl;
}

Measured memory_bytes: 1792
n,q=gets.split.map &:to_i
q.times{
	a,b=gets.split.map &:to_i
	if n==1
		p [a,b].min
	else
		while a!=b
			a>b&&(a,b=b,a)
			b=(b+n-2)/n
		end
		p a
	end
}

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

using namespace std;


int main()
{
  int64_t a,b;

  cin >> a >> b;

  if(a % 2 == b % 2)
    {
      if(a < b)
        {
          cout << a + abs((a - b)/2) << endl;
        }
      else
        {
          cout << b + abs((a - b)/2) << endl;
        }
    }
  else
    {
      cout << "IMPOSSIBLE" << endl;
    }

  return 0;
}


Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
answer = 0
seq = 0
for i,h in enumerate(H):
    if i < 1:
        continue
    if H[i-1] >= H[i]:
        seq += 1
    else:
        seq = 0
    if seq > answer:
        answer = seq
print(answer)

Measured memory_bytes: 15020
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    int l = S.length();
    int R = 0;
    for(int i = 0;i<l/2;i++){
      if(S.charAt(i)!=S.charAt(l-i-1)){
        R++;
      }
    }
    System.out.println(R);
  }
}

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

using namespace std;

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

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

#define CHMIN(a, b) a=min((a), (b))
#define CHMAX(a, b) a=max((a), (b))

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

// len(a, b)=2a+len(a, b-a)=2*2a+len(a, b-2a)=2*(b/a)*a+len(a, b%a)
ll len(ll a, ll b){
	if(a==0){
		return -b;
	}
	if(a>b){
		return len(b, a);
	}
	return 2*(b/a)*a+len(a, b%a);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, x;
	cin>>n>>x;
	cout<<n+len(x, n-x)<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
    int a, b;
    std::cin >> a >> b;
    int c = 0;

    c = a - b * 2;
    if (c > 0)
    {
        std::cout << c << std::endl;
    }
    else
    {
        std::cout << 0 << std::endl;
    }
    
    return 0;
}

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

int main() {
  long N;
  cin>>N;
  vector<int> a(1000005);
  long M=N;
  for(int i=2;i<=sqrt(N);i++){
    while(M%i==0){
      a[i]++;
      M /=i;
    }
  }
  long ans=0;
  if(M!=1) ans++;


  for(int i=2;i<1000005;i++){
    int now=1;
    while(a[i]>=now){
      a[i] -=now;
      ans++;
      now++;
    }
  }
cout<<ans<<endl;
  }


Measured memory_bytes: 7276
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

  int A,B;
  int a[200000];
  int b[200000];
  map <int, int> mpa,mpb;

 int main(){

  int i;

  cin >> A;
  for ( i = 0; i < A; i++ ) cin >> a[i];
  cin >> B;
  for ( i = 0; i < B; i++ ) cin >> b[i];
  

  for ( i = 0; i < A; i++ ) mpa [a[i]]++;
  for ( i = 0; i < B; i++ ) mpb [b[i]]++;

  for ( i = 0; i < B; i++ ){
   int x = b[i];
   if(mpb[x] > mpa[x]){
    cout << "NO" << endl;
    return 0;
   }
  }
   cout << "YES" << endl;
  
 return 0;
}


Measured memory_bytes: 20608
import bisect
import heapq
n,m = map(int,input().split())
A = list(map(int,input().split()))
A = list(map(lambda x: x*(-1), A))


heapq.heapify(A)


for _ in range(m):
  a = -heapq.heappop(A)//2
  heapq.heappush(A,-a)
print(-sum(A))

Measured memory_bytes: 14380
import java.util.*;
import java.io.*;
public class Main{
/// functions
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
// end
static long[] f;
// taking inputs
static BufferedReader s;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
// ends
//......................................@uthor_Alx..............................................

public static void main(String[] args) throws  IOException{
       assign();
       int[] nm=int_arr();
       int x=(nm[0]*(nm[0]-1))/2+nm[1]*(nm[1]-1)/2;
       out.write(x+"");
             
        out.flush();
  }
}


Measured memory_bytes: 21588
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <list>
#define pie 3.141592653589793
#define si(a) scanf("%d",&a)
#define ss(a) scanf("%s",a)
#define sl(a) scanf("%lld",&a)
#define pi(a) printf("%d",a)
#define pl(a) printf("%lld",a)
#define ps(a) printf("%s",a)
#define ll long long
using namespace std;
int main()
{
  string s,t;
  cin >> s >> t;
  int len = s.length();
  int ind=0;
  std::vector<string> v;
  while(true){
    if(ind+t.length()>len)
      break;
    string temp=s;
    int ind1=0;
    bool f=0;
    for(int i=ind;i<s.length();i++){
      if(ind1==t.length())
        break;
      if(temp[i]==t[ind1])
        ind1++;
      else if(temp[i]!=t[ind1]){
        if(temp[i]=='?'){
          temp[i]=t[ind1];
          ind1++;
        }
        else{
          f=1;
          break;
        }
      }
    }
    if(!f){
      for(int i=0;i<temp.length();i++){
        if(temp[i]=='?')
          temp[i]='a';
      }
      v.push_back(temp);
    }
    ind++;
  }
  if(v.size()==0){
    cout << "UNRESTORABLE" << endl;
  }
  else{
    sort(v.begin(),v.end());
    cout << v[0] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#if 0
date +%Y.%m.%d

令 a[n + 1] 为 a 的异或和。
不难发现每次操作 a[x] 等价于交换 a[x] 与 a[n + 1];
那么将 a, b 离散化后，判无解就很简单了。
#endif
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 100005;
int a[maxn], b[maxn];
int tmp[maxn];
int tot[maxn];
int fa[maxn], size[maxn];

int find(int x) {
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

int main() {
	int n = read;

	for(int i = 1; i <= n; i ++) {
		a[i] = read;
		a[n + 1] ^= a[i];
	}

	for(int i = 1; i <= n + 1; i ++)
		tmp[i] = a[i];
	std::sort(tmp + 1, tmp + n + 2);

	for(int i = 1; i <= n + 1; i ++) {
		a[i] = int(std::lower_bound(tmp + 1, tmp + n + 2, a[i]) - tmp);
		++ tot[a[i]];
	}

	for(int i = 1; i <= n; i ++) {
		b[i] = read;
		int x = int(std::lower_bound(tmp + 1, tmp + n + 2, b[i]) - tmp);
		if(tmp[x] != b[i] or !tot[x]) return puts("-1"), 0;
		b[i] = x;
		-- tot[x];
	}

	for(int i = 1; i <= n + 1; i ++) {
		fa[i] = i;
		size[i] = 1;
	}

	int ans = -1;
	for(int i = 1; i <= n; i ++) {
		int x = find(a[i]), y = find(b[i]);
		if(a[i] != b[i]) {
			/* debug("%d - %d\n", tmp[a[i]], tmp[b[i]]); */
			fa[x] = y;
			if(x != y)
				size[y] += size[x];
			++ ans;
		}
	}

	for(int i = 1; i <= n + 1; i ++)
		if(fa[i] == i and size[i] > 1)
			++ ans;

	if(fa[a[n + 1]] == a[n + 1] and size[a[n + 1]] == 1)
		++ ans;

	printf("%d\n", ans == -1 ? 0 : ans);
}


Measured memory_bytes: 4096
#pragma warning(disable: 4996)
#include <iostream>
#include <unordered_map>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

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

	int N, K, h, ans=0;
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> h;
		if (h >= K) ans++;
	}

	cout << ans << endl;

	return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int w, h, x, y, r;
  cin >> w >> h >> x >> y >> r;
  
  if (r <= x && x + r <= w && r <= y && y + r <= h) cout << "Yes\n";
  else cout << "No\n";
}


Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
long double a,b,h,m,c,d1,d2;
int main()
{
	cin>>a>>b>>h>>m;
	d1=m/2.0+h*30.0;
	d2=m*6.0;
	d2=fabs(d1-d2);
	c=sqrt(2.0*a*b)*sqrt((a*a+b*b)/(2.0*a*b)-cos(d2*3.14159265358979323846264338327950L/180.0));
	cout<<fixed<<setprecision(15)<<c; 
}


Measured memory_bytes: 4092
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}
string BinaryNum(int N)
{
        string S;
        while (N != 0)
        {
                if (N % 2 == 1)
                {
                        N--;
                        S = '1' + S;
                }
                else
                {
                        S = '0' + S;
                }
                N /= 2;
        }
        return S;
}

bool binary(vector<int> vec, int key)
{
        int left = 0;
        int right = vec.size();

        while (left < right)
        {
                int mid = (left + right) / 2;
                if (vec[mid] == key)
                {
                        return true;
                }
                else if (vec[mid] > key)
                {
                        right = mid;
                }
                else
                {
                        left = mid + 1;
                }
        }
        return false;
}
int main() //input->compute->output
{
        string Sa, Sb, Sc;
        cin >> Sa >> Sb >> Sc;
        int i = 1;
        int j = 0;
        int k = 0;
        char m = Sa[0];

        while (i <= Sa.length() && j <= Sb.length() && k <= Sc.length()){        
                if (m == 'a')
                {
                        m = Sa[i];
                        i++;
                }
                else if (m == 'b')
                {
                        m = Sb[j];
                        j++;
                }
                else
                {
                        m = Sc[k];
                        k++;
                }
        }
        if (i > Sa.length())
        {
                cout << 'A' << endl;
        }
        else if (j > Sb.length())
        {
                cout << 'B' << endl;
        }
        else
        {
                cout << 'C' << endl;
        }

        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	stack<char> st;
	int ans = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (st.empty() || st.top() == s[i])
			st.push(s[i]);
		else if (st.top() != s[i]) {
			st.pop();
			ans += 2;
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>


int main() {

	int k;
	int i = 0;
	char s[256];
	scanf("%d", &k);
	scanf("%s",s);
	
	while (s[i] != '\0' ) {
		  printf("%c", s[i]);
		  i++;
		  if (k == i)
		  {
			  if (s[i] != '\0') {
				  printf("...");
			  }
			  break;
		  }
		 
	}
	printf("\n");


	return 0;
}


Measured memory_bytes: 1680
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define LIMIT(d_in, d_min, d_max) max(d_min, min(d_max, d_in))
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	string S;
	cin >> S;
	int count0 = 0;
	int count1 = 0;

	for (int i = 0; i < S.size(); i++)
	{
		if (S[i] == '0')
			count0++;
		else
			count1++;
	}

	cout << S.size() - abs(count0 - count1) << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <string.h>
#include <set>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

const int MAX_N = 100000;
ll n, k;
ll a[MAX_N];

int main(){
  cin >> n >> k;
  REP(i, n) cin >> a[i];

  cout << (n - 2) / (k - 1) + 1 << endl;

  return 0;
}


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

int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  int Q; cin >> Q;
  vector<long long> answer;
  for (int q=0; q<Q; q++){
    int k; cin >> k;
    long long D=0, M=0, DM=0, ans=0;
    for (int i=0; i<N; i++){
      if (S[i]=='D'){
        D++;
      } else if (S[i]=='M'){
        M++;
        DM += D;
      } else if (S[i]=='C'){
        ans += DM;
      }
      if (i>=k-1){
        if (S[i-k+1]=='D'){
          DM -= M;
          D--;
        } else if (S[i-k+1]=='M'){
          M--;
        }
      }
    }
    answer.push_back(ans);
  }
  for (auto k: answer) cout << k << endl;
}


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

using namespace std;

int main(void) {
    int n;
    string s, w;

    while (scanf("%d", &n), n) {
        cin.ignore();
        getline(cin, s);
        stringstream ss;

        int i = 0, cnt = 0;
        vector<string> v(n);
        ss << s;
        while (ss >> w) v[i++] = w;

        for (int i = 1; i < n; i+=2) {
            if (!(cnt % 2)) {
                if (v[i] == "ru" || v[i] == "lu") cnt++;
            } else if (cnt % 2) {
                if (v[i] == "rd" || v[i] == "ld") cnt++;
            }
        }

        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
const long long INF = 100000000000;
typedef long long ll;
typedef vector<vector<ll>> Matrix;
Matrix dist; // グラフの距離を格納した2次元配列（隣接行列）
             // d[u][v]は辺e=(u,v)のコスト（辺が存在しない場合はINF、ただしd[i][i]=0）

//ワーシャルフロイド法
void warshall_floyd(int n){                                 // nは頂点数
  for (int i = 0; i < n; i++)     // 経由する頂点
    for (int j = 0; j < n; j++)   // 開始頂点
      for (int k = 0; k < n; k++) // 終端
        dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
}

int main(){
  int n, m, r;
  cin >> n >> m >> r;
  vector<ll> R(r);
  rep(i, r){
    cin >> R[i];
    R[i]--;
  }
  dist = Matrix(n, vector<ll>(n, INF));
  vector<ll> a(m), b(m), c(m);
  for (int i = 0; i < n; i++) dist[i][i] = 0;
  for (int i = 0; i < m; i++){
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]);
    dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]);
  }
  sort(R.begin(), R.end());
  warshall_floyd(n);
  ll ans = 100000000000;
  do{
    ll dis = 0;
    for(int i = 1; i < r; i++){
      dis += dist[R[i-1]][R[i]];
    }
    ans = min(ans, dis);
  } while (next_permutation(R.begin(), R.end()));
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;

int prime(int);


int main(){
  int n,sum;
  while(cin>>n){
    sum=0;
    //   cout<<"aaa"<<endl;
    for(int i=1;i<=n;i++){
      int j=n-i+1;
      //   cout<<prime(i)<<"bb"<<prime(j)<<endl;
      if(prime(i)==1&&prime(j)==1){sum++;}
    }
    cout<<sum<<endl;
  }
  return 0;
}

int prime(int n){
  int i;

  if(n==1)return 0;
  for(i=2;i<=sqrt(n);i++){
    if(n%i==0)return 0;
  }
  return 1;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  string a,b,c;
  cin>>a>>b>>c;
  if((a[a.length()-1]==b[0])&&(b[b.length()-1]==c[0])){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.lang.StringBuilder
import java.util.*

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)
    val s = sc.nextLine()
    println(if (s.replace("hi", "").length == 0) "Yes" else "No")
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 35908
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = Integer.parseInt(sc.next());
        int s = Integer.parseInt(sc.next());
        int ans = 0;
        for (int i = 0; i <= k; i++) {
            for(int j = 0; j <= k; j++) {
                int l = s - i - j;
                if (l >= 0 && l <= k) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 22100
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, k = LI()
flg = [False]*n
for i in range(k):
    d = I()
    a = LI()
    for j in a:
        flg[j-1] = True
ans = 0
for i in range(n):
    if not flg[i]:
        ans += 1
print(ans)

Measured memory_bytes: 68160
import java.util.Arrays;
import java.util.Scanner;

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

    int N = scanner.nextInt();
    long M = scanner.nextInt();
    long V = scanner.nextInt();
    int P = scanner.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) A[i] = scanner.nextInt();
    Arrays.sort(A);
    reverse(A);
    long[] cum = new long[N];
    for (int i = 1; i < N; i++) cum[i] = cum[i - 1] + A[i - 1];

    int count = 0;
    for (int i = 0; i < N; i++) {
      if (i < P) {
        count++;
        continue;
      }
      if (A[i] + M < A[P - 1]) break;
      long cap = M * (P - 1) + M * (N - i);
      cap += (i - P + 1) * (A[i] + M) - (cum[i] - cum[P - 1]);
      if (cap >= M * V) count++;
    }
    System.out.println(count);
  }

  private static void reverse(int[] a) {
    int i = 0;
    int j = a.length - 1;
    while (i < j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
      i++;
      j--;
    }
  }
}


Measured memory_bytes: 52508
# -*- coding: utf-8 -*-


def main():
    """Function."""
    a = str(input())
    b = str(input())

    if len(a) > len(b):
        print("GREATER")
    elif len(b) > len(a):
        print("LESS")
    else:
        flag = 0
        for i in range(len(a)):
            if int(a[i]) > int(b[i]):
                print("GREATER")
                flag = 1
                break
            elif int(a[i]) < int(b[i]):
                print("LESS")
                flag = 1
                break
            else:
                pass
        if flag == 0:
            print("EQUAL")


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
A, B = map(int, input().split())

def gcd(m, n) :
    while n :
        m, n = n, m % n
    return m

ret = 0
x = gcd(A, B)
if x % 2 == 0 :
    ret += 1
    while x % 2 == 0 :
        x //= 2
        
i = 3
while i * i <= x :
    if x % i == 0 :
        ret += 1
        x //= i
        
    while x % i == 0 :
        x //= i
        
    i += 2

if x != 1 :
    ret += 1
print(ret + 1)


Measured memory_bytes: 38896
#include <stdlib.h>
#include <stdio.h>
int compare(const void *a,const void *b){
    if(*(int *)a> *(int *)b) return -1;
    return 1;
}
int main()
{   int n;
    scanf("%d",&n);
    int a[n],b[n],c[n];
    long long takahashi=0,aoki=0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
        c[i]=a[i]+b[i];
        aoki+=b[i];
    }
    qsort(c,n,sizeof(int),compare);
    for(int i=0;i<n;i++){
        if(i%2==0){
            takahashi+=c[i];
        }
    }
    printf("%lld",takahashi-aoki);
    return 0;
}


Measured memory_bytes: 1788
// 2016-12-05
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

struct line { int h, p, q; };

int main() {
	int n, m, a, h, p, q;
	int r[100];
	vector<line> v;
	while (cin >> n >> m >> a, n) {
		v.clear();
		for (int i = 0; i < m; i++) {
			cin >> h >> p >> q;
			line l = {h, p - 1, q - 1};
			v.push_back(l);
		}
		sort(begin(v), end(v), [](const line& x, const line& y) { return x.h < y.h; });
		for (int i = 0; i < n; i++) {
			r[i] = i;
		}
		for (auto l : v) {
			swap(r[l.p], r[l.q]);
		}
		cout << r[a - 1] + 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3176
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define d_5 100000
#define d9_7 998244353
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
ll digitpower(ll a,ll b){//aのb乗を計算
  if(b==1){
    return a;
  }else if(b==0){
    return 1;
  }
  if(b%2==1){
    ll tmp = digitpower(a,(b-1)/2);
    tmp%=d9_7;
    tmp*=tmp;
    tmp%=d9_7;
    tmp*=a;
    return (tmp)%d9_7;
  }else{
    ll tmp = digitpower(a,(b)/2);
    tmp%=d9_7;
    tmp*=tmp;
    tmp%=d9_7;
    return (tmp)%d9_7;
  }
}
int main(void){
  ll n;
  cin>>n;
  vl d(n);
  rep(i,n)cin>>d[i];
  if(d[0]!=0){
    cout<<0;
    return 0;
  }
  rep(i,n){
    if(i!=0&&d[i]==0){
    cout<<0;
    return 0;

    }
  }
  sort(d.begin(),d.end());
  vl d2(n,0);
  rep(i,n){
    d2[d[i]]+=1;
  }
  ll ans=1;
  int begin=0;
  rep(i,n-1){
    if(begin==0 && d2[n-i-1]==0)continue;
    begin=1;
    rep(j,d2[n-i-1]){
      ans*=d2[n-i-2];
      ans%=d9_7;
    }
    //ans*=digitpower(d2[n-i-2],d2[n-i-1]);
    ans%=d9_7;
  }
  cout<<ans%d9_7<<endl;
  return 0;
}

Measured memory_bytes: 1792
#include <vector>
#include <iostream>
using namespace std;
class UnionFind {
private:
	int size_; vector<int> g; vector<vector<int> > v;
public:
	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};
	UnionFind(int size__) : size_(size__) {
		g.resize(size__); v.resize(size__);
		for (int i = 0; i < size__; i++) g[i] = i, v[i] = { i };
	};
	int size() { return size_; }
	int root(int x) { return g[x]; }
	int size(int x) { return v[x].size(); }
	bool same(int x, int y) { return g[x] == g[y]; }
	void unite(int x, int y) {
		x = g[x], y = g[y];
		if (x == y) return;
		if (v[x].size() < v[y].size()) swap(x, y);
		v[x].insert(v[x].end(), v[y].begin(), v[y].end());
		for(auto &e : v[y]) g[e] = x;
		v[y].clear();
	}
	bool operator==(const UnionFind& u) { return g == u.g; }
	bool operator!=(const UnionFind& u) { return g != u.g; }
	int operator[](int x) { return g[x]; }
};
int n, q, c, x, y;
int main() {
	scanf("%d%d", &n, &q);
	UnionFind u(n);
	for(int i = 0; i < q; i++) {
		scanf("%d%d%d", &c, &x, &y);
		if(c) cout << (u.same(x, y) ? 1 : 0) << endl;
		else u.unite(x, y);
	}
}

Measured memory_bytes: 3752
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#include <fstream>
#include <cassert>
#include <cmath>
#include <sstream>
#include <time.h>
#include <complex>

#include <unordered_map>
#include <unordered_set>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define DFOR(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define rep(i,n) FOR(i,0,n)
#define repn(i,n) FORN(i,1,n)
#define drep(i,n) DFOR(i,n-1,0)
#define drepn(i,n) DFOR(i,n,1)
#define MAX(a,b) a = Max(a,b)
#define MIN(a,b) a = Min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define Reset(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(all(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)
#define forever for(;;)
#define PINF 1000000000000
#define newline '\n'

#define test if(1)if(0)cerr
using namespace std;

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
typedef pair<char,char> cc;
typedef vector<ii> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l4;
const double pi = acos(-1.0);



int main()
{
    ios::sync_with_stdio(false);    cin.tie(0);
    const int maxn = 1e5+10;
    int s[maxn] = {0};
    int n, m;   cin >> n >> m;
    rep(i, m)
    {
        int u, v;   cin >> u >> v;
        if (u > v) swap(u, v);
        s[u] += 1;
        s[v] -= 1;
    }
    repn(i, n) s[i] += s[i-1];
    bool work = true;
    for (int i = 1; i < n; ++i)
    {
        if (s[i] % 2)
        {
            work = false;
            break;
        }
    }
    cout << (work?"YES":"NO") << newline;
}




Measured memory_bytes: 640
#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> um(n);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        um[a - 1] = i + 1;
    }
    for (int i = 0; i < n; ++i) {
        cout << um[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
}


Measured memory_bytes: 4736
#include <iostream>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdarg>
#include <set>
#include <limits>
#include <iomanip>

using namespace std;
#define INF 2e9 + 9
#define MOD 1000000007
#define ALL(v) v.begin() , v.end()
#define Int int64_t
#define pll pair<Int,Int>
template<class T> using pql = priority_queue<T, vector<T>>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define ll(n) Int n; cin >> n;
#define LL(...) Int __VA_ARGS___; cin >> __VA_ARGS___;
#define OUT(...) cout << __VA_ARGS___;
#define RP(n, i, s) for(Int i = s ;i < n ;i++)
#define REP(n, i) for (Int i = 0; i < n; i++)
#define REPe(n, i) for (Int i = 1; i <= n; i++)
#define RPe(n, i, s) for (Int i = s; i <= n; i++)
#define upd_max(maxer, updater) if (maxer < updater) maxer = updater;

void ansYes(bool flag) {
    if (flag) cout << "Yes" << endl; else cout << "No" << endl;
}

void ansYES(bool flag) {
    if (flag) cout << "YES" << endl; else cout << "NO" << endl;
}

struct node {
    Int to;
    Int length;
};


vector<Int> divisor(Int n) {
    vector<Int> ret;
    for (Int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    return (ret);
}

/*
vector<vector<int>> to;
vector<int> flag;
vector<int> c;


Int dfs(int from, int mae) {
    flag[from] = 1;
    Int mini = 0;
    for (auto next : to[from]) {
        if (next == mae) continue;
        if (flag[next] == 1) {
            return -1;
        } else {
            mini = min(mini, dfs(next, from));
        }
    }
    return mini;
}*/

int dx8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

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

struct datas {
    Int max;
    Int size;
};

class ContainChecker {
protected:
    Int minx, miny, maxx, maxy;
public:
    ContainChecker(Int minx, Int miny, Int maxx, Int maxy) : minx(minx), miny(miny), maxx(maxx), maxy(maxy) {};

    bool in(Int x, Int y) {
        return (minx <= x && miny <= y && x <= maxx && y <= maxy);
    }
};


int main(void) {
    Int n;
    cin >> n;
    vector<Int> memo(100003);
    REP(n,i){
        Int a,b;
        cin >> a >> b;
        a--; b--;
        memo.at(a)++;
        memo.at(b+1)--;
    }
    Int maxer = 0;
    REP(100002,i){
        memo.at(i+1) += memo.at(i);
        if (i <= memo.at(i)) {
            maxer = max(maxer, i);
        }else{
            //maxer = max(maxer, memo.at(i));
        }
    }
    cout << maxer << endl;
}





Measured memory_bytes: 3640
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(short i = 0; i < n; i++)


int main() {
    int a[3];
    
    cin >> a[0] >> a[1] >> a[2];
    
    sort(a, a + 3);
    
    int ans = a[2] - a[1];
    a[0] += ans;
    if((a[2] - a[0]) % 2 == 0){
        ans += (a[2] - a[0]) / 2;
    }
    else{
        ans += (a[2] - a[0]) / 2;
        ans += 2;
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
import itertools, math

N, M, R = map(int, input().split())
r = list(map(int, input().split()))

adj = [[float('inf')] * (N + 1) for _ in range(N + 1)]

for m in range(M):
    A, B, C = map(int, input().split())
    adj[A][B] = min(adj[A][B], C)
    adj[B][A] = min(adj[B][A], C)

res = float('inf')

for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

for perm in itertools.permutations(r):
    best = 0
    for x, y in zip(perm, perm[1:]):
        best += adj[x][y]
    res = min(res, best)

print(res)

Measured memory_bytes: 73048
#include <bits/stdc++.h>
#define ff { ios_base::sync_with_stdio(false);cin.tie(NULL);}
using namespace std;

typedef long long ll;
 ll  pp=1e9+7; 
double pi=3.141592653589793238;

 int main() {
        ff;
        
        ll x,y;
        cin>>x>>y;
        ll f=0;
        for(int i=0;i<=x;i++){
            ll z=y-2*i;
            if((x-i)*4==z){
                f=1;
                cout<<"Yes"<<endl;
                break;
            }
        }
        if(f==0)cout<<"No"<<endl;
		
    return 0;
}

            
		
        
           
  

Measured memory_bytes: 3648
import java.util.Scanner;
//import java.util.ArrayList;
//import java.util.Arrays;
//import java.util.PriorityQueue;
class Main {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        int n  = stdIn.nextInt();
        long  k = stdIn.nextInt();

        int[] a = new int[n];
        for(int i = 0;i < n;i++) {
            a[i] = stdIn.nextInt();
        }

        long count;
        long t = 1000000007L;

        long x = 0;
        long y = 0;
        for(int i = 0;i < n;i++) {
            for(int j = i+1;j < n;j++){
                if(a[i] > a[j]){
                    x++;
                }
            }
        }
        for(int i = 0;i < n;i++) {
            for(int j = i+1;j < n;j++){
                if(a[i] != a[j]){
                    y++;
                }
            }
        }

        if(k % 2 == 0){
            count = ((((x%t) * k) % t) + (((((y%t) * (k/2)) % t) * (k-1)) % t)) % t;
        }else {
            count = ((((x%t) * k) % t) + (((((y%t) * k) % t) * ((k-1)/2)) % t)) % t;
        }
        

        
        System.out.println(count);

        
    }

}

Measured memory_bytes: 26992
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
using ll=long long;
using P=pair<ll,int>;

int H,W;
#define index(a,b) ((a)*W+(b))
struct node{
    vector<int> to;
    vector<int> cost;
    ll min_cost;
    vector<int> path;
    node(){
        min_cost=INF;
    }
};
void dijkstra(int start_index,vector<node> &nodes){
    priority_queue<P,vector<P>,greater<P>> q;
    nodes[start_index].min_cost=0;
    q.push(P(0,start_index));
    while (q.size()!=0)
    {
        P p=q.top();
        q.pop();
        int v=p.second;
        if(nodes[v].min_cost<p.first)continue;
        for (int i = 0; i < nodes[v].to.size(); i++){
            int to=nodes[v].to[i];
            ll tmp_cost=nodes[v].min_cost+nodes[v].cost[i];
            if(nodes[to].min_cost>tmp_cost){
                nodes[to].min_cost=tmp_cost;
                q.push(P(nodes[to].min_cost,to));
            }
        }
    }

}

int main() {
    cin>>H>>W;
    int Ch,Cw,Dh,Dw;cin>>Ch>>Cw>>Dh>>Dw;
    int start_index=index(Ch-1,Cw-1);
    int goal_index=index(Dh-1,Dw-1);
    vector<vector<bool>> road(H,vector<bool>(W));
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            char S;cin>>S;
            road[i][j]=(S=='.');
        }
    }
    vector<node> nodes(H*W);
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            for (int k = 0; k < 3; k++){
                for (int l = -2*(k!=0); l < 3; l++){
                    if(k==0&&l==0)continue;
                    if(!road[i][j])continue;
                    if(i+k<H&&0<=j+l&&j+l<W){
                        if(road[i+k][j+l]){
                            nodes[index(i,j)].to.push_back(index(i+k,j+l));
                            nodes[index(i+k,j+l)].to.push_back(index(i,j));
                            nodes[index(i,j)].cost.push_back((k+abs(l)!=1)*1);
                            nodes[index(i+k,j+l)].cost.push_back((k+abs(l)!=1)*1);
                        }
                    }
                }
            }
        }
    }
    dijkstra(start_index,nodes);
    if(nodes[goal_index].min_cost==INF)cout<<-1<<endl;
    else cout<<nodes[goal_index].min_cost<<endl;

}

Measured memory_bytes: 159492
#ARC051C

sx,sy,tx,ty=map(int,raw_input().split())
x=tx-sx
y=ty-sy
print 'R'*x+'U'*y+'L'*x+'D'*y+'D'+'R'*(x+1)+'U'*(y+1)+'L'+'U'+'L'*(x+1)+'D'*(y+1)+'R'


Measured memory_bytes: 2568
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	int x;
	cin>>x;
	int ans;
	if(x>=400&&x<=599)
	ans=8;
	if(x>=600&&x<=799)
	ans=7;
	if(x>=800&&x<=999)
	ans=6;
	if(x>=1000&&x<=1199)
	ans=5;
	if(x>=1200&&x<=1399)
	ans=4;
	if(x>=1400&&x<=1599)
	ans=3;
	if(x>=1600&&x<=1799)
	ans=2;
	if(x>=1800&&x<=1999)
	ans=1;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3632
//#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>
//#include <stdio.h>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
typedef long long LL;
typedef long double LD;
//typedef boost::multiprecision::cpp_int bigint;
typedef pair<LL, LL> PLL;
typedef pair<int, int> PI;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef unsigned long long ULL;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int N;
	cin >> N;
	VI count(24, 0);
	VI D(N);
	for (int n = 0; n < N; n++) {
		cin >> D[n];
		count[D[n]]++;
		if (D[n] == 0 || count[D[n]] >= 3) {
			cout << 0 << "\n";
			return 0;
		}
	}
	int ans = 0;
	for (int c = 0; c < (1 << N); c++) {
		//0->早いほう、1->遅いほう
		for (int n = 0; n <= 23; n++) count[n] = 0;
		count[0] = 1;
		for (int n = 0; n < N; n++) {
			if ((c & (1 << n)) != 0)count[24 - D[n]]++;
			else count[D[n]]++;
		}
		int t = 0;
		for (; t <= 23; t++) {
			if (count[t] >= 2)break;
		}
		if (t != 24)continue;
		int temp = 0;
		for (int d = 1; d <= 23; d++) {
			for (t = 0; t < 23; t++) {
				if (count[t] == 0)continue;
				int tt = t + d;
				if (tt >= 24)tt -= 24;
				if (count[tt] != 0) {
					temp = d;
					break;
				}
			}
			if (temp != 0)break;
		}
		ans = max(ans, temp);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 3200
#include<stdio.h>
int main()
{
  int N,K,X,Y;
  int gokei=0;
  
  scanf("%d\n%d\n%d\n%d\n",&N,&K,&X,&Y);
  
  for(int i=1;i<=N;i++){
    if(i<=K) gokei+=X;
    else gokei+=Y;
  }
  
  printf("%d",gokei);
  
  return 0;
}

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

int main() {
  string s; cin >> s;
  int x = 700;
    if(s[0] == 'o') x += 100;
    if(s[1] == 'o') x += 100;
    if(s[2] == 'o') x += 100;
  cout << x;
}

Measured memory_bytes: 256
class BIT:
    def __init__(self, n):  # 1-indexed
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()

    def bitmax(self, i):
        ret = 0
        while i:
            ret = max(ret, self.tree[i])
            i ^= i & -i
        return ret

    def bitadd(self, i, x):  # i > 0
        while i <= self.size:
            if self.tree[i] >= x:
                break
            self.tree[i] = x
            i += i & -i
        return
      
n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
b = BIT(max(h) + 5)
for x, y in zip(h, a):
    b.bitadd(x, b.bitmax(x) + y)
print(b.bitmax(max(h)))

Measured memory_bytes: 35972
n = gets.to_i
s = gets.chomp

min = s[1...n].delete('W').size
cnt = min

(1...n).each do |i|
  if s[i] == 'E'
    cnt -= 1
  end
  if s[i - 1] == 'W'
    cnt += 1
  end
  min = cnt if cnt < min
end
puts min

Measured memory_bytes: 2820
/*
 * @Author: Kaizyn
 * @Date: 2020-06-13 19:58:06
 * @LastEditTime: 2020-06-21 17:36:14
 */ 
#include <bits/stdc++.h>

// #define DEBUG

using namespace std;

const double eps = 1e-7;
const double PI = acos(-1);
typedef pair<int, int> pii;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int N = 2e5+7;

int n, k;
int a[N];
int add[N];

inline void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int t = 1, cnt; t <= k; ++t) {
    memset(add+1, 0, sizeof(int)*n);
    for (int i = 1; i <= n; ++i) {
      ++add[max(1, i-a[i])];
      --add[min(n+1, i+a[i]+1)];
    }
    cnt = 0;
    for (int i = 1; i <= n; ++i) {
      a[i] = a[i-1]+add[i];
      cnt += a[i] == n;
    }
    if (cnt == n) break;
  }
  for (int i = 1; i <= n; ++i) {
    cout << a[i] << " \n"[i==n];
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int T = 1;
  // cin >> T;
  for (int t = 1; t <= T; ++t) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 5212
input_data = [input().split(" ") for _ in range(9)]
data = [(name, int(count1) + int(count2), int(count1) * 200 + int(count2) * 300) for name, count1, count2 in input_data]
output_data = [name + " " + str(count) + " " + str(price) for name, count, price in data]
print("\n".join(output_data))



Measured memory_bytes: 5600