akhauriyash/Code-Regression huggingface dataset:
k = int(input())
ans = {1: 1, 2: 9, 3: 30, 4: 76, 5: 141, 6: 267, 7: 400, 8: 624, 9: 885, 10: 1249, 11: 1590, 12: 2208, 13: 2689, 14: 3411, 15: 4248, 16: 5248, 17: 6081, 18: 7485, 19: 8530, 20: 10248, 21: 11889, 22: 13687, 23: 15228, 24: 17988, 25: 20053, 26: 22569, 27: 25242, 28: 28588, 29: 31053, 30: 35463, 31: 38284, 32: 42540, 33: 46581, 34: 50893, 35: 55362, 36: 61824, 37: 65857, 38: 71247, 39: 76884, 40: 84388, 41: 89349, 42: 97881, 43: 103342, 44: 111528, 45: 120141, 46: 128047, 47: 134580, 48: 146316, 49: 154177, 50: 164817, 51: 174438, 52: 185836, 53: 194157, 54: 207927, 55: 218812, 56: 233268, 57: 245277, 58: 257857, 59: 268182, 60: 288216, 61: 299257, 62: 313635, 63: 330204, 64: 347836, 65: 362973, 66: 383709, 67: 397042, 68: 416448, 69: 434025, 70: 456967, 71: 471948, 72: 499740, 73: 515581, 74: 536073, 75: 559758, 76: 583960, 77: 604833, 78: 633651, 79: 652216, 80: 683712, 81: 709065, 82: 734233, 83: 754734, 84: 793188, 85: 818917, 86: 846603, 87: 874512, 88: 909496, 89: 933081, 90: 977145, 91: 1006126, 92: 1041504, 93: 1073385, 94: 1106467, 95: 1138536, 96: 1187112, 97: 1215145, 98: 1255101, 99: 1295142, 100: 1342852, 101: 1373253, 102: 1422195, 103: 1453816, 104: 1502376, 105: 1553361, 106: 1595437, 107: 1629570, 108: 1691292, 109: 1726717, 110: 1782111, 111: 1827492, 112: 1887772, 113: 1925853, 114: 1986837, 115: 2033674, 116: 2089776, 117: 2145333, 118: 2197483, 119: 2246640, 120: 2332104, 121: 2379085, 122: 2434833, 123: 2490534, 124: 2554600, 125: 2609625, 126: 2693919, 127: 2742052, 128: 2813988, 129: 2875245, 130: 2952085, 131: 3003306, 132: 3096024, 133: 3157249, 134: 3224511, 135: 3306240, 136: 3388576, 137: 3444609, 138: 3533637, 139: 3591322, 140: 3693924, 141: 3767085, 142: 3842623, 143: 3912324, 144: 4027884, 145: 4102093, 146: 4181949, 147: 4270422, 148: 4361548, 149: 4427853, 150: 4548003, 151: 4616104, 152: 4718640, 153: 4812789, 154: 4918561, 155: 5003286, 156: 5131848, 157: 5205481, 158: 5299011, 159: 5392008, 160: 5521384, 161: 5610705, 162: 5739009, 163: 5818390, 164: 5930196, 165: 6052893, 166: 6156139, 167: 6239472, 168: 6402720, 169: 6493681, 170: 6623853, 171: 6741078, 172: 6864016, 173: 6953457, 174: 7094451, 175: 7215016, 176: 7359936, 177: 7475145, 178: 7593865, 179: 7689630, 180: 7886244, 181: 7984165, 182: 8130747, 183: 8253888, 184: 8403448, 185: 8523897, 186: 8684853, 187: 8802826, 188: 8949612, 189: 9105537, 190: 9267595, 191: 9376656, 192: 9574704, 193: 9686065, 194: 9827097, 195: 9997134, 196: 10174780, 197: 10290813, 198: 10493367, 199: 10611772, 200: 10813692}
print(ans[k])

Measured memory_bytes: 9400
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	 int a,b,money=0;
  
  	cin >> a >> b;
    for(int i=3;i>0;i--){
      if(a == i){
        money+=100000*(4-i);
      }
      if(b==i){
        money+=100000*(4-i);
      }
    }
  	if(a ==1 && b==1)money+=400000;
  
  cout << money;
  
  return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
m = max(A) 
min = float("inf")
for i in range(n):
  if min > abs(A[i] - m/2) and A[i] != m: 
    min = abs(A[i] - m/2)
    r = A[i]
print(m,r)


Measured memory_bytes: 62704
A,B,K=map(int,input().split())
a=A+K-1
b=B-K+1
if b<=a:
  for i in range(B-A+1):
    print(A+i)
else:
  for i in range(K):
    print(A+i)
  for i in range(K):
    print(B-K+1+i)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
    int a, b;
    cin >> a >> b;
    if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0){
        cout << "Possible\n";
    } else {
        cout << "Impossible\n";
    }
    return 0;
}

