akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    ll N, M, K;
    cin >> N >> M >> K;

    vector<ll> A(N + 1), B(M);
    A[0] = 0;
    FOR(i, 1, N + 1) {
        cin >> A[i];
        A[i] += A[i - 1];
    }

    FOR(i, 0, M) {
        cin >> B[i];
        if (i > 0 ) B[i] += B[i - 1];
    }

    debug(A, B);
    debug(K)

    ll ans = 0;
    REP(i, N + 1) {
        if (K < A[i]) break;
        ll c = (lower_bound(ALL(B), K - A[i] + 1) - B.begin());
        ans = max(ans, i + c);
    }

    print(ans);

    
}


Measured memory_bytes: 6340
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

#define rep(i,x,y) for (int i=x;i<=y;i++)
#define dep(i,y,x) for (int i=y;i>=x;i--)
#define sz(x) (int)(x.size())

using namespace std;

typedef long long LL;   
typedef unsigned long long uLL;

const int maxn=200000+7;
const LL MOD=(1e9)+7;

struct Node{
    int x,v;
    bool operator < (const Node b) {return v<b.v;}
} a[maxn];

int n,size,l,r,mid,Q[maxn],L[maxn],R[maxn],u[maxn];
LL F[maxn],sum;

bool cmp(int x,int y) {if (L[x]==L[y]) return R[x]<R[y]; else return L[x]<L[y];}

int main()
{
    scanf("%d",&n);
    rep(i,1,n) scanf("%d%d",&a[i].x,&a[i].v);

    sort(a+1,a+n+1);

    size=1,L[1]=1,Q[1]=1;
    rep(i,2,n)
    {
        if (a[Q[size]].x<a[i].x) Q[++size]=i;

        l=1,r=size;
        while ((r-l)>1)
        {
            mid=(l+r)>>1;
            if (a[Q[mid]].x>=a[i].x) r=mid; else l=mid+1;
        }

        if (a[Q[l]].x>=a[i].x) L[i]=Q[l]; else L[i]=Q[r];
    }

    size=1,R[n]=n,Q[1]=n;
    dep(i,n-1,1)
    {
        if (a[Q[size]].x>a[i].x) Q[++size]=i;

        l=1,r=size;
        while ((r-l)>1)
        {
            mid=(l+r)>>1;
            if (a[Q[mid]].x<=a[i].x) r=mid; else l=mid+1;
        }

        if (a[Q[l]].x<=a[i].x) R[i]=Q[l]; else R[i]=Q[r];
    }


    rep(i,1,n) u[i]=i;
    sort(u+1,u+n+1,cmp);

    F[0]=1;
    L[0]=R[0]=0,u[0]=0;

    l=0,r=0,sum=1;
    rep(i,1,n)
    {
        while (((r+1)<i)&&(R[u[r+1]]>=(L[u[i]]-1))) ++r,sum=(sum+F[r])%MOD;
        while ((l<=r)&&(R[u[l]]<(L[u[i]]-1))) sum=(sum-F[l]+MOD)%MOD,++l;
        F[i]=sum;
    }

    sum=0;
    rep(i,1,n) if (R[u[i]]==n) sum=(sum+F[i])%MOD;

    printf("%lld\n",sum);

    // system("pause");
    return 0;
}


Measured memory_bytes: 6400
#include <stdio.h>

bool cnt[128] = {0};

int main(void)
{
    bool flag = false;
    char str[32];
    scanf("%s", str);
    for (int i = 0; i < 32; i++) {
        if (str[i] < 'a' || str[i] > 'z') break;
        if (cnt[str[i]]) {
            flag = true;
            break;
        }
        else
            cnt[str[i]] = true;
    }
    if (flag) printf("no\n");
    else printf("yes\n");
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#ifdef _debug
#define dout(i) cout << #i << ' ' << i << ' '
#else 
#define dout(i) //
#endif
using ll = long long;
using ull = unsigned long long;
using ul = unsigned;
using db = double;
int n, q;
ll m, c;
vector<pair<int,int>> edge[2];
const int maxn = 100001;
int s[maxn], b[maxn];
string res[2] = {"No\n", "Yes\n"};
int find(int i){
	return i == b[i] ? i : b[i] = find(b[i]);
}
void merge(int x, int y){
	x = find(x), y = find(y);
	if(s[x] < s[y])swap(x, y);
	if(x != y){
		s[x] += s[y];
		b[y] = b[x];
		--c;
	}
}
#define same(a, b) (find(a) == find(b))
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 0, a, b, c;i < q;++i){
		cin >> a >> b >> c;
		edge[c].emplace_back(a, b);
	}
	if(m == n-1)return cout << res[edge[1].empty()], 0;
	c = n;
	for(int i = 1;i <= n;++i)b[i] = i, s[i] = 1;
	for(auto &p : edge[0])merge(p.first, p.second);
	for(auto &p : edge[1])if(same(p.first, p.second))return cout << res[0] , 0;
	cout << res[m <= (ll)n-c + c*(c-1)/2];
}

