akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int odd = 0;
		String tmp;

		for (int i = 1; i <= N; i++) {
			tmp = String.valueOf(i);
			if (tmp.length() % 2 != 0) {
				odd++;
			}
		}
		System.out.println(odd);
		sc.close();
	}
}

Measured memory_bytes: 26196
import math

n = int(input())

nums = []
[nums.append(int(input())) for _ in range(n)]

answer = 0
for i in range(n):
    count = 0
    dest = int(math.sqrt(nums[i])) + 1

    prime = True
    for j in range(2, dest):
        if nums[i] % j == 0:
            prime = False
            break

    if (nums[i] != 1) and prime:
        answer += 1

print(answer)


Measured memory_bytes: 6156
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();

		while (true) {
			draw(h,w);
			System.out.println();
			h = sc.nextInt();
			w = sc.nextInt();
			if (h == 0 && w == 0)
				break;
		}

	}

	public static void draw(int h, int w) {
		for (int i = 0; i < h; i++) {
			for(int j = 0; j < w; j++){
				System.out.print("#");
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 26788
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    if(a%1000==0){

      System.out.println(0);
      return;
    }
    System.out.println(1000 -a%1000);
  }
  
}



Measured memory_bytes: 35580
#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, x[200005], ca[200005], cb[200005], ans, ta, tb, tc;
 
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", x + i);
		ta = max(0, x[i] - ca[x[i]]);
		ca[x[i]]++;
		cb[ta]++;
	}
	for (int i = 1; i <= n; i++)
		ans += (cb[i] == 0);
	while (m--) {
		scanf("%d%d", &ta, &tb);
		ca[x[ta]]--;
		tc = max(0, x[ta] - ca[x[ta]]);
		cb[tc]--;
		if (tc && !cb[tc])
			ans++;
		x[ta] = tb;
		tc = max(0, x[ta] - ca[x[ta]]);
		ca[x[ta]]++;
		if (tc && !cb[tc])
			ans--;
		cb[tc]++;
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

int main(){
    string S,T;
    cin >> S >> T;
    vector<string> ANS;
    if(S.length()<T.length()){
        cout<<"UNRESTORABLE";
        return 0;
    }
    for(int i=0;i<=S.length()-T.length();i++){
        bool can=true;
        for(int j=0;j<T.length();j++){
            if(S[i+j]=='?') continue;
            if(S[i+j]!=T[j]) can=false;
        }
        if(can){
            string A=S.substr(0,i);
            A+=T;
            A+=S.substr(i+T.length());
            for(int k=0;k<A.size();k++) if(A[k]=='?') A[k]='a';
            ANS.push_back(A);
        }
    }
    if(ANS.size()==0){
        cout<<"UNRESTORABLE";
        return 0;
    }
    sort(ANS.begin(),ANS.end());
    cout<<ANS[0];
}

Measured memory_bytes: 256
tmp=input().split()
H,W=int(tmp[0]),int(tmp[1])
map = [['a' for x in range(W)] for y in range(H)]
countroad = 0
for i in range(H):
    tmp = input()
    for j in range(W):
        map[i][j] = tmp[j]
        if tmp[j] =='.':
            countroad += 1
count = 0
queue = [0]
check = [0]
dx,dy=0,0

def walkmap(pos1,pos2):
    if 0<=pos1 and pos1<H and 0<=pos2 and pos2<W:
        if map[pos1][pos2] == '.':
            mapIndex=pos1*W+pos2
            if mapIndex not in check:
                queue.append(mapIndex)
                check.append(mapIndex)
minstep = -1
while len(queue) > 0:
    count += 1
    #judge Goal
    if (H*W-1) in queue:
        minstep = count
        break
    target = len(queue)
    for j in range(target):
        #next walk
        dx = int(queue[0]/W)
        dy = int(queue[0]%W)
        queue.pop(0)
        walkmap(dx-1,dy)
        walkmap(dx+1,dy)
        walkmap(dx,dy-1)
        walkmap(dx,dy+1)
if minstep > 0:
    print(countroad-minstep)
else:
    print(minstep)

Measured memory_bytes: 3064
s = input()
s_set = list(set(s))    #重複削除

s_set.sort()

chk = list("abcdefghijklmnopqrstuvwxyz")

i = 0

while 1:
    if s_set[i] != chk[i]:
        print(chk[i])
        break
    i += 1
    
    if i >= (len(s_set)):
        print(chk[i])
        break
    if i >= 25:
        print("None")
        break

Measured memory_bytes: 3188
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using Enu = System.Linq.Enumerable;

public class Program
{
    public void Solve()
    {
        int N = Reader.Int(), A = Reader.Int(), B = Reader.Int();
        var S = Reader.String();
        var passed = new int[2];
        var ans = new int[N];

        for (int i = 0; i < N; i++)
            if (S[i] == 'a')
                passed[0] += ans[i] = passed.Sum() < A + B ? 1 : 0;
            else if (S[i] == 'b')
                passed[1] += ans[i] = passed.Sum() < A + B && passed[1] < B ? 1 : 0;

        Console.WriteLine(string.Join("\n", ans.Select(x => x == 1 ? "Yes" : "No")));
    }
}


class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
    static TextReader reader = Console.In;
    static readonly char[] separator = { ' ' };
    static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
    static string[] A = new string[0];
    static int i;
    static void Init() { A = new string[0]; }
    public static void Set(TextReader r) { reader = r; Init(); }
    public static void Set(string file) { reader = new StreamReader(file); Init(); }
    public static bool HasNext() { return CheckNext(); }
    public static string String() { return Next(); }
    public static int Int() { return int.Parse(Next()); }
    public static long Long() { return long.Parse(Next()); }
    public static double Double() { return double.Parse(Next()); }
    public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
    public static int[] IntArray(int N) { return Range(N, Int); }
    public static int[][] IntTable(int H) { return Range(H, IntLine); }
    public static string[] StringArray(int N) { return Range(N, Next); }
    public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
    public static string Line() { return reader.ReadLine().Trim(); }
    static string[] Split(string s) { return s.Split(separator, op); }
    static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
    static string Next() { CheckNext(); return A[i++]; }
    static bool CheckNext()
    {
        if (i < A.Length) return true;
        string line = reader.ReadLine();
        if (line == null) return false;
        if (line == "") return CheckNext();
        A = Split(line);
        i = 0;
        return true;
    }
}

