akhauriyash/Code-Regression huggingface dataset:
import sys
def input():
    return sys.stdin.readline()[:-1]

from itertools import count
from collections import Counter

def test():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    mxn = a[-1]
    c = Counter(a)
    a = sorted(list(set(a)))
    r = dict()
    for i in a:
        for j in count(1):
            if i * j > mxn: break
            r[i * j] = r.get(i * j, 0) + 1
    print(len([k for k in a if r[k] == 1 and c[k] == 1]))


test()

Measured memory_bytes: 218368
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

const int N=300+3;
const int p=1e9+7;

int C[N][N],F[N][N],G[N][N][N],pw[N][N],iv[N][N];
int n,m,res;

int Pow(int a,int b){
	int res=1;
	for (;b;b>>=1,a=1ll*a*a%p) if (b&1) res=1ll*res*a%p;
	return res;
}

int main(){
	For(i,0,N){
		C[i][0]=1;
		For(j,1,i+1) C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
	For(i,0,N) For(j,0,N){
		pw[i][j]=Pow(i,j);
		iv[i][j]=Pow(pw[i][j],p-2);
	}
	n=IN(),m=IN();
	For(a,1,n+1){
		For(b,0,m+1){
			F[a][b]=pw[a][b];
			For(i,1,a){
				F[a][b]=(F[a][b]-1ll*G[a][i][b]*pw[a-i][b]%p+p)%p;
			}
		}
		For(i,a+1,n+1){
			For(j,0,m+1){
				G[i][a][j]=((!j?0:G[i][a][j-1])+1ll*C[i-1][a-1]*iv[i-a][j]%p*F[a][j])%p;
			}
		}
	}
	printf("%d\n",F[n][m]);
}

Measured memory_bytes: 55936
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>

using namespace std;

struct Cake {
	long long x, y, z;
};

int main()
{
	long long N, M, ans = 0;
	cin >> N >> M;

	long long xx, yy, zz;
	vector<Cake> cakes(N);
	for (int i = 0; i < N; i++) {
		cin >> xx >> yy >> zz;
		cakes[i].x = xx;
		cakes[i].y = yy;
		cakes[i].z = zz;
	}

	for (int i = -1; i < 2; i += 2) {
		for (int j = -1; j < 2; j += 2) {
			for (int k = -1; k < 2; k += 2) {
				//sort(cakes.begin(), cakes.end(), [=](Cake l, Cake r) {return i*l.x != i*r.x ? (i*l.x > i*r.x) : j*l.y != j*r.y ? (j*l.y > j*r.y) : (k*l.z > k*r.z);});
				sort(cakes.begin(), cakes.end(), [=](Cake l, Cake r) {return (i*l.x + j*l.y + k*l.z > i*r.x + j*r.y + k*r.z); });
				/*
				cout << '(' << i << ',' << j << ',' << k << ')' << endl;
				for (int h = 0; h < N; h++) {
					cout << cakes[h].x << ',' << cakes[h].y << ',' << cakes[h].z << endl;
				}
				*/
				long long Max = 0;
				for (int h = 0; h < M; h++) {
					Max += i*cakes[h].x + j*cakes[h].y + k*cakes[h].z;
				}
				if (Max > ans) ans = Max;
			}
		}
	}

	cout << ans;

	char qq;
	cin >> qq;
	return 0;
}

Measured memory_bytes: 256
#define scanf_s scanf
#include <stdio.h>
#include <string>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <iostream>
using namespace std;
#define MAE 4280
#define MAX 100
int main() 
{
	int w, ans = 0, m[5] = { 10,20,30}, n[5] = { 1150,125,140,160 };
	while (1) {
		scanf_s("%d", &w);
		if (w == -1) break;
		ans = n[0];
		if (m[0] < w) ans += (w - m[0] > 10 ? 10 : w - m[0]) * n[1];
		if (m[1] < w) ans += (w - m[1] > 10 ? 10 : w - m[1]) * n[2];
		if (m[2] < w) ans += (w - m[2]) * n[3];
		printf("%d\n", MAE - ans);
	}
}

Measured memory_bytes: 1188
import java.util.Scanner;


public class Main {
	
	final int ny = 19*5+20*5;
	final int sy = 20*10;
	
	final long mill = tonum(1000, 1, 1);
	
	long ytod(int y) {
		y = y-1;
		int last = y%3;
		return (y/3)*(ny+ny+sy) + last * ny;
	}
	
	long mtod(int y, int m) {
		m = m-1;
		if(y % 3 == 0) {
			return m * 20;
		} else {
			int mm = m/2;
			return (m-mm) * 20 + mm * 19;
		}
	}
	
	long tonum(int y, int m, int d) {
		return ytod(y) + mtod(y,m) + d-1;
	}
	
	long solve(int y, int m, int d) {
		return mill - tonum(y,m,d);
	}
	
	public Main() {
		Scanner scanner = new Scanner(System.in);
		
		while(scanner.hasNext()) {
			int n = scanner.nextInt();
			for(int i=0; i<n; i++) {
				int y = scanner.nextInt();
				int m = scanner.nextInt();
				int d = scanner.nextInt();
				System.out.println(solve(y,m,d));
			}
		}
		
		scanner.close();
	}
	
	public static void main(String[] args) {
		new Main();
	}

}

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

UL N,K;
LL L,R;
LL A[40]={};
LL X[21][1048576]; UL Xp[21]={};
LL Z[21][1048576]; UL Zp[21]={};

int main() {
 scanf("%u%u",&N,&K);
 scanf("%lld%lld",&L,&R);
 rep(i,N) scanf("%lld",&A[i]);
 X[0][0]=Z[0][0]=0;
 Xp[0]=Zp[0]=1;
 rep(n,20){
  if(!A[n]) continue;
  for(UL k=n; k!=~0u; k--){
   rep(i,Xp[k]){
    X[k+1][Xp[k+1]]=X[k][i]+A[n];
    Xp[k+1]++;
   }
  }
 }
 rep(n,20){
  if(!A[n+20]) continue;
  for(UL k=n; k!=~0u; k--){
   rep(i,Zp[k]){
    Z[k+1][Zp[k+1]]=Z[k][i]+A[n+20];
    Zp[k+1]++;
   }
  }
 }
 rep(i,20) sort(X[i],X[i]+Xp[i]);
 rep(i,20) sort(Z[i],Z[i]+Zp[i]);
 
 ULL ans=0;
 
 rep(x,21) rep(z,21) {
  if(x+z!=K) continue;
  if(Xp[x]==0) continue;
  if(Zp[z]==0) continue;
  ULL tmp=0;
  UL Rq=Zp[z];
  UL Lq=Zp[z];
  rep(p,Xp[x]) {
   while(Lq) if(X[x][p]+Z[z][Lq-1]>=L) Lq--; else break;
   while(Rq) if(X[x][p]+Z[z][Rq-1]>R) Rq--; else break;
   ans+=Rq-Lq;
  }
 }
 printf("%llu\n",ans);
 return 0;
}



Measured memory_bytes: 19720
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int result = 0;
int i, j;
int n, m, k;
int s[100005] = {};
int s2[100005] = {};
int plus[100005] = {};
int memo=0;
char word[105][15];

int gcd(int a, int b) {
	if (a < b) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main() {
	
	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%d", &s[i]);
		s2[i] =s[i] - m;
		
	}
	for (i = 1; i < n; i++) {
		s2[0]=gcd(s2[0], s2[i]);
	}
  if (s2[0] < 0)s2[0] = -s2[0];
	printf("%d", s2[0]);
}

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

int main(){
  vector<int> v;

  for (int i = 0; i < 3; i++) {
    int x;
    cin >> x;
    v.push_back(x);
  }

  sort(v.rbegin(), v.rend());

  int ans = 0;
  while (true) {
    if (v[0] == v[1] && v[1] == v[2]) {
      break;
    }
    ans++;
    v[2]++;
    sort(v.rbegin(), v.rend());
    v[2]++;
    sort(v.rbegin(), v.rend());
  }

  cout << ans << endl;

  return 0;
}

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

int a[1000005], cnt = 1;
int main(){
  int s;
  cin >> s;
  while (true){
    if (a[s]){
      cout << cnt << '\n';
      return 0;
    }
    cnt++;
    a[s] = 1;
    if (s & 1) s = 3 * s + 1;
    else s = s/2;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//BEGIN CUT HERE
vector<int> knuth_morris_pratt(const string &s){
  int n=s.size();
  vector<int> kmp(n+1,-1),mp(n+1,-1);
  for(int i=0,j=-1;i<n;i++){
    while(~j&&s[i]!=s[j]) j=kmp[j];
    kmp[i+1]=mp[i+1]=++j;
    if(i+1<n&&s[i+1]==s[j]) kmp[i+1]=kmp[j];
  }
  return mp;
}
//END CUT HERE

//INSERT ABOVE HERE
signed ABC135_D(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  string s,t;
  cin>>s>>t;

  int n=s.size(),m=t.size();

  string b;
  while(b.size()<t.size()) b+=s;
  auto mp=knuth_morris_pratt(t+'$'+b+b);

  vector<int> match(n);
  for(int i=m+1;i<=m+n;i++)
    match[i-(m+1)]=mp[i+m]==m;

  vector< vector<int> > G(n);
  for(int i=0;i<n;i++)
    if(match[i]) G[i].emplace_back((i+m)%n);

  vector<int> indeg(n,0);
  for(int i=0;i<n;i++)
    for(int j:G[i]) indeg[j]++;

  queue<int> que;
  for(int i=0;i<n;i++)
    if(indeg[i]==0) que.emplace(i);

  vector<int> dp(n,0);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int u:G[v]){
      chmax(dp[u],dp[v]+1);
      indeg[u]--;
      if(indeg[u]==0) que.emplace(u);
    }
  }

  for(int i=0;i<n;i++){
    if(indeg[i]!=0){
      cout<<-1<<endl;
      return 0;
    }
  }

  cout<<*max_element(dp.begin(),dp.end())<<endl;
  return 0;
}
signed main(){
  ABC135_D();
  return 0;
}


Measured memory_bytes: 45228
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <map>
#include <math.h>
#include <numeric>
#include <list>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll power(ll x,ll y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);
 
}
int main()
{
ll n;
cin>>n;
ll ar[1000];
ll i;
for(i=0;i<n;i++)
cin>>ar[i];
ll mini=1000000000000;
ll count=0;
for(ll k=-100;k<=100;k++)
{
	count=0;
	for(i=0;i<n;i++)
		count+=power(abs(k-ar[i]),2);
	if(count<mini)
	mini=count;	
}
cout<<mini;
return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
ll MOD = 1e9+7;
ll INF = 1e18;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }

