akhauriyash/Code-Regression huggingface dataset:
def main():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = input()
    hand = [""] * N

    ans = 0
    for i, t in enumerate(T):
        if i <= K - 1:
            if t == 'r':
                hand[i] = 'p'
                ans += P
            if t == 's':
                hand[i] = 'r'
                ans += R
            if t == 'p':
                hand[i] = 's'
                ans += S
        else:
            if t == 'r':
                if hand[i - K] == 'p':
                    continue
                else:
                    hand[i] = 'p'
                    ans += P
            if t == 's':
                if hand[i - K] == 'r':
                    continue
                else:
                    hand[i] = 'r'
                    ans += R
            if t == 'p':
                if hand[i - K] == 's':
                    continue
                else:
                    hand[i] = 's'
                    ans += S

    print(ans)





if __name__ == "__main__":
    main()

Measured memory_bytes: 41584
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using ll=long long;
ll minimum[200010];
void solve(long long N, std::vector<long long> P){
  minimum[0]=P[0];
  for(ll i=1;i<N;i++){
    minimum[i]=min(minimum[i-1],P[i]);
  }
  int count=0;
  for(ll i=0;i<N;i++){
    if(P[i]<=minimum[i])
      count++;
  }
  cout<<count<<endl;
}

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


Measured memory_bytes: 3328
program scoring
    implicit none
    integer(8)::t1,t2,t_rate,t_max,diff!実行時間の計測関連
    integer(8)::D,C(26),last(26,365),last_sim(26,365),i,j,k,vmax,tbest,torigin
    integer(8)::drand,qrand!局所探索法の書き換え関連
    integer(8)::contests=26
    integer(8)::steps=0!ベンチマーク用
    integer(8),allocatable::S(:,:),T(:),V(:),Vorigin(:)
    !時間計測開始
    call system_clock(t1)

    !入力
    read*,D,C
    allocate(S(26,D))
    allocate(T(D))
    allocate(V(D))
    allocate(Vorigin(D))
    read*,S
    T=0
    V=0
    last=0
    last_sim=0

    !貪欲法による初期解の生成
    do i=1,D
        do j=1,26
            !得点の初期化
            if(i==1)V(i)=0
            if(i>1)V(i)=V(i-1)

            !lastの初期化
            if(i==1)last(:,i)=0
            if(i>1)last(:,i)=last(:,i-1)

            last(j,i)=i
            V(i)=V(i)+S(j,i)
            
            do k=1,26
                V(i)=V(i)-C(k)*(i-last(k,i))
            end do

            if(j==1)then
                vmax=V(i)
                tbest=j
            else if(V(i)>=vmax)then
                vmax=V(i)
                tbest=j
            end if
        end do
        if(i==1)last(:,i)=0
        if(i>1)last(:,i)=last(:,i-1)
        T(i)=tbest
        last(tbest,i)=i
    end do
    vmax=V(D)
    call system_clock(t2,t_rate,t_max)
    diff=t2-t1

    do
        if(diff>1990000000)exit
		steps=steps+1
        !乱数の生成
        drand=rnd_int(D)
        qrand=rnd_int(contests)

        last_sim(:,:)=last(:,:)
        Vorigin(:)=V(:)
        !drand日目に行うコンテストをqrandに変更する
        !last_simの書き換え
        torigin=T(drand)
        if(drand==1)then
            last_sim(T(drand),1)=0
            last_sim(qrand,1)=1
        else
            last_sim(T(drand),drand)=last(T(drand),drand-1)
            last_sim(qrand,drand)=drand
        end if
        !日付に対応するコンテストタイプの書き換え
        T(drand)=qrand

        !drand日目の得点の再計算
        if(drand==1)then
            V(drand)=0
        else
            V(drand)=V(drand-1)
        end if
        V(drand)=V(drand)+S(T(drand),drand)
        do i=1,26
            V(drand)=V(drand)-C(i)*(drand-last(i,drand))
        end do

        !drand+1日目以降の得点の再計算
        do i=drand+1,D
            last_sim(:,i)=last(:,i-1)
            V(i)=V(i-1)
            V(i)=V(i)+S(T(i),i)
            last(T(i),i)=i
            do j=1,26
                V(i)=V(i)-C(j)*(i-last(j,i))
            end do
        end do

        if(V(D)>vmax)then
            vmax=V(D)
            last(:,:)=last_sim
            Vorigin(:)=V
        else
            T(drand)=torigin
        end if
        !時間計測
        call system_clock(t2,t_rate,t_max)
        diff=t2-t1
    end do
    !print*,diff/dble(t_rate),steps
    !答えの出力
    do i=1,D
        print'(i0)',T(i)
    end do
contains
function rnd_int(rnd_max)
    integer(8),intent(in)::rnd_max
    integer(8)::rnd_int
    real::rnd_real
    call random_number(rnd_real)
    rnd_int=mod(int(rnd_real*100000000),rnd_max)+1
    return
end function
end program scoring

Measured memory_bytes: 3188
#include <cstdio>
using namespace std;
inline int rd(){
	int x=0,p=1;
	char a=getchar();
	while((a<48||a>57)&&a!='-')a=getchar();
	if(a=='-')p=-p,a=getchar();
	while(a>47&&a<58)x=(x<<1)+(x<<3)+(a&15),a=getchar();
	return x*p;
}
const int N=100002;
int n;
int a[N],b[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i;
	for(int i=1;i<=n;i++)printf("%d%c",b[i],i==n?'\n':' ');
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
string str;
int main() {
    while (getline(cin,str)) {
        if (str == "END OF INPUT") break;
        str += " ";
        int res = 0;
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] == ' ') cout << res, res = 0;
            else ++res;
        }
        cout << endl;
    }
}