Measured memory_bytes: 9944
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/math/tools/minima.hpp>

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

namespace adaptor = boost::adaptors;
using namespace std;
using boost::math::tools::brent_find_minima;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::split;
using boost::algorithm::replace_all;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP

void	Main()
{
	string	s;
	cin >> s;

	int z;
	int o;
	z = 0;
	o = 0;
	rep(i, s.size())
	{
		if (s.at(i) == '0')
			z++;
		else
			o++;
	}
	cout << 2 * min(z, o) << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 512
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    Array.Sort(nums);
    
		Console.WriteLine(nums[n/2]-nums[n/2-1]);
	}
}

Measured memory_bytes: 21344
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 1e9;

vector<int> to[2505];
vector<int> rto[2505];
bool reachableFrom1[2505];
bool reachableToN[2505];
bool ok[2505];

void dfs(int v) {

    if(reachableFrom1[v]) {
        return;
    }

    reachableFrom1[v] = true;
    
    for(int u : to[v]) {
        dfs(u);
    }
}

void rdfs(int v) {

    if(reachableToN[v]) {
        return;
    }

    reachableToN[v] = true;
    
    for(int u : rto[v]) {
        rdfs(u);
    }
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;

    vector<tuple<int, int, int>> edges;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;  b--;
        c -= p;
        c *= -1;
        edges.emplace_back(a, b, c);
        to[a].push_back(b);
        rto[b].push_back(a);
    }

    dfs(0);
    rdfs(n-1);

    rep(i, n) {
        ok[i] = reachableFrom1[i] && reachableToN[i];
    }

    vector<int> dist(n, INF);

    dist[0] = 0;
    bool upd = true;
    int step = 0;
    while(upd) {

        upd = false;
        
        rep(i, m) {
            int a, b, c;
            tie(a, b, c) = edges[i];

            if(!ok[a] || !ok[b]) {
                continue;
            }

            int newD = dist[a] + c;
            if(newD < dist[b]) {
                upd = true;
                dist[b] = newD;
            }
        }

        step++;

        if(step > n) {
            cout << -1 << endl;
            return 0;
        }
        
    }

    int ans = max(0, -dist[n-1]);

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

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <locale>
#include <iomanip>

#define nl '\n';

using namespace std;

int x;
string s;

int main(){

    cin >> s;

    x = s.length();

    set<char> se;

    for(int i = 0; i < x; i++){
        se.insert(s[i]);
    }

    if(x == se.size()){
        cout << "yes";
    } else{
        cout << "no";
    }





}

//g++ -std=c++14 comp.cpp -o b; ./b.exe
//g++ -std=c++14 comp.cpp && ./a.out

// char** arr = new char*[r];
// for(long long i = 0; i < r; i++) arr[i] = new char[c];

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

const int INF=1001001001;

int main(){
  int n,x,y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> ans(n);
  for(int sx=0;sx<n;++sx){
    vector<int> dist(n,INF);
    queue<int> q;
    q.push(sx);
    dist[sx]=0;
    while(!q.empty()){
      int v=q.front();
      int d=dist[v];
      q.pop();
      if(dist[v-1]==INF && v-1>=0){
        dist[v-1]=d+1;
        q.push(v-1);
      }
      if(dist[v+1]==INF && v+1<n){
        dist[v+1]=d+1;
        q.push(v+1);
      }
      if(v==x && dist[y]==INF){
        dist[y]=d+1;
        q.push(y);
      }
      if(v==y && dist[x]==INF){
        dist[x]=d+1;
        q.push(x);
      }
    }
    for(int i=0;i<n;++i){
      ans[dist[i]]++;
    }
  }
  for(int i=0;i<n;++i){
    ans[i]/=2;
  }
  for(int i=1;i<=n-1;++i){
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 256
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)
  
if N==1:
  print("POSSIBLE")
  exit(0)

stack=[]
stack.append([0,2,-1])
while stack:
  node=stack.pop()
  v=node[0]
  ship=node[1]
  parent=node[2]
  if v==N-1 and ship==0:
    print("POSSIBLE")
    break
  if ship<=0:
    continue
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,ship-1,v])
else:
  print("IMPOSSIBLE")


