akhauriyash/Code-Regression huggingface dataset:
import collections
import math

N, M = map(int, input().split())


def prime_factorize(n: int) -> list:
    primes = []
    while n % 2 == 0:
        primes.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes


def comb(n: int, r: int) -> int:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if M == 1:
    print(1)
else:
    primes = collections.Counter(prime_factorize(M))
    res = 1
    for freq in primes.values():
        res *= comb(N + freq - 1, freq)
        res %= (10 ** 9 + 7)
    print(res)


Measured memory_bytes: 134032
def main(argv)
  n = gets.chomp.to_i
  b = gets.chomp.split(' ').map(&:to_i)
  
  a = [0] * n
  a[0] = b[0]
  (n - 1).times do |i|
    a[i] = [a[i], b[i]].min
    a[i + 1] = b[i]
  end
  puts a.reduce(:+).to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

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

bool check(string s){
  int n = s.length();
  if (n%2==1){
    return false;
  }
  else {
    return (s.substr(0,n/2-1)==s.substr(n/2));
  }
}

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

  int a[n];
  int b[n];

  int cnt1=0, cnt2=0, cnt4=0;
  for (int i=0; i<n; i++){
    cin >> a[i];
    if (a[i]%4==0){
      b[i] = 4;
      cnt4++;
    }
    else if (a[i]%2==0){
      b[i] = 2;
      cnt2++;
    }
    else {
      b[i] = 1;
      cnt1++;
    }
  }

  if (cnt1<=cnt4+1 && cnt2==0){
    cout << "Yes" << endl;
    return 0;
  }
  else if (cnt1<=cnt4){
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" <<endl;
  return 0;
}


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

using namespace std;

typedef long long int ll;
#define pii pair<ll, ll>
#define F first
#define S second

const int N = 1e6;
const ll INF = 1e18;

// (m, c) -> y = mx+c
vector<pii> tree(4*N, {0, INF});

ll eval(pii& line, ll x){
	return (line.F*x + line.S);
}

void insert(ll l, ll r, int i, pii line){
	if(l == r){
		if(eval(tree[i], l) > eval(line, l)) tree[i] = line;
		return;
	}
	ll m = (l+r) >> 1;
	// check which one is dominating - 1 if 'line' is dominating
	// The line with lower value at 'm' is dominating (try to sketch a few lines)
	int dominating = (eval(tree[i], m) > eval(line, m))? 1 : 0;
	// the side at which the line 'dominating' is dominating
	int less_at_l =  (eval(tree[i], l) > eval(line, l))? 1 : 0;

	pii insert_below = (dominating == 1)? tree[i] : line;
	tree[i] = (dominating == 1)? line : tree[i];

	if(less_at_l == dominating){
		// covers the entire left side. So, check in right side
		insert(m+1, r, i*2+2, insert_below);
	}
	else{
		// covers the entire right side. So, check in left side
		insert(l, m, i*2+1, insert_below);
	}
}

