akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
typedef unsigned int ui; 
ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * x%mod;
		x = x * x%mod;
		n >>= 1;
	}
	return res;
}
int main(){
	int n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;
	ll sum[1001] = {}; sum[0] = (ll)1;
	ll per[1001], invper[1001];
	per[0] = (ll)1; invper[0] =1;
	for (ll i = 1; i <= 1000; i++) {
		per[i] = per[i - 1] * i%MOD;
	}
	for (ll i = 1; i <= 1000; i++) {
		invper[i] = mod_pow(per[i], MOD - 2, MOD);
	}
	ll superinvper[1001][1001];
	for (ll i = 0; i <= 1000; i++) {
		superinvper[i][0] = (ll)1;
		for (ll j = 1; j <= 1000; j++) {
			superinvper[i][j] = superinvper[i][j - 1] * invper[i] % MOD;
		}
	}
	for (int i = a; i <= b; i++) {
		for (int j = n - 1; j >= 0; j--) {
			if (sum[j] > 0) {
				for (int k = c; k <= d; k++) {
					if (j + i * k <= n) {
						sum[j + i * k] = (sum[j + i * k] + ((((sum[j] * per[n - j]) % MOD)*superinvper[i][k] % MOD)*invper[n-j-i*k]%MOD)*invper[k]%MOD) % MOD;
					}
				}
			}
		}
	}
	cout << sum[n] << endl;
	char nyaa;
	std::cin >> nyaa;
	return 0;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef map<ll,ll>::iterator itll;
typedef long double ld;
typedef map<ll,ll> mapll;
typedef map<string,ll> mapstl;
#define con continue
#define pb push_back
#define fi first
#define se second
#define fr front()
#define one 1.0
#define inf 1000000000000000000
#define all(vl) vl.begin(),vl.end()
#define m_p make_pair 
#define sz(a) sizeof(a)
#define forn(mp,it) for(it = mp.begin();it!=mp.end();it++)
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	ll cnt = 0;
	for(int i=1;i<=n;i++)
	{
		ll cop = i;
		ll tmp = 0;
		while(cop)
		{
			tmp++;cop/=10;
		}
		if(tmp%2)
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 3636
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# 初項s, 交差dのn個の数列の和
def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, L = map(int, input().split())

    a = []
    for i in range(N):
        a.append(L + i)

    total = sum(a)
    mini = INF
    ans = INF
    for i in range(N):
        x = total - a[i]
        if abs(total - x) < mini:
            mini = abs(total - x)
            ans = x
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4580
#include <iostream>
#include <vector>
#include <chrono>
#include <random>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n, m, a, b;
	std::cin >> n >> m >> a >> b;
	while(b > 0) {
		std::cout << (std::string(a, '0') + std::string(m - a, '1')) << '\n';
		std::cout << (std::string(a, '1') + std::string(m - a, '0')) << '\n';
		b--;
		n -= 2;
	}
	while(n--) {
		std::cout << (std::string(a, '0') + std::string(m - a, '1')) << '\n';
	}
}

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

using namespace std;

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int x = c - a, y = d - b;
    cout << c - y << " " << d + x << " " << a - y << " " << b + x;
    return 0;

}


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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)


