akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll dp[3001][3001];

ll solve(vector<int> &a, int i, int j, int turn){
    if(i>j)
        return 0;
    if(dp[i][j]!=-1)
        return dp[i][j];
    if(turn==0)
        return dp[i][j] = max(a[i]+solve(a,i+1,j,1), a[j]+solve(a,i,j-1,1));
    return min(solve(a,i+1,j,0), solve(a,i,j-1,0));
}

int main(){
    cin>>n;
    memset(dp, -1, sizeof dp);
    ll sum = 0;
    vector<int> a(n,0);
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum += a[i];
    }
    ll X = solve(a,0,n-1,0);
    ll Y = sum-X;
    cout<<(X-Y)<<endl;
    return 0;
}


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

int main(){
    int a,b,k;
    cin>>a>>b>>k;
    for(int i=0; i<k; i++){
        if(i%2==0){//高橋君のターン
            if(a%2==1)a--;
            b+=a/2;
            a/=2;
        }else{//青木君のターン
            if(b%2==1)b--;
            a+=b/2;
            b/=2;
        }
    }
    cout<<a<<" "<<b<<endl;
    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 < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
//#define S second
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 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;
}
signed main() {
    int S, W;
    cin >> S >> W;
    if(W >= S)
        cout << "unsafe" << endl;
    else
        cout << "safe" << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

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

int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}



string n;

int main(){
  int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int K;
  cin >> K;
  cout << a[K-1] << endl;
 
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		int aPos = ('a');
		StringBuilder res = new StringBuilder();
		while (N != 0) {
			if (N % 26 == 0) {
				res.insert(0, 'z');
				N--;
			} else {
				res.insert(0, (char) (aPos + (N % 26) - 1));
			}
			N /= 26;
		}
		System.out.println(res);
	}
}

Measured memory_bytes: 35736
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
    
    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    
    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }
    
    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
    
    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }
    
    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main() {
    int n, m; cin >> n >> m;
    UnionFind uf(n);
    rep(i, m) {
        int a, b; cin >> a >> b;
        a--, b--;
        uf.merge(a, b);
    }
    ll ans = 0;
    rep(i, n) {
        ans = max(ans, uf.size(i));
    }
    cout << ans << endl;
}


Measured memory_bytes: 6404
import java.util.*;

public class Main {
    static long MOD = 1000000007;
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] array = new long[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextLong();
        }
        
        long[] zero = new long[62];
        long[] one = new long[62];
        for (int i = 0; i < n; i++) {
            long num = array[i];
            for (int j = 0; j < 62; j++) {
                long tmp = num % 2;
                if (num == 0 || tmp == 0) {
                    zero[j]++;
                } else {
                    one[j]++;
                }
                
                num /= 2;
            }
        }
        
        long ans = 0;
        long two = 1;
        for (int i = 0; i < 62; i++) {
            long tmp = zero[i] * one[i];
            tmp %= MOD;
            
            tmp *= two;
            tmp %= MOD;
            
            ans += tmp;
            ans %= MOD;
            
            two *= 2;
            two %= MOD;
        }
        System.out.println(ans);
    }
}

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

using namespace std;
typedef long long int ll;
typedef long double ld;
#define REP(i, n) for(ll i = 0LL; i < (ll)(n); i++)
#define REPR(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define FOR(i, n, m) for(ll i = (ll)n; i < (ll)(m); i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL << 62)

#define PI (acos(-1))
#define PRINT(x) std::cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll countDigit(ll n) { return floor(log10(n) + 1); } 
typedef pair <ll,ll> P;
static const ll dx[8] = {0,1,0,-1, 1, -1, 1, -1}, dy[8] = {1,0,-1,0,1,1,-1,-1};

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

template <typename T1, typename T2> 
ostream& operator<<(ostream& os, const map<T1, T2>& m) 
{ 
    for (auto p : m) os << "<" << p.first << ", " << p.second << "> "; 
    return os; 
}

int main()
{
  ll N;
  cin >> N;
  ll t = N % 1000;
  if (t == 0) t = 1000;
  PRINT(1000 - t);
  return 0;
} 


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

int main() {
 string s; cin >> s;
 int x = 0;
 vector<int> dp(1<<26, 1e9);
 dp[0] = 0;
 for (char c : s) {
  x ^= 1 << (c-'a');
  for (int i = 0; i < 26; ++i) dp[x] = min(dp[x], dp[x ^ (1<<i)] + 1);
 }
 cout << max(1,dp[x]) << endl;
 return 0;
}


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

int main(){
    int MIN=1001;
    int c,t;
    int N,T;
    cin >>N>>T;
    for (int i = 0; i < N; i++){
        cin >>c>>t;
        if(t<=T){
            MIN=min(MIN,c);
        }
    }
    //cout << ans <<endl;
    if(MIN==1001){cout << "TLE" << std::endl;}else{cout << MIN <<endl;}
    
    return 0;
}


