akhauriyash/Code-Regression huggingface dataset:
import sys
from itertools import permutations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    def dfs(v, seen):
        if len(seen) == N:
            return 1

        ans = 0
        for nv in G[v]:
            if nv not in seen:
                seen.add(nv)
                ans += dfs(nv, seen)
                seen.remove(nv)

        return ans

    print(dfs(0, {0}))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9220
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int g,t;
    string q;
    cin>>t>>q;
    if(t&1)printf("No\n");
    else{
        for(g=0;g<t/2;g++)
            if(q[g]!=q[t/2+g])printf("No\n",g=t);
        if(g!=t+1)printf("Yes\n");
    }
    return 0;
}


Measured memory_bytes: 256
import bisect
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().rstrip()
T = readline().rstrip()
if len(S) < len(T):
    S, T = T, S


def pretty(ss):
    buf = []
    while ss is not None:
        s, ss = ss
        buf.append(s)
    buf.reverse()
    return "".join(buf)


def solve():
    index = collections.defaultdict(list)
    for i, sc in enumerate(S):
        index[sc].append(i)
    dp = [None] * len(T)
    for i, tc in enumerate(T):
        if tc not in index:
            continue
        dn = list(dp)
        ii = index[tc]
        if dn[0] is None or dn[0][0] > ii[0]:
            dn[0] = (ii[0], [chr(tc), None])
        for j in range(1, len(T)):
            if dp[j - 1] is None:
                break
            k = bisect.bisect_right(ii, dp[j - 1][0])
            if k < len(ii) and (dn[j] is None or dn[j][0] > ii[k]):
                dn[j] = (ii[k], [chr(tc), dp[j - 1][1]])
        dp = dn
    for i in range(len(T) - 1, -1, -1):
        if dp[i] is not None:
            return pretty(dp[i][1])
    return ""


if __name__ == "__main__":
    print(solve())


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

