akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N,M;
  cin >> N >> M;
  vector<int> A(M);
  int task=0;
  for(int i=0; i<M; i++){
    cin >> A.at(i);
    task += A.at(i);
  }
  if (task <= N){
    cout << N - task << endl;
  }
  else {
    cout << "-1" << endl;
  }
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

int
main()
{
  string s;
  cin >> s;
  cout << ((s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) ? "Bad" : "Good") << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.next().split("");
        for(int i=0;i<s.length;i++){
            if(i%2==0){
                if(!s[i].equals("h")){
                    System.out.println("No");
                    return;
                }
            }
            else{
                if(!s[i].equals("i")){
                    System.out.println("No");
                    return;
                }
            }
        }
        if(s.length==1 || s.length%2==1){
            System.out.println("No");   
            return; 
        }
        System.out.println("Yes");
    }
}


Measured memory_bytes: 23764
# coding:utf-8

import sys
import heapq
from collections import defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def dijkstra(start: int, size: int, graph: dict) -> list:
    costs = [INF] * size
    costs[start] = 0
    visited = set()
    hp = []
    heapq.heappush(hp, (0, start))
    while hp:
        hc, hv = heapq.heappop(hp)
        if hv in visited:
            continue
        for to, move_cost in graph[hv]:
            if hc + move_cost >= costs[to]:
                continue
            costs[to] = hc + move_cost
            heapq.heappush(hp, (costs[to], to))
        visited.add(hv)

    return costs


n = II()

G = defaultdict(list)
for _ in range(n - 1):
    a, b, c = LI()
    a -= 1
    b -= 1
    G[a].append((b, c))
    G[b].append((a, c))

q, k = LI()
k -= 1
C = dijkstra(k, n, G)

for _ in range(q):
    x, y = LI_()
    print(C[x] + C[y])


Measured memory_bytes: 58480
h, w = map(int,input().split())
s_l = []
for i in range(h):
    s_l.append(list(input()))

for i in range(h):
    s_l[i].insert(w,'*')
    s_l[i].insert(0,'*')

s_add = ['*']*(w+2)
s_l.insert(h,s_add)
s_l.insert(0,s_add)

for i in range(1,h+1):
    for j in range(1,w+1):
        if s_l[i][j] == '.':
            count = 0
            for k in range(i-1,i+2):
                for l in range(j-1,j+2):
                    if s_l[k][l] == '#':
                        count += 1
            s_l[i][j] = str(count)

s_l_result = s_l[1:h+1]
for i in range(h):
    print(''.join(s_l_result[i][1:w+1]))

Measured memory_bytes: 3188
#include<iostream>

using namespace std;

unsigned long long yakusu(unsigned long long a, unsigned long long b) {
	while (a != b) {
		if (a > b)
			a%b == 0 ? (a -= b * (a / b - 1)) : (a -= b * (a / b));
		else
			b%a == 0 ? (b -= a * (b / a - 1)) : (b -= a * (b / a));
	}

	return a;
}

int main() {
	int n, i;
	unsigned long long time, *ti, yaku, t;


	cin >> n;

	ti = new unsigned long long [n];
	
	for (i = 0; i < n; i++) {
		cin >> time;
		ti[i] = time;
	}

	if (n == 1) {
		cout << ti[0];
		return 0;
	}

	yaku = yakusu(ti[0], ti[1]);
	time = yaku * (ti[0] / yaku)*(ti[1] / yaku);

	for (i = 2; i < n; i++) {
		t = ti[i];
		if (time%t == 0)
			continue;
		if (t % time == 0) {
			time = t;
			continue;
		}
		yaku = yakusu(time, t);
		time = yaku * (time / yaku)*(t / yaku);
	}

	cout << time;

	return 0;
}


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