Measured memory_bytes: 256
using System;
class Program
{
	static void Main()
	{
      int breakb = 0;
	int divideNum = int.Parse(Console.ReadLine());//割られる数
      int[] numbers = new int[divideNum];
    int divideCount = 0;//割った回数
    int divideSource = 2;//割る数
	string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
    for(int i = 0;i < input.Length;i++)
    {
    numbers[i]  = int.Parse(input[i]);
    }
	while(true)
    {
     for(int i = 0;i < input.Length;i++)
     {
       if(!(numbers[i] % divideSource == 0))
       {
         breakb = 1;
       }
     }
      if(breakb == 1)break;
      else
      {
      divideSource *= 2;
      divideCount ++;
      }
    }
	Console.WriteLine(divideCount);
	}
}

Measured memory_bytes: 11204
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i,l,r) for(ll i=(l); i<(r); i++)
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; }
const ll INF = 1LL << 60;
const int inf = 1001001001;
const ll mod = 1000000007;
using pp=pair<ll,ll>;
 
// union by size + path having
class UnionFind {
public:
   vector <ll> par; // 各元の親を表す配列
   vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
 
   // Constructor
   UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
   }
   void init(ll sz_) {
       par.resize(sz_);
       siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
  }
 
   // Member Function
   // Find
   ll root(ll x) { // 根の検索
      while (par[x] != x) {
           x = par[x] = par[par[x]]; // x の親の親を x の親とする
       }
       return x;
  }
 
   // Union(Unite, Merge)
   bool unite(ll x, ll y) {
       x = root(x);
       y = root(y);
       if (x == y) return false;
       // merge technique（データ構造をマージするテク．小を大にくっつける)
       if (siz[x] < siz[y]) swap(x, y);
       siz[x] += siz[y];
       par[y] = x;
       return true;
  }
 
  bool same(ll x, ll y) { // 連結判定
       return root(x) == root(y);
  }
 
  ll size(ll x) { // 素集合のサイズ
      return siz[root(x)];
  }
};
 
ll modpow(ll x, ll n) {
   x = x%mod;
   if(n==0) return 1;  //再帰の終了条件
 
   else if(n%2==1) {
       return (x*modpow(x, n-1))%mod;  //nが奇数ならnを1ずらす
   }
   else return modpow((x*x)%mod, n/2)%mod;  //nが偶数ならnが半分になる
}
 
ll com(ll n, ll k) {
   ll x = 1;
   for(int i=n-k+1; i<=n; i++) {
      x = x*i%mod;
   }
 
   ll y = 1;
   for(int i=1; i<=k; i++) {
       y = y*i%mod;
   }
   y = modpow(y, mod-2);
 
   return x*y%mod;
}
 
bool is_prime(const unsigned n){
   switch(n){
       case 0: // fall-through
       case 1: return false;
       case 2: // fall-through
       case 3: return true;
  } // n > 3 が保証された
 
   if(n % 2 == 0 || n % 3 == 0) return false;
   // n は 2 と 3 のいずれの倍数でもないことが保証された
   // これより n は (6の倍数)-1 か (6の倍数)+1 である
 
   // 6の倍数前後の数を使って試し割りをする
   for(unsigned i = 5; i * i <= n; i += 6) {
       if(n % i     == 0) return false; // (6の倍数)-1
       if(n % (i+2) == 0) return false; // (6の倍数)+1
   }
 
   return true;
}
 
int digsum(int n) {
   int res = 0;
   while(n > 0) {
       res += n%10; //ここをres++;に変えたら桁数を求める関数になる
       n /= 10;
   }
   return res;
}
vector<ll> divisor(ll n){
   vector<ll> ret;
   for(ll i = 1 ; i*i <= n ; i++){
       if(n%i == 0){
           ret.push_back(i);
           if(i*i != n) ret.push_back(n/i);
       }
   }
   sort(ret.begin(),ret.end());
   return ret;
}
 
int main(){

    ll n,ans=0;
    cin >> n;
    FOR(i,1,n+1){
        if(i%2==1 && divisor(i).size()==8){
            ans++;
        }
    }

    cout << ans << endl;
 
}

Measured memory_bytes: 256
main(n,x,i,j,k,r){for(;scanf("%d%d",&n,&x),n;printf("%d\n",r))for(r=0,i=1;i<n-1;i++)for(j=i+1;j<n;j++)for(k=j+1;k<=n;k++)if(i+j+k==x)r++;exit(0);}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define RREP(i, n) for (long long i = n - 1, 0 <= i; i--)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define RFOR(i, start, end) for (long long i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    int N, K;
    cin >> N >> K;
    vector<ll> h(N);
    for (auto &&i : h) {
        cin >> i;
    }

    vector<ll> dp(N);
    FOR(i, 1, N) {
        dp[i] = INF64;
        FOR(j, 1, K + 1) {
            if (i - j < 0)
                break;
            chmin(dp[i], dp[i - j] + abs(h[i - j] - h[i]));
        }
    }
    print(dp[N - 1]);

    return 0;
}

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

using namespace std;

int main()
{
	string s;
	cin >> s;
	if (s.size() == 2)
		cout << s << endl;
	else
		cout << s[2] << s[1] << s[0] << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int weight[110], value[110];
int dp[110][10010]; //dp[i + 1][w] はi番目まで重さ制限w

int n, W;
int main(){
  cin >> n >> W;
  for (int i = 0; i < n; ++i){
    cin >> value[i] >> weight[i];
  }
  for (int w = 0; w <= W; ++w) dp[0][w] = 0;
  
  for (int i = 0; i < n; ++i){
    for (int w = 0; w <= W; ++w){
      if (weight[i] <= w){
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i]);
      }else{
        dp[i + 1][w] = dp[i][w];
      }
    }
  }
  cout << dp[n][W] << endl;
}