Measured memory_bytes: 47932
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define r0 return 0;
#define f(k,i,n,j) for(ll k=i;k<=n;k=k+j)
#define cin(a) cin>>a;
#define loop while(t--)
#define vi vector<int>
#define vii vector<long long int>
#define SORT(v) sort(v.begin(),v.end());
int main()
{
    
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)
    {
        s[i]='x';
    }
    cout<<s<<endl;
}

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

using namespace std;
typedef long long ll;

int main(){
    ll a,b; cin >> a >> b;
    
    ll temp = a * b;
    if(temp < 0) cout << "Zero" << endl;
    
    else if(a == 0) cout << "Zero" << endl;
    
    else if(a > 0) cout << "Positive" << endl;
    
    else if((b - a + 1) % 2 != 0) cout << "Negative" << endl;
    
    else cout << "Positive" << endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            String S = in.next();

            for (int i = 0; i < S.length(); i++) {
                if (i % 2 != 0) continue;
                out.print(S.charAt(i));
            }
            out.println();

        }

    }
}



Measured memory_bytes: 24172
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
    int A, B, H, M;
    cin >> A >> B >> H >> M;
    double angle;
    angle = (H * 60. + M) / 2. - M * 6;
    angle = min(abs(angle), 360. - abs(angle));
    double ans;
    ans = sqrt((A * A) + (B * B) - (2. * A * B * cos(angle / 180. * M_PI)));
    cout << fixed << setprecision(20) << ans << endl;
    return 0;
}




Measured memory_bytes: 4184
N,M = map(int,input().split())

L=[]
R=[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)

ans_min,ans_max=L[0],R[0]

def compare(min_,max_,min_i,max_i):
  if max_<min_i:
    ret_min,ret_max = -1,-1
  elif min_>max_i:
    ret_min,ret_max = -1,-1
  elif (min_<=min_i) and (min_i<=max_) and (max_<=max_i):
    ret_min,ret_max = min_i,max_
  elif (min_>=min_i) and (max_<=max_i):
    ret_min,ret_max = min_,max_
  elif (min_>=min_i) and (min_<=max_i) and (max_>=max_i):
    ret_min,ret_max = min_,max_i
  elif (min_<=min_i) and (max_i<=max_):
    ret_min,ret_max = min_i,max_i
  else:
    pass
#    print("else!")
  return ret_min,ret_max

for i in range(1,M):
  ans_min,ans_max = compare(ans_min,ans_max,L[i],R[i])
  if ans_min==-1 and ans_max==-1:
    ans_min=N+1
    break
#print("End",ans_min,ans_max)
if ans_min<=N:
  if ans_max<=N:
    print(ans_max-ans_min+1)
  else:
    print(N-ans_min+1)
else:
  print(0)

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;
typedef long long LL;
using Graph = vector<vector<int>>;

static long long INF = (1LL<<62);

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

	LL N;
	vector<LL> A;
	cin >> N;
	for(int i=0; i<N; i++){
		LL a;
		cin >> a;
		A.push_back(a);
	}

	LL ans = 0;
	LL mx = A[0];
	for(int i=1; i<N; i++){
		if(A[i] < mx){
			ans += (mx - A[i]);
		}
		else{
			mx = A[i];
		}
	}
	printf("%lld\n", ans);
	return 0;
}



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

#define endl '\n'
#define lfs cout<<fixed<<setprecision(10)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>&v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>&v,ll n){if(n!=0)cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};
template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}
ostream &operator<<(ostream &os, pair<ll, ll>&p){
  return os << p.first << " " << p.second;
}  
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll a,b,k;cin>>a>>b>>k;
  cout<<max(0LL,a-k) spa max(0LL,b-max(0LL,(k-a)))<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  
  int A, B;
  scanf("%d",&A);
  scanf("%d",&B);
  std::cout<<std::max(0,A-2*B) << std::endl;
  return 0;
}


Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
signed main(){
	int n,s;
	cin>>n>>s;
	vvi in(n,vi(2));
	rep(i,n)rep(j,2)cin>>in[i][j];
	
	vi out;
	int l=0,r=n-1;
	while(l<=r){
		if(s<in[l][0]){
			out.pb(in[r][0]);
			break;
		}
		if(in[r][0]<s){
			out.pb(in[l][0]);
			break;
		}
		if(in[l][1]>=in[r][1])out.pb(in[r][0]),in[l][1]+=in[r][1],r--;
		else out.pb(in[l][0]),in[r][1]+=in[l][1],l++;
	}
	out.pb(s);
	int sum=0;
	rep(i,out.size()-1)sum+=abs(out[i+1]-out[i]);
	cout<<sum<<endl;
}
















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