int main() {
    int N, K; cin >> N >> K;
    vector<int> A(N);
    rep(i, N){
        cin >> A[i];
    }

    int cnt = min(50, K);

    rep(i, cnt){
        vector<int> B(N+1);
        rep(j, N){
            int a = A[j];
            int l = max(0, j-a);
            int r = min(N, j+a+1);
            B[l]++;
            B[r]--;
        }
        for (int j = 1; j < N; j++){
            B[j] += B[j-1];
        }
        B.pop_back();
        A = B;
    }

    rep(i, N){
        cout << A[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 4800
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>

int n;
static const int nmax = 2005;
static const int INFTY = (1<<21);
static const int WHITE = 0; // Not visited
static const int GRAY = 1;  // Visited
static const int BLACK = 2; // In MST
std::array<std::array<int, nmax>, nmax> adjmat;
std::array<int, nmax> d, p;
std::array<int, nmax> color;

void dijklstra(int v)
{
  color.fill(WHITE);
  d.fill(INFTY);
  p.fill(-1);

  d[v] = 0;
  color[v] = GRAY;

  while (true)
    {
      auto mincost = INFTY;

      // Find minimum cost vertex from current MST
      for (int i=0; i<n; ++i)
        {
          if (color[i] != BLACK && d[i] < mincost)
            {
              mincost = d[i];
              v = i;
            }
        }
      //std::cout << v << std::endl;
      //std::for_each(d.begin(), d.begin()+n, [](auto x){std::cout << x << ' ';});
      //std::cout << std::endl;
      // Break if no update
      if (mincost == INFTY) break;

      // Include v in MST
      color[v] = BLACK;

      // Update minimum cost outside current MST
      for (int i=0; i<n; ++i)
        {
          if ( (color[i] != BLACK) && ((d[v] + adjmat[v][i]) < d[i]))
            {
              d[i] = d[v] + adjmat[v][i];
              color[i] = GRAY;
              p[i] = v;
            }
        }
    }
}

void print_distance(int v)
{
  dijklstra(v);

  for (int i=0; i<n; ++i)
    {
      std::cout << i << " " << d[i] << std::endl;
    }
}

int main ()
{
  std::cin >> n;

  for (int i=0; i<n; ++i){
    for (int j=0; j<n; ++j)
      adjmat[i][j] = INFTY;
  }
  for (int i=0; i<n; ++i)
    {
      int u, k;
      std::cin >> u >> k;
      for (int j=0; j<k; ++j)
        {
          int v, c;
          std::cin >> v >> c;
          adjmat[u][v] = c;
        }
    }

  print_distance(0);
}



Measured memory_bytes: 3576
N = int(input())
S = input()

count = 0

for i in range(10):
    c = S.find(str(i))
    if c > -1:
        for j in range(10):
            d = S[c + 1:].find(str(j))
            if d > -1:
                for k in range(10):
                    e = S[c + 1 + d + 1:].find(str(k))
                    if e > -1:
                        count += 1
print(count)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	long long int n,k,y,l(1);
   cin>>n;
  k=pow(10,18);
  for(int i=0;i<n;i++)
  {
    cin>>y;
    if(y==0)
    {
      l=0;
      k=1;
      break;
    }
    k=k/y;
    l*=y;
  }
  if(k==0)
  {
    cout<<"-1";
  }
  else cout<<l;
}

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


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int **c = new int*[3];
    for (int i = 0; i < 3; i++) {
        c[i] = new int[3];
        for (int j = 0; j < 3; j++)
            cin >> c[i][j];
    }

    int b_2 = c[0][1] - c[0][0], b_3 = c[0][2] - c[0][0];
    if (c[1][1]-b_2 != c[1][0] || c[1][0] != c[1][2] - b_3) {
        cout << "No" << endl;
        return 0;
    }
    if (c[2][1]-b_2 != c[2][0] || c[2][0] != c[2][2] - b_3) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define FUP(i,x,y) for(int i=(x);i<=(y);i++)
#define FDW(i,x,y) for(int i=(x);i>=(y);i--)
#define MAXN 20
#define INF 0x7fffffff
#define MOD 1000000007
#define ll long long
#define db double
using namespace std;
int read(){
    int w=0,flg=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')flg=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){w=w*10-'0'+ch,ch=getchar();}
    return w*flg;
}
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int abs(int x){return x<0?(-x):x;}
int n,num[MAXN],x[MAXN][MAXN],y[MAXN][MAXN],pd[MAXN][2],ans;
void dfs(int over)
{
	if(over==n)
	{
		int re=0;
		FUP(i,1,n)
		{
			if(pd[i][1]!=0)
			{
				//printf("%d,",i);
				re++;
			}
		}
		//puts("");
		ans=max(ans,re);
	}
	else
	{
		int u=over+1;
		if(pd[u][0]==0&&pd[u][1]==0)
		{
			pd[u][1]++;
			bool ck=false;
			FUP(i,1,num[u])
			{
				bool p1=(y[u][i]==0&&pd[x[u][i]][1]!=0);
				bool p2=(y[u][i]==1&&pd[x[u][i]][0]!=0);
				if(p1||p2)
				{
					FUP(j,1,i-1)
					{
						pd[x[u][j]][y[u][j]]--;
					}
					ck=true;
					break;
				}
				else
				{
					pd[x[u][i]][y[u][i]]++;
				}
			}
			if(!ck)
			{
				dfs(u);
				FUP(i,1,num[u])
				{
					pd[x[u][i]][y[u][i]]--;
				}
			}
			pd[u][1]--;
			pd[u][0]++;
			dfs(u);
			pd[u][0]--;
		}
		else if(pd[u][0]!=0)
		{
			pd[u][0]++;
			dfs(u);
			pd[u][0]--;
		}
		else
		{
			pd[u][1]++;
			bool ck=false;
			FUP(i,1,num[u])
			{
				bool p1=(y[u][i]==0&&pd[x[u][i]][1]!=0);
				bool p2=(y[u][i]==1&&pd[x[u][i]][0]!=0);
				if(p1||p2)
				{
					FUP(j,1,i-1)
					{
						pd[x[u][j]][y[u][j]]--;
					}
					ck=true;
					break;
				}
				else
				{
					pd[x[u][i]][y[u][i]]++;
				}
			}
			if(!ck)
			{
				dfs(u);
				pd[u][1]--;
				FUP(i,1,num[u])
				{
					pd[x[u][i]][y[u][i]]--;
				}
			}
			else
			{
				pd[u][1]--;
				return;
			}
		}
	}
}
int main(){
	n=read();
	FUP(i,1,n)
	{
		num[i]=read();
		FUP(j,1,num[i])
		{
			x[i][j]=read();
			y[i][j]=read();
		}
	}
	dfs(0);
	printf("%d",ans);
    return 0;
}

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

using namespace std;

#define int long long 
#define i_i pair<int, int>
#define vp vector<i_i>

signed main()
{
    int n, k;
    cin >> n >> k;
    vp data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].first >> data[i].second;
    }

    int pos = 1, ans = 0, nin = 0, now = 0;
    for (int i = 0; i < n; i++) {
        //std::cout << pos << " " << nin << " " << now << 
        //    " " << ans << std::endl;
        int dist = abs(pos - data[i].second);
        int time = data[i].first - now;
        if (nin && (time >= pos - 1 + data[i].second - 1)) {
            ans += nin * (pos - 1);
            nin = 0;
        }
        if (dist > time) {
            cout << -1 << endl;
            return 0;
        }
        ans += nin * time;
        nin++;
        if (nin > k) {
            cout << -1 << endl;
            return 0;
        }
        pos = data[i].second;
        now = data[i].first;
    }

    ans += nin * (pos - 1);
    std::cout << ans << std::endl;
    return 0;
}
    

    

