akhauriyash/Code-Regression huggingface dataset:
//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
}

//end of jonathanirvings' template v3.0.3 (BETA)

string s;
int k;

int main()
{
  s = GetString();
  scanf("%d",&k);
  REP(i,SIZE(s))
  {
    if (s[i] == 'a') continue;
    int x = 'z' + 1 - s[i];
    if (x <= k)
    {
      k -= x;
      s[i] = 'a';
    }
  }
  int t = (s[SIZE(s) - 1] - 'a' + k) % 26;
  s[SIZE(s) - 1] = (t + 'a');
  printf("%s\n",s.c_str());
  return 0;
}










Measured memory_bytes: 512
#include <bits/stdc++.h>
#define lol long long
template<class A,class B>inline bool chmax(A &a,const B &b){return(b>a&&(a=b,true));}
template<class A,class B>inline bool chmin(A &a,const B &b){return(b<a&&(a=b,true));}
using namespace std;
lol mod=1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;cin >>n;
  vector<int> a(n),b(n);
  for(int i=0;i<n;i++) cin >>a[i];
  b=a;
  sort(b.begin(),b.end());
  set<int> s;
  for(int i=0;i<n;i+=2){
    s.insert(b[i]);
  }
  int ans=0;
  for(int i=0;i<n;i+=2){
    if(s.find(a[i])==s.end()) ans++;
  }
  cout <<ans<<'\n';
  return (0);
}

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

