akhauriyash/Code-Regression huggingface dataset:
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

alias D = Tuple!(long, "sum", int, "i", int, "j", int, "k");

void calc_pq(int K, long[] a, long[] b, long[] c) {
    a.sort!("a > b");
    b.sort!("a > b");
    c.sort!("a > b");
    auto pq = new BinaryHeap!(Array!D);
    bool[Tuple!(int, int, int)] used;
    pq.insert(D(a[0] + b[0] + c[0], 0, 0, 0));
    while (K > 0) {
        auto d = pq.front;
        pq.popFront();
        if (tuple(d.i, d.j, d.k) in used) continue;

        writeln(d.sum);
        used[tuple(d.i, d.j, d.k)] = true;
        K--;

        int i = d.i;
        int j = d.j;
        int k = d.k;
        if (i + 1 < a.length)
            pq.insert(D(a[i + 1] + b[j] + c[k], i + 1, j, k));
        if (j + 1 < b.length)
            pq.insert(D(a[i] + b[j + 1] + c[k], i, j + 1, k));
        if (k + 1 < c.length)
            pq.insert(D(a[i] + b[j] + c[k + 1], i, j, k + 1));
    }
}

void calc(int k, long[] a, long[] b, long[] c) {
    long[] ab;
    foreach (x, y; cartesianProduct(a, b))
        ab ~= x + y;

    ab.sort!"a > b";
    c.sort!"a > b";
    long[] abc;
    foreach (x, y; cartesianProduct(c, ab.take(k)))
        abc ~= x + y;
    abc.sort!"a > b";
    foreach (e; abc.take(k)) writeln(e);
}

void main() {
    int x, y, z, k; scan(x, y, z, k);
    auto a = reads!long;
    auto b = reads!long;
    auto c = reads!long;


    calc(k, a, b, c);
}


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

int main()
{
    long long int n, x, input, cnt = 0, a, b;
    vector<long long int>candys;
    cin >> n >> x;
    for(long long int i = 0; i < n; i++){
        cin >> input;
        candys.push_back(input);
    }

    for(long long int i = 1; i < n; i++){
        long long int c = 0;
        if(i == 1)
            a = candys[0];
        else
            a = b;
        b = candys[i];
        if(a+b > x)
        {
            c = (a+b) - x;
            if(c >= b)
                b = 0;
            else
                b = b - c;
        }
        cnt += c;
    }
    cout << cnt;

    return 0;
}


Measured memory_bytes: 4320
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	map<string, int> cnt;
	for (int i=0; i<n; i++)
		cin >> s[i];

	for (int i=0; i<n; i++)
		cnt[s[i]]++;

	int max_value = 0;
	for ( auto i = cnt.begin(); i != cnt.end(); ++i)
		max_value = max(max_value, i->second);

	for ( auto i = cnt.begin(); i != cnt.end(); ++i) {
		if (i->second == max_value)
			cout << i->first << endl;
	}

	return 0;
}

Measured memory_bytes: 22272
N = gets.to_i
dp = Array.new(N + 1){[0,0,0]}
(1 .. N).each do |n|
  a,b,c = gets.split.map(&:to_i)
  dp[n][0] = [dp[n - 1][1] + a, dp[n - 1][2] + a].max
  dp[n][1] = [dp[n - 1][2] + b, dp[n - 1][0] + b].max
  dp[n][2] = [dp[n - 1][0] + c, dp[n - 1][1] + c].max
end
puts dp[N].max


