akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>

using namespace std;

#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))

typedef complex<double> P;
typedef long long ll;

const int MAX_SIZE = 10000;

// OÏ
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
// a1,a2ð[_Æ·éüªÆb1,b2ð[_Æ·éüªÌð·»è
int is_intersected_ls(P a1, P a2, P b1, P b2) {
    // üªª½sÈêÍdÈÁÄ¢È¢±ÆÉ·é
    if(abs(cross(a2-a1,b2-b1)) < EPS){
        return 0;
    }
    return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
        ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}
// a1,a2ð[_Æ·éüªÆb1,b2ð[_Æ·éüªÌð_vZ
P intersection_ls(P a1, P a2, P b1, P b2) {
  P b = b2-b1;
  double d1 = abs(cross(b, a1-b1));
  double d2 = abs(cross(b, a2-b1));
  double t = d1 / (d1 + d2);

  return a1 + (a2-a1) * t;
}

struct edgeInfo{
    P a;
    P b;
    int o;
    int l;
};

P p1,p2;

class Point{
public:
    P p;
    int l;
    int o;
    int t;

    bool operator<(const Point &pp)const{
        double dist1=abs(p1-pp.p);
        double dist2=abs(p1-this->p);
        return dist2<dist1;
    }
};

int main(){


    int data;
    cin>>data;
    while(data--){
        int x,y;
        cin>>x>>y;
        p1=P(x,y);
        cin>>x>>y;
        p2=P(x,y);
        int n;
        cin>>n;
        vector<edgeInfo> edges;
        for(int i = 0; i < n; i++){
            int xs,ys,xt,yt,o,l;
            cin>>xs>>ys>>xt>>yt>>o>>l;
            edgeInfo e;
            e.a=P(xs,ys);
            e.b=P(xt,yt);
            e.l=l;
            e.o=o;
            edges.push_back(e);
        }
        vector<Point> crossPoint;
        // ð_ðßé
        for(int i = 0;i < n; i++){
            if (abs(cross(p2-p1, edges[i].a-edges[i].b)) < EPS) { continue; }
            if(is_intersected_ls(edges[i].a,edges[i].b,p1,p2)){
                P res=intersection_ls(edges[i].a,edges[i].b,p1,p2);
                Point pp;
                pp.l=edges[i].l;
                pp.o=edges[i].o;
                pp.p=res;
                pp.t=pp.l^pp.o;
                crossPoint.push_back(pp);
            }
        }
        // ð_ðp1Éß¢ÔÉ\[g
        sort(crossPoint.begin(),crossPoint.end());

        if(crossPoint.size()==0){
            cout<<0<<endl;
            continue;
        }

        // »ÝÌ©ªÌHüîñ(1:nã,0:nº)
        int sit=0;
        sit=crossPoint[0].t;
        // ð_ðp1Éß¢ÔÉ
        int cnt=0;
        for(int i = 1; i < crossPoint.size(); i++){
            if(crossPoint[i].t!=sit){
                sit=crossPoint[i].t;
                cnt++;
            }

        }
        cout<<cnt<<endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

/*
cin.tie(0);
ios::sync_with_stdio(false);
*/

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int n,ans;
  cin>>n;
  for(int i=0;i<1000000;i++){
    if(i*i<=n)ans=i*i;
    else break;
  }
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
typedef vector < vector<ll> > Mat;

#define fi first
#define se second

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

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

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

  int N = S.length(), M = T.length();
  int ans = M;
  for (int i = 0; i <= N - M; i++){
    int cnt = 0;
    for (int j = 0; j < M; j++){
      if (S[i + j] != T[j]) cnt++;
    }
    ans = min(ans, cnt);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3632
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if i*500+j*100+k*50 == x:
        ans += 1
print(ans)

Measured memory_bytes: 9120
/*****And nothing else matters!******/

#include<bits/stdc++.h>
using namespace std;

#define pi 3.1415926535
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define llu unsigned long long
#define setbits(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define tc int test_case; cin >> test_case; while(test_case--)
#define f(i,a,n) for(int i = a ; i < n ; i++)
#define rf(i,n,a) for(int i = n-1 ; i >= a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define get(a,n) f(i,0,n) cin >> a[i];
#define show(a,n) f(i,0,n) cout << a[i] << " "; cout << endl;
#define sp(x) fixed << setprecision(10) << x
#define fast ios:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trace(x) cerr << '>' << #x << ':' << (x) << "\n"
#define trace2(x,y) cerr<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n"
#define trace3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define trace4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"

typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

const int inf = 1e9;
const ll inf64 = 1e18;
const int mod = inf + 7;
const int N = 1e6 + 10;

int main()
{
    fast;
    int n;
    cin >> n;
    vi a, b;
    f(i,0,n)
    {
        int x, y;
        cin >> x >> y;
        a.pb(x - y);
        b.pb(x + y);
    }

    sort(all(a));
    sort(all(b));

    cout << max(a.back() - a.front(), b.back() - b.front());
}


Measured memory_bytes: 5124
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//↑templete
#define int long long
signed main(){

	int N;
	cin>>N;
	int cnt[10][10]={};
	int ans=0;
	for(int i=1;i<=N;i++){
		string now=to_string(i);
		int a=now[0]-'0';
		int b=now.back()-'0';
		cnt[a][b]++;
	}
	for(int a=0;a<=9;a++){
		for(int b=0;b<=9;b++){
			ans+=cnt[a][b]*cnt[b][a];
		}
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        if(a + b <= (c * 2)) {
           System.out.println((a * x) + (b * y));
           return;
        }
        long minPrice = 0;
        if(x > y) {
            minPrice += c * 2 * y;
            x -= y;
            minPrice += Math.min(a, c * 2) * x;
        } else if(x < y) {
            minPrice += c * 2 * x;
            y -= x;
            minPrice += Math.min(b, c * 2) * y;
        } else {
            minPrice += c * 2 * x;
        }
        System.out.println(minPrice);
    }
}

Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main(){
  int n,q,t;cin>>n>>q;
  string name;
  queue<pair<string,int>> Q;
  
  for(int i=0;i<n;i++){
  	cin>>name>>t;
    Q.push(make_pair(name,t));
  }
  pair<string,int> u;
  int elaps=0,a;
  
  while(!Q.empty()){
  	u=Q.front();Q.pop();
    a=min(u.second,q);
    u.second-=a;
    elaps+=a;
    if(u.second>0){
    	Q.push(u); 
    }else{
    	cout<<u.first<<" "<<elaps<<endl;
    }
  }
}


Measured memory_bytes: 6228
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = iil()
B = iil()
ans = 0
sB = sum(B)
if n == 1:
    print(sum(A)+sum(B))
    exit()
for i in range(n):
#    print(A[:i])
#    print(B[:i-1])
    ans = max(sum(A[:i])-sum(B[:i-1])+sB,ans)
print(ans)

Measured memory_bytes: 3064
from collections import deque
n = int(input())
q = []
a=[]
for i in range(n):
    a.append(int(input())-1)
q.append(a[0])
cnt=0

while q:
    cnt+=1
    i = q.pop()
    q.append(a[i])
    if i==1:
        print(cnt)
        exit()
    if cnt>10**5:
        print(-1)
        exit()
print(-1)


Measured memory_bytes: 7424
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int v[1001][1001];
int cnt[1001][1001];
int main(){
	int h, w, n;
	while(cin >> h >> w >> n, h|w|n){
        FOR(i, 1, h+1) FOR(j, 1, w+1) cin >> v[i][j];
        for(int i = 1; i <= h; i++){
            for(int j = 1; j <= w; j++){
                if(i == 1 && j == 1){
                    cnt[i][j] = n-1;
                    continue;
                }
                cnt[i][j] = (!v[i-1][j]+cnt[i-1][j])/2+(v[i][j-1]+cnt[i][j-1])/2;
            }
        }
        int x = 1, y = 1;
        while(x <= w && y <= h){
            if((v[y][x]+cnt[y][x])%2)x++;
            else y++;
        }
        cout << y << ' ' << x << endl;
    }

    return 0;
}

Measured memory_bytes: 8992
n = int(input())
A1 = [int(i)  for i in input().split()]
A2 = [int(i)  for i in input().split()]
sums = []
for i in range(n):
  sums.append(sum(A1[0:i+1]) + sum(A2[i:n+1]))
print(max(sums))

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

int N;
int a[10001];

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

  int cnt = 0;
  for(int i=0; i<N; i++){
    while(a[i] % 2 == 0){
      cnt++;
      a[i] /= 2;
    }
  }
  cout<<cnt<<endl;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 112345;
int a[MAX_N];

int main2() {
  int N = nextInt();
  REP(i, N) a[i] = nextInt();
  sort(a, a + N);
  int b = a[0];
  for (int i = 0; i < N - 1; i++) {
    if (abs(a[N-1]/2.0 - b) > abs(a[N-1]/2.0 - a[i])) {
      b = a[i];
    }
  }
  cout << a[N - 1] << " " << b << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 640
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<set>
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
 
#define REP(i,n) for(ll i=0;i<(ll)(n);i++) //REP(i, 5) cout<<i;
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define MOD 1000000007 //10^9+7
//#define MOD 1
 
ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}
 
const int MAX = 2000;

long long fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void sosuu(ll n, vector<ll> &v){

  vector<ll> num(n, 0);

  FOR(i, 1, sqrt(n)){
    if(num[i]==0){
      FOR(j, 0, n/i){
        num[i+(j*i)] = 1;
      }
    }
  }
  REP(i, n){
    if(num[i]==0) v.push_back(i+1);
  }
}

ll GetDigit(ll num){
    ll digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}


int main(void){

  ll n,c,k;
  cin>>n>>c>>k;
  vector<ll> t(n);
  
  REP(i, n){
    ll x;
    cin>>x;
    t[i] = x;
  }
  sort(t.begin(), t.end());

  ll count = 0;
  ll time = 0;
  ll num = 0;

  REP(i, n){
    if(t[i]<=time && num<c){
      num++;
    }else{
      count++;
      time = t[i] + k;
      num = 1;
    }
  }
  cout<<count<<endl;
  return 0;
  
}

Measured memory_bytes: 1024
S = str(input())
s = []

tmp = 0
for i in range(len(S)-1):
  if S[i]=='L' and S[i+1]=='R':
    s.append(S[tmp:i+1])
    tmp = i+1
  elif i == len(S)-2:
    s.append(S[tmp:])
    
ans = [0]*len(S)
tmp = 0
for t in s:
  cnt = t.count('R')
  if len(t) % 2 == 0:
    ans[cnt+tmp-1], ans[cnt+tmp] = len(t)//2, len(t)//2
  else:
    if cnt % 2 == 0:
      ans[cnt+tmp-1], ans[cnt+tmp] = len(t)//2, len(t)//2+1
    else:
      ans[cnt+tmp-1], ans[cnt+tmp] = len(t)//2+1, len(t)//2
  tmp += len(t)
      
print(' '.join(map(str, ans)))

Measured memory_bytes: 20580
/*
 * * * * * * * * * * * * * 
 * Author: badgujjarajay *
 * * * * * * * * * * * * * 
 */

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
    int n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<tuple>
#include<string>
typedef unsigned long long ll;
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define repm(i,a,b) for(ll i=(a);i>(b);i--)
#define F first
#define S second
using namespace std;
const ll INF = 1e12;
const int i_INF = 2147483647;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
	ll n;
	cin >> n;
	ll min = INF;
	ll m = pow(n, 0.5);
	rep(i, 1, m + 1) {
		if (n % i == 0) {
			ll c = (i - 1) + (n / i - 1);
			if (c < min)min = c;
		}
	}
	cout << min << endl;
	return 0;
}

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif

int func(int a, int b, int c, int d){
    return abs(a-c) + abs(b-d);
}

signed main() {

    int a, b, x;
    cin>>a>>b>>x;
    
    if(a==0 && b==0) { cout << 1 << endl;}
    else if(a==0){cout<<b/x+1<<endl;}
    else{
        cout << b/x-(a-1)/x << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
class ModInt {
  static int MOD;
  long long x;

 public:
  static void mod(int m) { MOD = m; }

  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }

  long long val() { return x; }
};
int ModInt::MOD = 1000000007;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];

  vector<unordered_map<int, int>> B(N);
  unordered_map<int, int> lcm;
  rep(j, N) {
    int m = A[j];
    for (int i = 2; i * i <= m; i++) {
      if (m % i) continue;
      int r = 0;
      while (m % i == 0) {
        m /= i;
        r++;
      }
      B[j][i] = r;
      lcm[i] = max(lcm[i], r);
    }
    if (m != 1) {
      B[j][m] = 1;
      lcm[m] = max(lcm[m], 1);
    }
  }

  ModInt m = 1;
  for (auto it = lcm.begin(); it != lcm.end(); it++) {
    m *= ModInt(it->first).pow(it->second);
  }

  ModInt ans = 0;
  rep(i, N) ans += m / A[i];

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string.h>
#include <queue>

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

using namespace std;

typedef long long ll;

ll input[6];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll min = INF;
    
    REP(i, 6) {
        cin >> input[i];
        if (i != 0 && input[i] < min) {
            min = input[i];
        }
    }
    
    ll result = 0;
    if (input[0] < min) {
        result = 5;
    } else if (input[0] % min == 0) {
        result = (input[0] / min) + 4;
    } else {
        result = (input[0] / min) + 5;
    }
    
    cout << result << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 1000000000000000
#define fi first
#define se second
#define all(v) v.begin(),v.end()
int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
struct edge { int to, cost; };
int n;
string s;
signed main() {
	cin >> n >> s;
	int cnt = 0, ans;
	rep(i, n)if (s[i] == '.')cnt++;
	ans = cnt;
	rep(i, n) {
		if (s[i] == '#')cnt++;
		else cnt--;
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
typedef pair<ll,ll> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    ll n,k;
    ll ans=0;
    cin>>n>>k;
    if(k==0){
        ans=n*n;
        cout<<ans<<endl;
        return 0;
    }

    for(ll b=k+1;b < n+1;b++)
    {
        ans+=(b-k)*((n-b+1)/b +1);
        if(n%b<b-1) ans+=max(0ll,(n%b)-k+1);
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
/*
#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<typeinfo>
#include<utility>
#include<vector>
*/
#define int long long int
#define double long double
using namespace std;
#define MOD 1000000007
#define INF 1000000000000000007
const int MAX_N = 1 << 17;
#define rep(i, n) for (int(i) = 0, i##_len = (n); (i) < i##_len; (i)++)
#define reps(i, x) for (int(i) = 1; (i) <= (int)(x); (i)++)
#define rrep(i, x) for (int(i) = ((int)(x)-1); (i) >= 0; (i)--)
#define rreps(i, x) for (int(i) = ((int)(x)); (i) > 0; (i)--)
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define pb push_back
#define mp make_pair
#define bit(n) ((int)(1) << (n))
#define all(x) (x).begin(), (x).end()
#define debug(x) std::cout << #x << ": " << (x) << std::endl
#define nint int
using namespace std;

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
typedef pair<int, int> pii;
typedef pair<double, double> dop;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct aaa {
    aaa()
    {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} aaaaaaa;

int par[100000 + 1];    //親
int trank[100000 + 1];  //木の深さ

//n要素で初期化
void init(int n)
{
    for (int i = 0; i < n; i++) {
        par[i] = i;
        trank[i] = 0;
    }
}

//木の根を求める
int find(int x)
{
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    if (trank[x] < trank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (trank[x] == trank[y])
            trank[x]++;
    }
}

//xとyが同じ集合に属するか否か
bool same(int x, int y)
{
    return find(x) == find(y);
}

signed main()
{
    int n, m;
    cin >> n >> m;
    int out = 0;
    init(n);
    std::vector<std::vector<int>> xyz(m, std::vector<int>(3));
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z % 2 == 0) {
            z = 0;
        } else {
            z = 1;
        }
        x--;
        y--;
        xyz[i][0] = x;
        xyz[i][1] = y;
        xyz[i][2] = z;
        unite(x, y);
    }
    for (int i = 0; i < n; i++) {
        if (find(i) == i) {
            out++;
        }
    }
    cout << out << endl;
    return 0;
}

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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

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

    vector<ll> a(3*N);
    REP(i,3*N) cin >> a[i];
    sort(all(a));

    ll ans = 0;
    for(int i = N;i < 3*N ; i+=2) ans += a[i];

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

Measured memory_bytes: 2560
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*N
for i in range(1,N):
    dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i))
print(dp[N-1])                      
                      
                      
                  

Measured memory_bytes: 53216
from math import gcd
K = int(input())
sum_gcd = [0]*201
ans = 0
 
for i in range(1,K+1):
  for j in range(1,K+1):
    sum_gcd[gcd(i,j)] += 1
for i in range(1,K+1):
  for k in range(1,K+1):
    ans += sum_gcd[i]*gcd(i,k)
 
print(ans)

Measured memory_bytes: 9120
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main(void)
{
    int n;
    cin >> n;
    vector<int> a(n-1);
    rep(i, n-1) cin >> a[i];

    int ans[n];
    rep(i, n) ans[i] = 0;

    rep(i, n-1) {
        a[i]--;
        ans[a[i]]++;
    }
    
    rep(i, n) {
        cout << ans[i] << endl;
    }
    return 0;
}

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

using namespace std;

int main() {
  #ifdef _OFFLINE_
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  char str[200001];
  scanf("%s", str);
  int n = strlen(str);

  int cnt[26] = {};
  for(int i = 0; i < n; ++i) {
    cnt[ str[i] - 'a' ]++;
  }

  long long ans = 1;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < 26; ++j) {
      if(j != str[i] - 'a') {
        ans += cnt[j];
      }
    }
    cnt[ str[i] - 'a' ]--;
  }

  cout << ans;
}