int main(){
    int D,G;
    cin >> D >> G;
    vector<int> p(D+1), c(D+1);
    for(int i=1; i<=D; i++){
        cin >> p.at(i) >> c.at(i);
    }

    int ans = 1e9;
    for(int mask=0; mask<(1 << D); mask++){
        int score = 0, rest_max = 0, num = 0;;
        for(int i=1; i<=D; i++){
            if(mask >> (i-1) & 1){
                score += 100 * i * p.at(i) + c.at(i);
                num += p.at(i);
            }else{
                rest_max = i;
            }
        }
        if(score < G){
           int score_tmp = 100 * rest_max;
           int need = (G - score - 1)/score_tmp + 1;
           if(need > p.at(rest_max)) continue;
           num += need;
        }
        ans = min(ans, num);
    }
    cout << ans << endl;
}

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

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repp(i, n, m) for(int (i) = (n); (i) < (m); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long
#define ldou long double
#define fi first
#define se second
#define setpre(x) std::cout << fixed << setprecision(x)
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define out(x) cout << (x) << endl
#define outs(x) cout << (x) << " "
#define yn(x) cout << ((x)?("Yes"):("No")) << endl
#define YN(x) cout << ((x)?("YES"):("NO")) << endl
#define bit_c(x) __builtin_popcountll(x)

inline void logger(){ std::cout << " [LOGGER] " << endl; }
template<typename A, typename... B>
void logger(const A& a, const B&... b){
    cout << a << " , ";
    logger(b...);
}

typedef pair<lint, lint> P;
const lint MOD = 1000000007;
const lint MOD9 = 998244353;
const lint INF = MOD * MOD;
const int MAX = 405;

/* ...o(^-^)o... */
int n;
lint dp[MAX][MAX];
lint sum[MAX];

lint rec(int i, int j){
    if(dp[i][j] > 0) return dp[i][j];
    if(i+1 == j) return 0;
    lint res = INF;
    repp(k, i+1, j) res = min(res, rec(i, k)+rec(k, j));
    res += sum[j] - sum[i];
    dp[i][j] = res; return res;
}

int main(){
    cin >> n;
    vector<lint> a(n); rep(i, n) cin >> a[i];
    
    rep(i, n) sum[i+1] = sum[i] + a[i];

    out(rec(0, n));
}


Measured memory_bytes: 1536
N, A, B = map(int, input().split())

x = N // (A + B)

ans = 0
if x == 0:
    if N > A:
        ans = A
    else:
        ans = N
else:
    if N - (A + B)*x > A:
        ans = A * (x + 1)
    else:
        ans = N - B * x

print(ans) 

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

ll n,a[200000],sum,x,ans;

int main(){
    cin>>n;
    rep(i,n)cin>>a[i];
    rep(i,n){
        while(x<n&&(sum^a[x])==sum+a[x]){
            sum+=a[x];
            x++;
        }
        ans+=x-i;
        sum^=a[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int main() {
string s;
cin>>s;
int a=0;
int b=0;
int n=s.size();
int c[n]={};
char w;
int p=0;
if(n!=26){
for(int i=0; i<n; i++){
c[i]=s.at(i)-'a'+1;}
sort(c,c+n);
for(int i=0; i<n; i++){
if(c[i]!=i+1){
a=i;
p++;
break;
}}
if(p==0){
a=n;}
char q=a+'a';
s+=q;
cout<<s<<endl;}
else{
for(int i=0; i<n; i++){
c[i]=s.at(i)-'a';}
for(int i=0; i<n; i++){
if(c[n-2-i]<c[n-1-i]){
a=n-1-i;
b=1;
break;}}
if(b!=1){
cout<<-1<<endl;}
else{
b=10000;
for(int k=a; k<n; k++){
if(c[a-1]<c[k]){
b=min(b,c[k]);}
}
w=b+'a';
for(int i=0; i<a-1; i++){
cout<<s.at(i);}
cout<<w<<endl;}}}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<ll> vvll;
#define sort(v) sort(v.begin(), v.end())
#define rev(r) reverse(r.begin(), r.end());
#define cout(cc) cout << cc << endl;
int main() {
  double N,tax,max,aaa;
  cin >> N;
  vll VV(N);
  aaa=1;
  rep(i,N){
  	cin >> VV.at(i);
    aaa*=VV.at(i);
  }
  auto BB=VV;
  rep(i,N){
  	auto BB=VV;
    BB.at(i)=1;
    max=1;
    rep(j,N){
      max*=BB.at(j);
    }
    tax+=max;
  }
  cout << aaa/tax << endl;
}


Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Scanner;


public class Main {

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

		n = 16;

		char[] s = new char[n];
		for (int i = 0; i < n; i++) {
			s[i] = (char)('0' + sc.nextInt());
		}
		
		ans = "123456789:;<=>?0";

		for (int i = 0; i < 46; i++) {
			hm = new HashMap<String, Integer>();
			limit = i;
			dfs(new Panel(toString(s), 0));
		}
		
        sc.close();
	}

	private static void dfs(Panel u) {
		if (u.s.equals(ans)) {
			System.out.println(u.count);
			System.exit(0);
		}
		
		if (u.count + u.min > limit) {
			return;
		}

		hm.put(u.s, u.count);
//		System.out.println(u + k);

		StringBuffer str = new StringBuffer(u.s);
		
		int zero = str.indexOf("0");
		assert (zero != -1);
		for (int i = 0; i < d.length; i++) {
			if (zero + d[i] >= 0 && zero + d[i] < n && !(d[i] == -1 && (zero + d[i]) % 4 == 3) && !(d[i] == 1 && (zero + d[i]) % 4 == 0)) {
				str.setCharAt(zero, str.charAt(zero + d[i]));
				str.setCharAt(zero + d[i], '0');
				String tmps = str.toString();
				if (!hm.containsKey(tmps) || hm.get(tmps) > u.count + 1) {
					dfs(new Panel(tmps, u.count + 1));
				}
				str.setCharAt(zero + d[i], str.charAt(zero));
				str.setCharAt(zero, '0');
			}
		}
	}

	private static int n;
	private static int limit;
	private static String ans;
	private static final int[] d = {4, -4, -1, 1};
	
	private static HashMap<String, Integer> hm;

	private static class Panel {
		String s;
		int count;
		int min;
		
		Panel (String s, int count) {
			this.s = s;
			this.count = count;
			this.min = getMin(s);
		}
		
		private int getMin(String s) {
			char[] c = s.toCharArray();
			int ret = 0;
			for (int i = 0; i < c.length; i++) {
				int tmp = c[i] - '0';
				if (tmp != 0) {
					int x = (tmp - 1) % 4;
					int y = (tmp - 1) / 4;
					ret += Math.abs(x - i % 4) + Math.abs(y - i / 4);
				}
			}
			
			return ret;
		}

	}

	private static String toString(char[] s) {
		String ret = "";
		for (int i = 0; i < s.length; i++) {
			ret += s[i];
		}
		
		return ret;
	}
}

Measured memory_bytes: 339924
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
#include <queue>
#define enter putchar('\n')
#define space putchar(' ')
//#define ivorysi
#define pb push_back
#define mo 974711
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define MAXN 500005
#define eps 1e-12
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 - '0' + c;
	c = getchar();
    }
    res = res * f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) out(x / 10);
    putchar('0' + x % 10);
}
int N;
int64 A[100005],tmp[100005],sum[1000005];
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
	read(A[i]);
	tmp[i] = A[i];
    }
    tmp[N + 1] = 1000000001;
    sort(tmp + 1,tmp + N + 2);
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
	sum[i] = sum[i - 1] + tmp[i]; 
    }
    for(int i = 1 ; i <= N ; ++i) {
	if(2 * A[i] >= tmp[N]) {++ans;continue;}
	int t = lower_bound(tmp + 1,tmp + N + 2,2 * A[i] + 1) - tmp - 1;
	while(1) {
	    if(2 * sum[t] >= tmp[N]) {++ans;break;}
	    int p = lower_bound(tmp + 1,tmp + N + 2,sum[t] * 2 + 1) - tmp - 1;
	    if(p == t) break;
	    t = p;
	}
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }



int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans=0;
	cin >>n;
	
	rep2(i, 1, n+1){
		int c= i, p=0;
		while(c>0){
			c/=10; p++;
		}
		if(p&1) ans++;
	}
	cout <<ans <<"\n";
	return 0;
}