int main(void){

    string S, T, U;
    int A, B;
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    if(S==U){
        A--;
    }else{
        B--;
    }
    cout << A << " " << B << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define P pair<int,int>
#define All(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
typedef long long ll;
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const ll LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int main() {
	int n, h, ans = 0, cmp = 0;
	cin >> n >> h;
	int a[n], b[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	sort(a, a + n);
	reverse(a, a + n);
	sort(b, b + n);
	reverse(b, b + n);
	for (int i = 0; i < n; i++) {
		if (b[i] > a[0]) {
			cmp += b[i], ans++;
		}
		if (cmp >= h) {
			cout << ans << endl;
			return 0;
		}
	}
	if (cmp < h) {
		while (cmp < h) {
			cmp += a[0];
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
ll LCM(ll a, ll b) { return a / GCD(a, b)* b; }
 
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
 
inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}
 
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int N,A,B,C;
vi L;
int rec(int i, int a, int b, int c){
  if(i==N){
    if(!a||!b||!c) return INF;
    return abs(A-a)+abs(B-b)+abs(C-c);
  }
  int res=rec(i+1,a,b,c);
  
  chmin(res,rec(i+1,a+L[i],b,c)+(a?10:0));
  chmin(res,rec(i+1,a,b+L[i],c)+(b?10:0));
  chmin(res,rec(i+1,a,b,c+L[i])+(c?10:0));
  
  return res;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>N>>A>>B>>C;
  L.resize(N);
  rep(i,N) cin>>L[i];
  
  cout<<rec(0,0,0,0)<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_20190707_1
{    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());

            for(int i = (int)Math.Pow(N, 0.5); i >= 1; i--)
            {
                if(N % i == 0)
                {
                    Console.WriteLine((i - 1) + (N / i - 1));
                    return;
                }
            }

            Console.WriteLine(N - 1);
        }
    }
}

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

using namespace std;

int main(){
 int n; 
  cin >>  n;
 
  int res=1,odd=1,a;
  for(int i=0;i<n;i++){
    res*=3;
    cin >> a;
    if(a%2==0) odd*=2; 
    }
  
  cout << res-odd << endl;

}


Measured memory_bytes: 256
s = input()
n = len(s)
a = ''
ans = 'Yes'
if s[::-1] != s:
    ans = 'No'
for i in range((n-1)//2):
    a += s[i]
if a[::-1] != a:
    ans = 'No'
a = ''
for i in range((n+3)//2-1,n):
    a += s[i]
if a[::-1] != a:
    ans = 'No'
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define fr(i,a,b) for(long long int i=a; i<b; i++)
#define pb push_back
#define mp make_pair
using namespace std;
signed main() 
{
    fast
    ll n;
    cin>>n;
    ll s=0;
    for(ll i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
            s=s+i;
        }
    }
    cout<<s;
}

Measured memory_bytes: 3612
a = list(input())
b = list(input())
c = list(input())

num_li = [a,b,c]

now = 0
while True:
    if len(num_li[now])==0:
        print('A' if now==0 else 'B' if now==1 else 'C');exit()

    x = num_li[now].pop(0)
    now = 0 if x=='a' else 1 if x=='b' else 2

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

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

int main() {
    int N, K, ans = 0;
    
    cin >> N;
    cin >> K;
    vector<int> x(N);
    rep(i, N) {
        cin >> x.at(i);
    }

    rep(i, N) {
        ans += min(x[i] ,abs(x[i] - K)) * 2;
    }

    cout << ans << endl;

    return 0;
}


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

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int A, B, K;
	cin >> A >> B >> K;
	//bool frag = false;
	//if(K % 2 == 1) {
	//	frag = true;
	//}
	
	for(int i = 0; i < K; i++) {
		if(A % 2 == 1) {
			A = A - 1;
		}
		B = B + A/2;
		A = A/2;
		
		//if(frag && i == K-1) {
		if(i == K-1) {
			break;
		}
		
		i++;
		if(B % 2 == 1) {
			B = B - 1;
		}
		A = A + B/2;
		B = B/2;
	}
	
	cout << A << " " << B << endl;
		

}


Measured memory_bytes: 256
from math import gcd
n, x = map(int, input().split())
city = list(map(int, input().split()))
if x not in city:
    city.append(x)
city.sort(reverse=True)
for i in range(len(city) - 1):
    city[i] -= city[i + 1]
ans = city[0]
for i in range(len(city) - 1):
    ans = gcd(ans, city[i])
print(ans)

Measured memory_bytes: 20312
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
using namespace std;
#define lol long long


int main()
{
	int A, B, C;
	cin >> A >> B >> C;
	if (min(A, B) <= C && max(A, B) >= C) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    int n;
    string s,t;
    cin>>n>>s>>t;
    int ans=0;
    rep(i,n){
        FOR(j,i,s.size()){
            if(s[j]!=t[j-i]) break;
            if(j==s.size()-1){
                ans=s.size()-i;
                cout<<(int)s.size()*2-ans<<endl;
                return 0;
            }
        }
    }
    cout<<(int)s.size()*2-ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    // ABC152
    static final long MOD = 1_000_000_007;
    //10^9+7
    static final int MAX = 2_147_483_646;
    //intの最大値
    static final int INF = 1_000_000_000;
    //10^9
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        if(n == m){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

    }
}


Measured memory_bytes: 21844
s=input()
t=input()
a=[]
for i in range(len(s)-len(t)+1):
    f=True
    for j in range(len(t)):
        if s[i+j] != '?' and s[i+j] != t[j]:
            f=False
    if f == True:
        a.append(i)
s=s.replace('?','a')
if len(a) != 0:
    print(s[:a[-1]]+t+s[a[-1]+len(t):])
else:
    print('UNRESTORABLE')

Measured memory_bytes: 3064
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Ball Distribution
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  int d0 = n / k;
  int d1 = n - d0 * (k - 1);
  printf("%d\n", d1 - d0);
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
#define eps 1e-6
using namespace std;
const double pi = 3.1415926535;
int main(){
    int a,b,h;
    s(a) s(b) s(h)
    p((a+b)*h/2) pn














    return 0;

}


Measured memory_bytes: 256
import collections

N = int(input())
A = list(map(int, input().split()))
count_dict = collections.Counter(A)
combination_count = 0
for value in count_dict.values():
    combination_count += int(value*(value-1)/2)
for i in range(N):
    print(combination_count - count_dict[A[i]] +1)

Measured memory_bytes: 26780
//#include "pch.h" 
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod (int)(1e9 + 7)
#define inf (int)1e16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
using namespace std;
signed main() {
	int n;
	cin >> n;
	int a, b;
	a = 0;
	b = 0;
	rep(i, n) {
		char s;
		cin >> s;
		if (s == 'R') a++;
		else b++;
	}
	if (a > b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<int, int>;
vector<ii> dirs = {
  {1, 0}, {0, 1}, {-1, 0}, {0, -1},  // 4方向
  {1, 1}, {-1, 1}, {-1, -1}, {1, -1},  // 斜め
  {0, 0},  // 自身
};
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <class T, class S> vector<T> make_vec(size_t n, S x) { return vector<T>(n, x); }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...)); }

// debug
template <class T> ostream& operator<<(ostream& s, vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream& s, vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream& s, pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
  #define dump(...)
  #define endl "\n"
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }

struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int MOD = 1000000007;
// *************** TEMPLATE END *************** 

signed main() {
  int h, w; cin >> h >> w;
  vector<string> t(h); REP (i, h) cin >> t[i];
  auto dp = make_vec<int>(h, w, 0);
  REP (i, h) {
    int acc = 0;
    REP (j, w) {
      if (t[i][j] == '#') {
        acc = 0;
      } else {
        dp[i][j] += acc;
        acc++;
      }
    }
    acc = 0;
    for (int j = w - 1; j >= 0; j--) {
      if (t[i][j] == '#') {
        acc = 0;
      } else {
        dp[i][j] += acc;
        acc++;
      }
    }
  }
  REP (j, w) {
    int acc = 0;
    REP (i, h) {
      if (t[i][j] == '#') {
        acc = 0;
      } else {
        dp[i][j] += acc;
        acc++;
      }
    }
    acc = 0;
    for (int i = h - 1; i >= 0; i--) {
      if (t[i][j] == '#') {
        acc = 0;
      } else {
        dp[i][j] += acc;
        acc++;
      }
    }
  }
  dump(dp);
  int ma = 0;
  REP (i, h) {
    REP (j, w) {
      chmax(ma, dp[i][j] + 1);
    }
  }
  cout << ma << endl;
}


Measured memory_bytes: 35840
#include<bits/stdc++.h>
#define int long long
using namespace std;

int32_t main()
{
  int n;
  cin>>n;
  int a[n],q,b,c,sum=0,f=0;
  map<int,int>m;
  for(int i=0;i<n;++i)
  {
    cin>>a[i];
    m[a[i]]++;
    sum+=a[i];
  }
  cin>>q;
  while(q--)
  {
    cin>>b>>c;
    if(m[b]==0)
    {
      cout<<sum<<endl;
      continue;
    }
    else
    {
      f=m[b];
      if(b>c)
      {
        sum-=(b-c)*f;
      }
      else if(b<c)
      {
        sum+=(c-b)*f;
      }
      m[b]=0;
      m[c]+=f;
    }
    cout<<sum<<endl;
  }

}

Measured memory_bytes: 10116
#include <stdio.h>
int main(){
 
 int a, b, c, count = 0;
 scanf("%d%d%d", &a, &b, &c);
 for(a; a <= b; a++) {
 if(c%a == 0) {
 count++;
 }
 }
 printf("%d\n", count);
 
 return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

const ll MOD = 998244353;

struct mint {
    ll x;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {
    }
    mint operator-() const {
        return mint(-x);
    }
    mint &operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t / 2);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime MOD
    mint inv() const {
        return pow(MOD - 2);
    }
    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

ostream &operator<<(ostream &os, const mint &a) {
    return os << a.x;
}

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

    unordered_map<ll, ll> mp;

    ll mx   = 0;
    vec<ll> D(N);
    rep(i, N) {
        cin >> D[i];
        ++mp[D[i]];
        mx = max(mx, D[i]);
    }

    mint ans = 0;
    if (D[0]==0 && mp[0] == 1) ans = 1;
    
    for (int i = 1; i <= mx; ++i) {
        if (mp[i] == 0) {
            cout << 0 << '\n';
            return 0;
        }
         ans *= mint(mp[i - 1]).pow(mp[i]);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 7912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int main(){
  int n;
  cin>>n;
  vector<int>a(n);
  rep(i,n)cin>>a[i];
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  int alice=0,bob=0;
  for(int i=0;i<n;i++){
    if(i%2==0)alice+=a[i];
    else bob+=a[i];
  }
  cout <<alice-bob<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  vector<int> dp(n, inf);
  dp[0] = 0;
  rep(i, n) {
    rep3(j, i - 2, i) {
      if (j >= 0) chmin(dp[i], dp[j] + abs(a[i] - a[j]));
    }
  }
  cout << dp[n - 1] << endl;
}


Measured memory_bytes: 1024
import scala.annotation.tailrec
import scala.collection.{immutable, mutable}
object Main extends App {
  import scala.io.StdIn._
  val map = mutable.Map[Coordinate, Int]()
  val queue = mutable.Queue[Int]()
  loop()
  @tailrec def loop(): Unit = {
    val n = readInt()
    if (n == 0) return
    val nodes = Array.fill(2 * n){Nil: List[Edge]}
    map.clear()
    for (i ← 0 until n) {
      val Array(ax, ay, d) = readLine.trim.split(' ')
      val current@Coordinate(x, y) = Coordinate(ax.toInt, ay.toInt)
      for (neighbor ← current.neighbors; j ← map.get(neighbor)) {
        nodes(i * 2) ::= Edge(j, 0)
        nodes(j) ::= Edge(i * 2, 0)
      }
      val other: Coordinate = if (d == "x") Coordinate(x + 1, y) else Coordinate(x, y + 1)
      for (neighbor ← other.neighbors; j ← map.get(neighbor)) {
        nodes(i * 2 + 1) ::= Edge(j, 0)
        nodes(j) ::= Edge(i * 2 + 1, 0)
      }
      nodes(i * 2) ::= Edge(i * 2 + 1, 1)
      nodes(i * 2 + 1) ::= Edge(i * 2, 1)
      map += current → (i * 2)
      map += other → (i * 2 + 1)
    }
    val count = Array.fill(2 * n){-1}
    var canMake = true
    for (i ← count.indices if count(i) == -1 && canMake) {
      queue.clear()
      queue.enqueue(i)
      count(i) = 0
      while(queue.nonEmpty && canMake) {
        val current = queue.dequeue()
        for (Edge(next, cost) ← nodes(current)) {
          if (count(next) == -1) {
            count(next) = (count(current) + cost) % 2
            queue.enqueue(next)
          }else if (count(next) != (count(current) + cost) % 2){
            canMake = false
          }
        }
      }
    }
    println(if (canMake) "Yes" else "No")
    loop()
  }
  case class Edge(from: Int, cost: Int)
  case class Coordinate(x: Int, y: Int) {
    def neighbors: List[Coordinate] = List(Coordinate(x + 1, y), Coordinate(x - 1, y), Coordinate(x, y + 1), Coordinate(x, y - 1))
  }
}


Measured memory_bytes: 254372
use proconio::input;
use proconio::marker::Chars;

macro_rules! chmin {
    ($min_v: expr, $v: expr) => {
        if $v < $min_v {
            $min_v = $v;
            true
        } else {
            false
        }
    };
}

fn main() {
    input! {
        h: usize,
        w: usize,
        s: [Chars; h],
    };
    let inf = 100 * 100;
    let mut d = vec![vec![inf; w]; h];
    let mut q = std::collections::VecDeque::new();
    d[0][0] = if s[0][0] == '#' { 1 } else { 0 };
    q.push_back((0, 0));
    while let Some((y, x)) = q.pop_front() {
        if x + 1 < w {
            if chmin!(
                d[y][x + 1],
                d[y][x] + if s[y][x] == s[y][x + 1] { 0 } else { 1 }
            ) {
                q.push_back((y, x + 1));
            }
        }
        if y + 1 < h {
            if chmin!(
                d[y + 1][x],
                d[y][x] + if s[y][x] == s[y + 1][x] { 0 } else { 1 }
            ) {
                q.push_back((y + 1, x));
            }
        }
    }
    let ans = (d[h - 1][w - 1] + if s[h - 1][w - 1] == '#' { 1 } else { 0 }) / 2;
    println!("{}", ans);
}


Measured memory_bytes: 2212
#include <bits/stdc++.h>
    #include <math.h>
 
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    # define M_PI  3.14159265358979323846
 
 
    const int M=1e9+7;
    long long mod(long long x){
        return ((x%M + M)%M);
    }
    long long add(long long a, long long b){
        return mod(mod(a)+mod(b));
    }
 
    vector<ll>a(5005);
    vector<ll>b(5005);
    vector<ll>track;
    bool vis[5005];
 
    void dfs(int u , long long total_cycle){
        if(vis[u]) return ;
        vis[u]=true;
        total_cycle+=b[u];
        track.push_back(total_cycle);
        dfs(a[u],total_cycle);
    }
    void solve(){
        int n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++){
            cin>>a[i];
            a[i]--;
        }
        for(int i=0;i<n;i++)
            cin>>b[i];
        ll ans=-(1e18);
        for(int i=0;i<n;i++){
            memset(vis,false,sizeof(vis));
            dfs(i,0);
            if(track.back()>0 && k>=(int)(track.size())){
                ll cycles=(ll)(k/(int)track.size());
                ll left=(ll)(k%(int)track.size());
                ll maxi=-1e18;
                for(int x=0;x<(int)track.size();x++)
                    maxi=max(maxi,track[x]);
                ans=max(ans,(cycles-1LL)*(track.back())+maxi);
                maxi=-1e18;
                for(int x=0;x<left;x++)
                    maxi=max(maxi,track[x]);
                ans=max(ans,(cycles*track.back()) + maxi);
            }
            else{
                for(int j=0;j<(min((int)track.size(),k));j++){
                    ans=max(ans,track[j]);
                }
            }
            track.clear();
        }
        cout<<ans;
        return;
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cout<<fixed;
        cout<<setprecision(10);
//        freopen("timber_input.txt", "r", stdin);
//        freopen("timber_output.txt", "w", stdout);
        int t=1;
        // cin>>t;
        for(int i=1;i<=t;i++){
//            cout<<"Case #"<<i<<": ";
            solve();
        }
        return 0;

        }



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

int main() {
  string S;
  string T;
  cin >> S >> T;

  int L = S.size();

  for (int i = 0; i < L; i++) {
    string rotation = "";
    for (int j = i; j < i + L; j++) {
      rotation.push_back(S.at(j % L));
    }
    if (rotation == T) {
      printf("Yes");
      return 0;
    }
  }

  printf("No");
  return 0;
}


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


// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef complex<int> ci;
typedef complex<double> cd;
typedef complex<long double> cld;

// macros
#define rep(i, a, b) for(int i=a; i<b; i++)
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define tr(c, it) for(auto it=(c).begin(); it!=c.end(); it++)
#define pb push_back
#define mp make_pair
#define bitcount __builtin_popcount
#define ispresent(c, x) ((c).find(x) != (c).end())
#define watch(x) cout<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// template functions
template <typename T>
inline void printV(vector<T>& a) { rep(i, 0, sz(a)) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printV(vector<T>& a, int n) { rep(i, 0, n) { cout<<a[i]<<" "; } cout<<"\n"; }
template <typename T>
inline void printVV(vector<vector<T>>& a)
{
	rep(i, 0, sz(a)) {
		printV(a[i]);
	}
	cout<<"\n";
}

template <typename T>
inline void clearVV(vector<vector<T>>& a)
{
	for(auto& x:a) {
		x.clear();
	}
	a.clear();
}
template <typename T>
inline void assignVV(vector<vector<T>> &a, T val)
{
	for(int i=0; i<sz(a); i++) {
		for(int j=0; j<sz(a[i]); j++) {
			a[i][j]=val;
		}
	}
}


// constants
const long double eps = 1e-9;
const int inf = 5e8;
const int modn = 1e9+7;
const int MAX = 1e5;

typedef long double ld;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
    cout<<fixed<<setprecision(10);
	int n;
	cin>>n;
	vector<ld> p(n);
	rep(i,0, n) cin>>p[i];
	vector<vector<ld>> dp(n, vector<ld>(n));
	assignVV(dp, (ld)-1);
	
	function<ld(int, int)> solve=[&](int i, int no)
	{
		if(i==n-1) {
			if(no==0) return 1-p[i];
			else if(no<0) return (ld)0;
			else return (ld)1;
		}
		if(no<0) return (ld)0;
		//~ if(no>=n-i+1) return (ld)1;
		
		if(fabs(dp[i][no]+1)>eps) return dp[i][no];
		ld &memo=dp[i][no];
		memo=p[i]*solve(i+1, no-1);
		memo+=(1-p[i])*solve(i+1, no);
		return memo;
	};
	cout<<1-solve(0, n/2)<<"\n";
	//~ printVV(dp);
    return 0;
}



Measured memory_bytes: 141312
#include <iostream>
#include <string>
using namespace std;
 
int main() {
  int N,max;
  cin >> N >> max;
  int min = 99999;
  int sum = 0;
  int count = 0;
  for(int i = 0;i < N ;i++){
    int a; 
    cin >> a;
    sum += a;
    if(min > a) min = a;
  }
  count = N;
  max -= sum;
  while(max > 0){
    max -= min;
    if(max < 0) break;
    ++count;
  }
  cout << count << endl;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int N, K;
    cin >> N >> K;
    
    vec<int> p(N);
    rep(i, N) cin >> p[i];
    sort(all(p));
    int ans = 0;
    rep(i,K) ans+=p[i];
    cout << ans << endl;
}


Measured memory_bytes: 3600
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <limits>
#include <memory>
#include <queue>
#include <sstream>
#include <string>
#include <map>
#include <vector>
using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) static_cast<int>((a).size())
#define fillchar(a, x) memset(a, x, sizeof(a))
#define rep(i, a, b) for(int i=int(a); i<=int(b); ++i)
#define irep(i, a, b) for(int i=int(a); i>=int(b); --i)
#define replr(i, a, b) rep(i, a, (b)-1)
#define reprl(i, a, b) irep(i, (b)-1, a)
#define repn(i, n) rep(i, 0, (n)-1)
#define irepn(i, n) irep(i, (n)-1, 0)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<string> VS;
template<class T, class S> ostream& operator<<(ostream& os, const pair<T, S>& v) { return os<<"("<<v.first<<", "<<v.second<<")"; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v) { os<<"["; repn(i, sz(v)) { if(i) os<<", "; os<<v[i]; } return os<<"]"; }
template<class T> bool setmax(T &_a, T _b) { if(_b>_a) { _a=_b; return true; } return false; }
template<class T> bool setmin(T &_a, T _b) { if(_b<_a) { _a=_b; return true; } return false; }
template<class T> T gcd(T _a, T _b) { return _b==0?_a:gcd(_b,_a%_b); }

int solve(const vector<VPI> es, int st, int en) {
    const int n=sz(es);
    vector<bool> vis(n, false);
    VI cur;
    cur.pb(st), vis[st]=true;
    for(int ans=0; !cur.empty(); ++ans) {
        for(int i=0; i<sz(cur); ++i) {
            const int x=cur[i];
            for(const auto& e: es[x]) if(e.se==0) {
                if(!vis[e.fi]) {
                    vis[e.fi]=true;
                    cur.pb(e.fi);
                }
            }
        }
        if(vis[en]) return ans;
        VI tmp;
        for(int i=0; i<sz(cur); ++i) {
            const int x=cur[i];
            for(const auto& e: es[x]) if(e.se==1) {
                if(!vis[e.fi]) {
                    vis[e.fi]=true;
                    tmp.pb(e.fi);
                }
            }
        }
        cur=tmp;
    }
    return -1;
}

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

    int n, m; cin>>n>>m;
    vector<VPI> es(n+m);
    map<PII, VI> shares;
    repn(i, m) {
        int a, b, c; cin>>a>>b>>c;
        --a, --b;
        es[a].pb(mp(n+i, 1));
        es[b].pb(mp(n+i, 1));
        es[n+i].pb(mp(a, 0));
        es[n+i].pb(mp(b, 0));
        shares[mp(a, c)].pb(i);
        shares[mp(b, c)].pb(i);
    }
    for(const auto& kv: shares) {
        int i=-1;
        for(int j: kv.se) {
            if(i>=0) {
                es[n+i].pb(mp(n+j, 0));
                es[n+j].pb(mp(n+i, 0));
            }
            i=j;
        }
    }
    int ans=solve(es, 0, n-1);
    cout<<ans<<endl;


    return 0;
}


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

