akhauriyash/Code-Regression huggingface dataset:
def solve():
    H, W, K = map(int, input().split())
    s = []
    berryNum = 1
    noBerryRowIdx = []
    for i in range(H):
        ipt = input()
        firstBerry = ipt.find('#')
        ipt = list(ipt)
        if firstBerry >= 0:
            ipt[firstBerry] = '.'
            ipt[0] = '#'

            for ch in range(W):
                
                if ipt[ch] == '.':
                    if ch != 0 and str.isdigit(ipt[ch - 1]):
                        ipt[ch] = ipt[ch - 1]
                    else:
                        ipt[ch] = '0'
            
                if ipt[ch] == '#':
                    ipt[ch] = str(berryNum)
                    berryNum += 1
        else:
            noBerryRowIdx.append(i)

        s.append(ipt)
    
    for i in noBerryRowIdx:
        if i != 0:
            s[i] = s[i - 1]
    
    for i in reversed(noBerryRowIdx):
        if i != H - 1:
            s[i] = s[i+1]

    for line in s:
        print(*line)
    
if __name__ == '__main__':
    solve()

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

#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcd(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

  int n;
  cin >> n;
  vt<double> p(n);
  rep(i, 0, n) cin >> p[i];

  vvt<double> dp(n + 1, vt<double>(n + 1, 0.0));
  dp[0][0] = 1.0;
  rep(i, 0, n) {
    rep(j, 0, i + 1) {
      dp[i + 1][j + 1] += dp[i][j] * p[i];
      dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
    }
  }

  double ans = 0.0;
  rep(i, (n + 1) / 2, n + 1) ans += dp[n][i];
  cout << fixed << setprecision(20) << ans << endl;
}

Measured memory_bytes: 70784
N=int(input())
xy = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        x -= 1
        xy[i].append((x,y))
ans = 0
s = set()
t = set()
def true(s,t,j):
    if j not in t:
        s.add(j)
        return False
    return True
def false(s,t,j):
    if j not in s:
        t.add(j)
        return False
    return True
def chk(i):
    s = set()
    t = set()
    fl = False
    for j in range(N):
        if (i>>j)&1:
            fl |= true(s,t,j)
            for x,y in xy[j]:
                fl |= true(s,t,x) if y == 1 else false(s,t,x)
        else:
            fl |= false(s,t,j)
    return fl
ans = 0
for i in range(2**N):
    if chk(i):
        continue
    cnt = 0
    for j in range(N):
        if (i>>j)&1:
            cnt += 1
    ans = max(ans, cnt)
print(ans)