Measured memory_bytes: 256
x,y,a,b,c = map(int ,input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p = p[:x]
q = q[:y]

pqr = p + q + r
pqr.sort(reverse=True)

yamm = sum(pqr[:x+y])
print(yamm)

Measured memory_bytes: 23328
N,C=map(int, input().split())
A=[list(map(int, input().split())) for _ in range(N)]
D=[[] for i in range(C)]
DD=[[] for i in range(C)]
for s,t,c in A:
  D[c-1].append([s,t])
for i in range(C):
  E=sorted(D[i])
  e=len(E)
  for j in range(e):
    if j==0:
      DD[i].append([E[j][0],E[j][1]])
    elif j!=0 and E[j][0]==E[j-1][1]:
      DD[i][-1][-1]=E[j][1]
    else:
      DD[i].append([E[j][0],E[j][1]])
ANS=[0]*(10**5+3)
for i in range(C):
  F=DD[i]
  for i,j in F:
    ANS[i]+=1
    ANS[j+1]-=1
ans=0
d=0
for i in ANS:
  d+=i
  ans=max(d,ans)
print(ans)

Measured memory_bytes: 47688
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned


using namespace std;
const ll maxn=1e5; 
string a[maxn];
int main(){
	int t;
	scanf("%d",&t);
	int acnum=0,wanum=0,tlenum=0,renum=0;
	for (int i=0;i<t;i++){
		cin>>a[i];
	}
	for (int i=0;i<t;i++){
		
		if(a[i]=="AC"){
			acnum++;
		}
		else if(a[i]=="WA"){
			wanum++;
		}
		else if(a[i]=="TLE"){
			tlenum++;
		}
		if(a[i]=="RE"){
			renum++;
		}
	}
	cout<<"AC x " <<acnum<<endl<<"WA x "<<wanum<<endl<<"TLE x "<<tlenum<<endl<<"RE x "<<renum<<endl;
	return 0;
}


Measured memory_bytes: 6888
unittest
{
	assert( [ "7 3" ].parse.expand.solve == 1 );
	assert( [ "100 10" ].parse.expand.solve == 0 );
	assert( [ "1 1" ].parse.expand.solve == 0 );
}



import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nk = input.front.split.to!( int[] );
	
	return tuple( nk[ 0 ], nk[ 1 ] );
}

auto solve( in long n, in long k )
{
	if( n % k == 0 ) return 0;
	else             return 1;
}


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

#define ll long long
const ll mod = 1e9 + 7;
bool flaggy[25][25];
const int nax = (1<<21) + 2;

ll dp[nax][25];
ll brute(int i, vector<int> &bitmask){
	if(i >= bitmask.size())
		return 1;
	ll res = 0;
	if(dp[bitmask[i]][i] != -1)
		return dp[bitmask[i]][i];
	for(int j = 0; j<bitmask.size(); j++){
		
		
		if(bitmask[i] & 1<<j || flaggy[i][j])
			continue;
		for(unsigned int k = i; k<bitmask.size(); k++){
			//~if(!flaggy[k][j])
				bitmask[k] = bitmask[k] | 1<<j;
			}
		res = (res + brute(i+1, bitmask))%mod;
		for(unsigned int k = i; k<bitmask.size(); k++){
			//~if(!flaggy[k][j])
				bitmask[k] = bitmask[k] ^ 1<<j;
			}
			
		}
		//~cout << res << endl;
		return dp[bitmask[i]][i] = res%mod;
	}
 

int main(){
	int n;
	cin>>n;
	memset(dp, -1, sizeof(dp));
	vector<int> bitmask (n, 0);
	
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
			char ch; 
			cin>>ch;
			if(ch == '0')
				flaggy[j][i] = 1;
			else
				flaggy[j][i] = 0;
			}
		}
	//~for(int i = 0; i<bitmask.size(); i++)
		//~cout << bitmask[i] << endl;
	cout << brute(0, bitmask);
	//~cout << dp[bitmask[1]][1] << endl;
	
	return 0;
	}


Measured memory_bytes: 409856
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
 
Node root;
 
Node treeMinimum(Node x){
}
 
Node treeMaximum(Node x){
}
 
Node treeSearch(Node u, int k){
  while(u!=NIL && k!=u->key){
    if(k<u->key)
      u=u->left;
    else
      u=u->right;
  }
  return u;
}
 
Node treeSuccessor(Node x){
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
}
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x!=NIL){
    y=x;
    if(z->key<x->key)
      x=x->left;
    else
      x=x->right;
  }
  z->parent=y;
   
 
  if(y==NIL)
    root=z;
  else if(z->key < y->key)
    y->left = z;
  else
    y->right = z;
 
}
 
void inorder(Node u){
  if(u==NIL)
    return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
 
}
void preorder(Node u){
  if(u==NIL)
    return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}
 
 
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
 
  return 0;
}

Measured memory_bytes: 19364
#include <stdio.h>

#define MAX (20)

int main(){

    int a, b;    

    // 値の入力
    scanf("%d %d", &a, &b);

    if((b%a) == 0){
        printf("%d", a+b);
    }
    else{
        printf("%d", b-a);
    }

}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#define REP(i,n) for (int i=0;i<(n);++i)
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr int INF = 1 << 30;

