akhauriyash/Code-Regression huggingface dataset:
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#if defined(DAIJOBU)
#include "/home/ichigo/includes.hpp"
#include "PP.hpp"
#define deb(x...) cerr << "[" << #x << "] = " << x << "\n";
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long lint;
typedef vector<lint> vlint;
typedef vector<vlint> vvlint;
typedef pair<lint, lint> plint;
typedef double ld;

template<class T> bool chmin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	int a[n - 1];
	forn(i, n - 1)cin >> a[i];
	int ans = a[0] + a[n - 2];
	forn(i, n - 2)ans += min(a[i], a[i + 1]);
	cout << ans << '\n';
	return 0;
}



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

int main(void){
        int a,b,i,ans=0;

        cin >> a >> b;
        if(a <= b){
                for(i=0;i<b;i++){
                        ans += a*pow(10,i);
                }
                cout << ans << endl;
                return 0;
        }else{
                for(i=0;i<a;i++){
                        ans += b*pow(10,i);
                }
                cout << ans << endl;
                return 0;
        }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ford(i,a,b) for(int i=(a);i>=b;i--)
#define rep1(i,a,b) for(int i=(a);(i)<=(b);(i)++)
#define rep(i,a,b) for(int i=(a);(i)<(b);(i)++)
#define ll long long
#define N 105
#define pql priority_queue<ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rev(a,n) reverse(a,a+n)
using namespace std;
int x,n,p[N];
bool isforbidden(int a){
	rep(i,0,n) 
		if(p[i]==a) return 1;
	return 0;
}
int main() {
	cin>>x>>n;
	int min=x,max=x;
	rep(i,0,n) cin>>p[i];
	while(1) {
		if(!isforbidden(min)) break;
		min--;
	}
	while(1) {
		if(!isforbidden(max)) break;
		max++;
	}
	if(x-min>max-x) cout<<max;
	else cout<<min;
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
int MOD = 1000000007; //10^9 + 7


int main() {
	int r;
	cin >> r;
	cout << r * r << endl;
}

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

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

template<class T,class U>
ostream& operator<<(ostream& os,const map<T, U> & mp){
	os << "{";
	int i = 0;
	for(auto it : mp){
		if(i) os<<", ";
		os << it;
		i++;
	}
	os << "}";	
	return os;
}

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

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10, mod = 1e9 + 7;
int fact[N], invfact[N];
inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (((ll) x) * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}
void pre(){
	fact[0] = invfact[0] = 1;
	for(int i = 1;i < N; i++) fact[i] = mul(i, fact[i - 1]);
	invfact[N - 1] = inv(fact[N - 1]);
	for(int i = N - 2; i >= 1; i--) invfact[i] = mul(invfact[i + 1], i + 1);
	assert(invfact[1] == 1);
}

inline int C(int n, int k){
	if(n < k || k < 0) return 0;
	return mul(fact[n], mul(invfact[k], invfact[n - k]));
}
// const int N = 200005;
char s[N];
int main(){
	pre();
	int n; sd(n);
	scanf("%s", s);
	int curr_open = 0, ans = 1;
	for(int i = 0; i < 2 * n; i++){
		if( (s[i] == 'W') ^ (curr_open & 1) ){
			ans = mul(ans, curr_open);
			curr_open--;
		} else{
			curr_open++;
		}
	}
	printf("%d\n", mul(curr_open == 0, mul(ans, fact[n])));
}

Measured memory_bytes: 8192
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

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

N, W = MAP()
wv = [LIST() for _ in range(N)]
w0 = wv[0][0]

dic = defaultdict(list)
for w, v in wv:
	dic[w].append(v)

for key in dic:
	dic[key].sort(reverse=True)
	dic[key] = [0] + dic[key]
	dic[key] = list(accumulate(dic[key]))

for x in [w0, w0+1, w0+2, w0+3]:
	if not dic[x]:
		dic[x] = [0]
# print(dic)

ans = 0
for a in range(len(dic[w0])):
	for b in range(len(dic[w0+1])):
		for c in range(len(dic[w0+2])):
			for d in range(len(dic[w0+3])):
				w = w0*a + (w0+1)*b + (w0+2)*c + (w0+3)*d
				s = dic[w0][a] + dic[w0+1][b] + dic[w0+2][c] + dic[w0+3][d]
				if w <= W:
					ans = s if ans < s else ans
print(ans)


Measured memory_bytes: 5992
def solve():
    n = 5
    x = [int(input()) for _ in range(n)]
    k = int(input())
    for i in range(n):
        for j in range(i+1, n):
            if x[j] - x[i] > k:
                print(':(')
                exit()
    print('Yay!')


if __name__ == '__main__':
    solve()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;

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

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

    vector<int> num;
    int k;

    REP(i, 5) {
        int a;
        cin >> a;
        num.push_back(a);
    }
    cin >> k;
    if ((num[4] - num[0]) <= k) {
        cout << "Yay!\n";
    } else {
        cout << ":(\n";
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
int main(){
  long A,B,temp;
  std::cin>>A>>B;
  if(A<B){
    temp=B;
    B=A;
    A=temp;
  }
  if((A-B)%2==1){
    std::cout<<"IMPOSSIBLE"<<std::endl;
  }else{
    long ans=(A+B)/2;
    std::cout<<ans<<std::endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

int main()
{
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(i, n - 2)
  {
    if (s.substr(i, 3) == "ABC")
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String str = br.readLine();
    	if (str.equals("A")) {
    		System.out.println("T");
    	}
    	if (str.equals("T")) {
    		System.out.println("A");
    	}
    	if (str.equals("C")) {
    		System.out.println("G");
    	}
    	if (str.equals("G")) {
    		System.out.println("C");
    	}
    }
}

Measured memory_bytes: 22996
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <iomanip>
using namespace std;

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

  int n;
  cin >> n;
  int tmp = 1;
  for(int i = 0; i < 100; i++) {
    tmp *= 2;
    if (tmp > n) {
      tmp /= 2;
      cout << tmp << endl;
      return 0;
    }
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define inf (int)(1e9 + 1)

int main(){
	int N, i;
	scanf("%d", &N);
	vector<pair<int, int>> lr(N);
	for(i = 0; i < N; i++){
		int X, L;
		scanf("%d%d", &X, &L);
		lr[i].first = X - L;
		lr[i].second = X + L;
	}
	for(i = 0; i < N; i++){
		swap(lr[i].first, lr[i].second);
	}
	sort(lr.begin(), lr.end());
	for(i = 0; i < N; i++){
		swap(lr[i].first, lr[i].second);
	}
	int ans = 0;
	int now = -inf;
	for(i = 0; i < N; i++){
//		printf("lr[%d] = (%d, %d)\n", i, lr[i].first, lr[i].second);
		if(now <= lr[i].first){
			ans++;
			now = lr[i].second;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

struct UnionFind {
    vector<int> Parent;
    vector<int> Size;

    explicit UnionFind(int N) : Parent(N), Size(N,1){
        for(int i = 0; i < N; i++) Parent[i] = i;
    }

    int root(int A) {
        if (Parent[A] == A) return A;
        return Parent[A] = root(Parent[A]);
    }

    bool merge(int A, int B) {
        A = root(A);
        B = root(B);
        if (A == B) return false;

        if (Size[A] < Size[B]) swap(A, B);

        Size[A] += Size[B];
        Parent[B] = A;
        return true;
    }

    bool issame(int A, int B) { //
        return root(A) == root(B);
    }

    int findsize(int A) {
        return Size[root(A)];
    }
};

struct edge {
    int u, v, cost;
    bool operator < ( const edge &e) const {
        return cost < e.cost;
    }
};

int n,V,E;
vector<edge> es;

int kruskal(){
    sort(es.begin(),es.end());
    UnionFind Tree(V);
    int res = 0;
    for(int i = 0; i < E; i++){
        edge e = es[i];
        if(!Tree.issame(e.u, e.v)){
            Tree.merge(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}


signed main() {
    cin >> n;

    vector<pair<pair<int,int>,int>> a(n);
    for(int i = 0 ; i < n; i++){
        cin >> a[i].first.first >> a[i].first.second;
        a[i].second = i;
    }
    sort(a.begin(),a.end());
    for(int i = 1; i < n; i++){
        edge e = {};
        int u = a[i].second;
        int v = a[i-1].second;
        int cost = a[i].first.first - a[i-1].first.first;
        e = {u, v, cost};
        es.push_back(e);
    }

    for(int i = 0; i < n; i++){
        swap(a[i].first.first, a[i].first.second);
    }

    sort(a.begin(),a.end());
    for(int i = 1; i < n; i++){
        edge e = {};
        int u = a[i].second;
        int v = a[i-1].second;
        int cost = a[i].first.first - a[i-1].first.first;
        e = {u, v, cost};
        es.push_back(e);
    }

    V = n;
    E = es.size();
    cout << kruskal() << endl;
}



Measured memory_bytes: 10864
#include <stdio.h>
#define N 20000001

int B[N], C[N], A[N], n;

void CountingSort( int k ){
  int i, j;
  for( i = 0; i <= k; i++ ){
    C[i] = 0;
  }
  for( j = 1; j <= n; j++ ){
     C[A[j]]++;
  }
  for( i = 1; i <= k; i++ ){
    C[i] = C[i] + C[i-1];
  }
  for( j = n; j > 0; j-- ){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
}

main(){

  int i, max = 0;
  scanf("%d", &n);

  for( i = 1; i <= n; i++ ){
    scanf("%d", &A[i]);
    if(max < A[i]){
      max = A[i];
    }
  }

  CountingSort( max );
  
  for( i = 1; i <= n; i++ ){
    if(i > 1) printf(" ");
    printf("%d", B[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 21076
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define MAX(X,Y) (*max_element(X,Y))
#define MIN(X,Y) (*min_element(X,Y))
#define NP(X,Y) next_permutation(X,Y)
#define setp(X,Y) cout<<fixed<<setprecision(Y)<<X;
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,M,R;
int D[210];
int d[210][210];
int A[40010],B[40010],C[40010];


signed main(){
	cin>>N>>M>>R;
	REP(i,R){
		cin>>D[i];
		D[i]--;
	}
	REP(i,N)REP(j,N){
		d[i][j]=INF;
	}
	REP(i,M){
		cin>>A[i]>>B[i]>>C[i];
		A[i]--,B[i]--;
		d[A[i]][B[i]]=C[i];
		d[B[i]][A[i]]=C[i];
	}
	REP(k,N){
		REP(i,N){
			REP(j,N){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	sort(D,D+R);
	int ans=INF;
	do{
		int S=0;
		REP(i,R-1){
			S+=d[D[i]][D[i+1]];
		}
		ans=min(ans,S);
	}while(NP(D,D+R));
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int a[100100],b[100100];
int ans[100100];
vector<int> ab[100100];
int check[100100];
map<Pi,int> m;
int main(){
	cin>>n;
	REP(i,n-1){
		cin>>a[i]>>b[i];
		a[i]--,b[i]--;
		ab[a[i]].push_back(b[i]);
		ab[b[i]].push_back(a[i]);
	}
	int ans=0;
	REP(i,100100){
		ans=max(ans,ab[i].size());
	}
	cout<<ans<<endl;
	queue<Pi> q;
	q.push(Pi(0,-3));
	check[0]=1;
	while(q.size()){
		Pi tp=q.front();
		q.pop();
		int t1=tp.first;
		int t2=tp.second;
		int k=-1;
		for(int i=0;i<ab[t1].size();i++){
			if(check[ab[t1][i]]==1)continue;
			k++;
			if(k==t2)k++;
			m.insert(make_pair(Pi(t1,ab[t1][i]),k));
			m.insert(make_pair(Pi(ab[t1][i],t1),k));
			q.push(Pi(ab[t1][i],k));
			check[ab[t1][i]]=1;
		}
	}
	for(int i=0;i<n-1;i++){
		cout<<m.at(Pi(a[i],b[i]))+1<<endl;
	}
	return 0;
}
		

Measured memory_bytes: 19712
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())

edges = [[] for _ in range(n)]
l = {}
for i in range(n-1):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    l[(a-1,b-1)] = i
    l[(b-1,a-1)] = i

ans = [0]*(n-1)

visited = [-1]*n
q = deque([0])
visited[0] = 0

while q:
    v = q.popleft()
    i = 1
    for x in edges[v]:
        if visited[x] < 0:
            if i == visited[v]:
                i += 1
            visited[x] = i
            ans[l[(v,x)]] = i
            q.append(x)
            i += 1

print(max(ans))
for i in range(n-1):
    print(ans[i])



Measured memory_bytes: 94368
#include <bits/stdc++.h>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =999999999;

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}

//素数判定
ll isprime(ll n){
  bool prime=true;
  for(int i=2;i<n;i++){
    if(n%i==0){
      prime=false; break;
    }
  }
if(prime){cout<<n<<" is prime"<<endl;
         }else{cout<<n<<" is not prime"<<endl;}

}
//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




//10億7。　　　100000007
//2*2行列 H*W
//vector<vector<int>> vec(H,vector<int>(W));
//for(int i=0;i<H;i++){
//for(int j=0;j<W;j++){
//cin>>vec[i][j];
//  }
//}

//文字列→数列
//string S;int A=atoi(S.c_str());
//数列→文字列
//int A;string S=to_string(A);
//数字判定　isdigit(a)
//pair宣言　pair<int,int> p(5,7);
//ソート　sort(vec.begin(),vec.end());



int main(){
cout<<fixed<<setprecision(10);

int N;cin>>N;
  if(N%2==0){
    cout<<N<<endl;
  }else{cout<<N*2<<endl;
       }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int N,i,j;
	int d[200];
	cin >> N;
	int n = N;
	for (i = 1; i <= N;i++) {
		cin >> d[i];
		for (j = 0; j <= i-1; j++) {
			if (d[i] == d[j]) {
				n--;
				d[j] = 0;
			}
		}
	}
	cout << n;

	return 0;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

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

	int H,W;
	cin>>H>>W;
	vector<string> SMAP(H);
	rep(i,0,H)cin>>SMAP[i];

	vector<vector<int>> DP(H+1,vector<int>(W+1,0));
	DP[0][0]=1;
	rep(i,0,H)rep(j,0,W)
	{
		int ni,nj;
		ni=i+1,nj=j;
		if(ni<H&&nj<W&&SMAP[ni][nj]!='#')DP[ni][nj]=(DP[ni][nj]+DP[i][j])%MOD;
		ni=i,nj=j+1;
		if(ni<H&&nj<W&&SMAP[ni][nj]!='#')DP[ni][nj]=(DP[ni][nj]+DP[i][j])%MOD;
	}

	cout<<DP[H-1][W-1]<<endl;
	
	return 0;
}

Measured memory_bytes: 9216
n , m = map(int,input().split(" "))
c = []
ans = 0
pen = 0
for i in range(n):
    c.append(0)

for i in range(m):
    x , s = input().split(" ")
    p = int(x)
    if s == "AC":
        if c[p-1] == 0:
            c[p-1] = 1
            ans += 1
        elif c[p-1] < 0:
            pen += -(c[p-1])
            c[p-1] = 1
            ans += 1
    elif s == "WA":
        if c[p-1] <= 0:
            c[p-1] -= 1
print(str(ans) + " " + str(pen))

Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,a,tmp,count=0;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>a;
        if (i!=0&&a==tmp) {
            count++;
            tmp=0;
        } else {
            tmp=a;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>

#define DIV 1000000007
using namespace std;

typedef struct {
    int t;
    int x;
    int y;
}travel_t;

int main() {
    int N;
    cin >> N;

    vector<travel_t> travel(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> travel[i].t >> travel[i].x >> travel[i].y;
    }

    bool flag = true;
    for (int i = 1; i <= N; i++) {
        int dt = travel[i].t - travel[i - 1].t;
        int dist = abs(travel[i].x - travel[i - 1].x) + abs(travel[i].y - travel[i - 1].y);
            if (dt < dist)flag = false;
            else {
                if (dt % 2 != dist % 2) flag = false;
            }

    }
    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#define re register
#define maxn 250000
#define mod 1000000007
#define ll long long
using namespace std;
int last,cnt,sum=26;
char s[maxn];
bool vis[maxn];
int L[maxn],R[maxn];
char ans;

int main(){
	scanf("%s",s);
	int len=strlen(s);
	R[0]=len-1;
	for(re int i=len-1;i>=0;i--){
		if(vis[s[i]-'a']==0){
			sum--;
			vis[s[i]-'a']=1;
			if(sum==0){
				L[cnt]=i;
				cnt++;
				R[cnt]=i-1;
				sum=26;
				memset(vis,0,sizeof(vis));
			}
		}
	}
	L[cnt]=0;
	char ans;
	for(re int i=cnt;i>=0;i--){
		memset(vis,0,sizeof(vis));
		for(re int j=last;j<=R[i];j++){
			vis[s[j]-'a']=1;
		}
		for(re int j=0;j<26;j++){
			if(!vis[j]){
				printf("%c",j+'a');
				ans=j+'a';
				break;
			}
		}
		for(re int j=last;j<len;j++){
			if(s[j]==ans){
				last=j+1;
				break;
			}
		}
	}
	return 0;
}

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

int main(){
  int k;
  cin>>k;
  vector<ll>a;
  for(int i=1;i<=9;i++)a.push_back(i);
  while(1){
    if(k<=a.size()){
      cout<<a[k-1];
      return 0;
    }
    k-=a.size();
    vector<ll>old;
    swap(a,old);
    for(ll d:old){
      for(int i=-1;i<=1;i++){
        int s=d%10+i;
        if(s>9 ||s<0)continue;
        a.push_back(d*10+s);
      }
    }
  }
}


Measured memory_bytes: 1712
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor

import heapq
import itertools
import operator


inf = float('inf')


def get_int():
    return int(input())


def get_str():
    return input().strip()


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


def get_char_list():
    return list(input().strip())


# inputs
S = ""


def set_inputs():
    global S
    S = get_str()


def main():
    set_inputs()
    stack = []
    ret = 0
    for c in S:
        if stack and stack[-1] != c:
            ret += 2
            stack.pop(-1)
        else:
            stack.append(c)
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 46320
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <math.h>
using namespace std;

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

int main() {
  int N, M; cin >> N >> M;
  vector<vector<int> > e(N);
  for (int i = 0; i < M; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    e[a].push_back(b);
    e[b].push_back(a);
  }

  for (int i = 0; i < N; i++) {
    cout << e[i].size() << endl;
  }
}


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

using namespace std;

int main() {

  string substr;
  getline(cin, substr);
  
  string line;
  getline(cin, line);
  const int n = stoi(line);
  int count = 0;
  for ( int i = 0; i < n; i++ ){
    string input;
    getline(cin, input);
    input = input + input;
    if ( input.find( substr ) != string::npos ) {
      count++;
    }
  }
  cout << count << endl;
}

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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod (ll)(1e9 +7);

const double pi = acos(-1.0);

typedef vector<int> vi;
typedef string ss;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b; // Be careful not to overflow
}

ll digsum(ll n){
    ll sum = 0;
    while(n > 0){
        sum += n % 10;
        n /= 10;
    }

    return sum;
}

int main()
{
    ll n;
    cin >> n;
    vector<double>  a(n);
    rep(i,n)cin >> a[i];

    sort(all(a));

    double ans = 0;
    ans += a[0] / pow(2,n-1);
    REP(i,1,n)ans += a[i] / pow(2,n-i);

    /*rep(i,n)cout << a[i] << " ";
    cout << endl;*/

    //cout << a[n-1] / pow(2,n-1) << endl;
    
    printf("%.30f\n",ans);

    return 0;
}

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

void removeSpaces(string str)
{
    int count = 0;
    for (int i = 0; str[i]; i++)
        if (str[i] != ' ')
            str[count++] = str[i];
    str[count] = '\0';
}
int main()
{

    string str1;
    string str2;

    cin>>str1;
    cin>>str2;

    if(str1.size()>=101 || str2.size()>=101 || str1.size()<=0 || str2.size()<=0 )
    {
        return 0;
    }
    removeSpaces(str1);
    removeSpaces(str2);
    for (int i=0; i<str1.size(); i++)
    {
        str1[i]=tolower(str1[i]);
    }
    for (int j=0; j<str2.size(); j++)
    {
        str2[j]=tolower(str2[j]);
    }
 cout<<str2<<str1<<endl;


}


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

int main() {
    int a, b;  cin >> a >> b;
    if (b % a == 0)  cout << a+b << endl;
    else  cout << b-a << endl;
}

Measured memory_bytes: 256
/*
 _   ________   ___       __ ___   _           _  _
| | / /|  _  \ / _ \     / // _ \ | |         | |(_)
| |/ / | | | |/ /_\ \   / // /_\ \| | __ __ _ | | _
|    \ | | | ||  _  |  / / |  _  || |/ // _` || || |
| |\  \| |/ / | | | | / /  | | | ||   <| (_| || || |
\_| \_/|___/  \_| |_//_/   \_| |_/|_|\_\\__,_||_||_|
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
const int N = 5e5+50;
const int mod = 1e9+7;
const int in = 1e9+9;
#define size fksjfs
typedef pair<int,int> ii;
int n, m, k, size[N], col[N];
int parents[N];
pair<ii,int> edge[N];
#define fi first
#define se second
void Init(int n){
	for(int i=1;i<=n;i++) parents[i] = i, size[i] = 1;
}
int Find(int x){
	return parents[x] == x ? x : (parents[x] = Find(parents[x]));
}
void Union(int i,int j){
	int x = Find(i);
	int y = Find(j);
	if(x==y) return;
	if(size[x]>=size[y]){
		parents[y] = x;
		size[x] += size[y];
	}else{
		parents[x] = y;
		size[y]+=size[x];
	}
}
signed main(){
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) cin >> col[i];
	for(int i=1;i<=m;i++){
		int u, v, w;
		cin >> u >> v >> w;
		if(col[u]) u = col[u];
		else u+=k;
		if(col[v]) v = col[v];
		else v+=k;
		edge[i] = {{u,v},w};	
	}
	Init(n+k);
	sort(edge+1,edge+m+1,[](pair<ii,int> _a,pair<ii,int> _b){return _a.se < _b.se;});
	int ans = 0;
	int cnt = 0;
	for(int i=1;i<=m;i++){
		if(cnt==k-1) continue;
		int u = edge[i].fi.fi, v = edge[i].fi.se;
		if(Find(u)!=Find(v)){
			cnt++;
			Union(u,v);
			ans+=edge[i].se;
		}
	}
	if(cnt!=k-1) return cout << -1 , 0;
	cout << ans;
	return 0;
}


Measured memory_bytes: 16640
def F(N):
    if ((N+1) // 2) % 2 == 0:
        bit = 0
    else:
        bit = 1
    if N % 2 == 0:
        return bit ^ N
    else:
        return bit

A, B = map(int, input().split())
ans = F(A-1) ^ F(B)
print(ans)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define P pair<int,int>
#define PI 3.141592653589793
const int INF = 1001001001;

int main() {
	string s;
	cin >> s;
	bool ok = true;
	if (s.size() == 1|| s.size()%2==1) {
		cout << "No" << endl;
		return 0;
	}
	
	rep(i, s.size()) {
		if (i % 2 == 0) {
			if (s[i] == 'h') continue;
			ok = false;
			break;
		}
		else {
			if (s[i] == 'i') continue;
			ok = false;
			break;
		}
	}
	if (ok)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
k = int(input())

ls = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
]

print(ls[k-1])


Measured memory_bytes: 2940
N, K = map(int, input().split())

check_list = list(range(1,N+1))

for i in range(K):
  d = int(input())
  a = list(map(int, input().split()))
  for j in a:
    if j in check_list:
      check_list.remove(j)
print(len(check_list))




Measured memory_bytes: 9188
N, MOD = int(input()), 10 ** 9 + 7
memo = [{} for i in range(N + 1)]


def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i - 1], t[i] = t[i], t[i - 1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret


print(dfs(0, 'TTT'))


Measured memory_bytes: 48220
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	if(n<105){
		cout<<0<<endl;
	}
	else if(n<135){
		cout<<1<<endl;
	}
	else if(n<165){
		cout<<2<<endl;
	}
	else if(n<189){
		cout<<3<<endl;
	}
	else if(n<195){
		cout<<4<<endl;
	}
	else cout<<5<<endl;
}
//105 135 165 189 195



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define qi queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define prq priority_queue
#define foreach(it,c) for(__typeof((c).begin()) it=c.begin();it!=c.end();it++)
//#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
inline ll read(){
	ll x=0;
	int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	return x*f;
}
inline void out(int x){
	if(x>=10)out(x/10);
	putchar(x%10+'0');
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(d==1)cout<<"1\n";
	else cout<<"0\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int n,i;
    cin>>n;
    int v[n],c[n];
    vector<int> a;
    for (i=0;i<n;i++)
        cin>>v[i];
    for (i=0;i<n;i++)
        cin>>c[i];
    int ans=0;
    for (i=0;i<n;i++)
        a.pb(v[i]-c[i]);
    sort(a.rbegin(),a.rend());
    for (int x: a)
    {
        if (x>=0)
            ans+=x;
        else
            break;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){

int x[10];
int n;


cin >> n;

int max=0;
int sum=0;


for(int i = 0;i < n;i++){
cin >> x[i];
sum = sum+x[i];
	if(max<x[i]){
		max=x[i];
	}
}

if(sum>2*max){
	cout << "Yes";
}else{
	cout << "No";
}

return 0;
}

Measured memory_bytes: 256
X = int(input())
if 400 <= X <= 599 :
    print('8')
elif 600 <= X <= 799 :
    print('7')
elif 800 <= X <= 999 :
    print('6')
elif 1000 <= X <= 1199 :
    print('5')
elif 1200 <= X <= 1399 :
    print('4')
elif 1400 <= X <= 1599 :
    print('3')
elif 1600 <= X <= 1799 :
    print('2')
elif 1800 <= X <= 1999 :
    print('1')

Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
string x;
  cin>>x;
  int n=x.size();
  int ans=n;
  int s=0;
  rep(i,0,n){
    if(x[i]=='S') s++;
    else{
      if(s>0){
        s--;
        ans-=2;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3676
import java.util.*;
public class Main {
    
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] H = new int[N];
        for (int i = 0; i < H.length; i++) {
            H[i] = scanner.nextInt();
        }
        int[] good = new int[N];
        for (int i = 0; i < good.length; i++) {
            good[i] = 1;
        }
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt()-1;
            int B = scanner.nextInt()-1;

            if(H[A] < H[B]) good[A] = 0;
            else if(H[A]==H[B]){
                good[A]=0;
                good[B]=0;
            }else{
                good[B] = 0;
            }
        }
        int res = 0;
        for(int i=0; i<N; i++){
            res += good[i];
        }
        System.out.println(res);
    }
}

Measured memory_bytes: 60944
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
 
using namespace std;
using ll = long long int;


template <typename number>
pair<number, number> extended_euclid(number a, number b)
{
    number r0, r1, a0, a1, b0, b1;
    r0 = a; r1 = b;
    a0 = 1; a1 = 0;
    b0 = 0; b1 = 1;
    while (r1>0) {
        number q1 = r0 / r1;
        number r2 = r0 % r1;
        number a2 = a0 - q1 * a1;
        number b2 = b0 - q1 * b1;
        r0 = r1 ; r1 = r2;
        a0 = a1 ; a1 = a2;
        b0 = b1 ; b1 = b2;
    }
    number c = r0;
    a = a0; //x
    b = b0; //y
    return  {a, c};
}



ll calcLCM(ll a, ll b) {
  pair<ll, ll> result = extended_euclid(a, b);
  return a * b / result.second;
}
 
int main()
{
  int n, m;
  cin >> n >> m;
  string s, t;
  cin >> s >> t;
  ll lcm = calcLCM(n, m);
  ll alpha = lcm / n;
  ll beta = lcm / m;
  map<ll, char> exist;
  exist[1] = s[0];
  for(ll i = 1; i < n; i++)
  {
    ll index = 1 + i * alpha;
    exist[index] = s[i];
  }
  bool can = true;
  if(s[0] != t[0]) can = false;
  for(ll i = 1; i < m; i++)
  {
    ll index = 1 + i * beta;
    if(exist.count(index)){
      if(exist[index] != t[i]) can = false;
    }
  }
  if(can) {
    cout << lcm << endl;
  }else{
    cout << -1 << endl;
  }
}


Measured memory_bytes: 6144
#include <iostream>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <limits>
#include <vector>
#define ll long long

using namespace std;

struct Edge {
    int to;
    int id;
};

vector<vector<Edge> > vec;
//vector<int> ans;
vector<int> ans_vec;

void dfs(int c,int p,int parent_color){
    int k = 1;
    //cout << c << " " << p << " " << parent_color << endl;
    for(int i = 0;i < vec[c].size();i++){
        if(vec[c][i].to == p) continue;
        else{
            if(k != parent_color){
                ans_vec[vec[c][i].id] = k;
                k++;
            }
            else{
                k++;
                ans_vec[vec[c][i].id] = k;
                k++;
            }            
            dfs(vec[c][i].to,c,k - 1);
        }

    }
}

int main()
{
    int N;
    cin >> N;
    vec.resize(N);
    ans_vec.resize(N - 1);

    for(int i = 0;i < N - 1;i++){
        Edge tmp1,tmp2;
        int a,b;
        cin >> a >> b;
        --a;
        --b;
        tmp1.to = b;
        tmp1.id = i;
        tmp2.to = a;
        tmp2.id = i;
        vec[a].push_back(tmp1);
        vec[b].push_back(tmp2);
    }

    dfs(0,-1,-1);

    int max_ans = 0;

    for(int i = 0;i < ans_vec.size();i++){
        if(max_ans < ans_vec[i]){
            max_ans = ans_vec[i];
        }
    }

    cout << max_ans << endl;
    for(int i = 0;i < ans_vec.size();i++){
        cout << ans_vec[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 8320
#include<bits/stdc++.h>
using namespace std;
vector<int>v[200005];
int arr[200005];
int ans[200005];
int main(){
	int n,q;
	cin>>n>>q;
	int a,b;
	int u=n;
	while(u>1){
		cin>>a>>b;
		v[b].push_back(a);
		u--;
	}
	
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<v[i].size();j++){
//			cout<<v[i][j]<<" ";
//		}	
//		cout<<endl;
//	}
	
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>a>>b;
		arr[a]+=b;
	}
	
//	for(int i=1;i<=n;i++)cout<<arr[i]<<" ";cout<<endl;
	ans[1]=arr[1];
	printf("%d",ans[1]);
	for(int i=2;i<=n;i++){
		if(v[i].size()==0)continue;
		int sum=0;
		for(int j=0;j<v[i].size();j++){
			int k=v[i][j];
			sum+=ans[k];
		}
		ans[i]=sum+arr[i];
		printf(" %d",ans[i]);
	}
	
	return 0;
}

Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i = x; i < n; i++)
#define MAX 100
#define INF 1000000001
#define ADD_ROOT(size)                          \
    void *root_ADD_ROOT_[size + 2];             \
    root_ADD_ROOT_[0] = root;                   \
    for (int i = 1; i <= size; i++)             \
        root_ADD_ROOT_[i] = NULL;               \
    root_ADD_ROOT_[size + 1] = ROOT_END;        \
    root = root_ADD_ROOT_

#define DEFINE1(var1)                           \
    ADD_ROOT(1);                                \
    Obj **var1 = (Obj **)(root_ADD_ROOT_ + 1)

#define ad(x) int i = 100;
// enum {
//   AST_INT,
//   AST_SYM,
//   AST_STR,
//   AST_FUNCALL,
// };



// double winProb(int Rp, int Rq) {
//     return 1/(1+pow(10, (Rq-Rp)/400.));
// }

// int R[1<<10];
// double dp[12][1<<10];
int n,k;


int main() {
  cin >> n >> k;
  vector<int> a(n);
  REP(i,0,n) cin >> a[i];
  
  int ans = 1 + (n-2)/(k-1);
  cout << ans << endl;
  
  
//   int mn = INF;
//   int min_idx = -1;
//   REP(i,0,n) {
//       if (a[i] < mn) {
//           mn = a[i];
//           min_idx = i;
//       }
//   }
  
//   int one_step = k - 1;
//   int left = 0;
//   int right = 0;
//   left = min_idx % 2 == 1 ? ((min_idx+1) / one_step) : (min_idx / one_step);
//   right = ((n-1) - min_idx) % 2 == 1 ? (((n-1) - min_idx) + 1) / one_step : ((n-1) - min_idx) / one_step;
  
//   cout << left + right << endl;
//   if (sum - n)
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<ll>
#define ub upper_bound
#define lb lower_bound
#define all(v) ((v).begin()),((v).end())
#define allr(v) ((v).rbegin()),((v).rend())
#define ff first
#define ss second
#define mp make_pair
#define pll pair<ll,ll> 
#define fo(i,n) for(ll i=0;i<n;i++)
#define foa(i,s,e) for(ll i=(s);i<e;i++)
#define fod(i,s,e) for(ll i= (s);i>=(e);i--)
ll mod1 = 1e9 + 7;
ll mod2 = 998244353;
ll mul(ll x,ll y){
    return (1ll* (x%mod1)*(y%mod1));
}
ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
//ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
ll gcd(ll a,ll b){if(a<b) return gcd(b,a);if(b==0) return a;return gcd(b,a%b);} 
ll min(ll a,ll b){if(a<b)return a;return b;}
ll max(ll a,ll b){if(a>b)return a;return b;}
vll g[200001];
ll vis[200001];
ll in[200001];
ll n,k,f;
ll timer = 1;
ll nod = 1;
ll curr,K;
void dfs(ll u,ll k){
    
    if(vis[u]){
        if(k==0)curr = u;
        nod = u;
        f = timer - in[u];
        K = k;
        return;
    }
    vis[u] = 1;
    in[u]=timer++;

    if(k==0){
        curr = u;
        return;
    }
    k--;
    
    for(ll x:g[u]){
        
        dfs(x,k);
    }
}
void dfs2(ll u,ll k){
    if(k==0){
        curr = u;
        return;
    }
    k--;
    for(ll x:g[u]){
        dfs2(x,k);
    }
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    //freopen("error.txt" , "w" , stderr) ;
    #endif
    
    
    cin>>n>>k;
    ll temp;
    for(ll i = 1;i<=n;i++){
        cin>>temp;
        g[i].pb(temp);
    }
    dfs(1,k);
    //cout<<K<<endl;
    if(K>0){
        ll p = K%f;
        for(ll i = 1;i<=n;i++){
            vis[i] = 0;
        }
        dfs2(nod,p);
    }

    cout<<curr<<endl;

}

Measured memory_bytes: 22704
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <numeric>
#include <functional>
#include <stack>

int main (){
	int a;

	std::cin >> a;

	for (size_t i = 1; i <= 9; i++)
	{
		for (size_t j = 0; j <= 9; j++)
		{
			if (a == i * j) {
				std::cout << "Yes" << std::endl;
				return 0;
			}
		}
	}

	std::cout << "No" << std::endl;
	return 0;
}

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    string s1, s2;
    cin >> s1 >> s2;
    int l1 = sz(s1), l2 = sz(s2);
    vector<vi> dp(l1+1, vi(l2+1));
    rep1(i, l1) dp[i][0] = i;
    rep1(i, l2) dp[0][i] = i;
    rep(i, l1) rep(j, l2) {
        int cost = (s1[i]==s2[j]?0:1);
        dp[i+1][j+1] = min({ dp[i+1][j]+1, dp[i][j+1]+1, dp[i][j]+cost });
    }
    cout << dp[l1][l2] << endl;
    return 0;
}



Measured memory_bytes: 6876
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)

def min(a,b)
  a < b ? a : b
end


def max(a,b)
  a > b ? a : b
end

max_a = a[0]
idx = 0
n.times do |i|

  if a[i] > max_a
    max_a = a[i]
    idx = i
  end
end

max_a = a.max

diff = 0
tmp = 0
num = 0



if n == 2
  puts "#{a.max} #{a.min}"
  exit
end

# puts idx


n.times do |i|
  next if i == idx
  tmp = a[i]
  if a[i] >  max_a/2
    tmp = max_a - a[i]
  end
  # p tmp

  if tmp > diff
    diff = tmp
    num = a[i]
  end
end

puts "#{max_a} #{num}"


Measured memory_bytes: 9484
#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<n;i++)
#define vec vector
typedef int64_t intl;
#define fi first
#define se second
#define pushb push_back
#define popb pop_back
#define SortA(c) sort(c.begin(), c.end())
#define SortD(c) sort(c.rbegin(), c.rend())
const intl mod = 1000000007;

intl modpow(intl a, intl n, intl p){
  intl res = 1;
  while (n > 0){
    if (n&1){res = (res * a) % p;}
	a = (a * a) % p;
    n >>= 1;
  }
  return res;
}

intl modinv(intl a, intl p){
  if (a == 0){
    cout << "/0 at modinv"<<endl;
    exit(0);
  }
  if (a < 0){
    cout << "/- at modinv" <<endl;
    exit(0);
  }
  if (a==1){return 1;}
  if (a > p){return modinv(a%p, p);}

  return p - ( modinv(p%a,p) * (p/a) ) % p;
}

intl modcomb(intl n, intl k, intl p){
  if (k > n || k < 0 || n < 0){
    cout << "error at modcomb"<<endl;
    exit(0);
  }
  if (2*k > n){ k = n-k;}
  if (k ==0){return 1;}
  intl c=1;
  for (intl i = 0; i < k; i++){
    c =( c * ( (n-i) % p ) % p ) * modinv(i+1,p) % p;
  }
  return c;
}

int main(){
  intl n,a,b;
  cin >> n >> a >> b;
  if (n==2){
    cout << 0;
    return 0;
  }
  
  intl ans;
  ans = modpow(2, n, mod);
  ans -= modcomb(n, a, mod);
  ans -= modcomb(n, b, mod);
  ans -= 1;
  while (ans < 0){
    ans += mod;
  }
  cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
void vprint() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
template <class H, class... T> void vprint(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << '\n';
    vprint(std::forward<T>(args)...);
}
template <class T> void vprint(std::vector<T> &v) {
    for (auto &&i : v) {
        std::cout << i << '\n';
    }
}
template <class T> void mprint(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << "";
        }
    }
}

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

    ll a, b, x;
    cin >> a >> b >> x;
    ll ans = b / x - a / x;
    if (a % x == 0)
        ans++;
    print(ans);

    return 0;
}

Measured memory_bytes: 256