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

struct Edge {
    int to;
    int weight;
};
using Graph = vector<vector<Edge>>;

// 0: 白, 1: 黒, -1: 未探索
vector<int> seen;
int rColor[2] = {1, 0};

void DFS(const Graph &G, int v) {
    for (auto next : G[v]) {
        if (seen[next.to] != -1) continue;

        if (next.weight % 2 == 0) {
            seen[next.to] = seen[v];
        }
        else {
            seen[next.to] = rColor[seen[v]];
        }
        DFS(G, next.to);
    }
}

int main() {
    int N; cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; i++) {
        int u, v, w; cin >> u >> v >> w;
        struct Edge u2v;
        u2v.to = v - 1;
        u2v.weight = w;
        G[u - 1].push_back(u2v);
        struct Edge v2u;
        v2u.to = u - 1;
        v2u.weight = w;
        G[v - 1].push_back(v2u);
    }

    seen.assign(N, -1);
    seen[0] = 0;
    DFS(G, 0);

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


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

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

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

    int A[N];
    rep(i, N)
    {
        int k;
        cin >> k;
        A[k - 1] = i + 1;
    }

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

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b==c+d){
    cout << "Balanced" << endl;
  }else	if(a+b>c+d){
    cout << "Left" << endl;
  }else{
    cout << "Right" << endl;
  }


}

Measured memory_bytes: 256
# W H x y r
def inBox?(w, h, x, y, r)

  top_p    = y + r
  bottom_p = y - r
  right_p  = x + r 
  left_p     = x - r

  if ( 0 <=  bottom_p ) && ( top_p <= h ) && ( 0 <= left_p ) && ( right_p <= w )
    return true
  end

  return false
end

w, h, x, y, r = gets.chomp.split.map(&:to_i)

if inBox?(w, h, x, y, r)
  puts "Yes"
else
  puts "No"
end


Measured memory_bytes: 6860
w, h, x, y = gets.split(" ").map(&:to_i)

# 切った上での最大の面積を求める

# 複数方法あるか = 中心かどうかを求める

puts "#{w*h/2.0} #{(x*2==w && y*2==h)? 1 : 0}"


Measured memory_bytes: 1788
k = int(input())
a = list(map(int,input().split()))

#始めの人数がn人だった時終わりの人数
def g(n,a,k):
    for i in range(k):
        n = n - (n%a[i])
    return n

#print(g(8,a,k))

s = 0
t = 2 + k*max(a)
while t-s > 1:
    m = (s+t)//2
    if g(m,a,k)> 2:
        t = m
    else:
        s = m
    
p = 0
q = 2+k*max(a)
while q-p > 1:
    m = (p+q)//2
    if g(m,a,k) >= 2:
        q = m
    else:
        p = m

c = 1
if g(s,a,k) == 2:
    res = s
elif g(t,a,k) == 2:
    res = t
else:
    c = -1

if g(q,a,k) == 2:
    res2 = q
elif g(p,a,k) == 2:
    res2 = p
else:
    c = -1

if c == 1:
    print(res2,res)
else:
    print(-1)

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

#define X first
#define Y second
#define N 100005
#define M 1010
typedef long long ll;
typedef pair<int,int> pii;

const int INF=1<<30;

int n;
int a[N];
ll S,b[N];
ll s[N];

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),S+=a[i];
	if (S%(1ll*n*(n+1)/2)) printf("NO\n");
	else
	{
		bool flag=true;
		S/=1ll*n*(n+1)/2; b[n]=S;
		for (int i=1;i<n;i++)
		{
			if ((S-a[i+1]+a[i])%n) flag=false;
			else b[i]=(S-a[i+1]+a[i])/n;
			b[n]-=b[i];
		}
		for (int i=1;i<=n;i++) if (b[i]<0) flag=false;
		if (!flag) printf("NO\n");
		else
		{
			ll tmp=0;
			for (int i=1;i<=n;i++) tmp+=1ll*i*b[i];
			for (int i=n;i>=1;i--) s[i]=s[i+1]+b[i];
			for (int i=1;i<=n;i++)
			{
				if (1ll*i*S-tmp+1ll*n*s[i]!=a[i]) flag=false;
			}
			if (flag) printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}

Measured memory_bytes: 2176
import sys
readline = sys.stdin.readline

N,X,Y = map(int,readline().split())

G = [[] for i in range(N)]
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)

for i in range(N - 1):
  G[i].append(i + 1)
  G[i + 1].append(i)
  
ans = [0 for i in range(N)]

from collections import deque
for st in range(N):
  q = deque([[st,0,-1]])
  visited = set()
  while q:
    v,dist,parent = q.popleft()
    if v in visited:
      continue
    visited.add(v)
    ans[dist] += 1
    for child in G[v]:
      if child == parent:
        continue
      q.append([child, dist + 1, v])
    
for i in range(1, N):
  print(ans[i] // 2)

Measured memory_bytes: 72668
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main()
{
	int R[MAX], n;
	
	cin >> n;
	for ( int i = 0; i < n; ++i) { cin >> R[i]; }

	int maxv = -2000000000;
	int minv = R[0];

	for ( int i = 1; i < n; ++i)
	{
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}

	cout << maxv << endl;

	return 0;
}

Measured memory_bytes: 3868
#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int a, b, c;
    int a1, a2, a3;
    
    scanf("%d %d %d", &a, &b, &c);
    
    if (a <= b && a <= c){
        a1 = a;
        if (b <= c) {
            a2 = b;
            a3 = c;
        }else{
            a2 = c;
            a3 = b;
        }
    }else if(b <= a && b <= c){
        a1 = b;
        if(a <= c){
            a2 = a;
            a3 = c;
        }else{
            a2 = c;
            a3 = a;
        }
    }else if(c <= b && c <= a){
        a1 = c;
        if (a <= b) {
            a2 = a;
            a3 = b;
        }else{
            a2 = b;
            a3 = a;
        }
    }
    
    printf("%d %d %d\n", a1, a2, a3);
    
    return 0;
}

