akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
use itertools::Itertools;
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

fn main() {
    input! {
        n: usize,
        k: usize,
        mut a: [i64;n]
    }

    for _ in 0..k {
        let mut b: Vec<i64> = vec![0; n];

        for i in 0..n {
            let l = max(0, i as i64 - a[i]) as usize;
            let r = min(n as i64 - 1, i as i64 + a[i]) as usize;
            b[l] += 1;
            if r < n - 1 {
                b[r + 1] -= 1;
            }
        }

        a = vec![0; n];
        a[0] = b[0];
        for i in 1..n {
            a[i] = a[i - 1] + b[i];
        }

        if a.iter().all(|&i| i == n as i64) {
            break;
        }
    }

    print!("{}", a[0]);
    for i in 1..n {
        print!(" {}", a[i]);
    }
}


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

int main() {
    string W, T;
    cin >> W;
    //string::size_type idx;
    int count = 0;
    while (cin >> T && T != "END_OF_TEXT") {
        for(int i = 0; i < T.size(); i++) {
            if(T[i] >= 'A' && T[i] <= 'Z')
                T[i] += 32;
        }
        //idx = T.find(W);
        //if(idx != string::npos)
        if(T == W)
            count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3124
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 04/05/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int n; cin>>n;
  vector<int> A(n); for(auto& a:A) {cin>>a;a--;}
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (A[i] < i)
      continue;
    if (A[A[i]] == i)
      ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main()
{   long long a,b,d,ans=0,i,h=0;
    scanf("%lld%lld",&a,&b);
    d=b-a;
    for(i=d;i>=0;i--){
        h+=i;
    }
    ans=h-b;
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;
vector<int> v[100010];
int main(){
	long long i,j,k,n;
	cin >> n;
	for(i=0;i<=n;i++){
		if(i*(i+1)/2==n){
			k = i;
			break;
		}
		if(i==n){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	cout << k+1 << endl;
	int x = 1;
	for(i=1;i<=k+1;i++){
		for(j=i;j<=k;j++){
			v[i].push_back(x);
			v[j+1].push_back(x);
			x++;
		}
	}
	for(i=1;i<=k+1;i++){
		cout << v[i].size() << " ";
		for(int j:v[i]){
			cout << j << " ";
		}
		cout << endl;
	}
}

Measured memory_bytes: 4608
n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
cnt = [0]*10**5
ans = sum(a)
for i in a:
    cnt[i-1] += 1

for i in range(q):
    b, c = bc[i][0], bc[i][1]
    ans += (c - b)*cnt[b-1]
    cnt[c-1] += cnt[b-1]
    cnt[b-1] = 0
    print(ans)


Measured memory_bytes: 96488
// Author : Nachiket Kanore
// Institute : PICT, Pune

/* 
   If you know what you’re worth, 
   then go out and get what you’re worth
   But you gotta be willing to take the hits, 
   and not pointing fingers saying you ain’t 
   where you wanna be because of him, or her, or anybody. 
   Cowards do that and that ain’t you. You’re better than that! 
*/

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ld long double
#define endl '\n'
#define rep(x,s,e) for(int x=s;x<=(e);x++)
#define repn for(int x=0;x<n;x++)
#define rep1n for(int x=1;x<=n;x++)
#define rep1m for(int y=1;y<=m;y++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define precise(x) cout << fixed << setprecision(x)
#define bits(x) __builtin_popcount(x)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define test int t; cin>>t; while(t--)
#define FAST                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;


void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}


template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define see(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define see(x...)
#endif

const int inf = 1e18;
const int N = 1e5+5;


int32_t main(){
    FAST;

    int h , a;  cin >> h >> a;
    int ans = 0;
    while(h > 0){
        ans++;
        h -= a;
    }   cout << ans << endl;
    
    return 0;
}




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

using namespace std;

#define int long long

typedef long long ll;

long long n;
long long a[1200][1200];

vector<int> graph[2100000];
int in_d[2100000];

int use[2100000];
int day[2100000];

int get_num(int a, int b)
{
    if (a < b)
    {
        swap(a, b);
    }
    int x = a * (n + 2) + b;
    return x;
}

int In[2100000];
int Out[2100000];
int T = 1;
int color[2100000];
int visit = 0;

void dfs(int v)
{
    color[v] = 1;
    In[v] = T++;
    for (auto u : graph[v])
    {
        if (color[u] == 0)
        {
            dfs(u);
        }
        if (color[u] == 1)
        {
            cout << -1;
            exit(0);
        }
    }
    color[v] = 2;
    visit++;
    Out[v] = T++;
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < n - 1; j++)
        {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j + 1 < n - 1; j++)
        {
            int here = get_num(i, a[i][j]);
            int nxt = get_num(i, a[i][j + 1]);
            //cout << here << " " << nxt << endl;
            graph[here].push_back(nxt);
            in_d[nxt]++;
        }
    }

    long long v = 0;
    long long all = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            int match = get_num(i, j);
            if (!use[match]) all++;
            use[match] = 1;
            v = max(v, match);
        }
    }
    for (int i = 1; i <= v; i++)
    {
        if (in_d[i] == 0 && use[i] == 1)
        {
            dfs(i);
        }
    }
    if (all != visit)
    {
        cout << -1;
        return 0;
    }
    vector<pair<int, int> > TopSort;

    for (int i = 1; i <= v; i++)
    {
        if (use[i] == 1)
        {
            TopSort.push_back({-Out[i], i});
        }
    }

    sort(TopSort.begin(), TopSort.end());

    for (int i = 1; i <= v; i++) day[i] = 1;

    for (int i =0; i < TopSort.size(); i++)
    {
        int kek = TopSort[i].second;
        for (auto u : graph[kek])
        {
            day[u] = max(day[u], day[kek] + 1);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= v; i++)
    {
        if (use[i] == 1)
        {
            ans = max(ans, day[i]);
        }
    }
    cout << ans;
}


Measured memory_bytes: 131692
// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

template<typename T1, typename T2>
ostream& operator << (ostream& os, const pair<T1, T2>& p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& v) {
    os << "{";
    for(int i = 0; i < v.size(); i++)
        os << v[i] << (i+1<v.size()?", ":"");
    os << "}";
    return os;
}

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
//}}}

int X, Y;
void dfs(int a, int b, string s) {
    if(a == X && b == Y) {
        cout << s << endl;
        return;
    }
    if(max(a, b) >= 5 && min(a, b) <= 3) return;
    if(a == 5 && b == 5) return;
    if(max(a, b) >= 6 && min(a, b) == 4) return;
    dfs(a+1, b, s+"A");
    dfs(a, b+1, s+"B");
}
int main(){
    iostream_init();
    cin >> X >> Y;
    dfs(0, 0, "");
    return 0;
}

/* vim:set foldmethod=marker: */

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    Int(n);
    vector<int> data(n+1);
    for (int i = 0; i < n+1; i++) {
        cin >> data[i];
    }

    int s = 0;
    rep(i, data.size()) {
        s += data[i];
    }

    if (n == 0) {
        if (data[0] == 1) {
            cout << 1 << endl;
        } else {
            cout << -1 << endl;
        }
        return 0;
    }

    int k = data[n];
    for (int i = n-1; i >= 0; i--) {
        k = k / 2LL + k % 2LL + data[i];
    }
    if (k != 1) {
        cout << -1 << endl;
        return 0;
    }


    int p = 1, ans = 1;
    Rep(i, n+1) {
        p = min(p * 2, s) - data[i];
        ans += p + data[i];
        s -= data[i];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3988
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <climits>

#define size_t int

using namespace std;

int main(int argc, char const *argv[]) {
  int N;
  scanf("%d", &N);
  int v[N];
  int nn1[100001];
  int nn2[100001];
  for (size_t i = 1; i < 100001; i++) {
    nn1[i] = 0;
    nn2[i] = 0;
  }
  for (size_t i = 0; i < N; i++) {
    scanf("%d", &v[i]);
    if (!(i%2)) {
      nn1[v[i]]++;
    } else {
      nn2[v[i]]++;
    }
  }
  vector<pair<int, int> > pairs1;
  vector<pair<int, int> > pairs2;

  for (size_t i = 1; i < 100001; i++) {
    if (nn1[i] != 0) {
      pairs1.push_back(make_pair(nn1[i], i));
    }
    if (nn2[i] != 0) {
      pairs2.push_back(make_pair(nn2[i], i));
    }
  }
  sort(pairs1.begin(), pairs1.end());
  sort(pairs2.begin(), pairs2.end());
  // printf("%d", pairs2[0].first);
  // printf("%d" , pairs2.size());
  if (pairs1[pairs1.size()-1].second != pairs2[pairs2.size()-1].second) {
    // printf("aaa");
    printf("%d\n", N - pairs1[pairs1.size()-1].first - pairs2[pairs2.size()-1].first);
  } else {
    int r1 = pairs1.size() >= 2 ? N - pairs1[pairs1.size()-2].first - pairs2[pairs2.size()-1].first : INT_MAX;
    int r2 = pairs2.size() >= 2 ? N - pairs1[pairs1.size()-1].first - pairs2[pairs2.size()-2].first : INT_MAX;
    // printf("%d %d\n",r1,r2);
    if (r1 == INT_MAX && r2 == INT_MAX) {
      printf("%d\n", N / 2);
      return 0;
    }
    printf("%d\n", r1 > r2 ? r2 : r1);
  }
  return 0;
}


Measured memory_bytes: 2428
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n+2];
	a[0]=0;
	a[n+1]=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	int sum=0;
	int s=1;
	for(int i=2;i<=n+1;i++){
		if(a[i]==a[i-1]){
			s++;
		}
		else{
			if(s==a[i-1]){
				s=0;
			}
			else{
				if(a[i-1]<s){
					sum+=s-a[i-1];
				}
				else{
					sum+=s;
				}
			}
			s=1;
		}
	}
	cout<<sum;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>  // clang-format off
using namespace std;
using Int = long long;
#define REP2(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REP3(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define OVERLOAD2(_1, _2, _3, name, ...) name
#define REP(...) OVERLOAD2(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Feb 16 21:00:33 JST 2020
 **/

signed main() {
    Int n;
    cin >> n;
    REP(i, n) {
        Int x;
        cin >> x;
        if (x % 2 == 0 && x % 3 && x % 5) {
            cout << "DENIED" << endl;
            return 0;
        }
    }
    cout << "APPROVED" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define fort(i,n) for (int i = 1; i <= n; ++i)
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz size()
#define er erase
#define fr first
#define sc second
#define rc(x) return cout << x, 0
using namespace std;

int a,cnt=1;

int32_t main()
{
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> a;
    if (a==1||a==2||a==4) rc(4);
    while (1)
    {
        ++cnt;
        if (a%2==0) a/=2;
        else a=3*a+1;
        if (a==4||a==2||a==1) rc(cnt+3);
    }
}


Measured memory_bytes: 256
//
//  main.cpp
//  HelloWorld
//
//  Created by purple on 2020/04/13.
//  Copyright © 2020 Purple. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {


    int m,f,r;
    int sum=0;
    
    while(1){
        
        cin >> m >> f >> r;
        
        sum = m+f;
  
        if((m==-1)&&(f==-1)&&(r==-1))
              break;
        
        if((m==-1)||(f==-1))
            cout << "F" << endl;
        else if(sum>=80)
            cout << "A" << endl;
        else if((sum>=65)&&(sum<80))
            cout << "B" << endl;
        else if((sum>=50)&&(sum<65))
            cout << "C" << endl;
        else if((sum>=30)&&(sum<50)){
            if(r>=50)
                cout << "C" << endl;
            else
                cout << "D" << endl;
        }
        else
            cout << "F" << endl;


        
        /*
         中間試験、期末試験のいずれかを欠席した場合成績は F。
         中間試験と期末試験の合計点数が 80 以上ならば成績は A 。
         中間試験と期末試験の合計点数が 65 以上 80 未満ならば成績は B。
         中間試験と期末試験の合計点数が 50 以上 65 未満ならば成績は C。
         中間試験と期末試験の合計点数が 30 以上 50 未満ならば成績は D。 ただし、再試験の点数が 50 以上ならば成績は C。
         中間試験と期末試験の合計点数が 30 未満ならば成績は F。
         */
         
        
        
  
    }
    
    return 0;
    
}



Measured memory_bytes: 3084
using System;
using System.Linq;
using System.Threading.Tasks;
using static System.Console;
using static System.Math;
class program{
  static void Main(string[] args){
    program p = new program();
    p.Run();
  }
  void Run(){
	ulong N = ulong.Parse(ReadLine());
    ulong res = N*(N-1)/2;
    WriteLine(res.ToString());
  }

}

Measured memory_bytes: 11092
fun main(args:Array<String>) {
	val n = readLine()!!.toInt()
	val a = "0 ${readLine()!!} 0".split(" ").map{ it.toLong() }
	val move = LongArray(n+1){ i-> Math.abs(a[i]-a[i+1]) }
	val len=move.sum()
	
	(1..n).fold(StringBuilder()){ sb,i->
		val ans=len -move[i-1]-move[i] +Math.abs(a[i-1]-a[i+1])
		sb.append(ans).append("\n")
	}.let { println(it) }
}

Measured memory_bytes: 59888
'use strict';

function main(stdin) {
  const input = stdin.split(' ').map(v => parseInt(v, 10));
  const N = input[0];
  const K = input[1];

  const probs = [];

  for (let i = 0, p = 1; i < 20; ++i) {
    probs[i] = p;
    p /= 2;
  }

  let ans = 0;

  for (let n = 1; n <= N; ++n) {
    let i = 0;

    for (let k = n; k < K; k *= 2) {
      ++i
    }

    ans += probs[i];
  }

  ans = ans / N;
  
  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 21064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();

        System.out.println(proc(x));
    }

    public static String proc(int x) {
        int mod = x % 100;
        int c = x / 100;

        return Math.ceil(mod / 5d) <= c
            ? "1"
            : "0";
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);
 
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;
 
constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433;
 
template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
	string S; cin >> S;
	int N = S.size();
	corner(N&1,"No");
	for(int i = 0; i < N; ++i){
		corner(i%2==0 && S[i]!='h',"No");
		corner(i%2==1 && S[i]!='i',"No");
	}	
	cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        xs.append((x, i))
        ys.append((y, i))
    xs = sorted(xs)
    ys = sorted(ys)

    # 使う可能性のある辺のみを取り出す
    edges = []
    for i in range(1, N):
        edges.append((xs[i][0] - xs[i-1][0], xs[i-1][1], xs[i][1]))
        edges.append((ys[i][0] - ys[i-1][0], ys[i-1][1], ys[i][1]))
    edges = sorted(edges)

    # クラスカル法
    ans = 0
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)

if __name__ == "__main__":
    main()

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const ll inf = 1e18;




ll n, c;
ll h[maxn];
ll dp[maxn];


struct line {
    ll m, b;
    line(ll m, ll b) : m(m), b(b) {}
    ll eval(ll x) {
	return m*x + b;
    }
};

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

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

    vector<line> lines;


    auto rid = [&](line last, line last2, line cur) {
	// last2 and cur intersect after last and cur, so last is useless
	ll num2 = last2.b-cur.b;
	ll den2 = cur.m-last2.m;
	ll num = last.b-cur.b;
	ll den = cur.m-last.m;

	if (num2*den > num*den2) {
	    return true;
	}

	return false;
    };

    auto add_line = [&](ll m, ll b) {
	line cur = {m, b};
	while ((int)lines.size() >= 2 && rid(lines.end()[-1], lines.end()[-2], cur)) {
	    lines.pop_back();
	}
	lines.push_back(cur);
    };


    auto qry_hull = [&](ll x) {
	if (lines.empty()) {
	    return inf;
	}
	int len = lines.size();
	int lo = -1;
	int hi = len-1;

	while (hi-lo>1) {
	    int mid = (hi+lo)/2;
	    assert(mid+1<len);
	    if (lines[mid].eval(x) <= lines[mid+1].eval(x)) {
		hi = mid;
	    } else {
		lo = mid;
	    }
	}

	return lines[hi].eval(x);
    };

    for (int i=0; i<n; i++) {
	if (i>0) {
	    dp[i] = h[i]*h[i] + c + qry_hull(h[i]);
	}
	add_line(-2LL*h[i], dp[i]+h[i]*h[i]);
    }

    

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


Measured memory_bytes: 10380
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define ALL(v) v.begin(),v.end()
#define mp make_pair
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}}
template <class X> void prrr(X test){int f=0;for(auto it:test){cout<<(f++!=0?" ":"")<<it;}cout<<endl;}
template<typename X>
istream&operator>>(istream&i,vector<X>&v){for(X&x:v)i>>x;return i;}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(l, r); // 0 <= l, r <= n-1
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

