akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin, n;
    int cnt = 0;
    int mx = 0;
    REP(i, 0, n) {
        int a, b;
        cin, a, b;
        if (a == b) {
            cnt++;
        } else {
            cnt = 0;
        }
        chmax(mx, cnt);
    }
    print((mx >= 3 ? "Yes" : "No"));
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define fi first
#define se second
#define mp(x,y) make_pair(x,y);

/*struct comp
{
    bool operator()()
    {
        
    }
};*/

int32_t main() {
    int t=1;
    //cin>>t;
    while(t--)
    {
      string s;
      cin>>s;
      if(s=="ARC")
      {
          cout<<"ABC";
      }
      else
      {
          cout<<"ARC";
      }
      
      cout<<endl;  
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ff first
#define ss second
#define pb push_back
#define vi vector<ll>
#define all(_x) _x.begin(), _x.end()
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define lb(_x, _a) (lower_bound(all(_x), _a) - _x.begin())
#define ub(_x, _a) (upper_bound(all(_x), _a) - _x.begin())

int main()
{
  	// ll is int now
    ll n, x, y; cin>>n>>x>>y;
    vector<int> arr(n+10);
    for(int i=x+1; i<=n; i++)
    {
        // x to i
        arr[i] = min(i-x, 1 + abs(y - i));
    }
    vi dist(n+1, 0);
    // for(ll i=x+1; i<=n; i++) cout<<arr[i]<<" ";
    // cout<<endl;
    for(ll i=1; i<=n-1; i++)
    {
        for(ll j=i+1; j<=n; j++)
        {
            //i to j dist
            ll tem = 0;
            if(j<=x)
            {
                dist[j-i]++;
                continue;
            }   
            //min j-i or i to x + x to j
            tem = min(j-i, abs(x-i)+ arr[j]);
            dist[tem]++;
        }
    }
    for(ll i=1; i<=n-1; i++) cout<<dist[i]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int n,k,x,y,ans=0;
	scanf("%d%d%d%d",&n,&k,&x,&y);
	for(int i=0;i<n;i++){
		if(i<k)ans+=x;
		else ans+=y;
	}
	printf("%d",ans);
	return 0;
}

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

int main(){
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a+3);
	if((a[0]==a[1] && a[1] != a[2]) or (a[0] != a[1] && a[1]==a[2])) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
S=set(input())
Sl=list(S)
Sl.sort()
moji=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
T="None"
for i in range(len(Sl)):
    if Sl[i]!=moji[i]:
        T=moji[i]
        break

if T=="None" and len(Sl)<26:
    T=moji[i+1]

print(T)



Measured memory_bytes: 3188
import heapq

q = int(input())
inf = 10000000000
left = [inf]
right = [inf]
minval = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        _, a, b = query
        if a < -left[0]:
            v = -heapq.heappop(left)
            heapq.heappush(right, v)
            heapq.heappush(left, -a)
            heapq.heappush(left, -a)
            minval += abs(v - a) + b
        elif a > right[0]:
            v = heapq.heappop(right)
            heapq.heappush(left, -v)
            heapq.heappush(right, a)
            heapq.heappush(right, a)
            minval += abs(v - a) + b
        else:
            heapq.heappush(left, -a)
            heapq.heappush(right, a)
            minval += b
    else:
        print(-left[0], minval)

Measured memory_bytes: 19040
sx, sy, tx, ty = map(int, input().split())

dx, dy = tx-sx, ty-sy
ans = ''
ans += 'U'*dy
ans += 'R'*dx
ans += 'D'*dy
ans += 'L'*dx
ans += 'L'
ans += 'U'*(dy+1)
ans += 'R'*(dx+1)
ans += 'DR'
ans += 'D'*(dy+1)
ans += 'L'*(dx+1)
ans += 'U'

print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const int mod = 1000000007;
const int mod998 = 998244353;

int N, M, X, res;
vector<int>v[100000];

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		cin >> X;
		v[X % M].push_back(X);
	}
	res += v[0].size() / 2;
	for (int i = 1; i < M; ++i) {
		if (i + i == M) {
			res += v[i].size() / 2;
		}
		else if (v[i].size() > v[M - i].size() || (v[i].size() == v[M - i].size() && i <= M - i)) {
			res += v[M - i].size();
			map<int, int>mp;
			for (int j : v[i]) {
				++mp[j];
			}
			int c = 0;
			for (auto it = mp.begin(); it != mp.end(); ++it) {
				c += it->second / 2;
			}
			res += min(int(v[i].size() - v[M - i].size()) / 2, c);
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
using namespace std;

typedef long long ll;

int main() {
  set<string> st;
  string s; cin >> s;
  int K; cin >> K;
  for ( int i = 0; i < s.length(); i++ ) {
    for ( int j = 1; j <= K; j++ ) {
      st.insert(s.substr(i,j));
    }
  }
  int cnt = 1;
  string ans ="";
  for( auto itr = st.begin(); itr != st.end(); itr++ ) {
    //cout << *itr << endl;
    if ( cnt == K ) {
      ans = *itr;
      break;
    }
    cnt++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 998244353;

#define MAX_N 10000005
ll inv[MAX_N], fac[MAX_N], finv[MAX_N];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2; i<MAX_N; i++) {
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    fac[i] = fac[i-1] * (ll)i % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}
ll perm(ll n, ll r) {
  if(n < 0)       return 0;
  else if(n < r)  return 0;
  else            return (fac[n] * finv[n-r]) % mod;
}
ll comb(ll n, ll r) {
  ll ans = 1;
  ans = perm(n, r);
  ans = (ans * finv[r]) % mod;
  return ans;
}
ll binary_pow(ll a, ll N) {
  ll ans = 1;
  ll tmp = a;
  while(N > 0) {
    if(N % 2 == 1) {
      ans *= tmp;
      ans %= mod;
    }
    N /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return ans;
}

int main() {
  ll N;
  cin >> N;
  make();
  ll cnt = 0;
  REP(i, N/2+1, N+1) {
    cnt += comb(N, i) * binary_pow(2, N-i);
    cnt %= mod;
  }
  cout << (binary_pow(3, N) - cnt * 2 + mod * 2) % mod << endl;
  return 0;
}



Measured memory_bytes: 234752
def resolve():
    def BF(s, n, edge, inf=float("inf")):
        d = [inf for i in range(n)]
        d[s] = 0
        for i in range(n * 2):
            for before, after, dist in edge:
                if before != inf and d[before] + dist < d[after]:
                    if i < n:
                        d[after] = d[before] + dist
                    else:
                        d[after] = -inf
        return d
    n, m, p = map(int, input().split())
    inf = float("inf")
    edge = [list(map(int, input().split())) for _ in range(m)]
    edge = [[x - 1, y - 1, p - z] for x, y, z in edge]
    ans = -BF(0, n, edge, inf)[-1]
    print(max(0, ans) if ans < inf else -1)


if __name__ == "__main__":
    resolve()


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

int main(){
   int n;
   cin >> n;
   vector<int> v(n);
   rep(i,n) cin >> v[i];
   bool can = true;
   int mx = -1;
   rep(i,n){
      if (mx <= v[i]-1) mx = v[i]-1;
      else{
         if (mx <= v[i]) continue;
         can = false;
         break;
      }    
   }
   if (can) cout << "Yes" << endl;
   else cout <<"No" <<endl;

   return 0; 

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define fo(i,ini,n) for(int i=ini;i<n;i++)
int const inf=1e9+7;
typedef long long ll;

int main(){
	int t,k;
	cin>>t>>k;
	int a[t];
	fo(i,0,t){
		cin>>a[i];
	}
	vector<ll>dp(t+1,inf);
	dp[0]=0;
	fo(i,0,t-1){
		fo(j,i+1,k+1+i){
			dp[j]=min(dp[i]+abs(a[i]-a[j]),dp[j]);
		}
	}
	cout<<dp[t-1]<<endl;
}


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

int n,m;
vector<int> a,b;

struct UnionFind {
    vector<int> parent;
    UnionFind(int N) {
        parent=vector<int>(N,-1);
    }
    int root(int x) {
        if (parent[x] < 0) return x;
        return parent[x] = root(parent[x]);
    }
    int size(int x){
        return -parent[root(x)];
    }
    bool unite(int x, int y) {
        x=root(x);
        y=root(y);
        if (x==y) return false;
        if(size(x)<size(y)) swap(x,y);
        parent[x]+=parent[y];
        parent[y]=x;
        return true;
    }
    bool same(int x, int y) {
        return root(x)==root(y);
    }
};

int main(){

    cin >> n >> m;

    a=vector<int>(m);
    b=vector<int>(m);

    rep(i,m){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    UnionFind tree(n);
    vector<ll> ans;
    ans.push_back((ll)n*(n-1)/2);
    for(int i=m-1;i>=0;i--){
        ll t=ans.back();
        ll asize=tree.size(a[i]);
        ll bsize=tree.size(b[i]);
        if(tree.unite(a[i],b[i])){
            t-=(ll)asize*bsize;
        }
        ans.push_back(t);
    }

    rep(i,m){
        ans.pop_back();
        cout << ans.back() << endl;
    }

    return 0;
}

Measured memory_bytes: 3444
// {{{ by unolight
#pragma region
#include <bits/stdc++.h>
#include <unistd.h>
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-function"
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define RALL(x) rbegin(x),rend(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

namespace { namespace unolight {
// Read Input
template<class T> void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( int64_t &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<class T, class... U> void R( T& head, U&... tail ) { _R(head); R(tail...); }
// Write Output
template<class T> void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
void _W( const int64_t &x ) { printf("%" PRId64,x); }
void _W( const double &x ) { printf("%.16f\n",x); }
void _W( const char &x ) { putchar(x); }
void _W( const char *x ) { printf("%s",x); }
template<class T> void _W( const vector<T> &x ) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W( const T& head, const U&... tail ) { _W(head); putchar(sizeof...(tail)?' ':'\n'); W(tail...); }

#ifdef UNOLIGHT
#include "dump.hpp"
#else
#define dump(...)
#endif

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}
#pragma endregion
// }}}

void main() {
    int x;
    R(x);
    W(x^1);   
}

}} // {{{ main
int main() { unolight::main(); return 0; }
// }}}


Measured memory_bytes: 3824
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static final int MODULUS = 1_000_000_007;
    static final char[] ALPHABET = { 'A', 'C', 'G', 'T' };
    static final Set<String> EXCLUDED_PATTERNS = new HashSet<>(
            Arrays.asList("AGC", "GAC", "ACG", "AGGC", "ATGC", "AGTC"));

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

        int N = sc.nextInt();

        System.out.println(solve(N));

        sc.close();
    }

    static int solve(int N) {
        Map<String, Integer> patternToWayNum = new HashMap<>();
        patternToWayNum.put("", 1);

        for (int i = 0; i < N; ++i) {
            Map<String, Integer> nextPatternToWayNum = new HashMap<>();
            for (String pattern : patternToWayNum.keySet()) {
                for (char letter : ALPHABET) {
                    String nextPattern = pattern + letter;
                    if (nextPattern.length() > 4) {
                        nextPattern = nextPattern.substring(nextPattern.length() - 4);
                    }
                    String nextLastThreePattern = (nextPattern.length() == 4) ? nextPattern.substring(1) : nextPattern;

                    if (!EXCLUDED_PATTERNS.contains(nextPattern) && !EXCLUDED_PATTERNS.contains(nextLastThreePattern)) {
                        nextPatternToWayNum.put(nextPattern,
                                addMod(nextPatternToWayNum.getOrDefault(nextPattern, 0), patternToWayNum.get(pattern)));
                    }
                }
            }

            patternToWayNum = nextPatternToWayNum;
        }

        return patternToWayNum.values().stream().mapToInt(x -> x).reduce(Main::addMod).getAsInt();
    }

    static int addMod(int x, int y) {
        return (x + y) % MODULUS;
    }
}

Measured memory_bytes: 55812
n = int(input())
happiness = [list(map(int, input().split())) for _ in range(n)]

dp = [[0] * 3 for _ in range(n + 1)]

# dp[i + 1][j] := i 日目までの活動履歴のうち、最終日であるi日目には活動
# j(0: A, 1: B, 2: C) を選んだ場合の、得られる幸福度の最大値
# dp[ i ][ 0 ] から dp[ i + 1 ][ 1 ] への遷移
# dp[ i ][ 0 ] から dp[ i + 1 ][ 2 ] への遷移
# dp[ i ][ 1 ] から dp[ i + 1 ][ 0 ] への遷移
# dp[ i ][ 1 ] から dp[ i + 1 ][ 2 ] への遷移
# dp[ i ][ 2 ] から dp[ i + 1 ][ 0 ] への遷移
# dp[ i ][ 2 ] から dp[ i + 1 ][ 1 ] への遷移
# 日付
for i in range(n):
    for j in range(3):
        for k in range(3):
            if i == 0:
                dp[i + 1][k] = happiness[i][k]
            elif j == k:
                continue
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][k] + happiness[i][j])

print(max(dp[-1]))


Measured memory_bytes: 74072
#include<stdio.h>
int main()
{
	double n,m,a,b;
	scanf("%lf %lf",&a,&b);
	m=a;n=b;
	while (a!=b) 
	{if (a>b)  a=a-b;     
	else  b=b-a;}
	printf("%.lf",m*n/a);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(){
  int a,b,c=0;
  int x[]={1,3,5,7,8,10,12},y[]={4,6,9,11};
  scanf("%d %d",&a,&b);
  for(int i=0;i<7;i++)if(x[i]==a)for(int j=i;j<7;j++)if(x[j]==b)c=1;
  for(int i=0;i<4;i++)if(y[i]==a)for(int j=i;j<7;j++)if(y[j]==b)c=1;
  (c==1)?puts("Yes"):puts("No");
  return 0;
}

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

//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
typedef long long ll;

int main(){
    string S;
    cin >> S;
    int a=0,b=0;

    for (int i=0;i<S.size();++i) {
        if (S[i]=='0') a+=1;
        else b+=1;
    }
    cout << 2*min(a,b) << endl;

}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int INF=1e9;
int main(){
	int N,K;cin>>N>>K;
	int A[N];int sum=0;
	rep(i,0,N){ cin>>A[i];sum+=A[i]; }
	deque<int> d;
	for(int i=1;i*i<=sum;i++){
		if(sum%i==0){ d.push_back(i);d.push_back(sum/i); }
	}sort(d.begin(),d.end());
	int check,k;int u;int B[N];
	for(int i=d.size()-1;i>=0;i--){
		u=d[i];check=0;
		rep(j,0,N){
			k=A[j]%u;
			B[j]=-k;
            check+=k;
		}if(check%u==0){
            sort(B,B+N);
            int temp=accumulate(B,B+(check/u),0);
            if(check+temp<=K){
                cout<<u<<endl;
                return 0;
            }
        }
	}
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastReader scan = new FastReader();
		int n = scan.nextInt(), m = scan.nextInt(), c = scan.nextInt(), total = 0;
		int[] b = new int[m];
		for(int i = 0; i < m; i++) b[i] = scan.nextInt();
		for(int i = 0; i < n; i++) {
			int curr = 0;
			for(int j = 0; j < m; j++) curr += scan.nextInt() * b[j];
			curr += c;
			if(curr > 0) total++;
		}
		System.out.println(total);
		
	}
	
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}


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

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    vector<int> d(m, 0);
    vector<vector<int>> c(m);
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i];
        c[i].resize(b[i]);
        for(auto& x : c[i]){
            cin >> x;
            --x;
            d[i] |= (1 << x);
        }
    }

    vector<i64> dp(1 << n, INF);
    dp[0] = 0;
    for(int i = 0; i < m; ++i){
        vector<i64> nex(dp);
        for(int j = 0; j < (1 << n); ++j){
            if(dp[j] == INF)
                continue;
            nex[d[i] | j] = min(nex[d[i] | j], dp[j] + a[i]);
        }
        dp = move(nex);
    }
    cout << (dp.back() >= 1e17 ? -1 : dp.back()) << endl;

}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)

