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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI



void Main() {
    ll a, b, n, value;
    cin >> a >> b >> n;

    ll ans = 0;
    ll m = n;

    ll i;
    if (b <= n) {
        i = b - 1;
        value = floor(a * i / b) - a * floor(i / b);
        ans = max(ans, value);
    }
    else {
        i = n;
        value = floor(a * i / b) - a * floor(i / b);
        ans = max(ans, value);
    }


    // if (b < n) {
    //     m = n;
    // }

    // FOR(i, 1, m) {
    //     value = floor(a * i / b) - a * floor(i / b);
    //     ans = max(ans, value);
    // }

    COUT(ans);

}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*

N M Q
3 4 3
1 3 3 100
1 2 2 10
2 3 2 10



*/


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int n,r;

void solve(){
        if(n<10) {
                cout<<r+100*(10-n)<<endl;
        }else{
                cout<<r<<endl;
        }
}

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

        solve();
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
        int n;
        int l[1000],r[1000];
        int sum=0;
        cin >> n;
        for(int i=0; i<n; i++) {
                cin >> l[i] >> r[i];
        }
        for (int i = 0; i < n; i++) {
                sum += r[i] - l[i] + 1;
        }
        cout << sum << endl;

        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define PI 3.14159265359
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define tr(con, it) \
    for (auto it = con.begin(); it != con.end(); it++)
