akhauriyash/Code-Regression huggingface dataset:
N, M = map(int, input().split())
pathmat=[[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    pathmat[a-1][b-1] = 1
    pathmat[b-1][a-1] = 1

visited =  [False]*N
visited[0] = True


def DFS(now, visited):
    if all(visited):
        return 1
    ans = 0
    for i in range(N):
        if not pathmat[now][i]:
            continue
        if visited[i]:
            continue
        visited[i]=True
        ans += DFS(i, visited)
        visited[i]=False
    return ans

print(DFS(0,visited))

        
            


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

int main() {
	int a[2],k;
	cin >> a[0] >> a[1] >> a[2] >> k;
	sort (a,a+3);
	for (int i=0;i<k;i++)a[2]=a[2]*2;
	cout << a[0]+a[1]+a[2] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int n, a, cnt = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		if (a & 1) {
			cnt++;
		}
	}
	if (cnt % 2 == 0) {
		printf("YES\n");
	} else {
		printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  int a,b,c;cin>>a>>b>>c;
  if(b%a==0)cout<<"OK";
  else{
    if(b%a!=0&&b/a*a+a<=c)cout<<"OK";
    else cout<<"NG";
  }
  }

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,w;
  while(1){
    cin >>n>>w;
    if(n+w == 0)break;
    int num[1000];
    for(int i=0 ; i < 1000 ; i++)num[i]=0;
    int mx=0;
    int mxx=0;
    for(int i=0 ; i < n ; i++){
      int temp;
      cin >>temp;
      num[temp/w]++;
      mx=max(mx,temp/w);
      mxx=max(mxx,num[temp/w]);
    }
    double ans=0;
    for(int i=0 ; i <= mx ; i++){
      ans+=((double)(mx-i)/mx)*((double)num[i]/mxx);
    }
    cout <<ans+0.01<<endl;
  }
  return 0;
}

Measured memory_bytes: 1236
fun main(args: Array<String>) = ABC159B.main()

object ABC159B {
    fun readInt() = readLine()!!.toInt()
    fun readInts() = readLine()!!.split(" ").map { it.toInt() }

    fun main() {
        val S = readLine()!!
        val result = S.isKaibun() && S.cond2() && S.cond3()
        println(if (result) "Yes" else "No")
    }

    fun String.isKaibun(): Boolean = this == this.reversed()

    fun String.cond2(): Boolean {
        val N = this.length
        val sub = this.take((N - 1) / 2)
        return sub.isKaibun()
    }

    fun String.cond3(): Boolean {
        val N = this.length
        val sub = this.drop((N + 3) / 2 - 1)
        return sub.isKaibun()
    }
}

Measured memory_bytes: 33816
T = input()

s = list(T)
for i, x in enumerate(T):
  if x == "?":
    s[i] = "D"


count = 0
flag = False
for x in s:
  if x == "P":
    flag = True
  
  if x == "D":
    count += 1
    if flag:
      count += 1
      flag = False

print("".join(s))

Measured memory_bytes: 10780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int L, R, d; cin >> L >> R >> d;
    int ans = 0;
    for (int i = L; i <= R; i++) {
        if (i % d == 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3592
using System;

class Rectangle{
      static void Main(string[] args){
      	     string[] str = Console.ReadLine().Split(' ');
      	     int n = int.Parse(str[0]);
	     int m = int.Parse(str[1]);
	     int s = n * m;
	     int l = 2*n + 2*m;
	     Console.WriteLine("{0} {1}",s,l);
	     }
}

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

#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const ll MOD = 1e9+7;
const ll INF = (ll)1<<62;

bool comp(pair<int, int> a, pair<int, int> b){
	double av = (double)a.second/a.first;
	double bv = (double)b.second/b.first;
	return av<bv;
}

int main(){
	int H, N;
	vector<pair<int, int> > a;
	vector<ll> dp;
	cin>>H>>N;
	a.assign(N, {0, 0});
	int maxi = 0;
	for(int i=0;i<N;i++){
		cin>>a[i].first>>a[i].second;
		maxi = max(maxi, a[i].first);
	}
	dp.assign(H+1+maxi, INF);
	dp[0] = 0;
	//sort(a.begin(), a.end(), comp);
	//for(int i=0;i<N;i++)
	//cout<<a[i].first<<" "<<a[i].second<<" "<<(double)a[i].second/a[i].first<<"==\n";
	for(int h=0;h<=H+maxi;h++){
		for(int i=0;i<N;i++){
			dp[h] = min(dp[h], dp[max(0, h-a[i].first)]+a[i].second);
		}
		//cout<<dp[h]<<"\n";
	}
	ll ans = INF;
	for(int i=H;i<=H+maxi;i++)
		ans = min(ans, dp[i]);
	cout<<ans<<"\n";
	return 0;
}

/*
15 3
8 3
4 2
2 1

dp[h][i] = Min. cost to reduce H to less than or equal to zero using a[i, i+1, ... N] 

*/

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(6);
    /*start*/
    string s;
    cin >> s;
    rep(i, s.size())
    {
        s[i] = 'x';
    }
    c(s);
    return 0;
}

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

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


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

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";

const ld pie = 3.14159265358979 ;
const ll mod = 1e9 + 7 ;

string vow = "aeiou";

void solve ( int test_case )
{
    ll a , b ;
    cin >> a >> b ;

    ll ans = max ( a-2*b , 0LL ) ;
    cout << ans ; line
}

int main()
{
    int t = 1;
    //cin >> t;

    for ( int i=0 ; i < t ; i++ ) solve(i);
    return 0;
}


Measured memory_bytes: 256
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	A.sort(reverse = True)
	comfort = A[0]
	cnt = 0
	for i in range(2, n):
		if i % 2 == 0:
			cnt += 1
		comfort += A[cnt]
	print(comfort)	

if __name__ == "__main__":
	main()

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

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

int dp[4001];

int main(void){
	string s,t;
	while(cin >> s >> t){
		if(cin.eof()) break;
		int n=s.size(),m=t.size();
		

		int ans=0;
		rep(start,n){
			rep(i,max(n,m)){
				if(start+i>=n||i>=m) break;
				if(s[start+i]==t[i])
					dp[i+1]=dp[i]+1;
				else
					dp[i+1]=0;
				ans=max(ans,dp[i+1]);
			}
		}

		rep(start,m){
			rep(i,max(n,m)){
				if(i>=n||i+start>=m) break;
				if(s[i]==t[i+start])
					dp[i+1]=dp[i]+1;
				else
					dp[i+1]=0;
				ans=max(ans,dp[i+1]);
			}
		}		
		cout << ans << endl;		
	}
	return 0;
}

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

bool solve() {
    vector<char> stack;
    int stack_maru = 0;
    int stack_kaku = 0;
    bool ans = false;
    bool err = false;
    string str;
    getline(cin, str);
    if(str == ".") return false;
    else {
        for(auto c : str) {
            if(c=='(') stack.push_back('(');
            if(c=='[') stack.push_back('[');
            if(c==')') {
                if(stack.size()>0 && stack.back() == '(') {
                    stack.pop_back();
                } else {
                    err = true;
                    break;
                }
            }
            if(c==']') {
                if(stack.size()>0 && stack.back() == '[') {
                    stack.pop_back();
                } else {
                    err = true;
                    break;
                }
            }
        }
        if(stack.size()==0 && !err) cout << "yes" << endl;
        else cout << "no" << endl;
        return true;
    }
}

int main() {
    while(solve()) {}
}



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

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < 9; i++) {
    if(n > 111 * i && n <= 111 * (i + 1)) {
      cout << 111 * (i + 1) << endl;
    }
  }
}

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