Measured memory_bytes: 22556
# coding:utf-8
while 1:
    nn,s,mm=map(str,input().split())
    n=int(nn)
    m=int(mm)
    if s=='+':
        print(n+m)
    elif s=='-':
        print(n-m)
    elif s=='*':
        print(n*m)
    elif s=="/":
        print(n//m)
    else:
        break


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

int main(){
	int N;
	string S;
	cin >> N >> S;
	int ans = 0;
	for(int i = 0; i < N; i++)
	{
		int cnt = 0;
		for(char c = 'a'; c <= 'z'; c++)
		{
			bool x = false, y = false;
			for(int j = 0; j < i; j++)
			{
				if(S[j] == c) x = true;
			}
			for(int j = i; j < N; j++)
			{
				if(S[j] == c) y = true;
			}

			if(x && y) cnt++;
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

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

int calculateCost(vector<int> &height){
    int n = height.size();
    vector<int> dp(n,0);
    dp[1] = abs(height[1]-height[0]);
    for(int i=2;i<n;i++){
        dp[i] = min( (dp[i-1]+abs(height[i]-height[i-1])), (dp[i-2]+abs(height[i]-height[i-2])) );
    }
    return dp[n-1];
}
int main(){
    int n;
    cin>>n;
    vector<int> height(n);
    for(int i=0;i<n;i++){
        cin>>height[i];
    }
    cout<<calculateCost(height)<<endl;
}


Measured memory_bytes: 1024
// atcoder/abc179/E/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});

const int M = 1e5 + 5;
lli vis[M];
lli n, x, m;

lli B, length;
lli rec(lli curr, int depth)
{
  if (depth == n) return -1;
  if (0 <= vis[curr]) {
    B = vis[curr];
    length = depth - vis[curr];
    return curr;
  }

  vis[curr] = depth;
  return rec((curr * curr) % m, depth + 1);
}

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  while (cin >> n >> x >> m) {
    // cout << endl;
    fill(vis, vis + M, -1);
    B = length = -1;
    lli y = rec(x, 0);

    if (B == -1) {
      lli z = 0;
      for (int i = 0; i < M; ++i) {
        if (vis[i] == -1) continue;
        z += i;
      }
      cout << z << endl;
      continue;
    }

    lli w = (n - B) / length;
    lli r = (n - B) % length;

    lli z = 0;
    lli p = 0;
    lli q = 0;
    for (int i = 0; i < M; ++i) {
      if (vis[i] == -1) continue;

      if (vis[i] < B) z += i;
      else p += i;

      if (B <= vis[i] && vis[i] < B + r) q += i;
    }

    // cout << B << ' ' << length << endl;
    // cout << z << ' ' << p << ' ' << q << endl;
    cout << z + (p * w) + q << endl;
    // break;
  }

  return 0;
}


Measured memory_bytes: 4416
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << a*b/2;
    return 0;
}


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

using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	if (t.size() != s.size() + 1) {
		cout << "No";
		return 0;
	}
	for (int i = 0; i < s.size(); i++)
		if (s[i] != t[i]) {
			cout << "No";
			return 0;
		}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <iomanip>
#include <fstream>
#include <array>
using namespace std;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef pair<int,int> PII;
typedef long long int64;
typedef vector<int> VI;

int main() {
	//freopen("test.in","r",stdin);
	int64 x,k,d;
	cin >> x >> k >> d;
	x=abs(x);
	int64 m=x/d;
	int64 r=x%d;
	if (m>k) {
		cout << x-k*d << endl;
	} else {
		if ((k-m)%2==0) cout << r << endl;
		else cout << d-r << endl;
	}
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    ll n; cin >> n;
    int x = 1;
    while (n > 0) {
        n -= pow(26,x);
        x++;
    }
    x--;
    n += pow(26,x);
    n--;
    vector<char> ans(x,'a');
    int id = 0;
    while (n > 0) {
        ans[id++] += n%26;
        n /= 26;
    }
    reverse(all(ans));
    rep(i,ans.size()) cout << ans[i];
    cout << endl;
}

Measured memory_bytes: 4048
#include<stdio.h>
#include<stdlib.h>
int n,q;
char *s;
int *l,*r;
int count=0;
int *dr;
int main(){
    int i;
    scanf("%d%d",&n,&q);
    s=(char*)malloc(sizeof(char)*n);
    dr=(int*)malloc(sizeof(int)*n);
    l=(int*)malloc(sizeof(int)*q);
    r=(int*)malloc(sizeof(int)*q);
    scanf("%s",s);
    for(i=0;i<n;i++){
        if(s[i-1]=='A'&&s[i]=='C')count++;
        dr[i]=count;
    }
    for(i=0;i<q;i++)scanf("%d%d",&l[i],&r[i]);
    for(i=0;i<q;i++){
        // printf("%d %d\n",r[i]-1,l[i]-1);
        printf("%d\n",dr[r[i]-1]-dr[l[i]-1]);
    }
    free(s); free(l); free(r); free(dr);
    return 0;
}

Measured memory_bytes: 2048
#include "bits/stdc++.h"
#define readInt(x) scanf_s("%d", &x)
#define readStr(x) scanf("%s", x)
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmax(x, y) (x > (y) ? x : x = (y))
#define chmin(x, y) (x < (y) ? x : x = (y))
#define write(x) cout << (x) << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = INT32_MAX / 2;
const int MAX = 1e5 + 10;

int ABC[3];

int main()
{
    cin >> ABC[0] >> ABC[1] >> ABC[2];
    sort(begin(ABC), end(ABC));
    int cnt = 0;
    while (ABC[2] - ABC[0] > 1) {
        ABC[0] += 2;
        cnt++;
    }
    while (ABC[2] - ABC[1] > 1) {
        ABC[1] += 2;
        cnt++;
    }
    if (ABC[0] == ABC[1]) {
        if (ABC[1] != ABC[2]) cnt++;
    }
    else cnt += 2;
    write(cnt);
}

Measured memory_bytes: 256
import sys
from sys import stdin


def input(): return stdin.readline().rstrip()


def mips():
    return map(int, input().split())


def ii():
    return int(input())
A, B, C, X, Y = mips()
money = 0
while X > 0 and Y > 0:
    if (A+B) <= 2*C:
        money += (A+B)
        X -= 1
        Y -= 1
    else:
        money += 2*C
        X -= 1
        Y -= 1
while X > 0:
    if A <= 2*C:
        money += A
        X -= 1
    else:
        money += 2*C
        X -= 1
        Y -= 1
while Y > 0:
    if B <= 2*C:
        money += B
        Y -= 1
    else:
        money += 2*C
        X -= 1
        Y -= 1
print(money)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
typedef pair<pair<int, int>, int> PP;
typedef bitset<60> Bitset;
const ll INFL = 1LL << 60;
const int INF = INT_MAX;
const int MAX = 300000;
const int MOD = 1000000007;
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;cin>>n>>m>>k;
    vector<ll>suma(n+1,0),sumb(m+1,0);
    for(int i = 0; i < n; i++) {
        int a;cin>>a;suma[i+1] += suma[i]+a;
    }
    for(int i = 0; i < m; i++) {
        int b;cin>>b;sumb[i+1] += sumb[i]+b;
    }
    int ans = 0;
    for(int i = 0; i <= n; i++) {
        if(suma[i]>k) break;
        int j = upper_bound(sumb.begin(),sumb.end(),k-suma[i])-sumb.begin()-1;
        ans = max(ans,i+j);
    }
    cout<<ans<<endl;
}


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

namespace Aizu
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var data = Console.ReadLine().Split(' ').Select(d => int.Parse(d)).ToList<int>();

            int changeCount = 0;
            int num = 1;
            for(int i = n - 1;  -1 < i; i--)
            {
                for(int j = 0; j < i; j++)
                {
                    if (data[j + 1] < data[j])
                    {
                        var temp = data[j];
                        data[j] = data[j + 1];
                        data[j + 1] = temp;
                        changeCount++;
                    }
                }
                num++;
            }

            Console.WriteLine(string.Join(" ", (string[])data.Select(d => d.ToString()).ToArray()));
            Console.WriteLine(changeCount);
        }
    }

}



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