int main(){
  ll i, j;
  ll a, b;
  cin >> a >> b;
  if(a <= 8 && b <= 8)
    cout << "Yay!" << endl;
  else
    cout << ":(" << endl;//てすと

  return 0;
}


Measured memory_bytes: 256
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import numpy as np
import statistics
import string
import sys
from array import array
from collections import deque
from functools import wraps
import time

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

N, M = splitintinput()
A = listintinput()

day = sum(A)
if N < day:
    print(-1)
else:
    print(N-day)

Measured memory_bytes: 27948
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int output = 1;
  while(true){
    int temp = output*2;
    if(temp>N){
      cout << output << endl;
      break;
    }
    output = temp;
  }
  
}

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

int main() {
	//入力
	int A, B;
	cin >> A >> B;

	if (A < B) swap(A, B);

	//処理
	int ans = max(A + B, A + A - 1);

	//出力
	cout << ans << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-9;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
    int a,b,c,d;cin>>a>>b>>c>>d;
    if((abs(a-b)<=d&&abs(c-b)<=d)||abs(a-c)<=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int h,w;
  cin>>h>>w;
  vector<string>s(h);
  for(int i=0;i<h;i++)
  {
    cin>>s[i];
  }
  int count=0;
  for(int i=0;i<h;i++)
  {
    for(auto x:s[i])count+=(x=='#');
  }
  if(count==(h+w-1))cout<<"Possible"<<endl;
  else cout<<"Impossible"<<endl;
  return 0;
}

Measured memory_bytes: 256
//Wanna go back home

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end()
#define pb push_back
const int inf = 2147483647;

int main (){
    string s;cin>>s;
    int flag = 0;
    if(s.find("N")==string::npos)flag+=10;
    if(s.find("S")==string::npos)flag-=10;
    if(s.find("W")==string::npos)flag++;
    if(s.find("E")==string::npos)flag--;
    cout << (flag==0 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    N=int(input())
    A=sorted(list(map(int,input().split())))
    ans=1
    if 0 in A:
        print(0)
        return
    for i in range(N):
        ans*=A[i]
        if ans>10**18:
            print(-1)
            return
    print(ans)
main()

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

int main(){
  int x[5];
  for(int i=0; i<5; i++)
  	cin >> x[i];
  for(int i=0; i<5; i++){
  if(x[i]==0)
    cout << i+1 << endl;
  }
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
int f[100001][4],a[100001][4];
int main()
{
        int i,n,j,k;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
                scanf("%d %d %d",&a[i][1],&a[i][2],&a[i][3]);
        }
        for(i=1;i<=n;i++)
        {
                for(j=1;j<=3;j++)
                {
                        for(k=1;k<=3;k++)
                        {
                                if(k==j)
                                        continue;
                                f[i][j]=max(f[i][j],f[i-1][k]+a[i][j]);
                        }
                }
        }
        printf("%d",max(f[n][1],max(f[n][2],f[n][3])));
        return 0;
}


Measured memory_bytes: 3328
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
        k: usize,
        n: usize,
        mut a: [usize; n],
    }
    let mut b = a.iter().map(|ai| ai + k).collect::<Vec<_>>();
    a.append(&mut b);
    let mut ans = k;
    for i in 0..n {
        ans = ans.min(a[n - 1 + i] - a[i]);
    }
    println!("{}", ans);
}


Measured memory_bytes: 7996
s=input()
k=int(input())
substrings=set()
for i in range(len(s)):
    for j in range(5):
        if i+j<len(s):
            substrings.add(s[i:i+j+1])
substrings=sorted(list(substrings))
print(substrings[k-1])
            

Measured memory_bytes: 4592
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace Program
{
    public class ABC125B
    {
        static class Console_
        {
            private static Queue<string> param = new Queue<string>();
            public static int NextInt() => int.Parse(NextString());
            public static string NextString()
            {
                if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item);
                return param.Dequeue();
            }
        }

        static public void Main(string[] args)
        {
            var N = Console_.NextInt();
            var Vary = new int[N];
            for (int i = 0; i < N; ++i)
            {
                Vary[i] = Console_.NextInt();
            }
            for (int i = 0; i < N; ++i)
            {
                Vary[i] -= Console_.NextInt();
                if (Vary[i] < 0)
                {
                    Vary[i] = 0;
                }
            }

            Console.WriteLine(Vary.Sum());
        }
    }
}


