akhauriyash/Code-Regression huggingface dataset:
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System;
using static System.Console;
class E { static void Main() => new J(); }
class J
{
	public const int Inf = 1073741789;
	int[] G() => ReadLine().Split().Select(int.Parse).ToArray();
	public J()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	void Solve() => WriteLine(string.Join(" ", Calc()));
	List<int> Calc()
	{
		var N = G()[0];
		var a = G();
		var rev = new int[N];
		for (var i = 0; i < N; i++) rev[--a[i]] = i;
		var par = new[] { new RMQ(a, 0), new RMQ(a, 1) };
		var que = new PriorityQueue();
		var dict = new Dictionary<int, P>();
		Action<P> add = p =>
		{
			if (p.r - p.l > 1)
			{
				var z = par[p.l & 1].Min(p);
				dict[z] = p; que.Enqueue(z);
			}
		};
		add(new P(0, N));
		var list = new List<int>();
		while (que.Count > 0)
		{
			int x = que.Dequeue(), i = rev[x];
			var p = dict[x];
			int f = p.l & 1, y = par[1 - f].Min(i + 1, p.r), j = rev[y];
			//yield return x + 1;
			//yield return y + 1;
			list.Add(x + 1);
			list.Add(y + 1);
			add(new P(p.l, i));
			add(new P(i + 1, j));
			add(new P(j + 1, p.r));
		}
		return list;
	}
}
struct P
{
	public readonly int l, r;
	public P(int x, int y) { l = x; r = y; }
}
class RMQ
{
	readonly int N2;
	readonly int[] seg;
	public RMQ(int[] a, int f)
	{
		var N = a.Length;
		N2 = 1;
		while (N2 < N) N2 <<= 1;
		seg = new int[2 * N2 - 1];
		for (var i = 0; i < 2 * N2 - 1; i++) seg[i] = J.Inf;
		for (var i = f; i < N; i += 2) seg[i + N2 - 1] = a[i];
		for (var i = N2 - 2; i >= 0; i--) seg[i] = Math.Min(seg[2 * i + 1], seg[2 * i + 2]);
	}
	public int Min(P p) => Min(p.l, p.r);
	public int Min(int from, int to) => Min(from, to, 0, 0, N2);
	int Min(int from, int to, int node, int l, int r)
	{
		if (to <= l || r <= from) return J.Inf;
		else if (from <= l && r <= to) return seg[node];
		else return Math.Min(Min(from, to, 2 * node + 1, l, (l + r) >> 1), Min(from, to, 2 * node + 2, (l + r) >> 1, r));
	}
}
class PriorityQueue
{
	readonly List<int> list = new List<int>();
	public int Count { get; private set; } = 0;
	public void Enqueue(int x)
	{
		var pos = Count++;
		list.Add(x);
		while (pos > 0)
		{
			var p = (pos - 1) / 2;
			if (list[p] <= x) break;
			list[pos] = list[p];
			pos = p;
		}
		list[pos] = x;
	}
	public int Dequeue()
	{
		var value = list[0];
		var x = list[--Count];
		list.RemoveAt(Count);
		if (Count == 0) return value;
		var pos = 0;
		while (pos * 2 + 1 < Count)
		{
			var a = 2 * pos + 1;
			var b = 2 * pos + 2;
			if (b < Count && list[b] < list[a]) a = b;
			if (list[a] >= x) break;
			list[pos] = list[a];
			pos = a;
		}
		list[pos] = x;
		return value;
	}
}

Measured memory_bytes: 47824
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

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

int M[22][22], B[22];
class BCanYouSolveThis {
 public:
  void solve(std::istream &in, std::ostream &out) {
      int n, m, c;
      in >> n >> m >> c;
      forn(i, m)in >> B[i];

      forn(i, n)forn(j, m)in >> M[i][j];

      int ans = 0;

      for (int i = 0; i < n; ++i) {
          int s = c;
          for (int j = 0; j < m; ++j)
              s += B[j] * M[i][j];
          if (s > 0)
              ans++;

      }
      out << ans << '\n';
  }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    BCanYouSolveThis solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}

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

int main() {
    char S[4];
    cin >> S;

    long cnt1 = 1;
    long cnt2 = 1;

    for (long i = 1; i < 4; i++) {
        if (S[i] == S[0]) {
            cnt1++;
        }
    }
    if (cnt1 == 2) {
        char S2;
        long i2;
        for (long i = 1; i < 4; i++) {
            if (S[i] != S[i - 1]) {
                S2 = S[i];
                i2 = i;
                break;
            }
        }
        for (long i = 1; i < 4; i++) {
            if (i == i2) {
                continue;
            }
            if (S2 == S[i]) {
                cnt2++;
            }
        }
    }

    // cout << cnt1 << " " << cnt2 << endl;

    if (cnt1 == 2 && cnt2 == 2) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define pri 10000000007
using namespace std;
void run(){
	ll n;
	cin>>n;
	ll hi=0,ans=0;
	for(ll i=0;i<n;i++){
		ll h;
		cin>>h;
	   if(h>=hi){hi=h;ans++;}
		
	}
	cout<<ans<<endl;
	
	
	
}
int main() {
	
	ll t=1;
	//cin>>t;
	for(ll i=0;i<t;i++)run();
	
	// your code goes here
	return 0;
}

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

using namespace std;
using ll = long long int;

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    cout << fixed << setprecision(16);

    ll n;
    cin >> n;
    vector<pair<ll,ll>> p(n);
    for(ll i=0; i<n; i++)
        cin >> p[i].first, p[i].second = i;
    sort(p.begin(), p.end(), greater<>());

    set<ll> pos, sop;
    pos.insert(n);
    sop.insert(1);

    ll res = 0;
    for(ll i=0; i<n; i++) {
        ll t, j;
        tie(t, j) = p[i];
        ll r = *pos.upper_bound(j);
        ll rr = r == n ? n : *pos.upper_bound(r);
        ll l = -*sop.upper_bound(-j);
        ll ll = l == -1 ? -1 : -*sop.upper_bound(-l);
        res += t * ((l - ll) * (r - j) + (rr - r) * (j - l));

        pos.insert(j);
        sop.insert(-j);
    }
    cout << res << endl;
}


