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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

int cnt[300];
signed main(void)
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  cnt[a]++;
  cnt[b]--;
  cnt[c]++;
  cnt[d]--;
  FOR(i, 1, 105) cnt[i] += cnt[i-1];
  int ret = 0;
  REP(i, 105) {
    if(cnt[i] == 2) ret++;
  }
  cout << ret << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 100
int main(){
    int a[N],b[N];
    char op[N];
    int i;
    for(i=0;i<N;i++){
        scanf("%d %c %d",&a[i],&op[i],&b[i]);
         if(op[i]=='?'){
            break;
        }
    }
    for(i=0;i<N;i++){    
        switch(op[i]){
        case '+':
        printf("%d\n",a[i]+b[i]);
        break;
        
        case '-':
        printf("%d\n",a[i]-b[i]);
        break;
        
        case '/':
        printf("%d\n",a[i]/b[i]);
        break;
        
        case '*':
        printf("%d\n",a[i]*b[i]);
        break;
        
        case '?':
        break;
        }
    }
    
    return 0;
}


Measured memory_bytes: 2080
import std.stdio;
long div = 1_000_000_007;
void main() {
	long n, m;
	scanf("%ld %ld\n", &n, &m);
	auto dp = new long[n+2];
	dp[0] = 1;
	auto check = new bool[1_0000];
	foreach(_; 0..m) {
		long a;
		scanf("%ld\n", &a);
		check[a] = true;
	}
	foreach(i; 0..n) {
		if (check[i]) continue;
		dp[i+1] = (dp[i+1] + dp[i]) % div;
		dp[i+2] = (dp[i+2] + dp[i]) % div;
	}
	dp[n].write;
}


Measured memory_bytes: 3196
H, W, K = map(int, input().split())
MAP = [list(input()) for i in range(H)]
Ho = [MAP[i].count('#') for i in range(H)]
Whole = sum(Ho)
count = 0

def ve(j):
    count = 0
    for i in range(H):
        if MAP[i][j] == '#':
            count += 1
    return count

Ve = [ve(j) for j in range(W)]

def iter_p_adic(p, n):
    from itertools import product
    tmp = [range(p)] * n
    return product(*tmp)

ite_H = list(iter_p_adic(2, H))
ite_V = list(iter_p_adic(2, W))

for idx_H in ite_H:
    for idx_V in ite_V:
        count_double = 0
        count_minus = 0
        h = list(idx_H)
        v = list(idx_V)
        for k in range(W):
            if v[k] == 1:
                count_minus += Ve[k]
        
        for i in range(H):
            for j in range(W):
                if v[j] == 1 and h[i] == 1 and MAP[i][j] == '#':
                    count_double += 1
            if h[i] == 1:
                count_minus += Ho[i]
        if Whole - count_minus + count_double == K:
            count += 1

print(count)


Measured memory_bytes: 9284
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/math/common_factor.hpp>

#define rep_ui(k,n)      for(ui  i = (k); i < (n); ++i)
#define rep_si(k,n)      for(int i = (k); i < (n); ++i)
#define rep_ul(k,n)      for(ul  i = (k); i < (n); ++i)
#define rep_sl(k,n)      for(ll  i = (k); i < (n); ++i)
#define rep_ui_down(k,n) for(ui  i = (k); i > (n); --i)
#define rep_si_down(k,n) for(int i = (k); i > (n); --i)
#define rep_ul_down(k,n) for(ul  i = (k); i > (n); --i)
#define rep_sl_down(k,n) for(ll  i = (k); i > (n); --i)

#define rep_uj(k,n)      for(ui  j = (k); j < (n); ++j)
#define rep_sj(k,n)      for(int j = (k); j < (n); ++j)
#define rep_uj_down(k,n) for(ui  j = (k); j > (n); --j)
#define rep_sj_down(k,n) for(int j = (k); j > (n); --j)

#define rep(k,n)         rep_ui(k,n)

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vc)
{
  boost::for_each(vc, [&os, &vc](T value) {
    os << value;
    if (value != vc.back())
      os << ' ';
    });
  return os;
}

template<class T1, class T2>
inline
std::ostream&
operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
  return os << p.first << ' ' << p.second;
}