using namespace std;

using ll=long long;

int main(void){
	int a,b;
	cin >> a >> b;

	if(a==1) a+=13;
	if(b==1) b+=13;
	
	if(a>b)
		cout << "Alice" << endl;
	else if(a<b)
		cout << "Bob" << endl;
	else
		cout << "Draw" << endl;
	
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,k;
char s[125252];

int main(){
  scanf("%d%d",&n,&k);
  scanf("%s",s);
  int ok = 1, ng = n+1;
  while(abs(ok-ng)>1){
    int x = (ok+ng)/2;
    bool go = false;
    int sw = 0;
    FOR(i,1,x)if(s[i]!=s[i-1])sw++;
    FOR(i,x,n+1){
      int t = sw;
      if(s[i-x]=='0')t++;
      if(s[i-1]=='0')t++;
      if(t/2 <= k){
        go = true;break;
      }
      if(s[i-x+1]!=s[i-x])sw--;
      if(i<n && s[i-1]!=s[i])sw++;
    }
    (go ? ok : ng) = x;
  }
  printf("%d\n",ok);
  return 0;
}


Measured memory_bytes: 384
import scala.io.StdIn._
object Main extends App {
  readInt
  val as = readLine.split(" ").map(_.toLong)
  val bs = 0L +: readLine.split(" ").map(_.toLong)

  val (_, sum) = as.zip(bs).foldRight((0L, 0L)){case ((a, b), (pre, sum)) =>
    if (a < pre) (b, sum + a)
    else if (a - pre < b) (b - (a - pre), sum + a)
    else (0L, sum + pre + b)
  }

  println(sum)
}

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

int main(){
    int N;
    vector<int> ans;
    string s,t;
    int sl,tl;
    int n;
    bool ire=true;

    cin>>N>>s>>t;
    sl=s.length();
    tl=t.length();
    n=(sl!=tl) ? min(sl,tl) : sl;
    for(int i=0; i<n; i++){
        if(n==tl){
            if(s.substr(sl-n+i,sl)==t.substr(0,n-i)){
                ans.push_back(sl+tl-(n-i));
                ire=false;
            }
        }
        if(n==sl){
            if(s.substr(i,n)==t.substr(0,n-i)){
                ans.push_back(sl+tl-(n-i));
                ire=false;
            }
        }
    }

    for(int i=0; i<ans.size(); i++){
        if(ans[i]>=N){
            cout<<ans[i]<<endl;
            break;
        }
    }
    if(ire){
        cout<<tl+sl<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

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

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

    vector<int> tmp(n+1, 0);
    vector<vector<int>> dp(n+1, tmp);

    int res = 0;

    rep2(i, 1, n+1){
        rep2(j, 1, n+1){
            if(s[i-1]==s[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                res = max(res, min(dp[i][j], j-i));
            }
        }
    }

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

Measured memory_bytes: 101136
/*
https://t.me/unstoppabIesoIvemachinechannel
*/
#pragma ARCENIY_KIRILLOV_POVELITEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
//#pragma GCC target("popcnt")
//#pragma GCC target("sse4")
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(),a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;




const int maxn = 303;
const int INF = 1e18;
int d[maxn][maxn];
int ans[maxn][maxn];
signed main(){
    int n, m, L;
    cin >> n >> m >> L;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            d[i][j] = INF;
            ans[i][j] = INF;
        }
        d[i][i] = 0;
        ans[i][i] = 0;
    }
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        d[a][b] = min(d[a][b],c);
        d[b][a] = min(d[b][a],c);
    }
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
                if (d[i][j] <= L)
            ans[i][j] = min(ans[i][j], 1ll);
        }
    }
    for (int k = 0; k < n; k++){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                ans[i][j] = min(ans[i][j], ans[i][k] + ans[k][j]);
            }
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int s, t;
        cin >> s >> t;
        s--, t--;
        if (ans[s][t] == INF) cout << -1 << '\n';
        else cout << ans[s][t] - 1 << '\n';
    }
}


