akhauriyash/Code-Regression huggingface dataset:
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N; cin >> N;
    vi A(N); REP(i, N) cin >> A[i];

    sort(A.begin(), A.end(), greater<int>());

    pii ans;
    ans.first = A[0];
    int mid = A[0] % 2 == 1 ? (A[0] + 1) / 2 : A[0] / 2;
    int r = INF;
    REP(i,N) {
        if (abs(A[i] - mid) <= abs(r - mid)) {
            r = A[i];
        }
    }
    ans.second = r;

    cout << ans.first << " " << ans.second << endl;

    return 0;
}

Measured memory_bytes: 640
s = input()
ans = 100
for i in range(26):
    cur = 0
    c = chr(ord('a') + i)
    t = s
    if(not c in t): continue
    t2 = ""
    while(t.count(c) != len(t)):
        for j in range(len(t) - 1):
            if(t[j] == c or t[j + 1] == c):
                t2 += c
            else:
                t2 += 'A'
        cur += 1
        t = t2
        t2 = ""
    ans = min(cur, ans)
print(ans)


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

#define ld long double

using namespace std;

int n, k;
long double p, c;

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

	c = (ld) 1.0 / (ld) n;

	for(int i = 1; i <= n; i++){
		ld tmp = c;
		int x = i;

		while(x < k){
			x *= 2, tmp *= (ld) 0.5;
		}
		p += tmp;
	}

	printf("%.12Lf\n", p);
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long,long long>> vals[200005],segment;
long long n,m,t,sum;

long long getmin(int a , int b , int curr , int l , int r){
	if(b < l || a > r){
		return 1000000000;
	}
	if(a <= l && b >= r){
		return segment[curr].first+segment[curr].second;
	}
	segment[2*curr].second += segment[curr].second;
	segment[2*curr+1].second += segment[curr].second;
	segment[curr].first += segment[curr].second;
	segment[curr].second = 0;
	int mid = (l+r)/2;
	long long ret = min(getmin(a,b,2*curr,l,mid),getmin(a,b,2*curr+1,mid+1,r));
	segment[curr].first = min(segment[2*curr].first+segment[2*curr].second,segment[2*curr+1].first+segment[2*curr+1].second);
	return ret;
}

void update(int a , int b , long long val , int curr , int l , int r){
	if(b < l || a > r){
		return ;
	}
	if(a <= l && b >= r){
		segment[curr].second += val;
		return ;
	}
	segment[2*curr].second += segment[curr].second;
	segment[2*curr+1].second += segment[curr].second;
	segment[curr].first += segment[curr].second;
	segment[curr].second = 0;
	int mid = (l+r)/2;
	update(a,b,val,2*curr,l,mid),update(a,b,val,2*curr+1,mid+1,r);
	segment[curr].first = min(segment[2*curr].first+segment[2*curr].second,segment[2*curr+1].first+segment[2*curr+1].second);
}

int main(){
	cin >> n >> m;
	t = pow(2,ceil(log2(n+2)));
	segment.resize(2*t,{0,0});
	for(int i = 0 ; i < m ; i += 1){
		int l,r,v;
		cin >> l >> r >> v;
		vals[l].push_back({r,v});
		sum += v;
	}
	for(int i = n ; i >= 0 ; i -= 1){
		update(i+1,i+1,getmin(i+2,t,1,1,t),1,1,t);
		for(pair<int,int> j : vals[i]){
			update(j.first+2,t,j.second,1,1,t);
		}
	}
	cout << sum-getmin(1,1,1,1,t) << endl;
}

Measured memory_bytes: 19328
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//約数列挙(√N)
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}
//素因数分解(√N)
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
//素数テーブル(NloglogN)
vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
//二項係数(K)
template< typename T >
T binomial(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}
//二項係数テーブル(N^2)
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}

ll haiata(ll n){
  if(n==-1)return 0;
  if(n%4==0)return n;
  if(n%4==2)return n+1;
  if(n%4==1)return 1;
  return 0;
}
int main(){
  ll a,b;
  cin >> a >> b;
  bitset<63> c=haiata(a-1);
  bitset<63> d=haiata(b);
  bitset<63> e=c^d;
  cout << e.to_ullong() << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 9223372036854775807
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=1e5 ;
int main()
{
    fast ;
    ll a ; cin>>a ;
    ll ans=a+a*a+a*a*a ;
    cout<<ans ;



}




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

typedef long long ll;

ll C[51][51]; // C[n][k] -> nCk

void comb_table(int N) {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) {
				C[i][j]=1;
			}
			else {
				C[i][j] = C[i-1][j-1]+C[i-1][j];
			}
		}
	}
}