void solve(void)
{
  using std::string;
  using std::vector;
  using std::map;
  using std::pair;
  //string S{}; std::cin >> S;
  ui  N{}; std::cin >> N;
  ull X{}; std::cin >> X;

  vector<ull> L(N);
  rep(0, L.size())
    std::cin >> L[i];
  
  auto ans = 1UL;
  ull d{};
  rep(0, N)
  {
    d += L[i];
    if (d <= X)
    {
      ++ans;
    }
    else
    {
      break;
    }
  }

  std::cout << ans << '\n';

  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int pre[3][4010];

int main(){
    int n;
    long long ans=0LL;
    string s;
    cin>>n>>s;
    s=" "+s;
    int a[4010];
    for(int i=1;i<=n;i++){
        if(s[i]=='R')
            a[i]=0;
        else if(s[i]=='G')
            a[i]=1;
        else if(s[i]=='B')
            a[i]=2;
    }
    
    for(int i=n;i>=1;i--){
        pre[a[i]][i]=pre[a[i]][i+1]+1;
        pre[(a[i]+1)%3][i]=pre[(a[i]+1)%3][i+1];
        pre[(a[i]+2)%3][i]=pre[(a[i]+2)%3][i+1];
    }
    
    for(int i=1;i<=n-2;i++){
        for(int j=i+1;j<=n-1;j++){
            if(a[i]==a[j])
                continue;
            int pos;
            
            for(int k=0;k<=2;k++){
                if(k!=a[i] && k!=a[j]){
                    pos=k;
                    break;
                }
            }
            ans+=pre[pos][j+1];
        }
    }
    
    for(int i=1;i<=n-2;i++){
        for(int j=i+1;j<=n-1;j++){
            int pos=2*j-i;
            if(pos>n || pos<=0)
                break;
            
            if(a[i]!=a[j] && a[i]!=a[pos] && a[j]!=a[pos])
                ans--;
        }
    }
    
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 3692
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
int w,h,n;
int x,y,a;
bool s[1111][1111];
signed main(){
	cin>>h>>w>>n;
	rep(i,n){
		cin>>x>>y>>a;
		if(a==1){
			rep(j,x){
				rep(k,w){
					s[j][k]=true;
				}
			}
		}
		if(a==2){
			for(int j=x;j<h;j++){
				rep(k,w){
					s[j][k]=true;
				}
			}
		}
		if(a==3){
			rep(j,h){
				rep(k,y){
					s[j][k]=true;
				}
			}
		}
		if(a==4){
			rep(j,h){
				for(int k=y;k<w;k++){
					s[j][k]=true;
				}
			}
		}
	}
	int ans=0;
	rep(i,h){
		rep(j,w){
			if(!s[i][j])ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(){
  string s, t;
  cin >> s >> t;
  int f = 0;
  int ff = 0;
  for(int i = 0; i < s.size(); i++){
    f = 0;
    for(int j = 0; j < s.size(); j++){
      if(s[j] != t[(i + j) % s.size()]){
        f = 1;
        break;
      }
    }
    if(!f){
    ff = 1;
    break;
    }
  }
  if(ff)cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
import collections
n = int(input())
lis = []
for _ in range(n):
    lis.append(input())
c = collections.Counter(lis)
most = c.most_common()
most_counter = c.most_common()[0][1]
#print(most)
#print(most_counter)
tmp_lis = []
for m in most:
    if m[1] == most_counter:
        tmp_lis.append(m[0])
    else:
        break
for t in sorted(tmp_lis):
    print(t)

Measured memory_bytes: 59376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n,q;
  string s;
  cin>>n>>s>>q;
  set<int> a[26];
  rep(i,0,n) a[(int)s[i]-97].insert(i);
  
  rep(i,0,q){
    int b;
    cin>>b;
    if(b==1){
      int c;
      char d;
      cin>>c>>d;
      c--;
      rep(j,0,26){
        if(a[j].count(c)) a[j].erase(c);
      }
      a[(int)d-97].insert(c);
    }
    else{
      int l,r;
      cin>>l>>r;
      l--;
      r--;
      int ans=0;
      rep(j,0,26){
        if(a[j].size()){
          int e=*rbegin(a[j]);
          if(e>=l){
            int f=*a[j].lower_bound(l);
            if(f<=r) ans++;
          }
        }
      }
      cout<<ans<<endl;
    }
  }
}


Measured memory_bytes: 24324
#include <numeric>
#include <iostream>
using namespace std;
#define M 998244353

int modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}


int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    int sum = accumulate(a, a+n, 0);
    long long f[2][900001] = {};
    int cur = 0, prev = 1;
    f[prev][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int s = 0; s <= sum; s++) {
            f[cur][s] = (2 * f[prev][s] + (s >= a[i] ? f[prev][s - a[i]] : 0)) % M;
        }
        swap(cur, prev);
    }
    long long ans = modexp(3, n, M);
    for (int s = (sum + 1) / 2; s <= sum; s++) ans -= 3 * f[prev][s];
    if (sum % 2 == 0) {
        long long g[2][900001] = {};
        cur = 0, prev = 1;
        g[prev][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int s = 0; s <= sum; s++) {
                g[cur][s] = (g[prev][s] + (s >= a[i] ? g[prev][s - a[i]] : 0)) % M;
            }
            swap(cur, prev);
        }
        ans += 3 * g[prev][sum/2];
    }
    cout << (ans % M + M) % M << endl;
}


Measured memory_bytes: 28416
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

constexpr int64_t DIV1097 = 1000000007LL;

using namespace std;

int main()
{
    int64_t X;
    std::cin >> X;

    if (X <= 6) {
        std::cout << 1 << std::endl;
        return 0;
    }
    X -= 6;

    int64_t ans = (X / 11) * 2 + 1;

    auto rem = X % 11;
    if (0 < rem) {
        ans++;
        if (6 <= rem) {
            ans++;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;

    auto a = unordered_set<int>();
    for (int i = 0; i < n; i++) {
        int a_i;
        cin >> a_i;
        a.insert(a_i);
    }

    cout << (a.size() == (size_t)n ? "YES" : "NO");
    return 0;
}


Measured memory_bytes: 8520
require 'matrix'

h, w = gets.split.map(&:to_i)
rows = Array.new(h, w){gets.chomp.chars.map{|c| (c == '#') ? 1 : 0}}
a = Matrix.rows(rows.shift(h))
b1 = Matrix[[1, 1], [1, 1]]
b2 = Matrix[[0, 1], [1, 1]]
b3 = Matrix[[1, 1], [1, 0]]
(h - 1).times do |i|
  (w - 1).times do |j|
    if a.minor(i, 2, j, 2) == b1 || a.minor(i, 2, j, 2) == b2 || a.minor(i, 2, j, 2) == b3
      puts 'Impossible'
      exit
    end
  end
end
puts 'Possible'

Measured memory_bytes: 2684
/*
[agc037] A - Dividing a String
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
#define ALL(c) (c).begin(), (c).end()

const int MAX_N = 2e5;

int N;
string S;
int dp[MAX_N + 1];

ll solve() {
    if (N == 1) {
        return 1;
    }

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = S[0] == S[1] ? 1 : 2;
    for (int i = 3; i <= N; i++) {
        dp[i] = (S[i - 1] == S[i - 2]) ? dp[i - 3] + 2 : dp[i - 1] + 1;
    }

    return dp[N];
}

int main() {
    cin >> S;
    N = S.length();

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 1412
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define REP(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<Int, Int>;
template <class T> inline bool chmax(T& a, const T& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T& a, const T& b) {
    if (a <= b) return false;
    a = b;
    return true;
}
struct in {
    int n;
    in() {}
    in(int n_) : n(n_){};
    template <class T> operator T() {
        T ret;
        cin >> ret;
        return ret;
    }
    template <class T> operator vector<T>() {
        vector<T> ret(n);
        for (int i = 0; i < n; i++) cin >> ret[i];
        return ret;
    }
};
struct SetupIO {
    SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }
} setup_io;

#ifdef _MY_DEBUG
#include "/Users/knshnb/.competitive_local.hpp"
#else
#define dump(...)
#endif

/**
 *    author:  knshnb
 *    created: Tue Dec  3 01:53:56 JST 2019
 **/

signed main() {
    Int t1 = in(), t2 = in();
    Int a1 = in(), a2 = in();
    Int b1 = in(), b2 = in();
    Int x = t1 * (a1 - b1), y = t2 * (a2 - b2);
    if (x > 0) x = -x, y = -y;
    Int d = x + y;
    if (d == 0) {
        cout << "infinity" << endl;
    } else if (d < 0) {
        cout << 0 << endl;
    } else {
        Int ans = -x / d * 2 + 1;
        if (x % d == 0) ans--;
        cout << max(0LL, ans) << endl;
    }
}


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

int main(int argc, char** argv){
  int N;
  cin >> N;
  double x;
  string u;
  double ans;
  for(int cnt0=0; cnt0<N; cnt0++){
    cin >> x >> u;
    if(u == "JPY"){
      ans+=x;
    }else if(u == "BTC"){
      ans+=x*380000.0;
    }
  }
  printf("%lf", ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n,i,j,k,b;
  cin >> n;
  while(n!=0){
    int table[101][101]={{}};
    int m[101]={};
    int l[101]={};
    for(i=1;i<=n;i++){
      cin >> m[i];
      for(j=0;j<m[i];j++){
	cin >> b;
	table[i][b]=1;
      }
    }
    cin >> k;
    for(i=0;i<k;i++){
      cin >> b;
      l[b]=1;
    }
    int o=0,f=0,q=0;
    for(i=1;i<=n;i++){
      f=0;
      for(j=1;j<=n;j++){
	if(l[j]==1)
	  if(table[i][j]!=1) f=1;
      }
      if(f==0){
	if(o==0) o=i;
	else q=1;
      }	
    }
    if(q==1||o==0) cout << -1 << endl;
    else cout << o << endl;
    cin >> n;
  }
  return 0;
}

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

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

const int INF = 1001001001;

int main() {

    int n;
    cin >> n;

    vector<int> b(n - 1);

    rep(i, n - 1) {
        cin >> b[i];
    }

    vector<int> a(n);
    a[n - 1] = b[n - 2];
    for(int i = n - 2 ; i >= 1 ; i --) {
        a[i] = min(b[i], b[i - 1]);
    }

    a[0] = b[0];
    int sum = std::accumulate(a.begin(), a.end(), 0);

    cout << sum << endl;

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int mod = 1000000007;
    int N;
    cin >> N;

    long long int* a = new long long int[N];
    long long int sum = 0;
    for (int i = 0; i < N; i++){
        cin >> a[i];
        sum += a[i];
        sum %= mod;
    }


    long long int ans = 0;

    for (int i = 0; i < N-1; i++) {
        sum -= a[i];
        if (sum < 0) {
            sum += mod;
        }
        ans += sum * a[i];
        ans %= mod;
    }

    cout << ans << endl;


    delete[] a;

    return 0;
}

Measured memory_bytes: 4824
N, M, X, Y = map(int, input().split())
list_x = list(map(int,input().split(' ')))
list_y = list(map(int,input().split(' ')))
 
 
min_range = max(list_x)
max_range = min(list_y)
 
ans = 0
 
for i in range(X+1, Y+1):
  if(i > min_range and i <= max_range):
    ans = 1
 
if (ans == 1):
  print("No War")
elif (ans == 0):
  print("War")

Measured memory_bytes: 3064
#文字列の入力
S = input()

S_list = list(S)

ans = 0
for i in range(len(S_list)):
  if(S_list[i] == "7"):
    ans = 7
  else:
    ans = ans
    
    
    
if(ans == 7):
  print("Yes")
else:
  print("No")



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

int main () {
  int A, B, C, D;
  cin >> A >> B >> C >>D;
  
  int a = min(B, D) - max(A, C);
  if (a < 0) {
    cout << 0 << endl;
  }
  else {
    cout << a << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b-1); i >= (a); i--)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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;}

const int MAX_N = 110;
const int MAX_V = 100100;

int w[MAX_N], v[MAX_N];

ll dp[MAX_N][MAX_V];

int main () {
  int N, W; cin >> N >> W;
  REP(i,N) cin >> w[i] >> v[i];

  REP(i,MAX_N) REP(j,MAX_V) dp[i][j] = INFLL;
  dp[0][0] = 0;
  for (int i = 0; i < N; i++) {
    for (int sum_v = 0; sum_v < MAX_V; sum_v++) {
      if (sum_v-v[i] >= 0) {
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v-v[i]]+w[i]);
      }
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v]);
    }
  }

  ll ans = 0;
  REP(sum_v, MAX_V) {
    if (dp[N][sum_v] <= W) ans = sum_v;
  }
  cout << ans << endl;
}