int main(){
	int N;
	cin >> N;
	int nums[N];
	for(int i = 0; i < N; i++){
		cin >> nums[i];
	}
	sort(nums, nums + N);
	int num = nums[0];
	int continuity = 1;
	int ans = 0;
	for(int i = 1; i < N; i++){
		if(num == nums[i]){
			continuity++;
		}else{
			if(continuity % 2 == 1){
				ans++;
			}
			continuity = 1;
			num = nums[i];
		}
	}
	if(continuity % 2 == 1){
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
ll INF = 214748364700000000;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

int main(){
   int N,M;cin >> N >> M;
   vector<vector<int>> switches(M);
   vector<int> P(N);
   rep(i,M){
       int k;cin >> k;
       rep(j,k){
           int s;cin >> s;
           switches[i].push_back(s-1);
       }
   }
   rep(i,M) cin >> P[i];
   int ans = 0;
   rep(i,(1<<N)){
       bitset<10> S(i);
       bool frag = 1;
       rep(j,M){
           int cnt = 0;
           rep(k,switches[j].size()){
               if(S.test(switches[j][k])) cnt++;
           }
           if(cnt % 2 != P[j]) frag = 0;
       }
       if(frag) ans++;
   }
   cout << ans << endl;
}


Measured memory_bytes: 256
/*
    simple calculator ITP1_4_C
*/

#include <stdio.h>

int main(void)
{
    char op;
    int a, b;

    int continue_ = 1;
    while (continue_ == 1) {
        scanf("%d %c %d", &a, &op, &b);
        switch (op) {
            case '+':
                printf("%d\n", a + b); break;
            case '-':
                printf("%d\n", a - b); break;
            case '*':
                printf("%d\n", a * b); break;
            case '/':
                printf("%d\n", a / b); break;
            case '?':
                continue_ = 0;
        }
    }
    return (0);
}



Measured memory_bytes: 2056
//{{{
#include <bits/stdc++.h>
using namespace std;
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop,~))(__VA_ARGS__)
#define loop(n) rep2(_loop_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define repN(a) repX a
#define repX(a0,a1,a2,x,...) x
#define foreach(x,a) for(auto &x:a)
typedef long long ll;
const ll MOD = 1e9+7;
//}}}

int x[200000];
int y[200000];
int main(){
  int N;
  cin >> N;
  rep(i, N) cin >> x[i];
  rep(i, N) y[i] = x[i];
  sort(x, x + N);

  rep(i, N){
    if(y[i] < x[N / 2]){
      cout << x[N / 2] << endl;
    } else {
      cout << x[N / 2 - 1] << endl;
    }
  }
  return 0;
}


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

int main() {
  string s;
  int i, a = 0;
  cin >> s;
  for(i = 0; i < s.size(); i++) {
    if(s.at(i) == 'o') a++;
  }
  cout << 700 + a * 100 << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
// #define USE_LLONG_AS_INT
#ifdef USE_LLONG_AS_INT
#define int long long
#define inf (1ll<<60)
#else
#define inf (1<<30)
#endif
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=(n)-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

struct node{
    int n;
    node *l,*r;
};

int i;

node *get_tree(string &s){
    node *ret = new node();
    ret->n=-1;
    ret->l=NULL;
    ret->r=NULL;
    int l=-1;
    while(i<s.length()){
        if(s[i]=='('){
            i++;
            l++;
            if(s[i]==')'){
                i++;
                continue;
            }
            (l?ret->r:ret->l)=get_tree(s);
        }
        else if(s[i]=='['){
            i++;
            ret->n=0;
            while(s[i]!=']'){
                ret->n*=10;
                ret->n+=s[i]-'0';
                i++;
            }
            i++;
        }
        else if(s[i]==')'){
            i++;
            return ret;
        }
    }
    return ret;
}

node *make_tree(node *t1,node *t2){
    node *ret=new node();
    ret->n=t1->n+t2->n;
    if(t1->l!=NULL&&t2->l!=NULL)ret->l=make_tree(t1->l,t2->l);
    if(t1->r!=NULL&&t2->r!=NULL)ret->r=make_tree(t1->r,t2->r);
    return ret;
}

void print_tree(node *t){
    cout<<'(';
    if(t->l!=NULL)print_tree(t->l);
    cout<<')';
    cout<<'['<<t->n<<']';
    cout<<'(';
    if(t->r!=NULL)print_tree(t->r);
    cout<<')';
}
    
void run(){
    string s1,s2;
    cin>>s1>>s2;
    node *t1=get_tree(s1);
    i=0;
    node *t2=get_tree(s2);
    node *t3=make_tree(t1,t2);
    print_tree(t3);
    cout<<endl;
}


Measured memory_bytes: 3260
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>v1, v2;
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        v1.push_back(x + y);
        v2.push_back(x - y);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    cout << max(v1[n - 1] - v1[0], v2[n - 1] - v2[0]);
    return 0;
}

