akhauriyash/Code-Regression huggingface dataset:
H,W=map(int,input().split())
s=[0 for i in range(0,H)]
for i in range(0,H):
    s[i]=input().split()

black=[(i,j) for i in range(0,H) for j in range(0,W) if s[i][0][j]=='#']

flag=0
for i in range(0,H):
    for j in range(0,W):
        if (i,j) in black:
            if not ((i+1,j) in black or (i,j+1) in black or (i-1,j) in black or (i,j-1) in black):
                flag=1
if flag==0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 39664
///
// File:  d.cpp
// Author: ymiyamoto
//
// Created on Tue Apr 17 22:07:09 2018
//
#include <bits/stdc++.h>
using namespace std;

#define rep(_n, _init, _N) for (int32_t _n = _init; _n < (int32_t)(_N); _n++)
#define rrep(_n, _N, _end) for (int32_t _n = (int32_t)(_N); _n >= _end; _n--)
#define iceil(_x, _y) (((_x) + (_y)-1) / (_y))
#define ifloor(_x, _y) ((_x) / (_y))

static const double pi = 2 * asin(1);
static const double precision = 10e-9;

int32_t main()
{
  int32_t N, K;
  cin >> N >> K;

  vector<int32_t> arr(N + 1);
  arr[0] = 0;
  for (int32_t i = 1; i <= N; i++) {
    cin >> arr[i];
  }
  sort(arr.begin(), arr.end());

  int32_t left = 0;
  int32_t right = N + 1;
  while (left + 1 < right) {
    vector<vector<bool>> dp(N + 1, vector<bool>(K + 1));
    dp[0][0] = true;

    int32_t mid = (left + right) / 2;
    for (int32_t num = 1; num <= N; num++) {
      if (num == mid) {
        dp[num] = dp[num - 1];
      } else {
        for (int32_t val = 0; val <= K; val++) {
          if ((val - arr[num]) >= 0) {
            dp[num][val] = dp[num][val] || dp[num - 1][val - arr[num]];
          }
          dp[num][val] = dp[num][val] || dp[num - 1][val];
        }
      }
    }

    bool found = false;
    for (int32_t i = max(0, K - arr[mid]); i < K; i++) {
      if (dp[N][i]) {
        found = true;
      }
    }

    if (found) {
      right = mid;
    } else {
      left = mid;
    }
  }

  cout << left << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>

#define N 100000

int main() {
	static int hh[N];
	int n, i, cnt, max;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &hh[i]);
	max = cnt = 0;
	for (i = n - 2; i >= 0; i--) {
		if (hh[i] >= hh[i + 1])
			cnt++;
		else
			cnt = 0;
		if (max < cnt)
			max = cnt;
	}
	printf("%d\n", max);
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int INF=1e9;
int N;int L[size];
int binary(int l){
	int a=0,b=N;
	while(b-a>1){
		if(L[(a+b)/2]<l) a=(a+b)/2;
		else b=(a+b)/2;
	}return a;
}
int main(){
	cin>>N;
	rep(i,0,N) cin>>L[i];
	sort(L,L+N);
	int ans=0;
	rep(i,0,N){
		rep(j,0,i){
			ans+=max(binary(L[i]+L[j])-i,0);
            //cout<<L[i]+L[j]<<" "<<binary(L[i]+L[j])<<endl;
		}
	}cout<<ans<<endl;
}
//63 64 68 69 70
/*タスクを並列に行う
x=(x ? true : false)
sorted
auto it=lower_bound(v.begin(),v.end(),w) v[it-v.begin()]>=w
auto it=upper_bound(v.begin(),v.end(),w) v[it-v.begin()]>w
void func(int* vec){}
puts(string) cout<<string<<endl;
1.*a/b int to double
(int)a-48 char to int
(char)(i+97) int to char
stoi(s) string to int
stoll(s)
cout.precision(16);
cout<<fixed<<a;
printf("%.6lf\n",a);
accumulate(a,a+n,0);
*/

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

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

    ll ans_o = 0, sum_o = 0;
    ll ans_e = 0, sum_e = 0;
    rep(i, n) {
        sum_o += a[i];
        sum_e += a[i];
        if (i % 2) {
            if (sum_o <= 0) ans_o += -sum_o + 1, sum_o = 1;
            if (sum_e >= 0) ans_e += sum_e + 1, sum_e = -1;
        } else {
            if (sum_o >= 0) ans_o += sum_o + 1, sum_o = -1;
            if (sum_e <= 0) ans_e += -sum_e + 1, sum_e = 1;
        }
    }
    cout << min(ans_o, ans_e) << endl;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define ALL(v) v.begin(), v.end()
#define N 100007
#define INF 1000000007
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll fceil(ll a, ll b) { return (a % b == 0 ? a / b : a / b + 1); }
int main()
{
   int n;
   string s, ans = "Yes";
   cin >> n >> s;
   if (n %2 == 1)
      ans = "No";
   FOR(i, 0, n / 2)
   {
      if (s[i] != s[i + n / 2])
      {
         ans = "No";
         break;
      }
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
signed main(){
    ll n;cin>>n;
    vector<ll>a(n),b(n);
    rep(i,n){
        cin>>a[i]>>b[i];
    }
    ll cnt=0;
    for(int i=n-1;i>=0;i--){
        a[i]+=cnt;
        if(a[i])cnt+=((a[i]-1)/b[i]+1)*b[i]-a[i];
    }
    cout<<cnt<<endl;
}

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

int main() {
    int64_t a, b, c, k, ans = 0;
    cin >> a >> b >> c >> k;
    ans = min(a, k) - max(k - (a + b), 0L);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>

using namespace std;
#define mod 1000000007
#define ll long long 


ll dp[1009][1009];
int n, m;

char arr[1009][1009];

ll solve(int i, int j) {
	if(i == n - 1 && j == m - 1)
		return 1;

	if(dp[i][j] != -1)
		return dp[i][j];

	int ans = 0;
	if(i + 1 < n && arr[i + 1][j] == '.'){
		ans += solve(i + 1, j);
		ans %= mod;
	}
	if(j + 1 < m && arr[i][j + 1] == '.') {
		ans += solve(i, j + 1);
		ans %= mod;
	}
	return dp[i][j] = ans % mod;
}


int main() {
  	cin>>n>>m;
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin>>arr[i][j];

	cout<<solve(0, 0)%mod<<endl;

  	// memset(dp, -1, sizeof(dp));
  	// cout<<solve(0, 0)<<endl;

}

Measured memory_bytes: 9216
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a=sc.nextInt();
    int b=sc.nextInt();
    int answer = 0;
    
    if(2*b>=a){
      answer=0;
    }else{
      answer = a-2*b;
    }
    System.out.println(answer);
  }
  

  
}


Measured memory_bytes: 25172
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N, Q;
	cin >> N >> Q;
	string s;
	cin >> s;
	vector<char> t(Q);
	vector<char> d(Q);
	for(int i = 0; i < Q; i += 1)
	{
		cin >> t[i] >> d[i];
	}

	int left = 0, right = N - 1;
	for(int i = Q - 1; i >= 0; i -= 1)
	{
		if(s[left] == t[i] && d[i] == 'L')
		{
			left += 1;
		}
		else if(s[right] == t[i] && d[i] == 'R')
		{
			right -= 1;
		}

		if(left > 0 && s[left - 1] == t[i] && d[i] == 'R')
		{
			left -= 1;
		}
		else if(right < N - 1 && s[right + 1] == t[i] && d[i] == 'L')
		{
			right += 1;
		}

		if(left > right)
			break;
	}

	std::cout << std::to_string(right - left + 1) << std::endl;
	return 0;
}

Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep2(i, x, n) for (int i = x; i < n; ++i)

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

    int l = 1;
    int r = n;
    rep(i,m)
    {
        int li,ri;
        cin >> li >> ri;
        l = max(l, li);
        r = min(r, ri);

        if(l>r) break;
    }

    cout << max(r-l+1,0) << endl;
    return 0;
}

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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

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

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b; 
}

