akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
 
#define for0(i,n) for(ll i = 0;i < (n);i++)
#define for1(i,n) for(ll i = 1;i<=(n);i++)
#define for2(i,n) for(ll i = 2;i<=(n);i++)
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
#define rep(i,st,en,cnt) for(ll i = st;i <= en;i+=cnt)
#define PB push_back
#define MP make_pair
#define fastio cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false)
#define F first
#define S second
#define EPS 1e-12
#define all(x) (x).begin(),(x).end()
#define INF 0x5f3f3f3f3f3f3f3f
#define NEGINF -INF
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define inp_arr(a,n) for0(i,n) {cin>>a[i];}
#define out_arr(a,n) for0(i,n) {cout<<a[i]<<" ";}
 
using namespace std;
 
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ii> vii;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<pair<ll,ll> > vll;
typedef long double LD;
 
const ll mod =  998244353;

 
ll nop = 100;
vi primes(nop,1);
 
void sieve(){
    primes[1] = primes[0] = 0;
    for(ll i = 2;i * i <= nop;i++){
        if(primes[i]){
            for(ll j = i*i; j <= nop;j+=i){
                primes[j] = 0;
            }
        }
    }
}

ll phi(ll n) {
    ll tot = n;
    for(ll i = 2;i*i <= n;i++) {
        if(n%i == 0) {
            tot -= tot/i;
        }
        while(n%i == 0) {
            n /= i;
        }
    }
    if(n > 1) {
        tot -= tot/n;
    }
    return tot;
}

 
ll gcd(ll a,ll b){    //a larger, b smaller
    if(b>a) swap(b,a);
    if(b==0) return a;
    return gcd(b,a%b);
}
 
void extgcd(ll a,ll b,ll& x,ll& y){  //a smaller b larger
    if(a==0) {
        x = a;y = b;
        return;
    }
    extgcd(b%a,a,x,y);
    ll y1 = y,x1 = x;
    x = y1 - (b/a)*x1;
    y = x1;
}
 
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}
 
ll bexp(ll num,ll e){
    ll ans = 1;
    while(e>0){
        if(e&1){
            ans *= num;
        }
        num *= num;
        e>>= 1;
    }
    return ans;
}
 
ll mexp(ll num,ll e){
    ll ans = 1;
    while(e>0){
        if(e&1){
            ans = (ans*num)%mod;
        }
        num = (num*num)%mod;
        e>>=1;
    }
    return ans%mod;
}
 
ll modinv(ll a){
    return mexp(a,mod-2);
}

ll pow3(ll a,ll b,ll& mod) {
    ll ans = 1;
    while(b>0){
        if(b&1){
            ans = (ans*a)%mod;
        }
        a = (a*a)%mod;
        b>>=1;
    }
    return ans%mod;
}
 
void solve() {
    string s;
    cin>>s;
    reverse(all(s));
    map<int,int> cnt;
    ll ans = 0;
    int tmp = 0;
    cnt[0]++;
    int pw10 = 1;
    for0(i,s.length()) {
        tmp = (tmp + ((s[i]-'0')*pw10)%2019)%2019;
        ans += (ll)cnt[tmp];
        //cout<<tmp<<" "<<ans<<endl;
        cnt[tmp]++;
        pw10 = (pw10*10)%2019;
    }
    cout<<ans<<endl;
}

int main() {
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t = 1;
    //cin>>t;
    for1(T,t) {
        solve();  
    }
    return 0;
}


Measured memory_bytes: 3696
# cf16-finalC - Interpretation
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size + 1)]
        self.rank = [0] * (size + 1)

    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # in the same group
            return
        # unite a small one to a bigger one to balance trees
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    # Union-Find on spoken languages -> check all langs are in the same group?
    N, M = map(int, input().split())
    A = [(map(int, input().split())) for _ in range(N)]
    uf, spoken = UnionFind(M), set()
    for _, *langs in A:
        spoken.update(langs)
        primary = langs[0]  # primary language for the person
        for l in langs[1:]:
            uf.unite(primary, l)
    cur = uf.find(spoken.pop())  # group of one of spoken languages
    flg = all(uf.find(lang) == cur for lang in spoken)
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Measured memory_bytes: 48104
n = gets.to_i
a = gets.chomp
A = Array.new(n+1)
x = 0
for i in 1..n
  if a[i-1] == "I"
    x += 1
    A[i-1] = x
  else
    x -= 1
    A[i-1] = x
  end
end
A[n] = 0
puts A.max

Measured memory_bytes: 1916
n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

res = 100000000000000

(n - k + 1).times do |i|
  left = a[i]
  right = a[i + k - 1]
  
  if left * right > 0
    ans = [left.abs, right.abs].max
    res = [res, ans].min
  else
    ans = [left.abs, right.abs].max + [left.abs, right.abs].min * 2
    res = [res, ans].min
  end
end

puts res

Measured memory_bytes: 11012
#include <stdio.h>
#include <string.h>

typedef struct{
	char name[100];
	int win;
	int lose;
	int prior;
}team;