Measured memory_bytes: 256
// -----------------------------------
// Author     : MatsuTaku
// Affiliation: Tokushima University
// Country    : Japan
// Date       : 03/26/2020
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int x=0;
  int N; cin>>N;
  int ans = 0;
  char c;
  for (int i = 0; i < N; i++) {
    cin>>c;
    if (c == 'I')
      x++;
    else
      x--;
    ans = max(ans, x);
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    string ans;
    for (int i = 0; i < n; i++) {
        ans += s.at(i);
        ans += t.at(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
#include <tuple>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int M=8000+10;
char in[M];

int group[16][M];
int order[16][M];
int head[M];

void exec(){
	in[0]=0;
	scanf("%s",in);
	int len0=strlen(in);
	if(len0==0)exit(0);
	scanf("%s",in+len0);
	int len1=strlen(in+len0);
	int len=len0+len1;
	//cout << in << endl;
	fill(head,head+256,0);
	for(int i=0;i<len;i++){
		int v=in[i]-'A';
		head[v+1]++;
	}
	for(int i=1;i<'Z'-'A'+1;i++){
		head[i]+=head[i-1];
	}
	for(int i=0;i<len;i++){
		int v=in[i]-'A';
		//cout << v << ", " << head[v] << endl;
		order[0][head[v]++]=i;
		group[0][i]=v;
	}

	/*
	for(int i=0;i<len;i++)
	{
		int a=order[0][i];
				// debug
			int en;
			if(a<len0){
				en=len0;
			}else
			{
				en=len;
			}
			cout << group[0][a] << " ";
			for(int b=a;b<en;b++){
				cout << in[b];
			}
			cout << endl;

	}*/

	int e=1;
	for(;(1<<e)<=len;e++)
	{
		int w=1<<(e-1);

		fill(head,head+len+1,0);
		int vmax=-1;
		// set head
		for(int i=0;i<len;i++){
			int v=group[e-1][i];
			head[v+1]++;
			vmax=max(vmax,v);
		}
		for(int i=1;i<=vmax;i++){
			head[i]+=head[i-1];
		}
		// sort
		for(int i=0;i<len;i++){
			int a=order[e-1][i];
			if(len<=a+w||(a<len0&&len0<=a+w)){
				int v=group[e-1][a];
				order[e][head[v]++]=a;
			}
		}
		for(int i=0;i<len;i++){
			int a=order[e-1][i];
			if(a-w<0||(len0<=a&&a-w<len0)){
				continue;
			}
			int v=group[e-1][a-w];
			order[e][head[v]++]=a-w;
		}
		// set group
		int p0=-2,p1=-2;
		int g=-1;
		for(int i=0;i<len;i++){
			int a=order[e][i];
			int n0=group[e-1][a];
			int n1=-1;
			if(a+w<len0||(len0<=a&&a+w<len)){
				n1=group[e-1][a+w];
			}
			if(p0!=n0||p1!=n1){
				p0=n0;
				p1=n1;
				g++;
			}
			group[e][a]=g;
			// debug
#if 0
			int en;
			if(a<len0){
				en=len0;
			}else
			{
				en=len;
			}
			cout << group[e][a] << " ";
			for(int b=a;b<en;b++){
				cout << in[b];
			}
			cout << endl;
#endif	
		}
		//cout << endl;
	}

	// common
	int ret=0;
	for(int i=1;i<len;i++){
		int pre=order[e-1][i-1];
		int a=order[e-1][i];
		int sum=0;
		int r0=pre;
		int s0=a;
		if(r0>s0){
			swap(r0,s0);
		}
		if(len0<=r0||s0<len0)continue;
		while(1)
		{
			int r=r0+sum;
			int s=s0+sum;
			int l=0;
			while(r+(1<<l)<=len0&&s+(1<<l)<=len&&group[l][r]==group[l][s]){
				l++;
			}
			if(l==0)break;
			sum+=(1<<(l-1));
		}
		ret=max(ret,sum);
	}
	cout << ret << endl;
}
int main()
{
	while(1)exec();
}

Measured memory_bytes: 2016
x = int(input())
a = 0
if x == 0:
    print(0, 0)
else:
    while a ** 5 - (a - 1) ** 5 <= x:
        a += 1
        b = a
        while a ** 5 - b ** 5 < x:
            b -= 1
            if a ** 5 - b ** 5 == x:
                break
        else:
            continue
        break
    print(a, b)


Measured memory_bytes: 9168
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,s1=0,s2=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=n-1;i>=0;)
    {
        if(i>=0){s1+=a[i];i-=1;}
        if(i>=0){s2+=a[i];i-=1;}
    }
    cout<<s1-s2;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.ArrayDeque;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		ArrayDeque<Integer> que=new ArrayDeque<>();
		int[][] match=new int[n][n-1];
		int[] count=new int[n];
		for(int i=0; i<n; i++){
			que.add(i);
			for(int j=0; j<n-1; j++){
				match[i][j]=sc.nextInt()-1;
			}
		}
		int day=0;
		
		while(!que.isEmpty()){
			day++;
			ArrayDeque<Integer> tque=new ArrayDeque<>();
			boolean[] check=new boolean[n];
			while(!que.isEmpty()){
				int i=que.poll();
				if(count[i]==n-1){
					continue;
				}
				int tmp=match[i][count[i]];
				if(!check[tmp] && i==match[tmp][count[tmp]]){
					count[i]++;
					count[tmp]++;
					check[i]=true;
					check[tmp]=true;
					tque.add(i);
					tque.add(tmp);
					que.remove(tmp);
				}
			}
			que=tque;
		}
		for(int i=0; i<n; i++){
			if(count[i]<n-1){
				day=0;
				break;
			}
		}
		System.out.println(day-1);
	}
}