Measured memory_bytes: 11136
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CS_AtCoder {
	class Program {
		static void Main(string[] args) {
			new Calc().Solve();
		}
	}
	public class Calc {
		public Calc() { }
		public void Solve() {
			S = Console.ReadLine();
			search(0, 0, 0);
			result.WL();
			return;
		}
		string S;
		long result = 0;
		private void search(long current,int index,long sum) {
			if (index == S.Length-1) {
				current = current * 10 + S[index] - '0';
				sum += current;
				result += sum;
				return;
			}
			current = current * 10 + S[index] - '0';
			search(current, index + 1, sum);
			search(0, index + 1, sum + current);
		}
	}
	public static class Utils {
		public static int ReadInt() => int.Parse(Console.ReadLine());
		public static void WL(this object obj) {
			Console.WriteLine(obj);
		}
	}
}


Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  if (std::abs(a-c) <= d) {
    cout << "Yes" << endl;
  } else if (std::abs(a-b) <= d && std::abs(b-c) <= d) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
bool linearSearch(int A[], int n, int key){
  int i = 0;
  A[n] = key;
  while (A[i] != key) i++;
  return i != n ? true : false;
}

int main() {
  int i, n, q, key, sum = 0;
  cin >> n;
  int A[n + 1];
  for (i = 0; i < n; i++){
    cin >> A[i];
  }
  cin >> q;
  for (i = 0; i < q; i++){
    cin >> key;
    if(linearSearch(A, n, key)) sum++;
  }
  cout << sum << endl;
}


Measured memory_bytes: 3124
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <cassert>//assert();
#include <fstream>
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)

/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#define PII pair<int,int>
/////////
using namespace::std;

// 最大公約数
template<class T>
inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}
// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a * b / gcd(a, b);}
////////////////////////////////

inline void solve(){
	string str;
	cin >> str;
	int size = str.size();
	int A,Z;
	for(int i=0;i<size;++i){
		if( str[i] == 'A' ){
			A = i;break;
		}
	}
	for(int i=size-1;i>=0;--i){
		if( str[i] == 'Z' ){
			Z = i;break;
		}
	}
	cout << Z-A+1;
}

int main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数をいっぱい表示する。16?

	solve();

	return 0;
}


Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long
#define pb push_back
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define inp(n) for(i=0;i<n;i++) cin>>A[i];
#define inz(A,x) memset(A,x,sizeof(A))
#define lb lower_bound
#define ub upper_bound
#define all(v) v.begin(),v.end()
#define T 1000000
#define F first
#define S second
#define pi pair<int,int>
#define vi vector<int>v;
#define sz(v) v.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
			/*brownsands IIITA*/

signed main(){
  		
                boost
         int n,k;
		cin>>n>>k;
  int A[n+10],dp[n+10];
   inz(A,0);inz(dp,5);
  		for(int i=0;i<n;i++)
          cin>>A[i];
  dp[0]=0;
  		for(int i=0;i<n-1;i++){
          for(int j=i+1;j<=i+k;j++){
          
            if(j<n)
              dp[j]=min(dp[j],dp[i]+abs(A[i]-A[j]));
          // cout<<A[i]<<" "<<A[j]<<endl;
          }}
  cout<<dp[n-1];

            
			}
 

				
		
		





Measured memory_bytes: 1792
n = int(input())
ac = 0
wa = 0
tle = 0
re = 0
for _ in range(n):
    i = input()
    if i == 'AC':
        ac += 1
    elif i == 'WA':
        wa += 1
    elif i == 'TLE':
        tle += 1
    elif i == 'RE':
        re += 1

print('AC x ' + str(ac))
print('WA x ' + str(wa))
print('TLE x ' + str(tle))
print('RE x ' + str(re))


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

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

    int A, B, N;
    string S;
    cin >> N >> A >> B >> S;
    int AB = A+B;
    rep(i, N){
        string res = "No";
        if(S[i] == 'a'){
            if (AB > 0) {
                res = "Yes";
                AB -= 1;
            }
        }
        else if(S[i] == 'b'){
            if (AB > 0 && B > 0){
                res = "Yes";
                AB -= 1;
                B -= 1;
            }
        }
        cout << res << endl;
    } 
}