void swap(team *p, team *q){
	team tmp = *p;
	*p = *q;
	*q = tmp;
}

int main(void){
	while(1){
		int n, i, j, a;
		char c[100];
		team t[10];
		
		scanf(" %d", &n);
		if(n==0) break;
	
		for(i=0; i<n; i++){
			scanf(" %s", c);
			strcpy(t[i].name, c);
			t[i].win=0;
			t[i].lose=0;
			t[i].prior=i;
			
			for(j=0; j<n-1; j++){
				scanf(" %d", &a);
				if(a==0) ++t[i].win; 
				else if(a==1) ++t[i].lose;
			}
		}
		
		for(i=0; i<n; i++){
			for(j=0; j<n; j++){
				if( (t[i].win > t[j].win) || (t[i].win==t[j].win && t[i].lose < t[j].lose) ||  (t[i].win==t[j].win && t[i].lose==t[j].lose && t[i].prior < t[j].prior) )
					swap(&t[i], &t[j]);
			}
		}
	
		for(i=0; i<n; i++)
			printf("%s\n", t[i].name);

	}

	return 0;
}

Measured memory_bytes: 592
MEMO_LENGTH = 200000

N, X, M = gets.split.map &:to_i
a = X
ans = 0
if N < MEMO_LENGTH
  N.times{
    ans += a
    a = a.pow(2, M)
  }
  p ans
  exit
end

memo = []
MEMO_LENGTH.times{
  ans += a
  memo << a
  a = a.pow(2, M)
}
last = memo[-1]
idx = memo[0..-2].rindex(last)
# p [last, idx]
period = MEMO_LENGTH - 1 - idx
period_arr = memo[idx+1..-1]
period_sum = period_arr.sum
div, mod = (N - MEMO_LENGTH).divmod(period)
# p [div,mod, period_arr]
ans += period_sum * div + period_arr.take(mod).sum
p ans

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

using namespace std;

int main(){
	string s;
	cin >> s;
	int len = s.length();
	int ans = 0;
	int zero = 0;
	int one = 0;

	for(int i = 0; i < s.length(); i++){
		if(s[i] == '1') one++;
		if(s[i] == '0') zero++;
	}

	ans = min(zero, one);

	cout << ans * 2 << endl;
}

Measured memory_bytes: 512
def main():
    n = int(input())
    x = 10 ** 13
    i = 1
    while i * i <= n:
        if n % i == 0:
            j = n // i
            x = min(x, (i - 1) + (j - 1))
        i += 1
    print(x)

if __name__ == '__main__':
    main()


Measured memory_bytes: 39152
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<complex>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


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


#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

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


/******************************************************************************************/




int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	vector<int> a(3);
	a[0] = 1;
	a[1] = 2;
	a[2] = 3;
	
	int s, t;
	cin >> s >> t;

	for (int i = 0; i < 3; i++)
	{
		if (a[i] == s) {
			a[i] = -1;
		}
		if (a[i] == t) {
			a[i] = -1;
		}
	}

	for (int i = 0; i < 3; i++)
	{
		if (a[i] != -1) {
			cout << a[i] << endl;
			return 0;
		}
	}
	


	







	return 0;
}


Measured memory_bytes: 256
#include <iostream>                                                                                                   
  
  int main(){
     int N, K;
     std::cin >> N >> K;
     int A[N];
     int index;
     for(int i=0; i<N; ++i){
        std::cin >> A[i];
        if(A[i]==1) index = i;
     }
  
    int ans = N;
     int left = index;
     int right = N - index - 1;
     for(int i=0; i<K; ++i){
        int count = 1;
        int n = std::max(0,left-i);
        count += n/(K-1);
        if(n%(K-1)!=0) count += 1;
        n = std::max(0,right-K+1+i);
        count += n/(K-1);
        if(n%(K-1)!=0) count += 1;
        if(count<ans) ans = count;
     }
     std::cout << ans << std::endl;
     return 0;
 }

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

#define INF 10000

int n,m,k,s;
int t[100][100];

int main()
{
	cin >> n;

	for(int i=0; i<100; i++)
	for(int j=0; j<100; j++)
		t[i][j] = INF;

	for(int i=0; i<100; i++)
		t[i][i] = 0;

	for(int i=0; i<n; i++)
	{
		cin >> k >> m;
		for(int j=0; j<m; j++)
		{
			cin >> s;
			t[k-1][s-1] = 1;
		}
	}

	for(int k=0; k<n; k++)
	for(int i=0; i<n; i++)
	for(int j=0; j<n; j++)
	{
		if(t[i][j]>t[i][k]+t[k][j]) t[i][j] = t[i][k]+t[k][j];
	}

	cin >> n;
	while(n--)
	{
		cin >> k >> s >> m;
		if(t[k-1][s-1]+1<=m)
		{
			cout << t[k-1][s-1]+1 << endl;
		}
		else
		{
			cout << "NA" << endl;
		}
	}

	return 0;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1)
    printEoln();
  if (suc == 2)
    printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

template <class T, class U> void chmax(T &a, U b) {
  if (a < b)
    a = b;
}

