akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;

		while((str=br.readLine()) != null){
			double weight = Double.parseDouble(str);
			System.out.println(Judge(weight));
		}

	}

	static String Judge(double w){
		String weight="";
		if(w <= 48){
			weight="light fly";
		}else if(48<w && w<=51){
			weight="fly";
		}else if(51<w && w<=54){
			weight="bantam";
		}else if(54<w && w<=57){
			weight="feather";
		}else if(57<w && w<=60){
			weight="light";
		}else if(60<w && w<=64){
			weight="light welter";
		}else if(64<w && w<=69){
			weight="welter";
		}else if(69<w && w<=75){
			weight="light middle";
		}else if(75<w && w<=81){
			weight="middle";
		}else if(81<w && w<=91){
			weight="light heavy";
		}else if(91<w){
			weight="heavy";
		}
		return weight;
	}

}

Measured memory_bytes: 16904
x,n = map(int,input().split())
if n == 0:
    print(x)
    exit()
p = list(map(int,input().split()))
minimum = [-1,float('inf')]
item = [0]*102
for pi in p:
    item[pi] = 1
for i in range(102):
    if item[i] == 0 and minimum[1] > abs(x-i):
        minimum[1] = abs(x-i)
        minimum[0] = i
print(minimum[0])

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

int main()
{
    int n; cin>>n;
    int a[n]; for(e: a) cin>>e;

    long res=a[0]/2;
    int c=a[0]%2;
    for(int i=1; i<n; ++i) {
        if (a[i]==0) {
            c=0;
        }
        else {
            res+=c;
            a[i]-=c;
            c=0;
            res+=a[i]/2;
            c=a[i]%2;
        }
    }
    cout<<res<<endl;
}



Measured memory_bytes: 640
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

bool check(std::vector<std::string>& strs, int i, int j) {
  if (i < 0 || i >= strs.size())
    return false;
  if (j < 0 || j >= strs[0].size())
    return false;
  if (strs[i][j] == '#')
    return true;
  return false;
}

int main() {
  int h, w;
  std::cin >> h >> w;
  std::vector<std::string> grid;
  for (int i = 0; i < h; ++i) {
    std::string str;
    std::cin >> str;
    grid.push_back(str);
  }
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (grid[i][j] == '#') {
        if (!check(grid, i-1, j) && !check(grid, i, j-1) && !check(grid, i+1, j) && !check(grid, i, j+1)) {
          std::cout << "No" << std::endl;
          return 0;
        }
      }
    }
  }
  std::cout << "Yes" << std::endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using vec = vector<int>;

#define rep(i, n)  for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define Sort(a)    sort(a.begin(), a.end())
#define gSort(a)   sort(a.begin(), a.end(), greater<int>())
#define pout(n, a) cout << fixed << setprecision(n) << (a)
#define Cast(dig, n) static_cast<std::bitset<(dig)>>(n)

const int INF = 2147483647;
const ll  MOD = 1000000007;

int main() {
    ll x;
    cin >> x;

    ll ans = 0;

    ll sum = 100;
    while(sum < x) {
        sum *= 1.01;
        ans++;
    }

    cout << ans;
}

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

