akhauriyash/Code-Regression huggingface dataset:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def check(y,x):
        a = s[x][y]
        d = 0
        for i in range(x,w):
            if s[i][y] != a:
                break
            d += 1
        if d < k:
            return 0
        else:
            return d

    def update(y,x,d):
        for i in range(x,x+d):
            s[i][y] = 0

    def fall(s):
        res = [[] for i in range(w)]
        for x in range(w):
            for y in range(h):
                if s[x][y]:
                    res[x].append(s[x][y])
            for y in range(h-len(res[x])):
                res[x].append(0)
        return res

    h,w,k = LI()
    c = [list(map(int, input())) for i in range(h)]
    c = [[c[-1-y][x] for y in range(h)] for x in range(w)]
    ans = 0
    for sy in range(h):
        for sx in range(w):
            s = [[i for i in j] for j in c]
            s[sx][sy] = 0
            s = fall(s)
            m = 0
            is_update = 1
            p = 1
            while is_update:
                is_update = 0
                for y in range(h):
                    for x in range(w):
                        if s[x][y]:
                            d = check(y,x)
                            if d:
                                m += p*d*s[x][y]
                                update(y,x,d)
                                is_update = 1
                if is_update:
                    s = fall(s)
                    p <<= 1
            if ans < m:
                ans = m
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 50524
use std::str::FromStr;
use std::fmt::Debug;

fn read_line<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
}