using pii = pair<int, int>;
using vpii = vector<pii>;

int n, m, p, q, r;

int calc(pii seg, int n)
{
	int len = seg.scd - seg.fst + 1;

	if (n < p && p <= n + len - 1) {
		int a = (n + len - 1) - p;

		return calc(pii(seg.scd - a, seg.scd), p);
	}

	if (p <= n && n + len - 1 <= q) {
		return max(min(r - seg.fst + 1, len), 0);
	}

	if (n <= q && q < n + len - 1) {
		int a = q - n;

		return calc(pii(seg.fst, seg.fst + a), n);
	}

	return 0;
}

int main()
{
	omajinai;

	while (cin >> n >> m >> p >> q >> r, n) {
		deque<pii> dat;

		dat.push_back(pii(1, n));

		rep(_, m) {
			int x, y; cin >> x >> y;

			int sum = 0;

			vpii Top, Mid, Bottom;

			// Top?????????
			while (true) {
				pii a = dat.front();

				int v = a.scd - a.fst + 1;

				if (sum + v >= x) {
					int dif = x - sum-1;

					sum += dif + 1;

					Top.push_back(pii(a.fst, a.fst + dif));

					dat.pop_front();

					if (a.fst + dif + 1 <= a.scd) dat.push_front(pii(a.fst + dif + 1, a.scd));

					break;
				} else {
					Top.PB(a);
					sum += v;
				}

				dat.pop_front();
			}

			// Mid?????????
			while (true) {
				pii a = dat.front();

				int v = a.scd - a.fst + 1;

				if (sum + v >= y) {
					int dif = y - sum-1;

					sum += dif + 1;

					Mid.push_back(pii(a.fst, a.fst + dif));

					dat.pop_front();

					if (a.fst + dif + 1 <= a.scd) dat.push_front(pii(a.fst + dif + 1, a.scd));

					break;
				} else {
					Mid.PB(a);
					sum += v;
				}
				dat.pop_front();
			}

			// Bottom?????????
			while (true) {
				pii a = dat.front();

				int v = a.scd - a.fst + 1;

				if (sum + v == n) {
					sum += v;

					Bottom.push_back(pii(a.fst, a.scd));

					dat.pop_front();

					break;
				} else {
					Bottom.PB(a);
					sum += v;
				}

				dat.pop_front();
			}

			rep(i, Bottom.size()) dat.push_back(Bottom[i]);
			rep(i, Mid.size()) dat.push_back(Mid[i]);
			rep(i, Top.size()) dat.push_back(Top[i]);
		}

		int sum = 1;
		int ans = 0;

        rep(i, dat.size()) {
            pii a = dat[i];
			ans += calc(a, sum);
			sum += a.scd - a.fst + 1;
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 3212
N, M = map(int, input().split())
mod = 10**9+7
if min(N, M) + 1 < max(N, M):
    ans = 0
elif min(N, M) == max(N, M):
    ans = 1
    for i in range(1, N+1):
        ans *= i
        ans %= mod
    ans *= ans
    ans %= mod
    ans *= 2
    ans %= mod
else:
    ans = 1
    minNM = min(N, M)
    for j in range(1, 1+minNM):
        ans *= j
        ans %= mod
    ans *= ans
    ans %= mod
    ans *= minNM+1
    ans %= mod
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define UINF 18446744073709551615
#define F first
#define S second
#define ll long long
#define N 110
using namespace std;
ll n,m,sum=0,a[N],ans=0;
int main(){
	ll i;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(i=0;i<n;i++)
	{
		if(a[i]*4*m>=sum)
		{
			ans++;
		}
	}
	if(ans>=m)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}

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

using namespace std;

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

	unsigned int n;
	cin >> n;
	vector<int> subords(n);

	unsigned int x;
	for(int a = 1; a < n; a++){
		cin >> x;
		subords[x-1] += 1;
	}

	for(int sub : subords)
		cout << sub << "\n";

	return 0;
}


Measured memory_bytes: 3996
package main

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

func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()

    var n int
    fmt.Fscan(r, &n)
    s := make([]byte, n)
    fmt.Fscan(r, &s)
    ans := 0
    for sp := 1; sp < n; sp++ {
      front := s[:sp]
      back := s[sp:]
      var cnt [26]int
      res := 0
      for _, c := range front {
        cnt[int(c) - int('a')] = 1
      }
      for _, c := range back {
        res += cnt[int(c) - int('a')]
        cnt[int(c) - int('a')] = 0
      }
      if ans < res {
        ans = res
      }
    }
    fmt.Fprintln(w, ans)
}


Measured memory_bytes: 640
import sys
import math

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

a,b,c,d = nm()

a_hp = math.ceil(a/d)
b_hp = math.ceil(c/b)

if a_hp >= b_hp:
    print('Yes')
else:
    print('No')

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

int main()
{
  int n, x; cin >> n >> x;
  vector<int> l(n);
  vector<int> d(n+1, 0);
  rep(i, n) cin >> l[i];
  int ans = 1;
  rep(i, n) {
    d[i+1] = d[i]+l[i];
    if (d[i+1] <= x) ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()

min_d = 10**9
for i in range(K-1,N):
  d=h[i]-h[i-(K-1)]
  if d<min_d:
    min_d=d
print(min_d)

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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n; cin >> n;
    vi a(n),dp(n);
    forn(i,n) cin >> a[i];
    dp[n-2] = abs(a[n-2]-a[n-1]);
    dforn(i,n-2){
        int x = abs(a[i]-a[i+1]) + dp[i+1];
        int y = abs(a[i]-a[i+2]) + dp[i+2];
        dp[i] = min(x,y);
    }
    cout << dp[0] << endl;
    return 0;
}


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

using namespace std;

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<ll>
#define vl vector<ll>
#define pb push_back
#define INF 1000000007
#define PI 3.141592653
#define inf 100007
#define pll pair<ll,ll>
#define pii pair<int,int>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

int h,w,ans;
string s[30];
int used[32][32];
int d[22][22];

void bfs(pii p){
    queue<pii> que;
    que.push({p.first,p.second});
    used[p.first][p.second]=1;
    while(!que.empty()){
        pii k=que.front();
        int i=k.first,j=k.second;
        que.pop();
        if((i+1>=0 && i+1<h && j>=0 && j<w) && s[i+1][j]!='#' && !used[i+1][j]){
            que.push({i+1,j}),used[i+1][j]=1,d[i+1][j]=d[i][j]+1;
        }
        if((i-1>=0 && i-1<h && j>=0 && j<w) && s[i-1][j]!='#' && !used[i-1][j]){
            que.push({i-1,j}),used[i-1][j]=1,d[i-1][j]=d[i][j]+1;
        }
        if((i>=0 && i<h && j-1>=0 && j-1<w) && s[i][j-1]!='#' && !used[i][j-1]){
            que.push({i,j-1}),used[i][j-1]=1,d[i][j-1]=d[i][j]+1;
        }
        if((i>=0 && i<h && j+1>=0 && j+1<w) && s[i][j+1]!='#' && !used[i][j+1]){
            que.push({i,j+1}),used[i][j+1]=1,d[i][j+1]=d[i][j]+1;
        }
    }
}
  
int main(){
    cin>>h>>w;
    pan(i,h) cin>>s[i];
    pan(i,h)
        pan(j,w){
            if(s[i][j]=='.'){
                pan(k,h)
                    pan(l,w){
                        ans=max(ans,d[k][l]);
                        used[k][l]=0;
                        d[k][l]=0;
                    }
                bfs({i,j});
                // cout<<ans<<endl;
            }
        }
    cout<<ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;



int main(void) {
    
    int n,m;
    cin>>n>>m;
    int l=1,r=n;
    rep(i,m){
        int a,b;
        cin>>a>>b;
        l=max(l,a);
        r=min(r,b);
    }
    if(l>r)fin(0);
    else fin(r-l+1);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ans=1e8,sum1,sum2;
string s;
int main(){
	cin >> n >> s;
	for(int i=0;i<n;i++)
		if(s[i]=='.')sum2++;
	ans=min(ans,sum2);
	for(int i=0;i<n;i++){
		if(s[i]=='#')sum1++;
		if(s[i]=='.')sum2--;
		ans=min(ans,sum1+sum2);
	}
	cout << ans;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using ll = long long;
#define ull unsigned ll
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pi pair<int,int>
#define pl pair<ll, ll>
#define ppi pair<int, pii>
#define mt make_tuple
#define eb emplace_back
using namespace std;

const ll N = 2e5 + 5, mod = 1e9 + 7;
const int inf = 1e9 + 5;

bool cmp(const pair<ll, ll> &a, const pair<ll, ll> &b){
    if(a.F == b.F) return a.S < b.S;
    return a.F > b.F;
}
ll power(ll x, ll p){
    ll r = 1ll;
    x = x % mod;
    while(p > 0){
        if(p & 1) r = (r * x) % mod;
        p = p >> 1;
        x = (x * x) % mod;
    }
    return r;
}

void solve(){
    int n, k;
    cin >> n >> k;
    vi a(n);
    int ans = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        ans = max(ans, a[i]);
    }
    int l = 0, r = inf;
    while(l <= r){
        int mid = (l + r) / 2;
        int cnt = 0;
        if(mid==0){
            cout << 1 << endl;
            return;
        }
        for(int i = 0; i < n; i++){
            cnt += (a[i] - 1) / mid;
            if(cnt > k) break;
        }
        if(cnt > k){
            l = mid + 1;
        }
        else{
            r = mid - 1;
            ans = mid;
        }
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);//cout.tie(0);
    /*#ifndef ONLINE_JUDGE
        freopen("Input.txt", "r", stdin);
    #endif*/
    //freopen("running_on_fumes_chapter_1_input (1).txt", "r", stdin);
    //freopen("Output.txt", "w", stdout);
    int t = 1, p;
    //cin >> t;
    for(p = 1; p <= t; p++){
        //cout << "Case #" << p << ": ";
        solve();
    }
    return 0;
}



Measured memory_bytes: 3944
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'#')

A = np.zeros((H,W), np.int32)
A[X,Y] = np.arange(1,K+1)

np.maximum.accumulate(A, axis = 1, out = A)

for w in range(W-2, -1, -1):
	A[:,w] += A[:,w+1] * (A[:,w] == 0)

for h in range(1,H):
	if A[h,-1] == 0:
		A[h] += A[h-1]
for h in range(H-1,-1,-1):
	if A[h,-1] == 0:
		A[h] += A[h+1]

print('\n'.join(' '.join(row) for row in A.astype(str)))

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

int main() {
	int a, b, c;
	while (cin >> a >> b >> c) {
		int ans = 0;
		vector<int>nok;
		for (int i = 1;i <= 10;i++) {
			if (i != a&&i != b&&i != c)nok.push_back(i);
		}
		for (int i = 0;i < 7;i++) {
			if (a + b + nok[i] <= 20)ans++;
		}
		if (ans >= 4)cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    ll A, B, K; cin >> A >> B >> K;
    if(A < K){
        K -= A;
        A = 0;
        B -= min(B, K);
    }
    else{
        A -= K;
    }
    cout << A << " " << B << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main() {
	int N, D;
	cin >> N >> D;
	vector<vector<int>> A(N,vector<int>(D));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < D; j++) {
			cin >> A[i][j];
		}
	}
	int leng = 0;
	int ans = 0;
	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			for (int k = 0; k < D; k++) {
				leng += pow((A[i][k] - A[j][k]), 2);
			}
			if (fmod(sqrt(leng),1) == 0) {
				ans++;
			}
			leng = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(signed i=0;i<n;++i)
#define repi(n) rep(i,n)
#define int long long
#define str string
#define vint vector<int>
#define pint pair<int,int>
#define pb(a) push_back(a)
#define all(v) v.begin(),v.end()
#define yn(b) cout<<((b)?"Yes":"No")<<endl
#define YN(b) cout<<((b)?"YES":"NO")<<endl
#define call(a) for(auto t:a)cout<<t<<" ";cout<<endl
#define ENDL printf("\n");
#define debg(a) cout<<#a<<":"<<a<<endl;
#define SORT(a) sort(all(a));
#define INF 1LL<<60
#define inf INF
#define out(i) cout<<i<<endl;
#define allSum(a) accumulate(a.begin(),a.end(),0)
int min(int a,int b){if(a>b)return b;return a;}
int max(int a,int b){if(a>b)return a;return b;}

signed main(){
  int n;
  cin>>n;
  vector<string> s(n);
  rep(i,n)cin>>s[i];
  bool ans=true;
  rep(i,n)rep(j,n){if(i==j)continue;if(s[i]==s[j])ans=false;}
  for(int i=1;i<n;++i){
    if(s[i][0]!=s[i-1][s[i-1].length()-1])ans=false;
  }
  yn(ans);
  

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define RS(x) rsort(x.begin(),x,end()))
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
int INF = 1e9 + 1;
int MOD = 1e9+7;
struct initon
{
    initon()
    {
        cin.tie(0);
        ios::sync_with_stdio(false);
    };
};
typedef long double ld;
int k,n,a,b,c,ans,MAX,an;
string s;
signed main(){
cin >>k>>n;
vector<int> A(n);
REP(i,n)cin >>A[i];
REP(i,n-1){
  an=A[i+1]-A[i];
  if(an>=MAX){
    MAX=an;
  }
}
if(A[n-1]-A[0]<k/2){
an=A[n-1]-A[0];
}else{
  an=k-A[n-1]+A[0];
}
  if(an>=MAX){
    MAX=an;
  }
cout << k-MAX;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

int func(int a){
	int ret = 0;
	while(a){
		ret += a%10;
		a/=10;
	}
	return ret;
}
int main(void){
	int N;
	cin >> N;
	int a,b;
	int ans = inf;
	for(int i=0;i<(N+2)/2;i++){
		int temp = 0;
		a = i;
		b = N-i;
		if(a==0||b==0)continue;
		temp += func(a);
		temp += func(b);
		ans = min(ans,temp);
	}
	cout << ans << endl;
}

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

int main(){
    int a;
    int b;
    int c;
    int i;
    int x=0;
    
    cin >> a >> b >> c;
    
    for(i = a;i <= b;i++){
        
        if(c % i == 0){
            
            x +=1;
        }
        
    }
    
    cout << x << endl;
    
    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cout.precision(10);
    ll q, h, s, d, n, ans = 0;
    cin >> q >> h >> s >> d >> n;
    h = min(h, 2 * q);
    s = min(s, 2 * h);
    d = min(d, 2 * s);
    cout << n / 2 * d + n % 2 * s << endl;
    return 0;
}

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

#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FILL0(x) memset(x,0,sizeof(x))

using namespace std;

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

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

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

    int a, b, c, d;
    cin >> a >> b >> c >>d;
    while(a>0 || c>0)
    {
        c-=b;
        if(c<=0)
        {
            cout << "Yes" << endl;
            return 0;
        }
        a-=d;
        if(a<=0)
        {
            cout <<"No" << endl;
            return 0;
        }
    }

 

 

    return 0;
}
 

//cout << setprecision(13);
//next_permutation();
//__gcd();
//reverse();
//set ,tuple ,pair;
//bitset
//vector.find



Measured memory_bytes: 3652
#include "bits/stdc++.h"

using namespace std;

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(ll)(n);i>0;i--)
#define REP(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(v) v.begin(),v.end()
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
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 (a>b) { a = b; return 1; } return 0; }
const ll inf = 1000000001;
const ll INF = 2e18;
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);




int main() {
	int n, k;
	cin >> n >> k;
	vi a(n);
	int idx;
	rep(i, n) {
		cin >> a[i];
		if (a[i] == 1) {
			idx = i;
		}
	}
	int ans = inf;
	rep(i, n) {
		if (!in(idx, i, i + k)) {
			continue;
		}
		int res = 0;
		if (i%(k - 1) == 0) {
			res += i / (k - 1);
		}
		else {
			res += i / (k - 1) + 1;
		}
		int num = n - 1 - (i + k - 1);
		if (num > 0) {
			if (num % (k - 1) == 0) {
				res += num / (k - 1);
			}
			else {
				res += num / (k - 1) + 1;
			}
		}
		chmin(ans, res + 1);
	}
	cout << ans << endl;


}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int ar[200003];
    scanf("%d",&n);
    for(int i=0;i<=n-1;i++)
    {
        scanf("%d",&ar[i]);
    }
    int minn=ar[0];
    int cnt=1;
    for(int i=1;i<=n-1;i++)
    {
        if(ar[i]<minn)
        {
            minn=ar[i];
            cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 1000000007

vector<int> T[100010];
int p[100010], a[100010], d[100010];

void dep(int x, int v) {
	d[x] = v;
	for (int i : T[x]) {
		if (i == x)continue;
		dep(i, v + 1);
	}
}

int main(){
	int N, K, sc = 0;
	cin >> N >> K;
	for (int i = 1;i <= N;i++) {
		cin >> a[i];
		if (i == 1 && a[1] != 1) {
			sc++;
			a[1] = 1;
		}
		T[a[i]].push_back(i);
	}

	dep(1, 0);

	priority_queue<tuple<int,int,int>> Q;
	for (int i = 1;i <= N;i++) {
		if (T[i].size() == 0) {
			Q.push(make_tuple(d[i], 1, i));
		}
	}

	int f, g;
	while (!Q.empty()) {
		tie(ignore, f, g) = Q.top();
		Q.pop();
		if (g == 1)continue;
		if (p[g] >= f) {
			continue;
		}
		p[g] = f;
		if (f == K) {
			if (a[g] == 1)continue;
			Q.push(make_tuple(d[a[g]], 1, a[g]));
			sc++;
		}
		else {
			Q.push(make_tuple(d[a[g]], f + 1, a[g]));
		}
	}
	cout << sc << endl;
}

Measured memory_bytes: 11520
#include <iostream>
using namespace std;
const int MAX = 200000;

int main() {
	int n;
	cin >> n;
	int A[n];
	int bin[MAX+1] = {0};
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		bin[A[i]]++;
	}
	long long s = 0;
	for (int i = 0; i <= MAX; i++) {
		s += (long long)bin[i] * (bin[i] - 1) / 2;
	}
	for (int i = 0; i < n; i++) {
		long long ans = s - (bin[A[i]] - 1);
		cout << ans << endl;
	}
}


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

using namespace std;

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N, K;
  cin >> N >> K;
  vector < int > a(N);
  for (int& x: a)
    cin >> x;
  vector < bool > dp(K + 1);
  for (int stone = 0; stone <= K; ++stone)
    for (int x : a)
      if (stone >= x && !dp[stone - x])
        dp[stone] = true;
  if (dp[K])
    cout << "First\n";
  else
    cout << "Second\n";
}


Measured memory_bytes: 3616
let scan1 f = stdin.ReadLine() |> f
let scan2 f = stdin.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1]))
let scan3 f = stdin.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2]))