int main() {
	int N, A, B;
	cin >> N >> A >> B;
	vector<ll> v(N);
	for(int i=0; i<N; i++) cin >> v[i];

	comb_table(N);
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());

	double Mave=0;
	for(int i=0; i<A; i++) Mave += v[i];
	Mave /= A;

	int n=0, p=0;
	for (int i = 0; i < N; i++) {
		if (v[i] == v[A - 1]) {
			n++;
			if(i<A) p++;
		}
	}

	ll cnt=0;
	if (p == A) {
		for (p = A; p <= B; p++) {
			cnt += C[n][p];
		}
	}
	else {
		cnt += C[n][p];
	}

	cout.precision(20);
	cout << fixed << Mave << endl;
	cout << cnt << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

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

	int N;
	cin >> N;

	vector<int> a( N );
	for( auto& v: a ) { cin >> v; }

	int ans = 0;
	int x = 1;

	for( int i = 0; i < N; ++i ) {
		if( a[i] != x ) {
			ans += 1;
		}
		else {
			x += 1;
		}
	}

	cout << (ans == N ? -1 : ans) << endl;

	return 0;
}


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

int main() {
    ll N, M; cin >> N >> M;
    N -= 2, M -= 2;
    if (N < 0) N = 1;
    if (M < 0) M = 1;
    cout << N * M << endl;
}


Measured memory_bytes: 3568
n=int(input())
w=list(map(int,input().split()))
ans=[]
s1=0
s2=0
 
for i in range(n):
    for j in range(0,i):
        s1 += w[j]
    for k in range(i,n):
        s2 += w[k]
    ans.append(abs(s1 - s2))
    s1=0
    s2=0
    
print(min(ans))

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

int main(){
  int n;
  cin>>n;
  ll vec[n];
  for(int i=0;i<n;i++){
    cin>>vec[i];
  }
  sort(vec,vec+n);
  reverse(vec,vec+n);
  ll ans=0;
  ans+=vec[0];
  int x=2;
  for(int i=1;i<n-1;i++){
    if(x==n){
      break;
    }
    if(x>=n){
      ans-=vec[i-1];
      break;
    }
    ans+=vec[i]*2;
    x+=2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 5176
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def is_lunlun(n):
    s = str(n)
    for i in range(len(s)-1):
        if abs(int(s[i])-int(s[i+1])) > 1:
            return False
    return True

def slv(k):
    n = 1
    for _ in range(k-1):
        j = 0
        while True:
            l = 10**j
            t = 0
            t += n + l
            t -= (n+l) % l
            m = (t % (10**(j+1))) // l
            # print(t, j, m)
            for i in range(j-1, -1, -1):
                t += (10 ** i) * max(0, m-(j-i))
            # print(t, j)
            if is_lunlun(t):
                n = t
                break
            else:
                j+=1
            # if j > 5:
            #     break
        # print(n)
    return n



def main():
    K = read_int()
    print(slv(K))



if __name__ == '__main__':
    main()


Measured memory_bytes: 5836
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new MyInputStream(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(MyInputStream cin)
        {
            var N = cin.ReadInt();
            var A = cin.ReadInt();
            var B = cin.ReadInt();
            WriteLine(Enumerable.Range(1, N).Where(x => { int s = Sum(x); return A <= s && s <= B; }).Sum());
        }  

        public int Sum(int x)
        {
            return x.ToString().ToCharArray().Select(c => (int)(c - '0')).Sum();
        }
    }

    public class MyInputStream
    {
        private readonly System.IO.TextReader _stream;
        private char separator = ' ';
        private Queue<string> inputStream;
        public MyInputStream(System.IO.TextReader s, char separator = ' ')
        {
            this.separator = separator;
            this._stream = s;
            inputStream = new Queue<string>();
        }
        public string Read()
        {
            if (inputStream.Count != 0) return inputStream.Dequeue();
            string[] tmp = _stream.ReadLine().Split(separator);
            for (int i = 0; i < tmp.Length; ++i)
                inputStream.Enqueue(tmp[i]);
            return inputStream.Dequeue();
        }
        public string ReadLine() { return _stream.ReadLine(); }
        public int ReadInt() { return int.Parse(Read()); }
        public long ReadLong() { return long.Parse(Read()); }
        public double ReadDouble() { return double.Parse(Read()); }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read(); return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt(); return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong(); return ret;}
    }
}

Measured memory_bytes: 13524
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/

const int MAXN = 2000;

int n;
string stmp[MAXN];
int a[MAXN][MAXN];
ll go[MAXN][MAXN];
int gd[MAXN][MAXN];
int gr[MAXN][MAXN];

