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

using namespace std;

#define Vi vector<int>
#define FOR(i,s,e) for (int i=s; i<e; i++)
#define ITER(v) v.begin(), v.end()

constexpr int MAX_N = 1000;
constexpr int MAX_VAL = 10001;

int minCostSort(int* w, int* ref, int n, int minval) {
    bool isfixed[MAX_N] = {0};
    int cost = 0;
    FOR(i,0,n) {
        if (isfixed[i]) { continue; }
        int fromindex = i;
        int n_chain = 0;
        int minelm_in_chain = MAX_VAL;
        int sum = 0;
        while (true) {
            sum += w[fromindex];
            isfixed[fromindex] = true;
            ++n_chain;
            if (minelm_in_chain > w[fromindex]) { minelm_in_chain = w[fromindex]; }
            int destindex = distance(ref, lower_bound(ref, ref+n, w[fromindex]));
            if (destindex == i) { break; }
            fromindex = destindex;
        }
        if (n_chain < 2) { continue; }
        cost += min(
            sum + (n_chain-2) * minelm_in_chain,
            sum + (n_chain+1) * minval + minelm_in_chain
        );
    }
    return cost;
}

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

    int n;
    cin >> n;

    int w[MAX_N];
    int ref[MAX_N];
    int minval = MAX_VAL;
    FOR(i,0,n) {
        cin >> w[i];
        ref[i] = w[i];
        if (minval > w[i]) { minval = w[i]; }
    }

    sort(ref, ref+n);
    int cost = minCostSort(w, ref, n, minval);
    cout << cost << endl;

    return 0;
}

Measured memory_bytes: 3200
n,weight=map(int,input().split())
ans=0
bag=[[] for i in range(4)]
W,V=map(int,input().split());bag[0].append((W,V))
for i in range(n-1):
    w,v=map(int,input().split())
    bag[w-W].append((w,v))
for i in range(4):
    bag[i].sort(key=lambda x:x[1],reverse=True)
valuesum=[[0 for i in range(len(bag[j])+1)] for j in range(4)]
for i in range(4):
    for j in range(len(bag[i])):
        valuesum[i][j+1]=valuesum[i][j]+bag[i][j][1]
for i in range(len(bag[0])+1):
    for j in range(len(bag[1])+1):
        for k in range(len(bag[2])+1):
            for l in range(len(bag[3])+1):
                if i*W+j*(W+1)+k*(W+2)+l*(W+3)>weight:continue
                if valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]>ans:
                    ans=valuesum[0][i]+valuesum[1][j]+valuesum[2][k]+valuesum[3][l]
print(ans)

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