int main(void){

	int r; cin >> r;
	cout << r*r << endl;


	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
// #include <cmath>
// #include <math.h>
using namespace std;

int main(){
    int c11, c12, c13, c21, c22, c23, c31, c32, c33;
    cin >> c11 >> c12 >> c13;
    cin >> c21 >> c22 >> c23;
    cin >> c31 >> c32 >> c33;
    // int maxb0 = max({c11, c12, c13});
    int mina1 = min({c11, c12, c13});
    // cout << mina1 << endl;
    int b1, b2, b3;
    bool flag;
    for (int i=0; i<=mina1; ++i){
        flag = 1;       
        b1 = c11 - mina1;
        b2 = c12 - mina1;
        b3 = c13 - mina1;
        // cout << b1 << " " << b2 << " " << b3 << endl;
        if (c21 - b1 == c22 - b2 && c22 - b2 == c23 - b3){
            flag *= 1;
        } else {
            flag *= 0;
        }
        if (c31 - b1 == c32 - b2 && c32 - b2 == c33 - b3){
            flag *= 1;
        } else {
            flag *= 0;
        }
        if (flag == 1){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
    int A, B, C; cin >> A >> B >> C;
    if(A + B >= C - 1)
    {
        cout << B + C << endl;
        return 0;
    }
    else
    {
        cout << (A + B + 1) + B << endl;
        return 0;
    }
    return 0;
}


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

using namespace std;

int n, i, x, s, t;

void solve()
{
  cin >> n;
  for(i = 1; i <= n; i++)
  {
    cin >> x;
    s += x;
    t = max(t, x);
  }
  if(2 * t < s) cout << "Yes" << endl;
  	else cout << "No" << endl;
}

int main()
{
  solve();
}

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


auto solve(long long N, long long K, std::vector<long long> l){
    sort(begin(l), end(l), greater<long long>());
    auto bi = begin(l);
    auto ei = bi;
    advance(ei, K);
    return accumulate(bi , ei, 0LL);
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> l(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&l[i]);
    }
    auto result = solve(N, K, std::move(l));
    cout << result << endl;
    return 0;
}


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

using namespace std;
typedef pair<int, int> P;

int main()
{
    int N;
    cin >> N;
    vector<int> state(N);
    vector<vector<P>> A(N);
    int a, x;
    for (int i = 0; i < N; ++i)
    {
        cin >> a;
        A[i].resize(a);
        for (int j = 0; j < a; ++j)
        {
            cin >> x >> A[i][j].second;
            A[i][j].first = x - 1;
        }
    }

    bool flag;
    int ans = 0, count;
    for (int i = 1; i < (1 << N); ++i)
    {
        flag = true;
        for (int j = 0; j < N; ++j)
        {
            if ((i >> j) & 1)
            {
                for (int k = 0; k < A[j].size(); ++k)
                {
                    if (A[j][k].second)
                    {
                        if (((i >> A[j][k].first) & 1) != 1)
                        {
                            flag = false;
                            break;
                        }
                    }
                    else
                    {
                        if ((i >> A[j][k].first) & 1)
                        {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            if (!flag)
                break;
        }
        if (flag)
        {
            count = 0;
            for (int j = 0; j < N; ++j)
            {
                if ((i >> j) & 1)
                    ++count;
            }
            ans = max(ans, count);
        }
    }
    cout << ans << endl;
}


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


int main(void) {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a<c) {
    if (b>c){
      if(b<d){
      
      cout << b-c << endl;
      }
      else cout << d-c << endl;
    }
    else cout << 0 << endl;
  }
  else{
    if (d>a){
      if(d<b){
      cout << d-a << endl;
      }
      else cout << b-a << endl;
    }
    else cout << 0 << endl;
  }
  
               
   
}


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

int edge_color[100010];
std::vector<std::pair<int, int>> edges[100010]; // {to, num}

void dfs(int i, int used_color){
    int color = 0;
    for(auto edge : edges[i]){
        if(edge_color[edge.second]) continue;
        color++;
        if(color == used_color) color++;
        edge_color[edge.second] = color;
        dfs(edge.first, color);
    }
}





int main(){
    int n;
    std::cin >> n;
    for(int i = 0; i < n-1; i++){
        int a, b;
        std::cin >> a >> b;
        a--; b--;
//        edges[i] = Edge(a, b)
        edges[a].push_back({b, i});
        edges[b].push_back({a, i});
    }
    int max = 0;
    for(auto edge : edges){
        max = std::max(max, (int)edge.size());
    }
    dfs(0, 0);
    std::cout << max << std::endl;
    for(int i = 0; i < n-1; i++){
        std::cout << edge_color[i] << std::endl;
    }
    return 0;
}


Measured memory_bytes: 7424
/** "Ever tried.
         Ever failed.
               No matter.
                   Try Again.
                        Fail again.
                             Fail better.**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define pb push_back
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define setdp memset(dp,-1,sizeof(dp))
#define fr first
#define sc second
#define NumofDigits(n)   ((long long)log10(n)+1)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-9;
const int MOD = 1e9+7;
/*
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll fastpow(ll b, ll p)
{if(!p)return 1;ll ret = fastpow(b, p >> 1);ret *= ret;if(p&1)ret*= b;return ret;}
int dx[] = {- 1, 0, 0, 1, 0 };
int dy[] = { 0,- 1, 1, 0, 0 };*/
inline void File()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
int n,m,x;
int c[15],arr[15][15];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>x;
    for(int i=0; i<n; i++)
    {
        cin>>c[i];
        for(int j=0; j<m; j++)
            cin>>arr[i][j];
    }
    int ans=1e9;
    for(int msk=0; msk<(1<<n); msk++)
    {
        int cost=0;
        vector<int>lvls(m);
        for(int i=0; i<n; i++)
        {
            if(msk&(1<<i))
            {
                cost+=c[i];
                for(int j=0; j<m; j++)
                    lvls[j]+=arr[i][j];
            }
        }
        bool ok=true;
        for(int idx=0; idx<m; idx++)
            if(lvls[idx]<x)
                ok=false;
        if(ok)
            ans=min(ans,cost);
    }
    if(ans==1e9)
        return cout<<-1,0;
    cout<<ans;
}


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

int main()
{
    int N, M;
    cin >> N >> M;
    if(M < N) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
  string str ;
  getline(cin,str);
  if(str[1]=='S'){
    if(str[0]=='R' || str[2]=='R'){
      cout<<1;
    }
    if(str[0]=='S' && str[2]=='S'){
      cout<<0;
    }
    
  }
  if(str[1]=='R'){
    if(str[0]=='R' && str[2]=='R'){
      cout<<3;
    }
    if((str[0]=='R' && str[2]!='R')||(str[0]!='R' && str[2]=='R')){
       cout<<2;
    }
    if(str[0]!='R' && str[2]!='R'){
      cout<<1;
    }
  }
        
}                                      
                                       
    
      


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

namespace Finding_a_Word
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> words = new List<string>();
            string findingWord = Console.ReadLine();
            while (true)
            {
                string line = Console.ReadLine();
                if (line.Equals("END_OF_TEXT")) break;
                string[] strs = line.Split(' ');
                foreach (string str in strs)
                {
                    words.Add(str);
                }
            }
            FindingAWord problem = new FindingAWord();
            Console.WriteLine(problem.CountFindingWord(findingWord, words));
        }
    }

    public class FindingAWord
    {
        public int CountFindingWord(string findingWord, List<string> words)
        {
            int count = 0;
            foreach (string word in words)
            {
                if (findingWord.ToLower().Equals(word.ToLower()))
                {
                    count++;
                }
            }
            return count;
        }
    }
}

Measured memory_bytes: 5700
#include <bits/stdc++.h>
#define F(i,a,b) for(ll i=a;i<=(b);++i)
#define dF(i,a,b) for(ll i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-7
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 10007;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 

int n,h,w;
string s;

int main(){
	cin>>s;
	int n = s.size();
	if(s[n-1]=='s') s+="es";
	else s+='s';
	cout<<s<<endl;
}

Measured memory_bytes: 3608
var q = require("fs").readFileSync("/dev/stdin", "utf8").split(/\s+/).filter(x => x.length);
q.shift();
var a = q.map(x => +x);
// imos' method
for (var i = 1, l = a.length; i < l; i++)
    a[i] += a[i-1];
a.unshift(0);
// sort & count
a.sort((a, b) => a - b);
var j = 0, sum = 0;
for (var i = 1, l = a.length; i <= l; i++) {
    if (i === l || a[j] !== a[i]) {
        sum += (i - j) * (i - j - 1);
        j = i;
    }
}
console.log(sum / 2);

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

ll dp[100010],n;

void dep(){
	dp[0]=0;

	for(int i=1;i<=100000;i++){
			ll power=1;
	while(power<=i){
		dp[i]=min(dp[i],dp[i-power]+1);
		power*=6;
	}
	power=9;
	while(power<=i){
		dp[i]=min(dp[i],dp[i-power]+1);
		power*=9;
	}	
	}
}

int main() {
	cin>>n;
	for(int i=0;i<=100000;i++){
		dp[i]=inf;
	}
	dep();
	cout << dp[n];
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int a,b,k;
    cin>>a>>b>>k;
    for(int i=min(a,b);i>=1;i--){
        if(a%i==0 && b%i==0)k--;
        if(k==0){
            cout<<i<<endl;
            break;
        }
    }
}


Measured memory_bytes: 256
#include <stdio.h>

void po(char s[])
{
	for(int i=0;s[i]!='\0';i++)
	{
		for(int j=0;j<i;j++)
		{
			if(s[i]==s[j])
			{
				printf("no\n");
				return;
			}
		}
	}
	printf("yes\n");
}

int main(void)
{
	char s[26];
	scanf("%s",s);
	po(s);
	return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, p: "List[int]"):
    return sum(sorted(p)[:K])

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    p = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, p))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