let s = scan1 string
let k = scan1 int64 // 18桁らしいので収まる

// '1' でない最初のインデックス i? が k 以上 なら 1 が答えになる
// そうでないなら i? に格納されている数が答えになる

let xs = s.ToCharArray()

xs
|> Array.tryFindIndex ((<>) '1')
|> function
   | None -> printfn "1" // Sが全て1で構成されている
   | Some i -> if (int64 i) >= k
                 then printfn "1" // 後ろの方にあるので 1 が答え
                 else printfn "%c" xs.[i]


Measured memory_bytes: 14044
#include<iostream>
#include<cmath>
#include<iomanip>
#include<stack>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<limits>
#include<set>
using namespace std;

int main() {
	long long  r1, r2, r3, ans = r3 = r2 = r1 = 0;
	int len;
	string s;
	cin >> len >> s;
	for (int i = 0; i < len; i++)
	{
		if (s[i] == 'R')ans += r2 * r3, r1++;
		else if (s[i] == 'G')ans += r1 * r3, r2++;
		else ans += r1 * r2, r3++;
	}
	for (int i = 0; i < len; i++)
		for (int j = i; j < len; j += 2)
			if (s[i] != s[(i + j) / 2] && s[i] != s[j] && s[(i + j) / 2] != s[j])
				ans--;
	cout << ans;
}