int main(){
  ll a,b,c;
  cin>>a>>b>>c;
  if(a+b>=c) cout<<"No"<<endl;
  else{
    if(4*a*b<(c-a-b)*(c-a-b)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,len;
int sum[1001010];
int c[1010100],num;
struct mol
{
	int l;
	int r;
	int id;
	int ans;
}a[1001010];
inline int read()
{
	char c=getchar();
	int tot=1;
	while((c<'0'|| c>'9')&&c!='-')
		c=getchar();
	if(c=='-')
	{
		tot=-1;
		c=getchar();
	}
	int sum=0;
	while(c>='0'&&c<='9')
	{
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*tot;
}
inline void writ(int x)
{
	if(x<0)
	{
		putchar('-');
		writ(-x);
		return;
	}
	if(x>=10)
		writ(x/10);
	putchar(x%10+'0');
}
inline void write(int x)
{
	writ(x);
	printf("\n");
}
inline int bl(int x)
{
	return (x-1)/len+1;
}
inline int cmp(mol a,mol b)
{
	return bl(a.l)==bl(b.l)?(bl(a.l)&1)?a.r<b.r:a.r>b.r:a.l<b.l;
}
inline int cnm(mol a,mol b)
{
	return a.id<b.id;
}
inline void add(int x)
{
	num+=(++sum[c[x]]==1);
}
inline void del(int x)
{
	num-=(--sum[c[x]]==0);
}
int main()
{
	n=read();
	m=read();
	for(register int i=1;i<=n;i++)
		c[i]=read();
	len=n/sqrt(m*2/3);
	for(register int i=1;i<=m;i++)
	{
		a[i].l=read();
		a[i].r=read();
		a[i].id=i;
	}
	sort(a+1,a+m+1,cmp);
	int l=0,r=0;
	for(register int i=1;i<=m;i++)
	{
		while(l<a[i].l)
			del(l++);
		while(l>a[i].l)
			add(--l);
		while(r<a[i].r)
			add(++r);
		while(r>a[i].r)
			del(r--);
		a[a[i].id].ans=num;
	}
	for(register int i=1;i<=m;i++)
		write(a[i].ans);
	return 0;
}

Measured memory_bytes: 15324
import java.util.*;
import static java.lang.Math.*;

public class Main {
	
	public static void main(String... args) {
		System.out.println(findSubstring(scanString(), scanInt()));
	}
	
	private static String findSubstring(String s, int K) {
		Dict dict = new Dict(K);
		String last = "";
		for (int i = 0; i < s.length(); ++i) {
			if (!last.isEmpty() && last.charAt(0) < s.charAt(i)) {
				continue;
			}
			int jj = Math.min(s.length(), i + K);
			for (int j = i + 1; j <= jj; ++j) {
				dict.append(s.substring(i, j));
			}
			last = dict.last();
		}
		return dict.last();
	}

	private static class Dict {
		private int K;
		
		private final ArrayList<String> dict;
		
		private Dict(int K) {
			this.K = K;
			this.dict = new ArrayList<>(K + 1);
		}
		
		private boolean hasLast() {
			return K <= dict.size();
		}
		
		private String last() {
			return hasLast() ? dict.get(K - 1) : "";
		}
		
		private boolean append(String ss) {
			if (dict.isEmpty()) {
				dict.add(ss);
				return true;
			}
			
			int p = Integer.MAX_VALUE;
			for (int i = dict.size() - 1; 0 <= i; --i) {
				String s = dict.get(i);
				int r = ss.compareTo(s);
				if (r < 0) {
					p = i;
				} else {
					if (r == 0) {
						p = -1;
					}
					break;
				}
			}
			if (dict.size() < K) {
				if (p < 0 || dict.size() <= p) {
					dict.add(ss);
				} else {
					dict.add(p, ss);
				}
			} else {
				if (p < 0 || K <= p) {
					return false;
				}
				dict.add(p, ss);
			}
			if (K < dict.size()) {
				String e = dict.remove(K);
			}
			return true;
		}
	}
	
	private static final Scanner SC = new Scanner(System.in);

	private static int scanInt() {
		return SC.nextInt();
	}

	private static  String scanString() {
		return SC.next();
	}
}


Measured memory_bytes: 25292
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>

using namespace std;

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

typedef long long int ll;


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

	int n,m,start;
	int arr[101];
	cin >> n >> m >> start;
	rep(i , m)
		cin >> arr[i];

    sort(arr , arr+m);
	int cost = 0;
	for(int i=1 ; i<start ; i++)
	{
		if(binary_search(arr , arr+m , i))
		    cost++;
	}
	
	int cost1 = 0;
	for(int i=start+1 ; i<=n ; i++)
	{
		if(binary_search(arr , arr+m , i))
		    cost1++;
	}

	cout << min(cost , cost1);
	return 0;
}

Measured memory_bytes: 256
/*
g++ -std=c++11 -o2 -Wall ABC107C.cpp -o ./out/ABC107C.out
./out/ABC107C.out
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll xs[100010];
ll ls[100010];
ll rs[100010];

int main(){
//  freopen("./input/input.txt", "r", stdin);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> xs[i];
  }
  ll ans = 1e9;
  for (int i = 0; i <= n - k; ++i) {
    if (k == 1) {
      ans = min(ans, abs(xs[i]));
    } else {
      if (xs[i] < 0 && xs[i + k - 1] > 0) {
        ans = min(ans, 2 * abs(xs[i]) + xs[i + k - 1]);
        ans = min(ans, abs(xs[i]) + 2 * xs[i + k - 1]);
//        cout << i << " " << ans <<"\n";
      } else {
        ans = min(ans, max(abs(xs[i + k - 1]), abs(xs[i])));
//        cout << i << " " << ans <<"\n";
      }
    }
  }
  cout << ans << "\n";
}


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

int main () {

    int N;
    cin >> N;

    string S;
    cin >> S;

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int cnt = 0;

        for (char c = 'a'; c <= 'z'; c++) {
            bool left = false, right = false;

            for (int j = 0; j <= i; j++) {
                if (S[j] == c){ 
                    left = true;
                }
            }
            for (int j = i + 1; j < N; j++) {
                if (S[j] == c) {
                    right = true;
                }
            }

            if (left && right) {
                cnt++;
            }
        }

        ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}

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

int p[200002], q[200002];

int main(){
  int N; scanf("%d", &N);
  for(int i = 1; i <= N; i++) scanf("%d", &p[i]);

  int M; scanf("%d", &M);
  for(int i = 1; i <= M; i++) scanf("%d", &q[i]);

  sort(p + 1, p + N + 1);
  sort(q + 1, q + M + 1);

  bool ans = false;

  for(int x = 1, y = 1; x <= N; x++){
    if(p[x] > q[y]) break;
    if(p[x] == q[y]){
      if(y == M){ ans = true; break; }
      y++;
    }
  }

  puts(ans ? "YES" : "NO");
  return 0;
}

Measured memory_bytes: 1664
#include <stdio.h>

int main(void) {
  int n, m, l, i, j, k;
  int a[101][101], b[101][101];
  long long c[101][101];
  scanf("%d %d %d", &n, &m, &l);
  for (i = 0; i < n; i++) {
    for (j = 0; j < m; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  for (i = 0; i < m; i++) {
    for (j = 0; j < l; j++) {
      scanf("%d", &b[i][j]);
    }
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < l; j++) {
      c[i][j] = 0;
      for (k = 0; k < m; k++) {
        c[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  for (i = 0; i < n; i++) {
    for (j = 0; j < l - 1; j++) {
      printf("%lld ", c[i][j]);
    }
    printf("%lld\n", c[i][l - 1]);
  }
  return 0;
}



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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

ll stupid(ll x) {
    if (x<=6) return 1;
    if (x<=11) return 2;

    ll ans = 2;
    x -= 11;
    ans += 2LL*(x/11);
    x = x%11;
    
    if (x==0) return ans;
    if (x<=6) ans++; else ans+=2;

    return ans;

}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    ll x; cin>>x;

    out(stupid(x));

    ll ans = (x/11)*2;
    if (x%11 > 6) {
	ans+=2;
    } else if (x%11 > 0) {
	ans++;
    }

    cerr<<stupid(x)<<" "<<ans<<endl;
    assert(stupid(x) == ans);
    out(ans);
    

    return 0;
}


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

#define ll long long
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define fork(i,n) for(ll i=0; i<(n); i++)
#define forn for(ll i=0; i<(n); i++)
#define fori(i,k,n) for(ll i=k; i<(n); i++) 
#define all(x) (x).begin(),(x).end()
#define en '\n'
#define FILL(x,v) memset(x,v,sizeof(x))
#define pb push_back
template<typename T> void print(vector<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
 
template<typename T> void print(deque<T>& a)
{
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << ' ';
	cout << en;
}
 
template<typename T> void print(vector<vector<T>>& a)
{
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a[i].size(); j++)
			cout << a[i][j] << ' ';
		cout << en;
	}
}
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;}

void min_self(int &a, int b){
	a = min(a, b);
}
void max_self(int &a, int b){
	a = min(a,b);
}

// const int INF = 1e9 + 5;
const ll INF = 1e18L+5;

void solve(){
	string s, t;
	cin >> s >> t;
	int n = s.size();
	int m = t.size();
	vvi dp(n+1, vi(m+1, 0));
	int ans = 0;
	// get max
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(s[i-1]==t[j-1]){
				dp[i][j] = 1+ dp[i-1][j-1];
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
			ans = max(ans, dp[i][j]);
		}
	}
    int i = n, j = m;
    string res;
	// get string
    for (; i > 0 && j > 0; ) {
        if (s[i - 1] == t[j - 1]) {
            res += s[i - 1];
            --i, --j;
        } else {
            if (dp[i][j] == dp[i - 1][j])
                --i;
            else
                --j;
        }
    }
 
    reverse(res.begin(), res.end());
    cout << res << en;

}

int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);
 
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve();
    return 0;
}

Measured memory_bytes: 35584
import itertools

N,M = map(int, input().split())
g = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
  a,b = map(int, input().split())
  g[a-1][b-1]=1
  g[b-1][a-1]=1

  
jr = list(itertools.permutations(range(2,N+1),N-1))
js = []

for i in jr:
  j = list(i)
  j.insert(0,1)
  js.append(j)

ans = 0
  
for i in range(len(js)):
  hantei = True
  for j in range(N-1):
    a = js[i][j]
    #print(a)
    b = js[i][j+1]
    #print(b)
    if g[a-1][b-1] == 0:
      hantei = False
  if hantei:
    ans += 1

print(ans)

Measured memory_bytes: 10184
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
int main(){
    ll n;
    cin >> n;
    vector<ll> c(n-1),s(n-1),f(n-1);
    for(ll i=0;i < n-1;i++)
    {
        cin>>c.at(i)>>s.at(i)>>f.at(i);
    }

    for(ll i=0;i < n-1;i++)
    {
        ll t=s.at(i)+c.at(i);

        for(ll j=i+1;j < n-1;j++)
        {
            t+=max(f.at(j)*((t+f.at(j)-1)/f.at(j)),s.at(j))-t;
            t+=c.at(j);
        }
        cout << t << endl;
    }
    cout << 0 << endl;
}


Measured memory_bytes: 384
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr.append([10**10,10**10,100])
arr=sorted(arr,key=lambda x:x[0])
arr=sorted(arr,key=lambda x:x[2])
job=[[] for _ in range(m+1)]
c=arr[0][2]
ts=arr[0][0]
tt=arr[0][1]
for i in range(1,n+1):
  if c!=arr[i][2]:
    job[c].append([ts,tt])
    ts=arr[i][0]
    tt=arr[i][1]
    c=arr[i][2]
  else:
    if tt==arr[i][0]:
      tt=arr[i][1]
    else:
      job[c].append([ts,tt])
      ts=arr[i][0]
      tt=arr[i][1]
cnt=[0]*(10**5+2)
for tj in job:
  for ts,tt in tj:
    cnt[ts]+=1
    cnt[tt+1]-=1
for i in range(1,10**5+2):
  cnt[i]=cnt[i]+cnt[i-1]
print(max(cnt))

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


int main()
{
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int> A( Q );
	for( int i = 0; i < Q; i++ ) {
		cin >> A[i];
		A[i]--;
	}

	vector<int> a( N );
	for( int i = 0; i < Q; i++ ) {
		a[ A[i] ]++;
	}
	for( int i = 0; i < N; i++ ) {
		a[i] -= Q - K;
	}

	for( int i = 0; i < N; i++ ) {
		string ans = "Yes";
		if( a[i] <= 0 ) ans = "No";
		cout << ans << endl;
	}
}


Measured memory_bytes: 1408
# 2019/04/17
# AtCoder Beginner Contest 091 - C

#四隅: 4回ー表
#四辺(四隅除く): 6回ー表
#中: 9回ー裏
#ただし1行or1列のとき、裏

n, m = map(int, input().split())

if n == 1 and m == 1:
    ans = 1
elif n == 1 and m > 1:
    ans = m - 2
elif n > 1 and m == 1:
    ans = n - 2
else:
    ans = ( n - 2 ) * ( m - 2 )

print(ans)


Measured memory_bytes: 3316
#include <stdio.h>

int main(void)          
{
	int a, b, c;
	int i = 0;
	int count = 0;

	scanf("%d %d %d", &a, &b, &c);

	for (i = a; i <= b; i++) 
	{
		if (c%i == 0)
		{
			count++;
		}
	}

	printf("%d\n", count);
	return 0;
}

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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

LL max_prime = 100003;

int main(){
    int n,k,r,s,p;
    cin>>n>>k;
    cin>>r>>s>>p;
    string t;
    cin>>t;

    LL total = 0;
    string u = "";
    REP(i,n){
        if(t[i] == 'r'){
            if(i-k>=0 && u[i-k] == 'p'){
                u += "f";
                continue;
            }
            u += "p";
            total += p;
        }else if(t[i] == 's'){
            if(i-k>=0 && u[i-k] == 'r'){
                u += "f";
                continue;
            }
            u += "r";
            total += r;
        }else{
            if(i-k>=0 && u[i-k] == 's'){
                u += "f";
                continue;
            }
            u += "s";
            total += s;
        }
    }

    cout<<total<<endl;

    return 0;
}

Measured memory_bytes: 640
# coding: utf-8
# Here your code !
import math
 
num = int(input())
for i in range(num):
    x1,y1,x2,y2,x3,y3 = map(float,input().split())
    a1 = 2*(x2-x1)
    b1 = 2*(y2-y1)
    c1 = (x1*x1 - x2*x2 + y1*y1 - y2*y2)
    a2 = 2*(x3-x1)
    b2 = 2*(y3-y1)
    c2 = (x1*x1 - x3*x3 + y1*y1 - y3*y3)
 
    p1 = (b1*c2 - b2*c1) / (a1*b2 - a2*b1)
    p2 = (c1*a2 - c2*a1) / (a1*b2 - a2*b1)
    r = math.hypot(x1-p1, y1-p2)
    temp = [p1,p2,r]
    ans = map(lambda x:round(x,3),temp)
    print("%03.3f %03.3f %03.3f"%(temp[0],temp[1],temp[2]))

Measured memory_bytes: 7624
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < (int)(x); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = LLONG_MAX/4;
const int n_max = 1e5+10;

struct SegmentTree {
private:
    int n;
    vector<ll> node;

public:
    // 元配列 v をセグメント木で表現する
    SegmentTree(vector<ll> v) {
        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        // セグメント木全体で必要なノード数は 2n-1 個である
        ll sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, -INF);

        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = max(node[2*i+1], node[2*i+2]);
    }

    void update(ll x, ll val){
        //最下段のノードにアクセスする
        x += (n - 1);

        //最下段のノードを更新したら，あとは親に上って更新していく
        node[x] = val;
        while(x > 0){
            x = (x - 1) / 2;
            node[x] = max(node[2*x+1],node[2*x+2]);
        }
    }

    //要求区間[a,b)中の要素の最小値を答える
    //k := 自分がいるノードのインデックス
    //対象区間は[l,r)に当たる

    ll getmax(ll a, ll b, ll k=0, ll l=0, ll r=-1){
        //最初に呼び出されたときの対象区間は[0,n);
        if(r < 0) r = n;

        //要求区間と対象区間が交わらない -> INFを返す
        if(r <= a || b <= l) return -INF;

        //要求区間が対象を完全に被覆している -> 対象区間の答えを計算に使う
        if(a <= l && r <= b) return node[k];

        //要求区間が対象区間の一部を被覆 -> 子について探索を行う
        //左側の子を vl，右側の子を vr としている
        //新しい対象区間は，現在の対象区間を半分に割ったもの
        ll vl = getmax(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getmax(a, b, 2*k+2, (l+r)/2, r);
        return max(vl,vr);
    }
};

int main(){
    ll n,t; cin >> n >> t;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    SegmentTree seg(a);
    map<ll, ll> m;
    rep(i,n-1){
        ll ma = seg.getmax(i+1, n);
        m[a[i] - ma]++;
    }

    ll res = 0;
    auto itr = m.begin();
    debug((*itr).first);
    if((*itr).first < 0)res = (*itr).second;

    cout << res << endl;

}

Measured memory_bytes: 9328
from itertools import accumulate
from collections import Counter

N, P = map(int, input().split())
S = list(map(int, list(input())))

if P == 2 or P == 5:
    s_can = [1 if i % P == 0 else 0 for i in S]
    # s_cant = [0 if i == 1 else 0 for i in s_can]
    # s_acc = list(accumulate(s_can[::-1]))[::-1]
    answer = sum(idx for idx, i in enumerate(s_can, 1) if i)
    print(answer)
else:
    s = [0]
    t = 1
    for i in S[::-1]:
        r = i % P
        s.append(r * t % P)
        t = t * 10 % P

    s_acc = [None] * (N + 1)
    tmp = 0
    for idx, i in enumerate(s):
        tmp = (tmp + i) % P
        s_acc[idx] = tmp

    c = Counter(s_acc)
    answer = sum(i * (i - 1) // 2 for i in c.values())
    print(answer)


Measured memory_bytes: 20980
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        while(true){
            int num = scan.nextInt();
            int trial=0;
            if (num==0){
                break;
            }
            while(true){
                if(num==6174){
                    System.out.println(trial);
                    break;
                }
                int  foo[] = new int[4];
                for(int i=0;i<=3;i++){
                    int a = num%10;
                    foo[i]=a;
                    num=num/10;
                }
                if (foo[0]==foo[1] && foo[2]==foo[3] && foo[1]==foo[2]){
                    System.out.println("NA");
                    break;
                }

                Integer foo2[]={foo[0],foo[1],foo[2],foo[3]};
                Arrays.sort(foo);
                int l=0;
            
                for(int i=0;i<=3;i++){
                   l+=foo[i]*Math.pow(10, i);
                }
                Arrays.sort(foo2, Collections.reverseOrder());
                
                int s=0;
                for(int i=0;i<=3;i++){
                   s+=foo2[i]*Math.pow(10, i);
                }
                num=l-s;
                trial+=1;
            }
            
        }
    }
}


Measured memory_bytes: 50572
// SeeAlso: https://atcoder.jp/contests/abc153/tasks/abc153_e

#include <bits/stdc++.h>

using namespace std;

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

#define MAX 100000000
#define NIL -1
#define MOD 1000000007

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

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }

ll H, N;
ll A[MAX], B[MAX];

int main() {

    cin >> H >> N;

    ll mm_a = 0;
    rep(i, N) {
        cin >> A[i] >> B[i];
    } 

    ll dp[H+1];
    rep(i, H+1) {
        dp[i] = MAX;
    }
    dp[0] = 0;
    rep(i, N) {
        rep(j, H+1) {
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)],dp[j]+B[i]);
        }
    }
    print(dp[H]);
    return 0;
}


Measured memory_bytes: 2560
// #pragma GCC optimize("O3")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace ::std;
// clang-format off
template<typename T> T nxt() {T res; cin >> res; return res;}
#define tests() for (int _ = nxt<int>(); _ > 0; _--)
#define nxt1(t,n) t (n); cin >> n
#define nxt2(t,n,m) t (n),(m); cin >> n >> m
#define nxt3(t,n,m,k) t (n),(m),(k); cin >> n >> m >> k
#define rep(i, A) for (int i = 0 ; i < A ; i++)
#define ll long long
typedef pair<int,int> pii;typedef pair<ll, ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;
#define dbg(vari) cerr<<#vari<<" = "<<(vari)<<endl;
template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){for(T ti : t)s<<ti<<" ";return s; }
#define all(x) (x).begin(), (x).end()
#define last(vec) vec[vec.size()-1]
#define has(c,x) ((c).find(x) != (c).end())
// clang-format on

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
  
  int x = nxt<int>();
  cout << 1- x << endl;

    return 0;
}


Measured memory_bytes: 3648
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ab = [(a[i], b[i]) for i in range(n)]
ab.sort(key=lambda x: x[1])
a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]
ai = [(ab[i][0], i) for i in range(n)]
a.sort()
ai.sort(key=lambda x: x[0])

cond1 = True
for i in range(n):
    if a[i] > b[i]:
        cond1 = False
        break

idx = ai[0][1]
cnt = 1
while idx != 0:
    idx = ai[idx][1]
    cnt += 1
# print(a)
# print(ai)
# print(cnt)
if cnt == n:
    cond2 = False
    for i in range(n - 1):
        if b[i] >= a[i + 1]:
            cond2 = True
            break
else:
    cond2 = True

ans = "Yes" if cond1 and cond2 else "No"
print(ans)


Measured memory_bytes: 30436
//https://atcoder.jp/contests/caddi2018/tasks/caddi2018_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};


int N;
LL a[212345];
LL A[212345];
LL B[212345];
LL BS[212345];
LL BSS[212345];
LL C[212345];
LL r[212345];
LL get_height(int i,int j){
    return BS[j] - BS[i];
}
LL get_sum(int i,int j){
    return BSS[j]-BSS[i+1]-BS[i]*(j-i-1);
}
void solve(){
    for(int i:range(N-1)){
        B[i] = 0;
        if(A[i]<=A[i+1]){
            LL x = A[i];
            while(x*4<=A[i+1]){
                x*=4;
                B[i]-=2;
            }
        }
        else{
            LL x = A[i+1];
            while(A[i]>x){
                x*=4;
                B[i]+=2;
            }
        }
        BS[i+1]=BS[i]+B[i];
        BSS[i+2]=BSS[i+1]+BS[i+1];
    }
    stack<LL> st;
    C[N] = 0;
    st.push(N);
    for(int i=N-1;i>=0;i--){
        C[i] = 0;
        while(st.size()>1&&get_height(i,st.top())>0){
            st.pop();
        }
        C[i]+=get_sum(i,st.top());
        C[i]+=C[st.top()];
        st.push(i);
    }

    //for(int i:range(N)){cout<<B[i]<<" ";}cout<<endl;
    //for(int i:range(N+1)){cout<<BS[i]<<" ";}cout<<endl;
    //for(int i:range(N+2)){cout<<BSS[i]<<" ";}cout<<endl;

}

int main(){
    cin>>N;
    for(int i:range(N)){
        cin>>a[i];
    }
    for(int i:range(N))A[i]=a[i];
    solve();
    for(int i:range(N))r[i]=C[i]+i;
    for(int i:range(N))A[i]=a[N-1-i];
    solve();
    for(int i:range(1,N)){
        r[i]+=C[N-i];
    }
    LL ret= 1e18;
    for(int i:range(N)){
        chmin(ret,r[i]);
    }
    cout<<ret<<endl;
    return 0;
}

Measured memory_bytes: 13312
#include <iostream>
#include <string>
#include <set>

using namespace std;

int main() {
	int n;
	cin >> n;
	set<string> st;
	char c;
	bool hh = true;
	for (int i = 0; i < n; i++) {
		string a;
		cin >> a;

		if (st.size() != 0) {
			if (a[0] != c) {
				hh = false;
			}
		}

		if (st.find(a) == st.end()) {
			st.insert(a);
			int sz = a.size();
			c = a[sz-1];
		}
		else {
			hh = false;
		}
	}

	if (hh) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

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

int main() {
long long N,M,K;
  cin >> N >> M ;
  vector<long long>A(N);
  vector<double>B(N);
  std::priority_queue<double> q;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    q.push(a);
  }
  
  for(int i=0;i<M;i++){
    double d;
    d=q.top();
    q.pop();
    d=0.5*d;
    q.push(d);
  }
  for(int i=0;i<N;i++){
    long long l;
    l=q.top();
    q.pop();
    K=K+l;
  }
  cout << K << endl;

}


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

int N;
vector<int> vec1,vec2;

void solve(){

int max=0;
int tmp=0;

max+=vec1[0];
for (int i=0;i<N;i++) {max+=vec2[i];}
tmp=max;

for (int i=0;i<N-1;i++) {
tmp = tmp-vec2[i]+vec1[i+1];
if (max<tmp) max=tmp;
}

cout << max<<endl;

}

int main(){
cin >> N;
vec1.resize(N);
vec2.resize(N);
for (int i=0;i<N;i++) cin >> vec1[i];
for (int i=0;i<N;i++) cin >> vec2[i];
solve();
return 0;
}

Measured memory_bytes: 256
import Data.List
import Data.Char
import Data.Maybe
import qualified Data.ByteString.Char8 as BS8

main :: IO ()
main = do
    [k, x] <- unfoldr (BS8.readInteger . BS8.dropWhile isSpace) <$> BS8.getLine

    putStrLn $ intercalate " " $ map show [x-k+1..x+k-1]


Measured memory_bytes: 508
import sys
range = xrange
input = raw_input

a,b,c = [int(x) for x in input().split()]
k = int(input())

count = 0
while a >= b:
    b *= 2
    count += 1

while b >= c:
    c *= 2
    count += 1

print 'Yes' if count <= k else 'No'


Measured memory_bytes: 64336
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>

using namespace std;

int main(void) {
  int H, N;
  cin >> H >> N;
  int tmp;
  for (int i = 0; i < N; i++) {
    cin >> tmp;
    H -= tmp;
  }
  if (H <= 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


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

int main()
{
  int array[3];
  cin >> array[0] >> array[1] >> array[2];
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 2; j++)
    {
      if (array[j] > array[j+1])
      {
        int tmp = array[j];
        array[j] = array[j+1];
        array[j+1] = tmp;
      }
    }
  }
  cout << array[0] << " " << array[1] << " " << array[2] << endl;  
}


Measured memory_bytes: 3104
import java.util.Scanner;
import java.lang.Math;
import java.util.Arrays;

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

		int[] array = new int[3];
		for(int i = 0; i < 3; i++) {
			array[i] = sc.nextInt();
		}

		Arrays.sort(array);

		int a = array[2] * 10 + array[1];

		System.out.println(a + array[0]);
	}
}


Measured memory_bytes: 22604
#include<stdio.h>

int main(){
  int a,b,c;
  if(a<b){
    c=a;
    a=b;
    b=c;
  }
  scanf("%d%d",&a,&b);
  while(1){//ユークリッドの互除法を使う
    c=a%b;
    if(c==0)break;
    a=b;
    b=c;
  }
  printf("%d\n",b);
  return 0;
}



Measured memory_bytes: 2140
let () =
  let s = read_line () in
  let check = function
    |"SUN" -> 7
    |"MON" -> 6
    |"TUE" -> 5
    |"WED" -> 4
    |"THU" -> 3
    |"FRI" -> 2
    |_ -> 1
  in
  print_int @@ check s

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

using namespace std;

int main() {
  while (true) {
    int h, w;
    cin >> h >> w;
    if (h + w == 0) {
      break;
    }
    int diag2 = h * h + w * w;

    int ans_w = 150;
    int ans_h = 150;
    
    for (int i = 1; i < 151; i++) {
      for (int j = 1; j < 151; j++) {
        if (i >= j) {
          continue;
        }
        int temp = i * i + j * j;
        if (diag2 < temp) {
          int temp2 = ans_w * ans_w + ans_h * ans_h;
          if (temp < temp2) {
            ans_h = i;
            ans_w = j;
          } else {
            if (i < ans_h) {
              ans_h = i;
              ans_w = j;
            }
          }
        } else if (diag2 == temp) {
          if (h < i) {
            int temp2 = ans_w * ans_w + ans_h * ans_h;
            if (temp < temp2) {
              ans_h = i;
              ans_w = j;
            } else {
              if (i < ans_h) {
                ans_h = i;
                ans_w = j;
              }
            }
          }
        } 
      }
    }

    cout << ans_h << " " << ans_w << endl;
  }
  
  return 0;
}

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

int main(){
    using namespace std;
    unsigned long N;
    cin >> N;
    vector<unsigned long> c(N);
    for(auto& i : c){
        cin >> i;
        --i;
    }
    vector edge(N, vector(0, 0UL));
    for(unsigned long i{1}, a, b; i < N; ++i){
        cin >> a >> b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
    }
    vector euler_tour(N, vector(0, 0UL));
    vector<unsigned long> sz(N);
    [dfs_impl = [&c, &edge, &euler_tour, &sz, &N](auto f, unsigned long now, unsigned long prev, unsigned long& t) -> unsigned long {
        sz[now] = 1;
        euler_tour[c[now]].push_back(1);
        for(const auto& i : edge[now])if(i != prev){
            sz[now] += f(f, i, now, t);
            euler_tour[c[now]].push_back(sz[now]);
        }
        euler_tour[c[now]].push_back(N + 1);
        return sz[now];
    }]{unsigned long t{0};dfs_impl(dfs_impl, 0, 0, t);}();
    for(unsigned long i{0}; i < N; ++i){
        unsigned long cnt{0};
        vector<unsigned long> tmp{0};
        for(const auto& now : euler_tour[i]){
            if(now == 1){
                tmp.push_back(1);
            }else if(now <= N){
                auto t = now - tmp.back();
                cnt += t * (t + 1) / 2;
                tmp.back() = now;
            }else{
                auto t = tmp.back();
                tmp.pop_back();
                tmp.back() += t;
            }
        }
        cnt += (N - tmp.back() + 1) * (N - tmp.back()) / 2;
        cout << N * (N + 1) / 2 - cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 59068
#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int> Count(26, 0);
string Letter;
char alphabet;
char Alphabet;

void Counting(int i){
	for(unsigned int j = 0; j < Letter.size(); j++){
		if(Letter[j] == alphabet || Letter[j] == Alphabet) Count[i]++;
	}
}

int main(){
	while(getline(cin, Letter)){
		for(unsigned int i = 0; i < 26; i++){
			alphabet = 'a';
			Alphabet = 'A';
			alphabet += i;
			Alphabet += i;
			Counting(i);
		}
	}

	for(unsigned int i = 0; i < 26; i++){
		char alphabet = 'a' + i;
		cout << alphabet << " : " << Count[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1180
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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


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

    for(int i = 0; i <= n; i++){
        if(i + i * 8 / 100 == n){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;


    return 0;
}




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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  char c;
  cin >> c;
  if(c=='A'){
    cout <<'T' << endl;
  }else if(c=='T'){
    cout << 'A' << endl;
  }else if(c=='C'){
    cout << 'G' << endl;
  }else{
    cout << 'C' << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};
 
 
void solve(){
    ll n;
    cin>>n;
    cout<<n*800-(n/15)*200<<endl;


    
} 
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
     
    ll Q=1;
    // cin>>Q;
    rep(_,Q){
 
        solve();
 
    }
   
 
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
int main(){
    int N, Q;
    cin >> N;
    string S;
    cin >> S >> Q;
    vector<set<int>> alp(26);
    for(int i = 0; i < N; i++){
        int ind = S[i] - 'a';
        alp[ind].insert(i);
    }
    for(int i = 0; i < Q; i++){
        int flag;
        cin >> flag;
        if(flag == 1){
            int iq;
            char c;
            cin >> iq >> c;
            iq--;
            if(S[iq] != c){
                int ind1 = S[iq] - 'a';
                int ind2 = c - 'a';
                alp[ind1].erase(iq);
                alp[ind2].insert(iq);
                S[iq] = c;
            }
        }
        else{
            int cnt = 0;
            int lq, rq;
            cin >> lq >> rq;
            lq--;
            rq--;
            for(int j = 0; j < 26; j++){
                if(alp[j].empty()) continue;
                auto ite = alp[j].lower_bound(lq);
                if(ite != alp[j].end() && *ite <= rq) {
                    cnt++;
                }
            }
            cout << cnt << endl;
        }
    }
}

Measured memory_bytes: 27252
#include <bits/stdc++.h>
#define sz(v)   ((int)(v).size())
#define  all(v)    ((v).begin()),((v).end())
#define  allr(v)    ((v).rbegin()),((v).rend())
#define   pb         push_back
#define   mp         make_pair
#define    Lcm(a,b)  ((a*b)/(__gcd(a,b)))
#define    clr(v,d)      memset( v, d ,sizeof(v))
typedef  long long     ll ;
typedef  unsigned long long     ull ;
const long double eps= (1e-9);
using namespace std;
int dcmp(long double a,long double b){   return fabsl(a-b)<=eps ? 0: (a>b)? 1:-1  ;}
int getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1;}
int setBit1(int num, int idx) {return num | (1<<idx);}
ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}
ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}
void GO(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
string v[109];
int n,m,mem[109][109][2];
int solve(int r,int c,int pre){

    if(r==n-1&&c==m-1){
        if(v[r][c]=='.') return 0;
        if(pre==1) return 0;
        return 1;
    }
    int &ret=mem[r][c][pre];
    if(ret!=-1) return ret;
    int co=0;
    if(v[r][c]=='.'||pre==1) co=0;
    else
        co=1;
    int ans=100000;
    if(r+1<=n-1)
    ans=min(ans,co+solve(r+1,c,(v[r][c]=='.'?0:1)));

    if(c+1<=m-1)
    ans=min(ans,co+solve(r,c+1,(v[r][c]=='.'?0:1)));

    return ret=ans;
}
int main(){
    GO();

    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    clr(mem,-1);
    cout<<solve(0,0,0)<<"\n";
}


























































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

using namespace std;
#define int long long 
#define N 666666
int arr[N],a[N],b[N];
#define pi 6.28318530717958623200
signed main(){
	int n;
	cin>>n;
	printf("%.20f",pi*n);
	return 0;
}



Measured memory_bytes: 3760
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut info = vec![Vec::new(); n];
    for i in 0..m {
        let v = read_vec::<i64>();
        let l = v[0] as usize - 1;
        let r = v[1] as usize - 1;
        info[l].push((r, v[2]));
        info[r].push((l, -v[2]));
    }
    // println!("{:?}", info);

    let mut poses = vec![std::i64::MAX; n];
    for i in 0..n {
        if poses[i] != std::i64::MAX {
            continue;
        }
        poses[i] = 0;
        let mut que = VecDeque::new();
        que.push_back(i);

        while let Some(l) = que.pop_back() {
            let origin = poses[l];
            for &(r, dist) in info[l].iter() {
                if poses[r] == std::i64::MAX {
                    poses[r] = origin + dist;
                    que.push_back(r);
                }
                if poses[r] != origin + dist {
                    println!("No");
                    return;
                }
            }
        }
    }
    println!("Yes");
}


Measured memory_bytes: 18684
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
using ll=long long;
using ld=long double; 
using namespace std;
//const int INF = 7+(1e+9);
ll GCD(ll x, ll y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return GCD(y, x % y);
    }
}
ll LCM(ll x, ll y)
{
    return x / GCD(x, y) * y;
}
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll MOD=1e9+7;

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<ll>> vec(10,vector<ll>(10));
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            cin>>vec[i][j];
        }
    }
    for(int k=0;k<10;k++){
        for(int i=0;i<10;i++){
            for(int j=0;j<10;j++){
                vec[i][j]=min(vec[i][k]+vec[k][j],vec[i][j]);
            }
        }
    }
    ll sum=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ll x;
            cin>>x;
            if(x==-1)continue;
            sum+=vec[x][1];
        }
    }
    cout<<sum<<endl;
}


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

#define ll  long long int
#define pb push_back
#define rep(i , j , n) for(ll i = j ; i < n ; i++)
#define per(i , j , n) for(ll i = j ; i >= n ; i--)


int main(){
    ll n; 
    cin >> n;
    ll a[3][n],dp[3][n];
    rep(i,0,n){
        cin >> a[0][i] >> a[1][i] >> a[2][i];
    }
    rep(i,0,3){
        dp[i][0] = a[i][0];
    }
    rep(i,1,n){
        dp[0][i] = a[0][i] + max(dp[1][i - 1],dp[2][i - 1]);
        dp[1][i] = a[1][i] + max(dp[0][i - 1],dp[2][i - 1]);
        dp[2][i] = a[2][i] + max(dp[0][i - 1],dp[1][i - 1]);
    }
    cout << max(max(dp[0][n - 1],dp[1][n - 1]),dp[2][n - 1]);


}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Integer number = scanner.nextInt();
        String string = scanner.next();

        int wordCount = string.length();

        if (number < wordCount) {
            String cuttingWord = string.substring(0,number);
            cuttingWord += "...";
            System.out.println(cuttingWord);
        } else {
            System.out.println(string);
        }
    }
}


Measured memory_bytes: 27008
fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    solve(java.util.Scanner(System.`in`), pw)
    pw.flush()
}

fun solve(sc: java.util.Scanner, pw: java.io.PrintWriter) {
    val N = sc.nextInt()
    val X = Array(N) { sc.nextLong() }

    val Xs = X.sorted()
    val midL = Xs[N / 2 - 1]
    val midR = Xs[N / 2]

    for (i in 0 until N) {
        pw.println(if (X[i] < midR) midR else midL)
    }
}


Measured memory_bytes: 82360
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

long long int max( long long int a, long long int b )
{
    if( a >= b )    return a;
    
    return b;
}

long long int min( long long int a, long long int b )
{
    if( a <= b )    return a;
    
    return b;
}

int main()
{
    int n;
    cin>>n;
    long long int a, b;
    cin>>a;
    cin>>b;
    long long int max1 = a+b, min1 = a+b, max2 = a-b, min2 = a-b;
    for( int i = 1 ; i < n ; i++ )
    {
        long long int x, y;
        cin>>x;
        cin>>y;
        max1 = max( max1, x+y );
        max2 = max( max2, x-y );
        min1 = min( min1, x+y );
        min2 = min( min2, x-y );
    }
    
    cout<<max( max1-min1, max2-min2 );
    return 0;
}


Measured memory_bytes: 3632