akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  ll n;
  cin >> n;
  vector<ll> x(n),y(n);
  ll i;
  for(i=0;i<n;i++){
    cin >> x[i] >> y[i];
  }
  ll ma=-1000000000000000000,mi=1000000000000000000;
  for(i=0;i<n;i++){
    ma=max(ma,x[i]-y[i]);
    mi=min(mi,x[i]-y[i]);
  }
  ll ans=ma-mi;
  ma=-1000000000000000000,mi=1000000000000000000;
  for(i=0;i<n;i++){
    ma=max(ma,x[i]+y[i]);
    mi=min(mi,x[i]+y[i]);
  }
  ans=max(ans,(ma-mi));
  cout << ans << endl;
}

Measured memory_bytes: 6420
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int cnt=0;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]==s[i+1]){
			if(s[i]=='1'){
				s[i+1]='0';
			}
			else{
				s[i+1]='1';
			}
			cnt++;
		}
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define LIMIT 10000002
using namespace std;

static const double EPS = 1e-9;
typedef long long ll;
typedef pair<int, int> paii;

int n, allie[1000] = {0};

int solve()
{
	int res = INT_MAX, p = 0;
	bool dp[1000010] = {0};
	
	FOR(j, 0, n)
	{
		p += allie[j];
		
		RFOR(i, 0, 1000010)
		{
			if(( i == 0 || dp[i] == true)&&(i+allie[j] < 1000010))
			{
				dp[i+allie[j]] = true;
			}
		}
	}
	
	FOR(i, 0, p+1)
	{	
		if(dp[i] == true)
			res = min(res, abs((p-i)-i));
	}
	
	return res;
	
}

