akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(int i=cc;i>=n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>

using ll = long long;
int n;
vector<int> a;
void solve(){
    vector<int>ans;
    rep(i, 0, n){
        int k = -1;
        rrep(j, a.size()-1, 0){
        if(a[j] == j){
            k = j;
            break;
        }
        }
        if(k == -1){
            cout << -1 << endl;
            return;
        }
        ans.push_back(k+1);
        a.erase(a.begin()+k);
    }
    reverse(ans.begin(), ans.end());
    rep(i, 0, n){
        cout << ans[i] << endl;
    }
}

int main(){
    cin >> n;
    a.resize(n);
    rep(i, 0, n){
        cin >> a[i];
        a[i]--;
    }
    solve();
}

Measured memory_bytes: 256
#include <iostream>

#define MAX 100005
#define NIL -1

struct Node{int p, l, r;};

Node T[MAX];
int n, D[MAX];

void print(int u){
  int i, c;
  std::cout << "node " << u << ": ";
  std::cout << "parent = " << T[u].p << ", ";
  std::cout << "depth = " << D[u] << ", ";

  if (T[u].p == NIL) std::cout << "root, ";
  else if (T[u].l == NIL) std::cout << "leaf, ";
  else std::cout << "internal node, ";

  std::cout << "[";

  for (i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {
    if (i) std::cout << ", ";
    std::cout << c;
  }
  std::cout << "]" << std::endl;
}


void rec(int u, int p){
  D[u] = p;
  if (T[u].r != NIL) rec(T[u].r, p);
  if (T[u].l != NIL) rec(T[u].l, p + 1);
}

int main() {
  int i, j, d, v, c, l, r;
  std::cin >> n;
  for ( i = 0; i < n; i++) T[i].p = T[i].l = T[i].r  = NIL;

  for ( i = 0; i < n; i++) {
    std::cin >> v >> d;
    for ( j = 0; j < d; j++) {
      std::cin >> c;
      if (j == 0) T[v].l = c;
      else T[l].r = c;
      l = c;
      T[c].p = v;
    }
  }
  for ( i = 0; i < n; i++) {
    if (T[i].p == NIL) r = i;
  }

  rec(r, 0);

  for ( i = 0; i < n; i++) print(i);

  return 0;
}



Measured memory_bytes: 7784
#include <iostream>
#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(n);++(i))
#define all(x) (x).begin(),(x).end()
#define dump(x) cout << #x << " = " << (x) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl

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

const int INF = 1001001001;
const vector<int> di = {-1,  0, 1, 0};
const vector<int> dj = { 0, -1, 0, 1};


int main() {
    int n; cin >> n;
    vector<int> t(n + 1, 0), x(n + 1, 0), y(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> t[i] >> x[i] >> y[i];

    bool ok = true;
    rep(i, n) {
        int cost = t[i + 1] - t[i];
        int d = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
        if ((cost < d) || ((cost % 2) != (d % 2))) {
            ok = false;
            break;
        }
    }
    Yes(ok);
}


Measured memory_bytes: 1408
Adr = [[[0 for r in range(10)]for f in range(3)]for b in range(4)]

n = input()

for i in range(n):
    Inf = map(int, raw_input().split())

    Adr[Inf[0]-1][Inf[1]-1][Inf[2]-1] += Inf[3]

for b in range(4):
    for f in range(3):
        print "",
        for r in range(10):
            if r != 9:
                print Adr[b][f][r],
            if r == 9:
                if f == 3:
                    print Adr[b][f][r],
                if f != 3:
                    print Adr[b][f][r]


    if b < 3:
        print "####################"

Measured memory_bytes: 6424
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long int
#define phi 1.6180339
#define rep(i,n) for(auto i=0;i<(n);i++)
#define endl "\n"
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define op1 cin.tie(NULL)
#define op2 cout.tie(NULL)
#define op3 std::ios_base::sync_with_stdio(false)
#define MAXX 1000001
using namespace std;
void trozen()
{
  string s;
  cin>>s;
  int n=s.length();
  cout<<s;
  if(s[n-1]=='s') cout<<"es";
  else cout<<"s";
}
int32_t main()
{
    op1;op2;op3;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    trozen();
    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <tuple>
#include <utility>
using namespace std;
typedef long long ll;
#define for1(i,n) for (ll i=0;i<(n);(i)++)
#define for2(i,m,n) for (ll (i)=(m);(i)<(n);(i)++)
#define for3(i,m,n,d) for (ll (i)=(m);(i)<(n);(i)+=(d))
#define INF (1LL << 60)

class UnionFind {
public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<ll> Parent;
 
    //作るときはParentの値を全て-1にする
    //こうすると全てバラバラになる
    UnionFind(ll N) {
        Parent = vector<ll>(N, -1);
    }
 
    //Aがどのグループに属しているか調べる
    ll root(ll A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
 
    //自分のいるグループの頂点数を調べる
    ll size(ll A) {
        return -Parent[root(A)];//親をとってきたいß
    }
 
    //AとBをくっ付ける
    bool connect(ll A, ll B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
 
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらひっくり返しちゃう。
        if (size(A) < size(B)) swap(A, B);
 
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
 
        return true;
    }
};

void solve()
{
    ll N;
    cin >> N;
    vector<pair<ll,ll>> sx;
    vector<pair<ll,ll>> sy;
    vector<tuple<ll,ll,ll>> dis;
    for1(i,N) {
        ll x,y;
        cin >> x >> y;
        sx.emplace_back(x,i);
        sy.emplace_back(y,i);
    }
    sort(sx.begin(),sx.end());
    sort(sy.begin(),sy.end());
    bool first = true;
    ll px = 0;
    ll py = 0;
    ll pi = 0;
    for (auto s : sx) {
        if (first) {
            first = false;
        } else {
            dis.emplace_back(s.first - px, pi, s.second);
        }
        px = s.first;
        pi = s.second;
    }
    first = true;
    for (auto s : sy) {
        if (first) {
            first = false;
        } else {
            dis.emplace_back(s.first - py, pi, s.second);
        }
        py = s.first;
        pi = s.second;
    }
    sort(dis.begin(),dis.end());

    ll rest = N - 1;
    UnionFind uni(N);
    ll ans = 0;
    for (auto item : dis) {
        if (rest == 0) break;
        ll d,a,b;
        tie(d,a,b) = item;
        if (uni.root(a) == uni.root(b)) continue;
        ans += d;
        uni.connect(a,b);
        --rest;
    }

    cout << ans << endl;
}

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


Measured memory_bytes: 12896
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define MOD7 1000000007
#define LL_INF 1LL << 60
#define LL_MINF -1LL << 60
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const long double PI = (acos(-1));


int main(){
    string s;
    map<char,int> M;
    while(getline(cin, s)){
        for(char c : s){
        if('A' <= c and c <= 'Z') M[tolower(c)]++;
        else M[c]++;
    }
    }
    for(char x = 'a'; x <= 'z'; x++){
        cout << x << " : " << M[x] << endl;
    }
}


Measured memory_bytes: 3204
#include <iostream>

using namespace std;

int main() {
    string input;
    string ans;

    cin >> input;
    
    if (input[0] == input[1] && input[2] == input[3] && input[0] != input[2]) {
        ans = "Yes";
    }
    else if (input[0] == input[2] && input[1] == input[3] && input[0] != input[1]) {
        ans = "Yes";
    }
    else if (input[0] == input[3] && input[1] == input[2] && input[0] != input[1]) {
        ans = "Yes";
    }
    else { 
        ans = "No";
    }

    cout << ans << "\n";
    
    return 0;
}


Measured memory_bytes: 256
s = input()
LEN = len(s)
if LEN == 1:
    print(0)
    exit()
    
even = s[::2]
odd = s[1::2]

ew = even.count('1')
eb = (LEN+1)//2 - ew
ow = odd.count('1')
ob = (LEN)//2 - ow

print(min(eb + ow, ew + ob))

Measured memory_bytes: 9112
from collections import deque

N, M = map(int, input().split())
friends = [[] for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  friends[a].append(b)
  friends[b].append(a)

check = [False] * N
ans = 0

for i in range(N):
  if check[i] == False:
    check[i] = True
    D = deque(friends[i])
    tmp = 1
    while D:
      f = D.popleft()
      if check[f] == False:
        check[f] = True
        tmp += 1
        for j in friends[f]:
          D.append(j)
    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 112260
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int n;
string s;

int main(){
  cin >> n >> s;
  s.push_back('X');
  int res = 0;
  rep(i, n){
    if(s[i] != s[i + 1])
      res++;
  }
  cout << res << endl;
}

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

#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
namespace adaptor = boost::adaptors;

// 多倍長テンプレ
/* ---------------------- ここから ---------------------- */
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
/* ---------------------- ここまで ---------------------- */

using ll = long long;
using ull = unsigned long long;

void Main()
{
	int A;
	cin >> A;

	cout << A + A*A + A*A*A;
	return;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 3632
using System;
using System.Linq;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            // Console.WriteLine("Hello World!");
            var ab = Console.ReadLine().Split().Select(int.Parse).ToArray();
            
            Console.WriteLine(ab[1] % ab[0] == 0 ? ab.Sum() : ab[1] - ab[0]);
        }
    }
}


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

int main() {
	int L, R, d;
	cin >> L >> R >> d;

	int cnt = 0;
	for(int i = L; i <= R; i++) {
		if(i % d == 0) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3632
//A - αlphabet

#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	char c;
	cin>>c;
	if (c>= 65 && c<=90)
		cout<<'A'<<endl;
	else 
		cout<<'a'<<endl;
	return 0;
}


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

using namespace std;

class UnionFind {
public:
  vector<int> parent;

  UnionFind(int n) : parent(n, -1) {
  }

  int root(int x) {
    if (parent[x] < 0) {
      return x;
    } else {
      return parent[x] = root(parent[x]);
    }
  }

  bool issame(int x, int y) {
    return root(x) == root(y);
  }

  int size(int x) {
    return -parent[root(x)];
  }

  bool unite(int x, int y) {
    int rx = root(x), ry = root(y);
    if (rx == ry) return false;
    if (parent[rx] > parent[ry]) swap(rx, ry);
    parent[rx] += parent[ry];
    parent[ry] = rx;
    return true;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> X(N), Y(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }
  if (N == 1) {
    cout << 1 << '\n';
    return 0;
  }
  int res = N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (i == j) continue;
      int dx = X[i] - X[j], dy = Y[i] - Y[j];
      if (dx == 0 && dy == 0) continue;

      UnionFind uf(N);
      for (int a = 0; a < N; a++) {
        for (int b = 0; b < N; b++) {
          if (X[a] - X[b] == dx && Y[a] - Y[b] == dy) {
            uf.unite(a, b);
          }
        }
      }
      int cnt = 0;
      for (int a = 0; a < N; a++) {
        if (uf.root(a) == a) cnt++;
      }
      res = min(res, cnt);
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main implements Runnable {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
    }

    public void run() {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void solve() throws IOException {
        long n = in.nextLong();
        long m = in.nextLong();
        double d = in.nextLong();
        System.out.println((d == 0 ? 1 : 2) * (n - d) * (m - 1) / (n * n));
    }

}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException {super(System.out);}
}
class ContestScanner implements Closeable {
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}


Measured memory_bytes: 21716
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<climits>
#include<cstdlib>
#include<map>
#include<math.h>
#include<utility>
#include<vector>
using namespace std ;
typedef long long ll;

// N K
// A_1, ..., A_N

int gcm(int a, int b) {
	int result = a;
	int k = 0;
	int n = b;
	do {
		k = result % n;
		result = n;
		n = k;
	} while(k != 0);
	return result;
}

int lcm(int a, int b) {
	int g;
	g = gcm(a, b);
	return a*b/g;
}

int lcm_n(vector<int> &numbers) {
	int l;
	l = numbers[0];
	for (int i = 1; i < numbers.size(); i++) {
		l = gcm(l, numbers[i]);
	}
	return l;
}

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

  vector<int> v ;
  for(int i = 0; i!= N; ++i){
    int tmp ;
    cin >> tmp ;
    v.push_back(tmp) ;
  }

  cout << lcm_n(v) << endl;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

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

int main(){
    ll n, a, b; cin>>n>>a>>b;
    vector<ll> x(n);
    for(int i=0; i<n; i++) cin>>x[i];

    vector<ll> d(n);
    for(int i=0; i<n-1; i++){
        d[i]=x[i+1]-x[i];
    }

    ll ans=0;
    for(int i=0; i<n-1; i++){
        if(d[i]*a<=b) ans+=d[i]*a;
        else ans+=b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
s = input()
t = input()
for i in range(n):
    if s[i:] == t[:n - i]:
        print(n + i)
        exit()
print(n * 2)


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

void output(int *a,int n){
	int i;
	for(i=0;i<n;i++){
		printf("%d",a[i]);
		if(i!=n-1){
			printf(" ");
		}
	}
	printf("\n");
}

int main(){
	int n,s[100],i,j,v,tmp;
	char input[5*100+1],*p;
	
	fgets(input,sizeof input,stdin);
	sscanf(input,"%d",&n);
	
	fgets(input,sizeof input,stdin);
	
	p=strtok(input," ");
	s[0]=atoi(p);
	
	for(i=1;i<n;i++){
		p=strtok(NULL," ");
		s[i]=atoi(p);
	}
	output(s,n);
	for(i=1;i<n;i++){
		v=s[i];
		j=i-1;
		while(1){
			if(j<0||s[j]<=v){
				break;
			}
			s[j+1]=s[j];
			j--;
		}
		s[j+1]=v;
		output(s,n);
	}
	
	
	return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

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

int main(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans = 0;
    bool ok = true;
    ll temp = 0;
    for(int i = n-1; 0 <= i; i--){
        temp--;
        if(temp > a[i]){ok = false;break;}
        if(chmax(temp,a[i])){
            ans += temp;
        }
        if(temp > i){ok = false;break;}
        
    }

    cout <<(ok ? ans : -1) << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE

class Combination{
public:
  typedef long long ll;
  ll N;
  ll mod;
  vector<ll> fac;
  vector<ll> finv;
  vector<ll> inv;


  Combination(ll N = 1e6,ll mod = 1e9 + 7): N(N), mod(mod), fac(N+1), finv(N+1), inv(N+1){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(Int i = 2; i <= N; i++){
      fac[i] = fac[i-1] * i % mod;
      inv[i] = mod - inv[mod%i] * (mod / i) % mod;
      finv[i] = finv[i-1] * inv[i] % mod;
    }
  }

  function<ll(ll,ll)> get = [&](ll n,ll r){
    if( n < r ) return 0LL;
    if( n < 0 || r < 0) return 0LL;
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod;
  };

};
auto nCr = (new Combination())->get;

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

  Int X, Y;
  cin>>X>>Y;

  Int ans = 0;
  for(Int i=0;i<=X;i++){
    Int a = i; //(i+1, j+2)で動く回数
    Int b = (X - i)/2;
    if(a + 2 * b != X || 2 * a + b != Y) continue;
    ans += nCr(a + b, a);
    ans %= mod;
  }

  cout<<ans<<endl;

  return 0;
}


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

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == 0) {
        v.clear();
        return 0;
    }
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    return i;
}

bool solve(int N, vi& a) {
    sort(ALL(a)); reverse(ALL(a));
    int F = a[0], D = a.back();
    if (!(F == D*2 || F == D*2-1)) return false;

    map<int,int> st;
    for(int ai: a) st[ai]++;

    map<int,int> sqn;
    for (int i=0,j=F; i<=F; ++i,--j) {
        int Fi = max(i, j);
        assert(IN(Fi, D, F));
        sqn[Fi]++;
    }
    for (int d=D; d<=F; ++d) {
        if (st[d] < sqn[d]) return false;
        st[d] -= sqn[d];
    }
    if (st[D] != 0) return false;

    return true;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << (solve(N,a) ? "Possible":"Impossible") << endl;
    return 0;
}


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

#include <iostream>
#include <stdio.h>
#include <array>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <algorithm>
#include <map>
#include <cmath>
#include <stdlib.h>
#include <string.h>
#include <stack>
#include <bitset>

using namespace std;

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

int a, b;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
#define MAX(a,b) a>b? a:b
#define MIN(a,b) a>b? b:a


const int MOD = 1e9 + 7;
const ll INF=1e10;
const db PI = acos(-1.0);
const db EPS = 1e-10;


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


/*ll MAXX(vector<ll> a,ll k) {
	ll max = 0;
	REP(i, k) {
		if (a[i] >= max) max = a[i];
	}
	return max;
}*/

/*ll MINN(vector<ll> a,ll k) {
	ll min = INF;
	REP(i, k) {
		if (a[i] <= min)min = a[i];
	}
	return min;
}*/

/*ll SUM(vector<ll> a, ll k) {
	ll sum = 0;
	REP(i, k) {
		sum += a[i];
	}
	return sum;
}*/

/*db AVE(vector<ll> a, ll k) {
	db ave = SUM(a,k)/(db)k;
	return ave;
}*/

/*db VAR(vector<ll> a, ll k) {
	db ave,ave2,var;
	db sum = 0;
	REP(i, k) {
		sum += a[i] * a[i];
	}
	ave2 =sum/ k;
	ave = AVE(a,k);
	ave = pow(ave,2);
	var = ave2 - ave;
	return var;
}*/


template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}


template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}


/*void prime(int k) {
	int cnt = 0;
	for (int i = 2;i<k;i++) {
		if (k % i == 0) { cnt++; }
	}
	if (cnt == 0) cout << k << "は素数です。" << endl;
	else cout << k << "は素数ではありません。" << endl;
}*/



int main() {
	int a, b;
	cin >> a >> b;
	if ((a + b) % 2 == 0) {
		cout << (a + b) / 2 << endl;
	}
	else cout << "IMPOSSIBLE" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

using namespace std;

int main(){

	int H,W;
	scanf("%d %d",&H,&W);

	char map[H][W+1];
	int table[H+1][W+1];

	for(int i = 0; i <= H; i++){
		for(int k = 0; k <= W; k++)table[i][k] = 0;
	}

	scanf("%s",map[0]);

	for(int i = 1; i <= W; i++){
		table[1][i] = table[1][i-1] + map[0][i-1] - '0';
	}

	for(int i = 2; i <= H; i++){
		scanf("%s",map[i-1]);
		table[i][1] = table[i-1][1] + map[i-1][0] - '0';
		for(int k = 2; k <= W; k++){
			table[i][k] = min(table[i-1][k],table[i][k-1]) + map[i-1][k-1] - '0';
		}
	}

	printf("%d\n",table[H][W]);

    return 0;
}

Measured memory_bytes: 2764
#include<iostream>
#include<cstdio>
#include<cstring>

typedef long long ll;
const int N=25010,K=404,MOD=1000000007;

ll inv(int x){return (x==1 || x==-1)?x:(-(MOD/x)*inv(MOD%x)%MOD);}
inline void inc(int a,int &b){b=(a+b)%MOD;}

int f[N][K][2],g[N][K][2];
bool vis[K];

int A[N];
int n,m,k;

namespace CaseSimple
{
	bool check()
	{
		for(int i=1;i+k-1<=m;i++)
		{
			memset(vis,0,sizeof(vis));
			for(int j=1;j<=k;j++)vis[A[i+j-1]]=1;

			bool flag=1;
			for(int j=1;j<=k;j++)flag&=vis[j];
			if(flag)return 1;
		}
		return 0;
	}

	void dp(int h[N][K][2])
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<=k;j++)
				for(int l=0;l<2;l++)
				{
					int v=h[i][j][l],dv=(ll)v*(k-j)%MOD;

					inc(dv,h[i+1][j+1][l|(j+1==k)]);
					inc(-dv,h[i+1][j+2][l|(j+1==k)]);

					inc(v,h[i+1][1][l]);
					inc(-v,h[i+1][j+1][l]);
				}
			for(int l=0;l<2;l++)
				for(int j=1;j<=k+1;j++)
					inc(h[i+1][j-1][l],h[i+1][j][l]);
		}
	}

	void solve()
	{
		bool tmp=check();

		memset(vis,0,sizeof(vis));
		for(int i=1;i<=m;i++)
			if(vis[A[i]]){f[0][i-1][tmp]=1;break;}
			else vis[A[i]]=1;

		memset(vis,0,sizeof(vis));
		for(int i=m;i;i--)
			if(vis[A[i]]){g[0][m-i][tmp]=1;break;}
			else vis[A[i]]=1;

		dp(f),dp(g);

		int ans=0;
		for(int x=0,y,sx,sy;m+x<=n;x++)
		{
			y=n-m-x,sx=sy=0;

			for(int i=1;i<=k;i++)
				inc((f[x][i][1]+f[x][i][0])%MOD,sx),inc((g[y][i][1]+g[y][i][0])%MOD,sy);
			inc((ll)sx*sy%MOD,ans);

			sx=sy=0;
			for(int i=1;i<=k;i++)
				inc(f[x][i][0],sx),inc(g[y][i][0],sy);
			inc(-(ll)sx*sy%MOD,ans);
		}

		ans=(ans+MOD)%MOD;

		printf("%d\n",ans);
	}
}

namespace CaseHard
{
	void dp()
	{
		f[1][1][k==1]=k;
		g[1][1][k==1]=k*(m==1);

		for(int i=1;i<n;i++)
		{
			for(int j=1;j<=k;j++)
				for(int l=0;l<2;l++)
				{
					int v=f[i][j][l],dv=(ll)v*(k-j)%MOD;
					inc(dv,f[i+1][j+1][l|(j+1==k)]);
					inc(-dv,f[i+1][j+2][l|(j+1==k)]);
					inc(v,f[i+1][1][l]);
					inc(-v,f[i+1][j+1][l]);

					v=g[i][j][l],dv=(ll)v*(k-j)%MOD;
					inc(dv,g[i+1][j+1][l|(j+1==k)]);
					inc(-dv,g[i+1][j+2][l|(j+1==k)]);
					inc(v,g[i+1][1][l]);
					inc(-v,g[i+1][j+1][l]);
				}

			for(int l=0;l<2;l++)
				for(int j=1;j<=k+1;j++)
					inc(f[i+1][j-1][l],f[i+1][j][l]),inc(g[i+1][j-1][l],g[i+1][j][l]);

			for(int j=m;j<=k;j++)
				for(int l=0;l<2;l++)
					inc(f[i+1][j][l],g[i+1][j][l]);
		}
	}
	void solve()
	{
		dp();

		int ans=0,tmp=1;

		for(int i=1;i<=k;i++)
			inc(g[n][i][1],ans);

		for(int i=1;i<=m;i++)
			tmp=(ll)tmp*(k-i+1)%MOD;

		ans=ans*inv(tmp)%MOD;
		ans=(ans+MOD)%MOD;

		printf("%d\n",ans);
	}
}


bool judge()
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=m;i++)
		if(vis[A[i]])return 1;
		else vis[A[i]]=1;
	return 0;
}

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

	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",A+i);

	if(judge())CaseSimple::solve();
	else CaseHard::solve();

	return 0;
}