namespace AtCoder.Beginner112
{
    public class ABC112A
    {
        public static void Main(string[] args)
        {
            string age = Console.ReadLine();

            if (age == "1")
            {
                Console.WriteLine("Hello World");
            }
            else
            {
                string A = Console.ReadLine();
                string B = Console.ReadLine();
                Console.WriteLine(int.Parse(A) + int.Parse(B));
            }
        }
    }
}

Measured memory_bytes: 11220
#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() {
  int n;
  cin >> n;
  map<int, int> ans;
  for(int x=1;x<=100;x++) {
    for(int y=1;y<=100;y++) {
      for(int z=1;z<=100;z++) {
        int n = x*x + y*y + z*z + x*y + y*z + z*x;
        ans[n]++;
      }
    }
  }

  for(int i=1;i<=n;i++) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 5420
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

void solve();
int main() {
	solve();
#ifdef DBG
	while (true);
#endif
}

void solve() {
	ll n, A[200001];
	scanf("%lld", &n);
	A[0] = 0;
	for (ll i = 1; i <= n; i++)
		scanf("%lld", A + i), A[i] += A[i - 1];
	sort(A, A + n + 1);
	ll count = 0, carry = 1;
	for (ll i = 1; i <= n; i++) {
		if (A[i] == A[i - 1])
			carry++;
		else {
			count += carry * (carry - 1) / 2;
			carry = 1;
		}
	}
	count += carry * (carry - 1) / 2;
	printf("%lld\n", count);
}

Measured memory_bytes: 1664
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	long long n,x;
	scanf("%lld%lld",&n,&x);
	if(__gcd(n,x)!=1)
	{
		printf("%lld",__gcd(n,x)*3*(n/__gcd(n,x)-1));
		return 0;
	}
	printf("%lld",(n-1)*3);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <unordered_map>
#include <vector>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 2;
int a, b;

void Read(){
	cin >> a >> b;
	// x + y = a
	// 2x + 4y = b
	//Dx = 4a - b
	//Dy = b-2a
	//D = 2
}

void Solve(){
	int Dx = 4 * a - b;
	int Dy = b - 2 * a;
	if(Dx < 0 || Dy < 0 || (Dx & 1) || (Dy & 1))
		cout << "No";
	else
		cout << "Yes";
}

main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Read();
	Solve();
}


Measured memory_bytes: 3652
let get_int () = Scanf.scanf "%d " (fun v -> v)
let input_int_array n =
	Array.init n (fun _ -> Scanf.scanf "%d " (fun v -> v))

let () =
  let n = get_int ()
  in let ls = input_int_array n |> Array.to_list
  in 
  List.filter (fun v -> v mod 2 = 1) ls
  |> List.length
  |> (fun v -> if v mod 2 = 0 then "YES" else "NO")
  |> print_endline