int main()
{
	while(cin >> n, n)
	{
		FOR(i, 0, n)
		{
			cin >> allie[i];
		}
		
		cout << solve() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 2148
import itertools

n, m, q = map(int, input().split())

a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

for i in range(q):
	a[i], b[i], c[i], d[i] = map(int, input().split())

ans = 0

for comb in itertools.combinations_with_replacement(range(1, m+1), n):
	j = 0
	for i in range(q):
		if comb[b[i]-1]-comb[a[i]-1] == c[i]:
			j += d[i]
	#print('{} {}'.format(comb, j))
	ans = max(ans, j)

print(ans)

Measured memory_bytes: 9056
import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for i in range(N - 1):
  a, b = tuple(map(int, input().split()))
  e[a].append((b, i))
  e[b].append((a, i))
res = [0] * (N - 1)
vis = set()
def dfs(x):
  global vis
  global res
  viss = set()
  svis = set()
  t = 1
  for y, i in e[x]:
    if i in vis: viss.add(res[i])
  #print(x, viss)
  for y, i in e[x]:
    #print(x, y, t)
    while t in viss:
      t += 1
    if i in vis:
      continue
    #print(x, y, t)
    svis.add(y)
    vis.add(i)
    res[i] = t
    t += 1
  for y in svis:
    dfs(y)
  #print(res)
dfs(1)
print(max(res))
for r in res: print(r)

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

int check(int n) {
  int sum = 0;
  while (n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main() {
  int N, A, B,total=0;
  cin >> N >> A >> B;
  for (int i = 1; i <= N; i++) {
    int sum = check(i);
    if (sum >= A && sum <= B) {
      total += i;
    }
  }
  cout << total << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <numeric>


int main()
{
	long long n, k;

	std::cin >> n >> k;

	long long num = 1;

	for (size_t i = 0; i < n; i++)
	{
		num = std::min(num * 2, num + k);
	}

	std::cout << num << std::endl;

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<stdlib.h>
using namespace std;
char str[100][21];
int l[100];
int r[100];
struct wolf{
	int c[256];
	wolf(){
		for(int i=0;i<256;i++)c[i]=0;
	}
};
char p[100][21];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%s%d%d",str[i],l+i,r+i);
	}
	int b;
	scanf("%d",&b);
	for(int i=0;i<b;i++){
		scanf("%s",p[i]);
	}
	stack<wolf> S;
	bool ret=false;
	for(int i=0;i<b;i++){
		bool OK=true;
		for(int j=0;p[i][j];j++)if(p[i][j]<'0'||p[i][j]>'9')OK=false;
		if(OK){
			wolf w;
			w.c[atoi(p[i])]=1;
			S.push(w);
		}else if(p[i][0]!='+'&&p[i][0]!='-'&&p[i][0]!='*'&&p[i][0]!='/'){
			wolf w;
			int at=0;
			for(int k=0;k<a;k++){
				bool ok=true;
				for(int j=0;str[k][j]||p[i][j];j++)if(str[k][j]!=p[i][j])ok=false;
				if(ok)at=k;
			}
		//	printf("%d %d\n",i,at);
			for(int i=l[at];i<=r[at];i++)w.c[i]=1;
			S.push(w);
		}else{
			wolf B=S.top();
			S.pop();
			wolf A=S.top();
			S.pop();
			wolf w;
			if(p[i][0]=='+'){
				for(int k=0;k<256;k++)
					for(int j=0;j<256;j++)
						if(A.c[k]&&B.c[j])w.c[(k+j)%256]=1;
				S.push(w);
			}
			if(p[i][0]=='-'){
				for(int k=0;k<256;k++)
					for(int j=0;j<256;j++)
						if(A.c[k]&&B.c[j])w.c[(k-j+256)%256]=1;
				S.push(w);
			}
			if(p[i][0]=='*'){
				for(int k=0;k<256;k++)
					for(int j=0;j<256;j++)
						if(A.c[k]&&B.c[j])w.c[(k*j)%256]=1;
				S.push(w);
			}
			if(p[i][0]=='/'){
				for(int k=0;k<256;k++)
					for(int j=0;j<256;j++)
						if(A.c[k]&&B.c[j]){
							if(j==0)ret=true;
							else w.c[(k/j)%256]=1;
						}
				S.push(w);
			}
		//	printf("%d: ",i);
		//	for(int i=0;i<230;i++)printf("%d",w.c[i]);
		//	printf("\n");
		}
	}
	if(ret)printf("error\n");
	else printf("correct\n");
}

Measured memory_bytes: 1048
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

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

    lint ans = 0;
    for(lint i=0; i<=n; i++) {
        if(i%3 == 0 || i%5 == 0) {

        } else {
            ans += i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3580
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdint>

int main() {
  int N;
  scanf("%d", &N);

  std::vector<std::vector<int>> F(N, std::vector<int>(10));
  std::vector<std::vector<int>> P(N, std::vector<int>(11));

  for (int i=0; i<N; ++i) {
    for (int j=0; j<10; ++j) {
      scanf("%d", &F[i][j]);
    }
  }

  for (int i=0; i<N; ++i) {
    for (int j=0; j<11; ++j) {
      scanf("%d", &P[i][j]);
    }
  }

  int i_ub=1<<10;
  int res=-1e9;
  for (int i=1; i<i_ub; ++i) {
    int cur=0;
    for (int j=0; j<N; ++j) {
      int num=0;
      for (int k=0; k<10; ++k) {
        if (i >> k & 1 && F[j][k]) {
          ++num;
        }
      }
      cur += P[j][num];
    }
    res = std::max(res, cur);
  }

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


Measured memory_bytes: 256
# frozen_string_literal: true

n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
count = 0
sum = 0
c = []
(0...n).each do |i|
  e = a[i] - b[i]
  if e.negative?
    count += 1
    sum += e
    e = 0
  end
  c.push e
end
c.sort.reverse.each do |d|
  break if sum >= 0

  sum += d
  count += 1
end
puts count > n ? '-1' : count


Measured memory_bytes: 17672
# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2,x+1):
        res=res*i%mod
    return res

# combination nCr
def combi(n,r):
    if r<0 or r>n:
        return 0
    else:
        return fact(n)*inv(fact(r))*inv(fact(n-r))%mod

mod=10**9+7

N,K=map(int,input().split())
A=[-10**10] # 1-ind
A.extend(list(map(int,input().split())))
A.sort()

# print(A)

ans=0
# min
p=1
for i in range(N-K+1,0,-1):
    # print(i,A[i],p)
    temp=A[i]*p%mod    
    ans=(ans-temp)%mod
    # print((N-i+1)*inv(N-K-i+2))
    p=p*(N-i+1)*inv(N-K-i+2)%mod
# max
p=1
for j in range(K,N+1):
    # print(j,A[j],p)
    temp=A[j]*p%mod
    ans=(ans+temp)%mod
    p=p*j*inv(j-K+1)%mod

print(ans)

Measured memory_bytes: 64368
from collections import Counter

N,S = int(input()),[]
for _ in range(N):
	S.append(input())
c = Counter(S)

print('AC x ' + str(c['AC']))
print('WA x ' + str(c['WA']))
print('TLE x ' + str(c['TLE']))
print('RE x ' + str(c['RE']))

Measured memory_bytes: 83028
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch IntegerCards | diff IntegerCards.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address IntegerCards.cpp && ./a.out

/*
 
 5/25/2019
 
 5:09-
 
 */

const int MAX_N=1e6+1;
LL A[MAX_N],C[MAX_N];
int N,M,B[MAX_N];

void solve() {
  sort(A,A+N);
  vector<pair<LL,int>> X;
  REP(i,M) X.emplace_back(C[i],B[i]);
  sort(ALL(X)),reverse(ALL(X));
  int i=0;
  FORR(p,X) {
    LL c; int b; tie(c,b)=p;
    while(i<N&&b>0&&A[i]<c) {
      A[i]=c;
      ++i,--b;
    }
  }
  LL res=accumulate(A,A+N,0LL);
  cout<<res<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N>>M;
  REP(i,N) cin>>A[i];
  REP(i,M) cin>>B[i]>>C[i];
  solve();
  
  return 0;
}


Measured memory_bytes: 10996
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i,n) for(int i=0;i<n;++i)
#define rep(j,n) for(int j=0;j<n;++j)
#define REP(i,n) for(int i=1;i<=n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define len(s)   ((int)s.size())
#define F first
#define S second
#define pb push_back
#define pf push_front
#define m_p make_pair
typedef long long ll;
typedef double db;
typedef vector<string> ve;
typedef vector<pair<int, int> > vepa;
typedef set<string>se;
typedef map<string,int> mpp;
const ll N=1024,OO=1e14,MOD=1e9+7;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
ll TC,n,m,k,a,b,cnt,sum,mx,mn,arr[N];
bool f,vis[N];
int main(){
   IOS;
    cin>>n>>a>>b;
    if(n%a==0)cout<<(n/a)*b;
    else cout<<((n/a)*b)+b;
go;
}


Measured memory_bytes: 3640
n = int(input())
call = ''
one = n % 10
if(one == 2 or one == 4 or one == 5 or one == 7 or one == 9):
    call = 'hon'
elif(n % 10 == 0 or one == 1 or one == 6 or one == 8):
    call = 'pon'
else:
    call = 'bon'

print(call)

Measured memory_bytes: 9176
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
"""
漸化式は f(m,n) = (m-1)f(m-1,n-1) + (n-1)f(m-2,n-2)
初期条件 f(m-n,0)=1, f(m-n+1,1)=m-n
"""
MOD = 10**9+7
res = [0]*(n+1)
res[0] = 1
res[1] = m-n
for i in range(2,n+1):
    res[i] = (m-n+i-1)*res[i-1] + (i-1)*res[i-2]
    res[i] %= MOD

#print(res)
ans = res[n] 
for i in range(m,m-n,-1):
    ans *= i
    ans %= MOD

print(ans)

Measured memory_bytes: 28560
using System;

namespace AGC024_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = long.Parse(Console.ReadLine());
            var P = new int[N];
            var C = new int[N];
            for (int i = 0; i < N; i++)
            {
                P[i] = int.Parse(Console.ReadLine());
                C[P[i]-1] = i;
            }

            var c = 0;
            var left = -1;
            var a = 0;
            for (int i = 0; i < N; i++)
            {
                if (left < C[i]) c++;
                else c = 1;
                left = C[i];
                a = Math.Max(a, c);
            }
            Console.WriteLine(N-a);
        }
    }
}


Measured memory_bytes: 17312
#include<bits/stdc++.h>
using namespace std;
#define N 1050
int lcs(string X,string Y){
  int c[N+1][N+1];
  int m = X.size();
  int n = Y.size();
  int maxl = 0;
  X = ' ' + X;
  Y = ' ' + Y;
  for(int i=0;i<=m;i++) c[i][0]=0;
  for(int j=1;j<=n;j++) c[0][j]=0;
  for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
      if(X[i]==Y[j]) c[i][j]=c[i-1][j-1]+1;
      else c[i][j]=max(c[i-1][j],c[i][j-1]);
      maxl=max(maxl,c[i][j]);
    }
  }
  return maxl;
}
int main(){
  int q;cin>>q;
  while(q--){
    string a,b;cin>>a>>b;
    cout<<lcs(a,b)<<endl;
  }
  return 0;
}

Measured memory_bytes: 7256
#include<bits/stdc++.h>
using namespace std;
int main()
{	
  long long A, B;
  cin >> A >> B;
  for(int i=1; i<=B; i++)
  {
  	if((A*i)%B ==0)
    {
    	cout << A*i << endl;
      break;
    }
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,m,x,a[1000100];
int main()
{
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&x);
		a[x]++;
	}
	for (int i=1;i<=n;i++) printf("%d\n",a[i]);
} 

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;

vector<ll> x(200010);
vector<ll> p[200010];

void dfs(int s ,int pre){

	for(int i=0; i<p[s].size(); i++){
		int next =p[s][i];

		if(next ==pre)continue;

		x[next] +=x[s];

		dfs(next, s);
	}
}


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

	int n,q;cin>>n>>q;


	for(int i=0; i<n-1; i++){
		int from,to;cin>>from>>to;

		p[from].push_back(to);
		p[to].push_back(from);
	}

	for(int i=0; i<q; i++){
		int t,d; cin>>t>>d;
		x[t] +=d;
	}
	dfs(1 ,-1);

	for(int i=1; i<=n; i++){
		cout<<x[i]<<" ";
	}
	cout<<endl;


}




