akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define fo(i,n)         for(i=0;i<n;i++)
#define Fo(i,k,n)       for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x)          cout << #x << "=" << x << endl
#define deb2(x, y)      cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int N = 3e5, M = N;
//=======================

vi g[N];

void solve() {
	int i, j, n, m;
	string s, t;
	cin >> s >> t;
	n = s.length();
	m = t.length();
	int ans = INT_MAX;
	fo(i, n - m + 1) {
		int cur = 0;
		// deb(i);
		fo(j, m) {
			if (t[j] != s[i + j]) cur++;
		}
		// deb(cur);
		ans = min(ans, cur);
	}
	cout << ans << "\n";
}

int32_t main()
{
	FIO;
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif
	solve();
	return 0;
}

void ipgraph(int n, int m) {
	int i, u, v;
	while (m--) {
		cin >> u >> v;
		u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
}

void dfs(int u, int par) {
	for (int v : g[u]) {
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 10696
def doc_string():
    """
    I can fly.
    """

list = []
stack = []
if __name__ == "__main__":
    list = raw_input().split()

    for var in list:
        try:
            stack.append(int(var))
        except:
            if var == "+":
                a = stack.pop()
                b = stack.pop()
                stack.append(b + a)
            if var == "-":
                a = stack.pop()
                b = stack.pop()
                stack.append(b - a)
            if var == "*":
                a = stack.pop()
                b = stack.pop()
                stack.append(b * a)

    print stack.pop()

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

int main(){
  int N, K;
  cin >> N >> K;
  
  vector<int> x(N);
  rep(i, N) cin >> x[i];
  
  int res = 0;
  rep(i, N){ 
    if(x[i] < (abs(K - x[i]))) res += 2 * x[i];
    else res += 2 * (abs(K - x[i]));
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define rep(i,n)for(urs(n)i=0;i<(n);++i

int main(){
	
int a,b,c,d;

cin >> a >> b >> c >> d;

while (a>0&&c>0){
    c=c-b;
    if(c<=0){Yes(); return 0;}
    a= a-d;
    if(a<=0){No(); return 0;}

    //cout << "a;  "  << a << "c:     " << c << endl;
}
if(a>c)
Yes();
else No();

    return 0;

}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define ll long long

using namespace std;

int main(){

    int n,m;
    cin >> n >> m;

    vector<ll> a;
    vector<pair<ll,int>> cb;

    REP(i,n){
        ll tmp;
        cin >> tmp;
        a.push_back(tmp);
    }

    REP(i,m){
        int tmpb;
        ll tmpc;
        cin >> tmpb >> tmpc;
        cb.push_back(make_pair(tmpc,tmpb));
    }

    sort(ALL(a));
    sort(ALL(cb),greater<pair<ll,int>>());

    int cbi = 0;
    int cbr = cb[0].second;
    ll sum = 0;

    REP(i,n){
        if(cbr == 0){
            cbi++;
            if(cbi == cb.size()) break;
            cbr = cb[cbi].second;
        }

        if(a[i] >= cb[cbi].first){
            break;
        }else{

            a[i] = cb[cbi].first;
            cbr--;
        }
    }

    REP(i,n){
        sum += a[i];
    }

    cout << sum << endl;

 
    return 0;
}

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

#define N 8

int main(void){
  int i, j, k, n, max, min;
  char tmp, num[N+1];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%s", num);
    for(j = N-1; j > 0; j--){
      for(k = 0; k < j; k++){
	if(num[k]-'0' > num[k+1]-'0'){
	  tmp = num[k];
	  num[k] = num[k+1];
	  num[k+1] = tmp;
	}
      }
    }
    min = atoi(num);
    for(j = 0; j < N/2; j++){
      tmp = num[j];
      num[j] = num[N-1-j];
      num[N-1-j] = tmp;
    }
    max = atoi(num);
    printf("%d\n", max-min);
  }
  return 0;
}

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

using namespace std;
#define ll long long
const int N=2e5+5;
int ans[N];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    string s;
    cin>>s;
    int n=(int)s.size();
    for(int i=0;i<n;)
    {
        int e=0,o=0;
        while(s[i]=='R')
        {
            if(i%2==0) e++;
            else o++;
            i++;
        }
        int x=i-1;
        while(s[i]=='L')
        {
            if(i%2==0) e++;
            else o++;
            i++;
        }
        if(x%2==0)
        {
            ans[x]=e;
            ans[x+1]=o;
        }
        else
        {
            ans[x]=o;
            ans[x+1]=e;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(i) cout<<" ";
        cout<<ans[i];
    }
    return 0;
}


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

int main() {
  int ans=0;
  string s;
  cin>>s;
  rep(i,0,4){
    if(s[i]=='-'){
      ans--;
    }
    else{
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3612
import glob
import bisect

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\166\\D'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def calc(self, num):
        if num < 2:
            return 0
        return num * (num-1) / 2

    def resolve(self):

        X = int(self.input_data())

        squares = [0]*401
        for i in range(0,401):
            squares[i] = (i-200) ** 5

        finish = False
        for i in range (1,401):
            for j in range(0,400):
                if squares[i] - squares[j] == X:
                    print(str(i-200) + ' ' + str(j-200))
                    finish = True
                    break
            if finish:
                break


solver = Solver(REL_PATH)
solver.exec_resolve()


Measured memory_bytes: 9884
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

for line in stdin:
    L = [int(s) for s in line.split(',')]
    cross_over = L[10] * sum(L[:10]) / (L[10] + L[11])
    d = 0
    for i, xi in enumerate(L[:10]):
        d += xi
        if cross_over <= d:
            break
    print(i+1)

Measured memory_bytes: 4264
#include <iostream>
#include <vector>

const int INF = 1e9;

void print(std::vector<int> readVec){
    int sz = readVec.size();
    std::cout << "---" << std::endl;
    for(int i = 0; i < sz; ++i){
        std::cout << readVec.at(i) << std::endl;
    }
}

int main(){
    int n, k;
    std::cin >> n >> k;

    std::vector<int> h(n);
    for(int i = 0; i < n; ++i){
        std::cin >> h.at(i);
    }

    std::vector<int> dp(n, INF);
    dp.at(0) = 0;
    dp.at(1) = std::abs(h.at(1) - h.at(0));
    for(int i = 2; i < n; ++i){
        int limit = std::min(i, k);
        for(int j = 1; j <= limit; ++j){
            dp.at(i) = std::min(dp.at(i), dp.at(i - j) + std::abs(h.at(i) - h.at(i - j)));
        }
    }

    std::cout << dp.at(n - 1) << std::endl;

    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <numeric>
#include <string>
#include <bitset>
#include <functional>

using ld = long double;
using vld = std::vector<ld>;
using vvld = std::vector<vld>;
using vvvld = std::vector<vvld>;
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using str = std::string;
using vstr = std::vector<str>;

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

constexpr ld PI = 3.141592653589793L;
constexpr ld EPS = std::numeric_limits<ld>::epsilon();

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }
bool is_prime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

/*------------------------------------------------------------------------*/

const vll dy = { -1, 0, 1, 0 }, dx = { 0, 1, 0, -1 };

void solve();

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

    solve();
}

void solve() {
    ll h, w;
    std::cin >> h >> w;

    vstr s(h);
    for (ll i = 0; i < h; i++)
        std::cin >> s[i];

    auto bfs = [&](ll sy, ll sx, ll gy, ll gx) {
        vvll dist(h, vll(w, -1)); dist[sy][sx] = 1;
        std::queue<pll> que; que.push({ sy, sx });

        while (!que.empty()) {
            pll p = que.front(); que.pop();
            ll cy = p.first, cx = p.second;
            for (ll i = 0; i < 4; i++) {
                ll ny = cy + dy[i], nx = cx + dx[i];
                if (0 <= ny && ny < h && 0 <= nx && nx < w
                    && s[ny][nx] == '.' && dist[ny][nx] == -1) {
                    dist[ny][nx] = dist[cy][cx] + 1;
                    que.push({ ny, nx });
                }
            }
        }

        return dist[gy][gx];
    };

    ll dist = bfs(0, 0, h - 1, w - 1);

    if (dist == -1) { std::cout << -1 << '\n'; return; }

    ll ans = -dist;
    for (ll i = 0; i < h; i++) for (ll j = 0; j < w; j++)
        ans += s[i][j] == '.';

    std::cout << ans << '\n';
}


Measured memory_bytes: 3656
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
     
using namespace std;
     
#define EPS 10e-9
     
struct vertex {
    long long int c[3];
};
     
struct sphere {
    vertex v;
    long long int l;
    long double r;
};
     
#define vect vertex
     
long double norm( vect v ) {
    long double sum = 0.0;
    for( int i = 0; i < 3; i++ )
    	sum += v.c[i] * v.c[i];
    return sum;
}
     
int main(void){
    int N, Q;
    cin >> N >> Q;
     
    vector< sphere > obstacle( N );
    vector< vertex > red( Q );
    vector< vertex > blue( Q );
     
    for( int i = 0; i < N; i++ ) {
    	for( int j = 0; j < 3; j++ )
    		cin >> obstacle[i].v.c[j];
    	cin >> obstacle[i].r;
    	cin >> obstacle[i].l;
    }
    for( int i = 0; i < Q; i++ ) {
    	for( int j = 0; j < 3; j++ )
    		cin >> red[i].c[j];
    	for( int j = 0; j < 3; j++ )
    		cin >> blue[i].c[j];
    		
    }
     
    //赤いオブジェと青いオブジェを結ぶ線分と障害物の中心との距離が障害物の半径より小さいかどうかを調べればよい
     
    for( int i = 0; i < Q; i++ ) {
    	long long int sum = 0;
		vect v;
	    for( int j = 0; j < 3; j++ )
			v.c[j] = blue[i].c[j] - red[i].c[j];
    	for( int j = 0; j < N; j++ ) {
			if( norm( v ) > EPS ) {
    			long double t = 0.0;
    			for( int k = 0; k < 3; k++ )
    				t += v.c[k] * ( obstacle[j].v.c[k] - red[i].c[k] );
    			t /= norm( v );
    			long double dist = 0.0;
    			for( int k = 0; k < 3; k++ ) {
    				long double ld = red[i].c[k] + t * ( long double ) ( v.c[k] ) - obstacle[j].v.c[k];
    				dist += ld * ld;
    			}		
    			dist = sqrt( dist );
				long double distr = 0.0, distb = 0.0;
				for( int k = 0; k < 3; k++ ) {
					distr += ( red[i].c[k] - obstacle[j].v.c[k] ) * ( red[i].c[k] - obstacle[j].v.c[k] );
					distb += ( blue[i].c[k] - obstacle[j].v.c[k] ) * ( blue[i].c[k] - obstacle[j].v.c[k] );
				}
				if( t < EPS ) dist = sqrt( distr );
				if( t > 1 + EPS ) dist = sqrt( distb );
    			if( dist <= obstacle[j].r + EPS )
    				sum += obstacle[j].l;
			} else {
			}
    	}
    	cout << sum << endl;

    }
    return 0;
}

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

int main(){
  double a,b,h;
  cin >> a >>  b >> h;
  cout << (a+b)*h/2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

struct Stuple {
    int s; int t; int c;
    using type = tuple<int, int, int>;
    Stuple(int s, int t, int c): s(s), t(t), c(c){ }
    operator tuple<int, int, int> () const { return make_tuple(s, t, c); }
    // bool operator < (const Stuple& e) const { return type(*this) < type(e); }
    // ostream& operator >> (ostream& out) const { prints(type(*this)); return out; }
    bool operator < (const Stuple& e) const { return tie(s, t, c) < tie(e.s, e.t, e.c); }
    ostream& operator >> (ostream& out) const { prints(tie(s, t, c)); return out; }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, c;
    cin >> n >> c;
    // set<tuple<int, int, int>> stcs;
    set<Stuple> stcs;
    for(int i = 0; i < n; i++){
        int s, t, c;
        cin >> s >> t >> c;
        stcs.emplace(s, t, c);
    }
    int ans = 0;
    prints(stcs);
    while(stcs.size()){
        ans++;
        auto next = stcs;
        int time = -1, channel = -1;
        for(auto& stc : stcs){
            // if(time + (channel != get<2>(stc)) <= get<0>(stc)){
            //     time = get<1>(stc);
            //     channel = get<2>(stc);
            //     next.erase(stc);
            // }
            // get<0>(stc.data) = 1;
            // decltype(auto) a = get<0>(stc.data);
            // a = 1;
            // stc.t = 1;
            if(time + (channel != stc.c) <= stc.s){
                time = stc.t;
                channel = stc.c;
                next.erase(stc);
            }
        }
        next.swap(stcs);
    }
    cout << ans << '\n';
}


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

int main(){
  int a, b, c, d;

  scanf("%d %d %d %d", &a, &b, &c, &d);

  if(abs(a-c)<=d){
    cout << "Yes";
  } else if (abs(a-c)>d && abs(a-b)<=d && abs(b-c)<=d){
    cout << "Yes";
  } else{
    cout << "No";
  }
}


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

#define int long long
#define double long double
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
#define lb(v, z) lower_bound(all(v), z)
#define ub(v, z) upper_bound(all(v), z)
#define fill(a, z) memset(a, z, sizeof(a))
#define rep(i, a, b) for (i = (a); i <= (b); i++)
#define rdp(i, a, b) for (i = (a); i >= (b); i--)
#define cns(z) cout << z << ' '
#define cnl(z) cout << z << '\n'
#define M 1000000007
#define M2 998244353
#define endl "\n"
#define iip(t) \
	int t;     \
	cin >> t;
#define iip2(a, b) \
	int a, b;      \
	cin >> a >> b;
#define dip(a) \
	double a;  \
	cin >> a;
#define dip2(a, b) \
	double a, b;   \
	cin >> a >> b;
#define garr(ip)       \
	for (auto &x : ip) \
		cin >> x;
#define parr(ip)          \
	for (auto &x : ip)    \
		cout << x << " "; \
	cout << endl;
#define test   \
	int _t;    \
	cin >> _t; \
	while (_t--)

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

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	iip2(n,m);
	cout << min(n%m, abs(n%m-m)) << endl;
}

Measured memory_bytes: 256
-- Watch
import Data.List -- intercalate

main = readLn >>= putStrLn . solve

solve :: Int -> String
solve = intercalate ":" . map show . watch

watch :: Int -> [Int]
watch n = [h,m,s]
  where
    h = div n 3600
    m = mod (div n 60) 60
    s = mod n 60

-- import Data.List
-- intercalate :: [a] -> [[a]] -> [a]
-- intercalate xs xss = concat $ intersperse xs xss

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(5);
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if(s[0]=='M'){
            a[0]++;
        }
        if(s[0]=='A'){
            a[1]++;
        }
        if(s[0]=='R'){
            a[2]++;
        }
        if(s[0]=='C'){
            a[3]++;
        }
        if(s[0]=='H'){
            a[4]++;
        }
    }

    ll ans=0;
    for(int i = 0; i < 3; i++) {
        for(int j = i+1; j < 4; j++) {
            for(int k = j+1; k < 5; k++) {
                ans += a[i]*a[j]*a[k];
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3608
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define _CRT_SECURE_NO_WARNINGS
#define REP(i, n) for(int i=0; i<n; i++)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define ALL(x) (x).begin(),(x).end()
#define INF 999999999

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

int main() {
	int n, a, b;
	cin >> n;
	if (n == 1)puts("Hello World");
	if (n == 2) {
		cin >> a >> b;
		cout << a + b << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  char a[n];
  cin>>a;
  int i;
      int s=1;
  if(n==1)
    cout<<1;
  else
  {

    for(i=0;i<=n-2;i++)
    {
      if(a[i]!=a[i+1])
        s++;
    }
    cout<<s;
  }
  
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>

int main() {
	int n;
	std::cin >> n;
	std::vector<int>a(n);
	std::vector<int>b(n);
	std::vector<int>c(n);
	for (int i = 0;i < n;i++) {
		std::cin >> a[i];
	}
	for (int i = 0;i < n;i++) {
		std::cin >> b[i];
	}
	for (int i = 0;i < n;i++) {
		std::cin >> c[i];
	}
	std::sort(a.begin(), a.end());
	std::sort(c.begin(), c.end());
	long long int ans = 0;
	for (int i = 0;i < n;i++) {
		long long int d = std::lower_bound(a.begin(), a.end(), b[i])-a.begin();
		long long int e = c.end() - std::upper_bound(c.begin(), c.end(), b[i]);
		ans += d*e;
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<algorithm>
#define maxn 100005
using namespace std;
int n,ma[maxn];
struct node { int v; node *nxt; } edge[maxn*2],*head[maxn],*ncnt;
void addedge(int u,int v)
{
	ncnt++;
	ncnt->v=v,ncnt->nxt=head[u];
	head[u]=ncnt;
}
void dfs(int u,int fa)
{
	for(node *p=head[u];p;p=p->nxt)
	{
		int v=p->v;
		if(v==fa) continue;
		dfs(v,u);
		if(!ma[v])
		{
			if(ma[u]) { printf("First\n"); exit(0); }
			ma[u]=v,ma[v]=u;
		}
	}
}
int main()
{
	ncnt=&edge[0];
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v); addedge(v,u);
	}
	dfs(1,0);
	printf("%s\n",ma[1]?"Second":"First");
}

Measured memory_bytes: 4480
def is_acgt(s):
    for char in s_sub:
        if char not in {'A', 'T', 'G', 'C'}:
            return False
    return True

S = input()
length = len(S)
ans = 0
for i in range(length):
    for j in range(i + 1, length + 1):
        s_sub = S[i:j]
        if is_acgt(s_sub):
            ans = max(ans, len(s_sub))

print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <numeric>
#include <iterator>
using namespace std;

namespace {

}

int main()
{
	//vector<int> a(3);
	vector<vector<int>> a(3);

	for (int i = 0; i < 3; ++i){
		for (int j = 0; j < 3; ++j){
			int tmp;
			cin >> tmp;
			a[i].push_back(tmp);
			// cin >> a[i][j];
		}
	}

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i){
		int tmp;
		cin >> tmp;
		for (int i = 0; i < 3; ++i){
			for (int j = 0; j < 3; ++j){
				if (a[i][j] == tmp){
					a[i][j] = 0;
					goto out1;
				}
			}
		}
	out1:;
	}

	// 判定
	for (int i = 0; i < 3; i++){
		if ((a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0)
			|| (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0))
		{
			cout << "Yes" << endl;
			return 0;
		}

	}

	if ((a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0)
		|| (a[2][0] == 0 && a[1][1] == 0 && a[0][2] == 0))
	{
		cout << "Yes" << endl;
		return 0;
	}

	cout << "No" << endl;


	return 0;
}


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

using namespace std;

int main(){

    string s;
    cin >> s;
    
    for(int i=0;i<s.size();){
        if(s.substr(i,7) == "dreamer" && s.substr(i+5,5) != "erase")
            i += 7;
        else if(s.substr(i,6) == "eraser")
            i += 6;
        else if(s.substr(i,5) == "erase")
            i += 5;
        else if(s.substr(i,5) == "dream")
            i += 5;
        else {
            cout << "NO" << endl;
            return 0;
        }
    }

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

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

using namespace std;

int main(){
	string s1,s2,s3;
	cin >> s1 >> s2 >> s3;
	cout << (char)((char)s1[0] - 'a' + 'A');
	cout << (char)((char)s2[0] - 'a' + 'A');
	cout << (char)((char)s3[0] - 'a' + 'A');
	cout << endl;
	
	return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n,m;cin >> n>>m;
    lint mod = 1000000007;
    vector<lint> v(n + 1);
    REP(i, m) {
        int a;
        cin >>a;
        v[a] = -1;
    }
    v[0] = 1;
    if(v[1]==0)
        v[1] = 1;
    FOR(i,2,n+1){
        if(v[i]==-1){
            continue;
        }
        if (v[i-1] != -1)
        {
            v[i]+=v[i-1];
        }
        if (v[i-2] != -1)
        {
            v[i] += v[i - 2];
        }
        v[i] %= mod;
    }

    REP(i,n+1){
        //cout << v[i] << " ";
    }

    //lint ans=0;

    cout << v[n] <<"\n";

    return 0;
}

Measured memory_bytes: 1024
MIN = -119
MAX = 120
def calc(A, B):
    return A**5 - B**5

def main():
    X = int(input())
    for i in range(MIN, MAX+1, 1):
        for j in range(MIN, MAX+1, 1):
            if(X == calc(i, j)):
                print(*(i, j))
                return
main()

Measured memory_bytes: 64148
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


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

	map<string, int>mp;
	int N;
	cin >> N;
	int mx = -1;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		mp[S]++;
		mx = max(mx,mp[S]);
	}

	set<string>st;
	fore(x, mp) {
		if (x.second == mx)st.insert(x.first);
	}
	fore(x, st)puts(x);


	return 0;
}

Measured memory_bytes: 33280
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main(void){
    int n;

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

    sort(d.begin(), d.end());
    
    int ans = d[d.size()/2] - d[d.size()/2 - 1];

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

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
//define
#define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define Rep(x,y) for(int k=x;k<y;k++)
#define str string
#define vint vector<int>
#define vvint vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vool vector<bool>
#define vtr vector<str>
#define vvtr vector<vector<str>>
#define pb() push_back()
#define elif else if
#define all(x) x.begin(),x.end()
//function
int shizuku(int);
//UnionFind
struct UnionFind{
  vint par;
  UnionFind(int N):par(N){
    rep(0,N)par[i]=i;
  }
  int root(int x){
    if(par[x]==x)return x;
    return par[x]=root(par[x]);
  }
  void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)return;
    par[rx]=ry;
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
};

signed main(){
    int pow,D,G,N,M,X,count=0,count2=0;
    double d;
    int C='A'-'a';
    char op;
    str T;
    cin>>N>>M>>X;
    vint A(N);
    if(X-(N-M)<0)cout<<0<<endl;
    else cout<<X-(N-M)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 int main(){
   int n,m;
   cin>>n>>m;
   vector<int> lam(m);
   long long lili=0;
   rep(i,m){
   cin>>lam.at(i);
     lili+=lam.at(i);
   }
   if(lili>n)cout<<-1<<endl;
   else cout<<n-lili<<endl;
}


Measured memory_bytes: 3632
import heapq
N, M = map(int, input().split())
A = map(int, input().split())
AA = [-1 * x for x in A]
#print(AA)
heapq.heapify(AA)

for i in range(M):
  a = heapq.heappop(AA)
  #print(a, -a>>1)
  heapq.heappush(AA, -(-a >> 1))

print(-sum(AA))

Measured memory_bytes: 14180
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5 + 100;
int n;
int a[N];
int GCD(int a,int b) {
    if (b == 0) {
        return abs(a);
    }
    return GCD(b,a % b);
}
void nhap()
{
    cin >> n >> a[1];
    for (int i = 2; i <= n + 1; i++) {
        cin >> a[i];
    }
    sort(a + 1,a + 1 + n + 1);
}

void solve()
{
    int Res = 0;
    for (int i = 2; i <= n + 1; i++) {
        Res = GCD(Res,a[i] - a[i - 1]);
    }
    cout << Res;
}
int main()
{
    nhap();
    solve();
}


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

using namespace std;

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

/*素数判定*/
const int MAX = 1000100;
bool prime[MAX];

void sieve(){
	fill(prime, prime+MAX, true);
	prime[0] = prime[1] = false;

	for(int i=0; i < MAX; i++){
		if(!prime[i]) continue;
		for(int j=i+i; j < MAX; j += i){
			prime[j] = false;
		}
	}
}

int main(){
	int n, x;
	sieve();

	while(cin >> n >> x, n+x){
		bool b[1000100] = {false};
		vector<int> v(n);
		rep(i, n) cin >> v[i];

		b[0] = true;
		rep(i, n){
			for(int j=0; j <= x; j++){
				if(b[j] && v[i]+j <= x) b[v[i]+j] = true;
			}
		}
		int ret = -1;
		for(int i=0; i <= x; i++) if(b[i] && prime[i]) ret = i;
		if(ret == -1) cout << "NA" << endl;
		else cout << ret << endl;
	}
}

Measured memory_bytes: 3152
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

fun main(args: Array<String>) {
    val n = readInt()
    val a = readIntList()
    val pA = Array(n) { Pair(a[it], it) }
    pA.sortBy { it.first }
    println(pA.map { it.second+1 }.joinToString(separator = " "))
}

Measured memory_bytes: 86520
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    A,B = map(int, input().split())
    if A > 9 or B > 9:
        print(-1)
    else:
        print(A*B)

if __name__ == '__main__':
    main()

Measured memory_bytes: 4080
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pb push_back
using namespace std;
const int inf = 1<<30, maxn = 1<<19;
using ll = long long;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll n;
	cin >> n;
	ll ans = 0;
	for(ll d = 1; d <= n; d++)
		for(ll i = d; i <= n; i += d)
			ans += i;
	cout << ans;
	return 0;
}


Measured memory_bytes: 3632
H, W, K = map(int, input().split())
MOD, p, cnt = 10**9+7, [0]*W, 0
for bit in range(1<<(W-1)):
    s0 = bit&1
    flg=True
    for w in range(1, W-1):
        if (bit>>w)&1 and s0 == 1:flg=False; break
        s0 = (bit>>w)&1
    if flg:
        cnt += 1
        for w in range(W - 1):
            if (bit >> w)&1:p[w] += 1
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for h in range(H):
    for w in range(W):
        if w:
            dp[h+1][w-1] += dp[h][w]*p[w-1]
            dp[h+1][w-1] %= MOD
        if w-(W - 1):
            dp[h+1][w+1] += dp[h][w]*p[w]
            dp[h+1][w+1] %= MOD
        dp[h+1][w]+=dp[h][w]*(cnt-p[w-1]-p[w])
        dp[h+1][w]%=MOD
print(dp[H][K-1])

Measured memory_bytes: 63116
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


int dp[1010][1010];
int K = 1000000007;
int main(){
    char t[1010],b[1010];
    cin >> t >> b;
    int tlen = strlen(t);
    int blen = strlen(b);
    if(t[0] == b[0])dp[0][0] = 1;
    for(int i = 1;i < tlen;i++){
        dp[i][0] = dp[i-1][0];
        if(t[i] == b[0]){
            dp[i][0]++;
        }
    }
    for(int i = 1;i < tlen;i++){
        for(int j = 1;j < blen;j++){
            dp[i][j] = dp[i-1][j] % K; 
            if(t[i] == b[j]){
                dp[i][j] += dp[i-1][j-1] % K;
            }
            dp[i][j] %= K;
        }
    }
    cout << dp[tlen-1][blen-1] % K << endl;
}
    


Measured memory_bytes: 7016
//#define _CRT_SECURE_NO_WARNINGS
//#include <bits/stdc++.h>
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s; cin >> s;
	if (s == "ABC")cout << "ARC" << endl;
	else cout << "ABC" << endl;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 105
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
int n,a1,a2,ca,cb;
string a[M],b[M];
//???mamoru???, ???tameru???, ???kougekida??? ?????????????????§??????????????????????????????????????????????????????????????????????????????
int main()
{
	int ans1=0, ans2=0;
	a1=a2=0;
	ca=cb=0;
	RI(n);
	REP(i,1,n) cin>>a[i];
	REP(i,1,n) cin>>b[i];

	REP(i,1,n)
	{
		if(a[i]=="mamoru")
		{
			if(b[i]=="kougekida")
			{
				if(cb==5) a2++;
				if(cb==0) a1++;
				cb = 0;
			}
			else if(b[i]=="tameru")
				cb = min(cb+1, 5);
			
		}
		else if(a[i]=="tameru")
		{
			ca = min(ca+1, 5);
			
			if(b[i]=="kougekida")
			{
				if(cb>=1) a2++;
				if(cb==0) a1++;
				cb = 0;
			}
			else if(b[i]=="tameru")
				cb = min(cb+1, 5);
		}
		else //kougeki
		{
			if(b[i]=="kougekida")
			{
				if(ca>cb) a1++;
				if(ca<cb) a2++;
				ca = cb = 0;
			}
			else if(b[i]=="mamoru")
			{
				if(ca==0) a2++;
				if(ca==5) a1++;
				ca = 0;
			}
			else //tameru
			{
				if(ca==0) a2++;
				else a1++;
				cb = min(cb+1, 5);
			}
		}

		if(ans1+ans2==0 && a1+a2==1)
		{
			ans1 = a1;
			ans2 = a2;
		}
	}

	if(ans2) puts("Nakajima-kun");
	else if(ans1) puts("Isono-kun");
	else puts("Hikiwake-kun");
	return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
 
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);

    ll n,l;
    cin>>n>>l;
    ll a[n];
    ll sum = 0;
    for (int i = 0; i < n;i++){
        a[i] = l + i;
        sum += a[i];
    }
    ll b=1e9;
    for (int i = 0; i < n;i++){
        b = min(b, abs(a[i]));
    }
    for (int i = 0; i < n;i++){
        if(abs(a[i])==b){
            sum -= a[i];
            break;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<numeric>
#include<limits>
#include<map>
using namespace std;

#define rep(i,s,n) for(int i=s;i<n;i++)
#define dow(i,n,s) for(int i=n-1;i>=s;i--)
#define all(a) a.begin(),a.end()
#define rng(a,b,e) a.begin()+a,a.begin()+e
#define Sort(a) sort(a.begin(),a.end())
#define Qsort(a,size) qsort(a,size,sizeof(*a),compare_int)
typedef pair<int,int> II;
typedef pair<double,double> DD;
typedef pair<int,string> IS;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
bool compare_by_second(II a,II b) {
  if(a.second != b.second) return a.second < b.second;
  return a.first < b.first;
}
bool compare_int(const void *a,const void *b) { return *(int *)a - *(int *)b; }

const int INF = 1e+9;
const int MAX_R = 5e+2;
const int MAX_S = 5e+2;
const int MAX_P = 5e+5;

int r,s,p;
II goal;
bool flag;
vector<int> position;
vector<int> vtmp;

void solve();

int main() {

  cin>>r>>s>>p;
  goal.first = r+1; goal.second = s+1;
  int itmp1,itmp2;
  rep(i,0,p) {
    cin>>itmp1>>itmp2;
    if(itmp2>s) itmp2++;
    position.push_back(abs(goal.first-itmp1)+abs(goal.second-itmp2));
  }
  //rep(i,0,position.size()) cout<<position[i]<<endl;
  solve();

  return 0;
}

void solve() {
  /*
  flag = true;
  while(flag) {
    sort(all(position));
    vtmp = position;
    dow(i,position.size(),1) {
      if(position[i] == position[i-1]) vtmp[i]++;
    }
    position.clear();
    position = vtmp;
    vtmp.clear();

    rep(i,0,position.size()-1) flag &= (position[i] != position[i+1]);
    flag = !flag;

    cout<<boolalpha<<flag<<endl;
    cout<<"----position----"<<endl;
    rep(i,0,position.size()) cout<<position[i]<<endl;
  }
  */
  sort( all(position),greater<int>() );
  rep(i,0,position.size()) position[i]+=i;
  sort( all(position),greater<int>() );
  cout<<position[0]<<endl;
}



Measured memory_bytes: 4828
//AtCoder-2396
#include<cstdio>
#define ll long long
const int N=1e6+2,MOD=1e9+7;
int n,f[N],sum[N];
int main()
{
	f[1]=f[2]=f[0]=sum[0]=1;sum[1]=2;sum[2]=3;
	scanf("%d",&n);
	for(int i=3;i<=n;i++)
	{
		f[i]=f[i-1]+sum[i-3];
		f[i]-=f[i]>=MOD?MOD:0;
		sum[i]=sum[i-1]+f[i];
		sum[i]-=sum[i]>=MOD?MOD:0;
	}
	int ans=f[n];
	ans+=(ll)f[n-1]*(n-1)%MOD;
	ans-=ans>=MOD?MOD:0;
	for(int i=0;i<=n-2;i++)
	{
		ans+=(ll)f[i]*((ll)(n-1)*(n-1)%MOD+i+1)%MOD;
		ans-=ans>=MOD?MOD:0;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 7936
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
s = ns()
k = ni()


for i in s:
    if i == s[k-1]:
        print(i, end="")
    else:
        print("*", end="")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define ll long long
#define ld long double
#define mkp make_pair
#define sz(x) (int)x.size()
#define pi pair<long long, long long>
#define watch(x) cout << (#x) << " is " << (x) << endl; cout.flush()
#define endl '\n'
#define _ << ' '
#define min3(a, b, c) min(a, min(b, c))
#define min4(a, b, c, d) min(min(a, d), min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define max4(a, b, c, d) max(max(a, d), max(b, c))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> idxset;
//find_by_order(i) : iterator to the value at index i, order_of_key(x) : the index of value x
const ll mod = (ll)1e9+7;
const ll INF = (ll)1e9+1;

int q, l, r, pre[100001];
vector<int> p(100001, 1);

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
   // freopen("A.txt", "r", stdin);
    #endif
    p[0] = p[1] = 0;
    for(int i=2; i*i<=100000; i++)
    {
        if(!p[i]) continue;
        for(int j=2*i; j<=100000; j+=i)
        {
            p[j]=0;
        }
    }
    for(int i=2; i<=100000; i++)
    {
        pre[i] = pre[i-1];
        if(p[i]&&p[(i+1)/2])
            pre[i]++;
    }
    cin >> q;
    while(q--)
    {
        cin >> l >> r;
        cout << pre[r] - pre[l-1] << endl;
    }
}



Measured memory_bytes: 1408
n, k = map(int, input().split())
p = list(map(int, input().split()))

import numpy as np
exps = np.array(p) / 2 + 0.5

s = exps[:k].sum()
m = s
for i in range(1, n - k + 1):
    s = s - exps[i-1] + exps[i+k-1]
    if s > m:
        m = s
print(m)

Measured memory_bytes: 25604
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int h, n;
    cin >> h >> n;
    vector<int> a(n);
    vector<int> b(n);
    rep(i, n) cin >> a[i] >> b[i];
    vector<vector<int>> dp(n + 1, vector<int>(h + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= h; j++) {
            chmin(dp[i + 1][j], dp[i][j]);
            chmin(dp[i + 1][min(h, j + a[i])], dp[i + 1][j] + b[i]);
        }
    }
    cout << dp[n][h] << endl;
}

Measured memory_bytes: 39424
#include <cstdio>
#include <algorithm>
using namespace std;
int N, K, h[100001], dp[100001];
int main() {
  scanf("%d %d", &N, &K);
  for(int i = 1; i <= N; i++) scanf("%d", &h[i]);
  for(int i = 0; i <= N; i++) dp[i] = 1e9;
  dp[1] = 0;
  for(int i = 2; i <= N; i++) {
    for(int j = 1; i > j && j <= K; j++) {
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]));
    }
  }
  printf("%d", dp[N]);
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

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

  int n;
  cin >> n;

  int c = 1;
  int ans = 0;
  int prev = -1;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;

    if (a == prev) {
      c++;
    } else {
      if (c > 1) {
        ans += c / 2;
        c = 1;
      }
    }
    prev = a;
  }
  if (c > 1) ans += c / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
B = list(map(int, input().split()))
A = [10 ** 6] * N
for n in range(N - 1):
  A[n] = min(B[n], A[n])
  A[n + 1] = min(B[n], A[n + 1])
  
print(sum(A))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define trav(a, b) for(auto& a: b
#define all(a) a.begin(), a.end()
#define gottagofast ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;
								
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	map<char, int> mp;
	mp['M'] = 0;
	mp['A'] = 1;
	mp['R'] = 2;
	mp['C'] = 3;
	mp['H'] = 4;
	vector<int> cnt(6, 0);
	int n;
	cin >> n;
	while(n--) {
		string s; cin >> s;
		if(mp.count(s[0]))
			++cnt[mp[s[0]]];
	}
	vector<int> perm = {0, 0, 1, 1, 1};
	// for(int i = 0; i < 5; ++i) {
	// 	cout << cnt[i] << " ";
	// }
	// cout << "\n";
	ll ans = 0;
	do {
		// bool cando = true;
		// for(int i = 0; i < 5; ++i) {
		// 	if((cnt[i] > 0) xor (perm[i] > 0)) {
		// 		// cando = false;
		// 	}
		// }
		ll x = 1LL;
		for(int i = 0; i < 5; ++i)
			if(perm[i]) x *= perm[i] * cnt[i];
		ans += x;
	} while(next_permutation(all(perm)));
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

const int M = 1000000000 + 7;

long long inv(int x, int m) {
  long long a[3] = {1, 0, x};
  long long b[3] = {0, 1, m};
  while (b[2] > 0) {
    long long r = a[2] / b[2];
    for (int i = 0; i < 3; ++i) {
      a[i] = a[i] - b[i] * r;
    }
    std::swap(a, b);
  }
  if (a[2] != 1) {
    throw std::runtime_error("no inv");
  }
  return a[0] > 0? a[0] % m: (m - (-a[0]) % m) % m;
}

long long comb(int n, int r) {
  long long x = 1;
  r = std::min(n, n - r);
  for (int i = 0; i < r; ++i) {
    x = x * (n - i) % M * inv(i + 1, M) % M;
  }
  return x;
}

int main() {
  long long h, w, a, b, c;
  long long ans = 0;
  std::cin >> h >> w >> a >> b;
  ans = comb(h + w - 2, h - 1);
  for (int i = 0; i < b; ++i) {
    // c = comb(h - a + i - 1, h - a - 1) * comb(a + w - i - 2, a - 1) % M;
    if (i == 0) {
      c = comb(h - a - 1, h - a - 1) * comb(a + w - 2, a - 1) % M;
    } else {
      c = c * (h - a + i - 1) % M * inv(i, M) % M;
      c = c * (w - i) % M * inv(a + w - i - 1, M) % M;
    }
    ans = (ans + M - c) % M;
  }
  std::cout << ans << std::endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

int main() {
  string s;
  cin >> s;
  ll n = s.length();

  {
    bool f = false;
    if (s[n - 1] == '1') f = true;
    if (s[0] == '0') f = true;
    for (ll i = 1; i < n; i++) {
      if (s[i - 1] != s[n - i - 1]) {
        f = true;
      }
    }
    if (f) {
      cout << -1 << endl;
      return 0;
    }
  }

  vi v(n);
  ll p = n - 1;

  for (ll i = n - 1; i >= 0; i--) {
    v[i] = p;
    if (s[i] == '1') {
      p = i;
    }
  }

  for (ll i = 0; i < n - 1; i++) {
    cout << i + 1 << ' ' << v[i] + 1 << endl;
  }
}


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

using namespace std;

typedef long long LL;

const LL mod=1000000007;
LL n,m,p,nn,mm,d,ans;

LL pw(LL x,LL k){
	if (k==0) return 1;
	LL tmp=pw(x*x%mod,k>>1);
	return k&1?tmp*x%mod:tmp;
}

int main(){
	scanf("%lld%lld%lld",&n,&m,&p);
	nn=__gcd(n,p); n/=nn;
	mm=__gcd(m,p); m/=mm;
	d=__gcd(n,m);
	ans=(pw(2,d)+pw(2,n)+pw(2,m)-3)%mod;
	ans=pw(ans,nn*mm);
	printf("%lld\n",ans);
	
	return 0;
}
			

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

int main()
{
  ll a,b;
  cin >> a >> b;
  
  if(a < b){
    int tmp = a;
    a = b;
    b = tmp;
  }
  
  ll ans = 0;
  for(ll i = 1; ; i++){
    ans = a * i;
    for(ll j = 1; b*j <= ans; j++){
      if(b * j == ans){
        cout << ans << endl;
        return 0;
      }
    }
  }
  
}

Measured memory_bytes: 3608
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size,n=1,init=nil) #nに配列の次元数、sizeに配列の大きさ、initに初期値を投げることでその配列を返す
  if n==1
    return Array.new(size){init}
  else
    return Array.new(n).map{Array.new(size){init}}
  end
end

class Edge
  attr_accessor:to,:from,:c
  def initialize(from,to,c)
    @to=to
    @from=from
    @c=c
  end
end

n,m=get_i
edges=array(m,1)
m.times do|i|
  a,b,c=get_i
  a-=1
  b-=1
  c*=-1
  edges[i]=Edge.new(a,b,c)
end

INF=10**30
d=array(n,1,INF)
d[0]=0
flag=array(n,1,false)
n.times do|i|
  m.times do|j|
    e=edges[j]
    if d[e.to]>d[e.from]+e.c
      d[e.to]=d[e.from]+e.c
    end
  end
end
n.times do|i|
  m.times do|j|
    e=edges[j]
    if d[e.to]>d[e.from]+e.c
      d[e.to]=d[e.from]+e.c
      flag[e.from]=true
    end
    flag[e.to]=true if flag[e.from]
  end
end
if flag[n-1]
  puts "inf"
else
  puts d[n-1]*-1
end

Measured memory_bytes: 3836