akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n,k;
	long long int t;
	vector <long long int> v;
 
	cin >> n >> k;
 
	for(int i=0;i<n;i++)
	{
		cin >> t;
		v.push_back(t);
	}
 
	vector <unsigned long long int> v2;
 
	for(int i=0;i<n;i++)
	{
		unsigned long long int val = 0;
		for(int j=i;j<n;j++)
		{
			val += v[j];
			v2.push_back(val);
		}
	}
 
	sort(v2.rbegin(),v2.rend());
	
	unsigned long long int res = 0;
 
	for(long long int j=63;j>=0;j--)
	{
		vector <unsigned long long int> temp;
		int cnt = 0;
		for(int i=0;i<v2.size();i++)
		{
			if((v2[i]&(1LL << j)))
			{
				cnt++;
				temp.push_back(v2[i]);
			}
		}
		if(cnt >= k)
		{
			res += (1LL << j);
			v2 = temp;
		}
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 6384
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define OJ \
        freopen("input.txt","r",stdin); \
        freopen("output.txt","w",stdout);
using namespace std;

int main()
{
//	OJ;
	 ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   ll int n,ans=0,last;
   cin>>n;
   vector<int> v;
   for(int i=0;i<n;i++)
   {
      int x;
      cin>>x;
      v.push_back(x);
   }
   sort(v.begin(),v.end(),greater<int>());
   if(n%2)
   {
           for(int i=1;i<=n-(n+1)/2;i++)
   {
       ans+=v[i]*2;
       last=v[i];
   }
   
   ans-=last;
   ans+=v[0];
   cout<<ans<<endl;
   }
   else{
           for(int i=1;i<n-(n+1)/2;i++)
   {
       ans+=v[i]*2;
       last=v[i];
   }
   
   ans+=v[0];
   cout<<ans<<endl;
   }
  
}

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

using namespace std;

using ll = long long;

template<typename T>
struct SegmentTree {
    int n;
    std::vector<T> val;

    SegmentTree(int size) {
        for (n = 1; n < size; ) n <<= 1;
        val.assign(2 * n + 1, 0);
    }

    inline T op(const T &v1, const T &v2) const { return v1 <= v2 ? v2 : v1; }

    void update(int idx, T v) {
        idx += n - 1;
        val[idx] = v;
        while (0 < idx) {
            idx = (idx - 1) >> 1;
            val[idx] = op(val[2 * idx + 1], val[2 * idx + 2]);
        }
    }
    T find(int l, int r) {
        T res = 0;
        l += n - 1; r += n - 1;
        while (l < r) {
            if (!(l & 1)) res = op(res, val[l]);
            if (!(r & 1)) res = op(res, val[r - 1]);
            l >>= 1;
            r = (r - 1) >> 1;
        }
        return res;
    }
};

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

    // j \in [0, i) で h_j <= h_i で dp[j] が最大のもの
    int n;
    cin >> n;

    vector<int> h(n), a(n);
    for (auto &&x : h) { cin >> x; --x; }
    for (auto &&x : a) cin >> x;

    vector<ll> dp(n);
    SegmentTree<ll> seg(n);
    for (int i = 0; i < n; ++i) {
        const ll max_happy = seg.find(0, h[i]);
        dp[i] = max_happy + a[i];
        seg.update(h[i], dp[i]);
    }

    cout << *max_element(dp.begin(), dp.end()) << endl;

    return 0;
}


Measured memory_bytes: 7552
#include<stdio.h>
int n,k;
int ar[100000];
int x;
int r,l;
int m,t;
int i,j;
int used;

int max(int a,int b){
	if(a>=b)return a;
	else return b;
}

int main(){
	while(1){
		scanf("%d %d",&n,&k);
		if(n==0&&k==0)return 0;
		used=0;
		for(i=0;i<n+1;i++)ar[i]=0;
		for(i=0;i<k;i++){
			scanf("%d",&x);
			ar[x]=1;
		}
		r=1;l=1;
		if(ar[1]==0){
			used++;
			m=0;
		}else m=1;
		while(l<n){
			if(ar[++l]==0)used++;
			if(ar[0]==1)while(used>1){if(ar[r++]==0)used--;}
			if(ar[0]==0)while(used>0){if(ar[r++]==0)used--;}
			m=max(m,l-r+1);
		}
		printf("%d\n",m);
	}
}
		