fn main() {
    let vec: Vec<usize> = read_line();
    let k = vec[1];
    let hs: Vec<i32> = read_line();
    let mut dp: Vec<i32> = Vec::new();

    for _ in 0..hs.len() { dp.push(0); }
    dp[1] = (hs[1] - hs[0]).abs();

    for i in 2..hs.len() {
        let start: usize = if (i as i32) - (k as i32) >= 0 { i - k } else { 0 };
        let mut costs: Vec<i32> = Vec::new();

        for j in start..i { costs.push(dp[j] + (hs[i] - hs[j]).abs()); }
        dp[i] = costs.into_iter().min().unwrap();
    }

    println!("{}", dp.last().unwrap());
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
#define int long long

signed main(){
    int N; cin >> N;
    for(int n = 1; n <= N; n++){
        int cnt = 0;
        for(int x = 1; x * x <= n; x++){
            for(int y = 1; y * y + x * x + x * y <= n; y++){
                int b = x + y;
                int c = x * x + y * y + x * y - n;
                int tmp = sqrt(b * b - 4 * c) + 0.05;
                int z = (-b + tmp) / 2;
                /*
                for(int p = z - 10; p <= z + 10; p++){
                    if(p < 1) continue;
                    ll sum = x * x + y * y + p * p + x * y + y * p + p * x;
                    if(sum == n) cnt++;
                }
                */
                if(z < 1) break;
                ll sum = x * x + y * y + z * z + x * y + y * z + z * x;
                if(sum == n) cnt++;
            }
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 3548
#include <iostream>

using namespace std;

int main(void)
{
  int k, n;
  cin >> k >> n;
  int i;
  int ai;
  int pa = 0;
  int dmax = 0;
  int a1 = 0;
  for (i = 0; i < n; i++) {
    cin >> ai;
    if (i == 0) a1 = ai;
    dmax = max(dmax, ai - pa);
    pa = ai;
  }
  dmax = max(dmax, a1 + k - ai);
  cout << k - dmax << endl;
  return 0;
}


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

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

    vector<int> v(n);
    for(int i = 0; i < n; i++)  cin >> v[i];
    sort(v.begin(), v.end());

    int ans = 1<<30;
    for(int i = k-1; i < n; i++){
        ans = min(ans, v[i]-v[i-k+1]);
    }

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

Measured memory_bytes: 640
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val a = Array.fill(n, n)(sc.nextLong())

  var possible = true
  var ans = 0L
  for {
    x <- 0 until n
    y <- x+1 until n
  } {
    val d2 = a(x)(y)
    var necessary = true
    for (z <- 0 until n if necessary && z != x && z != y) {
      val d1 = a(x)(z) + a(z)(y)
      if (d1 < d2) {
        possible = false
      } else if (d1 == d2) {
        necessary = false
      }
    }
    if (necessary) {
      ans += d2
    }
  }

  println(if (possible) ans else -1)
}


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

int	n, m, num, max1, max2, ans, a[100005];

int main() {
	max1 = max2 = num = ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = n; i; i--) {
		max1 = max(a[i], max1);
		num = max(max1 - a[i], num);
	}
	for (int i = n; i; i--) {
		max2 = max(a[i], max2);
		if (max2 - a[i] == num)ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;

int main() {
	long long int n,m,a,b,c,d,e;
	long double z,w;
	string str;
	char ch;
	long long int x[130]={};
	cout << fixed << setprecision(10);
	cin>>a>>b>>c;
	cout<<max({a,b,c})-min({a,b,c});
	



	cout<<endl;
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define bye return 0
#define Yes cout << "Yes" << "\n"
#define No  cout << "No" << "\n"
#define YES cout << "YES" << "\n"
#define NO cout << "NO" << "\n"
#define endl cout << "\n"
using namespace std;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> xa;
    vector<int> ya;
    int x, y, m, n, cnt=0, a, b;
    cin >> n >> m >> x >> y;

    for(int i=0; i<n; ++i){
    	cin >> a;
    	xa.push_back(a);
    }

    for(int i=0; i<m; ++i){
    	cin >> b;
    	ya.push_back(b);
    }

    sort(xa.begin(), xa.end());
    sort(ya.begin(), ya.end());
    int lx=xa.size();
    //int ly=ya.size();

    //cout << xa[lx-1] << " " << ya[ly-1] << "\n";

    if(ya[0] > xa[lx-1] && ya[0] > x && ya[0] <=y) cout << "No War" << "\n";
    else cout << "War" << "\n";


   /*for(auto i:xa) cout << i << " ";
   	endl;
   for(auto i:ya) cout << i << " ";*/
    

   bye;
    
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#include<limits.h>
int main(){
    int N,K;
    scanf("%d %d",&N,&K);
    int p[1002];
    for(int i=0;i<N;i++)
        scanf("%d",p+i);
    for(int i=0;i<N;i++){
        for(int j=0;j<i;j++){
            if(p[j] > p[i]){
                int tmp=p[j];
                p[j] = p[i];
                p[i] = tmp;
            }
        }
    }
    int ans=0;
    for(int i=0;i<K;i++)
        ans += p[i];
    printf("%d",ans);
}


Measured memory_bytes: 1716
mi = lambda: map(int, input().split())
e = enumerate
n,k = mi()
m = (n+k).bit_length()
a = list(mi())
g = [None]*n

d = dict()
for i,x in e(a):
  d[x] = i
for i,x in e(a):
  g[d[x]] = ((i+1)%n,int(d[x]>=i)+int(i+1==n))
  d[x] = i
db = [g]
for _ in range(m):
  old = db[-1]
  new = [None]*n
  for i in range(n):
    p,q = old[i]
    r,s = old[p]
    new[i] = (r,q+s)
  db.append(new)
cur = 0
st = m
cs = 0
while st>=0:
  p,q = db[st][cur]
  if cs+q < k:
    cs += q
    cur = p
  else:
    st -= 1
    
q = list()
while cur < n:
  if g[cur][1] == 0:
    cur = g[cur][0]
  elif g[cur] == (0,1):
    break
  else:
    q.append(a[cur])
    cur += 1
  
print(' '.join(map(str,q)))

Measured memory_bytes: 332624
//無断転用の一切を禁ずるよ
#include<iostream>
#include<stdio.h>//printするよ
#include<vector>
#include<algorithm>//辞書順はnext_permutationだよ
#include<set>
#include<string>
#include<string.h>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<utility>//swapで数値交換するよ
//end of libraries
#define rt "\n"//改行を最速化させるよ
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define vcin(V) for (int i = 0; i < (V).size(); i++) { cin >> (V).at(i); }
#define sort(s) sort(s.begin(),s.end())
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define cncn int cnt=0
#define smsm int sum=0
#define nn int n=0
#define please return
#define AC 0//おまじないだよ
#define Rapid cin.tie(0);ios::sync_with_stdio(false)
//end of define
using namespace std;
typedef vector<int> vint;
typedef vector<string> vstr;
typedef vector<char> vcha;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool; 
//end of typedef

//最大公約数（GCD）を求めるよ
//最小公倍数（LCM）は＜＜　（A＋B）÷ GCD　 ＞＞で求まるよ

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}
//begin

int main(void){
	int h, w,n;
	cin >> h >> w>>n;
	cncn;
	if (h > w)cnt = h;
	else cnt = w;
	if (n % cnt == 0)cout << n / cnt << rt;
	else cout << n / cnt + 1 << rt;
	please AC;
}
//end t

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

using namespace std;

int main(){
    int n;
    string s;
    map<string, int> m;
    cin>>n;
    int mx = 0;
    for(int i=0;i<n;i++){
        cin >>s;
        m[s]++;
        mx = max(mx, m[s]);
    }

    for(pair<string, int> p:m){
        if(p.second == mx)
            cout<<p.first<<endl;
    }
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    int x = (a > b) ? a : b;
    int max = ( x > c) ? x : c;
    
    int y = (a > b) ? b : a;
    int z = (x > c) ? c : x;
    
    int middle = (y > z) ? y : z;
    int min = (y > z) ? z : y;
    
    cout << min << " " << middle << " " << max << endl;
    
    return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
using namespace std;
const int MAX = 1e5 + 10;
const ll MOD = 1e9 + 7;
int N, M, K, Q;
ll A[MAX], psum[MAX], bline[MAX];

int main()
{
	int i, j, k;
	scanf("%d%d", &N, &K);
	for (i = 1; i <= N; ++i) {
		scanf("%lld", &A[i]);
		psum[i] = psum[i - 1] + max(0LL, A[i]);
		bline[i] = bline[i - 1] + A[i];
	}
	if (K > N) {
		printf("0");
		return 0;
	}
	ll maxi = 0;
	for (i = 1; i + K - 1<= N; ++i) {
		maxi = max(maxi, psum[N] - psum[i + K - 1] + psum[i - 1]);
		maxi = max(maxi, psum[N] - psum[i + K - 1] + psum[i - 1] + bline[i + K - 1] - bline[i - 1]);
	}
	printf("%lld", maxi);
	
}

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

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  ll n;
  ll count=0;
  cin>>n;
  bool check=false;
  while(n--)
  {
    ll x,y;
    cin>>x>>y;
    if(x==y)
      count++;
    else
      count=0;
    
    if(count==3)
      check=true;
  }
  
  if(check)
    cout<<"Yes";
  else
    cout<<"No";  
  
}

Measured memory_bytes: 3656
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
int A[100010],B[100010];
vector<P> G[100010];
int C[100010];
int m=0;

void dfs(P a,int c){
	int color=1;
	REP(i,G[a.first].size()){
		if(color==c){
			color++;
		}
		C[G[a.first][i].second]=color;
		dfs(G[a.first][i],color);
		m=max(color,m);
		color++;
	}
}

signed main(){
	cin>>N;
	REP(i,N-1){
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
	}
	REP(i,N-1){
		G[A[i]].push_back({B[i],i});
	}
	int color=1;
	REP(i,G[0].size()){
		C[G[0][i].second]=color;
		dfs(G[0][i],color);
		m=max(color,m);
		color++;
	}
	cout<<m<<endl;
	REP(i,N-1){
		cout<<C[i]<<endl;
	}
	return 0;
}


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

using namespace std;

struct Card {
  char suit;
  long num;

  bool operator==(const Card& c) const {
    return (suit == c.suit) && (num == c.num);
  }

  bool operator!=(const Card& c) const {
    return !((suit == c.suit) && (num == c.num));
  }

  bool operator<=(const Card& c) const {
    return num <= c.num;
  }
};

void merge(vector<Card> &v, vector<Card> &vl, vector<Card> &vr) {
  int n = (int)v.size();
  int i, j, k;
  for (i = 0, j = 0, k = 0; i < n; ++i) {
    if (j >= (int)vl.size()) v[i] = vr[k++];
    else if (k >= (int)vr.size()) v[i] = vl[j++];
    else if (vl[j] <= vr[k]) v[i] = vl[j++];
    else v[i] = vr[k++];
  }
}

void mergesort(vector<Card> &v) {
  int n = (int)v.size();
  if (n > 1){
    vector<Card> vl(v.begin(), v.begin() + n/2);
    vector<Card> vr(v.begin() + n/2, v.end());
    mergesort(vl);
    mergesort(vr);
    merge(v, vl, vr);
  }
}

int partition(vector<Card> &v, int p, int r) {
  Card t;
  Card x = v[r];
  int i = p - 1;
  for (int j = p; j < r; ++j) {
    if (v[j] <= x) {
      ++i;
      t = v[i];
      v[i] = v[j];
      v[j] = t;
    }
  }
  t = v[i+1];
  v[i+1] = v[r];
  v[r] = t;

  return i+1;
}

void quicksort(vector<Card> &v, int p, int r) {
  if (r > p) {
    int q = partition(v, p, r);
    quicksort(v, p, q-1);
    quicksort(v, q+1, r);
  }
}

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

  int n;
  vector<Card> A, B;
  cin >> n;
  A.reserve(n);
  B.reserve(n);
  for (int i = 0; i < n; ++i) {
    Card c;
    cin >> c.suit >> c.num;
    A.push_back(c);
    B.push_back(c);
  }

  quicksort(A, 0, n-1);
  mergesort(B);

  int i;
  for (i = 0; i < n; ++i)
    if (A[i] != B[i]) break;
  if (i < n) cout << "Not stable\n";
  else cout << "Stable\n";

  for (int i = 0; i < n; ++i)
    cout << A[i].suit << " " << A[i].num << "\n";

  return 0;
}



Measured memory_bytes: 9032
#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <fstream>
#include <random>
#include <time.h>
#include <complex>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 999999999
#define rep(i,n) for(int (i)=0;(i)<n;(i)++)
#define Rrep(i,n) for(int i=n;i>0;i--)
#define arep(a,i,n) for(int i=a;i<n;i++)
#define SORT(v) sort((v).begin(),(v).end())
#define TEMP(type,x,y) do {temp temp=x,x=y,y=temp}while(0)

typedef struct _guidebook{
	string s;
	int point;
	int num;
}guidebook;

bool cmp2(const guidebook &a, const guidebook &b) {
	
	return a.s == b.s ? a.point > b.point : a.s < b.s;
}

int main() {

	int n;
	cin >> n;
	vector<guidebook>guidebooks(n);

	for (int i = 0; i < n; i++) {
		cin >> guidebooks[i].s >> guidebooks[i].point;
		guidebooks[i].num = i + 1;
	}

	sort(guidebooks.begin(), guidebooks.end(), cmp2);

	for (int i = 0; i < n; i++) {
		cout << guidebooks[i].num << endl;
	}

	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }

ll gcd(ll x, ll y)
{
    ll temp;
    while (y != 0) {
        temp = y;
        y = x % y;
        x = temp;
    }
    return (x);
}


int main() {
  int n;
  cin >> n;
  int a[n];
  FOR(i,0,n-1) cin >> a[i];

  ll l[n],r[n];

  FOR(i,0,n-2){
    if(i==0) l[0] = a[0];
    else{
      l[i] = gcd(l[i-1],a[i]);
    }
  }

  FORD(i,n-1,1){
    if(i==n-1) r[i] = a[n-1];
    else{
      r[i] = gcd(r[i+1],a[i]);
    }
  }

  ll max = 0;

  FOR(i,0,n-1){
    if(i==0) chmax(max,r[1]);
    else if(i==n-1) chmax(max,l[n-2]);
    else{
      chmax(max,gcd(l[i-1],r[i+1]));
    }
  }

  cout << max << endl;
  




}



Measured memory_bytes: 2176
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_owned()
}

fn reads<T>() -> Vec<T>
where
    T: std::str::FromStr,
    <T as std::str::FromStr>::Err: std::fmt::Debug,
{
    read_line()
        .split_whitespace()
        .map(|w| w.parse().unwrap())
        .collect()
}

fn main() {
    let n: usize = reads()[0];
    let mut aa: Vec<i64> = reads();
    aa.sort();

    let mut ans = (-1, -1);

    for &a in aa.iter() {
        let t = std::cmp::min(a, aa[n - 1] - a);
        if ans.1 < t {
            ans = (a, t);
        }
    }

    println!("{} {}", aa[n - 1], ans.0);
}


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

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 1000000007
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const int maxn=2e6+10;

int x1,y1,x2,y2;
ll tmp[maxn];

ll inv(ll x,int p) {
	if (p==0) return 1;
	if (p%2==1) return x*inv(x*x%mod,p/2)%mod;
	else return inv(x*x%mod,p/2); 
}

ll f(int x,int y) {
	return tmp[x+y]*inv(tmp[x],mod-2)%mod*inv(tmp[y],mod-2)%mod;
}

ll solve(int x,int y) {
	ll res=0;
	for (int i=1;i<=x+1;i++) (res+=f(i,y))%=mod;
	return res;
}

int main(){    
	tmp[0]=1;
	for (int i=1;i<maxn;i++) tmp[i]=(tmp[i-1]*(ll)i)%mod;
	cin>>x1>>y1>>x2>>y2;
	ll ans=solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1);
	ans%=mod;
	if (ans<0) ans+=mod;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 16000
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  long long  K, X;
  int ansCnt = 0;

  cin >> K >> X;
  if(K == 1){
//    cout << "case1: " << endl;
    cout << X;

  }else if((1000000 - X) < K){
//    cout << "case2: " << endl;

    long long ans = X-(K-1);
    while(ans <= 1000000){
      cout << ans;
      if(ans != 1000000){
        cout << " ";
      }
      ans++;
    }

  }else if((X + 1000000) < K){
//    cout << "case3: " << endl;

    long long ans = -1000000;
    while(ans <= (X + (K-1))){
      cout << ans;
      if(ans != (X + (K-1))){
        cout << " ";
      }
      ans++;
    }

  }else{
//    cout << "case4: " << endl;

    int x = 2*K -1;
    vector<long long> ans(x);
    for(int i=0; i<x; i++){
      ans[i] = X-(K-1) + i;
      cout << ans[i];
      if(i != x){
        cout << " ";
      }
    }
  }
  cout << endl;
}


Measured memory_bytes: 256
repeat = gets
for i in 1 .. repeat.to_i do
   line = gets
   test = line.split(/\s+/)
   tmp =[]
   tmp[0] = test[0].to_i
   tmp[1] = test[1].to_i
   tmp[2] = test[2].to_i

   if tmp[0]<tmp[1] then
   	te = tmp[0]
   	tmp[0] = tmp[1]
   	tmp[1]=te
   end

   if tmp[0]<tmp[2] then
   	te = tmp[0]
   	tmp[0] = tmp[2]
   	tmp[2]=te
   end

   if tmp[0]*tmp[0]==tmp[1]*tmp[1]+tmp[2]*tmp[2] then
   	puts "YES"
   else
   	puts "NO"
   end
end

Measured memory_bytes: 6108
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            Println(Ceiling((decimal)ReadLong() / new List<long>
            {
                ReadLong(),
                ReadLong(),
                ReadLong(),
                ReadLong(),
                ReadLong(),
            }.Min()) + 4);
        }

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int DigitsSum(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());

        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}



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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    long long A, B, V, W;
    cin >> A >> V;
    cin >> B >> W;
    long long T; cin >> T;
    long long D = abs(A - B);
    long long X = V - W;
    if (D <= X * T) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