Measured memory_bytes: 309244
#include <bits/stdc++.h>
#//include <ext/pb_ds/assoc_container.hpp>
#//include <ext/pb_ds/tree_policy.hpp>
#//include <ext/pb_ds/detail/standard_policies.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//insert(), find_by_order(), order_of_key()
typedef long long int ll;
typedef unsigned long long int llu;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define ref(i,n) for(int i=0;i<n;++i)
#define rer(i,n) for(int i=n;i>=0;--i)
#define refv(i,n,k) for (int i = k; i <= n; ++i) 
#define rerv(i,n,k) for (int i = k; i >= n; --i) 
#define fi first
#define priority_queue_2 priority_queue <int, vector<int>, greater<int> >
#define se second
#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
inline void pin(int n) { printf("%d\n",n);}
#define onec(x) __builtin_popcount(x);
#define all(x) x.begin(),x.end()
double PI = acos(-1);
const int inf =  0x3f3f3f3f;
#define sv()  int t; scanf("%d",&t); while(t--)
#define MOD 1000000007
#define TRACE
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
ll StoI(string &s){ll sum=0;for(ll i=0; i<s.size(); i++){s[i]-='0';sum=sum*10+s[i];}return sum;}
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
bool soo(pair<string, pair<int, int> > a, pair<string, pair<int, int> > b)
{
    if(a.fi <b.fi)
        return true;
    else if(a.fi > b.fi)
        return false;
    else{
        return a.se.fi > b.se.fi;
    }
}
int main()
{
    int n;
    cin >> n;
    vector<pair<string, pair<int, int> > > v(n);
    ref(i,n)
    {
        string s;
        int p;
        cin >> s >> p;
        v[i]= mp(s,mp(p,i+1));
    }   
    sort(all(v),soo);
    ref(i,n)
    cout << v[i].se.se << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  2*1e9;


int main(){
    ll N,W;
    cin>>N>>W;
    vector<ll> w(N),v(N);
    for(int i=0;i<N;i++)cin>>w[i]>>v[i];
    vector<ll> dp(N*1000+1, inf);
    dp[0] = 0;
    for(int i=0;i<N;i++){

	for(int j=N*1000;j>=v[i];j--){
	    dp[j] = min(dp[j],dp[j-v[i]] + w[i]);
	}
    }
    int ans = 0;
   // for(int i=0;i<N*100+1;i++)cout<<i<<' '<<dp[i]<<endl;
    for(int i=0;i<N*1000+1;i++)if(dp[i] <=W)ans = i;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }


int calc(int x)
{
	stringstream ss; ss << x * x;
	string num(ss.str());
	int res = 0;
	
	while(num.size() != 8) num = "0" + num;	
	
	rep(i, 4)
	{
		res *= 10;
		res += num[i + 2] - '0';
	}
	
	return res;
}

int main()
{
    int n;
	cin >> n;
	
	rep(i, n)
	{
		int x;
		
		cin >> x;
		
		cout << "Case " << i + 1 << ":" << endl;
		
		rep(j, 10)
		{
			x = calc(x);
			cout << x << endl;
		}
	}
}

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

long long a[1500000];
long long b[1500000];

int main()
{
    long long m,sum,n,j,k,i;
    scanf("%lld",&n);
    sum=0;
    for (i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum=sum+a[i];
    }
    k=n*(n+1)/2;
    if (sum % k !=0) {printf("NO\n");return 0;}
    m=sum /k;
    //printf("%lld",m);
    for (i=1;i<n;i++)
    {
        b[i]=a[i+1] -a[i];
        //printf("%lld ",b[i]);
    }
    b[n]=a[1]-a[n];
    j=0;
    for (i=1;i<=n;i++)
    {
        if ((m-b[i]) < 0) {printf("NO\n");return 0;}
        if ((m-b[i]) % n !=0) {printf("NO\n");return 0;}
        j=j+(m-b[i])/n;
    }
    if (j==m) {printf("YES\n");} else {printf("NO\n");}
    return 0;
}


Measured memory_bytes: 4992
#include<iostream>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  int count=0;
  for(int i=0; i<s.size()/2; i++){
    if(s[i]!=s[s.size()-1-i]){
        count++;
    }
  }
  cout << count << endl;
  
}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

// 3乗で通したお詫びにO(NlogN)で通します
// 参考 : https://twitter.com/SayakaAmemiya/status/1249515024541859842

template<int mod, int proot> struct NTT {
	int get_mod() { return mod; }
	int pow(int a, int b) {
	int res = 1;
		for (; b; b >>= 1) {
			if (b & 1) res = (int64_t) res * a % mod;
			a = (int64_t) a * a % mod;
		}
		return res;
	}
	int inv(int i) { return pow(i, mod - 2); }
	void ntt(std::vector<int> &a, bool inverse) {
		int n = a.size();
		assert((n & -n) == n);
		int h = pow(proot, (mod - 1) / n);
		if (inverse) h = inv(h);
		
		for (int i = 0, j = 1; j < n - 1; j++) {
			for (int k = n >> 1; k > (i ^= k); k >>= 1);
			if (j < i) std::swap(a[i], a[j]);
		}
		for (int i = 1; i < n; i <<= 1) {
			int base = pow(h, n / i / 2);
			int w = 1;
			
			std::vector<int> ws(i);
			for (int j = 0; j < i; j++) ws[j] = w, w = (int64_t) w * base % mod;
			
			for (int j = 0; j < n; j += i << 1) {
				for (int k = 0; k < i; k++) {
					int u = a[k + j];
					int d = (int64_t) a[k + j + i] * ws[k] % mod;
					a[k + j] = u + d >= mod ? u + d - mod : u + d;
					a[k + j + i] = d > u ? u + mod - d : u - d;
				}
			}
		}
		if (inverse) {
			int ninv = inv(a.size());
			for (auto &i : a) i = (int64_t) i * ninv % mod;
		}
	}
};

char inputbuf[4096];
char *ptr = inputbuf;

int main() {
	fread(inputbuf, 1, sizeof(inputbuf), stdin);
	int n = 0;
	while (*ptr >= '0' && *ptr <= '9') n = n * 10 + *ptr++ - '0';
	while (*ptr != 'R' && *ptr != 'G' && *ptr != 'B') ptr++;
	
	int back[3] = { 0 };
	int forward[3] = { 0 };
	std::vector<int> a(n);
	{
		for (int i = 0; i < n; i++) {
			a[i] = *ptr == 'R' ? 0 : *ptr == 'G' ? 1 : 2;
			back[a[i]]++;
			ptr++;
		}
	}
	
	int64_t res = 0;
	// j - i != k - jを無視したの
	for (int j = 0; j < n; j++) {
		back[a[j]]--;
		res += forward[(a[j] + 1) % 3] * back[(a[j] + 2) % 3];
		res += forward[(a[j] + 2) % 3] * back[(a[j] + 1) % 3];
		forward[a[j]]++;
	}
	// j - i == k - jで相異なるものを引く
	int n2 = 1;
	for (; n2 < n + n - 1; n2 <<= 1);
	NTT<40961, 3> ntt;
	std::vector<int> count[3];
	for (auto &i : count) i.resize(n2);
	for (int i = 0; i < n; i++) count[a[i]][i]++;
	for (auto &i : count) ntt.ntt(i, false);
	
	std::vector<int> conved[3]; // conved count[i], count[(i + 1) % 3]
	for (int i = 0; i < 3; i++) {
		auto &cur = conved[i];
		cur.resize(n2);
		for (int j = 0; j < n2; j++) cur[j] = (int64_t) count[i][j] * count[(i + 1) % 3][j] % 40961;
		ntt.ntt(cur, true);
	}
	for (int j = 0; j < n; j++) res -= conved[(a[j] + 1) % 3][j + j];
	
	printf("%" PRId64 "\n", res);
	
	return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n;
    cin >> n;
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }
    ll m = n;
    ll tmp = sqrt(n) + 1;
    ll ans = 0;
    for(i = 2;i <= tmp;++i){
        if(n%i == 0){
            ll tmp = 0;
            while(n%i == 0){
                n /= i;
                ++tmp;
            }
            for(j = 1;j <= 30;++j){
                if(tmp >= j){
                    tmp -= j;
                    ++ans;
                }else break;
            }
        }
        if(n == 1) break;
    }
    if(m == n) cout << 1 << endl;
    else if(n == 1) cout << ans << endl;
    else cout << ans+1 << endl;
    return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
