akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
int A[220000], B[220000];
signed main() {
    cin >> N;
    rep(i, N) { cin >> A[i] >> B[i]; }
    sort(A, A + N), sort(B, B + N);
    if (N & 1) {
        cout << B[N / 2] - A[N / 2] + 1 << endl;
    } else {
        cout << (B[N / 2] + B[N / 2 - 1]) - (A[N / 2] + A[N / 2 - 1]) + 1 << endl;
    }
}

Measured memory_bytes: 6760
#include <iostream>
#include <string>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main(){
  int N, T[50];
  string S[50], X;
  cin >> N;
  REP(i, N) {
    cin >> S[i] >> T[i];
  }
  cin >> X;
  int sleep = 0;
  for(; sleep < N; ++sleep) {
    if(S[sleep] == X) break;
  }
  int ret = 0;
  for(int i = sleep+1; i < N; ++i) {
    ret += T[i];
  }
  cout << ret << endl;
}

Measured memory_bytes: 256
//
// じょえチャンネル
// https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
//
// Created by yamunaku on 2020/02/22.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    //CFS;
    int n, q;
    cin >> n >> q;
    vl d(n);
    rep(i, n) cin >> d[i];
    rep(_, q){
        ll k, x, m;
        cin >> k >> x >> m;
        k--;
        ll ans = 0;
        ll sum = 0;
        ll add = 0;
        rep(i, n){
            if(d[i] % m == 0) ans += k / n + (i < k % n ? 1 : 0);
            if(i < k % n) add += d[i] % m;
            sum += d[i] % m;
        }
        add += k / n * sum;
        ans += (x + add) / m - x / m;
        cout << k - ans << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define All(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
#define IN(a, b, x) (a<=x&&x<b)
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<ll>>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename t, typename u, typename Comp=less<>>
bool chmax(t& xmax, const u& x, Comp comp={}) { if(comp(xmax, x)) { xmax = x; return true; } return false;}
template<typename t, typename u, typename Comp=less<>>
bool chmin(t& xmin, const u& x, Comp comp={}) { if(comp(x, xmin)) { xmin = x; return true;} return false;}
const int INF = 1e9;
const ll infl = ll(1e18)+5;
/*
*ios::sync_with_stdio(false);
*cin.tie(0);
*/

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

Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

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

	type

--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

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

	container

--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

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

	repetition

--------------------------------------------
*/
#define REP(n) for (int i = 0; i < n; i++)
#define REPj(n) for (int j = 0; j < n; j++)
#define REPinit(a, n) for (int i = a; i < n; i++)
#define REPinitj(a, n) for (int j = a; j < n; j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

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

	constant

--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

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

	Optimizer

--------------------------------------------
*/
//#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/*
--------------------------------------------
 
	Utility Algorithm

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

template <typename T>
void swapAlgorithm(T &a, T &b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

template <typename T1>
T1 euclideanAlgorithm(T1 a, T1 b)
{
    T1 a_tmp = a;
    T1 b_tmp = b;

    if (a_tmp > b_tmp)
    {
        swapAlgorithm<T1>(a_tmp, b_tmp);
    }

    T1 r = a_tmp % b_tmp;
    while (r != 0)
    {
        a_tmp = b_tmp;
        b_tmp = r;
        r = a_tmp % b_tmp;
    }
    return b_tmp;
}

template <typename T2>
T2 getLCM(T2 a, T2 b)
{
    return (a * b) / (euclideanAlgorithm(a, b));
}

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

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

    int N, A, B;
    cin >> N >> A >> B;
    cout << ((N * A < B) ? (N * A) : B) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <climits>
#include <utility>
#include <deque>
#include <list>
#include <stdexcept>
using namespace std;

#define ll long long
#define IN(type, name) type name; cin >> name
#define IN_V(type, name, size) vector<type> name(size); for(auto& x: name) cin >> x
#define IN_VPair(type1, type2, name, size) vector<pair<type1, type2>> name(size); for(auto& x: name) cin >> x.first >> x.second
#define IN_VW(type, name, size) vector<type> name(size); for(auto& x: name)

#define REP(name, start, end) for(ll name = (start); (name) < (end); ++(name))
#define ALL(iterable) (iterable).begin(), (iterable).end()

int main()
{
	cout << fixed << setprecision(6);
	IN(ll, n);
	IN_V(ll, hls, n);
	vector<ll> cost_dp(n);

	cost_dp[0] = 0;
	cost_dp[1] = abs(hls[1] - hls[0]);
	REP(i, 2, n) {
		cost_dp[i] = min(cost_dp[i - 2] + abs(hls[i] - hls[i - 2]), cost_dp[i - 1] + abs(hls[i] - hls[i - 1]));
	}

	cout << cost_dp[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 1792
macro_rules! input {
     (source = $s:expr, $($r:tt)*) => {
         let mut iter = $s.split_whitespace();
         input_inner!{iter, $($r)*}
     };
     ($($r:tt)*) => {
         let s = {
             use std::io::Read;
         let mut s = String::new();
         std::io::stdin().read_to_string(&mut s).unwrap();
         s
     };
     let mut iter = s.split_whitespace();
     input_inner!{iter, $($r)*}
     };
}
     
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::io::{stdout, Write, BufWriter};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
//#[allow(unused_imports)]
//use proconio::marker::{Isize1, Usize1, Bytes, Chars};

//#[proconio::fastout]
fn main() {
    input!{
        n: usize,
        words: [String; n],
    }
    let words: Vec<Vec<char>> = words.iter().map(|word| {
        word.chars().collect::<Vec<char>>()
    }).collect();
    if isdup(&words) {
        println!("No");
        return;
    }
    for i in 0..(n - 1) {
        if words[i].last().unwrap() != words[i + 1].first().unwrap() {
            println!("No");
            return;
        }
    }
    println!("Yes");
}

use std::collections::HashMap;
fn isdup<T>(v: &[T]) -> bool
where T: std::hash::Hash + std::cmp::Eq
{
    let mut map = HashMap::new();
    for e in v {
        let counter = map.entry(e).or_insert(0);
        *counter += 1;
    }
    map.values().any(|v| *v >= 2)
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
using namespace std;
int main(){

  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<=N-1;i++){
  
    cin>>A[i];
  }
  int nextnum=1;
  int ans=0;
  for(int i=0;i<=N-1;i++){
  
    if(A[i]==nextnum){
    
      nextnum++;
    }
    else{
    
      ans++;
    }
  }
  if(nextnum==1){
  
    cout<<-1;
    return 0;
  }
  cout<<ans;
}

Measured memory_bytes: 4044
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
#include <queue>
#define LL long long
#define inf 0x3f3f3f3f
#define lson rt<<1
#define rson rt<<1|1
#define PII pair<int,int>
#define test freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
using namespace std;
const int maxn=3e5+5;
int a[maxn],pre[maxn];
char s[maxn];
int main()
{
    //test
    int n,k;
    scanf("%d%d",&n,&k);
    scanf("%s",s);
    vector<int>sav,ans;
    s[0]='0';
    for(int i=0;s[i];++i) if(s[i]=='0') sav.push_back(i);
    int p=n;
    while(p)
    {
        int nex=lower_bound(sav.begin(),sav.end(),p-k)-sav.begin();
        nex=sav[nex];
        ans.push_back(p-nex);
        if(nex==p) {puts("-1");return 0;}
        p=nex;
    }
    for(int i=ans.size()-1;i>=0;--i) printf("%d ",ans[i]);
    return 0;
}


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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;
using Pdd = P<double,double>;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

int main(){
    int n,m;
    cin>>n>>m;
    V<Vi> s(m);
    REP(i,m){
        int k;
        cin>>k;
        REP(j,k){
            int s_tmp;
            cin>>s_tmp;
            s[i].pb(s_tmp);
        }
    }
    Vi p(m);
    REP(i,m) cin>>p[i];

    LL cnt = 0;
    REP(i,1<<n){
        Vi num_on(m,0);
        REP(k,m){
            REP(j,s[k].size()){
                if(bitset<10>(i)[s[k][j]-1]) num_on[k]++;
            }
        }
        bool flag = true;
        REP(j,m){
            if(num_on[j]%2!=p[j]){
                flag=false;
                break;
            }
        }
        if(flag) cnt++;
    }

    cout<<cnt<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
void solve() {
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    cout << max(0ll, a - 2 * b) << endl;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    ll sum = 0;
    ll ans = 10000000000000000;
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());

    for(int i = a[0]; i <= a[n-1]; i ++){
        sum = 0;
        rep(j,n){
            sum += (i-a[j])*(i-a[j]);
        }
        ans = min(ans,sum);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3632
def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

def main():
  global N 
  N, M = map(int, input().split())
  global par 
  par = [-1] * N
  p = list(map(int, input().split()))
  for i in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)
  ans = 0
  for i in range(N):
    if same(i, p[i]-1):
      ans += 1
  print(ans)

if __name__ == "__main__":
  main()


Measured memory_bytes: 15220
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
const int INF = 1001001001;

int main(){
  int n,m,l;
  cin >> n >> m >> l;
  vector<vector<int>> dist(n,vector<int>(n,INF));
  rep(i,n) dist[i][i] = 0;
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    a--; b--;
    dist[a][b] = dist[b][a] = c;
  }
  rep(k,n) rep(i,n) rep(j,n) chmin(dist[i][j],dist[i][k]+dist[k][j]);
  vector<vector<int>> dist2(n,vector<int>(n,INF));
  rep(i,n){
    rep(j,n){
      if(dist[i][j]<=l) dist2[i][j] = 1;
    }
  }
  rep(k,n) rep(i,n) rep(j,n) chmin(dist2[i][j],dist2[i][k]+dist2[k][j]);
  int q;
  cin >> q;
  rep(qi,q){
    int s,t;
    cin >> s >> t;
    s--; t--;
    int ans = dist2[s][t]-1;
    if(dist2[s][t]==INF) ans = -1;
    cout << ans << endl;
  }
}


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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

char A[4] = {'A', 'C', 'G', 'T'};

int main()
{
    char b;
    cin >> b;
    REP(i, 4)
    {
        if (A[i] == b)
        {
            cout << A[3 - i] << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 256
using System;

namespace ITP1_8_C
{
    class Program
    {
        static void Main(string[] args)
        {
            
            int[] output = new int[26];

            while (true)
            {
                string input = Console.ReadLine();
                if (input == null || input.Length == 0) break;

                input = input.ToLower();

                foreach (char i in input)
                {
                    if (i >= 'a' && i <= 'z')
                    output[ i - 'a' ] ++;
                }
            }
            
            for (char j='a'; j<='z'; j++)
            {
                Console.WriteLine("{0} : {1}", j, output[(j - 'a')]);
            }

        }
    }
}

Measured memory_bytes: 9180
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val ab = (1..n).map { readLine()!!.split(" ").map { it.toLong() } }.reversed()
    var cnt = 0L
    for (i in 0 until n) {
        val a = ab[i][0]
        val b = ab[i][1]
        val r = (cnt + a) % b
        if (r != 0L) cnt += b - r
    }
    println(cnt)
}

Measured memory_bytes: 65928
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SZ size()
int main()
{
    ll t,k,n,d,q,ct,x;
    map<ll,ll>mp;
    string a;
    cin>>n>>d;
    vector<vector<ll> >v(n, vector<ll>(d));
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<d;j++)
        {
            cin>>v[i][j];
        }
    }
    ct=0;
    double p;
    for(ll i=0;i<n;i++)
    {
        for(ll j=i+1;j<n;j++)
        {
            p=0.0;
            for(ll k=0;k<d;k++)
            {
                x=(v[i][k]-v[j][k]);
                p+=x*x;
            }
            p=sqrt(p);
            if(p==int(p)) ct++;
        }
    }
    cout<<ct<<endl;
}






Measured memory_bytes: 256
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-05-19 17:18
# @url:https://atcoder.jp/contests/abc135/tasks/abc135_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    s=str(input())
    S=s[::-1]
    dp=[[0]*13 for i in range(len(S))]
    mod=10**9+7
    p=1 # 每位的权重10的幂次
    for i in range(len(S)):
        if i==0:
            if S[i]!='?':
                t=p*int(S[i])%13
                dp[i][t]+=1
            else:
                for j in range(10):
                    dp[i][j]+=1
        else:
            if S[i]!='?':
                t=p*int(S[i])%13
                for j in range(13):
                    temp=(t+j)%13
                    dp[i][temp]=dp[i-1][j]%mod
            else:
                for j in range(10):
                    # t=p*j%13
                    for k in range(13):
                        temp=(p*j%13+k)%13
                        dp[i][temp]=(dp[i][temp]+dp[i-1][k])%mod
        p=(p%13*10%13)%13
    # print (dp)
    print (dp[len(S)-1][5])
if __name__ == "__main__":
    main()

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

using namespace std;

int main() {
  int H, W, h, w;
  cin >> H >> W >> h >> w;

  if(H % h == 0 && W % w == 0) {
    cout << "No" << endl;
    return 0;
  }

  cout << "Yes" << endl;

  bool hwSwapped = false;

  if(W % w == 0) {
    swap(W, H);
    swap(w, h);
    hwSwapped = true;
  }

  vector<int> s(W + 1);

  for(int i = 0; i < w; i++) {
    s[i] = 1000;
  }
  s[0] = 0;

  for(int i = w; i <= W; i++) {
    s[i] = s[i - w] - 1;
  }

  vector<int> a(W);

  for(int i = 0; i < W; i++) {
    a[i] = s[i + 1] - s[i];
  }

  if(hwSwapped) {
    for(int i = 0; i < W; i++) {
      for(int j = 0; j < H; j++) {
        cout << a[i];
        if(j == H - 1) {
          cout << endl;
        }else {
          cout << ' ';
        }
      }
    }
  }else{

    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        cout << a[j];
        if(j == W - 1) {
          cout << endl;
        }else {
          cout << ' ';
        }
      }
    }
  }



}


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

int main(){
    int n,k;
    int ans =0;
    cin >> n >> k;
    vector <int> a(n);
    for (int i =0;i<n;i++){
        cin >> a.at(i);
    }
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    for(int i=0;i<k;i++){
        ans+=a.at(i);
    }
        cout << ans << endl;
}    


Measured memory_bytes: 256
/*Remember: The Struggle is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

//reference:
//https://codeforces.com/blog/entry/74551

//crux: appending zeros to a no. doesn't change it's divisibility by p
//if p is co-prime to 10
//because (a*10^x)%p = 0 only when a%p = 0 as (10^x)%p != 0

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

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     makep        make_pair
#define     maket        make_tuple
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const int inf=1e18,M=1e9+7;
const int N=1e4+10;

vector<int> cnt(N);

int n,p;

int pw(int x,int n)
{
    int res=1;

    x%=p;
    for(;n;n/=2)
    {
        if(n%2)
            res=(res*x)%p;

        x=(x*x)%p;
    }

    return res;
}


void solve()
{
    cin>>n>>p;

    string s;
    cin>>s;

    if(p==2 || p==5)
    {
        int ans=0;
        for(int i=0;i<n;++i)
        {
            if((s[i]-'0')%p==0)
                ans+=i+1;
        }

        cout<<ans;

        return;
    }

    vector<int> pre(n+1,0);
    ++cnt[0];
    for(int i=0;i<n;++i)
    {
        pre[i+1]=(pre[i]+((s[i]-'0')*pw(10,n-i-1))%p)%p;
        ++cnt[pre[i+1]];
    }

    int ans=0;
    for(int i=0;i<p;++i)
        ans+=(cnt[i]*(cnt[i]-1))/2;

    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}




Measured memory_bytes: 2196
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int d, t, s;
	cin >> d >> t >> s;
	double t1  = (double)d/s;
	if(t1<=t) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define ll long long
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main(){
    int x; cin >> x;
    while(!IsPrime(x)){
        ++x;
    }
    cout << x << endl;
    return 0;
}

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

int main() {
	
	int N, M, T;
	cin >> N >> M >> T;
	
	vector<int>a (N+1);
	a[N] = T;
	
	for( int i = 0; i < N; i++)
		cin >> a[i];
		
	int ans = a[0] - M;
	
	for( int i = 0; i < a.size()-1; i++) {
		if( i == a.size() - 2 )
			ans += max(0, a[i+1]-a[i]-M);
		else
			ans += max(0, a[i+1]-a[i]-2*M);
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3136
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,Q=map(int,input().split())

uf=UnionFind(N)
for i in range(Q):
    t,u,v=map(int,input().split())

    if t==0:
        uf.union(u,v)
    else:
        if uf.find(u)==uf.find(v):
            print(1)
        else:
            print(0)


Measured memory_bytes: 11560
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int n;
    cin >> n;
    vector<ll> a(n);
    ll XorSum = 0;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        XorSum ^= a[i];
    }
    if(XorSum == 0){
        cout << 0 << endl;
        return 0;
    }
    XorSum ^= a[0];
    XorSum ^= a[1];
    ll X = a[0] + a[1] - XorSum;
    if(X % 2 != 0 || X < 0){
        cout << -1 << endl;
        return 0;
    }
    X >>= 1;
    
    ll A = X, B = X;
    for(int d = 50; d >= 0; --d){
        if(A >> d & 1)  continue;
        if(XorSum >> d & 1){
            if(A + (1LL << d) <= a[0]){
                A += 1LL << d;
            }
            else{
                B += 1LL << d;
            }
        }
    }
    if(A <= 0 || B < a[1]){
        cout << -1 << endl;
        return 0;
    }
    XorSum ^= A;
    XorSum ^= B;
    ll ans = a[0] - A;
    if(ans < 0 || XorSum != 0)  cout << -1 << endl;
    else    cout << ans << endl;
}

Measured memory_bytes: 3628
import Control.Monad
import Control.Applicative
import Data.List
solve :: [String] -> String
solve (n:ls) =
    let (l,r) = foldl' duel (0,0) $ map words ls in
    show l ++ " " ++ show r
    where
    duel :: (Int,Int) -> [String] -> (Int,Int)
    duel (pl,pr) [cl,cr]
        | cl < cr = (pl, pr+3)
        | cl > cr = (pl+3, pr)
        | otherwise = (pl+1, pr+1)

main =
    putStrLn =<< solve . lines <$> getContents 


Measured memory_bytes: 4112
let split c s = (
    let res = ref [] in
    let i = ref 0 in
    let n = String.length s in
    while !i < n do
      let j = !i in
      while !i < n && s.[!i] <> c do i := !i + 1 done;
      res := String.sub s j (!i - j) :: !res;
      i := !i + 1;
    done;
    List.rev !res
  );;

let rec range a b = if a > b then [] else a :: range (a + 1) b;;
let read_ints () = read_line () |> split ' ' |> List.map int_of_string;;

let rec gcd x y = if y = 0 then x else gcd y (x mod y);;
let lcm x y = x / gcd x y * y;;

let [a; b; c; d] = read_ints ();;
let a = a - 1;;

let f x c d = x - x / c - x / d + x / lcm c d;;

print_int (f b c d - f a c d);;
print_newline ();;


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    long n = input.nextLong();
    long ans = 1;
    while (n > 0) {
      ans = ans * 2;
      n = n / 2;
    }
    System.out.print(ans - 1);
  }
}


Measured memory_bytes: 21844
#!/usr/bin python3
# -*- coding: utf-8 -*-

import math

def main():
    A, B, H, M = map(int, input().split())
    rda = math.radians(360*(60*H+M)/(60*12))
    rdb = math.radians(360*M/60)
    La = [A*math.cos(rda),A*math.sin(rda)]
    Lb = [B*math.cos(rdb),B*math.sin(rdb)]
    ret = (La[0]-Lb[0])**2 + (La[1]-Lb[1])**2
    ret = ret ** 0.5
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9592
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{
	
	public static void main(String[] args) {
	
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		String st = fs.next();
		int ans = solve(st);
		System.out.println(ans);
		
		
	}
	
	static int solve(String s) {
		char[] arr = s.toCharArray();
		int countR = 0;
		for(char i: arr) {
			if(i=='R') {
				countR++;
			}
		}
		int countRinRange=0;
		for(int i=0;i<countR;i++) {
			if(arr[i]=='R') {
				countRinRange++;
			}
		}
		return countR-countRinRange;
	}
	
	void sort(int[] a) {
		ArrayList<Integer> list=new ArrayList<>();
		for (int i:a) list.add(i);
		Collections.sort(list);
		for (int i=0; i<a.length; i++) a[i]=list.get(i);
	}
	
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		public String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
	}
 
}





Measured memory_bytes: 37048
import math

#回転行列
#cosA -sinA
#sinA cosA

a, b, h, m = map(int, input().split())

hp_before = [0, a]
mp_before = [0, b]

h_rect = math.radians((h / 12 + m / 60 / 12) * 360)
m_rect = math.radians(m / 60 * 360)

hp_after = [hp_before[0]*math.cos(h_rect) - hp_before[1]*math.sin(h_rect),
            hp_before[0]*math.sin(h_rect) + hp_before[1]*math.cos(h_rect)]
mp_after = [mp_before[0]*math.cos(m_rect) - mp_before[1]*math.sin(m_rect),
            mp_before[0]*math.sin(m_rect) + mp_before[1]*math.cos(m_rect)]

distance = math.sqrt( (hp_after[0]-mp_after[0])**2 + (hp_after[1]-mp_after[1])**2 )

print(distance)

Measured memory_bytes: 9468
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
    static final int MAX = 100100;
    InputStream in = System.in;
    PrintStream out = System.out;
    // static int dp[][] = new int[MAX][MAX];
    static int L[] = new int[110];

    public void _main(String[] args) {
        Scanner sc = new Scanner(in);
        int N = sc.nextInt();
        int X = sc.nextInt();
        for(int i=0;i<N;i++) L[i] = sc.nextInt();

/*        int d=0,i=0;
        while (d<=X) {
            if (i<N) d += L[i++];
            else {
                i++;
                break;
            }
        }*/
        int cnt=1,d=0;
        for (int i=1;i<=X;i++) {
            if (cnt-1<N && d+L[cnt-1] <= X) d+=L[cnt++-1];
        }
        out.println(cnt);
    }

    public static void main(String[] args) {
        new Main()._main(args);
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
    return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 1e5 + 7, mod = 1e9 + 7;
int n;
int sa[N], sb[N];
LL val[N], sf[N], g[N], sg[N], f[N], ans, A, B;
void add(LL &a, LL b) { a += b; if(a >= mod) a -= mod;}
int main() {
#ifdef fwat
#endif
	scanf("%d%lld%lld", &n, &A, &B);
	rep(i, 1, n) scanf("%lld", &val[i]);
	sf[0] = sg[0] = f[0] = g[0] = 1;
	int La = 0, Ra = 0, Lb = 0, Rb = 0;
	rep(i, 1, n) {
		if(i ^ 1 && val[i] - val[i - 1] < A) La = i - 1;
		if(i ^ 1 && val[i] - val[i - 1] < B) Lb = i - 1;
		if(i == n) Ra = Rb = n - 1;
		while(Ra < i - 1 && val[i + 1] - val[Ra + 1] >= B) ++Ra;
		while(Rb < i - 1 && val[i + 1] - val[Rb + 1] >= A) ++Rb;
		
		if(La <= Ra)
		f[i] = (sg[Ra] - (La == 0 ? 0 : sg[La - 1]) + mod) % mod;
		sf[i] = (sf[i - 1] + f[i]) % mod;
		
		if(Lb <= Rb)
		g[i] = (sf[Rb] - (Lb == 0 ? 0 : sf[Lb - 1]) + mod) % mod;
		sg[i] = (sg[i - 1] + g[i]) % mod;
	}
	for(int i = n; i >= 0; --i) {
		add(ans, f[i]);
		if(i != n && val[i + 1] - val[i] < B) break;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 4352
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

struct UnionFind {
    vector<int> par;
    vector<int> siz;

    UnionFind(int N) : par(N), siz(N) {
        for (int i = 0; i < N; ++i) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
        siz[ry] = siz[ry] + siz[rx];
    }

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

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

    UnionFind uf(N);
    vector<set<int>> dame(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;

        // 0始まりの添字に合わせるために1減算する
        --a; --b;
        dame[a].insert(b);
        dame[b].insert(a);
        uf.unite(a, b);
    }

    for (int i = 0; i < K; ++i) {
        int c, d;
        cin >> c >> d;

        --c, --d;
        if (!uf.same(c, d)) continue;
        dame[c].insert(d);
        dame[d].insert(c);
    }

    for (int i = 0; i < N; ++i) {
        int ans = uf.size(i) - 1;
        ans -= dame[i].size();
        cout << ans << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 25472
using System;

class A{
  static void Main(){
    char[] S = Console.ReadLine().ToCharArray();
    bool N = false;
    bool So = false;
    bool W = false;
    bool E = false;
    for (int i = 0; i < S.Length; i++){
      if (S[i].ToString() == "N") N = true;
      else if (S[i].ToString() == "S") So = true;
      else if (S[i].ToString() == "W") W = true;
      else if (S[i].ToString() == "E") E = true;
    }
    if (N != So || E != W) Console.WriteLine("No");
    else Console.WriteLine("Yes");
  }
}


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

using namespace std;

using ll = long long;

class SegmentTree{
    public:
    ll size;
    vector<ll> dat;
    const ll MAXVAL = (1LL << 31) - 1; 

    SegmentTree(ll n){
        size = 1;
        while(size < n) size *= 2;

        dat = vector<ll>(2*size - 1, MAXVAL);
    }

    void update(ll k, ll a){
        k += size - 1;
        dat[k] = a;

        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    // Range Minimum Query
    // When get minimum value in [a, b), call query(a, b, 0, 0, size)
    ll query(ll a, ll b, ll k, ll l, ll r){
        if(r <= a || b <= l) return MAXVAL;
        if(a <= l && r <= b) return dat[k];
        else{
            ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
};

// DSL_2_A: 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n, q; cin >> n >> q;
    SegmentTree sg(n);
    vector<ll> ans;
    for(ll i=0;i<q;i++){
        ll com, x, y;
        cin >> com >> x >> y;
        if(com == 0){
            sg.update(x, y);
        }else{
            ans.push_back(sg.query(x, y + 1, 0, 0, sg.size));
        }
    }
    for(ll a: ans) cout << a << endl;
}


Measured memory_bytes: 5568
#include <cstdio>

using namespace std;

int calc(int a, int k) {
    while (1) {
        if (k > a) {
            return 0;
        } else {
            int x = a / k;
            int y = a % k % (x + 1);
            
            if (y == 0) return x;
            
            a = x * (k - 1) + y - 1;
        }
    }
}

int main() {
    int n, g = 0, i;
    
    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
        int a, k;
        
        scanf("%d %d", &a, &k);
        
        g ^= calc(a, k);
    }
    
    if (g > 0) {
        puts("Takahashi");
    } else {
        puts("Aoki");
    }
    
    return 0;
}


Measured memory_bytes: 128
a=input().split(" ")
L=int(a[0])
R=int(a[1])
if R-L>=672:
    print(0)
else:
    list=[]
    for p in range(0,R-L):
        for q in range(p+1,R-L+1):
            list.append(((L+p)*(L+q))%2019)
    print(min(list))

Measured memory_bytes: 6796
inp = input()
inpLi = inp.split(" ")

A1 = int(inpLi[0])
A2 = int(inpLi[1])
A3 = int(inpLi[2])

if (A1 + A2 + A3) >= 22 :
  print("bust")
else :
  print("win")

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 22;
const int INF = 1e17 + 239;

int n;

int dp[N][N];
int mem[N + 1][N + 1];

vector<int> solve(vector<int> ys, vector<int> cnts, vector<int> lims) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dp[i][j] = INF;
		}
	}
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			mem[i][j] = -1;
		}
	}
	auto go = [&](int l, int r) {
		if (mem[l + 1][r + 1] == -1) {
			int L = -INF;
			if (l >= 0) L = ys[l];
			int R = INF;
			if (r < n) R = ys[r];
			int c = 0;
			for (int i = l; i <= r; i++) {
				if (0 <= i && i < n) {
					int one = lims[i];
					one = min(one, abs(L - ys[i]));
					one = min(one, abs(R - ys[i]));
					c += one * cnts[i];
				}
			}
			mem[l + 1][r + 1] = c;
		}
		return mem[l + 1][r + 1];
	};
	for (int i = 0; i < n; i++) {
		dp[i][1] = go(-1, i);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dp[i][j] == INF) continue;
			for (int nx = i + 1; nx < n; nx++) {
				dp[nx][j + 1] = min(dp[nx][j + 1], dp[i][j] + go(i, nx)); 
			}
		}
	}
	vector<int> ans(n + 1, INF);
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			ans[j] = min(ans[j], dp[i][j] + go(i, n));
		}
	}
	ans[0] = go(-1, n);
	return ans;
}

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

	cin >> n;
	vector<int> x(n);
	vector<int> y(n);
	vector<int> cnt(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> cnt[i];
	}
	vector<int> ans(2 * n + 1, INF);
	for (int mask = 0; mask < (1 << n); mask++) {
		vector<int> lim(n);
		for (int i = 0; i < n; i++) {
			lim[i] = min(abs(x[i]), abs(y[i]));
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if ((mask >> j) & 1) {
					lim[i] = min(lim[i], abs(x[i] - x[j]));
				}
			}
		}
		vector<tuple<int, int, int>> A;
		for (int i = 0; i < n; i++) {
			A.push_back(make_tuple(y[i], cnt[i], lim[i]));
		}
		sort(A.begin(), A.end());
		vector<int> ys(n);
		vector<int> cnts(n);
		vector<int> lims(n);
		for (int i = 0; i < n; i++) {
			ys[i] = get<0>(A[i]);
			cnts[i] = get<1>(A[i]);
			lims[i] = get<2>(A[i]);
			// cerr << ys[i] << ' ' << cnts[i] << ' ' << lims[i] << endl;
		}
		auto cost = solve(ys, cnts, lims);
		// cerr << cost[0] << endl;
		// cerr << cost[1] << endl;
		// if (mask == 0) {
		// 	cerr << cost[1] << endl;
		// }
		for (int i = 0; i <= n; i++) {
			ans[i + __builtin_popcount(mask)] = min(ans[i + __builtin_popcount(mask)], cost[i]);
		}
	}
	for (int i = 0; i <= n; i++) {
		cout << ans[i] << '\n';
	}
}

Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int Mod = 1e9 + 7;

