akhauriyash/Code-Regression huggingface dataset:
package main

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

// 構造体の定義
type Stack struct {
	//空のInterfaceで任意の型に対応
	stack [20000]interface{}
	top   int
}

// 構造体に、関数を組み込む
func (s *Stack) push(x interface{}) {
	s.stack[s.top] = x
	s.top++
}

func (s *Stack) pop() interface{} {
	if s.isEmpty() {
		return -1
	}
	s.top--
	v := s.stack[s.top]
	return v
}

func (s *Stack) isEmpty() bool {
	return s.top == 0
}

func (s *Stack) isFull() bool {
	//capで、配列の容量を取得
	return s.top == cap(s.stack)
}

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanLines)
	input := nextStr()
	stack := &Stack{}
	valleys := []Valleys{}
	ans := 0

	for i, s := range input {
		switch string(s) {
		//バックスラッシュはエスケープ必要
		case "\\":
			stack.push(i)
		case "/":
			if stack.isEmpty() {
				continue
			} else {
				_p := stack.pop()
				//Interface{}からint型にキャスト
				p, _ := _p.(int)
				area := i - p
				ans += area
				for j := len(valleys) - 1; j >= 0; j-- {
					v := valleys[j]
					if p < v.from {
						area += v.area
						valleys = valleys[0:j]
						//fmt.Println(len(valleys)-1, valleys)
					} else {
						break
					}
				}

				valleys = append(valleys, Valleys{i, area})

			}
		}
		//fmt.Println(i, valleys)
	}
	fmt.Println(ans)
	fmt.Printf("%d", len(valleys))
	for _, v := range valleys {
		fmt.Printf(" %d", v.area)
	}
	fmt.Println()

}

type Valleys struct {
	from int
	area int
}



Measured memory_bytes: 1640
#include <bits/stdc++.h>
#define loop(n, i) for(int i=0;i<n;i++)
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;
using P = pair<ll, ll>;



int main(){
    int n; cin >> n;
    int b[200] = {};
    loop (n, i) cin >> b[i];

    int ans[200] = {};
    loop (n, i) {
        int m = n - i;
        int p = -1;
        loop (m, j) {
            int k = m - 1 - j;
            if (b[k] >= b[k + 1] && b[k] == k + 1) {
                p = k;
                break;
            }
        }
        if (p == -1) {
            cout << -1 << endl;
            return 0;
        }
        ans[m - 1] = b[p];
        for (int j = p; j < m; j++) {
            b[j] = b[j + 1];
        }
    }

    loop (n, i) cout << ans[i] << endl;

    return 0;
}



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

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

int main() {
  int h,w; cin>>h>>w;
  vector<vector<char>> G(h, vector<char>(w));
  rep(i, h) rep(j, w) cin>>G[i][j];

  vector<vector<int>> Dist(h, vector<int>(w, -1));
  queue<pair<int, int>> Que;
  Dist[0][0]=0;
  Que.push(make_pair(0, 0));
  while (!Que.empty()) {
    pair<int, int> P=Que.front();
    Que.pop();
    int x=P.first, y=P.second;
    rep(i, 4) {
      int nx=x+dx[i],ny=y+dy[i];
      if (nx<0||nx>=h||ny<0||ny>=w) continue;
      if (Dist[nx][ny]!=-1) continue;
      if (G[nx][ny]!='.') continue;
      Dist[nx][ny]=Dist[x][y]+1;
      Que.push(make_pair(nx, ny));
    }
  }
  int res=0;
  rep(i, h) rep(j, w) if (G[i][j]=='.') res++;
  if (Dist[h-1][w-1]==-1) cout<<-1<<endl;
  else cout<<res-Dist[h-1][w-1]-1<<endl;
}


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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string S, T;
	cin >> S >> T;
	

	for (int i = 0; i < S.size(); i++)
	{
		if (S == T) {
			cout << "Yes" << endl;
			return 0;
		}
		S = S.back() + S.substr(0, S.size() - 1);
	}
	cout << "No" << endl;
	return 0;
}

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

int main() {
    ll N, K;
    cin >> N >> K;

    ll x = N;
    x = min({x, x - (x/K) * K, abs(x - (x/K + 1) * K)});

    cout << x << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stdio.h>

#define _ << " " <<
#define debug(x) #x << " = " << x

#define ll long long
#define ull unsigned long long

int main() {
    std::ios::sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::deque<int> deck;

    bool end = true;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        if (end) {
            deck.push_back(x);
        } else {
            deck.push_front(x);
        }

        end = !end;
    }

    if (end) {
        auto it = deck.begin();
        while(it != deck.end()) {
            std::cout << *it << " ";
            ++it;
        }
        std::cout << std::endl;
    }

    if (!end) {
        auto it = deck.rbegin();
        while(it != deck.rend()) {
            std::cout << *it << " ";
            ++it;
        }
        std::cout << std::endl;
    }
    return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;


void ABC157C()
{
	int N, M;
	cin >> N >> M;
	vi A(N, -1);
	for (int i = 0; i < M; ++i)
	{
		int s, c;
		cin >> s >> c;
		--s;
		if (A[s] > -1 && A[s] != c)
		{
			cout << "-1" << endl;
			return;
		}
		A[s] = c;
	}
	if (N > 1 && A[0] == 0)
	{
		cout << "-1" << endl;
		return;
	}
	if (A[0] == -1)
		A[0] = N == 1 ? 0 : 1;
	int ans = 0;
	for (int i = 0; i < N; ++i)
	{
		ans *= 10;
		ans += max(A[i],0);
	}
	cout << ans << endl;

}


int main()
{
	ABC157C();
	return 0;
}

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

int main() {
	int X, A, B;
	cin >> X >> A >> B;

	if (B <= A)
		cout << "delicious" << endl;
	else if (A < B && B <= X + A)
		cout << "safe" << endl;
	else 
		cout << "dangerous" << endl;

}

Measured memory_bytes: 892
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static int h;
	static int w;
	static String[] a;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		h = sc.nextInt();
		w = sc.nextInt();
		a = new String[h];
		for (int i = 0; i < h; i++) {
			a[i] = sc.next();
		}
		int count = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (a[i].charAt(j) == '#') {
					count++;
				}
			}
		}
		if (count != h + w - 1) {
			System.out.println("Impossible");
		} else {
			System.out.println("Possible");
		}
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
		return hasNextByte();
	}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || Integer.MAX_VALUE < nl) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define x real()
