akhauriyash/Code-Regression huggingface dataset:
def a_connection_and_disconnection():
    from itertools import groupby
    S = input()
    K = int(input())

    # 連続した文字がn個あるなら、そのうちn//2個を変更しないといけない(基本)
    # 後にS中に現れる文字の種類が2以上であることを仮定する処理があるため、ここで分岐
    if len(set(S)) == 1:
        return len(S) * K // 2

    # S に対してランレングス圧縮に似たことをする(文字が何であるかは問わない)
    counter = [len(list(g)) for _, g in groupby(S)]
    # この式では、Sの先頭と末尾を結合したときに同じ文字が連続するかを考えない
    ans = sum([c // 2 for c in counter]) * K

    # Sの先頭と末尾が同じ文字の場合、上の式について
    # ・先頭と末尾を独立に計算してしまった分は引く(そんな部分はK-1箇所ある)
    # ・先頭と末尾を結合した分は足す(そんな部分はK-1箇所ある)
    # ということを反映したのが3つ目の式
    if S[0] == S[-1]:
        a, b = counter[0], counter[-1]
        ans -= (a // 2 + b // 2 - (a + b) // 2) * (K - 1)
    return ans

print(a_connection_and_disconnection())

Measured memory_bytes: 3064
//おまじない
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

int main(){
    
    int n;
    int a[50],b[50];
    int cnt = 0;
    
    cin >> n;
    
    rep(i,n){
        int c;
        cin >> c;
        a[i]=b[i]=c;
    }
    
    sort(a,a+n);
    
    rep(i,n){
        if(a[i]!=b[i])cnt++;
    }
    
    if(cnt==2||cnt==0){
        YES;
    }else{
        NO;
    }
    
    return 0;
}


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

int main(){
  int H1, H2, M1, M2, K;
  
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  
  int Total;
  
  Total = (H2 - H1) * 60;
  Total += (M2 - M1);
  
  cout << (Total - K);
  
  return 0;
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline
def print_ans(S, W):
    """Test Case
    >>> print_ans(4, 5)
    unsafe
    >>> print_ans(100, 2)
    safe
    >>> print_ans(10, 10)
    unsafe
    """
    if S > W :
         print('safe')
    else:
        print('unsafe')
if __name__ == '__main__':
    S, W = map(int, input().rstrip().split())
    print_ans(S, W)



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

int main(){
    char c;
    cin >> c;
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
        cout << "vowel" << endl;
    }else{
        cout << "consonant" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,m,ans=999999;
int f[60][3]={0};
char c;
void takahashi(int x,int a,int w,int b,int r){
	//cout<<a<<" "<<x<<endl;
	if(x==n-1){
		if(a<ans&&b!=0){
			//cout<<a<<endl;
			ans=a;
		}
	}
	else{
		if(b==0&&r==0){
			takahashi(x+1,a+f[x][1]+f[x][2],w+1,b,r);
			takahashi(x+1,a+f[x][0]+f[x][2],w,b+1,r);
		}
		else if(b>=1&&r==0){
			takahashi(x+1,a+f[x][0]+f[x][2],w,b+1,r);
			takahashi(x+1,a+f[x][0]+f[x][1],w,b,r+1);
		}
		else if(r>=1){
			takahashi(x+1,a+f[x][0]+f[x][1],w,b,r+1);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>c;
			if(c=='W'){
				f[i][0]++;
			}
			else if(c=='B'){
				f[i][1]++;
			}
			else{
				f[i][2]++;
			}
		}
	}
	takahashi(1,f[0][1]+f[0][2]+f[n-1][0]+f[n-1][1],0,0,0);
	cout<<ans<<endl;
}

Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  long long int a[5], N, m = 10000000000000000;
  cin >> N;
  for(int i = 0; i < 5; ++i) {
    cin >> a[i];
    m = min(a[i], m);
  }
  cout << (N - 1) / m + 5 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<vector<int>> E(N);
  for (int i = 0; i < M; i++){
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }
  vector<int> c(N, -1);
  bool ok = true;
  queue<int> Q;
  c[0] = 0;
  Q.push(0);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (int w : E[v]){
      if (c[w] == -1){
        c[w] = 1 - c[v];
        Q.push(w);
      } else if (c[w] == c[v]){
        ok = false;
      }
    }
  }
  if (!ok){
    cout << (long long) N * (N - 1) / 2 - M << endl;
  } else {
    vector<int> cnt(2, 0);
    for (int i = 0; i < N; i++){
      cnt[c[i]]++;
    }
    cout << (long long) cnt[0] * cnt[1] - M << endl;
  }
}

Measured memory_bytes: 9132
#include<stdio.h>
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	int i;
	int ans[55]={};
	int a,b;
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		ans[a-1]++;
		ans[b-1]++;
	}
	for(i=0;i<n;i++)
	  printf("%d\n",ans[i]);
	return 0;
}

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int t;
		HashMap<String, Integer> stat = new HashMap<String, Integer> ();
		stat.put("AC", 0);
		stat.put("WA", 0);
		stat.put("TLE", 0);
		stat.put("RE", 0);
		Scanner in = new Scanner(System.in);
		
		t = in.nextInt();
		while(t-- > 0) {
			String s = in.next();
			stat.put(s, stat.get(s) + 1);
		}
		
		for(String s : new String[]{"AC", "WA", "TLE", "RE"}) {
			System.out.printf("%s x %d\n", s, stat.get(s));
		}
		

	}
}