// return sorted 約数list 1 <= x <= n
vector<ll> divv(ll n) {
  vector<ll> v;
  for(ll i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.push_back(i);
      if(i*i != n) v.push_back(n/i);
    }
  }
  sort(ALL(v));
  return v;
}


int main() {
    ll n;
    cin>>n;
    vector<ll> v(n);
    cin>>v;
    ll sum = 0;
    map<ll,ll> m;
    for(auto it:v){
        m[it]+=1;
    }
    for(auto it = m.rbegin();it!=m.rend();){
        if ((*it).second ==0) {
            it++;
            continue;
        }
        auto val = (*it).first;
        m[val]--;
        ll b = 1;
        while(b<=val) b*=2;
        auto x = b -val;
        if(m.count(x) > 0 && m[x] > 0){
            sum++;
            m[x]--;
        }
    }
    pr(sum);
}

Measured memory_bytes: 14336
n,y = map(int, input().split())
a = -1
b = -1
c = -1
for i in range(n+1):
    for j in range(n+1-i):
        k = n-i-j
        sum = 10000*i + 5000*j + 1000*k
        if sum == y:
            a = i
            b = j
            c = k
                
print(a,b,c)

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

int main(){
	int n,v;
	map<int,int> mp;
	while(1){
		vector<int>  b ;
		cin >> n ;
		if(n==0){
			return 0;
		}
		for(int i=0;i<n;i++){
			cin >> v;
			b.push_back(v);
		}
		for(int j=0;;j++){
			vector<int>  a ;
			for(int i=0;i<=12;i++){
				mp[i]=0;
			}
			for(int i=0;i<n;i++){
			mp[b[i]] ++;
		}
			for(int i=0;i<n;i++){
				a.push_back(mp[b[i]]);
			}
			if(a == b){
				cout << j << "\n";
				cout << a[0] ;
				for(int i=1;i<n;i++){
					cout << " " << a[i] ;
				}
				cout << "\n";
				break;
			}
			else{
				b = a;
			}
		}
	}
}

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