Measured memory_bytes: 2036
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int l=sc.nextInt();
    int r=sc.nextInt();
    int min = 2019*2019;
    for(int i=l;i<=r&&i<=l+2019;i++){
        for(int j=i+1;j<=r&&j<=i+2019;j++){
            min=Math.min( ( ((i%2019)*(j%2019))%2019 ) ,min);
        }
    }
    System.out.println( min );
  }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int ans = 0;

    rep(i, n-1){
        for(int j = i + 1; j < n; j++) {
            int w = abs(a[i] - a[j]);
            ans = max(ans, w);
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3540
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/
	
	int n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];

	ll g = a[0];
	for (int i = 1; i < n; i++) {
		g = gcd(g, a[i]);
	}

	out(g);

	return 0;
}

Measured memory_bytes: 1024
l=list(str(input()))
l=[int(i) for i in l]
cnt=0
for i in range(len(l)-1):
  if(l[i]==l[i+1]):
    cnt+=1
    if(l[i]==0):
      l[i+1]=1
    elif(l[i]==1):
      l[i+1]=0
print(cnt)

Measured memory_bytes: 4652
#include<stdio.h>
int main(){
  long long n,a,b,ans=0,ama=0,sum=0;
  scanf("%lld%lld%lld",&n,&a,&b);
  ans=n/(a+b);
  ama=n%(a+b);
  if(ama>=a){
    sum=(a*ans)+a;
  }
  else{
    sum=a*ans+ama;
  }
  printf("%lld\n",sum);
  return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const LL MOD = 1000000007LL;
LL x[100000];
LL y[100000];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
		(x[i] += MOD) %= MOD;
	}
	for (int i = 0; i < m; i++) {
		cin >> y[i];
		(y[i] += MOD) %= MOD;
	}
	LL sum_x = 0;
	for (int i = 0; i < n; i++) {
		LL add = (2 * i - (n - 1) + MOD) % MOD;
		(add *= x[i]) %= MOD;
		(sum_x += add) %= MOD;
	}
	LL sum_y= 0;
	for (int i = 0; i < m; i++) {
		LL add = (2 * i - (m - 1) + MOD) % MOD;
		(add *= y[i]) %= MOD;
		(sum_y += add) %= MOD;
	}
	cout << (sum_x*sum_y) % MOD << endl;
}

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

int N, Q;
string S;
int l, r;

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

	cin >> N >> Q >> S;

	int cnt[100005]; memset(cnt, 0, sizeof(cnt));

	for (int i = 1; i < N; i++) {
		cnt[i] = cnt[i-1];
		if (S[i] == 'C' && S[i - 1] == 'A') cnt[i]++;
	}

	for (int i = 0; i < Q; i++) {
		cin >> l >> r;
		l--; r--;
		if (S[l] == 'A' && S[l + 1] == 'C') cout << cnt[r] - cnt[l + 1] + 1 << endl;
		else cout << cnt[r] - cnt[l + 1] << endl;
	}
}

Measured memory_bytes: 1488
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;

int n,left,right,s0,s1;
struct node {
	int x,y;
	bool operator <(node b) const {
		return x-y>b.x-b.y;
	}
} a[N];

char s[N];

int main() {
	scanf("%d",&n);
	for(int i=1,l,r;i<=n;i++) {
		scanf("%s",s+1); l=r=0;
		for(int j=1;s[j];j++)
			if(s[j]=='(') l++;
			else {
				if(l) l--;
				else r++;
			}
		if(!l&&r) right+=r;
		else if(!r&&l) left+=l;
		else a[i]=(node){l,r};
		s0+=l;s1+=r;
	}
	if(s0^s1) puts("No"),exit(0);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) {
		if(left<a[i].y) puts("No"),exit(0);
		left-=a[i].y-a[i].x;
	}
	if(left^right)puts("No");
	else puts("Yes"); return 0;
}


Measured memory_bytes: 9256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();


int main() {
    string s; int k;
    cin >> s >> k;
    set<string> cand;
    for(int len = 1; len <= min(k, int(s.size())); len++) {
        for(int i = 0; i <= s.size()-len; i++) {
            cand.insert(s.substr(i, len));
        }
    }
    int ranks = 1;
    for(string ss: cand) {
        if (ranks == k) {
            cout << ss << endl;
            break;
        }
        ranks++;
    }
    return 0;
}