#define present(con, ele) (con.find(ele) != con.end())
#define cpresent(con, ele) (find(all(con), ele) != con.end())
#define maximum(a, b, c) (a > b ? (a > c ? a : c) : (b > c ? b : c))
#define minimum(a, b, c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
typedef long long ll;
typedef long double lf;
typedef unsigned long long lu;
const ll mod = 1e9 + 7, m = 1e18;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, ans = 1;
    cin >> n;
    n++;
    vll a(n + 2), mx(n + 2), sum(n + 2);
    fr(i, 1, n + 1)
    {
        cin >> a[i];
    }
    for (int i = n - 1; i >= 1; i--)
    {
        sum[i] = sum[i + 1] + a[i + 1];
    }
    mx[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (mx[i] < a[i])
        {
            ans = -1;
            break;
        }
        else
        {
            mx[i + 1] = min((mx[i] - a[i]) * 2, m);
        }
        ans += min(mx[i + 1], sum[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT64_MAX;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;
using Vi = vector<long long int>;
typedef pair<int, int> P; typedef pair<ll, ll> PLL;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(ll i=0;i<N;i++)
auto max(auto x,auto y){if(x>y){return x;}else{return y;}}
auto min(auto x,auto y){if(x>y){return y;}else{return x;}}
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
typedef vector<vector<ll> > matrix;
void princ(auto x){cout<<x<<" ";}; void print(auto x){cout<<x<<"\n";};
///////////////////////////////////////////////////////////////////////////////////

ll n;
Vi w;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>n;
    w.resize(n);
    rep(i,n)cin>>w[i];
    ll tmp = 0;
    rep(i,n)tmp += w[i];
    ll tmm = 0;
    ll ans = INF;
    rep(i,n){
        tmm = 0;
        rep(j,i){
            tmm += w[j];
        }
        chmin(ans,abs(tmp-tmm-tmm));
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
/************************************************************
	> File Name: d.cpp
	> Author: TSwiftie
	> Mail: 2224273204@qq.com 
	> Created Time: Sun 17 May 2020 08:28:11 PM CST
************************************************************/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include <ext/rope>
#define lowbit(x) (x&-x)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lc (o<<1)
#define rc (o<<1|1)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<LL> vll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int INF = 0x3f3f3f3f;
const LL INF_ll = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double EPS = 1e-8;
const int N = 1e5+10;
int n, m;
vi G[N];
int pre[N];
signed main(void){
	IOS;
	cin >> n >> m;
	for(int i = 1,u,v;i <= m;i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	memset(pre,-1,sizeof pre);
	queue<int>q;
	q.push(1);
	while(q.size()){
		int u = q.front();
		q.pop();
		for(int &v : G[u]){
			if(pre[v]==-1){
				pre[v] = u;
				q.push(v);
			}
		}
	}
	for(int i = 2;i <= n;i++)
		if(pre[i]==-1){
			cout << "No" << endl;
			return 0;
		}
	cout << "Yes" << endl;
	for(int i = 2;i <= n;i++)
		cout << pre[i] << endl;
	return 0;
}


Measured memory_bytes: 10580
n = int(input())
s_list = list()
for i in range(n):
    s_list.append(input())
t = input()

s_list_a = [s.replace("?","a") for s in s_list]
s_list_a.append(t)
s_list_a.sort()
index_a = [i+1 for i,x in enumerate(s_list_a) if x == t]

s_list_z = [s.replace("?","z") for s in s_list]
s_list_z.append(t)
s_list_z.sort()
index_z = [i+1 for i,x in enumerate(s_list_z) if x == t]

indexes = [str(i) for i in range(index_z[0],index_a[-1]+1)]

answer = ' '.join(indexes)

print(answer)

Measured memory_bytes: 5108
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<string>
#include<complex>
#define pb push_back
#define clr clear()
#define sz size()
#define EPS (1e-8)
#define INF 500000000
#define For(i,a) for(int i=0;i<(int)a;i++)
#define all (a) (a).begin(),(a).end()
#define RES(i) memset(i,0,sizeof(i))
#define EQ(a,b) (abs((a)-(b))<EPS)
#define let(i,a) __typeof(a)i=(a)
#define each(i,a) for(let(i,(a).begin());i!=(a).end();i++)

using namespace std;

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

string grid[1100];
bool vis[1100][1100];
int w,h,n;

int main(){
  int x,y;
  cin >> w >> h;

  For(i,h)cin >> grid[i];

  For(i,h)For(j,w)vis[i][j] = false;

  stack<P> q;
  q.push(P(0,0));
  set<P> s;

  while(q.size()){
    int y = q.top().first, x = q.top().second;
    q.pop();
    
    if(grid[y][x] == 't'){
      cout << 0 << endl;
      return 0;
    }
    
    vis[y][x] = true;
    int dy[] = {-1,0,1,0},dx[] = {0,1,0,-1};
    
    For(i,4){
      int sy = y + dy[i] , sx = x + dx[i];
      if(sy<0 || sx<0 || h<=sy || w<=sx)continue;
      if(vis[sy][sx])continue;
      if(grid[sy][sx] == '#'){
	s.insert(P(sy,sx));
	continue;
      }
      q.push(P(sy,sx));
    }
  }

  cin >> n;
  For(i,n){
    cin >> x >> y;
    if(grid[y][x]=='#'){
      grid[y][x] = '.';

      int s1 = s.sz;
      s.insert(P(y,x));
      int s2 = s.sz;
      s.erase(P(y,x));
      if(s1==s2){
	q.push(P(y,x));
	
	while(q.size()){
	  int y = q.top().first, x = q.top().second;
	  q.pop();
	  
	  if(grid[y][x] == 't'){
	    cout << i+1 << endl;
	    return 0;
	  }
	  
	  vis[y][x] = true;
	  int dy[] = {-1,0,1,0},dx[] = {0,1,0,-1};
	  
	  For(i,4){
	    int sy = y + dy[i] , sx = x + dx[i];
	    if(sy<0 || sx<0 || h<=sy || w<=sx)continue;
	    if(vis[sy][sx])continue;
	    if(grid[sy][sx] == '#'){
	      s.insert(P(sy,sx));
	      continue;
	    }
	    q.push(P(sy,sx));
	  }
	}
      }
    }
  }

  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 9996
def warshall_floyd():
    '''
    すべての頂点間の最短距離を求める
    '''
    for k in range(10):
        for i in range(10):
            for j in range(10):
                c[i][j] = min(c[i][j], c[i][k] + c[k][j])


h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(10)]
a = [list(map(int, input().split())) for _ in range(h)]

warshall_floyd()

res = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            res += c[a[i][j]][1]

print(res)

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

int main(){
    int first[30],second[30],third[30],forth[30];
    int n,b,f,r,v;
    cin >> n;
    for(int i=0; i<30; i++){
        first[i] = 0;
        second[i] = 0;
        third[i] = 0;
        forth[i] = 0;
    };
    for(int i=0; i<n; i++){
        cin >> b >> f >> r >> v;
        if(b==1){
            first[(f-1)*10 + r-1] += v;
        }
        else if(b==2){
            second[(f-1)*10 + r-1] += v;
        }
        else if(b==3){
            third[(f-1)*10 + r-1] += v;
        }
        else if(b==4){
            forth[(f-1)*10 + r-1] += v;
        };
    };
    for(int i=0; i<30; i++){
        if((i+1)%10==0){
            cout << " " << first[i] << endl;
        }else{
            cout << " " << first[i];
        };
    };
    cout << "####################" << endl;
    for(int i=0; i<30; i++){
        if((i+1)%10==0){
            cout << " " << second[i] << endl;
        }else{
            cout << " " << second[i];
        };
    }; 
    cout << "####################" << endl;
    for(int i=0; i<30; i++){
        if((i+1)%10==0){
            cout << " " << third[i] << endl;
        }else{
            cout << " " << third[i];
        };
    };
    cout << "####################" << endl;
    for(int i=0; i<30; i++){
        if((i+1)%10==0){
            cout << " "<< forth[i] << endl;
        }else{
            cout << " " << forth[i];
        };
    };
    return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
typedef long long ll;
using namespace std;

int main(void)
{
	string s;
	cin >> s;
	int cnt = 0;

	for (int i = 0; i < s.length() - 1; i++)
	{
		if (s[i] == s[i + 1])
		{
			if (s[i] == '0') s[i + 1] = '1';
			else s[i + 1] = '0';
			cnt++;
		}
	}

	cout << cnt << endl;
}

Measured memory_bytes: 512
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int c = in.nextInt();
            int[] b = in.nextIntArray(m);

            int count = 0;
            while (n-- > 0) {
                int ms = c;
                for (int i = 0; i < m; i++)
                    ms += in.nextInt() * b[i];
                if (ms > 0)
                    count++;
            }
            out.println(count);
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
            this.bufPointer = 0;
            this.bufLength = 0;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int nextInt() {
            int n = 0;

            int b = readByte();
            while (isSpaceChar(b))
                b = readByte();

            boolean minus = (b == '-');
            if (minus)
                b = readByte();

            while (b >= '0' && b <= '9') {
                n *= 10;
                n += b - '0';
                b = readByte();
            }

            if (!isSpaceChar(b))
                throw new NumberFormatException();

            return minus ? -n : n;
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

    }
}



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

int main()
{
    int n;
    cin>>n;
    int A[n];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    int dp[n];
    memset(dp,0,sizeof(dp));
    dp[1] = abs(A[1]-A[0]);
    for(int i=2;i<n;i++){
        dp[i] = min(abs(A[i]-A[i-1])+dp[i-1],abs(A[i]-A[i-2])+dp[i-2]);
    }
    cout<<dp[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
k = gets.to_i

gcds = []

1.upto(k) do |a|
  1.upto(k) do |b|
    gcds << a.gcd(b)
  end
end

sum = 0

gcds.each do |ab|
  1.upto(k) do |c|
    sum += ab.gcd(c)
  end
end

print sum

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

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

const string lst[]={"Sunny", "Cloudy", "Rainy"};

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; cin>>s;
	int idx=-1;
	for (int i=0; i<3; i++)
		if(lst[i]==s) idx=i;
	cout<<lst[(idx+1)%3]<<"\n";
	return 0;
}

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

using namespace std;

deque <int> d;
int n, x;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &x);
		if (i & 1) d.push_back(x);
		else d.push_front(x);
	}
	if (n & 1) {
		for (int i = n - 1; i >= 0; --i) {
			printf("%d ", d[i]);
		} 
		puts("");
	} else {
		for (int i = 0; i < n; ++i) {
			printf("%d ", d[i]);
		} 
		puts("");
	}
  return 0;
}



Measured memory_bytes: 2944
//header{{{
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_int.hpp>
#include<boost/math/common_factor_rt.hpp>
  
using namespace std;
using namespace boost::multiprecision;  
using namespace boost::math;

#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) (x).begin(),(x).end()
#define Fixed fixed << setprecision(12)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
constexpr int MOD = 998244353;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
//inline int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
//inline int lcm(int a,int b){ return a / gcd(a,b) * b;}
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }

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

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

    int h,n;
    cin >> h >> n;

    vector<int> a(n+1),b(n+1);
    vector<vector<int> > dp(n+1,vector<int>(1e4 + 1,LINF));

    reps(i,n){
        cin >> a[i] >> b[i];
    }

    dp[0][0] = 0;
    reps(i,n){
        for(int j = 0;j <= 1e4;++j){
            dp[i][j] = dp[i-1][j];
            if(j - a[i] >= 0) chmin(dp[i][j],min(dp[i-1][j-a[i]] + b[i],dp[i][j-a[i]] + b[i]));
        }
    }

    int minv = LINF;
    for(int i = 1e4;i >= h;--i){
        chmin(minv,dp[n][i]);
    }

    cout << minv << '\n';

    return 0;
}


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

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

int main(){
    long long h, w;
    int n;
    cin >> h >> w >> n;
    map<pair<int, int>, int> mp;
    vector<long long> v(10, 0);
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        for(int j = 0; j < 9; j++){
            int nx = b + dx[j];
            int ny = a + dy[j];
            if(nx <= 0 || ny <= 0 || nx >= w - 1 || ny >= h - 1) continue;
            mp[make_pair(nx, ny)]++;
        }
    }
    long long cnt = 0;
    for(auto &e : mp) v[e.second]++, cnt++;
    v[0] = (h - 2) * (w - 2) - cnt;
    for(int i = 0; i < 10; i++) cout << v[i] << endl;
    return 0;
}