Measured memory_bytes: 596
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring>
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;

#define ll long long
#define INF 1e8
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int> 
#define N (1<<7)

const int maxn=45;
int n,ma,mb,ans=INF;
int a[maxn],b[maxn],c[maxn];
int dp[405][405];

int main()
{
	scanf("%d%d%d",&n,&ma,&mb);
	REP(i,n)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	rep(i,405)rep(j,405)dp[i][j]=INF;
	dp[0][0]=0;
	for(int p=1;p<=n;p++)
	for(int i=10*n;i>=a[p];i--)for(int j=10*n;j>=b[p];j--)
	{
		dp[i][j]=min(dp[i-a[p]][j-b[p]]+c[p],dp[i][j]);
	}
	for(int cnt=1;cnt<min(400/ma,400/mb);cnt++)
	ans=min(ans,dp[cnt*ma][cnt*mb]);
	if(ans==INF)printf("-1");
	else printf("%d",ans);
	return 0;
}
/*
40 2 3
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
10 10 100
*/

Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long

#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define endl '\n'
#define fi first
#define se second

using namespace __gnu_pbds;
using namespace std;
const int mod = 1e9 + 7;
// const int mod=998244353;
//const int mod=1e9+9;
//const int INF=4e18+10;
const int INF = 4e18 + 10;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define read(n) \
int n;      \
cin >> n;
#define readv(x, n)   \
vector<int> x(n); \
for (auto &i : x) \
    cin >> i;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

template <typename T1, typename T2>
void set_min(T1 &a, T2 b)
{
    a = min(a, (T1)b);
}

int multiply(int a, int b, int in_mod) { return (a * b) % in_mod; }
int mult_identity(int a) { return 1; }


auto power(auto a, int b, int in_mod)
{
    auto prod = mult_identity(a);
    auto mult = a % in_mod;
    while (b != 0)
    {
        if (b % 2)
        {
            prod = multiply(prod, mult, in_mod);
        }
        mult = multiply(mult, mult, in_mod);
        b /= 2;
    }
    return prod;
}
int mod_inv(int q, int in_mod)
{

    return power(q, in_mod - 2, in_mod);
}
void solve()
{

    int n ,k;
    cin>>n>>k;
    if(k==0)
    {
        cout<<n*n<<endl;
        return;
    }
    int ans = 0;
    for(int b= k+1;b<=n;b++)
    {
        int off = n - (k) + 1;
        ans += (off)/(b) *(b-k);
        ans += min(b-k, off %(b));
    }

    cout<<ans<<endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);
#ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen("INPUT.txt", "r", stdin);
        freopen("OUTPUT.txt", "w", stdout);
    }
#endif
    auto clk = clock();
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // -------------------------------------Code starts here---------------------------------------------------------------------

    int t = 1;
    // cin >> t;

    for (int test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<":\n";
        //cout<<"Trip #"<<test<<": ";
        // cout<<endl;
        solve();
        // solveB();

        // cout<<endl;
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;
    // cerr << fixed << setprecision(6) << "Time: " << ((long double)clk) / CLOCKS_PER_SEC << "\n";
    return 0;
}


Measured memory_bytes: 3612
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
A = list(map(int, input().split()))

from collections import defaultdict
# d = defaultdict(int)
d = defaultdict(list)
# d = defaultdict(set)
# d = {}


B = [0] * (N+1)
B[0] = 0 
# B[1] = A[0]
for i in range(0,N):
    B[i+1] = A[i]
    B[i+1] += B[i]

# print(B)


for i in range(0,N+1):
    d[ B[i] % M] += [i]
    # d[ B[i] % M] |= set([i])
# print(d)
# exit(0)

from bisect import bisect_left

ans = 0
for i in range(0,N+1):
    m = B[i] % M 
    # print(d[m])
    ans += bisect_left( d[m], i)
    # print("{i:3d}: d[{m}]: {d}  bisect({i}): {bi}".format(m=m, d=d[m], i=i, bi=bisect_left(d[m], i)))

    
    
# for i in range(N-1, -1, -1):

print(ans)
    
    


Measured memory_bytes: 62864
#include<stdio.h>
int main()
{
  int a,b[100],i,j,n=0,m;
  scanf("%d",&a);
  for(i=0;i<a;i++){
    scanf("%d",&b[i]);
  }
  for(i=0;i<a-1;i++){
    for(j=a-1;j>i;j--){
      if(b[j]<b[j-1]){
	m=b[j];
	b[j]=b[j-1];
	b[j-1]=m;
	n++;
      }
    }
  }
  for(i=0;i<a-1;i++){
    printf("%d ",b[i]);
  }
  printf("%d\n",b[i]);
  printf("%d\n",n);
  return 0;
}

Measured memory_bytes: 600
N = int(input())

result = []

for i in range(N):
    result.append(input())

count = [0,0,0,0]

for s in result:
    if s == "AC":
        count[0] += 1
    if s == "WA":
        count[1] += 1
    if s == "TLE":
        count[2] += 1
    if s == "RE":
        count[3] += 1