Measured memory_bytes: 86272
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int A,B,C;
void input() {
  cin>>A>>B>>C;
}
void solve() {
  // x * A % B == Cとなるようなxが存在するか？
   rep(i,1,22222){
     if (i*A%B == C){
       cout<<"YES"<<endl;
       return;
     }
   }
   cout<<"NO"<<endl;
  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

// varibable settings
#define infile "../test/sample-1.in"
#define int long long //{{{
const int INF=1e18;
const int MOD=1e9+7; //}}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ceil(a,b) ((a)+(b)-1)/(b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

int solve(){
  int h,w,a,b;cin>>h>>w>>a>>b;
  dump(h,w,a,b);

  rep(i, h){
    string r = "";
    rep(j, w){
      if (j<=a-1 && i<=b-1) r+='1';
      else if (j>a-1 && i>b-1) r+='1';
      else r+='0';
    }
    cout << r << endl;
  }
  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m,k;
map<pii,int> ids;
inline int getid(pii P){
  if(!ids.count(P)){
    int id = ids.size();
    ids[P] = id;
  }
  return ids[P];
}

int data[525252];
void init(){REP(i,525252)data[i]=-1;}
int root(int x){return data[x]<0?x:data[x]=root(data[x]);}
void unite(int x,int y){
  x=root(x);y=root(y);
  if(x!=y){
    if(data[x]>data[y])swap(x,y);
    data[x] += data[y];
    data[y] = x;
  }
}

int main(){
  init();
  scanf("%d%d%d",&n,&m,&k);
  REP(i,k){
    int x,y;
    scanf("%d%d",&x,&y);
    getid(pii(x,y));
  }
  // kabe
  int s = getid(pii(-1,1));
  int t = getid(pii(1,-1));
  FOR(x,2,n)getid(pii(x,-1));   // ue
  FOR(y,-1,m-1)getid(pii(n,y)); // migi
  FOR(y,1,m)getid(pii(-1,y));   // hidari
  FOR(x,-1,n-1)getid(pii(x,m)); // shita
  // unite
  int dx[] = {1,0,-1,0,1,1,-1,-1};
  int dy[] = {0,1,0,-1,1,-1,-1,1};
  for(auto &S : ids){
    int x = S.first.first;
    int y = S.first.second;
    int id = S.second;
    REP(i,8){
      int tx = x + dx[i];
      int ty = y + dy[i];
      pii Q = pii(tx,ty);
      if(ids.count(Q)){
        unite(id,ids[Q]);
      }
    }
  }
  s = root(s);
  t = root(t);
  if(s==t){
    puts("0");
    return 0;
  }
  int ddx[] = {2,2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1,0,1};
  int ddy[] = {2,1,0,-1,-2,-2,-2,-2,-2,-1,0,1,2,2,2,2};
  for(auto &S : ids){
    int x = S.first.first;
    int y = S.first.second;
    if(x<0 || y<0 || x>=n || y>=m)continue;
    int id = root(S.second);
    if(id!=s && id!=t)continue;
    REP(i,16){
      int tx = x+ddx[i];
      int ty = y+ddy[i];
      pii Q = pii(tx,ty);
      if(ids.count(Q)){
        int tid = root(ids[Q]);
        if(id==s && tid==t){
          puts("1");
          return 0;
        }
        if(id==t && tid==s){
          puts("1");
          return 0;
        }
      }
    }
  }
  puts("2");
  return 0;
}

Measured memory_bytes: 36420
use std::io;
use std::io::{BufRead, Write};

fn solve<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut buf = String::new();
    input.read_line(&mut buf).unwrap();
    let _n: usize = buf.trim_right().parse().unwrap();
    buf.clear();
    input.read_line(&mut buf).unwrap();
    let x: Vec<usize> = buf.split_whitespace().map(|s| s.parse().unwrap()).collect();
    let mut sorted = x.clone();
    sorted.sort();
    let half = x.len() / 2;
    for item in &x {
        let idx = sorted.binary_search(item).unwrap();
        writeln!(
            output,
            "{}",
            if idx < half {
                sorted[half]
            } else {
                sorted[half - 1]
            }
        ).unwrap();
    }
}

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    solve(stdin.lock(), stdout.lock());
}