int main(){
 int N, K, S;
 cin >> N >> K >> S;
   
      REP(i, N){
         if (i >= K)
         {
            if(S == 1e9) cout << 1 << ' ';
            else cout << S + 1 << ' ';
         }
         else
         {
            cout << S << ' ';
         }
      }
   

cout << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h> 
 
#define INF (1<<31) - 1 //INT_MAX/2
#define MOD 1000000007
#define PI  acos(-1)
 
using ll  = long long;
using ull = unsigned long long;

int main(int argc, char *argv[])
{
    std::string s1, s2, s3;
    std::cin >> s1 >> s2 >> s3;

    std::transform(s1.begin(), s1.end(), s1.begin(), toupper);
    std::transform(s2.begin(), s2.end(), s2.begin(), toupper);
    std::transform(s3.begin(), s3.end(), s3.begin(), toupper);

    std::cout << s1[0] << s2[0] << s3[0] << std::endl;
    return 0;
}

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

int main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    int water_max = 0;
    int sugar_max = 0;
    double conc_max = 0;
    int water, sugar;
    double conc;
    for (int i = 0; 100 * A * i <= F; i++) {
        for (int j = 0; 100 * A * i + 100 * B * j <= F; j++) {
            if (i + j != 0) {
                for (int k = 0; 100 * A * i + 100 * B * j + C * k <= F; k++) {
                    for (int l = 0; 100 * A * i + 100 * B * j + C * k + D * l <= F; l++) {
                        water = 100 * A * i + 100 * B * j;
                        sugar = C * k + D * l;
                        if (water + sugar <= F && 100.0 * sugar / water <= E) {
                            conc = 100.0 * sugar / (water + sugar);
                            if (conc >= conc_max) {
                                conc_max = conc;
                                water_max = water;
                                sugar_max = sugar;
                            }
                        }
                    }
                }
            }
        }
    }
    cout << water_max + sugar_max << " " << sugar_max << endl;
}


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


#define int long long 


const int N = 2e5 + 7, mod = 1e9 + 7;


int a[N], w[N], c[N], pwr[N];

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; string str; cin >> str; n = str.size();
	pwr[0] = 1;
	for(int i = 1; i <= n; i++) {
		a[i] = a[i - 1] + (str[i - 1] == 'A');
		w[i] = w[i - 1] + (str[i - 1] == '?');
		c[i] = c[i - 1] + (str[i - 1] == 'C');
		pwr[i] = (pwr[i - 1] * 3) % mod;
	}

	int ans = 0;

	for(int i = 1; i <= n; i++) if(str[i - 1] == 'B' || str[i - 1] == '?') {
		int lsum = pwr[w[i - 1]] * a[i - 1] % mod;
		if(w[i - 1]) {
			lsum += pwr[w[i - 1] - 1] * w[i - 1] % mod;
			lsum %= mod;
		}
		int rsum = pwr[w[n] - w[i]] * (c[n] - c[i]) % mod;
		if(w[n] - w[i]) {
			rsum += pwr[w[n] - w[i] - 1] * (w[n] - w[i]) % mod;
			rsum %= mod;
		}
		ans += lsum * rsum % mod;
		ans %= mod;
	}

	cout << ans << endl;
}

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

public class Main {

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

	static String[] dow = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

