akhauriyash/Code-Regression huggingface dataset:
/*  ex5_3
    ruuu0048 */
#include <stdio.h>

int main(void){

    int height,wide; //高さと横幅の変数を宣言

    scanf("%d %d",&height,&wide); //高さと変数を宣言

    char table[height][wide]; //マス目の配列を宣言


    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j <wide; j++)
        {
            scanf(" %c",&table[i][j]); //白黒を入力
        }   
    }

    
    for (int i = 0; i < height; i++)
    {
        int count = 0; //数える変数を宣言
        for (int j = 0; j <wide; j++)
        {
            if(table[i][j] == '#'){ //黒があったら
                count ++; //カウントする
            }
        }
        if (count == 0){ //i行目に一つも黒がなかったら
            for(int j = 0; j <wide; j++)
            {
                table[i][j] ='!'; //i行目をすべて'!'にする
            }
        }
    }

    for (int j= 0; j < wide; j++) //iとjを入れ替えて同じことをする
    {
        int count = 0;
        for (int i = 0; i <height; i++)
        {
            if(table[i][j] == '#'){
                count ++;
            }
        }
        if (count == 0){ //j列目に一つも黒がなかったら
            for(int i = 0; i <height; i++)
            {
                table[i][j] ='!'; //i行目をすべて'!'にする
            }
        }
    }


    for (int i = 0; i < height; i++)
    {
        int count = 0; //数える変数を宣言
        for (int j = 0; j <wide; j++)
        {
            if(table[i][j] != '!'){ //!じゃなかったら
                printf("%c",table[i][j]); //出力
                count ++; //数える
            }
        }
        if(count > 0){ //一回でも出力してたら
            printf("\n"); //改行を出力
        }
    }
    

    return 0; 
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
const int NMAX = 100000;
int main(){
    int N;
    vector<int> a;
    vector<int> passed;
    int button = 0;
    cin >> N;
    for (int i =0; i <N; ++i) {
        int input;
        cin >> input;
        a.push_back(input);
    }
    
    int on_now = 1;
    passed.push_back(on_now);
    for (int i =0; i <N; ++i) { //pressing i-th button
        on_now = a[on_now-1];
        
        passed.push_back(on_now);
        button += 1;
        if (on_now == 2) {
            cout << button << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {
    static final double TSUBO = 3.305785;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");
        double res = (double) Integer.parseInt(input[0]) * (double) Integer.parseInt(input[1]) / TSUBO;
        System.out.println(Math.ceil(res * 1000000) / 1000000);
    }
}

Measured memory_bytes: 26288
N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [float('inf')]*N
dp[0] = 0
for i in range(N):
    for j in range(max(0, i - K), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i]-h[j]))
print(dp[-1])

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

typedef long long int lli;

const int N = 5005;
const int logN = 13;
const int M = 205;
int n, m;

lli a[N];
lli b[N][M];
lli dp[N][N];
lli sparseT[N][logN];

void buildSparseT() {
	//Set the values in sparseT[*][0] beforehand
	for(int j = 1; j < logN; j++) {
		for(int i = 0; i + (1 << j) <= N; i++) {
			sparseT[i][j] = max(sparseT[i][j-1], sparseT[i + (1 << (j-1))][j-1]);
		}
	}
}