int main() {
  long long X;
  cin >> X;
  vector<long long> vec;
  for (long long i = 1; i * i <= X; i++) {
    if (X % i == 0) {
      vec.push_back(i);
      if (i * i != X) vec.push_back(X / i);
    }
  }
  sort(vec.begin(), vec.end());
  int s = vec.size();
  for (long long i = 0; i < s; i++) {
    for (long long j = 0; j < 1000; j++) {
      long long x, y;
      x = j;
      y = x - vec.at(i);
      if (x*x*x*x*x - y*y*y*y*y == X) {
        cout << x << " " << y << endl;
        break;
      }
    }
  }
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
using ll = long long;
int main(){
  const int mod = 7+(1e+9);
  int n; cin >> n;
  string s; cin >> s;
  for(int i = 2*n - 2; i >= 0; i-=2){
    if(s[i] == 'B')s[i] = 'W';
    else s[i] = 'B';
  }
  ll ans = 1;
  int cnt_b = 0;
  int now_w = 0;
  for(int i = 0; i < n*2; ++i){
    if(s[i] == 'W'){
      now_w++;
    } else {
      cnt_b++;
      if(now_w <= 0){
	cout << 0 << endl;
	return 0;
      }
      ans = (now_w * ans) % mod;
      now_w--;
    }
  }
  for(int i = n; i > 0; --i) ans = (ans*i)%mod;
  if(cnt_b != n) ans = 0;
  cout << ans << endl;
  return 0;
}


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

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

using namespace std;

long long count(string &s,int ptr,int dir,char c) {
  long long cnt = 0;
  ptr += dir;
  while( 0 <= ptr && ptr < (int)s.size() ) {
    if( s[ptr] == c ) ++cnt;
    else              --cnt;
    ptr += dir;
  }
  return cnt;
}

int main() {
  string s;
  getline(cin,s);
  long long cnt = 0;
  int ptr = -1;
  rep(i,(int)s.size()) if( s[i] == '*' ) { ptr = i; break; }
  cout << max(0LL,min(count(s,ptr,-1,'('),count(s,ptr,+1,')'))) << endl;
  return 0;
}

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

long long memo[10000007];

long long N;

int main(){
	cin >> N;

	for(long long i = 1; i <= N; i++) {
		for(long long j = 1; i * j <= N; j++) {
			//cout << "i = " << i << " j = " << j << endl;
			memo[i*j]++;
		}
	}

	long long ans = 0;
	for(long long i = 1; i <= N; i++) {
		ans += i * memo[i];
		//cout << "i = " << i << " " << memo[i] << endl;
	}
	cout << ans << endl;

}


Measured memory_bytes: 81748
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
int d[200][200];
const int INF = 1e9;
 
int main(){
    int n, m, r;
    cin >> n >> m >> r;
 
    VI p(r);
    REP(i,r) cin >> p[i];
    REP(i,r) p[i]--;
    sort(ALL(p)); 
 
    REP(i,n) REP(j,n) d[i][j] = INF * (i != j);
    REP(i,m){
        int u, v, l;
        scanf("%d %d %d", &u, &v, &l);
        u--;
        v--;
        d[u][v] = d[v][u] = l;
    }
 
    REP(i,n) REP(j,n) REP(k,n) d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
 
    // REP(i,n) REP(j,n) cout << d[i][j];
    // cout << endl;
 
    int ans = INF;
    do{
        int tmp = 0;
        REP(i,r-1) tmp += d[p[i]][p[i+1]];
        ans = min(ans, tmp);
    }while (next_permutation(ALL(p)));
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 384
import Data.List
import Control.Monad
import qualified Data.Vector as V
main = do
    [n, q] <- fmap read . words <$> getLine :: IO [Int]
    s <- getLine

    let ac = V.fromList . scanl (+) 0 $ (\x -> if x == "AC" then 1 else 0) . take 2 <$> tails s
    forM_ [1..q] . const $ do
        [l, r] <- fmap pred . fmap read . words <$> getLine
        print $ (ac V.! r) - (ac V.! l)


Measured memory_bytes: 15228
#!/usr/bin/env python3

import sys

sys.setrecursionlimit(10**7)

# Override `input` function because `stdin.readline()` is 10x faster than built-in `input()`
input = sys.stdin.readline


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h(typ) if m > 1 else typ(input()) for _ in range(n)]


def main():
    n, = read_h()
    arr = read_h()

    bad = 0
    for i, p in enumerate(arr):
        if p != i + 1:
            bad += 1
        if bad > 2:
            print('NO')
            return

    print('YES')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
var binarySearch = function (key, n, a) {
  var left = 0;
  var right = n;
  while (left < right) {
    var mid = Math.floor((left + right) / 2);
    if (a[mid] == key) {
      return true;
    } else if (key < a[mid]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return false;
}

var stdin = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr = (stdin.trim()).split('\n');
var s = arr[1].split(" ").map(Number);
var t = arr[3].split(" ").map(Number);
var ans = 0;
for (var i = 0; i < t.length; i++) {
  ans += binarySearch(t[i], s.length, s);
}
console.log(ans);

Measured memory_bytes: 30844
import sys
input = sys.stdin.readline
N, A, B, C, D = map(int, input().split())
for i in range(N - 1):
  l = C * i + A - D * (N - i - 1)
  r = D * i + A - C * (N - i - 1) + 1
  if B in range(l, r):
    print("YES")
    break
else: print("NO")

Measured memory_bytes: 67932
//https://atcoder.jp/contests/abc130/tasks/abc130_a
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int X, A;
    cin >> X >> A;
    cout << ( X >= A ? 10 : 0 ) << endl;
    return 0;
}


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

int main() {
	int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
	const int dx = tx - sx, dy = ty - sy;

	cout << string(dy, 'U') << string(dx, 'R');
	cout << string(dy, 'D') << string(dx, 'L');

	cout << 'L' << string(dy + 1, 'U') << string(dx + 1, 'R') << 'D';
	cout << 'R' << string(dy + 1, 'D') << string(dx + 1, 'L') << 'U';

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <utility>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl
#define PI 3.14159265359

const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const int mod = 1000000007;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  string s;
  cin >> s;

  if (s.size() % 2 != 0) {
    No;
    return 0;
  }
  for (int i = 0; i < s.size(); i+=2) {
    if (s[i] != 'h' || s[i + 1] != 'i') {
      No;
      return 0;
    }
  }

  Yes;


  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 
#include <time.h>

int main(void){
    std::string S;
    std::cin >> S;
    for(long i=0; i<S.length(); i++){
        if(S[i]=='?'){
            std::cout << "D";
        }else{
            std::cout << S[i];
        }
    }
    std::cout << std::endl;
    return 0;
}

Measured memory_bytes: 3752
#include "stdio.h"

int main(){
    long long int a[5];
    long long int n;
    long long int min;
    long long int mindiv;
    int minIndex;
    long long int ret;
    long long int i,j,k;
    long long int amari;
    scanf("%llu",&n);
    scanf("%llu",&a[0]);
    scanf("%llu",&a[1]);
    scanf("%llu",&a[2]);
    scanf("%llu",&a[3]);
    scanf("%llu",&a[4]);
    //ボトルネックを求める
    min = 1000000000000000;
    minIndex = 0;
    for(i=0;i<5;i++){
        if (min > a[i]){
            min = a[i];
            minIndex = i;
        }   
    }
    mindiv = n / min;
    amari = n % min;
    if (amari == 0){
        mindiv -= 1;
    }
    ret = 5 + mindiv;

    printf("%llu\n",ret);
    return 0;
}


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

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

	int n;
	cin >> n;
	vector<pair<int, int> > stuff(n);
	vector<int> rem(n, n);
	vector<int> which(n * n, -1);
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		p--;
		stuff[i] = {p, i};
		which[p] = i;
	}
	sort(stuff.begin(), stuff.end());
	auto fail = [&]() -> void {
		cout << "No" << '\n';
		exit(0);
	};
	int cur = 0;
	vector<int> ans(n * n, -1);
	for (auto z : stuff) {
		for (int _ = 0; _ < z.second; _++) {
			while (cur < z.first && ans[cur] != -1) cur++;
			if (cur >= z.first) fail();
			ans[cur] = z.second;
			rem[z.second]--;
		}
		if (ans[z.first] != -1) fail();
		ans[z.first] = z.second;
		rem[z.second]--;
	}
	vector<bool> good(n, false);
	for (int i = 0; i < n * n; i++) {
		if (which[i] != -1) good[which[i]] = true;
		if (ans[i] == -1) {
			for (int x = n-1; x >= 0; x--) {
				if (rem[x] && good[x]) {
					ans[i] = x;
					rem[x]--;
					break;
				}
			}
			if (ans[i] == -1) fail();
		}
	}
	for (int x = 0; x < n; x++) assert(rem[x] == 0);
	cout << "Yes" << '\n';
	for (int i = 0; i < n * n; i++) {
		cout << ans[i] + 1 << " \n"[i+1==n*n];
	}

	return 0;
}


Measured memory_bytes: 3200
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.DataAnnotations;
using System.Linq;
using System.Text;
using System.Threading;

class Program
{

    static int Max_N = 200000 + 1;
    static void Main(string[] args)
    {
        string str = Console.ReadLine();
        int len = str.Length;
        str = "";
        for (int i = 0; i < len; i++) str += "x";
        Console.WriteLine(str);
    }




}

Measured memory_bytes: 25848
// A.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[]) {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	bool ans = a[0] == 5 && a[1] == 5 && a[2] == 7;
	cout << (ans ? "YES" : "NO") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define ll long long
using namespace std;

int main(){
  int n;
  cin>>n;
  ll vec[n][3];
  ll minabs[n];
  for(int i=0;i<n;i++){
    cin>>vec[i][0]>>vec[i][1]>>vec[i][2];
    minabs[i]=min(abs(vec[i][0]),abs(vec[i][1]));
  }
  ll ans[n+1];
  for(int i=0;i<=n;i++){
    ans[i]=1e13;
  }
  int vecb[n];
  int vecc[n];
  ll cost[n];
  ll sum,x;
  for(int bit=0;bit<(1<<n);bit++){
    int t=0;
    for(int i=0;i<n;i++){
      if(bit&(1<<i)){
        vecb[i]=1;
        vecc[t]=i;
        t++;
      }
      else{
        vecb[i]=0;
      }
    }
    if(t==n){
      ans[t]=0;
      continue;
    }
    for(int i=0;i<n;i++){
      cost[i]=minabs[i];
    }
    /*x=0;
    for(int i=0;i<n;i++){
      if(vecb[i]==1){
        vecc[x]=i;
        x++;
      }
    }*/
    for(int bitb=0;bitb<(1<<t);bitb++){
      for(int i=0;i<t;i++){
        if(bitb&(1<<i)){ //縦に引く
          for(int j=0;j<n;j++){
            cost[j]=min(cost[j],abs(vec[j][0]-vec[vecc[i]][0]));
          }
        }
        else{ //横に引く
          for(int j=0;j<n;j++){
            cost[j]=min(cost[j],abs(vec[j][1]-vec[vecc[i]][1]));
          }
        }
      }
      sum=0;
      for(int i=0;i<n;i++){
        sum+=cost[i]*vec[i][2];
        cost[i]=minabs[i];
      }
      ans[t]=min(ans[t],sum);
    }
  }
  
  for(int i=0;i<n+1;i++){
    cout<<ans[i]<<endl;
  }
}

Measured memory_bytes: 3616
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

n=int(input())
s=list(input())
pre=s[0]
ans=1
for i in range(1,n):
    if s[i]!=s[i-1]:
        ans+=1
print(ans)

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

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

  vector<ll> a(n);
  for (ll i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.begin(), a.end(), greater<ll>());

  ll ans = 0;
  priority_queue<ll> q;
  for (ll i = 0; i < n; ++i) {
    if (q.empty()) {
      q.push(a[i]);
      continue;
    }

    if (q.top() == a[i]) {
      ans += q.top();
      q.push(a[i]);
    } else {
      ans += q.top();
      q.pop();
      q.push(a[i]);
      q.push(a[i]);
    }
  }

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


Measured memory_bytes: 6928
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define ll long long
//#define int long long
using namespace std;
void boost()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}
void free()
{
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
}
int a[100];
main()
{
	//free();
	boost();
	string s;
	cin >> s;
	for(int i = 0; i < s.size(); i++)
		a[s[i] - 'a']++;
	for(int i = 0; i < 27; i++)
		if(a[i] % 2 == 1)
			cout << "No", exit(0);
	cout << "Yes", exit(0);	
}


Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
// long long -> lint
using lint = long long;
// fast cin and cout from hitonanode-san's code
// w/o 71 ms -> w/ 18 ms (tested on ABC148-D with C++14(GCC 5.4.1))
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