Measured memory_bytes: 49380
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  while(true){
    int n;cin>>n;
    if(n == 0)break;
    vector<int> p;
    for(int i = 0; n > i; i++){
      p.push_back(0);
    }
    string s;cin>>s;
    int ba = 0;
    for(int i = 0; 100 > i; i++){
      int trn = i % n;
      if(s[i] == 'M'){//男
        p[trn]++;
      }else if(s[i] == 'L'){//姫
        p[trn]+=(ba+1);
        ba = 0;
      }else{
        ba += p[trn]+1;
        p[trn]=0;
      }
    }
    sort(p.begin(),p.end());
    for(int i = 0; n > i; i++){
      cout << p[i] << " ";
    }
    cout << ba << endl;
  }
}


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

int k, s, ans;

int main() {
  cin >> k >> s;
  ans = 0;
  rep (x, k) {
    rep (y, k) {
      if (s-k <= x+y && x+y <= s) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h,n;
  cin >> h >> n;
  int sum=0;
  vector<int> a(n);
  for(int i=0;i<n; i++){
  cin >> a[i];
  sum +=a[i];
  }
  if(sum>=h){
  cout << "Yes";
  }
  else{cout << "No";}
  return 0; 
}

Measured memory_bytes: 640
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private static int[][] findMode(Map<Integer, Integer> map) {
        int[][] ans = new int[2][2];
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int key = e.getKey();
            int val = e.getValue();
            if (val <= ans[1][1]) {
                continue;
            }
            if (val > ans[0][1]) {
                ans[1][0] = ans[0][0];
                ans[1][1] = ans[0][1];
                ans[0][0] = key;
                ans[0][1] = val;
            } else {
                ans[1][0] = key;
                ans[1][1] = val;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
        }

        Map<Integer, Integer> odd = new HashMap<>();
        Map<Integer, Integer> even = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = v[i];
            if (i % 2 == 0) {
                even.put(num, even.getOrDefault(num, 0) + 1);
                continue;
            }
            odd.put(num, odd.getOrDefault(num, 0) + 1);
        }
        int[][] oddFreqs = findMode(odd);
        int[][] evenFreqs = findMode(even);

        if (oddFreqs[0][0] == evenFreqs[0][0]) {
            System.out.println(Math.min(
                    n - oddFreqs[1][1] - evenFreqs[0][1],
                    n - oddFreqs[0][1] - evenFreqs[1][1]
            ));
            return;
        }
        System.out.println(n - oddFreqs[0][1] - evenFreqs[0][1]);
    }

}


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

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