Measured memory_bytes: 7044
#include <bits/stdc++.h>
using namespace std;
int temp,x;
map<int,int>  judge;
int main()
{
    int a,b,c;
    int flag=0;
    cin>>a>>b>>c;
    for(int i=1;;i++)
    {
        temp = a*i;
        x=temp%b;
        if(x==(c%b)){
            break;
        }
        if(judge[x]){
            flag=1;
             break;
        }
        judge[x]=1;
    }
    if(!flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int[] arr = new int[26];
		for (int i = 0; i < s.length(); i++) {
			arr[s.charAt(i) - 'a']++;
		}
		for (int i = 0; i < 26; i++) {
			if (arr[i] % 2 != 0) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
}


Measured memory_bytes: 25300
s = input()

arr = list(s)

count = 0

for i in range(len(arr)):
    if i % 2 == 0:
        if arr[i] == "R" or arr[i] == "U" or arr[i] == "D":
            count +=1
    if i % 2 == 1:
        if arr[i] == "L" or arr[i] == "U" or arr[i] == "D":
            count +=1        

if count == len(arr):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 38384
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] nums = new long[n];
		for(int i = 0; i < n; i++){
			nums[i] = sc.nextLong();
		}
		long result = 0;
		long sum = 0;
		// + - + -
		for(int i = 0; i < n; i++){
			if(i % 2 == 0 && sum + nums[i] <= 0){
				result += Math.abs(1 - (sum + nums[i]));
				sum = 1;
			}
			else if(i % 2 == 1 && sum + nums[i] >= 0){
				result += Math.abs(-1 - (sum + nums[i]));
				sum = -1;
			}
			else{
				sum += nums[i];
			}
		}
		
		long result2 = 0;
		sum = 0;
		// - + - +
		for(int i = 0; i < n; i++){
			if(i % 2 == 1 && sum + nums[i] <= 0){
				result2 += Math.abs(1 - (sum + nums[i]));
				sum = 1;
			}
			else if(i % 2 == 0 && sum + nums[i] >= 0){
				result2 += Math.abs(-1 - (sum + nums[i]));
				sum = -1;
			}
			else{
				sum += nums[i];
			}
		}
		
		System.out.println(Math.min(result, result2));
		
		sc.close();
	}
}

Measured memory_bytes: 50704
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long H = sc.nextLong();
        long[] dp = new long[50];
        for (int i=0;i<49;i++) {
            dp[i+1] = dp[i]+(1L<<i);
            if (H<=(1L<<i)-1) {
                System.out.println(dp[i]);
                break;
            }
        }
    }
}

Measured memory_bytes: 25044
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vi>;

int main() {
    string S;
    cin >> S;

    if(S == "ABC") {
        cout << "ARC" << endl;
    }
    else {
        cout << "ABC" << endl;
    }
    return 0;
}

Measured memory_bytes: 3628
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author Silviase
 */
public class Main {

  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    Scanner in = new Scanner(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    AGC034KenKenRace solver = new AGC034KenKenRace();
    solver.solve(1, in, out);
    out.close();
  }

  static class AGC034KenKenRace {

    public void solve(int testNumber, Scanner in, PrintWriter out) {
      // A < B < C < D のときは簡単で,Bから先にジャンプさせればいい
      // A < C < B < D でも同じ
      // A < B < D < C が面倒で,追い越さなければいけない
      // 追い越しは...と3連続が存在する必要があり,Bはこれの真ん中より手前であればいい.
      int n = in.nextInt();
      int a = in.nextInt() - 1;
      int b = in.nextInt() - 1;
      int c = in.nextInt() - 1;
      int d = in.nextInt() - 1;
      char[] s = in.next().toCharArray();
      boolean flagA = isReachable(s, a, c);
      boolean flagB = isReachable(s, b, d);
      boolean res = flagA && flagB;
      if (d < c) {
        res &= isOikoshiable(s, b, d);
      }

      out.println(res ? "Yes" : "No");

    }

    private boolean isReachable(char[] s, int from, int to) {
      int now = from;
      while (true) {
        if (s[now + 2] == '.') {
          now += 2;
        } else if (s[now + 1] == '.') {
          now += 1;
        } else {
          break;
        }
        if (now == to - 1 || now == to - 2) {
          return true;
        }
      }
      return false;
    }

    private boolean isOikoshiable(char[] s, int b, int d) {
      // b-1からdの1個手前までのいずれかから3連続で.があればよい
      for (int i = b + 1; i <= d + 1; i++) {
        if (s[i] == '.' && s[i - 1] == '.' && s[i - 2] == '.') {
          return true;
        }
      }
      return false;
    }

  }
}



Measured memory_bytes: 26920
if __name__ == '__main__':
    N = int(input())
    W = list(map(int, input().split()))
    a = float('inf')
    for T in range(1, N):
        S1, S2 = sum(W[:T]), sum(W[T:])
        if a >= abs(S1 - S2):
            a = abs(S1 - S2)
    print(a)
            

