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

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define endl "\n"
#define fff ff
#define sss ss.ff
#define ttt ss.ss
#define INF (1 << 30)
#define LLF (1ll << 60)
#define PRIME (1000000007)
#define FASTIO                      \
  std::ios::sync_with_stdio(false); \
  cin.tie(0)
#ifdef DEBUG
#define debug(x) cerr << #x << " = " << x << endl
#else
#define debug(x)
#endif
#define rep(i, begin, end)                            \
  for (__typeof(end) i = (begin) - ((begin) > (end)); \
       i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#define FILE_INPUT                  \
  freopen("input.txt", "r", stdin); \
  freopen("output.txt", "w", stdout)

#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<string> vs;

/*-----------------END TEMPLATE-----------------*/

ll _fat[2000050];

ll fat(ll i) { return _fat[i]; }

ll fast_exp(ll b, ll e) {
  ll res = 1;
  while (e) {
    if (e & 1) res = (res * b) % PRIME;

    e >>= 1;
    b = (b * b) % PRIME;
  }
  return res % PRIME;
}

ll inverse(ll i) { return (fast_exp(i, PRIME - 2) % PRIME); }

int main() {
  FASTIO;
  ll x, y;
  cin >> x >> y;
  _fat[0] = 1;
  _fat[1] = 1;
  for (ll i = 2; i <= 1000000; i++) {
    _fat[i] = (i * _fat[i - 1]) % PRIME;
  }

  ll ans = 0;
  for (ll i = 0; i <= 1000000; i++) {
    ll xx = i;
    ll yy = 2 * i;

    ll left = x - xx;
    ll lefty = y - yy;
    if (left < 0 || lefty < 0) continue;
    if (left != lefty * 2) continue;

    ll n = i + lefty;
    ll res =
        (((fat(n) * inverse(fat(n - i))) % PRIME) * inverse(fat(i))) % PRIME;
    ans = (ans + res) % PRIME;
  }

  cout << ans << endl;
}


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

int main()
{
    int N, K;
    cin >> N >> K;
    long count = 0;
    for (int i = 1; i <= N;i++){
        //cout << i << ' ' << i + K-1 << endl;
        if(i+K-1 <= N){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

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

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

        long n = sc.NextLong();

        long answer = 0;

        for (long i = 1; i <= n; i++)
        {
            long count = n / i;
            long tmpSum = i * (1 + count) * count / 2;
            answer += tmpSum;
        }

        Console.WriteLine(answer);
    }

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

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

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

            return _line[_index++];
        }

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

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

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


Measured memory_bytes: 27400
N = int(input())
H = list(map(int, input().split()))

H0 = H[0]
cnt = 0
cnt_list = []
for i in H[1:]:
  if H0 >= i:
    cnt += 1
  else:
    cnt_list += [cnt]
    cnt = 0
  H0 = i
cnt_list += [cnt]
print(max(cnt_list))

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

using namespace std;

typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)



signed main(){

	char in[1000];
	stack<int> s;

	while (scanf("%s", in) != EOF){
		if ('0' <= in[0] && in[0] <= '9')
			s.push(atoi(in));
		else if (in[0] == '+'){
			int a = s.top(); s.pop();
			int b = s.top(); s.pop();
			s.push(a + b);
		}
		else if (in[0] == '-'){
			int a = s.top(); s.pop();
			int b = s.top(); s.pop(); 
			s.push(b - a);
		}
		else if (in[0] == '*'){
			int a = s.top(); s.pop();
			int b = s.top(); s.pop();
			s.push(a * b);
		}
	}

	cout << s.top() << endl;

	return 0;
}



Measured memory_bytes: 3224
x, n = map(int, input().split())
p = list(map(int,input().split()))
ux = x
dx = x
while True:
    if dx in p:
        dx -= 1
    else:
        ans1 = dx
        break
while True:
    if ux in p:
        ux += 1
    else:
        ans2 = ux
        break
if x-dx <= ux-x:
    print(dx)
else:
    print(ux)

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

const ll INF = 1e15;

struct edge {
  int u, v, cost;
};

ll dist[1010];

int main() {
  int N, M;
  cin >> N >> M;
  vector<edge> edges(M);
  for (auto &e : edges) {
    cin >> e.u >> e.v >> e.cost;
    e.u--, e.v--;
    e.cost = -e.cost;
  }

  vector<ll> dist(N, INF);
  dist[0] = 0;
  for (int i = 0; i < 2 * N; i++) {
    for (auto e : edges) {
      if (dist[e.u] == INF) continue;
      if (dist[e.u] + e.cost < dist[e.v]) {
        dist[e.v] = dist[e.u] + e.cost;
        if (i >= N - 1) dist[e.v] = -INF;
      }
    }
  }
  if (dist[N - 1] == -INF)
    cout << "inf" << endl;
  else
    cout << -dist[N - 1] << endl;
}

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int visited[maxn];
vector<int> g[maxn];

void dfs(int u) {
    visited[u] = true;
    for (auto x : g[u]) {
        if (!visited[x]) {
            dfs(x);
        }
    }
}
void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)if (!visited[i])dfs(i), ans++;
    cout << ans - 1 << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 11068