int main() {
#ifdef FASTIO
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> stmp[i];
		for (int j = 0; j < n; ++j) {
			if (stmp[i][j] == '#')
				a[i][j] = 0;
			else
				a[i][j] = stmp[i][j] - '0';
		}
	}
	ll ans = 0;
	for (int i = n - 1; i >= 0; --i)
		for (int j = n - 1; j >= 0; --j) {
			if (a[i][j] == 0)
				continue;
			if (i + 1 < n && j + 1 < n && a[i + 1][j] != 0 && a[i][j + 1] != 0) {
				go[i][j] += go[i + 1][j];
				go[i][j] += go[i][j + 1];
				//TODO: optimize
				for (int k = i + 1; k < n && gd[j + 1][k] != -1; ++k) {
					if (gr[j][gd[j + 1][k]] == k)
						go[i][j] -= go[k][gd[j + 1][k]];
				}
				gd[j][i] = j;
				for (int x = j + 1; x < n && gr[j + 1][x] != -1; ++x)
					gr[j][x] = gr[j + 1][x];
				int st = i + 1;
				while (st < n && gd[j][st] != -1)
					++st;
				while (st < n && gd[j + 1][st] != -1)
					gd[j][st] = gd[j + 1][st], ++st;
				gr[j][j] = i;
			}
			else if (i + 1 < n && a[i + 1][j] != 0) {
				go[i][j] += go[i + 1][j];
				gd[j][i] = j;
				gr[j][j] = i;
			}
			else if (j + 1 < n && a[i][j + 1] != 0) {
				go[i][j] += go[i][j + 1];
				memcpy(gr[j] + j + 1, gr[j + 1] + j + 1, sizeof(gr[0][0]) * (n - j - 1));
				memcpy(gd[j] + i + 1, gd[j + 1] + i + 1, sizeof(gr[0][0]) * (n - i - 1));
				gd[j][i] = j;
				gr[j][j] = i;
			}
			else {
				memset(gr[j] + j + 1, -1, sizeof(gr[0][0]) * (n - j - 1));
				memset(gd[j] + i + 1, -1, sizeof(gr[0][0]) * (n - i - 1));
				gd[j][i] = j;
				gr[j][j] = i;
			}
			ans += go[i][j] * a[i][j];
			go[i][j] += a[i][j];
		}
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 26496
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def check(x,y):
        return (x == 0)|(x == w)|(y == 0)|(y == h)

    w,h,n = LI()
    px0 = []
    pxw = []
    py0 = []
    pyh = []
    for i in range(1,n+1):
        x,y,s,t = LI()
        if check(x,y)&check(s,t):
            if x == 0:
                px0.append((y,i))
            elif x == w:
                pxw.append((-y,i))
            elif y == 0:
                py0.append((-x,i))
            else:
                pyh.append((x,i))
            if s == 0:
                px0.append((t,i))
            elif s == w:
                pxw.append((-t,i))
            elif t == 0:
                py0.append((-s,i))
            else:
                pyh.append((s,i))
    px0.sort()
    pxw.sort()
    py0.sort()
    pyh.sort()
    p = px0+pyh+pxw+py0
    q = deque()
    for x, i in p:
        if q:
            qi = q.pop()
            if qi != i:
                q.append(qi)
                q.append(i)
        else:
            q.append(i)
    if q:
        print("NO")
    else:
        print("YES")
    return

#Solve
if __name__ == "__main__":
    solve()


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