Measured memory_bytes: 6272
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdlib>  
#include <cmath>
using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  int blank=1;
  int ans=0;
  while(blank < b){
    blank += a-1;
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <tuple>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <random>
#include <cstdlib>
#define INT_MAX 2147483647
#define INT_MIN -2147483646
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
using namespace std;
typedef long long int ll;

int main() {
	priority_queue<int> pq;
	string str;
	int k;
	while (1) {
		cin >> str;
		if (str == "insert") {
			cin >> k;
			pq.push(k);
		}
		else if (str == "extract") {
			cout << pq.top() << endl;
			pq.pop();
		}
		else if (str == "end") {
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 7004
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// ??§?¨????????´?????????????????????????
	class Pair {
		int cost, y, x, lr;
		Pair(int c, int y, int x, int lr) {
			this.cost = c;
			this.y = y;
			this.x = x;
			this.lr = lr;
		}
	}
	
	static final int INF = Integer.MAX_VALUE;
	static final int LEFT  = 0;
	static final int RIGHT = 1;
	
	static char[][] map;
	static int w;
	static int h;

	static int[] right_y = {-2, -1, 0, 1, 2, -1, 0, 1, 0};
	static int[] right_x = { 1,  1, 1, 1, 1,  2, 2, 2, 3};
	static int[] left_y =  { 0, -1,  0,  1, -2, -1,  0,  1,  2};
	static int[] left_x =  {-3, -2, -2, -2, -1, -1, -1, -1, -1};
	
	void run() {
		Scanner scan = new Scanner(System.in);
		while (true) {
			w = scan.nextInt();
			h = scan.nextInt();
			if (w + h == 0)
				break;
			map = new char[h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++)
					map[i][j] = scan.next().charAt(0);
			}
			
			System.out.println(solve());
		}
	}
	
	int solve() {
		// ??????????????¨?????????
		int[][][] dp = new int[h][w][2];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] != 'S') {
					dp[i][j][0] = INF;
					dp[i][j][1] = INF;
				} else {
					dp[i][j][0] = 0;
					dp[i][j][1] = 0;
				}
			}
		}
		
		/** ????????\??£?????????????¢????
		System.out.printf("w = %d, h = %d\n", w, h);
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++)
				System.out.print(map[i][j] + " ");
			System.out.println();
		}
		System.out.println();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (dp[i][j][0] == INF) {
					System.out.print("F ");
				} else {
					System.out.print(dp[i][j][0] + " ");
				}
			}
			System.out.println();
		}
		*/
		
		Queue<Pair> que = new PriorityQueue<Pair>(new Comparator<Pair>() {
			@Override
			public int compare(Pair o1, Pair o2) {
				return o1.cost - o2.cost;
			}
		});
		for (int j = 0; j < w; j++) {
			if (map[h - 1][j] == 'S') {
				que.add(new Pair(0, h - 1,j, LEFT));
				que.add(new Pair(0, h - 1,j, RIGHT));
			}
		}
		
		while(!que.isEmpty()) {
			Pair pair = que.poll();
			if (map[pair.y][pair.x] == 'T')
				return pair.cost;
			
//			if (dp[pair.y][pair.x][pair.lr] < pair.cost)
//				continue;
			int[] move_h, move_w;
			if (pair.lr == RIGHT) {
				move_h = right_y;
				move_w = right_x;
			} else {
				move_h = left_y;
				move_w = left_x;
			}
			
			for (int j = 0; j < 9; j++) {
				int my = pair.y + move_h[j];
				int mx = pair.x + move_w[j];
				if (my < 0 || mx < 0 || my >= h || mx >= w)
					continue;
				if (map[my][mx] == 'X' || map[my][mx] == 'S')
					continue;
				
				if (map[my][mx] == 'T') {
					dp[my][mx][pair.lr] = pair.cost;
					que.add(new Pair(pair.cost, my, mx, 1 - pair.lr));
					continue;
				}
				int cost = pair.cost + (int)(map[my][mx] - '0');
				if (cost <= dp[my][mx][pair.lr]) {
					dp[my][mx][pair.lr] = cost;
					que.add(new Pair(cost, my , mx, 1 - pair.lr));
				}
			}
		}
		return -1;
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 70524
// AOJ 1320: City Merger
// 2017.12.31 bal4u@uu

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

#define INF 0x70707070
char *city[16]; int csz[16];
char name[16][22]; int nsz[16]; char f[16];
int cost[16][16];
int dp[65536][16];

int naiveMatch(char *text, int len, char *pattern, int patlen)
{
    char c;
    char *tp, *pp;
    char *textEnd, *patEnd;

    if (len < patlen) return 0;

    textEnd = text + len - patlen + 1;
    patEnd  = pattern + patlen;

    c = *pattern++;
    while (text != textEnd) {
        if (*text++ == c) {
            tp = text;
            pp = pattern;
            do if (pp == patEnd) return 1;
            while (*tp++ == *pp++);
        }
    }
    return 0;
}

int calc(char *a, int alen, char *b)
{
	int k;

	for (k = alen-1; k > 0; k--) {
		if (*++a == *b && !memcmp(a, b, k)) return k;
	}
	return 0;
}