ll query(ll l, ll r, int i, int x){
	if(l == r) return eval(tree[i], x);
	ll m = (l+r) >> 1;
	if(m >= x) return min(eval(tree[i], x), query(l, m, i*2+1, x));
	return min(eval(tree[i], x), query(m+1, r, i*2+2, x));
}

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

	ll n, c;
	cin >> n >> c;
	vector<ll> h(n);
	for(int j = 0; j < n; j++) cin >> h[j];
	for(int j = 0; j < n; j++){
		ll cur = h[j]*h[j] + c + query(0, N, 0, h[j]);
		if(j == 0) cur = 0;

		ll slope = -h[j]*2;
		ll intercept = h[j]*h[j] + cur;
		insert(0, N, 0, {slope, intercept});

		if(j == n-1){
			cout << cur << '\n';
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 64384
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

#define _CRT_SECURE_NO_WARNINGS
#define TLong long long
#define TBMod 1000000007

int main(int argc, char const *argv[])
{
	int x;
	int i,max = 1,v;
	scanf("%d",&x);

	for (int i = 2; i <= x; ++i)
	{
		v = i * i;
		while(v <= x){
			if(max < v)	max = v;
			v *= i;
		}
	}
	printf("%d\n", max);
	return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;

int a[3][105];

int main()
{
	int n,ans,m;
	while(~scanf("%d",&n))
	{
		m = 0;
		for(int i = 1;i <= n;i++) scanf("%d",&a[1][i]);
		for(int i = 1;i <= n;i++) scanf("%d",&a[2][i]);
		for(int i = 1;i <= n;i++)
		{
			ans = 0;
			for(int j = 1;j <= i;j++) ans += a[1][j];
			for(int j = i;j <= n;j++) ans += a[2][j];
			m = max(m,ans);
		}
		printf("%d\n",m);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n; std::cin >> n;
    if (n % 10 == 3) std::cout << "bon";
    else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) std::cout << "pon";
    else std::cout << "hon";
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include <sstream> //string stream
#include<string>
#include<iostream>
#include<utility> //pair
#include <vector>
#include <algorithm>    // swap,sort,binary_search
#include <functional>   //greater
#include <map> //map
#include<set> //set
#include<queue>
#include<list> //list
#include<cmath>
#include<numeric>
#include<cassert>
#include<bitset>
#include <iomanip> //cout<<setprecision
using namespace std;
typedef long long ll;
#define rep(i,s,t) for(int i = s; i<t;i++)
const ll wari = 1000000007;

//omajinai yukue humei

int main(){
    int n,l; cin>>n>>l;
    string *s = new string[n];
    for(int i = 0 ; i<n;i++) cin>>s[i];
    sort(s,s+n);
    for(int i = 0 ; i<n;i++) cout<<s[i];
    cout<<endl;
}


Measured memory_bytes: 256
// 2020 03/28 ABC 160 B
#include <iostream>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)

int main () {
    int x;
    cin >> x;
    int ans = 0;

    ans = x / 500 * 1000;
    ans += (x % 500) / 5 * 5;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	bool ch=true;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		if(now%2==0){
			if(now%3!=0&&now%5!=0){
				ch=false;
			}
		}
	}
	if(ch){
		cout << "APPROVED";
	}
	else{
		cout << "DENIED";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3652
N=int(input())
D,X=map(int,input().split())
a = [int(input()) for i in range(N)]
ans=0
for i in range(N):
    n=0
    while(1):
        if a[i]*n+1>D:
            break
        else:
            ans+=1
            n+=1
print(ans+X)

Measured memory_bytes: 3060
//write：Sakura
//id：
//problem：
//note：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

typedef long long ll;

int n;
int a[105];
int Max=-(1<<30);
int Min=1<<30;

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		Max=max(Max,a[i]);
		Min=min(Min,a[i]);
	} 
	printf("%d\n",Max-Min);
	return 0;
}


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

using usize = ::std::size_t;
using u64 = ::std::uint_least64_t;

#define v(n) n*(n+1)*(n+2)/6

int main(int argc, char *argv[])
{
    // input from txt （提出時にこの箇所は削除すること）
    //ifstream in("in.txt");
    //cin.rdbuf(in.rdbuf());
 
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    static constexpr u64 Inf = ::std::numeric_limits<u64>::max() / 2;
    
    vector<u64> dp(1000001, Inf);
    vector<u64> dp2(1000001, Inf);
    dp[0] = 0;
    dp2[0] = 0;
    //int ti = clock();
    
    for (int i = 1; i <= 600; i++) {
        for (int j = v(i); j <= 1000000; j++) {
            for (int k = 1; j - k*v(i) >= 0 && k <= 5; k++) {
                dp[j] = min(dp[j], dp[j - k * v(i)] + k);
            }
        }
    }
    
    for (int i = 1; i <= 600; i += 4) {
        for (int j = v(i); j <= 1000000; j++) {
            for (int k = 1; j - k*v(i) >= 0; k++) {
                if (dp2[j] <= dp2[j - k * v(i)] + k) {
                    break;
                }
                dp2[j] = min(dp2[j], dp2[j - k * v(i)] + k);
            }
        }
    }
    
    //cout << (1.0 * (clock() - ti) / CLOCKS_PER_SEC) << endl;
    
    u64 N;
    while (cin >> N, N) {
        cout << dp[N]  << " " << dp2[N] << endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 18280
//プロ技のテストって裏あったの！？
#include<bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,n) for(int i=1; i<(n); i++)
#define pii pair<int,int>
#define gsort(x,n) sort((x),(x)+(n),greater<int>())
#define all(x) (x).begin(), (x).end()
#define int long long
#define abs(a) llabs(a)
#define re(s) reverse((s).begin(),(s).end())
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const long long mod = 1000000007;
using namespace std;

signed main(){

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

    string s,v;
    cin>>s>>v;
    int cnt = (s.size()+v.size());
    
    int a=0,b=0;
    
    rep(i,cnt){
        if(i%2==0){
            cout<<s[a];
            a++;
        }
        else{
            cout<<v[b];
            b++;
        }
    }
    cout<<'\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
#define ll long long

int main() {
	int m, minn, maxn, hoge, ans, maxhoge;
	while (1) {
		cin >> m >> minn >> maxn;
		if (m == 0 && minn == 0 && maxn == 0)break;
		vector<int> p(m);
		for (int i = 0; i < m; i++) {
			cin >> p[i];
		}
		sort(p.begin(), p.end());
		reverse(p.begin(), p.end());
		ans = minn - 1;
		for (int i = minn - 1; i < maxn; i++) {
			if (i == minn - 1) maxhoge = p[i] - p[i + 1];
			hoge = p[i] - p[i + 1];
			if (ans < i && hoge >= maxhoge) {
				ans = i;
				maxhoge = hoge;
			}
		}
		cout << ++ans << endl;

	}
	return 0;
}


Measured memory_bytes: 3160
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long L = long.Parse(str[0]);
		int N = int.Parse(str[1]);
		long[]A = new long[N];
		for(var i=0;i<N;i++){
			string str2 = Console.ReadLine();
			A[i] = long.Parse(str2);
		}
		long[]B = new long[N+1];
		long sum = 0;
		for(var i=0;i<N;i++){
			sum += A[i];
			B[i+1] = sum;
		}
		long ans = A[0];
		int na = 0;
		int na2 = N;
		while(true){
			na2--;
			if(na==na2){
				break;
			}
			ans += A[na]+(L-A[na2]);
			na++;
			if(na==na2){
				break;
			}
			ans += A[na]+(L-A[na2]);
		}
		long ansmax = ans;
		for(var i=1;i<N;i++){
			ans += A[(i+N-1)/2]-A[i-1]-A[i-1];
			ans -= L-A[(i+N)/2];
			ansmax = Math.Max(ans,ansmax);
		}
		ans = L-A[N-1];
		na = -1;
		na2 = N-1;
		while(true){
			na++;
			if(na==na2){
				break;
			}
			ans += A[na]+(L-A[na2]);
			na2--;
			if(na==na2){
				break;
			}
			ans += A[na]+(L-A[na2]);
		}
		ansmax = Math.Max(ans,ansmax);
		for(var i=N-2;i>=0;i--){
			ans += A[i+1]-A[(i+0+1)/2]-(L-A[i+1]);
			ans -= A[(i+0)/2];
			ansmax = Math.Max(ans,ansmax);
		}
		Console.WriteLine(ansmax);
	}
}

Measured memory_bytes: 18140
N, M = map(int, input().split())
h_list = list(map(int, input().split()))
good_obs = [1] * N

for i in range(M):
    a, b = map(int, input().split())
    if h_list[a-1] <= h_list[b-1]:
        good_obs[a-1] = 0
    if h_list[a-1] >= h_list[b-1]:
        good_obs[b-1] = 0
print(sum(good_obs))

Measured memory_bytes: 19996
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

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; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

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

template<typename T> class BinaryIndexedTree {
  private:
    int S;
    std::vector<T> v;
  public:
    BinaryIndexedTree<T> (int _S) {
      S = _S;
      v.resize(S+1);
    }
    void update(int i, T k) {
      for(i++; i <= S; i += i&-i) v[i] = v[i] + k;
    }
    T read(int i) {
      T sum = 0;
      for(i++; i; i -= i&-i)  sum = sum + v[i];
      return sum;
    }
    T read(int l, int r) {
      return read(r) - read(l-1);
    }
};


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N; std::cin >> N;
  std::string S; std::cin >> S;

  std::vector<BinaryIndexedTree<ll>> L(26, BinaryIndexedTree<ll>(N+1));
  rep(i, N) L[S[i]-'a'].update(i, 1);

  int Q ; std::cin >> Q;
  std::vector<int> ans;
  rep(i, Q) {
    int f;
    std::cin >> f;
    if ( f == 1 ) {
      int t; char c;
      std::cin >> t >> c;
      t--;
      int bef = S[t] - 'a';
      L[bef].update(t, -1);
      L[c-'a'].update(t, +1);
      S[t] = c;
    }
    else {
      int l, r; std::cin >> l >> r;
      l--, r--;
      int cnt = 0;
      rep(n, 26) {
        if ( L[n].read(l, r) != 0 ) cnt++;
      }
      ans.push_back(cnt);
    }
  }
  for(auto a : ans) std::cout << a << std::endl;
  return 0;
}


Measured memory_bytes: 106396
"""
ワーシャルフロイド法:O(n^3)
n:頂点数
"""
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

#######################
inf = float('inf')
n, w = [int(x) for x in input().split()] # n:頂点数, w:辺数
d = [[inf]*n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
for _ in range(w):
    x, y, z = [int(x) for x in input().split()] # 頂点xと頂点yの間の距離がz
    d[x][y] = z
    # d[y][x] = z # 有向グラフならこの行はコメントアウト
d = warshall_floyd(d)
for i in range(n):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        exit()
for i in d:
    print(" ".join([str(x) for x in i]).replace("inf", "INF"))




Measured memory_bytes: 6004
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V){os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P){return os << "(" << P.first << "," << P.second << ")";}
#ifndef ONLINE_JUDGE
#define TRACE
#endif

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1){ cout << name << " : " << arg1 << endl; }
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...) 1
#endif
#define mp make_pair
#define pb push_back
#define endl '\n'
#define F first
#define S second
#define I insert
typedef long double ld;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
const int N = 1e2+5;
const int M = 1e5 + 2;
ll w[N],v[N],dp[N][M];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout<<setprecision(25);
    ll n,W; cin>>n>>W;
    for(int i=1;i<=n;i++){
    	cin>>w[i]>>v[i];	
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=W;j++){
    		dp[i][j] = dp[i-1][j];
    		if(j-w[i] >= 0) dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
    	}
    }
    ll ans = 0;
    for(int i=1;i<=W;i++) ans = max(ans, dp[n][i]);
    cout<<ans;
}

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

