akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 1000000000;
const long long int llINF = 1000000000000000000;

using namespace std;
using ll = long long int;
using edge = struct {
  int to;
  int cost;
};
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end());
#define MIN(vec) *std::min_element(vec.begin(), vec.end());
#define MAXI(vec)                                                              \
  std::distance(vec.begin(), *std::max_element(vec.begin(), vec.end()));
#define MINI(vec)                                                              \
  std::distance(vec.begin(), *std::min_element(vec.begin(), vec.end()));
#define BIT(n, num) std::bitset<(n)>((num)).to_string()
#define MATMUL(a, b, c)                                                        \
  REP(i, a.size())                                                             \
  REP(j, b[0].size()) REP(k, a[0].size()) c[i][j] += a[i][k] * b[k][j];
#define CLA2(a) REP(i, a.size()) REP(j, a[0].size()) a[i][j] = 0;
#define REV(T) greater<T>()

ll pow_(ll a, ll n) {
  ll x = 1;
  while (n > 0) {
    if (n & 1)
      x = (x * a) % MOD;
    a = (a * a) % MOD;
    n >>= 1;
  }
  return x;
}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n)
        ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

map<ll, int> prime_factor(ll n) {
  map<ll, int> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1)
    ret[n] = 1;
  return ret;
}

ll factorial(int n) {
  ll ans = 1;
  for (int i = 2; i <= n; i++) {
    ans *= i;
    ans %= MOD;
  }
  return ans;
}
ll P(int n, int m) {
  ll ans = 1;
  for (int i = m + 1; i <= n; i++) {
    ans *= i;
    ans %= MOD;
  }
  return ans;
}
ll power(int n, int m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = power(n, m / 2);
    return (tmp * tmp) % MOD;
  } else {
    return (n * power(n, m - 1)) % MOD;
  }
}
ll C(int n, int m) {
  return (P(n, n - m) * power(factorial(m), MOD - 2)) % MOD;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
  ll N, V;
  vector<ll> A;
  cin >> N >> V;
  auto C = prime_factor(V);
  ll ANS = 1;
  AUTO(i, C) {
    if (i.second >= N) {
      ANS *= pow(i.first, i.second / N);
    }
  }
  cout << ANS << endl;
  return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<cstring>
#include<cassert>
#include<vector>
#include<list>
#include<queue>
#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<cmath>
#include<cstdlib>
#include<ctime>
#include<fstream>
#include<typeinfo>
#include<locale>
#include<iterator>
#include<valarray>
#include<complex>
#include<climits>
using namespace std;

#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)

//cout << fixed << setprecision(20) << p << endl;

template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

int maximum69Number (int num) {

           vector<int>d;
           while(num>0){
             d.pb(num%10);
             num/=10;
           }

          reverse(d.begin(),d.end());

          for(int i = 0; i<d.size(); i++){
            if(d[i]==6){
                d[i] = 9;break;
            }
          }
          int res = 0;
          for(int i = 0; i<d.size(); i++){
            res = res*10+d[i];
          }
          return res;
}


int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("out.txt","w",stdout);
     int n,m,a,b;
     cin >> a >> b;

       if(a>=b){
        for(int i=1; i<=a; i++)
            cout <<b;
            cout << '\n';
       }
       else{

        for(int  i = 1; i<=b; i++)
            cout << a;
            cout << '\n';
       }

  return 0;
}


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

using namespace std;

#define llong long long int
#define ldouble long double
#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)