Measured memory_bytes: 1416
#include<bits/stdc++.h>
    using namespace std;
    int Len[10],a[10];
    bool vis[10];
    int n,m;
    long long ans;
    int Min(int x,int y){
    	return x<y?x:y;
    }
    void solve(){
    	static int dp[310][1<<5][310];
    	memset(dp,0,sizeof(dp));
    	dp[0][0][0]=1;
    	for(int i=1;i<=(n+1)*m;i++){
    		for(int j=0;j<(1<<n);j++)
    			for(int k=0;k<=i;k++){
    				dp[i][j][k]+=dp[i-1][j][k];
    				if(i%(n+1)&&!(j&(1<<(i%(n+1)-1))))
    					dp[i][j|(1<<(i%(n+1)-1))][Min((n+1)*m,k<i-a[i%(n+1)-1]*(n+1)+1?k:i)]+=dp[i-1][j][k];
    			}
    	}
    	int st=0;
    	for(int i=(n+1)*m-Len[n]*(n+1)+1;i<=(n+1)*m;i++){
    		ans=ans+dp[(n+1)*m][(1<<n)-1][i];
    		st+=dp[(n+1)*m][(1<<n)-1][i];
    	}
    }
    void dfs(int p){
    	if(p>n){
    		solve();
    		return;
    	}
    	for(int i=0;i<n;i++){
    		if(!vis[i]){
    			vis[i]=1;
    			a[p-1]=Len[i];
    			dfs(p+1);
    			vis[i]=0;
    		}
    	}
    }
    int main(){
    //	freopen("F.in","r",stdin);
    	scanf("%d%d",&n,&m);
    	for(int i=0;i<n;i++)
    		scanf("%d",&Len[i]);
    	sort(Len,Len+n);
    	n--;
    	dfs(1);
    	long long cnt=1;
    	for(int i=1;i<=n;i++)
    		cnt=cnt*m;
    	for(int i=1;i<=n;i++)
    		cnt=cnt*i;
    	printf("%.14f\n",ans/(double)cnt);
    	return 0;
    }

Measured memory_bytes: 12288
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

#define MOD 1'000'000'007LL
ll pw(ll a, ll b){
	ll c = 1;
	do {
		if(b&1) c = c*a % MOD;
		a = a*a % MOD;
	} while(b /= 2);
	return c;
}

int main(){
	ll n; scanf("%lld", &n);
	printf("%lld\n", (pw(10, n) - pw(9, n) * 2 + pw(8, n) + MOD*10)%MOD);
}


Measured memory_bytes: 3820
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;