	static boolean solve() {
		int m = in.nextInt();
		int d = in.nextInt();
		if (m + d == 0) return false;

		out.println(dow[calculateDayOfWeek(2004,m,d)]);

		return true;
	}

	public static int calculateDayOfWeek(int y, int m, int d) {
		if (m <= 2) {
			y--; m += 12;
		}
		return (y+y/4-y/100+y/400+(13*m+8)/5+d)%7;
	}

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

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

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

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

Measured memory_bytes: 25948
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#if defined(DAIJOBU)
#include "/home/ichigo/includes.hpp"
#include "/home/ichigo/debug.hpp"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long lint;
typedef vector<lint> vlint;
typedef vector<vlint> vvlint;
typedef pair<lint, lint> plint;
typedef double ld;

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



int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	if(n < 1000)puts("ABC");
	else puts("ABD");
	return 0;
}



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

int main(){
  int a,b;
  char tmp;

  while(1){
    tmp = getchar();
    if(tmp=='0')break;

    for(int i=0;i<3;i++){
      a = 0;
      b = 0;
      while(1){
	tmp = getchar();
	if(tmp=='\n')break;
	else if(tmp == 'A')a++;
	else b++;
      }
      if(i==2)break;
      tmp = getchar();;
      if(tmp == 'A')a++;
      else b++;
      cout << a << " " << b << endl;
    }
    if(a<10 && b==10)b++;
    else if(b<10 && a==10)a++;
    else if(a>b)a++;
    else b++;
    cout << a << " " << b << endl;
  }
}

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;

vi D;
vvpi G;
vi vist, C;

void dfs(int x, int val, int col) {
  vist[x] = col;
  for (auto it : G[x]) {
    int y = it.first;
    if (D[y] == val and vist[y] == -1) {
      C[it.second] = val;
      dfs(y, val, col^1);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n , m;
  cin >> n >> m;
  D = vi(n);
  G = vvpi(n);
  vpi V(n);
  for (int i = 0; i < n; ++i) {
    cin >> D[i];
    V[i] = pi(D[i], i);
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    G[x].push_back(pi(y,i));
    G[y].push_back(pi(x,i));
  }
  sort(V.begin(), V.end());
  bool pots = true;
  C = vi(m, -1);
  vist = vi(n, -1);
  for (int i = 0; i < n; ++i) {
    int x = V[i].second;
    if (vist[x] != -1) continue;
    int minval = D[x] + 1;
    int minar = -1;
    int mincol = -1;
    int contt = 0;
    for (auto it : G[x]) {
      int y = it.first;
      if (D[y] < minval) {
        minar = it.second;
        minval = D[y];
        mincol = vist[y];
      }
      if (D[y] == D[x]) ++contt;
    }
    if (minval > D[x]) {
      pots = false;
      break;
    }
    else if (contt) {
      dfs(x, D[x], 0);
    }
    else {
      C[minar] = D[x];
      vist[x] = mincol^1;
    }
  }
  if (!pots) {
    cout << -1 << '\n';
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    if (vist[i]) cout << 'B';
    else cout << 'W';
  }
  cout << '\n';
  for (int i = 0; i < m; ++i) {
    if (C[i] == -1) cout << 1000000000 << '\n';
    else cout << C[i] << '\n';
  }

}


Measured memory_bytes: 13312
#include<bits/stdc++.h>
using namespace std;
#define LL long long

int n;
double dp[303][303][303];

double doit(int c1,int c2,int c3) {
    if (c1 == 0 && c2 == 0 && c3 == 0) {
		return 0;
    }
    if (dp[c1][c2][c3] > -1e-9) return dp[c1][c2][c3];

	int c0 = n-c1-c2-c3;
	dp[c1][c2][c3] = 0;
	if (c1 > 0) dp[c1][c2][c3] += c1*1.0/n*doit(c1-1,c2,c3);
	if (c2 > 0) dp[c1][c2][c3] += c2*1.0/n*doit(c1+1,c2-1,c3);
	if (c3 > 0) dp[c1][c2][c3] += c3*1.0/n*doit(c1,c2+1,c3-1);
	dp[c1][c2][c3] = (dp[c1][c2][c3]+1)/(1-c0*1.0/n);
	//printf("  %d,%d,%d,%d = %.4f\n",c0,c1,c2,c3,dp[c1][c2][c3]);
	return dp[c1][c2][c3];
}

int main() {
	scanf("%d",&n);
	int c[4];
	memset(c,0,sizeof(c));
	for (int i=0; i<n; i++) {
		int a;
		scanf("%d",&a);
		c[a]++;
	}
	for (int i=0; i<=n; i++)
		for (int j=0; j<=n; j++)
			for (int k=0; k<=n; k++)
				dp[i][j][k] = -1.0;
	printf("%.11f\n",doit(c[1],c[2],c[3]));
	return 0;
}


Measured memory_bytes: 217344
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String give = sc.next();
        int i=0;
        while(!(give.equals("END_OF_TEXT"))){
            if(give.equalsIgnoreCase(a)){
                i++;
            }
            give = sc.next();
        }
        System.out.println(i);
        sc.close();
    }
}


Measured memory_bytes: 26324
def func(N):
    return N%bin(N).count("1")

N = int(input())
X = input()

popcount = X.count("1")
X_num = int(X,2)

O = X_num%(popcount+1)
if popcount==1:
    I = 0
else:
    I = X_num%(popcount-1)

bO = 1
bI = 1

ans= []
for i in range(N):
    if X[-1-i]=="0":
        hoge = (O + bO)%(popcount+1)
    else:
        if popcount==1:
            ans.append(0)
            continue
        hoge = (I - bI)%(popcount-1)
    count = 1
    while hoge:
        hoge = func(hoge)
        count += 1
    ans.append(count)
    bO = (bO*2)%(popcount+1)
    if popcount != 1:
        bI = (bI*2)%(popcount-1)