namespace _0017
{
    public class Program

    {
        public static void Main(string[] args)
        {
            Calc calc = new Calc();
            List<string> ans = new List<string>();

            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                List<decimal> input = Console.ReadLine().Split(' ').Select(decimal.Parse).ToList();
                List<decimal> v_ab = new List<decimal> { input[2] - input[0], input[3] - input[1] };
                List<decimal> v_cd = new List<decimal> { input[6] - input[4], input[7] - input[5] };
                ans.Add(calc.ExteriorProduct(v_ab, v_cd));
            }

            foreach (string item in ans)
            {
                Console.WriteLine(item);
            }
        }
    }

    class Calc
    {
        internal string ExteriorProduct(List<decimal> v1, List<decimal> v2)
        {
            string ans;
            decimal e_p_x = v1[0] * v2[1] - v1[1] * v2[0];

            return ans = (e_p_x == 0) ? "YES" : "NO";
        }
    }

}


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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  int n,m;
  cin >> n >> m;
  const int max_n = 1e5;
  vector<int> a(n);
  // priority_queue<int> a;
  for(int i = 0; i < n; i++) {
    // int in;
    // cin >> in;
    // a.push(in);
    cin >> a[i];
  }

  sort(a.begin(), a.end());
  
  for(int i = 0; i < m; i++){
    int left = 0;
    int right = n-1;
    int price = a[n-1] / 2;
    while(right - left > 1){
      int x = (right + left) / 2;
      if(a[x] > price) right = x;
      else left = x;
    }
    // cout << a.size() << endl;
    // a.erase(a.begin() + n);
    if(a[left] > price) a.insert(a.begin() + left, price);
    else a.insert(a.begin() + right, price);
    // for(int i = 0; i < a.size(); i++) cout << a[i] << ", ";
    // cout << endl;

    // int price = a.top() / 2;
    // a.pop();
    // a.push(price);
  }
  
  long long sum = 0;
  for(int i = 0; i < n; i++) sum += a[i];
  // for(int i = 0; i < n; i++){
  //   sum += a.top();
  //   a.pop();
  // }
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 4152
#include <bits/stdc++.h>
using namespace std;
//Author: Ezio Sam
/* Shorthands */
#define ll long long
#define pb push_back
#define em emplace_back
#define mp make_pair
#define sp " "
#define cs "Case "
#define fi first
#define sn second

/* STL */
#define mem(a,n) memset(a, n, sizeof(a));
#define all(x) x.begin(),x.end()
#define alr(x) x.rbegin(),x.rend()
#define sz(x)  (int)x.size()
#define mx(v)  *max_element(v.begin(),v.end())
#define mxi(v) distance(v.begin(),max_element(v.begin(),v.end()))
#define mxa(a) *max_element(a, a.size())
#define r(a)   reverse(a.begin(),a.end())
/* loops */
#define fa(i, a, b) for (auto (i) = (a); (i) < (b); ++(i))
#define fr(i,n)   for(__typeof(n) i=0;i<(n);i++)
#define fn(i,n)   for(__typeof(n) i=1;i<=(n);i++)
/*Special*/
#define Ezio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define db(something)  cerr<<#something<<" - "<<something<<"\n";

