akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//ここまでテンプレ
int main(){
	int a,b;
	cin>>a>>b;
	if(a==0 || b==0 || (a<0 && 0<b))
		cout<<"Zero"<<endl;
	else if(0<b)
		cout<<"Positive"<<endl;
	else{
		if((b-a)%2==0)
			cout<<"Negative"<<endl;
		else
			cout<<"Positive"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using GRAPH = vector<vector<ll>>;
const string YES = "Yes";

void bfs(ll start, vector<ll>& prev, const GRAPH& G)
{
    queue<ll> que;

    prev[start] = 0;
    que.push(start);

    while (!que.empty()) {
        auto v = que.front();
        que.pop();

        for (auto e : G[v]) {
            if (prev[e] == -1) {
                prev[e] = v;
                que.push(e);
            }
        }
    }
}

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B)
{
    GRAPH graph(N+1);
    for (ll i = 0; i < M; i++) {
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }
    vector<ll> prev(N+1, -1);
    bfs(1, prev, graph);

    cout << YES << "\n";
    copy(begin(prev) + 2, end(prev), ostream_iterator<ll>(cout, "\n"));
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
#pragma GCC diagnostic ignored "-Wunused-result"
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> A(M);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, M, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 16048
#include <bits/stdc++.h>
using namespace std;
const int N=5e5;

  int n,c,k;
  int a[N];
void in()
{
  cin>>n>>c>>k;
  for (int i=0;++i<=n;)
    scanf("%d",a+i);
}

  int A,t,e;
void wor()
{
  sort(a+1,a+n+1);
  for (int i=0;++i<=n;)
    {
      if (a[i]>e||t==c)
        ++A,t=0,e=a[i]+k;
      ++t;
    }
}

void out()
{
  cout<<A;
}

int main()
{
  in();
  wor();
  out();
  exit(0);
}

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

int main() {
	int N, L;
    cin >> N >> L;
    int sum  = 0, mdis = abs(L);
    for (int i = L; i < L + N; ++i){
        sum += i;
        mdis = min(mdis, abs(i));
    }
    cout << (sum > 0 ? sum - mdis : sum + mdis)<< endl;
}

Measured memory_bytes: 256
def main():
    _ = input()
    a_list = sorted([int(i) for i in input().split()], reverse=True)

    height, width = None, None
    i = 0
    while (i != len(a_list)):
        a = a_list[i]
        j = i+1
        cnt = 1
        for j in range(i+1, len(a_list)):
            if cnt == 4: break
            b = a_list[j]
            if a != b:
                break
            cnt += 1
        if 1 < cnt and cnt < 4 and height == None:
            height = a
        elif 1 < cnt and cnt < 4 and width == None:
            width = a
            print(height*width)
            break
        elif cnt == 4 and height == None:
            height = a
            print(height*height)
            break
        elif cnt == 4:
            width = a
            print(height*width)
            break
        i = j
    if not height:
        print(0)
    

if __name__ == "__main__":
    main()

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

int main()
{
    int d, n, i, k=1;

    cin >> d >> n;

    for(i = 0;i < d;i++) {
        k *= 100; 
    }

    if(n == 100) {
        n = 101;
    }

    cout << k*n <<"\n";

    return 0;

}

Measured memory_bytes: 256
s=gets.chomp
n=2**s.size-1
res=0
for i in 0..n
    t=s.dup
    i.downto(0) {|j|
        s[j]=s[j]+?+ if i&(1<<j)>0
    }
    s+='-0'
    res+=eval s
    s=t.dup
end
p res/2


Measured memory_bytes: 2044
#include <bits/stdc++.h>
#include <limits>
#include <math.h>
#include <cmath>
#include <cctype>
#include <cstdio>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int> ;
using vs = vector<string>;
using vb = vector<bool>;
using vll = vector<long long>;
using vvll = vector<vector<long long >>;
#define PI 3.141592653
#define rep(i, k, n) for(ll i = k; i < n; i++)



int main(){
  string s, t;
  cin >> s >> t;
  ll n = s.size();
  ll ans = 0;
  rep(i, 0, n){
    if(s[i] != t[i]){ans++;}
  }

  cout << ans << endl;
}

Measured memory_bytes: 3916
#include <string>
#include <iostream>

using namespace std;

string reverse_seq(string str)
{
	string str_ = "";

	for(string::size_type i = 0; i < str.size(); i++)
	{
		str_ = str[i] + str_;
	}

	return str_;
}

int main()
{
	string str;

	cin>>str;
	
	cout << reverse_seq(str) << endl;
}

Measured memory_bytes: 1184
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

int n;

signed main(){
	read(n);
	write(n-1>>1);
}

Measured memory_bytes: 3596
def solve(n, s, mx):
    # print(n, s, mx)
    if n == 0:
        print(s)
    else:
        for i in range(mx):
            solve(n - 1, s + chr(ord("a") + i), max(mx, i + 2))

n = int(input())
solve(n - 1, 'a', 2)

Measured memory_bytes: 57176
#include<iostream>
#include<iomanip>
#include<functional>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<set>
#include<queue>
#include<cmath>

using namespace std;
#define LL long long
#define mod 1000000007

int K;
string S;

int main() {
	cin>>K>>S;
	if(K>=S.size())cout<<S<<endl;
	else{
		string tmp="";
		for(int i=0;i<K;i++)tmp+=S[i];
		tmp+="...";
		cout<<tmp<<endl;
	}

	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
void  solve(){
  int l;
  cin>>l;
  vector<pair<pair<int,int>,int>> v;
  int r=0,num=1;
  while(l>= num*2) num*=2,r++;
  int n=r+1;
  rep(i,1,r+1){
    v.pb({{i,i+1},(1<<(i-1))});
    v.pb({{i,i+1},0});
  }
  int st=num,en=l-1;
  int left= en-st+1;
  for(int idx=r;idx>=1;idx--){
    if(left<1<<(idx-1)) continue;
    v.pb({{idx,n},st});
    st+=(1<<(idx-1));
    left-=(1<<(idx-1));
  }
  cout<<n<<" "<<v.size()<<endl;
  rep(i,0,v.size()) cout<<v[i].f.f<<" "<<v[i].f.s<<" "<<v[i].s<<endl;
}
int main(){
    optimizeIO();
    solve();
}


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

int main(){
    string s;
    cin>>s;
    int n = s.size();
    int end = s.size()-1;
    vector<bool> used(26,false);
    for(int i=0;i<n;i++){
        used[s[i]-'a']=true;
    }
    //足すか減るか
    if(n<26){
        for(int i=0;i<26;i++){
            if(!used[i]){
                cout<<s<<char('a'+i)<<endl;
                return 0;
            }
        }
    }
    else{
        while(s[end]<s[end-1]){
            if(end==1) break;
            end--;
        }
        
        if(end==1){
            if(s[0]!='z'){
                cout<<char(s[0]+1)<<endl;
                return 0;
            }
            else{
                cout<<-1<<endl;
                return 0;
            }
        }else{
            char tmp = '~';
            for(int j=end;j<26;j++){
                if(s[end-1]<s[j]) tmp = min(tmp,s[j]);
            }
            cout<<s.substr(0,end-1)+tmp<<endl;
            return 0;
        }
        
    }
    
    return 0;
    
}

Measured memory_bytes: 3632
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var NAB = Sarray();
            var N = NAB[0];
            var MA = NAB[1];
            var MB = NAB[2];

            long[] Ai = new long[N], Bi = new long[N], Ci = new long[N];
            for (var i = 0; i < N; ++i)
            {
                var abc = Sarray();
                Ai[i] = abc[0];
                Bi[i] = abc[1];
                Ci[i] = abc[2];
            }
            var NONE = long.MaxValue / 2;
            var NMAX = 41;
            var AMAX = 420;
            var BMAX = 420;
            var dp = new long[NMAX, AMAX, BMAX];
            for (var n = 0; n < NMAX; ++n)
                for (var a = 0; a < AMAX; ++a)
                    for (var b = 0; b < BMAX; ++b)
                        dp[n, a, b] = NONE;
            dp[0, 0, 0] = 0;
            long asum = Ai.Sum(), bsum = Bi.Sum();

            for (var p = 0; p < N; ++p)
            {
                for (var a = 0; a <= asum; ++a)
                    for (var b = 0; b <= bsum; ++b)
                    {
                        if (dp[p, a, b] == NONE) continue;
                        dp[p + 1, a, b] = Min(dp[p + 1, a, b], dp[p, a, b]);
                        dp[p + 1, a + Ai[p], b + Bi[p]] = Min(dp[p + 1, a + Ai[p], b + Bi[p]], dp[p, a, b] + Ci[p]);
                    }
            }
            var ans = NONE;
            for (var n = 1; ; ++n)
            {
                if (asum < n * MA || bsum < n * MB) break;
                ans = Min(ans, dp[N, n * MA, n * MB]);
            }
            if (ans == NONE)
                WriteLine(-1);
            else
                WriteLine(ans);
        }
    }
}