using namespace std;

double th = M_PI * 60.0 / 180.0;

struct point {
    double x;
    double y;
};

void koch_calculation(point a, point b, point *s, point *t, point *u) {
    s->x = 1.0 / 3.0 * b.x + 2.0 / 3.0 * a.x;
    s->y = 1.0 / 3.0 * b.y + 2.0 / 3.0 * a.y;
    t->x = 2.0 / 3.0 * b.x + 1.0 / 3.0 * a.x;
    t->y = 2.0 / 3.0 * b.y + 1.0 / 3.0 * a.y;

    u->x = cos(th) * (t->x - s->x) - sin(th) * (t->y - s->y) + s->x;
    u->y = sin(th) * (t->x - s->x) + cos(th) * (t->y - s->y) + s->y;
}

void koch(int d, point p1, point p2) {
    if (d == 0) return;
    point *s, *t, *u;
    s = (struct point *)malloc(sizeof(struct point));
    t = (struct point *)malloc(sizeof(struct point));
    u = (struct point *)malloc(sizeof(struct point));
    koch_calculation(p1, p2, s, t, u);
    
    koch(d-1, p1, *s);
    printf("%.8f %.8f\n", s->x, s->y);
    koch(d-1, *s, *u);
    printf("%.8f %.8f\n", u->x, u->y);
    koch(d-1, *u, *t);
    printf("%.8f %.8f\n", t->x, t->y);
    koch(d-1, *t, p2);
}