Measured memory_bytes: 3060
n = int(input())
L = list(map(int,input().split()))

#L = reversed(L)

#max_a = 10**8
a = 1
ans = 0
for i in range(n):
    if L[i] == a:
        a += 1
    else:
        ans +=1

if ans == n:
    print(-1)
else:
    print(ans)
    




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

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()

using namespace std;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    FOR(i, 1, N) {
        int a;
        cin >> a;
        --a;
        g[a].push_back(i);
    }

    function<int(int)> f = [&](int u) {
        vector<int> fs;
        for (int v: g[u]) {
            fs.push_back(f(v));
        }
        sort(all(fs));
        int result = 0;
        REP(i, fs.size()) {
            amax(result, fs.size() - i + fs[i]);
        }
        return result;
    };

    cout << f(0) << endl;

    return 0;
}

Measured memory_bytes: 13568
N, X = [int(_) for _ in input().split()]

from itertools import permutations

def calc(x):
    # print("*", x)
    def sub(y, debug=0):
        if debug:
            print("D", y)
        while len(y) > 1:
            y = [sorted(y[i:i+3])[1] for i in range(len(y) - 2)]
            if debug:
                print("D", y)
        return y
    y = sub(x)
    if y[0] == 2:
        pass
        sub(x, 1)
        print("=", x)
    return y[0]

#r = set([])
#for x in permutations(range(1, N+ 1)):
#    r.add(calc(x))

if X == 1 or X == N * 2 - 1:
    print("No")
else:
    print("Yes")
    if X == N * 2 - 2:
        xs = list(range(N - 1, X + 2)) + list(range(1, N - 1))
    else:
        ys = list(range(1, X - 1)) + list(range(X + 3, N * 2))
        xs = ys[:N-3] + [X + 2, X - 1, X, X + 1] + ys[N-3:]
    for x in xs:
        print(x)

"""
3 4
1 2 3 4 5
2 3 4 5 1
4 4

"""


Measured memory_bytes: 16088
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define md 1000000007
#define mx 1e18
#define pb push_back
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pii pair<ll int,ll int>
#define ff first
#define ss second


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

	ll int ts=0;

	ll int ar[n+1];
	for(ll int i=1;i<=n;i++)
	{
		cin>>ar[i];
		ts+=ar[i];
	}

	ll int dp[n+1][n+1];
	for(ll int i=0;i<=n;i++)
		for(ll int j=0;j<=n;j++)
			dp[i][j]=0;

	for(ll int i=1;i<=n;i++)
		dp[i][i]=ar[i];

	for(ll int i=n-1;i>=1;i--)
	{
		for(ll int j=i;j<=n;j++)
		{
			dp[i][j]=max(ar[i]+min(dp[i+2][j],dp[i+1][j-1]),ar[j]+min(dp[i+1][j-1],dp[i][j-2]));
		}
	}	

	ll int x=dp[1][n];

	cout<<(2*x)-ts<<endl;

	return 0;
}


Measured memory_bytes: 70656
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    i = 1
    c = 0
    v = [0] * (N + 1)
    while v[i] == 0:
        if A[i - 1] == 2:
            print(c + 1)
            return
        v[i] = 1
        i = A[i - 1]
        c += 1
    print(-1)


main()


Measured memory_bytes: 7852
#define _USE_MATH_DEFINES // M_PI
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using 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,a,n) for(int (i)=(n)-1; (i)>=(a);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 2147483647;
constexpr 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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


int main() {
	init();

	string s; cin >> s;
	map<string, int>mp;
	mp["SUN"] = 7;
	mp["MON"] = 6;
	mp["TUE"] = 5;
	mp["WED"] = 4;
	mp["THU"] = 3;
	mp["FRI"] = 2;
	mp["SAT"] = 1;
	cout << mp[s] << "\n";


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int n;
int cnt = 0;
deque<int> q;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        auto it = lower_bound(q.begin(), q.end(), a);
        if (it == q.begin())
        {
            q.push_front(a);
        }
        else
        {
            q[it - q.begin() - 1] = a;
        }
    }

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

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<double> a(n);
	for(int i=0;i<n;i++)
		cin >> a[i];
	double ans=0;

	for(int i=0;i<n;i++)
		ans+=(1/a[i]);
	cout << fixed << setprecision(8) <<  1/ans << endl;




}


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

// mod1000000007の時の型 mint
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};


