akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int A, B, N;
signed main() {
    cin >> A >> B >> N;
    if (B - 1 <= N) { cout << (B - 1) * A / B << endl; }
    else { cout << N * A / B << endl; }
}


Measured memory_bytes: 3628
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b)	memset(a, b, sizeof a)
#define REP(i, x, n)	for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int DEG = 18;
vector<int> e[qq], f[qq];
int in[qq], out[qq], TimeTag;
LL dep[qq];
int fa[qq][DEG];
/*void Dfs(int u) {
	in[u] = ++TimeTag;
	for(int i = 1; i < DEG; ++i) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for(int i = 0; i < (int)e[u].size(); ++i) {
		int v = e[u][i];
		dep[v] = dep[u] + f[u][i];
		fa[v][0] = u;
		Dfs(v);
	}
	out[u] = TimeTag;
}*/
int x[qq], y[qq];
void Dfs(int u, int fa, LL dis) {
	dep[u] = dis;
	for(int i = 0; i < e[u].size(); ++i) {
		int v = e[u][i];
		if(v == fa)	continue;
		Dfs(v, u, dis + f[u][i]);
	}
}

int main(){
	int n;	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		int a, b;	LL c;
		scanf("%d%d%lld", &a, &b, &c);
		e[a].pb(b), e[b].pb(a);
		f[a].pb(c), f[b].pb(c);
	}
	int q, k;	scanf("%d%d", &q, &k);
	Dfs(k, -1, 0);
	for(int i = 1; i <= q; ++i) {
		int a, b;	scanf("%d%d", &a, &b);
		printf("%lld\n", dep[a] + dep[b]);
	}
	return 0;
}

Measured memory_bytes: 23808
#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

int Q;
deque <char> dq;
bool isReversed;

int main()
{
    char temp[100005];
    scanf(" %s", &temp);
    for (int i = 0; i < strlen(temp); i++) dq.push_back(temp[i]);
    scanf("%d", &Q);
    while (Q--)
    {
        int T; scanf("%d", &T);
        if (T == 1) isReversed = !isReversed;
        else
        {
            int F; char C;
            scanf("%d %c", &F, &C);
            if ((F == 1 && !isReversed) || (F == 2 && isReversed)) dq.push_front(C);
            else dq.push_back(C);
        }
    }
    if (isReversed)
    {
        while (!dq.empty())
        {
            char cur = dq.back(); dq.pop_back();
            printf("%c", cur);
        }
        printf("\n");
    }
    else
    {
        while (!dq.empty())
        {
            char cur = dq.front(); dq.pop_front();
            printf("%c", cur);
        }
        printf("\n");
    }
    return 0;
}


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

int main() {
  long long N,K;
  cin >> N >> K;
  for(int i=0;;i++){
    if(abs(N - K) >= N){
      break;
    }else{
      N = abs(N - K);
    }
    if (N >= K){
      N = N % K;
    }
  }
  cout << N << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W,sum=0;
  cin>>H>>W;
  vector<string>s(H);
	for(int i=0;i<H;i++){
      cin>>s.at(i);
    
      }
 for(int i=0;i<H;i++){
 
    for(int j=0;j<W;j++){
      
     if(s.at(i).at(j)=='#'){
       cout<<"#";
     }else{
      
       for(int k=-1;k<2;k++){
         for(int m=-1;m<2;m++){
           if(i+k<H && i+k>=0 && j+m<W && j+m>=0){
             if(s.at(i+k).at(j+m)=='#'){
             	sum++;
             	
             }
           }//if
         }//for
      
       }//for
       cout<<sum;
       
     	sum=0;
 
      }//else
      

    }//for
   cout<<endl;
  }//for
}//main
 
  
  

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int a,b,c;
    while(cin >>a >>b >>c,a|b|c)
    {
        int n;
        cin >>n;

        //??¨???????¨????????????°
        int m=a+b+c;
        //????????????????????????
        vector<int> v(m,2);

        vector<int> x(n),y(n),z(n),r(n);
        rep(i,n)
        {
            scanf(" %d %d %d %d",&x[i],&y[i],&z[i],&r[i]);
            --x[i];
            --y[i];
            --z[i];
        }

        //????????£?????????????????????????????????????????¨?????£???
        rep(i,n)
        {
            if(r[i]==0) continue;

            v[x[i]]=1;
            v[y[i]]=1;
            v[z[i]]=1;
        }

        //??????????????????????????????
        rep(t,n)rep(i,n)
        {
            if(r[i]==1) continue;
            //??????2????????£???(1)??§?¢??????????????????°???????????????(0)

            if(v[x[i]]==1 && v[y[i]]==1) v[z[i]]=0;
            if(v[y[i]]==1 && v[z[i]]==1) v[x[i]]=0;
            if(v[z[i]]==1 && v[x[i]]==1) v[y[i]]=0;
        }

        //output
        rep(i,m) printf("%d\n",v[i]);
    }
    return 0;
}