string n;
int d;
signed main()
{
	cin>>n;
	d=n.size();
	if(n[d-1]=='s') 
	{
		cout<<n<<'e'<<'s'<<endl;
	}
	else
	{
		cout<<n<<'s'<<endl;
	}
}

Measured memory_bytes: 3632
from collections import deque

inf=float('inf')

h,w=map(int,input().split())
maze=[]
st=[]
for j in range(h):
  a=list(input())
  for i in range(w):
    if a[i]=='.':
      a[i]=inf
    if a[i]=='#':
      a[i]=0
      st.append([j,i])
  maze.append(a)
  
de=deque(st)

while de:
  v=de.popleft()
  sy,sx=v[0],v[1]
  for p in ([1,0],[0,1],[-1,0],[0,-1]):
    ny,nx=sy+p[0],sx+p[1]
    if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!=0:
      if maze[ny][nx]>maze[sy][sx]+1:
        maze[ny][nx]=maze[sy][sx]+1
        de.append([ny,nx])

ans=0
for g in range(h):
  for f in range(w):
    ans=max(maze[g][f],ans)

print(ans)

Measured memory_bytes: 218600
S = input()
N = len(S)
for i in range(N):
    if S[i] == 'A':
        a_index = i
        break
S=S[::-1]
for i in range(N):
    if S[i] == 'Z':
        z_index = i
        break

print(N - z_index - a_index)


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

int N;
int M;

struct segtree{
  
  int n;
  long long v[1000000];
  long long lazy[1000000];
  
  segtree(int n_){
    n=1;
    while(n<n_)n*=2;
    for(int i=0;i<2*n-1;++i){
      v[i]=0;
      lazy[i]=0;
    }
  }

  long long query(int a,int b,long long add){
    return query(0,n,a,b,0,add);
  }

  long long push(int k){
    v[k]+=lazy[k];
    if(2*k+2<2*n-1){
      lazy[2*k+1]+=lazy[k];
      lazy[2*k+2]+=lazy[k];
    }
    lazy[k]=0;
  }
  
  long long query(int l,int r,int a,int b,int k,long long add){
    push(k);
    if(r<=a||b<=l){
      return -(1LL<<60);
    }else if(a<=l&&r<=b){
      lazy[k]+=add;
      push(k);
      return v[k];
    }else{
      long long vl=query(l,(l+r)/2,a,b,2*k+1,add);
      long long vr=query((l+r)/2,r,a,b,2*k+2,add);
      v[k]=std::max(v[2*k+1],v[2*k+2]);
      return std::max(vl,vr);
    }
  }
  
};

int main(){
  
  std::cin>>N;
  std::cin>>M;
  
  std::vector<int> dst[N];
  std::vector<long long> add[N];
  for(int i=0;i<M;++i){
    int l,r;
    long long a;
    std::cin>>l>>r>>a;
    --l;
    --r;
    dst[r].push_back(l);
    add[r].push_back(a);
  }
  
  segtree seg(N);
  for(int i=0;i<N;++i){
    long long sum=0;
    for(int j=0;j<dst[i].size();++j){
      sum+=add[i][j];
    }
    seg.query(i,i+1,sum+std::max(0LL,seg.query(0,i,0)));
    for(int j=0;j<dst[i].size();++j){
      seg.query(dst[i][j],i,add[i][j]);
    }
  }

  std::cout<<std::max(0LL,seg.query(0,N,0))<<std::endl;


  return 0;
}


Measured memory_bytes: 33920
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using ll = long long;
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    vector<pair<ll, ll>> rate(n);
    for (int i=0; i<n; i++) {
        cin >> rate.at(i).first >> rate.at(i).second;
    }
    ll a = 1, b = 1;
    for (pair<ll, ll> p : rate) {
        if (a%p.first != 0) {
            a += p.first - a%p.first;
        }
        if (b > a/p.first*p.second) {
            if (b%p.second != 0) {
                b += p.second - b%p.second;
            }
            a = b/p.second*p.first;
        }
        else {
            b = a/p.first*p.second;
        }
    }
    cout << a + b << endl;
    return 0;
}


Measured memory_bytes: 256
import math
N = int(input())
if math.sqrt(N)%1 == 0:
    K = int(math.sqrt(N))
    print(len(str(K)))