Measured memory_bytes: 27392
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
using namespace std;

#define debug(x) cout << #x << ": " << x << endl;
#define ll long long
#define mod 1000000007

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();
    if (n == 1)
        return;

    vector<cd> a0(n / 2), a1(n / 2);
    for (int i = 0; 2 * i < n; i++) {
        a0[i] = a[2*i];
        a1[i] = a[2*i+1];
    }
    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * PI / n * (invert ? -1 : 1);
    cd w(1), wn(cos(ang), sin(ang));
    for (int i = 0; 2 * i < n; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n/2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n/2] /= 2;
        }
        w *= wn;
    }
}

int main() {

  //freopen("input.in","r",stdin);
  //freopen("output.out","w",stdout);
  vector<int> A(1 << 18, 0);

  ll N, M, num;
  cin >> N >> M;
  for (size_t i = 0; i < N; i++) {
    cin >> num;
    A[num]++;
  }

  // A
  vector<cd> iA;
  for(int i = 0;i < A.size();i++) {
    iA.push_back(cd(A[i], 0));
  }

  fft(iA, false); // FFT(A)

  // FFT(A*A)
  for(int i = 0;i < iA.size();i++) {
    iA[i] = iA[i]*iA[i];
  }

  // A*A
  fft(iA, true);

  ll ans = 0;
  for(int i = 200000;i >= 0;i--) {
    ll freq = round(real(iA[i]));
    // if(freq != 0) {
    //   debug(i);
    //   debug(real(iA[i]));
    // }
    if(freq <= M) {
      ans += freq*1LL*i;
      M -= freq;
    } else {
      ans += M*1LL*i;
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 15596
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	while (N) {
		long long int num[50] = {};
		for (int i = 0; i < N; i++) {
			num[i] = (N-i) * MOD + i + 1;
		}
		for (int i = 0; i < M; i++) {
			cin >> K >> Q;
			for (int j = 0; j < N; j++) {
				if (num[j] % MOD < K) {
					num[j] += Q;
				}
				else if (num[j] % MOD < K + Q) {
					num[j] -= (K - 1);
				}
			}
		}
		for (int i = 0; i < N; i++) {
			if (num[i] % MOD == 1)cout << num[i] / MOD << endl;
		}
		cin >> N >> M;
	}
	return 0;
}

Measured memory_bytes: 3008
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;



//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1000000000

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

int n;
int f[100][10];
int p[100][11];
int binary[10];

void nishinsu(int decimal)
{
	int i;
	binary[10] = {};


	/* 10進数→2進数の変換 */
	for (i = 0; decimal>0; i++) {
		binary[i] = decimal % 2;
		decimal = decimal / 2;
	}


}



int main() {
	cin >> n;
	REP(i, n) {
		REP(j, 10) {
			cin >> f[i][j];
		}
	}
	REP(i, n) {
		REP(j, 11) {
			cin >> p[i][j];
		}
	}

	long long max = -INF;

	FOR(i, 1, 1024) {
		nishinsu(i);
		long long sum = 0;
		REP(j, n) {
			int c = 0;
			REP(k, 10) {
				if (binary[k] == 1 && f[j][k] == 1) {
					c++;
				}
			}
			sum += p[j][c];
		}
		if (sum > max) {
			max = sum;
		}

	}
	cout << max << endl;


	

	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define db double
#define ldb long double
#define vi vector<int>
#define vull vector<ull>
#define vll vector<ll>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define si set<int>
#define sll set<ll>
#define ins insert
#define vpp vector<pair<int,int>>
#define mp make_pair
#define ft first
#define sc second
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int n,x;
    cin>>n>>x;
    int a[n];
    int sum=0;
    rep(i,n){
    	cin>>a[i];
        sum+=a[i];	
	}
	sort(a,a+n);
	int m=a[0];
	int ans=n+(x-sum)/m;
	cout<<ans;
	return 0;
}

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

using namespace std;

//??¨?????\?????°????????§???
#define MAX 100000 
#define INFTY (1 << 30)

//???????????????
class Edge
{
public :
	int t, w;//???????????£?????????????????????
	Edge(){}
	Edge(int t, int w) :t(t), w(w) {}
};

vector<Edge> G[MAX];
int n, d[MAX];//??¨?????\?????°??????????????¢?´¢???????§??????????????????¢

bool vis[MAX];
int cnt;

void bfs(int s) 
{
	for (int i = 0; i < n; i++) {
		d[i] = INFTY;
	}

	queue<int> Q;
	Q.push(s);
	d[s] = 0;
	int u;

	while (!Q.empty()) {
		u = Q.front();
		Q.pop();

		for (int i = 0; i < G[u].size(); i++) {
			Edge e = G[u][i];
			if (d[e.t] == INFTY) {
				d[e.t] = d[u] + e.w;
				Q.push(e.t);
			}
		}
	}
}

//??¨?????´???????±?????????????
int diamterOfTree()
{
	bfs(0);
	int maxv = 0;
	int tgt = 0;

	for (int i = 0; i < n; i++) {
		if (d[i] == INFTY) {
			continue;
		}
		if (maxv < d[i]) {
			maxv = d[i];
			tgt = i;
		}
	}

	//??????????????????????????????????????????????????¢?´¢??§?????¢????±???????
	bfs(tgt);

	maxv = 0;

	for (int i = 0; i < n; i++) {
		if (d[i] == INFTY) {
			continue;
		}
		if (maxv < d[i]) {
			maxv = d[i];
		}
	}

	return maxv;

}

int main(void)
{
	int s, t, w;
	cin >> n;


	//n-1?????????????????°????????§???????????????????????????????????\???????????±????????????????????\????????????????????????
	for (int i = 0; i < n - 1; i++) {
		cin >> s >> t >> w;

		G[s].push_back(Edge(t, w));
		G[t].push_back(Edge(s, w));
	}

	cout << diamterOfTree() << endl;

	return 0;

}

Measured memory_bytes: 9840
#include <iostream>
#include <bits/stdc++.h>
#define rep(k,i,n) for(int i=k;i<n;++i)
using namespace std;
int main(void){
    // Your code here!
    int A,B,sum=1,i=0;
    cin>>A>>B;
    while(sum<B){
       ++i;
       sum+=A-1;
    }
    cout<<i<<endl;
}


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

using namespace std;

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

    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    using ll = long long;

    ll v = *max_element(b.begin(), b.end()) * n;

    const ll inf = 1LL << 60;

    vector<vector<ll>> dp(n + 1, vector<ll>(v + 1, inf));

    dp[0][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= v; j++) {
            dp[i + 1][j] = dp[i][j];

            if (j - b[i] >= 0) {
                dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - b[i]] + a[i]);
            }
        }
    }

    ll ans = 0;

    for (int i = v; i >= 0; i--) {
        if (dp[n][i] <= w) {
            ans = i;

            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = (int)1e5+10;
int a[MAXN],vis[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int now=1,step=0;
    while(now!=2){
        now=a[now];
        if(vis[now]==1)break;
        vis[now]=1;
        step++;
    }
    if(now==2)printf("%d\n",step);
    else printf("-1\n");
    return 0;
}



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

using namespace std;

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
    }
    // int b_max = *max_element(B.begin(), B.end());
    vector<int> cost(H + 1, 0);
    cost[0] = 0;
    for (int h = 1; h <= H; h++) {
        int cost_min = 100000000;
        for (int i = 0; i < N; i++) {
            if (h < A[i]) {
                cost_min = min(cost_min, B[i]);
            } else {
                cost_min = min(cost_min, cost[h - A[i]] + B[i]);
            }
        }
        cost[h] = cost_min;
    }
    // cout << cost[H / 10] << endl;
    cout << cost[H] << endl;
    return 0;
}