Measured memory_bytes: 1664
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int main(){
	long long n,i,ans=1;
	scanf("%lld",&n);
	for(i=1;i<=n;i++){
		ans*=i;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define LL long long
#define maxn 200010
#define mod 1000000007
using namespace std;
int a[maxn];
LL ans=1,x,y;
int main(){
	int n,k,i,b,l,r;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	if(a[1]>=0){
		for(i=n;i>=n-k+1;i--)ans=ans*a[i]%mod;
	}else if(a[n]<0){
		if(k&1){
			for(i=n;i>=n-k+1;i--)ans=ans*a[i]%mod;
			ans=(ans%mod+mod)%mod;
		}else{
			for(i=1;i<=k;i++)ans=ans*a[i]%mod;
		}
	}else{
		int cnt1=0,cnt2=0;
		for(i=1;i<=n;i++)
			if(a[i]<0)cnt1++;
			else break;
		cnt2=n-cnt1;
		if(cnt1/2*2+cnt2<k){
			for(i=1;i<=n;i++)ans=ans*a[i]%mod;
			ans=(ans%mod+mod)%mod;
		}else{
			if(k&1)
				ans=a[n],n--,k--;
			l=1,r=n;
			while(k){
				x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];
				if(x>y)x%=mod,ans=ans*x%mod,l+=2;
				else y%=mod,ans=ans*y%mod,r-=2;
				k-=2;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 4540
/*
  B - たてなが / Thin
  <http://abc049.contest.atcoder.jp/tasks/abc049_b>
  [Tips]
  ・scanfは空白類(スペース、改行、タブなど)は読み込まない。
  ・char型のポインタは宣言しただけでは、文字列を格納することができない。初期化が必要。<https://oshiete.goo.ne.jp/qa/8529783.html>
*/

#include <stdio.h>

int main(int argc, char const *argv[]) {

  int H,W;
  char C[101];
  int i;

  scanf("%d %d", &H, &W);

  for( i=0; i<H; i++ ){
    scanf("%s", C);
    printf("%s\n%s\n", C, C);
  }

  return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int k;
	cin >> k;
	vector<ll> a;
	rep(i,9) a.push_back(i+1);
	while(true){
		if(k <= a.size()){
			cout << a[k-1] << endl;
			return 0;
		}
		k -= a.size();
		vector<ll> old;
		swap(old, a);
		for(ll x : old){
			for(int i = -1; i <= 1; i++){
				int d = x%10 + i;
				if(d < 0 || d > 9) continue;
				ll nx = x*10 + d;
				a.push_back(nx);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1712
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import Data.List
import Data.Bits
import qualified Data.IntMap.Strict as IM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
-- import Control.Monad
-- import Control.Monad.ST
-- import Debug.Trace

solve :: Int -> [Int] -> Int
solve n as = answer
  where
  imap0 = foldl' op IM.empty as
    where op im a = IM.insertWith (+) a 1 im

  answer = sum $ unfoldr f imap0
    where
    f imap
      | IM.null imap = Nothing
      | x == b       = Just (m `div` 2, IM.delete x imapNxt)
      | otherwise    = fsub (IM.lookup x imap)
      where
      fsub Nothing = Just (0, imapNxt)
      fsub (Just k) | k <= m = Just (k, IM.delete x imapNxt)
                    | otherwise = Just (m, IM.adjust (+ (- m)) x imapNxt)
      ((b, m), imapNxt) = IM.deleteFindMax imap
      x = btox b

btox b = setBit 0 (64 - (countLeadingZeros b)) - b

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_n]:remLines1 = remLines0
      n = readBInt bs_n
      line2:remLines2 = remLines1
      as = map readBInt line2
  in solve n as

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents


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

int main() {
  ll n;
  cin >> n;
  ll x = 1, y = 1;
  if(n!=1) {
    while(true) {
      if(n!=1) {
        n /= 2;
        x *= 2;
        y += x;
      }
      else break;
    }
    cout << y << endl;
  }
  else cout << 1 << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int, int> P;
 
 
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
 
	int H, W, K, N;
	cin >> H >> W >> N;
	P p[N];
	rep(i,N) cin >> p[i].first >> p[i].second;
	map<int, int> mp1, mp2;
	rep(i,N){
		mp1[p[i].first]++;
		mp2[p[i].second]++;
	}
	int maxi1 = 0, maxi2 = 0;
	for(auto e : mp1){
		maxi1 = max(maxi1, e.second);
	}
	for(auto e : mp2){
		maxi2 = max(maxi2, e.second);
	}
	K = maxi1 + maxi2;
 
	int cou = H;
	int A[K+1]{}, B[K+1]{};
	for(auto u : mp1){
		A[u.second]++;
		cou--;
	}
	A[0] = cou;
	
	cou = W;
	for(auto u : mp2){
		B[u.second]++;
		cou--;
	}
	B[0] = cou;
	int ans = 0;
	for(int i=0;i<=K;i++){
		ans += A[i] * B[K-i];
	}
	rep(i,N){
		if(K == mp1[p[i].first] + mp2[p[i].second]){
			--ans;
		}
		if(K+1 == mp1[p[i].first] + mp2[p[i].second]){
			++ans;
		}
	}
	if(ans == 0) cout << K-1 << endl;
	else cout << K << endl;
}

Measured memory_bytes: 45800
import java.util.Scanner;

// 提出時にclass Main に書き換え
public class Main {
	public static void main(String[] args)  {
		// 標準入力を受け取る
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // int Nを受け取る
		int X = sc.nextInt(); // int Xを受け取る
		int T = sc.nextInt(); // int Tを受け取る
		sc.close(); // 標準入力を終了

		int a = 0; // タコ焼き機を使う回数
		if(N <= X) {
			a = 1;
		} else if(N % X != 0) {
			a = N / X + 1;
		}else {
			a = N / X;
		}

		System.out.println(a * T);
	}

}

Measured memory_bytes: 35684
# coding:utf-8
# 演算を辞書に押し込む
ops = {	"+": lambda a, b: b + a,
		"-": lambda a, b: b - a,
		"*": lambda a, b: b * a,
		"/": lambda a, b: b / a}

stack = []

for s in raw_input().split():
	if s in ops:
		stack.append(ops[s](stack.pop(), stack.pop()))
	else:
		stack.append(int(s))
print stack[-1]		

Measured memory_bytes: 4212
N = int(input())
S = input()
c = [str(i) for i in range(10)]
cands = []
for c1 in c:
    for c2 in c:
        for c3 in c:
            cands.append(c1 + c2 + c3)

cnt = 0
for c in cands:
    i = 0
    for s in S:
        if i == 3:
            break
            
        if c[i] == s:
            i += 1

    if i == 3:
        # print(c)
        cnt += 1
print(cnt)

Measured memory_bytes: 40796
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: an,bn,cn,ai,bi,ci
    character(100):: sa,sb,sc
    character(1):: t

    read*, sa
    read*, sb
    read*, sc
    an = len_trim(sa)
    bn = len_trim(sb)
    cn = len_trim(sc)

    ai=1;bi=1;ci=1
    t = 'a'
    
    do
        select case(t)
        case('a')
            if (ai > an) then
                print'(a)', 'A'
                stop
            end if
            t=sa(ai:ai)
            ai=ai+1
        case('b')
            if (bi > bn) then
                print'(a)', 'B'
                stop
            end if
            t=sb(bi:bi)
            bi=bi+1
        case('c')
            if (ci > cn) then
                print'(a)', 'C'
                stop
            end if
            t=sc(ci:ci)
            ci=ci+1
        end select
    end do
end program name

Measured memory_bytes: 256
a,b,m=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
#print(a,b,m)
#print(A)
#print(B)

total = 10**5+10**5
#print(total)

for i in range(m):
    x,y,c=map(int,input().split())
    #print(x,y,c)
    D = (A[x-1] + B[y-1] - c)
    if total > D:
        total = D
    #print(D)
A.sort()
B.sort()
if total > (A[0] + B[0]):
    total = (A[0] + B[0])
print(total)


Measured memory_bytes: 18608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define REPD(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


struct UnionFind{
    vector<ll> par;
    UnionFind(ll n) : par(n, -1){}
    

    int root(int x){
        if(par[x]<0) return x;
        return par[x] = root(par[x]);
    }

    bool same(int a, int b){
        return root(a)==root(b);
    }
    void unite(int a, int b){
        int x=root(a), y=root(b);
        if(same(x, y)) return;
        if(y<x) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
    int size(int x){
        return -par[root(x)];
    }

};


int main(){
    int n, m;   cin >> n >> m;
    vector<pair<ll, ll>> g(m);
    REP(i, m){
        ll a, b;    cin >> a >> b;
        a--, b--;
        g[i] = {a, b};
    }
    ll res=m;
    REP(i, m){
        ll a=g[i].first, b=g[i].second;
        UnionFind tree = UnionFind(n);
        for(auto x: g){
            if(x.first==a && x.second==b) continue;
            tree.unite(x.first, x.second);
        }
        if(tree.same(a, b)) res -= 1;
    } 
    cout << res << endl;

}

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

int main(){
    int h,w;
    cin >> h >> w;
    int s[h][w];
    int cnt = 0;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char c;
            cin >> c;
            if(c == '.'){
                s[i][j] = 0;
            }
            else{
                s[i][j] =  1;
                cnt++;
            }
        }
    }
    queue<pair<int,int>> que;
    que.push(make_pair(0,0));
    int d[h][w];
    const int inf = 10000;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            d[i][j] = inf;
        }
    }
    d[0][0] = 0;
    while(!que.empty()){
        auto p = que.front();
        que.pop();
        int x = p.first, y = p.second;
        if(x-1>=0 && d[x-1][y] == inf && s[x-1][y] == 0){
            que.push(make_pair(x-1,y));
            d[x-1][y] = d[x][y]+1;
        }
        if(x+1<h && d[x+1][y] == inf && s[x+1][y] == 0){
            que.push(make_pair(x+1,y));
            d[x+1][y] = d[x][y]+1;
        }
        if(y-1>=0 && d[x][y-1] == inf && s[x][y-1] == 0){
            que.push(make_pair(x,y-1));
            d[x][y-1] = d[x][y]+1;
        }
        if(y+1<w && d[x][y+1] == inf && s[x][y+1] == 0){
            que.push(make_pair(x,y+1));
            d[x][y+1] = d[x][y]+1;
        }
    }
    if(d[h-1][w-1] == inf) cout << -1 << endl;
    else cout << h*w - cnt - d[h-1][w-1] - 1 << endl;
    return 0;
}


Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    VI a,b;
    int n; R(n);
    LL sum=0;
    REP(i,n){
        int x,y;
        R(x,y);
        sum+=x;
        a.PB(x);
        b.PB(y);
    }
    if(a==b){
        W(0);
    }
    else{
        int mi=MOD;
        REP(i,n){
            if(a[i]>b[i])mi=min(mi,b[i]);
        }
        W(sum-mi);
    }
    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<ll> a(3*N);
  priority_queue<int, vector<int>, greater<int>> left;
  priority_queue<int> right;
  vector<ll> sum_left(N + 1),sum_right(N + 1);
  sum_left[0]=0; sum_right[N]=0;
  for(int i = 0; i < 3*N; i++){
    cin >> a[i];
    if(i <= N-1){
      left.push(a[i]);
      sum_left[0] += a[i];
    }
    else if(i >= 2*N){
      right.push(a[i]);
      sum_right[N] += a[i];
    }
  }
  for(int i = 0; i < N; i++){
    sum_left[i + 1] = sum_left[i] + a[N + i];
    left.push(a[N + i]);
    sum_left[i + 1] -= left.top();
    left.pop();
  }
  for(int i = 0; i < N; i++){
    sum_right[N - i - 1] = sum_right[N - i] + a[2*N - i - 1];
    right.push(a[2*N - i - 1]);
    sum_right[N - i - 1] -= right.top();
    right.pop();
  }
  ll ans = sum_left[0] - sum_right[0];
  for(int i = 1; i <= N; i++){
    ans = max(ans, sum_left[i] - sum_right[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 5368
// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 1000005;
string s;
int n;

bool check(int x, int y) {
  while (x <= y) {
    if (s[x] != s[y]) {
      return false;
    }
    x++, y--;
  }
  return true;
}

int main() {
  cin >> s;
  n = s.size();
  s = ' ' + s;
  if (check(1, n) && check(1, (n - 1) / 2) && check((n + 3) / 2, n)) {
    puts("Yes");
  } else {
    puts("No");
  }
  return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import kotlin.math.max

object Solve {

  private val br = BufferedReader(InputStreamReader(System.`in`))
  private val out = PrintWriter(System.out)

  fun solve() {

    var n = br.readLine()!!

    var sum = 0L

    for (c in n) {
      sum += (c - '0').toLong()
    }

    out.println(if (sum % 9 == 0L) "Yes" else "No")
    out.flush()
  }
}

fun main(args: Array<String>) {
  Solve.solve()
}

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

#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433L;

template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
std::vector<std::string> split(const std::string &str, const char delemiter) {std::vector<std::string> res;std::stringstream ss(str);std::string buffer; while( std::getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;}
int msb(int x) {return x?31-__builtin_clz(x):-1;}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; ++i) cin >> A[i];
    vector<ll> dp(N,0);
    dp[0]=1000;
    for(int i = 1; i < N; ++i) {
        for(int j = 0; j < i; ++j) {
            chmax(dp[i],dp[j]);
            ll m = dp[j];
            ll x = m/A[j], r = m%A[j];
            chmax(dp[i],A[i]*x+r);
        }
    }
    cout << dp.back() << endl;
    return 0;
}


Measured memory_bytes: 3636
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int d = sc.nextInt();
            if (!map.containsKey(d)) {
                map.put(d, 0);
            }
            map.put(d, map.get(d) + 1);
        }
        int m = sc.nextInt();
        List<Integer> t = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            t.add(sc.nextInt());
        }

        boolean ok = true;
        for (int i = 0; i < m; i++) {
            int x = t.get(i);
            if (!map.containsKey(x) || map.get(x) == 0) {
                ok = false;
                break;
            }
            map.put(x, map.get(x) - 1);
        }

        if (ok) {
            System.out.println("YES");
            return;
        }
        System.out.println("NO");
    }
}


Measured memory_bytes: 149100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)
int main()
{
     ios_base::sync_with_stdio(false);cin.tie(NULL);
     int i,n,t,p=INT_MAX,j=0,x,a=0,b,l=0,r=0,y,k,c,sum=0,m,d;
     cin>>n;
     for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            for(k=1;k<=n;k++){
                a=__gcd(i,j);
                sum+=__gcd(a,k);
 
            }
        }
     }
     cout<<sum<<endl;
 
     return EXIT_SUCCESS;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
 
const int INF = 1<<29;
 
int dp[256][16][128];
vector<P> stones[256];
 
int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);
 
  while (true) {
    int N, M;
    cin >> N >> M;
    if (N == 0 && M == 0) break;
   
    REP(i, N) {
      stones[i].clear();
      int k;
      cin >> k;
      REP(j, k) {
    int x, d;
    cin >> x >> d;
    stones[i].push_back(P(x, d));
      }
    }
 
    REP(i, N) REP(j, stones[i].size()) REP(k, M+1) dp[i][j][k] = INF;
    REP(j, stones[0].size()) dp[0][j][0] = 0;
    REP(j, stones[1].size()) dp[1][j][1] = 0;
    REP(i, N-1) {
      REP(j, stones[i+1].size()) {
    int x_now = stones[i+1][j].first, d_now = stones[i+1][j].second;
    REP(k, stones[i].size()) {
      int x_prev = stones[i][k].first, d_prev = stones[i][k].second;
      int safe = (d_now + d_prev) * abs(x_now - x_prev);
      REP(m, M+1) {
        dp[i+1][j][m] = min(dp[i+1][j][m], dp[i][k][m] + safe);
      }
    }
    if (i > 0) {
      REP(k, stones[i-1].size()) {
        int x_prev = stones[i-1][k].first, d_prev = stones[i-1][k].second;
        int safe = (d_now + d_prev) * abs(x_now - x_prev);
        REP(m, M) {
          dp[i+1][j][m+1] = min(dp[i+1][j][m+1], dp[i-1][k][m] + safe);
        }
      }
    }
      }
    }
 
    int ans = INF;
    REP(j, stones[N-1].size()) REP(m, M+1) ans = min(ans, dp[N-1][j][m]);
    REP(j, stones[N-2].size()) REP(m, M) ans = min(ans, dp[N-2][j][m]);
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2428
N, K = map(int, input().split())
P = list(map(int, input().split()))
numbers = [0,1,2,3,4,5,6,7,8,9]
use = []
for i in numbers:
  if not i in P:
    use.append(i)

ul = []
if 0 in use:
  for u5 in [0,use[1]]:
    for u4 in use:
      for u3 in use:
        for u2 in use:
          for u1 in use:
            ul.append(u5*10000 + u4*1000 + u3*100 + u2*10 + u1)
else:
    for u4 in use:
      for u3 in use:
        for u2 in use:
          for u1 in use:
            ul.append(use[0]*10000 + u4*1000 + u3*100 + u2*10 + u1)
            ul.append(u4*1000 + u3*100 + u2*10 + u1)
            ul.append(u3*100 + u2*10 + u1)
            ul.append(u2*10 + u1)
            ul.append(u1)
ul.sort()
for r in ul:
  if N <= r:
    print(r)
    break

Measured memory_bytes: 9668
n = int(input())
m = n
cnt = 0
while(m != 0):
    cnt += 1
    m = m // 10
ans = 0
if(n < 10):
    print(n)
elif(n < 100):
    print(9)
else:
    if(cnt % 2 == 0):
        k = 0
        while(k<cnt):
            ans += 9*10**k
            k += 2
    else:
        k = 1
        while(k<cnt):
            ans += 9*10**(k-1)
            k += 2
        d = n - 10**(k-1) + 1
        ans += d
    print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(void){
  int N,M;
  cin >> N >> M;
  
  vector<string>pic(N);
  
  for(int i=0;i<N;i++){
    cin >> pic[i];
  }
  
  for(int i=0;i<N;i++){
    cout << pic[i] << endl;
    cout << pic[i] << endl;
  }

  return 0;
}


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

int d, n, t[200], a[200], b[200], c[200];
int dp[210][210];

int main() {
	cin >> d >> n;
	for (int i = 0; i < d; i++) cin >> t[i];
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

	for (int i = 1; i < d; i++) {
		for (int j = 0; j < n; j++) {
			if (t[i - 1] < a[j] || b[j] < t[i - 1]) continue;
			for (int k = 0; k < n; k++) {
				if (t[i] < a[k] || b[k] < t[i]) continue;
				dp[i][k] = max(dp[i][k], dp[i - 1][j] + abs(c[j] - c[k]));
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) ans = max(ans, dp[d - 1][i]);
	cout << ans << endl;
}



Measured memory_bytes: 3248
#include <stdio.h> 
 #include <string.h> 
 
 
 int main(){ 
     int m, h; 
     char cards[256], temp[256], result[256]; 
     int i, j=0, len; 
 
 
     while(1){ 
         scanf("%s", cards); 
         len=strlen(cards); 
         if(strcmp(cards, "-")==0&&len==1)break; 
         scanf("%d", &m); 
         for(;m>0;m--){ 
             scanf("%d", &h); 
             strcpy(temp, cards); 
             for(i=0;i<h;i++){ 
                 cards[len-h+i]=temp[i]; 
             } 
             for(i=0;i<len-h;i++){ 
                 cards[i]=temp[i+h]; 
             } 
         } 
         for(i=0;i<len;i++){ 
             result[j++]=cards[i]; 
         } 
         result[j++]='\n'; 
     } 
     result[j]='\0'; 
     printf("%s", result); 
 
 
     return 0; 
}


Measured memory_bytes: 2040
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define CIN>>x scanf("%lld",&x);
#define all(v) v.begin(), v.end()
bool chmin(ll & a, ll  b) { if (b < a) { a = b; return 1; } return 0; }
bool chmax(ll & a, ll b) { if (b > a) { a = b; return 1; } return 0; }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N=500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
int main() {
    cin >> x>>y>>z;
    a=min({x,y,z});
    b=x+y+z-a-max({x,y,z});
    cout<<a*b/2<<endl;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int x, y, a, b, c;
	cin >> x >> y >> a >> b >> c;

	long long red[a], green[b], cless[c];
	for (int i = 0; i < a; ++i)
		cin >> red[i];
	for (int i = 0; i < b; ++i)
		cin >> green[i];
	for (int i = 0; i < c; ++i)
		cin >> cless[i];

	sort(red, a + red);
	sort(green, green + b);
	sort(cless, cless + c);

	vector<long long> res;
	for (int i = 0; i < x; i++)
		res.push_back(red[a - 1 - i]);
	for (int i = 0; i < y; i++)
		res.push_back(green[b - 1 - i]);

	sort(res.begin(), res.end());
	int j = 0;
	for (int i = c - 1; i >= 0; i--) {
		if (j >= res.size()) break;
		if (cless[i] > res[j]) {
			res[j] = cless[i];
			j++;
		}
	}

	long long ans = 0;
	for (long long x : res)
		ans += x;

	cout << ans;

	return 0;
}



Measured memory_bytes: 4852
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < n ; i++)
double dp[100][11000];
int V[100];
int move[100] = {};
int money[100] = {};
int main(){
	int X,Y,Z;
	while(cin >> X >> Y >> Z && X ){
		rep(i,100)rep(j,10001) dp[i][j] = 0.0;
		rep(i,100) move[i] = money[i] = 0;
		dp[0][0] = 1.0;
		for(int i = 0 ; i < X ; i++){
			cin >> V[i];
		}
		for(int i = 0 ; i < Z ; i++){
			int N,E,A;
			cin >> N >> E >> A;
			if( E == 1) move[N] = A;
			if( E == 2) money[N] = A;
			if( E == 3) money[N] = -A;
		}
		for(int i = 0 ; i < Y ; i++){
			for(int j = 0 ; j <= 10000 ; j++){
				if( dp[i][j] < 1e-9 ) continue;
				for(int k = 0 ; k < X ; k++){
					int next = min( Y , i + V[k] );
					int nextMoney = j;
					nextMoney += money[next];
					if( nextMoney < 0 ) nextMoney = 0;
					next += move[next];
					next = min( Y , next );
					dp[next][nextMoney] += dp[i][j] / X;
				}
			}
		}
		
		double ans = 0;
		for(int i = 0 ; i <= 10000 ; i++){
			ans += dp[Y][i] * i;
		}
		
		cout << (int)(ans + 1e-9) << endl;
		
	}
}

Measured memory_bytes: 9640
W, H, N = map(int, input().split())
xya = [list(map(int, input().split())) for _ in range(N)]
 
x1 = 0 #左端
x2 = W #右端
y3 = 0 #下端
y4 = H #上端
 
# 白い4角形が最小になる上下左右を見つける
for x,y,a in xya:
    if a == 1:
        x1 = max(x1, x)
    elif a == 2:
        x2 = min(x2, x)
    elif a == 3:
        y3 = max(y3, y)
    elif a == 4:
        y4 = min(y4, y)
else:
    # 右端が左端より左, 上端が下端より下,だと全部黒
    if x2 <= x1 or y4 <= y3:
        print(0)
    else:
        print((x2-x1) * (y4-y3))

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

ll a, b, c, d;

map<ll, ll> m;
ll dist(ll k) {
	if (m.find(k) != m.end()) {
		return m[k];
	}

	if (k == 0) {
		m[0] = 0;
		return 0;
	}
	if (k == 1) {
		m[1] = d;
		return d;
	}

	ll r = d * k;
	if (INF / d < k) {
		r = INF;
	}

	if (k % 2 == 0) {
		r = min(r, dist(k / 2) + a);
	}
	else {
		r = min({ r,dist(k / 2) + a + d,dist(k / 2 + 1) + a + d });
	}

	for (int i = -1; i <= 1; ++i) {
		if ((k + i) % 3 == 0) {
			r = min(r, dist((k + i) / 3) + b + d * abs(i));
		}
	}
	for (int i = -2; i <= 2; ++i) {
		if ((k + i) % 5 == 0) {
			r = min(r, dist((k + i) / 5) + c + d * abs(i));
		}
	}
	m[k] = r;

	return m[k];
}




int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		ll n;
		cin >> n;

		cin >> a >> b >> c >> d;
		m.clear();
		cout << dist(n) << endl;
	}

	
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long
long long INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

int main(){
    ll a,b,c;
    cin >> a;
    cout << a/3 <<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Task[] tasks;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		tasks = new Task[n];
		for(int i = 0; i < n; i++){
			long a = sc.nextLong();
			long b = sc.nextLong();
			tasks[i] = new Task(a, b);
		}
		Arrays.sort(tasks);
		boolean bool = true;
		long time = 0;
		for(int i = 0; i < n; i++){
			time += tasks[i].time;
			if(time > tasks[i].limit){
				bool = false;
				break;
			}
		}
		System.out.println(bool ? "Yes" : "No");
	}
}
class Task implements Comparable<Task>{
	long time;
	long limit;
	Task(long a, long b){
		time = a;
		limit = b;
	}
	@Override
	public int compareTo(Task t) {
		return (int) (this.limit - t.limit);
	}
}


Measured memory_bytes: 104340
#include <bits/stdc++.h>
using namespace std;
  
typedef long long int ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL); 
#define mod 1000000007
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define debug cout << "Hold right there sparky.....\n";
#define forn(low,high,i) for(i=low;i<high;i++)
#define forrev(high,low,i) for(i = high; i>= low;i--)

ll gcd(ll a,ll b)
{
	if(b==0)
		return a;
	else
		return gcd(b,b%a);
}

int main()
{
	   //      #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);    
    // freopen("output.txt", "w", stdout);
    //     #endif
   	
   ll n;
   cin>>n;
   cout<<(n-1)/2;
}

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

int main(){
    int a,b;
    int x,y;
    int n;
    
    while(std::cin >> a >> b){
        
        if(a == 0 && b == 0)
            break;
        
        std::cin >> n;
        
        std::vector<std::vector<int>> cor(b+1,std::vector<int>(a+1,0));
        std::vector<std::vector<int>> pro(b+1,std::vector<int>(a+1,0));
        
        while(n > 0 && std::cin >> x >> y){
            pro[y][x] = 1;
            --n;
        }
        
        if(pro[2][1] != 1)
            cor[2][1] = 1;
        
        if(pro[1][2] != 1)
            cor[1][2] = 1;
        
        for(int i = 1;i <= b;++i)
            for(int j = 1;j <= a;++j){
                if(pro[i][j] != 1)
                    cor[i][j] += cor[i-1][j] + cor[i][j-1];
            }
        std::cout << cor[b][a] << std::endl;
    }
}



Measured memory_bytes: 3152
#include<bits/stdc++.h>
#define rep(i,a,n) for (int i = a;i < n;i++)
#define per(i,n,a) for (int i = n-1;i >= a;i--)
using namespace std;

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


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

int main(){
    int H,W;cin>>H>>W;
    vector<string>field(H);
    vector<int>dx={-1,0,1,0};
    vector<int>dy={0,1,0,-1};
    bool flag2=true;
    rep(i,H){
        cin>>field.at(i);
    }
    rep(i,H){
        rep(j,W){
            bool flag=true;
            if(field.at(i).at(j)=='#'){
                flag=false;
                rep(k,4){
                    int ny=i+dy[k]; int nx=j+dx[k];
                    if(ny>=H||ny<0||nx>=W||nx<0){
                        continue;
                    }
                    if(field.at(ny).at(nx)=='#'){
                        flag=true;
                    }
                }
            }
            if(flag==false){
                flag2=false;
            }
        }
    }
    if(flag2){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int ans1=0,ans2=0;
const int N=1e5+5;
int arr[N];
int recur(int n,int k)
{
  int dp[n];
    dp[0]=0;

    for(int i=1;i<n;i++){
        if(i==1){
            dp[i]=abs(arr[0]-arr[1]);
        }

        else{
               int val=1e9;
            for(int c=i-1;c>=max(0LL,i-k);c--){

                val=min(val,dp[c]+abs(arr[i]-arr[c]));

            }

            dp[i]=val;
        }
    }
//    for(int i=0;i<n;i++){
//        cout<<dp[i]<<" ";
//    }
//    cout<<endl;
    return dp[n-1];
}
signed main()
{


    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++)cin>>arr[i];

    cout<<recur(n,k)<<endl;


    return 0;
}

Measured memory_bytes: 1792
/*input
6
4 2 9 7 1 5
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 3003;
vector < ll > v;
ll dp[N][N];

ll func(int l, int r)
{
	if(l > r) {
		return 0;
	}
	if(dp[l][r] > -1) {
		return dp[l][r];
	}

	ll a = v[l] + min(func(l + 2, r), func(l + 1, r - 1));
	ll b = v[r] + min(func(l + 1, r - 1), func(l, r - 2));
	return dp[l][r] = max(a, b);
}

int main()
{
  int n;
  cin >> n;
  v.resize(n);
  ll sum = 0;
  for(auto &x: v) {
  	cin >> x;
  	sum += x;
  }

  memset(dp, -1, sizeof(dp));
  ll d = func(0, n - 1);

  sum -= d;
  cout << d - sum;
  return 0;
}

Measured memory_bytes: 70912
import java.util.*;

public class Main{
  
  public static void main (String[] args){
  
  	Scanner scanner = new Scanner (System.in);
  
   	String N = scanner.nextLine();
    
    char a = N.charAt(0);
    char b = N.charAt(1);
    char c = N.charAt(2);
    char d = N.charAt(3);
    
    if (a==b && b==c){
      System.out.println("Yes");
    } else if (b==c && c==d){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<31);

using namespace std;

ll dp[1005][10005];
int n;
ll a[10005], b[10005];

// ll d(ll i, ll j){
//   if(j <= 0) return dp[i][j] = 0;
//   if(i == n) return dp[i][j] = INF;
//   if(dp[i][j] != -1) return dp[i][j];
//   return dp[i][j] = min({b[i] + d(i+1, j-a[i]), b[i] + d(i, j-a[i]), d(i+1, j)});
// }

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll h; cin >> h >> n;
    f(i, n) cin >> a[i] >> b[i];
    fo(i, 1, h+1) dp[n][i] = INF;
    for(ll i = n-1; i >= 0; i--){
      fo(j, 1, h+1){
        if(j - a[i] < 0) dp[i][j] = min(b[i], dp[i+1][j]);
        else{
          dp[i][j] = min({b[i] + dp[i+1][j-a[i]], b[i] + dp[i][j-a[i]], dp[i+1][j]});
        }
      }
    }
    cout << dp[0][h] << endl;
    return 0;
}


Measured memory_bytes: 78592
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n];
    int sum=0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        sum += a[i];
    }
    int ans = 1000000;
    for(int h=-100;h<=100;h++){
        int num = 0;
        for(int i=0; i<n; i++){
            num += (a[i]-h)*(a[i]-h);
        }
        ans=min(ans,num);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256