Measured memory_bytes: 384
use std::io::*;
use std::str::*;

// const MOD: i32 = 1000000007;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: usize = read().unwrap();

    use std::collections::HashSet;
    let mut a = HashSet::new();


    for _ in 0..n {
        let tmp: usize = read().unwrap();
        a.insert(tmp);
    }
    println!("{}", a.len());

}

Measured memory_bytes: 4476
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  ll count = 0;
  for (int i = 0; i < n; ++i) {
    if(s[i] == 'W') count++;
  }
  ll res = min(count, n-count);
  int countW, countR = 0;
  vector<int> vW, vR;
  for (int i = 0; i < n; ++i) {
    if(s[i] == 'W'){
      countW++;
      vW.push_back(i);
    }
  }
  for (int i =0; i < n; i++) {
    if(s[i] == 'R'){
      countR++;
      vR.push_back(i);
    }
  }

  int ind = int(vR.size())-1;
  count = 0;
  // print(vW);
  // print(vR);
  if(vW.size() == 0 || vR.size() == 0){
    cout << 0 << endl;
    return 0;
  }
  for (int i = 0; i < int(vW.size()); ++i) {
    if(vW[i] < vR[ind]){
      swap(s[vW[i]], s[vR[ind]]);
      ind--;
      count++;
    }
  }
  chmin(res, count);

  cout << res << endl;

}