Measured memory_bytes: 256
import sys

class Dice():
    top=0
    n=1
    e=3
    w=2
    s=4
    bottom=5
    dice=[1,2,3,4,5,6]
    def __init__(self,num):
        self.dice=num

    def roll(self,direction):
        if(direction=="N"):
            self.top,self.bottom,self.n,self.s = self.n,5-self.n,5-self.top,self.top
        elif(direction=="E"):
            self.top,self.bottom,self.e,self.w = self.e,5-self.e,5-self.top,self.top
        elif(direction=="W"):
            self.top,self.bottom,self.e,self.w = self.w,5-self.w,self.top,5-self.top
        elif(direction=="S"):
            self.top,self.bottom,self.n,self.s = self.s,5-self.s,self.top,5-self.top

    def equal(self,another):
        if(self.dice[self.top] != another.dice[another.top]):
            return False
        if(self.dice[self.n] != another.dice[another.n]):
            return False
        if(self.dice[self.e] != another.dice[another.e]):
            return False
        if(self.dice[self.w] != another.dice[another.w]):
            return False
        if(self.dice[self.s] != another.dice[another.s]):
            return False
        if(self.dice[self.bottom] != another.dice[another.bottom]):
            return False

        return True


dicea=Dice(list(map(int,input().split())))
diceb=Dice(list(map(int,input().split())))

roll_order="NNNNWNNNWNNNENNNENNNWNNNN"
for i in range(len(roll_order)):
    if(dicea.equal(diceb)):
        print("Yes")
        sys.exit()
    else:
        diceb.roll(roll_order[i])
print("No")