int main(){
    int H,W,K;cin>>H>>W>>K;
    vector<vector<int>> grid(H,vector<int>(W,0));
    for (int i = 0; i < H; i++)
    {
        string S;cin>>S;
        for (int j = 0; j < W; j++)
        {
            grid[i][j] = S[j] == '0' ? 0 : 1;
        }
        
    }

    int p = 1;
    for(int i = 0;i < H-1;i++){
        p *= 2;
    }
    vector<vector<int>> accum(H+1,vector<int>(W+1,0));
    for(int i = 0;i < H+1;i++){
        for(int j = 0;j < W+1;j++){
            if(i == 0 || j == 0){
                accum[i][j] = 0;
            }else{
                accum[i][j] = accum[i-1][j] + accum[i][j-1] - accum[i-1][j-1] + grid[i-1][j-1];
            }
        }
    }

    int ans = 1000000;
    for(int _col = 0;_col < p;_col++){
        // cout<<"----"<<endl;
        // cout<<_col<<endl;
        vector<int> cuts;
        cuts.push_back(0);
        for(int i = 0;i < H-1;i++){
            if((_col>>i)&1){
                cuts.push_back(i+1);
            }
        }
        cuts.push_back(H);
        int res = cuts.size()-2;
        // for(int i = 0;i < cuts.size();i++){
        //     cout<<cuts[i];
        // }cout<<endl;
        int prev_cut = 0;
        int now_cut = 0;
        // vector<int>;
        bool dame = false;
        for(int i = 1;i <= W;i++){
            for(int j = 0;j < cuts.size()-1;j++){
                if(accum[cuts[j+1]][i] - accum[cuts[j+1]][i-1] + accum[cuts[j]][i-1] - accum[cuts[j]][i] > K){
                    // cout<<accum[cuts[j+1]][i] - accum[cuts[j+1]][i-1] + accum[cuts[j]][i-1] - accum[cuts[j]][i]<<endl;
                    dame = true;
                }
            }
        }
        // cout<<"!"<<endl;
        if(dame)continue;
        while(now_cut <= W){
            bool flag = false;
            // cout<<"a"<<endl;
            // cout<<now_cut<<endl;
            for(int i = 0;i < cuts.size()-1;i++){
                // cout<<accum[cuts[i+1]][now_cut] + accum[cuts[i]][prev_cut] - accum[cuts[i+1]][prev_cut] - accum[cuts[i]][now_cut]<<endl;

                if(accum[cuts[i+1]][now_cut] + accum[cuts[i]][prev_cut] - accum[cuts[i+1]][prev_cut] - accum[cuts[i]][now_cut] > K){
                    flag = true;
                    break;
                }
                
            }
            if(flag){
                res++;
                prev_cut = now_cut-1;
            }
            now_cut++;
        }
        // cout<<res<<endl;
        ans = min(res,ans);
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 384
#pragma warning(disable:4996)


#include<iostream>
#include<algorithm>
//#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define INF 0x3f3f3f3f
#define inf 0x7FFFFFFF
#define MOD 1000000007
#define pii pair<ll,ll>
#define eps 1e-8
#define equals(a,b) (fabs(a-b)<eps)
#define bug puts("bug")
#define re  register
#define fi first
#define se second
const int maxn = 2e5+ 5;
const double Inf = 10000.0;
const double PI = acos(-1.0);
typedef  long long ll;
using namespace std;

int a[1005];

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	sort(a, a + n);
	int res = 0;
	for (int i = 0; i < k; i++) res += a[i];
	printf("%d", res);
}

Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define x real()
#define y imag()
#define fi first
#define se second
#define pii pair<int, int>

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, kk;
	cin >> n >> kk;
	vector<int> a(n), f(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0;i < n; i++) {
		cin >> f[i];
	}
	sort(a.begin(), a.end());
	sort(f.rbegin(), f.rend());
	int l = 0, r = 1e16;
	int ans = r;
	while (l <= r) {
		int m = (l + r) / 2;
		int k = kk;
		for (int i = 0; i < n; i++) {
			int tagh = m / f[i];
			if (tagh < a[i]) {
				k -= a[i] - tagh;
			}
		}
		if (k >= 0) {
			ans = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
	cout << ans << "\n";
}



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

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

using ll = int64_t;

using namespace std;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64_t n,m,k;cin >> n >> m >> k;
    vector<int64_t> a(n),b(m);
    vector<int64_t> c(n+1,0),d(m+1,0);

    REP(i,n){
        cin >> a[i];
        c[i+1] = c[i] + a[i];
    }
    REP(i,m){
        cin >> b[i];
        d[i+1] = d[i] + b[i];
    }

    int64_t ans = 0;

    REP(i,n + 1){
       int64_t left = k - c[i];
       if(left < 0)break;
       else{
           int64_t sum = i + (int64_t)(upper_bound(d.begin(),d.end(),left) - d.begin()) - 1;
           ans = max(ans,sum);
       }
    }
    cout << ans << '\n';

}



Measured memory_bytes: 9536
#include <cstdio>
#include <cstring>
#define maxn 2010
int n, m, ans;
char s[maxn];
int p[maxn][maxn];
inline int max(int a, int b) {return a > b ? a : b;}
struct node {
	int len, h;
	void add(int _a, int _b) {len = _a, h = _b;}
} S[maxn];
int top;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j++) p[i][j] = s[j] == '#';
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (p[i][j] ^ p[i + 1][j] ^ p[i][j + 1] ^ p[i + 1][j + 1]) p[i][j] = 0;
			else p[i][j] = p[i - 1][j] + 1;
		}
	}
	ans = max(n, m);
	for (int i = 1; i < n; i++) {
		S[++top].add(1, p[i][1]);
		for (int j = 2, len; j < m; j++) {
			len = 1;
			while (top && S[top].h >= p[i][j]) {
				len += S[top].len;
				ans = max(ans, len * (S[top].h + 1));
				top--;
			}
			S[++top].add(len, p[i][j]);
		}
		int len = 1;
		while (top) {
			len += S[top].len;
			ans = max(ans, len * (S[top].h + 1));
			top--;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
   string S;
   cin>>S;
  
   if(S=="SUN"){
      cout<<7<<endl;
   }
   if(S=="MON"){
      cout<<6<<endl;
   }
   if(S=="TUE"){
      cout<<5<<endl;
   }
   if(S=="WED"){
      cout<<4<<endl;
   }
   if(S=="THU"){
      cout<<3<<endl;
   }
   if(S=="FRI"){
      cout<<2<<endl;
   }
   if(S=="SAT"){
      cout<<1<<endl;
   }
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main(void) {
	int x=0;
	vector<int> data;
	for (int i = 0; i < 10; i++) {
		scanf("%d", &x);
		data.push_back(x);
	}
	sort(data.begin(), data.end(), greater<int>());
	for (int i = 0; i < 3; i++) {
		printf("%d\n", data[i]);
	}

	return 0;
}

Measured memory_bytes: 2656
#include <iostream>
typedef long long ll;
using namespace std;

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

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
C = str(input())

print(chr(ord(C)+1))



Measured memory_bytes: 38384
n = int(input())
a = [0] + list(map(int, input().split()))

m = 0
b = [0] * (n + 1)

for i in reversed(range(1, n+1)):
    cnt = 0
    for j in range(i, n+1, i):
        cnt += b[j]
    if cnt % 2 != a[i]:
        b[i] = 1
        m += 1

print(m)
if m > 0:
    print(*[i for i, j in enumerate(b) if j == 1], sep=' ')


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


#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (int i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (int i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

using namespace std;
inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; } 
inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;

int main () {               
    cin >> s;
    set < char > w;
   w.insert('A'),w.insert('C'), w.insert('G'),w.insert('T'); //"ACGT";
    n = s.size();
    for (int l = 0; l < n; l ++) {
    	int r = l;
    	if (w.find(s[l]) == w.end()) continue;
    	while (r + 1 < n && w.find(s[r + 1]) != w.end()) {
    		r ++;
    	}  
    	ans = max(ans, r - l + 1);
    }
    cout << ans;
    return Accepted;
}

// B...a D....

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

const int maxn = 17;
const LL mod = 998244353;
const int INF=1e9+2e7;

char s[maxn];
int num[4];
int main()
{
    int n,m,i,j,k,x,y,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%s",s);
        x=strlen(s);
        if(s[0]=='B'&&s[x-1]=='A') num[3]++;
        else if(s[0]=='B') num[1]++;
        else if(s[x-1]=='A') num[2]++;
        else num[0]++;
        for(j=1;j<x;j++)
        {
            if(s[j]=='B'&&s[j-1]=='A') ans++;
        }
    }
    x=0;
    if(num[2]>0)
    {
        x++;
        num[2]--;
    }
    if(num[1]>0)
    {
        x++;
        num[1]--;
    }
    x+=num[3];
    if(x>1) ans+=x-1;
    ans+=min(num[1],num[2]);
    printf("%d\n",ans);
    return 0;
}



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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,l; cin>>n>>l;
  ll sum=0;
  reps(i,n){
    sum+=l+i-1;
  }
  ll d=INF;
  ll ans=sum;
  reps(i,n){
    if(chmin(d,abs(sum-(sum-(l+i-1))))){
      ans=sum-(l+i-1);
    }
  }
  cout<<ans<<endl;
}


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