int gcd(int a,int b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

int kaizyou(int N){
  int num=1;
  for(int i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

int mod=1e9+7;

signed main() {
  int a,b;
  cin >> a>>b;
  if((a-b)%2==0){
    cout << (a+b)/2 << endl;
  }
  else{
    cout << " IMPOSSIBLE" << endl;
  }
  
}

  
  
  

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define PI 3.14159265358979
typedef long long int ll;

const double pi=3.1415;
ll absc(ll a,ll b){return (a-b>0?a-b:b-a);
}
ll mini(ll a,ll b){return (a>b?b:a);}
ll gcd(ll a,ll b){
	if(a<b)swap(a,b);
	return (a%b?gcd(a%b,b):b);
}
int main()
{
   string a;
   cin>>a;
   cout<<(a=="AAA"||a=="BBB"?"No":"Yes");
}


Measured memory_bytes: 256
n,*a=`dd`.split.map &:to_i;f=0;puts %w(Second First)[loop{b=a.map{|e|e&1^1};s=b.reduce :+;s==n-1&&(0...n).find{|i|b[i]==0&&a[i]>1&&a[i]-=1}||(break f^=s&1);g=a.reduce :gcd;a=a.map{|e|e/g};f^=1}]

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

using namespace std;
int main()
{
    string S;
    cin >> S;
    reverse(S.begin(),S.end());
    vector<string> word={"dream", "dreamer", "erase", "eraser"};
    for(int i=0;i<4;i++){
        reverse(word[i].begin(),word[i].end());
    }

    for(int i=0;i<S.size();){
        bool flag=false;
        for(int j=0;j<4;j++){
            if(S.substr(i,word[j].size())==word[j]){
                flag=true;
                i+=word[j].size();
            }
        }
        if(!flag){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

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

using namespace std;
typedef long long LL;

int u[110], v[110];
LL dp[100010];

int main() {
    int n, w;
    cin>>n>>w;
    for (int i=0;i<n;i++) scanf("%d%d", &u[i], &v[i]);
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for (int i=0;i<n;i++)
        for (int j=100000;j>=0;j--)
            if (j+v[i]<=100000 && dp[j]>-1 && (dp[j+v[i]]==-1 || dp[j+v[i]]>dp[j]+u[i])) dp[j+v[i]]=dp[j]+u[i];
    for (int i=100000;i>=0;i--)
        if (dp[i]<=w && dp[i]!=-1) {
            cout<<i<<endl;
            return 0;
        }
}

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

int n;
string str[1001];

void Make_Tree(){
  
  for(int i=0 ; i < n ; i++){
    for(int j=0 ; j < str[i].size() ; j++){
      if(str[i][j] != '.')break;
      if(str[i][j+1] != '.'){
	str[i][j]='+';
	break;
      }else{
	str[i][j]=' ';
      }
    }
  }

  for(int i=0 ; i < n ; i++){
    for(int j=0 ; j < str[i].size() ; j++){
      if(str[i][j] == '+'){
	int x=j;
	int y=i;
	while(y-1 >= 0 && str[y-1][x]==' '){
	  str[y-1][x]='|';
	  y--;
	}
      }
    }
  }
  
}
int main(){
  
  while(1){

    cin >>n;
    if(n==0)break;

    for(int i=0 ; i < n ; i++)cin >>str[i];
    Make_Tree();  
    for(int i=0 ; i < n ; i++)cout <<str[i]<<endl;

  }
  
  return 0;
}

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

string is_seaquence (int a, int b, int c) {
  return a < b && b < c ? "Yes" : "No";
}

int main(int argc, char const *argv[])
{
  int x, y, z;
  cin >> x >> y >> z;

  string judge = is_seaquence(x, y, z);
  cout << judge << "\n";

  return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
using namespace std;

typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef pair<int,int> pint;
typedef vector<pint> vping;

#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define mt make_tuple

int H,W;
char s[60][60];






int main() {
  cin >> H >> W;
  rep(i,H+2){
    rep(j,W+2){
      s[i][j] = '#';
    }
  }
  int bk = 0;

  rep(i,H){
    rep(j,W){
      cin >> s[i+1][j+1];
      if(s[i+1][j+1]=='#') bk++;
    }
  }

  // int score[H][W];
  vvint score(H+2,vint(W+2,-1));
  queue<tuple<int,int,int>> q; //x,y,s
  q.push(mt(1,1,0));
  int x,y,sc;

  int ans;

  while(!q.empty()){
    tie(x,y,sc) = q.front();
    q.pop();
    score[x][y] = sc;
    if(s[x-1][y]=='.'){s[x-1][y]='#';q.push(mt(x-1,y,sc+1));}
    if(s[x+1][y]=='.'){s[x+1][y]='#';q.push(mt(x+1,y,sc+1));}
    if(s[x][y-1]=='.'){s[x][y-1]='#';q.push(mt(x,y-1,sc+1));}
    if(s[x][y+1]=='.'){s[x][y+1]='#';q.push(mt(x,y+1,sc+1));}
  }

  if(score[H][W]<0){cout << -1 << endl;return 0;}




  ans = H*W - bk - (score[H][W]+1);


  cout << ans << endl;


}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define SWAP(type, x, y) do { type tmp = x; x = y; y = tmp; } while (0)

#define MOD 1000000007 

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

    int ans=(1900*M+100*(N-M))*(1<<M);
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 128
using System;

class LiningUp
{
	static public void Main(string[] args)
	{
		int N;

		N = int.Parse(Console.ReadLine());

		int[] A = new int[N+1];
		int[] count = new int[N];
		string[] vals = Console.ReadLine().Split(' ');
		for(int i=1; i<=N; i++)
		{
			A[i] = int.Parse(vals[i-1]);
			count[A[i]]++;
		}
		if(N%2 == 0)
		{
			for(int i = 1; i<=N-1; i+=2)
			{
				if(count[i] != 2)
				{
					Console.WriteLine(0);
					return;
				}
			}
		}
		else
		{
			if(count[0] != 1)
			{
				Console.WriteLine(0);
				return;
			}
			for(int i= 2; i<=N-1; i+=2)
			{
				if(count[i] != 2)
				{
					Console.WriteLine(0);
					return;
				}
			}
		}
		int result = 1;
		for(int i=0; i<N/2; i++)
		{
			result = result * 2 % 1000000007;
		}
		Console.WriteLine(result);
	}
}


Measured memory_bytes: 10072
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int main(){

    int a,b;
    char op;

    while(true){
        cin >> a >> op >> b;
        if(op=='?'){
            break;
        }
        if(op=='+'){
            cout << a+b << endl;
        }else if(op=='-'){
            cout << a-b << endl;
        }else if(op=='*'){
            cout << a*b << endl;
        }else if(op=='/'){
            cout << a/b << endl;            }
        }

    return 0;
}



Measured memory_bytes: 3112
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define N	100000

unsigned int X;

void srand_() {
	struct timeval tv;

	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec;
}

int rand_() {
	return (X *= 3) >> 1;
}

int *oj[N], oo[N];

void link(int i, int j) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		oj[i] = (int *) realloc(oj[i], o * 2 * sizeof *oj[i]);
	oj[i][o] = j;
}

void sort(int *aa, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[j] == a)
				j++;
			else if (aa[j] < a) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
			}
		sort(aa, l, i);
		l = k;
	}
}

int solve(int *aa, int n, int i_, int l) {
	int i = 0, j = n - 1;

	while (i < j)
		if (i == i_)
			i++;
		else if (j == i_)
			j--;
		else {
			if (aa[i] + aa[j] > l)
				return 0;
			i++, j--;
		}
	return 1;
}

int dp[N];

int dfs(int p, int i, int l) {
	static int aa[N];
	int o, n, lower, upper;

	for (o = 0; o < oo[i]; o++) {
		int j = oj[i][o];

		if (j != p && !dfs(i, j, l))
			return 0;
	}
	n = 0;
	for (o = 0; o < oo[i]; o++) {
		int j = oj[i][o];

		if (j != p)
			aa[n++] = dp[j] + 1;
	}
	sort(aa, 0, n);
	if (p == -1)
		return solve(aa, n % 2 == 0 ? n : n - 1, -1, l);
	if (n % 2 == 0) {
		if (solve(aa, n, -1, l)) {
			dp[i] = 0;
			return 1;
		}
		n--;
	}
	lower = -1, upper = n;
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (solve(aa, n, h, l))
			upper = h;
		else
			lower = h;
	}
	return upper < n && (dp[i] = aa[upper]) < l;
}

int main() {
	int n, h, i, j, k, lower, upper;

	srand_();
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		oj[i] = (int *) malloc(2 * sizeof *oj[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		link(i, j), link(j, i);
	}
	k = n - 1;
	for (i = 0; i < n; i++)
		k -= oo[i] / 2;
	lower = 0, upper = n - 1;
	while (upper - lower > 1) {
		int l = (lower + upper) / 2;

		if (dfs(-1, 0, l))
			upper = l;
		else
			lower = l;
	}
	printf("%d %d\n", k, upper);
	return 0;
}


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

typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7;
#define rep(i,N) for(ll i=0; i<(N); i++)

ll N;
ll A[100005];
ll B[100005];
ll C[100005];
ll ans;

ll cnt(ll i){
	ll k1=lower_bound(A,A+N,B[i])-A;
	ll k2=upper_bound(C,C+N,B[i])-C;
	return k1*(N-k2);
}

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N;

rep(i,N) cin>>A[i];
rep(i,N) cin>>B[i];
rep(i,N) cin>>C[i];

sort(A,A+N);
sort(C,C+N);

rep(i,N){
	ans+=cnt(i);
}

cout<<ans<<endl;

}
	


Measured memory_bytes: 2688
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <set>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b+1;i++)
#define Per(i,b,a) for(int i=b;i>=a;i--)

struct UnionFind{
    int N;
    int *parent;
    int *size;
    
    void create(int n){
        N = n;
        parent = new int[N];
        size = new int[N];
        rep(i,N) parent[i]  = i;
        rep(i,N) size[i] = 1;
    }
    int root(int x){
        int par = parent[x];
        if(par == x) return x;
        else{
            int ans = root(par);
            parent[x] = ans;
            return ans;
        }
    }
    bool is_same(int x,int y){
        x=root(x);
        y=root(y);
        return x==y;
    }
    void unite(int x,int y){
        x=root(x);
        y=root(y);
        if(x==y) return ;
        parent[y] = x;
        size[x]+=size[y];
    }
    int group_size(int x){
        x=root(x);
        return size[x];
    }
    void clear(){
        delete[] parent;
        delete[] size;
    }

};

int main(){
    int H,W;
    cin>>H>>W;
    UnionFind *Tate=new UnionFind[W];
    UnionFind *Yoko=new UnionFind[H];
    bool s[2000][2000];
    string S;
    rep(i,H){
        cin>>S;
        rep(j,W) s[i][j] = (S[j]=='.');
    }
    rep(i,W) Tate[i].create(H);
    rep(i,H) Yoko[i].create(W);

    rep(j,W){
        rep(i,H){
            if(i==0) continue;
            if(s[i][j]&&s[i-1][j]) Tate[j].unite(i,i-1);
        }
    }
    rep(i,H){
        rep(j,W){
            if(j==0) continue;
            if(s[i][j]&&s[i][j-1]) Yoko[i].unite(j,j-1);
        }
    }
    int ans = 0;
    rep(i,H){
        rep(j,W){
            if(s[i][j]){
                ans = max(ans,Tate[j].group_size(i)+Yoko[i].group_size(j));
            }
        }
    }
    cout<<ans-1<<endl;
    return 0;
}

Measured memory_bytes: 66944
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

vl fact,finv;
ll mdpow(ll x,ll k){
	ll res=1;
	while(k!=0){
		if(k&1)res=res*x%MOD;
		x=x*x%MOD;
		k=k>>1;
	}
	return res;
}

ll comb(ll n,ll k) {
	if(n==0&&k==0)return 1;
	if(n<k||n<0)return 0;
	return fact[n]*finv[n-k]%MOD*finv[k]%MOD;
}

struct ferm{
	ferm(ll n){
		fact.resize(n);
		finv.resize(n);
		fact[0]=1;
		finv[0]=1;
		rep(i,n-1){
			fact[i+1]=(fact[i]*(i+1))%MOD;
			finv[i+1]=mdpow(fact[i+1],MOD-2);
		}
	}
};


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	cout<<n-k+1<<endl;
}


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