int main(){
  int n;
  cin >> n;
  
  mint ans = 1;
  rep(i,n) ans *= i+1;
  cout << ans.x << endl;
  return 0;
}


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

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  int isittrue=0;
  for (int i=0;i<N;i++){
    cin >> A[i] >> B[i] ;
  }
  for(int i=0;i < N-2;i++){
    if(A[i]==B[i] && A[i+1]==B[i+1] && A[i+2]==B[i+2]){
      isittrue=1;
      break;
    }
  }
  if (isittrue==0){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#define int long long
signed main(){
  int start_R,start_L,goal_R,goal_L;
  int len,S_len;
  std::string S;
  std::cin>>S;
  S_len=S.length();
  std::vector<int>ans(S_len,0);
   for (int i=0;i<S_len;i++){
     if(S[i]=='R'){
       if(i==0){
         start_R=0;
       }else if(S[i-1]=='L'){
         goal_L=i-1;
         len=(goal_L-start_L+1);
         ans[start_L]+=(len+1)/2;
         ans[start_L-1]+=len/2;
         start_R=i;
       }
     }else if(S[i]=='L'){
       if(i==S_len-1){
         if(S[i-1]=='R'){
           goal_R=i-1;
           len=(goal_R-start_R+1);
           ans[goal_R]+=(len+1)/2;
           ans[goal_R+1]+=len/2;
           start_L=i;
         }
         goal_L=i;
         len=(goal_L-start_L+1);
         ans[start_L]+=(len+1)/2;
         ans[start_L-1]+=len/2;
       }else if(S[i-1]=='R'){
         goal_R=i-1;
         len=(goal_R-start_R+1);
         ans[goal_R]+=(len+1)/2;
         ans[goal_R+1]+=len/2;
         start_L=i;
       }
     }
   }
for (int i=0;i<S_len-1;i++){
  std::cout<<ans[i]<<" ";
}std::cout<<ans[S_len-1]<<std::endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int a[100005],n;
int gcd(int a,int b)
{if (a%b==0) return b;
return gcd(b,a%b);
}
int main (){
	int i,tar,maxn=0;
	scanf ("%d",&n);
	scanf ("%d",&tar);
	for (i=1;i<=n;i++)
	{scanf ("%d",&a[i]);
	if (a[i]>maxn) {maxn=a[i];}
	}
	int tp=a[1];
	for (i=2;i<=n;i++)
	{tp=gcd(a[i],tp);}
	if (tar%tp==0&&tar<=maxn)
	{printf ("POSSIBLE\n");}
	else {printf ("IMPOSSIBLE\n");}
	return 0;
}

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

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> a(H, vector<char>(W));
  vector<int> H_count(H), W_count(W);
  
  for(int i = 0;i < a.size(); i++){
    for(int j = 0; j < a.at(i).size();j++){
      cin >> a.at(i).at(j);
      if(a.at(i).at(j) == '.'){
        H_count.at(i)++;
        W_count.at(j)++;
      }
    }
  }
  
  for(int i = 0; i < a.size(); i++){
    if(H_count.at(i) == W) continue;
    else {
      for(int j = 0;j < a.at(i).size(); j++){
        if(W_count.at(j) == H){
          if(j % W == W -1){
            cout << endl;
          }
          continue;
        }    
        else{
          cout << a.at(i).at(j);
          if(j % W == W - 1){
            cout << endl;
          }
        }
      }  
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define PI 3.14159265358979
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repp(i, s, e) for(int i = (s); i <= (e); ++i)
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define FAST_IO() ios::sync_with_stdio(0); cin.tie(0)
template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { for (auto x : v) os << x << " "; return os << "\n"; }
template<class U, class V>
ostream& operator<<(ostream &os, const pair<U, V> &p) { return os << "(" << p.first << "," << p.second << ")";}


int main() {
	string s, t; cin >> s >> t;
	int S = sz(s), T = sz(t);
	vector<vector<int>> A(26);
	rep(i, S) {
		A[s[i] - 'a'].push_back(i);
	}
	ll ans = 0;
	int here = -1;
	for(auto &c : t) {
		if(A[c - 'a'].empty()) {
			cout << "-1\n";
			return 0;
		}
		int next = upper_bound(A[c - 'a'].begin(), A[c - 'a'].end(), here) - A[c - 'a'].begin();
		if(next == sz(A[c - 'a'])) {
			next = upper_bound(A[c - 'a'].begin(), A[c - 'a'].end(), -1) - A[c - 'a'].begin();
			ans += A[c - 'a'][next] + S - here;
		} else {
			ans += A[c - 'a'][next] - here;
		}
		// cout << here << "->" << A[c - 'a'][next] << "\n";
		here = A[c - 'a'][next];
	}
	cout << ans << "\n";
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define REP(i, a, b) for (long long i = a; i <= b; ++i)
#define ll long long
using namespace std;

ll n, ans;

inline ll read(){															//¿ì¶Á 
	ll s = 0, w = 1;
	char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) w *= ch == '-' ? -1 : 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
	return s * w;
}

inline void work(){
	n = read();																//ÊäÈën
	ans = (1 + n) * n >> 1;													//ÇóºÍ 
	REP(i, 3, n)															//´Ó3¿ªÊ¼Ã¶¾Ù 
		if (i % 3 == 0 || i % 5 == 0) ans -= i;								//Èç¹ûÊÇ3»ò5µÄ±¶Êý¾Í¼õÈ¥Õâ¸öÊý 
	printf("%lld\n", ans);													//Êä³ö´ð°¸ 
}

int main(){
	work();
	return 0;
}

Measured memory_bytes: 3712
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  int a[n];
  for(int i = 1 ; i <= n ; i++){
    scanf("%d", &a[i]);
  }
  int ans = 0;

  for(int x = 1 ; x <= n ; x++){
    if (x%2 == 1) {
      if (a[x]%2 == 1) {
        ans++;
      }
    }
  }
  printf("%d", ans);
  return 0;
}


Measured memory_bytes: 1724
////////////////////////////////////////////
///                                      ///
///         Template ver. 1 rapel        ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>
//#include <chrono>
//#include <random>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>

#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

const LL MOD = 1e9 + 7;
const int N = 3000;
LL dp[N + 5][N + 5];

int n;
string s;

LL calc(int kiri,int kanan) {
	if(kiri + kanan == 0) return 1;
	LL &res = dp[kiri][kanan];
	if(res != -1) return res;
	res = 0;
	if(s[n - kiri - kanan - 1] == '<') {
		for(int i = 1;i <= kanan;i++) {
			res = (res + calc(kiri + i - 1, kanan - i)) % MOD;
		}
	}
	else {
		for(int i = 1;i <= kiri;i++) {
			res = (res + calc(kiri - i, kanan + i - 1)) % MOD;
		}
	}
	return res;
}

LL pref[N + 5][N + 5];
LL suff[N + 5][N + 5];

void hora(int tc) {
	cin>>n;
	cin>>s;
	dp[0][0] = 1;
	pref[0][0] = 1;
	suff[0][0] = 1;
	for(int i = 1;i < n;i++) {
		for(int j = 0;j <= i;j++) {
			int k = i - j;
			if(s[n - i - 1] == '<' && k != 0) dp[j][k] = suff[j][k - 1];
			else if(s[n - i - 1] == '>' && j != 0) dp[j][k] = pref[j - 1][k];
			pref[j][k] = dp[j][k];
			suff[j][k] = dp[j][k];
			if(j != 0) pref[j][k] = (pref[j][k] + pref[j - 1][k + 1]) % MOD;
		}
		for(int k = 1;k <= i;k++) {
			int j = i - k;
			suff[j][k] = (suff[j][k] + suff[j + 1][k - 1]) % MOD;
		}
	}
	LL tot = 0;
	for(int i = 1;i <= n;i++) {
		tot = (tot + dp[i - 1][n - i]) % MOD;
	}
	cout<<tot<<endl;
}

int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}



Measured memory_bytes: 211328
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val xs = readLine()!!.split(" ").map { it.toLong() }.sorted()

    val dist = mutableListOf<Long>()
    for (i in 0 until xs.size - 1) {
        dist.add(Math.abs(xs[i] - xs[i + 1]))
    }

    dist.sortedDescending().drop(n - 1).sum().let(::println)
}

Measured memory_bytes: 54400
//#pragma GCC optimize "-O3"
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
#include"bits/stdc++.h"

using namespace std;

#define MAX 500002

int n;
vector<int> v;

#define MOD 1000000007

vector<int> xo;

long long int dp[1 << 20][2];

map<int, vector<int> > mp;

int imz[MAX];


long long int solve(vector<int> &idx) {
	long long int leading_zero = 1;
	long long int ot = 0;
	idx.push_back(n);
	long long int las = 0;
	if (xo[n - 1] == xo[idx[0]] || xo[n - 1] == 0) {

	}
	else {
		return 0;
	}
	for (int j = 0; j+1 < idx.size(); j++) {
		las = 0;
		las += leading_zero;

		ot += leading_zero;
		if (ot >= MOD)ot %= MOD;
		int interval = imz[idx[j + 1]-1]-imz[idx[j]];
		/*
		if (idx[j]) {
			interval -= imz[idx[j]];
		}
		*/
		if (interval) {
			las = 0;
			las = ot;
			las%MOD;
		}
		leading_zero += ot * (long long int)(interval);
		leading_zero %= MOD;
	}
	return las;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		v.push_back(a);
	}
	xo = v;
	for (int i = 0; i < v.size(); i++) {
		if(i)xo[i] ^= xo[i - 1];
		mp[xo[i]].push_back(i);
		if (xo[i] == 0) {
			imz[i]++;
		}
		if (i)imz[i] += imz[i - 1];
	}
	long long int ans = 0;
	for (auto &it : mp) {
		if (it.first == 0)continue;
		ans+=solve(it.second);
		ans %= MOD;
	}
	if (mp.count(0)) {
		long long int p1 = 1;
		auto u = mp[0];
		if (u.back() != n - 1) {

		}
		else {
			for (int j = 0; j+1 < u.size(); j++) {
				p1 *= 2LL;
				if (p1 >= MOD)p1 %= MOD;
			}
			ans += p1;
		}
	}
	ans %= MOD;
	printf("%lld\n", ans);
	return 0;
}

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