for i in range(N):
    print(ans[-1-i])

Measured memory_bytes: 89748
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map> 
#include <map> 
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
using namespace std;
typedef long long LL;
 
int main() {
	int t, i, j, k;
	int a, b, c ,F=0;
	char A[100];
	
	cin >> A;
 
	cout << A[0] << A[1] << A[2] << A[3] << A[4] << " "
		<< A[6] << A[7] << A[8] << A[9] << A[10] << A[11] << A[12] << " "
		<< A[14] << A[15] << A[16] << A[17] << A[18]
		
		
		
		<< endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"_,a=open(0);b,c=zip(*[(abs(i),i<0)for i in map(int,a.split())]);print(sum(b)-sum(c)%2*min(b)*2)\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 22644
from sys import stdin
n,k = map(int,stdin.readline().split())
h = list(map(int,stdin.readline().split()))
dp = [0]
for i in range(1,n):
    x = 10**10
    for j in range(max(0,i-k),i):
        x = min(x,dp[j]+abs(h[j]-h[i]))
    dp.append(x)
print(dp[-1])

Measured memory_bytes: 90436
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int dp[1010][1010];
int bingo[3][3];
bool flag[3][3];
int cnt[2][105];

int main() {
	int n;
	cin >> n;
	vector<int>a(n);
	map<int, int>mp;
	rep(i, n) {
		cin >> a[i];
		mp[a[i]]++;
	}
	ll ans = 0;
	for (auto p : mp) {
		ll n = p.second;
		ans += n * (n - 1) / 2;
	}
	rep(i, n) {
		ll res = ans;
		res -= (mp[a[i]] - 1);
		cout << res << endl;
	}
	return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <ctime>
#define ll long long
#define maxn 1000000007
using namespace std;
int mp[10][10];

int main(){
	int h,w,k,fun=0;
	scanf("%d%d%d",&h,&w,&k);
	getchar();
	for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            char c;
            scanf("%c",&c);
            if(c=='#')
                mp[i][j]=1;
        }
        getchar();
    }
    ll p=1<<(h+w+1);
    for(;(p>>(h+w+1))&1;p++)
    {
        int ans=0;
        for(int i=1;i<=h;i++)
        {
            for(int j=1;j<=w;j++)
            {
                if(!((p>>i)&1)&&!((p>>(j+h))&1))
                    ans+=mp[i][j];
            }
        }
        if(ans==k)
            fun++;
    }
    printf("%d\n",fun/2);
	return 0;
}


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

UL N,M;
UL Ez[15]={};
UL D[15][15];

UL dp[1<<15];
UL DSum=0;

int main() {
 scanf("%u%u",&N,&M);
 rep(i,N) rep(j,N) D[i][j]=10000000;
 rep(i,N) D[i][i]=0;
 rep(m,M){
  UL u,v,d; scanf("%u%u%u",&u,&v,&d);
  Ez[u]++;
  Ez[v]++;
  D[u][v]=D[v][u]=min(D[u][v],d);
  DSum+=d;
 }
 rep(k,N)rep(i,N)rep(j,N)
  D[i][j]=min(D[i][j],D[i][k]+D[k][j]);

 rep(i,1<<N) dp[i]=~0u;
 dp[0]=0;
 UL tg=0;
 rep(i,N) if(Ez[i]&1) tg|=(1<<i);
 rep(i,N)rep(j,i){
  UL m=(1<<i)|(1<<j);
  if(m&~tg) continue;
  UL d=D[i][j];
  rep(k,1<<15){
   if(k&m) continue;
   if(!~dp[k]) continue;
   dp[k|m] = min(dp[k|m],dp[k]+d);
  }
 }
 cout<<dp[tg]+DSum<<endl;
 return 0;
}



Measured memory_bytes: 3428
a = gets.split(' ')
n = a[0].to_i
m = a[1].to_i

$rr = Array.new(n) {|i| i}
def get_root(u) 
  if u == $rr[u]
    return u 
  else
    return $rr[u] = get_root($rr[u])
  end
end

def merge_root(u, v)
  x = get_root(u)
  y = get_root(v)
  # p x, y
  if (x == y) 
    return 0
  end
  $rr[x] = y
end

m.times do
  a = gets.split(' ')
  u = a[0].to_i - 1
  v = a[1].to_i - 1
  merge_root(u, v)
end

$h = Hash.new
n.times do |i|
  $h.has_key?(get_root(i)) ? $h[get_root(i)] += 1 : $h[get_root(i)] = 1
end

ans = 0
$h.each do |k, v|
  if (v > ans) 
    ans = v
  end
end
puts(ans)

Measured memory_bytes: 39156
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int d = sc.nextInt();
    int n = sc.nextInt();
    int i;
    int total = 0;
    if(d==0){
      if(n==100){
        total = 101;
      }else{
        total = n;
      }
    }else if(d==1){
      if(n==100){
        total = 10100;      
      }else{
        for(i=0;i<n;i++){
          total += 100;
      }
      }
    }else if(d==2){
      if(n==100){
        total = 1010000;
      }else{
        for(i=0;i<n;i++){
          total += 10000;
      }
      }
    }
    System.out.println(total);
 }
}

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

main()
{
    int n;
    cin>>n;
    double ret=0,a=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lf",&a);
        ret+=1/a;
    }
    ret=1/ret;
    cout<<ret<<endl;
}

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


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

  int a;
  cin >> a;
  cout << a+a*a+a*a*a << " " << endl;
  return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