Measured memory_bytes: 11348
#include <bits/stdc++.h>
using namespace std;
int N;
typedef long long ll;
typedef pair<int,int> P;

P f(int x){
    int a = x%10;
    int b = 0;
    while(x){
        b=x;
        x /= 10;
    }
    return P(a,b);
}


int main(){
    cin >> N;
    map<P,int> freq;
    for(int i = 1;i<=N;i++){
        P p = f(i);
        freq[p]++;
    }
    ll ans = 0;
    for(int i = 1;i<=N;i++){
        P p = f(i);
        P q(p.second, p.first);
        ans += freq[q];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <chrono>
#include <queue>
#include <functional>

#define out(t) cout << (t) << "\n"

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;

int popcount(uint x) {
    x -= x >> 1 & 0x55555555;
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = x + (x >> 4) & 0x0F0F0F0F;
    return x * 0x01010101 >> 24;
}

int tzcnt(uint x) {
    return popcount(~x & x - 1);
}

struct Point {
    int x, y;

    Point(int p, int q) : x(p), y(q) {}
};

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

    int n;
    cin >> n;

    vector<int> arr;
    arr.reserve(n);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    int m = arr[arr.size() - 1];

    cout << m << " ";

    int c = 0;

    for (int i = arr.size() - 2; i >= 0; --i) {
        if (arr[i] <= m / 2 || m - arr[i] <= m / 2) {
            c = abs(m / 2 - c) > abs(m / 2 - arr[i]) ? arr[i] : c;
        }
    }

    out(c);

    int aaa;
    cin >> aaa;
}

Measured memory_bytes: 640
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <utility>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define MOD 1000000007

int main(int argc, char const *argv[]) {
  long N,M;
  cin >> N >> M;
  if(N*2 >= M){
    cout << ((M-M%2)/2) << endl;
  }else{
    long amari = M - N*2;
    long ans = N + (amari - amari%4)/4;
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
package main

import(
	"os"
	"bufio"
	"strconv"
	"fmt"
)

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	a, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	b, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	c, _ := strconv.Atoi(sc.Text())
	if a < b && a < c && a < c{
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1092
use std::io;

fn main() {
    loop {
        let numbers = input_number();
        let h = numbers[0] as usize;
        let w = numbers[1] as usize;
        if h == 0 && w == 0 { break }
        for index in 0..h {
            if index == 0 || index == h - 1 {
                println!("{}", "#".repeat(w));
            } else {
                println!("#{}#", ".".repeat(w - 2));
            }
        }
        println!("");
    }
}

#[allow(dead_code)]
fn input_number() -> Vec<i64> {
    let mut input = String::new();

    io::stdin().read_line(&mut input)
        .expect("Failed to read line");

    let vec: Vec<i64> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap_or(0))
        .collect();
    vec
}



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


int main() {
	int a,b,c,d;
    cin >> a >> b >> c >> d;
    for(int i=0; i<200; i++){
        if(i%2==0){
            c-=b;
            if(c<=0){
             cout << "Yes" << endl;
             break;
            }
        }
        if(i%2==1){
            a-=d;
            if(a<=0){
             cout << "No" <<endl;
             break;
            }
        }
    }
}

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

int main() {
  int a,b,c;cin>>a>>b>>c;
  for(int i=1;i<b;i++){
    int d=a*i;
    if(d%b==c){
      cout<<"YES"<<endl;
      return 0;
    }
  }
  cout<<"NO"<<endl;
}

Measured memory_bytes: 3580
#define _GLIBCXX_DEBUG
#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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  map<int,int> mp;
  rep(i,n){
    mp[a[i]]++;
  }
  ll sum=0;
  for(auto c:mp){
    sum+=c.second-1;
  }
  if(sum%2==0){
    cout << mp.size() << endl;
  }
  else{
    cout << mp.size()-1 << endl;
  }
  
}

Measured memory_bytes: 5376
n=int(input())
a,b=map(int,input().split())
f=0
if n==1:
    f=1
    print("OK")
else:
    for i in range(a,b+1):
        if i%n==0:
            print("OK")
            f=1
            break
if f==0:
    print("NG")

Measured memory_bytes: 61620
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

lli h, w, a, b;

int main(void){
    cin >> h >> w >> a >> b;
    vector<lli> r(h), c(w);
    vector<string> ans(h);
    rep(i, h){
        if(i < b){
            string t(a, '0');
            string u(w-a, '1');
            ans[i] = t+u;
        }else{
            string t(a, '1');
            string u(w-a, '0');
            ans[i] = t+u;
        }
    }
    rep(i, h) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 4604
from collections import defaultdict
s = input()[::-1]
mod = 13
p = 10 ** 9 + 7
dic = defaultdict(int)
dic[0] = 1

for i in range(len(s)):
    tmp = defaultdict(int)
    if s[i] == "?":
        for j in range(10):
            d = j * pow(10, i, mod)
            for k, v in dic.items():
                tmp[(k + d) % mod] += v
                tmp[(k + d) % mod] %= p
    else:
        d = int(s[i]) * pow(10, i, mod)
        for k, v in dic.items():
            tmp[(k + d) % mod] = v
    dic = tmp
print(dic[5] % p)


Measured memory_bytes: 44892
#include <iostream>
#include <algorithm>

#define MAXN 100

using namespace std;

int C[3][3];
int A[3], B[3];

int main()
{
  for ( int i = 0; i < 3; ++i ) for ( int j = 0; j < 3; ++j ) scanf("%d", &C[i][j]);

  for ( int i = 0; i <= C[0][0]; ++i ) {
    int b1, b2, b3;
    b1 = C[0][0]-i; b2 = C[0][1]-i; b3 = C[0][2]-i;

    if ( C[1][0]-b1 == C[1][1]-b2 && C[1][0]-b1 == C[1][2]-b3 && C[2][0]-b1 == C[2][1]-b2 && C[2][0]-b1 == C[2][2]-b3) {
      cout << "Yes\n";
      break;
    }
    if ( i == C[0][0] ) cout << "No\n";
  }
  
}


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

const int NIL = -1;

template <typename T> struct Node { T parent = NIL, left = NIL, right = NIL; };

template <typename T> T getRoot(const std::vector<Node<T>> &t) {
  for (std::size_t i = 0; i < t.size(); ++i) {
    if (t.at(i).parent == NIL)
      return i;
  }
  return NIL;
}

template <typename T>
void printPreorder(const std::vector<Node<T>> &t, T u=0){
  if (u!=NIL) {
    std::cout << " " << u;
    printPreorder(t, t.at(u).left);
    printPreorder(t, t.at(u).right);
  }
}

template <typename T>
void printInorder(const std::vector<Node<T>> &t, T u=0){
  if (u!=NIL) {
    printInorder(t, t.at(u).left);
    std::cout << " " << u;
    printInorder(t, t.at(u).right);
  }
}

template <typename T>
void printPostorder(const std::vector<Node<T>> &t, T u=0){
  if (u!=NIL) {
    printPostorder(t, t.at(u).left);
    printPostorder(t, t.at(u).right);
    std::cout << " " << u;
  }
}

int main() {
  int n;
  std::cin >> n;
  std::vector<Node<int>> t(n, Node<int>{});

  int u, l, r;
  for (int i = 0; i < n; ++i) {
    std::cin >> u >> l >> r;
    t.at(u).left = l;
    t.at(u).right = r;
    if (l != NIL)
      t.at(l).parent = u;
    if (r != NIL)
      t.at(r).parent = u;
  }

  const int root = getRoot(t);

  std::cout << "Preorder" << std::endl;
  printPreorder(t, root);
  std::cout << std::endl;
  std::cout << "Inorder" << std::endl;
  printInorder(t, root);
  std::cout << std::endl;
  std::cout << "Postorder" << std::endl;
  printPostorder(t, root);
  std::cout << std::endl;
}



Measured memory_bytes: 3092
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<functional>
#include<vector>
#include<queue>
using namespace std;
#define f(i,n) for(int i=0;i<(int)n;i++)
#define MOD 1000000009

long long n;
int c[200001];
int bit[200001];

long long sum(long long i){
	long long s = 0;
	while (i > 0){
		s += bit[i];
		i -= i&-i;
	}
	return s;
}

void add(long long i, long long x){
	while (i <= n){
		bit[i] += x;
		i += i&-i;
	}
}


int main(void){
	char a[200010];
	f(i, 200010)a[i] = 0;
  f(i,200001)bit[i]=0;
	vector<long long>b[26];
	int k = 0;
	long long x;
	long long ans = 0;

	scanf("%s", a);
	n = strlen(a);

	f(i, n){
		b[a[i] - 97].push_back(i);
	}
	f(i, 26){
		if (b[i].size() % 2 == 1)k++;
	}

	if (k>1)printf("-1\n");
	else {
		f(i, 26){
			for (int j = 0; j < b[i].size(); j++){
				c[n - b[i][b[i].size() - j - 1]-1] = b[i][j]+1;
			}
		}
		f(i, n){
			ans += (i-sum(c[i]));
			add(c[i], 1);	
		}
		ans=ans/2;
		printf("%lld\n", ans);
	}


	return 0;
}


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

namespace AtCoder {

    class Program {

        static List<int> Coef(List<int> list, bool reverse) {

            var ret = new List<int>();
            var N = list.Count;

            if(N % 2 == 0) {

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

                    if (i == 0) {

                        ret.Add(1);
                    } else if (i == N - 1) {

                        ret.Add(-1);
                    } else if (i % 2 != 0) {

                        ret.Add(-2);
                    } else {

                        ret.Add(2);
                    }
                }

            } else {

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

                    if (i == 0 || i == N - 1) {

                        ret.Add(1);
                    } else if (i % 2 != 0) {

                        ret.Add(-2);
                    } else {

                        ret.Add(2);
                    }
                }
            }

            if(!reverse) {

                return ret.Select(e => e - e * 2).ToList();
            }
            return ret;
        }

        static void Main(string[] args) {

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

            var A = new List<int>();
            for(int _i = 0; _i < N; _i++) {

                A.Add(int.Parse(Console.ReadLine()));
            }
            A.Sort();

            var test1 = Coef(A, false);
            var test2 = Coef(A, true);

            test1.Sort();
            test2.Sort();

            var res1 = 0L;
            for (int i = 0; i < N; i++) {

                res1 += A[i] * test1[i];
            }
            var res2 = 0L;
            for (int i = 0; i < N; i++) {

                res2 += A[i] * test2[i];
            }

            Console.WriteLine(Math.Max(res1, res2));
        }
    }
}


Measured memory_bytes: 19424
#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
	modint sqr() { return (*this).operator*(n); }
};