Measured memory_bytes: 3196
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include <sstream>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
#include <iomanip>
#include <regex>
#include <initializer_list>
#define DBL_MIN 0.000000000000001
#define A_P(n,a,d) (n/2)*(2*a + (n-1)*d)
using namespace std;

int main(void){
  string s;
  cin >> s;
  int last = -1;
  while(last != s.size() ){
    last = s.size();
    s = regex_replace(s,regex("WW"),"W");
    s = regex_replace(s,regex("BB"),"B");
  }

  cout << s.size()-1 << endl;
}

Measured memory_bytes: 3720
// abc054d: Mixing Experiment
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

#define rep(i,n) for(int i=0;i<(n);i++)
#define upto(i,s,e,d) for(int i=(s);i<(e);i+=(d))
#define in(x) cin>>(x)
#define oute(x) cout<<(x)<<endl

#define INF 1000000

int main(){
  int N,Ma,Mb; cin>>N>>Ma>>Mb;
  vi A(N),B(N),C(N);
  int amax=1, bmax=1;
  rep(n,N){
    cin>>A[n]>>B[n]>>C[n];
    if(amax<A[n]) amax = A[n];
    if(bmax<B[n]) bmax = B[n];
  }

  int Na = N*amax, Nb = N*bmax;
  vector<vvi> dp(2, vvi(Na+1, vi(Nb+1, INF)));
  dp[0][0][0] = 0;

  int p,q;
  rep(n,N){
    p = n%2; q = (n+1)%2;
    rep(a,Na+1) rep(b,Nb+1){
      if(dp[p][a][b]==INF) continue;
      dp[q][a][b] = min(dp[q][a][b], dp[p][a][b]);
      dp[q][a+A[n]][b+B[n]] = min(dp[q][a+A[n]][b+B[n]], dp[p][a][b] + C[n]);
    }
  }

  int ans = INF;
  upto(a,1,Na+1,1)
    upto(b,1,Nb+1,1)
      if(a*Mb==b*Ma) ans = min(ans, dp[q][a][b]);

  if(ans==INF) ans = -1;
  oute(ans);

}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll K = 0;
ll t;
ll ret = 0;
string s;