Measured memory_bytes: 4416
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;

int main() {
  int N; cin >> N;
  vi a(N); rep(i,N) cin >> a.at(i);
  
  cout << *max_element(all(a)) - *min_element(all(a)) << endl;
}

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

int main()
{
	int N, l;
	int max_l;
	int lsum = 0;

	priority_queue<int> L;

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> l;
		L.push(l);
	}
	max_l = L.top();
	L.pop();
	while (!L.empty())
	{
		lsum += L.top();
		L.pop();
	}
	if (max_l >= lsum)
	{
		cout << "No" << endl;
	}
	else
	{
		cout << "Yes" << endl;
	}

	return(0);
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	if n == 1 {
		fmt.Println(0)
		return
	}
	totalComb := Pow(10, n%Mod) % Mod
	onlyOne := Pow(9, n%Mod) % Mod
	excludeBoth := onlyOne - Pow(8, n%Mod)%Mod
	ans := (totalComb - onlyOne - excludeBoth) % Mod
	if ans < 0 {
		ans += Mod
	}
	fmt.Println(ans)
}

const Mod = 1000000007

func Pow(a, n int) int {
	if n == 0 {
		return 1
	}
	v := 1
	for p := n; p > 0; p >>= 1 {
		if p&1 == 1 {
			v = v % Mod * a % Mod
		}
		a = a % Mod * a % Mod
	}
	return v % Mod
}


Measured memory_bytes: 1768
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

using ll = long long;
using p = pair<ll, ll>;

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

    ll N;
    cin >> N;

    vector<ll> A(N);
    for (auto&& a : A) {
        cin >> a;
    }

    for (ll i = 0; i < N; i++) {
        if (A[i] > i) {
            cout << -1 << endl;
            return 0;
        }
    }

    for (ll i = 1; i < N; i++) {
        if (A[i] > A[i - 1] + 1) {
            cout << -1 << endl;
            return 0;
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        if (i == N || A[i] != A[i - 1] + 1) {
            ans += A[i - 1];
        } 
    }

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



Measured memory_bytes: 1920
//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define NCK_MAX 510000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {
  int n,m;
  scanf("%d %d", &n,&m);
  if (n==m) printf("Yes\n");
  else printf("No\n");
  return 0;
}


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

using namespace std;

typedef long long ll;

int main()
{
	ll x;
	cin >> x;
	ll occ = 1;
	ll interval = 26;
	deque<char> dq;
	while(x > 0)
	{
		ll r = (x - 1) % interval + 1;
		r = (r - 1) / occ;

		dq.push_front('a' + r);

		x = x - interval;
		interval = interval * 26;
		occ = occ * 26;
	}

	string s;
	while(!dq.empty())
	{
		s.push_back(dq.front());
		dq.pop_front();
	}

	cout << s << endl;
}


Measured memory_bytes: 3636
#include <stdio.h>

int main() 
{

    long long int x;
    long long int num = 0;
    long long int tmp = 100;
    scanf("%lld", &x);

    while ( tmp <= x){
        num++;
        tmp = (long long int)(0.01 * tmp) + tmp;
        if( tmp >= x){
            printf("%lld", num);
            break;
        }

    }
    return 0;

}



Measured memory_bytes: 1728
#include<bits/stdc++.h>
using namespace std;
#define int 		  long long
#define	pb 			  push_back
#define all(a)		  (a).begin(),(a).end()
#define sz(x)		  (int)x.size()
#define endl	 	  "\n"
#define inf 		  1000000007
#define FOR(i, a, b)  for(int i=a; i<b; i++)

mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers. 

//int dp[500005] = {0};