Measured memory_bytes: 848
#define _USE_MATH_DEFINES

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <numeric>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

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

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

    string s;
    cin >> s;
    int l = 0, r = (int)s.size(), cnt = 0;
    while(l < r){
        if (s[l] == s[r - 1]){
            ++l, --r;
        }else if (s[l] == 'x'){
            ++l;
            ++cnt;
        }else if (s[r - 1] == 'x'){
            --r;
            ++cnt;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 512
#ABC088 d Grid Repainting 
from collections import deque 

def bfs():
    d = [[float('inf')]*w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w and maze[nx][ny] != '#' and d[nx][ny] == float('inf'):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return d[gx][gy]

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
sx, sy = 0, 0
gx, gy = h-1, w-1
white = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            white += 1
res = bfs()
if 0 < res < float('inf'):
    print(white - res - 1)
else :
    print(-1)

Measured memory_bytes: 9448
#include <stdio.h>

#define MAX 4

int main()
{
	char s[MAX+1];
	int flag=0;

	scanf("%s",s);

	for(int i=0; i<MAX-1;i++){
		if(s[i]==s[i+1])
			flag=1;
	}

	if(flag==0)
		printf("Good\n");
	else
		printf("Bad\n");
}

Measured memory_bytes: 128
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll INF = 1e18;

V vec;
ll n, k;
bool judge(ll x)
{
    ll cnt = 0;
    ll prev = x;
    while (1)
    {
        ll f = lower_bound(all(vec), prev) - vec.begin();
        if (f == n)
            break;
        cnt++;
        prev = vec[f];
    }
    return cnt <= k;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, w;
    cin >> n >> w;
    VV dp(n + 1, V(1e6,1e18));
    dp[0][0]=0;
    VP vec(n);
    rep(i, n) cin >> vec[i].F >> vec[i].S;
   // cout<<vec[0].S<<endl;
  //  cout<<dp[n][1e5]<<endl;
    rep(i,n){
        rep(j,1e5+1){
            chmin(dp[i + 1][j], dp[i][j]);
            chmin(dp[i+1][j + vec[i].S], dp[i][j] + vec[i].F);
        }
    }
  //  cout<<dp[3][1e5]<<endl;
    for (int i = 1e5; i >= 0;i--){
        if(dp[n][i]<=w){
         //   cout<<n<<" "<<i<<endl;
           // cout<<dp[3][1000000]<<endl;
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 797524
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		int left = a + b;
		int right = c + d;

		if (left > right) {
			System.out.println("Left");
		} else if (left == right){
			System.out.println("Balanced");
		} else {
			System.out.println("Right");
		}
	}
}


Measured memory_bytes: 23252
import java.util.Scanner;

class Main{

    static void print(String[] s){
        for(int i = 0; i < s.length; i++){
            System.out.print((i == 0 ? "" : " ") + s[i]);
        }
        System.out.println();
    }

    static boolean isSame(String[] a, String[] b){
        for(int i = 0; i < a.length; i++){
            if(!a[i].equals(b[i]))  return false;
        }
        return true;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());
        String[] array = sc.nextLine().split(" ");

        sc.close();

        String[] arrayB = array.clone();
        String[] arrayS = array.clone();

        int k = 0;
        while(k < n-1){
            for(int i = n-1; i > k; i--){
                if((int)(arrayB[i].charAt(1)) < (int)(arrayB[i-1].charAt(1))){
                    String tmp = arrayB[i];
                    arrayB[i] = arrayB[i-1];
                    arrayB[i-1] = tmp;
                }
            }
            k++;
        }

        print(arrayB);
        System.out.println("Stable");

        for(int i = 0; i < n; i++){
            int minj = i;
            for(int j = i; j < n; j++){
                if((int)(arrayS[j].charAt(1)) < (int)(arrayS[minj].charAt(1))){
                    minj = j;
                }
            }
            if(i != minj){
                String tmp = arrayS[i];
                arrayS[i] = arrayS[minj];
                arrayS[minj] = tmp;
            }
        }

        print(arrayS);
        if(isSame(arrayS,arrayB)){
            System.out.println("Stable");
        }else{
            System.out.println("Not stable");
        }
        
    }
}



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

int main() {
  int n, m, c; cin >> n >> m >> c;
  int a[m], b[m];
  for(int i = 0; i < m; i++) cin >> b[i];
  int counter = 0;
  for(int i = 0; i < n; i++) {
    int sum = c;
    for(int j = 0; j < m; j++) {
      cin >> a[j];
      sum += a[j] * b[j];
    }
    if(sum > 0) counter++;
  }
  cout << counter << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define MAX 99

int main(){
 char str[MAX];
 int len;
 scanf("%s", str);
 len = strlen(str);
 for(int i=0; i < len/2 ;i++){
	int last = len-1-i;
 	int mid = len/2 - i -1;
 	if(str[i] != str[last] || str[i] != str[mid]){
    	printf("No\n");
        break;
    }else if(i == len/2 -1 ){
    	printf("Yes\n");
    }
 }

 return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstring>
#include<string>
#include <queue>
#include <set>
using namespace std;
#define maxn 100005
struct box{
    bool red;
    int cnt;
}boxs[maxn];

int main(){
    int n,m,x,y;
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        boxs[i].red = 0;
        boxs[i].cnt = 1;
    }
    boxs[1].red = 1;
    while(m--){
        getchar();
        cin >> x >>y;
        if(boxs[x].red == 1)
            boxs[y].red = 1;
        boxs[x].cnt --;
        boxs[y].cnt ++;
        if(boxs[x].cnt == 0) boxs[x].red = 0;
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(boxs[i].red) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

import java.util.ArrayList;
import java.util.List;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		int[] flag = new int[26];
		String str = "";
		Scanner scan = new Scanner(System.in);
		String W = scan.nextLine();
		W = W.toLowerCase();
		try{
		while (scan.hasNextLine()) {
			String tmp = "";
			tmp = scan.nextLine();
				str = str + tmp.toLowerCase() + " ";
				if(tmp.length() == 0){
					break;
				}
		}
	}finally{
	}
		int cnt = 0;
		String[] s = str.split(" ");

		for (int i = 0; i < s.length;i++) {
			if(W.equals(s[i])){
				// System.out.println(s[i] +","+i);
				cnt++;
			}
		}

			System.out.println(cnt);
	}

}



Measured memory_bytes: 26200
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF = 0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a, LL b) {LL s = 1; while (b > 0) {if (b & 1)s = s * a % mod; a = a * a % mod; b >>= 1;} return s;}
LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
int dr[2][4] = {1, -1, 0, 0, 0, 0, -1, 1};
typedef pair<int, int> P;
const int maxn = 1e5 + 10;
char ar[maxn];
int main(void)
{
	int N, K;
	cin >> N >> K;
	cin >> (ar + 1);
	int cnt = 0;
	for (int i = 1; i <= N; ++i) {
		if (ar[i] != ar[i - 1])
			cnt++;
	}
	cout << min(N - 1, N - cnt + 2 * K) << endl;

	return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;

namespace atCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] temp = Console.ReadLine().Split(' ');
            int h = int.Parse(temp[0]);
            int w = int.Parse(temp[1]);
            List<List<char>> list = new List<List<char>>();
            List<char> add = new List<char>();

            for (int i = 0; i < w + 2; i++)
            {
                add.Add('.');
            }

            list.Add(add);

            for (int i = 0; i < h; i++)
            {
                List<char> cl = new List<char>();

                cl.Add('.');

                foreach (char c in Console.ReadLine().ToCharArray())
                {
                    cl.Add(c);
                }

                cl.Add('.');

                list.Add(cl);
            }

            list.Add(add);

            List<List<char>> result = new List<List<char>>();

            for (int i = 1; i <= h; i++)
            {
                result.Add(new List<char>(list[i]));

                for (int j = 1; j <= w; j++)
                {
                    int count = 0;
                    char c = list[i][j];

                    if (c == '#') continue;

                    if (list[i - 1][j - 1] == '#') count++;
                    if (list[i - 1][j] == '#') count++;
                    if (list[i - 1][j + 1] == '#') count++;
                    if (list[i][j - 1] == '#') count++;
                    if (list[i][j + 1] == '#') count++;
                    if (list[i + 1][j - 1] == '#') count++;
                    if (list[i + 1][j] == '#') count++;
                    if (list[i + 1][j + 1] == '#') count++;

                    result[i - 1][j] = char.Parse(count.ToString());
                }
            }

            for (int i = 0; i < h; i++)
            {
                string s = string.Empty;

                for (int j = 1; j <= w; j++)
                {
                    s += result[i][j];
                }
                
                Console.WriteLine(s);
            }
        }
    }
}