const static int MOD = 1000000000 + 7;
const static llong INF = 1LL << 60;
const static int dy[] = {0, 1, 0, -1};
const static int dx[] = {1, 0, -1, 0};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> bamboo_length(n);
    rep(i, n) cin >> bamboo_length[i];
    llong needed_iteration = 0;
    rep(i, n) needed_iteration += pow(4, i);
    needed_iteration *= 3;

    int ans = 1000000000;
    rep(bit, needed_iteration + 1) {
        llong tmp_bit = bit;
        list<int> com;
        while (1) {
            com.push_back(tmp_bit % 4);
            tmp_bit /= 4;
            if (tmp_bit < 4) {
                if (tmp_bit != 0) com.push_back(tmp_bit);
                break;
            }
        }

        if (com.size() < n) {
            int needed_add_0 = com.size();
            for (int i = 0; i < n - needed_add_0; ++i) {
                com.push_back(0);
            }
        }

        int len_a = 0, len_b = 0, len_c = 0;
        int cnt_a = 0, cnt_b = 0, cnt_c = 0;
        int i = 0;
        stl_rep(itr, com) {
            // cout << *itr << " ";
            if (*itr == 0) len_a += bamboo_length[i], ++cnt_a;
            if (*itr == 1) len_b += bamboo_length[i], ++cnt_b;
            if (*itr == 2) len_c += bamboo_length[i], ++cnt_c;
            ++i;
        }
        // cout << endl;
        if (len_a == 0 || len_b == 0 || len_c == 0) continue;
        ans = min(ans, abs(a - len_a) + abs(b - len_b) + abs(c - len_c) + 10 * (cnt_a - 1 + cnt_b - 1 + cnt_c - 1));
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#import numpy as np
#from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense
#from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N= int(input())
dist_mat=[inputs() for _ in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if dist_mat[j][k]==dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        #ans+=dist_mat[j][k]
        dist_mat[j][k]=0
      elif dist_mat[j][k]>dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        print(-1)
        exit()
for i in range(N):
  for j in range(N):
    ans +=dist_mat[i][j]
print(ans//2)
#print(ans//2)



Measured memory_bytes: 46088
s, t = list(input()[::-1]), list(input()[::-1])
for i in range(len(s) - len(t) + 1):
    for j in range(len(t)):
        if s[i+j]!=t[j] and s[i+j]!="?": break
    else:
        for j in range(len(t)): s[i+j] = t[j]
        break
else: print("UNRESTORABLE");exit()
print("".join(s).replace("?", "a")[::-1])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef complex<ll> reta;
const ll INF = 1e18 + 7;
const int MAXN = 2e5+7, MAXX=1e6+7;
int n, node_counter = 0, raiz, fe[4*MAXN], fd[4*MAXN];
reta f[4*MAXN], inicial;
ll h[MAXN], c, dp[MAXN];

inline int create(){
    node_counter++;
    fe[node_counter] = -1;
    fd[node_counter] = -1;
    f[node_counter] = inicial;
    return node_counter;
}
inline ll calc(reta r, ll val){return r.real()*val + r.imag();}
void upt(int node, int l, int r, reta nova){
    if(l > r)return;
    int mid = (l+r)/2;
    if(calc(nova, mid) >= calc(f[node], mid)){
        if(fd[node] == -1)fd[node] = create();
        upt(fd[node], mid+1, r, nova);
    }else{
        swap(f[node], nova);
        if(nova == inicial || l==r)return;
        if(fe[node] == -1)fe[node] = create();
        upt(fe[node], l, mid, nova);
    }
}
ll query(int node, int l, int r, ll x){
    if(node == -1)return INF;
    ll v_no = calc(f[node], x);
    int mid = (l+r)/2;
    if(x <= mid)return min(v_no, query(fe[node], l, mid, x));
    return min(v_no, query(fd[node], mid+1, r, x));
}
int main(){
    inicial.real(0); inicial.imag(INF);
    raiz = create();
    scanf("%d %lld", &n, &c);

    scanf("%lld", &h[1]);

    for(int i=2; i<=n; i++){
        reta ri;
        ri.real(-2*h[i-1]); ri.imag(dp[i-1] + h[i-1]*h[i-1]);
        upt(raiz, 1, MAXX, ri);

        scanf("%lld", &h[i]);
        dp[i] = c + h[i]*h[i] + query(raiz, 1, MAXX, h[i]);
    }
    printf("%lld\n", dp[n]);
}

Measured memory_bytes: 14592
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 66;
char odd[MAXN] = {'\0'} , even[MAXN] = {'\0'};
int main()
{
	scanf(" %s %s" , odd , even);
	int len1 = strlen(odd) , len2 = strlen(even);
	bool flag = 1;
	int i = 0 , j = 0;
	while(i < len1 && j < len2)
	{
		if(flag)
			printf("%c" , odd[i++]) , flag = !flag;
		else
			printf("%c" , even[j++]) , flag = !flag;
	}
	while(i < len1)	printf("%c" , odd[i++]);
	while(j < len2)	printf("%c" , even[j++]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    string S;
    cin >> S;
    int res{};
    REP( i, (int)S.size() )
    {
        res += stoi( S.substr( i, 1 ) );
    }
    cout << ( stoi( S ) % res  == 0 ? "Yes" : "No" ) << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
l1 = [[int(i) for i in input().split()] for i in range(n)]
l2 = [[int(i) for i in input().split()] for i in range(n)]
l1.sort(key=lambda x:x[0],reverse=True)
l2.sort(key=lambda x:x[1])

answer = 0
for a,b in l1:
    for c,d in l2:
        if a < c and b < d:
            answer += 1
            l2.remove([c,d])
            break

print(answer)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

ll mod = 1000000007;


// 文字列 s に含まれる 'AB' の数を数える
int count_ab(const string& s) {
  int count = 0;
  string find_word("AB");
  auto pos = s.find(find_word);
  while (pos != string::npos) {
    count++;
    pos = s.find(find_word, pos + find_word.size());
  }
  return count;
}

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

  int n;
  cin >> n;

  int cnt_AB = 0;
  int cnt_A = 0;
  int cnt_B = 0;
  int cnt_both = 0;

  rep(i, n) {
    string s;
    cin >> s;

    int m = (int)s.size();

    for(int j = 0; j < m - 1; j++){
      if(s[j] == 'A' && s[j+1] == 'B') cnt_AB++;
    }

    if(s.size() == 2 && s[0] == 'A' && s[1] == 'B');
    else if(s[0] == 'B' && s[m - 1] == 'A') cnt_both++;
    else if(s[0] == 'B') cnt_B++;
    else if(s[m - 1] == 'A') cnt_A++;
  }

  int ans = 0;

  if(cnt_both == 0) ans = min(cnt_A,cnt_B);
  else if(cnt_both != 0 and cnt_A + cnt_B > 0) ans = cnt_both + min(cnt_A,cnt_B);
  else if(cnt_both != 0 and cnt_A == 0 and cnt_B == 0) ans = cnt_both - 1;

  ans += cnt_AB;

  cout << ans << endl;

  return 0;
}


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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 998244353;

const int MAXN = 2e6 + 5;

ll pow_mod(ll a, ll st) {
	ll ans = 1ll;
	for(; st; st >>= 1ll) {
		if (st & 1) {
			ans = (ans * a) % MOD;
		}
		a = (a * a) % MOD;
	}
	return ans;
}

ll f[MAXN], f_inv[MAXN];

ll get_c(int i, int j) {
	if (j < 0 || j > i) {
		return 0ll;
	}
	ll ans = (f[i] * f_inv[j]) % MOD;
	return (ans * f_inv[i - j]) % MOD;
}

ll get_c_rep(int i, int j) {
	return get_c(i + j - 1, j);
}

void solve(){
	f[0] = 1ll;
	REP(i, 1, MAXN) {
		f[i] = (f[i - 1] * i) % MOD;
	}
	f_inv[MAXN - 1] = pow_mod(f[MAXN - 1], MOD - 2);
	for(int i = MAXN - 2; i >= 0; i--) {
		f_inv[i] = (f_inv[i + 1] * (i + 1)) % MOD;
	}
	
	int n, m;
	scanf("%d%d", &n, &m);
	ll ans = (n * get_c(m + n - 2, m)) % MOD;
	
	//cout << ans << endl;
	
	for(int i = m % 2; i <= min(m, n); i += 2) {
		ll tmp = get_c(n, i);
		int cnt2 = m + (m - i) / 2;
		ll tmp1 = get_c(n + cnt2 - 1, cnt2);
		ll tmp2 = get_c(n + cnt2 - m - 1, cnt2 - m);
		ll tmp3 = (n * tmp2) % MOD;
		ll tmp4 = (tmp1 - tmp3 + MOD) % MOD;
		ll tmp5 = (tmp * tmp4) % MOD;
		
		//cout << tmp1 << " " << tmp2 << " " << tmp3 << " " << tmp4 << " " << tmp5 << endl;
		
		ans = (ans + tmp5) % MOD;
	}
	cout << ans << endl;
}

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 31488
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int r,d,x;
  cin >> r >> d >> x;
  int ans[11];
  ans[0] = x;
  REP(i,10) ans[i+1] = r*ans[i]-d,cout << ans[i+1] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;
int h, w, d;

int main() {        
    cin >> h >> w >> d;
    vector<vector<int>> v1(h + 1, vector<int>(w + 1, 0));
    vector<pair<int, int>> v2(h * w + 1, make_pair(0, 0));
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> v1[i][j];
            v2[v1[i][j]] = make_pair(i, j);
        }
    }
    int q;
    cin >> q;
    vector<long long int> v3(h * w + 1, 0);
    for (int i = 1; i <= h * w; i++) {
        if (i - d >= 1) {
            v3[i] = v3[i - d] + abs(v2[i].first - v2[i - d].first) + abs(v2[i].second - v2[i - d].second);
        } else {
            v3[i] = 0;
        }
    }
    for (int i = 0; i < q; i++) {
        long long int res = 0;
        int l, r;
        cin >> l >> r;
        cout << v3[r] - v3[l] << endl;
    }
}


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

#define HAS_TEST_CASE 0  // Do you forget to complete this?

namespace registerGen
{
typedef long long ll;

const int N=5e5;

int n,m,a[N+10];
char str[N+10];

inline void main()
{
	scanf("%d%s",&n,str+1);
	int cnt=0,ans=0;;
	for(int i=1;i<=n;i++)
		if(str[i]=='W')cnt++;
	for(int i=n;i>=n-cnt+1;i--)
		if(str[i]=='R')ans++;
	printf("%d\n",ans);
}
}

int main()
{
#ifndef ONLINE_JUDGE
//	freopen("tmp.out","w",stdout);
#endif
	int T=1;
#if HAS_TEST_CASE
	scanf("%d",&T);
#endif
	while(T--)registerGen::main();
	return 0;
}


Measured memory_bytes: 4016
#include <iostream>

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

	int x = 0, y = 0;
	std::cin >> x;
	std::cin >> y;

	if ((x * y) & 1) {
		std::cout << "Odd";
	}
	else {
		std::cout << "Even";
	}
	return 0;
}


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

int main(){
  int N;
  cin>>N;
  vector<tuple< string, int, int>> p;
  int j,k;
  string S;
  for(int i=0;i<N;i++){
    cin>>S>>k;
    p.push_back(make_tuple(S, -k, i));
  }
  sort(p.begin(),p.end());
  for(int i=0;i<N;i++){
    tie(S,k,j)=p[i];
    cout<<j+1<<endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long X = sc.nextLong();
		long Y = sc.nextLong();
		int ans = 1;
		while(true) {
			X *= 2;
			if(Y >= X)
				ans += 1;
			else
				break;
		}
		System.out.println(ans);
	}

}


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

int main() {
	int N;
	cin >> N;
	vector<double> p(N + 1);
	for (int i = 1; i <= N; ++i) { cin >> p[i]; }

	vector<vector<double>> dp(N + 1, vector<double>(N + 1, 0));
	dp[1][0] = 1.0 - p[1];
	dp[1][1] = p[1];
	for (int i = 2; i <= N; ++i) {
		double back = 1.0 - p[i];
		for (int j = 0; j <= i; ++j) {
			dp[i][j] = dp[i - 1][j] * back;
			if (j > 0) { dp[i][j] += dp[i - 1][j - 1] * p[i]; }
		}
	}

	double res = 0;
	for (int i = N / 2 + 1; i <= N; ++i) {
		res += dp[N][i];
	}

	cout.precision(10);
	cout << fixed << res << endl;

	return 0;
}


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

double dp[21000][110];
int T[100];
int V[100];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	for(int i = 0; i < 21000; i++){
		for(int j = 0; j < 110; j++){
			dp[i][j] = -1;
		}
	}
	dp[0][0] = 0;

	int N;
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> T[i];
	}
	for(int i = 0; i < N; i++){
		cin >> V[i];
	}

	int tsum = 0;
	for(int i = 0; i < N; i++){
		int t = T[i], v = V[i];
		for(int j = tsum; j < tsum + t; j++){
			for(int k = 0; k <= v; k++){
				if(dp[j][k] < 0) continue;
				for(int dk = -1; dk <= 1; dk++){
					int nk = k + dk;
					if(nk < 0 || v < nk) continue;
					double sum = dp[j][k] + (k + nk) / 2.0;
					if(dk == 0 && k < v) sum += 0.25;
					dp[j + 1][nk] = max(dp[j + 1][nk], sum);
				}
			}
		}
		tsum += t;
	}
	cout << fixed << setprecision(15) << dp[tsum][0] << endl;
}


