akhauriyash/Code-Regression huggingface dataset:
w, h, n = map(int, input().split())
field = [["" for _ in range(w)] for _ in range(h)]

def draw(x0, x1, y0, y1):
    for y in range(y0, y1 + 1):
        for x in range(x0, x1 + 1):
            field[y][x] = "#"

for i in range(n):
    X, Y, a = map(int, input().split())
    if a == 1:
        draw(0, X - 1, 0, h - 1)
    elif a == 2:
        draw(X, w - 1, 0, h - 1)
    elif a == 3:
        draw(0, w - 1, 0, Y - 1)
    elif a == 4:
        draw(0, w - 1, Y, h - 1)

c = 0
for y in range(h):
    for x in range(w):
        if field[y][x] == "":
            c += 1

print(c)


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

using namespace std;

int main() {
  string N, M;
  cin >> N;
  M = N;
  reverse(N.begin(), N.end());
  if (N == M) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3596
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repe(i, n) REPN(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
template <typename T>
void coVec(const Vec1<T> &v){for(T i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;

int main(void){
	ll n;
	cin >> n;
	Vec2<ll> e(n, Vec(n));

	rep(i, n){
		bitset<10> bits1(i);
		REP(j, i+1, n){
			bitset<10> bits2(j);
			rep(k, 10){
				if(bits1[k] != bits2[k]){
					e[i][j] = k+1;
					break;
				}
			}
		}
	}

	rep(i, n){
		REP(j, i+1, n) cosp(e[i][j]);
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 2432
import java.io.*;
import java.util.*;

public class Main {

	static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e){e.printStackTrace();}
        }

        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {st = new StringTokenizer(br.readLine());}
            catch (Exception e) {e.printStackTrace();}
            return st.nextToken();
        }

        public int nextInt() {return Integer.parseInt(next());}

        public long nextLong() {return Long.parseLong(next());}

        public double nextDouble() {return Double.parseDouble(next());}

        public String nextLine() {
            String line = "";
            if(st.hasMoreTokens()) line = st.nextToken();
            else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
            while(st.hasMoreTokens()) line += " "+st.nextToken();
            return line;
        }
    }

	public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);

        String s = sc.nextLine();
        int k = s.length();

        while(k > 0) {
            if(k >= 5 && s.substring(k-5, k).equals("dream")) {
                k -= 5;
            }
            else if(k >= 7 && s.substring(k-7, k).equals("dreamer")) {
                k -= 7;
            }
            else if(k >= 5 && s.substring(k-5, k).equals("erase")) {
                k -= 5;
            }
            else if(k >= 6 && s.substring(k-6, k).equals("eraser")) {
                k -= 6;
            }
            else {
                pw.println("NO");
                pw.close();
                return;
            }
        }

        pw.println("YES");
        pw.close();
	}

}

// dream, dreamer, erase, eraser

Measured memory_bytes: 26708
import java .util.*;

public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String day = sc.next();
    String day_up = "2018/";
    
    for (int i = 5; i < 10; i++){
      day_up = day_up + day.substring(i, i+1);
    }
    System.out.println(day_up);
    
  }
}

Measured memory_bytes: 22996
//-*-coding:utf-8-*-
//----------------------------------------------------------
// module: main
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
//----------------------------------------------------------
#include <algorithm>
#include <vector>
#include <deque>
#include <map>

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXL = 10;

int numbers[MAXL];

bool can_solve(int i, int a, int b){
    int v = numbers[i];
    if (i >= MAXL) return true;

    if (v > a && can_solve(i+1, v, b)) return true;
    if (v > b && can_solve(i+1, a, v)) return true;
    return false;
}

bool solve(){
    return can_solve(0, -1, -1);

    int a = -1;
    int b = -1;
    for (int i = 0; i < 10; ++i)
        {
            if (a > b && b > 0) {
                if (numbers[i] > a) { a = numbers[i]; }
                else if (numbers[i] > b) { b = numbers[i]; }
                else return false;
            }
            else if (b > a && a > 0){
                if (numbers[i] > b) { b = numbers[i]; }
                else if (numbers[i] > a) { a = numbers[i]; }
                else return false;
            }
                
            if(a < 0){a = numbers[i]; continue; };
            if(b < 0){b = numbers[i]; continue; };
        }
    return true;
};

int main(int argc, char *argv[])
{
    int c;
    scanf("%d", &c);
    for (int i = 0; i < c; ++i)
        {
            scanf("%d %d %d %d %d %d %d %d %d %d", &numbers[0], &numbers[1], &numbers[2], &numbers[3], &numbers[4], &numbers[5], &numbers[6], &numbers[7], &numbers[8], &numbers[9]);
            bool result = solve();
            if ( solve() ){ printf("YES\n"); }
            else { printf("NO\n"); }
        }
    return 0;
}

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

#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int mod = (int)1e7+9;
#define REP0(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<=n;i++)
#define F first
#define S second
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define inf (int)(1e18)
#define prec(x) fixed<<setprecision(x)<<x
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

void solve(){
   ll a,b,c,d;
   cin>>a>>b>>c>>d;
   ll ans = max(a,b) * max(c,d);
   ll ans1 = min(a,b) * min(c,d);
   ll ans3 = max(a,b) * min(c,d);
   ll ans4 = min(a,b) * max(c,d);

   cout<<max({ans,ans1,ans3,ans4})<<endl;
}


