akhauriyash/Code-Regression huggingface dataset:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,K = map(int,input().split())
S = list(input())[:-1]
def rle(s):#計算量N
    n = len(s)
    tmp, count,stt,end = s[0], 1,[],[]
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            if tmp == "1":
                stt.append(i-count)
                end.append(i-1)
            tmp = s[i]
            count = 1
    if s[n-1] == "1":
        stt.append(n-count)
        end.append(n-1)
    return stt,end #最大2N文字
stt,end = rle(S)
n = len(stt)
if S[0] == "1" and S[N-1] == "1":
    if K >= n-1:
        print(N)
    else:
        MAX = 0
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
elif S[0] == "0" and S[N-1] == "0":
    if K >= n+1:
        print(N)
    else:
        MAX = max(end[K-1]+1,N-stt[-K])
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
elif S[0] == "1" and S[N-1] == "0":
    if K >= n:
        print(N)
    else:
        MAX = N-stt[-K]
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)
else:
    if K >= n:
        print(N)
    else:
        MAX = end[K-1]+1
        for i in range(n-K):
            MAX = max(MAX,end[i+K]-stt[i]+1)
        print(MAX)

Measured memory_bytes: 22104
#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll A[20][20],dp[1<<16] = {},value[1<<16] = {};

int main(){
	cin >> N;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cin >> A[i][j];
		}
	}
	for(int S=1;S<(1<<N);S++){
		for(int i=0;i<N;i++){
			if(S & (1<<i)){
				int T = S & ~(1<<i);
				value[S] = value[T];
				for(int j=0;j<N;j++){
					if(T & (1<<j)) value[S] += A[i][j];
				}
				break;
			}
		}
	}
	for(int S=0;S<(1<<N)-1;S++){
		int notS = S^((1<<N)-1);
		for(int T=notS;T>=0;T--){
			if((S&T)!=0) continue;
			dp[S|T] = max(dp[S|T],dp[S]+value[T]);
		}	
	}
	cout << dp[(1<<N)-1] << endl;
}

Measured memory_bytes: 1280
#include "bits/stdc++.h"
#define F first
#define S second
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll h = 0, a = 0;
  cin >> h >> a;
  cout << (h + a - 1) / a;
}



Measured memory_bytes: 3512
#![allow(non_snake_case, unused_macros, unused_imports)]

// Input
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

// Module
use std::cmp::{min,max};
use std::collections::{HashSet,BTreeMap};

// Main
fn main(){
    input!{
        x: u32,
    }
    println!("{}", if x<1200 {"ABC"}else{"ARC"});
}



Measured memory_bytes: 4352
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <deque>
using namespace std;
 
using ll=long long;
const int AMAX=100000;
ll cnt[AMAX+1];
 
int main(void){
  int N;
  ll K;
  cin>>N>>K;
  for(int i=0;i<N;++i) {
    int A, B;
    cin>>A>>B;
    cnt[A]+=B;
  }
  for(int ans=1; ans<=AMAX;++ans){
    if(K<=cnt[ans]) {
      cout<<ans<<endl;
      break;
    }
    K-=cnt[ans];
  }
  
  return 0;
}

Measured memory_bytes: 1024
//#include <bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){
    int N;
    cin >> N;
    for(int i = 1; i  <= 9; i++){
        if( N%i != 0) continue;
        int X = N/i; 
        if( 1<=X && X <=9 ){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
const string YES = "Yes";
const string NO = "No";
ll sum = 0;
void solve(long long N, long long M, std::vector<long long> A){
  ll ans = 0;
  double a = ((double)1/(double)(4*M));
  for (int i = 0; i < N; i++) {
    if( (double)((double)A[i]/(double)sum) >= a)ans++;
  }
  cout << (ans >= M ? YES:NO) << endl;
}

int main(){
    long long N;
	scanf("%lld",&N);
	long long M;
	scanf("%lld",&M);
	std::vector<long long> A(N);
	for(int i = 0 ; i < N ; i++){
		scanf("%lld",&A[i]);
    sum += A[i];
	}
    solve(N, M, std::move(A));
}


Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException{

		Scanner sc = new Scanner(System.in);
		String result = "";
		int score = 0;

		while(true) {
			int m = sc.nextInt();
			int f = sc.nextInt();
			int r = sc.nextInt();

			if(m == -1 && f == -1 && r == -1) {
				break;
			}

			score = m + f;

			if(m==-1 || f==-1) {
				result = "F";
			}else if(score >= 80) {
				result = "A";
			}else if(score >= 65) {
				result = "B";
			}else if(score >= 50) {
				result = "C";
			}else if(score >= 30) {
				if(r==-1 || r<50) {
					result = "D";
				}else if(r>=50) {
					result = "C";
				}
			}else {
				result = "F";
			}

			System.out.println(result);
		}

		sc.close();
	}
}


Measured memory_bytes: 26352
def Selection(A, N):
    c = 0
    i = 0
    while i < N:
        minj = i
        j = i
        while j < N:
            if A[j] < A[minj]:
                minj = j
            j += 1
        if i != minj:
            c += 1
            a = A[i]
            A[i] = A[minj]
            A[minj] = a
        i += 1
    return A, c

N = int(input())
A = list(map(int, input().split(' ')))
A, c = Selection(A, N)
print(' '.join(map(str, A)) + '\n' + str(c))


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

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> cnt(200001, 0);
    int Ai;
    for (int i = 0; i < N; i++)
    {
        cin >> Ai;
        cnt.at(Ai) += 1;
    }

    int v = 0;
    vector<int> w;
    for (int i = 0; i < 200001; i++)
    {
        if (cnt.at(i) > 0)
        {
            v++;
            w.push_back(cnt.at(i));
        }
    }
    sort(w.begin(), w.end());

    int res = 0;
    for (int i = 0; i < v - K; i++)
    {
        res += w.at(i);
    }
    cout << res << endl;
}