Measured memory_bytes: 18304
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <set>
using namespace std;
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
#define rep_r(i,s,n)for(int i = n;i>s;i--)
#define rep_re(i,s,n)for(int i = n;i>=s;i--)
typedef long long ll;
static const ll MOD = 1e9 + 7;
static const ll INF = (ll)1 << 62;

int main() {
	ll n; cin >> n;
	ll ans = 0;
	repe(i, 1, n) {
		if (0<=i && i <= 9)ans++;
		else if (100 <= i && i <= 999)ans++;
		else if (10000 <= i && i <= 99999)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] $) {
		Scanner sc = new Scanner(System.in);
		int k=sc.nextInt(),n=sc.nextInt();
		int max=Integer.MIN_VALUE;
		int[] a=new int[n];
		a[0]=sc.nextInt();
		for(int i=1;i<n;i++) {
			a[i]=sc.nextInt();
			max=Math.max(max, Math.abs(a[i]-a[i-1]));
		}
		max=Math.max(max, a[0]+k-a[n-1]);
		System.out.println(k-max);
		//System.out.println(max);
	}
}


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

int main() {
    int A,B;
    cin>>A>>B;
    int ans = 0;
    if(A>B){
        ans += A;
        A--;
    }else{
        ans += B;
        B--;
    }
    if(A>B){
        ans += A;
        A--;
    }else{
        ans += B;
        B--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

//Book Replacement
public class Main{

	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int m = sc.nextInt(), c = sc.nextInt(), n = sc.nextInt();
			if((m|c|n)==0)break;
			int[] k = new int[n];
			int[][] req = new int[n][50];
			for(int i=0;i<n;i++){
				k[i] = sc.nextInt();
				for(int j=0;j<k[i];j++)req[i][j]=sc.nextInt();
			}
			Queue<Integer> D1 = new LinkedList<Integer>();
			Set<Integer>[] d = new Set[m+1];
			for(int i=2;i<=m;i++)d[i]=new HashSet<Integer>();
			int res = 0;
			for(int j=0;j<50;j++)for(int i=0;i<n;i++){
				if(k[i]<=j)continue;
				int r = req[i][j];
				if(D1.contains(r)){
					res += 2; D1.remove(r); D1.add(r);
					continue;
				}
				boolean shelf = true;
				for(int a=2;a<=m;a++){
					if(d[a].contains(r)){
						shelf = false;
						d[a].remove(r); res+=a;
						break;
					}
				}
				if(shelf)res+=m+1;
				if(D1.size()<c){
					res+=1; D1.add(r);
					continue;
				}
				int pos = -1;
				for(int a=2;a<=m;a++){
					if(d[a].size()<c){
						pos = a; res+=a; d[a].add(r); break;
					}
				}
				if(pos==-1)res+=m+1;
				int old = D1.poll();
				res+=1;
				shelf = true;
				for(int a=2;a<=m;a++){
					if(d[a].size()<c){
						shelf = false;
						d[a].add(old); res+=a;
						break;
					}
				}
				if(shelf)res+=m+1;
				if(pos!=-1){
					d[pos].remove(r); res+=pos;
				}
				else res+=m+1;
				D1.add(r); res+=1;
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int mod=1e9+7;
int dp[201][10001];

int main()
{
    int n,W,w[200];
    scanf(" %d %d", &n, &W);
    rep(i,n) scanf(" %d", &w[i]);
    sort(w,w+n);

    int ans=0;

    int all_sum=0;
    rep(i,n) all_sum+=w[i];
    ans+=(all_sum<=W);

    rep(i,n)
    {
        int sum=0;
        rep(j,i) sum+=w[j];
        if(sum>W) break;

        memset(dp,0,sizeof(dp));
        dp[i+1][sum]=1;

        for(int j=i+1; j<n; ++j)for(int k=sum; k<=W; ++k)
        {
            (dp[j+1][k]+=dp[j][k])%=mod;
            if(k+w[j]<=W) (dp[j+1][k+w[j]]+=dp[j][k])%=mod;
        }

        for(int j=max(0,W-w[i]+1); j<=W; ++j) (ans+=dp[n][j])%=mod;
        // printf("  %d\n", ans);
    }

    printf("%d\n", ans);
    return 0;
}

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

int n,w[10240000],e[10240000],minv=99999999;

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		char aa;cin >> aa;
		aa=='W'?w[i]++:e[i]++;
		w[i]+=w[i-1];e[i]+=e[i-1];
	}
	for(int i=1;i<=n;i++){
		int ii=w[i-1]+e[n]-e[i];
		minv=min(minv,ii);
	}
	cout << minv;
	return 0;
}

Measured memory_bytes: 5504
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  ll H, N;
  cin >> H >> N;
  vector<ll> A(N);
  for_each(begin(A), end(A), [](auto& x) { cin >> x; });

  ll sum = accumulate(cbegin(A), cend(A), 0LL);
  string ans = "No";
  if (H - sum <= 0) {
    ans = "Yes";
  }

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


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n:=getNextInt(scanner)
	m:=getNextInt(scanner)
	if n == m{
		fmt.Fprintln(writer, "Yes")
		return
	}
	fmt.Fprintln(writer, "No")
}


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

int main(){
    int h , w;
    cin >> h >> w;
    int i, j;
    vector<vector<char>> a(h, vector<char>(w));
    for(i = 0;i < h;i++){
        for(j = 0;j < w;j++){
            cin >> a.at(i).at(j);
        }
    }

    for(i = 0;i < a.size();i++){
        for(j = 0;j < w;j++){
            if(a.at(i).at(j) != '.'){
                break;
            }
        }
        if(j == w){
            a.erase(a.begin()+i);
            i--;
        }
    }

    vector<vector<char>> tmp( w, vector<char>( a.size() ) );
    for(i = 0;i < a.size();i++){
        for(j = 0;j < w;j++){
            tmp.at(j).at(i) = a.at(i).at(j);
        }
    }
    /*
    for(i = 0;i < w;i++){
        for(j = 0;j < a.size();j++){
            cout << tmp.at(i).at(j);
        }
        cout << endl;
    }
    */

    for(i = 0;i < tmp.size();i++){
        for(j = 0;j < a.size();j++){
            if(tmp.at(i).at(j) != '.'){
                break;
            }
        }
        if(j == a.size()){
            tmp.erase(tmp.begin()+i);
            i--;
        }
    }

    vector<vector<char>> answer(tmp.at(0).size(), vector<char>(tmp.size()));
    for(i = 0;i < tmp.size();i++){
        for(j = 0;j < tmp.at(0).size();j++){
            answer.at(j).at(i) = tmp.at(i).at(j);
        }
    }

    for(i = 0;i < answer.size();i++){
        for(j = 0;j < answer.at(0).size();j++){
            cout << answer.at(i).at(j);
        }
        cout << endl;
    }


}

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

void solve() {
	string s, t;
	cin >> s >> t;
	std::cout << t << s << std::endl;
}

int main() {
	solve();
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,a[10005],ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=2;i<n;++i){
		if(a[i]>a[i-1]&&a[i]<a[i+1])ans++;
		if(a[i]<a[i-1]&&a[i]>a[i+1])ans++;
	}
	printf("%d",ans);
}

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