int n,a[MAXN],tot;
long long resp=0LL;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        tot+=a[i];
    }
    tot=round((double)tot/n);


    for(int i=0;i<n;i++){
        resp+=(long long)(pow(a[i]-tot,2));
    }

    cout<<resp;

}

Measured memory_bytes: 384
#include <stdio.h>

int main( void ) {
	int i, j, data[ 10 ], max, tmp;

	for ( i = 10; i--; scanf( "%d", data + i ) ) ;

	for ( i = 0; i < 3; i++ ) {
		max = i;
		for ( j = 9; j > i; j-- )
			if ( data[ max ] < data[ j ] )
				max = j;

		tmp = data[ i ];
		printf( "%d\n", data[ i ] = data[ max ] );
		data[ max ] = tmp;
	}

	return 0;
}

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

int main() {
  string s;
  cin >> s;
  map<char, int> cs;
  for(int i = 0; i < s.size(); ++i) {
    cs[s[i]]++;
  }
  for(int i = 0; i < 26; ++i) {
    char c = i + 'a';
    if(cs[c] == 0) {
      cout << c << endl;
      return 0;
    }
  }
  cout << "None" << endl;
  return 0;
}

Measured memory_bytes: 512
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        m: usize,
        abc: [(Usize1, Usize1, i64); m],
    };
    let abc = abc
        .iter()
        .map(|&(a_i, b_i, c_i)| (a_i, b_i, -c_i))
        .collect::<Vec<_>>();
    let inf = 1_000_000_000_000_000_000_i64;
    // bellman_ford
    let mut d = vec![inf; n];
    d[0] = 0_i64;
    for _ in 0..n - 1 {
        for &(u, v, w) in abc.iter() {
            if d[u] != inf && d[u] + w < d[v] {
                d[v] = d[u] + w;
            }
        }
    }
    let ans = -d[n - 1];
    let mut c = vec![false; n];
    for _ in 0..n {
        for &(u, v, w) in abc.iter() {
            if d[u] == inf {
                continue;
            }
            if d[u] + w < d[v] {
                d[v] = d[u] + w;
                c[v] = true;
            }
            if c[u] {
                c[v] = true;
            }
        }
    }
    if c[n - 1] {
        println!("inf");
    } else {
        println!("{}", ans);
    }
}


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

#define int long long

const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const char dc[4] = {'E', 'S', 'W', 'N'};

signed main() {
  int H, W, L;
  while ( cin >> H >> W >> L, H ) {
    char grid[H][W];
    int used[H][W][4];
    fill_n(**used, H*W*4, -1);    
    int y, x, d;    
    for ( int i = 0; i < H; i++ ) {
      for ( int j = 0; j < W; j++ ) {
	cin >> grid[i][j];
	if ( grid[i][j] != '#' && grid[i][j] != '.' ) {
	  y = i; x = j;
	  if ( grid[i][j] == 'E' ) d = 0;
	  if ( grid[i][j] == 'S' ) d = 1;
	  if ( grid[i][j] == 'W' ) d = 2;
	  if ( grid[i][j] == 'N' ) d = 3;
	}
      }
    }

    int cnt = 0;
    bool flag = false;
    while ( 1 ) {
      if ( used[y][x][d] >= 0 && !flag ) {
	if ( L-cnt-used[y][x][d]-10 > 0 ) {
	  cnt += (L-cnt-used[y][x][d]-1)/(cnt-used[y][x][d])*(cnt-used[y][x][d]);
	}
	flag = true;
      }
      if ( cnt >= L ) break;
      if ( cnt ) used[y][x][d] = cnt;      
      int nx = x+dx[d], ny = y+dy[d];
      if ( nx < 0 || ny < 0 || nx >= W || ny >= H || grid[ny][nx] == '#' ) {
	d = (d+1)%4LL;	
      } else {
	cnt++;
	x = nx;
	y = ny;
	if ( cnt >= L ) break;
      }
    }

    cout << y+1 << " " << x+1 << " " << dc[d] << endl;
  }

  return 0;
}



Measured memory_bytes: 3416
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef pair<int,int> P;
typedef long long ll;