lli getMax(int l, int r) { //[l, r)
	if(l == r-1) return sparseT[l][0];
	else {
		int powe = (int)(log2(r-l)+0.00001);
		return max(sparseT[l][powe], sparseT[r-(1 << powe)][powe]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	
	cin >> n >> m;
	a[0]=0;
	for(int i = 1; i < n; i++) cin >> a[i];
	for(int i = 1; i < n; i++) a[i] += a[i-1];
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
		cin >> b[i][j];
	}

	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
		dp[i][j] = 0;
	}
	
	for(int mi = 0; mi < m; mi++) {
		int val = -1;
		for(int i = 0; i < n; i++) {
			sparseT[i][0] = b[i][mi];
		}
		buildSparseT();
		for(int i = 0; i < n; i++) {
			int leftHigh, rightHigh;
			int low = 0;
			int high = i-1;
			//Get Left High (number first left of b[i][-] that is >= to it).
			if(i == 0 || getMax(0, i) < b[i][mi]) {
				leftHigh = -1;
			} else {
				while(high - low > 1) {
					int mid = (low+high)/2;
					int val = getMax(mid, i);
					
					if(val >= b[i][mi]) {
						low = mid;
					} else {
						high = mid;
					}
				}
				if(getMax(high, i) >= b[i][mi]) leftHigh = high;
				else leftHigh = low;
			}
			
			
			//Get Right High (number first right of b[i][-] that is > than it).
			low = i+1;
			high = n-1;
			if(i == n-1 || getMax(i+1, n) <= b[i][mi]) {
				rightHigh = n;
			} else { 
				while(high - low > 1) {
					int mid = (low+high)/2;
					int val = getMax(i+1, mid+1); //+1 to include the upper bound
					if(val > b[i][mi]) {
						high = mid;
					} else {
						low = mid;
					}
				}
				if(getMax(i+1, low+1) > b[i][mi]) rightHigh = low;
				else rightHigh = high;
			}
			
			//Apologies for the confusing i/j index inconsistencies
			dp[i][i] += b[i][mi];
			if(leftHigh != -1) dp[leftHigh][i] -= b[i][mi];
			if(rightHigh != n) dp[i][rightHigh] -= b[i][mi];
			if(leftHigh != -1 && rightHigh != n) dp[leftHigh][rightHigh] += b[i][mi];
		}
	}
		
	for(int i = n-1; i >= 0; i--) {
		for(int j = 0; j < n; j++) {
			if(i == n-1) dp[i][j] = dp[i][j] + dp[i][j-1];
			else if(j == 0) dp[i][j] = dp[i][j] + dp[i+1][j];
			else dp[i][j] = dp[i][j] + dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
		}
	}
	for(int i = 0; i < n; i++) for(int j = i; j < n; j++) dp[i][j] -= (a[j]-a[i]);
	
	lli ans = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			ans = max(ans, dp[i][j]);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

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

typedef long long ll;
typedef pair<int,int> P;
const ll MOD = 998244353;

int main(){
	ll n;
	string s;
	cin >> n >> s;
	
	vector<int> r,g,b;
	for(int i = 0 ; i < s.size() ; i ++){
		if(s[i] == 'R')r.push_back(i);
		else if(s[i] == 'G')g.push_back(i);
		else b.push_back(i);
	}
	
	vector<P> M[3];
	for(int i = 0 ; i < n ; i ++){
		vector<int> t;
		t.push_back(r[i]);
		t.push_back(g[i]);
		t.push_back(b[i]);
		sort(t.begin(),t.end());
		for(int j = 0 ; j < 3 ; j ++){
			if(r[i] == t[j])M[j].push_back(P(1,t[j]));
			if(g[i] == t[j])M[j].push_back(P(2,t[j]));
			if(b[i] == t[j])M[j].push_back(P(3,t[j]));
		}
	}
	
	ll ret = 1;
	ll j = 0;
	for(int i = 0 ; i < n ; i ++){
		while(M[0][i].first == M[0][j].first && M[0][j].second < M[1][i].second)j ++;
		ret *= j-i;
		ret %= MOD;
	}
	reverse(M[1].begin(),M[1].end());
	reverse(M[2].begin(),M[2].end());
	for(int i = 0 ; i < n ; i ++){
		M[1][i].second = -M[1][i].second;
		M[2][i].second = -M[2][i].second;
	}
	M[0] = M[2];
	j = 0;
	for(int i = 0 ; i < n ; i ++){
		while(M[0][i].first == M[0][j].first && M[0][j].second < M[1][i].second)j ++;
		ret *= j-i;
		ret %= MOD;
	}
	for(int i = 0 ; i < n ; i ++){
		ret *= i+1;
		ret %= MOD;
	}
	cout << ret << endl;
}

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

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

   for(int i = 0;i<n;i++)
   {
      for(int j = 0;j<n;j++)
      {
         if(s[i][j]=='1')
         G[i].push_back(j);
      }
   }
   int ans = -1;
   for(int i = 0;i<n;i++)
   {
      queue<int> Q;
      vector<int> dis(n,-1);
      Q.push(i);
      dis[i] = 1;
      while(!Q.empty())
      {
         auto now = Q.front();
         Q.pop();
         for(auto j:G[now])
         {
            if(~dis[j])continue;
            dis[j] = dis[now]+1;
            Q.emplace(j);
         }
      }
      bool flg = true;
      int now = -1;
      for(int fr = 0;fr<n;fr++)
      {
         for(auto to:G[fr])
         {
            if(abs(dis[fr]-dis[to])!=1)
            {
               flg = false;
            }
         }
         now = max(now,dis[fr]);
      }
      if(flg)
      {
         ans = max(ans,now);
      }
   }
   cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
// Welcome to my source code!

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

int main() {
    string w;
    cin >> w;
    int n = w.size();
    bool t[24] = {};
    for (int i = 0; i < n; i++) {
        int id = w[i] - 'a';
        if (t[id]) t[id] = false;
        else t[id] = true;
    }
    bool flag = true;
    for (auto x : t) {
        if (x) flag = false;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
char r[999],g[999],d[999],z[999];main(){
	int c,i,j,k,l;
	for(;scanf("%s%s%s",r,g,d)>2;z[l]=0,printf("%s\n",z)){
		for(i=j=k=l=0,c=g[j++];k+l<strlen(r)+strlen(g);){
		//if(c==r[i]){
			if(c==d[k]){//push_down
				k++;
				c=r[i++];
			}else{ //push_right
				z[l++]=c;
				c=g[j++];
			}
		}
	}
exit(0);}

Measured memory_bytes: 528
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    sa = [0] + list(accumulate(A))
    sam = [a % M for a in sa]
    ans = 0
    for n in Counter(sam).values():
        ans += n*(n-1)//2
    return ans

def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M, A))


if __name__ == '__main__':
    main()


Measured memory_bytes: 110432
N = int(input())
P = [0] + [int(_) for _ in input().split()]
count = 0
for i, v in enumerate(P):
    if i != v:
        P[i], P[v] = P[v], P[i]
        break
if sorted(P) == P:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 2940
#include <stdio.h>
#include <math.h>
#include<stdio.h>
#define M_PI 3.14159265358979323846
int main(){
  int a,b;
  char c;
  while(1) {
    scanf("%d %c %d", &a,&c,&b);//scanf("%d %c %d", &a,&c&b);//
    if(c == '?') break;
    if(c=='+') printf("%d\n",(a+b));
    else if(c=='-') printf("%d\n",(a-b));
    else if(c=='*') printf("%d\n",(a*b));
    else if(c=='/') printf("%d\n",(a/b));
  }
  
  
  //printf("%.6f %.6f\n", M_PI*a*a,M_PI*2.0*a);
  return 0;
}


Measured memory_bytes: 2688
#include<iostream>

using namespace std;

int main()
{
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  
  while(a>0 && c>0)
  {
    c-=b;
    a-=d;
  }
  
  if(c<=0)
    cout<<"Yes";
  
  else if(a<=0)
    cout<<"No";
   
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>

using namespace std;

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

	int yaki = 0;

	if (N % X == 0)
		yaki = N / X;
	else
		yaki = (int)(N / X + 1);

	cout << yaki * T;
	return 0;
}

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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979323846

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





int main() {
  ll N;
  cin >> N;
  ll ans = 0;

  for (ll i = 1; i <= N; i++){
    ll max = (ll)floor(N/i);
    ans += i * max * (1 + max) / 2;
  }

  cout << ans << endl;

  // cout << setprecision(8) << ans << endl;  // For double
}



Measured memory_bytes: 3640
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    int a, b, d, r;
    double f;
    cin >> a >> b;
    d = a / b;
    r = a % b;
    f = (double) a / b;
    cout << d << " " << r << " " << fixed << setprecision(8) << f << endl;

    return 0;
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
using namespace std;

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

    int kaijou = 1;
    int count = 0;
    while(n >= kaijou){
        kaijou *= k;
        count++;
    }
    print(count);
}