Measured memory_bytes: 1920
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric> // accumulate
#include <queue>
#include <string>
#include <cmath> // sqrt
using namespace std;
typedef long long ll;
const int INF = 1e9;

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r-l > 1) {
                lazy[2*k+1] += lazy[k];
                lazy[2*k+2] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    ll getmin(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return INF;
        if(a <= l && r <= b) return node[k];
        ll vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }

};
 
int main() {
    int n, q;
    cin >> n >> q;
    LazySegmentTree seg(vector<ll> (n, 0));

    for (int i = 0; i < q; i++) {
        int type, left, right;
        cin >> type >> left >> right;
        if (type == 0) {
            int val;
            cin >> val;
            seg.add(left, right+1, val);
        }
        else {
            cout << seg.getmin(left, right+1) << endl;
        }

    }

}


Measured memory_bytes: 7596
n,m=map(int,input().split())
l=[]
def nibutan(x,l):
    low=0
    high=len(l)-1
    while low<=high:
      mid=(low+high)//2
      guess=l[mid]
      if guess==x:
         return True
      elif guess>x:
          high=mid-1
      elif guess<x:
          low=mid+1
    return False
if m==0:
  pass
else:
  for i in range(m):
    l.append(int(input()))
l1=[0 for i in range(n+1)]
if 1 in l:
  l1[0]=0