void input() {
  IN(N);
}

void solve() {
  ll th = N / 500;
  ll fi = (N % 500) / 5;
  PRINT(th * 1000 + fi * 5);
}

int main(void){
  input();
  solve();
}


Measured memory_bytes: 256
import sys
from functools import lru_cache

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def solve(n, k):
    if n < 10:
        if k == 1:
            return n
        elif k == 0:
            return 1
        else:
            return 0

    q, r = divmod(n, 10)

    return solve(q, k) + solve(q, k - 1) * r + solve(q - 1, k - 1) * (9 - r)


def main():
    N = int(input())
    K = int(input())

    print(solve(N, K))


if __name__ == '__main__':
    main()


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

bool func(int size,int arr[],int index,int val,int target)
{
	if (index > size)return false;
	if (val > target)return false;
	else if (val == target)return true;
	else return (func(size,arr, index + 1, val + arr[index], target) || func(size,arr, index + 1, val, target));
}

int main()
{
	int n, *A;
	int q, *B;
	cin >> n;
	A = new int[n];
	for (int i = 0; i < n; i++)cin >> A[i];
	cin >> q;
	B = new int[q];
	for (int i = 0; i < q; i++)
	{
		cin >> B[i];
		if (func(n,A, 0, 0, B[i]))cout << "yes" << endl;
		else cout << "no" << endl;
	}
	delete[]A;
	delete[]B;
	return 0;
}

Measured memory_bytes: 3096
(let ((x (read)))
  (loop :named main
        :for i :from -118 :to 119
        :do (loop :for j :from -118 :to (1- i)
                  :if (= (- (expt i 5) (expt j 5)) x)
                  :do (progn
                        (format t "~A ~A~%" i j)
                        (return-from main)))))


Measured memory_bytes: 24432