#endif // ___CLASS_MODINT

#include <queue>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;
const long long inf = 1LL << 61;
using modulo = modint<1000000007>;
struct edge {
	int to, cost;
};
struct state {
	int pos; long long cost;
};
bool operator>(const state& s1, const state& s2) {
	return s1.cost > s2.cost;
}
struct answer {
	vector<long long> dist;
	vector<modulo> comb;
};
answer shortest_path(int src, vector<vector<edge> > &G) {
	int N = G.size();
	vector<long long> dist(N, inf); dist[src] = 0;
	vector<modulo> comb(N); comb[src] = 1;
	vector<bool> vis(N);
	priority_queue<state, vector<state>, greater<state> > que;
	que.push(state{ src, 0 });
	while (!que.empty()) {
		state u = que.top(); que.pop();
		if (vis[u.pos]) continue;
		vis[u.pos] = true;
		for (edge e : G[u.pos]) {
			if (dist[e.to] > dist[u.pos] + e.cost) {
				dist[e.to] = dist[u.pos] + e.cost;
				comb[e.to] = 0;
				que.push(state{ e.to, dist[e.to] });
			}
			if (dist[e.to] == dist[u.pos] + e.cost) {
				comb[e.to] += comb[u.pos];
			}
		}
	}
	return answer{ dist, comb };
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, M, S, T;
	cin >> N >> M >> S >> T; --S, --T;
	vector<vector<edge> > G(N);
	for (int i = 0; i < M; ++i) {
		int U, V, D;
		cin >> U >> V >> D; --U, --V;
		G[U].push_back(edge{ V, D });
		G[V].push_back(edge{ U, D });
	}
	answer TKHS = shortest_path(S, G);
	answer AOKI = shortest_path(T, G);
	modulo ans = (TKHS.comb[T]).sqr();
	long long d = TKHS.dist[T];
	for (int i = 0; i < N; ++i) {
		if (TKHS.dist[i] == AOKI.dist[i] && TKHS.dist[i] + AOKI.dist[i] == d) {
			ans -= (TKHS.comb[i] * AOKI.comb[i]).sqr();
		}
		for (edge e : G[i]) {
			if (TKHS.dist[i] * 2 < d && AOKI.dist[e.to] * 2 < d && TKHS.dist[i] + AOKI.dist[e.to] + e.cost == d) {
				ans -= (TKHS.comb[i] * AOKI.comb[e.to]).sqr();
			}
		}
	}
	cout << ans.get() << endl;
	return 0;
}