signed main(){
    // cout << fixed << setprecision(10) << flush;

    int n;
    cin >> n;
    vector<int> r(n), c(n);
    for(int i=0; i<n; i++){
        cin >> r[i] >> c[i];
    }

    // 最後の行列をどうやって掛けるか
    // (i-1)個 * 1個, (i-2) * (1 * 1), (i-3) * (2 * 1), ..., 1 * ((i-2) * 1)
    // のうちから最小を求め、ストックする
    // 0 <= i <= n
    // つまり、左から i 番目から j 番目までかけたときの最小の乗算の数、をストックしておく必要がある
    // dp[i][i] = 0
    // dp[i][j] = min_{i<=i_j<j} ((i ~ i_j までまとめたときの最小値) + r[i]*c[i_j]*c[j] + (i_j+1 ~ j-1 までまとめたときの最小値 + r[i_j+1]*c[j-1]*r[j]))
    // dp[i][j] = min_{i<=i_j<j} (dp[i][i_j] + r[i]*r[i_j]*c[j] + (dp[i_j+1][j-1] + r[i_j]*r[j]*c[j]))
    int INF = 1<<30;
    INF = INF<<30;
    vector<vector<int>> dp(n, vector<int>(n, INF));
    for(int i=0; i<n; i++){
        for(int j=0; j<=i; j++){
            dp[i][j] = 0;
        }
    }
    for(int i=n-1; i>=0; i--){
        for(int j=i+1; j<n; j++){
            dp[i][j] = dp[i][j-1] + r[i]*r[j]*c[j];
            for(int i_j=i; i_j<j; i_j++){
                dp[i][j] = min(dp[i][j], dp[i][i_j] + r[i]*r[i_j+1]*c[j] + (dp[i_j+1][j-1] + r[i_j+1]*r[j]*c[j]));
            }
        }
    }
    cout << dp[0][n-1] << endl;
    return 0;
}