int GCD(int a,int b){return b?GCD(b,a%b):a;}
int LCM(int a,int b){return (a*b)/GCD(a,b);}
int abs(int x){return x>0?x:-x;}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	string s;
	cin >> s;
	int ans = 0;
	REP(i, (int)s.size()){
		if (s[i] == '2')  ans++;
	}

	cout << ans << endl;
}


Measured memory_bytes: 768
#include<iostream>
using namespace std;
int main()
{
	int n,Y=0,W=0,G=0,P=0;
	cin >> n;
	char c;
	for(int i=1; i<=n; ++i)
	{
		cin>>c;
		
		if(c=='Y')
		{
			cout<<"Four"<<endl;
			return 0;
		}
	}
	cout<<"Three"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

int main () {
//  ios_base::sync_with_stdio(0);
//	freopen("input.txt", "rt", stdin);
//	freopen("output.txt", "wt", stdout);

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

	vector<bool> a(n, true);
	for (int i = 0; i < m; ++i) {
		int v1, v2;
		cin >> v1 >> v2;
		--v1, --v2;
		a[v1] = !a[v1];
		a[v2] = !a[v2];
	}

	bool key = true;
	for (int i = 0; i < n; ++i) {
		key &= a[i];
	}

	cout << (key ? "YES" : "NO") << endl;

	return 0;
}


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

using namespace std;

int dp[2][3001][50];
const int mod=100000;
int n,m,s;

int main(){
    while(cin>>n>>m>>s&&(n|m|s)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<2;i++)dp[i][0][n*n]=1;
        for(int i=m;i>=0;i--){
            for(int j=0;j<=s;j++){
                for(int k=n*n;k>=0;k--){
                    int cur=(i+1)%2;
                    int nxt=i%2;
                    int res=0;
                    if(k==n*n){
                        if(j==0)res=1;
                        else res=0;
                    }
                    else{
                        res+=dp[cur][j][k];
                        if(j-i>=0)res+=dp[cur][j-i][k+1];
                    }
                    dp[nxt][j][k]=res%mod;
                }
            }
        }
        cout<<dp[1][s][0]%mod<<endl;
    }
    return 0;
}

Measured memory_bytes: 2036
#include<bits/stdc++.h>
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rep(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define forn(i,n,m) for(int (i)=(n);i<=(int)(m);(i)++)
#define pb push_back
#define mp make_pair
#define re return
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
using namespace std;
const int INF=1e9;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef queue <int> qi;
string s;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	for(int i=0;i<s.size();i++)
		cout<<'x';
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

const int MAX = 200000;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;

bool f[26];

void solve(void){
    string S;
    cin >> S;
    if (S == "zyxwvutsrqponmlkjihgfedcba") cout << -1 << '\n';
    else {
        if (S.size() < 26) {
            rep(S.size(), i) {
                f[S[i]-'a'] = true;
            }
            int c = -1;
            rep(26, i) {
                if (!f[i]) {
                    c = i;
                    break;
                }
            }
            cout << S;
            putchar(c+'a');
            putchar('\n');
        }
        else {
            string T(S);
            next_permutation(T.begin(), T.end());
            rep(26, i) {
                putchar(T[i]);
                if (S[i] != T[i]) break;
            }
            putchar('\n');
        }
    }
}

int main(void){
  solve();
  return 0;
}


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

#define int long long
#define endl '\n'

#define IOS ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;

#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<vi>
#define vp vector<pii>
#define vs vector<string>
#define all(v) v.begin(),v.end()

#define lb  lower_bound
#define ub  upper_bound
#define bs  binary_search
#define ff  first
#define ss  second
#define sz(x) ((int)(x).size())
// #define rep(i,l,r) for(int i=(l);i<(r);++i)

#define gcd(a,b)    __gcd((a),(b))
#define lcm(a,b)    ((a)*(b)) / gcd((a),(b))

#define pi 3.14159265358979323846264338327950L
#define MOD 1000000007


int32_t main()
{


     int n;
     cin>>n;
     vi a(n);
     int sum=0;
     vi rep((int)1e5+5);
     for(auto &it:a)
     {
          cin>>it;
          sum+=it;
          rep[it]++;
     } 
     int q;
     cin>>q;
     while(q--)
     {
          int b,c;
          cin>>b>>c;
          sum-=rep[b]*b;
          rep[c]+=rep[b];
          
          sum+=rep[b]*c;
          rep[b]=0;
          cout<<sum<<endl;
     }   
     return 0;
}




Measured memory_bytes: 4836
#include <bits/stdc++.h>//
#define X first
#define Y second
using namespace std;
int n, m, x, y, z;
vector<pair<int, int> > a[2020];
vector<int> b[2020];
vector<int> c[2020];
int d[2020], w[4020];
int st[2020], ed[2020];
bool v[2020];
bool dfs(int x, int y, int t, vector<int> &b) {
	if (x == t) {
		return true;
	}
	for (auto i: a[x]) {
		if (i.X != y) {
			b.push_back(i.Y);
			if (dfs(i.X, x, t, b)) {
				return true;
			}
			b.pop_back();
		}
	}
	return false;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		a[x].push_back({y, 2 * i});
		a[y].push_back({x, 2 * i + 1});
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &st[i], &ed[i]);
		dfs(st[i], 0, ed[i], b[i]);
		assert(b[i].size() > 0);
		for (int j: b[i]) {
			c[j / 2].push_back(i);
			d[j / 2]++;
		}
	}
	for (int i = 1; i < n; i++) {
		z += min(d[i], 2);
	}
	while (true) {
		int p = 0, q = -1; // p = choose edge, q = choose path
		for (int i = 1; i < n; i++) {
			if (d[i] == 1 && w[i * 2] != w[i * 2 + 1]) {
				p = i;
				break;
			}
		}
		if (p == 0) {
			for (int i = 1; i < n; i++) {
				if (d[i] >= 2) {
					p = i;
					break;
				}
			}
		}
		if (p == 0) {
			break;
		}
		for (int i: c[p]) {
			if (!v[i]) {
				q = i;
				break;
			}
		}
		assert(q >= 0);
		bool rev = false;
		v[q] = true;
		for (int i: b[q]) {
			if (i / 2 == p) {
				if (w[i]) {
					swap(st[q], ed[q]);
					for (int &j: b[q]) {
						j ^= 1;
					}
				}
				for (int &j: b[q]) {
					d[j / 2]--;
					w[j] = 1;
				}
				break;
			}
		}
	}
	printf("%d\n", z);
	for (int i = 0; i < m; i++) {
		printf("%d %d\n", st[i], ed[i]);
	}
	return 0;
}