Measured memory_bytes: 3136
#include <iostream>
#include <string>

using namespace std;

// Solution

int main() {
    int n;
    cin >> n;
    int x = n % 10;
    if (x == 2 || x == 4 || x == 5 || x == 7 || x == 9) {
        cout << "hon";
    } else if (x == 0 || x == 1 || x == 6 || x == 8) {
        cout << "pon";
    } else {
        cout << "bon";
    }
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define pb(a) push_back(a)
#define MAX(a, b) ((a < b)?b:a)
#define MIN(a, b) ((a > b)?b:a)
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;

template<typename T> void cinpb(vector<T>& x) { T n; cin >> n; x.push_back(n); }
ull gcd(ull a, ull b) { return b ? gcd(b, a%b) : a; }
ull lcm(ull m, ull n) {	return ((0 == m) || (0 == n)) ? 0 : ((m / gcd(m, n)) * n); }
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void yesno(bool f) { cout << (f ? "Yes" : "No") << endl; }

void solve();

int main()
{
#ifdef _DEBUG
	std::ifstream in("input.txt");
	std::cin.rdbuf(in.rdbuf());
#endif


#ifdef _DEBUG
	int caseNo = 1;
	while ( !cin.eof() )
	{
		cout << "---------case" << caseNo << "---------" << endl;
#endif

		solve();

#ifdef _DEBUG
		caseNo++;
	}
#endif

	return 0;
}

//

void solve()
{
	int a, b;
	cin >> a >> b;

	int sum = 0;

	if ( a > b )
	{
		sum += a;
		a--;
	}
	else
	{
		sum += b;
		b--;
	}
	if ( a > b )
	{
		sum += a;
		a--;
	}
	else
	{
		sum += b;
		b--;
	}

	cout << sum << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

const int N = 26, D = 365;

using namespace std;
int main() {
    int d;
    cin >> d;
    vector<int> c(N);
    vector<vector<int>> s(D, vector<int>(N));
    for (int i = 0; i < N; ++i)
        cin >> c[i];
    for (int i = 0; i < d; ++i)
        for (int j = 0; j < N; ++j)
            cin >> s[i][j];
    vector<int> ans;
    vector<int> last(N, 0);
    for (int i = 1; i <= d; ++i) {
        int maxt = 0;
        double maxg = INT_MIN;
        for (int j = 0; j < N; ++j) {
            double gain = s[i - 1][j];
            for (int k = 0; k < N; ++k)
                if (k != j)
                    gain -= 1.2 * c[k] * (i - last[k]);
            if (gain > maxg) {
                maxg = gain;
                maxt = j;
            }
        }
        last[maxt] = i;
        ans.emplace_back(maxt + 1);
    }
    for (int i : ans)
        cout << i << endl;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

// BIT
// initialize : FenwickTree(n)
// add(pos, n): data[pos] += n;
// sum(l, r)  : sum [l, r)
template <typename T>
class FenwickTree
{
    const int n;
    vector<T> data;

  public:
    FenwickTree(int count) : n(count), data(count, 0) { ; }

    void add(int pos, const T &value)
    {
        assert(0 <= pos && pos < n);
        for (int i = pos; i < n; i |= i + 1)
            data[i] += value;
    }

    T sum(int pos) const
    {
        assert(0 <= pos && pos <= n);
        T res = 0;
        for (int i = pos - 1; i >= 0; i = (i & (i + 1)) - 1)
        {
            res += data[i];
        }
        return res;
    }

    T sum(int l, int r) const
    {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) + (-sum(l));
    }
    using value_type = T;
    using update_type = T;
};

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

    ll N;
    cin >> N;
    vector<ll> a(N), raw(N);
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        raw[i] = a[i];
    }
    sort(raw.begin(), raw.end());
    raw.erase(unique(raw.begin(), raw.end()), raw.end());
    for (int i = 0; i < N; i++)
    {
        a[i] = lower_bound(raw.begin(), raw.end(), a[i]) - raw.begin();
    }
    // m_l,r := (a_l, ..., a_r) の中央値
    int low = 0, high = raw.size();
    while (high - low > 1)
    {
        int mid = (low + high) / 2;
        // a[l,r] (1<=l<=r<=N) の内, (mid 未満の要素数 -> -1) <= (mid 以上の要素数 -> +1) を満たすものの個数
        // <=> a[l,r] の内, 要素の総和が 0 以上のものの個数
        vector<int> sum(N + 1, 0);
        sum[0] = N;
        for (int i = 0; i < N; i++)
        {
            sum[i + 1] = sum[i];
            if (a[i] < mid)
                sum[i + 1]--;
            else
                sum[i + 1]++;
        }
        ll cnt = 0;
        FenwickTree<int> ft(2 * N + 1);
        for (int i = 0; i <= N; i++)
        {
            cnt += ft.sum(sum[i] + 1);
            ft.add(sum[i], 1);
        }

        ll c = N * (N + 1) / 2;
        c = (c + 1) / 2;

        if (cnt >= c)
            low = mid;
        else
            high = mid;
    }
    cout << raw[low] << endl;
}


