akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::ops::Bound::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout]
fn main() {
    input! {
        n: usize,
        xy: [(i64, i64); n]
    }

    let mut xs = Vec::new();
    let mut ys = Vec::new();
    for (x, y) in xy {
        xs.push(x - y);
        ys.push(x + y);
    }
    let mut xmax = -1i64<<60;
    let mut xmin = 1i64<<60;
    for &x in &xs {
        xmax = max(xmax, x);
        xmin = min(xmin, x);
    }
    let mut ymax = -1i64<<60;
    let mut ymin = 1i64<<60;
    for &y in &ys {
        ymax = max(ymax, y);
        ymin = min(ymin, y);
    }
    let ans = max(xmax - xmin, ymax - ymin);
    println!("{}", ans);

}


Measured memory_bytes: 12376
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>

#define INF 1 << 29

using namespace std;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
char f[1003][1003];
bool visited[1003][1003][10];

class S{
public:
    int x;
    int y;
    int lvl;
    int step;

    S(int x, int y, int lvl, int step):x(x),y(y),lvl(lvl),step(step){}
};

int main(){
    int h,w,lvl,sx,sy,gx,gy;
    cin >> h >> w >> lvl;
    fill((char *)f, (char *)f+1003*1003, 'X');
    fill((bool *)visited, (bool *)visited+1003*1003*10, false);

    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin >> f[i][j];
            if(f[i][j] == 'S'){
                sx = j;
                sy = i;
            }else if(f[i][j] == lvl + '0'){
                gx = j;
                gy = i;
            }
        }
    }
    deque<S> q;
    q.push_back(S(sx,sy,1,0));
    visited[sy][sx][1] = true;
    int px,py,tmplvl,tmpstep;
    while(!q.empty()){
        px = q.front().x;
        py = q.front().y;
        tmplvl = q.front().lvl;
        tmpstep = q.front().step;
        q.pop_front();

        //printf("current:(y = %d, x = %d, lvl = %d, step = %d)\n", py,px,tmplvl,tmpstep);

        if(py == gy && px == gx && tmplvl == lvl+1){
            break;
        }
        visited[py][px][tmplvl] = tmpstep;
        for(int i=0;i<4;i++){
            int nx = px + dx[i];
            int ny = py + dy[i];

            if(f[ny][nx] != 'X'){
                if(f[ny][nx] == tmplvl +'0'){
                    q.push_back(S(nx,ny,tmplvl+1,tmpstep+1));
                }else{
                    if(!visited[ny][nx][tmplvl]){
                        q.push_back(S(nx,ny,tmplvl,tmpstep+1));
                        visited[ny][nx][tmplvl] = true;
                    }
                }
            }
        }
    }
    cout << tmpstep << endl;
}

Measured memory_bytes: 11000
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	var N, K int
	scanner.Scan()
	fmt.Sscanf(scanner.Text(), "%d %d", &N, &K)

	ans := 0

	// mod 0
	mod0 := N / K
	ans = ans + mod0*mod0*mod0

	// mod K / 2
	if K%2 == 0 {
		modK2 := (N + K/2) / K
		ans = ans + modK2*modK2*modK2
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
ll dp(ll n, ll x)
{
    ll res = 0;
    if (n == 0 && x == 1)
    {
        
        return 1;
    }
    else if (x == 1)
    {
        return 0;
    }
    else if (1 < x && x <= pow(2, n + 1) - 3 + 1)
    {
        //  cout << x << " " << n << pow(2, n + 1) - 3 + 1 << endl;
        res = dp(n - 1, x - 1);
    }
    else if (x == pow(2, n + 1) - 3 + 2)
    {
        //cout << "f3";
        res = pow(2, n); //2^(n+1)-1+1;
    }
    else if (pow(2, n + 1) - 3 + 2 < x && x < pow(2, n + 2) - 3)
    {
        // cout << "f4";
        res = pow(2, n) + dp(n - 1, x - pow(2, n + 1) + 3 - 2); //今までにどんぐらい食べたのか
    }
    else
    {
        // cout << "f5";
        res = pow(2, n + 1) - 1;
    }
    return res;
}
int main()
{
    ll n;
    ll x;
    cin >> n >> x;
    cout << dp(n, x);
    //まずレベルnバーガーがどのようなものなのかを理解しておかなければならない・
    //50だと10^15で大きさ的にはダメ。50でなんとかしたいところ。
    //pは2^(n+1)-1
    //大きさは2^(n+2)-3
    //x食べた時には、どの層に当たるのでしょうか。(1の時はB,2~an-1+1の時は下からx-1個食べた時と等しい、　a(n-1)+2はp,a(n-1)+3~2*a(n-1)+2だと、下から、x-)
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>

int cmpf1(const void * v1, const void * v2)
{
  return (int)(*((int *)v1)) - (int)(*((int *)v2));
}

int main()
{
  int i,n,last_d,c,t_c;
  int d[100000];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&(d[i]));
  }
  (void)qsort(d,n,sizeof(int),cmpf1);
  last_d = -1;
  t_c = c = 0;
  for(i=0;i<n;i++){
    if(d[i] != last_d){
      if(c>0){
        if( c>last_d ){
          t_c += c - last_d;
        } else if( c < last_d ){
          t_c += c;
        }
      }
      c = 0;
    }
    c ++;
    last_d = d[i];
  }
  if(c>0){
    if( c>last_d ){
      t_c += c - last_d;
    } else if( c < last_d ){
      t_c += c;
    }
  }
  printf("%d\n",t_c);
  
  return EXIT_SUCCESS;
}




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