Measured memory_bytes: 14404
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let K: usize = sc.get();
    let A: usize = sc.get();
    let B: usize = sc.get();
    if K == 1 || A % K == 0 || B % K == 0 || K - A % K <= B - A {
        println!("OK");
    } else {
        println!("NG");
    }
}


Measured memory_bytes: 2108
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
	int n;
	ll h;
	cin >> n >> h;
	vector<ll> a(n), b(n);
	rep(i, n) cin >> a[i] >> b[i];
	ll amax = 0;
	rep(i, n) {
		if (a[i] > amax) amax = a[i];
	}
	sort(b.begin(), b.end());
	ll ans = 0;
	for (int i = n - 1; i>=0; i--) {
		if(b[i]<=amax) break;
      h -= b[i];
		ans++;
		if (h <= 0) {
			cout << ans << endl;
			return 0;
		}
	}
	if (h%amax == 0) {
		ans += h / amax;
	}
	else {
		ans += h / amax + 1;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
typedef vector<vector<int>> Graph;

vector<ll> cnt;
void dfs(const Graph &g, int a, int b, ll num) {
    cnt[a] = num;
    for(auto na : g[a]) {
        if(na == b)
            continue;
        dfs(g, na, a, num + cnt[na]);
    }
}

int main() {
    int N, Q;
    cin >> N >> Q;
    Graph g(N);
    cnt.assign(N, 0);
    for(int i = 1; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 0; i < Q; ++i) {
        int p, x;
        cin >> p >> x;
        p--;
        cnt[p] += x;
    }
    dfs(g, 0, -1, cnt[0]);
    for(int i = 0; i < N; ++i)
        cout << cnt[i] << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 27392
h,w = map(int,input().split())
a = [[] for _ in range(h)]
for i in range(h):
    a[i] = [int(_) for _ in input().split()]
cnt = 0
res = []
for i in range(h):
    for j in range(w):
        if i != h-1 and a[i][j] % 2 == 1:
            cnt += 1
            res.append([i+1,j+1,i+2,j+1])
            a[i+1][j] += 1
for j in range(w-1):
    if a[h-1][j] % 2 == 1:
        cnt += 1
        res.append([h,j+1,h,j+2])
        a[h-1][j+1] += 1
print(cnt)
for i in range(len(res)):
    for j in range(4):
        print(res[i][j],end='')
        if j < 3:
            print(' ',end='')
        if j == 3:
            print()

Measured memory_bytes: 32040
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (int i = 0; i < n; i++)
#define IREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(a, b) for (int i = a; i < b + 1; i++)
#define all(v) v.begin(), v.end()
#define SENTINEL 2000000000
#define NIL -1
using namespace std;
typedef long long ll;

const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template <class T>inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}

int main()
{
    ll k,n;
    cin >> k >> n;
    ll max=0;
    vector<int> a(n);
    REP(i,n){
        cin >> a[i];
        if(i==0){
            continue;
        }
        if(a[i]-a[i-1]>max){
            max=a[i]-a[i-1];
        }
    }
    if(k-a[n-1]+a[0]>max){
        max = k - a[n - 1] + a[0];
    }
    cout << k-max << endl;
}

Measured memory_bytes: 1152
#include<stdio.h>
int main()
{
    int N;
    scanf("%d",&N);
    if(N%10==2||N%10==4||N%10==5||N%10==7||N%10==9)
    {
        printf("hon");
    }
    else if (N%10==0||N%10==1||N%10==6||N%10==8)
    {
        printf("pon");
    }
    else
    {
        printf("bon");
    }
    return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define inf 1012345678
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define next_permutation nxt_p
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define lower_bound lowb
#define upper_bound upb
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a*b/gcd(a,b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



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

	int h, w;
	cin >> h >> w;
	string fld[h];
	rep(i, h) cin >> fld[i];

	int dp[1010][1010];
	Fill(dp, 0);
	dp[0][0] = 1;

	rep(i, h) {
		rep(j, w) {
			if(fld[i][j] == '#') continue;

			if(i + 1 < h && fld[i + 1][j] == '.') {
				dp[i + 1][j] += dp[i][j];
				dp[i + 1][j] %= MOD;
			}
			if(j + 1 < w && fld[i][j + 1] == '.') {
				dp[i][j + 1] += dp[i][j];
				dp[i][j + 1] %= MOD;
			}
		}
	}

	// rep(i, h) {
	// 	rep(j, w) cout << dp[i][j] << " ";
	// 	cout << endl;
	// }

	cout << dp[h - 1][w - 1] << endl;
	return 0;
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vvint = vector<vint>;
using vvvint = vector<vvint>;
using vdouble = vector<double>;
using vvdouble = vector<vdouble>;
using vvvdouble = vector<vvdouble>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return (a > b && (a = b, true)); }
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return (a < b && (a = b, true)); }
template<typename T>
bool isin(T y, T x, T h, T w) { return (0 <= y && 0 <= x && y < h && x < w); }
template<typename T>
bool isin1(T y, T x, T h, T w) { return (0 < y && 0 < x && y <= h && x <= w); }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	os << v[0];
	for (int i = 1; i < v.size(); i++) os << " " << v[i];
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u; return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}


