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

#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed fixed<<setprecision(14)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline lol abs(A &a) { return (a < 0 ? -a : a); }
const lol Mod=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
lol n,m,k,r;
bool ans[110];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  lol a,b;
  cin >>n>>k;
  for(int i=0;i<k;i++){
    int d;
    cin >>d;
    for(int j=0;j<d;j++){
      cin >>a;
      ans[a]=true;
    }
  }
  lol p=0;
  for(int i=1;i<=n;i++) if(!ans[i]) p++;
  cout <<p<<'\n';
  return (0);
}


Measured memory_bytes: 3656
/*mohammadreza motabar*/
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define pb push_back
typedef pair<int,int> pii;
const ll MAX_N = 1e5,INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int a,b,c;cin>>a>>b>>c;
	if(a==b)
		cout<<c;
	else if(a==c)
		cout<<b;
	else
		cout<<a;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>

typedef long long ll;

int A[100000];
int N;

int MOD = 1000000007;


ll pow2(int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        ll x = pow2(n / 2);
        return (x * x) % MOD;
    } else {
        ll x = pow2(n / 2);
        return (2 * x * x) % MOD;        
    }
}

int solve(void) {
    std::sort(A, A + N);
    if (N % 2 == 0) {
        for (int i = 0; i < N / 2; i ++) {
            if (A[2*i] != 2*i+1) return 0;
            if (A[2*i] != 2*i+1) return 0;
        }
    } else {
        if (A[0] != 0) return 0;
        for (int i = 0; i < N / 2; i ++) {
            if (A[2*i+1] != 2*i+2) return 0;
            if (A[2*i+2] != 2*i+2) return 0;
        }
    }
    return pow2(N / 2);
}

int main(void) {
    scanf("%d", &N);
    for (int i = 0; i < N; i ++) scanf("%d", &A[i]);
    printf("%d\n", solve());
    return 0;
}

Measured memory_bytes: 512
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input() for _ in range(H)]

dist = [[float('inf') for _ in range(W)] for _ in range(H)]
dist[Ch][Cw] = 0
que = deque()
que.append((Ch, Cw))

while que:
    i, j = que.popleft()
    d = dist[i][j]
    for ni, nj in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
        if 0 <= ni < H and 0 <= nj < W:
            if S[ni][nj] == '.' and d < dist[ni][nj]:
                dist[ni][nj] = d
                que.appendleft((ni, nj))
    # magic
    nd = d+1
    for a in range(-2, 3):
        for b in range(-2, 3):
            ni, nj = i+a, j+b
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] == '.' and nd < dist[ni][nj]:
                    dist[ni][nj] = nd
                    que.append((ni, nj))

if dist[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(dist[Dh][Dw])


Measured memory_bytes: 101456
#include<cstdio>
int W, H;
const int MAXW = 105;
char field[MAXW][MAXW];
int res = 0;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
void dfs(int x, int y)
{
    char tmp = field[x][y];
    field[x][y] = ' ';
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < H && ny >= 0 && ny < W && field[nx][ny] == tmp){
            dfs(nx, ny);
        }
    }

}
int main()
{
    while(scanf("%d%d", &H, &W) && H){
        res = 0;
        for(int i = 0; i < H; i++)
            scanf("%s", field[i]);
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(field[i][j] != ' '){
                    dfs(i, j);
                    res++;
                }
            }
        }
        printf("%d\n", res);
    }
}



Measured memory_bytes: 3136
// ABC104-C
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
namespace you {
    std::string to_string(char val) {
        return std::string(1, val);
        // return std::string{val};
        // you::to_string(char)
    }
}