Measured memory_bytes: 158208
import scala.io.StdIn.{readInt, readLong};

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val arr = (0 until n).map(a => readLong).toArray;
        val interval = fetchInterval(n);
        val cnt = shellSort(arr, n, interval);
        println(interval.length);
        println(interval.mkString(" "));
        println(cnt);
        println(arr.mkString("\n"));
    }
    
    def fetchInterval(n: Int): List[Int] = { 
        val len = n;
        def go(g: Int, ret: List[Int]): List[Int] = {
            val ng = (g * 3) + 1;
            if (ng < len) go(ng, ng :: ret) else ret;
        }
        go(1, List(1));
    }
    
    def shellSort(arr: Array[Long], n: Int, interval: List[Int]): Int = {
        interval.foldLeft(0) { (cnt, i) =>
            (0 until n).foldLeft(cnt) { (cnt, j) =>
                insertionSort(arr, j, i) + cnt;
            }
        }
    }
    
    def insertionSort(arr: Array[Long], index: Int, interval: Int): Int = {
        val insert = arr(index);
        var cnt = 0;
        def go(curr: Int): Unit = {
            val prev = curr - interval;
            if (prev < 0 || arr(prev) <= insert) {
                arr(curr) = insert;
            } else {
                arr(curr) = arr(prev);
                cnt += 1;
                go(prev);
            }
        }
        go(index);
        cnt
    }
}