const int MN = 2010;

int N, K, Q;
int A[MN], chk[MN];
vector<int> X;

int main() {
    scanf("%d %d %d", &N, &K, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        X.push_back(A[i]);
    }

    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());

    int ans = 1e9;
    for(int q = 0; q < X.size(); q++) {
        for(int i = 0; i < N; i++) if(A[i] < X[q]) {
            chk[i] = 1;
        }

        vector<int> V;
        int s = -1;
        for(int i = 0; i < N; i++) {
            if(chk[i]) continue;
            if(s == -1) s = i;
            if(i == N - 1 || chk[i + 1]) {
                if(i - s + 1 >= K) {
                    vector<int> tmp;
                    for(int j = s; j <= i; j++) {
                        tmp.push_back(A[j]);
                    }
                    sort(tmp.begin(), tmp.end());
                    for(int j = 0; j <= (int)tmp.size() - K; j++) {
                        V.push_back(tmp[j]);
                    }
                }
                s = -1;
            }
        }
        sort(V.begin(), V.end());
        if(V.size() >= Q) ans = min(ans, V[Q - 1] - X[q]);
    }
    printf("%d", ans);
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  
  int a, b;
  int numa, numb;
  int ans1, ans2;
  int temp;
  int jdg=0;
  int i;
  
  while( scanf("%d", &a) != EOF ){
    scanf("%d", &b);      
      
    numa = a;
    numb = b;
    
    if( numa < numb ) {
      temp = numa;
      numa = numb;
      numb = temp;
    }
    
    while( numa % numb ){
      numa = numa % numb;
      temp = numa;
      numa = numb;
      numb = temp;
    }

    
    ans1 = numb;
    
    ans2 = (b/ans1) * a;
    
    printf("%d %d\n", ans1, ans2);
    
  }
  
    
  return 0;
}