Measured memory_bytes: 3052
MOVE = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]
answers = {"01234567": 0}

def swap(field, a, b):
  tmp = list(field)
  tmp[a], tmp[b] = tmp[b], tmp[a]
  return "".join(tmp)

def breadth_first_search(answers):
  q = [[0, "01234567"]]

  while len(q) != 0:
    g, field = q.pop(0)
    a = field.find("0")

    for b in MOVE[a]:
      tmp = swap(field, a, b)

      if not tmp in answers:
        answers[tmp] = g+1
        q.append([g+1, tmp])

  return answers

answers = breadth_first_search(answers)

while True:
  try:
    print answers[raw_input().replace(" ", "")]
  except:
    break

Measured memory_bytes: 6076
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main(void) {
	ll n,m;
	cin>>n>>m;
	vector<pair<ll,ll> > vp;
	rep(i,0,m){
		ll a,b;
		cin>>a>>b;
		a--;b--;
		vp.pb(mp(a,b));
	}
	priority_queue<ll, vector<ll>, greater<ll> > q; 
	sort(all(vp));
	ll index = 0;
	ll ans = 0;
	rep(i,0,n){
		if((!q.empty())&&q.top()==i){
			ans++;
			while((!q.empty())&&q.top()>=i){
				q.pop();
			}
		}
		while(index<m&&vp[index].fi==i){
			q.push(vp[index].se);
			index++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
	int a,b,k;
	cin >> a >> b >> k;

	for (int i=a;i<=b;i++) {
		if ((i<(a+k)) || (i>(b-k))) cout << i << endl;
	}
	
	return 0;
}


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

public class Main {
	public static void main (String[] args) throws Exception {
		SC sc=new SC(System.in);
		int H=sc.nextInt();
		int W=sc.nextInt();
		int D=sc.nextInt();
		int[][] map=new int[H*W+1][2];
		int[][] ary=new int[H][W];
		int[][] ans=new int[D][H*W/D+2];
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				ary[i][j]=sc.nextInt();
				map[ary[i][j]][0]=i;
				map[ary[i][j]][1]=j;
			}
		}
		for(int i=0; i<D; i++) {
			for(int j=i; j<=H*W; j+=D) {
				if(j==i) {
					ans[i][0]=0;
				}
				else {
					ans[i][(j-i)/D]=Math.abs(map[j][0]-map[j-D][0])+Math.abs(map[j][1]-map[j-D][1]);
					ans[i][(j-i)/D]+=ans[i][(j-i)/D-1];
				}
			}
		}
		int Q=sc.nextInt();
		for(int i=0; i<Q; i++) {
			int from=sc.nextInt();
			int to=sc.nextInt();
			int mod=from%D;
			if(from<D) {
				pl(ans[mod][(to-mod)/D]);
			}
			else{
				pl(ans[mod][(to-mod)/D]-ans[mod][(from-mod)/D]);
			}
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}

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

typedef long long ll;

int32_t main( )       {

    int n;
    ll sum=0;
    cin>>n;

    for(int i=1;i<=n;i++)    {
        ll num = n / i;
        sum+=(num*(num+1)*i) / 2;
    }
 cout<<sum;


return 0;
}


Measured memory_bytes: 3596
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

int H, W;
vector<string> S;
vvi board(101, vi(101));
vector<pair<int, int> > dd;

void dfs(int i, int j) {
    if(i > H-1 || j > W-1){
        return;
    }
    if(!board[i][j+1] || !board[i+1][j]){
        return;
    }
    int u, l;
    if(S[i][j+1] == S[i+1][j+1]){
        u = board[i][j+1];
    } else {
        u = 1 + board[i][j+1];
    }
    if(S[i+1][j] == S[i+1][j+1]) {
        l = board[i+1][j];
    } else {
        l = 1 + board[i+1][j];
    }
    board[i+1][j+1] = min(u, l);
    //cout << i+1 << ',' << j+1 << endl;
    dfs(i+1, j);
    dfs(i, j+1);
}

int main() {
    cin >> H >> W;
    S.push_back("");
    rep(i, W+1) {
        S[0].push_back('.');
    }
    rep (i, H) {
        S.push_back("");
        S[i+1] += '.';
        string r;
        cin >> r;
        S[i+1] += r;
        /*rep(j, W){
            S[i+1] += '#';
        }*/
        board[i+1][0] = 500;
    }
    rep(i, W) {
        board[0][i+1] = 500;
    }
    board[0][1] = 1;
    board[1][0] = 1;
    dfs(0, 0);
    cout << board[H][W]/2 << '\n';
}

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

using namespace std;

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

    vector<int> H(N);
    vector<int> DP(N);

    for(int& x : H) cin >> x;
    DP[0] = 0;
    DP[1] = abs( H[0] - H[1] );
    for(int i = 2; i < N; ++i) {
        DP[i] = min( DP[i - 1] + abs( H[i - 1] - H[i] ), 
                     DP[i - 2] + abs( H[i - 2] - H[i]) );
    }
    
    cout << DP[N - 1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<string>

using namespace std;
int main()
{
    // 整数の入力
    int j,x;
    string s;
    cin >> s;
    x=0;

    // 出力
    j = s.length()-1;
    for (int i = 0; i < s.length()/2; ++i) {
        
//                cout << s.substr(i,1) << " " << s.substr(j,1) <<endl;
                if(s.substr(i,1)!=s.substr(j,1)){
                    ++x;
                }

        j--;     
    }
    cout << x << endl;

    return 0;
}

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

int main(){
  int h, w, n;
  cin >> h >> w;
  cin >> n;
  int ans[h+1][w+1];
  int a[n+1];
  rep(i, n) cin >> a[i+1];
  bool r = true;
  P pos = P(1, 1);
  for(int i = 1; i <= n; i++){
    rep(j, a[i]){
      ans[pos.first][pos.second] = i;
      if(r){
        if(pos.second == w){
          pos.first++;
          r = false;
        } else pos.second++;
      } else {
        if(pos.second == 1){
          pos.first++;
          r = true;
        } else pos.second--;
      }
    }
  }
  rep(i, h){
    rep(j, w) cout << ans[i+1][j+1] << " ";
    cout << endl;
  }
  return 0;
}


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

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int t = sc.NextInt();
        int x = sc.NextInt();

        double answer = (double)t / x;

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13140
def resolve():
    '''
    code here
    '''
    A, B, C, K = [int(item) for item in input().split()]

    A_max = min(A, K)
    B_max = min(B, K - A_max)
    C_max = K - A_max - B_max

    print(A_max - C_max)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 9112
import java.util.Scanner;
class Main{
    public static void main(String[] args) {
        Scanner scn=new Scanner(System.in);
        int a=scn.nextInt();
        int b=scn.nextInt();
        int c=scn.nextInt();
        if(a-b==0){
            System.out.println(c);
        }else if(a-c==0){
            System.out.println(b);
        }else{
            System.out.println(a);
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    int K;
    Scd2(N,K);

    vi a(N);
    Rep(i,N){
        Scd(a[i]);
    }

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

    vi dp(K);

    int lb = -1;
    int ub = N;
    // [l,u)

    while( ub - lb > 1 ){
        int mid = (lb+ub) / 2;

        if( a[mid] >= K ) {
            ub = mid;
            continue;
        }

        dp.assign(K+3,0);
        dp[0] = 1;

        Rep(i,N){
            if( a[i] >= K ) break;
            if( i == mid ) continue;
            RRep(k,K-a[i]){
                dp[k+a[i]] = dp[k] & 1;
            }
        }

        bool isNeed = false;
        Repe(k,K,K-a[mid]){
            if( dp[k] ) isNeed = true;
        }


        if( isNeed ) ub = mid;
        else lb = mid;

        // printf ("!%d[%d]?%d [%d,%d)\n", a[mid], mid, isNeed, lb, ub );

    }

    printf ("%d\n", lb + 1 );


    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

int main() {
    reg int a = read(), b = read();
    if (a < 1 || a > 9) { puts("-1"); return 0; }
    if (b < 1 || b > 9) { puts("-1"); return 0; }
    cout << a * b << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

ll A, B, N;
// vector<int> A;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> A >> B >> N;
  // A.resize(N);
  // for (int i = 0; i < N; i++) {
  //   int tmp;
  //   cin >> tmp;
  //   A[i] = tmp;
  // }

  ll ans = 0;
  if (N < B) {
    ans = (A * N / B) - (A * (N / B));
  } else {
    ans = (A * (B - 1) / B) - (A * ((B - 1) / B));
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);
    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */

ll N; 

ll f(int a, int b) {
    ll res = 0;
    repr(i, 1, N+1) {
        if(i%10 == b && to_string(i)[0] == ('0'+a)) ++res;
    }
    return res;
}

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

    cin >> N;
    ll ans = 0;

    repr(i, 1, 10) repr(j, 1, 10) ans += f(i, j) * f(j, i);
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define abdelrahman001 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef long double ld;
using namespace std;
int main()
{
    abdelrahman001
    string s;
    cin >> s;
    if(s[0] == 'S')
        return cout << "Cloudy",0;
    if(s[0] == 'C')
        return cout << "Rainy",0;
    cout << "Sunny";
    return 0;
}


Measured memory_bytes: 256
/*************************
author : coldbeer
2019-05-20 11:17:49 PM IST
*************************/
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

const int N = (int)1e5 + 5;
typedef pair<int,int> pii;
typedef long long ll;
vector<pii> graph[N];

bool visited[N];
int clr[N];

void color(int src,ll dist = 0){
	visited[src] = true;
	for(auto itr : graph[src]){
		int child = itr.first;
		ll d = itr.second + dist;
		if(!visited[child]){
			if(d&1)
				clr[child] = 1;
			else
				clr[child] = 0;
			color(child,d);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 0;i < n - 1;i++){
		int u,v,w; cin >> u >> v >> w;
		graph[u].push_back({v,w});
		graph[v].push_back({u,w});
	}

	color(1,0);

	for(int i = 1;i < n + 1;i++)
		cout << clr[i] << endl;
	return 0;
}


Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  cin >> n>>k;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    int h;
    cin >> h;
    a.at(i)=h;
  }
  sort(a.begin(),a.end());
  int ans=1<<30;
  for(int i=0;i+k-1<n;i++){
    int mi = a.at(i+k-1)-a.at(i);
    ans =min(ans,mi);
  }
  cout << ans;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int price[3] = {0};
	rep (i, 3) cin >> price[i];

	sort(price, price + 3);
	
	int res = 0;
	rep (i, 2) res += price[i];

	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int N,M,X;
    while(cin>>N){
        cin>>M>>X;
        int left=0,right=0;
        int*p=new int[100];
        for(int i=0;i<M;i++){
            cin>>p[i];
            if(p[i]>X)right++;
            else left++;
        }
        cout<<(left>right?right:left)<<endl;
    }
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ran 202222
int n,A[20][ran];
int a[ran];
int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int t=0; t<20; t++)
	for(int i=1; i<=n; i++)
		if(a[i]&(1<<t))
			A[t][i] = i;
		else
			A[t][i] = A[t][i-1];
	long long int res = 0;
	for(int i=1; i<=n; i++){
		int mx = 0;
		for(int t=0; t<20; t++)
			if(A[t][i] > 0)
				mx = max(mx, A[t][A[t][i]-1]);
		res += i - mx;
	}
	cout << res << endl;
	return 0;
}


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

using namespace std;

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

    string s = to_string(n);
    int sn = 0;
    for (int i = 0; i < s.size(); i++)
    {
        sn += s[i] - '0';
    }

    if(n % sn == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())


trans = [a, b, c, d, e]
neck = min(trans)

if n % neck == 0:
    print(n // neck + 4)
else:
    print(n // neck + 5)


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

int main()
{
  string s, t;
  cin >> s;
  
  for (int i=0; i<s.size(); i++) {
	if (s.at(i) == '0') t.push_back('0');
    else if (s.at(i) == '1') t.push_back('1');
    else {
      if (t.size() != 0) t.pop_back();
    }
  }
  cout << t << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n, k;
	cin >> n >> k;
	vector<int> v(n, 0);
	
	
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		int b[a];
		for(int j = 0; j < a; j++){
			cin >> b[j];
			v[b[j] - 1]++;
			}
		}
		
		int c = 0;
		for(int i = 0; i < n; i++){
			if(v[i] == 0){
				c++;
				}
			}
		cout << c;
			}


Measured memory_bytes: 3628
N = int(input())
lst = list(map(int, input().split()))
def printInt(L):
    print(" ".join(map(str, L)))
for i in range(N):
    j = 0
    while j < i:
        if lst[j] > lst[i]:
            break
        j += 1
    tmp = lst[i]
    for x in range(i, j, -1):
        lst[x] = lst[x - 1]
    lst[j] = tmp
    printInt(lst)


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

int main(void)
{
    int n;
    cin >> n;
    vector<int> l(n+1),r(n+1);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin >> a >>b;
        l[i]=a,r[i]=b;
    }
    sort(l.rbegin(),l.rend());
    sort(r.begin(),r.end());
    ll ans=0;
    for(int i=0;i<=n;i++)
    {
        if(l[i]>r[i])
        {
            ans+=2*(l[i]-r[i]);
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main(int argc, char *argv[]) {
	string S;
	cin >> S;
	int K;
	cin >> K;

	vector<string> subs(K);
	for (int i = 0; i < S.size(); i++) {
		for (int j = i; j < S.size(); j++) {
			string s = S.substr(i, j - i + 1);
			if (!subs.back().empty() && s >= subs.back()) break;

			for (int k = 0; k < K; k++) {
				if (s == subs[k]) break;
				if (s < subs[k] || subs[k].empty()) {
					subs.insert(subs.begin() + k, s);
					subs.pop_back();
					break;
				}
			}
		}
	}

	cout << subs.back() << endl;
}

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

int main() {
  map<char,int> mp;
  rep(i,4){
    char s; cin >> s;
    auto itr = mp.find(s);        // "s" が設定されているか？
    if( itr != mp.end() )
      mp[s]++;
    else
      mp[s] = 1;
  }
  
  bool ok = true;
  for(auto it = mp.begin(); it!=mp.end(); it++){
    if(it->second != 2)
      ok = false;
    //cout << it->second << endl;
  }
  if(mp.size() != 2)
    ok = false;
  //cout << mp.size() << endl;
  
  if(ok)  cout << "Yes" << endl;
  else  cout << "No" << endl;
}

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

Measured memory_bytes: 128
#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 rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define show(x) cout << #x << " = " << (x) << endl;
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//cout << fixed << setprecision(10);

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

int main () {
  int a, b;
  cin >> a >> b;
  for (int i = 1; i <= 3; ++i) {
    if (i != a && i != b) cout << i << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define repr(i,a,b) for (int i = a; i > b; --i)
#define mm(lamb, tttt) memset(lamb, tttt, sizeof lamb)
 
#define null NULL
#define eps 0.000000001
#define mod 1000000007
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define sz(V) (int)V.size()
#define _ <<" "<<
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<ii> vii;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 	ll ans = 1;
	//freopen ("test.txt","r",stdin);
 	int n;cin>>n;
 	int a[n];
 	for (int i = 0; i < n; ++i)
 	{
 		cin>>a[i];
 	}
 	int dp[n+1] = {0};
 	dp[1] = 0;
 	dp[2] = abs(a[1] - a[0]);

 	for (int i = 3; i <= n; ++i)
 	 {
 	 	dp[i] = min(dp[i-1] + abs(a[i-1] - a[i - 2]) ,
 	 		     dp[i-2] + abs(a[i-1] - a[i-3])); 
 	 } 

 	 cout<<dp[n];
}

Measured memory_bytes: 1024
using System;
using System.Linq;
namespace a
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var N = Console.ReadLine();
            var n = N.Length;
            string A = N.Substring(n-1);
            if (A=="2" || A== "4" ||A == "5" || A == "7" || A == "9")
            {
                Console.WriteLine("hon");
            }
            else if(A == "0" || A == "1" || A == "6" || A == "8")
            {
                Console.WriteLine("pon");
            }
            else
            {
                Console.WriteLine("bon");
            }
        }
    }
}


Measured memory_bytes: 25872
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); //入出力高速化
  while (true) {
    int N; cin >> N;
    if (N == 0) break;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    sort(all(A));
    ll sum = accumulate(A.begin()+1,A.end()-1,0);
    cout << sum / (N-2) << endl;
  }
}


Measured memory_bytes: 3172
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc097/tasks/abc097_b

int main() {
    int x; cin >> x;
    vector<int> exp(x+5);
    exp[1] = 1;

    for (int i = 2; i < x; i++) {
        int v = i * i;
        while (v <= x) {
            exp[v] = 1;
            v *= i;
        }
    }

    for (int i = x; i >= 0; i--) {
        if (exp[i]) {
            cout << i << "\n";
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(), v.end()
#define mod 1000000007
#define mod2 1000000006
#define inf 1000000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<lli>
#define vii vector<int>
#define is indexed_set
#define eps 0.000001
#define endl '\n'
#define mo 998244353
#define pi 3.141592653589793
#define fi first
#define se second
using namespace std ;
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
void solve()
{
		lli n;
		cin>>n;
		lli a[n];
		for(lli i=0;i<n;i++)cin>>a[i];
		lli ani=0;
		for(lli i=0;i<n-1;i++){
			if(a[i+1]>=a[i])continue;
			ani+=a[i+1]-a[i];
			a[i+1]=a[i];
		}
		cout<<-1*ani;

}
 
int main()
{
/////////////////////////////////////
    fastio;
    
/////////////////////////////////////  
    lli t,m;
    //cin>>t;
    t=1;
    m=1;
    while(t--)
    {
    	//cout<<"Case #"<<m<<":"<<endl;
    	solve();  
    	m++;  
    }
}

Measured memory_bytes: 5172
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <climits>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define RFOR(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int INF = 1e9;
const ll LL_INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;
int dist[100005];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int K;
  cin >> K;
  deque<pair<int, int> > dq;
  fill(dist, dist + K + 1, INF);
  dq.push_back({1, 1});
  while(not dq.empty()){
    int u, cost;
    tie(u, cost) = dq.front();
    dq.pop_front();
    dist[u] = min(cost, dist[u]);
    if(dist[u*10 % K] == INF) dq.push_front({u*10%K, cost});
    if(u % 10 != 9 && dist[(u + 1)%K] == INF) dq.push_back({(u + 1)%K, cost + 1});
  }
  cout << dist[0] << endl;
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
using namespace std;
int main() {
    int n, m, a;
    cin >> n >> m;
    for(int i=0; i<m; i++) {
        cin >> a;
        n -= a;
    }
    if (n < 0) {
        n = -1;
    }
    cout << n << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

int main() {
	int n; std::cin >> n;
	std::vector<int> order(n), base(n), additional(n - 1);
	for (auto& a : order) {
		std::cin >> a; --a;
	}
	for (auto& b : base) std::cin >> b;
	for (auto& c : additional) std::cin >> c;
	int result = std::accumulate(base.begin(), base.end(), 0);
	for (auto i = 1; i < n; ++i) {
		if (order[i] == order[i - 1] + 1) {
			result += additional[order[i] - 1];
		}
	}
	std::cout << result << std::endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

inline void readChar(char &c) {
	for (c = getchar(); c != '.' && c != '#'; c = getchar());
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 2e5;
int n, a, b, c, d, cnt, lastRock;
char s[MAXN + 5];

int main() {
	read(n), read(a), read(b), read(c), read(d);
	if (d < c) swap(a, b), swap(c, d);//确保 d > c 
	for (int i = 1; i <= n; ++i) readChar(s[i]);
	for (int i = a; i <= c; ++i)
		if (s[i] == '#' && s[i - 1] == '#') {
			puts("No");
			return 0;
		}
	for (int i = b; i <= d; ++i)
		if (s[i] == '#' && s[i - 1] == '#') {
			puts("No");
			return 0;
		}
	if (a < b) {//b 先到 d，a 再到 b 
		puts("Yes");
		return 0;
	}
	for (int i = b; i <= d; ++i)//让 a 到一个合适的位置，使 b 能够到达 d
		if (s[i] == '#') {
			if (lastRock && ((i >= a + 2 && i <= c) || (lastRock >= a && lastRock <= c - 2) || 
			(lastRock < a && i > c)) && i - lastRock > 3) {
				puts("Yes");
				return 0;
			}
			lastRock = i;
			++cnt;
		}
	if (!cnt) {
		puts("Yes");
		return 0;
	}
	if (cnt == 1 && max(abs(a - lastRock), abs(c - lastRock)) > 3) {
		puts("Yes");
		return 0;
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int dl[35][35],du[35][35],dr[35][35],dd[35][35];
int dist[35][35];
int INF=99999;
int w,h;
int move_y[4]={-1,0,1,0};
int move_x[4]={0,-1,0,1};

void bfs(int x,int y){
  for(int a=0;a<4;a++){
    int dx=x+move_x[a];
    int dy=y+move_y[a];
    if(dx>=0&&dx<h&&dy>=0&&dy<w){
      bool flag=0;
      if(a==0){
        if(dl[x][y]==0) flag=true;
      }else if(a==1){
        if(du[x][y]==0) flag=true;
      }else if(a==2){
        if(dr[x][y]==0) flag= true;
      }else{
        if(dd[x][y]==0) flag=true;
      }
      if(flag==true){
      //  cout<<dx<<" "<<dy<<endl;
        if(dist[dx][dy]>dist[x][y]+1){
          dist[dx][dy]=dist[x][y]+1;
          bfs(dx,dy);
        }
      }
    }
  }
  return ;
}

void init(){
  for(int i=0;i<35;i++){
    for(int j=0;j<35;j++){
      dl[i][j]=0;
      du[i][j]=0;
      dr[i][j]=0;
      dd[i][j]=0;
      dist[i][j]=INF;
    }
  }
}

void circle(int w, int h){
  for(int i=0;i<h;i++){
    dl[i][0]=1;
    dr[i][w-1]=1;
  }
  for(int j=0;j<w;j++){
    du[0][j]=1;
    dd[h-1][j]=1;
  }
}

int main(){
  while(true){
    cin>>w>>h;
    if(w==0&&h==0) break;
    init();
    circle(w,h);
    int n=0;
    for(int i=0;i<2*h-1;i++){
      if(i%2==0){
        for(int j=0;j<w-1;j++){
          int val;
          cin>>val;
          if(val==1){
            dr[n][j]=1;
            dl[n][j+1]=1;
          }
        }
      }else{
        for(int j=0;j<w;j++){
          int val;
          cin>>val;
          if(val==1){
            dd[n][j]=1;
            du[n+1][j]=1;
          }
        }
        n++;
      }
    }
/*
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cout<<"dl:"<<i<<" "<<j<<"="<<dl[i][j]<<endl;
        cout<<"du:"<<i<<" "<<j<<"="<<du[i][j]<<endl;
        cout<<"dr:"<<i<<" "<<j<<"="<<dr[i][j]<<endl;
        cout<<"dd:"<<i<<" "<<j<<"="<<dd[i][j]<<endl<<endl;
      }
    }*/

    dist[0][0]=0;
    bfs(0,0);
    /*
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        cout<<dist[i][j]<<" ";
      }
      cout<<endl;
    }
  */
  if(dist[h-1][w-1]==INF){
    cout<<"0"<<endl;
  }else{
    cout<<dist[h-1][w-1]+1<<endl;
  }
}
  return 0;
}



Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define INF (1 <<29)
int dp[220][220];
int ans,cnt;
void permu(int a[],int size,int n)
{

    if(size==1)
    {
        cnt=0;

        for(int j=0; j<n-1; j++)
        {
            cnt+=dp[a[j]][a[j+1]];
        }
        ans=min(ans,cnt);
    }
    for(int i=0; i<size; i++)
    {
        permu(a,size-1,n);
        if(size%2)
            swap(a[0],a[size-1]);
        else
            swap(a[i],a[size-1]);
    }
}
int main()
{
    int i,j,k,l,m,n,r,a,b,c;
    cin>>n>>m>>r;
    int ro[m+10];
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i!=j)
                dp[i][j]=INF;
        }
    }
    for(i=0; i<r; i++)
        cin>>ro[i];
    for(i=0; i<m; i++)
    {
        cin>>a>>b>>c;
        dp[a][b]=min(dp[a][b],c);
        dp[b][a]=min(dp[b][a],c);
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(k=1; k<=n; k++)
            {
                dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
            }
        }
    }
    ans=INT_MAX;
    permu(ro,r,r);
    cout<<ans<<endl;

}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
	int x;
	char c[100];
	int i;
	int p=0,w=0,g=0,y=0;
	int h=0;
	cin >> x;

	for(i=0;i<x;i++){
		cin >> c[i];
		if(c[i] == 'P')
			p=1;
		else if(c[i] == 'W')
			w=1;
		else if(c[i] == 'G')
			g=1;
		else
			y=1;
	}
	
	if(p==1)h++;
	if(w==1)h++;
	if(g==1)h++;
	if(y==1)h++;

	if(h==3)
		cout << "Three";
	else
		cout << "Four";
	return 0;
}

Measured memory_bytes: 256