Measured memory_bytes: 5612
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin >> n >> l;
  int azi_n=0;
  azi_n = n*(n+2*l-1)*1/2;
  int difference = 4000000;
  int kakunin = 0;
  for(int i = 1; i<n+1;i++){
    if(abs(l+i-1)<=difference){
      difference =abs(l+i-1);
      kakunin = l+i-1;
    }
  }
  if(kakunin>0){
    cout << azi_n - difference;
  }
  else{
    cout << azi_n + difference;
  }
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List
import Data.Char
strToInt s = (read :: String -> Int) s

main :: IO ()
main = do
    -- スペース区切り整数の入力
    [n, m] <- map strToInt . words <$> getLine
    -- 出力
    putStrLn . show $ (n-1) * (m-1)


Measured memory_bytes: 508
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
int max(const void *a, const void *b){return *(int*)b - *(int*)a;}


int main(void)
{
    int a,b,c;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);

    printf("%d\n", c- (a-b) < 0 ? 0 : c- (a-b));
    
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>
#include<iostream>

#define FI first
#define SE second

using namespace std;

int ans,c;
string x;

int main(){
    cin>>x;
    int pan = x.length();

    for(int i =0;i<pan;i++){
        if(x[i]=='G'||x[i]=='C'||x[i]=='T'||x[i]=='A'){
            c++;
            ans= max(ans,c);
        } else {
            c = 0;
        }
    }
    ans = max(ans,c);
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010;
int n,m,a[4][N];
LL ans,cnt[N];
inline int in()
{
	char ch=getchar();
	int f=1,tmp=0;
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
	return tmp*f;
}

int main()
{
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	n=in();
	for(int i=1;i<=3;i++)
		for(int j=1;j<=n;j++)
		scanf("%d",&a[i][j]);
	for(int i=1;i<=3;i++)
		sort(a[i]+1,a[i]+n+1);
	for(int i=1,j=1;j<=n;j++)
	{
		while(a[1][i]<a[2][j]&&i<=n) i++;
		cnt[j]+=i-1;
	}
	for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
	for(int i=1,j=1;j<=n;j++)
	{
		while(a[2][i]<a[3][j]&&i<=n) i++;
		ans+=cnt[i-1];
	}
	printf("%lld",ans);
	return 0;
}


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

int main()
{
    ll a,b,x,ans;
    while(scanf("%lld%lld%lld",&a,&b,&x)!=EOF)
    {
        ans=b/x;
        if(a!=0) ans-=(a-1)/x;
        else ans++;
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
typedef long long ll;
ll n, a, b, l, r=1e9, m, h[100005];

bool f(ll p) {
	ll i, c=0;
	for(i=0; i<n; i++)
		c += h[i]>p*b ? (h[i]-p*b+a-1)/a : 0;
	return c<=p;
}

int main() {
	scanf("%lld%lld%lld", &n, &a, &b);
	a -= b;
	for(ll i=0; i<n; i++) scanf("%lld", &h[i]);
	while(l<r) {
		m = (l+r) / 2;
		if(f(m)) r = m;
		else l = m+1;
	}
	printf("%lld", r);
	return 0;
}

Measured memory_bytes: 896
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl; cout << "       ";
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   ";
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}

////////////////////////////////////////////////////////////////

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

	ll sum = A + B + C;
	vector<char> ans;
	if(sum == 1){
		for(int i=0; i<N; i++){
			if(s[i]=="AB"){
				if(A==0 && B==0){ cout << "No" << endl; return 0;}
				if(A==1){ A--; B++; ans.push_back('B');}
				else {A++; B--; ans.push_back('A');}
			}
			if(s[i]=="BC"){
				if(B==0 && C==0){ cout << "No" << endl; return 0;}
				if(B==1){ B--; C++; ans.push_back('C');}
				else {B++; C--; ans.push_back('B');}
			}
			if(s[i]=="AC"){
				if(A==0 && C==0){ cout << "No" << endl; return 0;}
				if(A==1){ A--; C++; ans.push_back('C');}
				else {A++; C--; ans.push_back('A');}
			}
		}
		cout << "Yes" << endl;
		for(int i=0; i<N; i++) cout << ans[i] << endl;
		return 0;
	}

	s.push_back("  ");//番兵
	for(int i=0; i<N; i++){
		if(s[i]=="AB"){
			if(A==0 && B==0){cout << "No" << endl; return 0;}
			if(A < B){ A++; B--; ans.push_back('A'); continue; }
			else if(A>B){A--; B++; ans.push_back('B'); continue;}
			//以下A==Bの場合
			if(s[i+1]=="BC"){ A--; B++; ans.push_back('B'); continue;}
			else {A++; B--; ans.push_back('A'); continue;}
		}
		else if(s[i]=="BC"){
			if(B==0 && C==0){cout << "No" << endl; return 0;}
			if(B < C){ B++; C--; ans.push_back('B'); continue;}
			else if(B>C){B--; C++; ans.push_back('C'); continue;}
			//以下B==Cの場合
			if(s[i+1]=="AC"){ B--; C++; ans.push_back('C'); continue;}
			else {B++; C--; ans.push_back('B'); continue;}
		}
		else if(s[i]=="AC"){
			if(A==0 && C==0){cout << "No" << endl; return 0;}
			if(A < C){ A++; C--; ans.push_back('A'); continue;}
			else if(A>C){A--; C++; ans.push_back('C'); continue;}
			//以下A==Cの場合
			if(s[i+1]=="BC"){ A--; C++; ans.push_back('C'); continue;}
			else {A++; C--; ans.push_back('A'); continue;}
		}
	}
	//cout << " A: " << A << " B: " << B << " C: " << C << endl;
	cout << "Yes" << endl;
	for(int i=0; i<ans.size(); i++){
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 9592
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <vector>
#define EPS 1e-9
using namespace std;

double add(double a,double b){
	if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))return 0.0;
	return a+b;
}

struct Point{
	double x,y,z;
	Point(double xx=0.0,double yy=0.0,double zz=0.0){
		x=xx;
		y=yy;
		z=zz;
	}
	Point operator+(Point p){
		return Point(add(x,p.x),add(y,p.y),add(z,p.z));
	}
	Point operator-(Point p){
		return Point(add(x,-p.x),add(y,-p.y),add(z,-p.z));
	}
	Point operator*(double d){
		return Point(x*d,y*d,z*d);
	}
	Point operator/(double d){
		return Point(x/d,y/d,z/d);
	}
};

typedef Point Vector;

class Circle{
public:
	Point p;
	Vector v;
	double r,rv;
	Circle(Point pp=Point(),Vector vv=Point(),double rr=0.0,double rrv=0.0){
		p=pp;
		v=vv;
		r=rr;
		rv=rrv;
	}
};

struct data{
	int type;
	double t;
	int v1,v2;
	data(int ty=0,double tt=0.0,int vv1=0,int vv2=0){
		type=ty;
		t=tt;
		v1=vv1;
		v2=vv2;
	}
	bool operator<(const data& d1)const{
		return t<d1.t;
	}
};

int n;
Circle c[301];

double res[301];
bool flag[301];
vector<data> query;

double C(int i,int j){
	double A=pow(c[i].v.x-c[j].v.x,2)+pow(c[i].v.y-c[j].v.y,2)+pow(c[i].v.z-c[j].v.z,2)-pow(c[i].rv+c[j].rv,2);
	double B=2.0*((c[i].p.x-c[j].p.x)*(c[i].v.x-c[j].v.x)+(c[i].p.y-c[j].p.y)*(c[i].v.y-c[j].v.y)+(c[i].p.z-c[j].p.z)*(c[i].v.z-c[j].v.z)+(c[i].r+c[j].r)*(c[i].rv+c[j].rv));
	double C=pow(c[i].p.x-c[j].p.x,2)+pow(c[i].p.y-c[j].p.y,2)+pow(c[i].p.z-c[j].p.z,2)-pow(c[i].r+c[j].r,2);
	if(B*B-4.0*A*C<0.0)return -1;
	double t1=(-B+sqrt(B*B-4.0*A*C))/(2.0*A);
	double t2=(-B-sqrt(B*B-4.0*A*C))/(2.0*A);
	if(t1<EPS && t2<EPS)return -1;
	if(t1<EPS)return t2;
	if(t2<EPS)return t1;
	return min(t1,t2);
}

int main(void){
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		query.clear();
		for(int i=0;i<n;i++){
			scanf("%lf %lf %lf",&c[i].p.x,&c[i].p.y,&c[i].p.z);
			scanf("%lf %lf %lf",&c[i].v.x,&c[i].v.y,&c[i].v.z);
			scanf("%lf %lf",&c[i].r,&c[i].rv);
			query.push_back(data(1,c[i].r/c[i].rv,i,-1));
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				double ct=C(i,j);
				if(ct>=0.0)query.push_back(data(2,ct,i,j));
			}
		}
		sort(query.begin(),query.end());
		for(int i=0;i<n;i++){
			res[i]=0.0;
			flag[i]=false;
		}
		for(int i=0;i<query.size();i++){
			if(query[i].type==1){
				if(!flag[query[i].v1]){
					flag[query[i].v1]=true;
					res[query[i].v1]=query[i].t;
				}
			}
			if(query[i].type==2){
				if(!flag[query[i].v1] && !flag[query[i].v2]){
					flag[query[i].v1]=true;
					flag[query[i].v2]=true;
					res[query[i].v1]=query[i].t;
					res[query[i].v2]=query[i].t;
				}
			}
		}
		for(int i=0;i<n;i++){
			printf("%.10f\n",res[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 1972
n=input()
a=[0]*4
for i in range(n):
    s=raw_input()
    if s=="AC":
        a[0]+=1
    elif s=="WA":
        a[1]+=1
    elif s=="TLE":
        a[2]+=1
    else:
        a[3]+=1
print "AC x",a[0]
print "WA x",a[1]
print "TLE x",a[2]
print "RE x",a[3]


Measured memory_bytes: 84504
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <stdio.h>
#include <bitset>

using namespace std;

#define fo(i,n) for(int i=0; i<(int)n; i++)
#define rep(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#define mp(a,b) make_pair(a,b)
#define pb(x) push_back(x)
#define pii pair<int,int>

vector<bitset<626> > v(625);
int n,m,d;

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

int main() {

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

	while (scanf("%d%d%d",&m,&n,&d) && n!=0) {
		for (int i=0; i<n; i++) {
			for (int j=0; j<m; j++) {
				int k = i*m+j;
				v[k].reset();
				v[k][k] = 1;
				int b;
				cin>>b;
				v[k][n*m] = b;
				for (int h=0; h<=d; h++) {
					int x = i+h;
					int y = j+(d-h);
					if (inside(x,y)) v[k][x*m+y] = 1;
					x = i+h;
					y = j-(d-h);
					if (inside(x,y)) v[k][x*m+y] = 1;
					x = i-h;
					y = j+(d-h);
					if (inside(x,y)) v[k][x*m+y] = 1;
					x = i-h;
					y = j-(d-h);
					if (inside(x,y)) v[k][x*m+y] = 1;
				}
			}
		}
		
		int k = 0;
		for (int i=0 ;i<m*n; i++) {
			int j = k;
			while (j<m*n && !v[j][i]) j++;
			if (j==m*n) continue;
			swap(v[k],v[j]);
			for (int j=k+1; j<m*n; j++) if (v[j][i]) v[j] ^= v[k];
			k++;
		}
		int ans = 1;
		
		for (int j=0; j<m*n; j++) {
			if (v[j][m*n] && v[j].count()==1) ans = 0;
		}
		
		cout<<ans<<endl;
		
	}
					

    return 0;

}

Measured memory_bytes: 1300
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, a[100008];

ll gcd(ll a, ll b){
	if(a < b){
		ll tmp = a;
		a = b;
		b = tmp;
	}
	if(a%b == 0){return b;}
	else{return gcd(b, a%b);}
}

int main(){
	cin >> n;
	
	ll agcd;
	vector<ll> neck;
	neck.push_back(1);
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
		if(i == 1){agcd = a[1];}
		else{
			ll buf = gcd(a[i], agcd);
			if(buf < agcd){
				neck.push_back(i);
			    agcd = buf;
			}
		}
	}
	
	ll ans = 0;
	for(ll j = 0; j < neck.size(); j++){
		ll neck_i = neck[j];
		ll ansbuf = 0;
		for(ll i = 1; i <= n; i++){
			if(i != neck_i){
				if(ansbuf == 0){ansbuf = a[i];}
				else{ansbuf = gcd(a[i], ansbuf);}
			}
		}
		if(ans == 0){ans = ansbuf;}
		else{ans = max(ansbuf, ans);}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
const int Maxn=1500+100;
const int Maxd=1e9;
 
struct Weighted_Vertex
{
    int u,w;
 
    bool operator< (Weighted_Vertex other) const
    {
        return w>other.w;
    }
};
 
int n,m;
vector <Weighted_Vertex> adj[Maxn];
 
int d[Maxn][Maxn];
vector <int> trace[Maxn][Maxn];
 
bool in[Maxn],Check[Maxn];
 
Weighted_Vertex MakeWV(int u, int w)
{
    Weighted_Vertex t;
    t.u=u; t.w=w;
    return t;
}
 
void DJK(int s, int d[Maxn], vector <int> trace[Maxn])
{
    priority_queue <Weighted_Vertex> q;
 
    for (int i=1; i<=n; i++) d[i]=Maxd;
    d[s]=0;
    q.push(MakeWV(s,0));
 
    while (!q.empty())
    {
        Weighted_Vertex t;
        t=q.top(); q.pop();
        if (d[t.u]!=t.w) continue;
 
        int u=t.u;
        for (int i=0; i<adj[u].size(); i++)
        {
        	t=adj[u][i];
            int v=t.u, w=t.w;
            if (d[v]==d[u]+w) trace[v].push_back(u); else
            if (d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                trace[v].clear(); trace[v].push_back(u);
                q.push(MakeWV(v,d[v]));
            }
        }
    }
}
 
void DFS(int r, int u)
{
    in[u]=true;
    Check[u]=false;
 
    for (int i=0; i<trace[r][u].size(); i++)
    {
        int v=trace[r][u][i];
        if (Check[v]) DFS(r,v);
    }
}
 
void Solve()
{
    int Res=0;
    for (int i=1; i<=n; i++)
    for (int j=i+1; j<=n; j++) Res=max(Res,d[i][j]);
 
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++) Check[j]=true;
        for (int j=i+1; j<=n; j++)
            if (d[i][j]==Res) DFS(i,j);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].push_back(MakeWV(v,w));
        adj[v].push_back(MakeWV(u,w));
    }
 
    for (int i=1; i<=n; i++) DJK(i,d[i],trace[i]);
    Solve();
 
    int Res=0;
    for (int i=1; i<=n; i++)
        if (!in[i]) Res++;
 
    printf("%d\n",Res);
    for (int i=1; i<=n; i++)
        if (!in[i]) printf("%d\n",i);
    return 0;
}


Measured memory_bytes: 143208
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    C = [input().strip("\n") for _ in range(H)]
    ans = 0
    rh = [True] * H
    rw = [True] * W
    for h in range(2 ** H):
        hh = h
        for i in range(H):
            if hh % 2 == 1: rh[i] = False
            else: rh[i] = True
            hh //= 2
        for w in range(2 ** W):
            ww = w
            for j in range(W):
                if ww % 2 == 1: rw[j] = False
                else: rw[j] = True
                ww //= 2
            
            count = 0
            for sh in range(H):
                for sw in range(W):
                    if rh[sh] and rw[sw] and C[sh][sw] == "#": count += 1
            if count == K: ans += 1
    print(ans)


    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 9248
#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);

	int a[100];
	int i;

	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	for (i = 0; i < n; i++)
	{
		if (i) printf(" ");
		printf("%d", a[n - 1 - i]);
		if (i == n - 1) printf("\n");
	}

	return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<stdio.h>
using namespace std;

int main(void){
	int num;
	cin >> num;
	int number[num];
	int i;
	for (i = num - 1; i >= 0; i--){
		cin >> number[i];
    }
    int j;
    for ( j = 0; j < num; j++ ){
        if ( j ) printf(" ");
        printf("%d", number[j]);
    }
    cout << endl;
}



Measured memory_bytes: 3236
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int h, w;
    cin >> h >> w;
    vector<vector<char>> hw(h, vector<char>(w));
    int cnt_dot = 0;
    rep(i, h) rep(j, w) {
        cin >> hw[i][j];
        if (hw[i][j] == '.') ++cnt_dot;
    }
    queue<pair<int, int>> que;
    vector<vector<int>> cnt(h, vector<int>(w, -1));
    que.push(make_pair(0, 0));
    cnt[0][0] = 1;
    int dy[4] = {1, -1, 0, 0};
    int dx[4] = {0, 0, 1, -1};
    while(!que.empty()) {
        pair<int, int> now = que.front(); que.pop();
        rep(i, 4) {
            int y = now.first + dy[i];
            int x = now.second + dx[i];
            if (y < 0 || y >= h || x < 0 || x >= w) continue;
            if (hw[y][x] == '#') continue;
            if (cnt[y][x] != -1) continue;
            que.push(make_pair(y, x));
            cnt[y][x] = cnt[now.first][now.second] + 1;
        }
    }
    if (cnt[h-1][w-1] == -1) cout << -1 << endl;
    else                     cout << cnt_dot - cnt[h-1][w-1] << endl;
    return 0;
}


Measured memory_bytes: 3624
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var nm = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var n = nm[0];
        var m = nm[1];
        var joint = new int[m][];
        for (int i = 0; i < joint.Length; i++)
        {
            joint[i] = Console.ReadLine().Split().Skip(1).Select(x => int.Parse(x)).ToArray();
        }
        var ps = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

        var jointBinary = new int[joint.Length];
        for (int i = 0; i < jointBinary.Length; i++)
        {
            jointBinary[i] = joint[i].Aggregate(0, (x, y) => x | (1 << y - 1));
        }

        var k = 0;
        for (int i = 0; i < (1 << n); i++)
        {
            var all = true;
            for (int j = 0; j < jointBinary.Length; j++)
            {
                var b = i & jointBinary[j];
                b = ((b & 0xF00) >> 8) ^ ((b & 0x0F0) >> 4) ^ (b & 0x00F);
                b = ((b & 0x00C) >> 2) ^ (b & 0x003);
                b = ((b & 0x002) >> 1) ^ (b & 0x001);
                all = all && b == ps[j];
            }
            if (all)
            {
                k++;
            }
        }
        Console.WriteLine(k);
    }
}