int main(void){
    int a,b;
    cin>>a>>b;
    cout<<max(a+b,max(a-b,a*b))<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

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

int main(){
    int n;
    cin >> n;
    vector<int>a(n),b(n);
    rep(i,n)cin >> a[i] >> b[i];
    sort(all(a));
    sort(all(b));
    int c,d;
    if(n%2==0){
        c = n/2-1;
        d = n/2;
        cout << ((b[c]+b[d]) - (a[c]+a[d])) + 1 << endl;
    }else{
        c = n/2;
        d = n/2;
        cout << (b[c]+b[d])/2 - (a[c]+a[d])/2 + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 4348
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

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

    vector<int>::iterator a_max = max_element(a.begin(), a.end());
    vector<int>::iterator a_min = min_element(a.begin(), a.end());

    if (*a_max < 0) {
        cout << n - 1 << endl;
        for (int i = 0; i < n - 1; i++) {
            cout << n - i << " " << n - i - 1 << endl;
        }
    } else if (*a_min >= 0) {
        cout << n - 1 << endl;
        for (int i = 0; i < n - 1; i++) {
            cout << i + 1 << " " << i + 2 << endl;
        }
    } else if (abs(*a_max) < abs(*a_min)) {
        cout << 2 * n - 1 << endl;
        for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
            cout << a_min - a.begin() + 1 << " " << i - a.begin() + 1 << endl;
        }
        for (int i = 0; i < n - 1; i++) {
            cout << n - i << " " << n - i - 1 << endl;
        }
    } else {
        cout << 2 * n - 1 << endl;
        for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
            cout << a_max - a.begin() + 1 << " " << i - a.begin() + 1 << endl;
        }
        for (int i = 0; i < n - 1; i++) {
            cout << i + 1 << " " << i + 2 << endl;
        }
    }
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	var a, b int
	minAB := n - 1

	for i := 1; i <= int(math.Sqrt(float64(n))); i++ {
		if n%i == 0 {
			a = n / i
			b = i

			if minAB > a+b-2 {
				minAB = a + b - 2
			}
		}

	}

	fmt.Println(minAB)
}


Measured memory_bytes: 512
N, M = map(int, input().split())

shita = 1
ue = 100000
for i in range(0, M):
    Li, Ri = map(int, input().split())
    if shita < Li:
        shita = Li
    if Ri < ue:
        ue = Ri

print(max(ue - shita + 1, 0))


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

int main()
{
  int num1, num2, num3, total;
  total = 0;

  cin >> num1 >> num2 >> num3;
  total = num1 + num2 + num3;

  if(total >= 22)
  {
    cout << "bust" << endl;
  }
  else
  {
    cout << "win" << endl;
  }
}


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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
const ll ll_inf = ll(1e9) * ll(1e9);
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
    ll h, w;
    cin >> h >> w;
    ll startX, startY, endX, endY;
    cin >> startX >> startY >> endX >> endY;
    startX--, startY--, endX--, endY--;

    vector<vector<char>> s(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> s[i][j];

    vector<vector<ll>> cnts(h, vector<ll>(w, ll_inf));  // 魔法使った回数
    queue<P> q, visited;
    q.push(P(startX, startY));
    cnts[startX][startY] = 0;

    while (!q.empty() || !visited.empty()) {
        ll nowX, nowY;
        if (!q.empty()) {
            nowX = q.front().first, nowY = q.front().second;
            visited.push(P(nowX, nowY));
            q.pop();
            rep(i, 4) {
                ll nextX = nowX + dx[i], nextY = nowY + dy[i];
                if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                    if (s[nextX][nextY] == '#') continue;
                    if (cnts[nowX][nowY] < cnts[nextX][nextY]) {
                        cnts[nextX][nextY] = cnts[nowX][nowY];
                        q.push(P(nextX, nextY));
                    }
                }
            }

        }
        else {  // 今まで通った道から魔法で行ける道を全て調べる
            nowX = visited.front().first, nowY = visited.front().second;
            visited.pop();
            for (ll ix = -2; ix <= 2; ++ix) {
                for (ll jy = -2; jy <= 2; ++jy) {
                    ll nextX = nowX + ix, nextY = nowY + jy;
                    if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                        if (s[nextX][nextY] == '#') continue;
                        if (cnts[nowX][nowY] + 1 < cnts[nextX][nextY]) {
                            cnts[nextX][nextY] = cnts[nowX][nowY] + 1;
                            q.push(P(nextX, nextY));
                        }
                    }
                }
            }
        }
    }
    if (cnts[endX][endY] == ll_inf) {
        cout << -1 << '\n';
    }
    else {
        cout << cnts[endX][endY] << '\n';
    }
    return 0;
}

Measured memory_bytes: 12472
#include<stdio.h>
int main(){
    double r; //rの定義
    scanf("%lf", &r);　//rの入力
    r = 2 * 3.14159265 * r;　//半径から円周を計算、格納
    printf("%lf",r);　//rの出力
    return 0;
}