void solve(){
	int n, m, p=0, c=0;
	cin>>n>>m;
	//map<int, string> mp;
	int freq[n+1] = {0};
	bool used[n+1] = {0};
	FOR(i, 0, m){
		int x;
		string s;
		cin>>x>>s;
		if(s=="AC" && !used[x]){
			p+=freq[x];
			used[x] = 1;
			c++;
		}
		else if(s=="WA" && !used[x]){
			freq[x]++;
		}
	}
	cout<<c<<" "<<p<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t=1;
	//cin>>t;
	FOR(i, 1, t+1){	
	//	cout<<"Case #"<<i<<":"<<endl;
		solve();
	}
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0;
 
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <stdlib.h>
#include <cmath>
#include <math.h>
#include <fstream>
#include <bitset>
#include <time.h>
#define int long long
using namespace std;
int n, m, ai;
int data[300][300];
int32_t main(){
    cin >> n >> m;
    for (int i=0; i < n; i++){
        for (int j=0; j < m; j++){
            cin >> ai;
            ai--;
            data[i][j] = ai;
        }
    }
    int answer = n;
    vector<bool> used;
    vector<int> ns;
    for (int i=0; i < m; i++){
        used.push_back(true);
        ns.push_back(0);
    }
    for (int i=0; i < m; i++){
        for (int j=0;j<m;j++){
            ns[j] = 0;
        }
        int maximum = 0;
        for (int j=0; j < n; j++){
            for (int k=0; k < m; k++){
                int number = data[j][k];
                if (used[number]){
                    ns[number]++;
                    maximum = max(ns[number], maximum);
                    break;
                }
            }
        }
        answer = min(answer, maximum);
        int del;
        for (int j=0; j < m; j++){
            if (ns[j] == maximum){
                del = j;
                break;
            }
        }
        used[del] = false;
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 896
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <queue>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
using namespace std;
#define sL(i) i << 1
#define sR(i) i << 1 | 1
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int, pair<int,int>> ppi;
const int MOD = 1e9 + 7;
const int INF = 2e9 + 5;

int n, a[2010];
ll dp[2010][2010];
int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    vector<pi> sorted;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sorted.emplace_back(a[i], i);
    }
    sort(sorted.begin(), sorted.end(), greater<pi>());
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = -INF;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        ll cur = sorted[i].first;
        ll idx = sorted[i].second;
        for (int j = 0; j <= i; j++) if (dp[i][j] != -INF) {
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], cur * abs(idx - j) + dp[i][j]);
            dp[i + 1][j] = max(dp[i + 1][j], cur * abs(n - 1 - (i - j) - idx) + dp[i][j]);
        }
    }
    ll ans = -1;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans;
}

Measured memory_bytes: 34600
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
 
using namespace std;

struct Node {
	int dist;
	vector<int> nexts;
};

const int INF = 1000;

int N;
vector<Node> nodes;

pair<int, int> solveNode(int idx) {
	rep(i, N) nodes[i].dist = INF;

	queue<int> q;
	q.push(idx);
	nodes[idx].dist = 0;
	while (!q.empty()) {
		int now = q.front(); q.pop();
		int nowdist = nodes[now].dist;
		for (int next : nodes[now].nexts) {
			if (nodes[next].dist <= nowdist) continue;
			nodes[next].dist = nowdist + 1;
			q.push(next);
		}
	}

	map<int, int> m;
	rep(i, N) m[nodes[i].dist] = max(m[nodes[i].dist], (int) nodes[i].nexts.size());

	int ret = 1;
	for (auto it : m) {
		int dist = it.first;
		int edgeNum = it.second;
		if (dist == 0) {
			ret *= edgeNum;
		} else if (edgeNum > 1) {
			ret *= edgeNum - 1;
		}
	}

	return make_pair((int) m.size(), ret);
}

pair<int, int> solveEdge(int idx1, int idx2) {
	rep(i, N) nodes[i].dist = INF;

	queue<int> q;
	q.push(idx1);
	q.push(idx2);
	nodes[idx1].dist = 0;
	nodes[idx2].dist = 0;
	while (!q.empty()) {
		int now = q.front(); q.pop();
		int nowdist = nodes[now].dist;
		for (int next : nodes[now].nexts) {
			if (nodes[next].dist <= nowdist) continue;
			nodes[next].dist = nowdist + 1;
			q.push(next);
		}
	}

	map<int, int> m;
	rep(i, N) m[nodes[i].dist] = max(m[nodes[i].dist], (int) nodes[i].nexts.size());

	int ret = 2;
	for (auto it : m) {
		int dist = it.first;
		int edgeNum = it.second;
		if (edgeNum > 1) {
			ret *= edgeNum - 1;
		}
	}

	return make_pair((int) m.size(), ret);
}