ll gcd(ll a, ll b){
	return b ? gcd(b, a%b) : a;
}

ll lcm(ll c, ll d){
	return c*d/gcd(c, d);
}

ll f(ll x, ll c, ll d){
	ll ans = x;
	ans -= x/c;
	ans -= x/d;
	ans += x/lcm(c, d);

	return ans;
}

int main(){
	ll a, b, c, d;
	cin >> a >> b >> c >> d;

	ll ans = f(b, c, d) - f(a-1, c, d);
	
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  double x1,y1,x2,y2,x3,y3,xp,yp;
  double a,b,c;
  
  while(scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp)!=EOF){
  
    a = (x1-xp)*(y2-yp)-(x2-xp)*(y1-yp);
    b = (x2-xp)*(y3-yp)-(x3-xp)*(y2-yp);
    c = (x3-xp)*(y1-yp)-(x1-xp)*(y3-yp);
  
  
    if( (a>0&&b>0&&c>0) || (a<0&&b<0&&c<0) ){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
  return 0;
  
}

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

int main(){
	int N,W;
	//vector<vector<int>/*??????*/>??¨???????????¨>>????§????
	vector<vector<int> > item;
	cin>>N>>W;
	item.resize(N+1);
	for(int i=0;i<=W;i++){
		item[0].push_back(0);
	}
	for(int i=1;i<=N;i++){
		int v,w;
		cin>>v>>w;
		for(int j=0;j<=W;j++){
			int Max = item[i-1][j];
			if(j>=w){	
				Max = max(item[i][j-w]+v,item[i-1][j]);
			}
			
			item[i].push_back(Max);
		}
	}
	cout<<item[N][W]<<endl;	
	
	
	return 0;
}

Measured memory_bytes: 5492
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int p[N],a[N],b[N];
struct node{int l,r,mid,mn;}s[N<<2];
void build(int di,int l,int r)
{
    s[di].l=l,s[di].r=r,s[di].mid=l+r>>1,s[di].mn=1e9;
    if(l==r)return;
    build(di<<1,l,s[di].mid),build(di<<1|1,s[di].mid+1,r);
}
void ins(int di,int x,int v)
{
    if(s[di].l==s[di].r){s[di].mn=v;return;}
    if(x<=s[di].mid)ins(di<<1,x,v);
    else ins(di<<1|1,x,v);
    s[di].mn=min(s[di<<1].mn,s[di<<1|1].mn);
}
int qry(int di,int l,int r)
{
    if(l<=s[di].l&&s[di].r<=r)return s[di].mn;
    else if(r<=s[di].mid)return qry(di<<1,l,r);
    else if(l>s[di].mid)return qry(di<<1|1,l,r);
    return min(qry(di<<1,l,r),qry(di<<1|1,l,r));
}
struct edge{int to,nxt;}e[N<<1];
int head[N],tot=1;
void adde(int x,int y){e[tot]=(edge){y,head[x]};head[x]=tot++;}
priority_queue<int>q;
int n,rd[N];
void topo()
{
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=e[j].nxt)rd[e[j].to]++;
    for(int i=1;i<=n;i++)if(!rd[i])q.push(i);
    int tt=0;
    while(!q.empty())
    {
        int u=q.top();q.pop(),b[++tt]=u;
        for(int i=head[u];i;i=e[i].nxt)
            if(!(--rd[e[i].to]))q.push(e[i].to);
    }
}
int main()
{
    int k;scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){int x;scanf("%d",&x),a[x]=i;}
    for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
    build(1,1,n);
    for(int i=n;i>=1;i--)
    {
        int x=qry(1,max(1,a[i]-k+1),a[i]);
        if(x>=1&&x<=n)adde(a[i],a[x]);
        x=qry(1,a[i],min(n,a[i]+k-1));
        if(x>=1&&x<=n)adde(a[i],a[x]);
        ins(1,a[i],i);
    }
    topo();
    for(int i=1;i<=n/2;i++)swap(b[i],b[n-i+1]);
    for(int i=1;i<=n;i++)p[b[i]]=i;
    for(int i=1;i<=n;i++)printf("%d\n",p[i]);
}