else:
  l1[0]=1

if 2 in l:
  l1[1]=0
elif 1 in l:
  l1[1]=1
else:
  l1[1]=2

if n>=3:
  for i in range(3,n+1): 
    if nibutan(i,l):
      pass
    else:
      l1[i-1]=(l1[i-2]+l1[i-3])%(((10**9)+7))
print(l1[n-1])

Measured memory_bytes: 7856
def inc(x,y,xx,yy)
	return x == xx ? nil : (y-yy).round(6)/(x-xx).round(6)
end

gets.to_i.times do |i|
  x1,y1,x2,y2,x3,y3,x4,y4 = gets.split.map(&:to_f)
  puts inc(x1,y1,x2,y2) == inc(x3,y3,x4,y4) ? 'YES' : 'NO'
end

Measured memory_bytes: 8740
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int INF=(2e9);
const int maxv=100+10;
struct Edge
{
    int to,cap,cost,rev;
};
int V,E,F;
vector<Edge> g[maxv];
int d[maxv];
int prevv[maxv];
int preve[maxv];
void add_edge(int from,int to,int cap,int cost)
{
    g[from].push_back((Edge)
    {
        to,cap,cost,g[to].size()
    });
    g[to].push_back((Edge)
    {
        from,0,-cost,g[from].size()-1
    });
}
int min_cost(int s,int t,int f)
{
    int res=0;
    while(f>0)
    {
        fill(d,d+V,INF);
        d[s]=0;
        bool bUpdate=true;
        while(bUpdate)
        {

            bUpdate=false;
            for(int i=0; i<V; i++)
            {
                if(d[i]==INF) continue;
                for(int j=0; j<g[i].size(); j++)
                {
                    Edge &e=g[i][j];
                    if(e.cap>0&&d[e.to]>d[i]+e.cost)
                    {
                        d[e.to]=d[i]+e.cost;
                        prevv[e.to]=i;
                        preve[e.to]=j;
                        bUpdate=true;
                    }
                }
            }
        }
        if(d[t]==INF ) return -1;
        int md=f;
        for(int i=t; i!=s; i=prevv[i])
        {
            Edge &e=g[prevv[i]][preve[i]];
            md=min(md,e.cap);
        }
        f-=md;
        res+=md*d[t];
        for(int i=t; i!=s; i=prevv[i])
        {
            Edge &e=g[prevv[i]][preve[i]];
            e.cap-=md;
            g[e.to][e.rev].cap+=md;
        }
    }
    return res;
}