Measured memory_bytes: 11220
a,b,m = map(int,input().split())
price_a = list(map(int,input().split()))
price_b = list(map(int,input().split()))

minPrice = min(price_a) + min(price_b)

for i in range(m):
	x,y,c = map(int,input().split())
	price = price_a[x-1] + price_b[y-1] -c
	if price < minPrice:
		minPrice = price

print(minPrice)

Measured memory_bytes: 97548
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<unordered_map>
#include<climits>
#include<fstream>
#include<time.h>
#include<cassert>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(),(a).end()
#define EPS (1e-13)
#define bit(n,k) ((n>>k)&1)
const ll Mod = 1e9 + 7;
const ll mod = 998244353;
struct H {
	ll x, y;
	bool operator<(const H& b) const {
		if (x != b.x) return x < b.x;
		return y < b.y;
	}
	bool operator>(const H& b) const {
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
	bool operator==(const H& b) const { return x == b.x && y == b.y; }
	bool operator!=(const H& b) const { return (*this) != b; }
};
struct P {
	ll pos, cost;
	bool operator<(const P& b) const { return cost < b.cost; }
	bool operator>(const P& b) const { return cost > b.cost; }
};
struct B {
	ll to, cost;
};
struct E {
	ll from, to, cost;
	bool operator<(const E& b) const { return cost < b.cost; }
	bool operator>(const E& b) const { return cost > b.cost; }
};
template<typename T, typename U>
void chmin(T& a, U b) {
	if (a > b) a = b;
}
template<typename T, typename U>
void chmax(T& a, U b) {
	if (a < b) a = b;
}
template<typename T>
T max_0(T a) {
	if (a < 0) return 0;
	return a;
}
template<typename T>
T min_0(T a) {
	if (a > 0) return 0;
	return a;
}
ll read() {
	ll u;
	ll k = scanf("%lld", &u);
	return u;
}
ll gcd(ll i, ll j) {
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcd(j % i, i);
}
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x % p;
		x = x * x % p;
		n >>= 1;
	}
	return res;
}//x^n%p
ll bitcount(ll x) {
	int sum = 0;
	for (int i = 0; i < 20; i++)
		if ((1ll << i) & x) sum++;
	return sum;
}
/*ll fact_[200000];
ll comb(ll x, ll y, ll mod = Mod) {
	if (!fact_[0]) {
		fact_[0] = 1;
		for (int i = 1; i < 200000; i++) {
			fact_[i] = fact_[i - 1] * i % mod;
		}
	}
	if (x < y) return 0;
	return mod_pow(fact_[x], mod, mod) *
		mod_pow(fact_[x - y], mod - 2, mod) % mod *
		mod_pow(fact_[y], mod - 2, mod) % mod;
}//xCy*/
const ll Inf = 3023372036854775807;
const int inf = 1500000000;
#define int long long
//----------------------------------------------------
int n;
ld a[200];
signed main() {
	cin >> n;
	priority_queue<ld, vector<ld>, greater<ld>>p;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		p.push(a[i]);
	}
	while (p.size() > 1) {
		ld a = p.top(); p.pop();
		ld b = p.top(); p.pop();
		p.push((a + b) / 2);
	}
	printf("%.20LF\n", p.top());
}