Measured memory_bytes: 84848
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
from _collections import defaultdict
from functools import lru_cache

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True

def fact(n):
    arr = defaultdict(int)
    temp = n
    for i in range(2,Math.roundUp(int(n ** 0.5),1) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == []:
        arr[n] = 1
    return arr
MOD = int(1e09) + 7

def main():
    N = cin.int()
    S = defaultdict(int)
    for i  in range(1,N + 1):
        T = fact(i)
        for k,v in T.items():
            S[k] += v
    ans = 1
    for v in S.values():
        ans *= (v+1)
        ans %= MOD
    print(ans)
    return

if __name__ == "__main__":
    main()


Measured memory_bytes: 41196
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define forn(a,b,c) for(int a=b;a<=c;a++)
#define ford(a,b,c) for(int a=b;a>=c;a--)
#define f first
#define s second
typedef pair<int,int> pii;
const int N=3e3+5;
const int mod=998244353;
const ll inf=1e18+7;
int n;double p[N],dp[N][N];
int main()
{
    scanf("%d",&n);
    forn(i,1,n){
        scanf("%lf",&p[i]);
    }
    dp[0][0]=1;
    forn(i,1,n){
        forn(j,0,i){
            dp[i][j]=dp[i-1][j]*(1-p[i]);
            if(j>0)
                dp[i][j]+=dp[i-1][j-1]*p[i];
           // printf("dp[%d][%d]:%g\n",i,j,dp[i][j]);
        }
    }
    double ans=0;
    forn(i,1,n){
        if(i>n/2){
            ans+=dp[n][i];
        }
    }
    printf("%.10f\n",ans);
    return 0;
}

Measured memory_bytes: 68992
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
using namespace std;

int main(){
    int n;
    cin >> n;
    REP(i, n){
        double x1, x2, x3, y1, y2, y3, div;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        div = x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2);
        double r1, r2, r3, X, Y, R;
        r1 = x1*x1 + y1*y1;
        r2 = x2*x2 + y2*y2;
        r3 = x3*x3 + y3*y3;
        X = r1*(y2-y3) + r2*(y3-y1) + r3*(y1-y2);
        Y = r1*(x3-x2) + r2*(x1-x3) + r3*(x2-x1);
        X = X / div / 2;
        Y = Y / div / 2;
        R = sqrt((X-x1)*(X-x1)+(Y-y1)*(Y-y1));
        printf("%.3f %.3f %.3f\n", X, Y, R);
    }
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int>x;
    for(int i=0;i<n;i++){
        int r;
        cin>>r;
        x.push_back(r);
    }
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        int pos,value;
        cin>>pos>>value;
        int ans=0;
        for(int j=0;j<x.size();j++){
            if(j+1==pos){
                ans+=value;
            }else{
                ans+=x[j];
            }
        }
        cout<<ans<<endl;
    }
	return 0;
}