int main()
{
    int num, current,sum=0,max=0;
    cin >> num;
    for(int i=0;i<num;i++){
        cin >> current;
        if(current > max){
            max = current;
        }
        sum += current;
    }

    if(max*2 >= sum){
        cout << "No" <<endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll   = long long;
using pll  = pair<ll,ll>;
using lls  = pair<pll,string>;
using vlls = vector<lls>;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define per(i,n) for(int i = (n)-1; i >= 0; --i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

string shrink(string s) {
    ll len = s.length();
    stack<char> stk;
    stk.push('$');
    rep(i,len) {
        if (stk.top() == '(' and s[i] == ')') {
            stk.pop();
        } else {
            // (, ), ((, )(, ))
            stk.push(s[i]);
        }
    }
    string res = "";
    while (stk.top() != '$') {
        res.push_back(stk.top());
        stk.pop();
    }
    reverse(all(res));
    // cerr << s << " -> " << res << endl;
    return res;
}

pll calc(string s) {
    string t = shrink(s);
    ll left  = count(all(t), '(');
    ll right = count(all(t), ')');
    return pll(left, right);
}

int main() {
    int n; cin >> n;
    vlls ss(n);
    rep(i,n) {
        cin >> ss[i].second;
        ss[i].first = calc(ss[i].second);
        // cerr << ss[i].first.first << ", " << ss[i].first.second << endl;
    }
    vlls former, latter;
    rep(i,n) {
        if (ss[i].first.first >= ss[i].first.second) former.push_back(ss[i]);
        else latter.push_back(ss[i]);
    }
    for (auto &v : former) {
        v.first.first = v.first.second;
    }
    for (auto &v : latter) {
        v.first.first = -v.first.first;
    }
    sort(all(former));
    sort(all(latter));

    string ans = "";
    for (auto &v : former) {
        ans += v.second;
    }
    for (auto &v : latter) {
        ans += v.second;
    }
    pll result = calc(ans);
    if (result.first == 0 and result.second == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 100780
c = []
c.append(list(map(int, input().split())))
c.append(list(map(int, input().split())))
c.append(list(map(int, input().split())))

ok = True
a = [0]*3
b = [0]*3
d = [0]*3
e = [0]*3
for i in range(3):
    a[i] = c[i][1]-c[i][0]
    b[i] = c[i][2]-c[i][1]
    d[i] = c[1][i]-c[0][i]
    e[i] = c[2][i]-c[1][i]
    
if a[0] != a[1] or a[0] != a[2] or a[1] != a[2]:
    ok = False
elif b[0] != b[1] or b[0] != b[2] or b[1] != b[2]:
    ok = False
elif d[0] != d[1] or d[0] != d[2] or d[1] != d[2]:
    ok = False
elif e[0] != e[1] or e[0] != e[2] or e[1] != e[2]:
    ok = False

if ok:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

const int MAX_H = 1010;
const int MAX_W = 1010;

int d[MAX_H][MAX_W];

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

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    rep(i, H) cin >> s[i];
    rep(i, H) rep(j, W) d[i][j] = INF;
    queue<pii> q;
    rep(i, H) rep(j, W) if(s[i][j] == '#') {
        d[i][j] = 0;
        q.push(make_pair(i, j));
    }
    auto isOutOfRange = [](int h, int w, int H, int W) {
        return h < 0 || h >= H || w < 0 || w >= W;
    };
    
    while(!q.empty()) {
        auto p = q.front();
        q.pop();
        int x = p.se;
        int y = p.fi;
        rep(i, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if(isOutOfRange(ny, nx, H, W) || d[ny][nx] <= d[y][x]+1) continue;
            d[ny][nx] = d[y][x] + 1;
            q.push(make_pair(ny, nx));
        }
    }
    int ans = 0;
    rep(i, H) rep(j, W) ans = max(ans, d[i][j]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13456
#include<stdio.h>
#include<stdlib.h>

#define MAX 100001
#define SENTINEL 1000000000

typedef struct{  
  int value;
  char c;
}Record;

void marge (Record A[],int left ,int mid,int right){
  int n1,n2,i,j,k;
  Record L[MAX/2+1],R[MAX/2+1];
  
  n1 = mid - left;
  n2 = right - mid;
  
  for(i=0; i<n1; i++) L[i]= A[left+i];
  for(i=0; i<n2; i++) R[i]= A[mid+i];

  L[n1].value = SENTINEL;
  R[n2].value = SENTINEL;
  i = j = 0;
  
  for(k=left; k < right; k++){
    if(L[i].value <= R[j].value){
      A[k] = L[i++];
    }
    else{
      A[k] = R[j++];
    }
  }
}

void margeSort(Record A[],int left,int right){
  int mid;
  if (left+1 < right){
    mid = (left + right)/2;
    margeSort(A,left,mid);
    margeSort(A,mid,right);
    marge(A,left,mid,right);
  }
}

int partition(Record B[],int p,int r){
  int x,i,j;
  Record temp;
  x = B[r].value;
  i=p-1;
  for(j=p; j<r; j++){
    if(B[j].value <= x){
      i++;
      temp = B[i];
      B[i] = B[j];
      B[j] = temp;
    }
  }
  temp = B[i+1];
  B[i+1] = B[r];
  B[r] = temp;
  
  return i+1;
}

void quickSort(Record B[],int p, int right){
  int k;
  if(p < right){
    k=partition(B,p,right);
    quickSort(B,p,k-1);
    quickSort(B,k+1,right);
  }
}


int main(){
  int i,j,n,l,stable;
  Record A[MAX],B[MAX];
  char s[100];


  
  scanf("%d",&n);
  for(i=0; i<n; i++){
    scanf("%s %d",s,&l);
    A[i].c = B[i].c =s[0];
    A[i].value = B[i].value =l;
  }
  margeSort(A,0,n);
  quickSort(B,0,n-1);

  stable = 1;
  for(i=0; i<n; i++){
    if(A[i].c != B[i].c)stable =0;
  }

  if(stable == 1)printf("Stable\n");
  else printf("Not stable\n"); 
  
  for(i=0; i<n;i++){
    printf("%c %d",B[i].c,B[i].value);
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 4064
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    if (i % 3 != 0 && i % 5 != 0) ans+=i;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(v) v.begin(),v.end()
#define vi vector<int> 
#define mod 1000000007
#define inf 1e17
#define fs first
#define ss second

template <typename T> 
void amax(T& x, T y) 
{ 
    if( x < y) x = y;
} 

template <typename T> 
void amin(T& x, T y) 
{ 
    if( x > y) x = y;
} 



int main(){
     
    int n,m;
    cin >> n >> m;
    
    int a = min(n,m);
    int b = max(n,m);
    
    for(int i =0;i<b;i++) cout<<a;

}


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

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

// repetition
//------------------------------------------
#define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)
#define REP(i, n) for (long long i = 0; i < (n); ++i)

// modint: mod 計算を int を扱うように扱える構造体
template <int MOD>
struct Fp {
  long long val;
  constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  constexpr int getmod() {
    return MOD;
  }
  constexpr Fp operator-() const noexcept {
    return val ? MOD - val : 0;
  }
  constexpr Fp operator+(const Fp& r) const noexcept {
    return Fp(*this) += r;
  }
  constexpr Fp operator-(const Fp& r) const noexcept {
    return Fp(*this) -= r;
  }
  constexpr Fp operator*(const Fp& r) const noexcept {
    return Fp(*this) *= r;
  }
  constexpr Fp operator/(const Fp& r) const noexcept {
    return Fp(*this) /= r;
  }
  constexpr Fp& operator+=(const Fp& r) noexcept {
    val += r.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp& operator-=(const Fp& r) noexcept {
    val -= r.val;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp& operator*=(const Fp& r) noexcept {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp& operator/=(const Fp& r) noexcept {
    long long a = r.val, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr bool operator==(const Fp& r) const noexcept {
    return this->val == r.val;
  }
  constexpr bool operator!=(const Fp& r) const noexcept {
    return this->val != r.val;
  }
  friend constexpr ostream& operator<<(ostream& os, const Fp<MOD>& x) noexcept {
    return os << x.val;
  }
  friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
    if (n == 0) return 1;
    auto t = modpow(a, n / 2);
    t = t * t;
    if (n & 1) t = t * a;
    return t;
  }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;
vector<ll> v;
ll n, k;
vector<ll> a, b;

void junjotui() {
  REP(i, n) {
    if (i == n - 1) {
      a[n - 1] = 0;
      continue;
    }
    int num = v[i];
    int cnt = 0;
    FOR(j, i + 1, n - 1) {
      if (v[j] < v[i]) {
        cnt++;
      }
    }
    a[i] = cnt;
  }
  return;
}

void miman() {
  REP(i, n) {
    int cnt = 0;
    REP(j, n) {
      if (v[j] < v[i]) {
        cnt++;
      }
    }
    b[i] = cnt;
  }
  return;
}

int main() {
  cin >> n >> k;
  v.resize(n);
  a.resize(n);
  b.resize(n);
  REP(i, n) {
    cin >> v[i];
  }
  junjotui();
  miman();
  mint ans = 0;

  REP(i, n) {
    mint tmp = a[i] * k;
    mint tmp2 = b[i];
    tmp2 = tmp2 * k * (k - 1) / 2;
    ans += tmp;
    ans += tmp2;
  }

  ANS(ans);

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

 int main()
 {

 int a[10000], min, max, n, i;
 long long sum = 0;
 scanf("%d", &n);//1以上が入力されるものとします
for(i = 0; i < n; i++){
 scanf("%d", &a[i]);
 sum += a[i];
 }
 max = min = a[0];//とりあえず最初の要素をセットしておく
for(i = 1; i < n; i++){//2番目以降の要素と比較
if(a[i] > max)max = a[i];
 if(a[i] < min)min = a[i];
 }
 printf("%d %d %lld\n", min, max, sum);

 return 0;
 }


Measured memory_bytes: 2104
N , M = map(int,input().split())
if N % 2 != 0:
    start = 1
    end = N
    for i in range(M):
        print(start,end)
        start += 1
        end -= 1
else:
    start = 1
    end = N
    judge = True
    for i in range(M):
        print(start,end)
        start += 1
        end -= 1
        if (end - start) <= N // 2 and judge:
            start += 1
            judge = False

Measured memory_bytes: 9280
n, k, l = map(int, raw_input().split())

def root(x):
    if x != parent[x]: parent[x] = x = root(parent[x])
    return x
def unite(x, y):
    px = root(x)
    py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py

parent = range(n)
for i in xrange(k):
    p, q = map(int, raw_input().split())
    unite(p-1, q-1)
parent1 = parent
for i in xrange(n):root(i)

parent = range(n)
for i in xrange(l):
    r, s = map(int, raw_input().split())
    unite(r-1, s-1)
parent2 = parent
for i in xrange(n):root(i)

dic = {}
for p1, p2 in zip(parent1, parent2):
    dic[p1, p2] = dic.get((p1, p2), 0) + 1

ans = [dic[p1, p2] for p1, p2 in zip(parent1, parent2)]
print " ".join(map(str, ans))


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

int main(){
	int k;
	queue<long long> q;
	long long x;
	
	cin >> k;
	for(int i = 1;i<=9;i++){
                q.push(i);
        }

	for(int j = 1;j<=k;j++){
		x = q.front();
		q.pop();
		if(x % 10 != 0){
			q.push(10*x + (x%10) - 1);
		}
		q.push(10*x + (x%10));
		if(x % 10 != 9){
			q.push(10*x + (x%10) + 1);
		}
	}
	cout << x << endl;
}

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

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define P pair<int , int>
#define V vector<int>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
	int n, d;	cin >> n >> d;

	int ans = n / (2 * d + 1);
	if(n % (2 * d + 1) != 0) ans += 1;

	SCOUT(ans) << endl;

	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    Program().solve()
}

class Program {
    fun solve() {
        val sc = MyScanner()
        val n = sc.nextInt()
        val a = sc.intList()

        var sum = ModInt(0)
        var sum2 = ModInt(0)

        for (i in 0 until n) {
            sum += a[i];
            sum2 += a[i].toLong() * a[i]
        }

        val t = sum * sum - sum2
        println(t / 2)
    }
}

class ModInt(_num: Number) : Number() {
    companion object {
        const val mod: Long = 1000000007L
    }

    private val num: Long = if (_num.toLong() < 0) (_num.toLong() % mod) + mod else _num.toLong() % mod
    operator fun plus(right: Number) = ModInt(num + (right.toLong() % mod))
    operator fun minus(right: Number) = ModInt(num - (right.toLong() % mod))
    operator fun times(right: Number) = ModInt(num * (right.toLong() % mod))

    // modが素数の時のみ
    operator fun div(right: Number) = this * ModInt(right).inverse()

    fun power(n: Number): ModInt {
        var a = this
        var result = ModInt(1)
        var tmp = n.toLong()
        while (tmp > 0) {
            if (tmp % 2 == 1L) {
                result *= a
            }
            tmp /= 2
            a *= a
        }
        return result
    }

    // modが素数のときのみ 逆元
    fun inverse(): ModInt {
        return power(mod - 2L)
    }

    override fun toString() = num.toString()
    override fun toInt() = num.toInt()
    override fun toLong() = num
    override fun toByte() = num.toByte()
    override fun toChar() = num.toChar()
    override fun toDouble() = num.toDouble()
    override fun toFloat() = num.toFloat()
    override fun toShort() = num.toShort()
}

class MyScanner {
    private var ptr = 0
    private var l = listOf<String>()

    fun next(): String {
        while (l.size <= ptr) {
            l = readLine()!!.split(' ')
            ptr = 0
        }
        return l[ptr++]
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextDouble() = next().toDouble()
    fun nextCharArray() = next().toCharArray()
    fun nextChar() = next()[0]

    fun list(): List<String> {
        ptr = l.size
        return readLine()!!.split(' ')
    }

    fun intList() = list().map { s -> s.toInt() }
    fun longList() = list().map { s -> s.toLong() }
    fun doubleList() = list().map { s -> s.toDouble() }

    fun array() = list().toTypedArray()
    fun intArray() = intList().toIntArray()
    fun longArray() = longList().toLongArray()
    fun doubleArray() = doubleList().toDoubleArray()
}


Measured memory_bytes: 69716
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
ll mpow(ll x, ll y, ll m) {
    if(y == 0) {
        return 1;
    } else {
        ll z = mpow(x, y / 2, m);
        return z * z % m * (y % 2 ? x % m : 1) % m;
    }
}
const ll MOD = 1000000007;
ll count_digits(ll d) {
    return 9 * mpow(10, d - 1, MOD) % MOD;
}
ll f(ll n) {
    ll ans = 0;
    while(n > 0) {
        n /= 10;
        ans++;
    }
    return ans;
}
vector<ll> divisors(ll n) {
    vector<ll> ans;
    for(ll d = 1; d * d <= n; d++) {
        if(n % d == 0) {
            ans.push_back(d);
            if(d * d != n) {
                ans.push_back(n / d);
            }
        }
    }
    return ans;
}
void solve(long long S) {
    vector<ll> F(23'000'000);
    ll ans = 0;
    for(ll L = 1, R = 1; L < 10'000'000; L++) {
        while((F[R] = F[R - 1] + f(R)) - F[L - 1] < S) {
            R++;
        }
        ans += F[R] - F[L - 1] == S;
        ans %= MOD;
    }
    ans += S / 8;
    ans %= MOD;
    for(ll d : divisors(S)) {
        if(d >= 8) {
            ans += count_digits(d) - S / d + MOD;
            ans %= MOD;
        }
    }
    cout << ans << endl;
}
int main() {
    long long S;
    scanf("%lld",&S);
    solve(S);
    return 0;
}


Measured memory_bytes: 179968
#include <bits/stdc++.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep_1 (i,j,n) for(int i=j;i<n;i++)
typedef long long ll;
typedef long l;
const ll l_INF = 1010101010101010;
const int INF = 1010101010;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(){
  int k; cin>>k;
  ll s=7;
  int ans=-1;
  ll x=7;
  if(k==1||k==7){
    cout<<1<<endl;
    return 0;
  }else if(k==11||k==77){
    cout<<2<<endl;
    return 0;
  }
  rep(i,1010100){
    x*=10;
    x%=k;
    s+=x;
    s%=k;
    if(s==0){
      ans=i+2;
      break;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define INF 800000000
#define MAX 1000

int main(){
  int H,W;
  cin>>H>>W;
  vector<vector<char>> s(H+2,vector<char>(W+2,'.'));
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>s.at(i).at(j);
    }
  }
  vector<vector<int>> count(H+2,vector<int>(W+2,0));
  if(s.at(1).at(1)=='.'){
    count.at(1).at(1)=0;
  }else{
    count.at(1).at(1)=1;
  }
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      if(i==1&&j==1){
        continue;
      }
      if(i==1){
        if(s.at(i).at(j-1)!=s.at(i).at(j)){
          count.at(i).at(j)=count.at(i).at(j-1)+1;
        }else{
          count.at(i).at(j)=count.at(i).at(j-1);
        }
      }else if(j==1){
        if(s.at(i-1).at(j)!=s.at(i).at(j)){
          count.at(i).at(j)=count.at(i-1).at(j)+1;
        }else{
          count.at(i).at(j)=count.at(i-1).at(j);
        }
      }else{
        int x=0;
        int y=0;
        if(s.at(i).at(j)!=s.at(i-1).at(j)){
          x=1;
        }
        if(s.at(i).at(j)!=s.at(i).at(j-1)){
          y=1;
        }
        count.at(i).at(j)=min(count.at(i-1).at(j)+x,count.at(i).at(j-1)+y);
      }
    }
  }
  int A=count.at(H).at(W);
  if(A==0){
    cout<<0<<endl;
  }else{
    cout<<(A-1)/2+1<<endl;
  }
}


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

#define ll long long
#define INF 1<<31-1
#define LNF 9223372036854775807
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define MOD 1000000007
//#define MOD 998244353
#define NUM 200010
 
void swap(int* a,int* b){int tmp=*a;*a=*b;*b=tmp;}
int abs(int a){if(a<0)return -a;return a;}
int dup(int a,int d){if(a%d==0)return a/d;else return a/d+1;}
int mod(int a,int m){if(a<0)return a%m+m;else return a%m;}

void swapl(ll* a,ll* b){ll tmp=*a;*a=*b;*b=tmp;}
ll absl(ll a){if(a<0)return -a;return a;}
ll dupl(ll a,ll d){if(a%d==0)return a/d;else return a/d+1;}
ll modl(ll a,ll m){if(a<0)return a%m+m;else return a%m;}

ll GCD(ll a,ll b){ll c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
ll LCM(ll a,ll b){return a*b/GCD(a,b);}

ll factorial(ll n, ll m) {return n < m ? 1 : n*factorial(n-1, m);}

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

// ll dp[]

ll func1(ll h){
    if (h == 1) return 1;
    
    return 1 + 2*func1(h/2);
}

int main(){
  ll H, A;
  

  scanf("%lld%lld", &H);

  
    printf("%lld\n", func1(H));
  
  
  return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas& x,ddatas& y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

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

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}
void judgement(int a){
  if(a){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  if(a){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}

int main(){
  startupcpp();
  ll i,N,M;
  cin>>N>>M;N++;M++;
  vec a(N),b(M);
  cin>>a[0]>>b[0];
  rep1(i,N)cin>>a[i];
  rep1(i,M)cin>>b[i];
  vrsort(a);
  vsort(b);
  if(a[0]<b[0])cout<<"No ";
  cout<<"War"<<endl;
  return 0;
}

Measured memory_bytes: 256
import java.math.*;
import java.util.Scanner;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		String a = scn.next();
		if((int)a.charAt(0)>96) {
			System.out.println('a');
		}else {
			System.out.println('A');
		}
	}
}	

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

int main() {
  int64_t a, b, c;
  cin >> a >> b >> c;

  int64_t d = c - a - b;
  
  if(d > 0 && d * d > 4 * a * b) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}


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

//{{{
/********************************************************************/
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef queue<int> qi;
typedef stack<int> si;
typedef deque<int> dqi;

#define reps(i, a, b) for (int i = a; i < b; ++i)
#define rep(i, n) reps(i, 0, n)
#define REPS(i, a, b) reps(i, a, b)
#define REP(i, n) rep(i, n)
#define deps(i, a, b) for (int i = a; i >= b; --i)
#define dep(i, n) deps(i, n, 0)
#define DEPS(i, a, b) deps(i, a, b)
#define DEP(i, n) dep(i, n)

#define pf push_front
#define pb push_back
#define mp make_pair
#define fst first
#define FST fst
#define sec second
#define SEC sec
#define sz(obj) ((int)(obj).size())
#define all(v) (v).begin(), (v).end()
#define ALL(v) all(v)
#define endl '\n'

const int INF = 999999999;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

//vector<string> split(const string &s, char delim) {
//  vector<string> elems;
//  string item;
//  for (char ch: s) {
//    if (ch == delim) {
//      if (!item.empty()) elems.push_back(item);
//      item.clear();
//    }
//    else item += ch;
//  }
//  if (!item.empty()) elems.push_back(item);
//  return elems;
//}

inline bool inside(int y, int x, int H, int W) { return y >= 0 && x >= 0 && y < H && x < W; }
inline int in() { int x; std::cin >> x; return x; }
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << '\n';
}
template <typename T> void print(T x) { std::cout << x << '\n'; }

/****************************************************************/
//}}}

int a[100005];
signed main()
{
  int n = in();
  int k = 0;
  rep(i, n) a[in()]++;
  rep(i, 100005) if (a[i]) k++;
  
  if (k & 1) print(k);
  else print(k - 1);

  return (0);
}

Measured memory_bytes: 640
#ifdef DEBUG_IS_VALID
#define DEB 1 
#define _LIBCPP_DEBUG 0
#else
#define DEB 0
#define NDEBUG
#endif

#include <bits/stdc++.h>
using namespace std;

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize ("-O3")

using namespace std;

#define DUMPOUT cout
#define dump(...) if(DEB) DUMPOUT<<"  "<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl<<"    "; if(DEB) dump_func(__VA_ARGS__)
template<typename T1,typename T2>ostream& operator << (ostream& os, pair<T1,T2> p){cout << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename T>ostream& operator << (ostream& os, vector<T>& vec) { os << "{"; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "}"; return os; }
template<typename T>ostream& operator << (ostream& os, set<T>& st){cout << "{"; for(auto itr = st.begin(); itr != st.end(); itr++) cout << *itr << (next(itr)!=st.end() ? ", " : ""); cout << "}"; return os;}
template<typename T1,typename T2>ostream& operator << (ostream& os, map<T1,T2> mp){cout << "{"; for(auto itr = mp.begin(); itr != mp.end(); itr++) cout << "(" << (itr->first) << ", " << (itr->second) << ")" << (next(itr)!=mp.end() ? "," : ""); cout << "}"; return os; }

void dump_func(){DUMPOUT << endl;}
template <class Head, class... Tail>void dump_func(Head&& head, Tail&&... tail){ DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...);}
template<class T> inline bool chmax(T& a,T const& b){if(a>=b) return false; a=b; return true;}
template<class T> inline bool chmin(T& a,T const& b){if(a<=b) return false; a=b; return true;}

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<Pl>;
using vvp = vector<vp>;

const int INF = 1<<29;
const long long LINF=1LL<<59;


void solve(long long N, std::vector<std::string> s){
  map<vl,ll> mp;
  rep(i,N){
    vl vec(26);
    rep(j,10) vec[int(s[i][j]-'a')]++;
    mp[vec]++;
  }
  ll ans = 0;
  for(auto& p:mp){
    if(p.second) ans += p.second * (p.second-1LL);
  }
  cout << ans/2LL << endl;
}

int main(){
  std::cout << std::fixed << std::setprecision(15);
  long long N;
  scanf("%lld",&N);
  std::vector<std::string> s(N);
  for(int i = 0 ; i < N ; i++){
    std::cin >> s[i];
  }
  solve(N, std::move(s));
  return 0;
}


Measured memory_bytes: 36992
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
int mod =1000000007;
const double PI = acos(-1);

int main(){
    ll a,b,c;cin>>a>>b>>c;
    ll ans = b/c-a/c;
    if(a%c==0)ans++;
    cout<<ans<<endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <utility> 
#include <tuple>
#include <iterator>
#include <functional>
using namespace std;
#define rep(i,n) for(long i=0; i<n; i++)





void solve(){
  int n,x;
  cin >> n >> x;
  int L[n+10];
  rep(i,n){
    cin >> L[i]; 
  }
  int count = 0;
  int sum = 0;
  while(sum <= x){
    sum += L[count];
    count ++ ;
  }
  cout << count << endl;
}

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


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W)->np.ndarray:
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N, K = ints()
A = read_matrix(N, N)


from numba import njit


@njit('i8[:,:](i8[:,:],i8[:,:])', cache=True)
def matmul_mod(X: np.ndarray, Y: np.ndarray)->np.ndarray:
    MOD = 10**9 + 7
    # return X @ Y
    ret = np.empty((X.shape[0], Y.shape[1]), dtype=np.int64)
    for i in range(X.shape[0]):  # Xの行
        for j in range(Y.shape[1]):  # Yの列
            tmp = (X[i, :] * Y[:, j]) % MOD
            ret[i, j] = tmp.sum() % MOD
    return ret


A_double = np.asanyarray(A, dtype=np.int64)
ans = np.eye(N, dtype=np.int64)
for j in range(int(K).bit_length()):
    if (K >> j) & 1:
        ans = matmul_mod(ans, A_double)
    A_double = matmul_mod(A_double, A_double)

print(ans.sum() % MOD)




Measured memory_bytes: 122044
using System;
using static System.Console;
using System.Linq;

namespace Main
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] tmp;
            tmp = ReadLine().Split(' ').Select(long.Parse).ToArray();
            long N = tmp[0];
            long M = tmp[1];
            tmp = ReadLine().Split(' ').Select(long.Parse).ToArray();
            WriteLine(N >= tmp.Sum() ? N - tmp.Sum() : -1);
        }
    }
}

Measured memory_bytes: 20532
//50000 for aizu0056
//1000000 for aizu0185
#define M 32769
p[M+1];


int main(){
  int n,i=2,j;
  p[1]=1;
  for(;i<=M;i++)
    if(!p[i])
      for(j=i*2;j<=M;j+=i)
        p[j]=1;
  for(;scanf("%d",&n),n;){
    int i=2,s=0;
    for(;i<=n/2;i++){
      if(p[i])continue;
      if(!p[n-i]){
        s++;
      }
    }
    printf("%d\n",s);
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	
	for(int i=0;i<s1.size();i++)
	{
		if(s1[i]!=s2[i])
		{
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        if (y % 2 == 0 && 4 * x >= y && 2 * x <= y) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

}


Measured memory_bytes: 35700
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef long double ld;

int main(){
    ll a,b,c;
    cin >> a >> b >> c;
    if (a<=c && b>=c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef long double D;
//typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){int i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}

vector<int> uft;

int parent(int a){return uft[a]==a?a:uft[a]=parent(uft[a]);}

void merge(int a,int b){uft[parent(a)]=parent(b);}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W;
  cin>>H>>W;
  vector<string> A(H);
  cin>>A;
  vector<string> C={{'6','3','1','4'},{'2','#','2','#'},{'1','3','6','4'},{'5','#','5','#'}};
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(A[i][j]!=C[i%4][j%4]){A[i][j]='#';}
    }
  }
  uft.resize(H*W);
  for(int i=0;i<H*W;i++){uft[i]=i;}
  vector<int> dx={1,0,-1,0};
  vector<int> dy={0,1,0,-1};
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      for(int k=0;k<4;k++){
        int x=i+dx[k],y=j+dy[k];
        if(0<=x && x<H && 0<=y && y<W && A[i][j]!='#' && A[x][y]!='#'){merge(x*W+y,i*W+j);}
      }
    }
  }
  cout<<(parent(H*W-1)==parent(0)?"YES":"NO")<<endl;
  

  return 0;
}



Measured memory_bytes: 3280
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  int i;
  cin>>i;
  for(int j = 0 ; j<i ; j++){
    cin>>a>>b>>c;
  if(a*a == b*b+c*c)
    cout<<"YES"<<endl;
  else if(b*b == a*a+c*c)
    cout<<"YES"<<endl;
  else if(c*c == b*b+a*a)
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
  }
  return 0;
}

Measured memory_bytes: 2972
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1e9
#define LIMIT 16
typedef vector<int> Vec;
 
const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};
int res;
bool flg;
 
bool inField(int y,int x){
  return 0 <= y && y < 3 && 0 <= x && x < 3; 
}
 
bool check(Vec &vec){
  for(int i = 0 ; i < 8 ; i++){
    if(vec[i] != i+1) return false;
  }
  return true;
}
 
void solve(Vec &start,int z,map<Vec,int> &cost){
  queue<Vec> Q;
  queue<int> zero;
  Q.push(start); zero.push(z);
  cost[start] = 0;
   
  while(!Q.empty()){
    Vec now = Q.front(); Q.pop();
    int pos = zero.front(); zero.pop();
    int x = pos % 3, y = pos / 3;
    if(!flg && check(now)){
      res = cost[now];
      return;
    }
    if(cost[now] == LIMIT) break;
    for(int i = 0 ; i < 4 ; i++){
      int nx = x + dx[i], ny = y + dy[i];
      if(!inField(ny,nx)) continue;
      vector<int> next = now;
      swap(next[pos],next[ny*3+nx]);
      if(!cost.count(next)){
        cost[next] = cost[now] + 1;
        Q.push(next);
        zero.push(ny*3+nx);
      }
    }
  }
}
 
int main(){
  int z = -1;
  vector<int> start(9),goal(9);
  for(int i = 0 ; i < 9 ; i++){
    cin >> start[i];
    goal[i] = i+1;
    if(start[i] == 0) z = i;
  }
  goal[8] = 0;
  res = INF; flg = false;
  map<Vec,int> s2v,g2v;
  solve(start,z,s2v);
  if(res == INF){
    flg = true;
    solve(goal,8,g2v);
  }
  map<Vec,int>::iterator s,g;
  for(s = s2v.begin() ; s != s2v.end() ; ++s){
    if(g2v[s->first]){
      res = min(res,s->second+g2v[s->first]);
    }
  }
  cout << res << endl;
  return 0;
}

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

int main() {
  int A,B;
  cin>>A>>B;
  string S;
  cin>>S;
  if(S[B-1]=='A'){
    S[B-1]='a';
  }
  if(S[B-1]=='B'){
    S[B-1]='b';
  }
  if(S[B-1]=='C'){
    S[B-1]='c';
  }
  cout<<S<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxs=6e5,mod=998244353;
int n,m,s;
long long Ans,fac[maxs],inv[maxs],pown[maxs],powm[maxs];
inline long long read(){
	long long x=0,f=1;
	char c;
	do{c=getchar();if(c=='-') f*=-1;}while(!isdigit(c));
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
long long qpow(long long x,int i){
	long long res=1;
	while(i){
		if(i&1) res=res*x%mod;
		x=x*x%mod;i>>=1;
	}
	return res;
}
long long C(int a,int b){return inv[b]*inv[a-b]%mod*fac[a]%mod;}
long long F(int k){return C(n,k)*C(m,k)%mod*fac[k]%mod*(pown[m-k]*powm[n-k]%mod)%mod;}
int main(){
	n=read();m=read();Ans=0;
	s=max(n,m);
	fac[0]=1;
	for(int i=1;i<=s;i++){fac[i]=fac[i-1]*i%mod;}
	inv[s]=qpow(fac[s],mod-2);
	for(int i=s;i>=1;i--){inv[i-1]=inv[i]*i%mod;}
	pown[0]=powm[0]=1;
	for(int i=1;i<=s;i++){
		pown[i]=pown[i-1]*(n+1)%mod;
		powm[i]=powm[i-1]*(m+1)%mod;
	}
	for(int i=0;i<=min(n,m);i++){Ans=(Ans+mod+(i%2==0?1:-1)*(F(i)))%mod;}
	printf("%lld\n",Ans);
	return 0;
}

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

int n,m;
double l,p[111],t[111],v[111],ans;
double dp[111][111][111],T[111][111];

int main(){
  cin>>n>>m>>l;
  r(i,n)cin>>p[i]>>t[i]>>v[i],p[i]/=100;
  r(i,n){
    dp[i][0][0]=1;
    r(j,m+1){
      if(j!=m)r(k,j+1){
        dp[i][j+1][k+1]+=dp[i][j][k]*p[i];
        dp[i][j+1][k]+=dp[i][j][k]*(1.0-p[i]);
      }
      if(v[i]>0)T[i][j]=l/v[i]+t[i]*j;
      else T[i][j]=1e9;
    }
  }
  r(i,n){
    ans=0;
    if(v[i]==0){
      cout<<0<<endl;
      continue;
    }
    r(j,m+1){
      double p=dp[i][m][j];
      r(k,n)if(k!=i){
        double sum=0;
        r(x,m+1) if(T[i][j]<T[k][x]) sum+=dp[k][m][x];
        p*=sum;
      }
      ans+=p;
    }
    printf("%.9f\n",ans);
  }
}


Measured memory_bytes: 8016
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w;
  cin>>h>>w;
  vector<string> s(h);
  for(int i=0;i<h;i++)
    cin>>s.at(i);
  vector<int> dy={-1,1,0,0};
  vector<int> dx={0,0,-1,1};
  vector<vector<int>> d(h,vector<int>(w,h*w));
  d.at(0).at(0)=1;
  queue<vector<int>> q;
  q.push({0,0,1});
  while(!q.empty()){
    auto a=q.front();
    q.pop();
    int y=a.at(0);
    int x=a.at(1);
    int dxy=a.at(2);
    for(int m=0;m<4;m++){
      int my=y+dy.at(m);
      int mx=x+dx.at(m);
      if(0<=my&&my<h&&0<=mx&&mx<w&&d.at(my).at(mx)==h*w&&s.at(my).at(mx)=='.'){
        d.at(my).at(mx)=dxy+1;
        q.push({my,mx,dxy+1});
      }
    }
  }
  int v=0;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      v+=(s.at(i).at(j)=='.'?1:0);
  cout<<max(v-d.at(h-1).at(w-1),-1)<<endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <stack>
#define ll long long
using namespace std;

string solve(string a, string b){
    int n1=a.length(), n2=b.length();
    int dp[n1+1][n2+1];
    for(int i=0;i<=n1;i++){
        for(int j=0;j<=n2;j++){
            if(i==0 || j==0){
                dp[i][j]=0;
            }
            else{
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
    }
    string res;
    res.resize(dp[n1][n2]);
    int i=n1, j=n2;
    int idx=dp[n1][n2];
    while(i>0 && j>0){
        if(a[i-1]==b[j-1]){
            res[idx-1] = a[i-1]; 
            i--;
            j--;
            idx--;
        }
        else if(dp[i][j] == dp[i-1][j] || dp[i][j-1]){
            if(dp[i][j-1]>dp[i-1][j]){
                j--;
            }
            else{
                i--;
            }
        }
    }
    return res;
}


int main() {
    string a, b;
    cin >> a;
    cin >> b;
    cout << solve(a, b)<< endl;
    return 0;    
}


Measured memory_bytes: 38788
S = list(map(str, input()))
N = len(S)+1
List = [0]*N
rightcount = 0
leftcount = 0

if S[0] == "<":
    leftcount+=1
else:
    rightcount+=1

for i in range(1, N-1):
    if S[i] == "<":
        leftcount+=1
        if S[i-1] == "<":
            List[i] = List[i-1]+1
        elif S[i-1] == ">":
            for j in range(rightcount):
                List[i-j] = j
            if List[i-rightcount]<=List[i-rightcount+1]:
                List[i-rightcount] = List[i-rightcount+1] + 1
            rightcount = 0


    if S[i] == ">":
        rightcount+=1
        if S[i-1] =="<":
            for j in range(leftcount+1):
                List[i-j] = leftcount - j
            leftcount = 0

if S[N-2] == "<":
    List[N-1] = List[N-2] + 1
else:
    for j in range(rightcount):
        List[N-1-j] = j
    if List[N-1-rightcount]<=List[N-1-rightcount+1]:
        List[N-1-rightcount] = List[N-1-rightcount+1] + 1

print(sum(List))


Measured memory_bytes: 27584
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
	const int maxn=100050;
	int n,m;	
	bool bl[maxn];
	int h[maxn];
	int ans;
	int main() {
		IOS
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			cin>>h[i];
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			if(h[a]==h[b]){
				bl[a]=bl[b]=1;
			}
			else if(h[a]>h[b]){
				bl[b]=1;
			}
			else
				bl[a]=1;
		}		
		for(int i=1;i<=n;i++)
			if(bl[i]==0)
				ans++;
		cout<<ans<<endl;
	}

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

using namespace std;

typedef long long ll;

#define mp make_pair

map<pair<int, int>, bool>vis;
vector<pair<int, int> >v;
int n;
set<pair<int, int> >diffs;

int calcStarts(int dX, int dY)
{
    int ret = 0;
    map<pair<int, int>, bool>curVis = vis;
    for(int i = 0; i < n; i++)
    {
        if(curVis[v[i]])
        {
            continue;
        }
        ret++;
        pair<int, int>curVal = v[i];
        while(curVis.count(curVal) && !curVis[curVal])
        {
            curVis[curVal] = 1;
            curVal.first += dX;
            curVal.second += dY;
        }
    }

    return ret;
}

int main()
{
    while(cin >> n)
    {
        v.resize(n);
        for(int i = 0; i < n; i++)
        {
            cin >> v[i].first >> v[i].second;
            vis[v[i]] = 0;
        }

        sort(v.begin(), v.end());
        diffs.clear();
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                diffs.insert(mp(v[j].first - v[i].first, v[j].second - v[i].second));
            }
        }

        int res = n;
        int dX, dY;
        for(auto it = diffs.begin(); it != diffs.end(); it++)
        {
            dX = it->first;
            dY = it->second;
            res = min(res, calcStarts(dX, dY));
        }

        cout << res << endl;
    }

    return 0;
}


Measured memory_bytes: 256