akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <queue>
using namespace std;

int n, q, p, x, a, b;
vector<int> y;
map<int,vector<int>> ab;
queue<int> qu;

int main(){
	cin >> n >> q;
	for (int i = 0; i < n; ++i) ab.emplace(i, vector<int>());
	for (int i = 0; i < n-1; ++i){
		cin >> a >> b;
		ab[a-1].push_back(b-1);
	}
	y.resize(n);
	fill(y.begin(), y.end(), 0);
	for (int i = 0; i < q; ++i){
		cin >> p >> x;
		y[p-1] += x;
	}
	qu.push(0);
	while (!qu.empty()){
		p = qu.front(); qu.pop();
		for (auto& e: ab[p]){
			y[e] += y[p];
			qu.push(e);
		}
	}
	for (int i = 0; i < n; ++i){
		printf("%d ", y[i]);
	}
}

Measured memory_bytes: 25088
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vl vector
using namespace std;
int main()
{
    ll x,n,i;
    ll a;
    cin>>x>>n;
    ll arr[102]={0};
    for(i=0;i<n;i++)
    {
        cin>>a;
        arr[a]++;
    }
    ll ind1,ind2;
    ll dis1,dis2;
    for(i=x;i<=101;i++)
    {
        if(arr[i]==0)
        {
            dis1=i-x;
            ind1=i;
            break;
        }
    }
    for(i=x;i>=0;i--)
    {
        if(arr[i]==0)
        {
            dis2=x-i;
            ind2=i;
            break;
        }
    }
    if(dis1==dis2) cout<<ind2;
    else if(dis1<dis2) cout<<ind1;
    else cout<<ind2;
    
}

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

vector<int> a;

int main()
{
  int n;
  cin >> n;
  a.resize(n);
  rep(i, n)
    cin >> a[i];
  vector<int> ans(n);
  rep(i, n)
    if (i % 2 == 0)
      ans[0] += a[i];
    else
      ans[0] -= a[i];
  ans[n-1] = 2 * a[n-1] - ans[0];
  for (int i=n-2; i>0; i--)
    ans[i] = 2 * a[i] - ans[i+1];
  rep(i, n)
    printf("%d\n", ans[i]);
  return 0;
}

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

#define int long long

const int INF = (int)1e18;

void WF(vector<vector<int>> &G){
  int n = G.size();
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
        G[j][k] = min(G[j][k], G[j][i] + G[i][k]);
      }
    }
  }
}