int main(){
    // input
    lint A, B, K, tmp;
    cin >> A >> B >> K;

    // calc
    // for Takahashi
    tmp = max( K-A, (lint)0 );
    A   = A - (K-tmp);
    K   = tmp;
    // for Aoki
    tmp = max( K-B, (lint)0 );
    B   = B - (K-tmp);

    // out
    cout << A << " " << B << endl;;
} 

Measured memory_bytes: 256
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, l = na()

r = l+n-1

if l >= 0:
    s = 0
    for i in range(l+1, r+1):
        s += i
    print(s)
elif r <= 0:
    s = 0
    for i in range(l, r):
        s += i
    print(s)
else:
    s = 0
    for i in range(l, r+1):
        s += i
    print(s)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,N-1,0)
#define RREPS(i,n) RFOR(i,N,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int INF=1e18;
const int MOD=1e9+7;

signed main(){
    int A,B,C,K;
    cin>>A>>B>>C>>K;
    int sum=0;
    if(K<=A)sum=K;
    if(A<K){
        sum+=A;
        K-=A;
        if(B<K){
          K-=B;
          sum-=min(K,C);
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 3632
n, l = map(int,input().split())
r = []
for i in range(1,n+1):
  r.append( l + i - 1 )
for i in range(400):
  for j in range(n):
    if abs(r[j]) == i:
      print(sum(r)-int(r[j]))
      exit()
  

Measured memory_bytes: 38512
H,W,K= map(int,input().split(' '))

HW = [ input() for _ in range(H) ]
already_reach = [ [0]*W for _ in range(H) ]

def search(h,w,num):
    hn = [0,1]
    wn = [1,0]
    from_num = 0
    to_num = 0
    w_to = 0
    for i in range(1,W):
        if 0 <= w-i and HW[h+0][w-i] == '.' and already_reach[h+0][w-i] == 0:
            from_num -= 1
        else:
            break
    for i in range(1,W):
        if w+i < W and HW[h+0][w+i] == '.' and already_reach[h+0][w+i] == 0:
            to_num += 1
        else:
            break
    for i in range(from_num,to_num+1):
        already_reach[h][w+i] = num
    
    for s in range(1,H):
        if h + s >= H:
            break
        flag = False
        for i in range(from_num,to_num+1):
            if HW[h+s][w+i] != '.' or already_reach[h+s][w+i] != 0:
                flag = True
                break
        if flag:
            break
        for i in range(from_num,to_num+1):
             already_reach[h+s][w+i] = num
    for s in range(1,H):
        if h - s < 0:
            break
        flag = False
        for i in range(from_num,to_num+1):
            if HW[h-s][w+i] != '.' or already_reach[h-s][w+i] != 0:
                flag = True
                break
        if flag:
            break
        for i in range(from_num,to_num+1):
             already_reach[h-s][w+i] = num
current_num = 1
for s in range(H):
    for i in range(W):
        if HW[s][i] == '#':
            search(s,i,current_num)
            current_num +=1
for s in range(H):
    print(' '.join(map(str,already_reach[s])))

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

int main(void){
    int N = 0, d = 0, i = 0, T = 0;
    int W[100];
    int s1[100], s2[100];

    for(i = 0; i < 100; i++){
        s1[i] = 0;
        s2[i] = 0;
    }

    scanf("%d", &N);

    for(i = 0; i < N; i++){
        scanf("%d", &W[i]);
    }

    for(T = 0; T < N-1; T++){
        for(i = 0; i <= T; i++){
            s1[T] += W[i]; 
        }
        for(i = T+1; i < N; i++){
            s2[T] += W[i];
        }
        if(T == 0){
            d = abs(s1[T] - s2[T]);
        }else if(d > abs(s1[T] - s2[T])){
            d = abs(s1[T] - s2[T]);
        }
    }

    printf("%d", d);

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	for(int i=0;i<=2;i++){
		if(a[i]!=b[2-i]){
			cout<<"NO";
			return 0;
		}
	}
	cout<<"YES";
}


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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int n, k;
    cin >> n >> k;
    vi h(n);
    rep(i, n) cin >> h[i];
    vi dp(n, INF);
    dp[0] = 0;
    rep(i, n) {
        rep1(j, k) if (i-j>=0) {
            dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 3980
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <cstring>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
typedef long long ll;
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

int main(){
    ll N,K; cin >> N >> K;
    vector<ll> a(N);
    ll sum = 0;
    for (int i = 0; i < N; i++){
        cin >> a[i];
        sum += a[i];
    }
    vector<ll> div;
    for (int i = 1; i*i <= sum; i++){
        if (sum % i == 0){
            div.push_back(i);
            div.push_back(sum / i);
        }
    }
    ll ans = 1; 
    vector<ll> rest(N);
    for (ll d : div){
        ll total = 0;
        for (int i = 0; i < N; i++){
            rest[i] = a[i] % d;
            total += rest[i];
        }
        sort(rest.begin(),rest.end());
        ll minus = total / d, plus = N - minus;
        ll cnt = 0;
        for (int i = 0; i < plus; i++) cnt += rest[i];
        if (cnt <= K) ans = max(ans,d);
    }
    cout << ans << endl;
}

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

using namespace std;
const int maxn=1e5;

vector<int> G[maxn+5];
vector<int> path;
int sz[maxn+5];
int n;
int mid;

void dfs(int x,int r)
{
	path.push_back(x);
	sz[x]=1;
	for (int e:G[x])
	{
		if (e==r) continue;
		dfs(e,x);
		sz[x]+=sz[e];
	}
	
	if (x==n)
	{
		mid=path[(path.size()+1)/2];
	}
	path.pop_back();
}

void solve()
{
	for (int i=1;i<=n;++i)
	{
		G[i].clear();
	}
	path.clear();
	
	for (int i=1;i<=n-1;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	
	dfs(1,-1);
	
	int sum1=n-sz[mid];
	if (sum1>sz[mid]) printf("Fennec\n");
	else printf("Snuke\n");
}

int main(void)
{
	#ifdef ex
	freopen ("std.in","r",stdin);
	#endif
	
	while (scanf("%d",&n)==1)
	{
		solve();
	}
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define rep(i, k, n) for (int i = (int)(k); i < (int)(n); ++i)
#define rrep(i, k, n) for (int i = (int)(n) - 1; i >= (int)(k); --i)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vv_ii;
typedef pair<int,ii> i_ii;
typedef vector<i_ii> vi_ii;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template <class T>
inline ostream& operator<<(ostream & o, vector<T> const& v) {
    for (int i = 0; i < (int)(v.size()) - 1; ++i)
        o << v[i] << ' ';
    if (!v.empty())
        o << v.back();
    return o;
}

template <class T, class Q>
inline ostream& operator<<(ostream & o, pair<T,Q> const& p) {
    o << "(" << p.fi << "," << p.se << ")";
    return o;
}

vvi tree;
vii edges;
map<ii,int> color;
bool visited[100010];
vi deg;


void dfs(int u, vi & rem, int ind, int last) {
    visited[u] = true;
    int ind2 = ind;
    rep(i, 0, tree[u].size()) {
        int v = tree[u][i];
        ii e = ii(min(u, v), max(u, v));
        auto it = color.find(e);
        if (it == color.end()) {
            if (rem[ind-1] == last)
                --ind;
            color[e] = rem[--ind];
        }
    }
    ind = ind2;
    rep(i, 0, tree[u].size()) {
        int v = tree[u][i];
        if (!visited[v]) {
            dfs(v, rem, ind, color[ii(min(u, v), max(u, v))]);
        }
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

    memset(visited, false, n * sizeof(bool));
    edges.resize(n-1);
    tree.resize(n);
    deg.resize(n);
    int max_deg = 0;
    rep(i, 0, n-1) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        tree[a].pb(b);
        tree[b].pb(a);
        edges[i] = ii(min(a, b), max(a, b));
        max_deg = max({max_deg, ++deg[a], ++deg[b]});
    }
    vi rem(max_deg);
    rep(i, 0, max_deg) {
        rem[i] = i+1;
    }
    
    rep(i, 0, n) {
        if (!visited[i]) {
            dfs(i, rem, rem.size(), 0);
        }
    }

    cout << max_deg << '\n';
    rep(i, 0, n-1) {
        cout << /*"edge (" << edges[i].fi+1 << "," << edges[i].se + 1 << ")  --> " <<*/ color[edges[i]] << '\n';
    }

    return 0;
}

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

int _min(
  int lhs
  , int rhs
)
{
  return ((lhs < rhs) ? lhs : rhs);
}

int _abs(
  int lhs
  , int rhs
)
{
  return ((lhs < rhs) ? (rhs - lhs) : (lhs - rhs));
}

int main()
{
  int N;
  cin >> N;
  vector<int> h(N);
  for (auto & _h : h)
    cin >> _h;
  vector<int> cost(N);
  int inf = 1000000000;
  int one, two;
  for (int i = 1; i < N; ++i)
  {
    one = two = inf;
    if (0 <= i - 1)
      one = cost[i - 1] + _abs(h[i - 1], h[i]);
    if (0 <= i - 2)
      two = cost[i - 2] + _abs(h[i - 2], h[i]);
    cost[i] = _min(one, two);
  }
  cout << cost[N - 1];
  return 0;
}


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

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

    std::vector<int> ref;
    for(int i = 1; i <= n; ++i){
        ref.push_back(i);
    }

    std::vector<std::vector<int>> refs;
    do{
        refs.push_back(ref);
    }while(std::next_permutation(ref.begin(), ref.end()));

    std::vector<int> p(n), q(n);
    for(int i = 1; i <= n; ++i){
        std::cin >> p.at(i - 1);        
    }
    for(int i = 1; i <= n; ++i){
        std::cin >> q.at(i - 1);        
    }

    auto a = std::distance(refs.begin(), std::find(refs.begin(), refs.end(), p));
    auto b = std::distance(refs.begin(), std::find(refs.begin(), refs.end(), q));

    std::cout << std::abs(a - b) << std::endl;

    return 0;
}

Measured memory_bytes: 3384
package main

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

func main() {
        var n int
        fmt.Scan(&n)
        sc := bufio.NewScanner(os.Stdin)
        sc.Split(bufio.ScanWords)
        nums := map[int]int{}
        for i := 0; i < n; i++ {
                sc.Scan()
                a, _ := strconv.Atoi(sc.Text())
                nums[a]++
        }
        var rests int
        for _, calledNum := range nums {
                if calledNum%2 == 1 {
                        rests++
                }
        }
        fmt.Printf("%d\n", rests)
}

Measured memory_bytes: 7296
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

int main(){
    int N,A,B;
    cin>>N>>A>>B;
    cout<<min(N*A,B)<<endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a_list = list(map(int,input().split()))
s_a_list = sorted(a_list)
alice = 0
bob = 0
while len(s_a_list)>1:
  alice += s_a_list.pop(-1)
  bob += s_a_list.pop(-1)
if len(s_a_list) != 0:
  alice += s_a_list.pop(-1)
print(alice-bob)


Measured memory_bytes: 3060
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1000000007,N=100000;
const double pi=acos(-1.0);
typedef long long ll;
int n;
ll a[200200],dp[200200][5]; 

int read()
{
	int x=0,f=1;char ch=getchar();
	while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
	while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
	return x*f;
}

int main()
{
	n=read();int i;
	for (i=1;i<=n;i++) a[i]=read();
	for (i=1;i<=n;i++)
	{
		ll mind=dp[i-1][0];
		dp[i][0]=dp[i-1][0]+a[i];
		mind=min(mind,dp[i-1][1]);
		if (a[i]) dp[i][1]=mind+(a[i]%2);else dp[i][1]=mind+2;
		mind=min(mind,dp[i-1][2]);
		if (a[i]) dp[i][2]=mind+((a[i]+1)%2);else dp[i][2]=mind+1;
		mind=min(mind,dp[i-1][3]);
		if (a[i]) dp[i][3]=mind+(a[i]%2); else dp[i][3]=mind+2;
		mind=min(mind,dp[i-1][4]);
		dp[i][4]=mind+a[i];
	}
	ll ans=min(min(dp[n][2],dp[n][3]),dp[n][4]);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 9600
#include<stdio.h>

int t[5005][5];
int u[5005][5];

void init(){
  int i,j;
  for(i=0;i<5005;i++){
    for(j=0;j<5;j++){
      if(i==0)t[i][j]=1;
      else t[i][j]=0;
    }
  }
}

void Delete(){
  int i,j;
  for(i=0;i<5005;i++)
    for(j=0;j<5;j++)
      u[i][j]=t[i][j];
  init();
  
  int H=1,cnt;
  for(i=0;i<5005;i++){
    cnt=0;
    for(j=0;j<5;j++)cnt+=u[i][j];
    if(cnt==5)continue;
    for(j=0;j<5;j++)t[H][j]=u[i][j];
    H++;
  }
}

int check(int y,int x,int h,int w){
  int i,j,flg=0;
  
  for(i=y;i<y+h;i++)
    for(j=x;j<x+w;j++)
      if(t[i][j]==1)flg=1;
  
  if(flg==0)return 0;

  y++;
  for(i=y;i<y+h;i++)
    for(j=x;j<x+w;j++)
      t[i][j]=1;
  
  return 1;
}

void Put(int pos,int h,int w){
  int i;
  for(i=5000;i>=0;i--)
    if(check(i,pos,h,w)==1)break;
}

int main(){
  int i,j;
  int n,d,p,q,ans;
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    
    init();
    for(i=0;i<n;i++){
      scanf("%d %d %d",&d,&p,&q);
      q--;
      if(d==1)Put(q,1,p);
      else Put(q,p,1);
      Delete();
    }
    
    ans=0;
    for(i=1;i<5005;i++)
      for(j=0;j<5;j++)
        ans+=t[i][j];
    printf("%d\n",ans);
  }
      
  return 0;
}

Measured memory_bytes: 796
#include <stdio.h>
 
int main(){
  int a, b, c;
  int ans = 0;
  
  scanf("%d %d %d",&a, &b, &c);
  
  ans = c - (a - b);
  
  if (ans < 0) {
    ans = 0;
  }
  
  printf("%d", ans);
  
  return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
#define int long long
using ll = long long;
using namespace std;
const int INF = 1LL << 50;
using P       = pair<int, int>;

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

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} SETUP;

signed main() {
    string s;
    cin >> s;
    int len = s.size();
    vector<int> acc(len + 1);
    rep(i, 0, len) {
        if (s[i] == 'p') {
            acc[i]--;
        } else {
            acc[i]++;
        }
    }
    rep(i, 0, len) {
        acc[i + 1] += acc[i];
    }
    int ans = acc[len - 1] / 2;
    cout << ans << endl;
}


Measured memory_bytes: 1216
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> list = new ArrayList<>();
        String[] a = { "3", "5", "7" };
        //listに全部突っ込む
        List<String> list2 = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        list2.add("3");
        list2.add("5");
        list2.add("7");
        for (int l = 1; l < 9; l++) {
            for (int i = 0; i < list2.size(); i++) {
                for (int j = 0; j < 3; j++) {
                    String s = list2.get(i) + a[j];
                    list.add(s);
                    temp.add(s);
                }
            }
            list2 = temp;
            temp = new ArrayList<>();;
        }
        int count = 0;
        for (int i = 0 ; i < list.size() ; i++) {
            if (list.get(i).contains("3") && list.get(i).contains("5") && list.get(i).contains("7") && Integer.valueOf(list.get(i)) <= n) {
                count++;
            }
        }
        System.out.println(count);
    }

}


Measured memory_bytes: 29524
# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする

求める答えは、CountB - CountA

・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)

CountB = B - (CountB_C + CountB_D - CountB_CD)

"""
from fractions import gcd
from math import floor

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        #return x - (floor(x/C) + floor(x/D) - floor(x/lcm(C,D)))
        return x - (x//C + x//D - x//lcm(C,D))

    ans = f(B) - f(A-1)

    print(ans)


if __name__ == "__main__":
    solve()


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

long long n, sm;
vector<long long> d;

bool fav(long long x){
	return (n % x == (n / x));
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
		
	cin >> n;
	if(n == 1)
		return cout << 0, 0;
	long long i;
	for (i = 1; 1LL * i * i < n; i++){
		if(n % i == 0){
			if(i > 1)
				if(fav(i - 1))
					sm += (i - 1);
			if(fav(1LL * n / i - 1))
				sm += (1LL * n / i - 1);
		}
	}
	if(i * i == n && fav(i - 1))
		sm += (i - 1);
	cout << sm;
}



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

int main() { 
    ll K, N;
    cin >> K >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<ll> dis;
    for (int i = 1; i < N; i++){
      dis.push_back(A[i] - A[i - 1]);
    }
    dis.push_back(K-A[N - 1] + A[0]);
    sort(dis.begin(), dis.end());
    ll out = 0;
    for (int i = 0; i < N - 1; i++) out += dis[i];
    cout << out << endl;
    return 0;
}

Measured memory_bytes: 6936
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <cstring>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define vi vector < int >
#define vll vector < long long >
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))
#define fname "searching"

const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;

int n, l;
string s[110];

string solve(){
	cin >> n >> l;
	for(int i = 0; i < n; ++i) cin >> s[i];
	sort(s, s + n);
	string ans = "";
	for(int i = 0; i < n; ++i) ans += s[i];
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    
    cout << solve();

	return 0;
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define MAX 500005
//#define INF 1001001001

template <typename T>
struct RMQ {
  const T INF = numeric_limits<T>::max();
  int n;
  vector<T> dat, lazy;
  RMQ(int _n) : n(), dat(_n*4,INF), lazy(_n*4,INF) {
    int x = 1;
    while (x < _n) x <<= 1;
    n = x;
  }

  void update(int i, T x) {
    i += n-1;
    dat[i] = x;
    while (i > 0) {
      i = (i-1)/2;
      dat[i] = min(dat[i*2+1],dat[i*2+2]);
    }
  }

  T query(int a, int b, int k, int l, int r) {
    eval(k);
    if (r <= a || b <= l) return INF;
    if (a <= l && r <= b) return dat[k];
    T mid = (l+r)>>1;
    T vl = query(a,b,k*2+1,l,mid);
    T vr = query(a,b,k*2+2,mid,r);
    return min(vl,vr);
  }
  T query(int a, int b) { return query(a,b,0,0,n); }

  void eval(int k) {
    if (lazy[k] == INF) return;
    if (k < n-1) lazy[k*2+1] = lazy[k*2+2] = lazy[k];
    dat[k] = lazy[k];
    lazy[k] = INF;
  }

  void update(int a, int b, int x, int k, int l, int r) {
    eval(k);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      lazy[k] = x;
      eval(k);
    } else {
      int mid = (l+r)>>1;
      update(a,b,x,k*2+1,l,mid);
      update(a,b,x,k*2+2,mid,r);
      dat[k] = min(dat[k*2+1],dat[k*2+2]);
    }
  }
  void update(int a, int b, int x) { update(a,b,x,0,0,n); }

  inline T operator[](int a) { return query(a,a+1); }
};

int main(int, char**)
{
  int n, q;
  cin >> n >> q;
  RMQ<int> rmq(n);

  vector<int> ans;
  rep(i,q) {
    int command; cin >> command;
    if (command == 0) {
      int s, t, x;
      cin >> s >> t >> x;
      rmq.update(s,t+1,x);
    } else if (command == 1) {
      int i; cin >> i;
      ans.push_back(rmq[i]);
    }
  }
  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 6468
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define pb push_back
const ll mod = 1e9 + 7;
int n, d[101], ans, x;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n;
    for(int i=1; i<=n; i++){cin>>x; d[x]++;}
    for(int i=1; i<=100; i++){if(d[i]) ans++;}
    cout<<ans;
}


Measured memory_bytes: 256
H,W = map(int,input().split())

space = [["." for w in range(W+1)] ]
for h in range(H):
    space.append(["."]+list(input())+["."])
space.append(["." for w in range(W+1)])

neighbor_num = [[0 for w in range(W+2)] for h in range(H+2)]

for h in range(1,H+1):
    for w in range(1,W+1):
        if space[h][w] == "#":
            neighbor_num[h][w] += 1
            neighbor_num[h-1][w] += 1
            neighbor_num[h+1][w] += 1
            neighbor_num[h][w+1] += 1
            neighbor_num[h][w-1] += 1

flag = 1
for h,numbers in enumerate(neighbor_num[1:H+1]):
    for w,neighber in enumerate(numbers[1:W+1]):
        if space[h+1][w+1] == "#" and neighber < 2:
            flag = 0
if flag == 1:
    print("Yes")
else:
    print("No")




Measured memory_bytes: 3188
/*
 * written by Yaqi Zhang
 * University of Wisconsin-Madison
 * 2020
 */

#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stdio.h>
#include<vector>

#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, R;
    cin >> N >> R;
    if(N >= 10) cout << R << endl;
    else cout << R + 100 * (10 - N) << endl;

    return 0;
}



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

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define fWrite          freopen ("out.txt","w",stdout);
#define TC              int t;cin >> t;FOR(tc,1,t)
#define LL              long long
#define ULL             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

#define Make(x,p)       (x  (1<<p))
#define DeMake(x,p)     (x & ~(1<<p))
#define Check(x,p)      (x & (1<<p))
#define popcount(x)     __builtin_popcount(x)

int main()
{
    int n,k;
    cin >> n >> k;
    int arr[n];
    REP(i,n) cin >> arr[i];
    sort(arr,arr+n);
    int dp[k+1]={0};
    FOR(j,1,k){
        REP(i,n){
            if(j-arr[i]<0) break;
            if(dp[j-arr[i]]==0) dp[j]=1;
        }
    }
    if(dp[k]) cout << "First";
    else cout << "Second";
}


Measured memory_bytes: 640
$mod=1e9+7;
@fact=(1,map$f=$f*$_%$mod,++$f..2e5);
$invfact[2e5]=$f=`python -c'print pow($f,$mod-2,$mod)'`;
$invfact[$_-1]=$f=$f*$_%$mod for reverse 1..2e5;
sub nCk{my($n,$k)=@_;
	$fact[$n]*$invfact[$k]%$mod*$invfact[$n-$k]%$mod
}
($H,$W,$A,$B)=glob<>;
for(0..$H-$A-1){
	($x+=nCk($B+$_-1,$B-1)*nCk($H+$W-$B-$_-2,$W-$B-1)%$mod)%=$mod;
}
print$x


Measured memory_bytes: 44416
/*ex6_2
ryo_1129*/
#include <stdio.h>
#include <string.h>
#define SIZE 101 //文字列のサイズ

int main(void){
    int message_length;//文字の長さの変数宣言
	char message[SIZE];//配列宣言
    fgets(message,SIZE,stdin);//文字の入力
    putchar(message[0]);//1文字目の出力
    //文字列の長さを出す、改行の1文字分も含む
    message_length = strlen(message);
    //最後の改行を消して、null文字を代入、長さも1減らす
    if(message_length > 0 && message[message_length -1] == '\n'){
        message[--message_length] = '\0';
    }
    //最初と最後の文字を抜いた、文字列の長さを出力
    printf("%d",message_length - 2);
    //最後の文字を出力
    putchar(message[message_length - 1]);
    //改行のための出力
    putchar('\n');
    return 0;
}

Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define str to_string
#define endl "\n"
#define PI 3.141592653589
using namespace std;
using lint = long long;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

//AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC(*'ω'*)AC
int main(){
    int n,ans=-1;cin>>n;
    for(int i=1;i<50000;i++){
        if((i*108)/100==n){
            ans=i;break;
        }
    }
    if(ans==-1){
        cout<<":("<<endl;
    }
    else cout<<ans<<endl;
}


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

const int M = 2e5;
int a[M];
int main()
{
	
	int n;
	while (cin >> n)
	{
		for (int i = 1; i <= n; ++i)
			cin >> a[i];
		if (n % 2 == 1)
		{
			cout << a[n];
			for (int i = n - 2; i >= 1; i = i - 2)
				cout << " " << a[i];
			for (int i = 2; i <= n - 1; i = i + 2)
				cout << " " << a[i];
			cout << endl;
		}
		else
		{
			cout << a[n];
			for (int i = n - 2; i >= 2; i = i - 2)
				cout << " " << a[i];
			for (int i = 1; i <= n - 1; i = i + 2)
				cout << " " << a[i];
			cout << endl;
		}
	}
	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long double ld;

const int MAX = 501,IINF = INT_MAX;
const ld LDINF = 1e100;
int H,W,sx,sy,gx,gy;
ld mincost[MAX][MAX][2]; // mincost[][][0] => from start, [1] = > from star
char c[MAX][MAX];
bool ban[MAX][MAX];
vector<int> star,plane;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

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

inline void bfs(vector<int> sp,vector<int> Forbidden,int type){
  rep(i,H)rep(j,W) mincost[i][j][type] = LDINF, ban[i][j] = false;
  queue<int> que;
  rep(i,(int)sp.size()) que.push(sp[i]), mincost[sp[i]/W][sp[i]%W][type] = 0;
  rep(i,(int)Forbidden.size()) ban[Forbidden[i]/W][Forbidden[i]%W] = true;

  while(!que.empty()){
    int cur = que.front(); que.pop();
    rep(i,4){
      int nx = cur % W + dx[i], ny = cur / W + dy[i];
      if( c[ny][nx] == '#' ) continue;
      if( ban[ny][nx] ) continue;
      if( mincost[ny][nx][type] == LDINF ) {
        mincost[ny][nx][type] = mincost[cur/W][cur%W][type] + 1;
        que.push(nx+ny*W);
      }
    }
  }
}

bool check(ld E){
  ld T = 0;

  rep(i,(int)plane.size()){
    int x = plane[i] % W, y = plane[i] / W;
    T += min(mincost[y][x][0],mincost[y][x][1]+E);
  }

  ld len = plane.size();
  return len * E > T;
}

int main(){
  cin >> W >> H;
  rep(i,H)rep(j,W){
    cin >> c[i][j];
    if( c[i][j] == 's' ) sx = j, sy = i, c[i][j] = '.';
    if( c[i][j] == 'g' ) gx = j, gy = i;
    if( c[i][j] == '*' ) star.push_back(j+i*W);
    if( c[i][j] == '.' ) plane.push_back(j+i*W);
  }

  vector<int> sp,forbidden;
  sp.push_back(gx+gy*W);
  forbidden = star;
  forbidden.push_back(gx+gy*W);
  bfs(sp,forbidden,0);

  sp = star;
  forbidden.push_back(gx+gy*W);
  //forbidden.clear();
  bfs(sp,forbidden,1);

  ld L = 0, R = 1e10, M = 0;
  rep(i,75){
    M = ( L + R ) * (ld)0.5;
    if( check(M) ) R = M;
    else           L = M;
  }

  cout << setiosflags(ios::fixed) << setprecision(20) << min((ld)mincost[sy][sx][0],(ld)mincost[sy][sx][1]+L) << endl;

  return 0;
}

Measured memory_bytes: 10456