Measured memory_bytes: 4568
# https://scrapbox.io/rustacean/ABC166-F_Three_Variables_Game

def dfs(i, a, b, c)
  
  return if a < 0 || b < 0 || c < 0
  
  if i == N
    puts "Yes"
    puts $ans
    exit
  end
  
  if S[i] == "AB"
    $ans[i] = 'A'
    dfs(i+1, a+1, b-1, c  )
    $ans[i] = 'B'
    dfs(i+1, a-1, b+1, c  )
  elsif S[i] == "AC"
    $ans[i] = 'A'
    dfs(i+1, a+1, b  , c-1)
    $ans[i] = 'C'
    dfs(i+1, a-1, b  , c+1)
  else
    $ans[i] = 'B'
    dfs(i+1, a  , b+1, c-1)
    $ans[i] = 'C'
    dfs(i+1, a  , b-1, c+1)
  end
end

N, a, b, c = gets.to_s.split.map{|e|e.to_i}
S = Array.new(N){ gets.to_s.chomp }

$ans = Array.new(N)
dfs(0, a, b, c)

puts "No"

# def solve1(a,b,c)
  
#   N.times do |i|
    
#     s = gets.to_s.chomp
    
#     if s == "AB"
#       a > b ? ( a-=1; b+=1) : (a+=1; b-=1)
#     elsif s == "AC"
#       a > c ? ( a-=1; c+=1) : (a+=1; c-=1)
#     else
#       b > c ? ( b-=1; c+=1) : (b+=1; c-=1)
#     end
    