int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&V,&E,&F);
    int u,v,cap,cost;
    for(int i=0; i<E; i++)
    {
        scanf("%d%d%d%d",&u,&v,&cap,&cost);
        add_edge(u,v,cap,cost);
    }
    printf("%d\n",min_cost(0,V-1,F));
    return 0;
}

Measured memory_bytes: 3292
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll A, B, C, D;
bool flag = false;

void solve(){
    D = C - A - B;

    if(D > 0 && 4*A*B < D*D) flag = true;

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

}

int main(){
    cin >> A >> B >> C;

    solve();
}


Measured memory_bytes: 256
import numpy as np
n=int(input())

ans=0

for k in range(n+1):
    if k%2==1:
        count=0
        m=int(np.sqrt(k)+1)
        for i in range(m):
            a=i+1
            if(k%a==0):
                count+=1
        if count==4:
            ans+=1

print(ans)


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define RREP(i,s,n) for(lli i=s;i>=n;i--)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)

lli data[60][60];

signed main(){

	lli h,w;
	cin>>h>>w;

	REP(i,0,h)REP(j,0,w){
		char c;
		cin>>c;
		if(c=='#')data[i][j]=1;
	}

	REP(i,0,h)REP(j,0,w){
		if(!data[i][j])continue;
		bool ok = false;
		REP(k,0,4){
			lli dx[4]={-1,0,1,0};
			lli dy[4]={0,1,0,-1};
			lli nextY = i+dy[k];
			lli nextX = j+dx[k];
			if(nextY<0 || nextY >= h || nextX <0 || nextX >= w)continue;
			ok |= (data[nextY][nextX])?true:false;
		}
		if(!ok){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;

	return 0;
}

Measured memory_bytes: 256
// Flipping Signs 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    ll m=0;;
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    ll mn=abs(a[0]);
    ll sum=0;
    for(int i=0; i<n; i++){
        if(a[i]<0){m++;}
        sum+=abs(a[i]);
        mn=min(abs(a[i]), mn);
    }
    if(m%2==0){
        cout << sum << endl;
        return 0;
    }
    else{
        cout << sum-(mn*2) << endl;
        return 0;
    }

}

Measured memory_bytes: 1024
N, K , Q = (int(i) for i in input().split())
A = [int(input()) for i in range(Q)]

point = [0] * N

for i in A:
    point[i - 1] = point[i - 1] + 1

point1 = []
for p in point:
    point1.append(K - (Q - p))

for p in point1:
    if p <= 0:
        print('No')
    else:
        print('Yes')

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

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPul(i, n) for (ull i = 0; i < (ull)(n); i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define REPRl(i, n) for(ll i = n; i >= 0; i--)
#define REPRul(i, n) for(ull i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < (int)n; i++)
#define FORl(i, m, n) for(ll i = m; i < (ll)n; i++)
#define FORul(i, m, n) for(ull i = m; i < (ull)n; i++)
#define ALL(v) v.begin(), v.end()
ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}

map<ll,ll> fList;

ll f(ll x){
  if(fList.find(x)==fList.end()){
    if(x==-1){
      fList[-1]=0;
    }else if(x==0){
      fList[0]=1;
    }else{
      ll x_1=f(x-1);
      ll x_2=f(x-2);
      fList[x]=(x_1+x_2)%1000000007;
    }
  }
  return fList[x];
}

int main() {
  ll n,m;cin>>n>>m;
  vector<ll> a(m+2);
  a[0]=-1;
  FORl(i,1,m+1){
    ll b;cin>>b;
    a[i]=b;
  }
  a[m+1]=n+1;
  
  ll ans=1;
  REPl(i,m+1){
    ll tmp=f(a[i+1]-a[i]-2);
    ans*=tmp;
    ans%=1000000007;
  }
  cout << ans << endl;
}

Measured memory_bytes: 14336
gets
a,t,d=1
gets.split.map(&:to_i).tap{|e|t=e.shift}.each{|i|
  next if t==i
  if !d
    d=t<=>i
  elsif d!=z=(t<=>i)
    a+=1
    d=nil
  end
  t=i
}
p a

Measured memory_bytes: 8452