Measured memory_bytes: 256
n, m = map(int, input().split())
l_max = 0
r_min = 10**5 + 1
for i in range(m):
  l, r = map(int, input().split())
  l_max = max(l_max, l)
  r_min = min(r_min, r)
print(max(r_min- l_max + 1, 0))


Measured memory_bytes: 45160
def dfs(n, s, types):
    if(n==1):
        for i in range(types):
            c = chr(97+i)
            print(s+c)
    else:
        for i in range(types):
            c = chr(97+i)
            if(i==types-1):
                dfs(n-1, s+c, types+1)
            else:
                dfs(n-1, s+c, types)

N = int(input())
dfs(N, '', 1)


Measured memory_bytes: 4340
import java.util.*;
public class Main{
	public static void main(String[]$){
		Scanner s=new Scanner(System.in);
		long k=s.nextInt(),a=s.nextInt(),b=s.nextInt(),c=k-a+1;
		System.out.println(Math.max(k+1,a+c/2*(b-a)+c%2));
	}
}

Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
using namespace std;
template<class T, class Compare = less<T> >
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template<class T, class Compare = greater<T> >
using MinHeap = priority_queue<T, vector<T>, Compare>;
using llong = long long;

namespace std {
    template <>
    class hash<tuple<llong, llong, llong> > {
    public:
        size_t operator()(const tuple<llong, llong, llong> &x) const {
            return hash<llong>()(get<0>(x)) ^ hash<llong>()(get<1>(x)) ^ hash<llong>()(get<2>(x));
        }
    };
}

llong n;
string str;

llong base[3] = {101, 117, 107};
llong basep[3][100005];
llong hsh[3][100005];
const llong mod = (llong)(1e9) + 7;

void build() {
    basep[0][0] = basep[1][0] = basep[2][0] = 1;

    for (int i = 0; i < 100003; i++) {
        basep[0][i + 1] = basep[0][i] * base[0] % mod;
        basep[1][i + 1] = basep[1][i] * base[1] % mod;
        basep[2][i + 1] = basep[2][i] * base[2] % mod;
    }

    for (int i = 0; i < str.size(); i++) {
        hsh[0][i + 1] = hsh[1][i + 1] = hsh[2][i + 1] = str[i];
    }

    for (int k = 0; k < 3; k++) {
        for (int i = 1; i < str.size(); i++) {
            hsh[k][i + 1] += hsh[k][i] * base[k] % mod;
            hsh[k][i + 1] %= mod;
        }
    }
}

tuple<llong, llong, llong> geth(llong l, llong r) {
    llong v1 = ((hsh[0][r] - hsh[0][l]*basep[0][r - l])%mod+mod)%mod;
    llong v2 = ((hsh[1][r] - hsh[1][l]*basep[1][r - l])%mod+mod)%mod;
    llong v3 = ((hsh[2][r] - hsh[2][l]*basep[2][r - l])%mod+mod)%mod;

    return make_tuple(v1, v2, v3);
}

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

    build();
    
    for (llong len = n / 2; len >= 1; len--) {
        unordered_map<tuple<llong, llong, llong>, llong> cnt;
        for (llong s = 0; s + len <= n; s++) {
            tuple<llong, llong, llong> idx = geth(s, s + len);
            
            llong t = cnt[idx];
            if (t > 0) {
                if (s >= t) {
                    cout << len << endl;
                    return 0;
                }
            }
            else {
                cnt[idx] = s + len;
            }
        }
    }

    cout << 0 << endl;

    return 0;
}


Measured memory_bytes: 3512
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n, m = sc.nextInt
    val xs = new Array[Int](m)
    for (i <- 0 until m) {
      xs(i) = sc.nextInt
    }

    val sortedXs = xs.sorted
    val diffs = new Array[Int](m - 1)
    for (i <- 0 until m - 1) {
      diffs(i) = sortedXs(i + 1) - sortedXs(i)
    }
    val ans = diffs.sorted.slice(0, diffs.length - (n - 1)).sum
    println(ans)

  }
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

int N;
int S[111111];