signed main(){

  while(true){
    int n, m, s, g1, g2;
    vector<vector<int>> G;
    int ans = INF;

    cin>>n>>m>>s>>g1>>g2;

    if(!n) break;


    s--, g1--, g2--;
    G.resize(n,vector<int>(n, INF));

    for(int i = 0; i < m; i++){
      int a, b, c;

      cin>>a>>b>>c;
      a--, b--;
      
      G[a][b] = c;
    }

    for(int i = 0; i < n; i++){
      G[i][i] = 0;
    }
    WF(G);

    for(int i = 0; i < n; i++){
      ans = min(ans, G[s][i] + G[i][g1] + G[i][g2]);
    }

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



Measured memory_bytes: 3212
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <map>
#include <deque>
#include <vector>
#include <assert.h>
#include <cstdio>
#include <iomanip>
#include <stack>
#include <bitset>
#include <queue>
#include <stdio.h>


using namespace std;



#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define sc second
#define y1 stupid_cmath



ll  n,k,d,x,y,r, cnt, a[1001001], p[1001001], F[1001000];
ll const INF = 100000001;
vector<ll> v1,v2;
string s;

int main(){
    //ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    cin>>s;
    for(int i = 0;i < s.size();i++){
        if(i % 2 == 0)
            cout<<s[i];
    }
    return 0;
}
/*
5
1 3 7 12 32
40
*/


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
typedef long long ll;

int main(){
    int r,d,x2000;
    cin >> r >> d >> x2000;
    int x = x2000;
    rep(i,10){
        x = r*x-d;
        cout << x << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.lang.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();
        char d = b.charAt(0);
        System.out.println("A"+d+"C");
    }
}


Measured memory_bytes: 38412
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N = 1;
	while (N) {
		string S; cin >> S;
		N = (S[0] - '0') * 1000 + (S[1] - '0') * 100 + (S[2] - '0') * 10 + (S[3] - '0');
		if (!N)break;
		VI A(4), B(4);
		A[0] = B[0] = N % 10;
		A[1] = B[1] = (N / 10) % 10;
		A[2] = B[2] = (N / 100) % 10;
		A[3] = B[3] = N / 1000;
		SORT(A);
		rSORT(B);
		if (A == B) {
			cout << "NA" << '\n';
			continue;
		}
		int ans = 0;
		while (N != 6174) {
			ans++;
			int b = B[0] * 1000 + B[1] * 100 + B[2] * 10 + B[3];
			int a = A[0] * 1000 + A[1] * 100 + A[2] * 10 + A[3];
			N = b - a;
			A[0] = B[0] = N % 10;
			A[1] = B[1] = (N / 10) % 10;
			A[2] = B[2] = (N / 100) % 10;
			A[3] = B[3] = N / 1000;
			SORT(A);
			rSORT(B);
		}
		cout << ans << endl;
	}

	return 0;
}




Measured memory_bytes: 3236
import sys
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.insert(A, 0, 0)

flg = [False for _ in range(N + 1)]
town = []
i = 1
cnt = 0
for _ in range(N):
    town.append(i)
    flg[i] = True
    i = A[i]

if len(town) >= K:
    print(town[K])
else:
    s = i
    to_s = town.index(s)
    loop = len(town) - to_s
    print(town[(K - to_s) % loop + to_s])

Measured memory_bytes: 51072
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
int main()
{
    ll n;
    cin >> n;
    if(n<600)
    {
        cout <<"8";
    }
    else if(n<800)
    {
        cout <<"7";
    }
    else if(n<1000)
    {
        cout <<"6";
    }
    else if(n<1200)
    {
        cout <<"5";
    }
    else if(n<1400)
    {
        cout <<"4";
    }
    else if(n<1600)
    {
        cout <<"3";
    }
    else if(n<1800)
    {
        cout <<"2";
    }
    else if(n<2000)
    {
        cout <<"1";
    }
    

}


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

int main(){
  int n;
  cin >> n;
  int a[n-1],b[n] = {0};
  for(int i = 0 ; i < n -1; i++) {
    cin >> a[i];
  }
  for(int i = 0 ; i < n-1 ; i++){
    int temp = a[i];
    b[temp - 1]++;
  }
  for(int i = 0 ; i < n ; i++){
    cout << b[i] << endl;
  }
}
  
  

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

int main (){
    int N,M;
    cin >> N >> M;
    vector<int> vec(N);
    for(int i=0; i<M; i++){
        int a,b;
        cin >> a >> b;
        vec.at(a-1) += 1;
        vec.at(b-1) += 1;
    }
    for(int s=0; s<N;s++){
        cout << vec.at(s) << endl;
    }
    
}

Measured memory_bytes: 3608
N,A,B = map(int,input().split())
H = [int(input()) for _ in range(N)]

d = A-B

def judge(k):
    cnt = 0
    remain = [max(h-k*B,0) for h in H]
    for r in remain:
        cnt += -(-r // d)
    if cnt <= k:
        return True
    else:
        return False

def biserch(ok,ng,judge):
    while abs(ok-ng) > 1:
        mid = (ok+ng) // 2
        if judge(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = biserch(10**9,-1,judge)
print(ans)

Measured memory_bytes: 11036
n,p=map(int,input().split())
s=input()

import sys
if p==2 or p==5:
    count=0
    for i in range(n):
        if int(s[i])%p==0:
            count+=i+1
    print(count)

    sys.exit()
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
inv=modinv(10,p)
pmod=[0]*p
pmod[0]=0
buf=0
count=0
for i in range(n):
    buf*=10
    buf+=int(s[i])
    buf%=p
    idx=buf*pow(inv,i,p)
    idx%=p
    count+=pmod[idx]
    pmod[idx]+=1
#print(pmod)
print(count+pmod[0])

Measured memory_bytes: 41308
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;
typedef pair<long long, long long> pll;
// scanf("%d %d %d %d", &w, &b, &d, &s); %lld
// printf("%d\n", points);
// const double PI = acos(-1);
struct edge {
    int v;
    long long w;
    edge(int _v, long long _w) {
        v = _v;
        w = _w;
    }

    bool operator < (const edge &b) const {
        return w > b.w; //Orden invertido
    }
};

int h, w;
const int MAX = 4e6;
vector<edge> g[MAX]; //Lista de adyacencia
bitset<MAX> vis; //Marca los nodos ya visitados
long long dist[MAX]; //Almacena la distancia a cada nodo
#define INF (1ll<<62)


void dijkstra(int u) {
    priority_queue<edge> pq;
    pq.push({u, 0});
    dist[u] = 0;
    while (pq.size()) {
        u = pq.top().v;
        pq.pop();
        if (!vis[u]) {
            vis[u] = true;
            for (auto nx : g[u]) {
                int v = nx.v;
                if(!vis[v] && dist[v] > dist[u] + nx.w) {
                    dist[v] = dist[u] + nx.w;
                    pq.push({v, dist[v]});
                }
            }
        }
    }
}

void init() {
    for(int i = 0; i < MAX; i++) {
        g[i].clear();
        dist[i] = INF;
        vis[i] = false;
    }
}
int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    int cur;
    pii ini, fin;
    cin >> h >> w >> ini.ft >> ini.sd >> fin.ft >> fin.sd;
    ini.ft--, ini.sd--, fin.ft--, fin.sd--;
    vector<string> v(h);
    init();
    for(int i = 0; i < h; i++)
        cin >> v[i];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(v[i][j] == '#') continue;
            cur = j + i * w;
            if(j + 1 < w && v[i][j + 1] != '#')
                g[cur].pb(edge(cur + 1, 0)), g[cur + 1].pb(edge(cur, 0));
            if(i + 1 < h && v[i + 1][j] != '#')
                g[cur].pb(edge(cur + w, 0)), g[cur + w].pb(edge(cur, 0));
            if(j - 1 >= 0 && v[i][j - 1] != '#')
                g[cur].pb(edge(cur - 1, 0)), g[cur - 1].pb(edge(cur, 0));
            if(i - 1 >= 0 && v[i - 1][j] != '#')
                g[cur].pb(edge(cur - w, 0)), g[cur - w].pb(edge(cur, 0));
            for(int k = max(i - 2,0);  k < min(i + 3, h); k++) {
                for(int l = max(j - 2,0);  l < min(j + 3, w); l++) {
                    int cur2 = k * w + l;
                    if(cur != cur2 && v[k][l] != '#')g[cur].pb(edge(cur2, 1)), g[cur2].pb(edge(cur, 1));
                }
            }
        }
    }
    dijkstra(ini.ft * w + ini.sd);
    cout << (dist[fin.ft * w + fin.sd] == INF ? -1 : dist[fin.ft * w + fin.sd]) << endl;
    return 0;
}