Measured memory_bytes: 458760
using System;


    class MainClass
    {
    public static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');

        int A = int.Parse(input[0]);

        int B = int.Parse(input[1]);

        int C= int.Parse(input[2]);

        int D = int.Parse(input[3]);

        if ((C -1)/ B <= (A-1) / D)
            
        {
            Console.WriteLine("Yes");

        }

        else
        {
            Console.WriteLine("No");
        }


       
    }
}


Measured memory_bytes: 17860
#include <stdio.h>
int main()
{
    double x1, y1, x2, y2;

    scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
    printf("%.8lf\n", hypot(x1 - x2, y1 - y2));
    return 0;
}



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


int main()
{
    int64_t n;
    cin>>n;
    int64_t s=0;
    int64_t i,j;
    for(i=2;i<=n/i;i++)
    {
        if(n%i) continue;
            for(j=i;j<=n;j*=i)
                if(n%j==0){s++;n=n/j;}
            while(n%i==0)
                n/=i;

    }
    if(n!=1) s++;
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3636
h,w=gets.split.map &:to_i
m=Array.new(h+1).map{Array.new(w+1)}
ans=Array.new(h+1).map{Array.new(w+1)}
h.times do|i|
  m[i]=(gets.chomp+".").chars
end
(w+1).times do|i|
  m[h][i]="."
end
h.times do|i|
  w.times do|j|
    if m[i][j]=="."
      x=0
      if m[i][j-1]=="#" then x+=1 end
      if m[i][j+1]=="#" then x+=1 end
      if m[i-1][j-1]=="#" then x+=1 end
      if m[i-1][j]=="#" then x+=1 end
      if m[i-1][j+1]=="#" then x+=1 end
      if m[i+1][j-1]=="#" then x+=1 end
      if m[i+1][j]=="#" then x+=1 end
      if m[i+1][j+1]=="#" then x+=1 end
      ans[i][j]=x
    else
      ans[i][j]="#"
    end
  end
end
h.times do|i|
  w.times do|j|
    print ans[i][j]
  end
  print "\n"
end


Measured memory_bytes: 2172
#pragma GCC optimize("Ofast",3,"inline")
#include <bits/stdc++.h>
using namespace std;
map<string,string> mp;
string s;
int main(){
	ios_base::sync_with_stdio(false);
	cin>>s;
	mp["Sunny"]="Cloudy";
	mp["Rainy"]="Sunny";
	mp["Cloudy"]="Rainy";
	cout<<mp[s];
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int me = 0,mini = INF;
vector<int> mesi(5);
for (int i = 0;i < 5;i++) {
    cin >> mesi.at(i);
    int a = mesi.at(i) % 10;
    if (a> 0 && a < mini) {
        mini = mesi.at(i)%10;
        me = i;
    }
}
int ans = 0;
for (int i = 0;i < 5;i++) {
    if (i == me || mesi.at(i) % 10 == 0) {
        ans += mesi.at(i);
    }else {
    int fu = 10-(mesi.at(i)%10);
    mesi.at(i) +=  fu;
    ans += mesi.at(i);
    }
}
cout << ans << endl;

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<n; i++)
#define REP(i,x,n) for (int i=x; i<n; i++)
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

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

    while (1){
        for(int i=2; i<=x; i++){
            if (i == x) goto OUT;
            if (x % i == 0) break;
        }
        x++;
    }
    OUT:
    cout << x << endl;
    return 0;
}


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