Measured memory_bytes: 3228
//OPTIMIZATONS
#pragma GCC optimize("02")
//CODE
#include<bits/stdc++.h>
// uncomment the below code to use int as long long
#define int long long
// uncomment the below code to use float as double
//#define float double
#define endl "\n"
#define debug cout<<"Good uptill here"<<endl<<flush;
#define deb(x) cout<<#x<<":"<<x<<endl<<flush;

using namespace std;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//CODE FOR SPECIFIED INPUT AND OUTPUT
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin>>n;
	while(n){
		if(n%10==7) break;
		n/=10;
	}
	if(n) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <cstring>

#define INF 1e9

using namespace std;
int w,h;
int wr[32][32];
int wb[32][32];
int dp[32][32];
int v[32][32];

void solve(){
	int x,y,i,j;
	x=0;y=0;
	while(1){
		v[x][y] = 1;
		if(x==w-1 && y==h-1) return;

		if(!wr[y][x  ]) dp[x+1][y] = min(dp[x+1][y], dp[x][y]+1);
		if(!wr[y][x-1] && x) dp[x-1][y] = min(dp[x-1][y], dp[x][y]+1);
		if(!wb[y][x  ]) dp[x][y+1] = min(dp[x][y+1], dp[x][y]+1);
		if(!wb[y-1][x] && y) dp[x][y-1] = min(dp[x][y-1], dp[x][y]+1);
		
		x=w-1;y=h-1;
		for(i=0;i<h;i++)
			for(j=0;j<w;j++){
				if(dp[j][i] == INF || v[j][i]) continue;
				if(dp[j][i] < dp[x][y]){
					x=j,y=i;
				}
			}
		if(v[x][y] || dp[x][y] == INF) return;
	}
}

main(){
	int i,j;
	while(cin>>w>>h, w){
		memset(v, 0, sizeof(v));
		memset(dp, 0, sizeof(dp));
		for(i=0;i<=h;i++)
			for(j=0;j<=w;j++)
				dp[j][i] = INF;
		for(i=0;i<h-1;i++){
			for(j=0;j<w-1;j++){
				cin >> wr[i][j];
			}
			for(j=0;j<w;j++){
				cin >> wb[i][j];
			}
		}
		for(j=0;j<w-1;j++){
			cin >> wr[i][j];
		}
		dp[0][0] = 1;
		solve();
		if(dp[w-1][h-1] != INF) cout << dp[w-1][h-1] << endl;
		else cout << 0 << endl;
	}
}

Measured memory_bytes: 880
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <deque>     // deque
#include <iomanip>   //setprecsion
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <utility>   // pair, make_pair
#include <vector>    // vector

#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>  //sin, cos, tan

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

void Main()
{
  ll n, k; cin >> n >> k;
  vb flag(n, true);
  rep(i, k)
  {
    ll d; cin >> d;
    for(ll j = 0;j < d;j++)
    {
      ll D; cin >> D;
      flag[D - 1] = false;
    }    
  }
  ll f = 0;
  rep(i, n)
  {
    if(flag[i]) f++;
  }
  fin(f);
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  //cout << setfill('0') << internal << setw(4); 0埋め４桁
  Main();
  return 0;
}


Measured memory_bytes: 3660
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
#define int long long
#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279; //円周率
/*---------------------便利な関数--------------------------------------*/
int fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}