print("AC x {}".format(count[0]))
print("WA x {}".format(count[1]))
print("TLE x {}".format(count[2]))
print("RE x {}".format(count[3]))



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

#define pb push_back
#define mp make_pair
#define size(n) ( int( n.size() ) )
#define sqr(n) ( (n) * (n) )
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 310;
int a[N][N], have[N], ans = N, curr[N], cnt[N];

int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n, m;
    scanf("%d %d",&n,&m);
    for ( int i = 1; i <= n; i++ ){
        for ( int j = 1; j <= m; j++ ){
            scanf("%d",&a[i][j]);
            have[j] = 1;
        }
        curr[i] = 1;
        cnt[ a[i][1] ]++;
    }
    have[0] = 1;
    for ( int i = 1; i <= m; i++ ){
        int cur = 0, p = 0;
        for ( int j = 1; j <= m; j++ ){
            if ( cur < cnt[j] ){
                p = j;
                cur = max( cur, cnt[j] );
            }
        }
        ans = min( ans, cur );
        have[p] = 0;
        for ( int j = 1; j <= n; j++ ){
            if ( a[j][ curr[j] ] == p ){
                cnt[p]--;

                while ( !have[ a[j][ curr[j] ] ] ){
                    curr[j]++;
                }
                cnt[ a[j][curr[j]] ]++;
            }
        }
    }
    printf("%d",ans);

    return 0;
}


Measured memory_bytes: 640
from collections import defaultdict

N, A = map(int, input().split())
x = [int(x) for x in input().split()]

for i in range(N):
    x[i] -= A
X = max(max(x), A)

dp = [defaultdict(int) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(-N * X, N * X + 1):
        dp[i + 1][j] = dp[i][j] + dp[i][j - x[i]]
print(dp[N][0] - 1)


Measured memory_bytes: 21248
import sys
import math
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
a = intl()
cnt1 = 0
cnt2 = 0
for i in range(n):
    if a[i]%2 == 0:
        cnt1 += 1
        if a[i]%3 == 0 or a[i]%5 == 0:
            cnt2 += 1
print("APPROVED" if cnt1 == cnt2 else "DENIED")

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

int main(){
  int n, k, s;

  while(cin >> n >> k >> s){
    if(n == 0) break;

    int ans = 0;

    for(int i = 1; i < (1 << n); i++){
      if(__builtin_popcount(i) != k) continue;

      int sum = 0;

      for(int j = 0; j < n; j++){
        if(!(i & (1 << j))) continue;
        sum += j + 1;
      }

      if(sum == s){
        ans++;
      }
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 1164
#!/usr/bin/env python3

def judge(k):
    c = 0
    _k = round(k**(1/2))
    for i in range(_k-1):
        if k % (i+1) == 0:
            c += 2
    if k % _k == 0:
        c += 1
    return c == 8 and k % 2

def solve(n):
    c = 0
    for i in range(n):
        if judge(i+1):
            c += 1
    return c


def main():
    N = int(input())
    print(solve(N))


if __name__ == '__main__':
    main()

Measured memory_bytes: 9340
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Measured memory_bytes: 76180
#include <bits/stdc++.h>
using namespace std;\
typedef long long ll;
typedef pair<ll,ll> P;
int main() {
  int n,m,a,b; cin>>n>>m;
  ll s=0;
  vector<P> v; for(int i=0;i<n;i++) cin>>a>>b,v.push_back(P(a,b));
  sort(v.begin(),v.end());
  for(P p:v){
    if(m>p.second) m-=p.second,s+=p.first*p.second;
    else{
      s+=p.first*m;
      break;
    }
  }
  cout<<s;
}

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

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

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

  queue<P> Q, R;
  vector<vector<int>> dist(h, vector<int>(w, -1));
  if (s[0][0] == '.') {
    Q.push(make_pair(0, 0));
    dist[0][0] = 0;
  }
  else {
    R.push(make_pair(0, 0));
    dist[0][0] = 1;
  }
  int d = 0;
  
  while (dist[h-1][w-1] == -1) {
    char path;
    if (d % 2 == 0) path = '.';
    else path = '#';
    while (Q.size()) {
      P p = Q.front();
      Q.pop();
      int x = p.first;
      int y = p.second;
      rep(i, 2) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= h || ny >= w) continue;
        if (dist[nx][ny] != -1) continue;
        if (s[nx][ny] != path) {
          R.push(make_pair(nx, ny));
          dist[nx][ny] = d + 1;
          continue;
        }
        Q.push(make_pair(nx, ny));
        dist[nx][ny] = d;
      }
    }
    ++d;
    while (R.size()) {
      P p = R.front();
      R.pop();
      Q.push(p);
    }
  }

  int ans = (dist[h-1][w-1] + 1) / 2;

  cout << ans << endl;

  return 0;
}

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

using namespace std;

int main() {

	int n, k;
	cin >> n >> k;

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

	sort(p.begin(), p.end());

	int res = 0;
	for (int i = 0; i < k; i++) {
		res += p[i];
	}

	cout << res << endl;

	return 0;

}

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

long long MOD = 1e9+7;
int MAX_INT = 1e9;

long long H, W;
vector<vector<long long>> cost_map(1000+1, vector<long long>(1000+1, 0));

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

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

  string S, T;
  cin >> S >> T;

  int min_num = INT_MAX;
  for(int i = 0; i <= S.size() - T.size(); ++i) {
    int count = 0;
    for(int j = 0; j < T.size(); ++j) {
      if(S[i+j] != T[j]) count++;
    }
    min_num = min(min_num, count);
  }

  cout << min_num << endl;

  return 0;
}