#[cfg(test)]
mod tests {
    fn test(input: &str, output: &str) {
        let mut v: Vec<u8> = Vec::new();
        ::solve(input.as_bytes(), &mut v);
        assert_eq!(String::from_utf8(v).unwrap(), output);
    }

    #[test]
    fn case1() {
        test(
            "4
2 4 4 3
",
            "4
3
3
4
",
        );
    }

    #[test]
    fn case2() {
        test(
            "2
1 2
", "2
1
",
        );
    }

    #[test]
    fn case3() {
        test(
            "6
5 5 4 4 3 3
", "4
4
4
4
4
4
",
        );
    }
}


Measured memory_bytes: 13432
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,k,q;
  cin>>n>>k>>q;
  int a[100000];
  int b[100000]={0};
  rep(i,q){
    cin>>a[i];
    b[a[i]-1]++;
  }
  rep(i,n){
    if(k-q+b[i]>0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  
  

  return 0;
}


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

int main() {
	int x, y;
	int N, Y;
	
	cin >> N; cin >> Y;

	for (x = 0; x <= N; x++) {
		for (y = 0; y <= N - x; y++) {
			if (10000 * x + 5000 * y + 1000 * (N - x - y) == Y) {
				cout << x << ' ' << y << ' ' << (N - x - y);
				return 0;
			}
		}
	}

	cout << "-1 -1 -1" << '\n';
}

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

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

    string ans;
    for(int i = 0; i < (1<<3); i++) {
        int ret = s[0] - '0';
        for(int k = 0; k < 3; k++) {
            if((i>>k)&1) ret += (s[k+1] - '0');
            else ret -= (s[k+1] - '0');
        }
        if(ret == 7) {
            for(int k = 0; k < 3; k++) {
                if((i>>k)&1) ans.append("+");
                else ans.append("-");
            }
            break;
        }
    }

    for(int i = 0; i < ans.size(); i++) {
        cout << s[i] << ans[i];
    }
    cout << s[(int)s.size()-1] << "=7" << endl;

    return 0;
}

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