Measured memory_bytes: 2216
/*

Name: Krishan Kant Agnihotri
FROM: University school of information and technology

*/
#include<bits/stdc++.h>
#define ull unsigned long long int
#define ll long long
#define FOR(i,n) for(int i = 0;i<n ;i++)
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define mii map<int,int>
#define uii unordered_map<int,int>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

#define pb push_back
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define print(x) cout<<x<<"\n";
using namespace std;
;
//use it with unordered_map<T,T,custom_hash> safe_map
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main()
{
    int n;
    cin>>n;
    ll i,j,k;
   vector<int> v(10060);
   for(int i = 1 ;i<=105;i++){
       for(j = 1 ;j<=105;j++){
           for(k = 1 ;k<=105;k++){
               ll tmp = i*i+j*j+k*k+i*j+i*k+j*k;
               if(tmp<10060)
               v[tmp]++;
           }
       }
   }
   for( i  =0 ;i<n ;i++){
       cout<<v[i+1]<<endl;
   }
    
}



Measured memory_bytes: 3612
#include <stdio.h>
#include <iostream>
#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;

struct node
{
    int key;
    node *parent, *left, *right;
};

node *root = nullptr;
void insert(node *z)
{
    node *y = nullptr;
    node *x = root;
    while (x != nullptr)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->parent = y;

    if (y == nullptr)
        root = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;
}

bool find(int k)
{
    node *x = root;
    while (x != nullptr)
    {
        if (x->key == k)
            return true;
        else if (x->key > k)
            x = x->left;
        else
            x = x->right;
    }
    return false;
}
node *getNextNode(node *x) //return x's succesor
{
    node *y;
    if (x->right == nullptr)
    {
        y = x->parent;
        while (y->left != x || y != nullptr)
        {
            x = y;
            y = x->parent;
        }
        return y;
    }
    else
    {
        x = x->right;
        while (x != nullptr)
        {
            y = x;
            x = x->left;
        }
        return y;
    }
}
void del(int k)
{
    node *x, *y, *z = root;
    while (z != nullptr)
    {
        if (z->key == k)
            break;
        else if (z->key > k)
            z = z->left;
        else
            z = z->right;
    }

    if (z == nullptr)
        return;
    if (z->left == nullptr || z->right == nullptr)
        y = z;
    else
        y = getNextNode(z);

    if (y->left != nullptr)
        x = y->left;
    else
        x = y->right;

    if (x != nullptr)
        x->parent = y->parent;

    if (y->parent == nullptr)
        root = x;
    else if (y->parent->left == y)
        y->parent->left = x;
    else
        y->parent->right = x;

    if (y != z)
        z->key = y->key;

    return;
}

void Preorder(node *x)
{
    printf(" %d", x->key);
    if (x->left != nullptr)
        Preorder(x->left);
    if (x->right != nullptr)
        Preorder(x->right);
}

void Inorder(node *x)
{
    if (x->left != nullptr)
        Inorder(x->left);
    printf(" %d", x->key);
    if (x->right != nullptr)
        Inorder(x->right);
}

int main()
{
    int m, k;
    string str;
    cin >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> str;
        if (str[0] == 'i')
        {
            node *z = (node *)malloc(sizeof(node));
            cin >> z->key;
            z->left = nullptr;
            z->right = nullptr;
            z->parent = nullptr;
            insert(z);
        }
        else if (str[0] == 'f')
        {
            cin >> k;
            if (find(k))
                printf("yes\n");
            else
                printf("no\n");
        }
        else if (str[0] == 'd')
        {
            cin >> k;
            del(k);
        }
        else
        {
            Inorder(root);
            printf("\n");
            Preorder(root);
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 21860
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int a[];
    static int answer = -1000000000;
    static int minv;


    public static void main(String[] args) {
        read();
        solve();
        System.out.println(answer);
    }

    public static void read() {
        n = sc.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        minv = a[0];

    }

    public static void solve() {
        for (int i = 1; i < n; i++) {
            if (a[i] - minv > answer) {
                answer = a[i] - minv;
            }
            if (minv > a[i]) {
                minv = a[i];
            }
        }
    }
}

Measured memory_bytes: 101936
#include <stdio.h>
int a[500],head=0;
int main(){
  int b,num=0;
  char c,d;
   
  while( (scanf("%c",&c))!=EOF){ 
    if(num==0&&c=='0'){ a[head]=num;
      head++;}
 
    if(c<='9'&&c>='0'){num=c-'0'+num*10;}      
    else if(num!=0){  
      a[head]=num;
      head++;
      num=0;
    }
    else {num=0;
      if(c=='+'){
        a[head-2]+=a[head-1];
        head--;
      }
      else if(c=='*'){
        a[head-2]*=a[head-1];
        head--;
      }
 
      else if(c=='-'){
        a[head-2]-=a[head-1];
        head--;
      }
    }  
  }
     
  printf("%d\n",a[head-1]);  
 
  return 0;
}

Measured memory_bytes: 540
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;




int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    vector<ll> count(n,0);
    ll mx=0;
    ll mi=E;
    for(int i=0;i<n;i++){
        cin>>a[i];
        count[a[i]]++;
        mx=max(mx,a[i]);
        mi=min(mi,a[i]);
    }
    if(count[mi]!=(mx&1?2:1) || mi!=(mx+1)/2){cout<<"Impossible"<<endl; return 0;}
    for(ll i=mx;i>mi;i--){
        if(count[i]<2){cout<<"Impossible"<<endl; return 0;}
    }
    cout<<"Possible"<<endl;
    
    
    
    
    return 0;
}


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