Measured memory_bytes: 50816
#include <bits/stdc++.h>
#define ll long long

std::map<ll,ll>rec;

ll n,a,b,c,d;

ll f(ll N){
	
	if (N == 0) return 0;
	if (N == 1) return d;
	if(rec.find(N)!=rec.end())return rec[N];
	ll ans = 1e18;
	if (N<=1e18/d) ans = N * d;
	ll l1 = (N/2)*2, r1 = ((N+1)/2)*2;
	ll l2 = (N/3)*3, r2 = ((N+2)/3)*3;
	ll l3 = (N/5)*5, r3 = ((N+4)/5)*5;
	ans = std::min(ans, f(l1/2) + (N-l1) * d + a);
	ans = std::min(ans, f(l2/3) + (N-l2) * d + b);
	ans = std::min(ans, f(l3/5) + (N-l3) * d + c);
	ans = std::min(ans, f(r1/2) + (r1-N) * d + a);
	ans = std::min(ans, f(r2/3) + (r2-N) * d + b);
	ans = std::min(ans, f(r3/5) + (r3-N) * d + c);
	rec[N] = ans;
	return ans;
}

void solve(){
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
	rec.clear();
	printf("%lld\n",f(n));
}

int main(){
	int t;scanf("%d",&t);while(t--)solve();
	return 0;
}




Measured memory_bytes: 4532
n = gets.to_i
ab = n.times.map{gets.split.map(&:to_i)}.sort_by{|i,j|i+j}.reverse
ans = 0
for i in 0..n-1
    if i%2 == 0
        ans += ab[i][0]
    else
        ans -= ab[i][1]
    end
end
puts ans

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9;
const LL LINF = INF * INF;

const int MAX = 1 << 17;
int n;
int h[MAX];
int dp[MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);

	cin >> n;
	FOR(i, 0, n)
		cin >> h[i];
	
	
	FOR(i, 0, n)
		dp[i] = INF;
	
	dp[0] = 0;
	FOR(i, 0, n - 1)
	{
		dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
		if (i + 2 < n)
			dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));	
	}
	
	cout << dp[n - 1] << endl;
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}


Measured memory_bytes: 1024
# AtCoder Regular Contest 097
# C - K-th Substring
# https://atcoder.jp/contests/arc097/tasks/arc097_a
from itertools import zip_longest
from collections import Counter

S = input()
K = int(input())

subs = set()
for i in range(1, 6):
    for j in range(len(S)):
        subs.add(S[j:j+i])

subs = list(subs)
subs.sort()

print(subs[K-1])

Measured memory_bytes: 4848
#include <bits/stdc++.h>
#define SIZE 205
#define MX 62
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll A[SIZE];
char S[SIZE];
ll bit[MX];
void solve()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",&A[i]);
	scanf("%s",&S);
	memset(bit,-1,sizeof(bit));
	for(int i=n-1;i>=0;i--)
	{
		int f=-1;
		for(int j=MX-1;j>=0;j--)
		{
			if(A[i]>>j&1)
			{
				if(bit[j]==-1)
				{
					f=j;
					break;
				}
				A[i]^=bit[j];
			}
		}
		if(S[i]=='1'&&f!=-1)
		{
			puts("1");
			return;
		}
		if(f!=-1) bit[f]=A[i];
	}
	puts("0");
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) solve();
}

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