Measured memory_bytes: 1184
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int n,a[15],x[15][14],y[15][14];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<a[i];j++){
            cin>>x[i][j]>>y[i][j];
            x[i][j]--;
        }
    }
    int ans=0;
    for(int S=0;S<1<<n;S++){
        bool ok=true;
        int mem=0;
        for(int i=0;i<n;i++){
            if(S>>i&1){
                mem++;
                for(int j=0;j<a[i];j++)
                    if(y[i][j]&&!(S>>x[i][j]&1)||!y[i][j]&&S>>x[i][j]&1)
                        ok=false;
            }
        }
        if(ok)
            ans=max(ans,mem);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
N = int(input())
As = list(map(int, input().split()))

dpMoney = [1000]
dpStock = [(0, 0)]
for A in As:
    money = max([A*s+m for s, m in dpStock])
    m = max(dpMoney)
    s2, m2 = m//A, m%A
    dpMoney.append(money)
    dpStock.append((s2, m2))

print(max(dpMoney))


Measured memory_bytes: 9188
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define all(x) x.begin(),x.end()

#pragma region GCD
ll gcd(ll a, ll b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return (a*b) / gcd(a, b);
}
#pragma endregion

int main()
{
	ll a, b; cin >> a >> b;
	cout << lcm(a, b) << endl;
}

Measured memory_bytes: 256
N, W = list(map(int, input().split()))
w0, v0 = list(map(int, input().split()))
w_dict = dict()
w_dict[w0] = [v0]
w_dict[w0+1] = list()
w_dict[w0+2] = list()
w_dict[w0+3] = list()

for _ in range(N-1):
    w, v = list(map(int, input().split()))
    w_dict[w].append(v)

w_dict[w0]   = sorted(w_dict[w0],   reverse=True)
w_dict[w0+1] = sorted(w_dict[w0+1], reverse=True)
w_dict[w0+2] = sorted(w_dict[w0+2], reverse=True)
w_dict[w0+3] = sorted(w_dict[w0+3], reverse=True)

max_sum_v = 0
for i_0 in range(len(w_dict[w0])+1):
    for i_1 in range(len(w_dict[w0+1])+1):
        for i_2 in range(len(w_dict[w0+2])+1):
            for i_3 in range(len(w_dict[w0+3])+1):
                sum_w = w0 * i_0 + (w0 + 1) * i_1 + (w0 + 2) * i_2 + (w0 + 3) * i_3
                if sum_w > W:
                    continue
                sum_v = sum(w_dict[w0][:i_0])   + \
                        sum(w_dict[w0+1][:i_1]) + \
                        sum(w_dict[w0+2][:i_2]) + \
                        sum(w_dict[w0+3][:i_3])
                max_sum_v = max(sum_v, max_sum_v)

print(max_sum_v)



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int N;
int K;

int main(){
  cin >> N >> K;
  if(N % K == 0){
    cout << 0 << endl;
  }
  else{
    cout << 1 << endl;
  }
}


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

int main(void) {
    double n;
    cin >> n;
    for (double co = 1; co <= n; co++) {
        if (floor(co * 1.08) == n) {
            cout << co << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 3704
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
struct edge {int to,costa,costb;};

signed main() {
int x;
cin>>x;
int a=x/100,b=x%100;
if(a>=(b-1)/5+1)cout<<1;
else cout<<0;

return 0;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
#define M 1000000007
#define T 998244353
#define PI 3.142
#define ll long long

using namespace std;

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


    
    int n, k, i, x, j, sum;
    cin >> n >> k;
    int a[n+1];
    int dp[n+1][k+1];
    for(i=1; i<=n; i++){
        cin >> a[i];
    }
    for(i=0; i<=n; i++){
        dp[i][0]=1;
    }
    for(i=0; i<=k; i++){
        if(i<=a[1]){
            dp[1][i]=1;
        }
        else {
            dp[1][i]=0;
        }
    }
    int sumarr[k+1];
    for(i=2; i<=n; i++){
        sum=0;
        for(j=0; j<=k; j++){
            if(j-a[i]<=0){
                sum = (sum + dp[i-1][j])%M;
            }
            else {
                sum = (sum + dp[i-1][j] - dp[i-1][j-a[i]-1])%M;
                if(sum<0){
                    sum = sum + M;
                }
            }
            sumarr[j]=sum;
        }
        for(j=1; j<=k; j++){
            dp[i][j] = sumarr[j];
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

Measured memory_bytes: 39808
#include<stdio.h>

int binary(int [],int,int);

int main()
{
  int S[100000],key,n,q,i,count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){scanf("%d",&S[i]);}
  scanf("%d",&q);
  for(i=0;i<q;i++)
  {
    scanf("%d",&key);
      if(binary(S,n,key)!=0)count++;
    }
  printf("%d\n",count);

  return 0;
}

int binary(int S[],int n,int key)
{
  int left=0,right=n,mid;
  while(left<right)
    {
      mid=(left+right)/2;
      if(S[mid]==key)return mid;
      else if(key<S[mid])right=mid;
      else left=mid+1;
    }
  return 0;
}

Measured memory_bytes: 2960
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long K = sc.nextLong();
        long a = sc.nextLong();
        long s = sc.nextLong();
        long d = sc.nextLong();
        sc.close();
        System.out.println((K - s) * (a - d));
    }
}

Measured memory_bytes: 21844
#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i,A,B) for(i=(A);i<=(B);++i)
using namespace std;
char a[105][105];
int f[105][105],n,m;
int main(){
    int i,j;
    scanf("%d%d",&n,&m);
    For(i,1,n)scanf("%s",a[i]+1);
    memset(f,0x3f,sizeof(f));
    f[n][m]=a[n][m]=='#';
    for(i=n;i;--i)
        for(j=m;j;--j)if(i<n||j<m){
            if(i<n)if(a[i+1][j]=='.')f[i][j]=min(f[i][j],f[i+1][j]+(a[i][j]=='#'));
            else f[i][j]=min(f[i][j],f[i+1][j]);
            if(j<m)if(a[i][j+1]=='.')f[i][j]=min(f[i][j],f[i][j+1]+(a[i][j]=='#'));
            else f[i][j]=min(f[i][j],f[i][j+1]);
        }
    printf("%d\n",f[1][1]);
    return 0;
}

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

int main()
{
	int eye[10000],N,M,masu[10000],B,i,ima,L,C,D,j,n=0,c=0,ba=0;
		cin>>N>>M;
		while(N!=0||M!=0){
		for(i=1;i<=N;i++){
			cin>>masu[i];
		}
		ima=1;
		for(i=0;i<M;i++){
			cin>>eye[i];
		}
		for(i=1;i<=M;i++){
			ima=ima+eye[i-1];
			if(ima>=N){
				n=i;
				break;
			}
			ima=ima+masu[ima];
			if(ima>=N){
				n=i;
				break;
			}
		}
	cout<<n<<endl;
	cin>>N>>M;
	}
	return 0;
}

Measured memory_bytes: 3104
#include<iostream>
#include<vector>
#include<string>
#include<climits>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<queue>


int main(){
	int n, a, b;
	std::cin>>n>>a>>b;
	

	std::cout<<std::min(n*a, b)<<std::endl;

	return 0;
	
}

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

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

void solve(void) {
  ll N; cin >> N;
  vector<string> s(N);
  rep(N, i) cin >> s[i];

  map<string, ll> prise;
  rep(N, i) prise[s[i]]++;

  cout << prise.size() << endl;
}

int main(void) {
  solve();
  return 0;
}

Measured memory_bytes: 24996
#include<stdio.h>
#include<math.h>
double areas(double x1,double y1,double x2,double y2,double x3,double y3)
{
	return 0.5*fabs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1));
}
int main()
{
	int i=0;
	double a[7],area[4];
	double x1,y1,x2,y2,x3,y3,x,y;
	while(scanf("%lf",&x1)!=EOF)
	{
	 for(i=0;i<7;i++)
		 scanf("%lf",&a[i]);
	 area[0] = areas(x1,a[0],a[1],a[2],a[3],a[4]);
	 area[1] = areas(x1,a[0],a[1],a[2],a[5],a[6]);
	 area[2] = areas(x1,a[0],a[3],a[4],a[5],a[6]);
	 area[3] = areas(a[1],a[2],a[3],a[4],a[5],a[6]);
	 if(fabs(area[0]-area[1]-area[2]-area[3])<0.00001)
		 printf("YES\n");
	 else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 608
// 65 - 90

int main()
{
  int n;
  char s[100000];
  scanf("%d %s", &n, &s);
  for (int i = 0; s[i] != '\0'; i++)
  {
    if (s[i] + n > 90)
    {
      printf("%c", s[i] + n - 26);
    }
    else
    {
      printf("%c", s[i] + n);
    }
  }
}

Measured memory_bytes: 128
k, x = [int(x) for x in input().split()]

lst = []

def chk(num):
    if num < -1000000:
        return -1000000
    elif num > 1000000:
        return 1000000
    else:
        return num

for i in range(x-k + 1, k + x):
    lst.append(chk(i))

print(*sorted(lst))



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

const int N = 2 * 100 * 1000 + 20;

int n, x, y, q;
int arr_p[N];

long long arr_in[N], arr_ans[N];

vector <int> gr[N];

void dfs(int);

int main() {
	cin >> n >> q;
	for (int i = 1; i < n; i++) {
		cin >> x >> y;
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	for (int i = 1; i <= q; i++) {
		cin >> x >> y;
		arr_in[x] += y;
	}
	dfs(1);
	for (int i = 1; i <= n; i++)
		cout << arr_ans[i] << " ";
}

void dfs(int a) {
	arr_ans[a] += arr_in[a];
	for (int u = 0; u < gr[a].size(); u++) {
		if (gr[a][u] != arr_p[a]) {
			arr_p[gr[a][u]] = a;
			arr_ans[gr[a][u]] += arr_ans[a];
			dfs(gr[a][u]);
		}
	}
}

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

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
typedef vector<ll> vll;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

int main(){
  ll H, W; cin >> H >> W;
  bool color[H][W], passed[H][W] = {};
  rep(h, H){
    string s;
    cin >> s;
    rep(w, W) color[h][w] = (s[w] == '#');
  }
  ll ans = 0;
  rep(h, H) rep(w, W){
    if(passed[h][w]) continue;
    queue<P> que;
    que.push(P(h, w));
    passed[h][w] = true;
    ll black = color[h][w], white = !color[h][w];
    while(!que.empty()){
      P crt = que.front();
      que.pop();
      ll h_ = crt.first, w_ = crt.second;
      // printf("%lld %lld\n", h_, w_);
      bool clr = color[h_][w_];
      if(h_ - 1 >= 0){
        if(!passed[h_-1][w_] && color[h_-1][w_] != clr){
          que.push(P(h_-1, w_));
          passed[h_-1][w_] = true;
          black += !clr;
          white += clr;
        }
      }
      if(h_ + 1 < H){
        if(!passed[h_+1][w_] && color[h_+1][w_] != clr){
          que.push(P(h_+1, w_));
          passed[h_+1][w_] = true;
          black += !clr;
          white += clr;
        }
      }
      if(w_ - 1 >= 0){
        if(!passed[h_][w_-1] && color[h_][w_-1] != clr){
          que.push(P(h_, w_-1));
          passed[h_][w_-1] = true;
          black += !clr;
          white += clr;
        }
      }
      if(w_ + 1 < W){
        if(!passed[h_][w_+1] && color[h_][w_+1] != clr){
          que.push(P(h_, w_+1));
          passed[h_][w_+1] = true;
          black += !clr;
          white += clr;
        }
      }
    }
    ans += black * white;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
 int main(void){
 int a,b;
scanf("%d%d",&a,&b);
if(a<b)
 printf("a < b\n");
if(a>b)
 printf("a > b\n");
if(a == b)
 printf("a == b\n");



 return 0;

 }

Measured memory_bytes: 580
/*
author: Apoorv Singh
*/

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

typedef vector <long long> vi;
typedef pair <long long, long long> pii;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define FOR(i, a, b) for (long long i = a; i < b; ++i)
#define FORR(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define int long long
#define inf LLONG_MAX
#define endl "\n"
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

template <class X>
void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}
template <typename X> ostream& operator << (ostream& x,const vector<X>& v){ for (X a : v) x << a << ' '; return x;} 
template <typename X, typename Y> ostream& operator << (ostream& x, const vector< pair<X, Y> >& v) {for (pair <X, Y> it : v) x << it.first << ' ' << it.second << endl; return x;} 
template <typename T, typename S> ostream& operator << (ostream& os, const map<T, S>& v) { for (pair <T, S> it : v) os << it.first << " => " << it.second << endl; return os; }

double pi = 3.14159265358979323846264338327950288419716939937510582097494459230;
int modulo = 1e9 + 7;

int fpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int a,b; cin >> a >> b;
    if (abs(b-a)%2 == 1)
    {
        cout << "IMPOSSIBLE";
        return 0;
    }
    cout << (a+b)/2;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp fixed << setprecision
#define pb(x) push_back(x)
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N, Z, W;
    cin >> N >> Z >> W;
    int a[N+1], b[N+1];
    a[N] = Z;
    rep3(i, N-1, 0) cin >> a[i];
    b[N] = W;
    rep3(i, N-1, 0) b[i] = a[i];
    //dp1(2)[i]:=残り(i+1)枚のときにX(Y)が手番のときの最終的なスコア
    int dp1[N], dp2[N];
    rep(i, N){
        //全部取る場合
        int res1 = abs(b[i+1]-a[0]), res2 = abs(a[i+1]-b[0]);
        //j枚残す場合
        rep2(j, 1, i){
            res1 = max(res1, dp2[j-1]);
            res2 = min(res2, dp1[j-1]);
        }
        dp1[i] = res1, dp2[i] = res2;
    }
    //rep(i, N) cout << dp1[i] << ' ' << dp2[i] << endl;
    cout << dp1[N-1] << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int A,B;
    scanf("%d %d",&A,&B);

    if (12.5*(A+1) <= 10*B || 10*(B+1) <= 12.5*A) {
        printf("%d\n",-1);
    }
    else if (12.5*A <= 10*B) {
        printf("%d\n",10*B);
    }
    else {
        if (A%2==0) {
            printf("%d\n",(int)(12.5*A));
        }
        else {
            printf("%d\n",(int)(12.5*A +1));
        }
    }
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    for(int d = 0; 7*d <= n; ++d){
        if((n-7*d)%4 == 0){ cout << "Yes" << endl; return 0;}
    }
    cout << "No" << endl; return 0;
}

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

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))

#define DIVUP(x, y) (((x) + ((y) - 1)) / (y))
#define DIVOFF(x, y) (((x) + ((y) / 2)) / (y))
#define REMAINDER(x, y) ((x) % (y))


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

  int count{};
  for (int i{}; i < 4; ++i) {
    if (N % 10 == 2) ++count;
    N /= 10;
  }

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


Measured memory_bytes: 760
#!/usr/bin/env python3
# 整数の入力
N = int(input())
data = [list(map(int, input().split())) for _ in range(N-1)]
# print(N)
#print(data)


for i in range(N-1):
    t = 0
    for j in range(i, N-1):
        #print(j)
        c = data[j][0]
        s = data[j][1]
        f = data[j][2]
        if t < s: 
            t = s
        elif t % f == 0:
            pass
        else:
            t += f - (t%f)
        t += c
    print(t)
        

print(0)

Measured memory_bytes: 9228
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()
#define DEBUG_INT(var) printf("the value of "#var" is %d\n", var)
#define PRINT_ARRAY(name, i) printf("the value of "#name"[%d] is %d\n", (i), name[(i)])
#define DEBUG_ARRAY(name, begin, end) REP(i, begin, end) PRINT_ARRAY(name, i)

#define pr_arr(name, a, b) \
  for (int i = (a); i < (b); i++) { \
    for (int j = (a); j < (b); j++) {\
      if (j > (a)) printf(" "); \
      printf("%lld", name[i][j]); \
    }\
    printf("\n");\
  }\

#define YES puts("YES")
#define NO  puts("NO")
#define Yes puts("Yes")
#define No  puts("No")

using namespace std;

typedef long long ll;


int H, W, K;
char s[305][305]; //# いちごあり
int ans[305][305];

int main(void) {
    scanf("%d %d %d", &H, &W, &K);
    rep(i, 0, H) scanf("%s", &s[i]);

    int x = 1;
    rep(i, 0, H) {
      
      int t = 0;
      rep(j, 0, W) if (s[i][j]=='#')t++;
      if (t==0) continue;

      t = 0;
      rep(j, 0, W) {
        if (s[i][j]=='#') {
          if (t==0) t++;
          else x++;
        }
        ans[i][j] = x;
      }
      x++;
    }

    rep(i, 1, H) {
      if (ans[i][0]==0) {
        rep(j, 0, W) {
          ans[i][j] = ans[i-1][j];
        }
      }
    }

    per(i, 0, H-1) {
      if (ans[i][0]==0) {
        rep(j, 0, W) {
          ans[i][j] = ans[i+1][j];
        }
      }
    }
   
    rep(i, 0, H) {
      rep(j, 0, W) {
        if (j>0) printf(" ");
        printf("%d", ans[i][j]);
      }
      printf("\n");
    }

	return 0;
}


Measured memory_bytes: 1152
import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long n = sc.nextLong();
            long k = sc.nextLong();
            if(n>=k){
                n = n%k;
            }
            System.out.println(Math.min(n,k-n));
        }
    }

Measured memory_bytes: 21844
import java.util.*;
import java.io.*;
public class Main{
	static int[] a;
	static ArrayList<Integer> x = new ArrayList<Integer>();
   public static void main(String[] main) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      PrintWriter out = new PrintWriter(System.out);
      int n = Integer.parseInt(st.nextToken());
      st = new StringTokenizer(br.readLine());
      a = new int[n];
      for(int i = 0; i < n; i++)
          a[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(a);
      sieve();
      out.println(x.size());
      out.close();
   }
   static void sieve() {
	   boolean[] dp = new boolean[1000001];
	   for(int i = 0; i < dp.length; i++)
		   dp[i] = true;
	   HashSet<Integer> elements = new HashSet<Integer>();
	   HashSet<Integer> dup = new HashSet<Integer>();
	   for(int i = 0; i < a.length; i++) {
		   if(elements.contains(a[i]))
			   dup.add(a[i]);
		   elements.add(a[i]);
		   if(!dup.contains(a[i]) && dp[a[i]] && a[i] <= 500000) {
			   for(int j = a[i]*2; j < 1000001; j += a[i]) {
				   dp[j] = false;
			   }
		   }
	   }
	   for(int i = 0; i < a.length; i++)
		   if(dp[a[i]] && !dup.contains(a[i]))
			   x.add(a[i]);
   }
}

Measured memory_bytes: 66120
#include <bits/stdc++.h>
using namespace std;
#define pi 2*asin(1.0)


//template functions
/////////////////////////
long Comb(long N,long M){// nCm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
for(long i=M;i>0;i--){
    ans=ans/i;
}
return ans;
}
long Perm(long N,long M){// nPm
long ans=1;
for(long i=N;i>N-M;i--){
    ans=ans*i;
}
return ans;
}
/////////////////////////



//Answer


int main() {

long N;
string str;
cin>>N>>str;
long countW=0,countR=0;

for(int i=0;i<N;i++){
    if(str.at(i)=='W'){
        countW++;
    }else{
        countR++;
    }
}
long ansR=countR;
long ansW=countW;

for(long i=0;i<countR;i++){
    if(str.at(i)=='R'){
        ansR--;
    }
}
for(long i=N-1;i>N-1-countW;i--){
    if(str.at(i)=='W'){
        ansW--;
    }
}
  
if(ansR>ansW){
    cout<<ansW<<endl;
}else{
    cout<<ansR<<endl;
}



}


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

using namespace std;
using ll = long long;
using pl = pair<ll,ll>;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

vector<pair<long long, long long> > prime_factorize(long long n) {
  vector<pair<long long, long long> > res;
  for (long long p = 2; p * p <= n; ++p) {
    if (n % p != 0) continue;
    int num = 0;
    while (n % p == 0) { ++num; n /= p; }
    res.push_back(make_pair(p, num));
  }
  if (n != 1) res.push_back(make_pair(n, 1));
  return res;
}

ll f(vector<ll> &v, int dep, int sum) {
  if(!(dep < v.size())) {
    return sum == 75;
  }
  ll ret = 0;
  for(ll i=0; i<=v[dep]; i++) {
    ret += f(v, dep+1, sum*(i+1));
  }
  return ret;
}

void solve(long long N){
  vector<vector<pl>> v(101);
  vector<ll> pf(101, 0);
  vector<ll> x;
  for(ll i=1; i<=100; i++) {
    v[i] = prime_factorize(i);
  }
  for(ll i=1; i<=N; i++) {
    for(auto p: v[i]) {
      pf[p.first] += p.second;
    }
  }
  ll n3 = 0;
  ll n5 = 0;
  ll n15 = 0;
  ll n25 = 0;
  ll n75 = 0;
  for(auto val : pf) {
    if(val != 0)
      if(val + 1 >= 75){
	n3++;
	n5++;
	n15++;
	n25++;
	n75++;
      } else if(val + 1 >= 25) {
	n3++;
	n5++;
	n15++;
	n25++;
      } else if (val +1 >= 15) {
	n3++;
	n5++;
	n15++;
      } else if(val + 1 >= 5) {
	n3++;
	n5++;
      } else if(val + 1 >= 3) {
	n3++;
      }
      x.push_back(val+1);
  }

  ll ans = 0;
  ans += n75;
  if(n5 > 0)
    ans += n15*(n5-1);
  if(n3 > 0)
    ans += n25*(n3-1);
  if(n5 > 0 and n3 > 1)
  ans += (n5*(n5-1)/2)*(n3-2);
  std::cout << ans << std::endl;

}

int main(){
  long long N;
  scanf("%lld",&N);
  solve(N);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
struct edge{int to;ll cap;int rev;};
int main(){
    ll N,W;
    cin>>N>>W;
    vector<ll> w(N),v(N);
    rep(i,N) cin>>w[i]>>v[i];

    vector< vector<ll> > dp(2, vector<ll>(100010));

    rep(i,2)rep(j,100010)dp[i][j]=-inf;
    int crt=0,nxt=1;
    dp[crt][0] = 0;
    rep(i,N){
        rep(j,100010)dp[nxt][j]=-inf;
        rep(j,W+1){
        if(dp[crt][j]==-inf)continue;
        if(j+w[i]<=W) dp[nxt][j+w[i]] = max(dp[nxt][j+w[i]],dp[crt][j]+v[i]);
        dp[nxt][j] = max(dp[nxt][j],dp[crt][j]);
        }
        swap(crt,nxt);
    }

    ll res=-inf;
    rep(j,W+1) res = max(res,dp[crt][j]);
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 2560
using System;

class Program
{
	static void Main(string[] args)
    {
    	int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
      	int max = 0;
        int tmp = 0;
        for(var i = 0; i < n; i++)
        {
           if (s[i] == 'I') { tmp++; }
           if (s[i] == 'D') { tmp--; }
           if (max < tmp) { max = tmp; }
        }
        Console.WriteLine(max);
    }
}

Measured memory_bytes: 13140
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    // 一行読み込み、空白で分解してusize２つパースする
    let N = get!(usize);
    let mut V: Vec<i32> = (0..N).map(|_| read()).collect();
    let mut C: Vec<i32> = (0..N).map(|_| read()).collect();
    let mut ans = 0;
    for i in 0..N {
        if V[i] > C[i] {
            ans += V[i] - C[i];
        }
    }
    println!("{}", ans);
}


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

bool is_square(int n)
{
    for (int i = 0; i <= n; i++)
    {
        if (i * i == n)
        {
            return true;
        }
    }
    return false;
}
double distance(double x1, double y1, double x2, double y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    string s;
    cin >> s;
    int a, b, c, d;
    a = s[0] - '0';
    b = s[1] - '0';
    c = s[2] - '0';
    d = s[3] - '0';
    if (a + b + c + d == 7)
    {
        cout << a << "+" << b << "+" << c << "+" << d << "=7" << endl;
    }
    else if (a + b + c - d == 7)
    {
        cout << a << "+" << b << "+" << c << "-" << d << "=7" << endl;
    }
    else if (a + b - c + d == 7)
    {
        cout << a << "+" << b << "-" << c << "+" << d << "=7" << endl;
    }
    else if (a + b - c - d == 7)
    {
        cout << a << "+" << b << "-" << c << "-" << d << "=7" << endl;
    }
    else if (a - b + c + d == 7)
    {
        cout << a << "-" << b << "+" << c << "+" << d << "=7" << endl;
    }
    else if (a - b + c - d == 7)
    {
        cout << a << "-" << b << "+" << c << "-" << d << "=7" << endl;
    }
    else if (a - b - c + d == 7)
    {
        cout << a << "-" << b << "-" << c << "+" << d << "=7" << endl;
    }
    else if (a - b - c - d == 7)
    {
        cout << a << "-" << b << "-" << c << "-" << d << "=7" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto abk = input.front.split.to!( long[] );
	return tuple( abk[ 0 ], abk[ 1 ], abk[ 2 ] );
}

auto solve( long a, long b, long k )
{
	auto al = a;
	auto ar = min( b, a + k );
	auto bl = max( a, b + 1 - k );
	auto br = b + 1;
	
	if( bl < ar ) bl = ar;
	
	return chain( iota( al, ar ), iota( bl, br ) ).map!( to!string ).join( "\n" );
}


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

int main()
{
	map<int, int> d;
	int n;

	while (cin >> n)
	{
		if (d.find(n) == d.end())
			d[n] = 1;
		else
			d[n]++;
	}

	map<int, int>::iterator it;
	int Max = 0;
	for (it=d.begin(); it!=d.end(); it++)
		if (Max < it->second)
			Max = it->second;

	for (it=d.begin(); it!=d.end(); it++)
		if (it->second == Max)
			cout << it->first << endl;
}

Measured memory_bytes: 0
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define ll long long
#define mod 998244353
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static int buf[20],len; len=0;
	if(x<0)x=-x,putchar('-');
	for(;x;x/=10)buf[len++]=x%10;
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
const int inv2=(mod+1)/2;
std::vector<int>nxt[maxn];
int dist1[maxn],dist2[maxn],dep[maxn];
ll f[maxn][3][3],tmp[3][3];
int n,S,T,L;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void dfs(int now,int fa,int* dep)
{
	for(int x:nxt[now])
		if(x!=fa){
			dep[x]=dep[now]+1;
			dfs(x,now,dep);
		}
}
void dp(int now,int fa)
{
	dep[now]=0;
	for(int x:nxt[now])
		if(x!=fa){
			dp(x,now);
			dep[now]=max(dep[now],dep[x]);
		}
	if(dep[now])f[now][0][0]=1;
	else f[now][1][1]=1;
	for(int x:nxt[now])
		if(x!=fa){
			memset(tmp,0,sizeof(tmp));
			int flag=(dep[x]==dep[now]);
			for(int i=0;i<3;i++)
				for(int j=0;j<3;j++)
					for(int k=0;k<3;k++)
						for(int l=0;l<3;l++)
							if(!flag)tmp[i][j]=(tmp[i][j]+3*f[now][i][j]*f[x][k][l])%mod;
							else{
								tmp[i][j]=(tmp[i][j]+f[now][i][j]*f[x][k][l])%mod;
								tmp[min(i+k,2)][j]=(tmp[min(i+k,2)][j]+f[now][i][j]*f[x][k][l])%mod;
								tmp[i][min(j+l,2)]=(tmp[i][min(j+l,2)]+f[now][i][j]*f[x][k][l])%mod;
							}
			memcpy(f[now],tmp,sizeof(tmp));
		}
	++dep[now];
}
int main()
{
	n=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		nxt[x].push_back(y); nxt[y].push_back(x);
	}
	dist1[1]=0;
	dfs(1,-1,dist1);
	S=1;
	for(int i=2;i<=n;i++)
		if(dist1[i]>dist1[S])S=i;
	dist1[S]=0;
	dfs(S,-1,dist1);
	T=1;
	for(int i=2;i<=n;i++)
		if(dist1[i]>dist1[T])T=i;
	dist2[T]=0;
	dfs(T,-1,dist2);
	L=dist1[T];
	if(L&1){
		int C1=0,C2=0;
		for(int u=1;u<=n;u++)
			for(int v:nxt[u])
				if(dist1[u]==L/2&&dist2[v]==L/2){
					C1=u; C2=v;
					break;
				}
		dp(C1,C2); dp(C2,C1);
		ll sum1=(f[C1][1][0]+f[C1][1][1]+f[C1][1][2])%mod,sum2=(f[C2][0][1]+f[C2][1][1]+f[C2][2][1])%mod;
		writeln(sum1*sum2%mod);
	}
	else{
		int C=0;
		for(int i=1;i<=n;i++)
			if(dist1[i]==L/2&&dist2[i]==L/2){
				C=i; break;
			}
		dp(C,-1);
		writeln(f[C][1][1]*inv2%mod);
	}
	// for(int i=1;i<=n;i++){
	// 	for(int j=0;j<3;j++)
	// 		for(int k=0;k<3;k++)
	// 			writesp(f[i][j][k]);
	// 	putchar('\n');
	// }
	return 0;
}

Measured memory_bytes: 36352
#include<iostream>

using namespace std;

int N,A,B,C,X;
int data[100];
 
int solve(){
  int res = 0;
  int p = 0;
  while(1){
    if(data[p]==X)p++;
    if(p==N)return res;
    res++;
    X=(A*X+B)%C;
    if(res>10000)return -1;
  }
  return res;
}
 
int main(){

  int i;
  
  while(1){
    cin>> N >> A >> B >> C>> X;
    if(N==0&&B==0&&C==0&&X==0)
      break;

    for(i=0;i<N;i++){
      cin>>data[i];
    }
    cout << solve() << endl;
  }
  return 0;
}


Measured memory_bytes: 3000
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int k = sc.nextInt();

		if((b- a) <(2 *k)) {
			for(int i =a; i <=b;i++) {
				System.out.println(i);
			}
		}else {
			for(int i = a; i < a +k;i++) {
				System.out.println(i);
			}
			for(int i = b-k +1; i <= b;i++) {
				System.out.println(i);
			}
		}
	}
}

Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  long long ans ;
  ans = 0;
  for ( int i = 1 ; i <= N ; i++ ){
    if ( i % 5 != 0 && i % 3 != 0 ) {
    ans += i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <math.h>
#include <assert.h>

using namespace std;

#define x first
#define y second
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define SZ(x) int(x.size())
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b-1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
#define ll long long
#define inf 1000000007
#define mod 1000000007
#define N 200005

template<typename U, typename V> void Min(U &a, const V & b){if(a > b)a = b;}
template<typename U, typename V> void Max(U &a, const V & b){if(a < b)a = b;}
template<typename U, typename V> void add(U &a, const V & b){a = (a + b) % mod;}
template<typename U> U gcd(U a, U b){
    if(a == 0)return b;
    if(b == 0)return a;
    if(a >= b)return gcd(a % b, b);
    else return gcd(a, b % a);
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int pow(int a, int b, int c){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % c;
        a = 1LL * a * a % c;
        b >>= 1;
    }
    return ans;
}

char s[305][305];
int a[305][305];
int fill(int i, int l, int r, int k){
    rep(j, l, r+1)if(a[i][j] && a[i][j] != k)return 0;
    rep(j, l, r+1)a[i][j] = k;
    return 1;
}
int vis[N];
int main(){
    int T, i, j, k, ca = 0, K, n, m;
    scanf("%d%d%d", &n, &m, &K);
    rep(i, 0, n)scanf("%s", s[i]);
    int sz = 0;
    rep(i, 0, n){
        rep(j, 0, m){
            if(s[i][j] == '#'){
                a[i][j] = ++sz;
                int x = j - 1;
                while(x >= 0 && !a[i][x] && s[i][x] == '.')a[i][x--] = sz;
                x = j + 1;
                while(x < m && !a[i][x] && s[i][x] == '.')a[i][x++] = sz;
            }
        }
    }
    rep(i, 0, n){
        rep(j, 0, m){
            k = a[i][j];
            if(!k || vis[k])continue;
            vis[k] = 1;
            int l = j, r = j;
            while(r < m && a[i][r] == k)r++;
            r--;
            int x = i+1;
            while(x < n && fill(x, l, r, k))x++;
            j = r;
        }
    }
    memset(vis, 0, sizeof(vis));
    per(i, 0, n){
        rep(j, 0, m){
            k = a[i][j];
            if(!k || vis[k])continue;
            vis[k] = 1;
            int l = j, r = j;
            while(r < m && a[i][r] == k)r++;
            r--;
            int x = i-1;
            while(x >= 0 && fill(x, l, r, k))x--;
            j = r;
        }
    }
    rep(i, 0, n){
        rep(j, 0, m)printf("%d ", a[i][j]);puts("");
    }
}


Measured memory_bytes: 2048
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n, m, x;
  cin >> n >> m >> x; x--;
  VI a(m), b(n, 0);
  REP(i, m) {
    cin >> a[i], a[i]--;
    b[a[i]] = 1;
  }

  int sum = 0;
  FOR(i, x, n) {
    sum += b[i];
  }
  int ret = 0;
  for(int i=x; i>=0; --i) {
    ret += b[i];
  }
  cout << min(sum, ret) << endl;

  return 0;
}


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

using namespace std;

#define endl '\n'

typedef long long int64;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
const int maxn = 2000 + 5;

int n, k;
int answer;
int dp[ maxn ][ maxn ];
int sm[ maxn ][ maxn ];
int size[ maxn ];
vi adj[ maxn ];

int solve(int u, int p){
	size[ u ] = 1;
	for (auto v : adj[ u ]) if (v != p){
		size[ u ] += solve(v, u);
		sm[u][0] += size[v];
		for (int i = 0; i <= size[v]; ++i)
			sm[u][i + 1] = min( sm
				[u][i + 1] + dp[v][i], oo);
	}

	memset(dp[u], oo, sizeof dp[u]);
	dp[u][0] = size[u] - 1;

	for (auto v : adj[u]) if (v != p){
		for (int i = 1; i <= min(size[v], k); ++i){
			int j = min(i, k - i);			
			dp[u][i] = min( dp[u][i], 
							dp[v][i - 1] + sm[u][j] - 
							(j == 0 ? size[v] : dp[v][j - 1]) );
		}
	}

	int limit = min( size[u], k );
	for (int i = 1; i <= limit; ++i)
		dp[u][i] = min( dp[u][i], dp[u][i - 1] );
	answer = min(answer, dp[u][limit] + n - size[u]);


	return size[ u ];
}

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

#ifdef MARX
	freopen("data.in", "r", stdin);
	// freopen("data.out", "w", stdout);
#endif

	cin >> n >> k;

	for (int i = 1; i < n; ++i){
		int u, v; cin >> u >> v;
		adj[ u ].push_back( v );
		adj[ v ].push_back( u );
	}

	answer = n - 1;

	solve(1, -1);

	cout << answer << endl;

	return 0;
}

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