long double a, b, x;

// cos a
double costh(double a, double b, double c) {
  return (b * b + c * c - a * a) / (2.0 * b * c);
}

long double solve();

int main() {
  cout << fixed << setprecision(10);
  cin >> a >> b >> x;
  cout << solve() << endl;
  return 0;
}

long double solve() {
  if(a * a * b == x) return 0;
  long double t, s, ans;
  if(a * a * b / 2 <= x) {
    t = (a * a * b - x) / (a * a / 2);
    s = sqrtl(a * a + t * t);
    ans = acos(a / s);
  }
  else {
    t = x * 2 / (b * a);
    s = sqrtl(t * t + b * b);
    ans = acos(-1) / 2 - acos(b / s);
  }

  return 180 * ans / acos(-1);
}

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

public class Main {

	static long expo(long base, long exp) {
		long t = 1L;
		while (exp > 0) {
			if (exp % 2 != 0)
				t = (t * base);

			base = (base * base);
			exp /= 2;
		}
		return t;
	}

	public static void main(String args[]) throws Exception {
		MyScanner sc = new MyScanner();
		PrintWriter pr = new PrintWriter(System.out);
		long x = sc.nextLong();
		long a = 0L, b = 0L;
		for (long i = -1000; i <= 1000; i++) {
			for (long j = -1000; j <= 1000; j++) {
				
				long p = expo(i , 5L);
				long q = expo(j , 5L);
				
				if(p - q == x) {
					a = i;
					b = j;
					break;
				}
			}
		}
		System.out.println(a + " " + b);
		pr.close();
	}

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

Measured memory_bytes: 37032
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

inf = 10 ** 18
dis = [inf] * n
dis[0] = 0

for z in range(2*n+1):
    update = False
    for a, b, c in edge:
        a -= 1
        b -= 1
        if dis[a] != inf and dis[b] > dis[a] - c:
            dis[b] = dis[a] - c
            update = True
            if b == n - 1 and z >= n - 1:
                print('inf')
                exit()
print(-dis[n-1])

Measured memory_bytes: 45672
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
const long INF = 1000000009;

typedef std::pair<int, int> P;

int h, w, d;
P pos[90000]; 
int dist[90000];

int main(){
	scanf("%d%d%d", &h, &w, &d);
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			int a;
			scanf("%d", &a);
			pos[a-1].first = i;
			pos[a-1].second = j;
		}
	}
	for(int i = d; i < h*w; i++){
		dist[i] = dist[i-d] + std::abs(pos[i].first - pos[i-d].first) + std::abs(pos[i].second - pos[i-d].second);
	}
	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", dist[r-1] - dist[l-1]);
	}
	return 0;
}


Measured memory_bytes: 2176
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let s: String = read();
    let mut d: Vec<bool> = vec![false; 27];
    let sc: Vec<char> = s.chars().collect();

    for i in 0..sc.len() {
        let si = sc[i];
        d[(si as u32 - 'a' as u32) as usize] = true
    }

    let mut ans: i64 = -1;
    for i in 0..d.len() {
        if d[i] == false {
            ans = i as i64;
            break;
        }
    }

    if ans == -1 || ans == 26 {
        println!("None")
    } else {
        println!("{}", std::char::from_u32('a' as u32 + ans as u32).unwrap());
    }
}


Measured memory_bytes: 4352
n = int(input())
if n == 1:
    print(1)
    exit()

i = 2
L = [0]*(n+1)
L[0] = 2
L[1] = 1
while i != n:
    L[i] = L[i-1]+L[i-2]
    i+=1

print(L[n-1]+L[n-2])


Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include <cmath>

#define fi first
#define se second
#define all(x) x.begin(), x.end()
using namespace std;
using ull = unsigned long long;
using ll = long long;

struct __INIT {
    __INIT() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __init;

int main() {
    int N;
    cin >> N;
    string s, t;
    cin >> s >> t;
    if(s.size() + t.size() <= N){
        cout << N << endl;
    }else {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            bool ok = true;
            int k = 0;
                for (int j = i; j < n; j++) {
                    if(k < t.size()) {
                        if (s[j] != t[k]) {
                            ok = false;
                            break;
                        }
                        k++;
                    }else break;
                }

            if(ok and N <= t.size() + i){
                cout << t.size() + i << endl;
                return 0;
            }
        }
        cout << s.size() + t.size() << endl;
    }

}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N, K, Q; cin >> N >> K >> Q;
	VI A(N);
	int ans = LLINF;
	REP(i, N)cin >> A[i];
	REP(i, N) {
		int X = A[i];
		VI tmp,fin;
		REP(j, N) {
			if (A[j] >= X)tmp.push_back(A[j]);
			else {
				SORT(tmp);
				REP(k, (int)tmp.size() - K + 1) {
					fin.push_back(tmp[k]);
				}
				
				tmp.clear();
				
			}
		}
		SORT(tmp);
		REP(k, (int)tmp.size() - K + 1)fin.push_back(tmp[k]);
		SORT(fin);
		if (Q - 1 < (int)fin.size())chmin(ans, fin[Q - 1] - fin[0]);
	}
	cout << ans << endl;

	
	return 0;
}



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