Measured memory_bytes: 2168
def judge(S,N):
    a = [x for x in list(S)]
    lst = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
    mak = []
    llst = lst + lst
    for i in range(len(a)):
        for j in range(26):
            if a[i]==llst[j]:
                mak.append(llst[j+N])
    print("".join(mak))

N = int(input())
S = input()
judge(S,N)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
const int MAX = 110;
int a[MAX];
bool can(int i, int m, double sum) {
    return 1.0*a[i] >= (sum/(4*m));
}
int main() {
   int m , n;
   scanf("%d %d", &n, &m);
   double sum = 0;
   for(int i = 0; i < n; ++i){
       scanf("%d", a+i);
       sum+=a[i];
   }
   sort(a, a+n);
   bool ok = true;
   for(int i = n-1, j = 0; i >= 0 && j < m; --i, ++j){
       ok &= can(i, m, sum);
   }
   puts(ok ? "Yes" : "No");
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int top, X[1000];

void push(int y)
{
  X[++top] = y;
}

int pop()
{
  top--;
  return X[top+1];
}


int main()
{
  int a, b;
  char c[100];
  top = 0;

  while(scanf("%s", c) != EOF)
    {
      if(c[0] == '+')
	{
	  a = pop();
	  b = pop();
	  push(a + b);
	}
      else if(c[0] == '-')
	{
	  a = pop();
	  b = pop();
	  push(b - a);
	}
      else if(c[0] == '*')
	{
	  a = pop();
	  b = pop();
	  push(a * b);
	}
      else
	{
	  push(atoi(c));
	}
    }
  printf("%d\n", pop());
  return 0;
}




Measured memory_bytes: 2068
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int n;
  cin>>n;
  vin a(n);
  rep(i,0,n){
   cin>>a[i]; 
  }
  sort(all(a));
  ll ans=0;
  if(n%2==0){//偶数
    bool ok=true;
    rep(i,0,n){
      if(i%2==0&& a[i]!=i+1) ok=false;
      if(i%2==1 && a[i]!=i) ok=false;
    }
    if(ok){
      ans=1;
      rep(i,0,n/2){
       ans*=2;
        ans%=inf;
      }
      
    }
  }
  else{//奇数
    bool ok=true;
    rep(i,0,n){
    if(i&2==0 && a[i]!=i) ok=false;
    if(i%2==1 && a[i]!=i+1) ok=false;
    }
    if(ok){
      ans=1;
     rep(i,0,(n-1)/2){
       ans*=2;
       ans%=inf;
     }
    }
  }//else
  
  cout<<ans<<endl;
}






//ぐうきで場合わけ　答えは2^(n/2)くらい　mod inf

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

int main() {
  string S;
  cin >> S;
  int x = 0;
  for(int i=0;i<4;i++){
    if(S.at(i)=='+'){
      x++;
    }
    else{
      x--;
    }
  }
  cout << x << endl;
}

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