signed main() {
	cin >> N;

	nodes.resize(N);

	rep(i, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		nodes[a].nexts.push_back(b);
		nodes[b].nexts.push_back(a);
	}

	pair<int, int> ret(1000, 1000);

	// 点について全探索
	rep(i, N) {
		ret = min(ret, solveNode(i));
	}

	// 辺について全探索
	rep(i, N) {
		for (int next : nodes[i].nexts) {
			ret = min(ret, solveEdge(i, next));
		}
	}

	cout << ret.first << " " << ret.second << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<numeric>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const ll MOD = 1000000007;
 
using namespace std;

int main()
{
    int N, M, t;   cin >> N >> M;
    vector<int> x(100000,0), p(M,0);
    for(int i=0; i<N; i++){
        cin >> t;
        x[t-1]++;
        p[t%M]++;
    }
    int tmp, ans, c;
    ans = 0;
    for(int i=1; i<M/2+1; i++){
        if(M%2==0 && i == M/2){
            ans += p[i]/2;
            c = 0;
        }else{
            ans += min(p[i],p[M-i]);
            c = abs(p[i] - p[M-i]);
        }
        if(p[i] > p[M-i])   tmp = i;
        else    tmp = M-i;
        for(int j=tmp-1; j<100000; j+=M){
            if(x[j] > 1 && c > 1){
                while(x[j] > 1 && c > 1){
                    ans++;
                    c -= 2;
                    x[j] -= 2;
                }
            }
        }
    }
    ans += p[0]/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4036
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
ll INF = 1001001001001001001;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

int main(){
    ll A,B,M;
    cin >> A >> B >> M;
    vector<ll> C(A),D(B);
    rep(i,A) cin >> C[i];
    rep(i,B) cin >> D[i];
    ll ans = INF;
    rep(i,M){
        ll x,y,c;
        cin >> x >> y >> c;
        x--;y--;
        ans = min(ans,C[x]+D[y]-c);
    }
    sort(ALL(C));
    sort(ALL(D));
    ans = min(ans,C[0] + D[0]);
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstring>

int main()
{
#ifdef LOCAL_JUDGE
    freopen("C.in", "r", stdin);
#endif
    int n;
    while (scanf("%d", &n) == 1) {
        int count[3];
        memset(count, 0, sizeof(count));
        for (int i = 0, a; i < n; ++ i) {
            scanf("%d", &a);
            a &= 3;
            if (a == 3) {
                a = 1;
            }
            count[a] ++;
        }
        int parts = count[1];
        if (count[2] > 0) {
            parts ++;
        }
        bool ok = count[0] + 1 >= parts;
        puts(ok ? "Yes" : "No");
    }
}

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

// iterator
#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

// input
#define cin1(x)             cin >> x
#define cin2(x, y)          cin >> x >> y
#define cin3(x, y, z)       cin >> x >> y >> z
#define ncin1(n, x)         REP(i, 0, n) {cin1(x[i]);}
#define ncin2(n, x, y)      REP(i, 0, n) {cin2(x[i], y[i]);}
#define ncin3(n, x, y, z)   REP(i, 0, n) {cin3(x[i], y[i], z[i]);}

// output
#define cout1(x)         cout << #x << ": " << x << endl;
#define ncout1(n, x)     REP(i, 0, n) {cout << #x << "[" << i << "]: "<< x[i] << endl;}

// sort
#define sort_r(x, y)        sort(x, y, greater<lli>()); // 降順(5,4,3,,,)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

typedef long long int lli;
typedef pair<lli, lli> P;


#define mod (1000000007)

int main() {
    lli n, k;
    cin2(n, k);
    lli a[n];
    ncin1(n, a);

    // 内部のやつを出す
    // i 個目
    lli ans1 = 0;
    REP(i, 0, n) {
        REP(j, i+1, n) {
            if (a[i] > a[j])
                ans1++;
            if (ans1 >= mod)
                ans1 = ans1 % mod;
        }
    }
    //cout1(ans1);

    lli ans2 = 0;
    // 次のやつとのやつを出す
    REP(i, 0, n) {
        REP(j, 0, n) {
            if (a[i] > a[j])
                ans2++;
            if (ans2 >= mod)
                ans2 = ans2 % mod;
        }
    }

    //cout1(ans2);
    lli x = (ans1 * k) % mod;
    lli y = (ans2 * ((k * (k-1) / 2) % mod)) % mod;
    //cout1(x);
    //cout1(y);
    cout << (x + y) % mod << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
	template <class Arg1, class... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args) {
		const char* sep = strchr(names + 1, ',');
		cerr.write(names, sep - names) << " : " << arg1 << "  ";
		__f(sep + 1, args...);
	}
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;
typedef pair<char,int> pci;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plll;
 


#define pb push_back
 
// order_of_key (k), find_by_order(k)
#define fi first
#define se second
#define input_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {cin>>a[i];}
#define debug_arr(a,n) {{for(__typeof (n) i=0; i<n; ++i) {cout<<a[i]<<" ";}cout<<"\n";}}
#define maxheap priority_queue<ll>
#define minheap priority_queue<ll,vector<ll> ,greater<ll>>
#define initialise(a, x) memset(a, x, sizeof(a))
#define endl '\n'
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
#define MAX 1000020
#define maxn 200005
#define eps 0.0000001

const ll mod=1e9+7;
const ll inf=1e18+2;

bool prime[MAX];
int n;
std::vector<int> fact[MAX];
int divd[MAX];


signed main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	cin>>n;

	prime[0]=1;
	prime[1]=1;

	for(int i=1;i<MAX;i++) divd[i]=1;

	int tmp,c;

	for(int i=2;i<MAX;i++)
	{
		if(!prime[i])
		{
			int j=i+i;

			divd[i]=2;

			while(j<MAX)
			{
				prime[j]=1;
				tmp=j;
				c=0;
				while(tmp%i==0)
				{
					tmp/=i;
					c++;
				}
				divd[j]*=c+1;
				j+=i;
			}
		}
	}

	// for(int i=1;i<=n;i++) trace(i,divd[i]);

	int ans=0;

	for(int c=1;c<n;c++)
	{
		ans+=divd[n-c];
	}

	cout<<ans<<'\n';


	

	return 0;
}

Measured memory_bytes: 31960
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (ll)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

void solve(){
	ll n,m;
	ll odd=0,even=0;
	cin>>n>>m;
	vector<ll> a(n);
	rep(i,0,n){
		cin>>a[i];
		a[i]/=2; 
		if(a[i]&1){
			odd = 1;
		}else{
			even = 1;
		}
	}
	if(odd&&even){
		cout<<0<<endl;
		return ;
	}
	ll ans=a[0];
	rep(i,1,n){
		if(ans>m){
			cout<<0<<endl;
			return ;
		}
		if(ans%a[i]){
			ans = ans*a[i]/__gcd(ans,a[i]);
		}
	}
	for(auto x:a){
		if(ans/x%2==0){
			cout<<0;
			return ;
		}
	}
	cout<<1+(m-ans)/(2*ans);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	
	private static int a, b, n;
	private static char[] f;

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		while((line=br.readLine()) != null){
			String[] arrays = line.split(" ");
			a = Integer.parseInt(arrays[0]);
			b = Integer.parseInt(arrays[1]);
			n = Integer.parseInt(arrays[2]);
			f = (String.valueOf((double)a/b).split("\\."))[1].toCharArray();
			
			int sum = 0;
			for(int i=0;i<n && i<f.length;i++){
				sum = sum + (int)(f[i]-'0');
			}
			System.out.println(sum);
		}

	}
}

Measured memory_bytes: 17016
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> g(n);

    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::deque<int> b { 0 }, w { n - 1 };
    std::vector<int> color(n);
    color[0] = 1;
    color[n - 1] = 2;
    while (!b.empty() || !w.empty()) {
        std::deque<int> nb, nw;
        for (int v : b) for (int to : g[v]) {
            if (color[to]) continue;
            color[to] = 1;
            nb.push_back(to);
        }
        for (int v : w) for (int to : g[v]) {
            if (color[to]) continue;
            color[to] = 2;
            nw.push_back(to);
        }

        std::swap(b, nb);
        std::swap(w, nw);
    }

    int bcnt = std::count(color.begin(), color.end(), 1), wcnt = n - bcnt;

    std::cout << (bcnt > wcnt ? "Fennec" : "Snuke") << std::endl;

    return 0;
}