int main(){
	string s;
	cin >> s;
	for(int i=0; i<3; i++){
		if(s[i]=='1'){
			s[i] = '9';
		}else if(s[i]=='9'){
			s[i] = '1';
		}
	}
	int ans;
	ans = (s[2]-'0') + (s[1]-'0')*10 + (s[0]-'0')*100;
	cout << ans << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, M; scanf("%d %d", &N, &M);
  vector<ll> X(N), Y(N), Z(N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld %lld %lld", &X[i], &Y[i], &Z[i]);
  }
  ll ans = -1;
  vector<int> signs = { 1, -1 };
  for (int i = 0; i < (1 << 3); ++i) {
    bitset<3> bits(i);
    vector<pair<ll, int>> v;
    for (int j = 0; j < N; ++j) {
      ll a = X[j] * signs[bits[0]];
      ll b = Y[j] * signs[bits[1]];
      ll c = Z[j] * signs[bits[2]];
      v.push_back(make_pair(a + b + c, j));
    }
    sort(v.begin(), v.end(), greater<pair<ll, int>>());
    ll sx = 0, sy = 0, sz = 0;
    for (int j = 0; j < M; ++j) {
      int ix = v[j].second;
      sx += X[ix];
      sy += Y[ix];
      sz += Z[ix];
    }
    ll sum = abs(sx) + abs(sy) + abs(sz);
    ans = max(ans, sum);
  }

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


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    ll n;
    cin>>n;
    vector<ll> a(n);
    rep(i,n){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    cout<<abs(a[0]-a[n-1])<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    ll n, A, B, C, D; cin >> n >> A >> B >> C >> D;
    if(A > B) swap(A, B);
    B -= A, A = 0;

    n--;
    bool ok = false;
    rep(i, n + 1){
        ll lb = C * i - D * (n - i);
        ll ub = D * i - C * (n - i);
        
        if(lb <= B and B <= ub){
            ok = true;
            break;
        }
    }

    cout << (ok ? "YES":"NO") << endl;

    return 0;
}


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


int main()
{
	int N = 0;
	char S[10000];

	scanf("%d", &N);

	scanf("%s", S);
	
	for (int i = 0; S[i] != NULL; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (S[i] == 'Z')
				S[i] = 'A';
			else
				S[i] ++;
		}

		printf("%c", S[i]);
	}

	return 0;

}

Measured memory_bytes: 128
import java.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    ArrayList<Integer>[] graph;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int[] pos = new int[n+1];
        for(int i=1;i<=n;i++) {
            a[i]=sc.nextInt();
            pos[a[i]] = i;
        }
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(0); ts.add(n+1);
        long ans = 0;
        for(int i=1;i<=n;i++){
            int lo = ts.lower(pos[i]);
            int hi = ts.higher(pos[i]);
            ans += ((long)(pos[i]-lo))*((long)(hi-pos[i]))*i;
            ts.add(pos[i]);
        }
        System.out.println(ans);
    }
}


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

int main() {
  int A, B;
  char ope;
  cin >> A >> ope >> B;
  
  int result;
  if( ope == '+' ){
    result = A + B;
  }
  else{
    result = A - B;
  }
  cout << result << endl;
}

Measured memory_bytes: 3572
#include <stdio.h>
#include <stdlib.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ll long long
#define INF 100000000
#define FOR(i,a,n) for(i=a;i<n;i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
void fill(int a[],int b,int c){
	for(int i=0;i<b;i++) a[i]=c;
	return;
}
int main(void)
{
	int n,t,i,k;
	int start;
	ll ans=0;
	scanf("%d %d",&n,&t);
	FOR(i,0,n){
		scanf("%d",&k);
		if(i!=0){
			if(start+t<k) ans+=t;
			else ans+=(k-start);
		}
		start=k;
	}
	printf("%lld\n",ans+t);
	return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 1e9, sizeof(mat))
typedef long long ll;

int main()
{
  // N + 1?????????????????????
  int N, M; cin >> N >> M;
  int D[N]; FOR(i,0,N) cin >> D[i];
  int C[M]; FOR(i,0,M) cin >> C[i];
  int dp[M+1][N+1]; FOR(i,0,M+1) FOR(j,0,N+1) dp[i][j] = 1e9;
  dp[0][0] = 0;
  FOR(i,0,M) {
    FOR(j,0,N+1) {
      // ??????
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
      // ??????
      if(j < N) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + C[i] * D[j]);
    }
  }
  int ans = 1e9;
  FOR(i,1,M+1) ans = min(ans, dp[i][N]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6168
#ifdef LOCAL_EXEC
#include "include.h"
#else
#include <bits/stdc++.h>
using namespace std;
#define trace(...)
#endif

using LL = long long;

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

	int n, T; cin >> n >> T;
	vector<pair<int, int>> dishes;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		dishes.emplace_back(a, b);
	}

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

	const int MAXT = 6010;
	vector<int> best(MAXT, 0);
	for (auto& e: dishes) {
		int a, b; tie(a, b) = e;
		vector<int> temp = best;
		for (int t = 0; t < T && t + a < MAXT; t++) {
			temp[t + a] = max(temp[t + a], best[t] + b);
		}
		best = temp;
	}
	int ans = 0;
	for (int x: best) ans = max(ans, x);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 384
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = [0] + A
B = [0] + B
for i in range(N):
    A[i + 1] += A[i]
for i in range(M):
    B[i + 1] += B[i]

res, j = 0, M
for i in range(N + 1):
    if A[i] > K:
        break
    while B[j] > K - A[i]:
        j -= 1
    res = max(res, i + j)
print(res)


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
	typedef pair<ll, ll> P;

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