Measured memory_bytes: 256
#[allow(unused)]
use std::io::Write;

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn main() {
    // 1つの数字
    let n: usize = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_right().to_owned();
        s.parse().unwrap()
    };

    // for a in 1..10 {
    //     if n % a == 0 && n / a <= 9 {
    //         "Yes"
    //     }
    // }
    let ans = if (1..10).any(|a| n % a == 0 && n / a <= 9) {
        "Yes"
    } else {
        "No"
    };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	double w, h, x, y;
	cin >> w >> h >> x >> y;

	double ans = (w * h)/2;
	cout << fixed << setprecision(9) << ans;

	if(x == (w/2) && y == (h/2)) cout << " 1";
	else cout << " 0";
}	

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

int main() {
	int S,h,m,s;
	cin >> S;
	h = S / 3600;
	m = (S % 3600) / 60;
	s= (S % 3600) % 60;
	cout << h <<":"<<m<<":"<<s<< endl;
	return 0;
}


Measured memory_bytes: 3088
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
//  cout.precision(15); cout << fixed;

int main() {
  int n; cin >> n;
  vector<int> A(n);
  loop(i,0,n) cin >> A[i];
  sort(A.rbegin(), A.rend());
  int sum = 0;
  for (int i=0; i<n; i+=2)  sum+=A[i];
  for (int i=1; i<n; i+=2)  sum-=A[i];
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;

char s[10000];

int main()
{
	while(1)
	{
		int n;
		scanf("%d",&n);
		if(n == 0)
		{
			break;
		}
		long long int maxw = -10000000000000;
		long long int ms = 0;
		long long int now = 0;
		for(int i = 0; i < n; i++)
		{
			long long int w;
			scanf("%lld",&w);
			now += w;
			maxw = max(maxw,now - ms);
			ms = min(ms,now);
		}
		printf("%lld\n",maxw);
	}
	return 0;
}

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

int main() {
	int n;
	cin>>n;
	ll sum[n],sum2[n];
	for(int i=0;i<n;i++){
	    ll x,y;
	    cin>>x>>y;
	    sum[i]=x+y;
	    sum2[i]=x-y;
	}
	sort(sum,sum+n);
	sort(sum2,sum2+n);
	ll ans=max((sum[n-1]-sum[0]),(sum2[n-1]-sum2[0]));
	cout<<ans;
	return 0;
}


Measured memory_bytes: 6752
package main

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

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func maxInt64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumInt64(a []int64) int64 {
	var ret int64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcdInt64(m, n int64) int64 {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcmInt64(m, n int64) int64 {
	return m / gcdInt64(m, n) * n
}

// sort ------------------------------------------------------------

type int64Array []int64

func (s int64Array) Len() int           { return len(s) }
func (s int64Array) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s int64Array) Less(i, j int) bool { return s[i] < s[j] }

type xxx struct {
	x int
}

type sortArray []xxx

func (s sortArray) Len() int           { return len(s) }
func (s sortArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortArray) Less(i, j int) bool { return s[i].x < s[j].x }

// -----------------------------------------------------------------

var n int
var h, dp []int

func dfs(i int) int {
	if dp[i] != -1 {
		return dp[i]
	}
	if i == n-1 {
		return 0
	}
	if i+2 < n {
		dp[i] = min(dfs(i+1)+abs(h[i]-h[i+1]), dfs(i+2)+abs(h[i]-h[i+2]))
	} else {
		dp[i] = dfs(i+1) + abs(h[i]-h[i+1])
	}
	return dp[i]
}

func main() {
	n = readInt()
	h = make([]int, n)
	for i := range h {
		h[i] = readInt()
	}
	dp = make([]int, n)

	for i := 1; i < n; i++ {
		if i-2 >= 0 {
			dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
		} else {
			dp[i] = dp[i-1] + abs(h[i]-h[i-1])
		}
	}

	fmt.Println(dp[n-1])
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define forn for(int i=0;i<n;i++)
#define form for(int j=0;j<m;j++)
#define pb push_back
#define mp make_pair
#define sc second
#define f first
#define kek cout<<"\n"
#define all(v)        ((v).begin()), ((v).end())
#define pob pop_back()
const ll MOD=1e9+7;
const int INF=1e8;
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  int n;
  cin>>n;
  int k;
  cin>>k;
  double ans=0;
  double arr[n];
  vector<double> v(n);
  double sum=0;
  int x;
 forn
 {
      cin>>x;
      v[i]=v[i] = (x *(x + 1))/2*(1.0 / x);
 }
 for(int i=0;i<k;i++) ans+=v[i];
 sum=ans;
 for(int i=k;i<n;i++) {sum+=v[i]-v[i-k]; ans=max(ans,sum);}
 cout<<fixed<<setprecision(12)<<ans;
 return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define DEBUG2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<endl
// #define LOCAL
typedef long long ll;
class Solver{
public:
    static const int MAXN=17;
    int N,M;
    int G[MAXN][MAXN];
    int dp[1<<MAXN][MAXN];
    int sum[1<<MAXN];
    void solve(){
        ios::sync_with_stdio(false);
        cin>>N>>M;
        int tot=0;
        for(int u=0;u<M;++u){
            int a,b,c;
            cin>>a>>b>>c;
            --a;--b;
            G[a][b]=G[b][a]=c;
            tot+=c;
        }
        
        for(int s=0;s<(1<<N);++s){
            for(int u=0;u<N;++u){
                if((s&(1<<u))==0)continue;
                for(int v=0;v<N;++v){
                    if((s&(1<<v))==0)continue;
                    if(G[u][v]==0)continue;
                    sum[s]+=G[u][v];
                }
            }
            sum[s]>>=1;
        }
        memset(dp,0xff,sizeof(dp));
        dp[1][0]=0;
        for(int s=1;s<(1<<N);++s){
            for(int u=0;u<N;++u){
                if(dp[s][u]==-1)continue;
                for(int v=0;v<N;++v){
                    if(s&(1<<v))continue;
                    if(!G[u][v])continue;
                    dp[s|(1<<v)][v]=max(dp[s|(1<<v)][v],dp[s][u]+G[u][v]);
                }
                int msk=((1<<N)-1)^s|(1<<u);
                for(int k=msk;k;k=(k-1)&msk){
                    dp[s|k][u]=max(dp[s|k][u],dp[s][u]+sum[k]);
                }
            }
        }
#ifdef LOCAL
        for(int s=0;s<(1<<N);s++){
            for(int v=0;v<N;v++){
                cout<<dp[s][v]<<" ";
            }
            cout<<'\n';
        }
#endif
        int ans=0;
        for(int s=0;s<(1<<N);++s){
            ans=max(ans,dp[s][N-1]);
        }
        ans=tot-ans;
        cout<<ans;
    }
};
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    (new Solver())->solve();
}

Measured memory_bytes: 9472
import numpy as np
# dfsで全探索
n, m, x = map(int, input().split())
c = []
a = np.zeros((n, m))
for i in range(n):
    ll = list(map(int, input().split()))
    c.append(ll[0])
    a[i] += np.array(ll[1:])
    

ans = float("INF")
# 0: Not Buy 1: Buy
s = []

def dfs(s):
    global ans
    if len(s) == n:
        r = np.zeros(m)
        ra = 0
        for j, k in enumerate(s):
            if k == 0:
                continue
            r += np.array(a[j])
            ra += c[j]
        if min(r) >= x:
            ans = min(ans, ra)
        return
    b = s.copy()
    nb = s.copy()
    b.append(0)
    nb.append(1)
    dfs(b)
    dfs(nb)

dfs([])
if ans == float("INF"):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 27124
#!python3

# input
N = int(input())


def prime_factor(x):
    m = {}
    i = 2
    while i ** 2 <= x:
        while x % i == 0:
            if i in m:
                m[i] += 1
            else:
                m[i] = 1
            x //= i
        i += 1
    if x != 1:
        m[x] = 1
    return m


def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors


def main():
    m = prime_factor(N - 1)
    ans = 1
    for v in m.values():
        ans *= v + 1
    
    l = make_divisors(N)
    for x in l:
        y = N // x
        while y % x == 0:
            y //= x
        if y % x == 1:
            ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD 1000000007
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main(){
    int n,W;
    scanf("%d%d",&n,&W);
    vector<ll> dp(W+1);
    for(int i=0;i<n;i++){
        ll weight,value;
        scanf("%lld%lld",&weight,&value);
        for(ll weight_already=W-weight;weight_already>=0;weight_already--){
            dp[weight_already+weight]=max(dp[weight_already+weight],dp[weight_already]+value);
        }
    }
    ll ans=0;
    for(int i=0;i<=W;i++){
        ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 1024
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
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;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum[ohara], k, q;

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

  cin >> n;
  rep(i, n) {
    cin >> a[i];
    sum[a[i]]++;
  }
  rrep(i, 1, n + 1) { ans += (sum[i]) * (sum[i] - 1) / 2; }
  rep(i, n) {
    cnt = ans;
    cnt -= (sum[a[i]]) * (sum[a[i]] - 1) / 2;
    sum[a[i]]--;
    cnt += (sum[a[i]]) * (sum[a[i]] - 1) / 2;
    sum[a[i]]++;
    Cout(cnt);
  }
  return 0;
}

Measured memory_bytes: 7296
#include<stdio.h>
#include<string.h>
int main(){
    char s[100+1];
    char s_rev[100+1];
    int count=0;
    scanf("%s",s);
    for(int i=strlen(s)-1;i>=0;i--){
        s_rev[strlen(s)-1-i] = s[i];
    }
    s_rev[strlen(s)] = '\0';
    for(int i=0;i<strlen(s);i++){
        if(s[i]!=s_rev[i]){
            count=count+1;
        }else{
            
        }
    }
    printf("%d\n",count/2);
}

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

using namespace std;
typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main(){
//    random_device rnd;
//    mt19937 mt(rnd());
      cin.tie(0);
      ios::sync_with_stdio(false);

      int N;
      cin >> N;
      vector<string> str (N);
      int ans = 0;
      int begin_B = 0;
      int end_A = 0;
      int check = -1;
      for(int i = 0;i < N;i++){
          cin >> str[i];
          for(int j = 0;j < str[i].size()-1;j++){
              if(str[i].at(j) == 'A' && str[i].at(j+1) == 'B'){
                  ans++;
              }
          }
          bool dummy_A = true;
          bool dummy_B = true;
          if(str[i].at(0) == 'B'){
              begin_B++;
              dummy_B = false;
          }
          if(str[i].at(str[i].size()-1) == 'A'){
              end_A++;
              dummy_A = false;
          }

          if(dummy_A != dummy_B){
              check = 0;
          }
      }

      if(max(begin_B,end_A) == 0)check = 0;
      cout << ans+min(begin_B,end_A)+check << endl;
}


Measured memory_bytes: 768
from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
D = defaultdict(int)

for i in A:
  if D[L[i]] < i:
    D[L[i]] = i

INF = float("inf")
dp = [-INF]*(N+1)
dp[0] = 0

for i in range(1, N+1):
  for j in D.keys():
    if i-j >= 0:
      dp[i] = max(dp[i], dp[i-j] + 1)
    else:
      dp[i] = max(dp[i], -INF)

ans = ""
temp = N

while temp > 0:
  for i, x in sorted(D.items(), key=lambda x: x[1], reverse=True):
    if temp - i >= 0 and dp[temp-i] == dp[temp] - 1:
      ans += str(x)
      temp -= i
      break

print(ans)

Measured memory_bytes: 9624
#include<bits/stdc++.h>
typedef long long int ll;
#define endl '\n'
using namespace std;
ll dp[100009][105][2],D;
const ll mod=1e9+7;
string s;
ll solve(int i = 0, int sum = 0, bool tight = 1){
    if(i == s.size())
        return (sum%D==0);
    if(dp[i][sum%D][tight] != -1)
        return dp[i][sum%D][tight];
    ll ret = 0;
    for(int d = 0; d <= (tight ? s[i] - '0' : 9); d++)
        ret += solve(i + 1, (sum + d)%D, d == s[i] - '0' ? tight : 0);
    return dp[i][sum%D][tight] = ret%mod;
}

int main(){
    //ios_base::sync_with_stdio(false),cin.tie(NULL);
    memset(dp,-1,sizeof(dp));
    cin>>s>>D;
    ll ans=solve();
    ans--;
    ans=(ans+mod)%mod;
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 165120
h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(input())
r=[False]*h
c=[False]*w

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            r[i]=True
            c[j]=True
            
for i in range(h):
    if r[i]==True:
        for j in range(w):
            if c[j]==True:
                print(a[i][j],end='')
        print()

Measured memory_bytes: 4468
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var imp = Console.ReadLine().Split(' ');
            int plus = (int.Parse(imp[0])) + (int.Parse(imp[1]));
            int minus1 = (int.Parse(imp[0])) - (int.Parse(imp[1]));
            //  int minus2 = (int.Parse(imp[1])) - (int.Parse(imp[0]));
            int ast = (int.Parse(imp[0])) * (int.Parse(imp[1]));

            int[] ans = { plus, minus1, /*minus2 ,*/ ast };
            Array.Sort(ans);

            Console.Write(ans[2]);
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>

using namespace std;

const long long X = 100000;
long long n, base = 1;
long long a[100005];
long long b[800005];

bool f(long long p)
{
    long long now = X, ans = 0;
    for(long long i = 1; i <= 800000; i++) b[i] = 0;
    for(long long i = 0; i < n; i++)
    {
        long long t = base + now;
        b[t]++;
        while(t != 1) t /= 2, b[t] = b[t * 2] + b[t * 2 + 1];
        if(a[i] >= p) now++;
        else now--;
        long long lt = base, rt = base + now;
        while(lt < rt)
        {
            if(lt % 2 == 1) ans += b[lt], lt++;
            lt /= 2;
            if(rt % 2 == 0) ans += b[rt], rt--;
            rt /= 2;
        }
        if(lt == rt) ans += b[lt];
    }
    if(ans >= (n * (n + 1) / 2 + 1) / 2) return true;
    else return false;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%lld", &n);
    for(long long i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
    }
    while(base < n + X) base *= 2;
    long long lt = 0, rt = 1e9, mid, ans = 0;
    while(lt < rt)
    {
        mid = (lt + rt) / 2;
        if(f(mid)) lt = mid + 1, ans = mid;
        else rt = mid - 1;
    }
    if(f(lt) && lt == rt) ans = lt;
    printf("%lld", ans);
    return 0;
}


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


typedef long long ll;
int N, T, t[201010];
//-----------------------------------------------------------------------------------
int main() {
    cin >> N >> T;
    rep(i, 0, N) scanf("%d", &t[i]);

    ll ans = 0;
    rep(i, 1, N) ans += min(T, t[i] - t[i - 1]);
    ans += T;

    cout << ans << endl;
}

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

int main()
{
    ll N, W;
    cin >> N >> W;
    vector<ll> w(N), v(N);
    for (ll n = 0; (n < N); ++n) {
        cin >> w[n] >> v[n];
    }
    vector<vector<ll>> dp(N, vector<ll>(W+1, 0));
    for (ll cw = 0; (cw <= W); ++cw) {
        if (cw >= w[0]) dp[0][cw] = v[0];
    }
    for (ll n = 1; (n < N); ++n) {
        for (ll cw = 0; (cw <= W); ++cw) {
            dp[n][cw] = dp[n-1][cw];
            if (cw - w[n] >= 0) {
                dp[n][cw] = max(dp[n][cw], v[n] + dp[n-1][cw-w[n]]);
            }
        }
    }
    cout << dp[N-1][W] << endl;
    return 0;
}


Measured memory_bytes: 79360
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		a: usize,
		b: usize,
	}

	let mut ans = 0usize;
	for i in a..=b {
		let s = format!("{}", i);
		if s.chars().nth(0).unwrap() == s.chars().nth(4).unwrap() && s.chars().nth(1).unwrap() == s.chars().nth(3).unwrap() {
			ans += 1;
		}
	}
	println!("{}", ans);
}



Measured memory_bytes: 2184
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <unordered_set>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

using namespace std;

const int MOD = 1000000007;

bool broken[100000+10];
int dp[100000+10];


int main(void) {
  int n, m;
  scanf("%d%d", &n, &m);
  REP(i, m) {
    int p;
    scanf("%d", &p);
    broken[p] = true;
  }
  dp[0] = 1;
  REP(i, n) {
    if(!broken[i+1]) dp[i+1] = (dp[i+1] + dp[i]) % MOD;
    if(!broken[i+2]) dp[i+2] = (dp[i+2] + dp[i]) % MOD;
  }
  cout << dp[n] << endl;
  return 0;
}


Measured memory_bytes: 768
using System;
using System.Linq;
using System.Collections.Generic;

namespace PANASONIC2020
{
    class C
    {
        static void Main(string[] args)
        {
            var x = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var a = x[0];
            var b = x[1];
            var c = x[2];

            var d = c - a - b;

            if (4 * a * b < d * d && d > 0) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}


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

int main(){
    int n,ans=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n-2;i++){
        if(a[i]<a[i+1]&&a[i+1]<a[i+2]) ans++;
        else if(a[i]>a[i+1]&&a[i+1]>a[i+2]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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

class matrix {
	int row;
	int col;
	long long int **cells;
public:
	matrix(int row,int col);
	matrix* multiple(matrix *b);
	~matrix();
	long long int getCells(int r, int c);
	void setCells(int r, int c, long long int x);
	void input();
	void output();
private:
	long long int multiple_sum(matrix *a,matrix *b, int i, int j);
};

long long int matrix::getCells(int r, int c){
        return cells[r][c];
}
void matrix::setCells(int r, int c, long long int x){
        cells[r][c] = x;
}


matrix::matrix(int row, int col){
        this->row = row;
        this->col = col;
        cells = new long long int*[row];
        for(int i = 0; i < row; i++){
                cells[i] = new long long int[col];
        }
}
matrix* matrix::multiple(matrix *b){
	matrix* c = new matrix(this->row,b->col);
	for(int i = 0; i < c->row; i++){
		for(int j = 0; j < c->col; j++){
			c->setCells(i,j, multiple_sum(this,b,i,j));
		}
	}
	return c;
}
long long int matrix::multiple_sum(matrix *a,matrix *b, int i, int j){
	long long int sum = 0;
	assert(b->row == a->col);
	int m = a->col;
	for(int k = 0; k < m; k++){
		sum += a->getCells(i,k) * b->getCells(k, j);
	}
	return sum;
}


matrix::~matrix(){
        for(int i = 0; i < row; i++){
                delete[] cells[i];      
        }
        delete[] cells;
}

void matrix::input(){
	for(int i = 0; i < this->row; i++){
		for(int j = 0; j < this->col; j++){
			int data;
			cin >> data;
			this->setCells(i,j,data);
		}
	}
}
void matrix::output(){
	for(int i = 0; i < this->row; i++){
		for(int j = 0; j < this->col; j++){
			cout << this->getCells(i,j);
			if (j == this->col - 1){
				cout << endl;
			}else{
				cout << " ";
			}
		}
	}
}
int main(int argc, char *argv[]){
	int n,m,l;
	cin >> n >> m >> l;
	matrix *a = new matrix(n, m);
	a->input();
	matrix *b = new matrix(m, l);
	b->input();
	matrix *c = a->multiple(b);
	c->output();
	delete c;
	delete b;	
	delete a;
}

Measured memory_bytes: 3208
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		System.out.println(f(b) ^ f(a - 1));
	}

	private static long f(long a) {
		if (a % 2 == 0) {
			long n = a / 2;
			if (n % 2 == 1) {
				return 1 ^ a;
			} else {
				return a;
			}
		} else {
			long n = (a + 1) / 2;
			if (n % 2 == 0) {
				return 0;
			} else {
				return 1;
			}
		}
	}
}


Measured memory_bytes: 23252
H, W = list(map(int, input().split()))
M = [['.' for w in range(W)] for h in range(H)]
for h in range(0, H):
    M[h] = list(input())

Yoko = [[0 for w in range(W)] for h in range(H)]
Tate = [[0 for w in range(W)] for h in range(H)]
for h in range(0, H):
    for w in range(0, W):
        if M[h][w] != '#':
            if w > 0 and M[h][w - 1] != '#':
                Yoko[h][w] = Yoko[h][w - 1]
            else:
                c = 0
                for d in range(w, W):
                    if M[h][d] == '#':
                        break
                    c += 1
                Yoko[h][w] = c
for w in range(0, W):
    for h in range(0, H):
        if M[h][w] != '#':
            if h > 0 and Tate[h - 1][w] > 0:
                Tate[h][w] = Tate[h - 1][w]
            else:
                c = 0
                for d in range(h, H):
                    if M[d][w] == '#':
                        break
                    c += 1
                Tate[h][w] = c
mx = 0
for w in range(0, W):
    for h in range(0, H):
        c = Yoko[h][w] + Tate[h][w] - 1
        if c > mx:
            mx = c
print(mx)

Measured memory_bytes: 249992
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 100000000

typedef  long long ll;

using namespace std;

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}


void solve(void){
    int a,b,c,d,e,k;
    cin >> a >> b >> c >> d >> e >> k;
    if(e-a <= k) cout << "Yay!" << endl;
    else cout << ":(" << endl;

}

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


Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define dme cout<<-1<<endl;return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=1e9+7;
const llint big=1e16+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
lldo gethan(lldo r,lldo hi,lldo mg){//0<=hi<mg
	if(r<mg){mg=r;}
	lldo ans=0;
	ans+=mg*sqrt(r*r-mg*mg)/2;
	ans+=r*r*(acos(hi/r)-acos(mg/r))/2;
	ans-=hi*sqrt(r*r-hi*hi)/2;
	return ans;
}
lldo getsol(lldo r,lldo hi,lldo mg,lldo ta){
	lldo hit=sqrt(r*r-hi*hi);
	if(ta<=-hit){return gethan(r,hi,mg)*2;}
	if(ta>=hit){return 0;}
	lldo mgt=sqrt(r*r-mg*mg);
	if(-hit<=ta&&ta<=-mgt){
		//cerr<<"de"<<__LINE__<<endl;
		lldo tar=sqrt(r*r-ta*ta);//ta???x??§?¨?
		return gethan(r,hi,mg)*2-gethan(r,hi,tar)+ta*(hi-tar);
	}
	
	if(mgt<=ta&&ta<=hit){
		//cerr<<"de"<<__LINE__<<endl;
		lldo tar=sqrt(r*r-ta*ta);//ta???x??§?¨?
		return gethan(r,hi,tar)+ta*(hi-tar);
	}
	//cerr<<"de"<<__LINE__<<endl;
	return gethan(r,hi,mg)-ta;
}
int main(void){
	int i,j,n,r;cin>>n>>r;
	int taka[200]={0};//??????????????????0 ??§?\????????????¢??????
	for(i=0;i<n;i++){
		int x,w,h;cin>>x>>w>>h;
		for(int j=x+100;j<min(200,100+x+w);j++){
			//99,100????¢?????????????
			taka[j]=h;
		}
	}
	lldo bmax=101,bmin=0;
	for(int h=0;h<42;h++){
		lldo gen=(bmax+bmin)/2;
		lldo solars=0;
		for(i=100-r;i<100+r;i++){
			lldo hi=min(abs(100-i),abs(99-i));
			lldo mg=max(abs(100-i),abs(99-i));
			solars+=getsol(r,hi,mg,taka[i]-gen);
		}
		//cerr<<"de gen="<<gen<<"solars="<<solars<<endl;
		if(solars>(r*r*pai/2)){bmax=gen;}
		else{bmin=gen;}
	}
	cout<<fixed<<setprecision(20)<<(bmax+bmin)/2<<endl;
	return 0;
}

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

long long ncr(int n,int r){
    long long g = 1;
    for (int i=1;i<=r;i++){
        g *= (n-r+i);
        g /= i;
    }
    return g;
}

long long pow(int n,int p){
    long long  g = 1;
    for (int i=0;i<p;i++){g *= n;}
    return g;
}

int main() {
    int n, p,a,odd=0,even=0;
    long long g = 0, h = 0;
    cin >> n >> p;
    for (int i=0;i<n;i++){
        cin >> a;
        if (a % 2 == 1) {odd += 1;}
        else {even += 1;}
    }

    if (p%2 != 0 && odd == 0) {h = 0;}
    else {for (int i=odd%2;i<=odd;i+=2) {h += ncr(odd,i);}}
    g = h * pow(2,even);
    cout << g << endl;
    return 0;
}

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

int main()
{
  int k, n;
  cin >> k >> n;
  
  vector<int> a(n);
  for (int i = 0; i < n; i ++)
    cin >> a.at(i);
  
  vector<int> b(n);
  for (int i = 0; i < n - 1; i ++)
    b.at(i) = a.at(i + 1) - a.at(i);
  b.at(n - 1) = a.at(0) + k - a.at(n - 1);
  
  int sum = 0;
  sort(b.begin(), b.end());
  for (int i = 0; i < n - 1; i ++)
    sum += b.at(i);
  
  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 1792