Measured memory_bytes: 11520
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
typedef long long unsigned int ll;
typedef pair<int, int> P;

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

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

#define rep(i,n) for(auto i=0; i<(n); i++)
#define isValidPoint(x, y, mx, my) x >= 0 && x  < mx && y >= 0 && y < my

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

const int MOD = 1000000007;

struct Pony
{
    long a, b;
 
    Pony(long a_, long b_)
    {
        a = a_;
        b = b_;
    }
 
    bool operator<(const Pony &another) const
    {
        return b < another.b;
    };
};

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

  long n;
  cin >> n;

  vector<Pony> p;

  for (int i = 0; i < (n); i++) {
    long a, b;
    scanf("%ld %ld", &a, &b);
    p.push_back(Pony(a, b));
  }

  sortv(p);

  long t = 0;
  long isok = true;
  rep(i, p.size()) {
    t += p[i].a;
    if (t > p[i].b) isok = false;
  }

  cout << (isok ? "Yes" : "No") << endl;
}


Measured memory_bytes: 6256
#include<stdio.h>
#include<math.h>
#define ll long long

ll dp[100010][3];

ll max(ll a, ll b)
{
        return (a>b)?a:b;
}

int main()
{
        ll n, i, j;
        scanf("%lld", &n);
        ll a[n+1][3];
        for(i = 1; i <= n; i++)
        {
                for(j = 0; j < 3; j++)
                {
                        scanf("%lld", &a[i][j]);
                }
        }

        dp[1][0] = a[1][0];
        dp[1][1] = a[1][1];
        dp[1][2] = a[1][2];

        for(i = 2; i <= n; i++)
        {
                for(j = 0; j < 3; j++)
                {
                        dp[i][j] = max(dp[i-1][(j+2)%3] + a[i][j], dp[i-1][(j+1)%3] + a[i][j]);
                }
        }

        printf("%lld\n", max(dp[n][0], max(dp[n][1], dp[n][2])));

        return 0;
}


Measured memory_bytes: 4864
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <bitset>
#include <cassert>

using namespace std;

const int SIZE = 1 << 17;

int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0,sign = 1;
    char ch = Advance();
    while (!isdigit(ch) && ch != '-')
        ch = Advance();
    if (ch == '-') {
        ch = Advance();
        sign = -1;
    }
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer * sign;
}

char ReadCh() {
    char ch = Advance();
    while (!isalpha(ch))
        ch = Advance();
    return ch;
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    if (m == 1 && n == 1) {
        printf("1\n");
        return 0;
    }
    if (n == 1) {
        printf("%d\n", m - 2);
        return 0;
    }
    if (m == 1) {
        printf("%d\n", n - 2);
        return 0;
    }
    printf("%lld\n", 1LL * (n - 2) * (m - 2));
    return 0;
}


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

int n,S,x[100007];
typedef long long ll;
ll p[100007],ans = 0ll;

int abs(int x) { return x > 0 ? x : -x; }

int solve(int l,int r)
{
	if(S < x[l]) { ans += x[r] - S; return x[r]; }
	if(S > x[r]) { ans += S - x[l]; return x[l]; }
	if(p[l] >= p[r]) { p[l] += p[r], ans += x[r] - solve(l,r - 1); return x[r]; }
	else { p[r] += p[l], ans += solve(l + 1,r) - x[l]; return x[l]; }
}

int main()
{
	scanf("%d%d",&n,&S);
	for(int i = 1;i <= n; ++ i)
		scanf("%d%lld",x + i,p + i);
	solve(1,n), printf("%lld\n",ans);
	
	return 0;
}

Measured memory_bytes: 6684
/* Author: Rennan Rocha
 * Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$
**/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll, ll>
#define vpi vector<pi>
#define vpll vector<pll>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//*find_by_order(); order_of_key();

int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    map<string, int> freq;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        freq[s]++;
    }

    vector<pair<int, string>> v;
    for(pair<string, int> s : freq) {
        v.PB(MP(s.S, s.F));
    }
    sort(v.rbegin(), v.rend());
    vector<string> ans;
    for(int i = 0; i < v.size(); i++) {
        if(i == 0) ans.PB(v[i].S);
        else {
            if(v[i].F == v[i-1].F) ans.PB(v[i].S);
            else break;
        }
    }
    sort(ans.begin(), ans.end());
    for(string s : ans) {
        cout << s << "\n";
    }
}


Measured memory_bytes: 31596
def main():
    n = int(input())
    ps = list(map(int, input().split()))
    sorted_ps = sorted(ps)

    cnt = 0
    for p, sp in zip(list(ps), sorted_ps):
        if p != sp:
            cnt += 1
            if cnt >= 3:
                print('NO')
                return
    print('YES')


main()


Measured memory_bytes: 3060
import std.stdio, std.string, std.conv;
void main()
{
  while(1){
    auto n = readln.chomp.to!int;
    int cnt;
    if(n==0) break;
    while(n!=1){
      if(n%2==0)
	n/=2;
      else
	n = n*3+1;
      cnt++;
    }
    cnt.writeln;
  }
}

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

int main() {
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	ll ans=min(a,k);
	k=k-min(a,k);
	k=k-min(k,b);
	ans=ans-min(c,k);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 1e5+5;

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

    int n,k;
    cin>>n>>k;
    cout<<n-k+1;
    
    return 0;
}