Measured memory_bytes: 15616
#include<stdio.h>
#define MAX 1000000
 
int main(){
   
  int h;
  int i;
  int A[MAX+1];
 
 
  scanf("%d", &h);
 
  for ( i = 1; i <= h; i++ ){
    scanf("%d", &A[i]);
  }
 
  for ( i = 1; i <= h; i++ ) {
     
    printf("node %d: key = %d, ", i, A[i]);
     
    if ( i / 2 >= 1 )printf("parent key = %d, ", A[i/2]);
    if ( i*2 <= h ) printf("left key = %d, ", A[i*2]);
    if ( i*2+1 <= h ) printf("right key = %d, ", A[i*2+1]);
 
    printf("\n");
  }
   
  return 0;
}

Measured memory_bytes: 608
#include <bits/stdc++.h>
#define ll          long long int
#define uu          first
#define vv          second
#define pii         pair<int,int>
#define pll         pair<ll,ll>
#define INF         1e9
#define fastRead    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

const int MAX = 1e6 + 6;

vector<int>edg[MAX];
int main()
{
    fastRead;
    
    int n , m;
    cin>>n>>m;
    vector<int>ara(n+1);
    for(int i = 1; i <=n ; i++ ) cin>>ara[i];
    while(m--) {
        int u , v;
        cin>>u>>v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    
    int ans = 0;
    
    for(int i =1 ; i <=n ; i++ ) {
        
        int tgt = ara[i];
        bool ok = 1;
        
        for(auto x : edg[i]) {
            if(ara[x] >= tgt) ok = 0;
        }
        if(ok) ans++;
    }
    cout<<ans<<'\n';
    return  0;
    
}

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

#define pb push_back
#define ll long long
int mo =  1e9+7;
// int dp[1000][1000];
using namespace std;


int main(int argc, char const *argv[])
{
	// ios::sync_withss_stdio(false);
	// cin.tie(0);
	// cout.tie(0);

	int n;
	scanf("%d ", &n);

	double a[n];

	for (int i = 0; i < n; ++i)
	{
		scanf("%lf", &a[i]);
	}

	double dp[n+1][n+1];
	memset(dp, 0, sizeof(dp));

	dp[0][0] = 1.0;

	for (int i = 0; i <=n; ++i)
	{
		for (int j = 1; j <=n; ++j)
		{
			if(i == 0 && j>=1){
				dp[i][j] = (1-a[j-1])*dp[i][j-1];
				continue;
			}
			if(i>j){
				dp[i][j] = 0;
				continue;}
			dp[i][j] = a[j-1]*dp[i-1][j-1] + (1-a[j-1])*dp[i][j-1];
		}
	}
	double sum = 0.0;

	for (int i = 0; i <=n; ++i)
	{
		if(n - i < i){
			sum+=dp[i][n];
		}
	}

	printf("%.10lf\n", sum);

}




Measured memory_bytes: 74076
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define ll long long
#define db double
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
const int maxn=2e5+7;
int n;

char cc;ll ff;
template<typename T>void read(T& aa) {
	aa=0;ff=1; cc=getchar();
	while(cc!='-'&&(cc<'0'||cc>'9')) cc=getchar();
	if(cc=='-') ff=-1,cc=getchar();
	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
	aa*=ff;
}

int fir[maxn],nxt[2*maxn],to[2*maxn],ind[maxn],e=0;
void add(int x,int y) {
	to[++e]=y;nxt[e]=fir[x];fir[x]=e;++ind[x];
	to[++e]=x;nxt[e]=fir[y];fir[y]=e;++ind[y];
}

int sum[maxn],zz[maxn];
set<int> G;
set<int>::iterator it;
bool init[maxn];
bool solve() {
	if(n==1) return 1;
	int s=1,t=0,x,y,z;
	For(i,1,n) if(ind[i]==1) zz[++t]=i,init[i]=1;
	while(s<=t) {
		G.clear();
		while(s<=t) {
			x=zz[s++];
			for(y=fir[x];y;y=nxt[y]) {
				if(init[z=to[y]]) continue;
				--ind[z]; if(!ind[z]) return 1; 
				if(G.find(z)!=G.end()) return 1;
				G.insert(z);
			}
		}
		for(it=G.begin();it!=G.end();++it) init[*it]=1;
		for(it=G.begin();it!=G.end();++it) {
			x=*it;
			for(y=fir[x];y;y=nxt[y]) {
				if(init[z=to[y]]) continue;
				--ind[z]; if(!ind[z]) return 1;
				if(ind[z]==1) zz[++t]=z;
			}
		}
		For(i,s,t) init[zz[i]]=1;
	}	
	return 0;
}

int main() {
	read(n); int x,y;
	For(i,1,n-1) {
		read(x); read(y);
		add(x,y);
	}
	if(solve()) printf("First\n");
	else printf("Second\n");
	return 0;
}


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

char F[102][102];

void Block(int c,int d,int x,int y){
	if(d==0){
    	for(int i=0;i<4;i++){
    		F[y  ][x+i]=c;
			F[y+1][x+i]=c;
    	}
  	}else{
    	for(int i=0;i<4;i++){
    		F[y+i][x  ]=c;
    		F[y+i][x+1]=c;
    	}
	}
}
void DFS(int y,int x,int c){
	if(F[y][x]!=c)
		return;

	F[y][x] = 6;

    DFS(y-1,x  ,c);
    DFS(y  ,x+1,c);
    DFS(y+1,x  ,c);
    DFS(y  ,x-1,c);
}
int main(){
	while(true){
		int w,h,xs,ys,xg,yg,n;
		cin >> w >> h;
		if(w==0&&h==0){break;}
		for(int i=0;i<h;i++){
			for(int k=0;k<w;k++){
				F[i][k]=-1;
			}
		}
		cin >> xs >> ys;
		cin >> xg >> yg;
		cin >> n;
		for(int i=0; i<n; i++){
			int c,d,x,y;
			cin >> c >> d >> x >> y;
			Block(c,d,x,y);
  		}
 		DFS(ys,xs,F[ys][xs]);
		if(F[yg][xg]==6){
			cout << "OK" << endl;
		}else{
			cout << "NG" << endl;
		}
	}
  return 0;
}


Measured memory_bytes: 3008
import java.util.Scanner;

class Main {
    void solve() {
        Scanner in = new Scanner(System.in);
        int h = in.nextInt(), w = in.nextInt(); in.nextLine();
        char[][] c = new char[h][w];
        for(int i = 0; i < h; i++) {
            String string = in.nextLine();
            c[i] = string.toCharArray();
        }
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                if(c[i][j] == '#') {
                    System.out.print(c[i][j]);
                }else {
                    int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1},
                            dy = {-1, -1, -1, 0, 1, 1, 1, 0};
                    int ans = 0;
                    for(int k = 0; k < 8; k++) {
                        if(0 <= i +dy[k]&& i +dy[k] < h && 0 <= j +dx[k] && j +dx[k] < w) {
//                            System.out.println((i + dy[k]) + " " + (j + dx[k]));
                            if(c[i + dy[k]][j + dx[k]] == '#') {
                                ans++;
                            }
                        }
                    }
                    System.out.print(ans);
                }
            }
            System.out.println();
        }
    }

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