Measured memory_bytes: 9208
#include	<stdio.h>
int	main(void)
{
	int S;
	int s,m,h;

	scanf("%d",&S);

	s=S%60;
	m=(S/60)%60;
	h=(S/3600)%24;

	printf("%d:%d:%d\n",h,m,s);

	return	0;
}

Measured memory_bytes: 592
N = int(input())
H = [int(v) for v in input().split()]
D = [0] * (N - 1)
for i in range(1, N):
    D[i - 1] = (0 if H[i - 1] < H[i] else 1)
m = 0
t = 0
for x in D:
    if x == 1:
        t += 1
    else:
        m = max(m, t)
        t = 0
m = max(m, t)
print(m)

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

using namespace std;

const int maxn=1e6+5;

int s[maxn],n,cnt;
vector<int>v;

void insertionsort(int g)
{
	for(int i=g;i<n;i++){
		int v=s[i],j=i-g;
		while(j>=0&&s[j]>v){
			s[j+g]=s[j];
			j-=g;
			cnt++;
		}
		s[j+g]=v;
	}
}

void shellsort()
{
	for(int h=1;;){
		if(h>n){
			break;
		}
		v.push_back(h);
		h=h*3+1;
	}
	int len=v.size()-1;
	for(int i=len;i>=0;i--){
		insertionsort(v[i]);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&s[i]);
	}
	shellsort();
	cout<<v.size()<<endl;
	for(int i=v.size()-1;i>=0;i--){
		printf("%d",v[i]);
		if(i){
			printf(" ");
		}
	}
	printf("\n");
	printf("%d\n",cnt);
	for(int i=0;i<n;i++){
		printf("%d\n",s[i]);
	}
	return 0;
}
/*
5
5 1 4 3 2
*/


Measured memory_bytes: 7168
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9+7LL;

int main() {
    ll N; cin >> N;
    vector<int> a(N);
    ll ans = 0;

    rep(i, N){
        ll A; cin >> A;
        if(i+A+1<=N-1) a.at(i+A+1)++;
        if(A<=i+1) ans += a.at(i-A+1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 4024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ALL(v) v.begin(), v.end()
ll mod = 1e9 + 7;
ll mul(ll a, ll b)
{
	return (a*b) % mod;
}
ll power(ll a, ll b)
{
	ll  re = 1;
	while(b)
	{
		while(!(b&1))a=mul(a,a),b>>=1;;
		re = mul(re,a);
		b--;
	}
	return re;
}
vector<ll> vec(1000010);
ll ncr(ll a, ll b)
{
	return (mul(vec[a], power(mul(vec[a-b], vec[b]), mod -2 )) );
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	

	int n;
	cin >> n;
	vector<int>a(n+1), num(n+1,0);
	for(int x =1; x<=n; x++)cin >> a[x];
		int u =0;
	for(int x =n; x>=1; x--)
	{
		for(int y =2*x; y<=n; y+=x)
			num[x] += num[y];
		if(num[x] % 2 == a[x])
			num[x] = 0;
		else
			num[x] =  1; 
		if(num[x] == 1)
			u++;
	}
	cout << u << endl;
	for(int x =1; x<=n; x++)
	{
		if(num[x] == 1)
			cout << x << " ";
	}
}

Measured memory_bytes: 10368
import collections
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
N=int(input())
D = collections.Counter(prime_factorize(N))
A=0
for d in D:
    e=D[d]
    for i in range(40):
        if (i+1)*(i+2)>2*e:
            A=A+i
            break
print(A)

Measured memory_bytes: 9484
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
typedef pair<int, int> pii;

const int INF = 1e9;
const int MAX_V = 100000;

int V, E, r;
vector<pii> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
	priority_queue<pii, vector<pii>, greater<pii> > que;
	for (int i = 0; i < V; i++) d[i] = INF;
	d[s] = 0;
	que.push(make_pair(0, s));

	while (!que.empty()) {
		pii p = que.top();
		que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); i++) {
			pii e = G[v][i];
			if (d[e.first] > d[v] + e.second) {
				d[e.first] = d[v] + e.second;
				que.push(make_pair(d[e.first], e.first));
			}
		}
	}
}