int main(){
  int n,k;
  cin >> n >> k;
  
  vector<int> l(n);
  for(int i=0; i<n; i++){
    cin >> l.at(i);
  }
  sort(l.begin(), l.end());
  
  int sum = 0;
  for(int i=0; i<k; i++){
    sum += l.at(n-1-i);
  }
  cout << sum << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int main(void){
    long long x;
    int i = 0,mn = INT_MAX;
    int a[10] = {};
    cin >> x;
    while(x > 0){
        a[i] = (x%10);
        i++;
        x /= 10;
    }
    for(int k = i-1;k >= 2;k--){
        int tmp,tmp2;
        tmp = (100*a[k] + 10*a[k-1] + a[k-2]);
        tmp2 = abs(tmp-753);
        mn = min(mn,tmp2);
    }
    cout << mn << endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.array;

void main() {
	ulong n;
	readf("%s", &n);

	auto divs = appender!(uint[]);

	if (n % 2 == 0) {
		uint c;
		do {
			n /= 2;
			++c;
		} while (n % 2 == 0);
		divs.put(c);
	}

	for (ulong i = 3;i * i <= n;i += 2) {
		if (n % i == 0) {
			uint c;
			do {
				n /= i;
				++c;
			} while (n % i == 0);

			divs.put(c);
		}
	}

	uint ans;

	if (n != 1) {
		++ans;
	}

	foreach (e;divs.data) {
		uint b = 1;
		while (b <= e) {
			e -= b;
			++b;
			++ans;
		}
	}
	writeln(ans);
}


Measured memory_bytes: 2836
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#N, W = map(int, input().split())
S = str(input())

if S == "Sunny" :
  print ("Cloudy")
elif S == "Cloudy" :
  print ("Rainy")
else :
  print ("Sunny")



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

using namespace std;

int main(){
    int c[3][3];

    for (int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++){
            cin >> c[i][j];
        }
    }
    
    bool flag = true;
    for (int i = 0; i < 2; i++){
        for (int j = i + 1; j < 3; j++){
            int x = c[i][0] - c[j][0];
            int y = c[i][1] - c[j][1];
            int z = c[i][2] - c[j][2];
            if (x != y || x != z){
                flag = false;
            }
        }
    }
    for (int i = 0; i < 2; i++){
        for (int j = i + 1; j < 3; j++){
            int x = c[0][i] - c[0][j];
            int y = c[1][i] - c[1][j];
            int z = c[2][i] - c[2][j];
            if (x != y || x != z){
                flag = false;
            }
        }
    }    
    
    if (flag == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<fstream>
#include<algorithm>
using namespace std;
using ll = long long;

int main(){
   string s1,s2;
   string str;
   int a,b;
   cin >> s1 >> s2;
   cin >> a >> b;
   cin >> str;
   if(s1==str)  a--;
   else b--;
   cout << a << " " << b << endl;
}

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

int main()
{
    long int s,c;
    cin >> s >> c;
    long int ans=0;
    if(c>=2*s){
        c -= 2*s;
        ans += s + c/4;
    }
    else{
        ans += c/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m, x;
	cin >> n;
	map<int, int> d;
	for(int i = 0; i < n; i++) {
		cin >> x;
		d[x]++;
	}
	cin >> m;
	for(int i = 0; i < m; i++) {
		cin >> x;
		if(d[x] == 0) {
			cout << "NO" << endl;
			return 0;
		}
		d[x]--;
	}
	cout << "YES" << endl;

	return 0;
}

Measured memory_bytes: 9600
/* ＵＴＦ－８ */
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int N;
	std::cin >> N;
	
	std::cout << (N-1)/2 << "\n";
}


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

a = [0]*3
b = [0]*3

for i in range(0, 101):
    a[0] = i
    b[0] = c[0][0] - a[0]
    b[1] = c[0][1] - a[0]
    b[2] = c[0][2] - a[0]
    a[1] = c[1][0] - b[0]
    a[2] = c[2][0] - b[0]

    for j in range(3):
        for k in range(3):
            if c[j][k] != a[j] + b[k]:
                break
        else:
            continue
        break
    else:
        print('Yes')
        break
else:
    print('No')





Measured memory_bytes: 3064
program d
 integer :: n,i,j
 integer(8) :: a(0:9)=(/0,1,2,4,7,12,20,29,38,52/),f(10)=0
 read(*,*) n
 f(3)=1
 do i=4,n
  f(i)=f(i-1)*(a(i-2)+a(i-3)+1)
 enddo
 do i=1,n
  do j=1,n
   if(i==j)then
    write(*,'(i0,x)',advance='no') 0;cycle
   endif
   write(*,'(i0,x)',advance='no') f(max(i,j))*a(min(i,j))+1
  enddo
  write(*,*)
 enddo
end program d

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> divs;
    for(int i = 1; i <= n; ++i) {
        if(n % i == 0) {
            divs.push_back(i);
        }
    }
    int ans = 10;
    for(int i : divs) {
        if(i == n) continue;
        string mn = "~", mx = " ";
        for(int j = 0; j < n; j += i) {
            string substr = s.substr(j, i);
            if(mn > substr) mn = substr;
            if(mx < substr) mx = substr;
        }
        //cout << i << ' ' << mn << ' ' << mx << endl;
        vector<int> val(i);
        for(int j = 0; j < i; ++j) {
            val[j] = int(mx[i - j - 1] - '0') - int(mn[i - j - 1] - '0');
        }
        for(int j = 0; j < i; ++j) {
            if(val[j] < 0) {
                val[j] += 10;
                val[j + 1] -= 1;
            }
        }
        bool isonedigit = true;
        for(int j = 1; j < i; ++j) {
            if(val[j] != 0) isonedigit = false;
        }
        if(isonedigit) {
            //cout << i << ' ' << val[0] << endl;
            ans = min(ans, val[0]);
        }
    }
    for(int i = 9; i >= 10 - ans; --i) {
        for(int j = 10; j <= i + ans; ++j) {
            vector<bool> dp(n + 1); dp[0] = true;
            for(int k = 1; k <= n; ++k) {
                // one-digit case
                int valone = int(s[k - 1] - '0');
                if(dp[k - 1] && i <= valone && valone <= j) dp[k] = true;
                if(k == 1) continue;
                int valtwo = int(s[k - 2] - '0') * 10 + int(s[k - 1] - '0');
                if(dp[k - 2] && i <= valtwo && valtwo <= j) dp[k] = true;
            }
            if(dp[n]) ans = min(ans, j - i);
        }
    }
    cout << ans << endl;
    return 0;
}


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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var list = new List<Model>();

            for (var i = 0; i < n; i++)
            {
                var line = Console.ReadLine().Split();
                var model = new Model() { number = i + 1, city = line[0], point = int.Parse(line[1]) };
                list.Add(model);
            }

            list.OrderBy(z => z.city).ThenByDescending(x => x.point).ToList().ForEach(f => {
                Console.WriteLine(f.number);
            });
        }
    }

    class Model
    {
        public int number { get; set; }
        public string city { get; set; }
        public int point { get; set; }
    }
}