template <class T, class U> void chmin(T &a, U b) {
  if (b < a)
    a = b;
}

template <class T> T Sq(const T &t) { return t * t; }

const int mod = 1e9 + 7;

signed main() {
  int a, b, c;
  std::cin >> a >> b >> c;
  print(c - min(a - b, c));
}


Measured memory_bytes: 256
N, M = map(int, input().split())
Edge = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    Edge[a].append(b)
    Edge[b].append(a)

Visited = [False for i in range(N)]
Visited[0] = True
ans = 0
def DFS(i):
    allvisited = True
    for j in range(N):
        if Visited[j] == False:
            allvisited = False
    if allvisited:
        return 1
    else:
        ret = 0
        for node in Edge[i]:
            if Visited[node] == False:
                Visited[node] = True
                ret += DFS(node)
                Visited[node] = False
        return ret

print(DFS(0))


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

int main(){
    int a, b, c, d;
    cin >> c >> d >> a >> b;
    if(a == -1 || b == -1){
        a = d, b = c;
    }
    if(a > b)       cout << "Alice" << endl;
    else if(a < b)  cout << "Bob" << endl;
    else            cout << "Draw" << endl;
    return 0;
}


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

int selectionSort(int A[],int N) {
    int sw=0;
    for (int i=0; i<N-1; i++) {
        int minj=i;
        for (int j=i; j<N; j++) {
            if (A[j]<A[minj]) {
                minj=j;
            }
        }
        int t=A[i];
        A[i]=A[minj];
        A[minj]=t;
        if (i!=minj) {
            sw++;
        }
    }
    return sw;
}
int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i=0; i<N; i++) {
        cin >> A[i];
    }
    int sw=selectionSort(A,N);
    for (int i=0; i<N; i++) {
        printf("%s%d",((i==0)?"":" "),A[i]);
    }
    printf("\n");
    printf("%d\n",sw);
    return 0;
}

Measured memory_bytes: 3164
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;

int main()
{
	double x;
	cin >> x;
	const double PI = acos(0) * 2;
	cout << setprecision(5) << fixed << PI * x * x << " " << 2 * PI * x;
}



Measured memory_bytes: 3284
N = int(input())
data = [input() for x in range(N)]

keys_list = ['AC','WA','TLE','RE']
check_list = {'AC':0,'WA':0,'TLE':0,'RE':0}

for x in data:
    check_list[x] = check_list[x] + 1

for x in keys_list:
    print('{} x {}'.format(x,check_list[x]))


Measured memory_bytes: 16328
//	C++ (Clang3.8.0)
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
	string s;
	bool f = true;
	
	cin >> s;
	
	if(s.empty() == 0 && s.size()%2==0){
		for(int i=0; i<s.size()/2; ++i){
			if(s[2*i]!='h' || s[2*i+1]!='i'){
				f = false;
				break;
			}
		}
	}else {
		f = false;
	}
	
	if(f){
		cout << "Yes";
	}else {
		cout << "No";
	}
	
	return 0;
}

Measured memory_bytes: 888
from pprint import pprint