Measured memory_bytes: 596
def lcm_base(x, y):
    return (x*y) // math.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


import math
from functools import reduce

n = int(input())
alist = list(map(int, input().split()))

print(lcm_list(alist))


Measured memory_bytes: 6328
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    int state = -a+b;

    cout << (state>x ? "dangerous" : (state<=0 ? "delicious" : "safe")) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<limits>
using namespace std;
typedef long long ll;

template <class T>
class Bellmanford {
    private:
        T inf;
        struct edge {
            int from, to;
            T cost;
        };
        vector<edge> es;
        vector<T> dist;
        vector<bool> is_negative;
        int node_num, edge_num;
        bool negative_loop;
    public:
        Bellmanford(int v, int e, T _inf) {
            inf = _inf;
            node_num = v;
            edge_num = e;
            dist.resize(node_num);
            is_negative.resize(node_num);
            negative_loop = false;
            fill(dist.begin(), dist.end(), inf);
            fill(is_negative.begin(), is_negative.end(), false);
        }
        void add_edge(int from, int to, T cost) {
            edge e = {from, to, cost};
            es.push_back(e);
        }
        void calc_shortest_path(int start) {
            dist[start] = 0;
            for (int i = 0; i < node_num; i++) {
                for (int j = 0; j < edge_num; j++) {
                    edge e = es[j];
                    if (dist[e.from] != inf && dist[e.to] > dist[e.from] + e.cost) {
                        dist[e.to] = dist[e.from] + e.cost;
                        if (i == node_num - 1) {
                            negative_loop = true;
                            is_negative[e.to] = true;
                        }
                    }
                    if (is_negative[e.from]) {
                        is_negative[e.to] = true;
                    }
                }
            }
        }
        bool is_negative_loop() {
            return negative_loop;
        }
        bool have_negative_path(int u) {
            // if path from start to u has negative loop, return true
            return is_negative[u];
        }
        T get_dist(int u) {
            return dist[u];
        }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M, P;
    cin >> N >> M >> P;
    ll A, B, C;
    Bellmanford<ll> bell(N, M, 1LL << 50);
    for (int i = 0; i < M; ++i) {
        cin >> A >> B >> C;
        A--, B--;
        C -= P;
        bell.add_edge(A, B, -C);
    }
    bell.calc_shortest_path(0);
    bell.calc_shortest_path(0);
    if (bell.have_negative_path(N - 1)) {
        cout << -1 << endl;
    }
    else {
        ll ans = bell.get_dist(N - 1);
        cout << max(-ans, 0LL) << endl;
    }
    return 0;
}