Measured memory_bytes: 13524
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long>a(n);
    vector<long>b(n);
    vector<long>c(n);
    for(int i=0;i<n;i++)cin >> a[i];
    for(int i=0;i<n;i++)cin >> b[i];
    for(int i=0;i<n;i++)cin >> c[i];
    
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());

    vector<long>apl(n,0);
    vector<long>bpl(n,0);

    vector<long>bsum(n,0);

    for(int i=0;i<n;i++){
        auto it = upper_bound(c.begin(),c.end(),b[i]);
        bpl[i] = c.end() - it;
    }

    bsum[n-1] = bpl[n-1];
    for(int i=n-2;i>=0;i--){
        bsum[i] = bpl[i] + bsum[i+1];
    }

    for(int i=0;i<n;i++){
        auto it = upper_bound(b.begin(),b.end(),a[i]);
        apl[i] = bsum[it - b.begin()];
    }

    long ans = 0;
    for(int i=0;i<n;i++)ans += apl[i];

    cout << ans << endl;
    

    
}

Measured memory_bytes: 7972
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<functional>
#include<stack>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin >> n;
    map<string,int> mp;
    string s;
    int maxx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        mp[s]++;
        maxx = max(maxx, mp[s]);
    }
    map<string,int>::iterator it;
    for (it=mp.begin(); it!=mp.end();it++)
    {
        if(it->second == maxx)
            cout<<(it->first)<<'\n';
    }
}