else:
    ls1 = []
    for i in range(1,math.ceil(math.sqrt(N))+1):
        if N%i == 0:
            ls1.append(i)
    K = max(ls1)
    A = str(N//K)
    B = str(K)
    print(max(len(A),len(B)))

Measured memory_bytes: 3064
n,k,q = gets.split(' ').map(&:to_i)
array = Array.new(n,k-q)
q.times do |b|
    # クイズのb問目？で正解した人の番号
    a = gets.to_i-1
    array[a] +=1
end
array.each do |d| 
    if d <= 0 
        puts 'No'
    else
        puts 'Yes'
    end
end


Measured memory_bytes: 3196
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], ps[MAXN], nxt[MAXN][3], nxt2[MAXN];
ll dp[MAXN];
string S;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>S;
	n=S.size();
	for (int i=1; i<=n; i++){
		A[i]=(S[i-1]=='b')+1;
		ps[i]=(A[i]+ps[i-1])%3;
	}
	nxt[n+1][0]=nxt[n+1][1]=nxt[n+1][2]=nxt2[n+1]=n+1;
	for (int i=n; i; i--){
		nxt[i][0]=nxt[i+1][0];
		nxt[i][1]=nxt[i+1][1];
		nxt[i][2]=nxt[i+1][2];
		nxt2[i]=nxt2[i+1];
		nxt[i][ps[i]]=i;
		if (1<i && A[i-1]==A[i]) nxt2[i]=i;
	}
	if (nxt2[1]==n+1) kill(1)
	dp[0]=1;
	for (int i=0; i<n; i++){
		dp[i]%=mod;
		if (ps[n]==ps[i] && i) ans=(ans + dp[i])%mod;
		dp[i+1]+=dp[i];
		
		int pos=nxt2[i+1];
		int c=3^A[i+1];
		int j=nxt[pos][(c+ps[i])%3];
//		debug2(i, j)
		dp[j]+=dp[i];
	}
	ans=(ans + dp[n])%mod;
	cout<<ans<<"\n";
	
	return 0;
}


Measured memory_bytes: 6860
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <cmath>

using namespace std;

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

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

  ll N, K;
  cin >> N >> K;
  vector<int> A(N);
  for (auto &x: A) cin >> x;

  vector<set<int> > occurence(200001);
  for (int i = 0; i < N; i++) {
    occurence[A[i]].insert(i);
  }
  set<int> leftoverSet;
  vector<int> leftoverVector;
  int pointer = -1;
  while (true) {
    if (pointer >= 0) {
      int currentNum = A[pointer];
      pointer = *(occurence[currentNum].lower_bound(0)); // find first occurence / next starting point
    }
    pointer++;
    auto it = leftoverSet.find(pointer);
    if (it != leftoverSet.end()) break;
    leftoverSet.insert(pointer);
    leftoverVector.push_back(pointer);
    while (pointer < N) {
      int currentNum = A[pointer];
      auto it = occurence[currentNum].upper_bound(pointer);
      if (it == occurence[currentNum].end()) break;
      else pointer = (*it) + 1;
    }
    if (pointer == N) pointer = -1;
  }
  ll target = 0;
  if (K <= leftoverVector.size()) target = K-1;
  else {
    ll start = 0;
    while (pointer != leftoverVector[start]) start++;
    ll end = leftoverVector.size();
    ll remaining = K - end - 1;
    ll remainder = remaining % (end - start);
    target = start + remainder;
  }

  pointer = leftoverVector[target];
  vector<int> ans;
  while (pointer < N) {
    int currentNum = A[pointer];
    auto it = occurence[currentNum].upper_bound(pointer);
    if (it == occurence[currentNum].end()) {
      ans.push_back(currentNum);
      pointer++;
    }
    else pointer = (*it) + 1;
  }

  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i];
    if (i < ans.size() - 1) cout << " ";
    else cout << endl;
  }

  return 0;
}


Measured memory_bytes: 32116
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(),(a).end()

using namespace std;

ll sum(int a){
  ll temp=(ll)(a-1)*a/2;
  return temp;
}