Measured memory_bytes: 256
/*
 * Counting Characters.c
 *
 *  Created on: 2015/02/13
 *
 */

#include <stdio.h>

int main(void){
    char ch;
    int alpha[26]={0},i;
    while(scanf("%c",&ch)!=EOF){
        if('A'<=ch && ch<= 'Z'){
            alpha[ch-'A']++;
        }
        else if('a'<=ch && ch<= 'z'){
            alpha[ch-'a']++;
        }
    }
    for(i=0;i<26;i++){
        printf("%c : %d\n",'a'+i,alpha[i]);
    }
    return 0;
}

Measured memory_bytes: 540
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	string s; cin >> s;
	vector<string>v = { "maerd", "remaerd" ,"esare", "resare" };
	reverse(s.begin(), s.end());

	for (int i = 0; i < s.size(); i++) {
		bool no = true;
		for (int j = 0; j < v.size(); j++) {
			if (i + v[j].size() - 1 < s.size() && s.substr(i, v[j].size()) == v[j])i += v[j].size() - 1, no = false;
		}
		if (no) { cout << "NO" << endl; return 0; }
	}
	cout << "YES" << endl;

	return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_M = 100;
const int MAX_N = 100;

const int INF = 1 << 29;

int M, N;
int X1[MAX_M], Y1[MAX_M];
int X2[MAX_N], Z2[MAX_N];

double width(int *X, int *Y, int n, double x)
{
  double lb = INF, ub = -INF;

  for (int i = 0; i < n; i++) {
    double x1 = X[i];
    double y1 = Y[i];
    double x2 = X[(i + 1) % n];
    double y2 = Y[(i + 1) % n];

    if ((x1 - x) * (x2 - x) <= 0 && x1 != x2) {
      double y = y1 + (y2 - y1) * (x - x1) / (x2 - x1);

      lb = min(lb, y);
      ub = max(ub, y);
    }
  }
  return max(0.0, ub - lb);
}

void solve()
{
  int min1 = *min_element(X1, X1 + M), max1 = *max_element(X1, X1 + M);
  int min2 = *min_element(X2, X2 + N), max2 = *max_element(X2, X2 + N);
  vector<int> xs;

  for (int i = 0; i < M; i++) xs.push_back(X1[i]);
  for (int i = 0; i < N; i++) xs.push_back(X2[i]);
  sort(xs.begin(), xs.end());

  double res = 0;
  for (int i = 0; i + 1 < (int)xs.size(); i++) {
    double a = xs[i];
    double b = xs[i + 1];
    double c = (a + b) / 2;

    if (min1 <= c && c <= max1 && min2 <= c && c <= max2) {
      double fa = width(X1, Y1, M, a) * width(X2, Z2, N, a);
      double fb = width(X1, Y1, M, b) * width(X2, Z2, N, b);
      double fc = width(X1, Y1, M, c) * width(X2, Z2, N, c);

      res += (b - a) * (fa + 4 * fc + fb) / 6;
    }
  }

  printf("%.10f\n", res);
}

int main()
{
  while (true) {
    scanf("%d%d", &M, &N);
    if (M == 0 && N == 0) break;

    for (int i = 0; i < M; i++) scanf("%d%d", X1 + i, Y1 + i);
    for (int i = 0; i < N; i++) scanf("%d%d", X2 + i, Z2 + i);

    solve();
  }
  return 0;
}



Measured memory_bytes: 2660
# solution

data= int(input())

array = format(data,"b")

mod = 1000000007

dynamic = [[0 for j in range(3)] for i in range(len(array)+1)]
dynamic[0][0] = 1

for i in range(len(array)):
  for j in range(3):
      for x in range(2):
        for y in range(x,2):
          b=(data>>i)&1
          dynamic[i+1][(x+y+j-b+1)//2] = (dynamic[i+1][(x+y+j-b+1)//2]+dynamic[i][j])%mod
print(dynamic[len(array)][0])

Measured memory_bytes: 3064
List = []
for i in range (3):
  List.append(int(input()))
X=int(input())
res = 0
c = 0
for i in range(List[0]+1):
  for j in range(List[1]+1):
    c = int(X/50) - 10 * i - 2 * j
    if 0<= c <= List[2]:
      res+=1
print(res)

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

int main() {
  string s,t;
  cin >> s >> t;
  for(int i=0;i<s.size();i++){
    if(s.at(i)==t.at(i)){
      if(i==s.size()-1){cout << "Yes" << endl;}
      continue;}
    else{cout << "No" << endl;
        break;}
  }
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int, int> P;
int main()
{
  int n;
  while(cin>>n,n) {
    stack<P> st; // i, color
    int bf = -1;
    FOR(i,1,n+1) {
      int in; scanf("%d", &in);
      if(bf != in) {
        if(i % 2 == 0) {
          st.pop();
          if(st.empty()) st.push(P(1, in));
        } else {
          st.push(P(i, in));
        }
      }
      bf = in;
    }
    P p1 = P(n+1, -1), p2; // p2 . . . p1
    int ans = 0;
    while(!st.empty()) {
      p2 = st.top(); st.pop();
      if(p2.second == 0) {
        ans += p1.first - p2.first;
      }
      p1 = p2;
    }
    cout << ans << '\n';
  }
  return 0;
}

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

int fact(int x){
    if(x==0) return 1;
    int a=1;
    for(int i=1; i<=x; i++) a *= i;
    return a;
}
int main(){
    int n;
    cin >> n;
    vector<int> p(n),q(n);
    rp(i,n) cin >> p.at(i);
    rp(i,n) cin >> q.at(i);
    int pdic=0,qdic=0;
    rp(i,n){
        if(i==0) {
            pdic += (p.at(i)-1)*fact(n-1); 
            qdic += (q.at(i)-1)*fact(n-1);
            continue;
        }
        int pctr=0,qctr=0;
        for(int j=0; j<i;j++){
            if(p.at(j)<p.at(i)) pctr++;
            if(q.at(j)<q.at(i)) qctr++;
        }
        pdic += (p.at(i)-pctr-1)*fact(n-i-1);
        qdic += (q.at(i)-qctr-1)*fact(n-i-1);
    }
    if(pdic<qdic) cout << qdic-pdic << endl;
    else cout << pdic-qdic << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))


//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[500010];//適宜変える(ecnt)
	int id[500010];//適宜変える(vcnt)
}G;
G g;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
//int csort(const void*a,const void*b){ll p=(*(E*)a).c,q=(*(E*)b).c;return p<q?-1:p>q?1:0;}
//void makeinvedge();
void readgraph(){
	//適宜変える
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,m){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		g.e[i].s=x;
		g.e[i].g=y;
	}
	g.vcnt=n;
	g.ecnt=m;
	qsort(g.e,g.ecnt,sizeof(E),esort);

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵
}