int main() {
	cin >> V >> E >> r;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		G[a].push_back(make_pair(b, c));
	}
	dijkstra(r);
	for (int i = 0; i < V; i++) {
		if (d[i] == INF) {
			cout << "INF" << endl;
			continue;
		}
		cout << d[i] << endl;
	}
}


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

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int d=max(a,b);
    int ans=0;
    if(c%d==0)
        ans=c/d;
    else
        ans=c/d+1;
    cout<<ans;
}


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

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF int(1e9)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 25

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

int n,m;
bool vst[MAXN][MAXN];

bool oob(int x,int y){
	return x<0 || x>=n || y<0 || y>=m;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>m;
	string a[n];
	forn(i,0,n) cin>>a[i];
	
	int ans=0;
	forn(s1,0,n){forn(s2,0,m){
		mset(vst,0);
		if(a[s1][s2]=='#') continue;
		queue<pair<ii,int> > q;
		q.push({{s1,s2},0});
		
		while(!q.empty())
		{			
			int x=q.front().F.F, y=q.front().F.S;
			int dist=q.front().S;
			q.pop();
			
			if(oob(x,y)) continue;
			if(a[x][y]=='#') continue;
			if(vst[x][y]) continue;
			vst[x][y]=1;
			
			ans=max(ans,dist);
			
			forn(i,0,4){
				q.push({{x+dx[i],y+dy[i]},dist+1});
			}
		}
	}}
	
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int isyy(int n){
	return (0<=n && n<=99);
}
int ismm(int n){
	return (1<=n && n<=12);
}

int main(){
	char s[6];
	int a,b;
	int ismmyy,isyymm;
	int i;
	scanf("%s",s);
	for(i=0;s[i]!='\0';i++){
		s[i]-='0';
	}
	a=s[0]*10+s[1];
	b=s[2]*10+s[3];
	
	ismmyy=(ismm(a)&&isyy(b));
	isyymm=(isyy(a)&&ismm(b));
	
	if(ismmyy && isyymm){
		printf("AMBIGUOUS\n");
	}else if(ismmyy){
		printf("MMYY\n");
	}else if(isyymm){
		printf("YYMM\n");
	}else{
		printf("NA\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

struct Cake
{
    vector<int64_t> qualities;

    Cake() : qualities(3) {}

    int64_t Score(int mask) const;
};

int Bit(int num, int pos)
{
    return (num & (1 << pos)) ? 1 : 0;
}

int64_t Cake::Score(int mask) const
{
    int64_t score = 0;
    for (size_t i = 0; i < qualities.size(); i += 1) {
        score += qualities[i] * (Bit(mask, i) ? 1 : -1);
    }
    return score;
}

struct CmpByMask
{
    int mask;

    CmpByMask(int mask) : mask(mask) {}

    bool operator()(const Cake &a, const Cake &b) const
    {
        return a.Score(mask) > b.Score(mask);
    }
};

int64_t Score(const vector<Cake> &cakes, int taken)
{
    vector<int64_t> scores(cakes[0].qualities.size(), 0);
    for (int i = 0; i < taken; i += 1) {
        for (size_t j = 0; j < scores.size(); j += 1) {
            scores[j] += cakes[i].qualities[j];
        }
    }

    int64_t total = 0;
    for (const auto &s : scores) {
        total += abs(s);
    }
    return total;
}

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

    vector<Cake> cakes(n);
    for (auto &c : cakes) {
        for (auto &q : c.qualities) {
            cin >> q;
        }
    }

    int64_t res = 0;
    for (int i = 0; i < (1 << cakes[0].qualities.size()); i += 1) {
        sort(cakes.begin(), cakes.end(), CmpByMask(i));
        res = max(res, Score(cakes, m));
    }

    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>){
    val S = next()
    val N = 13
    val MOD = 1000000007L
    var dp = LongArray(13)
    dp[0] = 1
    for (l in 0 until S.length) {
        val nextDP = LongArray(13)
        val c = if (S[l] == '?') -1 else S[l] - '0'
        for (n in 0 .. 9) {
            if (c != -1 && c != n) continue
            for (j in 0 until N) {
                nextDP[((j * 10) + n) % N] += dp[j]
                nextDP[((j * 10) + n) % N] %= MOD
            }
        }
        dp = nextDP
    }
    println(dp[5])
}
fun next() = readLine()!!

Measured memory_bytes: 41876
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<cassert>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<limits>
#include<ctime>
#include<stack>
#include<bits/stdc++.h>
#include<string>
#include<stdlib.h>
#include<stdio.h>
#define long long

using namespace std;

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	if(a==b+c or b==a+c or c==a+b){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}


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

int main() {
  int N, T, A, mi;
  cin >> N >> T >> mi;
  map<int, int> MA;
  while (cin >> A) {
    if (A > mi) MA[A - mi]++;
    mi = min(mi, A);
  }
  cout << MA.rbegin() -> second << "\n";
}

Measured memory_bytes: 8292
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<int> siz;
long long ans=1,n,k,a,b;

void dfs(int curr, int par){
	siz[curr] += 1;
	long long num=0;
	for(int i : graph[curr]){
		num += siz[i];
	}
	ans *= (k-num);
	ans %= 1000000007;
	for(int i : graph[curr]){
		siz[i] += 1;
		if(i != par){
			dfs(i,curr);
		}
	}
}

int main(){
	cin >> n >> k;
	graph.resize(n+1);
	siz.resize(n+1,0);
	for(int i = 0 ; i < n-1 ; i += 1){
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1,0);
	cout << ans;
}

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

using namespace std;

int main() {
    string S, T;
    cin >> S >> T;
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        if (S[i] == T[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    ans = 0
    for i in range(K):
        ans += A[i]
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 9188
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<fstream>
#include<algorithm>
using namespace std;
using ll = long long;

int main(){
    int a,b;
    cin >> a >> b;
    if(a==b)    cout << "Yes";
    else    cout << "No";
}

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

int main(void){
    int n,k;
    cin>>n>>k;
    int s[n];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    int ans=0;
    for(int i=0;i<n-k+1;i++){
        int p=0;
        p=(s[i+k-1]-s[i])+min(abs(s[i+k-1]),abs(s[i]));
        if(ans==0)ans=p;
        ans=min(ans,p);
    }
    cout<<ans<<endl;
}


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

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

	vector<vector<int>> tbl( 11 * 3, vector<int>( 11 ) );
	for( int K = 0; K <= 10; K++ ) {
		for( int i = 1; i <= 11 * 3; i++ ) {
			vector<vector<int>> mat( i, vector<int>( 7 ) );
			for( int j = 0; j < i; j++ ) {
				for( int l = 0; l < 7; l++ ) {
					int ii = j + 1;
					int jj = l + 1;
					mat[j][l] = ii * 7 + jj - 7;
				}
			}
			for( int j = 0; j < i - 3 + 1; j++ ) {
				for( int l = 0; l < 7 - 3 + 1; l++ ) {
					int sum = 0;
					for( int m = j; m < j + 3; m++ ) {
						for( int nn = l; nn < l + 3; nn++ ) {
							sum += mat[m][nn];
						}
					}
					if( sum % 11 == K ) {
						tbl[i - 1][K]++;
					}
				}
			}
		}
	}

	int m = n % 11;
	m--;
	if( m < 0 ) m = 10;
	long long d = tbl[m + 11][k] - tbl[m][k];
	long long d1 = tbl[m + 11 * 2][k] - tbl[m + 11][k];
	int nn = n / 11;
	if( m == 10 ) {
		if( nn ) nn--;
	}
	long long ans = tbl[m][k];
	if( nn > 0 ) ans += d;
	if( nn > 1 ) ans += d1 * ( nn - 1 );

	cout << ans << endl;
}


Measured memory_bytes: 256
N = int(input())
D = {}
max_num = -1
for i in range(N):
    s = input()
    if s in D:
        D[s] += 1
    else:
        D[s] = 0
    max_num = max(max_num, D[s])

result = []
for k, v in D.items():
    if v == max_num:
        result.append(k)

print(*sorted(result), sep='\n')


Measured memory_bytes: 33944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
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;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}
vector<bool> sieve(int n)
{
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (int j = 2; i * j <= n; j++)
            {
                isPrime[i * j] = false;
            }
        }
    }
    return isPrime;
}
int main()
{
    int N;
    cin >> N;
    auto isPrime = sieve(55555);
    vint ans;
    int cnt = 0;
    rep(i, 55555)
    {
        if (isPrime[i] and i % 5 == 1 and cnt < N)
        {
            ans.push_back(i);
            cnt++;
        }
        if (cnt >= N)
            break;
    }
    rep(i, N)
    {
        cout << ans[i] << " ";
    }

    return 0;
}


Measured memory_bytes: 256
//終局から考える。
//S[i] = '1'なるiについて、A[i]が{A[j], i+1≦j≦N-1, S[j] = '0'}と独立ならx≠0.
//全て従属とする。iが大きい方から考えると、最終的にx=0(従属)にできる。
//独立性の判定:
//・各数を2進数ベクトルと考えて {A[j], i+1≦j≦N-1, S[j] = '0'}について掃き出し法をおこない、
//  表現できるベクトル集合が同一のより単純な表現に直す
//・その表現では'1'の立つ最上位ビットの場所がdistinctだから、A[i]を作れるかを貪欲に判定できる
//計算量はO(TN^3). 厳しい？ -> 定数倍が軽いので大丈夫そう. 不安なら0ベクトルを取り除いておく.
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

void sweep(vector<int> &vs) {
	int n = vs.size();
	int row = 0;
	
	for (int i = 59; i >= 0; i--) {
		int pipot = -1;
		for (int j = row; j < n; j++) {
			if ((vs[j] >> i) & 1) {
				pipot = j;
				break;
			}
		}
		if (pipot == -1) continue;
		swap(vs[row], vs[pipot]);
		
		for (int j = row + 1; j < n; j++) {
			if ((vs[j] >> i) & 1) {
				vs[j] ^= vs[row];
			}
		}
		row++;
	}
	
	while (vs.size() > 0 && *vs.rbegin() == 0) vs.pop_back();
}

int solve(vector<int> a, string s) {
	int n = a.size();
	
	vector<int> vs;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == '0') {
			vs.push_back(a[i]);
		}
		else {
			sweep(vs);
			int val = a[i];
			for (int j = 0; j < vs.size(); j++) {
				if ((val ^ vs[j]) < val) {
					val ^= vs[j];
				}
			}
			if (val != 0) return 1;
		}
	}
	return 0;
}