vector<int> p(10);
vector<int> c(10);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    ll d,g;
    cin>>d>>g;
    rep(i,d){
        cin>>p[i]>>c[i];

    }
    ll ans=pow(10,5);
    int num=pow(2,d);
    for(int i=0;i<num;i++){
        int cur=0;
        ll score=0;
        for(int j=0;j<d;j++){
            if((i>>j)&1){
                cur+=p[j];
                score+=(j+1)*100*p[j]+c[j];
            }
        }
        if(score<g){
            for(int k=d-1;k>=0;k=k-1){
                //cout<<score<<" "<<i<<" "<<k<<endl;
                if(!((i>>k)&1)){
                        //cout<<score<<endl;
                    if(g<=score+(k+1)*100*(p[k]-1)){
                        int plus=ceil(double(g-score)/((k+1)*100));
                        cur+=plus;
                        break;
                    }else{
                        cur=pow(10,6);
                        break;
                    }
                }
            }
        }
        if(cur<ans and cur!=0){
            ans=cur;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int distance(int N, int X, int Y, int i, int j){
  if(j<X || i>Y)return j-i;
  else{
    if(i<X && j>=X && j<=Y)return min(j-i,X-i+1+Y-j);
    else if(i<X && j>Y)return X-i+1+j-Y;
    else if(i>=X && i<=Y && j<=Y && j>=X)return min(j-i,i-X+1+Y-j);
    else if(i>=X && i<=Y && j>Y)return min(j-i,i-X+1+j-Y);
  }
  
}

int main(){
  int N, X, Y;
  cin >> N >> X >> Y;
  X--; Y--;
  vector<int> d;
  for(int i=0; i<N; i++){
    for(int j=i+1; j<N; j++){
      d.push_back(distance(N,X,Y,i,j));
    }
  }
  vector<int> ans(N);
  for(int i=0; i<d.size(); i++){
    ans.at(d.at(i))++;
  }
  for(int i=1; i<N; i++){
    cout << ans.at(i) << endl;
  }
}

Measured memory_bytes: 10604
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007

//ここから編集する
struct BFS01 {
    struct edge {
        ll to, cost;
    };
    typedef pair<ll, ll> P;//firstは最短距離、secondは頂点の番号

    int V;//超点数
    vector<vector<edge> > G;//グラフ,G[i]はiから出る辺の集合,G[i][j]はiから出る辺のj番目の辺
    vector<ll> d; //最短距離

    BFS01(int N) {
        V = N;
        G = vector<vector<edge> >(N);
        d = vector<ll>(N);
    };

    void addEdge(int from, int to, int cost) {
        edge e;
        e.to = to;
        e.cost = cost;
        G[from].push_back(e);
    }

    void calc(int s) {
//        priority_queue<P,vector<P>,greater<P> > que;
        deque<P> que;
        fill(d.begin(), d.end(), INFl);
        d[s] = 0;
        que.push_back(P(0, s));

        while (!que.empty()) {
            P p = que.front();
            que.pop_front();
            ll v = p.second;
            if (d[v] < p.first) continue;
            for (int i = 0; i < G[v].size(); i++) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost && !(d[e.to] == INFl && d[v] == INFl)) {
                    d[e.to] = d[v] + e.cost;
                    if (e.cost == 0) {
                        que.push_front(P(d[e.to], e.to));
                    }else{
                        que.push_back(P(d[e.to],e.to));
                    }
                }
            }
        }

    }
};

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

    int K;
    cin >> K;
    BFS01 bfs01(K);
    rep(i, 0, K) {
        bfs01.addEdge(i, (i + 1) % K, 1);
        bfs01.addEdge(i, i * 10 % K, 0);
    }
    bfs01.calc(1);
    cout << bfs01.d[0] + 1 << endl;


    return 0;
}


Measured memory_bytes: 8832
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include<unordered_set>
#include<complex>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 2000 + 47;