//強連結成分分解O(V)
//*
#define VCNT 500010
int SCC[VCNT],SCCcnt;//SCC[i]=頂点iが属する強連結成分の番号
int SCCi[VCNT],SCCidx[VCNT];//SCCi[SCCidx[i]:SCCidx[i+1]]=強連結成分iに属する頂点の番号
int adv[VCNT],back[VCNT];
int sccs[VCNT],sccscnt;
int isin[VCNT],scct;
#undef VCNT
void sccdfs(int v){
	adv[v]=back[v]=++scct;
	sccs[sccscnt++]=v;
	isin[v]=1;
	rep(i,g.id[v],g.id[v+1]){
		int u=g.e[i].g;
		if(isin[u]!=2){
			if(isin[u]==0)sccdfs(u);
			back[v]=min(back[v],back[u]);
		}
	}
	if(back[v]==adv[v]){
		int u;
		do{
			u=sccs[--sccscnt];
			isin[u]=2;
			SCC[u]=SCCcnt;
		}while(u!=v);
		SCCcnt++;
	}
}
int sccc(const void*p,const void*q){
	if(SCC[*(int*)p]<SCC[*(int*)q])return -1;
	if(SCC[*(int*)p]>SCC[*(int*)q])return 1;
	if(*(int*)p<*(int*)q)return -1;
	return 1;
}
void scc(){
	SCCcnt=0;
	rep(i,0,g.vcnt)isin[i]=adv[i]=0;
	rep(i,0,g.vcnt)if(!adv[i])sccdfs(i);
	rep(i,0,g.vcnt)SCCi[i]=i;
	qsort(SCCi,g.vcnt,sizeof(int),sccc);

	SCCidx[0]=0;
	SCCidx[SCCcnt]=g.vcnt;
	rep(i,1,g.vcnt)if(SCC[SCCi[i-1]]!=SCC[SCCi[i]])SCCidx[SCC[SCCi[i]]]=i;
}
//*/

G gg;
//強連結成分のDAGグラフを明示的に作る
//*
void sccgraph(){
	//自己辺は取り除く
	//多重辺はそのまま
	int e=0;
	rep(i,0,g.ecnt){
		if(SCC[g.e[i].s]!=SCC[g.e[i].g]){
			gg.e[e].s=SCC[g.e[i].s];
			gg.e[e].g=SCC[g.e[i].g];
			e++;
		}
	}
	gg.vcnt=SCCcnt;
	gg.ecnt=e;
	qsort(gg.e,gg.ecnt,sizeof(E),esort);

	int p=0;
	rep(i,0,gg.vcnt){
		while(p<gg.ecnt&&gg.e[p].s<i)p++;
		gg.id[i]=p;
	}
	gg.id[gg.vcnt]=gg.ecnt;//番兵
}
//*/

//トポロジカルソートO(E+V)
//*
#define VCNT 500010
int vv[VCNT],vvcnt;//vv[] トポロジカル順の頂点のindex
int ideg[VCNT];
#undef VCNT
void toposo(){
	rep(i,0,gg.ecnt)ideg[gg.e[i].g]++;
	rep(i,0,gg.vcnt)if(ideg[i]==0)vv[vvcnt++]=i;
	rep(i,0,vvcnt){
		int v=vv[i];
		rep(i,gg.id[v],gg.id[v+1]){
			ideg[gg.e[i].g]--;
			if(ideg[gg.e[i].g]==0)vv[vvcnt++]=gg.e[i].g;
		}
	}
}
//*/

int main(){
	readgraph();
	scc();
	sccgraph();
	toposo();
	printf("%d\n",SCCcnt);
	rep(ii,0,SCCcnt){
		int i=vv[ii];
		printf("%d",SCCidx[i+1]-SCCidx[i]);
		rep(j,SCCidx[i],SCCidx[i+1])printf(" %d",SCCi[j]);
		puts("");
	}
}