int main(int argc, char const *argv[]) {
  string A;
  std::cin >> A;
  std::vector<int> counter(26,0);
  int leng=A.size();
  for (size_t i = 0; i < leng; i++) {
    ++counter[A[i]-97];
  }
  ll tt=sum(leng);
  for (size_t i = 0; i < 26; i++) {
    if(counter[i]==0){
      continue;
    }else{
      tt-=sum(counter[i]);
    }
  }

  printf("%lld\n",tt+1);
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
#include<debug.h>
#else
#define db(...) 21
#endif
#define found(m,x) ((m).find(x)!=(m).end())
#define uset unordered_set
#define umap unordered_map
#define a(x) x.begin(),x.end()
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#define input(v,n) for(int i=0;i<n;i++)cin>>v[i]
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pi;

const int nax = 1e5+7;
const int mod = 1e9+7; //1e9+2667
const int inf = numeric_limits<int> :: max();
// ===================== MANASH =================== //

int n,m;
int dp[2001][2001];
vector<pair<int,int>> p;
int maxdp( int s, int e) {

    int i = n - (e-s+1);
    if( i >= n or s > e ) return 0;
    int &ans = dp[s][e];
    if(ans != -1 ) return ans;
    int in = p[i].second;
    int left = p[i].first*(abs(s-in));
    int right = p[i].first*(abs(e-in));
    return ans = max(left+maxdp(s+1,e),right+maxdp(s,e-1));
}
void test() {

    cin >> n;
    p.resize(n);
    for( int i = 0; i < n; i++) {
        cin >> p[i].first;
        p[i].second = i;
    }
    sort(a(p),greater<pair<int,int>>());
    memset(dp,-1,sizeof(dp));
    cout << maxdp(0,n-1);
}

signed main() {

    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    cout<<"Time Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec.\n";
    #endif

    int T = 1;
    //cin >> T;
    while(T--) {
        test();
        cout << "\n";
    }
    return 0;

}

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

int main(){
  int A,B; 
  cin >>A>>B;
  
  int ans=0;
  repeat(i,2){
    if(A>B){
      ans += A;
      A--;
    }else{
      ans += B;
      B--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1 << 29;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
int w,h;
int gx,gy;
void print(vector<vector<int> > map){
  for(int i = 0;i < map.size();i++){
    for(int j =0;j < map[0].size();j++){
      if(map[i][j] == INF)cout << ";" << " ";
      else if(map[i][j] == -1)cout << "%" << " ";
      else cout << map[i][j] << " ";
    }
    cout << endl;
  }
}
int dfs(vector<vector<int> > &map,pair<int,int> c,int cnt){
  int x,y;
  int ans = INF;
  if(cnt >= 10)return ans;
  for(int i = 0;i < 4;i++){
    x = c.first;y = c.second;
    
    //if(map[x+dx[i]][y+dy[i]] == 1)continue;
    while(1){

      if(x+dx[i] < 0 || x+dx[i] >= w || y+dy[i] < 0 || y+dy[i] >= h )break;

      if(map[x+dx[i]][y+dy[i]] == 3){
	return cnt+1;
      }
      if(map[x+dx[i]][y+dy[i]] == 1){
	if(x == c.first && y == c.second)break;
	pair<int,int> tmp(x,y);
	map[x+dx[i]][y+dy[i]] = 0;
	ans = min(dfs(map,tmp,cnt+1),ans);
	map[x+dx[i]][y+dy[i]] = 1;
	break;
      }
      x += dx[i];y += dy[i];
    }
  }
  return ans;
}

int main(){

  while(cin >> w >> h,w || h){
    vector<vector<int> > map(w,vector<int>(h,0));
    pair<int,int> s;
    pair<int,int> g;
    for(int i = 0;i < h;i++){
      for(int j = 0;j < w;j++){
	cin >> map[j][i];
	if(map[j][i] == 2){
	  s.first = j;
	  s.second = i;
	  map[j][i]  = 0;
	}else if(map[j][i] == 3){
	  gx = j;
	  gy = i;
	}
      }
    }
    int ans = dfs(map,s,0);
    if(ans > 10)cout << -1 << endl;
    else cout << ans << endl;
  }
  return 0;
 
}

Measured memory_bytes: 1224
MOD = 10**9+7
n = int(input())
s = input()
dp = [[0 for _ in range(n)] for _ in range(n)]
dp[0] = [1 for _ in range(n)]

def cum_get(lis, l, r):
	if l > r:
		return 0
	else:
		return (lis[r+1] - lis[l]) % MOD

for i in range(n-1):
	cum = [0]
	for j in range(n):
		cum.append(cum[-1] + dp[i][j])
	if s[i] == "<":
		for j in range(n-i):
			dp[i+1][j] = cum_get(cum, 0, j)
	else:
		for j in range(n-i):
			dp[i+1][j] = cum_get(cum, j+1, n-i-1)

print(dp[n-1][0])

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

#define mp make_pair
#define ft first
#define sd second
#define pb push_back

const int maxN=202000;
const int Mod=1e9+7;

int n;
pair<int,int> D[maxN];
int St[maxN],Sm[maxN<<2],L[maxN],R[maxN];
vector<int> Vr[maxN];

void Modify(int x,int l,int r,int p,int key);
int Query(int x,int l,int r,int ql,int qr);
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d%d",&D[i].sd,&D[i].ft);
    sort(&D[1],&D[n+1]);

    for (int i=1,top=0;i<=n;i++){
	int l=1,r=top,pos=i;
	while (l<=r){
	    int mid=(l+r)>>1;
	    if (D[St[mid]].sd>D[i].sd) pos=St[mid],r=mid-1;
	    else l=mid+1;
	}
	L[i]=pos;
	if (top==0||D[i].sd>D[St[top]].sd) St[++top]=i;
    }

    for (int i=n,top=0;i>=1;i--){
	int l=1,r=top,pos=i;
	while (l<=r){
	    int mid=(l+r)>>1;
	    if (D[St[mid]].sd<D[i].sd) pos=St[mid],r=mid-1;
	    else l=mid+1;
	}
	R[i]=pos;
	if (top==0||D[i].sd<D[St[top]].sd) St[++top]=i;
    }

    for (int i=1;i<=n;i++) Vr[L[i]].pb(R[i]);
    Modify(1,0,n,0,1);

    for (int i=1;i<=n;i++){
	sort(Vr[i].begin(),Vr[i].end());
	for (int j=0;j<Vr[i].size();j++){
	    int r=Vr[i][j];
	    Modify(1,0,n,r,Query(1,0,n,i-1,n));
	}
    }
    //for (int i=1;i<=n;i++) cout<<L[i]<<" "<<R[i]<<endl;

    printf("%d\n",Query(1,0,n,n,n));return 0;
}
#define ls (x<<1)
#define rs (ls|1)
void Modify(int x,int l,int r,int p,int key){
    Sm[x]=(Sm[x]+key)%Mod;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (p<=mid) Modify(ls,l,mid,p,key);
    else Modify(rs,mid+1,r,p,key);
    return;
}
int Query(int x,int l,int r,int ql,int qr){
    if (l==ql&&r==qr) return Sm[x];
    int mid=(l+r)>>1;
    if (qr<=mid) return Query(ls,l,mid,ql,qr);
    else if (ql>=mid+1) return Query(rs,mid+1,r,ql,qr);
    else return (Query(ls,l,mid,ql,mid)+Query(rs,mid+1,r,mid+1,qr))%Mod;
}


Measured memory_bytes: 18304
#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>;

const int INF = 1001001001;
int dp[1000005][2];

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  s += '0';
  int n = s.size();
  rep(i,n+1)rep(j,2) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i,n)rep(j,2) {
    int x = s[i]-'0';
    x += j;
    rep(a,10) {
      int ni = i+1, nj = 0;
      int b = a-x;
      if (b < 0) {
        nj = 1;
        b += 10;
      }
      dp[ni][nj] = min(dp[ni][nj], dp[i][j]+a+b);
    }
  }
  int ans = dp[n][0];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 9220
//09
#include<iostream>
#include<algorithm>
#include<utility>

using namespace std;

int main(){
  for(int n,m,a;cin>>n>>m>>a,n|m|a;){
    int l[101];
    for(int i=1;i<=n;i++){
      l[i]=i;
    }
    pair<int,pair<int,int> >c[1000];
    for(int i=0;i<m;i++){
      int h,p,q;
      cin>>h>>p>>q;
      c[i]=make_pair(h,make_pair(p,q));
    }
    sort(c,c+m);
    for(int i=0;i<m;i++){
      swap(l[c[i].second.first],l[c[i].second.second]);
    }
    cout<<l[a]<<endl;
  }
  return 0;
}

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

bool asc(const vector<int> &v1, const vector<int> &v2) {
	if (v1[1] < v2[1]) {
		return true;
	} else if (v1[1] > v2[1]) {
		return false;
	} else {
		if (v1[2] < v2[2]) {
			return true;
		} else {
			return false;
		}
	}
}

bool id_asc(const vector<int> &v1, const vector<int> &v2) {
	return v1[0] < v2[0];
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<int> > v(M);
	for (int i = 0; i < M; i++) {
		int p, y;
		cin >> p >> y;
		v[i].push_back(i);
		v[i].push_back(p);
		v[i].push_back(y);
	}
	sort(v.begin(), v.end(), asc);

	v[0][3] = 1;
	int id = 2;
	for (int i = 1; i < M; i++) {
		if (v[i-1][1] != v[i][1]) {
			id = 1;
		}
		v[i][3] = id;
		id++;
	}

	sort(v.begin(), v.end(), id_asc);

	for (int i = 0; i < M; i++) {
		printf("%06d", v[i][1]);
		printf("%06d\n", v[i][3]);
	}
}


Measured memory_bytes: 7040
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;
int const DEV = 2019;

int main() {
  string s;
  cin >> s;
  ll n = s.size();

  ll cursor = 0;
  vector<ll> cnt(DEV, 0);
  cnt[cursor]++;
  ll factor = 1;

  rep(i, n) {
    cursor += (s[n-1-i] - '0') * factor;
    factor = factor * 10 % DEV;
    //cout << cursor << " " << cursor % DEV <<  endl;
    cnt[cursor % DEV]++;
  }

  ll ans = 0;

  rep(i, DEV) {
    ans += cnt[i] * (cnt[i]-1) / 2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3748
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	static final int INF = (int)1e9 + 7;
	ArrayList<Edge>[] G;
	boolean[] used;

	class Edge{
		int to,cap,rev;
		public Edge(int to,int cap,int rev){
			this.to = to;
			this.cap = cap;
			this.rev = rev;
		}
	}

	public void addEdge(int from,int to,int cap){
		G[from].add(new Edge(to,cap,G[to].size()));
		G[to].add(new Edge(from,0,G[from].size()-1));
	}

	public int dfs(int v,int t,int f){

		if(v == t)return f;

		used[v] = true;
		for(int i = 0;i < G[v].size();i++){

			Edge e = G[v].get(i);

			if(!used[e.to] && e.cap > 0){
				int d = dfs(e.to,t,Math.min(f, G[v].get(i).cap));
				if(d > 0){

					e.cap -= d;
					G[e.to].get(e.rev).cap += d;
					return d;
				}
			}

		}

		return 0;
	}

	public int max_flow(int s,int t){
		int flow = 0;
		for(;;){

			Arrays.fill(used, false);
			int f = dfs(s,t,INF);
			if(f == 0)return flow;
			flow += f;
		}
	}

	int V,E;

	@SuppressWarnings("unchecked")
	public void solve() {
		V = nextInt();
		E = nextInt();

		G = new ArrayList[V];
		for(int i = 0;i < V;i++){
			G[i] = new ArrayList<Edge>();
		}
		used = new boolean[V];

		for(int i = 0;i < E;i++){

			int u = nextInt();
			int v = nextInt();
			int c = nextInt();

			addEdge(u,v,c);
		}

		out.println(max_flow(0,V-1));
	}

	public static void main(String[] args) {
		new Thread(null,new Main(),"",32 * 1024 * 1024).start();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

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

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

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

	@Override
	public void run() {
		out.flush();
		new Main().solve();
		out.close();

	}
}

Measured memory_bytes: 26592
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>
#include <bitset>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int C[210000];

int main(){
	int N;
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> C[i];
	}
	sort(C, C + N);
	long long int p4 = 1;
	for(int i = 0; i < N - 1; i++){
		p4 *= 4;
		p4 %= MOD;
	}
	long long int ans = 0;
	for(int i = 0; i < N; i++){
		ans += C[i] * p4 % MOD * (N - i + 1) % MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9 + 7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
#ifdef LOCAL
#define debug(x) cerr << #x << ": " << x << endl
#else
#define debug(x)
#endif
int dx[4] ={ 1,0,-1,0 };
int dy[4] ={ 0,1,0,-1 };

int N, M;
ll a[1000];
int b[1000], c[1000][12];

ll dp[1000][(1<<12)+1];
ll solve(int now, int state){
	if(now == M){
		if(state == 0) return 0LL;
		else return 1000000000LL;
	}
	if(dp[now][state] != -1) return dp[now][state];
	ll ret = solve(now+1, state);
	int state2 = state;
	rep(i, b[now]){
		state2 &= ((1<<12)-1) - (1<<c[now][i]);
	}
	ret = min(ret, solve(now+1, state2)+a[now]);
	return dp[now][state] = ret;
}

signed main() {
	cin >> N >> M;
	rep(i, M){
		cin >> a[i] >> b[i];
		rep(j, b[i]){
			cin >> c[i][j];
			c[i][j]--;
		}
		rep(j, (1<<12)){
			dp[i][j] = -1;
		}
	}
	ll ans = solve(0, (1<<N)-1);
	if(ans >= 1000000000LL) cout << -1 << endl;
	else cout << ans << endl;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> vec(n);
    rep(i,n) cin >> vec[i];
    int cnt=0;
    for(int i=0;i<n;i++){
        if(vec[i]!=i+1) ++cnt;
    }
    if(cnt<=2) cout << "YES" << endl;
    else cout << "NO" << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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; }
const ll MOD = 1e9+7;

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> M;
    vector<ll> P;
    bool zero = false;
    REP(i,N){
        ll a;
        cin >> a;
        if(a == 0)
            zero = true;
        if(a < 0)
            M.push_back(-a);
        else
            P.push_back(a);
    }

    ll MS = M.size();
    ll PS = P.size();

    ll ans = 1;

    if(N == K){
        for(auto&& x : M)
            ans = (ans * x) % MOD;
        for(auto&& x : P)
            ans = (ans * x) % MOD;
        if(MS % 2)
            ans = MOD - ans;
        ans %= MOD;
    }
    // positive
    else if(!(MS == N && K % 2)){
        if(K == 2 && MS == 1 && PS == 1){
            ans *= P[0];
            ans %= MOD;
            ans *= M[0];
            ans %= MOD;
        }
        else{
            sort(M.rbegin(), M.rend());
            sort(P.rbegin(), P.rend());
            P.push_back(-1);

            int num = K;
            int pidx = 0;
            int midx = 0;
            while(num > 0){
                if(num == 1 || (MS - midx) < 2){
                    ans *= P[pidx];
                    ans %= MOD;
                    pidx++;
                    num--;
                }
                else{
                    ll mmul = M[midx] * M[midx+1];
                    ll pmul = P[pidx] * P[pidx+1];
                    if(mmul >= pmul){
                        ans *= (mmul % MOD);
                        ans %= MOD;
                        midx += 2;
                        num -= 2;
                    }
                    else{
                        ans *= P[pidx];
                        ans %= MOD;
                        pidx++;
                        num--;
                    }
                }
            }
        }
    }
    //negative
    else{
        if(zero) ans = 0;
        else{
            priority_queue<ll, vector<ll>, greater<ll>> que;
            for(auto&& x : M)
                que.push(x);
            for(auto&& x : P)
                que.push(x);
            REP(i,K){
                auto x = que.top();
                que.pop();
                ans *= x;
                ans %= MOD;
            }

            ans = MOD - ans;
            ans %= MOD;
        }
    }

    cout << ans << endl;

    return 0;
}


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

typedef long long ll;

ll cou;

void merge(vector<ll> &v,ll l,ll r){
    ll mid = (r+l)/2;
    ll n1 = mid-l;
    ll n2 = r-mid;
    vector<ll> a,b;
    for(ll i=0;i<n1;i++)a.push_back(v[l+i]);
    for(ll i=0;i<n2;i++)b.push_back(v[mid+i]);
    a.push_back(1e9);
    b.push_back(1e9);
    ll aa=0,bb=0;
    for(ll i=l;i<r;i++){
        if(a[aa]<b[bb]){
            v[i]=a[aa++];
        }else{
            v[i]=b[bb++];
            cou+=n1-aa;
        }
    }
}
void merge_sort(vector<ll> &v,ll l,ll r){
    if(r-l>1){
        ll mid = (r+l)/2;
        merge_sort(v,l,mid);
        merge_sort(v,mid,r);
        merge(v,l,r);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++)cin >> a[i];
    merge_sort(a,0,n);
    cout << cou << endl;
}



Measured memory_bytes: 6728
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
  cin>>s;
  int N=s.size();
  int Min=0;
  int Max=N-1;
  for(int i=0;i<N;i++)
  if(s.at(i)=='A'){
  Min=i; break;
  }
  for(int i=N-1;0<i;i--)
    if(s.at(i)=='Z'){
    Max=i; break;
    }
  int ans=Max-Min+1;
  cout<<ans<<endl;
  
 
   return 0;
}

Measured memory_bytes: 640
void main() {
	auto ip = readAs!(int[]), n = ip[0], q = ip[1];
	int[string] jobs;
	int[string] res;
	string[] res_order;
	string[] queue;
	int current;

	foreach(i; 0..n) {
		auto ip2 = readln.split, name = ip2[0], time = ip2[1].to!int;
		jobs[name] = time;
		queue ~= name;
	}

	while(!queue.empty) {
		auto p = queue.front;
		queue.popFront;
		auto t = jobs[p];
		if(t <= q) {
			res[p] = current += t;
			res_order ~= p;
		} else {
			queue ~= p;
			jobs[p] -= q;
			current += q;
		}
	}
	foreach(i; res_order) {
		"%s %d".writefln(i, res[i]);
	}
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 18984
#include<stdio.h>

typedef struct{
  char kigo;
  int num;
} C;

int main(){
  C A[36],B[36],tmp;
  int i,j,N,mini,c=0;
  scanf("%d",&N);
  for(i=0;i<N;i++)scanf(" %c%d",&A[i].kigo,&A[i].num);
  for(i=0;i<N;i++)B[i]=A[i];
//bubble
  for(i=0;i<N;i++){
    for(j=N-1;j>i;j--){
      if(A[j].num<A[j-1].num){
        tmp=A[j];
        A[j]=A[j-1];
        A[j-1]=tmp;
      }
    }
  }
  for(i=0;i<N-1;i++) printf("%c%d ",A[i].kigo,A[i].num);
  printf("%c%d\n",A[N-1].kigo,A[N-1].num);
  printf("Stable\n");
//selection
   for(i=0;i<N-1;i++){
    mini=i;
    for(j=i;j<N;j++){
      if(B[j].num<B[mini].num) mini=j;
    }
    tmp=B[i];
    B[i]=B[mini];
    B[mini]=tmp;
  }

   for(i=0;i<N-1;i++) printf("%c%d ",B[i].kigo,B[i].num);
   printf("%c%d\n",B[N-1].kigo,B[N-1].num);

   for(i=0;i<N;i++){
     if(A[i].kigo!=B[i].kigo||A[i].num!=B[i].num){
       printf("Not stable\n");
       return 0;
     }
   }
   printf("Stable\n");

   return 0;
}





Measured memory_bytes: 2084
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, a, b) for(int i = a; i >= b; --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const int INF = 1e9;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;


vector<P> edges[100010];
bool reached[100010];
int dp[100010];
int main() {
    int n;
    cin >> n;
    FOR(i, 0, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; w%=2;
        edges[u].push_back(make_pair(v, w));
        edges[v].push_back(make_pair(u, w));
    }
    reached[0] = true;
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int current_node = q.front();
        q.pop();
        for(P child : edges[current_node]) {
            if(reached[child.first]) continue;
            reached[child.first] = true;
            q.push(child.first);
            dp[child.first] = dp[current_node] ^ child.second;
        }
    }
    REP(i, n) cout << dp[i] << endl;
}

Measured memory_bytes: 6912