n,w = map(int,input().split())

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i-1][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            #i番目の品物を選ばない場合
            dp_table[i][sum_w] = dp_table[i-1][sum_w]


result = dp_table[n][w]
print(result)


Measured memory_bytes: 306968
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;

const int MAXN = 1e5 + 10;
int N;
long long _2[MAXN], _3[MAXN], tot;
map<long long, long long> cnt, mp;
long long ans;

int main() {
	register long long i, j;
	long long x;
	scanf("%d", &N);
	for(i = 1; i <= N; ++i) {
		scanf("%lld", &x); _2[i] = _3[i] = 1;
		for(j = 2; j * j * j <= x; ++j) {
			tot = 0;
			while(x % j == 0) x /= j, ++tot;
			if(tot % 3 == 1) _2[i] *= j, _3[i] *= j * j;
			if(tot % 3 == 2) _2[i] *= j * j, _3[i] *= j;
		}
		_2[i] *= x; _3[i] *= (long long) pow(x, 1.0L / 2) * (long long) pow(x, 1.0L / 2) == x ? pow(x, 1.0L / 2) : x * x;
		++cnt[_2[i]];
	}
	for(i = 1; i <= N; ++i)
		if(mp.count(_2[i]) == 0) {
			mp[_2[i]] = mp[_3[i]] = 1;
			if(_2[i] == 1) ++ans;
			else ans += max(cnt[_2[i]], cnt[_3[i]]);
		}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 22400
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define itn int
typedef long long ll;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };

signed main() {
	int h, w,H,W;
	cin >> H >> W;
	cin >> h >> w;
	int gridSize = H * W;
	int ans;
	ans = gridSize - (h * W + (H - h) * w);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
namespace AOJ
{
    class Program
    {
        static void Main()
        {
            var input = Console.ReadLine().Split(' ').Select(x=>int.Parse(x)).ToArray();
            Console.WriteLine((input[0] * input[1]) + " " + ((input[0] + input[1]) * 2));
        }
    }
}

Measured memory_bytes: 5860
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n,m,s,c;
    cin>>n>>m;
    vector<ll> num(n,-1);
    rep(i,m){
        cin>>s>>c;
        if(num[s-1]==-1||num[s-1]==c) num[s-1]=c;
        else{
            cout<<-1<<endl;
            return 0;
        }
    }
    if(n!=1&&num[0]==0){
        cout<<-1<<endl;
        return 0;
    }
    rep(i,n){
        if(i!=0||n==1){
            if(num[i]==-1) num[i]=0;
        }else{
            if(num[i]==-1) num[i]=1;
        }
        cout<<num[i];
    }
    cout<<endl;
    return 0;
}

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

int main()
{
    long long n, m, answer;
    cin >> n >> m;
    if(n == 1 && m ==1){
        answer = 1;
    }else if(n == 1 || m == 1){
        answer = n * m -2;
    }else{
        answer = (n-2)*(m-2);
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
import bisect


def main():
    N, M, K = map(int, input().split())
    A = [int(v) for v in input().split()]
    B = [int(v) for v in input().split()]
    ruisekiA = [0 for _ in range(N+1)]
    ruisekiB = [0 for _ in range(M+1)]
    for i in range(N):
        ruisekiA[i + 1] = ruisekiA[i] + A[i]
    for i in range(M):
        ruisekiB[i + 1] = ruisekiB[i] + B[i]

    ans = 0
    # A を i 個 使う
    for i in range(N+1):
        tans = i
        tk = K - ruisekiA[i]
        if tk < 0:
            break
        idx = bisect.bisect_left(ruisekiB, tk)
        if M+1 == idx or ruisekiB[idx] != tk:
            idx -= 1
        tans += idx
        ans = max(ans, tans)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 133048
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i,l,r) for(int i=l;i<=r;i++)
int d[3000][3000];
int n;
int a[3000];
int deq(int i,int j)
{int l = n-(j-i+1)+1;
	if(j<i)return 0;
    if(d[i][j]!=-1)return d[i][j];
     
	if(l%2==0)
	      {
             d[i][j]=min(deq(i+1,j)-a[i],deq(i,j-1)-a[j]);
	      }
		else
		  {
              d[i][j]=max(deq(i+1,j)+a[i],deq(i,j-1)+a[j]);
		  }
		  return d[i][j];
}
signed main()
{   //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //int n;
    cin>>n;
    memset(d,-1,sizeof(d[0][0])*3000*3000);
    for(int i=0;i<n;i++)cin>>a[i];
    
    cout<<deq(0,n-1)<<endl;


    return 0;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

ll x[100000];
int main() {
	ll n, a, b; scanf("%lld%lld%lld", &n, &a, &b);
	ll sum = 0;
	rep(i, n)scanf("%lld", &x[i]);
	rep(i, n - 1) {
		sum += min((x[i + 1] - x[i])*a, b);
	}
	printf("%lld\n", sum);
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = MOD - 1;
const ll LLINF= 4e18;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> G(n);
    stack<int> sta;
    vector<int> in(n,0);// 入次数
    vector<int> ans;
    REP(i, m) {
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        in[b]++;
    }// DAGか判定
// DAGなら最長経路を求める
// DAGでないなら-1
// nが頂点数
    REP(i, n) if (in[i] == 0) {
        sta.push(i);
    }
    while (!sta.empty()) {
        int p = sta.top(); sta.pop();
        ans.push_back(p);
        for (int v : G[p]) {
            in[v]--;
            if (in[v] == 0) {
                sta.push(v);
            }
        }
    }
    REP(i, ans.size()) {
        cout << ans[i]+1 << endl;
    }
}


Measured memory_bytes: 3140
# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    s = input()

    # See:
    # http://agc003.contest.atcoder.jp/data/agc/003/editorial.pdf
    # https://beta.atcoder.jp/contests/agc003/submissions/849782
    if (('S' in s) ^ ('N' in s)) or (('W' in s) ^ ('E' in s)):
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 2940
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k, r int
	fmt.Scan(&n, &k)
	p := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&r)
		p[i] = r
	}
	sort.Sort(sort.IntSlice(p))

	result := 0
	for i := 0; i < k; i++ {
		result += p[i]
	}
	fmt.Println(result)
}


Measured memory_bytes: 1888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
//constexpr ll MOD = 998244353;
//constexpr ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
constexpr ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)