signed main(){
	cin>>N;
	rep(i,N)cin>>S[i];

	int ans=0;
	for(int D=1;D<N;D++){
		if((N-1)%D==0){
			int s=0;
			for(int j=1;j*D<N-1-j*D;j++){
				s+=S[j*D]+S[N-1-j*D];
				chmax(ans,s);
			}
		}
		else{
			int s=0;
			for(int j=1;j*D<N&&N-1-j*D>D;j++){

				s+=S[j*D]+S[N-1-j*D];
				chmax(ans,s);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cassert>
#include <functional>
#include <string>
#include <sstream>
#include <cctype>
using namespace std;


int main(){
  int N; cin >> N;
  int min = 1000, max = 0;
  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    if(tmp < min) min = tmp;
    if(tmp > max) max = tmp;
  }
  cout << max - min << endl;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  i64 c;
  cin >> n >> c;
  vi64 x(n), v(n);
  rep(i, n) {
    cin >> x[i] >> v[i];
  }
  vi64 suml(n + 1);
  vi64 sumr(n + 1);
  rep(i, n) {
    suml[i + 1] = suml[i] + v[i];
    if (i == 0) {
      suml[i + 1] -= x[i];
    } else {
      suml[i + 1] -= x[i] - x[i - 1];
    }
  }
  rreps(i, n) {
    sumr[i - 1] = sumr[i] + v[i - 1];
    if (i == n) {
      sumr[i - 1] -= c - x[i - 1];
    } else {
      sumr[i - 1] -= x[i] - x[i - 1];
    }
  }
  vi64 maxl(n + 1);
  vi64 maxr(n + 1);
  rep(i, n) {
    amax(maxl[i + 1], max(maxl[i], suml[i + 1]));
  }
  rreps(i, n) {
    amax(maxr[i - 1], max(maxr[i], sumr[i - 1]));
  }
  i64 ans = 0;
  repc(i, n) {
    i64 sum = 0;
    if (i > 0) {
      sum += suml[i];
      sum -= x[i - 1];
    }
    sum += maxr[i];
    amax(ans, sum);
  }
  rrepc(i, n) {
    i64 sum = 0;
    if (i < n) {
      sum += sumr[i];
      sum -= c - x[i];
    }
    sum += maxl[i];
    amax(ans, sum);
  }
  cout << ans << endl;
}

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

int main(){
  int n,a,b; cin>>n>>a>>b;
  long long min_v=(long long)a*(n-1)+b;
  long long max_v=(long long)b*(n-1)+a;
  cout<<(max_v-min_v+1>=0 ? max_v-min_v+1:0)<<endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	int A, B;
	cin >> A >> B;

	if (abs(A - B) & 1) cout << "IMPOSSIBLE" << endl;
	else cout << (A + B) / 2 << endl;
}

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

using namespace std;

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define REP3(i, m, n) for(int i = m, i##_len=(n);i < i##_len;i++)
#define FORVEC(i, v) for(int i = 0;i < v.size();i++)

#define INF 1000000000
#define pb(a) push_back(a)
#define llong long long

int main(){
	int n,k;
	cin>>n>>k;
	int now=1;
	REP(i,n){
		if(now<k){
			now*=2;
		}else{
			now+=k;
		}
	}
	cout<<now<<"\n";
	return 0;
}

Measured memory_bytes: 256
from scipy.optimize import fmin

N = int(input())

INF = 10 ** 18

X, Y = [[],[],[]], [[],[],[]]
for _ in range(N):
    x, y, d = input().split()
    x, y = int(x), int(y)

    if d == "R":
        X[0].append(x)
    elif d == "L":
        X[1].append(x)
    else:
        X[2].append(x)

    if d == "U":
        Y[0].append(y)
    elif d == "D":
        Y[1].append(y)
    else:
        Y[2].append(y)

for i in range(3):
    X[i] = [min(X[i] + [INF]), max(X[i] + [-INF])]
    Y[i] = [min(Y[i] + [INF]), max(Y[i] + [-INF])]

def calc_area(t):
    if t < 0:
        return INF

    x_l, x_r = INF, -INF
    x_l, x_r = min(x_l, X[0][0] + i*t), max(x_r, X[0][1] + i*t)
    x_l, x_r = min(x_l, X[1][0] - i*t), max(x_r, X[1][1] - i*t)
    x_l, x_r = min(x_l, X[2][0]      ), max(x_r, X[2][1]      )

    y_l, y_r = INF, -INF
    y_l, y_r = min(y_l, Y[0][0] + i*t), max(y_r, Y[0][1] + i*t)
    y_l, y_r = min(y_l, Y[1][0] - i*t), max(y_r, Y[1][1] - i*t)
    y_l, y_r = min(y_l, Y[2][0]      ), max(y_r, Y[2][1]      )

    return (x_r-x_l) * (y_r-y_l)
    
opt = fmin(calc_area, x0 = 10**8, ftol=10**(-10), disp=False)
print(calc_area(opt[0]))

Measured memory_bytes: 58604
n, k, q = gets.split.map(&:to_i)
scores = Array.new(n + 1, 0)

q.times do
  a = gets.to_i
  scores[a] += 1
end

scores[1..-1].each do |s|
  puts k - (q - s) > 0 ? :Yes : :No
end

Measured memory_bytes: 3324
#include<iostream>

using namespace std;

int a[200005];
int ans[200005];
int M;
int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = n; i >= 1; i--) {
    int tmp = 0;
    for(int k = 1;;k++) {
      if(i * k > n) break;
      tmp += ans[i*k];
    }
      if(tmp % 2 != a[i]) {
	ans[i]++;
	M++;
      }
  }

  cout << M << endl;
  for(int i = 1; i <= n; i++) {
    if(ans[i] && i == n) cout << i << endl;
    else if(ans[i]) cout << i <<' ';
  }
  cout << endl;
 
}

  
 
  


Measured memory_bytes: 2432
#!/usr/bin/env python3
#EDPC M

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    lst = [0] + list(accumulate(dp[i-1]))
    for j in range(k+1):
        if j - a[i-1] < 0:
            dp[i][j] += lst[j+1] - lst[0]
            dp[i][j] %= mod
        else:
            dp[i][j] += lst[j+1] - lst[j-a[i-1]]
            dp[i][j] %= mod
print(dp[-1][-1])


        


Measured memory_bytes: 175240
# -*- coding: utf-8 -*-
# 整数の入力
# スペース区切りの整数の入力
a, b = map(int, input().split())

s = [a, b]
s = sorted(s)
sum = 0
sum += s[-1]
s[-1] -=1

s = sorted(s)
sum += s[-1]
# 出力
print(sum)

Measured memory_bytes: 3060
N = int(input())
a = list(map(int, input().split()))


#print(a)

ref1 = 1 #  
count = 1
ans = 0
while(count <= N):
    if a[count-1] != ref1: # 一致しないとき
        count += 1 # リスト値の引き上げ
        ans += 1
        #print("check",count,"???",ans)
    else: # 一致するとき
        ref1 += 1 # 基準値の引き上げ
        count += 1
        #print("check2",ref1)
print(ans if ans < N else -1)


Measured memory_bytes: 24744
# -*- coding: utf-8 -*-
# 整数の入力
s = input()

words = ["dream", "dreamer", "erase", "eraser"]

def check():
    tmp = s
    while(True):
      current_len = len(tmp)
      for w in words:
        if tmp.endswith(w):
          tmp = tmp[:-len(w)]
      if len(tmp) == 0:
          return "YES"

      if current_len == len(tmp):
          return "NO"

print(check())


Measured memory_bytes: 9248
#include <stdio.h>

void
to_card(int idx, char *suit, int *rank)
{
	switch (idx/13)
	{
	case 0: *suit = 'S'; break;
	case 1: *suit = 'H'; break;
	case 2: *suit = 'C'; break;
	case 3: *suit = 'D'; break;
	}
	*rank = idx%13 + 1;
}

void
to_idx(char suit, int rank, int *idx)
{
	switch (suit)
	{
	case 'S': *idx = 0*13 + (rank-1); break;
	case 'H': *idx = 1*13 + (rank-1); break;
	case 'C': *idx = 2*13 + (rank-1); break;
	case 'D': *idx = 3*13 + (rank-1); break;
	}
}


int
main()
{
	int n_exists;
	scanf("%d\n", &n_exists);

	int idx;
	int rank;
	char suit;
	int is_exists[4*13] = {0};

	int i;
	for (i = 0; i < n_exists; i++)
	{
		scanf("%c %d\n", &suit, &rank);
		to_idx(suit, rank, &idx);
		is_exists[idx] = 1;
	}
	for (idx = 0; idx < 4*13; idx++)
	{
		if (!is_exists[idx])
		{
			to_card(idx, &suit, &rank);
			printf("%c %d\n", suit, rank);
		}
	}

	return 0;
}

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

int main() {
    int H, W;
    cin>>H>>W;
    vector<string> map;
    string tmp;
    for(int i=0;i<H;++i){
        cin>>tmp;
        map.push_back(tmp);
    }
    int DP[H][W];
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            DP[i][j] = 0;
        }
    }

    if(map[0][0]=='#')DP[0][0] = 1;
    for(int i=1;i<H;++i){
        if(map[i][0]=='#'){
            if(map[i-1][0]=='#') DP[i][0] = DP[i-1][0];
            else DP[i][0] = DP[i-1][0] + 1;
        }
        else{
            DP[i][0] = DP[i-1][0];
        }
    }

    for(int i=1;i<W;++i){
        if(map[0][i]=='#'){
            if(map[0][i-1]=='#') DP[0][i] = DP[0][i-1];
            else DP[0][i] = DP[0][i-1] + 1;
        }
        else{
            DP[0][i] = DP[0][i-1];
        }
    }

    for(int i=1;i<H;++i){
        for(int j=1;j<W;++j){
            if(map[i][j]=='#'){
                if(map[i-1][j] == '#'){
                    if(map[i][j-1] == '#'){
                        DP[i][j] = min(DP[i-1][j], DP[i][j-1]);
                    }
                    else{
                        DP[i][j] = min(DP[i-1][j], DP[i][j-1]+1);
                    }
                }
                else{
                    if(map[i][j-1] == '#'){
                        DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]);
                    }
                    else{
                        DP[i][j] = min(DP[i-1][j] + 1, DP[i][j-1] + 1);
                    }
                }
            }
            else{
                DP[i][j] = min(DP[i-1][j], DP[i][j-1]);
            }
        }
    }
    cout<<DP[H-1][W-1]<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        for (int i = 0; i < n; i++) {
            double[] x = new double[2];
            double[] y = new double[2];
            double[] r = new double[2];
            for (int j = 0; j < 2; j++) {
                x[j] = scanner.nextDouble();
                y[j] = scanner.nextDouble();
                r[j] = scanner.nextDouble();
            }
            
            double xy = Math.sqrt( Math.pow(x[1]-x[0], 2)+Math.pow(y[1]-y[0], 2) );
            double rsum = r[0] + r[1];
            double rdiff0 = r[0] - r[1];
            double rdiff1 = r[1] - r[0];

            if (xy > rsum) {
                System.out.println("0");
            } else if (Math.abs(rdiff0) <= xy && xy <= rsum) {
                System.out.println("1");
            } else if (rdiff0 > 0) {
                System.out.println("2");
            } else {
                System.out.println("-2");
            }
        }
    }
}