int main()
{

   Ezio
   ll t,m,n,x,y,a,b;
   string s;

   cin>>n>>m;
   x=0;
   while(n--){
    cin>>a>>b;
    y= ceil(sqrt(a*a +b*b));
    if(y<=m) x++;
   }
   cout<<x<<endl;

   return 0;
}


Measured memory_bytes: 3684
class Dice:
        def __init__(self, strLabel):
                self.label = strLabel.split()
                self.label[0] = int(self.label[0])
                self.label[1] = int(self.label[1])
                self.label[2] = int(self.label[2])
                self.label[3] = int(self.label[3])
                self.label[4] = int(self.label[4])
                self.label[5] = int(self.label[5])
        def roll(self, r):
                if r == 'E':
                        temp = self.label[3]
                        self.label[3] = self.label[5]
                        self.label[5] = self.label[2]
                        self.label[2] = self.label[0]
                        self.label[0] = temp
                elif r == 'W':
                        temp = self.label[0]
                        self.label[0] = self.label[2]
                        self.label[2] = self.label[5]
                        self.label[5] = self.label[3]
                        self.label[3] = temp
                elif r == 'N':
                        temp = self.label[0]
                        self.label[0] = self.label[1]
                        self.label[1] = self.label[5]
                        self.label[5] = self.label[4]
                        self.label[4] = temp
                elif r == 'S':
                        temp = self.label[4]
                        self.label[4] = self.label[5]
                        self.label[5] = self.label[1]
                        self.label[1] = self.label[0]
                        self.label[0] = temp

dice = Dice(input())
rollList = list(input())

for i in range(len(rollList)):
        dice.roll(rollList[i])

print(dice.label[0])


Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
int factorial(int n);
int factorial(int n)
{
    if(n==1)
    {
        return 1;
    }
    else
    {
        return n*factorial(n-1);
    }

}

bool is_prime(ll n) {
    // Assumes that n is a positive natural number
    // We know 1 is not a prime number
    if (n == 1) {
        return false;
    }

    ll i = 2;
    // This will loop from 2 to int(sqrt(x))
    while (i*i <= n) {
        // Check if i divides x without leaving a remainder
        if (n % i == 0) {
            // This means that n has a factor in between 2 and sqrt(n)
            // So it is not a prime number
            return false;
        }
        i += 1;
    }
    // If we did not find any factor in the above loop,
    // then n is a prime number
    return true;
}
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
typedef unsigned long long  ull;

int check(int x,vector <int> a,int n)
{  int county=0;
  map <int,int> mapa;
    for(int i=0;i<n;i++)
    {
        mapa.insert(pair<int,int>(a[i],0));
    }
    for(int i=0;i<n;i++)
    {
        mapa[a[i]]++;
    }
   // cout<<mapa[1]<<mapa[2]<<mapa[3]<<mapa[4]<<mapa[5]<<endl;
    for(int i=0;i<a.size();i++)
    {   mapa[a[i]]--;
        if(mapa[abs(a[i]-x)]>0)
        {
            county++;


            mapa[abs(a[i]-x)]--;
        }


    }
    return county;
}



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

string s;
cin>>s;
int maxi=0;
int county=0;
for(int i=0;i<s.size();i++)
{

    if(s[i]=='R')
    {
        county++;
        if(i+1==s.size())
        {
            maxi=max(maxi,county);
        }
    }
    else if(s[i]=='S')
    {
        maxi=max(maxi,county);
        county=0;
    }
}
cout<<maxi<<endl;



}

Measured memory_bytes: 3656
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) (a).begin(), (a).end()
#define AALL(a, n) (a), ((a) + (n))
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define MODNUM (static_cast<int>(1e9 + 7))
#define MOD(x) ((x) % MODNUM)

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

const int INF = 2e9;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

inline int toInt(string s) {
	int v;
	istringstream sin(s);
	sin >> v;
	return v;
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; static_cast<int>(i * 1.08) <= n; i++) {
		int tmp = static_cast<int>(i * 1.08);
		if(tmp == n) {
			printf("%d\n", i);
			return 0;
		}
	}
	puts(":(");
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long ll;
void Read(int &x){
    static char c;
    while(!isdigit(c=getchar()));
    x=(c^48);
    while(isdigit(c=getchar()))
        x=x*10+(c^48);
    return;
}
void Read(ll &x){
    static char c;
    while(!isdigit(c=getchar()));
    x=(c^48);
    while(isdigit(c=getchar()))
        x=x*10+(c^48);
    return;
}
int n;
ll a[100005],s=1LL;
int main(){
    Read(n);
    for(int i=1;i<=n;++i){
        Read(a[i]);
        if(!a[i])
            return puts("0"),0;
    }
    for(int i=1;i<=n;++i){
        if(a[i]>1000000000000000000LL/s)
            return puts("-1"),0;
        s*=a[i];
    }
    printf("%lld\n",s);
    return 0;
}

Measured memory_bytes: 2380
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstdio>
using namespace std;