// @@ !! LIM()

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, K; cin >> N >> K;
  vector<ll> X(N), Y(N), vx(N), vy(N);
  for (ll i = 0; i < N; i++) {
    ll x, y; cin >> x >> y;
    vx[i] = X[i] = x;
    vy[i] = Y[i] = y;
  }
  sort(vx.begin(), vx.end());
  sort(vy.begin(), vy.end());
  ll ans = LLONG_MAX;
  for (ll x1 = 0; x1 < N; x1++) {
    for (ll y1 = 0; y1 < N; y1++) {
      for (ll x2 = x1 + 1; x2 < N; x2++) {
	for (ll y2 = y1 + 1; y2 < N; y2++) {
	  ll cnt = 0;
	  for (ll i = 0; i < N; i++) {
	    if (vx[x1] <= X[i] && X[i] <= vx[x2]
		&& vy[y1] <= Y[i] && Y[i] <= vy[y2]) cnt++;
	  }
	  if (cnt >= K) {
	    ans = min(ans, (vx[x2] - vx[x1]) * (vy[y2] - vy[y1]));
	  }
	}
      }
    }
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3640
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int ans=1;
  int cnt=0;
  while(ans<=b){
    if(cnt==a)
      break;
    ans*=2;
    cnt++;
  }
  ans+=b*(a-cnt);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
N,M=map(int,raw_input().split(' '))

m_1=[0]*(N+1)
m_N=[0]*(N+1)
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1:
        m_1[b]=1
    if b==N:
        m_N[a]=1

a=''.join(map(str,m_1))
b=''.join(map(str,m_N))

c=int(a,2)
d=int(b,2)


if c&d==0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

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

int main() {
    int n, a;
    cin >> n;
    double ans=0;
    for (int i=0;i<n;i++) {
        cin >> a;
        ans += 1.0/a;
    }
    ans = 1 / ans;
    cout << std::setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
int mod = 998244353;
// int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b % mod; if (a >= mod) a -= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(11);
  int T;
  T = 1;
  while (T--) solve();
}

void solve() {
  int n;
  cin >> n;
  int Q;
  cin >> Q;

  vector<vector<int> > G(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].eb(b);
    G[b].eb(a);
  }

  vector<ll> v(n);
  while (Q--) {
    int p, x;
    cin >> p >> x;
    p--;
    v[p] += x;
  }

  auto dfs = [&](auto&& dfs, int v_, int p) -> void {
    for (int nv : G[v_]) {
      if (nv == p) continue;
      v[nv] += v[v_];
      dfs(dfs, nv, v_);
    }
  };
  dfs(dfs, 0, -1);
  cout << v << endl;
}