int A[MAX];
int B[MAX];
int B1[MAX];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0);
	int n; 
	LL x;
	cin >> n >> x;
	FOR(i, 0, n)
	{
		cin >> A[i];
		B[i] = A[i];
	}

	LL ans = LINF;
	FOR(k, 0, n)
	{
		LL summ = 0;
		FOR(i, 0, n) summ += B[i];
		ans = min(ans, k * x + summ);
		FOR(i, 0, n)
		{
			B1[i] = min(A[i], B[(i - 1 + n) % n]);
		}

		FOR(i, 0, n)
		{
			B[i] = B1[i];
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int H[N];
  for (int i=0;i<N;i++){
    cin >> H[i];
  }
  int M=0,ans=0;
  for (int i=0;i<N;i++){
    if (M<=H[i]){
      ans++;
      M=H[i];
    }
  }
  cout << ans << endl;
}

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


template<class E, class T> struct Rerooting {
    using F = function<T(T, T)>;
    using H = function<T(T, E)>;
private : 
    struct Edge {
        int to;
        E data;
        T dp, sum;
        Edge (int to, E data, T dp, T sum) : 
            to(to), data(data), dp(dp), sum(sum) { }
    };
    vector<vector<Edge>> g; // グラフ(木)
    vector<T> subdp, dp;    // subdp : 部分木, dp : 全方位
    const T id;             // 単位元
    const F f;              // 累積和生成
    const H h;              // 辺から情報を得る

public : 
    Rerooting (int n, const F &f, const H &h, const T id) : 
        g(n), f(f), h(h), id(id), subdp(n, id), dp(n, id) { }

    void add_edge (int v, int u, const E &val) {
        g[v].emplace_back(u, val, id, id);
    }

    void dfs1 (int v, int p) {
        for (const auto &e : g[v]) {
            if (e.to == p) continue;
            dfs1(e.to, v);
            subdp[v] = f(subdp[v], h(subdp[e.to], e.data));
        }
    }

    void dfs2 (int v, int p, const T &top) {
        T buff = id;
        for (int i = 0; i < (int)g[v].size(); i++) {
            Edge &e = g[v][i];
            e.sum = buff;
            e.dp = h(e.to == p ? top : subdp[e.to], e.data);
            buff = f(buff, e.dp);
        }
        dp[v] = buff;
        buff = id;
        for (int i = (int)g[v].size() - 1; i >= 0; i--) {
            Edge &e = g[v][i];
            if (e.to != p) dfs2(e.to, v, f(buff, e.sum));
            e.sum = f(e.sum, buff);
            buff = f(buff, e.dp);
        }
    }

    vector<T> build(int s = 0) {
        dfs1(s, -1);
        dfs2(s, -1, id);
        return dp;
    }

};


int main() {
    using P = pair<int, int>;
    constexpr int INF = (1<<30);
    int n;
    cin >> n;
    
    auto f = [](pair<int, int> a, pair<int, int> b) {
        for (const auto &e : {b.first, b.second}) {
            if (a.first < e) {
                a.second = a.first;
                a.first = e;
            } else if (a.second < e) {
                a.second = e;
            }
        }
        return a;
    };
    auto h = [](pair<int, int> a, int b) {
        return pair<int, int>(max(0, a.first) + b, -INF);
    };
    
    Rerooting<int, pair<int, int>> g(n, f, h, pair<int, int>(-INF, -INF));
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g.add_edge(a, b, c);
        g.add_edge(b, a, c);
    }
    
    int ans = 0;
    for (const auto &e : g.build()) {
        ans = max(ans, e.first);
        ans = max(ans, e.first + e.second);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 37076
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int a = 0, b = 0;
	char c[100][100];
	double d[100][100];
	for (int i = 0; i < 100; i++)
	{
		for (int j = 0; j < 100; j++)
		{
			d[i][j] = -1;
		}
	}
	cin >> a >> b;
	for (int i = 0; i < a; i++)
	{
		cin >> c[i];
	}
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			for (int k = 0; k <= j; k++)
			{
				if (c[i][j - k] == 'c')
				{
					if (d[i][j] == -1)
					{
						d[i][j] = k;
					}
				}
			}
		}
	}
	for (int i = 0; i < a; i++)
	{
		for (int j = 0; j < b; j++)
		{
			cout << d[i][j];
			if (j + 1 == b)
			{
				cout << endl;
			}
			else
			{
				cout << " ";
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3344
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define ArraySizeOf(array)     (sizeof(array) / sizeof(array[0]))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define _GLIBCXX_DEBUG
int INF = 1e9+7;
unsigned NthDayOfWeekToDay(unsigned n, unsigned dow, unsigned dow1)
{
unsigned day;
if(dow < dow1) dow += 7;
day = dow - dow1;
day += 7 * n - 6;
return day;
}
unsigned DayToWeekNumber(unsigned day)
{
  return (day - 1) / 7 + 1;
}
unsigned AnotherDayOfWeek(unsigned day, unsigned day0, unsigned dow0)
{
  return (dow0 + 35 + day - day0) % 7;
}
using namespace std;
signed main(){
  int N;
  cin>>N;
  int ans=0;
  vector<int>a(N);
  rep(i,N)cin>>a[i];
  sort(a.begin(),a.end());
  rep(i,N)if(a[i]!=a[i-1])ans++;
  cout<<ans<<endl;
}

Measured memory_bytes: 3648
/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;

#define fst first
#define snd second
#define mp make_pair
#define mt make_tuple

/* ---------- conversion ---------- */

#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)
#define DOUBLE(n) static_cast<double>(n)

/* ---------- container ---------- */

#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) (LL((v).size()))

#define FIND(v, k) (v).find(k) != (v).end()
#define VFIND(v, k) find(ALL(v), k) != (v).end()

#define gsort(b, e) sort(b, e, greater<decltype(*b)>())

/* ----------- debug ---------- */

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
    return os << "(" << p.fst << "," << p.snd << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1e9 + 7;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */

template <typename T>
T sq(T a) {
    return a * a;
}

template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

ll pcnt(ll b) {
    return __builtin_popcountll(b);
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

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

    if (A == B) {
        cout << 1 << endl;
        return 0;
    }

    int h;
    for (h = 63; (A >> h) == (B >> h); --h) {};
    A &= (1LL << h) - 1;
    B &= (1LL << h) - 1;

    ll ans = (1LL << h) - A;

    int d;
    for (d = h; d >= 0 && (B >> d) == 0; --d) {};
    B = (1LL << (d + 1)) - 1;

    if (A > B) {
        ans += ans + B + 1;
    } else {
        ans += (1LL << h);
    }

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


Measured memory_bytes: 256
q = int(input())
a = [list(map(int,input().split())) for _ in range(q)]
import math
def f(a,b):
    k = int(math.sqrt(a*b))
    if k>=math.sqrt(a*b):
        k-=1
    if a==b:
        k = 2*min(a,b)-2
    elif min(a,b)+1==max(a,b):
        k = 2*min(a,b)-2
    else:
        if k*(k+1)>=a*b:
            k = 2*k-2
        else:
            k = 2*k-1
    return k
for a_ in a:
    print(f(a_[0],a_[1]))

Measured memory_bytes: 3064
#!/usr/bin/env python3
s = input()
c = [0] * len(s)
c[0] = 1
for i in range(1, len(s)):
    if i < 2:
        if s[i] == s[i - 1]:
            c[i] = c[i - 1]
        else:
            c[i] = c[i - 1] + 1
        continue
    if s[i] == s[i - 1]:
        c[i] = c[i - 3] + 2
    else:
        c[i] = c[i - 1] + 1
print(c[-1])


Measured memory_bytes: 16884
import java.util.Scanner;

public class  Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int n = scanner.nextInt();
		int m = scanner.nextInt();

		for(int i = 0; i < m; i++) {
			n -= scanner.nextInt();
		}

		if(n < 0) {
		System.out.print(-1);
		} else {
			System.out.print(n);
		}
	}
}

Measured memory_bytes: 46100
#include <bits/stdc++.h>
using namespace std;
#define ll	    long long
#define vi      vector <int>
#define vii     vector <pair<int,int>>
#define ii      pair<int,int>
#define loop(n)	for(int i=0;i<n;i++)
const ll mod=1e9+7;
bool is_prime(int n)
{
    if(n==2)
        return true;
    if(n%2==0||n<2)
        return false;
    for(int i=3; i<=sqrt(n); i+=2)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
long long power(ll n, ll k){
    if(k==0) return 1;
    ll sq=(power(n,k/2))%mod;
    sq=(sq*sq)%mod;
    if(k%2==1)
        sq=(sq*n)%mod;
    return sq%mod;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
// lcm = (a*b)/gcd(a,b)
//freopen("input.txt" ,"r",stdin );
//freopen("output.txt","w",stdout);
int n;
vector<int>a;
int memo[100005][2];
ll fun(int idx,bool done)
{
    if(idx>=n-1)return 0;
    int ch1=memo[idx][done],ch2=memo[idx][!done];
    if(ch1==-1)ch1=memo[idx][done]=fun(idx+1,0)+abs(a[idx]-a[idx+1]);
    if(ch2==-1&&idx<n-2)ch2=memo[idx][!done]=fun(idx+2,1)+abs(a[idx]-a[idx+2]);
    if(ch1==-1)ch1=1e9;
    if(ch2==-1)ch2=1e9;
    return min(ch1,ch2);
}
void fast();
int main()
{
    fast();
    cin>>n;
    a.resize(n);
    memset(memo,-1,sizeof memo);
    loop(n)cin>>a[i];
    cout<<fun(0,0);
}
void fast(){
std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
/*

*/


Measured memory_bytes: 7680
import math as mt
import itertools as it
import functools as ft
import random as rnd

stdin = lambda type_ = "int", sep = " ": list(map(eval(type_), input().split(sep)))
joint = lambda sep = " ", *args: sep.join(str(i) if type(i) != list else sep.join(map(str, i)) for i in args)

n = int(input())
H = int(input())
W = int(input())

print((n - W + 1) * (n - H + 1))

Measured memory_bytes: 5840
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define dunk(a) cout << (a) << endl
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;

int main() {
	int n; cin >> n;
	string s; cin >> s;
	int count = 0;
	for (int i = 0; i < n - 2; i++) {
		string t = s.substr(i, 3);
		if (t == "ABC") count++;
	}
	dunk(count);
	return 0;
}


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

using namespace std;
const long long mod = 1e9+7;
const int N = 1e5+5;

#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define fr(i,l,m) for(int i=l;i<m;i++)
int a[N][4];

int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
// Code Here
int n;
cin>>n;
fr(i,1,n+1)
{
    cin>>a[i][0]>>a[i][1]>>a[i][2];
}
ll ans=0;
fr(i,2,n+1)
{
    a[i][0]+=max(a[i-1][1],a[i-1][2]);
    a[i][1]+=max(a[i-1][0],a[i-1][2]);
    a[i][2]+=max(a[i-1][1],a[i-1][0]);
}
ans=max(max(a[n][0],a[n][1]),a[n][2]);
cout<<ans<<endl;
return 0;
}
/////////
/////////
////////



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FAST_INPUT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long

using namespace std;

const int mod = 1e9 + 7;


void add(int& a, int b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	}
}

void substract(int& a, int b) {
	a -= b;
	if (a < 0) {
		a += mod;
	}
}

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

	vector<int> dp(k + 1);

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		vector<int> lazy(k + 1);
		
		for (int used = k; used >= 0; used--) {
			int tmp = dp[used];
			int L = used + 1;
			int R = used + min(a[i], k - used);

			if (L <= R) {
				add(lazy[L], tmp);
				if (R + 1 <= k) {
					substract(lazy[R + 1], tmp);
				}
			}

			// for (int pos = L; pos <= R; pos++) {
			// 	add(dp[pos], tmp);
			// }
			// for (int val = 1; val <= a[i]; val++) {
			// 	if (used + val > k) {
			// 		break;
			// 	}
			// 	add(dp[used + val], dp[used]);
			// }
		}

		int prefix_sum = 0;
		for (int pos = 0; pos <= k; pos++) {
			add(prefix_sum, lazy[pos]);
			add(dp[pos], prefix_sum);
		}
	}

	cout << dp[k] << endl;
}

int main() {
    FAST_INPUT;

    solve();

    return 0;
}


Measured memory_bytes: 1024
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES	// M_PI=3.1415...
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 20桁出力 cout << setprecision(20) << double;
#include <queue>
#include <bitset>	// bitset<8> bs1(131uL); // 10000011 bs1[0]は1 01stringからビット集合生成可
#include <numeric>
#include <random>
#include <climits>  // A/Bを計算するときA==LLONG_MIN && B==-1のみ(1ull<<63)で代用
using namespace std;

typedef long long LL;
typedef pair<LL, LL> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;				// VVL v(100,VL(100,0));
typedef vector<pair<LL, LL> > VP;
typedef vector<string> VS;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<LL, pair<P, P> > PP;

#define INF 999999999999999997		// 少し加算したらオーバーフローする
#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(LL i=(a);i<(b);i++)
#define FOR_REV(i,a,b) for(int i=(a);i>=(b);i--)
#define FOR_ITR(d) for(auto itr=d.begin(),d_end=d.end();itr!=d_end;++itr)	// C++11
#define O(s) cout<<s<<endl;
#define SORTVL(v) sort(v.begin(), v.end());
#define SORTVL_GR(v) sort(v.begin(), v.end(), greater<LL>());

#define DUMP_VVI(b) if(dbgF){FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}

template<class T>T IN() { T d; cin >> d; return d; }

LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a % b) : a; } // 最大公約数（Greatest Common Divisor）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; } // 最小公倍数（Least Common Multiple）
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); } // うるう年判定
string Replace(string S, string from, string to) { auto p = S.find(from); while (p != string::npos) { S.replace(p, from.size(), to); p = S.find(from, p + to.size()); }return S; }
// 桁和
LL Ketawa_s(string s) { LL a = 0; FOR(i, 0, s.length())a += s[i] - '0'; return a; }
// 末尾数字で切り上げ
LL CeilLastNumber(LL n) { return ((n + (10 - 1)) / 10) * 10; }
//二項係数 nCk mod pを求める
const LL MAX = 510000, p = 998244353; LL fac[MAX], finv[MAX], inv[MAX];
/* 前処理 */void COM_init() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; FOR(i, 2, MAX) { fac[i] = fac[i - 1] * i % p; inv[i] = p - inv[p % i] * (p / i) % p; finv[i] = finv[i - 1] * inv[i] % p; } }
/* 主処理 */LL COM(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % p) % p; }

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