signed main() {
	int T;
	cin >> T;
	while (T--) {
		int i, n; cin >> n;
		vector<int> a(n);
		rep(i, n) cin >> a[i];
		string s; cin >> s;
		cout << solve(a, s) << endl;
	}
	return 0;
}

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

int ans[50010] = {};
int prime[50010] = {};
vector<int> VC;

void calc(){
	
	prime[0] = prime[1] = 1;
	for( int i=2 ; i<=50000 ; i++ ){
		if( !prime[i] ){
			VC.push_back(i) ;
			for( int j=2 ; i*j<=50000 ; j++ ){
				prime[i*j] = 1;
			}
		}
	}
	
	for( int i=4 ; i<=50000 ; i++ ){
		for( int j=0 ; VC[j] <= i/2 ; j++ ){
			if( !prime[i-VC[j]] ) ans[i]++;
		}
	}
	
}

int main(){
	
	calc();
	
	int n;
	while( cin >> n , n ){
		cout << ans[n] << endl ;
	}
	
	return 0;
}

Measured memory_bytes: 1664
//時間内にできず，しかもTLE

//方針は合っているが，オーダーがうっかり増えてしまっている
//setの要素削除できるようになっとかないと．
#include<bits/stdc++.h>
using namespace std;


typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define pb push_back
#define mp make_pair
#define snd second
#define fst first
#define debug printf("--%d--\n",__LINE__)
#define ll long long int