#define int long long
#define INF 1e18

signed main() {
    int n, m; cin >> n >> m;
    vector<int> cnt(m, 0);

    for(int i = 0; i < n; i++) {
        int k; cin >> k;
        for(int j = 0; j < k; j++) {
            int a; cin >> a;
            cnt[a - 1]++;
        }
    }

    int ans = 0;

    for(int i = 0; i < m; i++) {
        if(cnt[i] == n) ans++;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    long long ans = accumulate(a.begin(), a.end(), 0LL) - n;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//g++ -std=c++11 

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7

ll N, M;
ll S[2005];
ll T[2005];
ll memo[2005][2005];

int main(){
	cin >> N >> M;
	rep(i, N)  cin >> S[i + 1];
	rep(i, M) cin >> T[i + 1];


	rep(i, N + 1) memo[i][0] = 1;
	rep(j, M + 1) memo[0][j] = 1;

	// S
	for(ll i = 1; i <= N; i++) {
		// T
		for(ll j = 1; j <= M; j++) {
			if(S[i] == T[j]) {
				memo[i][j] = memo[i-1][j] + memo[i][j-1];
				memo[i][j] += DIV;
				memo[i][j] %= DIV;
			} else {
				memo[i][j] = memo[i-1][j] + memo[i][j-1] - memo[i-1][j-1];
				memo[i][j] += DIV;
				memo[i][j] %= DIV;
			}	
		}
	}

	cout << memo[N][M] << endl;
}


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

#define int long long

#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define ALL(v) (v).begin(), (v).end()

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

using pi = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vvb = vector<vb>;

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

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; }


signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    double a, b, c; cin >> a >> b >> c;
    c = c*acos(-1)/180.0;
    cout << a * b * sin(c) / 2.0 << endl << sqrt(a*a+b*b-2*a*b*cos(c)) + a + b << endl << b * sin(c) << endl;
}


Measured memory_bytes: 3556
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,a,maxv,minv=1000000009;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		if(a>maxv)maxv=a;
		if(a<minv)minv=a;
	}
	cout<<abs(maxv-minv);
} 

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
int n, m, x;
vector<int> data(100);
void solve(){
    cin >> n >> m >> x;
    int low = 0, high = 0;
    for(int i = 0; i < m; i++){
        cin >> data.at(i);
        if(data.at(i) > x)
        high++;
        else 
        low++;
    }
    cout << min(high, low) << endl;
}
int main(){
    solve();
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def run_length_encoding(s):
    '''連長圧縮を行う
    s ... iterable object e.g. list, str 
    return
    ----------
    s_composed,s_num,s_idx
    それぞれ、圧縮後の文字列、その文字数、その文字が始まるidx'''
    s_composed, s_sum = [], []
    s_idx = [0]
    pre = s[0]
    cnt = 1
    for i, ss in enumerate(s[1:], start=1):
        if pre == ss:
            cnt += 1
        else:
            s_sum.append(cnt)
            s_composed.append(pre)
            s_idx.append(i)
            cnt = 1
            pre = ss
    s_sum.append(cnt)
    s_composed.append(pre)
    # assert len(s_sum) == len(s_composed)
    return s_composed, s_sum, s_idx


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N = a_int()
A = ints()

# 原則安いときに買って高いときに売る
# 複利の計算が入るのがめんどいな
# 極大極小みつけて売り買いかな
# 同じ金額の日は無いも等しいので消しちゃうか
A, _, _ = run_length_encoding(A)
A = [400] + A + [0]
# print(A)

torihiki = []
for i in range(len(A) - 2):
    if A[i] > A[i + 1] and A[i + 1] < A[i + 2]:
        torihiki.append(A[i + 1])
    elif A[i] < A[i + 1] and A[i + 1] > A[i + 2]:
        torihiki.append(A[i + 1])

# 愚直シミュレーション
en = 1000
kabu = 0

for i, a in enu(torihiki):
    if i & 1:  # 売る
        en += kabu * a
        kabu = 0
    else:  # 買う
        kabu = en // a
        en %= a
print(en)


Measured memory_bytes: 67988
#include <bits/stdc++.h>
using namespace std;
//Coded in Dongge Jifang 4

int n,k,N;
long long a[100005],b[100005];
long long qzh[100005];
long long liml[100005],limr[100005];
long long dp[100005],dp2[100005];
long long ans=0x3f3f3f3f3f3f3f3fLL;

struct Node{
	long long num;
	Node *l,*r;
	Node(){
		num=n+1;
		l=r=0;
	}
}*root,*root2;

struct segtree{
	void init(Node* &now){
		if(!now){
			return;
		}
		init(now->l);
		init(now->r);
		delete now;
		now=0;
	}
	void update(int l,int r,long long x,Node* &now,int nl=0,int nr=k-1){
		if(!now){
			now=new Node();
		}
		if(nl>=l&&nr<=r){
			now->num=min(now->num,x);
			return;
		}
		if(nl>r||nr<l){
			return;
		}
		int m=(nl+nr)>>1;
		update(l,r,x,now->l,nl,m);
		update(l,r,x,now->r,m+1,nr);
		//now->num=min(now->l->num,now->r->num);
	}
	void upd(int l,int r,long long x,Node* &now){
		l=(l%k+k)%k;
		r=(r%k+k)%k;
		if(l<=r){
			update(l,r,x,now);
		}else{
			update(l,k-1,x,now);
			update(0,r,x,now);
		}
	}
	long long qmin(int whr,Node* &now,int nl=0,int nr=k-1){
		if(!now){
			now=new Node();
		}
		if(nl==whr&&nr==whr){
			return now->num;
		}
		int m=(nl+nr)>>1;
		if(m>=whr){
			return min(now->num,qmin(whr,now->l,nl,m));
		}else{
			return min(now->num,qmin(whr,now->r,m+1,nr));
		}
	}
}seg1,seg2;

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",a+i,b+i);
		if(b[i]==1&&a[i]*2>k){
			puts("-1");
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		qzh[i]=qzh[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		if(b[i]==1){
			liml[N]=2*(k-qzh[i]%k)%k;
			limr[N]=2*(k-qzh[i-1]%k)%k;
			N++;
		}
	}
	seg1.init(root);
	seg2.init(root2);
	dp[N-1]=dp2[N-1]=0;
	seg1.upd(liml[N-1]+1,limr[N-1]-1,N-1,root);
	seg2.upd(liml[N-1]+1,limr[N-1]-1,N-1,root2);
	//cerr<<liml[N-1]<<' '<<limr[N-1]<<endl;
	for(int i=N-2;i>=0;i--){
		int x=seg1.qmin(liml[i],root);
		//cerr<<liml[i]<<' '<<' '<<x<<endl;
		if(x==n+1){
			dp[i]=0;
		}else{
			dp[i]=min(dp[x]+((liml[x]-liml[i])%k+k)%k,dp2[x]+((limr[x]-liml[i])%k+k)%k);
		}
		x=seg2.qmin(limr[i],root2);
		if(x==n+1){
			dp2[i]=0;
		}else{
			dp2[i]=min(dp2[x]+((limr[x]-limr[i])%k+k)%k,dp[x]+((liml[x]-limr[i])%k+k)%k);
		}
		seg1.upd(liml[i]+1,limr[i]-1,i,root);
		seg2.upd(liml[i]+1,limr[i]-1,i,root2);
	}
	seg1.init(root);
	seg2.init(root2);
	for(int i=0;i<N;i++){
		int x=seg1.qmin(liml[i],root);
		//cerr<<i<<' '<<x<<' '<<n<<' '<<dp[i]<<endl;
		if(x==n+1){
			ans=min(ans,dp[i]);
		}
		x=seg2.qmin(limr[i],root2);
		if(x==n+1){
			ans=min(ans,dp2[i]);
		}
		seg1.upd(liml[i]+1,limr[i]-1,i,root);
		seg2.upd(liml[i]+1,limr[i]-1,i,root2);
	}
	printf("%lld\n",ans+qzh[n]*2);
	return 0;
}


Measured memory_bytes: 174080
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
    System.out.println(Math.max(Math.max(A, B), C) - Math.min(Math.min(A, B), C));
  }
}