int gcd(int a, int b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {      //最小公倍数
    return a * b / gcd(a, b);
}

int keta(int n) {        //桁数を求める
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}

int ketasum(int n) {    //各桁の和
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/*-------------ここまで---------------------------------------------*/

//C++(GCC9.2.1)

signed main() {
    //宣言
    int n;
    cin >> n;
    string s;
    cin >> s;
    if (n % 2 == 1) cout << "No" << "\n";
    else {
        int l = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (s[i] == s[n / 2 + i]) ++l;
            else continue;
        }
        if (l == n / 2) cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
    return 0;
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define LL long long
#define DB double
#define INF 1145141919810364364
#define PI 3.14159265358979
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)<(y)?(y):(x))
#define FOR(i,a,n) for(i=a;i<n;i++)
#define rep(i,n) FOR(i,0,n)
#define MOD 1000000007
//#define MOD 998244353
#define ERR 0.00000000000001
#define NUM 200010

void swap(LL* a,LL* b){LL tmp=*a;*a=*b;*b=tmp;}
void YN(int a){if(a==1)printf("Yes\n");if(a==0)printf("No\n");}
LL pwmn(LL a,LL n){LL ans=1;while(ans<a)ans*=n;return ans;}
LL GCD(LL a,LL b){LL c=1,tmp=MAX(a,b);b=MIN(a,b);a=tmp;while(c!=0){c=a%b;a=b;b=c;}return a;}
LL LCM(LL a,LL b){return a*b/GCD(a,b);}
int lcmp(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return 1;if(*(LL*)a<*(LL*)b)return -1;return 0;}
int lcmpr(const void* a,const void* b){if(*(LL*)a>*(LL*)b)return -1;if(*(LL*)a<*(LL*)b)return 1;return 0;}
int ccmp(const void* a,const void* b){return *(char*)a-*(char*)b;}
int ccmpr(const void* a,const void* b){return *(char*)b-*(char*)a;}
int scmp(const void* a,const void* b){return strcmp((char*)a,(char*)b);}
int scmpr(const void* a,const void* b){return strcmp((char*)b,(char*)a);}
LL mod(LL a,LL m){if(a<0)return a%m+m;else return a%m;}
LL DIV(LL a,LL d){LL m=MOD,x=1,y=0,k;while(m){k=d/m;d-=k*m;swap(&m,&d);x-=k*y;swap(&x,&y);}return mod(a*mod(x,MOD),MOD);}
LL FAC(LL a){LL i,ans=1;FOR(i,1,a+1){ans*=i;if(MOD>0&&ans>MOD)ans%=MOD;}return ans;}
LL POW(LL a,LL n){LL ans=1;while(n>0){if(n&1)ans=ans*a%MOD;a=a*a%MOD;n>>=1;}return ans;}
LL fact[NUM],finv[NUM],inv[NUM];
void comi(){LL i;fact[0]=fact[1]=1;finv[0]=finv[1]=1;inv[1]=1;FOR(i,2,NUM){fact[i]=fact[i-1]*i%MOD;inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}
LL com(LL n,LL k){if(n<k||n<0||k<0)return 0;return fact[n]*(finv[k]*finv[n-k]%MOD)%MOD;}

int main(){
  LL L,i,ans=0;
  DB l;
  scanf("%lld",&L);
  l=L/3.0;

  printf("%.10f\n",l*l*l);
	return 0;
}


Measured memory_bytes: 128
def examA():
    S = SI()
    T = SI()
    if S==T[:len(S)]:
        if len(S)+1==len(T):
            print("Yes")
            return
    print("No")
    return

def examB():
    A, B, C, K = LI()
    ans = 0
    if A>=K:
        ans = K
    else:
        ans += A
        K -= A
        if K>B:
            K -= B
            ans -= K
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examB()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 81340
#include <iostream>

using namespace std;

int main() {
    int w, h, x, y, r;
    
    cin >> w >> h >> x >> y >> r;
    if (((x-r) >= 0 && (x+r) <= w) && ((y-r) >= 0 && (y+r) <= h)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3108
#include <stdio.h>

void sort(int *a,int n)
{
     int i,j,index,max;
     for(i=0;i<n;i++){
       max=a[i];index=i;
           for(j=i+1;j<n;j++)
             if(max<a[j]){
               max=a[j];index=j;
             }
             a[index]=a[i];a[i]=max;
     }
     return ;
}
int main(void)
{
      int n,i,s;
      scanf("%d",&n);
      int a[n];
      for(i=0;i<n;i++)
        scanf("%d",&a[i]);
      sort(a,n);
      s=a[0]-a[n-1];
      printf("%d",s);
      return 0;
}

Measured memory_bytes: 1704
/*
          .  .
          |\_|\
          | a_a\
          | | "]
      ____| '-\___
     /.----.___.-'\
    //        _    \
   //   .-. (~v~) /|
  |'|  /\:  .--  / \
 // |-/  \_/____/\/~|
|/  \ |  []_|_|_] \ |
| \  | \ |___   _\ ]_}
| |  '-' /   '.'  |
| |     /    /|:  |
| |     |   / |:  /\
| |     /  /  |  /  \
| |    |  /  /  |    \
\ |    |/\/  |/|/\    \
 \|\ |\|  |  | / /\/\__\
  \ \| | /   | |__
       / |   |____)
       |_/
*/

#include <bits/stdc++.h>

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define mxn 100005
using namespace std;



int main()
{
    FLASH
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    if(k <= a)
    {
        cout << k;
    }
    else
    { 
      ll ans = a;
      k -= a;
      if(k <= b)
      {
        cout << ans;
      }
      else
      {
        k-=b;
        cout << ans - k;
      }
    }
    return 0;
}



Measured memory_bytes: 3652