int n;
int c[512][4];
ll ans = 0;

bool same(vi x, vi y){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if (x[j] != y[(i+j)%4]) break;
			if (j==3) return true;
		}
	}
	return false;
}

vi rot(vi a, int n){
	vi ret(4);
	for(int i=0;i<4;i++){
		ret[i] = a[(i+n)%4];
	}
	return ret;
}

vi normalize(vi a){
	int x = 0, y = 0;
	x = a[1] + a[2] - a[3] - a[0];
	y = a[0] + a[1] - a[2] - a[3];
	if (x==0 && y==0){
		if (a[0] > a[1]) return rot(a,1);
		return a;
	}
	if (x>0 && y>=0) return rot(a,1);
	if (x>=0 && y<0) return rot(a,2);
	if (x<0 && y<=0) return rot(a,3);
	return a;
}

int calcsym(vi a){
	if (a[0]==a[1] && a[0]==a[2] && a[0]==a[3]) return 4;
	if (a[0]==a[2] && a[1]==a[3]) return 2;
	return 1;
}

int main(void){
	cin >> n;
	for(int i=0;i<n;i++){
		vi men(4);
		for(int j=0;j<4;j++){
			cin >> c[i][j];
		}
	}
	ll ans = 0;
	vvi menscatalog;
	for(int i=0;i<n;i++){
		vi men(4);
		for(int j=0;j<4;j++){
			men[j] = c[i][j];
		}
		menscatalog.pb(normalize(men));
	}
	
	
	multiset<vi> allmens;
	for(int k=0;k<n;k++){
		allmens.insert(menscatalog[k]);
	}
	
	
	for(int i=0;i<n;i++){
		//erase i-th men
		multiset<vi>::iterator itr = allmens.find(menscatalog[i]);
		allmens.erase(itr);
		for(int j=i+1;j<n;j++){
			//erase j-th men
			multiset<vi>::iterator itr = allmens.find(menscatalog[j]);
			allmens.erase(itr);
			//insert (j-1)-th men (if j>i+1)
			if (j>i+1){
				allmens.insert(menscatalog[j-1]);
			}
			for(int k=0;k<4;k++){
				vvi mens;
				for(int l=0;l<4;l++){
					vi men;
					men.pb(c[i][l]);
					men.pb(c[j][(4-l+k)%4]);
					men.pb(c[j][(7-l+k)%4]);
					men.pb(c[i][(l+1)%4]);
					mens.pb(normalize(men));
				}
				//cout << i << " " << j << " " << k << endl;				
				/*for(int l=0;l<4;l++){
					for(int m=0;m<4;m++){
						cout << mens[l][m] << " ";
					}
					cout << endl;
				}*/
				vi chk(4);
				ll num = 1;
				for(int l=0;l<4;l++){
					if (chk[l]) continue;
					int cnt = 1;
					for(int m=l+1;m<4;m++){
						if (mens[l]==mens[m]){
							chk[m] = 1;
							cnt++;
						}
					}
					int mc = allmens.count(mens[l]);
					/*if (mc>0){
						cout << "mc = " << mc << ": ";
						for(int m=0;m<4;m++){
							cout << mens[l][m] << " ";
						}cout << endl;
					}*/
					int sym = calcsym(mens[l]);
					for(int m=0;m<cnt;m++){
						num *= (mc-m)*sym;
					}
				}
				ans += num;
			}
			
			//insert (n-1)-th men (if j=n-1)
			if (j==n-1){
				allmens.insert(menscatalog[n-1]);
			}			
		}
	}
	
	cout << ans << endl;
	
	
	return 0;
}