Measured memory_bytes: 6248
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO ;


namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    {
        static void Main(string[] args)
        {
            String []s=Console.ReadLine().Split(' ');
            int A=int.Parse(s[0]);
            int B=int.Parse(s[1]);
            int X=0;
            int counter=0;
            while(counter<2){
                if(A>B){
                    X=X+A;
                    A=A-1;
                    counter=counter+1;
                }else{
                    X=X+B;
                    B=B-1;
                    counter=counter+1;
                }
            }
            Console.WriteLine(X);

                


        }
    }
}

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

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

#define RFOR(i, b, a) for(int(i)=(b); (i)>=(a); (i)--)
#define RREP(i, n) FOR((i), (n), 0)

#define pb push_back
#define mp make_pair 

using namespace std;

const int INF=INT_MAX/4;
const int MOD=1000000007;
const double EPS=1e-14;

const bool debug_flag=true;

void debug(string str){
	if(debug_flag){
		cout<<str<<endl;
	}
}

void debugs(string str){
	if(debug_flag){
		cout<<str;
	}
}

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout.precision(10);

	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	int k=n-1;
	while(k>=0){
		cout<<a[k]<<" ";
		k-=2;
	}
	if(n%2==0){
		k=0;
	}else{
		k=1;
	}
	if(n>1){
	while(k<n-2){
		cout<<a[k]<<" ";
		k+=2;
	}
	cout<<a[k];
	}
	cout<<endl;

	return 0;
}



Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define per(i,a,b) for(ll i=(b)-1;i>=(a);i--)
const ll lim=120;
ll x,a,b;
int main() {
    ios_base::sync_with_stdio(0);
    cin>>x;
    rep(i,-lim,lim) rep(j, -lim, lim)
        if(i*i*i*i*i-j*j*j*j*j==x) a=i,b=j;
    cout<<a<<" "<<b<<"\n";
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/

int main(){
    double r; cin >> r;
    double ans = 2 * r * M_PI;
    cout << setprecision(23) << ans << endl;
}

Measured memory_bytes: 3752
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)
from collections import Counter, defaultdict
tmp = Counter(a)
c = defaultdict(int)
c.update(tmp)
ans = [None]*q
for i in range(q):
    bb,cc = map(int, input().split())
    if bb in c:
        s = s + (cc-bb) * c[bb]
        v = c.pop(bb)
        c[cc] += v
    ans[i] = s
write("\n".join(map(str, ans)))

Measured memory_bytes: 99416
N = int(input())
count = 0

if N <= 9:
    count+=1


for i in range(2, 10):
        if N % i == 0:
            j = N / i
            if 1 <= j <= 9:
                count += 1

            else:
                count = count

        else:
            count = count

if count == 0:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

set<string> st;
int main(){
    int m;
    cin>>m;
    string s;
    while(m--){
        cin>>s;
        st.clear();
        int n=s.size();
        string a1,a2,ra1,ra2;
        FOR(i,0,n){
            ra1=a1=s.substr(0,i);
            ra2=a2=s.substr(i,n-i);
            reverse(ra1.begin(),ra1.end());
            reverse(ra2.begin(),ra2.end());
            st.insert(a1+a2);st.insert(a2+a1);
            st.insert(ra1+a2);st.insert(a2+ra1);
            st.insert(a1+ra2);st.insert(ra2+a1);
            st.insert(ra1+ra2);st.insert(ra2+ra1);
        }
        cout<<st.size()<<endl;
    }
    return 0;
}


Measured memory_bytes: 3240
#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int x, a[n-1];
  for(int i=0; i<n-1; i++){
    a[i]=0;
  }
  for(int i=0; i<n-1; i++){
    cin >> x;
    a[x-1]++;
  }
  for(int i=0; i<n-1; i++){
    cout << a[i] << endl;
  }
  cout << "0";
  return 0;
}