int main()
{
	int a, b;
	cin >> a >> b;
	int ans = 0;
	for(auto i = a; i <= b; ++i){
		string s = to_string(i);
		string t = s;
		reverse(t.begin(), t.end());
		if(s == t) ++ans;
	}
	cout << ans << 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 SIZE 300005
#define MOD 998244353LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}

template<int N, typename T, T M>
struct ModFact {
    T fact[N+1];
    T ifact[N+1];
    constexpr ModFact() : fact(), ifact() {
        fact[0] = 1;
        for (int i=0; i<N; ++i)
            fact[i+1] = (fact[i]*(i+1))%M;
        ifact[N] = power(fact[N], M-2);
        for (int i=N-1; i >= 0; --i)
            ifact[i] = (ifact[i+1]*(i+1))%M;
    }
    constexpr T power(T a, T b) {
        T r = 1;
        while (b>0) {
            if((b&1)!=0) r = (r*a)%M;
            a = (a*a)%M;
            b >>= 1;
        }
        return r;
    }
    constexpr T comb(T n, T r) {
        return (((fact[n]*ifact[r])%M)*ifact[n-r])%M;
    }
};
 
ModFact<300000, ll, MOD> fact;

int main() {
    fastio();
    ll N, A, B, K, ans = 0;
	cin >> N >> A >> B >> K;
    ll g = gcd(A, B);
    if(K%g==0) {
        ll s, ca=B/g, cb=A/g;
        int i, j;
        for (i=0, j=N; i<=N && i*A<=K; i++) {
            while ((s=i*A+j*B)>K) j--;
            if (s==K) break;
        }
        while(i<=N && j>=0) {
            ans += fact.comb(N,i)*fact.comb(N,j);
            if(ans > MOD) ans %= MOD;
            i += ca; j -= cb;
        }
    }
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256