Measured memory_bytes: 56448
import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
      	int n = Integer.parseInt(line);
      
      	int x = n % 1000;
      	int answer = 0;
      	if(x > 0){
          answer = 1000 - x;
        }
      System.out.println(String.valueOf(answer));
    }
}

Measured memory_bytes: 35804
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug " << x << endl;
using namespace std;

int main(){
    int n, sum = 0;
    while(cin >> n){
        sum+= n;
    }
    cout << sum << endl;
}

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

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

int main(void){
    
    ll n; cin >> n;
    vector<ll> d(n);
    for(int i=0;i<n;i++) cin >> d[i];
    ll ans = 0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            ans += d[i]*d[j];
        }
    }

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


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iterator>


using namespace std;

int main(){
  int N;
  long long H;
  cin>>N>>H;
  vector<long long> a(N);
  vector<long long> b(N);
  for(int i=0;i<N;i++){
    cin>>a[i]>>b[i];
  }
  long long a_max=*max_element(a.begin(),a.end());
  //cout<<a_max;
  long long answer=0;
  sort(b.rbegin(),b.rend());
  for(int e:b){
    if(e<a_max)break;
    H=H-e;
    answer++;
    if(H<=0){
      cout<<answer;
      return 0;
    }
  }
  answer+=H/a_max;
  if(H%a_max!=0)answer+=1;
  cout<<answer;
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long int ll;
int main(){
int n,m,k;
cin >> n>> m;
vector <pair<ll,ll>> v[n];
pair<ll,ll> a[m];
ll p,y;
for(int i=0;i<n;i++) v[i].push_back(make_pair(0,0));
for(ll i=0;i<m;i++){
  cin >> p>> y;
  v[p-1].push_back(make_pair(y,i));
}
for(int i=0;i<n;i++){
  if(v[i].size()==1) continue;
  sort(v[i].begin(),v[i].end());
}
for(int i=0;i<n;i++){
  if(v[i].size()==1) continue;
  for(int j=1;j<v[i].size();j++){
    a[v[i][j].second].first=i+1;
    a[v[i][j].second].second=j;
  }
}
for(int i=0;i<m;i++){
    printf("%06d",a[i].first);
    printf("%06d\n",a[i].second);
}
}


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

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

    long long n, m;
    cin >> n >> m;

    if(n == 2 or m == 2){
        cout << 0 << endl;
        return 0;
    }else if(n == 1 or m == 1){
        cout << max(max(n, m) - 2, 1LL) << endl;
        return 0;
    }else{
        cout << (n - 2) * (m - 2) << endl;
    }
    
    /*
    int A[n][m] = {};
    int dx[9] = {-1, -1, 0, 0, 0, 1, 1, -1, 1};
    int dy[9] = {-1, 0, -1, 0, 1, 0, 1, 1, -1};
    REP(i, n){
        REP(j, m){
            REP(k, 9){
                int nx, ny;
                nx = i + dx[k];
                ny = j + dy[k];
                if(nx < 0 or ny < 0 or nx >= n or ny >= m){
                    continue;
                }
                A[nx][ny]++; 
            }
        }
    }

    REP(i, n){
        REP(j, m){
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
    */
    
    

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<P, int> PP;
int dx[2]={1,0};
int dy[2]={0,1};

int h,w;
string s[210];
int d[210][210];

void solve(){
    cin >> h >> w;
    rep(i,h){
        cin >> s[i];
    }
    rep(i,h){
        rep(j,w){
            d[i][j]=mod;
        }
    }
    deque<P> que;
    if(s[0][0]=='#'){
        que.push_back(P(0,0));
        d[0][0]=1;
    }
    else {
        que.push_back(P(0,0));
        d[0][0]=0;
    }
    while(!que.empty()){
        int sy=que.front().first,sx=que.front().second;int l=d[sy][sx];que.pop_front();
        //cout << s_y << " " << s_x << " " << l << endl;
        rep(k,2){
            int ny=sy+dy[k],nx=sx+dx[k];
            if(ny<h && nx<w){
                if(d[ny][nx]!=mod) continue;
                if(s[sy][sx]!=s[ny][nx]){
                    que.push_back(P(ny,nx));
                    d[ny][nx]=l+1;
                }
                else{
                    que.push_front(P(ny,nx));
                    d[ny][nx]=l;
                }
            }
        }
    }
    // rep(i,h){
    //     rep(j,w){
    //         cout << i << " " << j << " " << d[i][j] << endl;
    //     }
    // }
    cout << (d[h-1][w-1]+1)/2 << endl;
}

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

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

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

        int ans = 0;
        int p = 0;
        while (1) {
                p = S.find("ABC", p);
                if (p == string::npos) {
                        break;
                }
                else {
                        ans++;
                        p++;
                }

        }
        cout << ans << endl;

}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