int main(void)
{
	ll n, m;
	cin >> n >> m;
	vector<ll> as(m);
	vector<ll> bs(m);
	vector<ll> cs(m,0);
	rep(i, m) {
		cin >> as[i] >> bs[i];
		rep(j, bs[i]) {
			ll c;
			cin >> c;
			c--;
			cs[i] |= (1LL << c);
		}
	}
	const ll LARGE = 1e15;
	vector<vector<ll>> dp(m + 1, vector<ll>(1<<n, LARGE));
	dp[0][0] = 0;
	rep(i, m) {
		auto c = cs[i];
		auto a = as[i];
		dp[i + 1] = dp[i];
		for (int j = 0; j < 1 << n; j++) {
			dp[i + 1][j | c] = min(dp[i + 1][j | c], dp[i][j] + a);
		}
	}
	if (dp[m][(1 << n) - 1] == LARGE) {
		cout << -1 << endl;
		return 0;
	}
	cout << dp[m][(1 << n) - 1] << endl;
	return 0;
}

Measured memory_bytes: 32384
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <limits.h>
#include <bitset>
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
using prique = priority_queue<int>;
const int MOD = 1000000007;
const int INF = LLONG_MAX/3;
const int MAX = 510000;

signed main(){
    int n;
    cin>>n;
    int k=(int)sqrt(n*2)+1;
    if(k*(k-1)==n*2){
        cout<<"Yes"<<endl;
        cout<<k<<endl;
        vector<int> ans[k];
        int c=1;
        for(int j=0;j<k;j++){
            for(int s=j+1;s<k;s++){
                ans[j].push_back(c);
                ans[s].push_back(c);
                c++;
            }
        }
        for(int i=0;i<k;i++){
            cout<<k-1<<" ";
            for(int j=0;j<k-1;j++){
                cout<<ans[i][j]<<" ";
            }
            cout<<endl;
        }
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}



Measured memory_bytes: 3200
a,b = map(int, input().split())
n = 0
for i in range(1, 10):
    for j in range(10):
        for k in range(10):
            s = 10000 * i + 1000 * j + 100 * k + 10 * j + i
            if a <= s <= b:
                n += 1
print(n)

Measured memory_bytes: 2940
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    cout << min(n*a, b) << endl;

    return 0;
}



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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  c = 2 * c;
  int ans = 1e9;
  for (int i = 0; i <= max(x, y); ++i) {
    int tmp = c * i;
    tmp += a * max(0, x - i);
    tmp += b * max(0, y - i);
    ans = min(ans, tmp);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
/******************
*  Author: BD747  *
******************/
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#include<vector>
#include<bits/stdc++.h>
using namespace std;

int a,b,c;

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>a>>b>>c;
	cout<<min(a+b+1,c)+b<<endl;

	return 0;
}


Measured memory_bytes: 256
n = int(input())
A, B, C = [], [], []
for i in range(n):
    a, b, c = map(int, input().split())
    A.append(a); B.append(b); C.append(c)

dp = [[0] * 3 for _ in range(n+1)]

for i in range(n):
    dp[i+1][0] = max(dp[i+1][0], max(dp[i][1], dp[i][2])+A[i])
    dp[i+1][1] = max(dp[i+1][1], max(dp[i][0], dp[i][2])+B[i])
    dp[i+1][2] = max(dp[i+1][2], max(dp[i][1], dp[i][0])+C[i])
print(max(dp[n]))

Measured memory_bytes: 34572
#include <iostream>

using namespace std;

int SelectionSort(int A[], int N){
  int minj, tmp, cnt=0;

  for(int i = 0; i < N-1; i++){
    minj = i;
    for(int j = i; j < N; j++){
      if(A[j] < A[minj]){
	      minj = j;
      }
    }
    tmp = A[i];
    A[i] = A[minj];
    A[minj] = tmp;
    if(i != minj) cnt++;
  }

  return cnt;
}

int main(){
  int A[100], N, cnt;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }

  cnt = SelectionSort(A, N);

  for(int i = 0; i < N; i++){
    if(i > 0) cout << " ";
    cout << A[i];
  }
  cout << endl << cnt << endl;
  
  return 0;
}



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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, x;
	cin >> n;

	map<ll, ll> freq;
	vector<ll> a;
	for(int i = 0; i < n; i++)
	{
		cin >> x;

		if(freq[x] == 1)
		{
			freq[x] = 0;
			a.pb(x);
		}
		else
		{
			freq[x] = 1;
		}
	}

	sort(all(a));

	if(a.size() > 1)
	{
		cout << a[a.size()-1]*a[a.size()-2] << endl;
	}
	else
	{
		cout << 0 << endl;
	}
	return 0;	
}

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

const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;

struct edge { int a, b, w; };

int n, m, group[maxn];
vector<edge> G;

bool cmp(const edge& a, const edge& b) { return a.w < b.w; }

int Find(int v) { return (group[v] == v)? v : group[v] = Find(group[v]); }
void Union(int a, int b) { group[Find(a)] = Find(b); }


int main()
{
	while(scanf("%d%d", &n, &m) && n) {
		G.resize(m);
		for(int i = 0; i < m; i++) scanf("%d%d%d", &G[i].a, &G[i].b, &G[i].w);

		sort(G.begin(), G.end(), cmp);

		int mini = INF;
		for(int l = 0; l <= m-n+1; l++) {
			for(int i = 1; i <= n; i++) group[i] = i;

			int r, cnt = 0;
			for(r = l; r < m; r++) {
				int a = G[r].a, b = G[r].b;
				if(Find(a) != Find(b)) { Union(a, b); cnt++; }
				if(cnt == n-1) { mini = min(mini, G[r].w - G[l].w); break; }
			}
		}

		if(mini != INF) printf("%d\n", mini);
		else puts("-1");
	}

	return 0;
}