int main()
{
    string n;
    cin >> n;
    int x=n.size();
    int ans=0;
    for(int i=0;i<x;i++){
        if(n.at(i)=='x'){
            ans++;
        }
    }
    if(ans>=8){
        cout<<"NO"<<endl;
    }
    else{
        cout<<"YES"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<int>A(3);
  for(int i=0;i<3;i++){
    cin>>A[i];
  }
  sort(A.begin(),A.end());
  if(A[0]==A[1]&&A[1]!=A[2])cout<<"Yes"<<endl;
  else if(A[2]==A[1]&&A[0]!=A[2])cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

#define REP(i,n) for(int i = 0;i < n;i++)
#define REPR(i,n) for(int i = n-1;i >= 0;i--)
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define PRINT(s) cout<<s
#define PRINTS(s) cout<<s<<' '
#define PRINTL(s) cout<<s<<endl
#define INF 2e9
#define ALL(v) v.begin(),v.end()
#define ll long long

using namespace std;

string pop_back(string s){
    string t = s.substr(0,s.size()-1);
    return t;
}

int gcd(int max,int min){
    
    if(max<min){
        int tmp=max;
        max=min;
        min=tmp;
    }

    if(max%min==0)return min;
    else return gcd(min,max%min);

}

int main(void){

    int x,y,z;
    cin>>x>>y>>z;

    int people=0;
    int haba=0;
    while(haba<=x){
        people++;
        haba=people*y+(people+1)*z;
    }
    cout<<people-1<<endl;

    return 0;
}




Measured memory_bytes: 256
// AtCoder Grand Contest 015
// A - A+...+B Problem

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;


ll N, A, B;

int main() {

    ll ans;

    cin >> N >> A >> B;

    if (A > B) {
        ans = 0;
    } else {
        ans = max(0LL, (B - A) * (N - 2) + 1);
    }
    cout << ans << endl;

    return 0;

}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;

string s[1000];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int r, c;

bool good(int x, int y)
{
    return x >= 0 && y >= 0 && x < r && y < c;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> r >> c;
    queue<pair<int, int>> q, p;
    for (int i = 0; i < r; ++i)
    {
        cin >> s[i];
        for (int j = 0; j < c; ++j)
            if (s[i][j] == '#')
                p.emplace(i, j);
    }
    int sol = 0;
    while (!p.empty())
    {
        q = p;
        p = queue<pair<int,int>>();
        while (!q.empty())
        {
            int x,y;
            tie(x,y) = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (!good(xx, yy)) continue;
                if (s[xx][yy] == '.')
                {
                    s[xx][yy] = '#';
                    p.emplace(xx, yy);
                }
            }
        }
        if (!p.empty())
            sol++;
    }
    cout << sol;
}


Measured memory_bytes: 17680
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
long long  inv(long long b)
{
	if(b == 1)
	return 1;
	return (mod-mod/b)*inv(mod%b)%mod;
}
long long fac[N];
long long C(long long n,long long m)
{
	long long t = (fac[m]*fac[n-m])%mod;
	return (fac[n]*inv(t))%mod;
}
int main()
{
	long long n,i,a,b,k;
	fac[0] = 1;
	fac[1] = 1;
	for(i = 2;i <= 3e5+5;i++)
	    fac[i] = (fac[i-1]*i)%mod;
	cin>>n>>a>>b>>k;
	long long res = 0;
	for(i = 0;i <= n;i++)
	{
		if(k-(i*a) >= 0 && (k-a*i)%b == 0 && (k-a*i)/b <= n)
		{
		    res = (res+C(n,i)*C(n,(k-a*i)/b)%mod)%mod;
		}
	}
	cout<<res<<endl;

}


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

int main() {
    //
    int num;
    string str;
    map<string, int> m;
    vector<string> vec;
    // vector<string> vec1;

    cin >> num >> str;
    for (int i = 0; i < str.size() - 2; i++) {
        auto exists = find(vec.begin(), vec.end(), str.substr(i, 1)) != vec.end();
        if (exists == true) continue;

        vec.push_back(str.substr(i, 1));

        vector<string> vec2;
        for (int j = i + 1; j < str.size() - 1; j++) {
            auto exists2 = find(vec2.begin(), vec2.end(), str.substr(j, 1)) != vec2.end();
            if (exists2 == true) continue;

            vec2.push_back(str.substr(j, 1));

            for (int k = j + 1; k < str.size(); k++) {
                string tmp;
                tmp = str.substr(i, 1) + str.substr(j, 1) + str.substr(k, 1);
                m[tmp]++;
                // cout << tmp << endl;
            }
        }
    }

    cout << m.size() << endl;
    //
}

Measured memory_bytes: 3724