ll n, x, l;
pair<ll, ll> ps[100010];

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  REP(i, n) {
    cin >> x >> l;
    ps[i].first = x + l;
    ps[i].second = x - l;
  }
  sort(ps, ps + n);
  ll ans = 0, pos = -(1 << 30);
  REP(i, n) {
    if (pos <= ps[i].second) {
      ++ans;
      pos = ps[i].first;
    }
  }

  cout << ans;
  return 0;
}


Measured memory_bytes: 1792
<?php
define("MOD", 10**9+7);
fscanf(STDIN, "%d%d", $n, $k);
$A = array_map("intval", explode(" ", fgets(STDIN)));
sort($A);
prepareMod($n);
$ans = 0;
foreach($A as $i => $a){
    if($n-$i-1 >= $k-1){
        $ans = ($ans - $a * nCm($n-$i-1, $k-1))%MOD;
    }
}
$A = array_reverse($A);
foreach($A as $i => $a){
    if($n-$i-1 >= $k-1){
        $ans = ($ans + $a * nCm($n-$i-1, $k-1))%MOD;
    }
}
echo (($ans%MOD)+MOD)%MOD;

function prepareMod($n){
    global $f, $invf;
    $f[0] = $invf[0] = $invf[1] = 1;
    for($i = 1; $i <= $n; $i++)$f[$i] = $f[$i-1]*$i%MOD;
    for($i = 2; $i <= $n; $i++)$invf[$i] = (MOD - intdiv(MOD, $i))*$invf[MOD%$i]%MOD;
    for($i = 2; $i <= $n; $i++)$invf[$i] = $invf[$i]*$invf[$i-1]%MOD;
}
function nCm($n, $m){
    global $f, $invf;
    return $f[$n] * $invf[$n-$m] % MOD * $invf[$m] % MOD;
}

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

#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=810;
const int z[5][4]={{0,1},{0,-1},{1,0},{-1,0}};

int n;
double s;

int main(){
	n=rd();
	rep(i,1,n) s+=1.0/rd();
	s=1/s;
	printf("%.6lf\n",s);
}









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

using namespace std;

int main()
    {
    	int h[2],s[2];
    	
    	cin>>h[0]>>s[0]>>h[1]>>s[1];
    	
    	for(int i=0;i>=0;i++)
    	    {
    	    	h[1]-=s[0];
    	    	if(h[1]<=0)
    	    	 {
				   cout<<"Yes";
				   break;
			     }
    	    	  
    	    	h[0]-=s[1];
    	    	if(h[0]<=0)
    	    	  {
    	    	  	cout<<"No";
    	    	  	break;
				  }
    	    	 
			}
    	
    	return 0;
    	    
	}

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