#     return "No" if a < 0 || b < 0 || c < 0
#   end
  
#   "Yes"
# end

# def solve2(a, b, c)
  
#   N.times do |i|
#   s = gets.to_s.chomp
#     if (s == "AB" && (a == 0 && b == 0)) || (s == "AC" && (a == 0 && c == 0)) || (s == "BC" && (b == 0 && c == 0))
#       return "No"
#     else
#       return "Yes"
#     end
#   end
# end

# N, a, b, c = gets.to_s.split.map{|e|e.to_i}
# if 0 == a + b + c
#   puts "No"
# elsif 1 == a + b + c
#   puts solve1(a, b, c)
# else # 1 < a + b + c
#   puts solve2(a, b, c)
# end



Measured memory_bytes: 43244
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N, minNum=2e9, maxNum=-1, tmp;
    cin >> N;
    
    for(int i=0; i<N; i++){
	cin >> tmp;
	minNum = min(minNum, tmp);
	maxNum = max(maxNum, tmp);
    }

    cout << maxNum-minNum << endl;

}


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

#define int long long
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) otp(v[i]) cte
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n,m,a,b,ans[51];

main() {
    cin >> n >> m;
    rep(i,m) {
        cin >> a >> b;
        ans[a]++;
        ans[b]++;
    }
    rep1(i,n) ct(ans[i])
}