input_color = gets.split(' ').map{ |d| d.chomp}
input_count = gets.split(' ').map{ |d| d.to_i}
delete_color = gets.chomp
obj = Hash.new()
input_color.each_with_index do |el, idx|
  obj[el] = input_count[idx]
end
obj[delete_color] = obj[delete_color] - 1
puts "#{obj[input_color[0]]} #{obj[input_color[1]]}"

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define ll/*////////*/long long                           ///////////////////////////////
#define gcd(a,b)/*////////*/__gcd(a,b)                    //Please get-off from my code//
#define pi/*////////*/3.1415926536                        ///////////////////////////////
using namespace std;
int lcm(int a,int b){return (a*b)/(gcd(a,b));}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	//------Enter your code here.------
	int a,b,c,k;cin>>a>>b>>c>>k;
	while(b<=a and k)
	{
		b*=2;k--;
	}
	while(c<=b and k)
	{
		c*=2;k--;
	}
	if(b>a and c>b)cout<<"Yes\n";
	else cout<<"No\n";
}

Measured memory_bytes: 3608
A,B,H,M=map(int,input().split())

import math
theta_a = (30.*H+0.5*M)/180 * math.pi
theta_b = (6.*M)/180 * math.pi
# 原点はもう一つの端点
pa = [A*math.cos(theta_a), A*math.sin(theta_a)]
pb = [B*math.cos(theta_b), B*math.sin(theta_b)]

dis = math.sqrt((pa[0]-pb[0])**2+(pa[1]-pb[1])**2)
print(dis)


Measured memory_bytes: 9516
#include<iostream>
using namespace std;
int main()
{
   int i,c=0,a,b,sub;
   cin>>a>>b;
   for(i=1; ;i++)
   {
       sub=a-b;
       a=sub;
       if(sub<=0)
       {
           break;
       }


   }

    cout<<i<<endl;

  return 0;
}


Measured memory_bytes: 3600
from collections import defaultdict


N,K = map(int, input().split())
A = list(map(int, input().split()))

d = defaultdict(int)
# 先頭からiビット目に1が立っている個数を数え上げる
for a in A:
    for i in range(50):
        if a & (1 << i):
            d[i] += 1
dp = [[-1 for _ in range(2)] for _ in range(51)]
dp[0][0] = 0