Measured memory_bytes: 433972
#include<stdio.h>

int main(){
	int N, T, A;
	scanf("%d%d%d", &N, &T, &A);
	T *= 1000;
	A *= 1000;
	int H[N];
	int t[N];
	int ans = 0;
	for(int i=0; i<N; i++){
		scanf("%d", &H[i]);
		t[i] = T - H[i]*6;
		if((t[i]>A?t[i]-A:A-t[i]) < (t[ans]>A?t[ans]-A:A-t[ans])){
			ans = i;
		}
	}
	printf("%d", ans+1);
	return 0;
}


Measured memory_bytes: 128
import java.io.*;
import java.util.Scanner;
class Main{
  public static void main(String[] args)throws IOException{
    Scanner scan = new Scanner(System.in);
    int[] list = new int[100];
    while(scan.hasNextInt()){
      list[scan.nextInt()-1]++;
    }
    int max =0;
    for(int i=0;i<list.length;i++){
      max =Math.max(max , list[i]);
    }
    for(int i=0;i<list.length;i++){
      if(max ==list[i]){
        System.out.printf("%d\n",i+1);
    }
  }
  }
}

Measured memory_bytes: 12000
n = int(input())
ab = [0] * 100
for i in range(1, n + 1):
    s = str(i)
    front = s[0]
    back = s[-1]
    ab[int(front + back)] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += ab[i * 10 + j] * ab[j * 10 + i]

print(ans)


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
import bisect

INF = 10 ** 18
N = int(input())
A = [10 ** 10 - int(input()) for _ in range(N)] # 逆順にしておく

# 最長単調減少列：狭義

dp = [INF] * (N+1) # 長さ、その長さの末端としてありうる最大値

for a in A:
    idx = bisect.bisect_right(dp,a)
    dp[idx] = a

answer = bisect.bisect_left(dp, INF)
print(answer)

Measured memory_bytes: 7964
#include<stdio.h>
int main()
{
    int A,B,i,j,k;
    scanf("%d%d", &A, &B);
    i=A+B;
    j=A-B;
    k=A*B;
    if(i>j){
    if(i>k)
    printf("%d\n",i);
    else
    printf("%d\n",k);
    }
    else{
    if(k>j)
    printf("%d\n",k);
    else
    printf("%d\n",j);
    }
    return 0;
}


Measured memory_bytes: 1712
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(list(map(int, input().split())))
#print(a)

cnt = 0
ope=[]
for y in range(H):
    if y != H -1:
        for x in range(W):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y + 1][x] += 1
                cnt += 1
                ope.append([y+1,x+1,y+1+1,x+1])
    else:
        for x in range(W-1):
            if a[y][x] % 2 == 1:
                a[y][x] -= 1
                a[y][x+1] += 1
                cnt += 1
                ope.append([y+1,x+1,y+1,x+1+1])
print(cnt)
for el in ope:
    print(' '.join(list(map(str, el))))





Measured memory_bytes: 65756
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,m;
  cin>>n>>m;
  vector<int> cities(n,0);
  int road;
  for(int i=0;i<2*m;i++){
    cin>>road;
    cities.at(road-1)++;
  }
  for(int i=0;i<n;i++)cout<<cities.at(i)<<"\n";
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))

// #define DEBUG