Measured memory_bytes: 256
import numpy as np

a,b,c = map(int,input().split())

#if a**(1/2)+b**(1/2)<c**(1/2):
#if np.power(a,1/2)+np.power(b,1/2)<np.power(c,1/2):
if (c-a-b>0)and(4*a*b<((c-a-b)**2)):
  print("Yes")
else:
  print("No")


Measured memory_bytes: 12468
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>

#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#include <utility>
#include <list>

#include <cmath>
#include <algorithm>
#include <cassert>
#include <bitset>
#include <complex>
#include <climits>
#include <functional>
#include <unordered_set>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> l4;
typedef pair<double, double> dd;
#define mp make_pair
#define pb push_back

#define debug(x) cerr << #x << " = " << x << " "

int main()
{
  int n;
  scanf("%d", &n);
  multiset<int> st;
  for (int i = 0; i < n; ++i)
    {
      int x; scanf("%d", &x);
      st.insert(x);
    }
  const int P = 31;
  vector<int> pw2(P);
  for (int i = 0; i < P; ++i) pw2[i] = 1<<i;

  int ans = 0;
  while (!st.empty())
    {
      auto it = --st.end();
      int cur = *it;
      st.erase(it);
      while (!pw2.empty() && 2 * cur < pw2.back()) pw2.pop_back();
      assert(!pw2.empty());
      int tar = pw2.back() - cur;
      it = st.find(tar);
      if (it != st.end())
        {
          ++ans;
          st.erase(it);
        }
    }
  printf("%d\n", ans);
}


Measured memory_bytes: 9600
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

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

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




int main() {
    ll a, b;
    cin >> a >> b;
    if(a * b & 1){
        cout << "Odd" << endl;
    }
    else{
        cout << "Even" << endl;
    }
}

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

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;

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

    vector<int> G[N], value(N, 0);

    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
    }

    rep(i, Q) {
        int p, x;
        cin >> p >> x;
        value[p - 1] += x; 
    }

    //ans[0] = value[0];
    rep(i, N - 1) {
        rep(j, G[i].size()) {
            value[G[i][j]] += value[i];
        }
    }

    rep(i, N - 1) {
        cout << value[i] << " ";
    }
    cout << value[N - 1] << endl;
    return 0;
}

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

h,w = map(int,input().split())

c = []
for i in range(w):
    c.append(chr(150+i))

for i in range(h):
    inp = input()
    for j in range(w):
        c.append(inp[j])
h += 1
h2 = h**2
res = 0

for j in range(1,w):
    
    #d[x][y] : j列目x個とj-1列目y個の時の一致数
    d = [0]*(h2)

    for x in range(1,h):
        for y in range(1,h):
            if c[x*w+j] == c[y*w+j-1]:
                d[x*h+y] = d[x*h+y-h-1] + 1
            else:
                d[x*h+y] = d[x*h+y-h-1]
    
    #dp[x][y] : j列目x個とj-1列目y個までの最小一定数和
    dp = [10**10]*h2

    for i in range(h):
        dp[i] = dp[i*h] = 0

    for x in range(1,h):
        for y in range(1,h):
            if dp[x*h+y-1] < dp[x*h-h+y]:
                dp[x*h+y] = dp[x*h+y-1] + d[x*h+y]
            else:
                dp[x*h+y] = dp[x*h-h+y] + d[x*h+y]
    res += dp[-1]

print(res)





Measured memory_bytes: 118872
#include<iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <fstream>
#include <functional>

using namespace std;
using ll = long long;

#define all(x) (x).begin(),(x).end()
#define PRI(n) cout << n << " "<<endl;
#define PRI2(n, m) cout << n << " " << m << " "<<endl;

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

const char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
                           's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
const ll MOD = 1e9 + 7;

struct edge;
struct UnionFind;

bool isPrime(ll x);

ll GCD(ll a, ll b);

ll LCM(ll a, ll b);