Measured memory_bytes: 17664
n = gets.chomp.to_i
a_arr = gets.chomp.split(" ").map(&:to_i)
a_arr << 0

kai_arr = []
uri_arr = []

tmp_i = 0
tmp = a_arr[tmp_i]
1.upto(n) do |i|
  if tmp < a_arr[i]
    kai_arr << tmp_i
    tmp_i = i
    tmp = a_arr[tmp_i]
  elsif tmp > a_arr[i]
    uri_arr << tmp_i
    tmp_i = i
    tmp = a_arr[tmp_i]
  end
end

stock = 0
yen = 1000
0.upto(n-1) do |i|
  kai = kai_arr[0]
  uri = uri_arr[0]
  if kai == i
    tmp_stock = yen / a_arr[i]
    yen -= tmp_stock * a_arr[i]
    stock += tmp_stock
    kai_arr.shift
  elsif uri == i
    tmp_yen = a_arr[i] * stock
    yen += tmp_yen
    stock = 0
    uri_arr.shift
  end
end

puts yen


Measured memory_bytes: 14396
import math

a,b,h,m = map(int,input().split())

theta_b = 360*m/60
theta_a = 30*(h+m/60)
theta = abs(theta_a-theta_b)

if theta > 180:
    theta = 360 - theta

ans = math.sqrt(a*a+b*b-2*a*b*math.cos(math.radians(theta)))
print(ans)