int main()
{
	int n, i, j, k, s, lim, ans;

	while (scanf("%d", &n) && n > 0) {
		for (i = 0; i < n; i++) {
			scanf("%s", name[i]), nsz[i] = strlen(name[i]);
		}

		memset(f, 0, sizeof(f));
		for (i = 0; i < n; i++) {
			if (f[i]) continue;
			for (j = 0; j < n; j++) if (j != i) {
				if (naiveMatch(name[i], nsz[i], name[j], nsz[j])) f[j] = 1;
			}
		}

		k = 0;
		for (i = 0; i < n; i++) {
			if (f[i]) continue;
			city[k] = name[i], csz[k++] = nsz[i];
		}
		n = k;

		for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
			if (j == i) cost[i][j] = csz[i];
			else cost[i][j] = csz[j] - calc(city[i], csz[i], city[j]);
		}

		memset(dp, INF, sizeof(dp));
		for (i = 0; i < n; i++) dp[1<<i][i] = csz[i];

		lim = (1<<n) - 1;
		for (s = 0; s <= lim; s++) {
			for (i = 0; i < n; i++) if ((s >> i) & 1) {
				for (j = 0; j < n; j++) {
					if ((s >> j) & 1) continue;
					k = dp[s][i] + cost[i][j];
					if (k < dp[s|(1<<j)][j]) dp[s|(1<<j)][j] = k;
				}
			}
		}

		ans = INF;
		for (i = 0; i < n; i++) {
			k = dp[lim][i];
			if (k < ans) ans = k;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 5952
N, C = map(int, input().split())
S = [[0, 0, 0] for i in range(N + 2)]
L = [[0, 0, 0] for i in range(N + 2)]
R = [[0, 0, 0] for i in range(N + 2)]
for i in range(N):
  x, v = map(int, input().split())
  S[i + 1] = [v, x, C - x]
  L[i + 1][0] = L[i][0] - x + S[i][1] + v
  L[i + 1][1] = L[i + 1][0] - x
  L[i + 2][2] = max(L[i + 1][2], L[i + 1][1])
for i in range(N, 0, -1):
  R[i][0] = R[i + 1][0] - S[i][2] + S[i + 1][2] + S[i][0]
  R[i][1] = R[i][0] - S[i][2]
  R[i - 1][2] = max(R[i][2], R[i][1])
ans = 0
for i in range(N + 1):
  ans = max(L[i][0] + R[i][2], L[i][2] + R[i][0], ans)
print(ans)

Measured memory_bytes: 57620
s = input()
k = int(input())
c = []
for i in range(len(s)):
    for j in range(k): c.append(s[i:i+j+1])
c.sort()
pre = ''
for x in c:
    if pre == x: continue
    k -= 1
    if k == 0:
        print(x)
        break
    pre = x


Measured memory_bytes: 4340
n = int(input())
t = list(map(int, input().split()))
m = int(input())
px = [map(int, input().split()) for _ in range(m)]
p, x = [list(i) for i in zip(*px)]
t_c = t[:]
for i in range(m):
    t[p[i]-1] = x[i]
    print(sum(t))
    t[p[i]-1] = t_c[p[i]-1]


Measured memory_bytes: 3064
#include<iostream>

using namespace std;
using P = pair<int, int>;

int map[22][22];

P dirs[] = {P(1, 0), P(-1, 0), P(0, 1), P(0, -1)};

int dfs(int h, int w) {
    if (!map[h][w]) return 0;
    map[h][w] = 0;
    int ans = 0;
    for (P dir : dirs) {
        ans += dfs(h + dir.first, w + dir.second);
    }
    return ans + 1;
}

int main() {
    while (1) {
        int w, h;
        cin >> w >> h;
        if (w == 0) break;

        for (int i = 0; i < 22; ++i)
            for (int j = 0; j < 22; ++j)
                map[i][j] = 0;
        
        int pw, ph;
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                char c;
                cin >> c;
                if (c == '.') map[i][j] = 1;
                if (c == '@') { 
                    map[i][j] = 1;
                    ph = i;
                    pw = j;
                }
            }
        }
        cout << dfs(ph, pw) << endl;
    }
}

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

using namespace std;
/*
2 3 1
1 2 2
4
*/
int mx;

struct type{
	int a,b,c,d;
	void read(){
		cin >> a >> b >> c >> d;
		a--,b--;
	}
	void pr(){
		cout << a << " " << b << " " << c << "  " << d << "\n";
	}
};
int n,m,q;
vector<type> w; 
vector<int> a;
void f(int last,int id){
	if(id==n){
		int r = 0;
		for(int i = 0; i < q; i++){
			if(a[w[i].b] - a[w[i].a]==w[i].c)
				r+=w[i].d;
//			cout << a[w[i].b] << " " << a[w[i].a] << "\n";  
		}
		mx = max(mx,r);
		return;
	}
	for(int i = last; i <= m; i++){
		a[id] = i;
		f(i,id+1);
	}
}


int main(){
	cin >>  n >> m >> q;
	a.resize(n);
	for(int i = 0; i < q; i++){
		type X;
		X.read();
		w.push_back(X);
	}
	
	f(1,0);
	cout << mx << "\n";
	return 0;
}


Measured memory_bytes: 3584
#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>;
using G = vector<vector<int>>;
    