Measured memory_bytes: 3656
using System;
using System.Collections.Generic;

class Program {
  static void Main (string[] args) {
    string str = Console.ReadLine();
    if (str == "A") {
      Console.WriteLine("T");
    } else if (str == "T") {
      Console.WriteLine("A");
    } else if (str == "G") {
      Console.WriteLine("C");
    } else {
      Console.WriteLine("G");
    }
  }
}

Measured memory_bytes: 11092
S = input()

if S == 'SUN':
    print(7)
elif S == 'MON':
    print(6)
elif S == 'TUE':
    print(5)
elif S == 'WED':
    print(4)
elif S == 'THU':
    print(3)
elif S == 'FRI':
    print(2)
elif S == 'SAT':
    print(1)


Measured memory_bytes: 9112
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

ll S, s_len = 0;
ll s_num[10];

void solve() {
    ll ans = 0;
    for (ll i = 0; i < pow(2, s_len); i++) {
        ll sum = 0;
        string temp;
        for (ll j = 0; j < s_len; j++) {
            if (1 & i >> (s_len - 1) != 1) continue;
            temp += to_string(s_num[s_len - 1 - j]);
            if ((1 & i >> j) == 1) {
                sum += stol(temp);
                temp = "";
            }
        }
        ans += sum;
    }
    cout << ans << endl;
}