typedef vector <int> Row;
typedef vector <Row> Matrix;

void add_self(int& x,int y){
    x += y;
    if(x>=Mod)  x -= Mod;
}
int mul(int x,int y){
    return (ll) x*y % Mod;
}

Matrix Zero(int n,int m){
    return Matrix(n,Row(m,0));
}
Matrix Ident(int n){
    Matrix Res = Zero(n,n);
    for(int i=0;i<n;i++)    Res[i][i] = 1;
    return Res;
}
Matrix Multy(const Matrix& A,const Matrix& B){
    assert(A[0].size()==B.size());
    Matrix Res = Zero(A.size(),B[0].size());
    for(int i=0;i<A.size();i++)
        for(int j=0;j<B[0].size();j++)
            for(int k=0;k<A[0].size();k++)
                add_self(Res[i][j],mul(A[i][k],B[k][j]));
    return Res;
}
Matrix Power(const Matrix& A,ll k)
{
    if(!k)  return Ident(A.size());
    if(k&1) return Multy(A,Power(A,k-1));
    return Power(Multy(A,A),k/2);
}

int main()
{
    int n;
    ll k;
    cin >> n >> k;

    Matrix Graph = Zero(n,n);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&Graph[i][j]);

    Matrix Base = Zero(1,n);
    for(int i=0;i<n;i++)    Base[0][i] = 1;

    Matrix T = Power(Graph,k);

    Matrix Res = Multy(Base,T);

    int Ans = 0;
    for(int i=0;i<n;i++)    add_self(Ans,Res[0][i]);

    cout << Ans;
}


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