Measured memory_bytes: 23764
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp make_pair

const char cs[] = "01+-*()";
char src[128], s[128];
int _i, token;

void check(int a) {
    if (a < 0 || a >= 1024) throw "overflow";
}

int next() {
    if (s[_i] == 0) return 0;
    if (s[_i] == '0' || s[_i] == '1') {
        int a = 0;
        while (s[_i] == '0' || s[_i] == '1') {
            a = a * 2 + (s[_i++]-'0');
            check(a);
        }
        return -(a+1);
    }
    return s[_i++];
}

pair<int, bool> expr(), term(), factor();

int parse() {
    _i = 0;
    token = next();
    const int ans = expr().first;
    if (token != 0) throw "ill end";
    return ans;
}

pair<int, bool> expr() {
    pair<int, bool> a = term();
    while (token == '+' || token == '-') {
        const char op = token;
        token = next();
        const pair<int, bool> b = term();
        a.first = op == '+' ? a.first + b.first : a.first - b.first;
        a.second = true;
        check(a.first);
    }
    return a;
}

pair<int, bool> term() {
    pair<int, bool> a = factor();
    while (token == '*') {
        token = next();
        const pair<int, bool> b = factor();
        a.first = a.first * b.first;
        a.second = true;
        check(a.first);
    }
    return a;
}

pair<int, bool> factor() {
    if (token < 0) {
        const int a = -(token+1);
        token = next();
        return mp(a, false);
    }
    if (token == '(') {
        token = next();
        pair<int, bool> a = expr();
        if (a.second == false) throw "(-)";
        if (token != ')') throw "unmatched";
        token = next();
        return mp(a.first, false);
    }
    throw "ill char";
}