int main(void) {
    int n;
    cin >> n;
    
    point a, b;

    a.x = 0.0;
    a.y = 0.0;
    b.x = 100.0;
    b.y = 0.0;

    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);

    return 0;
}


Measured memory_bytes: 3480
#include<bits/stdc++.h>
#define f first
#define s second
#define mk make_pair
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector<pair<int , int> >student;
        for(int i = 1; i <=n; i++){
            int tmp;
            cin >> tmp;
            student.emplace_back(mk(tmp,i) );
        }
        sort(student.begin(),student.end());
        
        for(auto x : student){
            cout << x.s << " ";
        }
        cout << '\n';
        
    }
}    

Measured memory_bytes: 1780
S = input()

ans = 0
cnt = 0
flg = 0
for i in range(len(S)-1) :
    if S[i] == "A" :
        cnt += 1
    elif S[i]+S[i+1] == "BC" :
        flg = 1
        ans += cnt
    elif flg :
        flg = 0
    else :
        cnt = 0
print(ans)


Measured memory_bytes: 3500
import std.stdio, std.conv, std.string, std.bigint;

void main() {
	int input = to!int(chomp(readln()));
	writeln(lucas(input));
}

BigInt lucas(int n) {
	if(n == 0) return BigInt(2);
	if(n == 1) return BigInt(1);
	
	BigInt a = 2, b = 1, c = 3;
	for(int i = 2; i <= n; i++) {
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}


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

using namespace std;
using ll = long long;

template <typename T> T gcd(T a, T b) {
  if (a < b) return gcd(b, a);
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll A, B;
  cin >> A >> B;
  ll gcdn = gcd(A, B);
  ll gcdc = gcdn;
  ll res = 1;
  for (ll i = 2; i * i <= gcdn; i++) {
    if (gcdc % i != 0) continue;
    res++;
    while (gcdc % i == 0) {
      gcdc /= i;
    }
  }
  if (gcdc > 1) {
    res++;
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static void solve() {
		String[] s = in.next().split(",");
		int[] a = new int[5];
		for (int i=0; i<5; i++) {
			a[i] = Integer.parseInt(s[i]);
		}

		Arrays.sort(a);
		if ((a[0] == a[1] && a[1] == a[2] && a[2] == a[3]) || (a[1] == a[2] && a[2] == a[3] && a[3] == a[4])) {
			out.println("four card");
		} else if ((a[0] == a[1] && a[1] == a[2] && a[3] == a[4]) || (a[0] == a[1] && a[2] == a[3] && a[3] == a[4])) {
			out.println("full house");
		} else if ((a[0] + 1 == a[1] && a[1] + 1 == a[2] && a[2] + 1 == a[3] && a[3] + 1 == a[4]) || (a[0] == 1 && a[1] == 10 && a[2] == 11 && a[3] == 12 && a[4] == 13)) {
			out.println("straight");
		} else if ((a[0] == a[1] && a[1] == a[2]) || (a[2] == a[3] && a[3] == a[4]) || (a[1] == a[2] && a[2] == a[3])) {
			out.println("three card");
		} else if ((a[0] == a[1] && a[2] == a[3]) || (a[0] == a[1] && a[3] == a[4]) || (a[1] == a[2] && a[3] == a[4])) {
			out.println("two pair");
		} else if (a[0] == a[1] || a[1] == a[2] || a[2] == a[3] || a[3] == a[4]) {
			out.println("one pair");
		} else {
			out.println("null");
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		while(in.hasNext()) solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26204
/*
* @Author: _dp95
* @Date:   2020-04-03 06:02:01
*/
#include "bits/stdc++.h"
using namespace std ;

#define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll ;
typedef long double ldb ;

#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'

#define all( x ) x.begin(),x.end() 
#define sz( x ) ( int )( x ).size( )
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

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

const int MAX = 2*1000*1000 + 10 ;
const ll INF = 1e18 ;
const int MOD = 1e9 + 7 ;

signed main( ){
  timesaver ;
  ll k, n ;
  cin >> k >> n ;
  vector< ll > v(n), l(n), r(n) ;
  for( ll &i : v )
    cin >> i ;
  l[0] = 0 ;
  r[n-1] = 0 ;
  for( int i = 1 ; i < n ; i++ )
    l[i] = l[i-1] + v[i] - v[i-1] ;
  for( int i = n-2 ; i >= 0 ; i-- )
    r[i] = r[i+1] + v[i+1] - v[i] ;
  // for( ll i : l )
  //   cout << i << " " ;
  // cout << nl ; 
  // for( ll i : r )
  //   cout << i << " " ;
  // cout << nl ;
  ll ans = min( l[n-1], r[0] ) ;
  for( int i = 1 ; i < n-1 ; i++ ){
    ans = min( ans, l[i] + r[i+1] + (v[0]+k-v[n-1]));
  }
  cout << ans << nl ;
}

Measured memory_bytes: 4992
import sys
import math

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
   
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N=int(input())
cnt=0
li=[]

for _ in range(N):
	li.append(int(input()))
	
so=sorted(li)
ct=1

for i in range(N-1):
	if so[i]==so[i+1]:
		ct+=1
	else:
		cnt+=ct%2
		ct=1
		
cnt+=ct%2



if N==1:
	print(1)
else:	
	print(cnt)
			


Measured memory_bytes: 8280
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, K = map(int, input().split())
    Norg = N

    if N == K:
        print(0)
        exit()

    if N > K:
        N = N % K

    if N == 0:
        print(0)
        exit()
    else:
        if N <= K // 2:
            print(N)
        else:
            print(abs(N - K))

    # print(Norg, K)
    # print(N, K)



if __name__ == '__main__':
    main()

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

int main()
{
  int a, b, ans = -1;
  cin >> a >> b;

  for (int i = 1; i < 1010; i++)
  {
    if (floor(i * 0.08) == a and floor(i * 0.10) == b)
    {
      ans = i;
      break;
    }
  }
  cout << ans << "\n";
}

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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a)-1;i>=(b);i++)
#define RREP(i, n) FOR(i, n, 0);

signed main () {
  cin.tie(0);
  cout << setprecision(10);

  int h, w; cin >> h >> w;
  int a[501][501];
  FOR(i, 1, h+1) {
    FOR(j, 1, w+1) {
      cin >> a[i][j];
    }
  }
  vector<vector<int>> ans;

  FOR(i, 1, h+1) {
    FOR(j, 1, w) {
      if(a[i][j]%2 == 1) {
        ans.pb({i, j, i, j+1});
        a[i][j]--;
        a[i][j+1]++;
      }
    }
  }

  FOR(i, 1, h) {
    if(a[i][w]%2 == 1) {
      ans.pb({i, w, i+1, w});
      a[i][w]--;
      a[i+1][w]++;
    }
  }

  cout << ans.size() << endl;
  REP(i, ans.size()) {
    cout << ans[i][0] << " "
         << ans[i][1] << " "
         << ans[i][2] << " "
         << ans[i][3] << endl;
  }
  
}


Measured memory_bytes: 12976
while True :
    H, W = map(int, input().split())
    if H == W == 0 :
        break
    for i in range(H) :
        row = ""
        if i % 2 == 0 :
            for j in range(W) :
                if j % 2 == 0 :
                    row += "#"
                else :
                    row += "."
        else :
            for j in range(W) :
                if j % 2 == 0 :
                    row += "."
                else :
                    row += "#"
        print(row)
    print("")


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

void Insert(vector<int>& vecIn, int nCount)
{
	for (int i = 1; i < nCount; i++)
	{
		int nTemp = vecIn[i];
		int j = i - 1;
		for (; j >= 0 && vecIn[j] > nTemp; --j)
		{
			vecIn[j + 1] = vecIn[j];
		}
		vecIn[j + 1] = nTemp;
		for (int i = 0; i < vecIn.size(); i++)
		{
			cout << vecIn[i];
			if (i != vecIn.size()-1)
			{
				cout << " ";
			}
		}
		cout << endl;
	}

}


int main()
{
	int nCount;
	cin >> nCount;
	vector<int> vecIn;
	for (int i = 0; i < nCount; i++)
	{
		int nTemp = 0;
		cin >> nTemp;
		vecIn.push_back(nTemp);
	}
	for (int i = 0; i < vecIn.size(); i++)
	{
		cout << vecIn[i];
		if (i != vecIn.size()-1)
		{
			cout << " ";
		}
	}
	cout << endl;
	Insert(vecIn, nCount);
	//system("pause");
	return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define int long long
int findLowerBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{

    auto low = lower_bound(arr.begin(),
                           arr.end(), p);

    return low - arr.begin();
}
int findUpperBound(
    vector<pair<int, int>> &arr,
    pair<int, int> &p)
{
    auto up = upper_bound(arr.begin(),
                          arr.end(), p);

    return up - arr.begin();
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int r, g, b;
    cin >> r >> g >> b;
    int p = r * 10 * 10 + g * 10 + b;
    if (p % 4 == 0)
        cout << "YES"
             << "\n";
    else
    {
        cout << "NO"
             << "\n";
    }

    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
 long long int d=5*10e15;
int main()
{

 long long  int a,b,i,l,k=1;;
string s;
  cin>>s;
  cin>>b;
i=0;
while(b>0)
{
    l=s[i]-'0';
    k=1*pow(l,d);

    b-=k;
i++;
}
cout<<l<<endl;


}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	if (a%b==0) return b;
	gcd(b,a%b);
} 
int main(){
	char a,b;
	cin >> a >> b;
	if (a<b) cout << "<\n";
	else if (a==b) cout << "=\n";
	else cout << ">\n";
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int x[10000],y[10000],i=1,j,sp;
	scanf("%d %d",&x[0],&y[0]);
	while(x[i-1]!=0||y[i-1]!=0){
		scanf("%d %d",&x[i],&y[i]);
		if(x[i]>y[i]){
			sp=x[i];
			x[i]=y[i];
			y[i]=sp;
		}
		i++;
	}
	
	if(x[i-1]==0&&y[i-1]==0){	
		for(j=0;j<i-1;j++){
		printf("%d %d\n",x[j],y[j]);
		}
	}
return 0;
}

Measured memory_bytes: 620
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	LL l, r; cin >> l >> r;

	if (r - l > 1e4) {
		cout << 0 << endl;
		return 0;
	}

	LL ans = 2019;
	for (int i = l; i < r; i++) {
		for (int j = l+1; j < r+1; j++) {
			LL tmp = (LL)i*(LL)j;
			tmp %= 2019;

			ans = min(ans, tmp);
		}
	}

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

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

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

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}

int64 h, w;

int64 to_idx(int64 y, int64 x) {
  return y*w+x;
}

PLL to_pos(int64 idx) {
  return PLL(idx/h, idx%h);
}

int64 th = 0;
int main(void) {
  while ( cin >> w >> h && w + h) {
    auto G = make_v<PLL>(h*w, 0);
    REP(i, 2*h-1) {
      if (i % 2 == 0) {
        REP(j, w-1) {
          cin >> th;
          if (!th) {
            G[to_idx((i/2), j)].emplace_back(1, to_idx((i/2), j+1));
            G[to_idx((i/2), j+1)].emplace_back(1, to_idx((i/2), j));
          }
        }
      } else {
        REP(j, w) {
          cin >> th;
          if (!th) {
            G[to_idx(i/2, j)].emplace_back(1, to_idx(i/2+1, j));
            G[to_idx(i/2+1, j)].emplace_back(1, to_idx(i/2, j));
          }
        }
      }
    }
    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
    pq.emplace(0, 0);
    vector<int64> d(h*w, INF_LL);
    d[0] = 0;
    while (pq.size()) {
      int64 v, c;
      tie(c, v) = pq.top(); pq.pop();
      if (d[v] < c) continue;
      REP(i, G[v].size()) {
        int64 u, cc;
        tie(cc, u) = G[v][i];
        if (d[v] + cc < d[u]) {
          d[u] = d[v] + cc;
          pq.emplace(d[u], u);
        }
      }
    }
    if (d[to_idx(h-1, w-1)] == INF_LL) {
      cout << 0 << endl;
    } else {
      cout << d[to_idx(h-1, w-1)]+1 << endl;
    }
  }
}


Measured memory_bytes: 3168
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7


def main():
    S = input()
    T = input()
    if T[:-1] == S:
        print("Yes")
        return
    print("No")


if __name__ == "__main__":
    main()


Measured memory_bytes: 9040
#include <bits/stdc++.h>
using namespace std;
const int maxn = 111;
int a[maxn];
int main()
{
  int n;
  scanf("%d",&n);
  int sum = 0;
  for(int i = 0 ; i < n ; i++)
  {
    scanf("%d",&a[i]);
    sum += a[i];
  }
  int ans = 100000;
  for(int i = 1 ; i < n ; i++)
  {
    int t1 = 0 , t2 = 0;
    for(int j = 0 ; j <= i ; j++)
    {
      t1 += a[j];
    }
    t2 = sum - t1;
    ans = min(ans,abs(t2-t1));
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
LL imos[128][128][128];
int main(void)
{
  LL n,k;
  cin >> n >> k;
  map<LL,int> compmap[3];
  vector<LL> comp[3];
  vector<LL> habitat[6];
  REP(j,6) habitat[j].resize(n);
  REP(i,n) REP(j,6) cin >> habitat[j][i];
  REP(i,n) REP(j,6) comp[j%3].push_back(habitat[j][i]);
  REP(j,3) SORT(comp[j]);
  REP(j,3) REP(i,comp[j].size()) compmap[j][comp[j][i]]=i;
  REP(x,128) REP(y,128) REP(z,128) imos[x][y][z]=0LL;
  REP(i,n){
    REP(state,8){
      int a,b,c;
      a=(state&1);
      b=((state&2)>>1);
      c=((state&4)>>2);
      imos[compmap[0][habitat[0+a*3][i]]][compmap[1][habitat[1+b*3][i]]][compmap[2][habitat[2+c*3][i]]]+=((a^b^c)?-1:1);
    }
  }
  REP(x,127) REP(y,127) REP(z,127) imos[x+1][y][z]+=imos[x][y][z];
  REP(x,127) REP(y,127) REP(z,127) imos[x][y+1][z]+=imos[x][y][z];
  REP(x,127) REP(y,127) REP(z,127) imos[x][y][z+1]+=imos[x][y][z];
  LL answer=0LL;
  REP(x,127) REP(y,127) REP(z,127) if(imos[x][y][z]>=k) answer+=(comp[0][x+1]-comp[0][x])*(comp[1][y+1]-comp[1][y])*(comp[2][z+1]-comp[2][z]);
  cout << answer << endl;
  return 0;
}

Measured memory_bytes: 17624
#include<iostream>

using namespace std;

int main(){
    int x, y;

    cin >> x >> y;

    bool flag;

    if(x==2 || x==12){
        flag = false;
    }else{
        flag = true;
    }

    if(flag){
        if(x==1 || x==3 || x==5 || x==7 || x==8 || x==10 || x==12){
            if(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12){
                flag = true;
            }else{
                flag = false;
            }
        }else{
            if(y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12){
                flag = false;
            }else if(y==2){
                flag = false;
            }else{
                flag = true;
            }
        }
    }

    if(flag){
        cout << "Yes";
    }else{
        cout << "No";
    }
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

	// 頂点の訪問状態、WHITE:未訪問、GLAY:訪問中、BLACK:訪問済
	public static final int WHITE = 0;
	public static final int GLAY = 1;
	public static final int BLACK = 2;

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		int[][] ab = new int[M][2];

		Map<Integer, List<Integer>> graph = new HashMap<>();

		for(int i=0;i<M;i++) {
			ab[i][0] = sc.nextInt();
			ab[i][1] = sc.nextInt();

			if(graph.containsKey(ab[i][0])) {
				List<Integer> l = graph.get(ab[i][0]);
				l.add(ab[i][1]);
				graph.put(ab[i][0], l);
			}else {
				List<Integer> l = new ArrayList<>();
				l.add(ab[i][1]);
				graph.put(ab[i][0], l);
			}

			if(graph.containsKey(ab[i][1])) {
				List<Integer> l = graph.get(ab[i][1]);
				l.add(ab[i][0]);
				graph.put(ab[i][1], l);
			}else {
				List<Integer> l = new ArrayList<>();
				l.add(ab[i][0]);
				graph.put(ab[i][1], l);
			}
		}
		int ans=0;
		for(int i=0;i<M;i++) {
			int a = ab[i][0];
			int b = ab[i][1];

			List<Integer> l = graph.get(a);
			l.remove(Integer.valueOf(b));
			graph.put(a, l);

			l = graph.get(b);
			l.remove(Integer.valueOf(a));
			graph.put(b, l);

			l = depth_stack(ab[0][0],N+1,graph);
			if(l.size() != N) {
				ans++;
			}

			l = graph.get(a);
			l.add(b);
			graph.put(a, l);

			l = graph.get(b);
			l.add(a);
			graph.put(b, l);

		}
		System.out.println(ans);
	}

	public static List<Integer> depth_stack(int first,int N,Map<Integer, List<Integer>> graph) {

		//訪問済みの頂点のリスト
		List<Integer> reached = new ArrayList<>();

		// 頂点が訪問済みかを記録する配列。0:未訪問、1:訪問中、2:訪問済
		int[] color = new int[N];
		// 時間
		int time = 0;
		// 最初に訪問した時間/訪問終了の時間 の配列
		int[][] df = new int[N][2];

		// 探索用スタック
		List<Integer> stack = new ArrayList<>();
		// 始点firstをスタックに追加
		stack.add(first);
		color[first] = GLAY;
		df[first][0] = ++time;;
		reached.add(first);

		while (!stack.isEmpty()) {
			// スタックの一番上の点
			int top_v = stack.get(stack.size() - 1);
			if(!reached.contains(top_v)) reached.add(top_v);

			// スタックの一番上の点 に隣接する点のリスト
			List<Integer> vlist = graph.get(top_v);
			// 隣接する点のリストから最初の訪問済ではない点を取得、全て訪問済みなら -1 とする
			int i = 0;
			while (i < vlist.size() && (color[vlist.get(i)] == BLACK || color[vlist.get(i)] == GLAY))
				i++;
			int next_v = (i < vlist.size()) ? vlist.get(i) : -1;
//			System.out.println(top_v + "," + next_v);
			if (next_v != -1) {
				// 隣接点がある
				if (color[next_v] == WHITE) {
					color[next_v] = GLAY;
					df[next_v][0] = ++time;
					stack.add(next_v);
				}
			} else {
				// 隣接点がない
				stack.remove(stack.size() - 1);
				color[top_v] = BLACK;
				df[top_v][1] = ++time;
			}
		}
		return reached;
	}

}


Measured memory_bytes: 23764
from functools import lru_cache
@lru_cache(None)
def solve(n,k) :
    if n <= 9 and k == 1 :
        return n
    elif n <= 9 and k >= 2 :
        return 0
    elif k == 0:
        return 1
    else :
        m = n //10
        r = n % 10
        return  r * solve(m,k-1) + (9 - r) * solve(m-1,k-1) + solve(m,k)

n = int(input())
k = int(input())
print(solve(n,k))


Measured memory_bytes: 3812