Measured memory_bytes: 5040
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main(){
	int d,e;
	while(cin>>d>>e){
		if(d==0&&e==0) break;
		double sa=d+e;
		for(int i=0;i<=d/2;i++){
			double a=pow(pow(d-i,2)+pow(i,2),0.5)-e;
			sa=min(sa,max(a,-a));
		}
		cout<<sa<<endl;
	}
    return 0;
}

Measured memory_bytes: 1304
#include<iostream>

using namespace std;
const int MAX_N=1e5+5;

long long x[MAX_N];
long long v[MAX_N];
long long sum[MAX_N];
long long v_max[MAX_N];
long long v_max_inv[MAX_N];
long long max(long long x,long long y){return x>y?x:y;}
long long min(long long x,long long y){return x<y?x:y;}
int main(){
  int n;
  long long c;
  cin>>n>>c;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>v[i];
  }
  x[n+1]=c;
  sum[0]=0;
  for(int i=0;i<n;i++)sum[i+1]=sum[i]+v[i+1];
  v_max[0]=0;
  for(int i=1;i<=n;i++)v_max[i]=max(v_max[i-1],sum[i]-x[i]);
  v_max_inv[n+1]=0;
  for(int i=n;i>0;i--)v_max_inv[i]=max(v_max_inv[i+1],sum[n]-sum[i-1]-(c-x[i]));
  long long ans=0;
  for(int i=1;i<=n+1;i++){
    ans=max(sum[n]-sum[i-1]+v_max[i-1]-2*(c-x[i]),ans);
  }
  for(int i=0;i<=n;i++){
    ans=max(sum[i]+v_max_inv[i+1]-2*x[i],ans);
  }
  cout<<ans<<endl;
}


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

void call(int n){
  int i = 1;
  do {
    if ( i % 3 == 0 ){
      cout << " " << i;
      continue;
    }
    int x = i;
    do {
      if ( x % 10 == 3 ){
        cout << " " << i;
        break;
      }
      x /= 10;
    } while(x > 0);
  } while(++i <= n);

  cout << endl;
}

int main() {
  int n;
  cin >> n;
  call(n);
}

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

table=[[0]*9 for i in range(9)]

for i in range(1,N+1):
  if int(str(i)[len(str(i))-1])==0:
    continue
  table[int(str(i)[0])-1][int(str(i)[len(str(i))-1])-1]+=1

ans=0
for i in range(9):
  for j in range(i,9):
    if i==j:
      ans+=table[i][j]*table[j][i]
    else:
      ans+=table[i][j]*table[j][i]*2
print(ans)

Measured memory_bytes: 9184
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <ctype.h>
using namespace std;

typedef long long ll;

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