int main() {
    cin >> S;
    while (S > 0) {
        s_num[s_len++] = S % 10;
        S /= 10;
    }
    solve();
    return 0;
}

Measured memory_bytes: 256
n, l = map(int, raw_input().split())
a = map(int, raw_input().split())
# print a
i = 0
untied  = False
while i < (len(a)-1):
    if a[i] + a[i+1] >= l:
        # print i, a[i]
        untied = True
        break
    i += 1
if untied == False:
    print "Impossible"
    exit()
print "Possible"
for k in xrange(n-1, i+1, -1):
    print k
for k in xrange(1, i+2):
    print k

Measured memory_bytes: 11340
K=int(input())
import queue
q=queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(K):
    tmp=q.get()
    if tmp%10 !=0:
        q.put(10*tmp+(tmp%10)-1)
    q.put(10*tmp+(tmp%10))
    if tmp%10 !=9:
        q.put(10*tmp+(tmp%10)+1)
print(tmp)

Measured memory_bytes: 12452
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    sc = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]

    result = [''] * N
    for s, c in sc:
        if result[s - 1] == '':
            result[s - 1] = str(c)
        elif result[s - 1] == str(c):
            pass
        else:
            print(-1)
            return

    if result[0] == '':
        result[0] = '0' if N == 1 else '1'

    for i, x in enumerate(result):
        if x == '':
            result[i] = '0'

    if N != 1 and result[0] == '0':
        print(-1)
    else:
        print(''.join(result))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <float.h>