#define y imag()
#define EPS (1e-9)
using namespace std;
typedef complex<double> point;

double dot(point a,point b){return a.x*b.x+a.y*b.y;}

double cross(point a,point b){return a.x*b.y-a.y*b.x;}

int ccw(point a,point b,point c){
  point d=b-a;
  point e=c-a;
  if(cross(d,e)>0)return 1;//?????´
  if(cross(d,e)<0)return -1;//?????´
  if(dot(d,e)<0)return 2;//onlineback
  if(abs(d)<abs(e))return -2;//onlinefront
  return 0;//onsegment
}

//??´??????????????????
bool intersection(point a,point b,point c,point d){
  return (ccw(a,b,c)*ccw(a,b,d)<=0&&ccw(c,d,a)*ccw(c,d,b)<=0);
}

//????????¨???????????¢
double getdistance_sp(point a,point b,point p){
  if(!(dot(p-a,b-a)>=0&&dot(p-b,a-b)>=0))return min(abs(p-a),abs(p-b));
  return abs(cross(p-a,b-a)/abs(b-a));
}

//????????¨??????????????¢
double getdistance_ss(point a,point b,point c,point d){
  if(intersection(a,b,c,d))return 0;
  return min(min(getdistance_sp(c,d,a),getdistance_sp(c,d,b)),
	     min(getdistance_sp(a,b,c),getdistance_sp(a,b,d)));
}

//???p??????????§???¢v???(?????´?????????->1,?¢????????????????->2,?????´?????????->3)
int getstate(vector<point> v,point p){
  int n=v.size();
  for(int i=0;i<n;i++){
    int c=ccw(v[i],v[(i+1)%n],p);
    if(c==0)return 2;
    if(c!=1)return 3;
  }
  return 1;
}

//???????§???¢v??¨???p????????¢
double getdistance_pp(vector<point> v,point p){
  int n=v.size();
  if(getstate(v,p)!=3)return 0;
  double r=abs(v[0]-p);
  for(int i=0;i<n;i++)r=min(r,getdistance_sp(v[i],v[(i+1)%n],p));
  return r;
}

//???????§???¢v??¨??????ab????????¢
double getdistance_ps(vector<point> v,point a,point b){
  int n=v.size();
  double r=abs(v[0]-a);
  if(getstate(v,a)!=3||getstate(v,b)!=3)return 0;
  for(int i=0;i<n;i++){
    r=min(r,getdistance_ss(v[i],v[(i+1)%n],a,b));
  }
  return r;
}