int main()
{
	string s;
	cin >> s;
	rep(i, s.size())
		s[i] = 'x';
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
/*
AuThOr Gwj
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define debug_pair(A) cerr<<A.FIR<<" "<<A.SEC<<endl;
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int ap[1000000+20],n,a[200000+20];
int main(){
	fastio;
	cin>>n;
	rb(i,1,n) {
		cin>>a[i];
		
	}
	sort(a+1,a+1+n);
	rb(i,1,n){
		if(a[i]==a[i-1]){
			ap[a[i]]=1;
		}
	}
	int res=0;
	rb(i,1,n){
		if(!ap[a[i]])
			res++;
		if(a[i]!=a[i-1]){
			for(int j=2*a[i];j<=1000000;j+=a[i]){
				ap[j]=1;
			}
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 8384
def submit():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    modp = 10 ** 9 + 7
    dp = [[0 for _ in range(w)] for _ in range(h)]
    dp[0][0] = 1
    for i in range(h):
        for j in range(w):
            dp[i][j] %= modp
            if i + 1 < h and a[i + 1][j] == ".":
                dp[i + 1][j] += dp[i][j]
            if j + 1 < w and a[i][j + 1] == ".":
                dp[i][j + 1] += dp[i][j]
    print(dp[h - 1][w - 1])


submit()
            


Measured memory_bytes: 90844
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    A,B,K=map(int,input().split())
    ans=A-K if A-K>0 else 0
    ans2=B-(K-A if K-A >0 else 0)
    ans2=ans2 if ans2>0 else 0
    print(str(ans)+' '+str(ans2))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
N = int(input())
cards = {"S":list(range(1,14)),"H":list(range(1,14)),"C":list(range(1,14)),"D":list(range(1,14))}
# print(cards)
for n in range(N):
    a,b=input().split()
    cards[a].remove(int(b))
# print(cards)

for k in cards.keys():
    for v in cards[k]:
        print(k,v)


Measured memory_bytes: 5600
from functools import lru_cache


N, M = map(int, input().split())
E = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

S = 1
G = (1 << N) - 1


@lru_cache(2**N*N)
def is_visited(v, path):
    return path & (1 << v)


@lru_cache(2**N*N)
def count(u, path):
    if path == G:
        return 1

    return sum(
        count(v, path ^ (1 << v))
        for v in E[u]
        if not is_visited(v, path)
    )


print(count(0, S))


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

int show_list(map<long, int> &m)
{
    cout << "list: ";
    for(auto itr = m.begin(); itr != m.end(); itr++) {
        for(int i = 0; i < itr->second; i++) {
            cout << itr->first << " ";
        }
    }
    cout << endl;
}

int main()
{
    int N, tmp;
    int d = 0;
    map<long, int> m;
    int ans = 0;

    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> tmp;
        m[tmp]++;
    }

    for(auto itr = m.rbegin(); itr != m.rend(); itr++) {
        //show_list(m);
        long v = itr->first;
        //cout << "v: " << v << endl;
        for(int t = 1; t <= 32; t++) {
            long val = pow(2, t);
            //cout << "val = " << val << endl;
            if(v <= val && val < v * 2) {
                while(m.find(v) != m.end() && m[v] > 0 && m.find(val - v) != m.end() && m[val - v] > 0) {
                    //cout << "hit = " << v << ", " << val - v << endl;
                    m[val - v]--;
                    m[v]--;
                    ans++;
                }
            } else if(val == v * 2) {
                while(m.find(v) != m.end() && m[v] > 1) {
                    //cout << "hit = " << v << ", " << v << endl;
                    m[v] -= 2;
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 12800
def bubbleSort(A, N):
    flag = 1
    cnt = 0
    while flag:
        flag = 0
        for j in range(N - 1, 0, -1):
            if A[j] < A[j - 1]:
                cnt += 1
                A[j], A[j - 1] = A[j - 1], A[j]
                flag = 1
    print(*A)
    print(cnt)
N = int(input())
A = list(map(int, input().split()))
bubbleSort(A, N)


Measured memory_bytes: 5608
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main(){
    ll N;
    cin >> N;
    vector<ll> ans;
    ll sum = 0;
    if(N == 3){
        cout << "2 5 63\n";
        return 0;
    }else if(N == 4){
        cout << "2 5 20 63\n";
        return 0;
    }
    for(ll k = 0; ans.size() < N; k++){
        for(ll j : {2, 3, 4, 6}){
            if(ans.size() >= N) break;
            ans.push_back(6 * k + j);
            sum += 6 * k + j;
            sum %= 6;
        }
    }
    ll las = ans.size() - 1;
    if(sum == 2){
        if(ans[las] % 6 == 2) ans[las] += 4;
        else ans[las - 1] += 4;
    }else if(sum == 3){
        if(ans[las] % 6 == 0) ans[las] += 3;
        else ans[las - 1] += 3;
    }else if(sum == 5){
        ans[las]++;
    }
    for(ll i = 0; i < ans.size(); i++) cout << ans[i] << " \n"[i == ans.size() - 1];
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
 int n,k,x,y;
 cin >> n >> k >> x >> y;
 if(n>k){
  cout << k*x+(n-k)*y << endl;
 }else{
  cout << n*x << endl;
 }
 return 0;
}

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

int main(){
  int n,m,k,t,ans=0;cin>>n>>m;
  vector<int> x(m,0);
  REP(i,n){
    cin>>k;
    REP(j,k){
      cin>>t;
      x.at(t-1)++;
    }
  }
  REP(i,m) if(x.at(i)==n) ans++;
  cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <cctype>
#include <fstream>
#include <cstring>

using namespace std;

#define ll long long
#define MOD 1000000007
#define INF 2000000000
#define LINF 9000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define du(x) cout<<#x<<'='<<x<<endl
#define du2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define du3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl
#define ddarr(arr,a,b) rep(i,a){rep(j,b){cout<<*(arr+i*b+j)<<' ';}cout<<endl;}
#define ddd ifstream in("Text.txt");cin.rdbuf(in.rdbuf());


ll A[100000];

int main() {
    ll N;
    cin >> N;
    rep(i, N)cin >> A[i];

    ll cnt = 0;
    rep(i, N) {
        if (A[i] < 0)cnt++;
        A[i] = abs(A[i]);
    }


    sort(A, A + N);


    ll ans = 0;
    if (cnt % 2 == 0) {
        rep(i, N)ans += A[i];

    }
    else {
        rep(i, N) {
            ans += A[i];
        }
        ans -= A[0]*2;
    }

    cout << ans << endl;;
}

Measured memory_bytes: 1024
n = int(raw_input())

def makeHash(letter):
    if letter == 'A':
        return 1
    elif letter == 'C':
        return 2
    elif letter == 'G':
        return 3
    elif letter == 'T':
        return 4
    return 0

dict = {}
for i in range(n):
    command, word = raw_input().split()
    key = 0
    if command == 'insert':
         dict[word] = 1
    elif command == 'find':
        if word in dict: 
            print 'yes'
        else:
            print 'no'
        

Measured memory_bytes: 64856
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int w = sc.nextInt();
		int[] ints = new int[w];
		for (int i=0; i<w; i++) {
			ints[i] = i+1;
		}
		int n = sc.nextInt();
		String[] strs = new String[2];
		for (int i=0; i<n; i++) {
			strs = sc.next().split(",");
			int L = Integer.parseInt(strs[0]) - 1;
			int R = Integer.parseInt(strs[1]) - 1;
			int temp = ints[L];
			ints[L] = ints[R];
			ints[R] = temp;
		}
		for (int i=0; i<w; i++) {
			System.out.println(ints[i]);
		}
	}
}


Measured memory_bytes: 26300
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	} 
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	m := scanInt()
	as := scanInts(n)

	sum := make([]int, n+1)

	for i := 0; i < n; i++ {
		sum[i+1] = sum[i] + as[i]
		sum[i+1] %= m
	}

	cnt := map[int]int{}
	ans := 0

	for i := 0; i < n+1; i++ {
		ans += cnt[sum[i]]
		cnt[sum[i]]++
	}

	fmt.Fprintln(wr, ans)
}


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

int main()
{
    int N, K, tmp;
    cin >> N >> K;
    vector<int64_t> list(N + 1);
    double max = 0;
    double ans;

    cin >> list.at(1);

    for (int i = 2; i < N + 1; i++)
    {
        cin >> tmp;
        list.at(i) = list.at(i - 1) + tmp;
    }

    for (int i = 0; i + K < N + 1; i++)
    {
        if (list.at(i + K) - list.at(i) > max)
            max = list.at(i + K) - list.at(i);
    }

    ans = (max + K) / 2;
    cout << fixed << setprecision(10) << ans;
}

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

int main(){
    int n,a,b;
    string s;
    cin >> n >> a >> b >> s;
    int x = a + b;
    int y = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'a'){
            if(x){
                cout << "Yes" << endl;
                x--;
            }else{
                cout << "No" << endl;
            }
        }else if (s[i] == 'b'){
            if(x && y < b){
                cout << "Yes" << endl;
                x--;
                y++;
            }else{
                cout << "No" << endl;
            }
        }else if (s[i] == 'c'){
            cout << "No" << endl;
        }
    }
    return 0;
}

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

int main() {
  int n, m, a[100];
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int k = 1; k <= m; k++) {
    for (int i = 0; i < n - 1; i++) {
      if (a[i] % k > a[i+1] % k) swap(a[i], a[i+1]);
    }
  }
  for (int i = 0; i < n; i++) printf("%d\n", a[i]);
}



Measured memory_bytes: 2684
// g++ -I ~/Documents/AtCoder -std=gnu++14 -o test ~/Documents/AtCoder/test.cpp && ./test && rm test
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define all(v)    (v).begin(), (v).end()
#define in        ([]{int n; cin>>n; return n;}())
using namespace std;
using lint = int64_t;


int main() { cin.tie(0); ios::sync_with_stdio(false);
    int N=in;
    vector<int> W(N);
    rep( i, N ) W[i]=in;

    int min_value = INT_MAX;
    int left=0, right;
    rep( i, N ) {
        right += W[i];
    }

    rep( i, N-1 ) {
        left += W[i];
        right -= W[i];
        min_value = min( min_value, abs(left-right) );
    }

    cout << min_value << '\n';
}


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

int main() {
  int n;
  while (cin >> n) {
    int cnt = 0;
    for (int a = 0; a <= 9; a++) {
      for (int b = 0; b <= 9; b++) {
        for (int c = 0; c <= 9; c++) {
          for (int d = 0; d <= 9; d++) {
            if (a + b + c + d == n) cnt++;
          }
        }
      }
    }
    cout << cnt << endl;
  }
  return 0;
}


Measured memory_bytes: 3076
n = int(input())
A = list(map(int, input().split()))

def rule1(L):
    if len(set(L))!=2:
        return False
    if L.count(0)!=len(L)//3:
        return False
    return True

def rule2(L):
    if len(set(L))!=3:
        return False
    sL = set(L)
    if L.count(list(sL)[0])==L.count(list(sL)[1])==L.count(list(sL)[2]):
        if list(sL)[0] ^ list(sL)[1] ^ list(sL)[2] ==0:
            return True
        else:
            return False
    else:
        return False

if sum(A)==0 or rule1(A) or rule2(A):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 20380
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

ll T[2],A[2],B[2];

int main(){
  cin>>T[0]>>T[1];
  cin>>A[0]>>A[1];
  cin>>B[0]>>B[1];

  if(A[0]*T[0]+A[1]*T[1]==B[0]*T[0]+B[1]*T[1]){
    cout<<"infinity"<<endl;
    return 0;
  }

  if(A[0]*T[0]+A[1]*T[1]>B[0]*T[0]+B[1]*T[1]){
    swap(A[0],B[0]);
    swap(A[1],B[1]);
  }

  if(A[0]<B[0]){
    cout<<0<<endl;
    return 0;
  }

  ll ng=1;
  while(1){
    ll res=ng*((A[0]-B[0])*T[0]+(A[1]-B[1])*T[1]);
    ll p=(A[0]-B[0])*T[0];
    if(res+p>=0) ng*=10;
    else break;
  }

  ll ok=0;
  while(abs(ok-ng)>1){
    ll mid=(ok+ng)/2;
    ll res=mid*((A[0]-B[0])*T[0]+(A[1]-B[1])*T[1]);
    ll p=(A[0]-B[0])*T[0];
    if(res+p>=0) ok=mid;
    else ng=mid;
  }

    ll res=ok*((A[0]-B[0])*T[0]+(A[1]-B[1])*T[1]);
    ll a=(A[0]-B[0])*T[0];

  ll ans=2*ok;
  if(res+a==0) ans--;
  ll p=(A[0]-B[0])*T[0];
  ll q=(A[1]-B[1])*T[1];
  if(p<0&&p+q>=0) ans++;
  else if(p>0&&p+q<=0) ans++;

  cout<<ans<<endl;


  

  return 0;
}


Measured memory_bytes: 256
import itertools
N=int(input())
S=[input() for _ in range(N)]
M=0
A=0
R=0
C=0
H=0
alives=0
march=['M','A','R','C','H']
for i in S:
    if i.startswith('M'):
        M+=1
    elif i.startswith('A'):
        A+=1
    elif i.startswith('R'):
        R+=1
    elif i.startswith('C'):
        C+=1
    elif i.startswith('H'):
        H+=1

if M==0:
    march.pop(march.index('M'))
if A==0:
    march.pop(march.index('A'))
if R==0:
    march.pop(march.index('R'))
if C==0:
    march.pop(march.index('C'))
if H==0:
    march.pop(march.index('H'))

if len(march)<3:
    print(0)
    exit(0)

seq=list(itertools.combinations(march,3))

ans=0
for i in seq:
    temp=1
    for ch in i:
        if ch=='M':
            temp*=M
        if ch=='A':
            temp*=A
        if ch=='R':
            temp*=R
        if ch=='C':
            temp*=C
        if ch=='H':
            temp*=H
    ans+=temp

print(ans)

Measured memory_bytes: 57432
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
    return xx*ff;
}
long long READ(){
    long long xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
    return xx*ff;
}
char one(){
	char ch=getchar();
	while(ch==' '||ch=='\n')
		ch=getchar();
	return ch;
}
int n,x[110];
inline int sqr(int x){return x*x;}
int main(){
	//freopen("in.txt","r",stdin);
	n=read();
	for(int i=1;i<=n;i++)
		x[i]=read();
	int ans=1<<30;
	for(int i=1;i<=100;i++){
		int sum=0;
		for(int j=1;j<=n;j++)
			sum+=sqr(i-x[j]);
		ans=min(ans,sum);
	}
	printf("%d\n",ans);
	return 0;
}





Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

s, w = MAP()


if s <= w:
    print("unsafe")
else:
    print("safe")

Measured memory_bytes: 10036
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(), b = sc.nextInt();
		sc.close();
		int dif = b-a-1;
		int x = dif*(dif+1)/2 - a;
		System.out.println(x);
	}

}

Measured memory_bytes: 21972
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <iomanip>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <stdlib.h>
#include <set>
typedef long long ll;
using namespace std;

int main() {
	int x,a,b;
	cin>>x>>a>>b;
	if(b-a>x){
		cout<<"dangerous"<<endl;
	}else if(b>a){
		cout<<"safe"<<endl;
	}else{
		cout<<"delicious"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
N = gets.to_i
#N = 10**5
loser = Array.new(N+1){Array.new}
(2..N).each do |i|
    winner = gets.to_i
    loser[winner].push(i)
end

cand = Array.new(N+1){Array.new}
ans = Array.new(N+1)

stack = [1]
while stack.length > 0
    i = stack[-1]
    if loser[i].length > 0
        stack.push(loser[i].pop)
    else
        if cand[i].length > 0
            cand[i].sort_by!{|i|-i}
            ans[i] = cand[i].length.times.map{|j| j + cand[i][j]}.max + 1
        else
            ans[i] = 0
        end
        stack.pop
        cand[stack[-1]].push(ans[i]) if stack.length > 0
    end
end

puts ans[1]

Measured memory_bytes: 27644
#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int a_index, z_index;
	for (int i = 0; i < s.length(); i++) {
		if (s.at(i) == 'A') {
			a_index = i;
			break;
		}
	}
	for (int i = s.length()-1; i > a_index; i--) {
		if (s.at(i) == 'Z') {
			z_index = i;
			break;
		}
	}
	cout << z_index - a_index + 1 << endl;
}

Measured memory_bytes: 640
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	int N;
	long[] A;
	long[] sums;
	long MOD = 1000000007L;

	Main(BufferedReader in) throws IOException {
		N = Integer.parseInt(in.readLine());
		String[] tokens = in.readLine().split(" ");
		A = new long[N];
		for (int i = 0; i < N; ++i) {
			A[i] = Long.parseLong(tokens[i]);
		}

		sums = new long[N];
		sums[N - 1] = A[N - 1];
		for (int i = N - 2; i >= 0; --i) {
			sums[i] = sums[i + 1] + A[i];
			sums[i] %= MOD;
		}
	}

	void calc() {
		long result = 0;
		for (int i = 0; i + 1 < N; ++i) {
			result += A[i] * sums[i + 1];
			result %= MOD;
		}
		System.out.println(result);
	}

	void showResult() {
	}
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

const int INF = 1001001001;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

void solve() {
  int n;
  cin >> n;
  vi32 p(n * n);
  cin >> p;
  rep(i, n * n) {
    p[i]--;
  }
  vector<vi32> dp(n, vi32(n));
  rep(i, n) rep(j, n) {
    dp[i][j] = min({i, j, n - i - 1, n - j - 1});
  }
  vector<vi32> f(n, vi32(n));
  int ans = 0;
  rep(i, n * n) {
    int x = p[i] % n;
    int y = p[i] / n;
    ans += dp[x][y];
    f[x][y] = 1;
    using T = tuple<int, int, int>;
    queue<T> q;
    rep(k, 4) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
      q.emplace(nx, ny, dp[x][y]);
    }
    while (sz(q)) {
      int x, y, cost;
      tie(x, y, cost) = q.front();
      q.pop();
      if (dp[x][y] <= cost) continue;
      dp[x][y] = cost;
      rep(k, 4) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        q.emplace(nx, ny, cost + (f[x][y] ? 0 : 1));
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 6064
#include<iostream>
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;
int MOD=100000;
int main(){
    int n,m;
    while(cin>>n>>m,n+m){
        int dp[110][110][2]={0};
        dp[1][0][0]=dp[0][1][1]=1;
        rep(i,n)rep(j,m)rep(k,2){
			dp[i+1+k][j][0]=(dp[i+1+k][j][0]+dp[i][j][k])%MOD;
			dp[i][j+1+(1^k)][1]=(dp[i][j+1+(1^k)][1]+dp[i][j][k])%MOD;
        }
        cout<<(dp[n][m-1][0]+dp[n-1][m][1])%MOD<<endl;
    }
}

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

using namespace std;

char kind[4] = {'S','H','C','D'};

int main(void) {
	int n;
	cin >> n;
	char c;
	int num;
	vector< vector<int> > card(4,vector<int>(13,0));
	for (int i = 0; i < n; ++i) {
		cin >> c;
		cin >> num;
		if (c == 'S') {
			card[0][num-1] = 1;
		}
		else if (c == 'H') {
			card[1][num-1] = 1;
		}
		else if (c == 'C') {
			card[2][num-1] = 1;
		}
		else {
			card[3][num-1] = 1;
		}
	}
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 13; ++j) {
			if (card[i][j] == 0) {
				cout << kind[i] << " ";
				cout << j+1 << endl;
			}
		}
	}
	return 0;
}



Measured memory_bytes: 3160
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    ll N;
    cin >> N;
    ll cp = N;
    int sum = 0;
    while(N){
        sum += N % 10;
        N /= 10;
    }
    if (cp % sum == 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }


    return 0;
}


Measured memory_bytes: 888
#include <iostream>

using namespace std;

int main(void){
	while( 1 ) {
		int N;
		cin >> N;
		if( N == 0 ) break;
		int ans = 0;

		for(int i = 1; i * i <= N; i++) {
			if( i * i == N ) ans++;
		}

		for(int i = 1; i * i <= N; i++) {
			for(int j = i; i * i + j * j <= N; j++) {
				if( i * i + j * j == N ) ans++;
			}
		}

		for(int i = 1; i * i <= N; i++) {
			for(int j = i; i * i + j * j <= N; j++) {
				for(int k = j; k * k + j * j + i * i <= N; k++) {
					if( i * i + j * j + k * k == N ) ans++;
				}
			}
		}

		for(int i = 1; i * i <= N; i++) {
			for(int j = i; i * i + j * j <= N; j++) {
				for(int k = j; k * k + j * j + i * i <= N; k++) {
					for(int l = k; l * l + k * k + j * j + i * i <= N; l++) {
						if( i * i + j * j + k * k + l * l == N ) ans++;
					}
				}
			}
		}

		cout << ans << endl;

	}
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <list>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip> // setprecisionを使用するのに必要 cout << fixed << setprecision(15) << p でpを小数点以下15桁表示
using namespace std;
#define REPD(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) REPD(i, 0, n)
#define DIV0 1000000007
typedef long long ll;
#define fin(ans) cout << (ans) << '\n'
/*

*/
int main()
{
    int A,B,C,K;
    cin >> A >> B >> C >> K;
    while(K){
        if(B <= A){
            K--;
            B *= 2;
        }else{
            K--;
            C *= 2;
        }
    }
    if(A < B && B < C){
        fin("Yes");
    }else{
        fin("No");
    }
    return 0;
}

Measured memory_bytes: 3128