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

using namespace std;

typedef pair<int, int> pii;

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

int N, M, K;
int did_num[20];
int num_did[120];
int v[120][120];
int dp[1<<16];


int main() {
    rep(i, 120) num_did[i] = -1;
    rep(i, 1<<16) dp[i] = INT_MAX;

    cin >> N >> M >> K;
    rep(i, M) { int x; cin >> x; did_num[i] = x-1; num_did[x-1] = i; }
    rep(i, N) rep(j, K) { int x; cin >> x; v[i][j] = x-1; }

    dp[(1<<M)-1] = 0;
    queue<int> que;
    que.push((1 << M) - 1);
    while(!que.empty()) {
        int s = que.front(); que.pop();
        int t = dp[s];
        rep(k, K) {
            int ns = 0;
            rep(i, M) {
                if(s>>i & 1) {
                    int src = did_num[i];
                    int tgt = v[src][k];
                    if(num_did[tgt] >= 0) ns |= 1 << num_did[tgt];
                }
            }
            if(ns == 0) {
                cout << t + 1 << endl;
                return 0;
            }
            if(dp[ns] > t + 1) {
                dp[ns] = t + 1;
                que.push(ns);
            }
        }
    }
}



Measured memory_bytes: 3576
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	long long int N;
	long long int K;
	cin >> N >> K;
	vector<long long int> H(N);
	
	for(long long int i = 0;i<N;i++){
		std::cin >> H[i];
	}
	
	sort(H.begin(), H.end(), greater<int>());
	long long int result = 0;
	
	
	for(int i = 0;i<N;i++){
		if(i<K){
		}else{
			result+=H[i];
		}
	}
	std::cout << result <<  std::endl;
}


Measured memory_bytes: 1920
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
int dp[2010][2010];

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int S[2010], T[2010];
    rep(i, N) cin >> S[i];
    rep(i, M) cin >> T[i];
    rep(i, N + 1) dp[i][0] = 1;
    rep(j, M + 1) dp[0][j] = 1;
    rep(i, N) {
        rep(j, M) {
            if (S[i] == T[j]) dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % mod;
            dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + mod) % mod;
        }
    }
    cout << dp[N][M] << endl;


    return 0;
}
// 1 3
// 3 1
//   / 1 3
// / 1 1 1
// 3 1 1 2
// 1 1 2 3

// 1 2  
// 2 

Measured memory_bytes: 31744
#include<bits/stdc++.h>
#define ll long long int
using namespace std;


int main(){
    int n;
    cin>>n;
    vector<int>v(n),dp(n);
    for(int i = 0 ; i < n ; i++){
        cin>>v[i];
    }
    dp[0]=0;
    dp[1]=abs(v[1]-v[0]);
    for(int i = 2 ; i < n ; i++ ){
        dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),dp[i-2]+abs(v[i]-v[i-2]));
    }
    cout<<dp[n-1];
    
}


Measured memory_bytes: 3932
using System;
class aoj
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            int[] b = new int[3];
            int d = 0;
            while (a != 3)
            {
                string c = Console.ReadLine();
                if (c == "HIT")
                {
                    d += b[2];
                    b[2] = b[1];
                    b[1] = b[0];
                    b[0] = 0;
                    b[0] += 1;
                }
                else if (c == "HOMERUN")
                {
                    d +=( b[0] + b[1] + b[2] + 1);
                    b[0] = 0;
                    b[1] = 0;
                    b[2] = 0;
                }
                else if (c == "OUT")
                    a++;
            }
            Console.WriteLine(d);
        }
    }
}

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

int main() {
    ll N, P;
    string S;
    cin >> N >> P >> S;

    if (P == 2 or P == 5) {
        ll ans = 0;
        rep(i, S.size()) {
            ll tmp = S[i] - '0';
            if (tmp%P == 0) ans += (i + 1);
        }
        cout << ans << endl;
    }
    else {
        ll ans = 0, sum = 0, base = 1;
        map<ll, ll> cnt;
        cnt[0]++;
        for (int i = S.size()-1; i>=0; --i) {
            ll tmp = S[i] - '0';
            tmp = (tmp * base) % P;
            sum = (sum + tmp) % P;
            ans += cnt[sum];
            cnt[sum]++;
            base = (base * 10) % P;
        }
        cout << ans << endl;
    }
}


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

using namespace std;


int main() {

	string S;
	cin >> S;
	
	if(S == "Sunny"){
		
		cout << "Cloudy" << endl;
	}else if (S == "Cloudy"){
		cout << "Rainy" << endl;
		
	}else{
		cout << "Sunny" << endl;
		
	}
	

    return 0;
}