# 頭からi桁
for i in range(50):


    # 先頭からi番目の位置の数字
    if K & (1 << (50-i-1)):
        digit = 1
    else:
        digit = 0

    # i桁目に1を選んだ時
    use_1 = (N-d[50-i-1]) * (1 << (50-i-1))
    # i桁目に0を選んだ時
    use_0 = d[50-i-1] * (1 << (50-i-1))

    if K < (1 << (50-i-1)):
        use_1 = 0

    """
    i-1桁までがKより小さい場合、0,1どちらも選択可能
    dp[i][1] == -1 だとそれは起こりえない
    """
    if dp[i][1] != -1:
        dp[i+1][1] = max(dp[i+1][1], dp[i][1] + max(use_0, use_1))

    """
    i-1桁まで同じで、i桁目でKより小さくなる場合（Kのi桁目が1で0を選択）
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][1] = max(dp[i+1][1], dp[i][0] + use_0)

    """
    i-1桁まで同じで、i桁目でKとまた一致する場合
    """
    if dp[i][0] != -1:
        if digit == 1:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_1)
        else:
            dp[i+1][0] = max(dp[i+1][0], dp[i][0] + use_0)

print(max(dp[-1]))


Measured memory_bytes: 68696
#include<bits/stdc++.h>
    using namespace std ; 
    const int MAXN = 2000 + 100 ; 
     
    int n , k , res  , dp[MAXN] , ans = MAXN; 
    vector<int>adj[MAXN] ; 
     
    void dfs(int u , int par=-1 , int h=0 )
    {
    	if(h>(k/2))
    		res++ ;
    	if(k%2 == 1 && h == (k/2)+1)
    		dp[u] ++ ; 
    	
    	for(auto v : adj[u])
    	{
    		if(v == par)
    			continue ; 
    		dfs(v , u , h+1) ; 
    		dp[u] += dp[v] ; 
    	}
    }
     
    int main()
    {
    	cin >> n >> k ; 
    	for(int i=0 ; i<n-1 ; i++)
    	{
    		int u , v ; 
    		cin >> u >> v ; 
    		u-- , v-- ;
    		adj[u].push_back(v) ;
    		adj[v].push_back(u) ; 
    	}
    	
    	for(int i=0 ; i<n  ;i++)
    	{
    		dfs(i) ; 
    		if(k%2 == 1)
    		{
    			int mx = 0  ;
    			for(auto x : adj[i])
    			{
    				mx = max(mx , dp[x]) ;
    			}
    			res-=mx;
    		}
    		ans= min(ans , res) ; 
    		res = 0 ; 
    		for(int j=0 ; j<n ; j++)
    			dp[j] = 0  ; 
    	}
    	cout << ans << endl ; 
    }

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

int main(){
	
	long long int year1,year2;
	cin>>year1>>year2;
	
	int min=2020;
	//2000 5000
	//2020 4040
	//4038
	if(year2-year1>=2019){
		min=0;
	}else{
		for(long long int i=year1;i<=year2;i++){
			for(long long int j=i+1;j<=year2;j++){
				long long int s;
				s=((i%2019)*(j%2019))%2019;
				if(s<min){
					min=s;
				}
			}
		}
	}
	cout<<min<<endl;
	return 0;
}






Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "queue"
using namespace std;


vector <int> bfs (int v, vector < vector <int> > &adj)
{
	vector < int > visited(adj.size(), 0);
	queue < pair <int, int> > q;
	q.push({v, -1});
	while (not q.empty())
	{
    int current, parent;
    tie(current, parent) = q.front(); q.pop();
		if (not visited[current])
		{
			visited[current] = parent;
			// cout << current << ' ';
			for (auto i: adj[current]) {
        q.push({i, current});
      }
		}
	}
  return visited;
}

int main() {
  int n, m, a, b, possible = 1;
  cin >> n >> m;
  vector < vector <int> > adj(n+1);
  for (int i=0; i<m; i++) {
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  auto visited = bfs(1, adj);
  for (int i=1; i<=n; i++) {
    if (!visited[i]) {
      possible = 0;
      break;
    }
  }
  if (!possible) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    for (int i=2; i<=n; i++) {
      cout << visited[i] << '\n';
    }
  }
}


Measured memory_bytes: 11788
#include <bits/stdc++.h>
#include <cctype>
#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(){
    string str;
    getline(cin, str);
    int q;
    cin >> q;
    string order, p;
    int a, b;
    for (int i=0; i<q; i++){
        cin >> order >> a >> b;
        if (order=="replace") {
            cin >> p;
            str.replace(a, b-a+1, p);
        }
        if (order=="print") cout << str.substr(a,b-a+1) << endl;
        if (order=="reverse") {
            string str_rev(b-a+1, 'a');
            int j = 0;
            for(int i=b; i>=a;i--){
//                cout << i << ' ' << j << endl;
                str_rev.at(j) = str.at(i);
                j++;
            }
        str.replace(a,b-a+1,str_rev);
        }
//    cout << str << endl;
    }
}


Measured memory_bytes: 3184
[W,H,x,y,r] = input().split(' ')

W = int(W)
H = int(H)
x = int(x)
y = int(y)
r = int(r)
h = False

if r<=x and x <= W - r and r <=y and y <= H - r:
    print ('Yes')
else:
    print ('No')

Measured memory_bytes: 6724
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
// please, read the question correctly (do you need set or multiset)???
const int N=200010; //check the limits, dummy
int a[N];
int n, m;
int main(){
	ll x, k, d;
	scanf("%lld%lld%lld",&x,&k,&d);
	x=abs(x);
	ll tmp=x/d;
	if(tmp%2==k%2){
		k=min(k, tmp);
	}
	else{
		k=min(k, tmp+1);
	}
	ll ans=abs(x-k*d);
	cout<<ans<<endl;
}

Measured memory_bytes: 3796
#include <iostream>

using namespace std;

int order[4000];

bool search(int);

class Member {
public:
	Member() {sum = 0;}
	
	void add(long price, long num) {
		sum += (long long int)price*num;
	}
	
	bool milion()
	{
		if (sum >= 1000000) return true;
		else return false;
	}
	
private:
	long long int sum;
	int id;
};


bool search(int num)
{
	for (int i=0; i<4000; i++) 
		if (order[i] == num ) return true;
	
	return false;
	
}

int main()
{
	int n, idx, memNum;
	long price, num;
	bool nothing;

	
	ios::sync_with_stdio();
	
	while (1) {
		Member *member = new Member[4000];
		memNum=0;
		nothing =true;
		
		for (int i=0; i<4000; i++) order[i] = -1;
		
		if (cin >> n, !n) break;
		for (int i=0; i<n; i++) {
			scanf("%d %ld %ld", &idx, &price, &num);
			member[idx].add(price, num);
			if (!search(idx)) order[memNum++] = idx;
		}
		
		for (int i=0; i<4000 && order[i] > 0; i++) 
			if (member[order[i]].milion()) { cout << order[i] << endl; nothing = false; }
		if (nothing) cout << "NA" << endl;
	}
}

Measured memory_bytes: 0
#define _USE_MATH_DEFINES
 
#include <bits/stdc++.h>
 
#define len(x) (int)((x).size())
#define endl '\n'
#define x first
#define y second
#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
 
#ifdef LOCAL
	#define dbg(x) cout << #x << " = " << x << endl;
#else 
	#define dbg(x)
#endif 
 
using namespace std;
 
void solve(); signed main() {
#ifdef LOCAL
    freopen("file1.txt", "r", stdin);                                       
    freopen("file2.txt", "w", stdout);
#endif
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(15);
    solve();  	
}

void solve() {
	vector<string> dt = {"Sunny", "Cloudy", "Rainy", "Sunny"};

	string s;
	cin >> s;

	for (int i = 0; i < 3; ++i) {
		if (dt[i] == s) {
			cout << dt[i + 1] << endl;
			return;
		}
	}
}

Measured memory_bytes: 256
//1hour 10minutes
#include <bits/stdc++.h>
#define dbg(x) cout << #x << ": " << (x) << '\n'
#define ff first
#define ss second
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
const ll mod = 998244353;

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

   int n, s;
   cin >> n >> s;
   vector <ll> a(n);
   for (auto &i : a)
      cin >> i;
   vector <vector <ll>> dp(n + 1, vector <ll> (s + 1));
   vector <ll> bin(n + 1, 1);
   for (int i = 1; i <= n; i++) {
      bin[i] = (2 * bin[i - 1]);
   }

   dp[0][0] = 1;

   for (int i = 0; i < n; i++) {
      for (int j = 0; j <= s; j++) {
         dp[i + 1][j] += (2 * dp[i][j]) % mod;
         dp[i + 1][j] %= mod;
         if (dp[i][j] && j + a[i] <= s) {
            dp[i + 1][j + a[i]] += dp[i][j];
            dp[i + 1][j + a[i]] %= mod;
         }
      }
   }

   cout << dp[n][s] % mod << '\n';

   return 0;
}

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

#define fs first
#define se second
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ") 
{ rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

int main() {
	vector<pii> v;
	lint n = in(), k = in();

	rep(i, n) {
		int a = in(), b = in();
		v.push_back(pii(a, b));
	}

	sort(all(v));

	lint cnt = 0;
	rep(i, n) {
		cnt += v[i].se;
		if (cnt >= k) {
			print(v[i].fs);
			return 0;
		}
	}
}



Measured memory_bytes: 1400
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef vector<LL> VEC;
typedef vector<VEC> VVEC;
typedef  pair<LL,LL> P;


const LL INF=1<<30;
const LL MOD=1000000007;




int main(){
    	int a,b,c,x;
        cin>>a>>b>>c>>x;
        int count=0;
        for(int i=0;i<=a;++i){
            for(int j=0;j<=b;++j){
                for(int k=0;k<=c;++k){
                    if(i*500+j*100+k*50==x){
                        count++;
                    }
                }
            }
        }
        cout<<count<<endl;
}



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

using namespace std;

int main() {

  

  string s,t;
  cin >> s;
  
  for (int i=0 ;i<4;i++){
    t= t+s.at(i);
   }
  t = t+ ' ';
  for(int i =4;i<12;i++){
    t=t+s.at(i);
    }
  cout << t<< endl;

  }



Measured memory_bytes: 256
import java.util.*;

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

    int N = sc.nextInt() - 1;
    int K = sc.nextInt() - 1;
    int ans = 0;

    for (int i=0; i < N; i++) {
      int num = sc.nextInt();
    }

    while (N > 0) {
      N = N - K;
      ans++;
    }

    System.out.println(ans);

  }
}


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

template<class T> inline vector<pair<T, T> > primeFactorize(T n) {
    vector<pair<T, T> > res;
    for (T a = 2; a * a <= n; a++) {
        if (n % a != 0) continue ;
        T ex = 0;
        while (n % a == 0) {
            ++ex;
            n /= a;
        }
        res.push_back({a, ex});
    }
    if (n != 1) res.push_back({n, 1});
    return res;
}

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

    ll n;
    cin >> n;

    auto pf = primeFactorize(n);

    int count = 0;
    for (auto i : pf) {
        ll p = i.second;
        ll b = 1;
        while (b <= p) {
            p -= b;
            b++;
            count++;
        }
    }
    cout << count << '\n';
    return 0;
}


Measured memory_bytes: 3652
from collections import deque

s = deque(input().rstrip())
q = int(input())

reverse = False
for i in range(q):
    query = input()
    if int(query[0]) == 1:
        reverse = not reverse
    else:
        _, f, c = query.split()
        if int(f) == 1:
            if reverse:
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if reverse:
                s.appendleft(c)
            else:
                s.append(c)
if reverse:
    s.reverse()

print(''.join(s))


Measured memory_bytes: 8564
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
        long[] a = new long[N];
        for(int i=0; i<N; i++) {
            a[i] = Long.parseLong(sc.next());
        }
        
        Arrays.sort(a);
        long max = a[0];
        long min = a[0];
        long ans = 1000000000;
        for(int i=0; i<N-K+1; i++) {
            min = a[i];
            max = a[i+K-1];
            if(ans > max-min) ans = max-min;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 49604
#include<cstdio>
#include<vector>
using namespace std;
vector<int> e[60];
int n,m,dfn[60],low[60],tot,u,v,sta[60],cnt,co[60],cntot;
void dfs(int x,int las)
{
	dfn[x]=low[x]=++tot;
	sta[++cnt]=x;
	for(int i=0;i<e[x].size();++i)
	{
		int y=e[x][i];
		if(!dfn[y])
		{
			dfs(y,x);
			low[x]=min(low[x],low[y]);
		}
		else if(!co[y]&&y^las)	low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x])
	{
		co[x]=++cntot;
		while(sta[cnt]^x)	co[sta[cnt--]]=cntot;
		--cnt;
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d %d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;++i)
	{
		if(!dfn[i])	dfs(i,i);
	}
	printf("%d\n",cntot-1);
	return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let h: usize = input();
    let w: usize = input();
    let d: usize = input();
    let a: Vec<Vec<usize>> = (0..h).map(|_| (0..w).map(|_| input()).collect()).collect();
    let q: usize = input();
    let lr: Vec<(usize, usize)> = (0..q)
        .map(|_| {
            let l = input();
            let r = input();
            (l, r)
        })
        .collect();

    let mut m = std::collections::HashMap::new();
    for i in 0..h {
        for j in 0..w {
            m.insert(a[i][j], (i, j));
        }
    }

    let mut s = vec![0; h * w + 1];
    for i in d + 1..h * w + 1 {
        let p = m.get(&i).unwrap();
        let q = m.get(&(i - d)).unwrap();
        s[i] = s[i - d] + (p.0 as i64 - q.0 as i64).abs() + (p.1 as i64 - q.1 as i64).abs();
    }

    for (l, r) in lr {
        println!("{}", s[r] - s[l]);
    }
}


Measured memory_bytes: 14588
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

p,q,r = get_nums_l()

print(p+q+r-max(p,q,r))

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

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	if(a!=c){
		cout << 1 << endl;
	}else{
		cout << 0 << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int a;
string s;
cin >> a >> s;
if(a>=3200) {
  cout << s << endl;
} else {
  cout << "red" << endl;
}
return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

// -----------------------------------------------
// Framework <https://github.com/vain0x/procon>
// -----------------------------------------------

//
// Macro debug!
//

#[cfg(debug_assertions)]
include!{"./procon/debug.rs"}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($($arg:expr),*) => {};
}

//
// Macro input!
//

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//
// IteratorExt
//

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}





fn main() {
    input! {
        a: usize,
        b: usize,
    }
    let ans = match a {
        x if x <= 5 => 0,
        x if 6 <= x && x <= 12 => b/2,
        _ => b,
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
n=int(input())

p1=list(map(int, input().split()))
p2=list(map(int, input().split()))

mhd=0
ecd=0
trd=0
chd=0
for i  in range(n):
    mhd=mhd+abs(p1[i]-p2[i])
    ecd= ecd+abs(p1[i]-p2[i])**2
    trd=trd+abs(p1[i]-p2[i])**3
    chd=max(chd, abs(p1[i]-p2[i]))

print(mhd)
print(ecd**0.5)
print(trd**(1/3))
print(chd)
    
    



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

using namespace std;

int dist(int x1, int y1, int x2, int y2){
  return abs(x1-x2) + abs(y1-y2);
}

int main(){
  int n, a, b, c, d, ans = INT_MAX;

  cin >> n >> a >> b >> c >> d;
  a--, b--, c--, d--;
  for(int i = 1 ; i < n ; i++){
    ans = min(ans, dist(a%i,a/i,b%i,b/i)+dist(c%i,c/i,d%i,d/i));
  }
  cout << ans << endl;

  return 0;
}

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

int main() {
    int N,Y;
    cin >> N>>Y;
    for (int i = 0; i < 2001; i++)
    {
        for (int j = 0; j < 2001; j++)
        {
            if (9000*i+4000*j+1000*N==Y)
            {   
                if (N-i-j >=0)
                {
                    cout << i <<" "<< j <<" "<< N-i-j<<endl;
                    return 0;
                }
                
            
            }
            
        }
        
    }
    cout << -1 <<" "<< -1 << " " <<-1 <<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(){
    int n , m , k ;
    bool f = false;
    
    cin >> n >> m >> k;
    
    for(int i=0 ;i<=n ;i++ ){
        for(int j=0 ;j<=m ;j++ ){
            if( i*m + j*n - 2 *(i*j) == k){
                f = true;
            }
        }
    }
    
    if(f){
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return(0);
}

Measured memory_bytes: 256
s = input()

for i in range(1,len(s)+1,2):
    if s[i-1] == 'L':
        print('No')
        break
else:
    for i in range(2,len(s)+1,2):
        if s[i-1] == 'R':
            print('No')
            break
    else:
        print('Yes')

Measured memory_bytes: 9048
#include <unordered_set>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <functional>
#include <set>

int N;
long long Y;

void run() {
	std::cin >> N >> Y;
	Y /= 1000;
	int x = 0;
	int y = 0;
	int z = 0;
	while (Y > 0) {
		if (Y > 5 * N) {
			Y -= 10;
			++x;
		}
		else if (Y == 5 * N) {
			Y -= 5;
			++y;
		}
		else {
			Y -= 1;
			++z;
		}
		--N;
	}
	if (!(Y == 0 && N == 0)) {
		x = -1;
		y = -1;
		z = -1;
	}
	printf("%d %d %d", x, y, z);
}
int main() {
	run();
	return 0;
}


Measured memory_bytes: 888
# C Many Formulas
s = input()
n = len(s)

def dfs(string, depth):
    if depth == n-1:
        return eval(string)
    return dfs(string+s[depth+1], depth+1) + dfs(string+"+"+s[depth+1], depth+1)

print(dfs(s[0], 0))

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

int main()
{
  int l,r;
  cin>>l>>r;
  int ml=l%2019,mr=r%2019;
  if(ml>mr) cout<<"0"<<endl;
  else
  {
    int temp=mr-ml+1;
    int temp1=r-l+1;
    if(temp!=temp1) cout<<"0"<<endl;
    else
    {
      int ans=INT_MAX;
      for(int i=ml;i<=mr;i++) for(int j=i+1;j<=mr;j++) ans=min(ans,(i*j)%2019);
      cout<<ans<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin>>N;
    vector<tuple<string,int,int>> t(N);
    for (int i=0;i<N;++i) {
        cin>>get<0>(t[i])>>get<1>(t[i]);
        get<2>(t[i])=i+1;
    }
    sort(t.begin(), t.end(), [](auto a, auto b){
        if(get<0>(a)==get<0>(b))return get<1>(a)>get<1>(b);
        else return get<0>(a)<get<0>(b);
    });
    for (auto x:t)cout<<get<2>(x)<<endl;
}

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

int main() {
    int a,b,c; cin >> a >> b >> c;
    int count=0;
    count+=c/(a*7+b)*7;
    c%=(a*7+b);
    if(c/a>=7){
        count += 7;
    }
    else if(c%a!=0){
        count += (c/a+1);
    }
    else count += (c/a);
    cout << count << endl;    
    

    return 0;
}


Measured memory_bytes: 3116
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

score = B[A[0] -  1]
for i in range(1, n):
  score += B[A[i] - 1] + (C[A[i - 1] - 1] if A[i] - A[i - 1] == 1 else 0)

print(score)

Measured memory_bytes: 3064
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	bool pos = false;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (N == i * j) pos = true;
		}
	}

	if (pos) cout << "Yes" << "\n";
	else cout << "No" << "\n";

	return 0;
}

Measured memory_bytes: 256
a = [list(map(int,input().split())) for i in range(3)]
n = int(input())
b = [int(input()) for i in range(n)]
 
for i in b:
  for j in range(3):
    for k in range(3):
      if i == a[j][k]:
        a[j][k] = 0
        
for i in range(3):
  if sum(a[i]) == 0:
    print('Yes')
    exit()
    
if a[0][0]+a[1][0]+a[2][0] == 0 or a[0][1]+a[1][1]+a[2][1] == 0 or a[0][2]+a[1][2]+a[2][2] == 0:
  print('Yes')
elif a[0][0]+a[1][1]+a[2][2] == 0 or a[0][2]+a[1][1]+a[2][0] == 0:
  print('Yes')
else:
  print('No')
    

Measured memory_bytes: 3064
import sys
from sys import stdin
sys.setrecursionlimit(10**7)

def dfs(v, p):
    for next_v in graph[v]:
        if next_v == p:
            continue
        count[next_v] += count[v]
        dfs(next_v, v)

if __name__ == "__main__":
    N, Q = [int(_) for _ in stdin.readline().rstrip().split()]
    graph = [[] for i in range(N+1)]
    count = [0]*(N+1)
    for i in range(N-1):
        a, b = [int(_) for _ in stdin.readline().rstrip().split()]
        graph[a].append(b)
        graph[b].append(a)
    for i in range(Q):
        p, x = [int(_) for _ in stdin.readline().rstrip().split()]
        count[p] += x
    dfs(1, 0)
    print(*count[1:])

Measured memory_bytes: 230932
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int K = sc.nextInt();
    sc.close();

    boolean loop = true;
    int ans = 1;
    while (loop) {
      if ((N / K) != 0) {
        N = (N / K);
        ans++;
        continue;
      }
      loop = false;
    }
    System.out.printf("%d", ans) ;
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	

ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;
        x = (x*x) % p; 
    } 
    return res; 
} 
  
ll modInverse(ll n, ll p) 
{ 
    return power(n, p-2, p); 
} 
  
ll nCr(ll n, ll r, ll p) 
{ 
   if (r==0) 
      return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 
    ll fac[n+1]; 
    fac[0] = 1; 
    for (ll i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 

ll count(ll n, ll r, ll a, ll p) 
{ 
    ll fac[n+1]; 
    fac[0] = 1; 
    for (ll i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[a], p) % p) % p; 
} 

ll m = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,k;
	cin >> n >> k;
	for (ll z=1;z<=k;z++){
		if (z > n-k+1) cout << 0 << endl;
		else cout << (nCr(n-k+1,z,m)*count(k-1,k-z,z-1,m))%m << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>

unsigned int elevations[100002];
bool reached[100002] = {false};

int main() {
    int n, m, a, b;
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        std::cin >> elevations[i + 1];
    }
    int good = n;
    for (int i = 0; i < m; ++i) {
        std::cin >> a >> b;
        if (elevations[a] > elevations[b]) {
            if (!reached[b]) {
                good -= 1;
                reached[b] = true;
            }
        } else if (elevations[a] == elevations[b]) {
            if (!reached[a]) {
                good -= 1;
                reached[a] = true;
            }
            if (!reached[b]) {
                good -= 1;
                reached[b] = true;
            }
        } else if (!reached[a]){
            good -=1;
            reached[a] = true;
        }
    }
    std::cout << good;
    return 0;
}

Measured memory_bytes: 4080
#include <stdio.h>
#include <string.h>

void foo(int num){
	int i,tmp,cnt,map[10];

	memset(map,0,sizeof(map));

	tmp = 0;
	cnt = 1;
	while(num != 0){
		if(num%2){
			map[tmp] = cnt;
			tmp++;
		}
		num /= 2;
		cnt *= 2;
	}

	for(i = 0;i < tmp;i++){
		printf("%d%c",map[i],i == tmp-1 ? '\n' : ' ');
	}
}

int main(){
	int n;

	while(scanf("%d",&n) != EOF){
		foo(n);
	}

	return 0;
}

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

#define ll long long
typedef pair <int, int> ii;
typedef pair <ll, int> lli;
#define ar array
#define pb push_back
#define fi first
#define se second
#define sz size
#define mp make_pair
#define nl '\n'
#define all(x) (x).begin(), (x).end()
#define int_max numeric_limits<int>::max()
#define int_min numeric_limits<int>::min()
#define ll_max numeric_limits<ll>::max()
#define ll_min numeric_limits<ll>::min()

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define im(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

// custom sort example
//sort(all(a), [ ]( const auto& c, const auto& d) {
	//if (c.fi.se != d.fi.se) {
		//return c.fi.se < d.fi.se; // lower first
	//}
	//if (c.fi.fi != d.fi.fi) {
		//return c.fi.fi > d.fi.fi; // higher first
	//}
	//return c.se > d.se; // higher first
//});

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <class T>
auto lbf(const std::set<std::pair<T, T>>& s, T first)
{
   static constexpr T min = std::numeric_limits<T>::min();

   return s.lower_bound({first, min});
}

int MOD = 1000000007;

ll pw(ll n, ll k) {
	ll r = 1;
	for(; k; k >>= 1) {
		if(k&1) r = r * n % MOD;
		n = n * n % MOD;
	}
	return r;
}
ll inv(ll n) { return pw(n, MOD-2); }

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	int n, res = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int b;
		cin >> b;
		if (b % 2 == 1 && i % 2 == 1) {
			res++;
		}
	}
	cout << res << nl;
}


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

UL N;
UL A[100000];

UL partition(UL* A,UL p,UL r){
 UL x = A[r];
 UL i = p-1;
 for(UL j=p; j<r; j++)
  if(A[j] <= x){ i++; swap(A[i],A[j]); }
 swap(A[i+1],A[r]);
 return i+1;
}

int main() {
 scanf("%u",&N);
 rep(i,N) scanf("%u",&A[i]);
 UL p=partition(A,0,N-1);
 rep(i,N){
  if(i) printf(" ");
  printf((p==i) ? "[%u]" : "%u", A[i]);
 } printf("\n");
 return 0;
}



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

string S; long long dp[200009][3][4], power[200009], mod = 998244353;

void init() {
	dp[0][0][3] = 1;
	for (int i = 0; i < 200000; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 4; k++) {
				for (int l = 0; l < 3; l++) {
					if (k != l) {
						dp[i + 1][(j + l) % 3][l] += dp[i][j][k];
						dp[i + 1][(j + l) % 3][l] %= mod;
					}
				}
			}
		}
	}
	power[0] = 1; for (int i = 1; i <= 200000; i++) power[i] = (power[i - 1] * 3LL) % mod;
}

int main() {
	cin >> S; init();
	if (S == "abc" || S == "acb" || S == "bac" || S == "bca" || S == "cab" || S == "cba") {
		cout << "3" << endl;
		return 0;
	}
	bool flag1 = false, flag2 = false; int cnt = 0;
	for (int i = 0; i < S.size(); i++) {
		cnt += (S[i] - 'a');
		if (i < S.size() - 1) {
			if (S[i] == S[i + 1]) flag1 = true;
			if (S[i] != S[i + 1]) flag2 = true;
		}
	}
	long long sum = dp[S.size()][cnt % 3][0] + dp[S.size()][cnt % 3][1] + dp[S.size()][cnt % 3][2]; sum %= mod;
	if (flag2 == false) cout << "1" << endl;
	else if (flag1 == false) {
		cout << (power[S.size() - 1] - sum + mod + 1) % mod << endl;
	}
	else {
		cout << (power[S.size() - 1] - sum + mod) % mod << endl;
	}
	return 0;
}

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

int main(){
	int n; cin >> n;
	vector< int > v(n);
	for(int i = 0; i < n; ++i){
		cin >> v[i];
	}
  int larr[n + 1];
  int rarr[n + 1];
  for(int i =  0; i < n; ++i){
  	larr[i] = i - v[i];
  	rarr[i] = i + v[i]; 
  }
  ll ans = 0;
  sort(rarr, rarr + n);
  for(int i = 0; i < n; ++i){
  	auto z = lower_bound(rarr,rarr + n,larr[i]);
  	auto y = upper_bound(rarr,rarr + n,larr[i]);
  	if(y - z > 0 && *z == larr[i]){
  		ans += (ll)(y - z);
  		//cout << i + 1 << '\n';
  	}
  }
  //cout << "==========" << '\n';
  cout << ans << '\n';
}

Measured memory_bytes: 5632
import java.util.Scanner;

public class Main{

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

		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int h = Integer.parseInt(sc.next());
		int w = Integer.parseInt(sc.next());
		
		double at = (double) (Math.PI * h) /6;
		at -= (double)(Math.PI * w * 11 )/360;
		
		
		double ans = a*a + b*b - 2 * a *b * Math.cos(at);
		ans = Math.sqrt(ans);
		System.out.println(ans);
	
	}

}


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

using namespace std;

const int A = 55555;

int main() {
    ios::sync_with_stdio(false);

    vector<int> p;
    for (int i = 2; i < 55555; i++) {
        bool f = true;
        for (int j = 0; j < p.size() && p[j] * p[j] <= i; j++) {
            if (i % p[j] == 0) {
                f = false;
                break;
            }
        }
        if (f) {
            p.push_back(i);
        }
    }

    int n;
    cin >> n;

    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < p.size() && p[j] % 5 != 1) {
            j++;
        }
        cout << p[j] << (i == n - 1 ? '\n' : ' ');
        j++;
    }

    return 0;
}


Measured memory_bytes: 384
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>


#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...)
#define showlr(n,l,r)
#endif

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;
/*------------end of definitions------------*/

char C;
map<char,char> mp;

signed main(){

    mp['A']='T';
    mp['T']='A';
    mp['G']='C';
    mp['C']='G';

    in(C);
    out(mp[C]);
    
    return 0;
}


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

long long choose2(long long n){
    return n*(n-1)/2;
}

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]--;
    }
    vector<int> cnt(n);
    for(int i=0;i<n;i++){
        cnt[a[i]]++;
    }
    long long sum=0;
    for(int i=0;i<n;i++){
        sum+=choose2(cnt[i]);
    }
    for(int i=0;i<n;i++){
        long long ans=sum;
        ans-=choose2(cnt[a[i]]);
        ans+=choose2(cnt[a[i]]-1);
        cout<<ans<<endl;
    }

    return 0;
}

Measured memory_bytes: 4096
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <deque>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main() {

	int n, d;
	cin >> n >> d;

	if (n % (d * 2 + 1) == 0)
		cout << n / (d * 2 + 1) << endl;
	else
		cout << n / (d * 2 + 1) + 1 << endl;

	return 0;
}

Measured memory_bytes: 256
r, c = map(int, input().split())

LIST = []
for i in range(r):
    List = [int(x) for x in input().split()]
    LIST.append(List)

for i in range(r):
    Lsum = sum(LIST[i])
    LIST[i].append(Lsum)

Listbo = []
for i in range(c+1):
    SUM = 0
    for j in range(r):
        L = LIST[j]
        SUM += L[i]
    Listbo.append(SUM)
LIST.append(Listbo)

for i in range(r+1):
    LI = LIST[i]
    for j in range(c+1):
        if j==c:
            print(LI[j])
        else:
            print(LI[j],end=' ')


Measured memory_bytes: 6248
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <cmath>
using namespace std;

#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647

int main() {
	int N;
	cin >> N;
	vector<int> vec(N);
	int sum = 0;
	bool flags = false;
	for (int i = 0; i < N; ++i) {
		cin >> vec[i];
		sum += vec[i];
		if (vec[i] % 10 != 0) {
			flags = true;
		}
	}


	if (flags == false) {
		cout << 0 << endl;
	}
	else {
		if (sum % 10 == 0) {
			sort(vec.begin(), vec.end());
			for (size_t t = 0; t < vec.size(); ++t) {
				if (vec[t] % 10 != 0) {
					cout << sum - vec[t] << endl;
					break;
				}
			}
		}
		else {
			cout << sum << endl;
		}
	}

	return 0;
}

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

int main()
{
  int time;
  int syain[3][2];
  int h,m,s;
  int ans[3];

  for(int i = 0;i < 3;i++){
    for(int j = 0;j < 2;j++){
      cin >> h >> m >> s;
      syain[i][j] = h*3600+m*60+s;
    }
    ans[i] = syain[i][1]-syain[i][0];
    
    cout << ans[i]/3600 << " " << (ans[i]%3600)/60 << " " << (ans[i]%3600)%60 << endl;
  }
}

Measured memory_bytes: 1160