int main()
{
  ll H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (ll i = 0; i < H; i++)
  {
    cin >> S.at(i);
  }

  vector<vector<ll>> dp(H, vector<ll>(W, INF));
  dp.at(0).at(0) = (S.at(0).at(0) == '#');

  for (ll d = 1; d < H + W - 1; d++)
  {
    for (ll i = 0; i < H; i++)
    {
      ll j = d - i;
      if (!(0 <= j && j < W))
        continue;
      
      if (i != 0)
      {
        bool b = (S.at(i - 1).at(j) == '.' && S.at(i).at(j) == '#');
        chmin(dp.at(i).at(j), dp.at(i - 1).at(j) + b);
      }
      if (j != 0)
      {
        bool b = (S.at(i).at(j - 1) == '.' && S.at(i).at(j) == '#');
        chmin(dp.at(i).at(j), dp.at(i).at(j - 1) + b);
      }
    }
  }

  /*
  for (ll i = 0; i < H; i++)
  {
    for (ll j = 0; j < W; j++)
    {
      cerr << dp.at(i).at(j) << " ";
    }
    cerr << endl;
  }
  //*/

  ll ans = dp.at(H - 1).at(W - 1);
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(5)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef complex<double> Point;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int n, s;
int memo[11][800][1 << 10];

int solve(int i, int j, int v)
{
	if (memo[i][j][v] >= 0) return memo[i][j][v];
	if (i == n)
	{
		if (j == s) return 1;
		else return 0;
	}

	int res = 0;
	REP(k, 10)
	{
		if ((v >> k) & 1) continue;
		if (j + k*(i + 1) > s) break;
		res += solve(i + 1, j + (i + 1)*k, v | (1 << k));
	}
	return memo[i][j][v] = res;
}

int main()
{
	while (cin >> n >> s)
	{
		MS(memo, -1);
		cout << solve(0, 0, 0) << endl;
	}
	return 0;
}

Measured memory_bytes: 36368
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;


signed main() {
  int H, W, D; 
  cin >> H >> W >> D;

  vector<vector<int>> A(H, vector<int>(W));
  REP(i, H) REP(j, W) cin >> A[i][j];

  vector<pair<int, int>> pos(H*W+1);
  REP(i, H) REP(j, W){
    pos[A[i][j]] = {i, j};
  }

  vector<int> sum(H*W+1, 0);
  FOR(i, D+1, H*W+1){
    sum[i] = sum[i-D]+abs(pos[i].first-pos[i-D].first)+abs(pos[i].second-pos[i-D].second);
  }
  
  int Q;
  cin >> Q;
  while(Q--){
    int l, r;
    cin >> l >> r;

    cout << sum[r]-sum[l] << endl;
  }

  return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <map>

using namespace std;

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

	string S;
	cin >> S;

	for (int i = 0; i < S.size(); i++)
	{
		cout << "x";
	}

	return 0;
}

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

int a[109];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        a[p]++;
        mx = max(mx, p);
    }
    for (int i = 0; i <= mx; i++) {
        int t = max(i, mx - i);
        if (a[t] <= 0) {
            cout << "Impossible" << '\n';
            return 0;
        }
        a[t]--;
    }
    for (int i = 1; i <= (mx + 1) / 2; i++)
        if (a[i] > 0) {
            cout << "Impossible" << '\n';
            return 0;
        }
    cout << "Possible" << '\n';
    return 0;
}


Measured memory_bytes: 256
let lower_bound (a : int array) first last v =
  let rec doit len first =
    if len = 0 then first
    else
      let half = len / 2 in
      let mid = first + half in
      if a.(mid) < v then doit (len - half - 1) (mid + 1)
      else doit half first in
  doit (last - first + 1) first

let () =
  let n = read_int () in
  let dp = Array.make (n + 1) max_int in
  let l = ref 0 in
  for _ = 0 to n - 1 do
    let a = read_int () in
    let x = lower_bound dp 0 n a in
    dp.(x) <- a;
    if x + 1 > !l then l := x + 1;
  done;
  Printf.printf "%d\n" !l

Measured memory_bytes: 5280
n = input()
t = int(n)
num = t-2
list = input().rstrip().split(" ")
target = []
for i in list:
    target.append(int(i))
target.sort()
target.reverse()
ans = target[0]
i = 1
k = 0
while num > 0:
    ans += target[i]
    k += 1
    num -=1
    if k == 2:
        i += 1
        k = 0
print(ans)

Measured memory_bytes: 31756
#include <iostream>
#include <cstring>
#include <algorithm>
#include <list>
#include <map>
#include <cmath>
#include <string>
#include <iterator>
#include <vector>
 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 26;

int largest(int a, int b){
	return (a<b)?b:a;
}