Measured memory_bytes: 384
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>

using namespace std;

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

	string s;
	int res = 0;

	cin >> s;

	for (int i = 2; i < s.length(); i+=2)
	{
		string t = s.substr(0, i);
		string s1 = t.substr(0, i / 2);
		string s2 = t.substr(i / 2);
		if (s1 == s2)
		{
			res = max(res, i);
		}
	}

	cout << res << '\n';

	return 0;
}


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

void solve(long long N, vector<long long> a){
	priority_queue<long long, vector<long long>, greater<long long> > fque;
	priority_queue<long long> bque;

	vector<long long> front_score(2*N+1);
	vector<long long> back_score(2*N+1);
	for(long long i = 0 ; i <= N-1 ; i++){
		fque.push(a[i]);
		front_score[N] += a[i];
	}
	for(long long i = N+1 ; i <= 2*N ; i++){
		fque.push(a[i-1]);
		front_score[i] += front_score[i-1]+a[i-1]-fque.top();
		fque.pop();
	}

	for(long long i = 2*N ; i <= 3*N-1 ; i++){
		bque.push(a[i]);
		back_score[2*N] += a[i];
	}
	for(long long i = 2*N-1 ; i >= N ; i--){
		bque.push(a[i]);
		back_score[i] += back_score[i+1]+a[i]-bque.top();
		bque.pop();
	}
	long long res = front_score[N]-back_score[N];
	// printf("%lld\n", front_score[N]);
	// printf("%lld\n", back_score[N]);
	for(long long i = N+1 ; i <= 2*N ; i++){
		res = max(res, front_score[i]-back_score[i]);
		// printf("%lld\n", front_score[i]);
		// printf("%lld\n", back_score[i]);
	}

	printf("%lld\n", res);
}

int main(){
	long long N;
	scanf("%lld",&N);
	vector<long long> a(3*N-1+1);
	for(long long i = 0 ; i <= 3*N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, a);
	return 0;
}


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

int main(){
    int n; cin >> n;
    vector<double> v(n);
    rep(i, n) cin >> v[i];
    sort(all(v));
    for(int i=0; i<n-1; i++) {
        double a = (v[i] + v[i+1]) / 2;
        v[i+1] = a;
    }

    cout << setprecision(20) << v[n-1] << endl;
}
   

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  int x;
  cin >> x;
  cout << (x+110)/111 * 111 << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2*(1e5)+10;
int a[N];
int n,m;
ll ans;