Measured memory_bytes: 9116
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <cassert>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
typedef long long ll;
typedef pair<int,int> Pii;
const int INF=(1<<30)-1;
const int MAX=310;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}
int main(){
	int n,m;
	cin>>n>>m;
	int p[n]={};
	REP(i,m){
		int a,b;
		cin>>a>>b;
		p[a]++;
		p[b]++;
	}
	REP(i,n){
		if(p[i]%2!=0){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<string.h>
using namespace std;
char s[110],s1[110],s2[110];
bool check(char s[110])
{
	int i,l=strlen(s);
	for(i=0;i<l/2;i++)
		if(s[i]!=s[l-i-1])return 0;
	return 1;	
}
int main()
{
	cin>>s;
	int i,l=strlen(s);
	for(i=0;i<(l-1)/2;i++)
	    s1[i]=s[i];
	for(i=(l+3)/2-1;i<l;i++)
	    s2[i]=s[i];
	if(check(s))
	{
		if(check(s1))
		{
			if(check(s2))cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
		else cout<<"No"<<endl;
	}	    
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#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()

typedef long long lint;

using namespace std;

int main(){
  string S;
  cin>>S;
  int s=0;
  for(auto c:S){
    if(c=='o')s++;
  }
  cout<<(s+(15-S.size())>=8?"YES":"NO")<<endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin
import math

[N, x] = list(map(int, stdin.readline().rstrip().split()))
a = list(map(int, stdin.readline().rstrip().split()))

a_sorted = sorted(a)


count=0
for i in range(N):
    #x -= a_sorted[i]
    x = x - a_sorted[i]
    if x >=0:
        count += 1
    else:
        break

if x > 0:
    count -= 1

print(count)


Measured memory_bytes: 3060
a,b = map(int, input().split())
if a>0 and b>0:
    print("Positive")
elif a<=0 and b>=0:
    print("Zero")
elif a<0 and b<0:
    if (b-a+1)%2 == 0:
        print("Positive")
    elif(b-a+1)%2 == 1:
        print("Negative")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int64_t powermod(int64_t x, int64_t y, int64_t p){
  if(y < 0 || x <= 0)
    return 0;
  else{
    int64_t n = 1;
    x %= p;
    for(int64_t i = 0; i < y; i++){
      n = n*x%p;
    }
    return n;
  }
}
int main() {
    int h, w;
    cin >> h >> w;
    vector<string>ss(h);
    rep(i,h) cin >> ss[i];
    vector<vector<bool>> s(h,vector<bool>(w,true));
    rep(i,h){
        rep(j,w){
            if(ss[i][j] == '#') s[i][j] = false;
        }
    }

    vector<vector<int>> cnt1(h,vector<int>(w,0));
    rep(i,h){
        if(s[i][0]) cnt1[i][0] = 1;
        for(int j = 1; j < w; j++)
            if(s[i][j])  
                cnt1[i][j] = cnt1[i][j-1]+1;
    }
    rep(i,h){
        for(int j = w-2; j >= 0; j--){
            if(s[i][j+1] && s[i][j]) cnt1[i][j] = cnt1[i][j+1];
        }
    }

    vector<vector<int>> cnt2(h,vector<int>(w,0));
    rep(j,w){
        if(s[0][j]) cnt2[0][j] = 1;
        for(int i = 1; i < h; i++)
            if(s[i][j])  
                cnt2[i][j] = cnt2[i-1][j]+1;
    }
    rep(j,w){
        for(int i = h-2;i >= 0; i--){
            if(s[i+1][j] && s[i][j]) cnt2[i][j] = cnt2[i+1][j];
        }
    }

    vector<vector<int>> cnt(h,vector<int>(w,0));
    rep(i,h)rep(j,w) cnt[i][j] = cnt1[i][j]+cnt2[i][j]-1;
/*
    rep(i,h){
        rep(j,w){
            cout << cnt1[i][j] << ",";
        }
        cout << endl;
    }
*/
    rep(i,h){
        sort(cnt[i].begin(),cnt[i].end());
        reverse(cnt[i].begin(),cnt[i].end());
    }
    sort(cnt.begin(),cnt.end());
    reverse(cnt.begin(),cnt.end());
    cout << cnt[0][0] << endl;
}

Measured memory_bytes: 52224
H, W = map(int, input().split())
a = []
for i in range(H):
  b = list(input())
  a.append(b)
for i in range(2*H):
  for j in range(W):
    if j != W - 1:
      print(a[i//2][j],end="")
    else:
      print(a[i//2][j])

Measured memory_bytes: 4596
N, K = map(int, input().split())
D = list(map(str, input().split()))
for i in range(N, 10**18):
  num = i
  i = str(i)
  for j in range(len(str(num))):
    if i[-1] in D:
      num=0
      break
    else:
      i = i[:-1]
      continue
  if num:
    print(num)
    break

Measured memory_bytes: 3060
/*
 *Author - Abhas Jain
 *Code is inside the solve function
 */
 
#include <bits/stdc++.h>
 
#define F first
#define S second
#define all(c) c.begin(), c.end()
#define endl '\n'
#define pb push_back
#define mp make_pair 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
 
typedef long long ll;
typedef long double ld;

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define bac(i,a,b) for(ll i=a;i>=b;i--)

 
using namespace std;
using namespace __gnu_pbds;
template <typename A, typename B>
string to_string(pair<A, B> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef AJ47
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const ld PI = 3.141592653589793;
const ll INF = 9223372036854775807ll;
const ll mod = 1e9 + 7;
 
void solve() 
{
    int n, m;
    cin >> n >> m;
    ll cur = 0, pp = 0;
    vector<int> p(n, 0);
    vector<int> pen(n, 0);
    for (int i = 0; i < m; ++i) {
    	int c;
    	cin >> c;
    	c--;
    	string s;
    	cin >> s;
    	if (s[0] == 'W') {
    		if (!p[c]) pen[c]++;
    	} else {
    		if (!p[c]) cur++;
    		p[c]++;
    	}
    }
    for (int i = 0; i < n; ++i) {
    	if (p[i]) pp += pen[i];
    }
    cout << cur << " " << pp << endl;
}
 
int main( )
{   
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
int main(){
    int a,b,c,X,ans=0,mas=0;
    cin >> a >> b >> c >> X;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                    mas=i*500+j*100+k*50;
                if(X==mas){
                    ans++;
                }
            }
        }
    } 
    cout << ans << endl;
}

Measured memory_bytes: 256
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

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

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

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()

if n==1:
    print(0)
    exit()

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

# """nを素因数分解"""
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
# print(factorization(m))
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

a = factorization(n)
# print(a)

ls = []
count = -1
wa = 0
for i in range(40):
    count += 1
    wa += count
    ls.append(wa)
# print(ls)

ans = 0
for _,m in a:
    ind = bisect_right(ls,m)
    ans += ind-1
print(ans) 

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<ll,ll>;

template <typename M>
struct SegmentTree{
    using T = typename M::type;

    int numLeaves;
    std::vector<T> data;
    
    SegmentTree(int n){
        numLeaves = 1;
        while(numLeaves < n){
            numLeaves *= 2;
        }
        
        data.resize(numLeaves * 2);
        std::fill(data.begin() + numLeaves, data.end(), M::identity());
        
        for(int i=numLeaves-1;i>0;--i){
            data[i] = M::bop(data[i*2], data[i*2+1]);
        }
    }

    template <typename F>
    SegmentTree(int n, F f){
        numLeaves = 1;
        while(numLeaves < n){
            numLeaves *= 2;
        }

        data.resize(numLeaves * 2);
        for(int i=0;i<n;++i){
            data[i + numLeaves] = std::move(f(i));
        }
        std::fill(data.begin() + numLeaves + n, data.end(), M::identity());

        for(int i=numLeaves-1;i>0;--i){
            data[i] = M::bop(data[i*2], data[i*2+1]);
        }
    }

    void set(int k, T v){
        k += numLeaves;
        data[k] = v;
        
        while(k > 1){
            k /= 2;
            data[k] = M::bop(data[k*2], data[k*2+1]);
        }
    }
    
    T product(int l, int r){
        l += numLeaves;
        r += numLeaves;
        
        T pl = M::identity(), pr = M::identity();
        for(;l<r;l/=2,r/=2){
            if(l & 1){
                pl = M::bop(pl, data[l]);
                l += 1;
            }
            if(r & 1){
                r -= 1;
                pr = M::bop(data[r], pr);
            }
        }
        
        return M::bop(pl, pr);
    }
    
    T at(int i){
        return data[i + numLeaves];
    }
};

struct M{
    using type = ll;
    static type identity(){
        return 0;
    }
    static type bop(type &m1, type &m2){
        return m1 + m2;
    }
};

SegmentTree<M> seg(200100);
ll N, D, A;
P ps[200100];
std::vector<ll> xs;

ll damage(ll x){
    int i = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin();

    return seg.product(0, i + 1);
}

void attack(ll x, ll t){
    int l = std::lower_bound(xs.begin(), xs.end(), x) - xs.begin(),
        r = std::upper_bound(xs.begin(), xs.end(), x + 2ll * D) - xs.begin();

    seg.set(l, seg.at(l) + t * A);
    seg.set(r, seg.at(r) - t * A);
}

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

    std::cin >> N >> D >> A;

    xs.resize(N);

    for(int i=0;i<N;++i){
        ll X, H;
        std::cin >> X >> H;

        ps[i] = std::make_tuple(X, H);
        xs[i] = X;
    }

    std::sort(ps, ps + N);
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
  
    ll res = 0;

    for(int i=0;i<N;++i){
        ll X, H;
        std::tie(X, H) = ps[i];

        ll d = damage(X), r = std::max<ll>(H - d, 0), t = (r + A - 1) / A;

        res += t;
        attack(X, t);
    }

    std::cout << res << std::endl;
}


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

#define X first
#define Y second
#define MP make_pair

using namespace std;

typedef long long ll;

const int N = 1e5 + 12;
const ll mod = 1e9 + 7;

int n;

int main () {
	n = 3;
	map<int, int> mp;
	for(;n--;){
		int x;
		scanf("%d", &x);
		mp[x] += 1;
	}
	if(mp[5] == 2 && mp[7] == 1){
		cout << "YES";
	}
	else{
		cout << "NO";
	}
}


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

#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 2e9, mod = 998244353;

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n; cin >> n;
    vector<pair<ll, ll>> robot(n + 1);
    vector<ll> dp(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> robot[i].first >> robot[i].second;
    }

    robot[n] = make_pair(inf, inf);
    sort(all(robot));
    dp[n] = 1;
    vector<int> st = {n};

    for (int i = n - 1; i >= 0; --i) {
        ll gor = robot[i].first + robot[i].second;
        while (!st.empty() && robot[st.back()].first < gor) 
            st.pop_back();

        dp[i] = (dp[i] + dp[i + 1] + dp[st.back()]) % mod;
        st.push_back(i);
    }

    cout << dp[0] << '\n';

}

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

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

const int MAXN = 1e5;
const int MAXM = 100;

int N, M;
vector<int> V1, V2, A, B;

int main()
{
    int i, j;

    scanf("%d%d", &N, &M);
    int cnt=0;
    for(i=1; i<=M; i++)
    {
        int X; scanf("%d", &X);
        if(X%2) V2.push_back(X), cnt++;
        else V1.push_back(X);
    }
    if(cnt>2) return !printf("Impossible");

    if(cnt>0) A.push_back(V2[0]);
    for(i=0; i<V1.size(); i++) A.push_back(V1[i]);
    if(cnt>1) A.push_back(V2[1]);

    if(A.size()==1)
    {
        if(A[0]>1) B.push_back(A[0]-1);
        B.push_back(1);
    }
    else
    {
        B.push_back(A[0]+1);
        for(i=1; i+1<A.size(); i++) B.push_back(A[i]);
        if(A.back()>1) B.push_back(A.back()-1);
    }

    for(i=0; i<A.size(); i++) printf("%d ", A[i]);
    printf("\n%d\n", B.size());
    for(i=0; i<B.size(); i++) printf("%d ", B[i]);
}


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

int main()
{
	int N, K;
	cin >> N >> K;
	
	// check upper bound
	if (K > (N-1) * (N-2) / 2)
	{
		cout << -1 << '\n';
		return 0;
	}

	// construct graph with max amount of distance-2 vertices
	vector<pair<int, int>> edges;
	for (int i = 1; i < N; ++i)
		edges.push_back({0, i});
	
	// add edges to decrease distance-2 vertices
	int remove = (N-1) * (N-2) / 2 - K;
	for (int i = 1; i < N - 1; ++i)
	{
		for (int j = i + 1; j < N; ++j)
		{
			// check to see if we have a proper amount of distance-2 vertices
			if (remove == 0)
			{
				cout << edges.size() << '\n';
				for (auto& edge : edges)
					cout << edge.first+1 << ' ' << edge.second+1 << '\n';
				return 0;
			}
			
			edges.push_back({i, j});
			remove--;
		}
	}
	
	// complete graph case
	cout << edges.size() << '\n';
	for (auto& edge : edges)
		cout << edge.first+1 << ' ' << edge.second+1 << '\n';
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		int n1,n2;
		String str1,str2;

        Scanner in = new Scanner(System.in);

        str1 = in.next();
        str2 = in.next();

        n1 = Integer.parseInt(str1);
        n2 = Integer.parseInt(str2);

        System.out.println(n1*n2 + " " + (n1*2 + n2*2) );

        in.close();
    }
}

Measured memory_bytes: 25984
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using Vertex = std::uint32_t;
using Weight = std::uint32_t;
using Graph = std::vector<std::vector<std::pair<Vertex, Weight>>>;

const auto Inf = std::numeric_limits<Weight>::max();
std::vector<Weight> Dijkstra(const Vertex s, const Graph& g)
{
    auto n = g.size();
    auto dist = std::vector<Weight>(n, Inf);
    dist[s] = 0;

    auto comp = [](auto x, auto y) { return x.second > y.second; };
    auto q =
        std::priority_queue<std::pair<Vertex, Weight>, std::vector<std::pair<Vertex, Weight>>, decltype(comp)>(comp);

    auto visited = std::vector<bool>(n, false);
    q.emplace(s, dist[s]);
    while (!q.empty())
    {
        auto v = q.top().first;
        q.pop();

        if (visited[v]) continue;

        visited[v] = true;

        for (const auto& node : g[v])
        {
            auto v_n = node.first;
            auto d_n = node.second;

            if (dist[v_n] > dist[v] + d_n)
            {
                dist[v_n] = dist[v] + d_n;
                q.emplace(v_n, dist[v_n]);
            }
        }
    }
    return dist;
}
int main()
{
    auto n = Vertex();
    auto m = Vertex();
    auto r = Weight();

    std::cin >> n >> m >> r;

    auto c = std::vector<Vertex>(r);
    for (Vertex i = 0; i < r; ++i)
    {
        std::cin >> c[i];
        --c[i];
    }
    std::sort(c.begin(), c.end());
    auto g = Graph(n);
    for (Vertex i = 0; i < m; ++i)
    {
        Vertex a;
        Vertex b;
        Vertex w;

        std::cin >> a >> b >> w;

        g[a - 1].emplace_back(b - 1, w);
        g[b - 1].emplace_back(a - 1, w);
    }

    auto dist_list = std::vector<std::vector<Weight>>();
    dist_list.reserve(r);
    for (Vertex s = 0; s < n; ++s)
    {
        dist_list.emplace_back(Dijkstra(s, g));
    }

    auto result = Weight(Inf);
    do
    {
        auto distance = Weight(0);
        for (Vertex i = 0; i < r - 1; ++i) distance += dist_list[c[i]][c[i + 1]];

        if (distance < result) result = distance;

    } while (std::next_permutation(c.begin(), c.end()));

    std::cout << result << std::endl;

    return 0;
}

Measured memory_bytes: 896
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var W = input[1].split(" ").map(i => parseInt(i));
  var ans=100000000;
  var sum1=0;
  var sum2=0;
  for(var i=0;i<N;i++){
    sum1+=W[i];
  }
  for(var i=0;i<N;i++){
    sum2+=W[i];
    ans=Math.min(ans,Math.abs(sum2-(sum1-sum2)));
  }

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val h = sc.nextInt()
    val w = sc.nextInt()
    val ch = sc.nextInt() - 1
    val cw = sc.nextInt() - 1
    val dh = sc.nextInt() - 1
    val dw = sc.nextInt() - 1
    val s = Array(h) { Array(w) { '.' } }
    for (i in 0 until h) {
        val _s = sc.nextLine()
        for (j in 0 until w) {
            s[i][j] = _s[j]
        }
    }
    val dist = Array(h) { Array(w) { Int.MAX_VALUE } }
    val deque = ArrayDeque<Triple<Int, Int, Int>>()
    deque.addFirst(Triple(ch, cw, 0))
    val visited = Array(h) { Array(w) { false } }
    while (deque.count() > 0) {
        val (i, j, d) = deque.pollFirst()
        if (visited[i][j]) continue
        dist[i][j] = d
        visited[i][j] = true
        val ai = arrayOf(i - 1, i, i + 1, i)
        val aj = arrayOf(j, j - 1, j, j + 1)
        for (k in 0 until 4) {
            val ni = ai[k]
            val nj = aj[k]
            if (ni in 0 until h && nj in 0 until w && !visited[ni][nj] && s[ni][nj] == '.') {
                deque.addFirst(Triple(ni, nj, d))
            }
        }
        val bi = arrayOf(i - 2, i - 1, i, i + 1, i + 2)
        val bj = arrayOf(j - 2, j - 1, j, j + 1, j + 2)
        for (k in 0 until 5) {
            for (l in 0 until 5) {
                val ni = bi[k]
                val nj = bj[l]
                if (ni in 0 until h && nj in 0 until w && !visited[ni][nj] && s[ni][nj] == '.') {
                    deque.addLast(Triple(ni, nj, d + 1))
                }
            }
        }
    }
    println(if (dist[dh][dw] == Int.MAX_VALUE) -1 else dist[dh][dw])
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 109232
IDENTIFICATION DIVISION.
PROGRAM-ID. 103C.
ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
  SELECT STDIO ASSIGN TO KEYBOARD. 
*>
DATA DIVISION.
FILE SECTION.
FD STDIO.
01 INP   PIC X(700000).
*>
WORKING-STORAGE SECTION.
01 N         PIC 9(6) COMP.
01 H         PIC 9(6) COMP.
01 N1        PIC 9(6) COMP VALUE 100000.
01 TBL1.
   03 TBL1-S                OCCURS 100000 DEPENDING ON N1. 
      05 K1  PIC 9(6).
      05 V1  PIC 9(6).
01 TBL2.      
   03 TBL2-S                OCCURS 100000 DEPENDING ON N1. 
      05 K2  PIC 9(6).
      05 V2  PIC 9(6).
01 VW        PIC 9(6) COMP.
01 CNT       PIC 9(6) COMP.
01 OUT       PIC Z(5)9.
01 P1        PIC 9(6) COMP.
01 P2        PIC 9(6) COMP.
01 I         PIC 9(6) COMP.
01 IX        PIC 9(1).
*>
PROCEDURE DIVISION.
  ACCEPT N.
  COMPUTE H = N / 2. 
*>
  OPEN INPUT STDIO.
  READ STDIO.
  CLOSE STDIO.
*>
  MOVE ZERO TO TBL1 TBL2 CNT.
  MOVE 1    TO P1 IX.
  PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
    PERFORM VARYING P2 FROM P1 BY 1 UNTIL INP(P2:1) = ' '
    END-PERFORM
  *>
    MOVE INP(P1:P2 - P1) TO VW
    IF (IX = 1)
      ADD  1  TO K1(VW)
      MOVE VW TO V1(VW)
    ELSE
      ADD  1  TO K2(VW)
      MOVE VW TO V2(VW)
    END-IF  
  *>
    COMPUTE IX = 3 - IX
    COMPUTE P1 = P2 + 1    
  END-PERFORM.
*>
  SORT TBL1-S DESCENDING KEY K1.
  SORT TBL2-S DESCENDING KEY K2.
*>
  EVALUATE TRUE
    WHEN (V1(1) = V2(1))
      IF (K1(1) + K2(2) >= K1(2) + K2(1))
        COMPUTE CNT = N - K1(1) - K2(2)
      ELSE
        COMPUTE CNT = N - K1(2) - K2(1)
      END-IF       
    WHEN OTHER
      COMPUTE CNT = N - K1(1) - K2(1)
  END-EVALUATE.
*>
  MOVE CNT TO OUT.
  DISPLAY FUNCTION TRIM(OUT).
  STOP RUN.


Measured memory_bytes: 4272
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			(3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
template<class T> void chmax(T &a, const T &b){if(a<b)a=b;}
template<class T> void chmin(T &a, const T &b){if(a>b)a=b;}
void YN(bool b){cout<<(b?"YES":"NO")<<endl;}
void Yn(bool b){cout<<(b?"Yes":"No")<<endl;}
void yn(bool b){cout<<(b?"yes":"no")<<endl;}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,in,gc=1,gd=1;
	cin>>n;
	rep(i,n){
		cin>>in;
		gc=gcd(gd,in);
		gd=(gd*in)/gc;
	}
	cout<<gd<<endl;
}




Measured memory_bytes: 3216
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  ll N;
   ll M;
  cin >>N>>M;
  vl L(M);
  vl R(M);
  rep(i,M) {
    cin >>L.at(i)>>R.at(i);
  }
  sort(all(L));
  sort(all(R));
  
  ll x=L.at(M-1);
  ll y=R.at(0);
  ll count=1;
  if(x<=y) {
  rep(i,N) {
if(x<y) {
  count++;
  x=x+1;
  
}
if(x==y) {
  break;
}
  }
  cout<<count<<endl;
}
  else {
    cout<<0<<endl;
  }
  
  
}
 

Measured memory_bytes: 1792
n,k=map(int, input().split())
s=list(input())
k=k-1
if s[k] == "A":
    s[k] = "a"
if s[k] == "B":
    s[k] = "b"
if s[k] == "C":
    s[k] = "c"

print("".join(s))

Measured memory_bytes: 3060
import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

a,b,c,k = Ri()
ans = 0
ans+=(min(a,k))
k-=min(a,k)
k-=min(b,k)
ans-=min(k,c)

print(ans)

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

const int MAXV = 101010;
const ll INF = 1e17;
struct edge { ll to, cost; edge(int t=0, int c=0) : to(t), cost(c) {} };
int V;
vector<edge> G[MAXV];
ll d[MAXV];

void dijkstra(int s) {
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(make_pair(0, s));

    while (!que.empty()) {
        pair<ll, ll> p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    int M;
    cin >> V >> M;
    for (int i=V-1; i>0; --i) {
        G[i].emplace_back(i-1, 0);
    }

    rep(i, M) {
        ll l, r, c;
        cin >> l >> r >> c;
        l--; r--;
        G[l].emplace_back(r, c);
    }

    dijkstra(0);
    if (d[V-1] == INF) {
        cout << -1 << endl;
    }
    else {
        cout << d[V-1] << endl;
    }
}


Measured memory_bytes: 10232
#include<stdio.h>

int main(){
	int a,b,c,d;
	
	scanf("%d %d %d %d",&a,&b,&c,&d);
	
	while(a >= 0 && c>= 0){
		c -= b;
		if(c <= 0){
			printf("Yes");
			return 0;
		}
		a -= d;
		if(a <= 0){
			printf("No");
			return 0;
		}
		
	}
	
	
	return 0;
} 

Measured memory_bytes: 1664
# 入力
N = int(input())
C = [int(input()) for _ in range(N)]

# 現時点で最も左の、色C_iの石が存在する負のインデックス（0は存在しないことを表す）
k = [0 for _ in range((2 * 10**5) + 1)]

# 動的計画法により解を求める
dp = [0 for _ in range(N)]
k[C[-1]] = -1
dp[-1] = 1
for i in range(2, N + 1):
    if k[C[-i]] == 0 or k[C[-i]] == -i + 1:
        dp[-i] = dp[-i + 1]
    else:
        dp[-i] = (dp[-i + 1] + dp[k[C[-i]]]) % (10**9 + 7)
    k[C[-i]] = -i
ans = dp[0]

# 出力
print(ans)

Measured memory_bytes: 20532
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 
using namespace std;
int main()
{
    int n;
    vector<tuple<string,int,int>> vec;
    while (~scanf("%d", &n)) {
        vec.clear();
        REP(i,1,n) {
            string x;
            int y;
            cin >> x >> y;
            vec.push_back( make_tuple(x, -y, i) );
        }
        sort(vec.begin(), vec.end());
        for (auto i:vec) {
            string x;
            int y,z;
            tie(x,y,z) = i;
            printf("%d\n", z);
        }
    }
    return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

class Edge {
    int from, to;
    this(int from, int to) {
        this.from = from;
        this.to = to;
    }
    override string toString() {
        return [from, to].to!string;
    }
}
class Graph {
    Edge[][] G;
    int V;
    this(int V) {
        this.V = V;
        G = new Edge[][V];
    }
    void addEdge(int from, int to) {
        G[from] ~= new Edge(from, to);
        G[to] ~= new Edge(to, from);
    }
    int[] findArticulations() {
        auto dfs_order = new int[V];
        auto lowlink = new int[V];
        dfs_order[] = -1;
        int c = 0;
        int[] articulations;
        void dfs(int v, int prev) {
            int children_count = 0;
            bool articulation = false;
            dfs_order[v] = c++;
            lowlink[v] = dfs_order[v];
            foreach (e; G[v]) {
                auto next = e.to;
                if (next == prev) continue;
                if (dfs_order[next] >= 0) { 
                    // already visited. this 'e' is backedge.
                    lowlink[v] = min(lowlink[v], dfs_order[next]);
                } else {
                    children_count++;
                    dfs(next, v);
                    lowlink[v] = min(lowlink[v], lowlink[next]);
                    if (v > 0 && dfs_order[v] <= lowlink[next]) {
                        articulation = true;
                    }
                }
            }
            if (v == 0 && children_count >= 2) articulation = true;
            if (articulation) articulations ~= v;
        }
        dfs(0, -1);
        return articulations;
    }
}

void main() {
    int V, E; scanf("%d %d\n", &V, &E);
    auto graph = new Graph(V);
    foreach (i; 0 .. E) {
        int s, t; scanf("%d %d\n", &s, &t);
        graph.addEdge(s, t);
    }
    auto ans = graph.findArticulations();
    sort(ans);
    foreach (a; ans) {
        writefln("%d", a);
    }
}

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

typedef long long ll;
#define FOR(i, a, n) for (ll i=(ll)a;i<(ll)n;i++)
#define REP(i, n) FOR(i, 0, n)

int main(){
    int n, m; cin >> n >> m;

    struct data_t{
        int num;
        ll cost;
    };
    vector<data_t> c; c.resize(n);

    REP(i, n){
        cin >> c[i].cost >> c[i].num;
    }

    sort(c.begin(), c.end(), 
        [](const data_t &a, const data_t &b){return a.cost < b.cost;});

    int left = m;
    ll ans = 0;

    REP(i, n){
        if (left<=c[i].num){
            ans += c[i].cost * left;
            break;
        }
        else{
            ans += c[i].cost * c[i].num;
            left -= c[i].num;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    s=set(range(N))
    for _ in range(M):
        x,y=map(lambda x: int(x)-1,input().split())
        edge[x].append(y)
        try:
            s.remove(y)
        except:
            pass
    que=list(s)
    memo=[0]*N
    def saiki(v):
        if memo[v]:
            return memo[v]
        tmp=0
        for nv in edge[v]:
            memo[v]=max(memo[v],saiki(nv)+1)
            tmp=max(tmp,memo[v])
        return tmp
    ans=0
    for v in que:
        ans=max(ans,saiki(v))
    print(ans)
    
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 130084
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
using namespace std;
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(b - a == c - b) cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <cmath>
#include <iterator>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

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

    vector<int> heights;
    int h;
    for (int i = 0; i < n; ++i)
    {
        cin >> h;
        heights.push_back(h);
    }

    vector<int> intermediate(n, 0);
    for (int i = n-2; i >= 0; --i)
    {
        int h = heights[i];
        int min = -1;
        for (int l = 1; l <= k; l++)
        {
            if (i + l > n - 1) break;
            int tmp = std::abs(h - heights[i + l]) + intermediate[i + l];
            if (min == -1 || tmp < min)
            {
                min = tmp;
            }
        }
        intermediate[i] = min;
    }

    cout << intermediate[0];
    return 0;
}


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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if (A+B>C+D) {
    cout << "Left" << endl;
  }
  
  else if (A+B==C+D) {
    cout << "Balanced" << endl;
  }
  
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static BigInteger MOD = BigInteger.valueOf((long) 1e9 + 7);

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++)
            p[i] = in.nextInt();

        int[] sorted = p.clone();
        Arrays.sort(sorted);

        boolean flag = false;
        if (equals(p, sorted)) {
            out.println("YES");
            return;
        }

        search:
        for (int i=0; i < n-1; i++) {
            for (int j=i+1; j < n; j++) {
                int[] swapped = swap(p.clone(), i, j);
                if (equals(swapped, sorted)) {
                    flag = true;
                    break search;
                }
            }
        }

        out.println(flag ? "YES" : "NO");
    }

    private static int[] swap(int[] p, int i, int j) {
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
        return p;
    }

    private static boolean equals(int[] a, int[] b) {
        for (int i1 = 0; i1 < a.length; i1++) {
            if (b[i1] != a[i1])
                return false;
        }
        return true;
    }

}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int n,k;

main(){
  cin>>n>>k;
  vector<int> a(n);

  rep(i,n){
    cin>>a[i];
  }

  int ans=INF;

  rep(i,n-k+1){
    int l=a[i],r=a[i+k-1];

    if(l*r<0){
      l=abs(l);
      r=abs(r);
      ans=min(ans,min(l,r)*2+max(l,r));
    }else{
      l=abs(l);
      r=abs(r);
      ans=min(ans,max(l,r));
    }
  }


  cout<<ans<<endl;
}


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

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    int dx = tx - sx;
    int dy = ty - sy;

    cout << string(dy, 'U') << string(dx, 'R');
    cout << string(dy, 'D') << string(dx, 'L');
    cout << 'L' << string(dy + 1, 'U') << string(dx + 1, 'R') << 'D';
    cout << 'R' << string(dy + 1, 'D') << string(dx + 1, 'L') << 'U';

    cout << "\n";

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
const int vx[4]={-1,0,0,1},vy[4]={0,-1,1,0};
int H,W,K;
char A[810][810];
struct Point{int x,y,d;}Q[810*810];
int min(int a,int b){return a<b?a:b;} 
int main(){
	scanf("%d%d%d",&H,&W,&K);
	for(int i=0;i<H;i++){
		scanf("%s",A[i]);
		for(int j=0;j<W;j++)if(A[i][j]=='S')*Q=(Point){i,j,0};
	}
	Point*h=Q,*t=Q+1;
	int ans=1<<30;
	for(;h<t;h++){
		ans=min(ans,1+(min(min(h->x,H-h->x-1),min(h->y,W-h->y-1))+K-1)/K);
		if(ans<2)break;
		if(h->d<K)for(int d=0,dx,dy;d<4;d++)if(A[dx=h->x+vx[d]][dy=h->y+vy[d]]=='.'){
			*t++=(Point){dx,dy,h->d+1};
			A[dx][dy]=1; 
		}
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 2944
h, w, n = [int(i) for i in input().split()]
sr, sc = [int(i) for i in input().split()]
s = input()
t = input()


dpx = [None for _ in range(n*2+1)]
dpy = [None for _ in range(n*2+1)]

dpx[0] = (1, w+1)
dpy[0] = (1, h+1)

# search safety region from tail
for i in range(1,n*2+1):
    is_t = i % 2 == 1
    strategy = t[-1-(i-1)//2] if is_t else s[-1-(i-1)//2]

    # T's turn: want to expand region
    if is_t:
        if strategy == 'L':
            dpx[i] = (dpx[i-1][0], min(dpx[i-1][1] + 1, w+1))
            dpy[i] = dpy[i-1]
        if strategy == 'R':
            dpx[i] = (max(1, dpx[i-1][0] - 1), dpx[i-1][1])
            dpy[i] = dpy[i-1]
        if strategy == 'U':
            dpy[i] = (dpy[i-1][0], min(dpy[i-1][1] + 1, h+1))
            dpx[i] = dpx[i-1]
        if strategy == 'D':
            dpy[i] = (max(1, dpy[i-1][0] - 1), dpy[i-1][1])
            dpx[i] = dpx[i-1]
    # S's turn: want to contract region
    else:
        if strategy == 'L':
            dpx[i] = (dpx[i-1][0] + 1, dpx[i-1][1])
            dpy[i] = dpy[i-1]
        if strategy == 'R':
            dpx[i] = (dpx[i-1][0], dpx[i-1][1] - 1)
            dpy[i] = dpy[i-1]
        if strategy == 'U':
            dpy[i] = (dpy[i-1][0] + 1, dpy[i-1][1])
            dpx[i] = dpx[i-1]
        if strategy == 'D':
            dpy[i] = (dpy[i-1][0], dpy[i-1][1] - 1)
            dpx[i] = dpx[i-1]
    # safety region has been cotrancted to 0, then break
    if len(range(*dpx[i])) == 0 or len(range(*dpy[i])) == 0:
        break

print('NO' if dpx[-1] is None else 'YES' if sr in range(*dpy[-1]) and sc in range(*dpx[-1]) else 'NO')


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

using namespace std;

template<class T>
class Dice {
  private:
    void roll(int a, int b, int c, int d){
	swap(x[a], x[b]);
	swap(x[b], x[d]);
	swap(x[c], x[d]);
    }
  public:
    T x[6];
    void roll_N(){ roll(0, 1, 4, 5); }
    void roll_E(){ roll(0, 3, 2, 5); }
    void roll_S(){ roll(0, 4, 1, 5); }
    void roll_W(){ roll(0, 2, 3, 5); }
    void rotation(){ roll(1, 2, 3, 4); }
    
    void roll(int top, int front)
    {
	for (int i = 0; i < 2; i++) {
	    for (int j = 0; j < 4; j++) {
		roll_N();
		if (top == x[0]) {
                    goto next;
                }
	    }
	    roll_E();
	}
        next:
	for (int i = 0; i < 4; i++) {
	    rotation();
	    if (front == x[1]) {
                break;
            }
	}
    }
    
    bool operator == (Dice &d)
    {
	for (int i = 0; i < 4; i++) {
	    for (int j = 0; j < 4; j++) {
		d.roll_N();
		bool equals = true;
		for (int k = 0; k < 6; k++) {
		    if (x[k] != d.x[k]) { 
			equals = false;
			break;
		    }
		}
		if (equals) {
                    return true;
                }
	    }
	    for (int j = 0; j < 4; j++) {
		d.roll_E();
		bool equals = true;
		for (int k = 0; k < 6; k++) {
		    if (x[k] != d.x[k]) {
			equals = false;
			break;
		    }
		}
		if (equals) {
                    return true;
                }
	    }
	    d.rotation();
	}
	return false;
    }
    
    bool operator < (const Dice &d) const
    {
	for (int i = 0; i < 6; i++) {
	    if (x[i] != d.x[i]) {
                return x[i] < d.x[i];
            }
	}
	return false;
    }
};

int main()
{
    int N;
    while (cin >> N, N) {
        string s;
        Dice<int> d;
        for (int i = 0; i < 6; i++) {
            d.x[i] = i + 1;
        }
        int res = 1;
        for (int i = 0; i < N; i++) {
            cin >> s;
            switch (s[0]) {
                case 'N': {
                    d.roll_N();
                    break;
                }
                case 'E': {
                    d.roll_E();
                    break;
                }
                case 'S': {
                    d.roll_S();
                    break;
                }
                case 'W': {
                    d.roll_W();
                    break;
                }
                case 'L': {
                    for (int i = 0; i < 3; i++) {
                        d.rotation();
                    }
                    break;
                }
                case 'R': {
                    d.rotation();
                    break;
                }
            }
            res += d.x[0];
        }
        cout << res << endl;
    }        
    return 0;
}

Measured memory_bytes: 3216