int main() {
	int n = 0;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	for(int i = 0; i < n; ++i){
		cin >> a[i];
		b[i] = a[i];
	}
	int cnt = 0;
	sort(b.begin(), b.end());
	for(int i = 0; i < n; ++i){
		if(a[i] != b[i]){
			++cnt;
		}
		if(cnt > 2){
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;

    return 0;
}

Measured memory_bytes: 256
//ABC150 D

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = s; i < (int)(n); i++)
const lint mod = 1000000007;


lint ans = 0;
lint N,M;
lint A[100000];


lint gcd(lint a, lint b){
  if (a%b == 0){
      return(b);
  }
  else{
      return(gcd(b, a%b));
  }
}

lint lcm(lint a, lint b){
   return ((a * b) / gcd(a, b));
}

lint cnt(lint x){
  lint res = 0;
  while(x%2 == 0){
    x /= 2;
    res++;
  }
  return res;
}

int main() {
  cin >> N >> M;
  
  lint hkbs = 1;
  rep(i,N){
    scanf("%lld",&A[i]);
    A[i] /= 2;
  }
  lint tmp = cnt(A[0]);
  hkbs = lcm(hkbs,A[0]);
  reps(i,1,N){
    if(tmp != cnt(A[i])){
      cout << "0" << endl;
      return 0;
    }
    if(hkbs < A[i]){
      hkbs = lcm(A[i],hkbs);
    }
    else{
      hkbs = lcm(hkbs,A[i]);
    }
  }
  

  ans = M/hkbs;
  ans = (ans+1)/2;

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


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#define MAX 500000
#define NIL NULL
struct t{
  int val;
  struct t *parent,*left,*right;
};
typedef struct t * T;
int n;
T root=NIL;

void insert(int u){
  T next,look,z;
  z=(T)malloc(sizeof(struct t));
  z->val=u;
  z->parent=z->left=z->right=NIL;
  next=root;
  look=NIL;
  while(next!=NIL){
    look=next;
    if(z->val > look->val) next=look->right;
    else next=look->left;
  }
  z->parent=look;

  if(z->parent==NIL) root=z;
  else if(z->val > look->val) look->right=z;
  else look->left=z;

}
void preorder(T u){
  if(u==NIL) return;
  printf(" %d",u->val);
  preorder(u->left);
  preorder(u->right);
}
void inorder(T u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->val);
  inorder(u->right);
}
int main(){
  int i,u;
  char com[10];
  scanf("%d",&n);
  //for(i=0;i<n;i++) tree[i].p=tree[i].l=tree[i].r=NIL;

  for(i=0;i<n;i++){
    scanf("%s",com);
    if(com[0]=='i'){
      scanf("%d",&u);
      insert(u);
    }else{
       inorder(root);
       printf("\n");
       preorder(root);
       printf("\n");
     }
  }
  return 0;
}



Measured memory_bytes: 25148
#include <stdio.h>

int check_num(int a, int n) {
    if(a==n) return 1;
    else return 0;
}

int main() {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);

    int c5=0, c7=0;
    c5 += check_num(A, 5);
    c5 += check_num(B, 5);
    c5 += check_num(C, 5);
    c7 += check_num(A, 7);
    c7 += check_num(B, 7);
    c7 += check_num(C, 7);

    if((c5==2)&&(c7==1)) printf("YES\n");
    else printf("NO\n");

    return 0;

}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

ll t;
string n;

ll ans1, ans2;
vector<string>ans_v;

void solve(vector<string> v){
	// for(ll i = 0; i < v.size(); i++)cout << v[i] << ",";
	// cout << endl;
	ll sum = 0;
	for(ll i = 0; i < v.size(); i++){
		stringstream ss;
		ss << v[i];
		ll tmp;
		ss >> tmp;
		sum += tmp;
	}
	if(t < sum)return;
	if(ans1 == sum)ans2++;
	if(ans1 < sum){
		ans1 = sum;
		ans2 = 1;
		ans_v = v;
	}
}

int main(){

	for(;cin >> t >> n;){
		if(t == 0 && n == "0")break;
		ans1 = -1;
		ans2 = 0;
		for(ll i = 0; i < (1 << (n.size() - 1)); i++){
			vector<string>v;
			string tmp = "";
			for(ll j = 0; j < n.size(); j++){
				tmp += n[j];
				if(i & (1 << j)){
					v.push_back(tmp);
					tmp = "";
				}
			}
			if(tmp != "")v.push_back(tmp);
			solve(v);
		}
		if(ans1 < 0)cout << "error" << endl;
		else if(ans2 > 1)cout << "rejected" << endl;
		else{
			cout << ans1;
			rep(i, ans_v.size())if(ans_v[i].size())cout << " " << ans_v[i];
			cout << endl;
		}
	}

    return 0;
}


Measured memory_bytes: 3124
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <random>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
//const double EPS = 1e(-12);
const double pi = acos(-1);
typedef pair<int, int> P;
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
#define OUTPUT(i) (cout << (ll)i << endl)
#define ALL(a) ((a).begin(), (a).end())

int arr[110];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);

    ll N;
    cin >> N;

    for (int i = 2; i <= N; ++i)
    {
        int t = i;
        for (int j = 2; j <= t; ++j)
        {
            int cnt = 0;
            while (t % j == 0)
            {
                t /= j;
                cnt++;
            }
            arr[j] += cnt;
        }
    }

    /*for (int i = 0; i <= N; ++i)
        cout << arr[i] << " ";
    cout << endl;*/

    ll ans = 0;

    ll t2 = 0, t4 = 0, t14 = 0, t24 = 0,
       t74 = 0;
    for (int i = 0; i <= 100; ++i)
    {
        if (arr[i] >= 2)
            t2++;
        if (arr[i] >= 4)
            t4++;
        if (arr[i] >= 14)
            t14++;
        if (arr[i] >= 24)
            t24++;
        if (arr[i] >= 74)
            t74++;
    }
    //cout << t2 << " " << t4 << " " << t14 << " " << t24 << " " << t74 << endl;
    ans += t74;

    ans += t4 * (t4 - 1) / 2 * (t2 - 2);

    ans += t24 * (t2 - 1);

    ans += (t4 - 1) * t14;

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