void Main() {
	int H, W; cin >> H >> W;
	vector<string> S(H); cin >> S;
	
	vvint dp(H, vint(W, INF));
	dp[0][0] = (S[0][0] == '#');
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (dp[i][j] == INF) continue;
			if (i < H-1) chmin(dp[i+1][j], dp[i][j] + (S[i][j] == '.' && S[i+1][j] == '#'));
			if (j < W-1) chmin(dp[i][j+1], dp[i][j] + (S[i][j] == '.' && S[i][j+1] == '#'));
		}
	}
	cout << dp[H-1][W-1] << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout << fixed << setprecision(20);
	Main();
	return (0);
}


Measured memory_bytes: 384
let input = readLine()!.characters.split(" ").map{Int(String($0))!}
let (R, G, B, N) = (input[0], input[1], input[2], input[3])
var ans = 0
for r in 0...N {
    for g in 0...N {
        let b = N - (r*R + g*G)
        if (b >= 0) && (b % B == 0) {
            ans += 1
        }
    }
}
print(ans)

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

using namespace std;

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

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

bool check(ll x) {
    vector<bool> ok(3);
    while (x > 0) {
        int m = x % 10;
        if (m == 3) ok[0] = true;
        else if (m == 5) ok[1] = true;
        else if (m == 7) ok[2] = true;
        x /= 10;
    }
    return (ok[0] && ok[1] && ok[2]);
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int res = 0;
    ll n;
    cin >> n;
    queue<ll> q;
    q.push(3);
    q.push(5);
    q.push(7);
    while (1) {
        ll f = q.front();
        q.pop();
        if (f > n) break;
        if (check(f)) res++;
        q.push(f * 10 + 3);
        q.push(f * 10 + 5);
        q.push(f * 10 + 7);
    }
    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 768
/*
ID: barish21
LANG: C++14
TASK: test
*/

/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();

const intt max1 = 11;
const intt max2 = 102;
const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;
const intt lg2 = 7;
const intt lg3 = 10;
const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;
const intt lg7 = 24;
const intt lg8 = 27;
const intt lg9 = 30;
const intt lg18 = 60;
const intt INF = 2LL * 1000000000;
/***************/

/***Additional Functions***/
intt powmod(intt a,intt b,intt mod){intt res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
intt gcd(intt a, intt b) { while(b) b ^= a ^= b ^= a %= b; return a;}
intt lcm(intt a,intt b){return a*b/gcd(a,b);}
intt is_prime(intt n){if(n==1)return 0;if(n==2)return 1;if(n%2==0)return 0;for(intt i=3;i<=sqrt(n);i+=2)if(n%i==0)return 0;return 1;}
intt is_integer(double n){if(floor(n)==ceil(n))return 1;return 0;}

intt sto_int(string s){stringstream ss(s);intt n;ss>>n;return n;}
string to_string(intt n){stringstream ss;ss<<n;string s=ss.str();return s;}
/**************************/

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    IO;
    intt n, a, b;
    cin >> n >> a >> b;
    cout << max (0LL, ((n - 1) * b + a) - ((n - 1) * a + b) + 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll 				long long
#define int             long long int
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define modp            998244353
#define inf             (ll)1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO           	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl 			'\n'
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void solve()
{
	int n; cin >> n;
	string s; cin >> s;
	int r = 0;
	for(int i = 0; i < n; i++)
		if(s[i] == 'R')
			r++;
	if(r == n || r == 0)
		cout << 0 << endl;
	else
	{
		int mn = 0;
		int cnt = 0;
		for(int i = 0; i < r; i++)
		{
			if(s[i] != 'R')
				cnt++;
		}
		for(int i = n-1; i >= r; i--)
			if(s[i] != 'W')
				mn++;
		cout << min(mn, cnt) << endl;
	}
}
 
int32_t main()
{
	FIO
    // w(t)
    {
    	solve();
    }
    return 0;
}
	

	

Measured memory_bytes: 3760
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int N = sc.nextInt();
    int[] a = new int[N];
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    LinkedList<Integer> que = new LinkedList<Integer>();
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < a[i]; j++) {
        que.add(i + 1);
      }
    }
    int[][] c = new int[H][W];
    for(int i = 0; i < H; i++) {
      if(i % 2 == 0) {
        for(int j = 0; j < W; j++) {
          c[i][j] = que.poll(); 
        }
      } else {
        for(int j = W - 1; j >= 0; j--) {
          c[i][j] = que.poll(); 
        }
      }
    }
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        System.out.print(c[i][j]);
        if(j < W - 1) System.out.print(" ");
        if(j == W - 1) System.out.println();
      }
    }
  }
}