int main(){
    int l, r, d;
    cin >> l >> r >> d;
    int n1, n2;
    n1 = (l-1) / d;
    n2 = r / d;
    int ans = n2 - n1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3588
#include<stdio.h>
int main()
{
	int a, b, c, d, e,i,o=0;
	scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
	while (1){
		o++;
		b -= d;
		c -= e;
		if (b <= 0 && c <= 0){
			break;
		}
		
}
	a = a - o;
	printf("%d\n",a );
	return 0;
}

Measured memory_bytes: 1024
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 300010;
const int MAXM = 1010;
const int MAXK = 110;
const int MAXQ = 200010;

int n, a[MAXN], f[MAXN];
vector<int> b, s;

int getNumberOfLarger(int u) {
    if (b[0] < u) return 0;

    int dau = 0, cuoi = SZ(b)-1;
    while (dau <= cuoi) {
        int mid = (dau + cuoi) >> 1;
        if (b[mid] >= u) dau = mid+1;
        else cuoi = mid-1;
    }
    return cuoi+1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FOR(i,1,n) f[a[i]]++;
    FOR(i,1,n)
        if (f[i]) b.emplace_back(f[i]);
    sort(ALL(b));
    reverse(ALL(b));

    FOR(i,0,SZ(b)-1) 
        if (i == 0) s.emplace_back(b[i]);
        else s.emplace_back(s[SZ(s)-1] + b[i]);

    FOR(k,1,n) {
        if (k > SZ(b)) {
            cout << 0 << "\n";
            continue;
        }
        int numOfGroup = k;
        int numInEach = n / k;

        int cnt = getNumberOfLarger(numInEach);

        numOfGroup -= cnt;

        if (numOfGroup <= 0) {
            cout << numInEach << "\n";
            continue;
        }
        int N = n;
        int Min = 1000000000;
        if (cnt) {
            N = n - s[cnt-1];
            Min = b[cnt-1];
        }

        while (cnt < SZ(b) && b[cnt] > N / numOfGroup) {
            Min = min(Min, b[cnt]);
            N -= b[cnt];
            cnt++;
            numOfGroup--;
        }
        
        if (numOfGroup) numInEach = N / numOfGroup;
        else numInEach = 1000000000;

        cout << min(Min, numInEach) << "\n";
    }
    return 0;
}


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

#define min(x,y) ((x)<(y))?(x):(y)
#define max(x,y) ((x)>(y))?(x):(y)

int main(void)
{
	int A, B;
	cin >> A >> B;
	int large = max(A, B);
	int small = min(A, B);

	if (small == 1 && large == 2)cout << 3 << endl;
	else if (small == 2 && large == 3)cout << 1 << endl;
	else cout << 2 << endl;

	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

ll Solve() {
    int n, k;
    cin >> n >> k;

    vector<ll> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];

    ll max_v = 0;
    for (int l = -1; l < n; ++l) {
        for (int r = n; 0 <= r && l < r; --r) {
            vector<ll> select;
            for (int i = 0; i <= l; ++i)
                select.push_back(v[i]);
            for (int i = n - 1; r <= i; --i)
                select.push_back(v[i]);

            if (k < (int)select.size()) continue;

            sort(select.begin(), select.end());
            ll sum = accumulate(select.begin(), select.end(), 0ll);
            int res = k - select.size();

            max_v = max(max_v, sum);
            for (int i = 0; i < res && i < (int)select.size(); ++i) {
                if (select[i] < 0) {
                    sum -= select[i];
                }
            }
            max_v = max(max_v, sum);
        }
    }

    return max_v;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    cout << Solve() << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define min3(x, y, z) min(x, min(y, z))
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);

lli n, m, k;

int main() {
	fast_io();
	//freopen("inp.in", "r", stdin);

	cin >> n >> m >> k;
	if(n % 2 == 0 || m % 2 == 0 || k % 2 == 0)
		cout << 0;
	else
		cout << min3(n * m, n * k, m * k);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define tezi ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
typedef long long ll;

int main(){
    tezi;
    string s;
    cin >> s;
    for(int i = 0; i < (int)s.length(); ++i){
        if(s[i] == '?') cout << 'D';
        else cout << s[i];
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3744
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
T = LS2()
s = len(S)
t = len(T)

ans = 10**5
for i in range(s-t+1):
    count = 0
    for j in range(t):
        if T[j] != S[i+j]:
            count += 1
    ans = min(ans,count)

print(ans)


Measured memory_bytes: 64828
#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(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

struct RollingHash {
	vector<ll> mod;
	vector<vector<ll> > hs, pw;
	string s;
	ll base;
	int n;
	
	RollingHash() {}
	RollingHash(string s) { init(s); }
	
	void init(string _s) {
		s = _s;
		n = s.size();
		
		mod.clear();
		hs.clear();
		pw.clear();
		
		mod.push_back(999999937);
		mod.push_back(1000000007);
		
		base = 9973;
		
		hs.resize(mod.size(), vector<ll>(n + 1));
		pw.resize(mod.size(), vector<ll>(n + 1));
		
		REP(i, mod.size()) {
			pw[i][0] = 1;
			REP(j, n) {
				hs[i][j + 1] = (hs[i][j] + s[j]) * base % mod[i];
				pw[i][j + 1] = pw[i][j] * base % mod[i];
			}
		}
	}
	
	inline ll hash(int l, int r, int i) {
		return (hs[i][r] - hs[i][l] * pw[i][r - l] % mod[i] + mod[i]) % mod[i];
	}
	
	inline bool match(int l1, int r1, int l2, int r2) {
		bool res = true;
		REP(i, mod.size()) if (hash(l1, r1, i) != hash(l2, r2, i)) res = false;
		return res;
	}
};

string w;
bool cut[512345] = {}; // 0:ok, 1:no
bool rcut[512345] = {};

int main() {
	cin >> w;
	RollingHash rh(w);
	
	int l = w.size();
	
	bool ok = true;
	
	FOR(i, 1, l / 2 + 1) {
		bool f = true;
		// head
		for (int j = i + i; j <= l; j += i) {
			if (!rh.match(0, i, j - i, j)) { f = false; break; }
			cut[j] = true;
		}
		if (l % i == 0 && f) ok = false;
		
		// back
		for (int j = l - i - i; j >= 0; j -= i) {
			if (!rh.match(l - i, l, j, j + i)) break;
			rcut[j] = true;
		}
	}
	
	int cnt = 0;
	FOR(i, 1, l) if (!cut[i] && !rcut[i]) cnt++;
	
	//if (debug) cout << "cnt : " << cnt << endl;
	
	bool same = true;
	FOR(i, 1, l) if (w[i - 1] != w[i]) same = false;
	
	int a, b;
	if (same) a = l, b = 1;
	else if (ok) a = 1, b = 1;
	else a = 2, b = cnt;
	
	printf("%d\n%d\n", a, b);
	
	return 0;
}


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

#define int  long long
#define EB emplace_back
#define MOD 1000000007
#define F first
#define S second
#define endl "\n"

 
using namespace std; 

int32_t main()
{
   int n; cin >> n;
  	int ans = 0;
  for(int i = 0; i < n; i++) {
    int x; cin >> x;
    if(i % 2 == 0 and x % 2 == 1) ans ++;
  }
  cout << ans;
    
	
	return 0;
}


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

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

	if (s <= "2019/04/30")
	{
		cout << "Heisei" << endl;
	}
	else
	{
		cout << "TBD" << endl;
	}

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int solve(string x, int target, int k) {
    vector<int> vec;
    for (auto q : x) {
        if (q == 'L') vec.push_back(1);
        else vec.push_back(0);
    }
    priority_queue<pair<int, int>> pq, pq2;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i] == (target ^ 1)) {
            int cnt = 0;
            int tmp = i;
            for (int j = i; j < vec.size(); j++, i++) {
                if (vec[j] == (target ^ 1)) cnt++;
                else break;
            }
            if (tmp == 0 || i == vec.size() - 1)pq2.push({cnt, tmp});
                else pq.push({cnt, tmp});
            i--;
        }
    }
    int cnt = 0;
    while (pq.size()) {
        for (int i = pq.top().second; i < vec.size(); i++)
            if (vec[i] == (target ^ 1)) vec[i] = target;
            else break;
        pq.pop();
        if (++cnt == k) break;
    }
    while (pq2.size()) {
        if (cnt == k) break;
        for (int i = pq2.top().second; i < vec.size(); i++)
            if (vec[i] == (target ^ 1)) vec[i] = target;
            else break;
        pq2.pop();
        if (++cnt == k) break;
    }
    int ans = 0;
    for (int i = 0; i < vec.size() - 1; i++)
        if (vec[i] == vec[i + 1]) ans++;
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k >> s;
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
        if (s[i] == s[i + 1]) ans++;
    cout << max(ans, max(solve(s, 1, k), solve(s, 0, k)));
    return 0;
}


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

#define fi first
#define se second
#define endl '\n'
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mp make_pair
#define pb push_back
#define lowbit(a) (a&(-a))
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()
#define mst(a,v) memset(a,v,sizeof(a))
#define debug(x) cout<<#x": "<<x<<'\n';
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

const int N=100010;
const int mod=1e9+7;
const ld PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

template<typename T>inline void gmax(T &A,T B) {(A<B)&&(A=B);}
template<typename T>inline void gmin(T &A,T B) {(A>B)&&(A=B);}

template <class T>
inline bool re(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}

ll dp[111111];
int w[111],v[111];

int main()
{
#ifdef local
    //freopen("in.txt", "r", stdin);
#endif
    IOS;
    int n,c;
    cin>>n>>c;
    for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
    for(int i=1; i<=n; i++)
        for(int j=c; j>=w[i]; j--)
        gmax(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[c];
    return 0;
}


Measured memory_bytes: 1024
n = int(input())
*li,=map(int, input().split())
from collections import Counter
c = Counter()
for i in li:
    c[i] += 1
ans=0
from math import comb
for i in c.values():
    ans += comb(i, 2)
for i in li:
    print(ans - comb(c[i], 2) + comb(c[i]-1, 2))
  

Measured memory_bytes: 32172
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  string S;
  cin >> S;
  
  if(S.at(0)==S.at(1) && S.at(2)==S.at(3) && S.at(0)!=S.at(2)){
    cout<<"Yes"<<endl;}
  else if(S.at(0)==S.at(2) && S.at(1)==S.at(3) && S.at(0)!=S.at(1)){
    cout<<"Yes"<<endl;}
  else if(S.at(0)==S.at(3) && S.at(1)==S.at(2) && S.at(0)!=S.at(1)){
    cout<<"Yes"<<endl;}
  else if(true){
    cout << "No" << endl;}
     }
    
    
  

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

int main(){
    int n;
    cin >> n;
    VVI F(n, VI(10)), P(n, VI(11));
    rep(i,n)rep(j,10){
        cin >> F[i][j];
    }
    rep(i,n)rep(j,11){
        cin >> P[i][j];
    }

    VI profit(1024,0);

    rep2(b,1,1024){
        VI c(n,0);
        rep(a,10){
            if(b & (1 << a)){
                rep(i,n){
                    if(F[i][a]) c[i]++;
                }
            }
        }
        rep(i,n){  
            profit[b] += P[i][c[i]];
        }
    }
    
    cout << *max_element(profit.begin()+1, profit.end()) << endl;

    return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<string>v(n); for(auto&i:v)cin>>i;
	sort(v.begin(),v.end());
	int ans=1;
	for(int i=1;i<n;++i){
		if(v.at(i)==v.at(i-1))continue;
		++ans;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 9528