ll nCr(int n, int r);


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

    UnionFind(int N) {
        for (int i = 0; i < N; ++i) {
            par.push_back(i);
            rank.push_back(0);
        }
    }

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

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])par[x] = y;
        else {
            par[y] = x;
            if (rank[x] == rank[y])rank[x]++;
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

ll M, N;
bool s[10][10];
bool p[10];

int main() {
    ll N, M;
    cin >> N >> M;
    ll s = 0, e = N;
    REP(i, M) {
        ll a, b;
        cin >> a >> b;
        if(s<a)s = a;
        if(e>b)e = b;
    }
    if(e-s>=0)PRI(e-s+1)
    else PRI(0)
    
    return 0;
}

struct edge {
    int to, cost;
    bool flag = false;
};

bool isPrime(ll x) {
    if (x == 0)return 0;
    if (x == 1)return 0;
    if (x == 2)return 1;
    if (x % 2 == 0)return 0;
    FOR(i, 3, x - 1) {
        if (x % i == 0)return 0;
    }
    return 1;
}

ll GCD(ll a, ll b) {
    if (b == 0)return a;
    return GCD(b, a % b);
}

ll LCM(ll a, ll b) {
    ll gcd = GCD(a, b);
    return a / gcd * b;
}

ll nCr(int n, int r) {
    vector<ll> C(r + 1);
    C[0] = 1;
    FOR(i, 1, n) for (int j = min(i, r); j < 1; --j)C[j] = (C[j] + C[j - 1]) % MOD;
    return C[r];
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#define ll long long
#define mod 1000000007
using namespace std;

string s;
//       position,sum,state 
int d, dp[100005][110][2];

// curpos , cursum , state
// base case: curpos = s.size()

int solve(int pos, int cursum, bool state)
{
	if (pos == s.size())
	{
		if (cursum % d == 0)return 1;
		else return 0;
	}
	if (dp[pos][cursum][state] != -1)return dp[pos][cursum][state];
	int tmp = 0;
	for (int i = 0; i < 10; i++)
	{
		if (state)
		{
			tmp = (tmp + solve(pos + 1, (cursum + i) % d, 1)) % mod;
		}
		else
		{
			if (i < s[pos] - '0')
			{
				tmp = (tmp + solve(pos + 1, (cursum + i) % d, 1)) % mod;
			}
			else if (i == s[pos] - '0')
			{
				tmp = (tmp + solve(pos + 1, (cursum + i) % d, 0)) % mod;
			}
		}
	}
	return dp[pos][cursum][state] = tmp;
}

int main()
{
	memset(dp, -1, sizeof dp);
	cin >> s >> d;
	cout << ((solve(0, 0, 0) - 1) + mod) % mod << '\n';
	return 0;
}

Measured memory_bytes: 87040
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector
;
#define vvec(s) vector<vector
> ;
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vector<int> v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    lli h,w,a,b;
    cin>>h>>w>>a>>b;
    vvi ans(h,vi(w,1));
    rep(i,a){
        rep(j,b){
            ans[j][i]=0;
        }
    }
    rep(i,h-b){
        rep(j,w-a){
            ans[h-i-1][w-j-1]=0;
        }
    }
    rep(i,h){
        rep(j,w){
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define fr first
#define sc second
#define pb push_back
const ll mod = 1e9+7;
const int N = 1e6+205;
ll cnt[N];
void solve(){
	for(int i=1;i<N;i++){
		for(int j=i;j<N;j+=i){
			cnt[j]++;
		}
	}
	int n; 
	cin>>n; 
	ll ans = 0;
	for(int i=1;i<n;i++){
		int dif = n-i;
		ans+=cnt[dif];
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 11460
n = int(input())
ls = []
for i in range(n):
    x,l = map(int,input().split())
    ls.append([x-l,l+x])
    
ls = sorted(ls, key=lambda x: x[1])
ans = n

for i in range(1,n):
    if ls[i][0] < ls[i-1][1]:
      ls[i][1] = ls[i-1][1]
      ans -=1
        
print(ans)

Measured memory_bytes: 22100
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <pair<int, int> > bridges;
int a, b, n, m;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		bridges.push_back(make_pair(b, a));
	}
	sort(bridges.rbegin(), bridges.rend());
	int ans = 0;
	while (!bridges.empty()) {
		int cut = bridges[bridges.size() - 1].first - 1;
		ans++;
		while (bridges[bridges.size() - 1].second <= cut && cut <= bridges[bridges.size() - 1].first && !bridges.empty())
			bridges.pop_back();
	}
	cout << ans << endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

void solve(long long N, vector<long long> P){
	ll now = INF, res = 0;
	rep(i, N) {
		if (P[i] <= now) {
			now = P[i];
			res++;
		}
	}
	cout << res << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> P(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&P[i]);
	}
	solve(N, P);
	return 0;
}



Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll mod = 1e9 + 7;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}

double DegreeToRadian(double degree){
    return degree * M_PI / 180.0;
}

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


/////////////////////////////////////////////////////////////////////////////////////

int main(){
    int n, m;
    cin >> n >> m;
    vector<long long> h(n);
    for(int i = 0;i < n;i++){
        cin >> h[i];
    }
    vector<int> con[100010];
    for (int i = 0;i < m;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        con[a].push_back(b);
        con[b].push_back(a);
    }

    int count = 0;
    for (int i = 0;i < n;i++){
        bool highest = true;
        for (int v : con[i]){
            if (h[i] <= h[v]){
                highest = false;
                break;
            }
        }
        if (highest){
            count++;
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 8960
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define maxn 1005
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
int n,c;
int a[maxn][maxn];
int d[maxn][maxn];
ll dp[maxn][maxn];
vector<pa> edge[maxn];
int main()
{
	scanf("%d%d",&n,&c);
	for(int i=1;i<=c;i++)
		for(int j=1;j<=c;j++)
			scanf("%d",&d[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
			edge[(i+j)%3].push_back(pa(i,j));
		}
	}

	for(int i=1;i<=c;i++)
	{
		for(int j=0;j<=2;j++)
		{
			int len=edge[j].size();
			ll res=0;
			for(int k=0;k<len;k++)
			{
				int x=edge[j][k].first,y=edge[j][k].second;
				res+=d[a[x][y]][i];
			}
			dp[j][i]=res;
		}
	}
	ll ans=12345623423413243ll;
	for(int i=1;i<=c;i++)
	{
		for(int j=1;j<=c;j++)
		{
			for(int k=1;k<=c;k++)
			if(i!=j && j!=k && k!=i)
			{
				ll res=dp[0][i];
				res+=dp[1][j];
				res+=dp[2][k];
				ans=min(ans,res);
			}
		}
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 8752
#include<bits/stdc++.h>
using namespace std;
int a[11][11];
int main()
{
	int ans=0,i,j,k,n,m;
	float tmp;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			tmp=0;
			for(k=1;k<=m;k++)
			{
				tmp+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
			}
			tmp=sqrt(tmp);
			if(tmp==(int)(tmp))
				ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

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

#define      pb    push_back
#define      ff    first
#define      ss    second
#define      ll    long long int
#define      endl  "\n"
#define      FASTIO        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define      TEST    ll t ; cin >> t ; while( t -- )


//------------------------------------------------------------------------//

#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

//------------------------------------------------------------------------//

const ll big = 10e15 + 11 ;


int  main (  ) {

    FASTIO ;

    int n , m ;
    cin >> n >> m ;

    vector < ll > v( n + 2 ) , graph[ n + 2 ] ;

    for( int i = 1 ; i <= n ; i++ ) cin >> v[ i ] ;

    for( int i = 0 ; i < m ; i++ ){
        int a , b ;
        cin >> a >> b ;

        graph[ a ].pb( b ) ;
        graph[ b ].pb( a ) ;
    }

    ll ans = 0 ;

    for( int i= 1 ; i <= n ; i++ ){
        ll x = v[ i ] ;

        int len = graph[ i ].size( ) , flag = 0 ;

        for( int j = 0 ; j < len ; j++ ){
            int child = graph[ i ][ j ] ;

            if( v[ child ] >=  x ){
                flag = 1 ;
                break ;
            }
        }
        if( !flag ) ans++ ;
    }

    cout << ans << endl ;


    return  0 ;
}


Measured memory_bytes: 9800
import java.util.Scanner;

public class Main
{
	public static void main(String arg[])
	{
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext())
		{
			int count = 0;
			int n = sc.nextInt();
			if(n==0)
				System.exit(0);
			while(n>0)
			{
				int m=n;
				while(m%5==0)
				{
					count ++;;
					m=(m/5);
				}
				n--;
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 12000
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        List<Integer> al = new ArrayList<>();  
        int q = Integer.parseInt(sc.next());
        for (int i = 1; i <= q; i++) {
            int query = Integer.parseInt(sc.next());
            if (query == 0) {
                int x = Integer.parseInt(sc.next());
                al.add(x);
//                pw.println(al);
            } else if (query == 1) {
                int p = Integer.parseInt(sc.next());
                pw.println(al.get(p));
            } else if (query == 2) {
                al.remove(al.size()-1);
//                pw.println(al);
            }
        }
        pw.flush();
    }
}


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

const int N = 200010;
const int moder = int(1e9) + 7;
using ll = long long;

int a[N];

int powermod(int a, int exp){
    int ret = 1;
    for ( ; exp > 0; exp >>= 1){
        if (exp & 1){
            ret = 1ll * ret * a % moder;
        }
        a = 1ll * a * a % moder;
    }
    return ret;
}

int main(){
    int n, K;
    scanf("%d%d", &n, &K);
    for (int i = 0; i < n; ++ i){
        scanf("%d", &a[i]);
    }
    int prod = 1;
    if (n == K){
        for (int i = 0; i < n; ++ i){
            prod = 1ll * prod * a[i] % moder;
        }
        prod += prod < 0 ? moder : 0;
        printf("%d\n", prod);
        return 0;
    }
    std::sort(a, a + n, [](const int &p1, const int &p2){return std::abs(p1) > std::abs(p2);});
    int minus = 0;
    for (int i = 0; i < K; ++ i){
        if (a[i] == 0){
            puts("0");
            return 0;
        }
        minus += a[i] < 0;
    }
    if (minus % 2 == 0){
        for (int i = 0; i < K; ++ i){
            prod = 1ll * prod * a[i] % moder;
        }
        prod += prod < 0 ? moder : 0;
        printf("%d\n", prod);
        return 0;
    }
    int pos[2][2] = {{-1, -1}, {-1, -1}};
    for (int i = K - 1; i >= 0; -- i){
        if (a[i] > 0){
            pos[0][0] = i;
            break;
        }
    }
    for (int i = K - 1; i >= 0; -- i){
        if (a[i] < 0){
            pos[0][1] = i;
            break;
        }
    }
    for (int i = K; i < n; ++ i){
        if (a[i] > 0){
            pos[1][0] = i;
            break;
        }
    }
    for (int i = K; i < n; ++ i){
        if (a[i] < 0){
            pos[1][1] = i;
            break;
        }
    }
    if ((pos[0][0] == -1 || pos[1][1] == -1) && (pos[0][1] == -1 || pos[1][0] == -1)){
        if (a[n - 1] == 0){
            puts("0");
        }
        else{
            for (int i = n - K; i < n; ++ i){
                prod = 1ll * prod * a[i] % moder;
            }
            prod += prod < 0 ? moder : 0;
            printf("%d\n", prod);
        }
        return 0;
    }
    int type;
    if (pos[0][0] == -1 || pos[1][1] == -1){
        type = 2;
    }
    else if (pos[0][1] == -1 || pos[1][0] == -1){
        type = 1;
    }
    else{
        ll value1 = std::abs(1ll * a[pos[1][1]] * a[pos[0][1]]);
        ll value2 = std::abs(1ll * a[pos[1][0]] * a[pos[0][0]]);
        if (value1 > value2){
            type = 1;
        }
        else{
            type = 2;
        }
    }
    for (int i = 0; i < K; ++ i){
        prod = 1ll * prod * a[i] % moder;
    }
    if (type == 1){
        prod = 1ll * prod * a[pos[1][1]] % moder * powermod(a[pos[0][0]], moder - 2) % moder;
    }
    else{
        prod = 1ll * prod * a[pos[1][0]] % moder * powermod(a[pos[0][1]], moder - 2) % moder;
    }
    prod += prod < 0 ? moder : 0;
    printf("%d\n", prod);
    return 0;
}


Measured memory_bytes: 4516
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

  int n; cin >> n;
  vector<double> p(n);
  for(int i = 0; i < n; i++){
    cin >> p[i];
  }

  static double dp[3001][3001];
  dp[0][0] = 1;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      dp[i+1][j+1] += dp[i][j] * p[i];
      dp[i+1][j] += dp[i][j] * (1 - p[i]);
    }
  }

  double ans = 0;
  for(int i = (n+1)/2; i <= n; i++){
    ans += dp[n][i];
  }
  printf("%.10f\n",ans);

  return 0;
}


Measured memory_bytes: 70528
#include <bits/stdc++.h>
 using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 int main(){
   string s,t;
   int a=0;
   cin>>s>>t;
   rep(i,3)
   if(s.at(i)==t.at(i))a++;
   cout<<a<<endl;

}

Measured memory_bytes: 384
import itertools
import math

N = int(input())
p = []
for i in range(N):
    x, y = [int(n) for n in input().split()]
    p.append([x, y])

total_length = 0
k = 0
for pattern in itertools.permutations(p):
    k += 1
    length = 0
    for i in range(N-1):
        length += math.sqrt((pattern[i+1][0] - pattern[i][0])**2 + (pattern[i+1][1] - pattern[i][1])**2)
    total_length += length

print(total_length/k)

Measured memory_bytes: 9076
use std::cmp;

fn main() {
    let (a, b, c, d): (i64, i64, i64, i64) = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };

    let ans = cmp::max(cmp::max(a * c, a * d), cmp::max(b * c, b * d));
    println!("{}", ans);
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define Test(tt) cout << "Case #" << tt << ": "

using namespace std;

const int MAXN = (int) 2e5;

int x[MAXN + 1], y[MAXN + 1];

struct DSU {
    vector <int> par, sz;
    int n;
    inline void init(int _n) {
        n = _n;
        par.resize(n + 1);
        sz.resize(n + 1, 1);
    }
    int root(int x) {
        if(par[x] == 0)
            return x;
        return par[x] = root(par[x]);
    }
    inline void join(int x, int y) {
        x = root(x), y = root(y);
        if(x != y) {
            par[x] = y;
            sz[y] += sz[x];
        }
    }
};


int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    vector<pair<int, int>> ord(n);
    for(i = 1; i <= n; i++) {
    	cin >> x[i] >> y[i];
    	ord[i - 1] = {x[i], i};
    }
    sort(ord.begin(), ord.end());

    DSU dsu; dsu.init(n);
    set<pair<int, int>> mst;

    for(i = n - 1; i >= 0; i--) {
    	int p = ord[i].second;
    	while(1) {
    		auto it = mst.lower_bound({y[p], 0});
    		if(it == mst.end()) break;

    		dsu.join(p, it -> second);
    		if(next(it) == mst.end()) {
    			break;
    		}
    		else {
    			mst.erase(it);
    		}
    	}
    	if(dsu.root(p) == p)
    		mst.insert({y[p], p});
    }

    for(i = 1; i <= n; i++) {
    	cout << dsu.sz[dsu.root(i)] << "\n";
    }
	
    return 0;
}


Measured memory_bytes: 8180
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

int main() {
	int N;
	cin >> N;
	int ans = 0;
	for(int i = 1; i <= N; i++) {
		if(i % 2 == 0) continue;
		int cnt = 0;
		for(int j = 1; j <= i; j++)
			if(i % j == 0) cnt++;
		if(cnt == 8) ans++;
	}
	cout << ans << "\n";
}

Measured memory_bytes: 3464
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <utility>

#include <cassert>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define FOR(i,a,b) for(ll i=(a); i < (b); i++)
#define RFOR(i,a,b) for(ll i=(b)-1; i >= (a); i--)
#define rep(i,n) FOR(i,0,(n))
#define rrep(i,n) RFOR(i,0,(n))

const int INF = 1e8;
int dp[2100*2][2100];

struct BIT {
	vector<int> dat;
	int size;
	BIT(int n) {
		this->init(n);
	}
	void init(int n) {
		dat.resize(n+1);
		size = n;
		rep(i,dat.size()) dat[i] = 0;
	}
	int sum(int i) {
		i++;
		int s = 0;
		while(i > 0) {
			s += dat[i];
			i -= i & -i;
		}
		return s;
	}
	void add(int i) {
		i++;
		while(i < dat.size()) {
			dat[i]++;
			i += i & -i;
		}
	}
};

int main() {
	int N;
	cin >> N;
	vector<int> w(N), b(N);
	vector<BIT> BITs;
	rep(i,2100) BITs.push_back(BIT(N*2+10));
	rep(i,2*N) {
		string c;
		int a;
		cin >> c >> a;
		a--;
		if(c == "B") {
			b[a] = i;
		}
		else {
			w[a] = i;
		}
	}
	rep(i,2100*2)
		rep(j,2100)
			dp[i][j] = INF;
	dp[0][0] = 0;

	FOR(i,1,2*N+1) {
		rep(j, min<ll>(i,N)+1) {
			int ww, bb;
			ww = bb = INF;

			if(0 < i-j && i-j <= min<ll>(i,N))
				ww = i-1 - BITs[j].sum(w[i-j -1]) + dp[i-1][j];
			if(j)
				bb = i-1 - BITs[j-1].sum(b[j -1]) + dp[i-1][j-1];

			dp[i][j] = min(min(ww, bb), INF);

		}
		rep(j, N+1) {
			if(j && j <= N && i <= j) {
				BITs[j].add(b[min(i,j)-1]);
			}
			else if(0 < i-j && i-j <= N) {
				BITs[j].add(w[i-j -1]);
			}
		}
	}
	/*
	rep(i,20) {
		rep(j,10) {
			printf("%5d", i-j <= N && j <= N ? dp[i][j] : INF);
		}
		puts("");
	}
	// */

	cout << dp[2*N][N] << endl;
	return 0;
}


Measured memory_bytes: 67712
def main():
    N, P = map(int, input().split())
    S = input()
    ans = 0
    mods = [0 for i in range(N+1)]
    digits = 1

    if P == 2 or P == 5:
        for i in range(N-1, -1, -1):
            if int(S[i])%P == 0:
                ans += i+1
        print(ans)
        return

    for i in range(N-1, -1, -1):
        mods[i] = (int(S[i]) * digits % P + mods[i+1]) % P
        digits = digits * 10 % P

    count = [0 for i in range(P)]
    for i in range(N, -1, -1):
        ans += count[mods[i]]
        count[mods[i]] += 1

    print(ans)

main()

Measured memory_bytes: 53344
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 26;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

vector<int> djikstra(map<int, vector<pair<int, int>>> &g, int s, int n)
{
    vector<int> ret(n, IINF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty())
    {
        auto pos = pq.top().second;
        auto cost = pq.top().first;
        pq.pop();
        if (ret[pos] <= cost)
        {
            continue;
        }
        ret[pos] = cost;
        for (auto &&x : g[pos])
        {

            pq.push({cost + x.second, x.first});
        }
    }
    return ret;
}

void solve(int n, int m, int s, int g1, int g2)
{
    map<int, vector<pair<int, int>>> gf, gb;
    rep(i, m)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        gf[a].push_back({b, c});
        gb[b].push_back({a, c});
    }
    auto ds = djikstra(gf, s, n);
    auto dg1 = djikstra(gb, g1, n);
    auto dg2 = djikstra(gb, g2, n);
    int ans = IINF;
    rep(i, n)
    {
        chmin(ans, ds[i] + dg1[i] + dg2[i]);
    }
    cout << ans << endl;
}

int main()
{
    int n, m, s, g1, g2;
    while (cin >> n >> m >> s >> g1 >> g2, n)
    {
        s--;
        g1--;
        g2--;
        solve(n, m, s, g1, g2);
    }
    return 0;
}


Measured memory_bytes: 3252
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef long double ld;
const ld pi = 4*atan((ld)1);
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll nax = 0;

ll a, b, c;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> a >> b >> c;
	b *= c;
	if(a <= b){
		cout << "Yes\n";
	}
	else{
		cout << "No\n";
	}
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i, n) {
        cin >> p[i];
        ++p[i];
    }
    int mx = 0;
    int s = 0;
    queue<double> q;
    rep(i, n) {
        s += p[i];
        q.push(p[i]);
        if (q.size() > k) {
            s -= q.front();
            q.pop();
        }
        if (q.size() == k) {
            chmax(mx, s);
        }
    }
    double ans = mx;
    ans /= 2;
    printf("%.10f\n", ans);
}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("test.inp","r",stdin);
    long long int n,i,j;
    long long int  w;
    cin >> n >> w;
    long long int m[n+10],v[n+10];
    long long int f[n+10][w+10];
    for ( i = 1; i <= n; i++)
    {
        cin >> m[i] >> v[i];
    }
    for ( j = 0; j <= w; j++)
    {
        f[0][j] = 0;
    }
    for ( i = 1; i <= n; i++)
    {
        f[i][0] = 0;
    }
    for (i = 1; i <= n; i++)
    {
        for ( j = 0; j <= w; j++)
        {
                if ( m[i] > j)
            {
                f[i][j] = f[i-1][j];
            }
                else
            {
                f[i][j] = max((f[i-1][j-m[i]]+v[i]),(f[i-1][j]));
            }
        }
    }
    cout << f[n][w];
    return 0;
}


Measured memory_bytes: 80512
from collections import deque
d = deque()

k = int(input())

for i in range(1,10):
    d.append(i)
    
for i in range(k):
    x = d.popleft()
    if not x%10 == 0:
        d.append(x*10+(x%10)-1)
    d.append(x*10+(x%10))
    if not x%10 == 9:
        d.append(x*10+(x%10)+1)

print(x)

Measured memory_bytes: 11908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const double pie = 3.14159265358979;

int main(){
   int n;
   cin >> n;
   vector<int> L(n);
   for(int i = 0; i < n; i++) cin >> L[i];
   sort(all(L));
   int ans = 0;
   for(int i = 0; i < n-2; i++){
       for(int j = i+1; j < n-1; j++){
           ans += lower_bound(all(L), L[i] + L[j]) - L.begin() - j - 1;
       }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll 				long long
#define int             long long int
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define modp            998244353
#define inf             (ll)1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO           	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl 			'\n'
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void solve()
{
	int x;
	cin >> x;
	if(x == 0)
		cout << 1 << endl;
	else
		cout << 0 << endl;
}
 
int32_t main()
{
	FIO
    // w(t)
    {
    	solve();
    }
    return 0;
}
	

	

Measured memory_bytes: 3648
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static List<Edge>[] graph; //配列番号＝頂点番号。各頂点から出る複数のエッジをListにして持たせる
    static int dist[]; //ダイクストラの結果として、各頂点までの距離が格納される配列

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        graph = new List[n];
        for (int i=0;i<n;i++) graph[i] = new ArrayList<>();
        int s = 0;

        for (int i = 0 ; i < n - 1 ; i++) {
            int u = i ;
            int v = i + 1;
            int cost = 1;
            graph[u].add(new Edge(v, cost));
            graph[v].add(new Edge(u, cost));            ;
        }

        graph[x - 1].add(new Edge(y - 1, 1));
        graph[y - 1].add(new Edge(x - 1, 1));
        //メソッド実行
        int ans[] = new int[10003];
        for (int i = 0 ; i < n ; i++) {
            dist = new int[n]; //各ノードまでの距離
            dijkstra(i); //dist[]の中身に最短経路が入ります
            for (int j = i ; j < n ; j++) {
                ans[dist[j]]++;
            }
        }

        for (int i = 1 ; i < n ; i++) {
            System.out.println(ans[i]);
        }


    }
    static void dijkstra(int v) { //出発頂点を引数にとります
        //dist[]の初期化
        int INF = Integer.MAX_VALUE / 3;
        Arrays.fill(dist, INF);
        dist[v] = 0;

        //頂点を、出発点からの距離が近い順に取得できるPriorityQueueを用意
        PriorityQueue<Vertex> pq = new PriorityQueue<>((v1, v2)->v1.dist < v2.dist ? -1:1);

        //出発頂点をQueueに格納して、whileループスタート
        pq.add(new Vertex(v, dist[v]));
        while(!pq.isEmpty()) {
            //次に扱う頂点をQueueから取り出す
            Vertex now = pq.poll();
            if(now.dist > dist[now.id])continue; //後から新しく更新されて、見る必要がない場合
            //頂点から出るエッジ全てを見て、接続先の頂点のコストをより小さくできるなら更新
            for(Edge e : graph[now.id]) {
                if(dist[e.to] > dist[now.id] + e.cost) {
                    //更新
                    dist[e.to] = dist[now.id] + e.cost;
                    //更新した場合は、接続先の頂点をQueueに入れる
                    pq.add(new Vertex(e.to, dist[e.to]));
                }
            }
        }
    }

  //分かりやすくなるので、エッジと頂点はクラス化します。

}

class Edge {
    int to, cost;
    public Edge(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }
}
class Vertex{
    int id;
    long dist;
    public Vertex(int id, long dist) {
        this.id = id;
        this.dist = dist;
    }
}

Measured memory_bytes: 82860
# -*- coding: utf-8 -*-

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result



n = int(input())
s = []
for i in range(n):
  s.append(input())
h = []
b = 'abcdefghijklmnopqrstuvwyz'
for i in s:
  a = [0] * 27
  for c,d in enumerate(b):
    a[c] = i.count(d)
  ss = ''
  for j in a:
    ss += str(j)
  h.append(ss)
 
ans = 0
c = {}
for i in h:
  if c.get(i, -1) == -1:
    c[i] = 1
  else:
    c[i] += 1
sum = 0
for i in c:
  if c[i] < 2:
    continue
  ans += cmb(c[i],2)

print(ans)

Measured memory_bytes: 28200
n=int(input())
d,x=map(int,input().split())
a=[int(input()) for i in range(n)]

ans=n
for i in a:
	cnt=1
	t=1
	while  t<=d:
		t=cnt*i+1
		cnt+=1
		if t<=d:
			ans+=1

print(ans+x)

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

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

int n;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  int d = n % 10;
  switch (d) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      cout << "hon" << endl;
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      cout << "pon" << endl;
      break;
    default:
      cout << "bon" << endl;
      break;
  }

  return 0;
}


Measured memory_bytes: 3652