Measured memory_bytes: 45924
def swap(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
def gcd(x, y):
    if(x < y):
        swap(x, y)
    mod = x % y
    if mod == 0:
        return y
    else:
        return gcd(y, mod)
def lcm(x, y):
    return x * y / gcd(x, y)
while True:
    try:
        (a, b) = map(int ,raw_input().split())
    except EOFError:
        break
    print gcd(a, b), lcm(a, b)

Measured memory_bytes: 4996
alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
C = input(str())
c = int(alphabet.index(C))
ans = int(c + 1)
print(alphabet[ans])

Measured memory_bytes: 3060
class Dice:
  def __init__(self, state):
    self.state = state

  def vertical(self, direction):
    s = self.state
    state = [s[1], s[5], s[0], s[4]]
    if direction < 0:
      s[0], s[1], s[4], s[5] = state
    elif 0 < direction:
      s[0], s[1], s[4], s[5] = reversed(state)
    return self
  
  def lateral(self, direction):
    s = self.state
    state = [s[2], s[5], s[0], s[3]]
    if direction < 0:
      s[0], s[2], s[3], s[5] = state
    elif 0 < direction:
      s[0], s[2], s[3], s[5] = reversed(state)
    return self

  def north(self):
    self.vertical(-1)
    return self

  def south(self):
    self.vertical(1)
    return self
  
  def east(self):
    self.lateral(1)
    return self

  def west(self):
    self.lateral(-1)
    return self

dice = Dice(input().split())

for direction in list(input()):
  if direction == 'N':
    dice.north()
  elif direction == 'S':
    dice.south()
  elif direction == 'W':
    dice.west()
  elif direction == 'E':
    dice.east()

print(dice.state[0])



Measured memory_bytes: 5572
import java.util.Scanner

object Main extends App {

  val sc = new Scanner(System.in)

  val (a, b, c, d) = (sc.nextInt, sc.nextInt, sc.nextInt, sc.nextInt)

  if (math.abs(a - c) <= d) {
    println("Yes")
  } else if (math.abs(a - b) <= d && math.abs(b - c) <= d) {
    println("Yes")
  } else {
    println("No")
  }
}


Measured memory_bytes: 25532
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  vector<long long> ab(N);
  long long ans = 0;
  for(int i = 0;i < N;i++) {
    long long a,b;
    cin >> a >> b;
    ab.at(i) = a+b;
    ans -= b;
  }

  sort(ab.rbegin(),ab.rend());

  for(int i = 0;i < N;i++) {
    if(i%2 == 0) ans += ab.at(i);
  }

  cout << ans << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N];
int num,ans[N];

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	for (int i=n;i;i--) {
		int  tot=0;
		for (int j=i;j<=n;j+=i) tot+=ans[j];
		if (a[i]==0 && tot%2==1 || a[i]==1 && tot%2==0) ans[i]=1,num++;
	}
	cout<<num<<endl;
	for (int i=1;i<=n;i++)
		if (ans[i]) printf("%d ",i);
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int MX = 100 * 1000 + 7;
int cnt[MX];
int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
        cnt[x + 1]++;
        cnt[x + 2]++;
    }
    int res = 0;
    for (int i = 0; i < MX; i++) res = max(res, cnt[i]);
    cout << res << endl;
}



Measured memory_bytes: 640
# -*- coding: utf-8 -*-
# agc037/agc037_a
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    S = i2s()
    len_S = len(S)
    pre_S = S[0]
    i = 1
    cnt = 1
    while i < len_S:
        n = 1
        if S[i:i+n] == pre_S:
            n += 1
        if S[i:i+n] == pre_S:
            cnt -= 1
        pre_S = S[i:i+n]
        i += n
        cnt += 1
    print(cnt)
    return

main()


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long long gcd(long long a,long long b) {
  if(b == 0) return a;
  else return gcd(b,a%b);
}
 
int main() {
  
  int K;
  cin >> K;

  long long ans = 0;
  for(int i = 1;i <= K;i++) {
    for(int j = 1;j <= K;j++) {
      for(int k = 1;k <= K;k++) {
        long long g = gcd(i,j);
        g = gcd(g,k);
        ans += g;
      }
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x;
    cin >> n >> m >> x;
    vector<int>c(12);
    vector<vector<int>>a(12,vector<int>(12));
    for(int i=0;i<n;i++){
        cin >> c[i];
        for(int j=0;j<m;j++) cin >> a[i][j];
    }
        int sum=2000000;
        for (int tmp = 0; tmp < (1 << 12); tmp++) {
            bitset<12> s(tmp);
            for(int j=0;j<m;j++){
                int suma = 0 ,sumc = 0;
                for(int i=0;i<n;i++){
                    if(s.test(i)){
                        suma += a[i][j];
                        sumc += c[i];
                    }
                }
                if(suma < x)break;
                else if(j==(m-1))sum = min(sum ,sumc);
            }
        }
    
    if(sum!=2000000)cout << sum << endl;
    else cout<<"-1"<<endl;

}

Measured memory_bytes: 3636
let n, m = Scanf.scanf " %d %d" @@ fun a b -> a, b
let a_s = Array.init m @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let memo = Array.make (n + 1) @@ -1
let rec f n =
  if memo.(n) <> -1 then memo.(n)
  else if n <= 1 then (memo.(n) <- 1; 1)
  else
    let f1 = f (n - 1) in
    let f2 = f (n - 2) in
    memo.(n) <- (f1 + f2) mod 1_000_000_007; 
    memo.(n)
let _ =
  Array.iter (fun a -> memo.(a) <- 0) a_s;
  f n |> Printf.printf "%d\n"

Measured memory_bytes: 7040
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N, L;
  cin>>N>>L;
  vector<string> S(N);
  for(int i=0;i<N;++i) cin>>S[i];
  sort(S.begin(), S.end());
  string ans;
  for(int i=0;i<N;++i) ans += S[i];
  cout<<ans<<endl;
}



Measured memory_bytes: 3600
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int MAX=11000;
vector<ll> prime;
bool isprime[MAX];
void sieve(){
	for(ll i=3; i<MAX; i+=2){
		isprime[i]=1;
	}
	isprime[2]=1;
	prime.push_back(2);
	for(ll i=3; i<MAX; i++){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=2*i; j<MAX; j+=i){
				isprime[j]=0;
			}
		}
	}
	return;
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b, a%b);
}
void div(vector<ll> &v, ll p){
    while(!v.empty() && v.back()==0) v.pop_back();
    if(v.size()<=p-1) return;
    int n=v.size();
    ll a=v.back();
    v.pop_back();
    v[n-p]=(v[n-p]+a)%p;
    div(v, p);
}
int main()
{
    int n; cin>>n;
    sieve();
    ll a[10001];
    ll g=0;
    for(int i=n; i>=0; i--){
        cin>>a[i];
        g=gcd(abs(a[i]), g);
    }
    for(int i=0; i<=n; i++) a[i]/=g;
    vector<ll> ans;
    for(ll i=2; i*i<=g; i++){
        if(g%i==0){
            while(g%i==0) g/=i;
            ans.push_back(i);
        }
    }
    if(g>1) ans.push_back(g);
    for(int i=0; prime[i]<=n; i++){
        ll p=prime[i];
        if(a[0]%p!=0) continue;
        vector<ll> v;
        for(int i=0; i<=n; i++){
            v.push_back((a[i]%p+p)%p);
        }
        div(v, p);
        if(v.empty()) ans.push_back(p);
    }
  if(ans.empty()){
    cout<<endl; return 0;
  }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    for(auto p:ans) cout<<p<<endl;
    return 0;
}