typedef pair<string,int> psi;
vector<psi> stay;

int main(void){
	int n,t;
	cin >> n >> t;

	int prev=-1;
	for(int i=0;i<n;++i){
		string st,sn,at,an;
		cin >> st >> sn >> at >> an;
		int sh=10*(st[0]-'0')+(st[1]-'0');
		int sm=10*(st[3]-'0')+(st[4]-'0');
		int s=sh*60+sm;
		int ah=10*(at[0]-'0')+(at[1]-'0');
		int am=10*(at[3]-'0')+(at[4]-'0');
		int a=ah*60+am;

		if(prev!=-1&&s-prev>=t) stay.push_back(make_pair(sn,s-prev));
		prev=a;
	}
	cout << stay.size() << endl;
	for(int i=0;i<stay.size();++i) cout << stay[i].first << " " << stay[i].second << endl;
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <iomanip>
#include <set>
#include <sstream>
#include <cmath>
#include <deque>
#include <list>
#include <bitset>
using namespace  std;
typedef pair<long long , long long> P;
typedef long long int64;
typedef long long lint;
#define REP(i, n) for(long long (i)=0; (i)<(n); ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define FST first
#define SND second

signed main(){
    int A[5];
    REP(i, 5) cin >> A[i];
    int minx = 10;
    int ans = 0;
    REP(i, 5){
        int x = A[i]%10;
        if(x!=0) minx = min(minx, x);
        if(x!=0) ans += A[i] + 10-x;
        else ans += A[i]; 
    }
    ans -=  10 - minx;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

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


//const int MAX = 1000000;
//bool is_prime[MAX + 10];
//
//int memo[MAX + 10];
int key(int n)
{
	//if (is_prime[n])
	//	return n;
	//else if (~memo[n])
	//	return memo[n];

	int sum = 0, last;
	for (int i = 2; i <= n; ++i)
	{
		if (n % i == 0)
		{
			sum += i, last = i;
			while (n % i == 0)
				n /= i;
		}
	}
	return 2*last - sum;
}
int main()
{
	//fill_n(is_prime, MAX, true);
	//for (int i = 2; i*i <= MAX; ++i)
	//	if (is_prime[i])
	//		for (int j = 2*i; j <= MAX; j += i)
	//			is_prime[j] = false;

	//fill_n(memo, MAX, -1);
	int a, b;
	while (scanf("%d%d", &a, &b), a | b)
		puts(key(a) > key(b) ? "a" : "b");
}

Measured memory_bytes: 844
#include <bits/stdc++.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;

int main(){
    int h, w, i, j, k;
    vector<string> s;
    cin >> h >> w;
    int mem[h][w] = {};
    for(i = 0; i < h; i++){
        string t;
        cin >> t;
        s.push_back(t);
        int lw = 0;
        for(j = 0; j < w; j++){
            if(s[i][j] == '#'){
                lw = j + 1;
                continue;
            };
            if(s[i][j] == '.' && (j+1 == w || s[i][j+1] == '#')){
                for(k = lw; k <= j; k++){
                    mem[i][k] = j - lw + 1;
                }
            }
        }
    }
    for(j = 0; j < w; j++){
        int t = 0;
        for(i = 0; i < h; i++){
            if(s[i][j] == '#'){
                t = i + 1;
                continue;
            };
            if(s[i][j] == '.' && (i+1 == h || s[i+1][j] == '#')){
                for(k = t; k <= i; k++){
                    mem[k][j] += i - t + 1 - 1;
                }
            }
        }
    }
    int a = 0;
    for(i = 0; i < h; i++){
        for(j = 0; j < w; j++){
            a = MAX(a, mem[i][j]);
        }
    }
    cout << a << endl;

}

Measured memory_bytes: 19840
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
#define inf (INT_MAX-1)
#define INF 9223372036854775807
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r);
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r);
#define TYPE int
#define MEMSET(a) memset(a,0,sizeof(a))
const int mod=(int)1e09+7;