Measured memory_bytes: 256
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
def inpl(): return list(map(int, input().split()))

#### START
N = int(input())
s = input()

ans = 0
for i in range(1, N):
  aset = set(list(s[0:i]))
  bset = set(list(s[i:]))
  ta = len(aset & bset)
  if ta>ans:
    ans=ta

print(ans)

Measured memory_bytes: 3444
#include <cstdio>

int N,M,Q;
int as[199999];
int result[199999];
int pos[199999];
int used[199999];
int added[199999];
int ok[199999];
int main() {
	scanf("%d%d%d",&N,&M,&Q);
	for(int i=1;i<=Q;i++) scanf("%d",&as[i]);
	int rlen=1;
	for(int i=Q;i>0;i--) {
		if(used[as[i]]==0) {
			used[as[i]]=1;
			result[rlen++]=as[i];
		}
	}
	for(int i=1;i<=M;i++) if(used[i]==0) result[rlen++]=i;
	int ed=0;
	for(int i=1;i<M;i++) if(result[i]>result[i+1]) ed=i;
	for(int i=1;i<=M;i++) pos[result[i]]=i;
	ok[0]=N;
	for(int i=Q;i>0;i--) {
		int nw=pos[as[i]];
		if(nw<=ed) {
			if(ok[nw]<ok[nw-1]) ok[nw]++;
		}
	}
	for(int i=1;i<=ed;i++) if(ok[i]<N) {
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 2176
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    std::ios::sync_with_stdio(false);

    string N;
    cin >> N;
    if (N[0] == N[1] && N[0] ==  N[2] || N[1] == N[2] && N[1] == N[3] )
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 256
function main(input) {
  const args = input.split(' ');
  const a = parseInt(args[0], 10);
  const b = parseInt(args[1], 10);
  
  if ( a * b % 2 == 0){
    console.log('Even');
  }else{
    console.log('Odd');
  }
  
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
/*
    PHULKAARI 
                --Gippy Grewal
                                            */
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
//#include <boost/functional/hash.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int lli;
lli mod=1e9+7ll;
lli INF=1e17;
#define sqr(x) (x) * (x)
#define bip(n) __builtin_popcountll(n)//no of ones bit in binary!!
#define bictz(n) __builtin_ctzll(n)//no of trailing zeroes in binary!!
#define biclz(n) __builtin_clzll(n)//no of leading zeroes in binary!!
#define bffs(n) __builtin_ffsll(n)//index of first one bit!!
typedef pair<lli,lli> ll;
#define mem1(a,x) fill(&a[0], &a[0] + sizeof(a) / sizeof(a[0]), x)
#define mem2(a,x) fill(&a[0][0], &a[0][0] +sizeof(a)/sizeof(a[0][0]),x)
#define mem3(a,x) fill(&a[0][0][0], &a[0][0][0] +sizeof(a)/sizeof(a[0][0][0]),x)
#define fi1 ifstream fin("input.txt")
#define of1 ofstream fout("output.txt")
int fmx(int x, int y) { return (((y-x)>>(31))&(x^y))^y; }
int fmi(int x, int y) { return (((y-x)>>(31))&(x^y))^x; }
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ost;
lli n,q,z,y,k,m;
const double pi1=3.14159265358979323846;
//matrix exponentiation is associative and distributive
lli me(lli a,lli b)
{
    lli res=1;
    while(b)
    {
        if(b&1)
        res=(res%mod*a%mod)%mod;
        a=a*a;
        a%=mod;
        b=b>>1;
    }
    return res;
}
lli mI(lli a)
{
    return (me(a,mod-2)%mod+mod)%mod;
}
bool cmp(ll a,ll b)
{
    if(a.first==b.first)
    return a.second<b.second;
    return a.first<b.first;
}
lli dp[2005][2005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin>>n>>k;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=(dp[i-1][j-1]%mod+dp[i-1][j]%mod+mod)%mod;
        }
    }
    for(int i=1;i<=k;i++)
    {
        lli dd=(dp[k-1][k-i]%mod*dp[n-k+1][n-k-i+1]%mod)%mod;
        cout<<dd<<"\n";
    }
    // cout << a.a[0][0] << " " <<a.a[0][1] << " " << a.a[1][0] << " " << a.a[1][1] <<"\n";
}

Measured memory_bytes: 30208
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i,s,n) for(ll i=(s);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n,k;cin>>n>>k;
    vin a(n);
    rep(i,n)cin>>a[i];
    int g=0;
    rep(i,n)g=__gcd(g,a[i]);
    rep(i,n){
        if(a[i]/k>0&&(a[i]%k)%g==0){
            cout<<"POSSIBLE"<<endl;
            return 0;
        }
    }
    cout<<"IMPOSSIBLE"<<endl;
}

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

using namespace std;

const int MAXN = 1e5 + 15;

int N, K, Q;
int cnt[MAXN];

int main() {

	scanf("%d%d%d", &N, &K, &Q);

	for( int player, i=0 ; i<Q ; i++ ) {
		scanf("%d", &player);
		cnt[player]++;
	}

	for( int i=1 ; i <= N ; i++ ) {
		if ( K - Q + cnt[i] > 0 ) {
			puts("Yes");
		} else {
			puts("No");
		}
	}

	return 0;
}

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