Measured memory_bytes: 21844
#include <vector>
#include <iostream> 
#include <limits>

using namespace std;

int main(int argc, char *argv[]) {
	int N;
	long long A = 0, B = 0;

	cin >> N;

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

	long long ans = numeric_limits<long long>::max();
	for (int i = 0; i < N - 1; i++) {
		A += a[i];
		B -= a[i];
		ans = min(ans, abs(B - A));
	}

	cout << ans << endl;

	return 0;
}

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

int main()
{
	string S;

	char ACTG[4] = {'A','C','T','G'};
	int ans = 0,cnt = 0;

	cin >> S;

	for(int i=0;i<S.size();i++)
	{
		bool flag = false;
		for(auto c : ACTG)
		{
			if(c == S[i])
			{
				flag =true;
				cnt++;
				break;
			}
		}
		ans = max(ans,cnt);
		if(!flag)
		{
			cnt = 0;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
res = b[-1]
for i in range(n - 1):
    res += b[i]
    if a[i] + 1 == a[i + 1]:
        res += c[a[i] - 1]
print(res)

Measured memory_bytes: 9128
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <map>
#include <string>
#include <utility>

#define repd(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
	int a;
	cin >> a;
	return a;
}

void inputArray(int *p,int a){
	rep(i,a){
		cin >> p[i];
	}
}

void inputVector(vector<int> *p,int a){
	rep(i,a){
		int input;
		cin >> input;
		p -> push_back(input);
	}
}

template <typename T>
void output(T a,int precision){
	if(precision > 0){
		cout << setprecision(precision) << a << "\n";
	}else{
		cout << a << "\n";
	}
}

struct node{
	bool flashed;
	int a,b,c;
	node(int in1,int in2,int in3){
		a=in1;
		b=in2;
		c=in3;
	}
};

int main(){
	//source
	ll x,y,z,k;
	cin >> x >> y >> z >> k;
	ll a[x],b[y],c[z];
	for(ll i=0;i<x;i++){
		cin >> a[i];
	}
	for(ll i=0;i<y;i++){
		cin >> b[i];
	}
	for(ll i=0;i<z;i++){
		cin >> c[i];
	}
	sort(a,a+x,greater<>());
	sort(b,b+y,greater<>());
	sort(c,c+z,greater<>());

	vector<ll> ans;
	rep(l1,x){
		rep(l2,x){
			rep(l3,z){
				if(l1*l2*l3<=k){
					ans.push_back(a[l1]+b[l2]+c[l3]);
				}
			}
		}
	}

	sort(ans.rbegin(),ans.rend());

	ll loop=k;
	rep(i,loop){
		cout << ans[i] << endl;
	}
	
	return 0;
}


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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

typedef tuple<int, int, int> ti;

const int MAX_N = 1e5 + 10;

struct PT{
	int x, y, ix;
	PT(int xx, int yy, int ii) : x(xx), y(yy), ix(ii) {}
	PT() {PT(0, 0, 0);}
	bool operator<(const PT &o) {return x == o.x ? y < o.y : x < o.x;}
};
int getDis(PT a, PT b) {return max(abs(a.x - b.x), abs(a.y - b.y));}

int N, A, B, D, Cnt[MAX_N];
PT Nr[MAX_N];
vector<int> Ed[MAX_N];
void add(int x, int y) {Ed[x].push_back(y), Ed[y].push_back(x);}
int main() {
	cin >> N >> A >> B; A--; B--;
	for(int i=0; i<N; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Nr[i] = PT(x - y, x + y, i);
	}
	D = getDis(Nr[A], Nr[B]);

	int xd[2] = {D, D};
	int yd[2] = {D, D-1};
	
	for(int k=0; k<2; k++) {
		for(int i=0; i<N; i++) swap(Nr[i].x, Nr[i].y);
		sort(Nr, Nr+N);

		int jSt=0, jEn=0;
		vector<int> Connect(N, 0);
		for(int il=0, ir=0; il<N; il=ir) {
			while(ir < N and Nr[il].x == Nr[ir].x) ir++;
			while(jSt < N and Nr[il].x + xd[k] > Nr[jSt].x) jSt++;
			while(jEn < N and Nr[il].x + xd[k] >= Nr[jEn].x) jEn++;
			if(jSt == jEn) continue;

			int jl = jSt, jr = jSt;
			for(int i=il; i<ir; i++) {
				while(jl < jEn and Nr[jl].y + yd[k] < Nr[i].y) jl++;
				while(jr < jEn and Nr[jr].y - yd[k] <= Nr[i].y) jr++;
				Cnt[Nr[i].ix] += jr-jl;
				if(jl == jr) continue;
				Connect[jl]++, Connect[jr-1]--;
				add(Nr[i].ix, Nr[jl].ix);
			}
		}
		for(int i=1; i<N; i++) Connect[i] += Connect[i-1];
		for(int i=0; i<N-1; i++) if(Connect[i]) add(Nr[i].ix, Nr[i+1].ix);
	}
	
	vector<bool> vis(N, 0);
	queue<int> Q; Q.push(A); vis[A] = true;
	ll ans = 0;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		ans += Cnt[v];
		for(int w : Ed[v]) if(!vis[w]) Q.push(w), vis[w] = true;
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main() {
  int n, m;
  std::cin >> n >> m;

  std::vector<int> a(n);
  int total = 0;
  for (int i = 0; i < n; ++i) {
    std::cin >> a.at(i);
    total += a[i];
  }
  double threshold = ((double) total) / (4 * m);
  std::sort(a.begin(), a.end(), std::greater<int>());
  std::cout << ((a[m-1] < threshold) ? "No" : "Yes") << std::endl;              
}

Measured memory_bytes: 256
//
// Created by 陈基彤 on 2020-01-09.
//
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5 + 5;
const LL mod = 1e9 + 7;
vector<int> edge[maxn];
int n;
LL sum[maxn],num[maxn];
LL tt;
void dfs(int x,int fa){
    LL nows = 0,nown = 0,tot = 0;
    for(auto i: edge[x])if(i != fa){
        dfs(i,x);
        tot = (tot + nown*num[i]%mod + nown*sum[i]%mod + num[i]*nows%mod)%mod;
        nows = (nown*sum[i]%mod + num[i]*nows%mod + sum[i]+nows)%mod;
        nown = (nown*num[i]%mod + num[i] + nown)%mod;
    }
    num[x] = (nown * 2 + 1)%mod;
    sum[x] = (nows * 2 + nown)%mod;
    tt = (tt+tot + nows)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    LL inv2 = (mod+1)/2;
//    printf("inv2 is %lld\n",inv2);
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(1,0);
//    for(int i=1;i<=n;i++)
//        printf("%lld %lld %lld\n",i,num[i],sum[i]);
    tt = (tt%mod + mod)%mod;
//    printf("%lld\n",tt);
    LL dv = 1;
    for(int i=1;i<=n;i++)
        dv = (dv*inv2)%mod;
    cout<<tt*dv%mod<<endl;
    return 0;
}



/*
5
1 2
1 5
2 3
2 4
*/


Measured memory_bytes: 27648
#include <cstdio>

int main(){
	
	int N;
	scanf("%d",&N);
	
	int a,A;
	for(int i=0;;i++){
		a = i*i;
		if(a<=N){
			A = a;
		}else{
			break;
		}
	}
	
	printf("%d",A);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define lla(s) s.rbegin(),s.rend()
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;

int gcd(int a,int b){
    if(a>b){swap(a,b);}
    if(a==0){return b;}
    else{return gcd(b%a,a);}
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,k,ans;
    cin>>n>>k;
    if(n<k){ans=min(k-n,n);}
    else if(n%k==0){
        ans = 0;
    }
    else{
        ans=min(abs(n%k-k),n%k);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        long n=sc.nextLong();
        long k=sc.nextLong();
        n=n%k;
        n=Math.min(n,Math.abs(n-k));
        System.out.println(n);
    }
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
#define degreeToRadian(deg) (((deg)/360)*2*M_PI)
#define radianTodegree(rad) (((rad)/2/M_PI)*360)
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; }
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;
const int MOD = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//cin.tie(0);ios::sync_with_stdio(false);
//cout << fixed << setprecision(15) << y << endl;
int main() {
  int k; cin >> k;
  string s = "";
  rep (i, k) {
    s += "ACL";
  }
  cout << s << endl;
  return 0;
}


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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

using namespace std;

#define MAX_N 200005
int N;
LL T;
LL t[MAX_N];

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

  LL ans = 0;
  for (int i = 1; i < N; i++) {
    ans += min(T, t[i] - t[i-1]);
  }

  ans += T;
  cout << ans << endl;

  return 0;
}


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

int main() {
    int a, p;
    cin >> a >> p;

    int ans = (a * 3 + p) / 2;

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


Measured memory_bytes: 256