int main(){
    string s;
    cin >> s;
    string s1,s2;
    int cnt=0;
    if(s.size()%2 == 0){
        for(int i=0;i<s.size()/2;i++){
            s1 += s.at(i);
        }
        for(int j=s.size()/2;j<s.size();j++){
            s2 += s.at(j);
        }
        reverse(s2.begin(),s2.end());
        for(int k=0;k<s1.size();k++){
            if(s1.at(k) != s2.at(k))cnt++;
        }
    }else{
        for(int i=0;i<s.size()/2;i++){
            s1 += s.at(i);
        }
        for(int j=s.size()/2+1;j<s.size();j++){
            s2 += s.at(j);
        }
        reverse(s2.begin(),s2.end());
        for(int k=0;k<s1.size();k++){
            if(s1.at(k) != s2.at(k))cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;

int main() {
  INCANT;
  cin >> N;
  cout << 48-N << "\n";
  return 0;
}

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

int main(){
  int a,b;
  while(cin>>a && cin>>b){
    if(a==0 && b==0)break;
    if(a<b)cout<<a<<" "<<b<<endl;
    else   cout<<b<<" "<<a<<endl;
  }
  return 0;

}

Measured memory_bytes: 2984
from itertools import product


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    s = ["#" * (w + 2)] + ["#" + _s + "#" for _s in s] + ["#" * (w + 2)]
    ans = 0
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for _h, _w in product(range(1, h + 1), range(1, w + 1)):
        if s[_h][_w] == "#":
            continue
        q = list()
        for x, y in d:
            if s[_h + x][_w + y] == ".":
                q.append((_h + x, _w + y, _h, _w))
        if len(q) > 2:
            continue
        c = [[h * w] * (w + 2) for _ in range(h + 2)]
        c[_h][_w] = 0
        while q:
            cx, cy, px, py = q.pop()
            if c[px][py] + 1 >= c[cx][cy]:
                continue
            c[cx][cy] = c[px][py] + 1
            for x, y in d:
                if s[cx + x][cy + y] == ".":
                    q.append((cx + x, cy + y, cx, cy))
        for i, j in product(range(1, h + 1), range(1, w + 1)):
            ans = max(ans, c[i][j] * (s[i][j] == "."))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 3316