int main() {
  string s, t;
  cin >> s >> t;
  
  int minimum = s.size();
  for (int i = 0; i < s.size() - t.size() + 1; i++) {
    int cnt = 0;
    for (int j = 0; j < t.size(); j++) {
      if (s.at(j + i) != t.at(j)) {
        cnt++;
      }
    }
    minimum = min(minimum, cnt);
  }
  
  cout << minimum << endl;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;
const ll MOD=1000000007,MOD2=998244353;



int main() {
    string S;
    cin>>S;
    string ans="Yes";
    rep(i,S.size()){
        if(i%2==0 && S.at(i)=='L'){ans="No";}
        if(i%2==1 && S.at(i)=='R'){ans="No";}
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import bisect
INF = 2**31 - 1

n = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(n)]
for _ in range(n-1):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  T[u].append(v)
  T[v].append(u)
stack = []
L = [INF]*n
ans = [0]*n
def dfs(v, par=-1):
  a = A[v]
  idx = bisect.bisect_left(L, a)
  stack.append((idx, L[idx]))
  L[idx] = a
  ans[v] = bisect.bisect_left(L, INF)
  for nv in T[v]:
    if nv != par:
      dfs(nv, v)
  b, c = stack.pop()
  L[b] = c
dfs(0)
print(*ans, sep="\n")

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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

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

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

void solve() {
    const i64 mod = 1'000'000'007;

    i64 N;
    cin >> N;

    string S;
    cin >> S;

    vector<i64> cnt(26);

    rep(i,0,N){
        ++cnt[S[i]-'a'];
    }

    i64 ans=1;
    rep(i,0,26){
        ans*=(cnt[i]+1);
        ans%=mod;
    }

    ans-=1;
    ans+=mod;
    ans%=mod;

    cout << ans << endl;
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<double> dvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

const int MAX_N=100000;
ll h[MAX_N+1];
int N;
ll dp[MAX_N+1];

void solve(){
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(int i=2;i<N;i++) dp[i]=min(dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i]-h[i-2]));
    cout<<dp[N-1]<<endl;
}

int main(){
    cin>>N;
    rep(i,N) cin>>h[i];
    solve();
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


int main() {
  ll N;
  cin>>N;
  ll count=0;
  vl vec(N);
  rep(i,N){
    cin>>vec.at(i);
  }
  for (int i = 0; i < N; i++){
    if(vec.at(i)==i+1){
      count++;
      i++;
    }
  }
  cout<<count<<endl;
}


Measured memory_bytes: 1024
s = input()
t = input()

a = []

for i in range(len(s) - len(t) + 1):
    w = s[i:i + len(t)]
    sum = 0
    for j in range(len(t)):
        if w[j] != t[j]:
            sum += 1
    a.append(sum)

print(min(a))


Measured memory_bytes: 73128
#include<stdio.h>

int main(){
	int a[52],b[52],p,c,i,j,n,r;
	while(1){
		scanf("%d %d",&n,&r);
		if(n==0&&r==0)break;
		for(i=1;i<=n;i++)a[i-1]=n-i+1;
		while(r--){
			//for(i=0;i<n;i++)printf("%d ",a[i]);
			//printf("\n");
			scanf("%d %d",&p,&c);
			for(i=0;i<c;i++)b[i]=a[p+i-1];
			for(i=p-2;i>=0;i--)a[i+c]=a[i];
			for(i=0;i<c;i++)a[i]=b[i];
		}
		printf("%d\n",a[0]);
	}
	return 0;
}

Measured memory_bytes: 1028
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		String kakou = s.substring(s.length() - 1);
		if(kakou.equals("s")){
			// 出力
			System.out.println(s + "es");

		}else{
			System.out.println(s + "s");
		}
		
	}
}

Measured memory_bytes: 38440
include Math
def fetch_prime_list3(max)
  table = Array.new(max + 1,true)
  prime_list = []

  (2..max).each do |num|
      if table[num] == true
        if num%10 == 3
          prime_list << num
        end
      k = num * num
      while k <= max
        table[k] = false
        k += num
      end
    end
  end
  return prime_list
end

N = gets.to_i
sosu3 = fetch_prime_list3(55555)

for i in 0..N-1 do
  print sosu3[i]
  print " "
end
puts ""




Measured memory_bytes: 2172
#include<bits/stdc++.h>
#define ll long long 
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define endl "\n"
#define MOD 1000000007 // 10^9 + 7
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define all(c) (c).begin(), (c).end()

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string s;
	cin >> s;
	set<char> s1(s.begin(),s.end());
	bool f=false;
	for(auto &x : s1) {
		int ct = count(all(s),x);
		if(ct != 2){
			f=true;
			break;
		}
	}
	if(!f) cout<<"Yes"<<endl;
	else 	cout<<"No"<<endl;
	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;
class Binaryindextree{
  private:
    vector<ll>v;
  public:
    Binaryindextree(int n):v(n + 1){}
    ll sum(int i){
      ll res = 0;
      for(++i; i > 0; i -= i & -i)res += v[i];
      return res;
    }
    void add(int i,ll t){
      for(++i; i < v.size(); i += i & -i)v[i] += t;
      return;
    }
};
int main(){
  int n,q;
  cin >> n >> q;
  Binaryindextree BIT(n);
  rep(i,q){
    int a,b,c;
    cin >> a >> b >> c;
    if(a == 0){
      b--;
      BIT.add(b,c);
    }
    if(a == 1){
      b--,c--;
      cout << BIT.sum(c) - BIT.sum(b - 1) << endl;
    }
  }
  return 0;
}


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

int n,m;
vector<int>adj[200001];
int vis[200001];