// -------------------------------------------------------------------------------

int main() {
	FAST_IO;
	bool dbgF = true; // for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;

	LL r;
	cin >> r;

	O(r * r);

	return 0;
}

Measured memory_bytes: 256
from math import factorial
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


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


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


def S(): return input()


def MS(): return map(str, input().split())


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


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


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


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


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


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


YN = {False: 'No', True: 'Yes'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True


def main():
    n = '0' + S()
    N = len(n)
    n = n[::-1]
    n = [int(i) for i in n]
    dp = [[0] * 2 for i in range(N+1)]
    dp[0][1] = 1

    # print(n)
    for i in range(N):
        # print(i, 'no up', dp[i][0] + n[i], dp[i][1] + n[i] + 1)
        # print(i, 'no down', dp[i][0] + 10 - n[i], dp[i][1] + 10 - (n[i] + 1))
        dp[i+1][0] = min(dp[i][0] + n[i], dp[i][1] + n[i] + 1)
        dp[i+1][1] = min(dp[i][0] + 10 - n[i], dp[i][1] + 10 - (n[i] + 1))

    print(min(dp[N]))


if __name__ == '__main__':
    main()


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

int main(void) {
  int n;
  cin >> n;
  vector<int> ss(n);
  int sum = 0;
  for (int &s : ss) {
    cin >> s;
    sum += s;
  }

  if (sum % 10 == 0) {
    int minimum = 1000;
    for (const int &s : ss) {
      if (s % 10 != 0) {
        minimum = min(minimum, s);
      }
    }

    if (minimum == 1000) {
      cout << 0 << endl;
    } else {
      cout << sum - minimum << endl;
    }
  } else {
    cout << sum << endl;
  }

  return 0;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int A,B,M;
    cin>>A>>B>>M;
    int a[A],b[B],ma,mb;
    ma=INT_MAX;
    mb=INT_MAX;
    for(int i=0;i<A;i++) cin>>a[i],ma=min(ma,a[i]);
    for(int i=0;i<B;i++) cin>>b[i],mb=min(mb,b[i]);
    int ans=ma+mb;
    int x,y,c;

    for(int i=0;i<M;i++)
    {
        cin>>x>>y>>c;
        ans = min(ans, (a[x-1]+b[y-1]-c));

    }

    ans = min(ans,ma+mb);
    cout << ans << endl;
    return 0;
}


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

int main() {
    int r,c;
    cin >> r >> c;
    int a, A[101] = {0};
    for(int i = 0; i < r; i++){
        int sum = 0;
        for(int j = 0; j < c; j++){
            cin >> a;
            A[j] += a;
            sum += a;
            cout << a << " ";
        }
        cout << sum << endl;
    }
    int sum = 0;
    for(int i = 0; i < c; i++){
        sum += A[i];
        cout << A[i] << " ";
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3108
import numpy as np

L, R = map(int, input().split())

min_ = np.inf
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if (i * j) % 2019 <= min_:
            min_ = (i * j) % 2019
            if min_ == 0:
                print(min_)
                exit()

print(min_)


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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  int n;
  vector<LL> seq;
  vector<vector<LL>> m;
  Solver(LL n) : n(n), seq(1 << n), m((1 << n), vector<LL>(2)){};
  vector<LL> calc(vector<LL> a, vector<LL> b) {
    vector<LL> ret;
    for (int i = 0; i < 2; ++i) {
      ret.push_back(a[i]);
      ret.push_back(b[i]);
    }
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());
    sort(ret.begin(), ret.end(),
         [&](const int &x, const int &y) { return seq[x] > seq[y]; });
    while (ret.size() > 2) {
      ret.pop_back();
    }
    DBG(ret)
    return ret;
  }
  void solve() {
    for (int i = 0; i < (1 << n); ++i) {
      scanf("%lld", &seq[i]);
      m[i] = {i, 0};
      for (int j = 0; j < 18; ++j) {
        if ((i >> j) & 1) {
          m[i] = calc(m[i], m[i - (1 << j)]);
        }
      }
    }
    vector<LL> ans(1 << n);
    ans[1] = seq[0] + seq[1];
    DBG(m)
    for (int i = 2; i < (1 << n); ++i) {
      ans[i] = max(ans[i - 1], seq[m[i][0]] + seq[m[i][1]]);
    }
    for (int i = 1; i < (1 << n); ++i) {
      printf("%lld\n", ans[i]);
    }
  }
};
}  // namespace Problem