int main() {
  string s;
  cin >> s;
  if(s.size()%2 == 1){
    cout << "No" << endl;
    return 0;
  }
  rep(i,s.size()){
    if(i%2 == 0 && s[i] != 'h'){
      cout << "No" << endl;
      return 0;
    }
    if(i%2 == 1 && s[i] != 'i'){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+10;
int a[N];
map <int,int>mp;
string s;
int main()
{
    long long a;
    cin>>a>>s;
    long long b;

    b=(s[0]-'0')*100+(s[2]-'0')*10+(s[3]-'0');

    a*=b;
    a/=100;
    cout<<a<<endl;

}


Measured memory_bytes: 3644
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)

# BIT 木


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define ALL(c) (c).begin(), (c).end()

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

const ll INF = TEN(18);

int main() {
    int n;
    cin >> n;
    V<int> A(n);
    rep(i, n) cin >> A[i];
    using pll = pair<ll, ll>;
    V<pll> vl(n, mp(-INF, INF)), vr(n, mp(-INF, INF));

    auto ch = [&](pll& a, pll b) {
        if (abs(a.se - a.fi) > abs(b.fi - b.se)) {
            a = b;
        }
        return;
    };

    rep(t, 2) {
        ll s = 0;
        V<ll> acm;
        V<pll>& vec = (t == 0 ? vl : vr);

        rep(i, n) {
            s += A[i];
            acm.pb(s);
            if (i) {
                int p = lower_bound(ALL(acm), s / 2) - acm.begin();
                if (p == i) --p;
                auto x = mp(acm[p], s - acm[p]);
                ch(vec[i], x);
                --p;
                if (p >= 0) {
                    auto x = mp(acm[p], s - acm[p]);
                    ch(vec[i], x);
                }
            }
        }
        reverse(ALL(A));
    }

    ll ans = INF;
    for (int i = 1; i < n - 2; ++i) {
        auto p = vl[i], q = vr[n - i - 2];
        V<ll> v = {p.fi, p.se, q.fi, q.se};
        sort(ALL(v));
        chmin(ans, v.back() - v[0]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14004
#include <bits/stdc++.h>
#define For(i, begin, end) for(int i=begin;i<end;i++)
#define Rep(i, n) For(i,0,n)
#define Sort(v) sort(v.begin(),v.end())
using namespace std;

int main(){
  string X,Y;cin>>X>>Y;
  if(X>Y)cout<<">";
  else if(X<Y)cout<<"<";
  else cout<<"=";

  return 0;
}

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

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

        int ans=a;
        int re=1;
        while(ans<b){
            ans+=a-1;
            re++;
        }
        if(b==1) re = 0;
        cout << re << endl;
        return 0;
    }


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

int main(){
    ll n,k; cin >> n >> k;
    vector<ll> p(n);
    rep(i,n) cin >> p.at(i);
    vector<ll> rui(n+1);
    rui.at(0) = 0;
    for(int i=1;i<n+1;i++){
        rui.at(i) = rui.at(i-1) + p.at(i-1);
    }
    ll maximum = 0;
    ll start;
    for(int i=k;i<n+1;i++){
        if(maximum <rui.at(i)-rui.at(i-k)){
            maximum = rui.at(i) - rui.at(i-k);
            start = i-k;
        }
    }
    double ans = 0.0;
    for(int i=start;i<(start+k);i++){
        ans += (p.at(i) + 1)/2.0;
    }
    cout << setprecision(10) << ans << endl;
}

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

int main() {
	int n;
	cin >> n;
	set<string> ss;
	char l = '\0';
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if(l != '\0' && s[0] != l) {
			cout << "No" << endl;
			return 0;
		} else {
			l = s[s.length() - 1];
		}
		if(ss.find(s) != ss.end()) {
			cout << "No" << endl;
			return 0;
		} else {
			ss.insert(s);
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
work_list = [[] for m in range(M + 1)]
for n in range(N):
    a, b = map(int, input().split())
    if a <= M:
        work_list[a].append(-b)

Q = [0 for m in range(M)]
ans = 0
for m in range(1, M+1):
    for work in work_list[m]:
        heapq.heappush(Q, work)
    ans += heapq.heappop(Q)

print(-ans)


Measured memory_bytes: 18580
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vpii vector< pair<int,int> >
#define mii map<int,int>
#define MOD 1000000007
#define fr(i,k,n) for(int i=k;i<n;i++)
#define fl(i,k,n) for(int i=k;i>=n;i--)
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int h1,m1,h2,m2,k;
cin>>h1>>m1>>h2>>m2>>k;
int min=0;
if(m2>=m1)
{
min+=(h2-h1)*60;
min+=(m2-m1);
}
else
{
	min+=(h2-h1-1)*60;
	min+=60-abs(m2-m1);
	
}
cout<<min-k;
return 0;
}
// Problem : A - Study Scheduling
// Contest : AtCoder - NOMURA Programming Competition 2020
// URL : https://atcoder.jp/contests/nomura2020/tasks/nomura2020_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)



Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _cin      ios_base::sync_with_stdio(0);  cin.tie(0);
#define READ      freopen("input.txt", "r", stdin);
#define WRITE     freopen("output.txt", "w", stdout);
#define endl "\n"
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define repd(i,a,b) for(ll i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define vvll vector<vector<ll> >
#define vll vector<ll>
#define mint map<ll,ll>
#define sz(x) (ll)x.size()
#define sll set<ll>
#define pll pair<ll,ll>
#define F first
#define S second
const ll MAX = 1000004;

int main() {

	_cin
	// READ
	// WRITE
	ll n, W;
	cin >> n >> W;
	ll w[n], v[n];
	rep(i, 0, n) {
		cin >> w[i] >> v[i];
	}
	ll dp[n + 1][W + 1];
	//dp[i][j] - max value for weight j using i element
	rep(i, 0, n + 1) {
		rep(j, 0, W + 1) {
			if (i == 0 || j == 0) dp[i][j] = 0;
			else if (w[i - 1] <= j) {
              dp[i][j]=max(v[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
			} else dp[i][j] = dp[i - 1][j];

		}
	}
	cout<<dp[n][W]<<endl;

}

Measured memory_bytes: 82372
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

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

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    map<string,int> bmp;
    REP(i,N){
        string tmp; cin >> tmp;
        bmp[tmp]++;
    }
    int M; cin >> M;
    map<string,int> rmp;
    REP(i,M){
        string tmp; cin >> tmp;
        rmp[tmp]++;
    }
    int ans = 0;
    for(auto p : bmp){
        int tmp;
        if(rmp.find(p.first) == rmp.end()){
            tmp = p.second;
        }
        else{
            tmp = p.second - rmp[p.first];
        }
        if(ans < tmp) ans = tmp;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl

using namespace std;
using lli = long long int;

lli mod197 = 1000000007LL;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

lli h[100000] = {};

int main(void) {

	lli N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> h[i];

	sort(h, h + N);

	lli ans = 1000000000;

	for (int i = 0; i <= N - K; i++) {
		CHMIN(ans,h[i + K - 1] - h[i]);
	}

	COUT(ans);

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main() {
    ll h,w; cin >> h >> w;
    if(h == 1 || w == 1)print(1);
    else if((h * w) % 2 == 0)print((h * w) / 2);
    else if((h * w) % 2 == 1)print((h * w) / 2 + 1);
}

Measured memory_bytes: 256
import string
import re
import datetime
import calendar
import collections
import heapq
import bisect
import array

import numpy as np

a, b = map(int,input().split())

ans = np.empty((100, 100), dtype=int)

x, y = ans.shape

for i in range(x):
    for j in range(y):
        if j == 0:
            ans[i,j] = 1
        elif j == y-1:
            ans[i,j] = 0
        elif (i % 4) == 0 or (i % 4) == 1:
            ans[i,j] = 1
        else:
            ans[i,j] = 0
def cut_b():
    itr = 1
    for i in range(2, x, 4):
        for j in range(2, y//2, 2):
            yield itr
            ans[i,j] = ans[i+1,j] = 1
            itr+=1

def cut_w():
    itr = 1
    for i in range(0, x, 4):
        for j in range(-3, -y//2, -2):
            yield itr
            ans[i,j] = ans[i+1,j] = 0
            itr+=1

for i in cut_b():
    if i == a:
        break
for i in cut_w():
    if i == b:
        break
print(100, 100)
for i in range(x):
    for j in range(y):
        if ans[i,j] == 0:
            print('.', end="")
        else:
            print('#', end="")
    print()


Measured memory_bytes: 14444
n = gets.to_i

xyh = []
n.times {xyh << gets.split.map(&:to_i)}

ans = catch do |tag|
    101.times do |i|
        101.times do |j|
            l = 0
            r = 10 ** 12

            xyh.each do |x, y, h|
                if h == 0
                    break if (ar = (x - i).abs + (y - j).abs) < l
                    r = ar if r > ar
                else
                    break if !(ah = h + (x - i).abs + (y - j).abs).between?(l, r) 
                    l = r = ah
                end
            end and throw(tag, [i, j, l])
        end
    end
end

puts ans.join(" ")

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

int main() {
	int64_t A, B, C, K;
	cin >> A >> B >> C >> K;
	if (A > K) {
		std::cout << K << '\n';
	} else if (A + B >= K) {
		std::cout << A << '\n';
	} else {
		std::cout << A - (K-A-B) << '\n';
	}
}


Measured memory_bytes: 3604
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second

struct perm {
private:
	int sz;
	vector<ll> p, invp;
public:
	perm(int n) {
		sz = n + 1;
		p.resize(sz), invp.resize(sz);
		p[0] = 1;
		rep1(i, sz - 1) {
			p[i] = p[i - 1] * i%mod;
		}
		invp[sz - 1] = 1;
		ll cop = mod - 2, x = p[sz - 1];
		while (cop) {
			if (cop % 2)invp[sz - 1] = invp[sz - 1] * x%mod;
			cop >>= 1; x = x * x % mod;
		}
		per(i, sz - 1) {
			invp[i] = invp[i + 1] * (i + 1) % mod;
		}
	}
	ll comb(ll x, ll y) {
		if (x < y || y < 0)return 0;
		ll ret = p[x];
		(ret *= invp[y]) %= mod;
		(ret *= invp[x - y]) %= mod;
		return ret;
	}
	ll combP(ll x, ll y) {
		if (x < y || y < 0)return 0;
		return p[x] * invp[x - y] % mod;
	}
};
void solve() {
	perm p(1 << 18);
	int n, m, k; cin >> n >> m >> k;
	ll ans = 0;
	vector<ll> s({ 1 });
	vector<ll> t({ 1 });
	rep1(i, k) {
		ll sum1 = p.comb(n + 2 * i, i) - p.comb(n + 2 * i, i - 1);
		if (sum1 < 0)sum1 += mod;
		ll sum2 = p.comb(m + 2 * i, i) - p.comb(m + 2 * i, i-1);
		if (sum2 < 0)sum2 += mod;
		s.push_back(sum1);
		t.push_back(sum2);
	}
	rep(i, k + 1) {
		ll csum = s[i] * t[k - i] % mod*p.comb(n + m + 2*k, n + 2*i) % mod;
		ans = (ans + csum) % mod;
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	//stop
	return 0;
}


Measured memory_bytes: 7328
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define Inf 1000000000000000000
#define nmax_def 110000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

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

int main() {
	ll N, X, D;
	cin >> N >> X >> D;
	if (D < 0) {
		X *= -1;
		D *= -1;
	}
	ll ans = 0;
	if (D == 0) {
		if (X == 0)
			ans = 1;
		else
			ans = N + 1;
	}
	else {
		ll iprev_dist = D / gcd(abs(X), D);
		vector<pll> sumLR(N + 1); // 取る個数
		rep(i, N + 1) {
			sumLR[i].first = X * i + D * i * (i - 1) / 2;
			sumLR[i].second = sumLR[i].first + D * i * (N - i);
			if (sumLR[i].first > sumLR[i].second)
				swap(sumLR[i].first, sumLR[i].second);
			ans += (sumLR[i].second - sumLR[i].first) / D + 1;

			int iprev = i - iprev_dist;
			if (iprev >= 0) {
				pll sumLR_excluded = sumLR[iprev];
				sumLR_excluded.first = max(sumLR_excluded.first, sumLR[i].first);
				sumLR_excluded.second = min(sumLR_excluded.second, sumLR[i].second);
				if (sumLR_excluded.first <= sumLR_excluded.second)
					ans -= (sumLR_excluded.second - sumLR_excluded.first) / D + 1;
			}
		}
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 3328
def main():
    S = input()
    w1 = 'dream'[::-1]
    w2 = 'dreamer'[::-1]
    w3 = 'erase'[::-1]
    w4 = 'eraser'[::-1]
    S = S[::-1]
    words = [w1, w2, w3, w4]

    i = 0
    while i != len(S):
        for w in words:
            if S[i:].startswith(w):
                i += len(w)
                break
        else:
            print("NO")
            exit()

    print("YES")



if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='?'){
            if(i!=0&&i!=s.size()-1&&s[i-1]=='D'&&s[i+1]=='D')s[i]='P';
            else s[i]='D';
        }
    }
    cout<<s<<endl;
}


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

int main(){
  int N, y; cin >> N >> y;
  vector<int> x(N);
  for(int i = 0; i < N; i++){
    cin >> x[i];
  }
  x.push_back(y);
  sort(x.begin(), x.end());
  int gcd_ans = x[1] - x[0];
  for(int i = 1; i < N; i++){
    gcd_ans = __gcd(gcd_ans, x[i + 1] - x[i]);
  }
  cout << gcd_ans << endl;
}

Measured memory_bytes: 1024
/*
16:50 - 
 */

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cassert>
#include<climits>
#include<iomanip>
#include<string>
#include<cstring>
#include<cstdlib>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define MAX 500
#define pow2(a) ((a)*(a))

using namespace std;


// Library - maxflow - begin 17:01
struct edge{
  int to,cap,rev;
  edge(int to=IINF,int cap=IINF,int rev=IINF):to(to),cap(cap),rev(rev){}
};

vector<vector<edge>> G;
bool used[MAX];

void add_edge(int from,int to,int cap){
  G[from].push_back(edge(to,cap,G[to].size()));
  G[to].push_back(edge(from,0,G[from].size()-1));
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v] = true;
  for(int i=0;i<G[v].size();i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d>0){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;
      }
    }
  }
  return 0;
}

int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,IINF);
    if(f == 0)return flow;
    flow += f;
  }
}

// Library - maxflow - end 17:07

struct Point{
  double x,y,v;
  Point(double x=IINF,double y=IINF,double v=IINF):x(x),y(y),v(v){}
};

struct Data{
  double cost;
  int from,to;
  Data(double cost=IINF,int from=IINF,int to=IINF):cost(cost),from(from),to(to){}
  bool operator < (const Data& a)const{ return cost < a.cost; }
};

int N,M,source,sink;
Point troops[MAX];
Point base[MAX];
bool check[MAX];
vector<Data> info;


inline double getDist(Point a,Point b){ return sqrt(pow2(a.x-b.x)+pow2(b.y-a.y)); }

int main(){
  while(cin >> N >> M, N|M){
    info.clear();
    rep(i,N)cin >> troops[i].x >> troops[i].y >> troops[i].v;
    rep(i,M){
      cin >> base[i].x >> base[i].y; check[i] = false;
      rep(j,N)info.push_back(Data(getDist(base[i],troops[j])/troops[j].v,j,N+i));
    }
    sort(info.begin(),info.end());
    source = N+M; sink = source+1;
    G.resize(sink+1);
    rep(i,sink+1)G[i].clear();
    rep(i,N)add_edge(source,i,1);
    rep(i,M)add_edge(N+i,sink,1);
    vector<vector<edge>> tmp = G;
    double ans = IINF;
    double L = 0, R = (1<<27),H;
    rep(_,100){
      H = (L+R)*0.5;
      G = tmp;
      rep(i,info.size()){
	if(equals(info[i].cost,H) || info[i].cost < H)add_edge(info[i].from,info[i].to,1);
	else break;
      }
      if(max_flow(source,sink) == M){
	ans = min(ans,H);
	R = H;
      } else L = H;
    }

    cout << setiosflags(ios::fixed) << setprecision(8) << ans << endl;

  }
  return 0;
}

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



int main() {
    int N; cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    if(A[0] != 0){
        cout << -1 << endl;
        return 0;
    }
    ll ans = 0;
    for(int i = N-1; i > 0; i--){
        int tmp=A[i];
        ans += tmp;
        if(A[i]-A[i-1] > 1){
            cout << -1 << endl;
            return 0;
        }
        while(A[i]-A[i-1] == 1){
            i--;
        } 
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
function f(n, y)
	a = [-1, -1, -1]
	p = y%10000
	q = convert(Int, (y-p)/10000)
	for i in 0:q
		if i <= n
			m = y - i*10000
			r = m%5000
			s = convert(Int, (m-r)/5000)
			for j in 0:s
				if i + j <= n
					o = m - j*5000
					if o%1000 ==0 && i + j + o/1000 == n
						a[1] = i
						a[2] = j
						a[3] = convert(Int, o/1000)
					end
				end
			end
		end
	end
	return(a)
end


function main()
	n = parse.(split(readline()))
	ans = f(n[1], n[2])
	print(ans[1], " ", ans[2], " ", ans[3])
end


main()


Measured memory_bytes: 122956
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
print(N**3)


Measured memory_bytes: 23120
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INF = 1e18;

void dfs(int n, vector<vector<int>>& to, vector<bool>& judge) {
  if(!judge[n]) {
    judge[n] = true;
    rep(i, to[n].size())
      dfs(to[n][i], to, judge);
  }
}

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> a(M), b(M), c(M);
  rep(i, M) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
  }
  vector<vector<int>> to(N), co(N), rto(N);
  rep(i, M) {
    to[a[i]].push_back(b[i]);
    rto[b[i]].push_back(a[i]);
    co[a[i]].push_back(-c[i]);
  }
  vector<bool> stot(N), ttos(N);
  dfs(0, to, stot);
  dfs(N-1, rto, ttos);
  vector<bool> isTrue(N);
  rep(i, N) {
    if(stot[i] && ttos[i])
      isTrue[i] = true;
  }
  vector<ll> node(N, INF);
  node[0] = 0;
  rep(i, N-1) {
    rep(j, N) rep(k, to[j].size()) {
      if(isTrue[to[j][k]])
        chmin(node[to[j][k]], node[j]+co[j][k]);
    }
  }
  vector<ll> check = node;
  rep(i, N) rep(j, to[i].size()) {
    if(isTrue[to[i][j]])
      chmin(check[to[i][j]], check[i]+co[i][j]);
  }
  rep(i, N) {
    if(node[i] != check[i]) {
      cout << "inf" << endl;
      return 0;
    }
  }
  cout << -node[N-1] << endl;
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 998244353;
ll po[200005];
int x[200005], y[200005];
vector<int> v[200005];
vector<int> vx, vy;

struct ft{
    int ft[200005];
    void update(int i, int v){
        for(;i<=200000;i+=(i&-i)) ft[i] += v;
    }
    int query(int i){
        int res = 0;
        for(;i>0;i-=(i&-i)) res += ft[i];
        return res;
    }
}f[4];

int main(){
    po[0] = 1;
    for(int i=1;i<=200000;i++) po[i] = po[i-1]*2%mod;
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d%d", &x[i], &y[i]);
        vx.push_back(x[i]);
        vy.push_back(y[i]);
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    for(int i=1;i<=n;i++){
        x[i] = lower_bound(vx.begin(), vx.end(), x[i]) - vx.begin() + 1;
        y[i] = lower_bound(vy.begin(), vy.end(), y[i]) - vy.begin() + 1;
        f[0].update(x[i], 1);
        f[1].update(y[i], 1);
        f[3].update(y[i], 1);
        v[x[i]].push_back(y[i]);
    }

    ll ans = 0;
    for(int x=1;x<=n;x++){
        for(int j=0;j<v[x].size();j++){
            int y = v[x][j];
            f[3].update(y, -1);
        }

        for(int j=0;j<v[x].size();j++){
            int y = v[x][j];
            ans = (ans + (po[n]-1) + mod)%mod;
            ans = (ans - (po[f[0].query(x-1)]-1) + mod)%mod;
            ans = (ans - (po[n - f[0].query(x)]-1) + mod)%mod;

            ans = (ans - (po[f[1].query(y-1)]-1) + mod)%mod;
            ans = (ans - (po[n - f[1].query(y)]-1) + mod)%mod;

            ans = (ans + (po[f[2].query(y-1)] - 1))%mod;
            ans = (ans + (po[f[2].query(200000) - f[2].query(y)] - 1))%mod;

            ans = (ans + (po[f[3].query(y-1)] - 1) + mod)%mod;
            ans = (ans + (po[f[3].query(200000) - f[3].query(y)] - 1) + mod)%mod;
        }

        for(int j=0;j<v[x].size();j++){
            int y = v[x][j];
            f[2].update(y, 1);
        }
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 20588
from collections import Counter


def solve(s):
    freq = sorted(Counter(s).values())
    if sum(freq) == 1:
        return True
    if sum(freq) == 2:
        return freq[-1] == 1
    return len(freq) == 3 and freq[2] - freq[0] <= 1


print('YES' if solve(input()) else 'NO')


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin>>N;
  vector<string> S(N);
  for(int i=0;i<N;i++){
    cin>>S.at(i);
  }
  cin>>M;
  vector<string> T(M);
  for(int i=0;i<M;i++){
    cin>>T.at(i);
  }
  int ans=0;
  for(int i=0;i<N;i++){
    int pt=0;
    for(int j=i;j<N;j++){
      if(S.at(i)==S.at(j)){
        pt++;
      }
         }
         for(int j=0;j<M;j++){
           if(S.at(i)==T.at(j)){
             pt--;
           }
         }
    ans=max(ans,pt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n = int(input())

w = list(map(int, input().split()))

sum_l = 0
sum_r = 0
l = 0
r = len(w) - 1

for i in range(len(w)) :
    if sum_l <= sum_r :
        sum_l += w[l]
        l += 1
    else :
        sum_r += w[r]
        r -= 1

print(abs(sum_l - sum_r))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>

#define PI (3.14159265358979323846)
#define INF (1e+9)
#define DIV_NUM (1000000007)

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> input;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        input.push_back(tmp);
    }

    int count = 0;
    for (int i = 1; i < n-1; i++) {
        if (input[i - 1] < input[i] && input[i] < input[i + 1]) {
            count++;
        }
        else if (input[i - 1] > input[i] && input[i] > input[i + 1]) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}




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

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
template <typename T> constexpr T inf = numeric_limits<T>::has_infinity ? numeric_limits<T>::infinity() : numeric_limits<T>::max() / 4;

#define REP(i, stop) FOR(i, 0, stop)
#define FOR(i, start, stop) for (int i = start, i##_len = stop; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define COMP(key) [](const auto& a, const auto& b) { return a.key < b.key; }

template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& a) { return is >> a.first >> a.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& a) { for (T& x : a) is >> x; return is; }

void LOG(const int& x) { cerr << x << "\n"; }
template<typename T> void LOG(const vector<T>& a) { for (const T& x : a) cerr << x << " "; cerr << "\n"; }
template<typename T, std::size_t S> void LOG(const T (&a)[S]) { REP(i, S) cerr << a[i] << " "; cerr << "\n"; }
template<typename T, std::size_t S, std::size_t R> void LOG(const T (&a)[S][R]) { REP(i, S) { REP(j, R) cerr << a[i][j] << " "; cerr << "\n"; } }

i64 ceil(i64 a, i64 b) { return (a - 1) / b + 1; }
i64 gcd(i64 a, i64 b) { while (b != 0) { i64 t = b; b = a % b; a = t; } return a; }
i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
i64 gcd(const vector<i64>& v) { return accumulate(ALL(v), 1LL, static_cast<i64(*)(i64, i64)>(gcd)); }
i64 lcm(const vector<i64>& v) { return v.empty() ? 0LL : accumulate(v.begin() + 1, v.end(), v[0], static_cast<i64(*)(i64, i64)>(lcm)); }
i64 pow(i64 x, i64 y, i64 z) { i64 a = 1; while (y > 0) { if (y & 1) a = a * x % z; x = x * x % z; y /= 2; } return a; }
i64 inv(i64 x, i64 m) { return pow(x, m - 2, m); }

struct InitCpp { InitCpp() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } initCpp;

const i64 INF = inf<i64>;
using P = pair<i64, i64>;
const i64 M = 1000000007;
signed main() {
  i64 N;
  cin >> N;
  vector<i64> A(N);
  cin >> A;
  i64 sum = 0;
  REP(b, 61) {
    i64 odd = 0;
    i64 even = 0;
    for (i64 a : A) {
      if ((a >> b) & 1) {
        odd += 1;
      } else {
        even += 1;
      }
    }
    i64 add = odd * even % M * ((1LL << b) % M) % M;
    sum = (sum + add) % M;
  }
  cout << sum << endl;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {

	static Scanner scan = new Scanner(System.in);

	public static void main(String[] args) {
		long n = scan.nextLong();
		long m = scan.nextLong();
		long d = scan.nextLong();

        double ans = (m - 1) * (n - d) * 2;
        if (d == 0) {
            ans = (m - 1) * (n - d);
        }
        System.out.println(ans / Math.pow(n, 2));
    }
}


Measured memory_bytes: 22100