int main() {
    scanf("%s", src);
    int ans = -1;
    rep (b, 7*7*7*7*7) {
        for (int i = 0, p = b; src[i]; i++) {
            s[i] = src[i];
            if (s[i] == '.') {
                s[i] = cs[p%7];
                p /= 7;
            }
        }
        try {
            ans = max(ans, parse());
        }
        catch (const char *err) {
            //printf("%s\n", err);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 1088
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair <int,int> pii;
typedef vector <pii> vpii;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef long long int lli;
typedef vector <lli> vlli;
typedef vector <vlli> vvlli;
typedef vector <string> vs;
typedef vector <bool> vb;

#define rep(i, n) for( i = 0; i < (n); ++i)
#define repA(i, a, n) for( i = a; i <= (n); ++i)
#define repD(i, a, n) for( i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sortr(x) sort(x.begin(),x.end(),greater <int> ())
#define mod 1000000007
#define ff first
#define ss second
#define fill(a,c)  memset(a, c, sizeof (a))
#define formap(i,v) for(auto &i: v)
#define dbg(x) cout << #x << " = " << x << '\n'
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it<<endl;} cerr<<endl
#define dbgstlp(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it.first<<" , "<<it.second<<endl;} cerr<<endl
#define PI  3.14159265358979323846
#define pb push_back



int main() {
    cin.sync_with_stdio(0);cin.tie(0);
    cin.exceptions(cin.failbit);
    
    
    int i,j,k,n,cnt=0,x;
    cin>>n;
    vi a(n+1,0);
    for (i=1;i*i<=n;i++){
        for (j=1;i*i+j*j<=n;j++){
            for (k=1;;k++){
               x= i*i+j*j+k*k+i*j+j*k+i*k;
               if (x>n)break;
               else a[x]++;
            }
        }
    }
    repA(i,1,n)cout<<a[i]<<endl;
    
    
    
    
    
    
    
    
    
    
     
   
   
	return 0;
}


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

int main() {
  string S; long long K; cin>>S>>K;
  bool ans = true;
  for(int i=0; i<min(K,(long long)S.size()); i++){
    if(S.at(i) >='2'){
      ans = false;
      cout<<S.at(i)<<endl;
      break;
    }
  }
  if(ans){
    cout<<'1'<<endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<new>

using namespace std;
#define ALLAY_SIZE(a)  sizeof((a))/sizeof(*(a))

enum BASE_NO{
  FIRST = 0,
  SECOND,
  THIRD,

  BASE_NUM
};

enum PUT_IN {
  HIT = 0,
  HOMERUN,
  OUT,

  IN_NUM
};
static const string put_in[IN_NUM]{
  "HIT",
  "HOMERUN",
  "OUT"
};

class Base
{
public:
  Base() { Reset(); }
  void BaseIn(int base) { base_exist[base] = true; }
  void BaseOut(int base) { base_exist[base] = false; }
  bool IsBaseIn(int base) { return base_exist[base]; }
  bool Rotate() { 
    bool add_score;

    // ??????????????????????????????
    for (int i = THIRD; i >= 0; i--) {
      int next_base = i + 1;
      
      // ???????????°??????????????´??????TRUE?????????
      if (i == THIRD) add_score = IsBaseIn(i);
      else            base_exist[next_base] = base_exist[i];
    }

    return add_score;
  }
  int Reset() {
    // ?????????????????????reset???????????°?????????
    int runnner_count = 0;
    for (int i = 0; i < ALLAY_SIZE(base_exist); i++) {
      if (IsBaseIn(i)) runnner_count++;
      BaseOut(i);
    }
    
    return runnner_count;
  }
private:
  bool base_exist[BASE_NUM];
};

class BaseballGame
{
public:
  BaseballGame() : score(0), out_count(0), is_game_end(false) {}
  void Hit() {
    //  ???????????????????????¬????????°?????????????????°?????????????¶???????
    if (base.Rotate())
      score++;
    //  ???????????????????????????????????????
    base.BaseIn(FIRST);
  }
  void Homerun() {
    //  ??°?????°??????????????????
    Hit();
    //  ???????????°?????¨????????¬????????????
    int add_score = base.Reset();
    // ?????????????????°????????°??????????????????
    score += add_score;
  }
  void Out() {
    // ??¢???????????????????????????
    out_count++;
    // ??¢?????????????????????3??????????????¨??????????????°??????
    if (out_count >= GAMEEND_OUT_NUM)
      is_game_end = true;
  }

  int   GameScore() {
    return score;
  }
  bool  IsGameEnd() {
    return is_game_end;
  }
private:
  static const int GAMEEND_OUT_NUM = 3;

	int   score;
  int   out_count;
  Base  base;
  bool  is_game_end;
};

int main() {
  int game_num;
  cin >> game_num;
  for (int i = 0; i < game_num; i++) {
    BaseballGame game;
    while (!game.IsGameEnd()) {
      string in_data;
      cin >> in_data;

      if (in_data == put_in[HIT])
        game.Hit();
      else if (in_data == put_in[HOMERUN])
        game.Homerun();
      else if (in_data == put_in[OUT])
        game.Out();
    }
    cout << game.GameScore() << endl;
  }
}

Measured memory_bytes: 1220
from math import ceil
from itertools import product

d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]

ans = 1000
for pat in product(["1", "0"], repeat=d):
    score = 0
    cnt = 0
    not_complete = 0
    for i, bl in enumerate(pat):
        if bl == "1":
            score += 100 * (i + 1) * pc[i][0] + pc[i][1]
            cnt += pc[i][0]
        else:
            not_complete = i

    if score < g:
        add = ceil((g - score) / (100 * (not_complete + 1)))
        if add < pc[not_complete][0]:
            cnt += add
        else:
            continue

    ans = min(ans, cnt)

print(ans)


Measured memory_bytes: 3188
import sys
N = int(input())
c = list(input())
n = 0
k = N - 1
for i in range(N):
    if c[i] == 'W':
        for j in range(k, i, -1):
            if c[j] == 'R':
                n += 1
                c[i] = 'R'
                c[j] = 'W'
                k = j - 1
                break
            if j == i + 1:
                print(n)
                sys.exit()
print(n)

Measured memory_bytes: 10692
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int u[maxn], to[maxn];
long long best[maxn];
void init(){ 
	for(int i = 0; i < maxn; i++){
		u[i] = i;
		to[i] = -1;
		best[i] = 1ll<<60;
	}
}
int find(int x){
	if(x == u[x]) return x;
	return u[x] = find(u[x]);
}
long long cost[maxn];
vector<pair<int,int> > e[maxn];
int main(){
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++) cost[i] = 1ll<<60;
	for(int i = 0; i < q; i++){
		int a, b; long long c; cin >> a >> b >> c;
		cost[a] = min(cost[a], c + 1);
		cost[b] = min(cost[b], c + 2);
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}
	for(int i = 0; i < 2 * n; i++){
		int now = i % n; 
		int prv = now - 1; if(prv < 0) prv += n;
		cost[now] = min(cost[now], cost[prv] + 2);
	}
	auto dist = [&](int u, int v){
		if(u == v) return 0ll;
		long long ans = 1ll<<60;
		for(int rot = 0; rot < 2; rot++){
			swap(u, v);
			if(u < v){
				ans = min(ans, cost[u] + (v - u - 1) * 2);
				ans = min(ans, cost[v] + (n - v + u - 1) * 2);
			}
		}		
		return ans;
	};
	init();
	set<int> all;
	for(int i = 0; i < n; i++){
		all.insert(i);
	}
	int comps = n;
	long long ans = 0;
	while(comps > 1){
		vector<pair<int,int> > vert;
		for(int i = 0; i < n; i++){
			vert.push_back({find(i), i});
			to[find(i)] = -1;
			best[find(i)] = 1ll<<60;
		}
		sort(vert.begin(), vert.end());
		int j = 0;
		for(int i = 0; i < n; i = j){
			while(j < n && vert[j].first == vert[i].first) j++;
			for(int k = i; k < j; k++) all.erase(vert[k].second);
			int head = vert[i].first;
			for(int k = i; k < j; k++){
				auto it = all.lower_bound(vert[k].second);
				int going;
				if(it == all.end()) going = *all.begin();
				else going = *it;
				long long d = dist(vert[k].second, going);
				int hgo = find(going);
				if(best[head] > d) best[head] = d, to[head] = going;
				if(best[hgo] > d) best[hgo] = d, to[hgo] = head;
			}
			for(int k = i; k < j; k++) all.insert(vert[k].second);
		}
		for(int i = 0; i < n; i++){
			int head = find(i);
			for(auto ed : e[i]){
				if(find(ed.first) != head){
					if(best[head] > ed.second){
						best[head] = ed.second;
						to[head] = ed.first;
					}
					if(best[find(ed.first)] > ed.second){
						best[find(ed.first)] = ed.second;
						to[find(ed.first)] = head;
					}
				}
			}
		}
		vector<pair<long long, int>> heads;
		for(int i = 0; i < n; i++) if(i == find(i)) heads.push_back({best[i], i});
		sort(heads.begin(), heads.end());
		for(auto h : heads){
			int head = h.second;
			if(find(head) != find(to[head])){
				ans += best[head];
				comps--;
				u[find(head)] = find(to[head]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 33780
//
//  main.cpp
//  B - One Clue
//
//  Created by Hashizo on 2019/08/10.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>

using namespace std;

#undef LONG_MAX
#undef LONG_MIN

#define LONG_MAX	9223372036854775807
#define LONG_MIN	(-LONG_MAX  -1)

#define ll long long

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

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

	ll low,hight;
	
	if ((x-k+1) < -1000000) {
		low =-1000000;
	}
	else {
		low =(x-k+1);
	}
	
	if ((x+k-1) < 1000000) {
		hight = (x+k-1);
	}
	else {
		hight = 1000000;
	}

	FOR(i, low, hight+1){
		cout << i << " ";
	}
	
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define sws ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INFINITO 1000000000
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define fo(i, n) for( int i = 0; i < n; i++ )


int main() {

    int n;
    cin >> n;

    vi p(n), q(n);
    fo(i, n) cin >> p[i];
    fo(i, n) cin >> q[i];

    int a = 1, b = 1;
    while ( prev_permutation(p.begin(), p.end()) ) a++;
    while ( prev_permutation(q.begin(), q.end()) ) b++;

    cout << abs(a - b) << endl;

    return 0;
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
  	cin >> a >> b;
  	cout << ((a * b) % 2 == 0 ? "Even" : "Odd") << '\n';
    return 0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define P pair<int,int>
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
#define Size(n) (n).size()

typedef long long ll;

using namespace std;

const int INF = 1e9,MOD = 1e9 + 7;
const ll LINF = 1e18;

//long long int kaizyo(long long int hh){
  //  cmp=1;
    //while(hh>1){
      //  cmp=(cmp*hh)%MOD;
        //hh--;
    //}
    //return cmp;
//}
//long long int ruizyo(long long int aa, long long int bb){
  //  if(aa==0){
    //    return 1;
    //}
    //else if(aa%2==0){
      //  long long int tt=ruizyo(aa/2,bb);
        //return (tt*tt)%MOD;
    //}
    //else{
      //  return (ruizyo(aa-1,bb)*bb)%MOD;
    //}
//}フェルマ－のア


//while(x!=0){
            //sum+=x%10;
           // x/=10;
        //}
        //各桁の和

//pair<int,int> p[100000];
//P r[100000];
//cin >> tmp;
//p[i]=make_pair(tmp,i);
//cout << p[i].second+1 << endl;//ペアの右側つまりiを出力

//s.find(w[i])==string::npos
//findの使い方

//for(int i=0;i<n;i++){
   // b[i]=x%2;
    //x/=2;
  //}二進数

//visited=vector<vector<bool>>(10,vector<bool>(10,false));アを全部falseに


long long int n,cnt=0,ans=0,a[10000000],b,c,cmp=INF,t,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;

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

       cin >> n>>t;
       rep(i,n)cin>>a[i];
       rep(i,n){
           cmp=min(cmp,a[i]);
           cmpp=a[i]-cmp;
         //  cout << cmpp <<" " << cmp << endl; 
           if(cmpp==pos){
               pos=cmpp;
               ans++;
           }
           else if(cmpp>pos){
               pos=cmpp;
               ans=1;
           }
       }
       Cout(ans);
return 0;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	N = N % 10;
	if (N == 3) {
		cout << "bon" << endl;
	}
	else if (N == 0 || N == 1 || N == 6 || N == 8) {
		cout << "pon" << endl;
	}
	else {
		cout << "hon" << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
h, w = gets.split.map(&:to_i)
s = []

h.times do
  s << gets.chomp
end

for i in 0...h
  for j in 0...w
    count = 0
    if s[i][j] == "#" then next end
    for dx in -1..1
      for dy in -1..1
        next_x = dx + i
        next_y = dy + j
        if next_x >= 0 && next_x < h && next_y >= 0 && next_y < w
          count += s[next_x][next_y] == "#" ? 1 : 0
        end
      end
    end
    s[i][j] = count.to_s
  end
end

puts s


Measured memory_bytes: 3836
#include <bits/stdc++.h>
#define sanyes ios_base::sync_with_stdio(0), cout.tie(0); cin.tie(0);
#define llong long long int
#define pb push_back
#define bpc __builtin_popcount
#define f first
#define s second

const llong mxn = 2 * 1e5 + 7;
const llong mod = 1e9 + 7;
const llong inf = 1e18 + 9;

using namespace std;

llong n, a[mxn], pr[mxn], mx = -inf, sum = 0, ans= 0;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }for (int i = 1; i <= n + 1; i ++){
        sum += a[i];
        if(a[i] == 0){
            ans += sum / 2;
            sum = 0;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int
func main() {
	defer stdout.Flush()

	N := readInt()
	M := readInt()
	Q := readInt()

	f := make([][]int, 510)
	for i := range f {
		f[i] = make([]int, 510)
	}
	for i := 0; i < M; i++ {
		l := readInt()
		r := readInt()
		f[l][r]++
	}

	for i := 1; i <= N; i++ {
		for j := 1; j <= N; j++ {
			f[i][j] += f[i][j-1]
		}
	}
	for i := N; i > 0; i-- {
		for j := 1; j <= N; j++ {
			f[i][j] += f[i+1][j]
		}
	}

	for i := 0; i < Q; i++ {
		l := readInt()
		r := readInt()
		println(f[l][r])
	}

}


Measured memory_bytes: 6144
# 隣との距離が大きいところで担当区間を区切るのがお得。
# 各担当区間では行ったり来たりせずに端から端まで動くのがお得。

n, m = map(int, input().strip().split())
xs = sorted(list(map(int, input().strip().split())))
if n >= m:
    print(0)
elif n == 1:
    print(xs[-1] - xs[0])
else:
    intervals = sorted([(xs[i + 1] - xs[i], i) for i in range(m - 1)], reverse=True)

    divides = sorted([ind for _, ind in intervals[:n - 1]])

    total = 0
    for i in range(len(divides) + 1):
        if i == 0:
            interval = xs[divides[i]] - xs[0]
        elif i < len(divides):
            interval = xs[divides[i]] - xs[divides[i - 1] + 1]
        else:
            interval = xs[-1] - xs[divides[i - 1] + 1]

        total += interval

    print(total)


Measured memory_bytes: 19092
INF = 9999


def prim(M):
    n = len(M)
    color = [0] * n
    d = [INF] * n
    d[0] = 0

    while True:
        minv = INF
        u = -1
        for i in range(n):
            # Black:2
            if minv > d[i] and color[i] != 2:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = 2

        for v in range(n):
            if color[v] != 2 and M[u][v] != INF:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
    return sum(d)


if __name__ == '__main__':
    n = int(input())
    A = []
    for i in range(n):
        src = input()
        dst = src.replace('-1', str(INF))
        ai = list(map(int, dst.split()))
        A.append(ai)
    print(prim(A))

Measured memory_bytes: 7860
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	int N;
	int d[100010]={};

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

	cout << d[N/2]-d[N/2-1] << endl;
	return 0;
}



Measured memory_bytes: 640