/*

for(int i = 0; i < N; i++){
	
}

for(int i = 0; i < N; i++){
	for(int j = 0; j < N; j++){
		
	}
}


*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

map<ll,ll> prime_factor(ll n) {
    map< ll, ll > ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}
int main(){
    ll n, p;
    cin >> n >> p;
    ll ans = 1;
    for(auto k : prime_factor(p)) {
        int t = k.second / n;
        ll tmp = 1;
        rep(i, t) tmp *= k.first;
        ans *= tmp;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
h, n = map(int, input().split())

dp = [float('inf')] * (h+1)

for _ in range(n):
    damage, mp = map(int, input().split())
    for i in range(h+1):
        if i <= damage:
            dp[i] = min(dp[i], mp)
        else:
            dp[i] = min(dp[i], dp[i-damage] + mp)
print(dp[h])


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

int main() {
	int X;
	cin >> X;
	queue<int> A, B;
	A.push(1);
	B.push(0);
	A.push(0);
	B.push(0);
	A.push(2);
	B.push(0);
	while (true) {
		int a = A.front();
		int b = B.front();
		A.pop();
		B.pop();
		if (pow(a,5) - pow(b,5) == X) {
			cout << a << " " << b << endl;
			break;
		}
		if (a >= 1 && a == b + 1) {
			A.push(a + 1);
			B.push(b + 1);
		}
		if (a < 1 && a == b + 1) {
			A.push(a - 1);
			B.push(b - 1);
		}
		A.push(a);
		B.push(b - 1);
	}
	return 0;
}


Measured memory_bytes: 4064
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;
//using static System.Globalization.CultureInfo;

class Program
{
    static void Main(string[] args)
    {
        var nm = Input.ar;
        var xyz = Input.twodimL(nm[0]);
        var res = 0L;
        for(var i = 0; i < 8; i++)
        {
            var ar = new[] { -1, -1, -1 };
            for (var j = 0; j < 3; j++)
                if ((1 & i >> j) == 1)
                    ar[j] = 1;
            var so = xyz.OrderByDescending(v => v[0] * ar[0] + v[1] * ar[1] + v[2] * ar[2]).Take(nm[1]).ToArray();
            var sum = 0L;
            for (var j = 0; j < 3; j++)
                sum += Abs(so.Sum(v => v[j]));
            res = Max(res, sum);
        }
        WriteLine(res);
    }
}

public class Input
{
    public static string read => ReadLine();
    public  static int[] ar => Array.ConvertAll(read.Split(' '), int.Parse);
    public  static int num => ToInt32(read);
    public  
static long[] arL => Array.ConvertAll(read.Split(' '), long.Parse);
    public  static long numL => ToInt64(read);
    public static int[][] twodim(int num)
        => Enumerable.Repeat(0, num).Select(v => ar).ToArray();
    public static long[][] twodimL(int num)
        => Enumerable.Repeat(0, num).Select(v => arL).ToArray();
    public  const string Alfa = "abcdefghijklmnopqrstuvwxyz";
    public  const int MOD = 1000000007;
}


Measured memory_bytes: 13792
from collections import deque

n = int(input())
A = list(map(int,input().split()))

dq = deque()
for i in range(n):
    if i % 2 == 0:
        dq.append(A[i])
    else:
        dq.appendleft(A[i])

ans = list(dq)
if n % 2 == 1:
    ans.reverse()
print(*ans)

Measured memory_bytes: 25532
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

const int N = 100100;
VI edges[N];

int col[N];
int wg[N];

int dfs(int v, int par = -1) {
  int sum = 0;
  REP(i, 0, edges[v].size()) {
    int w = edges[v][i];
    if (w == par) { continue; }
    int sub = dfs(w, v);
    sum += sub;
  }
  wg[v] = 1 + sum;
  return 1 + sum;
}

int main(void){
  int n;
  cin >> n;
  REP(i, 0, n - 1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  dfs(0);
  int win = 0;
  REP(i, 0, n) {
    int odd = 0;
    int sum = 0;
    REP(j, 0, edges[i].size()) {
      int w = edges[i][j];
      if (wg[w] > wg[i]) { continue; }
      if (wg[w] % 2 == 1) {
	sum += 1;
	odd += 1;
      }
    }
    if (i != 0) {
      odd += (n + 1 + sum) % 2;
    }
    if (odd >= 2) {
      cout << "First" << endl;
      return 0;
    }
  }
  cout << "Second" << endl;
}


Measured memory_bytes: 6272
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		double pond = 2 * Math.PI * r;
		System.out.println(pond);
	}

}


Measured memory_bytes: 35920
n,a,b = map(str,input().split())
# al = list(map(int,input().split()))
a = int(a)
b = int(b)

lst = []
for x in range(1,int(n)+1):
    total = 0
    for i in str(x):
        total += int(i)
    if a <= total <= b:
        lst.append(x)

print(sum(lst))

Measured memory_bytes: 3296
#include <bits/stdc++.h>
using namespace std;
int m;
long long a,b,c,sl,ck,res;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
#endif // LOCAL
    scanf("%d",&m);
    a=-1;
    for(int o=1;o<=m;o++)
    {
        scanf("%lld%lld",&c,&sl);
        if(c==0)
        {
            res+=sl;
            continue ;
        }
        while(sl>1 && c*sl>=10)
        {
            for(ck=2;ck<=sl;ck++)
                if(ck*c>=10) break;
            ck=min(ck,sl);
            if(sl%ck!=0)
            {
                res+=sl%ck;
                if(a==-1)
                {
                    a=0;
                    res--;
                }
                a+=(sl%ck)*c;
                if(a>=10)
                {
                    res++;
                    a=a%10+a/10;
                }
                sl-=sl%ck;
            }
            if(sl>0)
            {
                res+=sl;
                sl/=ck;
                c=(c*ck)%10+(c*ck)/10;
            }
        }
        if(sl>=2)
        {
            res+=sl-1;
            c=c*sl;
        }
        if(a==-1) a=c;
        else
        {
            res++;
            a+=c;
            if(a>=10)
            {
                res++;
                a=a%10+a/10;
            }
        }
    }
    cout<<res;
}




Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <stack>
#include <map>
using namespace std;


int main(){
    int x,y ;
    cin >> x >> y ;
    int a,b,c ;
    cin >> a >> b >> c ;
    vector<pair<int,char> > ap(0,pair<int,char>()) ;
    int p ;
    for (size_t i = 0; i < a; i++)
    {
        cin >> p ;
        ap.push_back(make_pair(p,'R')) ;
    }
    for (size_t i = 0; i < b; i++)
    {
        cin >> p ;
        ap.push_back(make_pair(p,'G')) ;
    }
    for (size_t i = 0; i < c; i++)
    {
        cin >> p ;
        ap.push_back(make_pair(p,'N')) ;
    }
    int rc = 0;
    int gc = 0;
    int nc = 0;
    int64_t ans = 0 ;
    sort(ap.begin(),ap.end()) ;
    int i = a+b+c-1 ;
    while (rc + gc + nc < x + y)
    {
        if (ap.at(i).second == 'R')
        {
            if (rc < x)
            {
                rc ++ ;
                ans += ap.at(i).first ;
            }
            
        }if (ap.at(i).second == 'G')
        {
            if (gc < y)
            {
                gc ++ ;
                ans += ap.at(i).first ;
            }
            
        }if (ap.at(i).second == 'N')
        {
            nc ++ ;
            ans += ap.at(i).first ;
            
        }
        i -- ;       
    }
    
    cout << ans << endl ;
    
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
bool is_cube(long long N){
  long long tv = 10000;
  long long fv = -1;
  while (tv - fv > 1){
    long long mid = (tv + fv) / 2;
    if (mid * mid * mid >= N){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  return tv * tv * tv == N;
}
long long is_square(long long N){
  long long tv = 100000;
  long long fv = -1;
  while (tv - fv > 1){
    long long mid = (tv + fv) / 2;
    if (mid * mid >= N){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  if (tv * tv == N){
    return tv;
  } else {
    return -1;
  }
}
int main(){
  int N;
  cin >> N;
  vector<long long> s(N);
  for (int i = 0; i < N; i++){
    cin >> s[i];
  }
  int cnt = 0;
  vector<long long> t;
  for (int i = 0; i < N; i++){
    if (is_cube(s[i])){
      cnt++;
    } else {
      t.push_back(s[i]);
    }
  }
  int ans = 0;
  if (cnt >= 1){
    ans++;
  }
  map<long long, int> A;
  map<long long, int> B;
  map<pair<long long, long long>, int> C;
  int M = t.size();
  for (int i = 0; i < M; i++){
    long long t2 = t[i];
    for (long long j = 2; j * j * j <= t[i]; j++){
      while (t2 % (j * j * j) == 0){
        t2 /= j * j * j;
      }
    }
    t[i] = t2;
    long long c = is_square(t[i]);
    if (c != -1){
      B[c]++;
    } else {
      long long mx = -1;
      for (long long j = 2; j * j * j <= t[i]; j++){
        if (t[i] % j == 0 && is_square(j) == -1 && is_square(t[i] / j) != -1){
          mx = max(mx, is_square(t[i] / j));
        }
        if (t[i] % (j * j) == 0 && is_square(t[i] / (j * j)) == -1){
          mx = max(mx, j);
        }
      }
      if (mx != -1){
        C[make_pair(mx, t[i] / (mx * mx))]++;
      } else {
        A[t[i]]++;
      }
    }
  }
  set<long long> val;
  for (auto P : A){
    val.insert(P.first);
  }
  for (auto P : B){
    val.insert(P.first);
  }
  for (long long x : val){
    ans += max(A[x], B[x]);
  }
  set<pair<long long, long long>> val2;
  for (auto P : C){
    long long x = P.first.first;
    long long y = P.first.second;
    val2.insert(make_pair(min(x, y), max(x, y)));
  }
  for (auto P : val2){
    long long x = P.first;
    long long y = P.second;
    ans += max(C[make_pair(x, y)], C[make_pair(y, x)]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 22524
package main

import (
	"fmt"
)

func main()  {
	var n int

	fmt.Scan(&n)
	a := make([]int64, n)

	for i := range a {
		fmt.Scan(&a[i])
	}

	x :=  a[0]
	for i:=1;i<n;i++ {
		x = gcd(x, a[i])
		//fmt.Println(x)
	}
	fmt.Println(x)
}

func gcd(x int64, y int64) int64 {
	if x < y {
		x, y = y, x
	}

	if z := x%y; z == 0 {
		return y
	} else {
		return gcd(y, z)
	}
}

Measured memory_bytes: 5504
n = int(input())

a = list(map(int, input().split()))

# 累積和を求める
for i in range(n-1):
        a[i+1] += a[i]

#真ん中の仕切りを固定し、左右の配列についてさらに仕切りを動かして確認する
#累積和なので単調増加だから、左右の二つの配列について、仕切りを追加したときに差が最も小さい仕切りの位置を保存
l = 0
r = 2
ans = float("inf")
#mは真ん中の仕切りの位置
for m in range(1, n-1):
        #累積和が単調増加だから、mを固定したとき2a[l]-a[m]も単調増加で、lを増加させていくと徐々に減少しlとl+1で逆転する部分を左の仕切りとする。
        #2倍しないと累積和が単調増加のためずっと右辺が小さいままになる
        #部分配列の平均値に近い部分を二分探索で探すことも可能だが、平均計算処理と探索処理に加え、候補がbisectで求めた位置の前後も含まれるのでめんどくさい
        while abs(2*a[l] - a[m]) > abs(2*a[l+1] - a[m]): 
                l += 1
        while abs(2*a[r] - a[n-1] - a[m]) > abs(2*a[r+1] - a[n-1] - a[m]):
                r += 1

        bcde = [a[l], a[m]-a[l], a[r]-a[m],  a[n-1]-a[r]]
        ans = min(ans, max(bcde)-min(bcde))
print(ans)


Measured memory_bytes: 24680
#include <iostream>
#include <cstdlib>
#include <climits>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    
    int h[n+5];
    
    for (int i=1; i<=n; ++i) {
        cin >> h[i];
    }

    int dp[n+1];

    dp[0] = dp[1] = 0;

    for(int i=2; i<=min(k+1,n); ++i) {
        dp[i] = abs( h[1] - h[i] );
    }

    for(int i=k+2; i<=n; ++i) {
        int ans = INT_MAX;
        for(int j=1; j <= k; j++) {
            ans = min(ans, abs(h[i] - h[i-j]) + dp[i-j]);
        }
        dp[i] = ans;
    }
    cout << dp[n] << '\n';
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int n;
    cin >> n;

    vector<int> v(n);
    REP(i, n){
        cin >> v[i];
        if(v[i] > 12) v[i] = 24 - v[i];
    }

    sort(all(v));

    vector<int> u;
    u.push_back(0);

    REP(i, n){
        if(i%2 == 0){
            u.push_back(v[i]);
        }else{
            u.push_back(24 - v[i]);
        }
    }

    u.push_back(24);
    sort(all(u));

    int ans = 1e9;

    REP(i, n+1){
        chmin(ans, abs(u[i+1] - u[i]));
    }

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


Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <queue>
#define MAX_H 1000
#define MAX_W 1000
using namespace std;

typedef pair<int,int> P; // x,y(j,i)

int H,W,N;
char f[MAX_H][MAX_W];
int min_dist[10][10]; // distance from S,1,...,9 to S,1,...,9
P pos[10]; // position of S,1,..,9

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

bool isvalid(int x, int y) {
    return (0 <= x && x < W && 0 <= y && y < H);
}

void calcDist() {
    int visit_dist[MAX_H][MAX_W];
    memset(min_dist,0,sizeof(min_dist));
   for(int k=0;k<=N;k++) { // start pos
       queue< P > Q;
       Q.push(pos[k]);
        memset(visit_dist,0,sizeof(visit_dist));
        visit_dist[pos[k].second][pos[k].first] = 1;
       while(!Q.empty()) {
           P p = Q.front(); Q.pop();
           int dist = visit_dist[p.second][p.first];
           char ch = f[p.second][p.first];
           if(ch == 'X') continue;

           if(ch == 'S') {
              min_dist[k][0] = dist; 
           } else if('1' <= ch && ch <= '9') {
               min_dist[k][ch - '0'] = dist;
           }

           for(int i=0;i<4;i++) {
               int x = p.first + dx[i];
               int y = p.second + dy[i];
               if (isvalid(x,y) && !visit_dist[y][x]) {
                   visit_dist[y][x] = dist + 1;
                   Q.push(make_pair(x,y));
               }
           }
       }
   } 
}

void solve() {
    calcDist();

    int ans = 0;
    for(int i=1;i<=N;i++) {
        ans += min_dist[i-1][i];
    }
    ans -= N;
    if(ans < 0) ans = 0;
    cout << ans << endl;
}

main() {
    cin>>H>>W>>N;
    for(int i=0;i<H;i++) {
        for(int j=0;j<W;j++) {
            cin>>f[i][j];
            if(f[i][j] == 'S') {
                pos[0] = make_pair(j,i);
            } else if('1' <= f[i][j] && f[i][j] <= '9') {
                pos[f[i][j] - '0'] = make_pair(j,i);
            }
        }
    }
    solve();
}

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

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;

#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
constexpr auto INF = 4000000000; //4*10^9;
constexpr auto MOD = 1000000007; //10^9+7;


vi a(1000), b(1000);
int dp[1010][10010];

int main()
{
	vi a(1000), b(1000);
	int dp[1010][10010];
    int h,n;
    cin >> h >> n;

    rep(i, n)cin >> a[i] >> b[i];

    rep(i, 110) dp[i][0] = 0;

    rep(i, n) {
        for (int j = 1;j <= h;j++) {
            if (i == 0) dp[i][j] = ((j + a[0] - 1) / a[0]) * b[0];
            else dp[i][j] = min(dp[i - 1][j], dp[i][max(j - a[i], 0)] + b[i]);
        }
        
    }
    cout << dp[n - 1][h] << endl;
}

Measured memory_bytes: 39424
#include<bits/stdc++.h> 
//#include<atcoder/all>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;
//using namespace atcoder;
typedef long long ll;

int main(){
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << x2 + y1 - y2 << " " << y2 + x2 - x1 << " "
    << x1 + y1 - y2 << " " << y1 + x2 - x1 << endl;
}

Measured memory_bytes: 3588
Ss = input()

lenS = len(Ss)
i = 0
while i < lenS:
    if Ss[i:].startswith('dream'):
        if Ss[i + 5:i + 7] == 'er' and Ss[i + 7:i + 8] != 'a': # dreamer
            i += 7
        else: # dream
            i += 5
    elif Ss[i:].startswith('erase'):
        if Ss[i + 5:i + 6] == 'r': # eraser
            i += 6
        else: # erase
            i += 5
    else:
        print('NO')
        break
else:
    print('YES')


Measured memory_bytes: 3188
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"
#include "set"
#include "stack"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
typedef long long ll;
using namespace std;

int n, m, a, b, mem;
vector<int>v[100000];
vector<int>r;
bool vtd[100000], flag;

int dfs(int x) {
	vtd[x] = true;
	r.push_back(x);
	lp(v[x].size()) {
		if (vtd[v[x][i]] == false) {
			dfs(v[x][i]);
			return 0;
		}
	}
	return 0;
}
int main() {
	cin >> n >> m;
	lp(m) {
		cin >> a >> b;
		v[a - 1].push_back(b - 1);
		v[b - 1].push_back(a - 1);
	}
	lp(n)
		vtd[i] = false;
	dfs(0);
	dfs(0);
	cout << r.size()-1 << endl;
	for (int i = r.size() - 1; r[i] != 0; i--)
		cout << r[i]+1 << sp;
	cout << 1 << sp;
	for (int i = 1; r[i] != 0; i++)
		cout << r[i]+1 << sp;
	cout << endl;
	return 0;
}


Measured memory_bytes: 9720
N = int(input())
B = list(map(int, input().split()))

A = []

for i in range(N):
    if i == 0:
        A.append(B[0])
    elif i == N - 1:
        A.append(B[-1])
    else:
        A.append(min(B[i-1], B[i]))

print(sum(A))

Measured memory_bytes: 9100
import bisect
n = int(input())
ary = [sorted(map(int,input().split())) for _ in range(3)]
ans = 0
for i in range(n):
    a = bisect.bisect_left(ary[0],ary[1][i])
    b = n - bisect.bisect_right(ary[2],ary[1][i])
    ans += a*b
print(ans)

Measured memory_bytes: 22720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vp;
typedef map<ll, ll> mll;
typedef map<string, ll> mstrll;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep,)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
#define out(x) cout << (x)
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
ll a, b, c, d, e, f, g, i, n, m, x, y, z, w, h, ans, cnt, mx, mn;
string s, t;
vll dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
//vll dx = {-1, 0, 1, -1, 1, -1, 0, 1}, dy = {-1, -1, -1, 0, 0, 1, 1, 1};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> h >> w){
        ll l1 = h / 3, l2 = (h - l1) / 2, l3 = h - l1 - l2;
        a = w * (max({l1, l2, l3}) - min({l1, l2, l3}));
        l2 = w / 2, l3 = w - l2;
        b = max({w * l1, (h - l1) * l2, (h - l1) * l3}) - min({w * l1, (h - l1) * l2, (h - l1) * l3});

        l1++, l2 = (h - l1) / 2, l3 = h - l1 - l2;
        c = w * (max({l1, l2, l3}) - min({l1, l2, l3}));
        l2 = w / 2, l3 = w - l2;
        d = max({w * l1, (h - l1) * l2, (h - l1) * l3}) - min({w * l1, (h - l1) * l2, (h - l1) * l3});

        l1 = w / 3, l2 = (w - l1) / 2, l3 = w - l1 - l2;
        e = h * (max({l1, l2, l3}) - min({l1, l2, l3}));
        l2 = h / 2, l3 = h - l2;
        f = max({h * l1, (w - l1) * l2, (w - l1) * l3}) - min({h * l1, (w - l1) * l2, (w - l1) * l3});

        l1++, l2 = (w - l1) / 2, l3 = w - l1 - l2;
        g = h * (max({l1, l2, l3}) - min({l1, l2, l3}));
        l2 = h / 2, l3 = h - l2;
        i = max({h * l1, (w - l1) * l2, (w - l1) * l3}) - min({h * l1, (w - l1) * l2, (w - l1) * l3});
        print(min({a, b, c, d, e, f, g, i}));
    }
}



Measured memory_bytes: 256
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()

    # tmp = 1
    # for i in range(k):
    #     tmp *= a[i]
    #
    # prev = tmp

    for i in range(k, n):
        # crnt = (prev // a[i - k]) * a[i]

        print("Yes" if a[i] > a[i-k] else "No")
        # prev = crnt


if __name__ == '__main__':
    main()


Measured memory_bytes: 33940
#126
from math import ceil, log
n, k = list(map(int, input().split(' ')))
rate = 0
for i in range(1,n+1):
    x = ceil(log(k/i, 2))
    if x < 0:
        x = 0
    rate += (1/n)*(1/2)**x
print(rate)

Measured memory_bytes: 3060
N = int(input())
S = list(map(str, input()))

dp = [[0 for _ in range(N)] for _ in range(N)]
edge_r = N - 1
edge_d = N - 1
for i in reversed(range(N)):
	for j in reversed(range(N)):
		if i == edge_d or j == edge_r:
			if S[i] == S[j]:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
		else:
			if S[i] == S[j]:
				dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
	for j in range(N):
		if i >= j:
			continue
		# ij間の距離よりもdp[i][j]が大きいならば、それはかぶってる
		tmp = min(dp[i][j], j - i)
		ans = max(tmp, ans)
		
print(ans)

Measured memory_bytes: 248072
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef long double db;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int main() {
	int l,r,d; scanf("%d%d%d",&l,&r,&d);
	int g=0;
	if(l%d==0) ++g;
	printf("%d\n",(r/d-l/d)+g);
}


Measured memory_bytes: 3820
#include<iostream>
#include<cstdio>
#include<queue>
#define INF 100000000
using namespace std;

typedef pair<int,int> P;
typedef pair<P,P> P2;

int main(){
  int w,h;
  char grid[100][50];
  int d[2][100][50];
  int dy[] = {-2,-1,0,1,2,-1,0,1,0} , dx[] = {1,1,1,1,1,2,2,2,3};

  while(scanf("%d%d",&w,&h), w||h){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)
	scanf(" %c ",&grid[i][j]);

    priority_queue<P2,vector<P2>,greater<P2> > q;

    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	if(grid[i][j] == 'S'){
	  d[0][i][j] = d[1][i][j] = 0;
	  q.push(P2(P(0,0),P(i,j)));
	  q.push(P2(P(0,1),P(i,j)));
	}else d[0][i][j] = d[1][i][j] = INF;
      }

    while(q.size()){
      P2 p = q.top();q.pop();
      int t = p.first.first, f = p.first.second;
      int y = p.second.first, x = p.second.second;

      if(grid[y][x] == 'T'){
	q.push(p);
	cout << t << endl;
	break;
      }

      for(int k=0;k<9;k++){
	int ty = y+dy[k], tx = !f?(x+dx[k]):(x-dx[k]);
	if(ty<0 || tx<0 || h<=ty || w<=tx)continue;
	if(d[1-f][ty][tx]<INF)continue;

	int tt;
	if('1'<=grid[ty][tx] && grid[ty][tx]<='9')tt = grid[ty][tx]-'0';
	else if(grid[ty][tx] == 'T')tt = 0;
	else tt = -1;

	if(tt>=0){
	  if(d[1-f][ty][tx] > t + tt){
	    d[1-f][ty][tx] = t+tt;
	    q.push(P2(P(t+tt,1-f),P(ty,tx)));
	  }
	}
      }
    }
    if(q.empty())cout << -1 << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int n, k, a[N];

bool cmp (int x, int y) {
	return abs(x) > abs(y);
}

int binpow (int a, int n) {
	int res = 1;
	while (n) {
		if (n % 2 == 1)
			res = res * a % mod;
		n /= 2;
		a = a * a % mod;
	}

	return res;
}


main () {
	cin >> n >> k;
	bool ok = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i]; 
		if (a[i] >= 0)
			ok = 1;
	}

	sort(a + 1, a + 1 + n, cmp);

	if (!ok || n == k) {
		if (k % 2 == 1)
			reverse(a + 1, a + 1 + n);
		int ans = 1;
		for (int i = 1; i <= k; ++i)
			ans = ans * a[i] % mod;
		cout << (ans + mod) % mod;
		return 0;
	}

	int cnt = 0, mn1 = inf + 1, mn2 = inf + 1, ans = 1;
	for (int i = 1; i <= k; ++i) {
		ans = ans * a[i] % mod;
		if (a[i] < 0) {
			++cnt; 
			mn1 = -a[i];
		} else
			mn2 = a[i];
	}



	if (cnt % 2 == 1) {
		int mx1 = -1, mx2 = -1;
		for (int i = k + 1; i <= n; ++i) {
			if (a[i] < 0)
				mx1 = max(mx1, -a[i]);
			if (a[i] >= 0)
				mx2 = max(mx2, a[i]);
		}


		if (mn2 > inf || mx1 < 0 || (mn1 <= inf && mx2 > -1 && mn2 * mx2 > mn1 * mx1)) {
			ans = ans * binpow(mod - mn1, mod - 2) % mod;
			ans = ans * mx2 % mod;			
		} else {
			ans = ans * binpow(mod - mn2, mod - 2) % mod;
			ans = ans * mx1 % mod;
		}
	}

	cout << (ans + mod) % mod;
}
	
        	
//check for the constants

                                                                                   	

                                  

Measured memory_bytes: 5140
#include<iostream>

int main() {
	int N = {};// 商品代金
	int change={};//お釣り
	int Min_value = 1;//下限値
	int Max_value = 10000;//上限値
	std::cin >> N ;

	if (Min_value > N || N > Max_value) {
		std::cout << "予算を10000円を超えてます！" << std::endl;
	}

	while (N >= 1000)
	{
		if (N == 1000) {
			change = 0;
			std::cout << change << std::endl;
			return 0;
		}

		N=N - 1000;

	}

	change = 1000-N;
	std::cout << change << std::endl;


}

Measured memory_bytes: 3632
from collections import deque

n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

dist = [-1 for _ in range(n)]
dist[0] = 0
q = deque()
q.append(0)
while q:
    v = q.popleft()
    for nv, w in edges[v]:
        if dist[nv] != -1: continue
        dist[nv] = dist[v] + w
        q.append(nv)

for i in range(n):
    if dist[i] % 2:
        print(1)
    else:
        print(0)

Measured memory_bytes: 74016
#include <iostream>
using namespace std;
int main(void){
    int k,s,i,j,ans=0;
    cin >> k >> s;
    for(i=0;i<=k;i++){
        for(j=0;j<=k;j++){
            if(i+j<=s and s-i-j<=k) ans++;
        }
    }
    cout << ans;
}

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

using namespace std;

int main(){
    int64_t t1, t2;
    cin >> t1 >> t2;
    int64_t a1, a2, b1, b2;
    cin >> a1 >> a2 >> b1 >> b2;
    int64_t c1 = a1 * t1, c2 = a2 * t2, d1 = b1 * t1, d2 = b2 * t2;
    if (c1 + c2 == d1 + d2){
        cout << "infinity" << endl;
        return 0;
    }

    if (c1 < d1){
        swap(c1, d1);
        swap(c2, d2);
    }

    if (c1 + c2 > d1 + d2){
        cout << 0 << endl;
        return 0;
    }

    int64_t d = d1 + d2 - (c1 + c2);
    int64_t ans = 2 * ((c1 - d1) / d) - 1;
    int64_t a = 0, b = ((c1 - d1) / d) * d;
    a += c1;
    b += d1;
    if (a == b){
        ans++;
    }
    else if (a > b){
        ans++;
        a += c2;
        b += d2;
        if (a < b)
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>
#include <cctype>
#include <climits>
#include <list>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int N; cin>>N;
  if(N==1) {
    cout << "Hello World" << endl;
  } else if(N==2) {
    int a,b; cin>>a>>b;
    cout << a+b << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int MAXN = 2e5+10;
int n, p;
string s;

ll pref[MAXN];

int main(){
  cin.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> p;
  cin >> s;
  reverse(s.begin(), s.end());
  // we want to know, what difference of prefix sums from (i,j) /10^i = 0
  // if p != 2 and p != 5, the divide part makes no difference.
  // If p==2 or p==5, this question is easy.
  pref[0] = 0;
  ll pten = 1;
  for(int i=0;i<n;i++) {
    pref[i+1] = (pref[i] + pten*(s[i]-'0'))%p;
    pten = pten*10%p;
    //cerr << pref[i+1] <<endl;
  }
  ll cnt = 0;
  for(int i=0;i<n;i++) {
    if (p==2 && (s[i]-'0')%2==0) {
      cnt += n-i;
    }
    if (p==5 && (s[i]-'0')%5==0) {
      cnt += n-i;
    }
  }
  if (p!=2 && p!=5) {
    map<int, int> occ;
    for(int i=n;i>=0;i--) {
      // now we need to count if we minus pref[i], how prefs are equal 
      cnt+=occ[pref[i]];
      // Add pref for future use
      occ[pref[i]]++;
    }
  }
  cout << cnt <<endl;
}


Measured memory_bytes: 2452
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

int n,m;

int main() {
    cin >> n >> m;
    vector<int> used(n+10,0);
    vector<int> in(m);
    for(int i=0;i<m;i++) cin >> in[i];
    for(int i=m-1;i>=0;i--){
        if(used[in[i]]==1) continue;
        cout << in[i] << endl;
        used[in[i]] = 1;
        //cout << "used " << in[i] << " " << used[in[i]] << endl;
    }
    //for(int i=1;i<=n;i++) cout << i << " " << used[i] << endl;
    for(int i=1;i<=n;i++){
        if(!used[i]) cout << i << endl;
    }

    return 0;
}

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



int main()
{
    ios_base::sync_with_stdio(false);

    long long int i,j,k,a,b,c,d,e,n,m,v;
    cin>>n>>m;
    long long int ar[n+1],ar2[n+1];
    memset(ar,0,sizeof(ar));
    memset(ar2,0,sizeof(ar2));
    c=0;
    d=0;
    for(i=1;i<=m;i++)
    {
        cin>>a;
        string s;
        cin>>s;


        if(s=="AC")
        {
            if(ar[a]!=1){
                c++;
                ar[a]=1;
                d+=ar2[a];
            }
        }
        else
        {
            if(ar[a]!=1){
               ar2[a]++;
            }
        }
    }
    cout<<c<<" "<<d<<"\n";
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
  ll n, ans = 0;
  cin >> n;
  vector<ll> a(n);
  for(ll i = 0; i < n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  for(ll i = 0; i < n; i++) for(ll j = i + 1; j < n; j++) for(ll k = j + 1; k < n; k++) if(a[i] + a[j] > a[k]) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
 
bool flag[100001];
ll int ans[100001];
ll int mod = 1000000007;
int main(){
  int n, m;
  cin >> n >> m;
  REP(i, n+1){
    flag[i] = false;
    ans[i] = 0;
  }
  REP(i, m){
    int t;
    cin >> t;
    flag[t] = true;
  }
  ans[0] = 1;
  REP(i, n){
    if(flag[i]) continue;
    if(i + 1 <= n) ans[i+1] = ((ans[i] + ans[i+1]) % mod);
    if(i + 2 <= n) ans[i+2] = ((ans[i] + ans[i+2]) % mod);
    // cout << ans[i] << endl;
  }
  cout << ans[n] << endl;

}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>
int needleX[4] = { -1,0,1,0 };
int needleY[4] = { 0,1,0,-1 };

int main(void) {
    int N,X;
    std::cin >> N >> X;
    int ans =N,input,cost=0,mincost=9999999;
    for(int i=0;i<N;i++){
        std::cin >> input;
        cost+=input;
        mincost=std::min(mincost,input);
    }
    ans+=(X-cost)/mincost;
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <deque>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define eb emplace_back
#define ep emplace
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2 vector<vec>
#define vecll2 vector<vecll>
#define vec3 vector<vec2d>
#define vecll3 vector<vecll2d>
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(vector<T> v){for(T e:v)cout<<e<<" ";cout<<endl;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}
const ll INF=1e17;

double dp[700],p[700];
int sz[700];
main(){
    int n=in();
    int m=in();
    vec2 G(n);
    rep(i,m){
        int a=in()-1;
        int b=in()-1;
        G[a].pb(b);
        sz[a]++;
    }
    dp[n-1]=0;
    rep3(i,n-2,0){
        for(auto e:G[i]){
            dp[i]+=dp[e]/sz[i];
        }
        dp[i]+=1.0;
    }
    double ans=dp[0];
    p[0]=1;
    rep(i,n){
        for(auto e:G[i]){
            p[e]+=p[i]/sz[i];
        }
    }
    double tmp=dp[0];
    // print(p);
    rep(i,n){
        if(G[i].size()==1)continue;
        double sum=0;
        double mx=0.0;
        for(auto e:G[i]){
            sum+=(dp[e]+1);
            chmax(mx,dp[e]+1);
        }
        double P=p[i]/sz[i];
        double t=tmp-P*mx;
        P/=(double)(sz[i]-1);
        t+=P*(sum-mx);
        chmin(ans,t);
    }
    std::printf("%.10f",ans);
}

Measured memory_bytes: 1408
h, w = map(int, input().split())
T = [[] for i in range(h)]
S = [[0] * w for i in range(h)]
for i in range(h):
    a = list(map(int, input().split()))
    T[i] = a

for i in range(h):
    for j in range(w):
        T[i][j] = T[i][j] % 2

move = []
i = 0
j = 0
k = 0
flag = False
while True:
    px, py = i, j
    if T[i][j] == 1:
        flag = True
    if i % 2 == 0:
        j += 1
        if j == w:
            j -= 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False
        k += 1
    else:
        j -= 1
        if j == -1:
            j += 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False

print(len(move))
for i in range(len(move)):
    x, y, w, z = move[i][0] + 1, move[i][1] + 1, move[i][2] + 1, move[i][3] + 1
    print(x, y, w, z)


Measured memory_bytes: 24668
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define MAX(a,b) a=a>b?a:b
#define MIN(a,b) a=a<b?a:b
#define REP(i,x,n) for(int i=x;i<n;i++)
#define REPR(i,x,n) for(int i=n-1;i>=x;i--)
#define pb  push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLr(obj) (obj).rbegin(), (obj).rend()
#define endl "\n"
#define F first
#define S second
#define EN cout<<endl;
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll,ll,ll> PP;
typedef tuple<ll,ll,ll,ll> PPP;
const ll mod=1000000007;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void yes(T b){if(b)out("yes");else out("no");}
template<class T> void Yes(T b){if(b)out("Yes");else out("No");}
template<class T> void YES(T b){if(b)out("YES");else out("NO");}
template<class T> void no(T b){if(b)out("no");else out("yes");}
template<class T> void No(T b){if(b)out("No");else out("Yes");}
template<class T> void NO(T b){if(b)out("NO");else out("YES");}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll modpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
 


int main(){
    ll n;cin>>n;
    
    map<string,ll>m;
    m["AC"]=0;
    m["RE"]=0;
    m["WA"]=0;
    m["TLE"]=0;
    rep(i,n){
        string s;cin>>s;
        m[s]++;
    }
    cout<<"AC x "<<m["AC"]<<endl;
    cout<<"WA x "<<m["WA"]<<endl;
    cout<<"TLE x "<<m["TLE"]<<endl;
    cout<<"RE x "<<m["RE"]<<endl;


    
}


Measured memory_bytes: 3608