Measured memory_bytes: 256
//#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int>x(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	sort(x.begin(), x.end());
	long long int ans = 1e9;
	for (int i = x[0]; i <= x[n - 1]; i++) {
		long long int sum = 0;
		for (int j = 0; j < n; j++) {
			sum += pow(i - x[j], 2);
		}
		ans = min(ans, sum);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3556
class Arrow
  attr_reader :source, :sink, :label

  def initialize(source, sink, label)
    @source = source
    @sink = sink
    @label = label
  end
end

def push(queue, spell)
  size = queue.size
  index = queue.index{|entry| entry[0] >= spell} || size
  return queue[index][1] if index < size && queue[index][0] == spell

  # return nil if index > 0 && !spell.start_with?(queue[index - 1][0])
  queue.slice!(index..-1) if index < size && !queue[index][0].start_with?(spell)

  nodes = {}
  queue.insert(index, [spell, nodes])
  nodes
end

def calc(n, arrows, start, goal)
  ins = Array.new(n){[]}
  arrows.each do |arrow|
    ins[arrow.sink] << arrow.source
  end

  reachable_from = {}
  stack = [goal]
  until stack.empty?
    node = stack.pop
    reachable_from[node] = true
    ins[node].each do |source|
      stack << source unless reachable_from[source]
    end
  end

  return nil unless reachable_from[start]
  arrows.select!{|arrow| reachable_from[arrow.sink]}

  outs = Array.new(n){[]}
  arrows.each do |arrow|
    outs[arrow.source] << arrow
  end

  limit = n * arrows.map{|arrow| arrow.label.size}.max

  queue = [['', {start => true}]]
  until queue.empty?
    spell, nodes = queue.shift
    return spell if nodes[goal]
    return nil if spell.size > limit

    nodes.each do |node, _|
      outs[node].each do |arrow|
        new_nodes = push(queue, spell + arrow.label)
        new_nodes[arrow.sink] = true if new_nodes
      end
    end
  end
  nil
end

loop do
  n, a, s, g = gets.split.map(&:to_i)
  break if n == 0

  arrows = (0...a).map do |i|
    x, y, lab = gets.split
    Arrow.new(x.to_i, y.to_i, lab)
  end

  puts calc(n, arrows, s, g) || 'NO'
end

Measured memory_bytes: 10696
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int a, b, k;
    cin>>a>>b>>k;
    if(b-a>=2*k){
        rep(i, k) cout<<a+i<<endl;
        rep(i, k) cout<<b-(k-1)+i<<endl;
    }
    else {
        for(int i =a;i<=b;i++) cout<<i<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
<?php


fscanf(STDIN, "%d%d",$N, $K);
$map = fscanf(STDIN, str_repeat("%d", $N));

for($i=0;$i<$N;$i++){
    $tmp = 0;
    for($j=$i;$j<$N;$j++){
        $tmp+= $map[$j];
        $list[] = $tmp;
    }
}
$ans = 0;
for($i=40;$i>=0;$i--){
    $k=0;
    $tmp = [];
    foreach($list as $value){
        if(($value & 2**$i) > 0){
            $k++;
            $tmp[] = $value;
        }
    }
    if($k >= $K){
        $list = $tmp;
        $ans += 2**$i;
    }
}
echo $ans;

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

using namespace std;

typedef long long LL;

const int maxn = 5e3 + 5;
const int P = 1e9 + 7;

int n, f[maxn][maxn], len;

char s[maxn];

inline int read() {
	char ch = getchar(); int u = 0, f = 1;
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) {u = u * 10 + ch - 48;  ch = getchar();} return u * f;
}

inline int ksm(int x, int k) {
	int cnt = 1;
	while(k) {
		if(k & 1) cnt = 1ll * cnt * x % P;
		x = 1ll * x * x % P; k >>= 1;
	} return cnt;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}

int main() {
	n = read(); scanf("%s", s + 1);
	len = strlen(s + 1);
	/*for(register int i = 1; i <= len; i++) s[i] -= '0';

	f[1][0][0] = 1;
	f[1][1][0] = 1; f[1][1][1] = 1;

	for(register int i = 2; i <= n; i++) {
		int t = i & 1, t0 = t ^ 1;

		memset(f[t], 0, sizeof(f[t]));

		for(register int j = 0; j <= i; j++) {
			if(j <= 0) {
				f[t][j][0] = pls(f[t0][1][0], f[t0][1][1]);
				f[t][j][0] = pls(f[t][j][0], f[t0][j][0]); continue;
			}
			int p0 = s[j - 1] << 1;
			f[t][j][p0] = pls(f[t0][j + 1][0], f[t0][j + 1][1]);
			f[t][j][p0 | 1] = pls(f[t0][j + 1][2], f[t0][j + 1][3]);
			if(j > 1) {
				int p1 = s[j - 2] << 1;
				f[t][j][0] = pls(f[t][j][0], f[t0][j - 1][p1]);
				f[t][j][1] = pls(f[t][j][1], f[t0][j - 1][p1]);
				f[t][j][2] = pls(f[t][j][2], f[t0][j - 1][p1 | 1]);
				f[t][j][3] = pls(f[t][j][3], f[t0][j - 1][p1 | 1]);
			} else {
				f[t][j][0] = pls(f[t][j][0], f[t0][j - 1][0]);
				f[t][j][1] = pls(f[t][j][1], f[t0][j - 1][0]);
			}
		}
	}

	cout << f[n & 1][len][s[len] | (s[len - 1] << 1)];*/
	
	f[0][0] = 1;
	for(register int i = 1; i <= n; i++)
		for(register int j = 0; j <= i; j++) {
			if(j > 0)
				f[i][j] = pls(f[i][j], f[i - 1][j - 1] * 2 % P);
			else f[i][j] = pls(f[i][j], f[i - 1][j]);
			f[i][j] = pls(f[i][j], f[i - 1][j + 1]);
		}
	
	cout << (1ll * f[n][len] * ksm(ksm(2, len), P - 2) % P);
	return 0;
}


Measured memory_bytes: 96384
#include<iostream>
#include<queue>

using namespace std;
static const int N = 100;
static const int INFTY = (1 << 21);

int n, M[N][N];
int d[N];

void bfs(int s) {
  queue<int> q;
  q.push(s);
  for ( int i = 0; i < n; i++ ) d[i] = INFTY;
  d[s] = 0;
  int u;
  while( !q.empty() ) {
    u = q.front(); q.pop();
    for ( int v = 0; v < n; v++ ) {
      if ( M[u][v] == 0 ) continue;
      if ( d[v] != INFTY ) continue;
      d[v] = d[u] + 1;
      q.push(v);
    }
  }
  for ( int i = 0; i < n; i++ ) {
    cout << i+1 << " " << ( (d[i] == INFTY) ? (-1) : d[i] ) << endl;
  }
}

int main() {
  int u, k, v;

  cin >> n;
  for ( int i = 0; i < n; i++ ){
    for ( int j = 0; j < n; j++ ) M[i][j] = 0;
  }

  for ( int i = 0; i < n; i++ ) {
    cin >> u >> k;
    u--;
    for ( int j = 0; j < k; j++ ) {
      cin >> v;
      v--;
      M[u][v] = 1;
    }
  }
  bfs(0);

  return 0;
}


Measured memory_bytes: 3112
import math

N = int(input())
a_li = []
b_li = []
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    a_li.append(a)
    b_li.append(b)
for i in reversed(range(N)):
    a, b = a_li[i], b_li[i]
    a += ans
    div = math.ceil(a / b)
    ans += b * div - a
print(ans)


Measured memory_bytes: 85664
S = input()

mae = int(S[:2])
ato = int(S[2:])

if mae <= 12 and ato <= 12 and mae != 0 and ato != 0:
    print("AMBIGUOUS")
elif mae > 12 and ato <= 12 and ato != 0:
    print("YYMM")
elif mae <= 12 and ato > 12 and mae != 0:
    print("MMYY")
elif mae <= 12 and ato == 0 and mae != 0:
    print("MMYY")
elif mae == 0 and ato <= 12 and ato != 0:
    print("YYMM")
else:
    print("NA")

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

int main(){
  int n,y;
  cin >> n >> y;
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= n-i; j++){
      if(y==i*10000+j*5000+(n-i-j)*1000){
        cout << i << " " << j << " " << n-i-j << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
}


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

int main(){
    int N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> table(N);
    for(int i =0; i < N; i++){
        long long a, b;
        cin >> a >> b;
        table.at(i) = make_pair(a,b);
    }
    sort(table.begin(), table.end());
    long long sum = 0;
    long long bottles = 0;
    for(int i =0; i < N; i++){
        bottles += table.at(i).second;
        if(bottles > M){
            sum += table.at(i).first*(M + table.at(i).second - bottles);
            break;
        }
        else {
            sum += table.at(i).first*table.at(i).second;
            // cout << sum << endl;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.rmi.server.ExportException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.solve();
    }
    private void solve() throws Exception {
        FastScan scan = new FastScan(System.in);
        int N = scan.scanInt();
        List<Path>[] graph = new List[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int a = scan.scanInt()-1;
            int b = scan.scanInt()-1;
            long c = scan.scanLong();
            graph[a].add(new Path(b, c));
            graph[b].add(new Path(a, c));
        }
        int Q = scan.scanInt();
        int K = scan.scanInt()-1;
        Queue<Integer> queue = new ArrayDeque<>(N);
        long[] distances = new long[N];
        boolean[] visited = new boolean[N];
        Arrays.fill(distances, Long.MAX_VALUE);
        distances[K] = 0;
        queue.add(K);
        while(!queue.isEmpty()) {
            int current = queue.poll();
            visited[current] = true;
            for (Path p : graph[current]) {
                if (visited[p.to]) {
                    continue;
                }
                distances[p.to] = distances[current] + p.cost;
                queue.add(p.to);
            }
        }
        for (int i = 0; i < Q; i++) {
            int from = scan.scanInt() - 1;
            int to = scan.scanInt() - 1;
            System.out.println(distances[from] + distances[to]);
        }
    }

    class Path {
        int to;
        long cost;
        Path(int to, long cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    class FastScan {
        BufferedReader br;
        StringTokenizer st;
        FastScan(InputStream is) {
            InputStreamReader isr = new InputStreamReader(is);
            this.br = new BufferedReader(isr);
        }
        String next() throws IOException {
            while (this.st == null || !this.st.hasMoreTokens()) {
                this.st = new StringTokenizer(br.readLine().trim());
            }
            return st.nextToken();
        }
        long scanLong() throws IOException {
            return Long.parseLong(this.next());
        }
        int scanInt() throws IOException {
            return Integer.parseInt(this.next());
        }
        double scanDouble() throws IOException {
            return Double.parseDouble(this.next());
        }
        char scanCharacter() throws IOException {
            return this.next().charAt(0);
        }
        String nextLine() throws IOException {
            return br.readLine().trim();
        }
    }
}


Measured memory_bytes: 84868