int main(){
    fastio;
    #ifndef ONLINE_JUDGE
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
    int tc = 1;
    // cin>>tc;
    for(int i=1;i<=tc;i++){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3648
n,m = map(int,input().split())
x = list(map(int,input().split()))

if m <= n:
    ans = 0
else:
    x.sort()
    dx = [x[i]-x[i-1]-1 for i in range(1,m)]
    dx.sort(reverse=True)
    ans = x[m-1] - (x[0] - 1) - n - sum(dx[:n-1])

print(ans)


Measured memory_bytes: 13968
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
//		String[] tmpArray = br.readLine().split(" ");
		int n = Integer.parseInt(br.readLine());
//		int b = Integer.parseInt(tmpArray[1]);
//		int c = Integer.parseInt(tmpArray[2]);
//		int y = Integer.parseInt(tmpArray[3]);
//		int r = Integer.parseInt(tmpArray[4]);

		int[][][] person = new int[4][3][10];
		for(int i = 0;i < 4; i++){
			for(int j = 0; j < 3; j++){
				Arrays.fill(person[i][j], 0);
			}
		}

		//String[] tmpArray = br.readLine().split(" ");
		//int[] input = new int[n];
		for(int i = 0; i < n; i++){
			String[] tmpArray = br.readLine().split(" ");
			int b = Integer.parseInt(tmpArray[0])-1;
			int f = Integer.parseInt(tmpArray[1])-1;
			int r = Integer.parseInt(tmpArray[2])-1;
			int v = Integer.parseInt(tmpArray[3]);
			
			person[b][f][r] += v;
		}
		
		for(int i = 0; i < 4; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 10; k++){
					System.out.print(" "+person[i][j][k]);
				}
				System.out.println();
			}
			if(i != 3){
				for(int j = 0; j < 20; j++){
					System.out.print("#");
				}
				System.out.println();
			}
		}
//		
//		System.out.print(input[0]);
//		for(int i = 1 ; i < n; i++){
//			System.out.print(" "+ input[i]);
//		}
//		System.out.println();
////		
//		Arrays.sort(input);
//		System.out.printf("%d %d %d\n", input[0], input[input.length - 1], sum);
//		
//		while(true){
//			String[] tmpArray = br.readLine().split(" ");
//			int a = Integer.parseInt(tmpArray[0]);
//			int b = Integer.parseInt(tmpArray[1]);
//			if(a == 0 && b == 0){
//				break;
//			}
//			
//			for(int i = 0; i < a; i++){
//				for(int j = 0; j < b; j++){
//					if((i + j)%2 == 1){
//						System.out.print(".");
//					}
//					else{
//						System.out.print("#");
//					}
//				}
//				System.out.println();
//			}
//			System.out.println();
//		}

		//		int[] array = new int[3];
//		array[0] = a; array[1] = b; array[2] = c;
//
//		Arrays.sort(array);
//		System.out.printf("%d %d %d\n", array[0], array[1], array[2]);
		/*
		if(a < b && b < c){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}*/
	}

}

Measured memory_bytes: 24892
N = int(input())
S = list(input())
left = [0] * N
if S[0] == '#':
    left[0] += 1
for i in range(1,N):
    left[i] = left[i-1]
    if S[i] == '#':
        left[i] += 1
if left[-1] == 0:
    print(0)
    exit()

right = [0] * N
if S[-1] == '.':
    right[-1] += 1
for i in reversed(range(N-1)):
    right[i] = right[i+1]
    if S[i] == '.':
        right[i] += 1
if right[0] == 0:
    print(0)
    exit()
ans = min(left[-1],right[0])
for i in range(N):
    if S[i] == '#':
        ans = min(ans,left[i]-1 + right[i])
print(ans)


Measured memory_bytes: 20108
#include<set>
#include<map>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
 
struct lex_compare {
    bool operator()(const ll &a, const ll &b)const
{
    return a>b;
}
};
 