int main() {
  // std::cin.tie(0);
  // std::ios_base::sync_with_stdio(false);
  long long n = 0;
  scanf("%lld", &n);

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


Measured memory_bytes: 25640
n, k = [int(i) for i in input().split()]
h = [0 for _ in range(n)]
for i in range(len(h)):
    h[i] = int(input())
h = sorted(h)

_min = h[k-1] - h[0]
for i in range(k, len(h)):
    if h[i] - h[i - k + 1] <= _min:
        _min = h[i] - h[i - k + 1]
print(_min)

Measured memory_bytes: 8276
import numpy as np

S = list(input())
T = list(input())

count_A_S = np.r_[[0], np.array(S) == 'A']
count_A_S = count_A_S.cumsum()
count_B_S = np.r_[[0], np.array(S) == 'B']
count_B_S = count_B_S.cumsum()
count_A_T = np.r_[[0], np.array(T) == 'A']
count_A_T = count_A_T.cumsum()
count_B_T = np.r_[[0], np.array(T) == 'B']
count_B_T = count_B_T.cumsum()

def check(a1, b1, a2, b2):
  if a1 < a2:
    if b1 < b2:
      diff1 = a2 - a1; diff2 = b2 - b1
      diff = abs(diff1 - diff2)
    else:
      diff = b1 - b2 + a2 - a1
  else:
    if b1 < b2:
      diff = a1 - a2 + b2 - b1
    else:
      diff1 = a1 - a2; diff2 = b1 - b2
      diff = abs(diff1 - diff2)
  if diff % 3 == 0:
    return 'YES'
  else:
    return 'NO'

q = int(input())
ans = []
for i in range(q):
  a, b, c, d = map(int, input().split())
  num_a_s = count_A_S[b] - count_A_S[a-1]
  num_b_s = count_B_S[b] - count_B_S[a-1]
  num_a_t = count_A_T[d] - count_A_T[c-1]
  num_b_t = count_B_T[d] - count_B_T[c-1]
  ans.append(check(num_a_s, num_b_s, num_a_t, num_b_t))

print(*ans, sep='\n')

Measured memory_bytes: 20360
from sys import stdin
from collections import deque

n,m=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,stdin.readline().split())
    a-=1
    b-=1
    ab[a].append(b)
    ab[b].append(a)