Measured memory_bytes: 4420
#include <iostream>
#include <algorithm>
using namespace std;
int N, A[16], x[16][16], y[16][16], t[16], ans;
int main() {
  cin >> N;
  for(int i = 1; i <= N; ++i) {
    cin >> A[i];
    for(int j = 1; j <= A[i]; ++j) {
      cin >> x[i][j] >> y[i][j];
    }
  }
  for(int i = 0; i < (1<<N); ++i) {
    int cnt = 0;
    for(int j = 0; j < N; ++j) {
      t[j+1] = i&(1<<j)?1:0;
      cnt += t[j+1];
    }
    int ok1 = 0;
    for(int j = 1; j <= N; ++j) {
      int ok2 = 0;
      for(int k = 1; k <= A[j]; ++k) {
        if(t[j] == 1 && t[x[j][k]] == y[j][k]) ++ok2;
        else if(t[j] == 0) ++ok2;
      }
      if(A[j] == ok2) ++ok1;
    }
    if(N == ok1) ans = max(ans, cnt);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
program bbb
implicit none

integer(16) :: n, i, j, l, dumy
character(10),allocatable,dimension(:) :: s
integer(16),allocatable,dimension(:) :: t, p, q

read*, n
allocate(s(n))
allocate(t(n))
allocate(p(n))
allocate(q(n))
t=0

do i=1,n
read*, s(i), p(i)
q(i)=i
end do

p=-p

do i=1,n
l=len_trim(s(i))
 do j=1,l
 t(i)=t(i)+((iachar(s(i)(j:j))-80))*(10**(2*(11-j)))
 end do
t(i)=t(i)+p(i)
end do

do i=1,n
 do j=i+1,n
 if(t(i)>t(j)) then
 dumy=t(i)
 t(i)=t(j)
 t(j)=dumy
 dumy=q(i)
 q(i)=q(j)
 q(j)=dumy
 end if
 end do
end do

do i=1,n
write(*,'(i0)') q(i)
end do

end program

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a)      (a).begin(),(a).end()
#define debug_array(a,n) for (ll bccc=(0); bccc<(n); bccc++) cout<<a[bccc]<<" "
#define debug_vector(a) for(ll bccc=(0); bccc<(a.size());bccc++) cout<<a[bccc]<<" "
#define F           first
#define S           second
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
/* ll t = 0;
ordered_multiset me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

///////////   t is insertion time
*/
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
typedef long double lld;
lld pi=3.14159265358;
ll powr(ll a,ll b)
{
    ll c=1;
    ll i;
    for(i=0;i<b;i++)
        c*=a;
    return c;
}
ll hell=1000000007;
//ll hell=998244353 ;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());  after namespace std
// srand(chrono::high_resolution_clock::now().time_since_epoch().count()); after ios:base
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll n,k;
ll a[102];
ll dp[102][100005];
ll prefsum[102][100005];
/*ll f(ll i,ll done)
{
    if(i==n)
    {
        if(done==k)
            return 1;
        else
            return 0;
    }
    if(done>k)
        return 0;
    if(dp[i][done]!=-1)
        return dp[i][done];
    ll j;
    ll ans=0;
    for(j=0;j<=a[i];j++)
        ans=(ans+f(i+1,done+j))%hell;
    dp[i][done]=ans;
    return ans;
}*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp,0,sizeof(dp));
    memset(prefsum,0,sizeof(prefsum));
    ll i,j;
    cin>>n>>k;
    for(i=0;i<n;i++)
        cin>>a[i];
    //cout<<f(0,0);
    for(i=0;i<100005;i++)
    {
        if(i<=a[0])
            dp[0][i]=1;
        else
            dp[0][i]=0;
    }
    prefsum[0][0]=dp[0][0];
    for(i=1;i<100005;i++)
        prefsum[0][i]=prefsum[0][i-1]+dp[0][i];
    for(i=1;i<n;i++)
    {   ll p=dp[i-1][0];
        prefsum[i-1][0]=p;
        for(j=1;j<=k;j++)
            {
                p=(p+dp[i-1][j])%hell;
                prefsum[i-1][j]=p;
            }
        for(j=0;j<=k;j++)
        {
            if(j>=(a[i]+1))
                dp[i][j]=(prefsum[i-1][j]-prefsum[i-1][j-a[i]-1]+hell)%hell;
            else
                dp[i][j]=(prefsum[i-1][j]+hell)%hell;
        }
    }
    cout<<dp[n-1][k];
    return 0;
}


Measured memory_bytes: 159616
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  cin >> N >> A;
 
  if (A > 498) {
    cout << "Yes" << endl;
  }

  else if ((N % 500)-1 < A){
    cout << "Yes" << endl;
  }
  
  else if ((N % 500) > A){
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoderRegularContest069
{
    public class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(program1(new String[] { Console.ReadLine(), Console.ReadLine() }));
        }

        public static string program1(string[] args)
        {
            var n = int.Parse(args[0]);
            var s = args[1].ToCharArray();

            var animalPattern = new List<char>[] { new List<char>() { 'S', 'S' }, new List<char> { 'S', 'W' }, new List<char> { 'W', 'W' }, new List<char> { 'W', 'S' } };

            return string.Join("", animalPattern.Select(animals =>
            {
                var prevAnimal = animals.First();
                
                foreach(var ans in s.Skip(1))
                {
                    var last = animals.Last();
                    if (last == 'S' && ans == 'x' || last == 'W' && ans == 'o')
                    {
                        animals.Add(prevAnimal == 'S' ? 'W' : 'S');
                    }
                    else
                    {
                        animals.Add(prevAnimal);
                    }
                    prevAnimal = last;
                }

                return animals;
            })
            .Where(animals => animals.First() == animals.Last())
            .Select(animals => animals.Take(n))
            .FirstOrDefault(animals => {
                if (s.First() == 'o' && animals.First() == 'S' || s.First() == 'x' && animals.First() == 'W')
                {
                    return animals.ElementAt(1) == animals.Last();
                }
                else
                {
                    return animals.ElementAt(1) != animals.Last();
                }
            }) ?? new List<char>() { '-', '1' }) ;
        }
    }
}


Measured memory_bytes: 16224
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int n [] = new int [3];

		for(int i = 0; i < 3; i++) {
			n[i] = sc.nextInt();
		}
		Arrays.sort(n);

		int ans = Math.abs(n[1]-n[0]);
		ans = ans + Math.abs(n[2]-n[1]);

		System.out.println(ans);
		sc.close();

	}

}


Measured memory_bytes: 21844
{-# LANGUAGE BangPatterns #-}
module Main where
import qualified Data.ByteString.Char8 as B
import Data.List(foldl', unfoldr)
import Data.Char(isSpace)
import Data.Monoid((<>))
import Debug.Trace
import System.Mem.Weak
import System.Mem
import Control.Exception

sort :: Ord a => [a] -> [a]
sort = sortBy compare

{-# NOINLINE sort #-}
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy compare = mergeAll . sequences
    where
    sequences (a:b:xs)
      | a `compare` b == GT = descending b [a]  xs
      | otherwise       = ascending  b (a:) xs
    sequences xs = [xs]

    descending a as (b:bs)
      | a `compare` b == GT = descending b (a:as) bs
    descending a as bs  = (a:as): sequences bs

    ascending a as (b:bs)
      | a `compare` b /= GT = ascending b (\ys -> as (a:ys)) bs
    ascending a as bs   = let !x = as [a]
                          in x : sequences bs

    mergeAll [x] = x
    mergeAll xs  = mergeAll (mergePairs xs)

    mergePairs (a:b:xs) = let !x = merge id a b
                          in x : mergePairs xs
    mergePairs xs       = xs

    merge !acc as@(a:as') bs@(b:bs')
      | a `compare` b == GT = merge (acc.(b:)) as  bs'
      | otherwise       = merge (acc.(a:)) as' bs
    merge acc [] bs         = acc bs
    merge acc as []         = acc as

data PI = PI {-# UNPACK #-}!Int {-# UNPACK #-} !Int {-# UNPACK #-} !Int
    deriving (Eq, Ord)

parse :: B.ByteString -> [PI]
parse = unfoldr step
  where
  step !s | B.null s = Nothing
          | otherwise = do
               (n1, s1) <- B.readInt s
               (n2, s2) <- B.readInt (B.tail s1)
               let !s3 = B.dropWhile isSpace s2
               return (PI (- (n1 + n2)) n1 n2, s3)

main :: IO ()
main = do
    n <- fmap read getLine :: IO Int
    content <- B.getContents
    let asbs = parse content
    let l  = sort asbs
        ps = cycle [1,-1 :: Int]
        ans = sum $ zipWith (\(PI _ a b) p -> if p == 1 then a else -b) l ps
    evaluate l
    traceMarker "sort" (print ans)


Measured memory_bytes: 21244
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
a_max = a[0]
a_med = round(a_max / 2)
min = a[0] - a[n-1]
a_answer = a[n-1]
for i in range(1, n):
    if min > abs(a[i] - a_med):
        min = a[i] - a_med
        a_answer = a[i]
print("{0} {1}".format(a_max, a_answer))


Measured memory_bytes: 14052
N, Q = map(int, input().split())
# print(N, Q)
S = input()
lr_array = [list(map(int, input().split())) for i in range(Q)]
AC_array = []
AC_count = 0

# print(S)
for i, s in enumerate(S):
    if i == 0:
        s_old = s
        continue
    if s_old == "A" and s == "C":
        AC_count += 1
    AC_array.append(AC_count)
    s_old = s

# print(lr_array)
# print(AC_array)
ans = ""
for lr in lr_array:
    ans += str(AC_array[lr[1] - 2] -
               (AC_array[lr[0] - 2] if lr[0] > 1 else 0)) + "\n"
print(ans[:-1])

Measured memory_bytes: 32028
N = int(input())
len_N = len(str(N))

memo = {}

if str(N)[1:len_N-1]:
    center_val = int(str(N)[1:len_N-1])
else:
    center_val = 0
for a in range(1, 10):
    for b in range(1, 10):
        count = 0
        if a == b and a <= N:
            count += 1
        if len_N >= 2 and 10*a + b <= N:
            count += 1
        if len_N >= 3:
            for i in range(3, len_N):
                count += 10**(i-2)
            if a < int(str(N)[0]):
                count += 10**(len_N-2)
            elif a == int(str(N)[0]):
                if b <= int(str(N)[-1]):
                    count += center_val + 1
                else:
                    count += center_val
        memo[(a, b)] = count
# print(memo)

ans = 0
for A in range(1, N+1):
    A1 = str(A)[0]
    A2 = str(A)[-1]
    if A1 == "0" or A2 == "0":
        continue
    ans += memo[(int(A2), int(A1))]
    # print(A, memo[(int(A2), int(A1))])
print(ans)

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

using namespace std;

#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;


int main(void){

    int n;
    cin >> n;

    bool ok = false;
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        int d1, d2;
        cin >> d1 >> d2;
        if(d1 == d2){
            cnt++;
        }else{
            if(cnt >= 3) ok = true;
            cnt = 0;
        }
    }
    if(cnt >= 3) ok = true;

    if(ok){
        cout << "Yes" << "\n";
    }else{
        cout << "No" << "\n";
    }


    return 0;
}


Measured memory_bytes: 3632