Measured memory_bytes: 11616
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    L, R, d = ZZ()
    ans = 0
    for i in range(L, R+1):
        if i%d == 0: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll cc(int n, int k){
    return (n+k-1)/k;
}

int main(){
    ll k,q;cin>>k>>q;

    vector<int> d(k);
    for(int i = 0 ; i < k; i++) cin>>d[i];

    for(int i = 0; i < q; i++){
        int n,x,m;
        cin>>n>>x>>m;
        ll last = x;
        ll eq = 0;
        for(int i = 0;  i < k; i++){
          ll num = cc(n-i-1,k);
          last+=(d[i]%m)*num;
          if(d[i]%m == 0)eq+=num;
        }
       ll ans = (n-1) - (last/m - x/m) - eq;
       cout<<ans<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
int a[100005][4];
int dp[100005][4];

using namespace std;
int n;
int ans(int ind,int flag)
{
    if(ind==n)return 0;
    if(dp[ind][flag]!=-1)return dp[ind][flag];
    
    int maxi = 0;
    if(flag==0)
    {
        maxi = max(maxi,a[ind][1]+ans(ind+1,1));
        maxi = max(maxi,a[ind][2]+ans(ind+1,2));
        maxi = max(maxi,a[ind][3]+ans(ind+1,3));        
    }
    else if(flag==1)
    {
        maxi = max(maxi,a[ind][2]+ans(ind+1,2));
        maxi = max(maxi,a[ind][3]+ans(ind+1,3));
    }
    else if(flag==2)
    {
        maxi = max(maxi,a[ind][1]+ans(ind+1,1));
        maxi = max(maxi,a[ind][3]+ans(ind+1,3));
    }
    else if(flag==3)
    {
        maxi = max(maxi,a[ind][2]+ans(ind+1,2));
        maxi = max(maxi,a[ind][1]+ans(ind+1,1));
    }    
    
    return dp[ind][flag] = maxi;
}

int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        for(int j = 1;j<=3;j++)
        {
            cin>>a[i][j];
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<ans(0,0);
    return 0;
}


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

long long a, b, k;

void in();
void solve();
void out();

int main(){
    in();
    solve();
    out();
}

void in(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> a >> b >> k;
}

void solve(){
    if(k >= a){
        k -= a;
        a = 0;
    }
    else{
        a -= k;
        k = 0;
    }
    b = max(0ll, b - k);
}

void out(){
    cout << a << ' ' << b;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
S = input()

ans = []

for i in range(len(S)):
    if S[i] == "0" or S[i] == "1":
        ans.append(S[i])
    elif 0 < len(ans):
        ans.pop()

for i in range(len(ans)):
    print(ans[i], end='')

Measured memory_bytes: 95496
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ini(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define int int64_t
#define inf LLONG_MAX

void solve()
{
    int n,i;
    string str;

    cin>>str;

    int curr=0;
    int ans=0;

    for(int i=0;i<str.size();i++)
    {
        if(str[i] == 'R')
            curr++;
        else
        {
            ans=max(ans,curr);
            curr=0;
        }
    }
    ans=max(ans,curr);
    cout<<ans<<endl;
}


signed main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // int tt;    cin>>tt;    while(tt--)
        solve();
     
    cerr<<" Execution : "<<(1.0*clock())/CLOCKS_PER_SEC<<"s \n";
        
        
return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
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;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, y, z;
    cin >> x >> y >> z;
    print((x - 2 * z) / (y + z) + ((x - 2 * z) % (y + z) >= y));
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define F(i,a,n) for(int i=a; i<n; i++)
#define INF 100000000000 // long only

int compare(const void *b1, const void *b2){ // 昇順
    if((long)b1 > b2) return 1;
    else if(b1 < b2) return -1;
    else return 0;
}


int cmp(long *b1, long *b2){ // 昇順
    if(*b1 > *b2) return 1;
    else if(*b1 < *b2) return -1;
    else return 0;
}



int main(){
  int n;
  scanf("%d",&n);
  long a[n];
  long ai[n];
  long aj[n];
  long max=0,min=INF;
  F(i,0,n){
    scanf("%ld",a+i);
    ai[i]=a[i]+i+1;
    aj[i]=i+1-a[i];
    if(max<a[i])max=a[i];
    if(min>a[i])min=a[i];
  }
  qsort(ai,n,sizeof(long),cmp);
  qsort(aj,n,sizeof(long),cmp);
  int i=0,j=0;
  long ans=0;
  while(i+1<n && j<n){
    long tmpi=1,tmpj=0;
    while(ai[i]==ai[i+1] && i+1<n){
      tmpi++;
      i++;
    }
    while(ai[i]!=aj[j] && ai[i]>aj[j] && j<n) j++;
    while(ai[i]==aj[j] && j<n){
      tmpj++;
      j++;
    }
    ans += tmpi*tmpj;
    i++;
  }
  printf("%ld\n",ans);
  return 0;
}

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

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n,N=12;
    cin >> n;
    map <tuple <int,int,int,int>,int > m;
    for(int _=0;_<n;_++){
    	string st;
    	cin >> st;
    	int a=0,b=0,c=0,d=0,id=-1;
    	for(int i=0;i<st.size();i++){
    		if(st[i]=='.'){
    			id=i;
    			break;
    		}
    	}
    	if(id!=-1){
    		st.erase(id,1);
    		c=d=(int)st.size()-id;
    	}
    	int x=0;
    	for(auto i:st){
    		x=x*10+(i-'0');
    	}
    	while(x%2==0)x/=2,a++;
    	while(x%5==0)x/=5,b++;
    	int u=min(a,c),v=min(b,d);
    	a-=u,c-=u,b-=v,d-=v;
    	auto tp=make_tuple(a,b,c,d);
    	m[tp]++;
    }
    int ans=0,cnt=0;
    for(auto [k1,v1]:m){
    	for(auto [k2,v2]:m){
    		int a1,a2,b1,b2,c1,c2,d1,d2;
    		tie(a1,b1,c1,d1)=k1;
    		tie(a2,b2,c2,d2)=k2;
    		if(a1+a2>=c1+c2 and b1+b2>=d1+d2){
    			if(k1==k2){
    				cnt+=v1;
    			}
    			ans+=v1*v2;
    		}
    	}
    }
    cout << (ans-cnt)/2 ;
}

Measured memory_bytes: 3656
s=int(input())
C=set()
C.add(s)
Cl=[s]
m=0

def f(x):
    if x%2==0:
        return int(x/2)
    else:
        return 3*x+1
while(1):
    m+=1
    x=f(Cl[m-1])
    if x in C:
        break
    Cl+=[x]
    C.add(x)
print(m+1)
    

Measured memory_bytes: 38256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  int N, K;
  std::cin >> N >> K;

  // Main

  // Output
  std::cout << N - K + 1 << std::endl;

  return 0;
}


Measured memory_bytes: 256
[n, m] = [int(i) for i in input().split()]
l = []
r = []

for i in range(m):
    k = input().split()
    l.append(int(k[0]))
    r.append(int(k[1]))

out = min(r) - max(l) + 1
if (out > 0):
    print(out)
else:
    print(0)


Measured memory_bytes: 10984
w, h, n = map(int, input().split())
xya = [list(map(int, input().split())) for _ in range(n)]

l, r, b, t = 0, w, 0, h
for x, y, a in xya:
    if a == 1:
        l = max(x, l)
    elif a == 2:
        r = min(x, r)
    elif a == 3:
        b = max(y, b)
    elif a == 4:
        t = min(y, t)
print(max(0, r - l) * max(0, t - b))


Measured memory_bytes: 62692
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
 

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

ll A(ll x){
    if(x>=0)return x;
    else return -x;
}

 
int main(void){
    ll n,x;
    cin>>n>>x;
    ll ans = 0;
    for(ll i=0;i<n;i++){
        ll a;
        cin>>a;
        if(i==0)ans = A(x-a);
        else ans = gcd(ans,A(x-a));
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
    int A, B;
    char op;

    cin >> A >> op >> B;

    int result = 0;
    
    if (op == '+') {
        result = A + B;
    } else if (op == '-') {
        result = A - B;
    }

    cout << result << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        double[] p=new double[n];
        for(int i=0;i<n;i++){
            p[i]=sc.nextInt();
        }
        double [] e=new double[n+1];
        double res=0;
        for(int i=1;i<=n;i++)
        {
            e[i]=e[i-1]+(1+p[i-1])/2;
        }
        for(int i=k;i<=n;i++)
        {
            res=Math.max(res,e[i]-e[i-k]);
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 86224
n,s=int(input()),input()
s+=s[:2]
# 羊:0 狼:1
for i in range(2):
    for j in range(2):
        a=[0]*(n+2)
        a[0]=i
        a[1]=j
        for k in range(1,n+1):
            if a[k]==0:
                if s[k]=="o":
                    a[k+1]=a[k-1]
                else:
                    a[k+1]=not a[k-1]
            else:
                if s[k]=="o":
                    a[k+1]=not a[k-1]
                else:
                    a[k+1]=a[k-1]
        if a[0]==a[n] and a[1]==a[n+1]:
            print(*["W" if k else "S" for k in a[:n]],sep="")
            exit()
print(-1)

Measured memory_bytes: 66396
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll l,r,a,x,y,z, b, c, i, j, k, n, m;
ll arr[2000005],ans[2000005];
string s, str;

int main() {
	cin >> n;
	memset(arr, 0, 10);
	for (i = 0; i < n; i++) {
		cin >> s;
		if (s[0] == 'A')
			arr[0]++;
		else if (s[0] == 'W')
			arr[1]++;
		else if (s[0] == 'T')
			arr[2]++;
		else
			arr[3]++;
	}
	cout << "AC x " << arr[0] << '\n' << "WA x " << arr[1] << '\n' << "TLE x " << arr[2] << '\n' << "RE x " << arr[3];
	return 0;
}
/*
5
30 40 975
*/

Measured memory_bytes: 3200
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
using namespace std;


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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF;
    string str;
    cin>>n>>a>>b;
    if((b-a)%2){
        cout<<min(a-1,n-b)+1+(b-a-1)/2<<endl;
    }else{
        cout<<(b-a)/2<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
# Problem D - Replacing

# input
N = int(input())
a_nums = list(map(int, input().split()))
Q = int(input())

# initialization
nums = [0] * (10**5 + 1)
cur_sum = sum(a_nums)
for a in a_nums:
    nums[a] += 1

# count
for i in range(Q):
    b, c = map(int, input().split())
    b_count = nums[b]
    cur_sum = cur_sum - b_count*b + b_count*c
    print(cur_sum)
    nums[b] = 0
    nums[c] += b_count


Measured memory_bytes: 20996
#include<iostream>

using namespace std;

int main(){
  string N,M;
  bool eq=true;
  cin>>N>>M;
  
    if(N.size()>M.size()){
        cout<<"GREATER"<<endl;;
        return 0;
    }
    if(N.size()<M.size()){
        cout<<"LESS"<<endl;
        return 0;
    }

  for(int i=0;i<N.size();++i){ 
    if(N[i]>M[i]){
        cout<<"GREATER"<<endl;;
        return 0;
    }
    if(N[i]<M[i]){
        cout<<"LESS"<<endl;
        return 0;
    }
  }
    cout<<"EQUAL"<<endl;;
}

Measured memory_bytes: 256
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
int main(){
  int x,sum=0,ma=0;
  rep(i,5){
    cin>>x;
    sum+=(x+9)/10*10;
    ma=max(ma,(1000-x)%10);
  }
  cout<<sum-ma<<endl;
  return 0;
}

Measured memory_bytes: 3644
N = int(input())
A = list(map(int, input().split()))

cost = [abs(0-A[0])] + [abs(A[i] - A[i+1]) for i in range(N-1)] + [abs(0 - A[-1])]
sumCost = sum(cost)
for i in range(N):
    if i == 0:
        print(sumCost - abs(0-A[0]) - abs(A[0]-A[1]) + abs(0-A[1]))
    elif i == N-1:
        print(sumCost - cost[-2] - cost[-1] + abs(0-A[-2]))
    else:
        print(sumCost - cost[i] - cost[i+1] + abs(A[i-1] - A[i+1]))

Measured memory_bytes: 14048
use proconio::*;

#[fastout]
fn run() {
    input! {
        n: usize,
        mut cnt: [usize; 3],
        s: [String; n],
    }
    let s: Vec<usize> = s
        .into_iter()
        .map(|s| {
            if s == "AB" {
                0
            } else if s == "BC" {
                1
            } else {
                2
            }
        })
        .collect();
    let w = 2usize;
    let encode = |c: &[usize]| -> usize {
        c.iter().fold(0, |c, a| c * (w + 1) + std::cmp::min(w, *a))
    };
    let decode = |mut c: usize| -> [usize; 3] {
        let mut id = [0; 3];
        for id in id.iter_mut().rev() {
            *id = c % (w + 1);
            c /= w + 1;
        }
        id
    };
    let mut dp = vec![vec![false; (w + 1).pow(3)]; n + 1];
    let mut prev = vec![vec![((w + 1).pow(3), 3); (w + 1).pow(3)]; n + 1];
    for c in cnt.iter_mut() {
        *c = std::cmp::min(*c, w);
    }
    dp[0][encode(&cnt)] = true;
    for i in 0..n {
        let x = s[i];
        let y = (x + 1) % 3;
        for j in 0..(w + 1).pow(3) {
            if !dp[i][j] {
                continue;
            }
            let mut c = decode(j);
            for &(x, y) in [(x, y), (y, x)].iter() {
                if c[x] > 0 {
                    c[x] -= 1;
                    c[y] += 1;
                    let id = encode(&c);
                    dp[i + 1][id] = true;
                    prev[i + 1][id] = (j, y);
                    c[x] += 1;
                    c[y] -= 1;
                }
            }
        }
    }
    if dp[n].iter().all(|p| !*p) {
        println!("No");
        return;
    }
    let mut ans = vec![];
    let mut pos = 0;
    for i in 0.. {
        if dp[n][i] {
            pos = i;
            break;
        }
    }
    for k in (1..=n).rev() {
        ans.push(prev[k][pos].1);
        pos = prev[k][pos].0;
    }
    ans.reverse();
    let c: Vec<_> = "ABC".chars().collect();
    println!("Yes");
    for a in ans {
        println!("{}", c[a]);
    }
}

fn main() {
    run();
}


Measured memory_bytes: 57080
S,T=input(),input();l,m=len(S),len(T)
for i in range(l-m+1):
 if all(c in"?"+d for c,d in zip(S[-i-m:],T)):S=S.replace("?","a");print(S[:-i-m]+T+S[l-i:]);quit()
print("UNRESTORABLE")

Measured memory_bytes: 3060
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        A, B = map(int, input().split())

        if B == 1:
            print(0)
            exit()

        x = A
        cnt = 1
        while x < B:
            x -= 1
            x += A
            cnt += 1
        print(cnt)


if __name__ == '__main__':
    AtCoder().main()

Measured memory_bytes: 38384