Measured memory_bytes: 20524
import math

A, B, H, M = map(int, input().split())
long_angle = M / 60 * 360
if H == 12:
    H = 0
short_angle = H / 12 * 360 + M / 60 * 30
angle = abs(long_angle - short_angle)
cos = math.cos(math.radians(angle))
print((A ** 2 + B ** 2 - 2 * A * B * cos) ** 0.5)


Measured memory_bytes: 62412
import java.util.*;
class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
int card[][]=new int[n][3];
int point[]=new int[n];

for(int j=0;j<n;j++){
	for(int i=0;i<3;i++) card[j][i]=sc.nextInt();
}
for(int i=0;i<3;i++){
    for(int j=0;j<n;j++){
	int flag=0;
        for(int k=0;k<n;k++){	
	    if(card[j][i]==card[k][i])flag++;
	    }
  if(flag==1)point[j]+=card[j][i];
}
}
for(int j=0;j<n;j++)System.out.println(point[j]);
}
}

Measured memory_bytes: 20820
/**
 * Heian-Kyo Walking
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {

	static final int PX = -1; //non-passing in x-axis
	static final int PY = -2; //non-passing in y-axis

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

		int n = parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			line = br.readLine();
			int gx = parseInt(line.substring(0, line.indexOf(' ')));
			int gy = parseInt(line.substring(line.indexOf(' ') + 1));
			int[][] routes = new int[gx + 1][gy + 1];

			//
			int p = parseInt(br.readLine());
			for (int j = 0; j < p; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int x1 = parseInt(st.nextToken());
				int y1 = parseInt(st.nextToken());
				int x2 = parseInt(st.nextToken());
				int y2 = parseInt(st.nextToken());
				int px, py;
				if (x1 != x2) {
					px = Math.max(x1, x2);
					py = y1;
					routes[px][py] += PX;
				} else {
					px = x1;
					py = Math.max(y1, y2);
					routes[px][py] += PY;
				}
			}
			for (int j = 1; j <= gx; j++) {
				if (routes[j][0] != PX) {
					routes[j][0] = 1;
				} else {
					for (int k = j; k <=gx ; k++) {
						routes[k][0] = 0;
					}
					break;
				}
			}
			for (int j = 1; j <= gy; j++) {
				if (routes[0][j] != PY) {
					routes[0][j] = 1;
				} else {
					for (int k = j; k <=gy ; k++) {
						routes[0][k] = 0;
					}
					break;
				}
			}

			// solve
			for (int j = 1; j <= gx; j++) {
				for (int k = 1; k <= gy; k++) {
					if (routes[j][k] == 0) {
						routes[j][k] = routes[j][k - 1] + routes[j - 1][k];
					} else {
						if (routes[j][k] == PX) routes[j][k] = routes[j][k - 1];
						else if (routes[j][k] == PY) routes[j][k] = routes[j - 1][k];
						else routes[j][k] = 0;
					}
				}
			}
			System.out.println(routes[gx][gy] > 0 ? routes[gx][gy] : "Miserable Hokusai!");
		}
	}
} //end main

Measured memory_bytes: 19208
n = gets.to_i
a,b = Array.new(n){ gets.split.map(&:to_i) }.transpose
a.sort!
b.sort!

if n.odd?
  m = (n + 1) / 2
  mini = a[m-1]
  maxi = b[-m]
  puts maxi - mini + 1
  exit
else
  m = n / 2
  mini = a[m] + a[m-1]
  maxi = b[-m] + b[-m-1]
  puts maxi - mini + 1
end



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

const int MAX = 2100;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int N, K, ret;
    COMinit();
    cin >> N >> K;


    for(int i=1; i<=K; i++) {
        ret = (COM(K-1, i-1) * COM(N-K+1, i)) % MOD;
        cout << ret << endl;
    }
    return 0;
}

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

typedef long long ll;

ll N;
vector<int> A;

int cc[20][2];
int dp(int idx, int t) {
    if(idx == A.size()) return 0;
    int &ret = cc[idx][t];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i <= (t? A[idx] : 9); i++) {
        ret = max(ret, i + dp(idx + 1, t & (A[idx] == i)));
    }
    return ret;
}

int main() {
    cin >> N;

    while(N) {
        A.push_back(N % 10);
        N /= 10;
    }
    reverse(A.begin(), A.end());

    memset(cc, -1, sizeof(cc));
    cout << dp(0, 1);
}


Measured memory_bytes: 256