Measured memory_bytes: 21504
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<string.h>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<deque>
#include<string>
#include<random>
#include<stack>
#include<limits.h>
#define int long long
using namespace std;

int b[10];
signed main() {
	int a; cin >> a;
	for (int c = 0; c < a; c++) {
		cin >> b[c];
	}
	int ans = 0;
	for (int i = 0; i < a; i++) {
		int k = 1;
		for (int j = 0; j < i; j++) {
			if (b[j] % 2 == 0)k *= 2;
		}
		if (b[i] & 1)k *= 2;
		for (int j = i + 1; j < a; j++)k *= 3;
		ans += k;
 	}
	cout << ans << endl;
}

Measured memory_bytes: 256
fn dfs(u: usize, k: u32, next: &Vec<Vec<usize>>, parent: &Vec<usize>) -> (u32, u32) {
    let mut costs = 0;
    let mut max_d = 0;
    for &v in next[u].iter() {
        let (c, d) = dfs(v, k, next, parent);
        if d+1 == k && u != 0 {
            costs += c+1;
        } else {
            costs += c;
            max_d = max(max_d, d+1);
        }
    }
    if u == 0 && parent[u] != 0 {
        costs += 1;
    }
    (costs, max_d)
}
fn main() {
    let (n, k): (usize, u32) = readln();
    let a = readln::<Vec<usize>>().iter().map(|x| x - 1).collect::<Vec<usize>>();
    let mut next = vec![Vec::new(); n];
    for (u, &p) in a.iter().enumerate() {
        if u != 0 {
            next[p].push(u);
        }
    }
    let answer = dfs(0, k, &next, &a).0;
    println!("{}", answer);
}

// --- template ---
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::HashSet;

pub trait FromLn {
    fn fromln(s: &str) -> Self;
}
pub fn readln<T: FromLn>() -> T {
    let mut buf = String::new();
    let _ = ::std::io::stdin().read_line(&mut buf).unwrap();
    T::fromln(buf.trim())
}
pub fn readlns<T: FromLn>(n: usize) -> Vec<T> {
    let mut vs = vec![];
    for _ in 0..n { vs.push(readln()); }
    vs
}
macro_rules! fromln_primitives {
    ($($t:ty),*) => { $(
        impl FromLn for $t {
            fn fromln(s: &str) -> $t {
                s.parse().unwrap()
            }
        }
    )* }
}
fromln_primitives!(String, bool, f32, f64, isize, i8, i16, i32, i64, usize, u8, u16, u32, u64);
impl<T> FromLn for Vec<T> where T: FromLn {
    fn fromln(s: &str) -> Vec<T> {
        s.split_whitespace().map(T::fromln).collect()
    }
}
impl FromLn for Vec<char> {
    fn fromln(s: &str) -> Vec<char> {
        s.chars().collect()
    }
}
macro_rules! fromln_tuple {
    ($($t:ident),*) => {
        impl<$($t),*> FromLn for ($($t),*) where $($t: FromLn),* {
            fn fromln(s: &str) -> ($($t),*) {
                let mut it = s.split_whitespace();
                let t = ($($t::fromln(it.next().unwrap())),*);
                assert_eq!(it.next(), None);
                t
            }
        }
    }
}
fromln_tuple!(A, B);
fromln_tuple!(A, B, C);
fromln_tuple!(A, B, C, D);
fromln_tuple!(A, B, C, D, E);
fromln_tuple!(A, B, C, D, E, F);

Measured memory_bytes: 20348
def ns():
    import sys
    return map(int, sys.stdin.readline().split())
  
def ss():
    import sys
    return list(sys.stdin.readline().strip())
  
N, = ns()
S = ss()
K, = ns()

c = S[K-1]
print(''.join(s if s == c else '*' for s in S))


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <regex>
#include <climits>

#define FOR(i, f, n) for(int (i) = (f), TMPend = (n); (i) < TMPend; (i)++)
#define RFOR(i, f, n) for(int (i) = (f), TMPend = (n); (i) >= TMPend; (i)--)
#define REP(i, n) for(int (i) = 0, TMPend = (n); (i) < TMPend; (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0, TMPend = (n); (i) < TMPend; (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define forin(i, a) for(auto i: (a))
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](auto const &a, auto const &b){ return c ;}
#define key(t, x, compare) [](const t &a, const t &b){ return a x compare b x ;}
#define unless(a) if(!(a))

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