#ifdef DEBUG
#define dump(...) fprintf(stderr, __VA_ARGS__)
#else
#define dump(...)
#endif

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

using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;

const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};


ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}

random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

using CST = tuple<int, int, int>;

int main(void){
    for(int n, m; cin >> n >> m, n;){
        vector<vi> edge(n);
        vector<CST> cst(m);
        rep(i, m){
            int s, t, c; cin >> s >> t >> c;
            s--, t--;
            edge[s].push_back(t);
            edge[s].push_back(s);
            cst[i] = tie(c, s, t);
        }
        sort(_all(cst));

        UnionFind uf(n);

        int cnt = 0, res;
        for(auto & e : cst){
            int c, s, t; tie(c, s, t) = e;

            if(uf.findSet(s, t)) continue;

            uf.unionSet(s, t);
            cnt++;

            if(cnt == n / 2){
                res = c;
                break;
            }
        }

        cout << res << endl;
    }

    return 0;
}

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

using namespace std;

using int64 = long long;

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

  int n;
  cin >> n;
  vector<string> ss(n);
  for (int i = 0; i < n; i++) cin >> ss[i];

  unordered_map<string, int64> count_map;
  for (const string& s : ss) {
    string ms = s;
    sort(ms.begin(), ms.end());
    count_map[ms]++;
    // if (count_map.find(ms) == count_map.end()) {
    //   count_map[ms] = 1;
    // } else count_map[ms]++;
  }

  int64 ans = 0;
  for (const auto& kv : count_map) {
    int64 v = kv.second;
    ans += v * (v - 1) / 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 16036
#include <iostream>
#include <vector>
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
using namespace std;
using ll = long long;

void Output(const vector<int> &a){
  REP(i,a.size()){
    cout << a[i];
    if(i != a.size()-1) cout << " ";
  }
  cout << endl;
}

int SelectionSort(vector<int> &a, int n){
  int res = 0;
  REP(i,n){
    int minj = i;
    FOR(j,i,n){
      if(a[minj] > a[j]) minj = j;
    }
    if(i != minj){
      swap(a[i], a[minj]);
      ++res;
    }
  }
  return res;
}

int main(){
  int n; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];
  int res = SelectionSort(a,n);
  Output(a);
  cout << res << endl;
  return 0;
}


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

int main(){
    int n;
    cin >> n;
    int a[n+1],b[n+1],sum1=0,ma=0,sum2=0,sum;
    for (int i = 0;i < n;i++) {cin >> a[i];ma+=a[i];}
    for (int i = 0;i < n;i++) cin >> b[i];
    //sum=a[0]+b[n-1];
    ma+=b[n-1];
    //cout << sum << endl;
    for(int i=0;i <=n-1;i++){
        sum1+=a[i];
        for(int j = i;j <= n-1;j++){
                sum2 += b[j];               
            
            }
            sum = sum1+sum2;
            ma = max(ma,sum);
            sum2 = 0;

        
        
    }
    //if(ma > sum ) sum=ma;
    cout << ma << endl;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;

int h,w,sx,sy,gx,gy;
int dist[1050][1050];
string s[1050];
constexpr int dx[4] = {1,0,-1,0};
constexpr int dy[4] = {0,1,0,-1};

int main() {
  cin >>h>>w>>sx>>sy>>gx>>gy;
  sx--; sy--; gx--; gy--;
  rep(i,h) cin >> s[i];

  rep(i,h) rep(j,w) dist[i][j] = -1;
  int d = 0;
  deque<P> q;
  q.push_back({sx,sy});
  q.push_back({INF,INF});

  while (q.size()>=2) 
  {
    int x = q.front().first, y = q.front().second;
    q.pop_front();

    if (x == INF) {
      q.push_back({INF,INF});
      d++;
      continue;
    }

    if(x<0||x>=h||y<0||y>=w||s[x][y]=='#'||dist[x][y]!=-1) continue;
    dist[x][y] = d;
    rep(i,4) {
      q.push_front({x+dx[i],y+dy[i]});
    }
    for (int i = x-2; i <= x+2; i++) {
      for (int j = y-2; j <= y+2; j++) {q.push_back({i,j});}
    }
  }
  
  cout << dist[gx][gy] << endl;
  return 0;
}

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		int strN = 2; //文字列を何行受け取るか
		for(int i = 0; i < strN; i++){
			line += br.readLine() + " ";
		}
		String[] param = line.split(" ");

		InterchangeablyJoin(param);
	}
	
	static void InterchangeablyJoin(String[] param){
		StringBuffer buffer = new StringBuffer();
		
		for(int i = 0; i < param[0].length(); i++){
			buffer.append(param[0].charAt(i));
			if(i > param[1].length()-1) break;
			buffer.append(param[1].charAt(i));
		}
		System.out.println(buffer.toString());
	}

}