Measured memory_bytes: 512
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    dp = [[[0] * f for _ in range(2)] for _ in range(10002)]
    dp[0][0][0] = 1
    l = len(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = input()
d = int(input())
print(digit_dp(k, d) % mod)


Measured memory_bytes: 101612
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>

#ifndef ULLONG
typedef unsigned long long ULLONG;
#endif
#ifndef LLONG
typedef long long LLONG;
#endif

static void B_task();

int main()
{
	B_task();
	
	fflush(stdout);
	return 0;
}

static void B_task()
{
	char szYM[5] = { 0 };
	char szF[3] = { 0 };
	char szL[3] = { 0 };

	scanf(" %s", szYM);

	for (int i = 0; i < 2; i++) {
		szF[i] = szYM[i];
		szL[i] = szYM[i + 2];
	}

	long fr = strtol(szF, 0, 10);
	long Lr = strtol(szL, 0, 10);

	const char* ans = "NA";
	if (((fr > 12) && (Lr <= 12) && (Lr > 0))
		|| ((fr == 0) && (Lr <= 12) && (Lr > 0))) {
		ans = "YYMM";
	}
	if (((Lr > 12) && (fr <= 12) && (fr > 0))
		|| ((Lr == 0) && (fr <= 12) && (fr > 0))) {
		ans = "MMYY";
	}
	else if ((fr <= 12) && (fr > 0) && (Lr <= 12) && (Lr > 0)) {
		ans = "AMBIGUOUS";
	}

	printf("%s\n", ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    bool flag = true;
    for(int i=0; i<s.length(); i++){
        if(i%2==0){
            if(s[i]!='R' && s[i]!='D' && s[i]!='U'){
                flag = false;
                break;
            }
        }
        else{
            if(s[i]!='L' && s[i]!='U' && s[i]!='D'){
                flag = false;
                break;
            }
        }
    }
    if(flag)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(a,n) for(int i=a;i<n;i++)
#define rep1(a,n) for(int i=a;i<=n;i++)
int main()
{
  ll a,b,c,d,t,m,r,n,lcm,p;

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

  r=(b/c)-(a/c);
  if(a%c==0)
    r++;
  n=(b/d)-(a/d);
  if(a%d==0)
    n++;

  m=__gcd(c,d);
  lcm=(c/m)*d;

  p=(b/lcm)-(a/lcm);
  if(a%lcm==0)
    p++;

  cout<<b-a+1-r-n+p<<"\n";
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using static System.Math;

class Program
{
    static void Main()
    {
        string[] s = Console.ReadLine().Split();
        int a = int.Parse(s[0]);
        int b = int.Parse(s[1]);
        if (a >= 13)
        {
            Console.WriteLine(b);
            return;
        }
        if (a >= 6)
        {
            Console.WriteLine(b / 2);
            return;
        }
        Console.WriteLine(0);
    }
}

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

int main() {
  int N;
  cin >> N;
  string ans="No";
  while (N>0) {
    if (N%10==9) {
      ans = "Yes";
      break;
    }
    N/=10;
  }
  cout << ans << endl;
}


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

#define ll long long int
#define hell 998244353
#define vi vector <ll>
#define pb push_back
#define pii pair<ll,ll>
#define vii vector <pii>
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define sep(i,a,b)  for(ll i=a-1;i>=b;i--)
#define inf (ll)(1e16)

using namespace std;

vi adj[100005];
vector <bool> visited(100005,false);
vi dp(100005,-1);

ll dfs(ll s)
{
    if(dp[s]!=-1)
        return dp[s];
    visited[s]=true;
    ll ans=0;
    for(auto ch:adj[s])
    {
        if(!visited[ch])
            ans=max(ans,dfs(ch));
        ans=max(ans,dp[ch]);
    }
    //cout<<s<<" "<<1+ans<<"\n";
    return dp[s]=1+ans;
}

void solve()
{
    ll n,m,u,v;
    cin>>n>>m;
    rep(i,0,m)
    {
        cin>>u>>v;
        adj[u].pb(v);
    }
    rep(i,1,n+1)
    {
        if(!visited[i])
            dfs(i);
    }
    cout<<*max_element(dp.begin(),dp.end())-1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}


Measured memory_bytes: 9984
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long 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 (b<a) {a=b; return 1;} return 0;}

const ll INF = 1LL<<60;
const int MAX_N = 1005;

vvi to(MAX_N), ot(MAX_N);
vector<tuple<int, int, int>> es;
bool seen_1[MAX_N], seen_2[MAX_N], seen[MAX_N];
ll d[MAX_N];

void dfs(int v) {
    if (seen_1[v]) return;
    seen_1[v] = true;
    for (int u : to[v]) {
        dfs(u);
    }
}

void rdfs(int v) {
    if (seen_2[v]) return;
    seen_2[v] = true;
    for (int u : ot[v]) {
        rdfs(u);
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        to[a].pb(b);
        ot[b].pb(a);
        es.eb(a, b, -c);
    }
    dfs(0);
    rdfs(n-1);
    rep(i, n) seen[i] = seen_1[i] && seen_2[i];
    rep(i, n) d[i] = INF;
    d[0] = 0;
    bool neg = false;
    for (int i = 0; ; ++i) {
        bool update = false;
        rep(j, m) {
            int from, to; ll cost;
            tie(from, to, cost) = es[j];
            if (!seen[from] || !seen[to]) continue;
            if (d[from] != INF && chmin(d[to], d[from] + cost)) update = true;
        }
        if (!update) break;
        if (i == n-1) { neg = true; break;} 
    }
    if (neg) cout << "inf" << endl;
    else cout << -d[n-1] << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <regex>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<ll>;
using vpii = vector<pii>;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define rFOR(i,a,b) for(int i=(b);i>=(a);i--)
#define SORT(a) sort((a).begin(),(a).end());
#define rSORT(a) sort((a).rbegin(),(a).rend());
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end());
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;

//sankou
//vvi = vector<vector<int>>(20, vector<int>(10, 0));

//seiki
//#include <regex>
/*bubun*/
//regex_search("u32", regex("[0-9]"));      // true
/*kanzen*/
//regex_match("u32", regex("(i|u)\\d+"));   // true

int isP(int n) {
    if(n<=1) return 0;
    FOR(i,2,(int)sqrt(n)) {
        if(n%i==0) return 0;
    }
    return 1;
}

int main() {

    int A,B;
    cin >>A>>B;
    if((A<=8)&&(B<=8)) {
        cout <<"Yay!";
    }else{
        cout <<":(";
    }

    return 0;
}





Measured memory_bytes: 256
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}
/*
inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
*/
// }}}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
  
    string s,t;
    cin >> s >> t;

    int n = s.size(),m = t.size();

    vector<vector<int> > dp(n+1,vector<int>(m+1));
    reps(i,n){
        reps(j,m){
            if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }

    string res;

    int y = n,x = m;

    while(dp[y][x]){
        if(dp[y][x] == dp[y-1][x]) --y;
        else if(dp[y][x] == dp[y][x-1]) --x;
        else{
            res += s[y-1];
            --y;
            --x;
        }
    }
        
    reverse(all(res));
    cout << res << '\n';

    return 0;
}


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

int main() {
	string s;
	cin >> s;
	int left = 0, right = s.size();
	while (left < right) {
		int mid = (left + right) / 2;
		// test mid
		int even_low = 0;
		int even_high = mid;
		bool even_ok = even_high >= even_low;
		if (mid % 2) {
			even_high--;
		}
		int odd_low = 1;
		int odd_high = mid;
		bool odd_ok = odd_high >= odd_low;
		if (mid % 2 == 0) {
			odd_high--;
		}
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '1') {
				even_low++;
				even_high++;
				odd_low++;
				odd_high++;
			}
			else if (s[i] == '0') {
				even_low--;
				even_high--;
				odd_low--;
				odd_high--;
			}
			else {
				even_low--;
				even_high++;
				odd_low--;
				odd_high++;
			}
			while (even_low < 0) {
				even_low += 2;
			}
			while (even_high > mid) {
				even_high -= 2;
			}
			while (odd_low < 0) {
				odd_low += 2;
			}
			while (odd_high > mid) {
				odd_high -= 2;
			}
			if (even_high < even_low) {
				even_ok = false;
			}
			if (odd_high < odd_low) {
				odd_ok = false;
			}
		}
		if (odd_ok || even_ok) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	cout << left << endl;
}

Measured memory_bytes: 4560
/*
    Problem 67
    https://atcoder.jp/contests/abc065/tasks/arc076_b
*/
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* class */
class DisjontSet {
    public:
    vector<int> d;
    DisjontSet (int size) : d(size, -1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
};
class Edge {
    public:
    int from, to, cost;
    Edge (int from, int to, int cost) :
    from(from), to(to), cost(cost) {}
    bool operator < (const Edge &e) const {
        return cost < e.cost;
    }
};
class Point {
    public:
    int x, y, ind;
    Point (int x, int y, int ind) : x(x), y(y), ind(ind) {}
    bool operator < (const Point &p) const {
        return x < p.x;
    }
};
/* constant */
const int INF = 1 << 30;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, x, y;
    cin >> N;
    vector<Point> p1, p2;
    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        p1.push_back(Point(x, y, i));
        p2.push_back(Point(y, x, i));
    }
    sort(p1.begin(), p1.end());
    sort(p2.begin(), p2.end());

    vector<Edge> edges;
    for (int i = 0; i < N - 1; i++) {
        int diff1 = abs(p1[i].x - p1[i + 1].x);
        int diff2 = abs(p2[i].x - p2[i + 1].x);
        edges.push_back(Edge(p1[i].ind, p1[i + 1].ind, diff1));
        edges.push_back(Edge(p2[i].ind, p2[i + 1].ind, diff2));
    }

    sort(edges.begin(), edges.end());
    DisjontSet dset = DisjontSet(N + 1);
    int totalCost = 0;
    for (Edge e : edges) {
        if (dset.unite(e.from, e.to)) totalCost += e.cost;
    }
    cout << totalCost << '\n';
}

Measured memory_bytes: 7212
import sys
sys.setrecursionlimit(10 ** 6)

def is_bipartite(v, d):
    color[v] = d
    for u in E[v]:
        if color[u] == d:
            return False
        elif color[u] != -1:
            continue
        if not is_bipartite(u, (d + 1) % 2):
            return False
    return True

N, M = map(int, input().split())
E = [[] for _ in range(N)]
color = [-1] * N

for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

if is_bipartite(0, 0):
    b = sum(color)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Measured memory_bytes: 31156