Measured memory_bytes: 620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define fi firstS
#define mp make_pair

void setIO(string name = "") { 
    ios_base::sync_with_stdio(0); cin.tie(0);
}

int main(){
    setIO(); 
    int n;
    cin >> n;
    if(n >= 30){
        cout << "Yes";
    }else{
        cout << "No";
    }
    return 0;   
}


Measured memory_bytes: 3592
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
#include <numeric>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<int, int> mp;
map<int, int>mm;
#define ll long long
#define ld long double
#define PI 3.14159265358979l

unsigned gcd(unsigned a, unsigned b) {
	if (a < b) gcd(b, a);
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
char tolower(char c) {
	return (c + 0x20);
}
int num(int a,int b) {
	int c = 1;
	while (b > a) {
		a *= 2;
		c*=2;
	}
	return c;
}

int main() {
	string s;
	cin >> s;
	int y = stoi(s.substr(0, 2));
	int m = stoi(s.substr(2, 2));
	bool yy = false;
	bool mm = false;
	if (0<m && m < 13) {
        yy = true;
	}
	if (y < 13 && 0<y) {
		mm = true;
	}
	if (yy&&mm)cout << "AMBIGUOUS" << endl;
	else if (yy)cout << "YYMM" << endl;
	else if (mm)cout << "MMYY" << endl;
	else cout << "NA" << endl;
	cin >> s;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
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 main(){
  string S; cin >> S;
  if(S=="ABC")cout << "ARC" << endl;
  else cout << "ABC" << endl;
  return 0;
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

ll n;

int main(){
	cin.sync_with_stdio(false);
  ll cnt=0;
  cin>>n;
  rep(i,n){
    ll l,r;
    cin>>l>>r;
    cnt+=r-l+1;
  }
  cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
bool is_integer(double x)
{
  return floor(x) == ceil(x);
}
int main()
{
  int x;
  cin >> x;
  if (x == 1)
  {
    cout << "0" << endl;
  }
  else
  {
    cout << "1" << endl;
  }
}


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

int W, H, x, y, r;

int main() {
    cin >> W >> H >> x >> y >> r;
    
    if (   0 <= x - r && 0 <= y - r
        && x + r <= W && y + r <= H ) {
        printf("Yes\n");
    } else printf("No\n");
    
    return 0;
}

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

int main() {
	string s;
	cin >>s;
	if(s[2] == s[3] && s[4] == s[5])
	{
	    cout << "Yes\n";
	}
	else
	{
	    cout << "No\n";
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 20
#define R register
#define INF 0x3f3f3f3f
#define lxl long long
using namespace std;

inline lxl read()
{
	lxl x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

int n;
lxl a[maxn];

inline lxl dp(int l,int r,lxl x,lxl y)
{
	if(l+1==r) return a[l]*x+a[r]*y;
	lxl ans=1e18;
	for(R int i=l+1;i<r;++i)
		ans=min(ans,dp(l,i,x,x+y)+dp(i,r,x+y,y)-1ll*(x+y)*a[i]);
	return ans;
}

int main()
{
	n=read();
	for(R int i=1;i<=n;++i)
		a[i]=read();
	printf("%lld\n",dp(1,n,1,1)/*+a[1]+a[n]*/);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define VMAX 10000

int main(){
  unsigned short *A,*B;
  int i,j,n;
  int C[VMAX+1];
 
  scanf("%d",&n);
  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

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

  for(i=1;i<VMAX;i++){
    C[i] = C[i] + C[i-1];
    //printf("C[%d]:%d\n",i,C[i]);
  }
  
  for(j=n-1;j>=0;j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  for(i=1;i<n+1;i++){
    if(i == n) printf("%d\n",B[i]);
    else printf("%d ",B[i]);
   }
  return 0;
}



Measured memory_bytes: 9592