Measured memory_bytes: 20820
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <iomanip>
#include <map>
#include <queue>
#include <tuple>
#include <math.h>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef tuple<int,int,int> P;


int main(){
    ll N;
    cin >> N;
    ll ans=N-1;
    for(ll i=2; i<=sqrt(N); i++){
        if(N%i!=0) continue;
        ll tmp=N/i;
        ans=min(ans,tmp+i-2);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const ll Mod = 998244353;
const int MAX = 510000;
const double PI = 3.14159265358979;
const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> xy(N);
  vector<int> v1, v2;
  for (int i=0; i<N; i++) {
    cin >> xy[i].first >> xy[i].second;
    int a = xy[i].first+xy[i].second;
    int b = xy[i].first-xy[i].second;
    v1.push_back(a);
    v2.push_back(b);
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  cout << max(v1[N-1]-v1[0], v2[N-1]-v2[0]) << endl;
  return 0;
}

Measured memory_bytes: 6644
#include<stdio.h>
const int N=10000;
int main()
{
	int a[N]={0}, n, maxn=-1000005, minn=1000005;
	long long sum=0;
	scanf("%d", &n);
	for(int i=0;i<n;i++)
	{
		scanf("%d", &a[i]);
		if(a[i]>maxn)
		{
			maxn=a[i];
		}
		if(a[i]<minn)
		{
			minn=a[i];
		}
		sum+=a[i];
	}
	printf("%d %d %lld\n", minn, maxn, sum);
	return 0;
}


Measured memory_bytes: 2800
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = []
    r = 1
    for inv in mod_invs(max, mod):
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return (
                self._factorials[n]
                * self._finvs[r]
                % self._mod
                * self._finvs[n - r]
                % self._mod
        )


P = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

# A = np.array(A, dtype=int)
# vpow = np.vectorize(lambda a, b: pow(a, b, P))
# mat = []
# for i in range(P):
#     mat.append(vpow(i, np.arange(P)))
# print(np.array(mat).sum(axis=1) % P)
# print(np.array(mat).sum(axis=0) % P)
# mat = np.hstack((mat, [[a] for a in A]))
#
# print(mat)
#


# 解説AC
# f(x) = 1−(x - j)^(P - 1) は、x == j のとき1、それ以外のとき0
# A[j] == 1 である j について上記の式を足し合わせる
comb = Combination(max=P - 1, mod=P)
ncr = [comb.ncr(P - 1, i) for i in range(P)]
B = [0] * P
for j, a in enumerate(A):
    if a == 0:
        continue
    pw = 1  # pow(-j, i, P)
    for i in range(P):
        B[i] -= pw * ncr[i] % P
        B[i] %= P
        pw = (pw * -j) % P
    B[-1] += 1
    B[-1] %= P
print(*B[::-1])


Measured memory_bytes: 44952
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

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

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

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n-1);
    REP(i, n){
        cin >> a[i];
        a[i]--;
    }
    REP(i, n){
        cin >> b[i];
    }
    REP(i, n-1){
        cin >> c[i];
    }
    int ans = 0;
    int prev = -100;
    REP(i, n){
        ans += b[a[i]];
        if(a[i] - prev == 1){
            ans += c[prev];
        }
        prev = a[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import math
import statistics
import heapq

A, B, C = map(int, input().split())
K = int(input())

for a in range(K + 1):
    for b in range(K + 1 - a):
        for c in range(K + 1 - a - b):
            Ad = A * (2 ** a)
            Bd = B * (2 ** b)
            Cd = C * (2 ** c)
            # print("{} {} {}".format(a, b, c))
            # print("{} {} {}".format(Ad, Bd, Cd))

            if Ad < Bd < Cd:
                print("Yes")
                sys.exit()

print("No")





Measured memory_bytes: 72868
def resolve():
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    dp = [[0] * (W + 1)]
    for i in range(N):
        d = []
        for w in range(W + 1):
            if w >= weight[i]:
                d.append(max(dp[-1][w - weight[i]] + value[i], dp[-1][w]))
            else:
                d.append(dp[-1][w])
        dp.append(d)
    print(dp[-1][-1])


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 172364
import sys

def check_alloc(weights, k, cpct):
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > k or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = map(int, input().split())
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	w = int(input())
	weights[i] = w
	sum += w
	maxi = max(maxi, w)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
cpct = 0
while start <= end:
	cpct = int(start + (end - start) / 2)
	check = check_alloc(weights, k, cpct)
	if check == False:
		start = cpct + 1
	else:
		if start == end: break
		end = cpct
	
print(cpct)



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

#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define ll long long

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

	vector<int> a(n + 1);
	vector<int> b(n);

	rep(i,n + 1){
		cin >> a[i];
	}
	rep(i,n){
		cin >> b[i];
	}

	ll sum = 0;
	rep(i, n){
		int k = min(a[i], b[i]);
		sum += k;
		a[i] -= k;
		b[i] -= k;
		int l = min(a[i + 1], b[i]);
		sum += l;
		a[i + 1] -= l;
	}		

	cout << sum << endl;

    return 0;
}



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

int main()
{
	int n;
	cin>>n;
	int t=n;
	int ans=0;
	while(t)
	{

		ans+=t%10;
		t/=10;
	}
	if(n%ans==0)
	{
		puts("Yes");
	}
	else
	{
		puts("No");
	}


	return 0;
}


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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i, )
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

if x == 1:
    print(1)
else:
    ans = []
    ok = 0
    for i in range(x, 1, -1):    
        tmp = make_divisors(i)
        for j in tmp[:-1]:
            for k in range(1,10):
                if j**k == tmp[-1]:
                    ok = 1
                    break
        
        if ok == 1:
            break

    print(i)

Measured memory_bytes: 39024
#include <bits/stdc++.h>
using namespace std;
int mn=INT_MAX;
 
int f(int a[],int n,int i,int c,int k){
    
    int cst[n];
    cst[0]=0;
    cst[1]=abs(a[1]-a[0]);
    
    for(int i=2;i<n;i++){
    
        int m=INT_MAX;    
        for(int j=1;j<=k;j++){
            
        if((i-j)<0)break;    
        int u=abs(a[i]-a[i-j])+cst[i-j];
        m=min(u,m);
        }
        cst[i]=m;
        
    }

    
    return cst[n-1];
}
 
int main() {
	   int n,k;cin>>n>>k;
	   int a[n],i;
	   for(int i=0;i<n;i++)cin>>a[i];
	   
	   mn=f(a,n,0,0,k); 
	cout<<mn<<endl;
	return 0;
}

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

#define ll long long

int main() {
    int n;
    scanf("%d", &n);

    pair<ll, ll> t[n];
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &t[i].second, &t[i].first);
    }

    sort(t, t + n);

    ll sum = 0;
    string ans = "Yes";
    for (int i = 0; i < n; i++) {
        sum += t[i].second;
        if (sum > t[i].first) {
            ans = "No";
            break;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 6820
#!/usr/bin/ruby
# -*- coding: utf-8 -*-

loop do
  n, k = gets.split(/ /).map(&:to_i)
  n > 0 or break
  cards = k.times.map{gets.to_i}.sort
  has_empty = false
  if cards[0] == 0 then
    cards.shift
    has_empty = true
    j = 2
  end
  last = -2
  cnt1 = has_empty ? 1 : 0
  cnt2 = 0
  maxcnt = 0
  cards.each do|c|
    if last+1 == c then
      cnt1 += 1
      cnt2 += 1
    elsif has_empty && last+2 == c then
      cnt1 = cnt2+2
      cnt2 = 1
    else
      cnt1 = 1
      cnt2 = 1
    end
    if cnt1 > maxcnt then
      maxcnt = cnt1
    end
    last = c
  end
  puts maxcnt
end

Measured memory_bytes: 7496
x,n=map(int,input().split())
if n==0:
  print(x)
  exit()
A=set(map(int,input().split()))
for i in range(100):
  if x+i not in A:
    a=x+i
    break
for i in range(100):
  if x-i not in A:
    b=x-i
    break

if abs(a-x)==abs(x-b):
  print(b)
elif abs(a-x)>abs(x-b):
  print(b)
else:
  print(a)

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

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

    if (n < 10){
        cout << "Yes" << endl;
        return 0;
    }
    for (int karen = 2; karen < 10; karen++){
        if(n % karen == 0){
            if(n / karen < 10){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

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

Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0

for i in range(0,a+1):
    for j in range(0,b+1):
        for k in range(0,c+1):
            total = i * 500 + j * 100 + k * 50
            if total == x:
                count += 1

print(count)


Measured memory_bytes: 3060
import numpy as np
import math
import itertools
values = []
n = int(input())
towns = [list(map(int,input().split())) for _ in range(n)]
num_root = math.factorial(n)
for root in itertools.permutations(towns):
  for i in range(n - 1):
    level = (root[i][0] - root[i + 1][0])**2 + (root[i][1] - root[i + 1][1])**2
    values.append(math.sqrt(level))
print(sum(values)/num_root)

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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 <= i; i--)
#define FOR(i, from, to) for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to) for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;

ll gcd(ll a, ll b)
{
    return (a < b) ? gcd(b, a) : ((a % b) ? gcd(b, a % b) : b);
}

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

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

    ll ok = 1;
    ll ng = N;
    while (1 < ng - ok)
    {
        ll n = ok + (ng - ok) / 2;
        ll sum = n * (n + 1) / 2;
        if (sum < N)
        {
            ok = n;
        }
        else
        {
            ng = n;
        }
    }

    ll sum = ng * (ng + 1) / 2;
    ll a = sum - N;
    for (ll i = 1; i < ng + 1; i++)
    {
        if (i != a)
            cout << i << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,m,A[15],B[101];


int mem[101][1<<15],used[101][1<<15],sum[1<<15];

int dfs(int idx,int sta){
  if(idx==m) return 0;
  if(used[idx][sta]++)return mem[idx][sta];
  int &res=mem[idx][sta]=abs(sum[sta]-B[idx])+dfs(idx+1,sta);
  
  for(int i=0;i<n;i++){
    if(!((sta>>i)&1))continue;
    res=min(res,dfs(idx,~((~sta)|(1<<i))));
  }
  return res;
}

int main(){
  while(1){
  cin>>n>>m;
  if(!n&&!m)break;
  for(int i=0;i<n;i++) cin>>A[i];
  for(int i=0;i<m;i++) cin>>B[i];
  sort(A,A+n);
  sort(B,B+m,greater<int>());
  memset(used,0,sizeof(used));
  memset(sum,0,sizeof(sum));

  for(int i=0;i<(1<<n);i++)
    for(int j=0;j<n;j++)if((i>>j)&1)sum[i]+=A[j];
 
  cout<<dfs(0,(1<<n)-1)<<endl;
  }
  return 0;
}

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

int main() {
    int x;
    cin >> x;
    for (int i = 1; ; ++i) {
        if (i * (i + 1) / 2 >= x) {
            cout << i << endl;
            break;
        }
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
using namespace std;

#define REP(i,n) for(int i=0;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    int n;
    cin >> n;
    
    ll lucas[100];
    lucas[0]=2;
    lucas[1]=1;
    for(int i=2; i<=n; ++i) lucas[i] = lucas[i-1]+lucas[i-2];
    
    cout << lucas[n] << ENT;
    return 0;
}

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


Measured memory_bytes: 256
n=int(input())
A=[0]+list(map(int, input().split()))
B=[0]*(n+1)
B[n//2+1:]=A[n//2+1:]
for i in range(n//2, 0, -1):
  B[i]=(sum([B[j] for j in range(2*i, n+1, i)])+A[i])&1
res=[]
for i in range(n+1):
  if B[i]==1:
    res.append(i)
print(len(res))
if res:
  print(*res)
    

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

int main(){
    int k, x;
    cin >> x >> k;
    vector<int> ans;
    for(int i = max(-1000000, k-x+1); i <= min(1000000, k+x-1); i++){
        ans.push_back(i);
    }
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << " \n"[i+1==ans.size()];
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    static Scanner cin = new Scanner();
    static void Main() {
        string S = Console.ReadLine();
        if (S.Length == 2) Console.WriteLine(S);
        else if(S.Length == 3) {
            for (int i = 2; i >= 0; i--) {
                Console.Write(S[i].ToString());
            }
            Console.WriteLine();
        }
        Console.ReadLine();
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]) {
    int n = 0;
    int p = 0;
    cin >> n;
    vector<int> pmin(n, 0);
    cin >> pmin[0];
    int count = 1;
    for (int i = 1; i < n; i++) {
        cin >> p;
        if (pmin[i - 1] >= p) { count++; }
        pmin[i] = min(p, pmin[i-1]);
    }

    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 1024
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict, deque

def bfs(tree, k):
  dq = deque()
  dq.append((-1, 1, 0))
  print(k)
  ans = dict()
  while dq:
    _, s, c = dq.popleft()
    if _ != -1:
      ans[(_, s)] = c
    for i, t in enumerate(tree[s]):
      dq.append((s, t, ((c+i) % (k)+1)))
  return ans

def main():
  n = int(input())
  edges = [tuple(map(int, input().strip().split())) for _ in range(n-1)]
  counts = numpy.zeros(n)
  tree = defaultdict(list)
  for s, t in edges:
    counts[s-1] += 1
    counts[t-1] += 1
    tree[s].append(t)
  k = int(numpy.max(counts))
  ans = bfs(tree, k)
  for edge in edges:
    print(ans[edge])

if __name__=='__main__':
  main()

Measured memory_bytes: 56552
#include <cstdio>
#include <map>

int n;
std::map<int, int> cnt;

void init() {
  scanf("%d", &n);
  for (int i = n; i--;) {
    int x;
    scanf("%d", &x);
    ++cnt[x];
  }
}

bool solve() {
  if (cnt.size() > 2) return false;
  if (cnt.size() == 1) return cnt.begin()->first <= n / 2 || cnt.begin()->first == n - 1;
  int a = cnt.begin()->first, b = cnt.begin()->second, x = cnt.rbegin()->first, y = cnt.rbegin()->second;
  if (b + 2 * (x - b) > n) return false;
  if (a + 1 != x) return false;
  if (2 * (x - b) > y) return false;
  return b + 1 <= x && x <= b + y / 2;
}

int main() {
  init();
  puts(solve() ? "Yes" : "No");
  return 0;
}


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

#define INF (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define N 100005
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795

ll f(ll a)
{
  ll cnt=0,i;
  for(i=1;i*i<a;i++)
  {
if(a%i==0)cnt+=2;
  }
  if(i*i==a)cnt++;
  return cnt;
}

ll powM(ll a,ll b, ll m)
{ 
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
return ans%m;
}


int main()
{
ll k,a,b,flag=0;
cin>>k>>a>>b;
for(int i=a;i<=b;i++)
{
  if(i%k==0)
  {
    flag=1;
    break;
  }
}
if(flag)cout<<"OK"<<"\n";
else cout<<"NG"<<"\n";



  
  return 0;
}





Measured memory_bytes: 3628
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

long N, cnt;

bool ask(long n) {
    writeln("? ", n);
    stdout.flush;
    cnt += 1;
    
    debug {
        string sn = n.to!string;
        string sN = N.to!string;
        return (n <= N && sn <= sN) || (n > N && sn > sN);
    } else {
        return readln.chomp == "Y";
    }
}

void main() {
    debug {N = readln.chomp.to!long;}

    long x = 10;
    for (; x <= 10^^9 && ask(x); x *= 10) {}

    if (x == 10L^^10) { // N = 1, 10, 100, ...
        x = 2;
        for (; x <= 2 * 10L^^9 && !ask(x); x *= 10) {}
        writeln("! ", x / 2);
    } else {
        long hi = x - 1;
        long lo = x / 10;
        while (hi - lo > 1) {
            long mid = (hi + lo) / 2;
            if (ask(mid * 10L^^9)) hi = mid;
            else lo = mid;
        }
        writeln("! ", hi);
    }

    debug {cnt.writeln;}
}


Measured memory_bytes: 1104
#include <stdio.h>
#include <stdlib.h>

#define Max 10000
#define NIL -1

struct node{
  int l;
  int r;
  int p;
};

 struct node T[Max];
 int D[Max],H[Max];

void setDepth(int u, int d){
  if(u== NIL) return;
    D[u]=d;
    setDepth(T[u].l,d+1);
    setDepth(T[u].r,d+1);

}

int setHeight(int u){
  int h1=0,  h2=0;
  if(T[u].l!= NIL) h1=setHeight(T[u].l)+1;
  if(T[u].r!= NIL) h2=setHeight(T[u].r)+1;
  return H[u]=(h1>h2? h1:h2);
}

int getSibling(int u){
  if(T[u].p == NIL) return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL)
  return T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != NIL)
  return T[T[u].p].r;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("sibling = %d, ",getSibling(u));
  int deg=0;
  if(T[u].l!=NIL) deg++;
  if(T[u].r!=NIL) deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].p==NIL) printf("root\n");
  else if(T[u].l == NIL && T[u].r == NIL){
    printf("leaf\n");
  }
  else printf("internal node\n");
  }


int main(){
  int v,l,r,i,n, root=0;
  scanf("%d",&n);

  for(i=0;i<n;i++) T[i].p = NIL;

  for(i=0;i<n;i++){
    scanf("%d%d%d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    if(l != NIL) T[l].p=v;
    if(r != NIL) T[r].p=v;
  }

  for(i=0;i<n;i++) if(T[i].p == NIL) root = i;

  setDepth(root,0);
  setHeight(root);

  for(i=0;i<n;i++) print(i);

  return 0;
}



Measured memory_bytes: 2088
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ll                  long long int
#define ull                 unsigned long long int
#define ld                  long double
#define fi                  first
#define se                  second
#define pb                  push_back
#define pbb                 pop_back
#define mp                  make_pair
#define pii     	        pair<int,int>
#define all(x)              x.begin(), x.end()
#define uniq(x)             x.erase(unique(x.begin(),x.end()),x.end())
#define mem(array, value)   memset(array, value, sizeof(array))
#define lcm(a,b)            (abs(a)/gcd(a,b))*abs(b)
#define PI      	        2*acos(0.0)
#define INF     	        1e9
#define EPS     	        1e-8
#define line                cout << "\n==========\n"
#define fastRead 	        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> orderedSet; 

const int N = 1e5+9;
int n;
int ara[N];
int dp[N];

int main ()
{
    #ifdef Lollipop
    //freopen ("input.txt", "r", stdin);
    //freopen ("output.txt", "w", stdout);
    #endif
    cin >> n;
    for (int i = 0; i<n; i++){
        cin >> ara[i];
    }
    dp[0] = 0;
    dp[1] = abs(ara[0] - ara[1]);
    for (int i = 2; i<n; i++){
        dp[i] = min(dp[i-1] + abs(ara[i] - ara[i-1]), dp[i-2] + abs(ara[i] - ara[i-2]));
    }
    cout << dp[n-1] << endl;
    return 0;
}



Measured memory_bytes: 1024