a = list(map(int,input().split()))

a_max = max(a)

half_a = a_max//2

comb = 1000000000
for i in range(N):
    if a[i]==a_max:
        continue
    if comb>abs(half_a-a[i]):
        idx =i
        comb = abs(half_a-a[i])

print(str(a_max) + ' ' + str(a[idx]))

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

int main() {
	int  a,b;
	cin >> a >>b;
	if (a==b)cout << "Draw" << endl;
	else if(a==1)cout << "Alice" << endl;
	else if (b==1)cout << "Bob" << endl;
	else if (a<b)cout << "Bob" << endl;
	else if (a>b)cout << "Alice" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>                                                          
#define rep(i,n) for (int i = 0; i< (n); i++)                                     
using ll = long long;                                                             
using namespace std;                                                              
                                                                                  
int main(){                                                                       
        ll N, A, B;                                                               
        cin >> N >> A >> B;                                                       
        ll ans;                                                                   
        if ((B-A)%2 == 0) ans = (B-A)/2;                                          
        else ans = min(A-1,N-B) + (B-A+1)/2;                                      
        cout << ans << endl;                                                      
                                                                                  
        return 0;                                                                 
}       

Measured memory_bytes: 3584
N, M = 4, 3
HRR = [1, 2, 3, 4]
ARR = [
    [1, 3],
    [2, 3],
    [2, 4],
]

N,M =  map(int,input().split())
HRR = list(map(int,input().split()))
ARR = []
for i in range(M):
    ARR.append(list(map(int,input().split())))


def calculate(n, m, hrr, arr):
    dict = {}
    for i in range(n):
        dict.__setitem__(i, True)

    for ar in arr:
        start = ar[0] - 1
        end = ar[1] - 1
        if hrr[start] > hrr[end]:
            dict.__setitem__(end, False)
        if hrr[start] == hrr[end]:
            dict.__setitem__(start, False)
            dict.__setitem__(end, False)

        if hrr[start] < hrr[end]:
            dict.__setitem__(start,False)


    print(sum(list(dict.values())))

calculate(N,M,HRR,ARR)

Measured memory_bytes: 42700
import math
 
def combination(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)
 

n,p = map(int,input().split())

t = list(map(int,input().split()))

gu = 0

ki = 0

for i in t:
    if i%2==0:
        gu += 1
    else:
        ki += 1

gukumi = 0

kikumi = 0

for i in range(1,gu+1):
    gukumi += combination(gu,i)

if p == 0:
    for i in range(2,ki+1,2):
        kikumi += combination(ki,i)
    ans = kikumi+1+gukumi
else:
    for i in range(1,ki+1,2):
        kikumi += combination(ki,i)
    ans = kikumi
    

ans += gukumi*kikumi

print(ans)

Measured memory_bytes: 38568
#include<bits/stdc++.h>
#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) ((long long 1) << t)
#define PER(i,y,x) for(ll i=y; i>=x; i--)
#define vll vector<ll>
#define vvll vector<vector<ll>>
using namespace std;
typedef long long ll;
ll const MAX = 1e5 + 5;

queue<ll> que;
vvll g(MAX);

ll const MOD = 1e9 + 7;
ll mod_p(ll x, ll y) {
	   x %= MOD;
	   y %= MOD;
	   return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
	   x %= MOD;
	   y %= MOD;
	   return x * y%MOD;
}

ll mod_pow(ll x, ll t) {
	   x %= MOD;
	   if (t == 0) {
			   return 1;
	   }
	   else {
			   ll v = mod_pow(x, t / 2);
			   if (t % 2 == 0) {
					   return v * v % MOD;
			   }
			   else {
					   return v * v%MOD * x %MOD;
			   }
	   }
}

ll mod_inv(ll x) {
	   return mod_pow(x, MOD - 2);
}

vll parent(MAX, -1);
int main(){
	ll n,k;
	cin >> n >> k;
	REP(i,1,n-1){
		ll a,b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	ll ans = 1;
	vll color(MAX, k);
	que.push(1);
	parent[1] = 0;
	while(!que.empty()){
		ll cur = que.front();
		que.pop();
		ans = mod_m(ans, color[parent[cur]]);
		color[cur]--;
//		cout << cur << " ! " << color[parent[cur]] << endl;
		color[parent[cur]]--;
		for(auto nex: g[cur]){
			if(parent[nex] != -1){
				continue;
			}
			parent[nex] = cur;
			que.push(nex);
			color[nex]--;
//			cout << cur << " " << nex << endl;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 8948
N,M=map(int,input().split())
ans,L,R=0,0,N
for i in range(M):
  Ltmp,Rtmp=map(int,input().split())
  if L<Ltmp:
    L=Ltmp
  if R>Rtmp:
    R=Rtmp
if L<=R:
  ans=R-L+1
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;

int main() {
	string s; cin >> s;
	int ans = 0;
	for (int i = 0; i < (int)s.length(); ++i) {
		if (i % 2 == 0) {
			ans += s[i] == 'p' ? -1 : 0;
		}
		else {
			ans += s[i] == 'g' ? 1 : 0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pint = pair<int, int>;
using Graph = vvi;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

vb seen;
Graph g;

int main() {
    int h, w;
    cin >> h >> w;
    vs s(h);
    rep(i, h) cin >> s[i];

    int white = 0;
    rep(i, h) rep(j, w) if(s[i][j] == '.') white++;

    vvi dist(h, vi(w, -1));
    queue<P> q;
    auto update = [&](int i, int j, int x) {
        if(dist[i][j] != -1) return;
        dist[i][j] = x;
        q.push(P(i, j));
    };

    update(0, 0, 0);

    while(!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();

        rep(i, 4) {
            int ny = y + dy[i], nx = x + dx[i];

            if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if(s[ny][nx] == '#') continue;

            update(ny, nx, dist[y][x] + 1);
        }
    }

    if(dist[h-1][w-1] == -1) cout << -1 << endl;
    else cout << white - dist[h-1][w-1] - 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int N,A,B;
	int min;
	char s[101];

	scanf("%d %d %d",&N,&A,&B);
	if(N*A < B){ min = A*N;
	}else{	min = B;}

	printf("%d \n",min);
	return 0;
}

Measured memory_bytes: 128
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
inf = 10**20

N,K = map(int,input().split())
A = list(map(int,input().split()))

def distance(x,d):
    r = x%d
    return(min(r,d-r))

def cost(d,numList):
    r = list(map(lambda x: x%d, numList))
    r.sort(reverse=True)
    p = sum(r)//d
    c = 0
    for i in range(p):
        c += d - r[i]
    return(c)

def divisors(n):
    sq = math.ceil(math.sqrt(n))
    ans = []
    for i in range(1,sq):
        if n%i == 0:
            ans.append(i)
            ans.append(n//i)
    return(ans)

s = sum(A)
divs = divisors(s)
ans = 1
for d in divs:
    c = cost(d, A)
    if c <= K:
        ans = max(ans,d)
print(ans)

Measured memory_bytes: 6424
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <utility>
#include <bitset>

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

using namespace std;
using ll = long long int;
using ld = long double;
using vl = vector<ll>;
using vd = vector<ld>;

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

	string s;
	cin >> s;

	bool used[26];
	REP(i, 26) {
		used[i] = false;
	}
	REP(i, s.size()) {
		used[s[i] - 'a'] = true;
	}
	REP(i, 26) {
		char ness;
		if (!used[i]) {
			ness = 'a' + i;
			cout << s << ness;
			return 0;
		}
	}
	int flag = 0;
	for (int i = s.size() - 1; i > 0; i--){
		if (s[i] > s[i - 1]) {
			flag = i; break;
		}
	}
	if (flag) {
		char nass;
		for (int i = s.size() - 1; i >= flag; i--) {
			if (s[i] > s[flag - 1]){
				nass = s[i]; break;
			}
		}
		cout << s.substr(0,flag-1) << nass;
		return 0;
	}
	else {
		cout << -1;
		return 0;
	}
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int n,v[101],i,l,r,mmin=101,nr;
int main()
{
    cin >> n;
    l = 1;
    r = n+1;
    for(i = 1; i <= n; ++i)
        cin >> v[i];
    while(l != n+1)
    {
        mmin = 101;
        r = n+1;
        for(i = l; i <= n; ++i)
        {
            if(v[i] == 0)
            {
                r = i;
                break;
            }
            else
                mmin = min(v[i],mmin);
        }
        for(i = l; i < r; ++i)
            v[i]-= mmin;
        if(mmin < 101)
            nr += mmin;
    if(l == r) l++;
    }
    cout << nr;
    return 0;
}


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

#define N 100000
#define M 100000

int aa[N], bb[M], cc[M];

int compare_a(const void *a, const void *b) {
	int ia = *(int *) a;
	int ib = *(int *) b;

	return ia - ib;
}

int compare_i(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return cc[j] - cc[i];
}

int main() {
	static int ii[M];
	int n, m, i, j, k;
	long long ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < m; i++) {
		scanf("%d%d", &bb[i], &cc[i]);
		ii[i] = i;
	}
	qsort(aa, n, sizeof *aa, compare_a);
	qsort(ii, m, sizeof *ii, compare_i);
	for (i = j = 0; j < m; i = k, j++)
		for (k = i; k < n && bb[ii[j]] > 0; k++)
			if (cc[ii[j]] > aa[k]) {
				aa[k] = cc[ii[j]];
				bb[ii[j]]--;
			}
	ans = 0;
	for (i = 0; i < n; i++)
		ans += aa[i];
	printf("%lld\n", ans);
	return 0;
}


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

int main(){
  int S, u = 0;
  cin >> S;
  
  while(S/500 > 0){
    S -= 500;
    u += 1000;
  }
  while(S/5 > 0){
    S -= 5;
    u += 5;
  }
  
  cout << u << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define REP(i,j,n) for(int i = j;i < (n);i++)
#define intput(i) cout << i << endl
#define ll long long
#define stringput(s) cout << (string)(s) << endl
int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int sum = a + b;
  if(sum >= c) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll R, C, N;
struct Node {
  int x, y, val;
  Node() = default;
  Node(int a, int b, int c) : x(a), y(b), val(c) {}
};
bool onEdge(int x, int y) { return x == 0 || x == R || y == 0 || y == C; }
vector<Node> up;
vector<Node> lleft;
vector<Node> rright;
vector<Node> down;

void addNode(int x, int y, int val) {
  Node cur = Node(x, y, val);
  if (x == 0) {
    up.push_back(cur);
    return;
  }

  if (x == R) {
    down.push_back(cur);
    return;
  }

  if (y == 0) {
    lleft.push_back(cur);
    return;
  }

  if (y == C) {
    rright.push_back(cur);
    return;
  }
}
bool calc() {
  cin >> R >> C >> N;

  for (int i = 0; i < N; ++i) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    if (!onEdge(x1, y1) || !onEdge(x2, y2)) continue;
    addNode(x1, y1, i);
    addNode(x2, y2, i);
  }

  auto sortx = [](const Node &n1, const Node &n2){
    return n1.x < n2.x;
  };
  auto sorty = [](const Node &n1, const Node &n2){
    return n1.y < n2.y;
  };
  sort(up.rbegin(), up.rend(), sorty);
  sort(lleft.begin(), lleft.end(), sortx);
  sort(down.begin(), down.end(), sorty);
  sort(rright.rbegin(), rright.rend(), sortx);

  vector<Node> line;
  line.insert(line.end(), up.begin(), up.end());
  line.insert(line.end(), lleft.begin(), lleft.end());
  line.insert(line.end(), down.begin(), down.end());
  line.insert(line.end(), rright.begin(), rright.end());

  stack<Node> stk;
  for (auto const &node : line) {
    if (stk.size() && stk.top().val == node.val) {
      stk.pop();
    } else {
      stk.push(node);
    }
  }

  return stk.empty();
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  if (calc()) {
    cout << "YES";
  } else
    cout << "NO";
  cout << endl;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

string s;
ll dp[100010][10][13];

ll solve(int pos, int val, int tmp) {
    if (pos >= s.size()) {
        return (tmp % 13 == 5);
    }
    if (dp[pos][val][tmp] != -1) return dp[pos][val][tmp] % MOD;
    ll ret = 0LL;
    if (s[pos] == '?') {
        for (int i = 0; i <= 9; ++i) {
            int k = tmp * 10 + i;
            int x = k / 13;
            int ntmp = k - x * 13;
            ret = (ret % MOD + solve(pos + 1, i, ntmp) % MOD) % MOD;
        }
    }
    else {
        int k = s[pos] - '0';
        int x = (k + tmp * 10) / 13;
        int ntmp = (k + tmp * 10) - x * 13;
        ret = (ret % MOD + solve(pos + 1, k, ntmp) % MOD) % MOD;
    }
    return dp[pos][val][tmp] = ret;
}

int main() {
    cin >> s;
    memset(dp, -1LL, sizeof(dp));
    cout << solve(0, 0, 0) << endl;
    return 0;
}


Measured memory_bytes: 109824