Measured memory_bytes: 34780
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace  std;
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rep(n) for (int i = 0; i < n; ++i)
#define ps(x) cout << x << endl;
#define ps_end(x) ps(x); return;

const int md = 1e9 + 7; //998244353 ;
void addto(int &x, int y) { x = x + y; if (x >= md) x -= md; }
int add(int x, int y) { int z = x + y; return z >= md? z -= md : z;}
void updmin(auto&x, auto y ) { if (y < x) x = y;}
void updmax(auto&x, auto y ) { if (y > x) x = y;}
long long pw(auto x, auto y) {	
	long long s = 1;
	while(y) {
		if (y & 1) s = s * x % md;
		x= 1LL * x * x % md; y /= 2;
	}
	return s;
}


const int maxn = 1e6 + 10;

int T, n, m;

void task() {
	int k;
	cin >> n >> k;
	vector<int> a(n);
	rep(n) cin >> a[i];
	int l = 1, r = 1e9;
	while (l <= r) {
		ll s = 0;
		int mid = (l + r) / 2;
		rep(n) {
			s += a[i] / mid + (a[i] % mid > 0) - 1;
			if (s > k) break; 
		};
		if (s <= k) r = mid - 1;
		else l = mid + 1;
	}
	cout << r + 1 << endl;
	// you should actually read the stuff at the bottom
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout<<fixed<<setprecision(20);
  T = 1;
  for (int ti = 1; ti <= T; ++ti) {
    task();
  }
  return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* write down
*/


Measured memory_bytes: 3980
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#define REP(i, n) for(int i=0; i<(n); i++)
#define FOR(i, a, n) for(int i=(a); i<(n); i++)
using namespace std;

int main(){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x3,y3,x4,y4;
    x3 = x2+y1-y2;
    y3 = y2+x2-x1;
    x4 = x1+y1-y2;
    y4 = y1+x2-x1;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

Measured memory_bytes: 256