Measured memory_bytes: 3216
#include<stdio.h>


int main(){

  int n, m, x, y, z, cnt=0, i;
  int a[110]={}, b[110]={}, c[110]={};

  scanf("%d", &n);
  scanf("%d", &x);
  for(i=0;i<x;i++){
    scanf("%d", &m);
    a[m]=1;
  }
  scanf("%d", &y);
  for(i=0;i<y;i++){
    scanf("%d", &m);
    b[m]=1;
  }
  scanf("%d", &z);
  for(i=0;i<z;i++){
    scanf("%d", &m);
    c[m]=1;
  }

  for(i=1;i<=n;i++){
    if((a[i]==1&&b[i]==1&&c[i]==1)||(a[i]==0&&b[i]==1&&c[i]==1)||(a[i]==0&&b[i]==0&&c[i]==1)) cnt++;
  }

  printf("%d\n", cnt);

  return 0;
}

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

int main(){
	string s;
	cin >> s;
	int a = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'A' && s[i+1] == 'C') a = 1;
	}
	if(a == 1) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1000000007;

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

    vector<ll> A(N), B(N);
    for(int i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }

    ll ans = 0;
    ll sum_up = 0;
    for(int i=N-1;i>=0;i--){
        ll up = (B[i] - (A[i] + sum_up) % B[i]) % B[i];
        ans += up;
        sum_up += up;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3


def solv(w, h, x, y):
    ha = w * h / 2
    dw = abs(w/2-x)
    dh = abs(h/2-y)
    if dw == 0 and dh == 0:
        return (ha, 1)
    else:
        return (ha, 0)


if __name__ == '__main__':

    w, h, x, y = map(int, input().split())

    ans = solv(w, h, x, y)

    print(ans[0], ans[1])


Measured memory_bytes: 2940
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Main main = new Main();
        main.solv();
    }
    
    private void solv() {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int q = input.nextInt();
        Deque<Proc> st = new ArrayDeque<Proc>(n);
        while (n-- > 0) {
            String name = input.next();
            int time = input.nextInt();
            st.add(new Proc(name, time));
        }
        
        int t = 0;
        while (st.isEmpty() == false) {
            Proc p = st.poll();
            if (p.getTime() <= q) {
                t += p.getTime();
                System.out.println(p.getName() + " " + t);
            } else {
                t += q;
                p.subTime(q);
                st.add(p);
            }
        }
    }
    
    private void print(Object[] xs) {
        StringBuilder sb = new StringBuilder();
        for (Object x : xs) sb.append(x.toString()).append(' ');
        System.out.println(sb.toString().trim());
    }
    
    private static class Proc {
        String name;
        int time;
        public Proc(String name, int time) {
            this.name = name;
            this.time = time;
        }
        public int getTime() {return time;}
        public int subTime(int t) {time -= t; return time;}
        public String getName() {return name;}
    }
}

Measured memory_bytes: 65700
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <string>
#include <bitset>
#include <algorithm>
#include <functional>
using namespace std;
using ll = long long;

int main(){
    ll ans=0;
    ll N,M;
    cin >> N >> M;
    priority_queue<ll,vector<ll>,greater<ll>> PQ;
    for (ll i = 0;i<N;i++){
        ll a;
        cin >> a;
        ans+=a;
        PQ.push(a);
    }

    vector<pair<ll,ll>> vec(M);
    for (ll i=0;i<M;i++){
        ll b,c;
        cin >> b >> c;
        vec[i] = make_pair(b,c);
    }

    sort(vec.begin(),vec.end(),
        [](const pair<ll,ll>& x,const pair<ll,ll>& y){
        return x.second > y.second;
    });
    
    for (ll i=0;i<M;i++){
        //cout << vec[i].first << ":"<<vec[i].second << endl;
        ll cnt = 0;
        while(PQ.top() < vec[i].second){
            ans -= PQ.top();
            PQ.pop();
            ans += vec[i].second;
            PQ.push(vec[i].second);
            cnt++;
            if (cnt==vec[i].first) break;
        }
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 2676
from sys import stdin

n = stdin.readline().rstrip()
arr = [int(x) for x in stdin.readline().rstrip().split()]

alice_score = 0
bob_score = 0

for i in range(len(arr)):
    max_num = max(arr)
    if(i%2!=0):
        
        alice_score += max_num
        arr.remove(max_num)
    else:
        bob_score += max_num
        arr.remove(max_num)

print(abs(alice_score - bob_score))

Measured memory_bytes: 3060
n=int(input())
S=list(input())
W=[0]*(n+1)
B=[0]*(n+1)
for i in range(n):
  if S[i]=="#":
    B[i+1]=B[i]+1
  else:
    B[i+1]=B[i]
for i in range(n-1,-1,-1):
  if S[i]==".":
    W[i]=W[i+1]+1
  else:
    W[i]=W[i+1]
ans=10**10
for i in range(n+1):
  a=W[i]+B[i]
  if a<ans:
    ans=a
print(ans)

Measured memory_bytes: 14180
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    boolean[] b = new boolean[26];
    for (int i = 0; i < s.length(); i++) {
      b[s.charAt(i) - 'a'] = true;
    }

    for (int i = 0; i < 26; i++) {
      if (!b[i]) {
        System.out.println((char) ('a' + i));
        return;
      }
    }

    System.out.println("None");

  }
}

Measured memory_bytes: 39156
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

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

    vector<int> count(4);

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (s[i] == s[j]) count[i]++;
        }
    }
    for (int i = 0; i < 4; i++) {
        count[i] = -count[i];
    }
    sort(count.begin(), count.end());
    if (count[0] == -2 && count[1] == -2 && count[2] == -2 && count[3] == -2) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }

    return 0;
}

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