queue=[0]
ans=[-1]*n
ans[0]=0
while len(queue)!=0:
    now_check=queue.pop(0)
    for i in ab[now_check]:
        if ans[i]==-1:
            queue.append(i)
            ans[i]=now_check
print('Yes')
for i in range(1,n):
    print(ans[i]+1)

Measured memory_bytes: 34276
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int N_MAX = 210, M_MAX = N_MAX*(N_MAX-1)/2, R_MAX = 8;
const int INF = 1e8;
int V,E,R;
int G[N_MAX][N_MAX];

void warshall_floyd(){
  rep(w,V)rep(v,V)rep(u,V) 
    G[v][u] = min(G[v][u],G[v][w] + G[w][u]);
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V >> E >> R;
  vector<int> vr(R);
  rep(i,R){
    cin >> vr[i];
    --vr[i];
  }
  sort(all(vr));

  rep(v,V)rep(u,V) G[v][u] = (v==u) ? 0:INF;

  rep(i,E){
    int f,t,c; cin >> f >> t >> c;
    --f;--t;
    G[f][t] = G[t][f] = c; 
  }

  warshall_floyd();

  ll res = MAX_I;
  do{
    ll route = 0;
    rep(i,R-1) route += G[vr[i]][vr[i+1]];
    res = min(res,route);
  }while(next_permutation(all(vr)));

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>

using namespace std;
typedef long long ll;

ll min(ll x, ll y){
    if(x<y){
        return x;
    }
    else{
        return y;
    }
}

int main()
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++){
    cin>>a[i];
}
ll dp[n];
dp[n-1]=0;
dp[n-2]=abs(a[n-2]-a[n-1]);
for(ll i=n-3;i>=0;i--){
    dp[i]=min(dp[i+1]+abs(a[i+1]-a[i]),abs(a[i+2]-a[i])+dp[i+2]);
}
cout<<dp[0]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<functional>


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

int main(){
    int n ;cin >> n ;
    int A[n] ;
    rep(i,n) cin >> A[i];
    int min_A = 1e9+1 ;
    int max_A = 0 ;
    rep(i,n) min_A= min(A[i],min_A);
    rep(i,n) max_A= max(A[i],max_A);
    cout << max_A - min_A << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>

template <typename T>
constexpr T abs(const T& x)
{
    return x > 0 ? x : -x;
}

template <typename T>
constexpr T max(const T& x, const T& y)
{
    return x > y ? x : y;
}

template <typename T>
constexpr T min(const T& x, const T& y)
{
    return x < y ? x : y;
}





int n, Q, u, v;
long long tag[200010];
std::vector <int> t[200010];


void dfs(int x, int f)
{
    for (auto i : t[x])
        if (i != f)
        {
            tag[i] += tag[x];
            dfs(i, x);
        }
}

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

    std::cin >> n >> Q;
    for (int i = 1; i < n; ++i)
        std::cin >> u >> v,
        t[u].push_back(v), t[v].push_back(u);

    for (; Q; --Q)
    {
        std::cin >> u >> v;
        tag[u] += v;
    }

    dfs(1, 1);

    for (int i = 1; i <= n; ++i)
        std::cout << tag[i] << " ";
    std::cout << std::endl;

    return 0;
}

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