int in(void){
	int i;scanf("%d",&i);
	return i;
}
long long llin(void){
	long long i;scanf("%lld",&i);
	return i;
}
double din(void){
	double i;scanf("%lf",&i);
	return i;
}
void chin(char s[]){
	scanf("%s",s);
}
void print(int a){
	printf("%d\n",a);
}
void llprint(long long a){
	printf("%lld\n",a);
}
void dprint(double a){
	printf("%.10f\n",a);
}
void print2(int a,int b){
	printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
	return a>b?a:b;
}
long long min(long long a,long long b){
	return a<b?a:b;
}
long long llabs(long long a){
	return a>0?a:-a;
}
double dmax(double a,double b){
	return a>b?a:b;
}
int cmp(const void *a,const void *b){
	return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
	return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
	return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
	return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}
long long gcd(long long x,long long y){
	return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
	return x/gcd(x,y)*y;
}

// konoshita kara kaku

int main(void){
	long long x=llin(),ans=0;
	ans=2*(x/11);
	if(x%11>6)ans+=2;
	else if(x%11>0)ans++;
	llprint(ans);
	return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
ll c[15];
int main() {
	ll n, m, x;
	cin >> n >> m >> x;
	vector<vector<ll>>a(n);
	a.resize(m);
	for (int i = 0; i < n; i++) {
		cin >> c[i];
		for (int j = 0; j < m; j++) {
			int x; cin >> x;
			a[i].push_back(x);
		}
	}
	ll ans = inf;
	for (int bit = 0; bit < (1 << n); bit++) {
		ll sum = 0;
		vector<ll>check(m, 0);
		bool ok = true;
		for (int i = 0; i < n; i++) {
			if (bit & (1 << i)) {
				sum += c[i];
				for (int j = 0; j < m; j++) {
					check[j] += a[i][j];
				}
			}
		}
		for (int k = 0; k < m; k++) {
			if (check[k] < x) {
				ok = false;
			}
		}
		if (ok) {
			ans = min(ans, sum);
		}

	}
	if (ans == inf) {
		cout << "-1" << endl;
	}
	else {
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h  / 2 << endl;
    return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n; cin >> n;
	map<int, int> cnt;
	ll ans = 0;
	
	rep(i, 1, n + 1) {
		int t; cin >> t;
		ans += cnt[i - t];
		cnt[t + i]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 20636
def main():
    N = int(input())
    S = [[] * N for i in range(N)]
    ans = 0

    for i in range(N):
        A = int(input())
        for j in range(A):
            x, y = map(int, input().split())
            S[i].append([x-1, y])

    P = [0]*N
    
    for i in range(2**N):
        for j in range(N):
            if P[j] == 0:
                P[j] = 1
                break
            else:
                P[j] = 0
        
        if sum(P) <= ans:
            continue
        flag = 0
        for p in range(len(P)):
            if P[p] == 1:
                for s in S[p]:
                    if s[1]!= P[s[0]]:
                        flag = 1
        if flag == 1:
            continue
        else:
            ans = sum(P)
        
    print(ans)


 
if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<stdio.h>
 
int main(){
    int train[10];
    int num = 0, i, n;

    while(scanf("%d", &n) != EOF){
        if(n == 0){
            num--;
            printf("%d\n", train[num]);
        } else {
            train[num] = n;
            num++;
        }
    }
    return 0;
}

Measured memory_bytes: 600
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int h = sc.nextInt();
        double area = (double) w * (double) h / 2.0;
        int x = sc.nextInt();
        int y = sc.nextInt();
        int cnt = 0;
        if(x - w / 2.0 == 0 && y - h / 2.0 == 0)
        	cnt++;
        System.out.println(area + " " + cnt);
    }
}


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }

struct Ford_Fulkerson {

    // 行先、容量、逆辺の行先の g での index;
    struct edge { int to, cap, rev; };

    int n;
    vector<vector<edge>> g;
    vector<bool> seen;

    Ford_Fulkerson(int _n) {
        n = _n;
        g.assign(n, vector<edge>());
        seen.assign(n, false);
    }

    // 辺の追加
    void add_edge(int from, int to, int cost) {
        g[from].push_back(edge{to, cost, (int)g[to].size()});
        g[to].push_back(edge{from, 0, (int)g[from].size() - 1});
    }

    // v から t へのパスを探して最大流量を返す
    int dfs(int v, int t, int mincap) {
        if(v == t) return mincap;
        seen[v] = true;
        for(edge &e : g[v]) {
            if(!seen[e.to] && e.cap > 0) {
                int d = dfs(e.to, t, min(mincap, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // s から t への最大流
    int max_flow(int s, int t) {
        int flow = 0;
        for(;;) {
            seen.assign(seen.size(), false);
            int f = dfs(s, t, inf);
            if(f == 0) return flow;
            flow += f;
        }
    }

};

int main(){

    int n;
    cin >> n;
    V<P> rs(n), bs(n);

    rep(i,n) {
        int a, b;
        cin >> a >> b;
        rs[i] = make_pair(a,b);
    }
    rep(i,n) {
        int a, b;
        cin >> a >> b;
        bs[i] = make_pair(a,b);
    }

    Ford_Fulkerson ff(n*2+2);
    rep(i,n)rep(j,n) {
        if(rs[i].fi < bs[j].fi && rs[i].se < bs[j].se) {
            ff.add_edge(i, j+n, 1);
        }
    }

    int l = n*2, r = n*2+1;
    rep(i,n) ff.add_edge(l,i,1);
    rep(i,n) ff.add_edge(i+n, r, 1);

    int ans = ff.max_flow(l,r);
    cout << ans << endl;
}

Measured memory_bytes: 3732
n = int(input())
ans = ""
for i in range(1, n + 1):
    if(i % 3 == 0):
        ans += " " + str(i)
        continue
    x = i
    while(x):
        if(x % 10 == 3):
            ans += " " + str(i)
            break
        x //= 10
print(ans)


Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    string s, t; cin >> s >> t;

    ll chksize = s.size()-t.size()+1;

    // sの切り出し
    for(ll i=s.size()-t.size(); i>=0; i--){
        bool match = true;
        // tの全てと一致確認
        for(ll j=0; j<t.size(); j++){
            if(s[i+j] != '?' && s[i+j] != t[j]){
                match = false;
                break;
            }
        }
        if(!match) continue;
        s = s.substr(0, i) + t + s.substr(i+t.size());
        for(ll j=0; j<s.size(); j++) if(s[j] == '?') cout << "a"; else cout << s[j];
        cout << endl;
        return 0;
    }
    cout << "UNRESTORABLE" << endl;
}

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

using namespace std;

const int maxn = 1e5 + 9;
long long result[maxn];

class dsu {
public:
	vector<int> parent, size, rank;
	dsu(int n) : parent(n + 1), size(n + 1, 1), rank(n + 1, 0) {
		for (int i = 0; i < n + 1; i++) {
			parent[i] = i;
		}
	}
	int find(int u) {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]);
	}
	long long merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return -1LL;
		long long ret = size[u] * (size[u] - 1LL) * 1LL / 2LL + size[v] * (size[v] - 1LL) * 1LL / 2LL;
		if (rank[u] < rank[v]) {
			parent[u] = v;
			size[v] += size[u];
			size[u] = 0;
		} else {
			parent[v] = u;
			size[u] += size[v];
			size[v] = 0;
		}
		if (rank[u] == rank[v]) rank[u]++;
		return ret;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> edges;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		edges.push_back(make_pair(a, b));
	}
	long long inf = n * (n - 1LL) * 1LL / 2LL, tmp = inf;
	dsu uf(n);
	for (int i = 0; i < m; i++) {
		result[m - i - 1] = tmp;
		pair<int, int> edge = edges[m - i - 1];
		long long d = uf.merge(edge.first, edge.second);
		if (d == -1LL) continue;
		tmp += d;
		int size = uf.size[uf.find(edge.first)];
		tmp -= size * (size - 1LL) * 1LL / 2LL;
	}
	for (int i = 0; i < m; i++) {
		cout << result[i] << '\n';
	}
	
	return 0;
}


Measured memory_bytes: 4084
/**
 *   created: 03 June 2019  00:25:23
**/
#include<bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef vector< pair<int , int> > vii;
typedef long long ll;
typedef vector<long long> vl;
typedef pair<long long , long long> pll;
typedef vector< pair<long long , long long> > vll;

#define PB push_back
#define PPB pop_back
#define all(c) c.begin(),c.end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rrep(i,a,b) for(int i = (int)(a-1); i>=(int)(b); i--)
#define INFLL 2000000000000000007
#define INF 2000000007
#define MOD 1000000007


#define TRACE

#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

#else

#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif


void optimizeIO()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

//                                        //AUTHOR: Kaushalesh Shukla

//=========================================================================================================
ll modexpo(ll n, ll p){
	if(p==0)
		return 1;
	if(p%2==0)
		return modexpo((n%MOD * n%MOD)%MOD, p/2);
	return (n%MOD*modexpo(n,p-1)%MOD)%MOD;
}
int main()
{
	optimizeIO();
	int tt=1;
	//cin>>tt;
	while(tt--){
		int n,k;
		cin>>n>>k;
		vi v(n);
		rep(i,0,n)
			cin>>v[i];
		sort(all(v));
		int mini = INF;
		rep(i,0,n-k+1){
			mini = min(mini, v[i+k-1]-v[i]);
		}
		cout<<mini;
	}
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int N=3050,mo=1e9+7,P=(mo+1)/2;
inline int gi() {
  char ch=getchar(); int q=0,x=0;
  while(ch<'0'||ch>'9') q=(ch=='-'?1:q),ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int a[N],f[N][N],g[N][N],p[N],t[N];
int main(){
  int n,q,x,y,s=1; cin>>n>>q;
  for (int i=1; i<=n; ++i) a[i]=gi();
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=n; ++j){
      if (a[i]<a[j]) f[i][j]=1;
      if (a[i]>a[j]) g[i][j]=1;
    }
  for (int i=1; i<=q; ++i){
    x=gi(),y=gi(),s=s*2%mo;
    for (int j=1; j<=n; ++j)
      if(j!=x&&j!=y) {
	f[j][x]=f[j][y]=1ll*P*(f[j][x]+f[j][y])%mo;
	f[x][j]=f[y][j]=1ll*P*(f[x][j]+f[y][j])%mo;
      }
    f[x][y]=f[y][x]=1ll*P*(f[x][y]+f[y][x])%mo;
  }
  int ans=0;
  for(int i=1; i<=n; ++i)
    for(int j=i+1; j<=n; ++j)
      ans=(ans+1ll*f[j][i]*s)%mo;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 72320
def solve(a,b,k):
  if k <= a: return a - k, b
  elif k <= a + b: return 0, b - (k - a)
  else: return 0, 0

a,b,k = map(int,input().split())
ans_1, ans_2 = solve(a,b,k)
print(f"{ans_1} {ans_2}")

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

int main() {
  string s;
  cin >> s;
  
  int ans=0;
  rep(i, s.size()) {
    if(s[i] == 'A') {
      ans -= i;
      break;
    }
  }
  rep(i, s.size()) {
    if(s[s.size()-i-1] == 'Z') {
      ans += s.size()-i-1;
      break;
    }
  }
  
  cout << ans+1 << endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int key){
  NodePointer cur=nil->next;
  while((cur!=nil)&&(cur->key!=key)){
    cur=cur->next;
  }
  return cur;
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  if(t==nil){
    return;
  }
  t->prev->next=t->next;
  t->next->prev=t->prev;
  free(t);
}

void deleteFirst(){
  /*
  NodePointer t = nil->next;
  if ( t == nil ) return;
  */
  deleteNode(nil->next);
}

void deleteLast(){
  /*
  NodePointer t = nil->prev;//tにnil->prevが入ってるから
  if ( t == nil ) return;
  */
  deleteNode(nil->prev);
}

void delete(int key){
  NodePointer delnode;
  delnode=listSearch(key);
  deleteNode(delnode);
}


void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;
  x->next=nil->next;
  nil->next->prev=x;
  nil->next=x;
  x->prev=nil;
}

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
  }

  printList();
  return 0;
}
/*
void delete(int key){
  NodePointer n,delnode;
  if((n=listSearch(key)!=NULL){
      delnode=nil->next;
      nil->next=delnode->next;
  }
}
NodePointer listSearch(int key){
  NodePointer n;
  for(n=nil;n->next!=NULL;){
    if(n->next->key==key){
      return 0;
    }
  }
  return NULL
}
void delete(int key){
  NodePointer n,delnode;
  if((n=listSearch(key)!=NULL){
      delnode=nil->next;
      nil->next=delnode->next;
  }
}
 */



Measured memory_bytes: 33020