Measured memory_bytes: 9504
import java.util.Scanner;

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

		int n = sc.nextInt();
		int[] h = new int[n];

		for (int i = 0; i < n; i++) {
			h[i] = Integer.parseInt(sc.next());
		}

		int ans = 0;
		int act = 0;

		for (int i = 0; i < n; i++) {
			if (act >= h[i]) {
				act = h[i];
			} else {
				ans += h[i] - act;
				act = h[i];
			}
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 21844
import sys
sys.setrecursionlimit(10 ** 5)


def main():
    S = input()
    K = int(input())

    c = S[0]
    count = [1]
    for s in S[1:]:
        if c == s:
            count[-1] += 1
        else:
            count.append(1)
            c = s

    if S[0] != S[-1]:
        ans = sum(map(lambda x: x // 2, count))
        ans *= K
        print(ans)
        return

    if len(count) == 1:
        ans = (count[0] * K) // 2
        print(ans)
        return

    ans = 0
    for c in count:
        ans += c // 2
    count[0] += count[-1]
    ans += sum(map(lambda x: x // 2, count[:-1])) * (K - 1)
    print(ans)


main()


Measured memory_bytes: 3064
import java.util.*;

public class Main{
	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);
		double x1 = scan.nextDouble();
		double y1 = scan.nextDouble();
		double x2 = scan.nextDouble();
		double y2 = scan.nextDouble();
		double dist = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		System.out.println(dist);
	}
}

Measured memory_bytes: 27920
"""
F = [1,1]
def fibo(n):
    if n <= len(F):
        return F[n-1]
    while len(F) < n:
        F.append(F[-1] + F[-2])
    return F[n-1]
"""

N, M = list(map(int, input().split()))
A = [int(input()) for _ in range(M)]
MOD = 1000000007

if M == 0:
    B = []
    B.append(N+1)
elif M == 1:
    B = []
    B.append(A[0])
    B.append(N - A[0])

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


ans = 1
if 0 in B:
    ans = 0
else:
    F = [1,1]
    for n in B:
        while len(F) < n:
            F.append(F[-1] + F[-2])
        now = F[n-1]
        ans = ans * now % MOD
print(ans)


Measured memory_bytes: 460020