int main() {
  int n,m,a[100];
  cin>>n>>m;
  int popu=0; double sum_a=0;
  rep(i,n){
    int A;
    cin>>A;
    a[i]=A;
    sum_a+=a[i];
  }
  rep(i,n){
    if(a[i] >= sum_a/(4*m)){
      popu++;
    }
  }
  if(popu>=m){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 3636
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long i64;

int D, len = 0;
i64 pw[20], result = 0;

void work(int x, int L, i64 rest, i64 way) {
  if (x == L / 2) {
    if (rest == 0) result += way * ((L & 1) ? 10 : 1);
    
    return;
  }

  if ((L & 1) && x == L / 2) {
    work(x + 1, L, rest, way * 9);
  } else {
    if (pw[L - x - 1] - pw[x] > 0) {
      for (int i = -9; i <= 10; ++i) {
	if ((pw[L - x - 1] - pw[x]) * i > rest) {
	  if (i != 10) work(x + 1, L, rest - (pw[L - x - 1] - pw[x]) * i, way * (9 - abs(i) + (x != 0)));
	  if (i > -9) work(x + 1, L, rest - (pw[L - x - 1] - pw[x]) * (i - 1), way * (9 - abs(i - 1) + (x != 0)));
	  break;
	}
      }
    } else {
      for (int i = 9; i >= -10; --i) {
	if ((pw[L - x - 1] - pw[x]) * i > rest) {
	  if (i != -10) work(x + 1, L, rest - (pw[L - x - 1] - pw[x]) * i, way * (9 - abs(i) + (x != 0)));
	  if (i < 9) work(x + 1, L, rest - (pw[L - x - 1] - pw[x]) * (i + 1), way * (9 - abs(i + 1) + (x != 0)));
	  break;
	}
      }
    }
  }
  
}

int main() {
  scanf("%d", &D);
  
  pw[0] = 1;

  for (int i = 1; i < 20; ++i) pw[i] = pw[i - 1] * 10;

  for (int i = 18; i; --i)
    work(0, i, D, 1);

  printf("%lld\n", result);
  return 0;
}


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

int main(){
  int N,M;
  cin >>N>>M;
  int s[N+10]={0};
  int e[N+10]={0};
  int a,b;
  for (int i=0;i<M;i++){
    cin>>a>>b;
    if(a==1){
      s[b]=1;
    }
    if(b==N){
      e[a]=1;
    }
  }
  for(int i=1;i<N+1;i++){
    if((s[i]==1)&&(e[i]==1)){
      cout<<"POSSIBLE"<<endl;
      return  0;
    }
  }
  cout<<"IMPOSSIBLE"<<endl;
  return 0;
}


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

ll dp[1001][1001];

int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int main()
{
	int h,w;
	cin >> h >> w;
	int sx,sy,tx,ty;
	cin >> sx >> sy >> tx >> ty;
	sx--;sy--;tx--;ty--;
	priority_queue< pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>> >> PQ;
	for(int i = 0;i<h;i++)for(int j = 0;j<w;j++)dp[i][j] = 1e9;
	vector<string> G(h);
	for(int i = 0;i<h;i++)cin >> G[i];
	PQ.emplace(0,pair<int,int>(sx,sy));
	dp[sx][sy] = 0;

	while(!PQ.empty())
	{
		auto now = PQ.top();
		PQ.pop();
		//cout<<now.first<<endl;
		auto nowp = now.second;
		if(dp[nowp.first][nowp.second]!=now.first)continue;

		for(int i =0;i<4;i++)
		{
			auto next = nowp;
			next.first+=dx[i];next.second+=dy[i];
			if(next.first<0||next.first>=h||next.second<0||next.second>=w)continue;
			if(G[next.first][next.second]=='#')continue;
			if(dp[next.first][next.second]>now.first)
			{
				dp[next.first][next.second] = now.first;
				PQ.emplace(now.first,next);
			}
		}
		//cout<<'a'<<endl;
		for(int i = -2;i<3;i++)for(int j = -2;j<3;j++)
		{
			auto next = nowp;
			next.first += i;next.second+=j;
			if(next.first<0||next.first>=h||next.second<0||next.second>=w)continue;
			if(G[next.first][next.second]=='#')continue;
			if(dp[next.first][next.second]>now.first+1)
			{
				dp[next.first][next.second] = now.first+1;
				PQ.emplace(now.first+1,next);
			}
		}

		
	}

	if(dp[tx][ty]==1e9)dp[tx][ty]=-1;
	cout<<dp[tx][ty]<<endl;

}


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

ll n;
ll a[200002];

int main(){
    cin >> n;
    for(ll i=0;i<n;i++) cin >> a[i];
    ll res=0;
    ll right=0;
    ll sum=0;
    for(ll left=0;left<n;left++){
        while(right<n&&(sum^a[right])==(sum+a[right])){
            sum+=a[right];
            right++;
        }
        res+=right-left;
        if(left==right) right++;
        else sum-=a[left];
    }
    cout << res << endl;
}

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

int main() {
  ll x, k, d;
  cin >> x >> k >> d;
  if (x < 0) x = -x;

  ll num = x / d;
  ll r = x % d;
  if (r > abs(r - d)) {
    ++num;
    r = abs(r - d);
  }

  ll ans;
  if (num < k) {
    if ((k - num) % 2 == 0) {
      ans = r;
    } else {
      ans = d - r;
    }
  } else {
    ans = x - k * d;
  }

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

Measured memory_bytes: 3616