int main(){
    ll N,W;
    cin>>N>>W;
    vector<ll>w(N),v(N);
    for(int i=0;i<N;i++){
        cin>>w[i]>>v[i];
    }
    set<ll,lex_compare>weights;
    for(ll i=N;i>0;i--){
        for(int j=3*i;j>=0;j--)
            weights.insert(w[0]*i+j);
    }
    weights.insert(0);
    map<ll,ll>dp;
    dp.clear();
    ll ans=0;
    for(int i=0;i<N;i++){
        for(auto j:weights){
            if(j>=w[i]){
                    if(dp[j-w[i]]||j-w[i]==0){
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                    if(j<=W)ans=max(ans,dp[j]);
                }
            }
        }
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 1920
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
#include <sstream>
using namespace std;
int main(void){
    int n,ans,i,j,k,l;
    while(cin >> n){
    ans = 0;
    for(i = 0; i <= 9; i++){
        for(j = 0; j <= 9; j++){
            for(k = 0; k <= 9; k++){
                for(l = 0; l <= 9; l++){
                    if(i+j+k+l == n){
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3048
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
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 ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

void DFS(vvc &g,vvb &ok,int h,int w){
	ok.at(h).at(w) = true ;
	for(int i=0;i<4;i++){
		ll y = h+dy4.at(i) ;
		ll x = w+dx4.at(i) ;
		if(g.at(y).at(x)=='.'&&!ok.at(y).at(x)) DFS(g,ok,y,x) ;
	}
}

int main(){
	ll h,w,k,sx,sy,gx,gy ;
	cin >> h >> w >> k >> sy >> sx >> gy >> gx ;
	vvc g(h+2,vc(w+2,'@')) ;
	for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin >> g.at(i).at(j) ;
	vvb ok(h+2,vb(w+2,false)) ;
	DFS(g,ok,sy,sx) ;
	if(ok.at(gy).at(gx)){
		vector<vvll> cnt(h+2,vvll(w+2,vll(4,INF))) ;
		priority_queue<pair<pll,pll>,vector<pair<pll,pll>>,greater<pair<pll,pll>>> pq ;
		auto push = [&](ll a,ll b,ll c,ll d){
			pair<pll,pll> tmp = {{a,b},{c,d}} ;
			pq.emplace(tmp) ;
		} ;
		push(0,0,sy,sx) ;
		while(!pq.empty()){
			pair<pll,pll> cur = pq.top() ; pq.pop() ;
			ll y = cur.second.first ;
			ll x = cur.second.second ;
			ll dir = cur.first.second ;
			ll d = cur.first.first ;
			if(cnt.at(y).at(x).at(dir)<=d) continue ;
			cnt.at(y).at(x).at(dir) = d ;
			for(int i=0;i<4;i++){
				if(i==dir){
					y += dy4.at(i) ;
					x += dx4.at(i) ;
					if(g.at(y).at(x)=='.'&&cnt.at(y).at(x).at(dir)==INF){
						push(d+1,dir,y,x) ;
					}
					y -= dy4.at(i) ;
					x -= dx4.at(i) ;
				}else{
					if(cnt.at(y).at(x).at(i)==INF){
						push((d+k-1)/k*k,i,y,x) ;
					}
				}
			}
		}
		ll ans = INF ;
		for(int i=0;i<4;i++) chmin(ans,cnt.at(gy).at(gx).at(i)) ;
		cout << (ans+k-1)/k << endl ;
		// for(int i=1;i<=h;i++){
			// for(int j=1;j<=w;j++){
				// ll sub = INF ;
				// for(int k=0;k<4;k++) chmin(sub,cnt.at(i).at(j).at(k)) ;
				// cout << sub << " " ;
			// }
			// cout << endl ;
		// }
	}else{
		cout << -1 << endl ;
	}
}


Measured memory_bytes: 334312
#include<iostream>
#include<cstdlib>

using namespace std;


int num_of_line;
int price[200000];

// 最大値と最大値のインデックスを返却する関数
int max(int begin, int *index);

int main()
{
    cin >> num_of_line;

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

    // 配列操作用インデックス
    int *max_index = (int *)malloc(1 * sizeof(int));

    *max_index = 0;

    int max_price = 0;
    int max_diff_price = -1000000000;

    for (int ti = 0; ti < num_of_line; ti++) {
        if (ti >= *max_index)
            max_price = max(ti, max_index);
        
        if (ti < num_of_line - 1) {
            int tmp = max_price - price[ti];
            if (tmp > max_diff_price)
                max_diff_price = tmp;
        }  
    }

    cout << max_diff_price << endl;

    return 0;
}

int max(int begin, int* index)
{
    int max = 0;
    int ind = 0;

    for (int i = begin + 1; i < num_of_line; i++) {
        if (price[i] >= max) {
            max = price[i];
            ind = i;
        }
    }

    *index = ind;
    return max;
}


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

const int INF = 1000000100;
int tmp[20];

int simulate(int bits, vector<int> &C, vector<vector<int>> &A, int N, int M, int X)
{
    int res = 0;
    for(int i = 0; i < M; ++i) tmp[i] = 0;
    for(int i = 0; i < N; ++i) {
        if((bits >> i) & 1) {
            res += C[i];
            for(int j = 0; j < M; ++j) {
                tmp[j] += A[i][j];
            }
        }
    }
    for(int i = 0; i < M; ++i) {
        if(tmp[i] < X) return INF;
    }
    return res;
}

int main() {
    int N, M, X;
    cin >> N >> M >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));
    for(int i = 0; i < N; ++i) {
        cin >> C[i];
        for(int j = 0; j < M; ++j) {
            cin >> A[i][j];
        }
    }

    int res = INF;
    for(int bits = 0; bits < (1 << N); ++bits) {
        res = min(res, simulate(bits, C, A, N, M, X));
    }
    if(res == INF) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

Measured memory_bytes: 3636
from collections import deque
from itertools import product


def main():
    h, w = map(int, input().split())
    c = tuple(map(lambda x: int(x)+1, input().split()))
    d = tuple(map(lambda x: int(x)+1, input().split()))
    s = ['#'*(w+4)]*2 + [f'##{input()}##' for _ in range(h)] + ['#'*(w+4)]*2

    move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
    move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

    cost = [[float('inf')] * (w+4) for _ in range(h+4)]
    cost[c[0]][c[1]] = 0
    yet = deque([(c[0], c[1], 0)])
    done = deque()

    while yet:
        y, x, m = yet.popleft()
        done.append((y, x, m))
        # Move A
        for dx, dy in move_a_area:
            hh, ww = y + dy, x + dx
            if s[hh][ww] == '#' or cost[hh][ww] <= m:
                continue
            cost[hh][ww] = m
            yet.append((hh, ww, m))
        # Move B
        if not yet:
            while done:
                y, x, m = done.popleft()
                for dx, dy in move_b_area:
                    hh, ww = y + dy, x + dx
                    if s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
                        continue
                    cost[hh][ww] = m + 1
                    yet.append((hh, ww, m + 1))

    print(v if (v := cost[d[0]][d[1]]) < float('inf') else -1)


if __name__ == '__main__':
    main()


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

int main() {
    std::string S;
    std::cin >> S;

    const int MOD = 2019;
    const int n = S.size();
    int cnt[2019] = {0};

    int64_t r[n+1] = {0};
    int64_t p = 1;
    cnt[0] = 1; 
    for (int i = n - 1; i >= 0; --i) {
        r[i] = r[i + 1] + p * (S[i] - '0');
        r[i] %= MOD;
        p = p * 10 % MOD;
        ++cnt[r[i]];
    }

    int64_t ans = 0;
    for (int i = 0; i < 2019; ++i) {
        // printf("cnt[%d]=%d\n", i, cnt[i]);
        ans += cnt[i] * (cnt[i] - 1) / 2;
    }
    
    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 5292
from fractions import Fraction

while True:
    s = input()
    if s == '#':
        break
    if s[-4:] == 'west':
        ans = Fraction(90)
        s = s[:-4]
    else:
        ans = Fraction(0)
        s = s[:-5]
    i = 1
    while s:
        if s[-4:] == 'west':
            ans += Fraction(90, 1 << i)
            s = s[:-4]
        else:
            ans -= Fraction(90, 1 << i)
            s = s[:-5]
        i += 1
    print(ans)

Measured memory_bytes: 10092
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;

int main(){
    using namespace std;
    int n;
    cin >> n;
    vector <int> data(n);
    rep(i, n) cin >> data[i];
    bool flag = false;
    int cnt = 0;
    rep(j, n - 1) {
        if (flag) {
            flag = false;
            continue;
        }
        if (data[j + 1] == data[j]) {
            flag = true;
            ++cnt;
        }
    }
    cout << cnt << 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;

int main(){
	string s;
	cin >> s;
	string a;
	a = "SUN";
	int i(0);
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << 7 << endl;
		return 0;
	}
	i++;
	a = "SAT";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	a = "FRI";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	a = "THU";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	a = "WED";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	a = "TUE";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	a = "MON";
	if((s[0] == a[0]) && (s[1] == a[1]) && (s[2] == a[2])){
		cout << i << endl;
		return 0;
	}
	i++;
	return 0;
}

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

int abs(int a, int b)
{
  return (a > b) ? a - b : b - a;
}

int w, h, n, spotx[1000], spoty[1000], total = 0;
int main()
{
  cin >> w >> h >> n;
  for(int i = 0; i < n; i++) cin >> spotx[i] >> spoty[i];
  for(int i = 1; i < n; i++){
    if((spotx[i - 1] <= spotx[i] && spoty[i - 1] >= spoty[i]) || (spotx[i - 1] >=spotx[i] && spoty[i - 1] <= spoty[i])){
      total += abs(spotx[i - 1], spotx[i]) + abs(spoty[i - 1], spoty[i]);
    }
    else{
      total += max(abs(spotx[i - 1], spotx[i]), abs(spoty[i - 1], spoty[i]));
    }
  }
  cout << total << endl;
  return 0;
}

Measured memory_bytes: 1168
#include <cstdio>
#include <algorithm>
using namespace std;
static const int MAX = 10;
static const int INFTY = 1000000;
int V;
int d[MAX][MAX];


void floyd() {
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            if (d[i][k] == INFTY) continue;
            for (int j = 0; j < V; j++) {
                if (d[k][j] == INFTY) continue;
                d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int sum, minv=INFTY, mini;
    for (int i = 0; i < V; i++) {
        sum = 0;
        for (int j = 0; j < V; j++) sum += d[i][j];
        if (sum < minv) { minv = sum, mini = i; }
    }
    printf("%d %d\n", mini, minv);
}



int main() {
    int E, source, target, cost;
    for(; ;) {
        std::scanf("%d", &E);
        if (E == 0) break;
        for (int i = 0; i < 10; i++) fill(d[i], d[i]+10, INFTY);
        V = 0;
        for (int i = 0; i < E; i++) {
            std::scanf("%d %d %d", &source, &target, &cost);
            d[source][target] = d[target][source] = cost;
            V = max(V, max(source, target));
        }
        V++;
        for (int i = 0; i < V; i++) d[i][i] = 0;
        floyd();
    }
    return 0;
}



Measured memory_bytes: 2700
while True:
    n, m, a = map(int, raw_input().split())
    if n == 0:
        break
    bar = [[-1 for i in xrange(n + 1)] for j in xrange(1001)]
    for i in xrange(m):
        h, p, q = map(int, raw_input().split())
        bar[h][p] = q
        bar[h][q] = p
    
    cur = a
    
    for i in xrange(1000, -1, -1):
        if bar[i][cur] != -1:
            cur = bar[i][cur]
    print cur

Measured memory_bytes: 6052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=1e18;
int main(){
  int n;
  cin >> n;
  vector<ll> a(n),dp(n+1,0);
  for(int i=0;i<n;i++){
    cin >> a[i];
    dp[i+1]=dp[i]+a[i];
  }
  for(int split=2;split+1<n;split++){
    ll p=0,q=dp[split],r=0,s=dp[n];
    auto itr1 = lower_bound(dp.begin(), dp.end(), dp[split]/2);
    auto itr2 = lower_bound(dp.begin(), dp.end(), (dp[n]+dp[split])/2);
    
    for(int d=-1;d<2;d++){
      if(max(p,q-p)>max(*(itr1+d),q-*(itr1+d))){
        p=*(itr1+d);
      }
      if(max(r-q,s-r)>max(*(itr2+d)-q,s-*(itr2+d))){
        r=*(itr2+d);
      }      
    }
    ll diff=max({s-r,r-q,q-p,p})-min({s-r,r-q,q-p,p});
    ans=min(ans,diff);
  }
  cout << ans << endl;
}


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

int main(){
  string s;
  cin >> s;
  int w;
  cin >> w;
  int n=1;
  if(w==1){
    cout << s << endl;
    return 0;
  }
  for(int i=0; i<s.size(); i++){
    if(n%w==1) cout << s[i];
    n++;
  }
  cout << endl;
}
      


Measured memory_bytes: 3596
#include <stdio.h>

int main(){
    int n, T, c[100], t[100];
    int i, cmin=1001;

    scanf("%d %d", &n, &T);

    for(i=0; i<n; i++){
        scanf("%d %d", &c[i], &t[i]);

        if(T >= t[i]){
            if(cmin > c[i]){
                cmin = c[i];
            }
        }
    }

    if(cmin == 1001)
        printf("TLE\n");
    else
        printf("%d\n", cmin);
    
    return 0;

}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> A(N);
    for(auto& in:A){ cin >> in; in = abs(in);}
    ll odd_cnt,even_cnt;
    odd_cnt = even_cnt = 0;
    for(auto a:A){
        if(a%2 == 0){
            even_cnt++;
        }else{
            odd_cnt++;
        }
    }
    if(odd_cnt%2 == 1){
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    return 0;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, std::vector<long long> A){
    LL all = 0;
    REP1(i, N+2) all += abs(A[i] - A[i-1]); 
    REP1(i, N-1) cout << all - abs(A[i] -  A[i-1]) - abs(A[i+1] - A[i]) + abs(A[i+1] - A[i-1]) << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    N+=2;
    std::vector<long long> A(N);
    A.PB(0);
    for(int i = 1 ; i < N-1 ; i++){
        scanf("%lld",&A[i]);
    }
    A.PB(0);
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 2032
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

void print_vec(vector<int> vec)
{
  cout << "[";
  for (int i = 0; i < vec.size(); i++)
  {
    cout << vec.at(i);
    if (i < vec.size() - 1)
    {
      cout << ", ";
    }
  }
  cout << "]...size: " << vec.size() << endl;
}

int main()
{
  int n = 0;
  cin >> n;

  while (true)
  {
    char op;
    cin >> op;
    if (op == '=')
    {
      break;
    }

    int m;
    cin >> m;

    if (op == '+')
    {
      n += m;
    }
    else if (op == '-')
    {
      n -= m;
    }
    else if (op == '*')
    {
      n *= m;
    }
    else
    {
      n /= m;
    }
  }

  printf("%d\n", n);
}



Measured memory_bytes: 3220
#include <bits/stdc++.h>
#define OP_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fo(i,a,b) for(int i = a; i < b; i++)
#define foi(i,a,b) for(int i = a; i>=b; i--)
#define fi first
#define si second
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const ll INF = 1e18L + 5;

int main(){
  OP_IO;
  int N,W;
  cin>>N>>W;
  vpii inp(N);
  ll sum_value = 0;
  fo(i,0,N){
    cin>>inp[i].fi>>inp[i].si;
    sum_value += inp[i].si;
  }
  vll dp(sum_value+1, INF);
  dp[0] = 0;
  fo(i,0,N){
    foi(j,sum_value,0){
      if(inp[i].si <= j){
	dp[j] = min(dp[j], inp[i].fi + dp[j-inp[i].si]);
      }
    }
  }
  ll answer = 0;
  fo(i, 0, sum_value+1){
    if(dp[i] <= W){
      answer = max(answer, (ll)i);
    }
  }
  cout<<answer<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,x) for(int i=0; i<x; i++)
using namespace std;
typedef long long ll;

int N;
vector<vector<pair<int,int>>>Graph(100000+2);
vector<int> ans;
vector<bool> flg(100002,false);

// v is parent
void dfs(int v,int sum){
  if(flg[v]) return;
  flg[v] = true;

  if(sum==0) ans[v]=0;
  else ans[v] = 1;

  for(auto e: Graph[v]){
    int nv = e.first;
    int val = e.second;
    if(v == nv) continue;

    dfs(nv, (sum+val)%2);

  }
}


int main(){
  cin>>N;
  ans.resize(N);
  rep(i,N-1){
    int u,v;
    ll w;
    cin>>u>>v>>w;
    u--,v--;
    Graph[u].push_back(make_pair(v,w%2));
    Graph[v].push_back(make_pair(u,w%2));

  }

  //rep(i,N) for(auto e:Graph[i] ) cout<<e.second<<endl;

  dfs(0,0);

  rep(i,N) cout<<ans[i]<<endl;
}


Measured memory_bytes: 8320
using System;
using System.Linq;
using System.Collections.Generic;

namespace cs
{
    class Program
    {
        static void Main(string[] args)
        {
            var pg = new Program();
            pg.Execute();

        }

        private void Execute()
        {
            var input = ReadLinesLongList;
            var A = input.ElementAt(0);
            var B = input.ElementAt(1);
            var C = input.ElementAt(2);
            var D = input.ElementAt(3);

            for (long i = 1; ; i++)
            {
                if (C - B * i <= 0)
                {
                    OutputResult("Yes");
                    return;
                }
                if (A - D * i <= 0)
                {
                    OutputResult("No");
                    return;
                }


            }
        }

        private void OutputResult<Type>(Type result)
        {
            Console.WriteLine(result);
        }

        static long ReadLineLong => long.Parse(Console.ReadLine());
        static string ReadLineString => Console.ReadLine();
        static IEnumerable<long> ReadLinesLongList => Console.ReadLine().Split(' ').Select(i => long.Parse(i));
        static IEnumerable<string> ReadLinesStringList => Console.ReadLine().Split(' ');

        public static int Gcd(int a, int b)
        {
            Func<int, int, int> gcd = null;
            gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
            return a > b ? gcd(a, b) : gcd(b, a);
        }

    }
}


Measured memory_bytes: 28188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    int N;cin >> N;cout << N*N*N << endl;
}

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

using namespace std;
using ll=long long;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;
const int MOD = 1000000007;

double dp[3000][3000]={0.0};

int main() {

int n; cin >> n;
double p[n];
for (int i = 1; i <= n; ++i)
{
    cin >> p[i];
}
dp[0][0] = 1.0;
for (int i = 0; i <n; ++i)
{
    for (int j = 0; j <=i ; ++j)
    {
        dp[i+1][j] += dp[i][j]*(1.0-p[i+1]);
        dp[i+1][j+1] += dp[i][j]*p[i+1];
    }
}
int div = (n+1)/2;
double sum = 0.0;
for (int i = div; i <=n ; ++i)
{
   sum += dp[n][i];
}

printf("%.10lf\n",sum );
return 0;
}




Measured memory_bytes: 68864
import math
A,B,H,M = [int(i) for i in input().split()]
angle_A = 30*H + M/2
angle_B = 6*M
angle = angle_A - angle_B
C = A**2 + B**2 - 2*A*B*math.cos(math.radians(angle))
print(math.sqrt(C))

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

struct Edge {int to, cost;};

int main() {
    int N; cin >> N;
    using P = pair<int, int>;
    vector<P> X(N), Y(N);
    rep(i, 0, N) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        X[i] = {x, i};
        Y[i] = {y, i};
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    vector<vector<Edge>> G(N);
    auto input = [&](vector<P> &V) {
        rep(i, 0, N - 1) {
            int f = V[i].second;
            int t = V[i + 1].second;
            int d = V[i + 1].first - V[i].first;
            G[f].push_back({t, d});
            G[t].push_back({f, d});
        }
    };
    input(X);
    input(Y);
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<int> visited(N);
    pq.push({0, 0});
    int ans = 0;
    while(!pq.empty()) {
        P t = pq.top(); pq.pop();
        int cur = t.second;
        int cost = t.first;
        if(visited[cur]) continue;
        visited[cur] = 1;
        ans += cost;
        for(auto &e : G[cur]) {
            if(visited[e.to]) continue;
            pq.push({e.cost, e.to});
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11384
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
signed main()
{
	string s;
	cin>>s;
	int ans=-1;
	for (int i=0;i<sz(s);i+=2){
		if (s.substr(0,i/2)==s.substr(i/2,i/2))  ans=i;
	}
	cout<<ans;
	re 0;
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectContest
{
    class Test
    {
        static void Main()
        {
            var v = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
            int a = v[0], b = v[1], c = v[2];
            Console.WriteLine(Math.Min(Math.Min(a, b) + c, a + b));
        }

    }
}

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

#define ll long long
#define int ll
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

#define dump(x)  cerr << #x << " = " << (x) << endl; 

typedef pair<int, int> P;
struct Point{
	int x, y;
};
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = {1,0,-1,0};


signed main(){

	int N;
	int a[100000], b[100000];
	int sum=0;

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

	if (sum % (N*(N + 1) / 2) != 0){
		cout << "NO" << endl;
		return 0;
	}
	int K = sum / (N*(N + 1) / 2);
	if (K == 0){
		cout << "NO" << endl;
		return 0;
	}

	// 0, -N, -2N, ...になってるか？
	int bsum = 0;
	for (int i = 0; i < N; i++){
		b[i] = a[(i+1)%N] - a[i] - K;
		bsum += b[i];
	}
	bool r=true;
	for (int i = 0; i < N; i++){
		if (b[i] % N != 0 || b[i]>0){
			r = false;
			break;
		}
	}
	if (bsum%K != 0)
		r = false;

	if (r) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


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

int main(){
  int n,l;
  cin >> n >> l;
  
  int a[n];
  int i, sum =0;
  for(i=0; i<n; i++){
    a[i] = i+l;
    sum += a[i];
  }
  
  int j,sumi = 0, min = 1000000,dif,res;
  for(i=0; i<n; i++){
    sumi = 0;
    for(j=0; j<n; j++){
      if(j != i)
        sumi += a[j];
    }
    dif = abs(sum - sumi);
    if(dif < min){
      min = dif;
      res = sumi;
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.PriorityQueue
import java.util.Collections

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map(String::toInt)
    val a = PriorityQueue<Long>(n, Collections.reverseOrder()).apply {
        readLine()!!.split(" ").forEach { add(it.toLong()) }
    }

    repeat(m) {
        a.run { add(poll() / 2) }
    }

    println(a.toList().sum())
}

Measured memory_bytes: 71776
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=1e9+7;
const int size=1e5;
const int inf=1e9;
int main(){
	int H,W,h,w; cin>>H>>W>>h>>w;
	if(H % h == 0 && W % w == 0) cout<<"No"<<endl;
	else{
		int a[H][W] = {};
		int s,t;
        if(h == 1){ s = W / w + 1; t = - s * (w - 1) - 1; }
        else if(w == 1){ s = H / h + 1; t = - s * (h - 1) - 1; }
        else{ s = (H / h) * (W / w) / min(H, W) + 1; t = - s * (h + w - 1) - 1; }
		for(int i = 0; i < H; i += h){
			rep(j,0,W) a[i][j] = s;
		}for(int j = 0; j < W; j += w){
            rep(i,0,H) a[i][j] = s;
        }
		for(int i = h-1; i < H; i += h){
			for(int j = w-1; j < W; j += w){
				a[i][j] = t;
			}
		}
		cout<<"Yes"<<endl;
		pprint(a,,H,W);
	}
}

Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll N=1e6+5,inf=1e18,mod=1e9+7;
#define test ll testcases;cin>>testcases; while(testcases--)
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll> 
#define pld pair<ld,ld> 
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define sz(x) ((ll)((x).size()))
const ld pi=3.141592653589793238;

bool check_prime(ll n)
{
	ll flag=0,i;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			flag=1;
			break;
		}
	}
	if(n==1)
	{
		return false;
	}
	else if(flag==0 || n==2 || n==3)
	{
		return true;
	}
	else
	{
		return false;
	}
}

ll fastexpo(ll a,ll b,ll MOD) 
{
	ll result=1;
	while(b>0)
	{
		if(b%2==1)
		{
			result=(result*a)%MOD;
		}
		a=(a*a)%MOD;
		b=b/2;
	}
	return result;
}

ll dp[100005];
ll w[105],v[105];
ll W,n;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll i,k,j;
    cin>>n>>W;
    for(i=0;i<n;i++)
    {
    	cin>>w[i]>>v[i];
    }
   	for(j=0;j<100005;j++)
   	{
   		dp[j]=inf;
    }
    dp[0]=0;
    for(i=0;i<n;i++)
    {
    	for(j=100004;j>=v[i];j--)
    	{
    		dp[j]=min(dp[j-v[i]]+w[i],dp[j]);
    	}
    }
    for(i=100004;i>=0;i--)
    {
    	if(dp[i]<=W)
    	{
    		k=i;
    		break;
    	}
    }
    cout<<k<<"\n";
	return 0;
}

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

const int INF = 1 << 30;

int main() {
  int n;
	string s;
	cin >> n >> s;
	vector<int> wh(n + 1), bl(n + 1);
	for (int i = 0; i < n; i++) {
		wh[i + 1] = wh[i] + (s[i] == '.' ? 1 : 0);
		bl[i + 1] = bl[i] + (s[i] == '#' ? 1 : 0);
	}
	int ans = INF;
	for (int i = 0; i <= n; i++) {
		ans = min(ans, bl[i] - bl[0] + wh[n] - wh[i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 5208
// Zhupengfei 2018
// This program / source file is in public domain.

// Solution for problem: Tak And Hotels (Take 3)

#include <bits/stdc++.h>

using namespace std;

// Main segment

int d[100001][18] = {};
int x[100001] = {};

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

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> x[i];
    }
    int L;
    cin >> L;
    for (int i = 1; i <= N; i++) {
        d[i][1] = upper_bound(x + i, x + N + 1, x[i] + L) - x - 1;
    }
    for (int k = 2; k <= 18; k++) {
        for (int i = 1; i <= N; i++) {
            d[i][k] = d[d[i][k - 1]][k - 1];
        }
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        int cnt = 0;
        for (int i = 18; i >= 1; i--) {
            if (d[a][i] < b) {
                a = d[a][i];
                cnt += (1 << (i - 1));
            }
        }
        if (a != b) {
            cnt++;
        }
        cout << cnt << endl;
    }

#ifdef LOCAL
    system("pause");
#endif
    return 0;
}


Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
#define debug(...) { printf("#  "); printf(__VA_ARGS__); puts(""); }
#define fi first
#define se second
#define endl "\n" 
using ll = long long;
using pII = pair <int, int>;
using pLL = pair <ll, ll>;
using VI = vector <int>;
using VL = vector <ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; } 
template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }
template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }
inline int rd() { int x; cin >> x; return x; }
template <class T> inline void rd(T &x) { cin >> x; }
template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }
template <class T> inline void out(T s) { cout << s << "\n"; }
template <class T> inline void out(vector <T> &vec) { for (auto &it : vec) cout << it << endl; } 
inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }
constexpr int N = 1e5 + 10;
int n, m;
vector <vector<int>> G;
int sta[N], vis[N], use[N], d_in[N], d_out[N];
bool Insta[N];
void check(vector <int> &vec) {
	for (auto &it : vec) d_in[it] = d_out[it] = 0, use[it] = 1;
	for (auto &u : vec) {
		for (auto &v : G[u]) {
			if (use[v]) 
				++d_out[u], ++d_in[v];
		}
	}
	for (auto &u : vec) if (d_in[u] != 1 || d_out[u] != 1) {
		for (auto &it : vec) use[it] = 0;
		return;
	}
	out(vec.size()); out(vec);
	exit(0);
}
void Tarjan(int u) {
	vis[u] = 1;
	sta[++*sta] = u;
	Insta[u] = true;
	for (auto &v : G[u]) { 
		if (!Insta[v]) {
			Tarjan(v);
		} else {
			vector <int> vec;
			for (int i = *sta; i >= 1; --i) {
				vec.push_back(sta[i]);
				if (sta[i] == v) break;
			}
			check(vec);
		}
	}
	(*sta)--;
	Insta[u] = false; 
}


void run() {
	G.clear(); G.resize(n + 1);
	for (int i = 1, u, v; i <= m; ++i) {
		cin >> u >> v;
		G[u].push_back(v);
	}
	memset(vis, 0, sizeof vis);
	memset(use, 0, sizeof use);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			*sta = 0;
			Tarjan(i);
		}
	}
	out(-1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cout << fixed << setprecision(20);
	while (cin >> n >> m) run();
	return 0;
}


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

int main() {
	int c[3][3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++)
			cin >> c[i][j];
	}

	bool exist = true;
	for (int j = 0; j<2; j++) {
		for (int i = 0; i < 2; i++) {
			int dif = c[i][j] - c[i][j + 1];
			int dif2 = c[i + 1][j] - c[i + 1][j + 1];
			if (dif != dif2) exist = false;
		}
	}
	for (int j = 0; j<2; j++) {
		for (int i = 0; i < 2; i++) {
			int dif = c[i][j] - c[i + 1][j];
			int dif2 = c[i][j + 1] - c[i + 1][j + 1];
			if (dif != dif2) exist = false;
		}
	}
	if (exist) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	//system("pause");
	return 0;
}


Measured memory_bytes: 256
d,g=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(d)]

ans=1000

for b in range(1<<d):
  s=0
  cnt=0
  for i in range(d):
    if b&(1<<i):
      s+=l[i][0]*(i+1)*100+l[i][1]
      cnt+=l[i][0]
  for i in range(d-1,-1,-1):
    if not b&(1<<i):
      for j in range(1,l[i][0]):
        if s<g:
          s+=(i+1)*100
          cnt+=1
  if s>=g:
    ans=min(ans,cnt)
print(ans)

Measured memory_bytes: 43376
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

ll gcd(ll a, ll b);
ll power(ll n, ll k);
ll inv(ll n);
ll genfact(ll n, ll k);
ll fact(ll n);
ll nck(ll n, ll k);

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

  int res = 0;
  for (int i = 1; i < n; i++){
    if (s[i] == 'E')
      res++;
  }
  int t = res;
  for (int i = 1; i < n; i++){
    t += (s[i] == 'E' ? -1 : 0) + (s[i-1] == 'W' ? 1 : 0);
    res = min(res, t);
  }

  cout << res << endl;

  return 0;
}

ll gcd(ll a, ll b){
  if (a < b)
    return gcd(b, a);
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

ll power(ll n, ll k){
  ll res = 1;
  while(k > 0){
    if (k & 1) 
      res = res * n % MOD;
    n = n * n % MOD;
    k >>= 1;
  }
  return res;
}

ll genfact(ll n, ll k){

  ll res = 1;
  while (k >= 0){
    res = (res * (n - k)) % MOD;
    k--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}

ll fact(ll n){
  return genfact(n, n - 1);
}

ll nck(ll n, ll k){
  if (k == 0)
    return 1;
  if (n <= 0)
    return 0;

  return ((genfact(n, k) % MOD) * inv(fact(k))) % MOD;
}


Measured memory_bytes: 900
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }

int n;
vvec G;
vec c;
vec ans;
int idx=0;
void dfs(int pre,int now){
    ans[now]=c[idx]; idx++;
    for(auto next:G[now]){
        if(pre==next) continue;
        dfs(now,next);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    cin>>n;
    G.resize(n);
    c.resize(n);
    ans.resize(n,0);
    rep(i,n-1){
        int a,b;cin>>a>>b;a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    rep(i,n) cin>>c[i];
    sort(rall(c));
    dfs(-1,0);
    ll sum=0;
    rep(i,n){
        sum+=c[i];
    }
    cout<<sum-c[0]<<endl;
    rep(i,n){
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 1536