int main() {
    scanf("%d%d",&n,&m);
    for(int i=0,u,v;i<m;i++) {
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    queue<int> que;
    vis[1]=1;
    que.push(1);
    while(!que.empty()) {
        int cur=que.front();que.pop();
        for(auto &it:adj[cur]) if(!vis[it]) {
            vis[it]=vis[cur]+1;
            que.push(it);
        }
    }
    if(vis[n] && vis[n]<=3) puts("POSSIBLE");
    else puts("IMPOSSIBLE");

    return 0;
}


Measured memory_bytes: 13168
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> t(n); for (auto&& e : t) cin >> e;
  int m; cin >> m;
  while (m--) {
    int p, x; cin >> p >> x, --p;
    int res = 0;
    for (int i = 0; i < n; ++i) {
      res += i == p ? x : t[i];
    }
    cout << res << '\n';
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    const long long L = 100000000LL * 200000 + 199999LL * 100000LL * 100000000LL;
    int N;
    long long X, sD;
    while(cin >> N >> X >> sD){
        map<int, vector<pair<long long, long long>>> mp;
        long long D = abs(sD);
        if(D == 0){
            cout << (X == 0 ? 1 : N+1) << endl;
            continue;
        }
        mp[L%D] = vector<pair<long long, long long>>();
        mp[L%D].emplace_back(L/D, L/D);
        for(long long i=1;i<=N;i++){
            long long l = (i*X + (i-1)*i/2*sD + L);
            long long r = (i*X + (2*N-1-i)*i/2*sD + L);
            if(l > r) swap(l, r);
            int key = l%D;
            if(!mp.count(key)){
                mp[key] = vector<pair<long long, long long>>();
            }
            mp[key].emplace_back(l/D, r/D);
        }
        long long res = 0;
        for(auto& val : mp){
            auto& v = val.second;
            sort(v.begin(), v.end());
            auto end = v[0].first - 1;
            for(auto& p : v){
                res += max(0LL, p.second - max(end, p.first) + 1);
                end = max(end, p.second+1);
            }
        }
        cout << res << endl;
    }
}

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

using namespace std;

int main(int argc, char* argv[]){
    long long int N,answer;
    cin >> N;
    if(N%2==0) {
        answer = N/2;
        answer *= (N-1);
    }else {
        answer = (N-1)/2;
        answer *= N;
    }
    cout << answer << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <utility>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

void debug_print_ints(int* as, int n){
  printf("%d\n", n);
  for(int i=0; i < n; i++){
    printf("%d, ", as[i]);
  }
  printf("\n");
}

int N, K;
int pos[100001];
int cnt = 0;
bool zero = false;
int hajimete = -1;

int right2id(int i){
  if(i == 0){
    return 0;
  }
  int res = hajimete + (i - 1);
  if(0 <= res && res < cnt){
    return res;
  }else{
    return -1;
  }
}

int left2id(int i){
  if(i == 0){
    return 0;
  }
  int res = hajimete - i;
  if(0 <= res && res < cnt){
    return res;
  }else{
    return -1;
  }
}

void debug_id(){
  printf("hajimete: %d\n", hajimete);
  for(int i=0; i < cnt; i++){
    printf("%d: %d %d\n", i, left2id(i), right2id(i));
  }
}

int main(){
  scanf("%d %d", &N, &K);

  for(int i=0; i < N; i++){
    int temp;
    scanf("%d", &temp);
    if(temp != 0){
      pos[cnt] = temp;
      cnt++;
    }else{
      zero = true;
    }
    if(temp > 0 && hajimete == -1){
      hajimete = cnt - 1;
    }
  }
  if(hajimete == -1){
    //all are negative
    hajimete = cnt;
  }
  if(zero){
    N--;
    K--;
  }
  if(K == 0){
    printf("0\n");
    return 0;
  }

  //debug_print_ints(pos, N);

  //debug_id();
  

  
  int res = 1000000000;
  for(int i=0; i <= K; i++){
    int leftid = left2id(i);
    int rightid = right2id(K - i);
    if(leftid == -1 || rightid == -1){
      continue;
    }
    int leftlen = i == 0 ? 0 : abs(pos[leftid]);
    int rightlen = i == K ? 0 : abs(pos[rightid]);
    res = min(res, min(2*leftlen + rightlen, leftlen + 2*rightlen));
  }
  printf("%d\n", res);
  
  return 0;
}
  


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

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

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

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define drep(i, n) for(int i = n - 1; i >= 0; i--)

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

int main() {
  ll a, b, n;
  cin >> a >> b >> n;
  ll ans = 0;

  if (n % b == 0) {
    ans = (n - 1) * a / b  - a * ((n - 1) / b);
  } else {
    ans = n * a / b  - a * (n / b);
    ll base = (n / b) * b - 1;
    ans = max(ans, base * a / b - a * (base / b));
  }
  P(ans);
  return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
using namespace std;

bool comp_fn(pair<int, pair<string, int> > a, pair<int, pair<string, int> > b){
    if(a.second.first < b.second.first) return true;
    else if(a.second.first > b.second.first) return false;
    else {
        if(a.second.second > b.second.second) return true;
        else if(a.second.second < b.second.second) return false;
    }
}

int main(){
    IOS;

    int n;
    cin >> n;
    // vector<vector<int, int, int> > data(n);
    vector<pair<int, pair<string, int> > > data(n);

    for(int i=0;i<n;i++){
        int  p;
        string s;
        cin >> s >> p;
        pair<int, pair<string, int> > pr;
        pr.first = i+1;

        pair<string, int> row; 
        row.first = s;
        row.second = p;

        pr.second = row;

        data[i] = pr;
    }

    sort(data.begin(), data.end(), comp_fn);

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

    return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	var n int
	fmt.Scan(&n)

	scanner := bufio.NewScanner(os.Stdin)
	hs := strToIntSlice(scanLine(scanner))

	maxHeight := max(hs, n)

	count := 0
	for height := 1; height <= maxHeight; height++ {
		flag := false
		for index := 0; index < n; index++ {
			if hs[index] >= height && flag == false {
				flag = true
				count++
			} else if hs[index] < height && flag == true {
				flag = false
			}
		}
	}

	fmt.Println(count)
}


func scanLine(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func strToIntSlice(line string) []int {
	strSlice := strings.Split(line, " ")

	var intSlice []int
	for _, str := range strSlice {
		intValue, _ := strconv.Atoi(str)
		intSlice = append(intSlice, intValue)
	}

	return intSlice
}

func max(hs []int, n int) int {
	max := 0
	for index := 0; index < n; index++ {
		if max < hs[index] {
			max = hs[index]
		}
	}
	return max
}

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

int main() {
    int N; cin >> N;
    vector<int> vec(N);
    for (int i=0; i<N; i++) cin >> vec.at(i);

    bool ret = false;
    int elem = 1;
    int cnt = 0;
    for (int i=0; i<N; i++) {
        if (elem == vec.at(i)) {
            ret = true;
            elem++;
            continue;
        }
        cnt++;
    }

    if (ret) {
        cout << cnt << endl;
    } else {
        cout << -1 << endl;
    }
}

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

const int N = 1e5+5;
vector<int> heights;
int cache[N];
int n;

int solve(int idx){
	if( idx >= n-1 ){ return 0; }
	if( cache[idx] != -1 ){ return cache[idx]; }
	int &ans = cache[idx];
	int a1 = 1e9;
	int a2 = 1e9;
	if( idx == n-2 ){
		a1 = solve(idx+1) + abs(heights[idx] - heights[idx+1]);
	}else{
	  a1 = solve(idx+1) + abs(heights[idx] - heights[idx+1]);
	  a2 = solve(idx+2) + abs(heights[idx] - heights[idx+2]);
	}
	ans = min(a1,a2);
	return ans;
}



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

	cin>>n;
	heights.resize(n+10);
	for(int i=0; i<n; ++i){
		cin>>heights[i];
	}
	memset(cache,-1,sizeof(cache));
	int ans = solve(0);
	cout<<ans<<'\n';
	return 0;
}


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

template <typename T, typename U>
void chmax(T &a, const U &b){
  a = std::max<T>(a, b);
}


namespace solver{
  int64_t dp[3001][3001][4];
  int64_t item[3001][3001];
  constexpr int64_t H = 1000000000;

  void solve(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    
    int R, C, K; std::cin >> R >> C >> K;

    for(int i = 0; i < K; ++i){
      int r, c, v; std::cin >> r >> c >> v;
      --r, --c;
      item[r][c] = v;
    }

    for(int i = 0; i <= R; ++i){
      for(int j = 0; j <= C; ++j){
        for(int k = 0; k <= 3; ++k){
          if(i + 1 <= R){
            chmax(dp[i + 1][j][0], dp[i][j][k]);
            if(k <= 2) chmax(dp[i + 1][j][0], dp[i][j][k] + item[i][j]);
          }
          if(j + 1 <= C){
            chmax(dp[i][j + 1][k], dp[i][j][k]);
            if(k <= 2) chmax(dp[i][j + 1][k + 1], dp[i][j][k] + item[i][j]);
          }
        }
      }
    }

    int64_t ans = 0;
    for(int i = 0; i <= 3; ++i) ans = std::max(ans, dp[R][C][i]);
    
    std::cout << ans << "\n";
  }
}

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


Measured memory_bytes: 355364
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int cnt[4]={0};

    REP(i,3){
        int a,b; cin>>a>>b;
        a--; b--; 
        cnt[a]++; cnt[b]++;
    }

    if(*max_element(cnt,cnt+4)==2)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  long n;
  cin>>n;
  vector<bool> v;
  while(n!=0){
    v.push_back(abs(n%2));
    n=(n-abs(n%2))/2;
    n*=(-1);
  }
  int k=v.size();
  if(k==0)cout<<0;
  for (int i = k-1; i >= 0; i--) {
    cout<<v[i];
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;


int main(){
    ll x,y,z,k;
    cin>>x>>y>>z>>k;
    vector<ll> a(x);
    vector<ll> b(y);
    vector<ll> c(z);
    for(int i=0;i<x;i++) cin>>a[i]; sort(a.begin(),a.end());
    for(int i=0;i<y;i++) cin>>b[i]; sort(b.begin(),b.end());
    for(int i=0;i<z;i++) cin>>c[i]; sort(c.begin(),c.end());

    ll ub,lb;
    lb=0; ub=INF;
    while(ub-lb>1){
        ll m=(ub+lb)/2;
        ll cnt=0;
        bool flag=0;
        for(int i=x-1;i>=0;i--){
            for(int j=y-1;j>=0;j--){
                for(int l=z-1;l>=0;l--){
                    if(a[i]+b[j]+c[l]<m) break;
                    cnt++;
                    if(cnt>=k){
                        flag=1;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(flag){
            lb=m;
        }else{
            ub=m;
        }
    }
    ll cnt=0;
    priority_queue<ll> q;
    for(int i=x-1;i>=0;i--){
        for(int j=y-1;j>=0;j--){
            for(int l=z-1;l>=0;l--){
                if(a[i]+b[j]+c[l]<=lb) break;
                q.push(a[i]+b[j]+c[l]);
            }
        }
    }
    for(int i=0;i<k;i++) q.push(lb);
    for(int i=0;i<k;i++){
        cout<<q.top()<<endl;
        q.pop();
    }
    return 0;
}

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

struct UnionFind 
{
vector<int> par;
UnionFind(int N) : par(N)
{
for(int i=0;i<N;i++)par[i]=i;
}
int root(int x)
{
if(par[x]==x)return x;
return par[x]=root(par[x]);
}
void unite(int x,int y)
{
int rx=root(x);int ry=root(y);
if(rx==ry)return;
par[rx]=ry;
}
bool same(int x,int y)
{
int rx=root(x);int ry=root(y);
return rx==ry;
}
};

int main()
{
int n,q;scanf("%d %d",&n,&q);
UnionFind tree(n);
for(int i=0,com,x,y;i<q;i++)
{
scanf("%d %d %d",&com,&x,&y);
if(com==0)tree.unite(x,y);
else if(tree.same(x,y))printf("1\n");
else printf("0\n");
}
}


Measured memory_bytes: 3240
N, M = map(int, input().split())
A = list(map(int, input().split()))
total_vote = sum(A)
selectable = total_vote / (4 * M)
A.sort(reverse = True)
count = 0

for i in range(N):
    if A[i] >= selectable :
        count += 1
        if count == M:
            print('Yes')
            break;

    else:
        print('No')
        break;


Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define lli long long int
#define mod 1000000007
#define pb push_back
#define pf push_front
#define ulli unsigned long long int
#define what_is(x) cerr << #x << " is " << x << endl;
#define pi 2*acos(0.0)
#define F  first
#define S  second
#define endl '\n'
#define all(x) x.begin(),x.end()
using namespace std;
const lli INF = 1e18L+5;
/*
lli power(lli x,lli y)
{
    lli res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=y/2;
    }
    return res;
}
*/
int main()
{
//cout.precision(10);
//cout.setf(ios::fixed,ios::floatfield);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
	lli T=1;
    //cin>>T;
	while(T--)
	{
		lli i,a,b,n,z;
		vector<lli> v;
		cin>>n;
		for(i=0;i<n;i++)
		{
			cin>>z;
			v.pb(z);
		}
		lli cunt=0,ans=0;
		for(i=1;i<n;i++)
		{
			if(v[i]<=v[i-1])
			cunt++;
			else
			{
				cunt=0;
			}
			ans=max(ans,cunt);
		}
		cout<<ans<<endl;
	}
}
/*
contest
tt
*/


Measured memory_bytes: 1400
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s=sc.next();
		//String[] t=new String[4];
		int n = sc.nextInt();
		int m = sc.nextInt();
		int k = sc.nextInt();
		long count=0;
		long count1=0;
		int[] array = new int[3];
		Arrays.sort(array);

		/*for(int i=0;i<4;i++) {
			t[i]=s.substring(i,i+1);
			System.out.println(t[i]);
		}*/

		/*if(count>2||count1>=2) {
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}*/

		System.out.println(Math.min(m*n,k));
	}
}




Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(a,j,n) for(ll i=a;i<j;i=i+n )
typedef pair<ll,ll> P;
const ll mod = 1000000007;
const ll INF = 1000000009;
ll i;
ll ruijou(ll x, ll y){
    if(y==0) return x;
    if(y%2==0) return ruijou(x*x,y/2);
    else return x*ruijou(x,y-1);
}


int main(){
    ll L,R;
    cin>>L>>R;
    if(R-L>=2018)cout<<0;
    else{
        ll ans=2018;
        for(ll j=L;j<R;j++){
            for(ll k=j+1;k<=R;k++){
                ans=min(ans,(j*k%2019));
            }
        }
        cout<<ans;
    }
    cout<<endl;
}


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

int main(){
  int n, m;
  cin >> n >> m;
  map<ll,ll> mp;
  rep(i,n) {
    int a;
    cin >> a;
    mp[-a]++;
  }
  
  rep(i,m) {
    int b, c;
    cin >> b >> c;
    mp[-c] += b;
  }

  ll res = 0;
  ll cnt = 0;
  for (auto e : mp) {
    ll num = e.second;
    ll a = -e.first;
    if (cnt + num <= n) res += num * a, cnt += num;
    else {
      ll d = max(0LL,n - cnt);
      res += a * d;
      cnt += d;
    }
    //out << res <<  " " << cnt << endl;
  }
  //cout << cnt << endl;
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;



int main() {
  int h,w;
  scanf("%d%d",&h,&w);
  int n;
  scanf("%d",&n);
  vi a(n);
  cin>>a;
  vvi ans(h,vi(w));
  int x = 0;
  rep(i,n) {
    rep(j,a[i]) {
      int ni = x/w, nj = x%w;
      if (ni&1) nj = w-nj-1;
      ans[ni][nj] = i+1;
      ++x;
    }
  }
  rep(i,h) cout<<ans[i]<<endl;
  return 0;
}






















Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
#define MAXH 101
#define MAXW 101
#define INF 1000
#define MAXN 200002

int K, N;
int A[MAXN];

int main(){
    cin >> K >> N;

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

    int intm = 0, p = -1;
    for(int i = 0;i < N - 1;i++){
        if(intm < A[i + 1] - A[i]){
            intm = A[i + 1] - A[i];
            p = i;
        }
    }
    if(intm < A[0] + K - A[N - 1]){
        intm = A[0] + K - A[N - 1];
        p = N - 1;
    }
    
    printf("%d\n", K - intm);


    return 0;
}

Measured memory_bytes: 1024
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

void main()
{
    auto nm = readln.split.to!(int[]);
    auto N = nm[0];
    auto M = nm[1];

    long x = 1;
    int c;
    foreach (a; readln.split.to!(long[])) {
        auto y = x / gcd(x, a/2) * (a/2);
        if (y < 0 || M < y) {
            writeln(0);
            return;
        }
        x = y;
        int d;
        while (a%2 == 0) {
            ++d;
            a /= 2;
        }
        if (c == 0) {
            c = d;
        } else if (c != d) {
            writeln(0);
            return;
        }
    }
    writeln((M - x) / (x*2) + 1);
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

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

#define INF INT_MAX/3

#define MAX_N 1000


//// UnionFind
struct UnionFind{
	vector<int> v;
	UnionFind(int n) : v(n, -1) {}

	int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return false;
		if (-v[x] < -v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		return true;
	}
	bool root(int x) { return v[x] < 0; }
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -v[find(x)]; }
};

int n,m;
int num;
PPI es[11111];

bool ok(ll x){
	set<int> st;
	UnionFind uf(n);
	rep(i,m){
		if(es[i].fi>x)break;
		uf.unite(es[i].se.fi,es[i].se.se);
	}
	rep(i,n){
		st.insert(uf.find(i));
	}
	return st.size()-1<n/2;
}

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n>>m;
		if(n==0&&m==0)break;
		rep(i,m){
			cin>>es[i].se.fi>>es[i].se.se>>es[i].fi;
			es[i].se.fi--;
			es[i].se.se--;
		}
		sort(es,es+m);
		int lb=0,ub=1000;
		while(ub-lb>1){
			int mid=(lb+ub)/2;
			if(ok(mid))ub=mid;
			else lb=mid;
		}
		cout<<ub<<endl;
	}
	return 0;
}

Measured memory_bytes: 3308
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
 
using namespace std;

const int INF = 1 << 30;

int main(){
    int N,T;
    int ans = INF;

    cin >> N >> T;

    for(int i = 0;i < N;i++){
        int c,t;
        cin >> c >> t;
        if(t <= T)ans = min(ans,c);
    }

    if(ans == INF)cout << "TLE" << endl;
    else cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import qualified Data.Array.IO as A
import Debug.Trace
import Data.List
import Control.Monad
import Data.Ord

r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

rp :: IO (Int,Int)
rp  = toTup . unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine

toTup [a,b] = (a,b)


main :: IO ()
main = do
    n <- readLn
    ws <- r n
    let ls = U.scanl' (+) 0 ws
    let rs = U.scanr' (+) 0 ws
    let res = (U.tail . U.init . U.map abs) $ U.zipWith (-) ls rs
    print $ U.minimum res

Measured memory_bytes: 508
a,b,c,d = map(int,input().split())
total_count_1 = 0
total_count_2 = 0


while c > 0:
    c = c - b
    total_count_1 +=1

while a >0:
    a = a -d
    total_count_2 +=1

if  total_count_1 <= total_count_2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9180
#include<bits/stdc++.h>                                                                                                                         
using namespace std;                                               
int main()
{
	int s1,s2,t1,t2; 
	cin>>s1>>s2>>t1>>t2;
	for(int i=s2;i<t2;i++) cout<<'U';
	for(int j=s1;j<t1;j++) cout<<'R';
	for(int i=t2;i>s2;i--) cout<<'D';
	for(int j=t1;j>s1;j--) cout<<'L';
	cout<<'L';
	for(int i=s2;i<=t2;i++) cout<<'U';
	for(int j=s1;j<=t1;j++) cout<<'R';
	cout<<'D';
	cout<<'R';
	for(int i=t2;i>=s2;i--) cout<<'D';
	for(int j=t1;j>=s1;j--) cout<<'L';
	cout<<'U';
	return 0;
}  

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> G[200005];
ll v[200005];
int arrived[200005];

int dfs(int idx, ll pval) {
  arrived[idx] = 1;
  v[idx] += pval;
  for (int i=0; i<G[idx].size(); i++) {
    int n = G[idx][i];
    if (!arrived[n]) {
      dfs(n, v[idx]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  for (int i=0; i<N-1; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for (int i=0; i<Q; i++) {
    int p, x;
    cin >> p >> x;
    v[p] += x;
  }
  dfs(1, 0LL);
  cout << v[1];
  for (int i=2; i<=N; i++) {
    cout << ' ' << v[i];
  }
  cout << endl;
}

Measured memory_bytes: 25088
#include<bits/stdc++.h>
#define  ll  long long int
#define  sz  200010

using namespace std;

map<ll,ll>mp;

int main()
{

    ll s=0,i,j,k,p,d,n,a,b;

    cin>>n;

    for(i=1;i<=n;i++)
    {
        cin>>a;
        mp[a]++;
    }

    map<ll,ll>::iterator it;

    for(it=mp.begin();it!=mp.end();it++)
    {
        a=it->first;
        b=it->second;

        if(b<a)s+=b;
        else if(b>a)
        {
            s+=(b-a);
        }
    }

    cout<<s<<endl;

    return 0;
}


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

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)

const ll MOD = 1000000007;

using namespace std;

int main()
{
	string S;
	cin >> S;
	string a[4] = { "dreamer","dream","erase","eraser" };

	IREP(i, S.length() - 1)
	{
		string sub = S.substr(i);
		REP(j, 4)
		{
			if (a[j].length() >= sub.length()) {
				if (a[j] == sub)
				{
					S.erase(i);
					break;
				}
				if (a[j].substr(a[j].length() - sub.length()) == sub) {
					break;
				}
			}
			if (j == 3)
			{
				cout << "NO" << endl;
				return 0;
			}
		}
	}
	cout << "YES" << endl;
	return 0;
}

Measured memory_bytes: 512
while(h,w=gets.split.map &:to_i)[0]>0
a=[]
b=[s=0]*w
h.times{|i|gets;a[i]=[]
w.times{|j|a[i]<<l=$_[j]<?.?0:(a[i][-1]||0)+1
m=b[j]+=l>0?1:0
l*m>s&&(1..m).each{|k|l>(t=a[i-k+1][j])&&l=t;l*m<s ?(break):s<l*k&&s=l*k}}}
p s
end

Measured memory_bytes: 8560
s = input()

flg = 0

if s[0] == "A":
    flg = 1
else:
    print("WA")
    exit()

t  = s[2:-1]


if t.count("C") == 1:
    flg = 1
else:
    print("WA")
    exit()

s=s.replace("A", "")
s =s.replace("C", "")


if s.islower():
    print("AC")
else:
    print("WA")


Measured memory_bytes: 9052
#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;



int main(void){

    int N;
    cin>>N;
    int a[N];
    int count[N];
    int i;
    int ans=0;
    rep(i,N){
        cin>>a[i];
        count[i]=0;
        while(a[i]%2==0){
            a[i]/=2;
            count[i]++;
            ans++;
        }
    }
    cout << ans << endl;


    return 0;
}

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


int main(){
   int h,w,a,b;
   cin >>h>>w>>a>>b;
   cout << (h-a)*(w-b) <<endl;
   return 0;
}


Measured memory_bytes: 256