int64_t luca(int n) {
  if(n == 0) {
    return 2;
  }
  else if (n == 1) {
    return 1;
  }
  else {
    return luca(n-1) + luca(n-2);
  }
}

int main() {
  int n;
  cin >> n;
  long long ret = 0;
  long long prev_2 = 2;
  long long prev_1 = 1;
  if(n == 0) {
    cout << 2 << endl;
    return 0;
  }
  else if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  for(int i = 0; i<n-1; i++) {
    ret = prev_1 + prev_2;
    prev_2 = prev_1;
    prev_1 = ret;
  }
  cout << ret << endl;
  return 0;
} 
  



Measured memory_bytes: 256
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int main() {
    char a,b;
    cin>>a>>b;
    if(a==b)cout<<"H"<<endl;
    else cout<<"D"<<endl;
    return 0;
}

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

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

Measured memory_bytes: 640
n,x,m=map(int,input().split())
# -1はまだ来てない
order=[-1 for i in range(m)]
index=0
#0,1,2,...　番目の数字を配列で記憶高々mこ
a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1
#1周期の和
tmp=sum(a[order[x]:index])
T=index-order[x]
if(n-1<order[x]):
    print(sum(a[:n]))
else:
    #ループ前の和
    sum1=sum(a[:order[x]])
    #ループ前を全体から引いた数
    x1=n-order[x]
    #ループ回数
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))


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

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

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> ks(m);
  rep(i, m) {
    int k;
    cin >> k;
    vector<int> s(k);
    rep(j, k) {
      int ss;
      cin >> ss;
      ss--;
      s[j] = ss;
    }
    sort(s.begin(), s.end());
    ks[i] = s;
  }
  vector<int> p(m);
  rep(i, m) {
    cin >> p[i];
  }

  ll res = 0;
  for (int bit = 0; bit < (1 << n); ++bit) {
    vector<int> S;
    for (int i = 0; i < n; ++i) {
      if (bit & (1 << i)) {
        S.push_back(i);
      }
    }
    bool allOk = true;
    rep(i, m) {
      int pp = p[i];
      int cnt = 0;
      vector<int> k = ks[i];
      for (int kk : k) {
        if (find(S.begin(), S.end(), kk) != S.end()) {
          cnt++;
        }
      }
      if (cnt % 2 != pp) {
        allOk = false;
        break;
      }
    }
    if (allOk) {
      res++;
    }
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;

#define m(a, b) memset(a, b, sizeof(a))
#define py(b, a) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & (-x))

const int maxn = 1e5 + 10;
const int inf = 1e9;
typedef long long LL;
typedef pair<int, int> PII;

LL num;
LL pos, last;
LL gcd(LL n, LL m){
	if(m == 0) return n;
	else return gcd(m, n % m);
}
int main(){
	int n, ans = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++){
		scanf("%d", &num);
		ans += num - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
import collections
n = int(input())
a = [int(x) for x in input().split()]
even = []
uneven = []
for i in range(n):
  if i%2 == 0:
    uneven.append(a[i])
    continue
  even.append(a[i])

uneven_counter = collections.Counter(uneven)
sortede_uneven_counter = sorted(uneven_counter.items(),key=lambda x:x[1],reverse=True)
even_counter = collections.Counter(even)
sortede_even_counter = sorted(even_counter.items(),key=lambda x:x[1],reverse=True)
  
ans = (n/2 - sortede_uneven_counter[0][1]) + (n/2 - sortede_even_counter[0][1])

if sortede_uneven_counter[0][0] == sortede_even_counter[0][0]:
  if len(set(a)) == 1:
    ans = n/2
  elif sortede_uneven_counter[0][0] ==sortede_even_counter[0][0]:
    ans = (n/2 - sortede_uneven_counter[1][1]) + (n/2 - sortede_even_counter[0][1])
    ans2 = (n/2 - sortede_uneven_counter[0][1]) + (n/2 - sortede_even_counter[1][1])
    if ans2<ans:
      ans = ans2

print(int(ans))

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

#define int long long
const int INF = 1e9+1;

signed main() {
	int N;
	cin >> N;
	
	vector<int> A(N), B(N);
	int ans = 0;
	int mi = INF;
	for ( int i = 0; i < N; i++ ) {
		cin >> A[i] >> B[i];
		if ( A[i] > B[i] ) mi = min(mi, B[i]);
		ans += A[i];		
	}

	ans -= mi;
	if ( A == B ) ans = 0;
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 512
//In the Name of God
//Ya Ali

#include <bits/stdc++.h>

#define int long long

#define err(A) cout << #A << " = " << (A) << endl

using namespace std;

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

  int n;
  cin >> n;

  if (n % 2)
    {
      cout << 0 << endl;
      return 0;
    }

  int ans = 0;
  for (int t = 5; t <= n; t *= 5)
    ans += (n / t) / 2;

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


Measured memory_bytes: 256