int main(){
  int n,h,a,b,c,d;
  double ans,dis;
  point s,g;
  vector<point> v;
  while(1){
    cin>>n;
    if(!n)break;
    ans=(1e9);
    cin>>s.x>>s.y>>g.x>>g.y;
    while(n--){
      cin>>a>>b>>c>>d>>h;
      v.push_back(point(a,b));
      v.push_back(point(c,b));
      v.push_back(point(c,d));
      v.push_back(point(a,d));
      dis=getdistance_ps(v,s,g);
      if(dis>h)ans=min(ans,(dis*dis+h*h)/(2*h));
      else ans=min(ans,dis);
      v.clear();
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1308
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int k,n;
	cin>>k>>n;
	int a[n+1],b[n],c[n];
	for(int i=1;i<=n;i++)
	{
	    cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		b[i]=a[i+1]-a[i];
	}
	b[n]=k-a[n]+a[1];
	sort(b+1,b+n+1);
	cout<<k-b[n];
	return 0;
}

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

def main():
    N,K=map(int,input().split())
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        a,b=map(lambda x:int(x)-1,input().split())
        edge[a].append(b)
        edge[b].append(a)
    stack=[(0,0)]
    ans=K
    used=[False]*N
    while stack:
        v,d=stack.pop()
        i=0
        used[v]=True
        for nv in edge[v]:
            if not used[nv]:
                ans*=K-i-1-min(1,d)
                ans%=MOD
                stack.append((nv,d+1))
                i+=1
    print(ans)
            

if __name__ == '__main__':
    main()


Measured memory_bytes: 67376
n,k,q=list(map(int,input().split()))
a = [int(input()) for i in range(q)]

dic={}
for i in range(n):
  dic[i]=0

for i in range(q):
  dic[a[i]-1]=dic[a[i]-1]+1

for i in range(n):
  if(k-(q-dic[i])>0):
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 19088
D = [i for i in range(10)]
N,K = map(int,input().rstrip().split(" "))
A = list(map(int,input().rstrip().split(" ")))
flag = True
for i in range(N,10 ** 6 + 1):
    flag = True
    for i2 in range(6):
        if i >= 10 ** i2 and (i // (10 ** i2)) % 10 in A:
            flag = False
            break
    if flag:
        print(i)
        break

Measured memory_bytes: 67664
#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, (b), sizeof(a))
#define fore(i,a) for(int i=0;i<a;i++)
#define fore1(i,j,a) for(int i=j;i<a;i++)
#define print(ar) for(int i=0;i<ar.size();i++)cout<<ar[i]<<" ";
#define END cout<<'\n'
const double pi=acos(-1.0);
 
typedef pair<int, int> PII;
 
typedef vector<long long> VI;
 
typedef vector<string> VS;
 
typedef vector<PII> VII;
 
typedef vector<VI> VVI;
 
typedef map<int,int> MPII;
 
typedef set<int> SETI;
 
typedef multiset<int> MSETI;
 
typedef long int li;
 
typedef unsigned long int uli;
 
typedef long long int ll;
 
typedef unsigned long long int  ull;
ll fastexp (ll a, ll b, ll n) {
  ll res = 1;
  while (b) {
      if (b & 1) res = res*a%n;
      a = a*a%n;
      b >>= 1;
  }
  return res;
}
void fast(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
 {  fast();
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	while(1){
	    if(b>=c){
	        cout<<"Yes"<<endl;
	        break;}
	        else if(d>=a){cout<<"No"<<endl;
	        break;
	}
	else {
	    c=c-b;
	    a=a-d;
	}
 }}

Measured memory_bytes: 3616
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
#define P pair<int,int>
#define space ' '
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

const int maxn = 100000;

int main(){
    string s;
    ll ans=0;
    ll k;
    cin >> s;
    cin >> k;
    
    if(k<=2){
        string t=s;
        rep(i,k-1){
            t+=s;
        }
        ll streak=0;
        ll add=0;
        rep(i,t.size()-1){
            if(t[i]==t[i+1]){
                streak++;
            }else{
                add+=(streak+1)/2;
                streak=0;
            }
            if(i==t.size()-2){
                add+=(streak+1)/2;
                streak=0;
            }
        }
        ans=add;
    }else{
    
        ll tmp_1=0,tmp_2=0,tmp_3=0;
        ll dif_1=0,dif_2=0;
        
        ll streak=0;
        ll add=0;
        rep(i,s.size()-1){
            if(s[i]==s[i+1]){
                streak++;
            }else{
                tmp_1+=(streak+1)/2;
                streak=0;
            }
            if(i==s.size()-2){
                tmp_1+=(streak+1)/2;
                streak=0;
            }
        }
        string t = s+s;
        rep(i,t.size()-1){
            if(t[i]==t[i+1]){
                streak++;
            }else{
                tmp_2+=(streak+1)/2;
                streak=0;
            }
            if(i==t.size()-2){
                tmp_2+=(streak+1)/2;
                streak=0;
            }
        }
        
        string u=s+s+s;
        
        rep(i,u.size()-1){
            if(u[i]==u[i+1]){
                streak++;
            }else{
                tmp_3+=(streak+1)/2;
                streak=0;
            }
            if(i==u.size()-2){
                tmp_3+=(streak+1)/2;
                streak=0;
            }
        }
        dif_1=tmp_2-tmp_1;
        dif_2=tmp_3-tmp_2;
        
        ans=tmp_1+(dif_1+dif_2)*((k-1)/2)+dif_1*((k-1)%2);
        
    }
    
    cout << ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i=0; i<N; i++){
    cin >> S[i];
  }
  
  sort(S.begin(), S.end());
  vector<string> X(N);
  vector<int> Y(N);
  X[0]=S[0];
  Y[0]++;
  int now=0;
  for(int i=1; i<N; i++){
    if (S[i]==S[i-1]) Y[now]++;
    else{
      now++;
      X[now]=S[i];
      Y[now]++;
    }
  }
  int max=0;
  for(int i=0; i<=now; i++){
    if(max<Y[i]) max=Y[i];
  }
  
  for(int i=0; i<=now; i++){
    if(Y[i]==max) cout<<X[i]<<endl;
  }
}

Measured memory_bytes: 16640
#include<stdio.h>
int main(){
int a,b,c,i,x=0,y=0;
while(1){
scanf("%d\n",&a);
if(a==0){
break;
}
else{
for(i=0;i<a;i++){
scanf("%d %d\n",&b,&c);
if(b>c){
x=x+b+c;
}
else if(b==c){
x=x+b;
y=y+c;
}
else{
y=y+b+c;
}
}
printf("%d %d\n",x,y);
x=0,y=0;
}
}
return 0;
}


Measured memory_bytes: 2076
#include <bits/stdc++.h>
using namespace std;
#define M0D 998244353;
vector<int> G[100009];
int ans[100009];
queue<int> test;

void answww(int num, int sup){
  test.pop();
  for(int j=0; j<G[num].size(); j++){
    if(ans[G[num][j]]==0){
      test.push(G[num][j]);
      ans[G[num][j]] = num;
    }
  }
  if(test.size()>0) answww(test.front(),sup);
}

int main(){
  int N,M,sup=1;
  cin >> N >> M;
  int A[M+1],B[M+1];
  for(int i=0; i<N+1; i++) ans[i] = 0;
  for(int i=1; i<=M; i++) cin >> A[i] >> B[i];
  for(int i=1; i<=M; i++){
    G[A[i]].push_back(B[i]);
    G[B[i]].push_back(A[i]);
  }
  test.push(1); ans[1] = 1;
  answww(test.front(),sup);
  cout << "Yes" << endl;
  for(int i=2; i<N+1; i++) cout << ans[i] << endl;
  return 0;
}


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

int main()
{
    int n;
    cin >> n;
    map<int, int> a_map;
    rep(i, 0, n)
    {
        int a;
        cin >> a;
        a_map[a] ++;
    }
    vector<pll> a_cnt;
    for(auto a_c : a_map)
    {
        ll a = a_c.first;
        ll c = a_c.second;
        a_cnt.emplace_back(a, c);
    }

    sort(a_cnt.begin(), a_cnt.end());
    reverse(a_cnt.begin(), a_cnt.end());
    
    ll ans = 1;
    rep(i, 0, 2)
    {
        ll l = -1;
        rep(j, 0, a_cnt.size())
        {
            ll a = a_cnt[j].first;
            ll c = a_cnt[j].second;
            if (c > 1)
            {
                l = a;
                a_cnt[j] = make_pair(a, c - 2);
                break;
            }
        }
        if (l == -1) l = 0;
        ans *= l;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7156
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

vector<int> as;

Int table[55][55];
Int table_sum[55];
Int ans;

Int pop_count[1 << 18];

int main()
{
    int n, k, s, t;
    for (int i = 1; i < (1 << 18); i++)
        pop_count[i] = pop_count[i / 2] + i % 2;
    cin >> n >> k >> s >> t;
    for (int i = 0; i < 55; i++) {
        table[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            table[i][j] = table[i - 1][j] + table[i - 1][j - 1];
        }
    }

    for (int i = 0; i < 55; i++) {
        for (int j = 1; j <= k; j++) {
            table_sum[i] += table[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if ((a & s) != s)
            continue;
        if ((a | t) != t)
            continue;
        as.push_back(a);
    }
    for (int i = 0; i <= t; i++) {
        if ((i & s) != s)
            continue;
        if ((i | t) != t)
            continue;
        unordered_map<int, Int> cnt;
        for (auto a : as) {
            cnt[a & i]++;
        }
        Int tmp = 0;
        for (auto p : cnt) {
            tmp += table_sum[p.second];
        }
        if (pop_count[i ^ s] % 2 == 0)
            ans += tmp;
        else
            ans -= tmp;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    bool flag = true;
    rep(i, n) {
        int a;
        cin >> a;
        if(a&1){
            flag = false;
        }
    }
    puts(flag ? "second" : "first");
}

Measured memory_bytes: 384
import sys
c=list(map(int,input().split()))
diffa=c[1]-c[0]
diffb=c[2]-c[1]

c=list(map(int,input().split()))
if(diffa!=(c[1]-c[0]) or diffb!=(c[2]-c[1])):
    print("No")
    sys.exit()

c=list(map(int,input().split()))
if(diffa!=(c[1]-c[0]) or diffb!=(c[2]-c[1])):
    print("No")
    sys.exit()

print("Yes")

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 200010
vector<pair<ll,ll> >v;
int main(){
    ll n,k,s;
    cin>>n>>k>>s;
    rep(i,n){
	if(i<k)cout<<s<<endl;
	else{
	    if(s==1000000000)cout<<1<<endl;
	    else cout<<1000000000<<endl;
	}
    }
}




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

const int E = 12;
const int M = 52;

int main() {
  ll n;
  while (cin >> n, n) {
    string s;
    cin >> s;
    ll m0 = 1ll << M;
    for (int i = 0; i < M; i++) {
      m0 |= (ll)(s[i] - '0') << (M - 1 - i);
    }

    ll e = 0, m = m0;
    for (ll i = 0, k; i < n; i += k) {
      k = m0 >> e ? ((1ll << M + 1) - m - 1) / (m0 >> e) + 1 : 1e18;
      if (i + k <= n) {
        m = m + k * (m0 >> e) >> 1;
        e++;
      } else {
        m = m + (n - i) * (m0 >> e);
      }
    }

    cout << bitset<E>(e) << bitset<M>(m) << endl;
  }
}



Measured memory_bytes: 3152
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;

#define ll long long
#define pal pair<ll,ll>
#define pad pair<double,double>
#define PB push_back
#define MP make_pair
#define F first
#define S second

const ll MOD = 1e9+7;
const ll INF = 1e18;
const double EPS = 1e-8;

long long MODPOW(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ret;
}

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}


int main(){
	ll n,k,ans=-INF;
	cin >> n >> k;
	vector<ll> p(n+1),c(n+1);
	for(ll i=1;i<=n;i++){
		cin >> p[i];
	}
	for(ll i=1;i<=n;i++){
		cin >> c[i];
	}
	for(ll i=1;i<=n;i++){
		ll tmp=0,now=i;
		vector<ll> loop(n+1,0);
		vector<ll> lloop(n+1,-INF);
		vector<bool> visited(n+1,false);
		for(ll j=1;j<=k;j++){
			if(visited[p[now]]){
				loop[0]=j-1;
				tmp= (k/loop[0])*loop[loop[0]] + lloop[k%loop[0]];
				if(lloop[k%loop[0]]<0){ tmp-=lloop[k%loop[0]];}
				chmax(ans, tmp);
				tmp=(k/loop[0]-1)*loop[loop[0]] + lloop[loop[0]];
				chmax(ans, tmp);
				
				break;
			}else{
				now= p[now];
				loop[j]=loop[j-1]+c[now];
				lloop[j]=max(loop[j],lloop[j-1]);
				tmp+=c[now];
				visited[now]=true;
				chmax(ans,tmp);
				
			}
		}
		chmax(ans, tmp);
		
	}
	cout << ans << endl;

}

Measured memory_bytes: 3724
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def check(x, N, M, V, P, A):
    if (N - x) <= P:
        return True

    if V <= x + P:
        return (A[x] + M) >= A[N-P]

    x_score = A[x] + M
    total_v = (V - x - P) * M
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

    if A[N-P] > x_score:
        return False

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = LI()
    A.sort()

    if(check(0, N, M, V, P, A)):
        print(N)
        return

    r = N - 1
    l = 0
    while r-l > 1:
        mid = (l+r) // 2
        # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
        if check(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    print(N - r)



if __name__ == '__main__':
    main()


Measured memory_bytes: 88300
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int main()
{
    fast
    int q=1;

    while(q--)
    {
     string s; cin>>s;
     if(s.back()=='s')
        cout<<s+"es";
     else
        cout<<s+'s';




    }

    return 0;
}


Measured memory_bytes: 3660
#include <iostream>
using namespace std;
int main(void){
   int a;
   cin>>a;
  if(a==1){
      cout<<"fri"<<endl;
  }
  else if(a==2){
      cout<<"sat"<<endl;
  }
  else if(a==3){
      cout<<"sun"<<endl;
  }
  else if(a==4){
      cout<<"mon"<<endl;
  }
  else if(a==5){
      cout<<"tue"<<endl;
  }
  else if(a==6){
      cout<<"wed"<<endl;
  }
  else if(a==7){
      cout<<"thu"<<endl;
  }
  else if(a==8){
      cout<<"fri"<<endl;
  }
  else if(a==9){
      cout<<"sat"<<endl;
  }
  else if(a==10){
      cout<<"sun"<<endl;
  }
  else if(a==11){
      cout<<"mon"<<endl;
  }
  else if(a==12){
      cout<<"tue"<<endl;
  }
  else if(a==13){
      cout<<"wed"<<endl;
  }
  else if(a==14){
      cout<<"thu"<<endl;
  }
  else if(a==15){
      cout<<"fri"<<endl;
  }
  else if(a==16){
      cout<<"sat"<<endl;
  }
  else if(a==17){
      cout<<"sun"<<endl;
  }
  else if(a==18){
      cout<<"mon"<<endl;
  }
  else if(a==19){
      cout<<"tue"<<endl;
  }
  else if(a==20){
      cout<<"wed"<<endl;
  }
  else if(a==21){
      cout<<"thu"<<endl;
  }
  else if(a==22){
      cout<<"fri"<<endl;
  }
  else if(a==23){
      cout<<"sat"<<endl;
  }
  else if(a==24){
      cout<<"sun"<<endl;
  }
  else if(a==25){
      cout<<"mon"<<endl;
  }
  else if(a==26){
      cout<<"tue"<<endl;
  }
  else if(a==27){
      cout<<"wed"<<endl;
  }
  else if(a==28){
      cout<<"thu"<<endl;
  }
  else if(a==29){
      cout<<"fri"<<endl;
  }
  else if(a==30){
      cout<<"sat"<<endl;
  }
   return 0;
}



Measured memory_bytes: 3116
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include<numeric>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
class DFS{
public:
    int n;
    int time = 0;
    vector<vector<int> > G;
    vector<bool> flag;
    vector<int> d;
    vector<int> f;

    DFS(){
        cin >> n;
        G.resize(n);
        d.resize(n);//最初に発見された時刻
        f.resize(n);
        flag.resize(n,false);
        REP(i,n){
            int u,k; cin >>u>>k;
            u--;
            if(k != 0){
            REP(j,k){
                int a; cin >>a;
                G[u].push_back(a);
                G[u][j]--;
            }
            }
        }
        //time = 0;
    }
    
    void dfs(int now){
        //d[now] = time;
        flag[now] = true;
        d[now] = ++time;
        if(G[now].size() > 0){
            REP(i,G[now].size()){
                //time++;
                if(flag[G[now][i]] == false){
                    flag[G[now][i]] = true;
                    d[G[now][i]] = time+1;
                    dfs(G[now][i]);
                }
            }
        }
        f[now] = ++time;
        return;
    }

};

int main(){
    //cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
    DFS maze;
    REP(i,maze.n){
        if(maze.flag[i] == 0) {
            maze.dfs(i);
        }
    }
    REP(i,maze.n){
        cout << i+1 << ' ' << maze.d[i] << ' ' << maze.f[i] << endl;
    }

}


Measured memory_bytes: 3240
s=input()
for i in range((len(s)-1)//2):
    if s[i]!=s[len(s)-i-1]:
      print("No")
      exit()
for i in range(((len(s)-1)//2)//2):
    if s[i]!=s[(len(s)-1)//2-i-1]:
      print("No")
      exit()
for i in range(((len(s)-1)//2)//2):
    if s[(len(s)+1)//2+i]!=s[len(s)-i-1]:
      print("No")
      exit()
print("Yes")

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

int main(){
  int N,K;
  long long sum=0;
  cin>>N>>K;
  vector<int> H(N);
  for(int i=0; i<N; i++){
    cin>>H.at(i);
  }
  sort(H.begin(),H.end());
  for(int i=0; i<N-K; i++){
    sum+=H.at(i);
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 4056
num = input()
num = num.rstrip().split(" ")
if int(num[0])>=10:
    num[0]=num[0]
else:
    num[0]="0"+str(num[0])
if int(num[1])>=10:
    num[1]=num[1]
else:
    num[1]="0"+str(num[1])
if int(num[2])>=10:
    num[2]=num[2]
else:
    num[2]="0"+str(num[2])


list1 = [int(num[0]),int(num[1]),int(num[2])]
list1 = sorted(list1)
#print(list1)
count= input()

print(int(list1[2]*(2**int(count))+list1[1]+list1[0]))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,a,b;
    while(cin>>n>>a>>b){
        ll e=(n-1)*a+b;
        ll f=(n-1)*b+a;
        if(n==1&&a==b){
            cout<<1<<endl;
            continue;
        }
        if(n==1||a>b){
            cout<<0<<endl;
            continue;
        }
        cout<<f-e+1ll<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define Int long long
using namespace std;

const int MAXN=50005;
const int NAX=1005;
const long MOD=(long)(1e9+7);

Int N,M,K;
Int X,Y,Z;
Int perform(Int x){
    return (x*(x+1))/2LL;
}
vector<Int> A;


int main()
{
    int ans=0;int best=0;
    cin>>N;
    string S;cin>>S;
    for(auto x:S){
        if(x=='I') ++ans;
        else --ans;
        best=max(best,ans);
    }
    best=max(best,0);
    cout<<best<<"\n";
     
}


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

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

int main() {
    int n;
    cin >> n;
    vector<int> b(n);
    rep(i, n) cin >> b[i];
    int sz = n;
    vector<int> ans;
    while(1) {
        int best = -1;
        if (b.empty()) break;
        rep(i, sz) {
            if (b[i] == i + 1) best = i;
        }
        if (best == -1) {
            cout << "-1\n";
            return 0;
        }
        ans.push_back(best+1);
        b.erase(b.begin() + best);
        --sz;
    }
    reverse(ans.begin(), ans.end());
    rep(i, (int)ans.size()) {
        cout << ans[i] << endl;
    }
    return 0;
}

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

int main(){
	int N, M, C;
	cin >> N >> M >> C;
	vector<int> B(M);
	for(int i = 0; i < M; ++i) cin >> B[i];
	vector<vector<int>> A(N, vector<int>(M));
	for(int i = 0; i < N; ++i) {
		for(int k = 0; k < M; ++k) {
			cin >> A[i][k];
		}
	}

	int cnt = 0;
	for(int i = 0; i < N; ++i) {
		int res = 0;
		for(int k = 0; k < M; ++k) {
			res += A[i][k] * B[k];

			if(k == M - 1) {
				res += C;

				if(res > 0) {
					cnt++;
				}
			}
		}
	}

	cout << cnt << endl;
}

Measured memory_bytes: 256
N,Q=map(int,input().split())
S=input()
lr=[list(map(int,input().split()))for _ in range(Q)]

count=[0]+[0]*(N-1)
i=1
while i<N:
    if S[i-1]=='A' and S[i]=='C':
        count[i]=count[i-1]+1
    else:
        count[i]=count[i-1]
    i+=1

for l,r in lr:
    print(count[r-1]-count[l-1])

Measured memory_bytes: 29604
#include <vector>

struct union_find {
    using size_type = std::size_t;
private :
    size_type _size;
    std::vector<int> node;
public :
    union_find (int n) : node(n, -1), _size(n) { }

    bool unite (int x, int y) {
        if ((x = root(x)) == (y = root(y))) return false;
        if (node[x] > node[y]) std::swap(x, y);
        node[x] += node[y];
        node[y] = x;
        _size--;
        return true;
    }

    bool same (int x, int y) {
        return (root(x) == root(y));
    }

    int root (int x) {
        if (node[x] < 0) return x;
        return node[x] = root(node[x]);
    }

    size_type size (size_type x) {
        return (size_type(-node[root(x)]));
    }

    constexpr const size_type &size () const noexcept {
        return _size;
    }

};


#include <bits/stdc++.h>

int main() {
    std::size_t n;
    int m, k;
    std::cin >> n >> m >> k;
    
    union_find uf(n);
    std::vector<int> ans(n, -1);
    
    for (int i = 0; i < m; i++) {
        std::size_t x, y;
        std::cin >> x >> y;
        x--; y--;
        uf.unite(x, y);
        ans[x]--; ans[y]--;
    }

    for (int i = 0; i < k; i++) {
        std::size_t x, y;
        std::cin >> x >> y;
        x--; y--;
        if (uf.same(x, y)) {
            ans[x]--; ans[y]--;
        }
    }

    for (std::size_t i = 0; i < n; i++) {
        std::cout << ans[i] + int(uf.size(i)) << '\n';
    }

    return 0;
}

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

const int MAXN = 3010;
const int mod = 1000000007;
void reduce(int & x) { x += x >> 31 & mod; }
char buf[MAXN];
int rs[MAXN], n, m;
int pre[MAXN];
int f[MAXN][MAXN];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> n >> m >> buf + 1;
	for (int i = 1; i <= n + 1; ++i) rs[i] = i;
	for (int i = 1, a, b; i <= m; ++i)
		std::cin >> a >> b, rs[a] = std::max(rs[a], b);
	for (int i = 1; i <= n; ++i) rs[i] = std::max(rs[i], rs[i - 1]);
	for (int i = 1; i <= n; ++i)
		pre[i] = pre[i - 1] + (buf[i] & 1);
	f[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) if (int t = f[i - 1][j]) {
			int hav = j + pre[rs[i]] - pre[rs[i - 1]];
			reduce(f[i][hav] += t - mod);
			if (hav) reduce(f[i][hav - 1] += t - mod);
		}
		for (int j = 0; j <= n; ++j)
			if (rs[i] - i - j < 0) f[i][j] = 0;
	}
	std::cout << f[n][0] << std::endl;
	return 0;
}


Measured memory_bytes: 35584
#include <stdio.h>

#define NUM_OF_WEIGHT	( 10 )

int weight[ NUM_OF_WEIGHT ] =
{
	1, 2, 4, 8, 16, 32, 64, 128, 256, 512
};

void showWeightPattarn( int inputWeight );

int main( void )
{
	int weight;
	
	while( scanf( "%d", &weight ) != EOF )
	{
		showWeightPattarn( weight );
	}
	
	return (0);
}

void showWeightPattarn( int inputWeight )
{
	int i;
	int numOfUsed;
	int useWeight[ NUM_OF_WEIGHT ];
	
	for( i = NUM_OF_WEIGHT - 1, numOfUsed = 0; i >= 0; i-- )
	{
		if( inputWeight - weight[ i ] >= 0 )
		{
			useWeight[ numOfUsed ] = i;
			numOfUsed++;
			inputWeight -= weight[i];
		}
	}
	
	numOfUsed--;
	for( i = numOfUsed; i >= 0; i-- )
	{
		printf( "%d", weight[ useWeight[i] ] );
		if( i != 0 )printf( " " );
	}
	printf( "\n" );
}

Measured memory_bytes: 596
#include <iostream>

int main()
{
    int P, Q, R;
    scanf("%d %d %d", &P, &Q, &R);

    if(P > Q && P > R) printf("%d\n", Q+R);
    else if(Q > R) printf("%d\n", P+R);
    else printf("%d\n", P+Q);
}

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

#define loop(i, times) for(int i = 0; i < times; i++)
#define seloop(i, start_index, end_index) for(int i = start_index; i < end_index; i++)
#define eqseloop(i, start_index, end_index) for(int i = start_index; i <= end_index; i++)

using namespace std;

class NyaGadgetVector
{
public:
	/**
	@brief 加算関数
	@note
	 collectionの全要素にadd_valueだけ値を加算する
	**/
	template<typename T> static void Add(vector<T>& collection, T add_value)
	{
		for (auto& e : collection)
			e += add_value;
	}
	/**
	@brief 標準入力関数
	@note
	 標準入力から入力されたsize個の値をcollectionに格納する
	**/
	template<typename T> static void InputStream(vector<T>& collection, int size)
	{
		for (int i = 0; i < size; i++)
			cin >> collection[i];
	}
	/**
	@brief 最大値取得関数
	@note
	 collectionの要素の中で最大値を取得する
	**/
	template<typename T> static T Max(const vector<T>& collection)
	{
		T max = collection[0];
		for (const auto& e : collection)
		{
			if (max < e)
				max = e;
		}
		return max;
	}
	/**
	@brief 合計関数
	@note
	 collectionのstart_indexからend_index-1までの要素を合計して返す
	**/
	template<typename T> static T Sum(const vector<T>& collection, int start_index, int end_index)
	{
		int sum = 0;
		for (int i = start_index; i < end_index; i++)
			sum += collection[i];
		return sum;
	}
};

int main()
{
	int n; cin >> n;	// 木の本数
	int k; cin >> k;	// 飾り個数
	int diff_num = k - 1;

	vector<int> tree(n, 0);
	NyaGadgetVector::InputStream(tree, n);
	sort(tree.begin(), tree.end());


	vector<int> diff(n-1, 0);
	loop (i, n - 1)
		diff[i] = abs(tree[i + 1] - tree[i]);

	multiset<int> min;
	loop (i, diff.size() - (diff_num-1))
		min.insert(NyaGadgetVector::Sum(diff, i, i+diff_num));

    std::cout << *min.begin(); 
}


Measured memory_bytes: 5760
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
#include <cassert>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;

inline bool check(ll x, ll y, ll xMax, ll yMax) { return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string tostring(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }
template<class T> inline T mypow(T x, ll n) { T res = 1; while (n > 0) { if (n & 1)res = res * x;	x = x * x;	n >>= 1; }return res; }
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

#define For(i,a,b)	for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define rFor(i,a,b)	for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n)	rFor(i,n,0)
#define each(i,n)	for(auto &i : n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define sz(a)		(sizeof(a))
#define tostr(a)	tostring(a)
#define dump(val) 	cerr << #val " = " << val << endl;
#define Fill(a,v)	fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)

const ll dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = 1e17 + 9;

#define int ll
#define double ld

int n;
map<int, int> dp[100001];
int a[100001];

int solve(int i, int ma) {
	if (dp[i].count(ma)) {
		return dp[i][ma];
	}
	if (i == n) {
		return 0;
	}
	if (a[i] <= ma + 1) {
		return dp[i][ma] = solve(i + 1, max(a[i], ma));
	}

	int res = 0;
	int r = a[i] - 1;
	int ad = r / (ma + 1);
	if (ad) {
		res = max(res, solve(i + 1, max(1ll, ma)) + ad);
	}
	return dp[i][ma] = res;
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << solve(0, 0) << endl;

	return 0;
}

Measured memory_bytes: 21504
#include <iostream>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 100000000
using namespace std;
int main()
{
  int N;
  cin>>N;
  int H[N];
  int dp[N]={0};
  rep(i,N){
    cin>>H[i];
    dp[i]=INF;
  }
  dp[0]=0;
  dp[1]=abs(H[1]-H[0]);
  rep(i,N-2)dp[i+2]=min(dp[i]+abs(H[i+2]-H[i]),dp[i+1]+abs(H[i+2]-H[i+1]));
  cout<<dp[N-1]<<"\n";
}

Measured memory_bytes: 1024
W,H,N = map(int,input().split())
x_a=0
y_a=0
x_b=W
y_b=H
for i in range(N):
  x,y,a = map(int,input().split())
  if a ==1:
    x_a=max(x_a,x)
  elif a ==2:
    x_b=min(x_b,x)
  elif a==3:
    y_a=max(y_a,y)
  elif a==4:
    y_b=min(y_b,y)
print((x_b-x_a)*(y_b-y_a) if x_b-x_a > 0 and y_b-y_a > 0 else '0')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int MOD=1000000007;
const int nmax=3123;

int n,a[312],cnt[4],sum,a1,a2,a3;
double dp[312][312][312],res;

double solve(int a,int b)
{
    return (double)a/b;
}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]);
        ++cnt[a[i]];
    }
    sum=cnt[1]+cnt[2]+cnt[3];
    dp[cnt[1]][cnt[2]][cnt[3]]=1;
    for(int i=cnt[3]; i>=0; --i)
    {
        a2=cnt[2]+cnt[3]-i;
        for(int j=a2; j>=0; --j)
        {
            a3=cnt[1]+a2-j;
            for(int k=a3; k>=0; --k)
            {
                if(k!=0)
                    dp[k][j][i]+=dp[k-1][j+1][i]*solve(j+1,k+j+i);
                if(j!=0)
                    dp[k][j][i]+=dp[k][j-1][i+1]*solve(i+1,k+j+i);
                dp[k][j][i]+=dp[k+1][j][i]*solve(k+1,k+j+i+1);
            }
        }
    }
    for(int i=cnt[3]; i>=0; --i)
    {
        for(int j=cnt[2]+cnt[3]-i; j>=0; --j)
        {
            for(int k=sum-i-j; k>=0; --k)
            {
                if(i+j+k!=0)
                    res+=dp[k][j][i]*solve(sum,i+j+k);
            }
        }
    }
    printf("%.9f",res);
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define EACH(i, a) for(auto&& i:a)
#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,a,b) for(ll i = (b)-1; i >= (a); --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define pb push_back
#define ALL(v) (v).begin(),(v).end()

const ll linf = 1e18;
const ll inf = 1e9;

template<class T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}

ll A = 1007, modA = 1e9+7;

vector< vector<ll> > G;
vector<ll> h;

ll add(ll a, ll b) {
    return (a + b) % modA;
}
ll mul(ll a, ll b) {
    return a * b % modA;
}
ll dfs(ll v, ll prev) {
    ll res = 1;
    EACH(to, G[v]) {
        if (to == prev) continue;
        res = add(res, mul(A, dfs(to, v)));
    }
    return h[v] = res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin >> n;
    G.clear(); G.resize(n);
    ll root = 0;
    REP(i, n-1) {
        ll a, b; cin >> a >> b; --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    h.assign(n, -1);
    dfs(0, -1);
    map<ll, ll> cnt;
    ll ans = 0;
    REP(i, n) {
        ans += cnt[h[i]];
        cnt[h[i]]++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 19972
/*
    author: Salam_35
    Created at :

*/

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

#define ll long long int
#define pb push_back
#define sc(n) scanf("%d",&n)
#define Max 100005
#define scan(n) scanf("%lld",&n)
#define pi acos(-1.0)
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ALL(x) x.begin(),x.end()
#define sci(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define load(array,size)  for(ll i=0 ; i<size ; i++) cin>>array[i] ;
#define load1(array,size)  for(ll i=1 ; i<=size ; i++) cin>>array[i] ;
#define INF	1LL<<19
#define pll pair<ll,ll>
#define mst(arr,value) memset(arr,value,sizeof(arr));


const ll MOD = 1e9+7;

typedef vector<ll>vec;
typedef pair<ll,ll> pii;
typedef map<ll,ll>mpll;
typedef set<ll>seet;
vec primes;

double calc(double n)
{
    double ans=0.0;
    for(double i=1.0;i<=n;i++)
    {
        ans+=(double)(i/n);
    }
    return ans;
}
double ans[10000000];
int main()
{
    int n,k;
    cin >> n >>k;
    double arr[n+10];
    cin>>arr[0];
    ans[0]=calc(arr[0]);
    double baal=ans[0];
    for(int i=1;i<n;i++)
    {
        double a;
        cin >> a;
        arr[i]=a;
        baal+=calc(a);
        ans[i]=ans[i-1]+calc(a);
    }
    double uttor=-1.0;

    for(int i=0;i<n-k;i++)
    {
        uttor=max(ans[i+k]-ans[i],uttor);
    }
    if(n==k)
        cout<<setprecision(18)<<fixed<<ans[n-1]<<endl;
    else
    cout<<setprecision(18)<<fixed<<uttor<<endl;
}



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

using namespace std;


int main(){
	
	int n;
	cin >> n;
	int a[n];
	for(int i = 1; i<=n; i++)
		cin >> a[i];
	int ans = 0;
	for(int i = 1; i<=n; i++){
		if(i&1 && a[i]&1)
			ans++;
		}
	cout <<ans <<endl;
	
	
  	


}


Measured memory_bytes: 3616
import sys
sys.setrecursionlimit(1000000)

N=int(input())

L=[[]for i in range(N+1)]
C=[0 for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    C[a]+=1
    C[b]+=1
M=0
m=0
for i in range(1,N+1):
    if len(L[i])>m:
        m=len(L[i])
        M=i
C=list(map(int,input().split()))
C.sort(reverse=True)
#print(C)
l=[-1 for i in range(N+1)]
l[M]=0

X=[0 for i in range(N+1)]
X[M]=C[0]
cnt=1
def dfs(x):
    for i in L[x]:
        if l[i]==-1:
            l[i]=l[x]+1
            global cnt
            X[i]=C[cnt]
            cnt+=1
            dfs(i)
dfs(M)
#print(l)
#print(X)
print(sum(X)-max(X))
ans=str(X[1])
for i in range(2,N+1):
    ans+=" "+str(X[i])
print(ans)

Measured memory_bytes: 11380
#include<iostream>
#include<string>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
#define N 3
#define N2 9

struct Puzzle{
  int f[N2];
  int space;
  string path;
  bool operator < ( const Puzzle &p ) const {
    for( int i = 0 ; i < N2 ; i++ ){
      if( f[i] == p.f[i] ) continue;
      return f[i] > p.f[i];
    }
    return false;
  }
};

static const int dx[4] = { -1, 0, 1, 0};
static const int dy[4] = { 0, -1, 0, 1};
static const char dir[4] = { 'u', 'l', 'd', 'r'};

bool isTarget(Puzzle p){
  int i;
  for( i = 0 ; i < N2 ; i++ ){
    if( p.f[i] != ( i + 1 ) ) return false;
  }
  return true;
}

string bfs(Puzzle s){
  queue<Puzzle> Q;
  map<Puzzle, bool> V;
  int i, a;
  Puzzle  u ,v;
  s.path = "";
  Q.push(s);
  V[s] = true;

  while( !Q.empty()){
    u = Q.front();
    Q.pop();
    if( isTarget(u) ) return u.path;
    int sx = u.space / N;
    int sy = u.space % N;
    for( a = 0 ; a < 4 ; a++ ){
      int tx = sx + dx[a];
      int ty = sy + dy[a];
      if( tx < 0 || ty < 0 || tx >= N || ty >= N ) continue;
      v = u;
      swap(v.f[u.space],v.f[tx*N+ty]);
      v.space = tx * N + ty;
      if( !V[v] ){
	V[v] = true;
	v.path += dir[a];
	Q.push(v);
      }
    }
  }
  return "unsolvable";
}

int main(){
  Puzzle in;
  int i;

  for( i = 0 ; i < N2 ; i++ ){
    cin >> in.f[i];
    if( in.f[i] == 0 ){
      in.f[i] = N2;
      in.space = i;
    }
  }
  string ans = bfs(in);
  cout << ans.size() << endl;
  
  return 0;
}



Measured memory_bytes: 30600
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
    
		int shakeNum = sc.nextInt();
      
      	int counter = 0;
      
      	String rt = "No";
      
      	for(int i = 0; i < shakeNum; i++) {
        	int num1 = sc.nextInt();
        	int num2 = sc.nextInt();
          
          	if(num1 == num2) {
            	counter += 1;
              	if(counter >= 3) {
                	rt = "Yes";
                  	break;
                }
            } else {
            	counter = 0;
            }
        }
    	System.out.println(rt);
    }
}

Measured memory_bytes: 35956