int main() {
  int n;
  string str, s;
  cin >> n >> str;

  int maxval = -1;
  int count = 0;
  vector<char> v;
  for (int i = 0; i != s.size() - 1; ++i) {
    s = str;
    v.clear();
    count = 0;
    for (int j = 0; j < i + 1; ++j) {
      auto result = find(v.begin(), v.end(), s[j]);
      if (result == v.end()) {
        v.push_back(s[j]);
        for (int k = i + 1; k != s.size(); ++k) {
          if (s[j] == s[k]) {
            ++count;
            break;
          }
        }
      }
    }
    maxval = max(maxval, count);
  }

  cout << maxval << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

using namespace std;
int main()
{
    /*
    cin>>x;
    cout<<x<<endl;
    */
    int n,m,i,j,max,sum=0,tmp;
    cin>>n>>m;
    vector<int> k(m,0);
    for(i=0;i<n;i++){
        cin>>tmp;
        for(j=0;j<tmp;j++){
            cin>>max;
            k[max-1]++;
        }
    }
    for(i=0;i<m;i++)
        if(k[i]==n)
            sum++;
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;cin>>s;
if(s=="AKIHABARA")cout<<"YES"<<endl;
else if(s=="AKIHABAR")cout<<"YES"<<endl;
else if(s=="AKIHABRA")cout<<"YES"<<endl;
else if(s=="KIHABR")cout<<"YES"<<endl;
else if(s=="AKIHBARA")cout<<"YES"<<endl;
else if(s=="AKIHBAR")cout<<"YES"<<endl;
else if(s=="AKIHBRA")cout<<"YES"<<endl;
else if(s=="AKIHBR")cout<<"YES"<<endl;
else if(s=="KIHABARA")cout<<"YES"<<endl;
else if(s=="KIHABAR")cout<<"YES"<<endl;
else if(s=="KIHABRA")cout<<"YES"<<endl;
else if(s=="KIHABR")cout<<"YES"<<endl;
else if(s=="KIHBARA")cout<<"YES"<<endl;
else if(s=="KIHBAR")cout<<"YES"<<endl;
else if(s=="KIHBRA")cout<<"YES"<<endl;
else if(s=="KIHBR")cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, M; scanf("%d %d", &N, &M);
  int E = (1 << M);
  int ans = E * (1900 * M + (N - M) * 100);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 55;

int a, b, c, i, bg;
int full, part;

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

    cin >> a >> b >> c;
    bg = max(max(a, b), c);

    for (; ; bg++) {
        full = part = 0;

        full += (bg - a) / 2;
        part += (bg - a) % 2;

        full += (bg - b) / 2;
        part += (bg - b) % 2;

        full += (bg - c) / 2;
        part += (bg - c) % 2;

        if (part % 2) continue;
        cout << full + (part / 2);
        return 0;
    }

    return 0;
}


Measured memory_bytes: 256
N=input()
s=list(raw_input())

def judge(a,b):
	t=[]
	t.append(a)
	t.append(b)

	for ind, i in enumerate(s):
		if ind==0:
			continue

		if i=="o" and t[ind]=="S":
			t.append(t[ind-1])
		elif i=="o" and t[ind]=="W":
			if t[ind-1]=="S":
				t.append("W")
			elif t[ind-1]=="W":
				t.append("S")
		elif i=="x" and t[ind]=="S":
			if t[ind-1]=="S":
				t.append("W")
			elif t[ind-1]=="W":
				t.append("S")
		elif i=="x" and t[ind]=="W":
			t.append(t[ind-1])

	if t[0]==t[-1]:
		if s[0]=="o" and t[0]=="S":
			if t[1]==t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="o" and t[0]=="W":
			if t[1]!=t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="x" and t[0]=="S":
			if t[1]!=t[-2]:
				print "".join(t[:-1])
				quit()
		elif s[0]=="w" and t[0]=="W":
			if t[1]==t[-2]:
				print "".join(t[:-1])
				quit()			
	else:
		return False

judge("S","S")
judge("S","W")
judge("W","S")
judge("W","W")
print -1




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

int main() {
	long long n, k, ans = 0; cin >> n >> k;
	for (long long b = k + 1, m; b <= n; b++) {
		m = n / b;
		ans += (b - k) * m + max(n - (b * m + k - 1), 0LL) - (k == 0 ? 1 : 0);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)


def main():
    def read_tree(n):
        parents = [0 for _ in range(n + 1)]
        for _ in range(n - 1):
            a, b = [int(x) for x in input().split()]
            parents[b] = a
        return parents

    n, q = [int(x) for x in input().split()]

    parents = read_tree(n)
    cnt = [0] * (n + 1)

    for _ in range(q):
        p, x = [int(x) for x in input().split()]
        cnt[p] += x
    
    for i in range(1, n + 1):
        cnt[i] += cnt[parents[i]]

    for i in range(1, n + 1):
        print(cnt[i], end=" ")


main()


Measured memory_bytes: 22700
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    ab = []
    odd = False
    if N % 2 == 1:
        odd = True
    for i in range(N):
        ab.append(LI())

    # beginning sort
    beg_ab = sorted(ab, key=lambda x:x[0])
    en_ab = sorted(ab, key=lambda x:x[1])[::-1]
    # even
    if odd:
        l = beg_ab[N//2][0]
        r = en_ab[N//2][1]
        cnt = r - l + 1
    else:
        l1 = beg_ab[(N-1)//2][0]
        l2 = beg_ab[(N-1)//2 + 1][0]

        r1 = en_ab[(N-1)//2][1]
        r2 = en_ab[(N-1)//2 + 1][1]
        cnt = 2 * ((r1+r2)/2 - (l1+l2)/2) + 1
    print(int(cnt))


main()



Measured memory_bytes: 50288
#include<bits/stdc++.h>
using namespace std;
#define forN(n, N) for(int n=0; n<N; n++)
#define res_out(ans) cout << ans << "\n";
#define ll long long

int N, A, B, C;
int l[int(1e4)];

int dfs(int n, int a,int b,int c){
    int ret[4] = {};
    if(n == N){
        if(a == 0 || b == 0 || c == 0)return 1e6;
        return abs(A - a)  + abs(B - b) + abs(C - c) - 30;
    }
    ret[0] = dfs(n + 1, a, b, c);
    ret[1] = dfs(n + 1, a + l[n], b, c) + 10;
    ret[2] = dfs(n + 1, a, b + l[n], c) + 10;
    ret[3] = dfs(n + 1, a, b, c + l[n]) + 10;
    return *min_element(ret, ret + 4);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> A >> B >> C;
    forN(n, N)cin >> l[n];
    res_out(dfs(0, 0, 0, 0));
    return 0;
}

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

using namespace std;

int main()
{
	int n, id[4001], p, s;
	bool a[4001], f;
	long long int t, u, b[4001];
	
	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		fill(a, a+4001, false);
		fill(b, b+4001, 0);
		p = 0;
		
		for(int i = 0; i < n; i++){
			cin >> s >> t >> u;
			b[s] += t * u;
			if(a[s]){
				continue;
			}
			id[p++] = s;
			a[s] = true;
		}
		f = true;
		for(int i = 0; i < p; i++){
			if(b[id[i]] >= 1000000){
				cout << id[i] << endl;
				f = false;
			}
		}
		
		if(f){
			cout << "NA" << endl;
		}
	}
	
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i=0;i<N;i++){
    cin >> d.at(i);
  }
  sort(d.begin(),d.end());
  reverse(d.begin(),d.end());

  int count=0;
  int tmp=0;
  for(int i=0;i<N;i++){
    if(tmp!=d.at(i)){
      count++;
      tmp=d.at(i);
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

typedef struct TimeCard {
	int h;
	int m;
	int s;
}TimeCard;

int main(void)
{
	TimeCard date[3];

	int h1, h2, m1, m2, s1, s2,total=0;
	int i;

	for (i = 0; i < 3; i++) {
		scanf("%d %d %d %d %d %d", &h1, &m1, &s1, &h2, &m2, &s2);
		total = (h2 * 60 * 60 + m2 * 60 + s2) - (h1 * 60 * 60 + m1 * 60 + s1);
		date[i].h = total / 60 / 60;
		total -= date[i].h * 60 * 60;
		date[i].m = total / 60;
		total -= date[i].m * 60;
		date[i].s = total;
	}
	for (i = 0; i < 3; i++)
		printf("%d %d %d\n",date[i].h,date[i].m,date[i].s);
	
	return 0;
}

Measured memory_bytes: 600
#include<iostream>
      
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
  
int n, M[MAX][MAX];
  
void dijkstra() {
   int min;
   int d[MAX], color[MAX];
  
   for ( int i = 0; i < n; i++ ) {
      d[i] = INFTY; 
      color[i] = WHITE;
   }
  
   d[0] = 0;
   color[0] = GRAY;
     
   while ( 1 ) {
      min = INFTY; 
      int a = -1;
      for ( int i = 0; i < n; i++ ) {
         if ( min > d[i] && color[i] != BLACK ) {
             a = i;
             min = d[i];
         }
      }
  
      if ( a == -1 ) break;
      color[a] = BLACK;
        
      for ( int v = 0; v < n; v++ ) {
         if ( color[v] != BLACK && M[a][v] != INFTY ) {
            if ( d[v] > d[a] + M[a][v] ) {
               d[v] = d[a] + M[a][v];
               color[v] = GRAY;
            }
         }
      }
   }
  
   for ( int i = 0; i < n; i++ ) {
      cout << i << " " << ( d[i] == INFTY ? -1 : d[i] ) << endl;
   }
}
  
int main() {

   cin >> n;
   for ( int i = 0; i < n; i++ ) {
      for ( int j = 0; j < n; j++ ) {
         M[i][j] = INFTY;
      }
   }
  
   int k, c, a, v;
    
   for ( int i = 0; i < n; i++ ) {
      cin >> a >> k;  
  
      for ( int j = 0; j < k; j++ ) {
         cin >> v >> c;
         M[a][v] = c;
      }
   }
  
   dijkstra();
  
   return 0;
}

Measured memory_bytes: 3100
N=int(input())
List=list(map(int,input().split()))
List.sort()
A = 0

for i in range(len(List)-1):
  a = List[i]
  b = List[i+1]
  
  if a == b:
    A = 1
    
if A == 1:
  print("NO")
else:
  print("YES")

Measured memory_bytes: 26808
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int main()
{
  vector<int> primes;

  primes.push_back(2);
  for (int i=3;i<=1000;i+=2) {
    int flag=0;
    for (int j=2;j<i;j++) {
      if (i%j==0) {
	flag=1;
	break;
      }
    }
    if (flag==0) {
      primes.push_back(i);
    }
  }

  int n;
  long long int ans=1;

  scanf("%d",&n);

  for (int i=0;i<primes.size();i++) {
    int p=primes[i];
    int count=0;

    while (p<=n) {
      count+=n/p;
      p=p*primes[i];
    }
    ans=(ans*(count+1))%1000000007;
  }

  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    S = []
    for _ in range(N):
        s = int(input())
        S.append(s)

    sm = sum(S)
    if sm % 10 != 0:
        print(sm)
        exit()

    S.sort()
    for si in S:
        if si % 10 != 0:
            print(sm - si)
            exit()
    print(0)

if __name__ == "__main__":
    main()

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

int main()
{
    int h, w;
    bool flag = false;
    cin >> h >> w;
    vector<string> a(h);
    for(int i=0; i<h; i++) cin >> a[i];
PR:
    for(int i=0; i<w+2; i++) printf("#");
    printf("\n");
    if(flag) return 0;
    flag = true;
    for(int i=0; i<h; i++) {
        printf("#");
        printf("%s", a[i].c_str());
        printf("#\n");
    }
    goto PR;
}

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

#define EPS 0.0000000001
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point{
	public:
		double x, y;

		Point(double x = 0, double y = 0): x(x), y(y) {}

		Point operator + (Point p){ return Point(x + p.x, y + p.y);}
		Point operator - (Point p){ return Point(x - p.x, y - p.y);}
		Point operator * (double a){ return Point(a * x, a * y);}
		Point operator / (double a){ return Point(x / a, y / a);}

		double abs(){ return sqrt(norm());}
		double norm(){ return x * x + y * y;}

		bool operator < (const Point &p) const{
			return x != p.x ? x < p.x : y < p.y;
		}

		bool operator == (const Point &p) const{
			return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
		}
};

struct Segment {
	Point p1, p2;
};
typedef Segment Line;

class Circle{
	public:
		Point c;
		double r;
		Circle(Point c = Point(), double r = 0.0): c(c), r(r) {}
};

typedef Point Vector;
typedef vector<Point> Polygon;

double dot(Vector a, Vector b){
	return a.x * b.x + a.y * b.y;
}
double cross(Vector a, Vector b){
	return a.x * b.y - a.y * b.x;
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2){
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if(cross(a, b) > EPS) return COUNTER_CLOCKWISE;
	if(cross(a, b) < -EPS) return CLOCKWISE;
	if(dot(a, b) < -EPS) return ONLINE_BACK;
	if(a.norm() < b.norm()) return ONLINE_FRONT;

	return ON_SEGMENT;
}

int main(void){
	Point p0, p1, p2;
	int q;
	cin >> p0.x >> p0.y >> p1.x >> p1.y;
	cin >> q;
	for(int i=1;i<=q;i++){
		cin >> p2.x >> p2.y;
		switch(ccw(p0, p1, p2)){
			case 1:
				cout << "COUNTER_CLOCKWISE" << endl;
				break;
			case -1:
				cout << "CLOCKWISE" << endl;
				break;
			case 2:
				cout << "ONLINE_BACK" << endl;
				break;
			case -2:
				cout << "ONLINE_FRONT" << endl;
				break;
			case 0:
				cout << "ON_SEGMENT" << endl;
				break;
		}
	}
	return 0;
}

Measured memory_bytes: 3220
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  var a = o.l();
  return a[0]+a[1]+a[2] >= 22 ? "bust" : "win";
}

Measured memory_bytes: 22080
// 2020-08-26 16:05:35
// clang-format off
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

// clang-format on
void answer() {
  int n;
  cin >> n;
  vector<int> p(55555 + 55, 1), ans;
  p[0] = p[1] = 0;
  REP(i, 2, 55555 + 5) if (p[i]) {
    for (int j = 2 * i; j < 55555 + 5; j += i) p[j] = 0;
    if (i % 5 == 1) {
      ans.push_back(i);
      if (ans.size() == n) break;
    }
  }
  rep(i, ans.size()) {
    if (i) cout << ' ';
    cout << ans[i];
  }
  cout << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)((x).size())
#define debug(x) cout << #x << ":" << x << ' ';
#define debugg(x) cout << #x << ":" << x << ' ' << "\n";
#define endl "\n"
#define L(X) ((X)<<1)
#define R(X) (((X)<<1)|1)
#define M(X,Y) (((X)+(Y))>>1)
#define FIN(x) freopen(x, "r", stdin);
#define FOUT(x) freopen(x, "w", stdout);

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<ll, ll>;

const int MAXN = 1010;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long int LLINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const double PI = acos(-1);

template<typename T>   T max_self(T& a, T b) { if (a < b) a = b; return a; }
template<typename T>   T min_self(T& a, T b) { if (a > b) a = b; return a; }
template<typename T>   T add(T x, T y) { return ((x % MOD)  + (y % MOD)) % MOD;}
template<typename T>   T mul(T x, T y) { return ((x % MOD) * (long long)(y % MOD)) % MOD;}
template<typename T>   T sub(T x, T y) { return add(x, -y + MOD);}
template<typename T>   T gcd(T a, T b) { return b ? gcd(b, a % b) : a;}
template<typename T>   T lcm(T a, T b) { return a / gcd(a, b) * b;}
template<typename T>   vector<T> read(vector<T>& v, int n) {v.resize(n); for (auto &x : v)cin >> x;}
template<typename T>   void trav(vector<T> &v) {for (int i = 0 ; i < (int)v.size() ; ++i) {cout << v[i]; if (i != (int)v.size() - 1) cout << ' ';}}
int lg2(long long x)   {   return 64 - __builtin_clzll(x) - 1;	}
int lg2(int x)   {   return 32 - __builtin_clzll(x) - 1;	}

ll n, m, dp[MAXN][MAXN];
char g[MAXN][MAXN];

ll solve(ll i, ll j) {
	if (i < 1 || j < 1) return 0;
	if (g[i][j] == '#') return 0;
	if(dp[i][j] != -1) return dp[i][j];
	if (i == 1 && j == 1) return dp[i][j] = 1;
	return dp[i][j] = add(solve(i - 1, j), solve(i, j - 1));
}

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

	memset(dp, -1, sizeof dp);

	cin >> n >> m;

	for (int i = 1 ; i <= n ; ++i) {
		for (int j = 1 ; j <= m ; ++j) {
			cin >> g[i][j];
		}
	}

	cout << solve(n, m) << endl;



	return 0;
}


Measured memory_bytes: 9216
from itertools import product

n = int(input())
a = []
for _ in range(n):
  a_i = int(input())
  t = []
  for _ in range(a_i):
    t.append(tuple(map(int,input().split())))
  a.append(t)

ans = 0
for case in product(range(2),repeat=n):
  frag = False
  for i in range(n):
    if case[i]==1:
      for x,y in a[i]:
        if case[x-1]!=y:
          frag = True
          break
    if frag:
      break
  if not frag:
    ans = max(ans,sum(case))
print(ans)

Measured memory_bytes: 44528
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

inline int read () {
    int ret = 0, t = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') t = -1, c = getchar();
    while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret * t;
}

#include <deque>
deque <char> d;
char s[100100];
int main () {
    cin >> s;
    int i, j = strlen(s);
    for (i = 0; i < j; i++) d.push_back(s[i]);
    int Q = read(), rev = 0;
    while (Q--) {
        int T = read();
        if (T == 1) rev = 1 - rev;
        else {
            int F = read();
            char c[2]; cin >> c;
            if ((F == 1 && !rev) || (F == 2 && rev)) d.push_front(c[0]);
            else d.push_back(c[0]);
        }
    }
    if (!rev) while (!d.empty()) putchar(d.front()), d.pop_front();
    else while (!d.empty()) putchar(d.back()), d.pop_back();
    return 0;
}

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

#define MAX_N 40

int N;
long long W;
long long v[MAX_N];
long long w[MAX_N];

typedef pair< long long, long long > P;
vector< P > v1;
vector< P > v2;

int main()
{
	cin >> N >> W;
	for( int i = 0; i < N; i++ ) {
		cin >> v[i] >> w[i];
	}

	P p;
	p.first = 0;
	p.second = 0;
	v1.push_back( p );
	v2.push_back( p );

	int n2 = N / 2;
	int i;
	for( i = 0; i < n2; i++ ) {
		int sz = v1.size();
		for( int j = 0; j < sz; j++ ) {
			p = v1[j];
			p.first += w[i];
			p.second += v[i];
			v1.push_back( p );
		}
	}
	for( ; i < N; i++ ) {
		int sz = v2.size();
		for( int j = 0; j < sz; j++ ) {
			p = v2[j];
			p.first += w[i];
			p.second += v[i];
			v2.push_back( p );
		}
	}
	sort( v1.begin(), v1.end() );
	sort( v2.begin(), v2.end() );

	long long ans = 0;
	long long v2max = 0;
	int v2i = 0;
	int sz = v2.size();
	for( int v1i = v1.size() - 1; v1i >= 0; v1i-- ) {
		if( v1[v1i].first > W ) {
			continue;
		}
		while( v1[v1i].first + v2[v2i].first <= W && v2i < sz ) {
			v2max = max( v2max, v2[v2i].second );
			v2i++;
		}
		ans = max( ans, v1[v1i].second + v2max );
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 43756
from collections import defaultdict

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

d = defaultdict(int)
b = dict()

for p, y in sorted(years, key=lambda x: x[1]):
    d[p] += 1
    b[y] = '{:06d}{:06d}'.format(p, d[p])

for p, y in years:
    print(b[y])


Measured memory_bytes: 98264
#include<iostream>
#include<vector>
using namespace std;
const int N=12,M=1003;
int n,m,s;
char G[N][M];
void solve()
{
	cin>>n>>m>>s;
	int i,j,k,o;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>G[i][j];
		}
	}
	int ans=0x3f3f3f3f;
	for(i=0;i<1<<n-1;i++)
	{
		vector<int>pos;//存水平切割的位置 
		pos.push_back(0);
		for(j=1;j<=n;j++)
		{
			if(i&1<<j-1)
			{
				pos.push_back(j);
			}
		}
		pos.push_back(n);
		//此水平切割状态当前切割次数
		int now=pos.size()-2;
		//存水平切割的每一块当前'1'的个数 
		vector<int>cntr(pos.size()-1,0);
		//从左往右贪心 
		for(j=1;j<=m;j++)
		{
			bool ok=1;
			//存第j列水平切割后每一块的个数 
			vector<int>cntc(pos.size()-1,0);
			for(k=0;k<cntr.size();k++)//枚举水平切割的每一块 
			{
				for(o=pos[k]+1;o<=pos[k+1];o++)
				{
					cntc[k]+=G[o][j]^48;
				}
				//切割之后还行不通 
				if(cntc[k]>s) goto next_condition;
				//需要切割 
				if(cntr[k]+cntc[k]>s) ok=0;
			}
			if(ok) 
			{
				for(k=0;k<cntr.size();k++)
				{
					cntr[k]+=cntc[k];//不竖直切割 
				}
			}
			else
			{
				now++;
				cntr=cntc;//竖直切割 
			}
		}
		ans=min(ans,now);
		next_condition:; 
	}
	cout<<ans<<endl;
}
int main()
{
	solve();
	return 0;
}


Measured memory_bytes: 256
import Data.Char 

main = do
  s <- getLine
  putStrLn $ if (startWithA s && check (tail s)) then "AC" else "WA"
 
 
startWithA :: String -> Bool
startWithA = (== 'A') . head
 
check :: String -> Bool
check s = inCheck False 1 (length s) s
  where
    inCheck :: Bool -> Int -> Int -> String -> Bool
    inCheck True _ _ [] = True
    inCheck False _ _ [] = False
    inCheck b cur len (x:xs) = 
      case x of
        'C' -> if cur >= 2 && cur <= len-1 && not b then inCheck True (cur+1) len xs else False
        c -> if isLower c then inCheck b (cur+1) len xs else False

Measured memory_bytes: 380
#include "bits/stdc++.h"

#define rep(i, a) for (ll i = 0; i < (a); ++i)
#define FORV(a, A) for (auto &a : A)

using namespace std;

using ll = long long;

void Main() {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  int num = 1;
  rep(i, n - 1) if (s[i + 1] != s[i])++ num;
  rep(i, k) {
    num = max(1, num-2);
  }
  cout << n - num << endl;
}

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

Measured memory_bytes: 512
let md = 1000000007;;
let ( *** ) x y = x * y mod md;;

let n, k = Scanf.scanf "%d %d" (fun x y -> x, y);;
let deg = Array.make n 0;;
for i = 1 to n - 1 do
  let a, b = Scanf.scanf " %d %d" (fun x y -> x-1, y-1) in
  deg.(a) <- deg.(a) + 1;
  deg.(b) <- deg.(b) + 1;
done;;

let rec perm n r = if n < 0 || r < 0 || n < r then 0
               else if r == 0 then 1
               else n *** perm (n - 1) (r - 1);;

Array.mapi (fun i x -> if i = 0 then perm k (x + 1) else perm (k-2) (x - 1)) deg
|> Array.fold_left ( *** ) 1
|> print_int;;
print_newline ();;


Measured memory_bytes: 7552
#include<iostream>
#include<math.h>
#define ll long long int
using namespace std;

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

	ll ans = 0,max_till_now = a[0];
	for(int i=1;i<n;++i) {
        if(a[i] > max_till_now){
            max_till_now = a[i];
        }
        else if(a[i] < max_till_now) {
            ans += (max_till_now - a[i]);
        }
	}
	cout << ans << " ";
	return 0;
}


Measured memory_bytes: 4756
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
#define vint vector<int>
#define vll vector<ll>
typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int from, to, cost; };
struct gNode { int from, to, cost; };
struct tNode { int value; int parent; vector<int> child; };

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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n/2);
	if(n & 1) res = res * x % MOD;
	return res;
}

int dp[SIZE];

int main(void){
	int n, k; cin >> n >> k;
	vint h(n);
	rep(i, n) cin >> h[i];

	fill(dp, dp+SIZE, INF);
	dp[0] = 0;
	rep(i, n){
		rep(j, k+1){
			if(i < n-j) dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j] - h[i]));
		}
	}
	cout << dp[n-1] << endl;

	return 0;
}

Measured memory_bytes: 1024