void output__(){
  cout << endl;
}

template <class Head, class... T>
void output__(Head const &v, T const &...a) {
  if(sizeof...(a) == 0) {
    cout << v;
  } else {
    cout << v << " ";
  }
  output__(a...);
}

int N;
vector<vector<long long>> A;

long long score(int state) {
  int t = 1;
  vector<int> hist;
  long long result = 0;
  rep(i, N) {
    if (state & t) {
      forin(h, hist) {
        result += A[i][h];
      }
      hist.push_back(i);
    }
    t <<= 1;
  }
  return result;
}

long long emp = numeric_limits<long long>::min();
vector<long long> dp(1 << 16);
long long dfs(int state) {
  if (dp[state] != emp) {
    return dp[state];
  }

  long long maxv = score(state);
  for (int t = (state - 1) & state; t > 0; t = (t - 1) & state) {
    maxv = max(maxv, dfs(state ^ t) + dfs(t));
  }
  return dp[state] = maxv;
}

int main(){

  int input(n);
  N = n;
  rep(i, n) {
    long long list_input(t, n);
    vector<long long> tmp(t, t + n);
    A.push_back(tmp);
  }

  fill(dp.begin(), dp.end(), emp);

  out(dfs((1 << n) - 1));
}


Measured memory_bytes: 896
#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 D;
    cin>>D;
    vector<int> c(26);
    rep(i,26){
        int tmp=0;
        cin>>tmp;
        c[i]=tmp;
    }
    vector<vector<int>> s(D,vector<int>(26));
    vector<int> last(26,0);//最後にiのテストをやってからの経過日数とする
    rep(i,D){
        rep(j,26){
            int stmp=0;
            cin>>stmp;
            s[i][j]=stmp;
        }
    }

    vector<int> ans(D);
    rep(i,D){
        int tmp;
        cin>>tmp;
        ans[i]=tmp;
    }
    
    //i日目の満足度を計算する
    int manzokudo=0;//sは0indexにつき
    rep(i,D){
        //i日目にやるやつはans[i]
        manzokudo+=s[i][ans[i]-1];//sは0indexにつき

        rep(j,26){
            //テストans[i]-1以外はやってないので満足度下がる
            if(j!=ans[i]-1)
            manzokudo+=c[j]*(last[j]+1)*-1;//やってないとしたので1ひいとく
        }
        //i日目にans[i]-1番のテストをやることに決めたので
        //ans[i]-1番以外のlastを1増やす,ans[i]-1番は0に戻る
        rep(j,26){
            if(j!=ans[i]-1){
                last[j]++;
            }else{
                last[j]=0;
            }
        }
        cout << manzokudo << endl;
    }


    return 0;
}

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