int main(){
    int N;
    cin >> N;
    int d[N];
    for(int i = 0; i < N; ++i) cin >> d[i];
    int sum = 0;

    for(int i = 0; i < N - 1; ++i){

        for(int j = i + 1; j < N; ++j){
            sum += d[i] * d[j];
        }
    }
    cout << sum << endl;
}

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

int main()
{
	int a, b, c, d, e, f, s;

	cin >> a >> b >> c >> d >> e >> f;

	s = a;

	if (s > b)
		s = b;
	if (s > c)
		s = c;
	if (s > d)
		s = d;

	if (e >= f)
		cout << a + b + c + d - s + e << endl;
	else
		cout << a + b + c + d - s + f << endl;

	return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<int, int> ti2;
typedef tuple<int, int, int> ti3;
typedef tuple<int, int, int, int> ti4;
typedef tuple<ll, ll> tl2;
typedef tuple<ll, ll, ll> tl3;
typedef tuple<ll, ll, ll, ll> tl4;
typedef vector<int> vi;
typedef vector<ti2> vti2;
typedef vector<ti3> vti3;
typedef vector<ti4> vti4;
typedef vector<ll> vl;
typedef vector<tl2> vtl2;
typedef vector<tl3> vtl3;
typedef vector<tl4> vtl4;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vti2> vvti2;
typedef vector<vti3> vvti3;
typedef vector<vti4> vvti4;
typedef vector<vl> vvl;
typedef vector<vtl2> vvtl2;
typedef vector<vtl3> vvtl3;
typedef vector<vtl4> vvtl4;
typedef vector<vs> vvs;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i < i##_len; i++)
#define FORD(i, a, b) for (int i = (a), i##_len = (b); i > i##_len; i--)
#define FORR(t, a) for (auto t : a)
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define SORT(a, func) sort(ALL(a), [](const auto& x, const auto& y) func)
#define GET(i, j) get<j>(i)
#define MT(x, ...) make_tuple(x, __VA_ARGS__)
#define PRINT(i) cout << i << endl
#define PRINT2(i, j) cout << i << " " << j << endl
#define PRINT3(i, j, k) cout << i << " " << j << " " << k << endl
#define PRINT4(i, j, k, l) cout << i << " " << j << " " << k << " " << l << endl
#define PRINTL(a)                                       \
    for (const auto& d9aw : a) { cout << d9aw << " "; } \
    cout << endl

//演算子オーバーロード
bool operator<(const ti2 x, const ti2 y) {
    if (GET(x, 0) != GET(y, 0))
        return GET(x, 0) < GET(y, 0);
    else
        return GET(x, 1) < GET(y, 1);
}
bool operator>(const ti2 x, const ti2 y) {
    if (GET(x, 0) != GET(y, 0))
        return GET(x, 0) > GET(y, 0);
    else
        return GET(x, 1) > GET(y, 1);
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a < b)
        cout << "a < b" << endl;
    else if (a > b)
        cout << "a > b" << endl;
    else
        cout << "a == b" << endl;
}


Measured memory_bytes: 3068
import sys
input = sys.stdin.readline  # NOQA
sys.setrecursionlimit(10 ** 7)  # NOQA

from collections import deque


def dfs(G, v, p, counter):
    """G: graph, v: vertex, p: parent"""
    parent = [-1] * len(G)
    stack = deque([v])
    while stack:
        v = stack.pop()
        for c in G[v]:
            if c == parent[v]:
                continue
            parent[c] = v
            stack.append(c)
            counter[c] += counter[v]


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    dfs(G, 0, -1, counter)
    print(*counter)


if __name__ == "__main__":
    main()


Measured memory_bytes: 54516
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;
const int MOD = 1e9 + 7;

int A[N], B[N], n;
ll sol = 0;

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++)
		scanf("%d%d", A + i, B + i);
	for(int i = n - 1;i >= 0;i--){
		sol += (B[i] - (sol + A[i]) % B[i]) % B[i];
	}
	printf("%lld\n", sol);
	return 0;
}


Measured memory_bytes: 2476
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp14
{
    class Program
    {
        static void Main(string[] args)
        {
            var solver = new Solver();
            solver.Calc();
        }
    }

    public class Solver
    {

        public void Calc()
        {

            var N = long.Parse(Console.ReadLine());

            var As = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();

            Console.WriteLine(As.Distinct().Count() == As.Count() ? "YES" : "NO");

            //var SP = Console.ReadLine().Split();


            //var AB = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();

            //var U = Console.ReadLine();

            //var S = Console.ReadLine();

            //Console.WriteLine(new string('x', S.Length));


        }
    }
}

Measured memory_bytes: 51124
N = int(input())
A = list(map(int, input().split()))