double minkdist(int *x, int *y, int n, int p)
{
  int i;
  double sum = 0;
  for (i = 0; i < n; i++)
    sum += pow(abs(x[i] - y[i]), p);
  return pow(sum, 1.0 / p);
}

double infindist(int *x, int *y, int n)
{
  int i;
  double max = -DBL_MAX;
  for (i = 0; i < n; i++)
    if ((double) abs(x[i] - y[i]) > max)
      max = (double) abs(x[i] - y[i]); 
  return max;
}

int main(void)
{
  int n, *x, *y, i;
  scanf(" %d", &n);
  x = (int *) malloc(sizeof(int[n]));
  y = (int *) malloc(sizeof(int[n]));
  for (i = 0; i < n; i++)
    scanf(" %d", x + i);
  for (i = 0; i < n; i++)
    scanf(" %d", y + i);
  printf("%lf\n", minkdist(x, y, n, 1));
  printf("%lf\n", minkdist(x, y, n, 2));
  printf("%lf\n", minkdist(x, y, n, 3));
  printf("%lf\n", infindist(x, y, n));
  return 0;
}



Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,n) for(int i=(a); i<(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
int main() {
  int N; cin >> N;
  vvi A(N, vi(2,0));
  rep(i, N) A[i][0] = i;
  rep2(i, 1, N) {int s; cin >> s; A[s-1][1]++;}
  rep(i, N) cout << A[i][1] << endl;
}

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

const int N=25;
const long long INF=1e18; 
int n;
int a[N];

long long DFS(int l,int r,int x,int y)
{
	if(l+1>=r) return 0;
	long long res=INF;
	for(register int i=l+1;i<r;++i)
		res=min(res,DFS(l,i,x,x+y)+DFS(i,r,x+y,y)+1ll*(x+y)*a[i]);
	return res;
}

int main(void)
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	printf("%lld\n",DFS(1,n,1,1)+a[1]+a[n]);
	return 0;
}

Measured memory_bytes: 3832
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;

int main(){
	int n,m;cin>>n>>m;
	cout<<n*(n-1)/2+m*(m-1)/2<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20001


typedef struct stack{
  int f;
  int s;
} Sta;

void push(int S[], int x, int *top){
  S[(*top)++] = x;
}

int pop(int S[], int *top){
  (*top)--;
  return S[*top];
}

void push2(Sta S[], int x, int y, int *top){
  S[*top].f = x;
  S[(*top)++].s = y;
}

void uni(Sta S[], int *top){
  int i;

  for( i = (*top)-1 ; i > 0 ; i-- ){
    if( S[i].f < S[i-1].f ){
      (*top)--;
      S[i-1].f = S[i].f;
      S[i-1].s += S[i].s;
    }
  }
}


int main(){
  int top1=0, top2=0;
  int S1[MAX];
  Sta S2[MAX];
  int i, j, x, sum=0, cnt=0;
  char s[MAX];

  scanf("%s",s);

  for( i = 0 ; i < strlen(s) ; i++ ){
    if( s[i] == '\\' ){
      push(S1, i, &top1);
      continue;
    }
    else if( s[i] == '/' ){
      if( top1 == 0 ) continue;
      x = pop(S1, &top1);
      sum += (i - x);
      push2(S2, x, i-x, &top2);
      uni(S2, &top2);
      continue;
    }
  }


  printf("%d\n",sum);
  if( top2 == 0 ) printf("%d\n", top2);
  else{
    cnt = top2;
    printf("%d ",cnt);
    for( i = 0 ; i < top2 - 1 ; i++ ){
      printf("%d ", S2[i].s);
    }
    printf("%d\n", S2[top2-1].s);
  }

  return 0;
}



Measured memory_bytes: 2108
#include<cstdio>
#include<algorithm>
#define maxn 10000011
using namespace std;
int n,K,m;
long long a[maxn]; int la=0;
long long llq[20];
int calc(long long x) {
	int ans=0;
	while (x) {
		ans+=x%10;
		x/=10;
	}
	return ans;
}
bool check(long long x) {
	long long ans=x; int cnt=0;
	while (ans%10==9) ans/=10, cnt++;
	if (ans==0) return 1;
	return calc(x+llq[cnt])*x<=calc(x)*(x+llq[cnt]);
}
int main() {
	scanf("%d",&n);
	llq[0]=1; for (int i=1;i<=16;i++) llq[i]=llq[i-1]*10;
	for (int i=1;i<=9;i++) a[++la]=i;
	for (int i=1;i<=14;i++) {
		long long b=llq[i]-1;
		for (int j=1;;j++) {
			long long c=b+j*llq[i];
			if (c>1e15) break;
			if (check(c)) a[++la]=c;
			else break;
		}
	}
	sort(a+1,a+1+la); la=unique(a+1,a+1+la)-a-1;
	for (int i=1;i<=n;i++) printf("%lld\n",a[i]);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;

#define pf(n) cout << n << endl
#define ps() cout <<" ";
#define sf(n) cin >> n
#define in(i,n) for (int i = 0; i < n; i++)
#define vi vector<int>
#define vp vector<pair<int, int>>
#define graph vector< vector<int> >
#define vs vector<string>
#define mn -
#define pls +
#define mod %
#define E =
#define EE ==
#define le <=
#define ge <=
int mx=9999999;
/**  '' "\n" - ^ **/

class Template{
    public:
    void yes()
    {
        cout<<"Yes\n";
    }

    void no()
    {
        cout<<"No\n";
    }
    void YES()
    {
        cout<<"YES\n";
    }

    void NO()
    {
        cout<<"NO\n";
    }

    void Case(int i,int n)
    {
        cout<<"Case:"<<i<<" "<<n<<endl;
    }
    /**  '' "\n" x ^ **/
    /** printf("\n") */
};
int main() {

    //ios::sync_with_stdio(false);
    //cin.tie(0);
    Template root;
    int n,m;
    cin>>n>>m;
    float sum=0;
    float  a[n];
    in(i,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
    float  k=sum/(4*m);
    //pf(sum);
    //pf(k);
    int c=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>=k)c++;
    }
    if(c>=m)
        root.yes();
    else root.no();
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
 
#define iter(i, n) forw(i, 1, n)
#define iter0(i, n) for (int i = 0; i < n; ++i)
#define iter_r(i, n) for (int i = n; i >= 1; --i)
#define forw(i, a, b) for (int i = a; i <= b; ++i)
 
#define NR 201000
 
bool mark[NR];
int n, V, x[NR], v[20], pre[NR][20], suc[NR][20], l, f[601000], g[601000];
 
int main() {
	scanf("%d%d", &n, &V);
	for (; V > 0; V = V / 2) v[l++] = V; v[l++] = 0;
	iter(i, n) scanf("%d", &x[i]);
	
	iter0(i, l) suc[n][i] = n, pre[1][i] = 1;
	forw(i, 2, n) iter0(k, l) pre[i][k] = (x[i] - x[i - 1] <= v[k] ? pre[i - 1][k] : i);
	iter_r(i, n - 1) iter0(k, l) suc[i][k] = (x[i + 1] - x[i] <= v[k] ? suc[i + 1][k] : i);
 
 
 
	int M = 1 << l;
	iter0(s, M) g[s] = n + 1;
	iter0(s, M) {
		//printf(": %d %d %d\n", s, f[s], g[s]);
		iter0(i, l) if (!(s >> i & 1)) {
			f[s ^ (1 << i)] = max(f[s ^ (1 << i)], f[s] == n ? n : suc[f[s] + 1][i]);
			g[s ^ (1 << i)] = min(g[s ^ (1 << i)], g[s] == 1 ? 1 : pre[g[s] - 1][i]);
		}
	}
 
	bool all = false;
	iter0(s, M) if (!(s & 1)) {
		int t = M - 1 - s - 1;
		int l = f[s], r = g[t];
		//printf("!%d %d %d\n", l, r, suc[l+1][0]);
 
		if (l + 1 >= r) all = true;
		else if (suc[l + 1][0] >= r - 1) mark[l + 1] = true;
	}
 
	if (all) iter(i, n) mark[i] = true;
 
	int r = 0;
	iter(i, n) {
		if (mark[i]) r = suc[i][0];
		puts(i <= r ? "Possible" : "Impossible");
	}
	return 0;
}

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



int main(){
    int n;
    cin>>n;
    ll m;
    cin>>m;
    ll a[100005];
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]%=m;
    }
    
    
    map<ll,ll> mod;
    ll sum[100005]={0};
    
    for(int i=0;i<n;i++){
        sum[i+1]=a[i]+sum[i];
        sum[i+1]%=m;
        
    }
    mod[0]=1;
    for(int i=1;i<=n;i++){
        mod[sum[i]]++;
    }
    ll ans=0;
    for(auto i : mod){
        ans += (i.second*(i.second - 1)) / 2;
    }
    
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 5760
// Author: Tyler Wang

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

using namespace std;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.precision(12);
  std::cerr.precision(12);
  std::mt19937 rng((std::uint_fast32_t)std::chrono::high_resolution_clock::now()
                       .time_since_epoch()
                       .count());
  int n;
  cin >> n;
  vector<double> p(n);
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
  }
  vector<vector<double>> dp(n + 1, vector<double>(n + 1));
  dp[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      dp[i + 1][j + 1] += dp[i][j] * p[i];
      dp[i + 1][j] += dp[i][j] * (1 - p[i]);
    }
  }
  double ans = 0;
  for (int j = 0; j <= n; ++j) {
    if (j > n - j) {
      ans += dp[n][j];
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

int main(){
    long double a,b,h,m;
    const long double pi = 3.141592653589793;
    cin >> a >> b >> h >> m;
    long double w = abs((30*h+(m/2))-6*m);
    long double rad = pi*w/180;
    long double ans = sqrt((a*a)+(b*b)-(2*a*b*cos(rad)));
    cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 4128
N, L = map(int, input().split())
S = list(input() for i in range(N))
str = ""
for i in range(N-1):
    for j in range(N-1):
        if S[j+1] + S[j] <= S[j] + S[j+1]:
            S[j], S[j+1] = S[j+1], S[j]
for i in S:
    str += i
print(str)


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


int n;
int a[200000];

pair<long long, long long> x[200000];
pair<long long, long long> y[200000];


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

	long long ans = 1LL << 60;

	cin >> n;
	rep(i, n)cin >> a[i];
	
	int idx = 1;
	x[1] = make_pair(a[0], a[1]);
	for (int i = 2; i+2 < n;i++) {
		x[i] = x[i - 1];
		x[i].second += a[i];
		while (x[i].first < x[i].second - a[idx]) {
			x[i].first += a[idx];
			x[i].second -= a[idx];
			idx++;
		}
	}
	idx = n-2;
	y[n-2] = make_pair(a[n-2], a[n-1]);
	for (int i = n-3; i >= 2; i--) {
		y[i] = y[i + 1];
		y[i].first += a[i];
		while (y[i].first - a[idx] > y[i].second) {
			y[i].first -= a[idx];
			y[i].second += a[idx];
			idx--;
		}
	}

	for (int i = 1; i + 2 < n; i++) {
		long long b[4] = { x[i].first, x[i].second, y[i + 1].first, y[i + 1].second };
		ans = min(ans, *max_element(b, b + 4) - *min_element(b, b + 4));
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7296
let rep_char c n =
  let b = Buffer.create n in
  for i = 1 to n do
    Buffer.add_char b c
  done ;
  Buffer.contents b

let count s c =
  let len = String.length s in
  let rec aux i acc =
    if i >= len then acc
    else
      match String.index_from s i c with
      | j -> aux (succ j) (succ acc)
      | exception _ -> acc
  in
  aux 0 0

let solve ls =
  let rec aux c tmp =
    if c = '{' then List.fast_sort String.compare tmp
    else
      let next = (Char.code c |> succ |> Char.chr) in
      match List.fold_left
              (fun acc s -> min acc (count s c)) 50 ls with
      | 0 -> aux next tmp
      | n -> aux next (rep_char c n :: tmp)
  in
  aux 'a' []

let rec pr_ls = function
  | [] -> print_newline ()
  | h :: t-> print_string h; pr_ls t

let mk_ls n =
  let rec aux n ls =
    if n <= 0 then ls else aux (pred n) (read_line () :: ls)
  in
  aux n []

let () =
  mk_ls (read_int ()) |> solve |> pr_ls

Measured memory_bytes: 4480
# coding: utf-8
from collections import Counter as co
n=int(input())
a=[int(x) for x in input().split()]
d=dict(co(a))
#print(d)
p={}
for x in d:
    y=d[x]
    p[x]=max((y*(y-1))//2,0)
#print(p)
ss=0
for x in p:
    ss+=(p[x])
#print(ss)
for i in a:
    x=d[i]-1
    #print(x,end=' ')
    y=max(x*(x-1)//2,0)
    print(ss-p[i]+y)
    #dd[i]=max(dd[i]-1,)
    #print(ss-(p[i]-1)



    

Measured memory_bytes: 32152
S = input()

len_s = len(S)

import numpy as np
s_arr = np.array(list(map(int, list(S))))
s_arr[s_arr == 0] = -1

a_arr = np.ones(len_s)
a_arr[::2] = -1
b_arr = np.ones(len_s)
b_arr[1::2] = -1

num_a = sum((s_arr * a_arr) < 0)
num_b = sum((s_arr * b_arr) < 0)

print(min(num_a, num_b))

Measured memory_bytes: 18860
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#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 VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int d[3] = {-1,0,1};
int main(){
   int n,m;cin>>n>>m;
   vector<P>p(n);
   vector<P>q(m);
   rep(i,n){
       int a,b;cin>>a>>b;
       p[i] = make_pair(a,b);
   }

   rep(i,m){
       int a,b;cin>>a>>b;
       q[i] = make_pair(a,b);
   }
   int res = 0;
   rep(i,n){
       int mem = INF;
       int id = 1;
       rep(j,m){
           if(abs(q[j].first-p[i].first)+abs(q[j].second-p[i].second)<mem){
                mem = abs(q[j].first-p[i].first)+abs(q[j].second-p[i].second);
                id = j+1;
           }
       }
       cout<<id<<endl;
   }
}



Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int i,x,y;
	for(i=1;;i++){
		scanf("%d %d",&x,&y);
		if(x==0 && y==0){
			break;
		}
		else if(x<=y){
			printf("%d %d\n",x,y);
		}
		else{
			printf("%d %d\n",y,x);
		}
	}
	
	return 0 ;
}

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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void Dump(const T& A) {
    REP(i, A.size() - 1) cout << A[i] << " ";
    cout << A[A.size() - 1] << "\n";
}

int gcd(int x, int y) {
    if (x < y) swap(x, y);

    while (y > 0) {
        const auto r = x % y;
        x = y;
        y = r;
    }
    return x;
}

bool isPrime(int x) {
    if (x == 2) return true;
    if (x < 2 || x % 2 == 0) return false;

    auto i = 3;
    while (i <= sqrt(x)) {
        if (x % i == 0) return false;
        i += 2;
    }
    return true;
}


int main() {
    ll n;
    cin >> n;
    auto R = Read(n);

    ll ans = -INF;
    ll R_min = INF;
    FOR(i, 1, n) {
        chmin(R_min, R[i - 1]);
        chmax(ans, R[i]- R_min);
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N;
  cin>>N;
  vector<long long> vec;
  for(long long i=0;i*i<=N;i++){
    long long a = i*i;
    vec.push_back(a);
  }
  reverse(vec.begin(),vec.end());
  cout<<vec.at(0)<<endl;
  return 0;
}

Measured memory_bytes: 640
<>=~/.* /;
map$s+=$_,@X=(0,glob<>);
@Y=glob<>.$';
while(@X){$s+=$Y[$j++]until$Y[$j]+$s>$';$\+=$-=$s>$'?0:$#X+$j-$\;$s-=pop@X}
print

Measured memory_bytes: 78968
#include<bits/stdc++.h>
using namespace std;
const static int MOD = 100000;

int M, N;
char S[20][20];
int dp[2][1 << 19][2][2]; // dp[i][j][k]: 旗の状態iで上の行がkのときの組み合わせ数

int main()
{
  cin >> M >> N;
  for(int i = 0; i < M; i++) {
    for(int j = 0; j < N; j++) {
      cin >> S[i][j];
    }
  }
  int BitMask = (1 << (N - 1)) - 1;
  dp[1][0][0][0] = 1;
  for(int i = 0; i < M * N; i++) {
    char& Cur = S[i / N][i % N];
    for(int bit = 0; bit < (1 << (N - 1)); bit++) {  // 上の行の状態
      for(int k = 0; k < 2; k++) {                   // よいはたかどうか
        for(int l = 0; l < 2; l++) {                 // 前Jを使ったかどうか
          if(dp[(i + 1) & 1][bit][k][l] == 0) continue;
          int NextBit = ((bit << 1) | (l && Cur == 'O')) & BitMask;
          if(Cur == 'J') {
            (dp[i & 1][NextBit][k][1] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
          } else if(Cur == 'O') {
            (dp[i & 1][NextBit][k][0] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
          } else if(Cur == 'I') {
            (dp[i & 1][NextBit][k | (i % N != N - 1 && ((bit >> (N - 2)) & 1))][0] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
          } else {
            (dp[i & 1][NextBit][k][1] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
            (dp[i & 1][((bit << 1)|l)&BitMask][k][0] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
            (dp[i & 1][NextBit][k | (i % N != N - 1 && ((bit >> (N - 2)) & 1))][0] += dp[(i + 1) & 1][bit][k][l]) %= MOD;
          }
          dp[(i + 1) & 1][bit][k][l] = 0;
        }
      }
    }
  }
  int ret = 0;
  for(int i = 0; i < (1 << (N - 1)); i++) {
    for(int k = 0; k < 2; k++) {
      (ret += dp[(M * N - 1) & 1][i][1][k]) %= MOD;
    }
  }
  cout << ret << endl;
}

Measured memory_bytes: 15852
#include <bits/stdc++.h>
#define N 1000000007
using namespace std;

long long n;
// a,t,g,c
long long dp[105][4][4][4] = {0};

long long solve();

int main() {
  cin >> n;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  dp[0][1][1][1] = 1;
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < 4; ++j)
      for(int k = 0; k < 4; ++k)
        for(int l = 0; l < 4; ++l) {
          // m l k j
          long long num = 0;
          if(l == 0 && k == 3 && j == 2) continue;
          if(l == 0 && k == 2 && j == 3) continue;
          if(l == 2 && k == 0 && j == 3) continue;
          for(int m = 0; m < 4; ++m) {
            if(m == 0 && k == 2 && j == 3) continue;
            if(m == 0 && l == 2 && j == 3) continue;
            num += dp[i][k][l][m];
            num %= N;
          }
          dp[i + 1][j][k][l] += num;
          dp[i + 1][j][k][l] %= N;
        }
  long long ans = 0;
  for(int i = 0; i < 4; ++i)
    for(int j = 0; j < 4; ++j)
      for(int k = 0; k < 4; ++k) {
        ans += dp[n][i][j][k];
        ans %= N;
      }
  return ans;
}

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

int go(vector<int>a,int n,int k){
	vector<int>dp(n+1,INT_MAX);
	dp[1]=0;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(i-j>=1){
				dp[i]=min(dp[i],abs(a[i]-a[i-j])+dp[i-j]);
			}
		}
	}
	return dp[n];
}
int main(){
	int n,k;
	cin>>n>>k;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<go(a,n,k);
}

Measured memory_bytes: 4244