int Abs(int x){return x<0?-x:x;}
ll get_val(int x){
	ll ret=0;
	for (int i=1;i<=n;++i) ret+=Abs(a[i]-x);
	return ret;
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
#endif
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",a+i),a[i]=a[i]-i;
	sort(a+1,a+1+n);
	ans=0;
	if (n&1)
		ans=get_val(a[(n+1)/2]);
	else{
		int tmp=(int)(a[n/2]+a[n/2+1])/2;
		ans=min(get_val(tmp),get_val(tmp+1));
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 1024
def main():
    N = int(input())
    S = str(input())
    if N % 2 == 1:
        print('No')
    elif N == 2:
        if S[0] == S[1]:
            print('Yes')
        else:
            print('No')
    else:
        n = (N // 2) - 1
        na = n + 1
        if S[0:n] == S[na:-1]:
            print('Yes')
        else:
            print('No')
main()

Measured memory_bytes: 9052
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int n;
  while(cin>>n,n) {
    int a[n];
    REP(i,n)
      cin>>a[i];
    int res = 0;
    
    REP(i,n) {
      int dn = 0;
      for (int c=1; c<=3; ++c) {
        int hazime = 1;
        for (int j=i-1, k=i+1;j>=0 || k<n; ) {
          int cc;
          if (!hazime) {
            if (j >= 0) cc = a[j];
            else cc = a[k];
          }
          else cc = c;
//          printf("%d,%d %d %d:\n",j,k,cc, i);
          //if (a[k] != cc) break;
          int ue = 0, shita = 0;
          while (j >= 0 && cc == a[j]) {
            ++ue;
            --j;
          }
          while (k < n  && cc == a[k]) {
            ++shita;
            ++k;
          }
//          printf("ue=%d,shita=%d\n",ue,shita);
          if (ue + shita >= 4-hazime) dn += ue+shita + hazime;
          else break;
          hazime = 0;
        }
        res = max(res, dn);
      }
    }
    cout << n-res << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double PI = 4*atan(1);
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
// ll gcd(ll a, ll b) { 
//     if (a == 0) return b; 
//     return gcd(b % a, a); 
// }
// ll f(ll x) {
// 	x%=MOD;
// 	if(x<0)x+=MOD;
// 	return x;
// }
// ll power(int base, int power) {
// 	ll prod = 1;
// 	ll b = base;
// 	while(power) {
// 		if (power & 1) {
// 			prod = f(prod*b);
// 		}
// 		b = f(b*b);
// 		power/=2;
// 	}
// 	return prod;
// }
// struct line {
//     int m, c;
//     ll eval(int x) { return 1LL * m * x + c; }
//     double intersectX(line l) { return (double) (c - l.c) / (l.m - m); }
// };

int n, m, h[100001];
vector<int> adj[100001];
void solve() {
	scanf("%d %d",&n,&m);
	for (int i = 1; i <= n; i++) scanf("%d",&h[i]);
	for (int i = 0,a,b; i < m; i++) {
		scanf("%d %d",&a,&b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		bool good = true;
		for (int j : adj[i]) {
			if (h[j]>=h[i]) {
				good = false;
				break;
			}
		}
		cnt+=good;
	}
	printf("%d\n",cnt);
}
int main() {

	// int t;
	// cin >> t;
	// for (int i = 1; i <= t; i++) { 
		// cout << "Case #" << i << ": ";
		solve();
	// }
}

Measured memory_bytes: 9264
def solve():
  n,x = (int(i) for i in input().split())
  s = sorted(list(int(i) for i in input().split()))
  dp = [[0]*(x+1) for _ in range(n+2)]
  for i in range(x):
    dp[0][i] = i
  mod = 10**9+7
  for i in range(n):
    for j in range(x+1):
      dp[i+1][j] += dp[i][j%s[i]]
      dp[i+1][j] %= mod
      dp[i+1][j] += dp[i][j]*i
      dp[i+1][j] %= mod
  print(dp[n][x])
  
solve()





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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
typedef vector<vector<int>> Graph;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

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

    ll A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    ll ans = INFLL;
    ans = min(ans, X * A + Y * B);

    for (int x=0; x<=X; x++) {
        ans = min(ans, 2 * x * C + A * max(0LL, (X - x)) + B * max(0LL, (Y - x)));
    }
    for (int y=0; y<=Y; y++) {
        ans = min(ans, 2 * y * C + A * max(0LL, (X - y)) + B * max(0LL, (Y - y)));
    }
    cout << ans << endl;
}

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

int main()
{
     long p, n;
     cin >> p >> n;
     long int arr[n];
     for(int i = 0; i < n ;i++)
        cin >> arr[i];
    long max = INT_MIN;
    for(int i = 1; i < n; i++)
        if(arr[i] - arr[i-1] > max)
            max = arr[i] - arr[i-1];
    if(p+arr[0] - arr[n-1] > max)
        max = p+arr[0] - arr[n-1];
    cout << p - max;

}


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

int main() {
    int N; cin >> N;
    vector<int> h(N);
    for(int i = 0; i < N; i++) cin >> h[i];

    int ans = h[0];
    int old = h[0];
    for(int i = 1; i < N; i++) {
        if(old < h[i]) {
            ans += h[i] - old;
        }
        old = h[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 888
import java.util.*;
class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int many = 0;
            for (int m = 0; m < 10; m++) {
                for (int o = 0; o < 10; o++) {
                    for (int p = 0; p < 10; p++) {
                        for (int q = 0; q < 10; q++) {
                            if ((m + o + p + q) == n) {
                                many++;
                            }
                        }
                    }
                }
            }
            System.out.println(many);
        }

    }
}

Measured memory_bytes: 18852
n, m = map(int, input().split())

graphs = list([list(map(int, input().split())) for x in range(m)])

def search_indecies(num, remainGraph, path):
    indecies = []
    for i, currentNode in enumerate(remainGraph):
        if currentNode[0] == num or currentNode[1] == num:
            others = get_other_num(currentNode, num)
            if all([x[0] != others and x[1] != others for x in path]):
                indecies.append(i)
    return indecies



def search_iterative(currentGraph, currentNodeNum, currentIndex, path):
    prev = currentNodeNum

    currentNode = currentGraph.pop(currentIndex)
    path.append(currentNode)
    if len(path) == n - 1:
        return [path]
    nextNum = get_other_num(currentNode, prev)

    nextCandidateIndecies = search_indecies(nextNum, currentGraph, path)

    pathList = []
    for nextIndex in nextCandidateIndecies:
        c = search_iterative(currentGraph[:], nextNum, nextIndex, path[:])
        pathList += c

    return pathList

def get_other_num(currentNode, prev):
    return currentNode[0] if currentNode[1] == prev else currentNode[1]


startIndecies = search_indecies(1, graphs, [])

resuts = []
for startIndex in startIndecies:
    path = []
    resuts += search_iterative(graphs[:], 1, startIndex, path)

allPaths = [r for r in resuts if len(r) > 0]
print(len(allPaths))

Measured memory_bytes: 3956
K=int(input())

import itertools,math
from functools import reduce

data = [i for i in range(1,K+1)]

def gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a,b,c in itertools.product(data, repeat=3):
    ans += gcd(a,b,c)
print(ans)



Measured memory_bytes: 69464
N = int(input())
ab = [[0, 0] for i in range(N)]
b = [0]*N
cd = [[0, 0] for i in range(N)]
d = [0]*N

for i in range(N):
    ab[i] = list(map(int, input().split()))
for i in range(N):
    cd[i] = list(map(int, input().split()))

points = [[] for i in range(N)]
points2 = [[] for i in range(N)]
cd.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)

points.sort(key=lambda x: len(x))
ans = 0

for i in range(N):
    for j in range(N):
        if ab[i][0] < cd[j][0] and ab[i][1] < cd[j][1]:
            ans += 1
            cd[j][0] = -1
            break
print(ans)


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    b = SI()
    dic = dict(zip('AGCT', 'AGCT'[::-1]))
    ans = dic[b]

    return ans

print(main())

Measured memory_bytes: 3064