mi = min(A)
while 1:
    for i in range(N):
        if A[i] != mi:
            A[i] %= mi
            if A[i] <= 0:
                A[i] = mi
    if min(A) == mi:
        break
    else:
        mi = min(A)

print(mi)

Measured memory_bytes: 14252
import java.util.*;


public class Main {
	//template
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		//
		new Main().aoj0532();
	}

	int min(int[] arr){
		int ret = arr[0];
		for(int i = 0; i < arr.length; i++){
			if(ret>arr[i])ret = arr[i];
		}
		return ret;
	}
	
	int max(int[] arr){
		int ret = arr[0];
		for(int i = 0; i < arr.length; i++){
			if(ret<arr[i])ret = arr[i];
		}	
		return ret;
	}
	
	int sum(int[] array){
		int sum = 0;
		for(int v : array){
			sum += v;
		}
		return sum;
	}
	
	
	//--------------------------
	
	void aoj0532(){
		for(int i = 0; i < 3; i++){
			int in = sc.nextInt()*60*60+sc.nextInt()*60+sc.nextInt();
			int out = sc.nextInt()*60*60+sc.nextInt()*60+sc.nextInt();
			int diff = out - in;
			
			int h = diff/(60*60);
			diff -= h*60*60;
			int m = diff/60;
			diff -= m*60;
			int s = diff;
			
			System.out.println(h+" "+m+" "+s);
		}
	}
	
	void aoj0533(){
		int[] wp = new int[10];
		int[] kp = new int[10];
		for(int i=0; i<10; i++){ wp[i] = sc.nextInt(); }
		for(int i=0; i<10; i++){ kp[i] = sc.nextInt(); }
		
		Arrays.sort(wp); Arrays.sort(kp);
		System.out.println((wp[9]+wp[8]+wp[7]) + " " + (kp[9]+kp[8]+kp[7]));
	}
	
	
}

Measured memory_bytes: 17176
#include<bits/stdc++.h>
# define ll long long int
# define Mod 1000000007
using namespace std;
vector<ll> tree[200005];
vector<ll> ans(200005);
void fast(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
}

void dfs(ll v,ll par=-1){
	for(ll u:tree[v]){
		if(u==par)continue;
		ans[u]+=ans[v];
		dfs(u,v);
	}
}

int main(){
	fast();
	ll n,q;
	cin>>n>>q;
	for(ll i=1;i<n;i++){
		ll x,y;
		cin>>x>>y;
		--x,--y;
		tree[x].push_back(y);
		tree[y].push_back(x);
	}
	for(ll i=1;i<=q;i++){
		ll p,x;
		cin>>p>>x;
		--p;
		ans[p]+=x;
	}
	dfs(0);
	for(ll i =0;i<n;i++)cout<<ans[i]<<" ";
}

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

#define int long long

int K;
vector<int> S, T;

int dfs(int k, vector<int> s) {  
  /* cout << k << " ";
     for ( int i : s ) cout << i;
     cout << endl; */
  if ( k == K ) return 0;
  if ( s[k] == T[k] ) return dfs(k+1, s);  

  int ret = 11;
  int add = T[k]-s[k];  
  for ( int i = k; i < K; i++ ) {
    s[i] = (s[i]+add+10)%10;    
    ret = min(ret, dfs(k+1, s)+1);    
  }

  return ret;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  while ( cin >> K, K ) {
    S = T = vector<int>(K);  
    {
      string a, b;
      cin >> a >> b;
      for ( int i = 0; i < K; i++ ) {
	S[i] = a[i]-'0';      
      }
      for ( int i = 0; i < K; i++ ) {
	T[i] = b[i]-'0';      
      }
    }

    cout << dfs(0, S) << endl;    
  }
  
  return 0;
}



Measured memory_bytes: 3232
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;++i) cin>>arr[i];
    int xx[n]={0};
    xx[0]=0;
    xx[1]=abs(arr[0]-arr[1]);
    for(int i=2;i<n;++i)
    {
        xx[i]=min(xx[i-2]+abs(arr[i-2]-arr[i]),xx[i-1]+abs(arr[i-1]-arr[i]));
    }
    cout<<xx[n-1]<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, k; cin >> n >> k;
    vint l(n);
    rep(i,n) cin >> l[i];
    sort(rall(l));
    int sum = 0;
    rep(i,k) sum += l[i];
    cout << sum << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    G[B].append(A)

cl = [-1] * (N+1)
cl[1] = 0
is_bipartite = True
stack = [1]
while stack:
    v = stack.pop()
    for c in G[v]:
        if cl[c] != -1 and cl[c] == cl[v]:
            is_bipartite = False
            break
        if cl[c] == -1:
            cl[c] = 1 - cl[v]
            stack.append(c)
    if not is_bipartite:
        break
if is_bipartite:
    print(cl.count(0) * cl.count(1) - M)
else:
    print(N * (N - 1) // 2 - M)

Measured memory_bytes: 59372
#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,n) for(int i=1;i<=n;i++)
int main()
{
    string s,p;

    cin >> s >> p;

    int ls=s.length(),lp=p.length();
    int idx;
    int bit=0;

    rep(i,ls){
        rep(j,lp){
            idx = (i+j) % ls;
            if(s[idx]!=p[j]) break;
            if(j==lp-1) bit=1;
        }
        if(bit == 1) break;
    }

    if(bit==1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;


}


Measured memory_bytes: 3220