int main(){
  int n,array[100001],ans=0,array2[100001]={};
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>array[i];
  }
  sort(array,array+n);
  for(int i=0;i<n;i++){
    if(array[i]>=100001){
      ans++;
    }else{
      array2[array[i]]++;
    }
  }
  for(int i=1;i<=100000;i++){
    if(array2[i]){
      if(array2[i]>=i){
      ans+=abs(array2[i]-i);
      }else{
        ans+=array2[i];
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iomanip>
#define faster       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define f(i,a,b) for(ll i=a;i<b;i++)
#define r(i,a,b) for(ll i=a;i>b;i--)
using namespace std;
typedef long long ll;
typedef long double ld;

int main(){
 ll n; cin >> n;
 vector <ll> v(n);
 f(i,0,n){
   cin>>v[i];
 }

 vector <ll> dp(n);
 dp[0]=0;
 dp[1]=abs(v[1]-v[0]);

 f(i,2,n){
   ll step1=dp[i-1]+abs(v[i]-v[i-1]);
   ll step2=dp[i-2]+abs(v[i]-v[i-2]);

   if(step1>=step2){
     dp[i]=step2;
   }else{
     dp[i]=step1;
   }
 }

 cout << dp[n-1] << endl;
 return 0;


}

Measured memory_bytes: 1792
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

class BIT{
  constructor(n){
    this.a = Array(n+1).fill(0);
  }
  add(val,id){
    for(var x=val,i=id;i<this.a.length;i+=i&-i)this.a[i]+=x;
  }
  get(id){
    for(var r=0,i=id;i;i-=i&-i)r+=this.a[i];
    return r;
  }
  range(l,r){//[l,r]
    return this.get(r) - this.get(l-1);
  }
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var [n,q] = nexts(2);
  var bi = new BIT(n);
  for(var i = 1; i <= n; i++){
    var a = next();
    bi.add(a,i);
  }
  for(var i = 0; i < q; i++){
    var [t,x,y] = nexts(3);
    if(t){
      print(bi.range(x+1,y));
    }else{
      bi.add(y,x+1);
    }
  }
}

Measured memory_bytes: 223864
#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const int big=1e8+10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
vector<pair<int,int>> oya;
vector<vector<pair<int,int>>> ko;
vector<int> kos;
void make_tree(int per=-1,int ter=0)
{//make_tree(-1,root);で木を作れる
	auto itr=ko[ter].end();
	for(auto it=ko[ter].begin();it!=ko[ter].end();it++){
		if(it->fir==per){itr=it;break;}
	}
	if(itr!=ko[ter].end()){oya[ter]=(*itr);ko[ter].erase(itr);}
	for(auto it=ko[ter].begin();it!=ko[ter].end();it++){
		make_tree(ter,it->fir);
	}
}
int sison_num(int ter=0){
	int ret=1;
	for(int i=0;i<ko[ter].size();i++){ret+=sison_num(ko[ter][i].fir);}
	kos[ter]=ret;
	return ret;
}

int main(void){
	int i,n;cin>>n;
	llint ans=0;
	llint minhen=big;
	vector<int>zyu;//実は要素数は1か2
	oya.res(n);
	ko.res(n);
	kos.res(n);
	for(i=0;i<n-1;i++){
		int a,b,c;cin>>a>>b>>c;a--;b--;
		ko[b].pub(mp(a,c));
		ko[a].pub(mp(b,c));
		
	}
	make_tree();
	sison_num();
	for(i=0;i<n;i++){
		int maxsub=n-kos[i];
		for(int j=0;j<ko[i].size();j++){maxeq(maxsub,kos[ko[i][j].fir]);}
		if(maxsub*2<=n){zyu.pub(i);}
	}
	for(i=1;i<n;i++){//i=0には親がない
		ans+=(llint)oya[i].sec*min(kos[i],n-kos[i])*2;
		if(abs(kos[i]-n+kos[i])<2){mineq(minhen,oya[i].sec);}
	}
	if(zyu.size()==1){
		int cent=zyu[0];
		minhen=oya[cent].sec;
		for(i=0;i<ko[cent].size();i++){mineq(minhen,ko[cent][i].sec);}
	}
	else{
		if(zyu[0]==0){swap(zyu[0],zyu[1]);}
		int a=zyu[0];int b=zyu[1];
		if(oya[a].fir==b){minhen=oya[a].sec;}
		else{minhen=oya[b].sec;}
	}
	ans-=minhen;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 10880
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI=acos(-1);
const ll mod=1e9+7;
typedef long long ll;
int f[65];
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        ll a;
        scanf("%lld",&a);
        for(ll j=0;j<62;j++)
            if(a&((ll)1<<j))
                f[j]++;
    }

    ll sum=0;
    for(ll i=0;i<62;i++){
        sum+=(((((ll)1<<i)%mod)%mod)*(n-f[i])%mod)*f[i]%mod;
        sum%=mod;
    }
    cout << sum << endl;
    return 0;
}

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

int main() {
  int H, W;
  scanf("%d%d", &H, &W);
  int h, w;
  scanf("%d%d", &h, &w);

  printf("%d", H * W - (h * W + (H - h) * w));
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

template<class T>
bool is_prime(T n) {
    if (n <= 1) return false;
    for (long long i = 2; (i * i) <= n; i++) {
        if ((n % i) == 0) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    vector<ll> dp(1e5 + 1, 0);
    reps(i, 1, sz(dp)) {
        dp[i] = dp[i - 1];
        if ((is_prime(i)) && (is_prime((i + 1) / 2))) dp[i]++;
    }
    ll q;
    cin >> q;
    rep(i, q) {
        ll l, r;
        cin >> l >> r;
        cout << (dp[r] - dp[l - 1]) << endl;
    }
    return 0;
}


Measured memory_bytes: 1408
package main

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

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func bfs(e [][]int, s int) (int, int) {
	set := e[s]
	visited := map[int]struct{}{s: {}}
	last := s
	count := 0
	for len(set) > 0 {
		nextSet := []int{}
		debugf("bfs: set: %v\n", set)

		for i := range set {
			visited[set[i]] = struct{}{}
			last = set[i]

			for _, j := range e[set[i]] {
				if _, ok := visited[j]; !ok {
					nextSet = append(nextSet, j)
				}
			}
		}
		set = nextSet
		count++
	}
	return last, count
}

func radius(e [][]int) int {
	farthest, _ := bfs(e, 0)
	debugf("farthest: %v\n", farthest)

	_, count := bfs(e, farthest)
	return count
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	e := make([][]int, n)

	for i := 0; i < n-1; i++ {
		u := nextInt()
		v := nextInt()
		e[u-1] = append(e[u-1], v-1)
		e[v-1] = append(e[v-1], u-1)
	}
	debugf("e: %v\n", e)

	ans := radius(e)
	debugf("radius: %v\n", ans)

	if ans%3 != 1 {
		_, _ = fmt.Fprint(writer, "First")
	} else {
		_, _ = fmt.Fprint(writer, "Second")
	}
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 29952